[8 April 2008]

I had another bad dream last night. Enrique came back.

“I don’t think you liked Cheney very much. Or Eric van der Vlist, either, judging from his comment. So I’ve written another conforming XSD 1.0 processor, in a different vein.” He handed me a piece of paper which read:

echo "Input not accepted; unknown format."

“This is Caspar,”

“Caspar as in Weinberger?”

“Hauser. As you can see, Caspar doesn’t have the security features of Cheney, but it’s also conforming.”

I should point out for readers who have not encountered the figure of Kaspar Hauser that he was a mysterious young man found in Nuremberg in the 1820s, raised allegedly without language or human contact, who never quite found a way to fit into society, and is thus a convenient focal point for meditations on language and civilization by artists as diverse as Werner Herzog, Paul Verlaine, and Elizabeth Swados.

“Conforming? I don’t think I want to know why you think so.”

“Oh, sure you do. Don’t be such a wet blanket.”

“I gather you’re going to tell me anyway. OK, if there’s no way out of it, let’s get this over with. Why do you think Caspar is a conforming XSD processor?”

“I’m not required to accept XML, right? Because that, in the logic of the XSD 1.0 spec, would impede my freedom to accept input from a DOM or from a sequence of SAX events. And I’m not required to accept any other specific representation of the infoset. And I’m also not required to document the formats I do accept.”

“There don’t seem to be any conditionals here: it looks at first glance as if Caspar doesn’t support any input formats.” (Enrique, characteristically sloppy, seems to have thought that Hauser was completely alingual and thus could not understand anything at all. That’s not so. But I didn’t think it was worth my time, even during a bad dream, to argue with Enrique over the name of his program.)

“Right. Caspar understands no input formats at all. I love XSD 1.0; I could write conforming XSD 1.0 processors all day; I don’t understand why some people find it difficult!”

Cycles in multiplication graphs

[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?)

Multiplication graphs, exponentiation graphs, power graphs

[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.

Exponentiation graph for the digit 3

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.

Multiplication graph for the digit 3

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.

An odd fact about fifth powers

[27 December 2007; crucial typo corrected, graphics added 29 December]

Over Christmas I got a copy of Oystein Ore’s book Number theory and its history (New York: McGraw-Hill, 1948; reprint New York: Dover, 1988).
In section 2-3, exercise 5 reads

5. Prove that in the decadic number system [i.e. using decimal numerals] the fifth power of any number has the same last digit as the number itself.

This is straightforward enough, if you’ve just read the preceding section. (My exposition isn’t as good as Ore’s, so I won’t try to explain it.)

But now consider a related problem.

For numbers n whose decimal representation ends in a particular digit d, we can make a little directed graph that makes it easy to calculate the final digit of any number multiplied by n. Each graph will have ten nodes, labeled 0 through 9, and there will be an arc from node i to node j if and only if multiplying n by a number ending in i produces a number ending in j.

For the digit 3, for example, we’ll have the arcs 0 → 0, 1 → 3, 2 → 6, 3 → 9, 4 → 2, 5 → 5, 6 → 8, 7 → 1, 8 → 4, and 9 → 7. Like this:

Exponentiation graph for the digit 3

And for the digit 5, there will be arcs from each odd-numbered state to state 5, and from each even-numbered state to state 0. And so on.
Like this:

Exponentiation graph for the digit 5

There ought to be a name for these graphs, but I don’t know of one. I’ll call them multiplication graphs.

Now, consider what problem 5 means in terms of these multiplication graphs. For the given number, we pick the appropriate graph. If we raise the number to the power 0, the result is a number whose decimal representation ends in ‘1’. (Because it’s always the number 1.) Call the state labeled ‘1’ the start state. A path of length 1 will always take us to the state named for the digit whose multiplication properties the graph represents: in graph 3, a path of length 1 takes us to state 3, in graph 7, a path of length 1 takes us to state 7. Call this state the ‘characteristic state’.

If we raise the number to the power n, the result will have a decimal representation ending in the digit we reach by following a path through the graph, beginning at the start state and having exactly n steps. Final digit of the square? Follow a path two steps long. Final digit of the fifth power? Follow a path five steps long.

So: in terms of multiplication graphs, exercise 5 amounts to proving that in each graph, a path of length 5 takes you to the same state as a graph of length 1. Or, equivalently, that there is a cycle of length 4, or 2, or 1, beginning at the characteristic state of the graph.

It’s clear that there must be cycles in the graphs, and that the cycles can’t have length greater than 10, since there are only ten states. It’s clear, after a moment’s thought, that any cycle must either hit only even numbers or only odd numbers, and so any cycle must have length less than or equal to 5.

In fact, however, the cycles are all for length 1 (in graphs 0, 1, 5, and 6), 2 (graphs 4 and 9) or 4 (graphs 2, 3, 7, 8).

Why are there no cycles of length 5?