When is a tree (large, woody plant) not a tree (connected acyclic graph)?

This has something or other to do with the topic of the previous post.

(The tree (?) is a crepe myrtle near the campus of North Carolina State University in Raleigh.)

The drawing below, brazenly swiped from a 1964 Martin Gardner column, illustrates the solution to a well-known puzzle. If you stack n bricks on a table, how far can you make them extend over the edge without toppling?

The answer given, for bricks of unit length, is one-half the nth harmonic number, the sum of the series 1/2 + 1/4 + 1/6 + 1/8 + … + 1/2n. Since this series diverges, the overhang can be as large as you please, given enough bricks (and a strong enough table).

In describing this result, Gardner uses the word “unbelievable,” and when I first read about it, that was my reaction too. It is one of those facts that are inescapably true, and yet still implausible. Now I learn that the truth is even stranger—that far larger overhangs can be achieved.

The overhang for the harmonic stack is approximately equal to 1/2 ln n; it turns out other stacks achieve an overhang on the order of the cube root of n. This is an enormous improvement. For a million bricks, the harmonic stack can’t get beyond 13.8 bricklengths, whereas the cube-root stack extends 100 bricklengths beyond the edge.

How is it done? I’m not telling. If you can’t figure out the trick, you’ll have to consult the links below.

The key idea in the alternative solutions has apparently been known for at least 20 years. (Actually, I’d be surprised if it wasn’t known to stonemasons centuries ago, as well as generations of children playing with wood blocks—but I don’t have a reference to support that conjecture.) Quite new, however, is the mathematical analysis showing exactly how large the overhang can be. Last year Mike Paterson of the University of Warwick and Uri Zwick of Tel Aviv University presented a paper at SODA (the Symposium on Discrete Algorithms) giving optimal solutions for n up to 30, and showing that the asymptotic rate of growth is n^1/3. Now Peterson and Zwick, along with Yuval Peres (Berkeley), Mikkel Thorup (AT&T Labs) and Peter Winkler (Dartmouth) have proved that order n^1/3 is the best that can achieved:

More specifically, we show that any n-block stack with an overhang of at least 6n^1/3 is unbalanced, and must hence collapse. Thus we conclude that the maximum overhang with n blocks is of order n^1/3.

Links: The 2006 Paterson-Zwick paper is here in the SODA proceedings (subscription required) and here in the arXiv. (It is also to appear in the American Mathematical Monthly.) The five-author proof is at the arXiv here.

This morning I am enjoying the benefits of jet lead. My watch says it’s 7:30, but the hotel-room clock reads 4:30, so I have a few hours free to lie awake and solve the world’s problems. As a warmup exercise I’m doing mental arithmetic. I’m dividing integers, and trying to figure out how I do it.

I know what got me started on this particular line of predawn predaydreaming. On the flight out here I was reading a paper on division by Eric Allender of Rutgers. Then yesterday I was reminded again of division’s divisiveness when I ran into a friend, Robert L. Constable of Cornell (another refugee from the Eastern time zone, who’s probably awake now too). Constable said something I found provocative—which is a little odd, because he was repeating my own words to me, from an article I wrote a while ago. Paraphrasing Constable paraphrasing me: We should count ourselves lucky that multiplication is a polynomial-time operation.

In the article I went on to elaborate:

If you are given two prime numbers, it’s easy to multiply them, yielding a bigger number as the product. But trying to undo this process—to take the product and recover the two unknown factors—seems to be much more difficult. We have fast algorithms for multiplying but not for factoring. Why is that?

The contrast between multiplying and factoring is indeed fascinating, but maybe not quite as dramatic as that passage suggests. In the first place, we don’t really know that factoring is difficult. At the moment I don’t have an efficient, polynomial-time factoring program installed on my computer, but I can’t prove that you don’t have one. It’s not even true that we have no fast algorithms for factoring. We do know of one such algorithm; it’s just that you need a quantum computer to run it.

In any case, factoring isn’t how I’m passing my time this morning; I’m dividing. The two things are related, of course; either of them might claim to be the inverse of multiplication. (If you stop people on the street and ask, “What’s the opposite of multiplying?” few of them would reply “factoring.”) We can think of division as lazy factoring, or factoring with a head start. Dividing 40321 by 29 looks like an easier task than factoring 40321. But just how easy is it to divide? Specifically, what is the complexity class of division? Is it one of those tough exponential problems, or can we count on doing it in polynomial time, even in the worst case?

Here’s the most elementary division algorithm: Find x ÷ y by counting how many times you can subtract y from x. Stop counting when x is less than y; the count at that point becomes the quotient, and whatever is left of x is the remainder. In other words:

function divide(x,y)
   q = 0
   while x ≥ y
      x = x - y
      q++
   return (q,x)   //quotient, remainder

