[30 December 2007]

I’ve been wondering why there are no cycles longer than 4 steps in multiplication graphs.

I’m not sure that what follows counts as a reason, but it’s been interesting thinking about some properties of multiplication graphs, and the result is a chain of observations that runs like this:

1. Any number can be multiplied by any number, and produces exactly one result. So in each multiplication graph each node has one outgoing arc, and (in decimal graphs) there are exactly ten arcs.
2. Since each node has an outgoing arc, there are no dead ends: each path through the graph can be extended indefinitely. One step, two, …, nine, ten, eleven.
3. Since there are paths of length ten and greater, there must be cycles in the graph. (If a path of length n contains no cycles, then it is incident to n + 1 vertices. So any path of length ten that has no cycles must touch eleven different nodes. We only have ten nodes, so the path must necessarily contain a cycle.)
4. Multiplication of evens by evens, or evens by odds, produces even numbers. So in the even-numbered graphs (i.e. those for 0, 2, 4, 6, and 8), every arc points to an even digit. And in the odd-numbered graphs, arcs which start at even digits point to even digits.
5. Multiplication of odds by odds produces odds. So in odd-numbered graphs, arcs which start at odd digits point to odd digits. And these are the only arcs that point to odd-numbered nodes, in any (decimal) multiplication graphs. I repeat: no arcs ever run from even-numbered digits to odd-numbered digits. The even digits form a sort of black hole: once you get in, you never get out.
6. As a consequence, any cycle must either visit only even digits, or only odd digits. (If it starts on an even digit, then the path can never reach an odd digit. If the cycle starts on an odd digit, and then continues to an even digit, it can never get back to any odd digit, and therefore cannot get back to its starting point.)
7. So there is an upper bound on the length of cycles in decimal multiplication graphs: five (for the five even digits or the five odd digits). Any cycle of length five must visit either all five even digits or all five odd digits.
8. Multiplying any number by (a number ending in) zero produces (a number ending in) zero. So in any multiplication graph, the arc that starts at 0 goes to 0, creating a cycle of length 1. In other words, zero is also a kind of black hole.
9. Because zero is a black hole, no cycle of length > 1 through the even digits can visit the 0 node.
10. Any cycle of length 5 over the even digits must (as noted above in item 7) visit all the even digits, and thus must visit 0. But no cycle that visits 0 can have length > 1. So: no cycle of length 5 over the even digits can exist.
11. Multiplying a number ending in 5 by any number produces a number ending in either 0 or 5. (Or, equivalently, every arc beginning at 5 in any decimal multiplication graph goes either to 5 or to 0.) So the set {0, 5} is also a black hole.
12. Because {0, 5} is a black hole, no cycle of length > 1 through the odd numbers can visit 5.
13. Any cycle of length 5 over the odd digits must visit 5. But no cycle of length > 1 can visit 5. So: no cycle of length 5 over the odd digits can exist.

Points 6, 10, and 13 seem to prove that for decimal multiplication graphs, the upper bound on cycle length is four. (And in fact there are several cycles of length four, as may be seen by inspection.)

What about multiplication graphs for positional number systems with bases other than ten?

It seems obvious that zero will be a black hole in any positional number system, so there will never be cycles that cover all the digits in the system; for numbers written in base b, there’s an upper bound on cycle length of b – 1.

Also, if b is divisible by two, then the distinction between odds and evens will be visible in the final digit of any number written in base b, in which case there will be an upper bound on cycle length of b / 2, or possibly (b / 2) – 1.

More generally, whenever b is divisible by some number n, the set of multiples of n become a black hole and limit the length of cycles.

Several new questions now come up to occupy our thoughts.

In decimal notation, the fifth power of any number ends with the same digit as the number. Is this true of fifth powers in any positional notation? It seems unlikely.

But is there always, for any base, some power with this property? That is, for any base b is there a power p such that we can usefully write an exercise like the one from Oystein Ore from which we started?