The procedure requires exactly q subtraction steps, and so its time complexity is proportional to x / y. This sounds pretty good—a linear-time algorithm. Unfortunately, though, that’s not the proper way to measure the algorithm’s running time. The correct complexity is not a function of x or y or q but a function of the number of bits or digits in these quantities. And that means the repeated-subtraction algorithm is exponential; for an n-bit number, the running time is O(2ⁿ).

Of course no one really divides by repeated subtraction, even at five o’clock in the morning.

Like most of my contemporaries, I was exposed at a tender age to the algorithm known as long division, or guzzinta. I understand that this technique has now been dropped from the curriculum in many schools, to the disgust of educators who believe it’s immoral for youth to be spared any trauma their parents endured. Far be it from me to shirk my patriotic duty to torture children, but I’m actually glad that long division is being retired from the canon of skills that every educated person is expected to master. Part of my reason is that I never learned the trick very well myself, and I’m hoping to avoid embarrassment. But there’s also the fact that this is the first nontrivial algorithm most of us encounter in life, and it’s a really weird one. It makes for a rough and ragged introduction to the charms of algorithmic reasoning.

Here’s part of a worked example of long division from the Ask Dr. Math section of the Math Forum at Drexel University:

Let's divide 175 by 3:
      ______
    3 ) 175

We take the dividend (175) one digit at a time starting
at the left. If we tried to divide 1 by 3, we would get zero,
so let's skip that and use the first two digits, 17:

      ___5_
    3 ) 17
        15
        --
         2

What I did was to look through the multiplication
table for 3 (in my mind), looking for the biggest multiple
of 3 that is less than 17: 3, 6, 9, 12, 15, 18 - since 18 is
too big, we use 3 x 5 = 15.

It’s the bit about looking through the multiplication table in your mind that I find unsettling. Note that what’s involved here is not just a matter of using the familiar 10-by-10 multiplication table “in reverse.” When you multiply decimal numbers, you take each digit of the multiplier and the multiplicand, find the corresponding column and row in the table, and, presto, there’s the partial product at the intersection. Reversing this process would mean using the divisor to select a row in the table, finding the dividend in that row, then reading off the index of the column to determine a digit of the quotient. But, as Dr. Math notes, the dividend is generally not present in the table; you have to search for “the biggest multiple less than….” No such searching (or guessing) step is needed with multiplication.

I have another gripe with the long-division algorithm: It mixes up operations on numbers with operations on digits—on the written representation of numbers. The various multiplication and subtraction steps that enter into the long-division procedure are well-defined operations in arithmetic, but when you come to that business about “bringing down the next digit,” you’re manipulating arbitrary symbols rather than acting on numerical values. How would you express the “bringing down” step in terms of +, – and × operations? If you think this is a frivolous quibble, try writing a computer program to implement the long-division algorithm. At some points in the program you’ll want numbers to be numbers—things you can add, subtract and multiply—but at other points it’s more convenient to represent numbers as lists of digits, which are easy to select and move around but not so easy to combine numerically.

Okay. So now it’s six o’clock local time, the horizon is brightening, and I seem to have persuaded myself that division of integers is so awkward as to be all but impossible. And yet…. I have just divided 40321 by 29, getting a quotient of 1390 and a remainder of 11. My algorithm—though I hesitate to glorify it with that term—seems to be a crude mishmash of long-division and Newton’s method. I make guesses, do some trial multiplication, and use the sign and magnitude of the error to suggest a better guess. It works, but it’s not pretty, and I wouldn’t want to be teaching it to impressionable youth. There’s a faint whiff of nondeterminism about it, as if I were guessing the answer rather than calculating it.

Why is division so hard?

At times I feel this is a dumb question, and that the universe doesn’t owe us an answer to such questions. Some things are just harder than others; that’s the way the world works. We can count ourselves lucky that multiplication has a polynomial-time algorithm; we have no right to expect that our luck will hold when we turn to division.

But then I get to thinking about physical systems that multiply and divide, where the two operations seem perfectly symmetrical. An example is an electrical circuit governed by Ohm’s law.

If we attach the terminals of a voltmeter to opposite ends of a resistor, we observe Ohm’s law in the form E = IR: Voltage is equal to the product of current and resistance. If we install an ammeter in series with the resistor, we see the effects of the law I = E/R: Current is equal to voltage divided by resistance. If you prefer pipes to wires, you can do the hydraulic version of the experiment, and there are also lots of mechanical schemes, where the same principle is illustrated with levers, gears, pulleys and such. In all of these systems, nature seems to divide just as easily as it multiplies. Why can’t we do the same with pencil and paper, or transistors, or neurons?

Much of theoretical computer science is given over to questions just like these. Given a certain model of computation, how many operations are needed to solve a problem? If we were given some extra resource (randomness, perhaps, or quantum superposition), would that make the job any easier? Can we reduce one problem to another and thereby solve both of them with the same method?

In the case of division, the answers are in. Specifically, they’re in the paper by Eric Allender that got me started on this strange morning’s meditation. The conclusions are simply stated. Forget about those whiffs of nondeterminism; division, along with the other three arithmetic operations, is a member in good standing of the familiar and friendly complexity class P, made up of deterministic polynomial-time problems. Indeed, all four operations belong to a subclass of P called L, which consists of just those problems that can be solved by a deterministic algorithm in polynomial time and with a logarithmic amount of memory (or, again, with memory proportional to the number of digits in the input). [Correction: As Ryan Williams and Jonathan Katz point out in the comments: a logspace solution has to fit in an amount of memory proportional to the logarithm of the number of digits.] Allender narrows down the complexity of division still further: It belongs to a class called DLOGTIME-uniform TC⁰. If you want to know just what that means, I must send you off to Allender’s paper (PDF).

Putting multiplication and division in the same complexity class doesn’t mean they’re exactly equal in difficulty. Complexity theory adopts the amusing practice of ignoring all constant factors and all terms other than the fastest-growing one, so that a running time of, say, 10⁶n² + 1000n is considered the same as n². But in the case of multiplication and division this approximation is reasonably close to reality.

Most of the results on the complexity of division are quite recent. People have been dividing for millennia, but Allender’s paper is titled “The Division Breakthroughs,” and it describes results published within the past decade. For most of the history of Homo calculensis, we didn’t know how good we had it.

Should I be surprised to wake up in the morning and find out that division isn’t as hard as it seems? On the one hand, it’s common sense that division can’t be really, really hard, because we do it all the time, getting answers promptly and reliably. On the other hand, division algorithms are so ugly we have to hide them from the children. I don’t know what to think. My mind is divided.

Update 2007-10-11. In the comments, Jonathan Katz asks a very good question: How is division done on real computers? I wish I could give a detailed answer. Here’s what little I know.

Modern general-purpose processors come with built-in hardware for floating-point division. The most popular method seems to be an algorithm called SRT division, after D. Sweeney of IBM, J. E. Robertson of the University of Illinois and T. D. Tocher of Imperial College London, who independently came up with variations on the same theme in the 1950s. The underlying idea is not fundamentally different from long division, but there are a couple of tricks and tweaks to speed the process. Although the numbers are represented in binary, the calculation is usually done in radix 4, so that the quotient is calculated two bits at a time. Moreover, the quotient digits are not 0, 1, 2, 3 but –2, –1, 0, 1, 2; this choice of digits has the advantage that the multiplication steps in the algorithm can be implemented as simple shifts and negations. But with five possible quotient digits in radix 4, there is some ambiguity or redundancy: Some numbers can be represented in more than one way. This has to be resolved, and the answer converted to conventional notation, at the end of the operation.

What I find particularly intriguing is that the “whiff of nondeterminism” I thought I smelled in schoolbook division also turns up here. David L. Harris, Stuart F. Oberman and Mark A. Horowitz explain:

The key idea of SRT division is to guess the quotient digit based on a few of the most significant divisor and partial remainder bits, rather than computing it exactly. As long as the guess is close enough, the algorithm can correct on subsequent steps using redundant quotient digits.

From the Dorling Kindersley Eyewitness Travel Guide to the Pacific Northwest, page 218:

In spite of its name, False Creek is not a creek at all….

Hardware is hard, whereas software is soft; the people who named these things knew what they were talking about.

A while ago, I volunteered to help a friend upgrade the disk drive of an Apple iBook. My first clue that this was going to be a fun project was learning that we needed a special tool called a spudger just to pry open the case. As it turned out, the spudging part of the job wasn’t really that bad; the sleek, black, nylon implement worked quite smoothly. (But so did an old putty knife.) Following instructions , I removed 3 Torx screws, 41 Phillips screws, 1 magnet, 3 rubber feet, 2 greasy springs, 4 strips of sticky tape, the battery, the keyboard, the Airport card, the RAM shield, the lower case, the bottom shield, the DC-in board, the upper case, the top shield, a restraining bracket, and the hard drive. Then I plugged in the new drive and replaced the restraining bracket, the top shield, …, sticky tape, greasy springs, rubber feet, magnet, Phillips screws and Torx screws. Finally, all the parts were back in the box and the case was snapped together again where I had spudged it apart. But when I pressed the power button: Total absence of joy. I pressed it again: Not a peep from the speaker, not a glimmer of light in the screen. Yet again: Nothing but a blank stare.

My purpose in writing about this low point in my career as a high-tech handyman is not to rant about the frustrations of technology or our throwaway culture, where nothing’s worth fixing and nobody knows how to fix it anyway. On the contrary, I want to take a moment to marvel at the elegance and ingenuity of microelectronic technology. After all, it’s the wonder of our age.