Prove that in the [base b] number system, the [nth] power of any number has the same last digit as the number itself.

It seems plausible, but why should this be so?

And on closer examination, I find it’s not true. But why not?

Here’s the first counter-example I found. For octal numbers, there is no power with this property. In octal, no higher power of a number ending in 2 ends in 2; they all end in 4 or 0.

What property of the base determines (a) whether there is such a p, and (b) what the value of p is? (Conjecture: it has something to do with the factors and the prime factors of b. But what?)

[29 December 2007]

As mentioned elsewhere, I’ve been amusing myself reading Oystein Ore, Number theory and its history (New York: McGraw-Hill, 1948; reprint New York: Dover, 1988). I’m not making fast progress, because I’m stuck thinking about some implications of exercise 5 in section 2-3:

Prove that in the decadic number system the fifth power of any number has the same last digit as the number itself.

This has led me to spend time thinking about various kinds of graphs which seem somehow related to this problem and to the more general topics of number theory it illustrates.

Exponentiation graphs

Simplest are perhaps what I’ll call ‘exponentiation graphs‘, one graph for each decimal digit. They show what happens to the last digit of a number when it’s raised to a (non-negative, integral) power. (Brief digression. Yes, to be correct I should say “the last digit in the decimal representation of a number”, not just “the last digit of the number”. But the shorter form is shorter, and in context not really less clear. So if your inner pedant was wanting to correct me just now, please forgive me this informality. And if not, please forgive me for the eighty-three words it is costing me to tell my own inner pedant to put a sock in it.)

The exponentiation graph for the digit 3, for example, starts with (a node for) the digit 1 (which is the final digit of 3, or any number ending in 3, raised to the 0th power), then a node for the digit 3 itself (the first power), then 9 (for any number ending in 3, the square ends in 9), then 7, then 1 again.

Each exponentiation graph starts with (a node for) the digit 1, and in each we can trace a path n steps long to find the digit that will end the nth power of any number which ends in the digit for which the graph is constructed.

All ten of the graphs are drawn on a separate page, if you want them.

Multiplication graphs

Each exponentiation graph is actually just part of a larger graph, which shows for (numbers ending in) each digit d what the final digit x will be when that number is multiplied by a number ending in digit y: there is an arc from y to x.

The full multiplication graph for 3 is as follows; you can see that the exponentiation graph shown above is a subgraph of this.

These graphs I’ve also drawn; they are also on a separate page, if you want them. Thank heavens for graphviz!

Power graphs

We can imagine yet another kind of graph, which I’ll call a power graph. One power graph for each non-negative integer n; each graph has ten nodes 0-9, and in each case there is an arc from x to y if and only if a number whose last digit is x, when raised to the power n, produces a result whose last digit is y.

Drawing these is an exercise left for the reader and/or the future.

Ore’s question, recast

Ore’s exercise 2-3.5, translated into graph terms, amounts to this: prove that for each of the ten exponentiation graphs (or: each of the ten multiplication graphs), the paths starting at node 1 with length 1 and length 5 end up at the same node.

This will be true whenever there is a cycle of length 1, 2, or 4 starting from the node after 1 (which is always the node for the digit whose graph this is).

Or another formulation: prove that for the fifth-power graph, each node has an outgoing arc leading back to itself.

And now I can repeat the question that struck me when I started thinking about these graphs the other day: why do all the cycles in the multiplication graphs have length 1, 2, or 4? Why do none of them have length > 4?

I don’t know exactly what a satisfactory answer to this question will look like: what I want is an explanation, any explanation, that makes me say “Oh, right. Of course.“ (In the back of my mind, I’m remembering that morning when I first encountered the proof of the formula for the sum of the interior angles of a convex polygon, and the quiet click my mind made when I understood it. But I’ll take what I can get, click or no click.)

I do have some ideas. But this post is already longer than I intended, and what with drawing the pictures it has taken a lot longer to prepare than I expected. So my current attempts at understanding why there can’t be cycles of length > 4 will have to wait for another entry.