I recently had occasion to pull an old book off the shelf: Introduction to VLSI Systems by Carver Mead (Caltech) and Lynn Conway (then Xerox PARC, now University of Michigan).

This is a hands-on, do-it-yourself guide to designing silicon chips—arguably the most complex artifacts ever created by human minds and hands. (When Mead and Conway were writing, “VLSI” meant thousands of transistors on a chip; now it’s hundreds of millions.) Intricate as the circuits might be, Mead and Conway leave you feeling that you can understand absolutely everything about them, from the physics of electrons drifting through doped silicon, to the operation of individual transistors and logic gates, to the organization of those gates into higher-level modules such as adders and shift registers, to the layout of the patterns for the various layers, to the process of fabrication. I’ve always been particularly fond of the colorful layout diagrams, which look nothing like engineering drawings and everything like textile patterns.

Things have changed somewhat since the late 1970s—the era of the circuits described by Mead and Conway. Chip layouts were then checked and documented by printing them out at enlarged scale with a multicolor pen plotter. Quite a few of those plots wound up decorating engineer’s offices. (Maybe that was their real purpose.) If you tried to make a similar plot of a modern chip layout, it would cover a square kilometer. Nevertheless, even though this book is 30 years out of date, it is still the guidebook I would choose to take with me on any visit to the world of digital devices.

In their preface, Mead and Conway write: “In any given technology, form follows function in a particular way.” Yet what’s most extraordinary about the design of silicon circuits is how function follows form. It’s magic: When you print those patterns of interwoven colored stripes onto the surface of a silicon wafer, they come to life! They become active agents rather than mere geometric figures, capable of computing—almost capable of thinking. It’s as if the printed words in a book began reading themselves aloud and commenting on the story in which they occur.

If it’s surprising that mere geometric patterns can be transformed into a computing machine, I sometimes find it equally astonishing that mere machinery can be made to compute. The objects of computation are abstract entities such as numbers, bits, sets, logical operations. These things all seem (to me) to have an existence independent of any specific physical embodiment. When I think of a logical formula—P AND (Q OR R), say—I don’t ordinarily have in mind the little series-and-parallel network of transistors that Mead and Conway would design to implement this function in nMOS technology. P, Q and R are variables, or truth values, not voltages and currents. So why does our universe offer this curious mapping between physical structures and computational ones? Why is it possible to build computers? Why do we need to build them? Why can’t we just compute with pure thought stuff?

A few years ago, if I had written a paragraph like the one above, I would now be awaiting a letter or a phone call from Rolf Landauer, a wonderfully irascible physicist at IBM, who would forcefully remind me that “Information is physical!” Landauer died in 1999, so I no longer have the benefit of his critiques, but I’ve just discovered that his views on this issue are very ably representing in the final chapter of Mead and Conway, a chapter I had not properly appreciated when I first encountered their book. They write:

Computation is a physical process. Data elements must be represented by some physical quantity in a physical structure, for example, as the charge on a capacitor or the magnetic flux in a superconducting ring. These physical quantities must be stored, sensed, and logically combined by the elementary devices of any technology out of which we build computing machinery.

I’m not going to try to argue the contrary proposition—that computation is an abstract, mathematical process, which just happens to be modeled accurately by certain physical events and structures—but I would like to register my ongoing puzzlement at this close correspondence between the world of atoms and the world of numbers. I can believe it’s true that information is physical, but at a deep level I don’t get why it’s necessary.

Consider this: Since 1994, thanks to Peter Shor, we’ve had an algorithm for efficiently finding the prime factors of integers. But the algorithm only works on a quantum-mechanical computer; with a computer built according to the principles of classical physics, all known factoring algorithms require an effort that grows exponentially with the size of the integer. Someday, when the novelty has worn off, this situation will seem perfectly natural and unremarkable, but for now I am still bothered by the hint of a link between number theory and the laws of matter and energy. In this context, the quantum computer seems like a spudger—an overly specialized tool that you wouldn’t need if things were designed properly in the first place.

Mead and Conway is a terrific book, but it offers no useful advice on reviving an unresponsive iBook. For that I made an appointment at the Genius Bar of the local Apple Store. Quoth the genius: “Nevermore.” The cost of the repair would exceed the price of a comparable new iBook.

But this story has a happy ending, much to my surprise. Having already turned my friend’s computer into a plastic brick, I couldn’t do much further damage by spudging around inside it. And even if I failed to bring it back to life, performing an autopsy might teach me something. Over the next week I became adept at stripping the machine down to bare boards in half an hour. It didn’t take long to identify the cause of death. A small white plastic socket in the northeast corner of the circuit board was wobbling like a loose tooth. Evidently I hadn’t been gentle enough when I disconnected a cable during my first disassembly. That cable goes to the power button.

I fixed it with Krazy Glue and clothespins. Hardware is hard, but it’s no match for a well-practiced spudger.

We learn so early in life about +, −, × and ÷ that we tend to see these operations as the unique foundation stones of arithmetic, on which everything else must be built. But there are other operators we can apply to pairs of numbers. In a paper recently posted on the arXiv, Shinji Tanimoto of Kochi Joshi University asks if there might be some operation that lies between addition and multiplication.

Here’s what between means. Suppose the operation exists, and assign it the symbol ◊. (Tanimoto chooses a different symbol, but that one is harder to encode in HTML.) Now, for all positive a and b:

if  a+b  <  a×b,   a+b  <  a ◊ b  <  a×b;

if  a+b  >  a×b,   a+b  >  a ◊ b  >  a×b;

if  a+b  =  a×b,   a+b  =  a ◊ b  =  a×b;

Can we actually find an operation that has these properties? As a strategy for searching, Tanimoto suggests looking at the various definitions of a mean. Associated with addition is the arithmetic mean, defined as (a+b)/2. Likewise multiplication has the geometric mean, √ab. The hypothetical new operation ◊ should also have an associated mean, which for all a and b would lie between the arithmetic and the geometric means of a and b. And such a mean does exist! It was studied at length by Carl Friedrich Gauss, who called it the arithmetic-geometric mean, or AGM.

The AGM is defined as the limit of an iterative process:

function agm(a, b) =
  if a == b return a
  else return agm( (a+b)/2, sqrt(a*b) )

Viewed as a computer program, this is one of those weird malformed algorithms that ought to run forever but actually—if a and b are finite-precision floating-point numbers—returns a value quite promptly. Gauss proved that the iterates of a and b converge on the same value; furthermore, that value is always between the arithmetic and the geometric means (in the sense of “between” given above).

So now we have a mean that lies between the arithmetic mean and the geometric mean. How do we get from there to a binary operator ◊ that interpolates between addition and multiplication? Consider the following two identities, where AM is the arithmetic mean and GM is the geometric mean:

a+b = AM(a, b) + AM(a, b)

a×b = GM(a, b) × GM(a, b)

These equations can be taken as definitions of the + and × operators; in other words, we can define addition and multiplication as the unique operations that make the identities valid. And we can write the same kind of equation for the ◊ operator and the AGM:

a◊b = AGM(a, b) ◊ AGM(a, b)

Again, the ◊ operation is to be defined as the unique operation that satisfies the identity. Tanimoto transforms this equation into the form:

AGM(1, (a◊b) ) = AGM(a, b),

which can be “solved for ◊” by iterative methods.

At this point a numerical example will help. Suppose a = 3 and b = 5. AGM(3, 5) evaluates to approximately 3.936, and so the ◊ operation needs to be defined in such a way that AGM(1, (3◊5) ) will also have the value 3.936. It turns out that AGM(1, 9) yields the correct result, and so it follows that 3◊5 must be equal to 9. Note that 3◊5 = 9 lies between 3+5 = 8 and 3×5 = 15, as required. Pretty cool, eh?

No doubt the ◊ operation will soon be added to the elementary-school curriculum, alongside the standard quartet of ambition, distraction, uglification and derision.

Update 2007-09-03: Please see the comments for important corrections.

Quantum computing gets a lot of attention, but we don’t hear much about quantum mathematics. The very idea is an affront to Platonist thinkers everywhere—those of us who consider the elements of mathematics to be independent of the physical universe. Is the truth of the Pythagorean theorem subject to the same uncertainty as the fate of Schrodinger’s cat? Surely the counting numbers 1, 2, 3,… should be the same in any universe, whether quantum or classical; indeed, if you’re a full-gospel, whole-Bible Platonist, you might well argue that those numbers existed even before there was a universe. (At the opposite extreme are the constructivists, who warn that the only numbers you can count on are those you have fingers for.)

Questions like these are easily settled by experiment: Just annihilate the universe, abolish space and time, and try doing a few sums in the void. I would put the proposition to the test right now except that I don’t want to miss this week’s episode of “1 vs. 100.”

Paul Benioff of Argonne National Laboratory has been thinking and writing about these issues for some time. A few weeks ago he posted a preprint on the arXiv titled “Space of quantum theory representations of natural numbers, integers, and rational numbers.” I’ve been struggling to understand that paper, along with a couple of earlier ones on the same theme (here and here). I’m still a long way from mastering this material, but here’s what I’ve made of it so far.

Even if you go along with the Platonist view that the true home of all things mathematical is an ideal realm outside of time and space, we don’t live in that realm. Whenever we want to do something with numbers (or other mathematical entities), we have to represent them somehow in this universe. We chalk them on the blackboard; we twiddle the beads of an abacus; we load patterns of bits into a computer memory; even mental arithmetic requires a mind, which in turn seems to require a body. Thus no one does mathematics without atoms and photons and other toys and tools of the physicist, and so perhaps it’s not utterly crazy to suppose that what we can accomplish in mathematics may depend to some extent on the laws of physics. All the evidence suggests that those laws are inescapably quantum mechanical.

Benioff argues that numbers have to be represented and manipulated in ways that accord with quantum principles; for example, all operations should be reversible, and they should enforce “unitarity,” meaning that the probabilities of all possible outcomes should sum to exactly 1. At the same time, it’s important that numbers behave like numbers: They have to obey familiar axioms of arithmetic, or they’re of no use to mathematics. In the case of the counting numbers (a.k.a. the natural numbers) we have to be able to add and multiply. For the integers (the natural numbers augmented with zero and negative values), subtraction must also be allowed. The rationals introduce division. And for all these kinds of numbers we should be able to determine if two numbers are equal, and put them in order if they are not.

Quantum computing is usually discussed in terms of qubits, or the quantum equivalent of binary digits. Benioff extends the discussion to qukits, the quantum equivalent of base-k digits. Think of a qukit as a black box that holds one of k values, but until you open the lid, you can’t be sure which value. Once you look inside, the uncertainty is resolved, and the box is found to contain a specific value. The question Benioff addresses is: How do you do arithmetic with such unruly numbers? If you can’t even be sure of what numbers you’re working with, how can you add or subtract them, or test them for equality? The answer, ultimately, is that you have to put up with a degree of uncertainty. In the quantum world, the commutative law of addition, a+b = b+a, is not a bedrock principle but a statement whose truth is a matter of probabilities.

Benioff presents a specific implementation of quantum-theoretical numbers, based on a two-dimensional lattice of qukits. Each number occupies its own row of the lattice, with the digits arrayed from left to right. For integers, a designated qukit (actually a qubit, since it has just two states) serves as a sign bit. For rationals, this special qubit also marks the position of the decimal point (or “k-al” point), separating the integer part from the fractional part. On first glance, this lattice of qukits doesn’t seem too different from the hardware of an ordinary computer, but the quantum nature of the qukits brings some peculiarities. For example, the result of every operation has to go into a newly allocated row of the lattice; you can never erase or overwrite an existing value, because quantum operations have to be reversible and cannot destroy information.

Benioff introduces a set of parameters for his numbering system: m and h are the coordinates of a number within the lattice of qukits, k is the base of the qukits, and g is a “gauge-fixing function.” This last item sounds quite arcane, but I think it has a fairly simple explanation. You can imagine a qukit as a vector that can point in any of k directions; the gauge-fixing function defines a reference direction from which all the others are measured.

Here’s a taste of what Benioff has to say about his quantum numbers:

Transformations (k, (m, h), g) → (k’, (m’, h’), g’) in the parameter set induce transformations in the representation space. These consist of unitary translations that move the qukit strings on the lattice, transformations that change states of strings of base-k qukits to states of strings of base-k’ qukits, and unitary gauge transformations for each k….

An interesting result is that the axioms and theorems for each of the three types of numbers [i.e., natural numbers, integers and rationals] are invariant under these transformations. They represent symmetries of the systems. This is the case even though the specific expressions of the axioms and theorems in terms of basic arithmetic relations and operations are different for different representations. This is like the situation in physics where the laws of physics are invariant under Lorentz transformations even though their specific expression in different reference frames may be different.

Another interesting result is that qukits q_k where k is a prime number function as elementary qukits. These are the “elementary particles” as far as quantum representations of numbers are concerned. Qukits where k is not prime can be considered as composites of the prime number q_k.

If you want to delve more deeply into these matters, I must send you to Benioff’s paper. Here I want to return to the broad question of whether this line of inquiry can really lead us to some kind of quantum mathematics, as opposed to an abstract version of quantum computing. Personally, I’m not quite persuaded, although I find the proposition intriguing.

In most of this work the focus is on the representation of numbers, rather than the numbers themselves—a preoccupation that seems more characteristic of computing than of mathematics. Interesting mathematical properties of numbers tend to be independent of their representation; for example, the number seven is a prime whether you write it in decimal notation as 7, in binary as 111 or as the Roman numeral vii. Of course you must choose some representation, and the choice can make a difference in what you can accomplish. Benioff points out that unary notation (in which seven becomes 1111111) is inherently less efficient than other schemes, because the amount of work expended in manipulating a number is proportional to the number itself rather than to the logarithm of the number. For similar reasons Benioff objects to building all of arithmetic on the successor function (n → n+1). But this fretting over efficiency again suggests a more computational than mathematical frame of mind. After all, unary numbers and the successor function are essential building blocks in theories of the foundations of mathematics, such as in the Principia Mathematica of Whitehead and Russell—who were blissfully unconcerned with efficiency.

If you accept that the physical representation of mathematical objects is a fundamental issue in mathematics, then it’s an easy step to the conclusion that any such representation has to be consistent with quantum principles. But is the mathematical imagination truly fettered by the bounds of the physical universe? Mathematicians routinely reason about objects and operations that have no explicit material representation—irrational numbers, for example, or Georg Cantor’s infinite sets. A century ago, in response to another challenge from those who wanted to fence in the scope of mathematics, David Hilbert defiantly proclaimed: “No one shall expel us from the paradise that Cantor has created for us.”

If I remain a tad doubtful about the mathematical status of quantum-theoretical numbers, I do think they offer an interesting perspective on quantum computing. So far, no one has succeeded in building a practical quantum computer with a large number of interacting qubits (or qukits). Technological skeptics contend it will not be done any time soon. Benioff’s work turns this argument on its head. Quantum computers are the only ones we can build, he says, because we live in a world where quantum physics is the law of the land. We may think we have classical computers, but that’s an illusion. We merely have quantum computers that are heavily biased toward specific classical outputs, but they always retain the possibility of delivering a quantum surprise. Usually we regard computing—whether it’s done with a machine or with pencil and paper—as an approximation to a mathematical ideal. If a calculation shows that a+b does not equal b+a, we don’t question the commutative law of addition; we look for a bug or an error. But maybe we need to consider the possibility that it’s the quantum computation that’s the ultimate reality, and the mathematical law is just our convenient and tidy approximation to it.

The story about young Gauss and his trick for summing an arithmetic series just won’t stop. My archive now includes 134 versions. Almost all the recent additions were discovered by Barry Cipra. (For a recap on what this is all about, see earlier bit-player postings here and here, or the American Scientist article here.)

I’ve also received an interesting e-mail from James Grant, developer of a Web site on Fibonacci:

… Fibonacci (better called Leonardo da Pisa) published the formula for adding a linear series in his pivotal book Liber Abaci in 1202, which persuaded Europe to use “Arabic numerals” (actually from India) instead of Roman numerals. He presents the method at the beginning of the 12th chapter. He also presents methods for calculating other series, including a series of squares.

Fibonacci does not claim to be the discoverer of these formulas. He credits Arab and Indian mathematicians.

I do not claim here that Gauss read Liber Abaci in time to impress his teacher. It seems quite fair to credit him with re-discovering this formula. I just think it’s important for us to be aware that the formula was known perhaps 1,000 years before Gauss sprang it on his teacher.

Here is part of the passage from Liber Abaci, transcribed from the translation of Lawrence E. Sigler (Springer-Verlag, 2002):

When you wish to sum a given series of numbers which increases by some given number, as increasing by ones, or twos, or threes, or any other numbers, then you multiply half the number of numbers in the series times the sum of the first and last numbers in the series, or you multiply half the sum of the first and last numbers in the series by the number of numbers in the series, and you will have the proposition. For example, I wish to sum 7 numbers that increase by threes from seven up to 31, namely 7, 10, 13, and so forth up to 31. The number of the aforesaid numbers is indeed 9, that is there are nine numbers in the aforesaid series, of which the first is the seven…. Therefore the sum of the extremes, namely the 7 and the 31 is 38; therefore if you multiply half the … 9 by the 38, or half the 38 by the 9, then the result is 171 for the sum of the posed series of nine numbers….

As Grant notes, Fibonacci is not the inventor of this method; it appears three centuries earlier in a manuscript attributed to Alcuin of York; furthermore, Don Knuth has pointed out that it can also be found in Archimedes. Among the early sources, however, Fibonacci makes the best effort at explaining the algorithm; other accounts merely state the problem and solution.

Among the 250 million Rubik’s cubes manufactured since 1980, how many lie abandoned in a scrambled state, having never regained their original configuration since being taken out of the box? Most of them, I would guess. Now comes word that those cubes might be restored to pristinity with a little less effort. The upper bound on the number of moves required to solve any state of Rubik’s cube has been lowered from 27 to 26. The result is reported by Daniel Kunkle and Gene Cooperman of Northeastern University in a preprint available here.

It’s well-known that Rubik’s cube isn’t really a toy or a puzzle but rather a group-theory machine in disguise. Each possible move, or twiddle—rotating a face by some multiple of 90 degrees—is a transformation that permutes the positions and orientations of the 26 “cubies.” From any position there are just 18 distinct nontrivial moves, but in various combinations they generate a total of 43,252,003,274,489,856,000 permutations. What is the maximum number of moves needed to transform any one state of the cube into any other? That’s the question Kunkle and Cooperman are addressing. In other words, they are looking for the longest shortest path.

In principle we could get the answer by exhaustive search. It would be done by constructing the “Cayley graph” for the Rubik group: a graph in which each possible configuration of the cube is represented by a node, and two nodes x and y are connected by an edge if some single move allows configuration x to be transformed into y. The most efficient solution for any state is the shortest path (i.e., sequence of edges) leading from that state to the node representing the solved state. The worst-case solution length for the entire puzzle is the maximum of the shortest solution paths for all the nodes. The Cayley graph approach was used by Cooperman and two colleagues to find the worst-case path for the 2 × 2 × 2 version of Rubik’s cube. The Cayley graph for this device has 88,179,840 nodes, and it turns out the longest paths within it have 11 steps. For the 3 × 3 × 3 cube, however, exhaustive search is just too exhausting.

To make the search feasible, Cubists have had to scale back their ambitions and accept an upper bound rather than a true maximum. First it was shown that the worst-case solution path cannot require more than 52 moves; then the bound was lowered to 30, and then 29; a year ago Silviu Radu got the number down to 27.

Kunkle and Cooperman’s strategy is to factor the problem into two pieces by segregating half-turn (180-degree) and quarter-turn (±90-degree) moves. The subgroup of states reachable by half-turn moves is quite small by Rubik group standards, with just 663,552 elements, and the number is further reduced to only 15,752 after various symmetries are eliminated. Calculating the best solution for each of these states took only about a day on an ordinary PC. The longest such paths have 13 steps.

The second phase of the analysis tackles the “cosets” of the half-turn subgroup. For each of the 663,552 positions reachable by making half-turns only, there are 65,182,537,728,000 additional positions reachable by making quarter-turn moves. Kunkle and Cooperman had to search for the longest shortest path connecting any two elements of this set. They exploited various symmetries to reduce the scope of the problem and devised fast algorithms for some of the basic steps in the calculation. Even so, they wound up running their computer program for 63 hours on 128 processors at the San Diego Supercomputer Center. At one point the data store for intermediate results ballooned to seven terabytes. At the end of the run, they found that the longest shortest path consisted of 16 moves.

Combining the two phases of this solution yields 13 moves for the half-turn part of the path and 16 moves for the coset part, for a total of 29 moves. This is not an improvement over the best existing result of 27. However, Kunkle and Cooperman found that the two-stage algorithm reports path lengths greater than 26 only for a comparative handful of states—about 14,000. By a brute-force search they were able to find solutions of length 26 or less for each of these states, and thereby established the 26-move bound overall. It’s possible that further brute-force searching will lower the limit further to 25 moves.

Other experiments done by Herbert Kociemba, Richard Korf and others have shown that most randomly selected cube states can be solved in 18 moves or less. Korf has conjectured that all configurations are solvable in about 20 steps. We’ll see whether this is true—but probably not soon.

Anthony G. Pakes of the University of Western Australia shines further light on the “factoidal” function, discussed earlier here on bit-player and in the May-June issue of American Scientist:

I found your article about factoid(n) very interesting, and I offer you some analytically derived facts about it.

I will denote factoid(n) by f(n). You probably realize that 2f(2) is the payout in the St Petersberg game, i.e. the payout if tossing a fair coin repeatedly shows the first head on toss number n. Its probability law is exactly known, so there is not much more to say about it.

For n=2, 3, …, there is a critical number t_n such that 1 = t₂ < t₃ < t₄ < …, and the moment of order t of f(n) is finite iff t < t_n. I have an explicit formula for this moment. I believe that, for large n, t_n is asymptotically proportional to 1/n log(n) (natural logs), but my ‘proof’ of this is not entirely rigorous.

The distribution tail of f(n) is indeed fat; it decays in proportion to t_n^–x. I have values of the constants of proportionality. In this respect the distribution of f(n) is similar to members of the stable domain of attraction with index t_n. Also, it is nothing like a lognormal law, which has finite moments of all orders.

There is a limit law too: log(f(n))/n log(n) converges in distribution to the standard exponential law. This confirms your remarks about the probability of f(n) being bigger than n!. It does indeed converge to 1/e. In fact the probability that f(n) > (n!)^x converges to exp(–x).

A couple of general remarks. There is a book devoted to Products of Random Variables: by J Galambos & I Simonelli, Marcel Dekker Inc., (2004). The stopping rule defining f(n) is quite different to the model considered by Reed and Hughes; in their case it is independent of their summand random variables. For f(n) it is defined by its random factors, although it is a stopping time. Finally, f(n) is a function. For each n, it is a function defined on some sample space which could be made explicit, but almost never is. Besides being a random variable, it differs from n! in that f(n+1) cannot be computed from f(n) simply by multiplying by another random variable; changing n changes the probability law of the factor random variables. The situation is very similar to triangular arrays studied in the general summation theory of independent random variables, infinite divisibility and related stuff.