This just in from Bill Gasarch: The quest for a rectangle-free four-coloring of the 17-by-17 grid is over. If you don’t know what that’s all about, and you’d like to find out, see Bill’s blog post from 2009 or my earlier comments (one, two, three).

The coloring above (along with several others) was found by Bernd Steinbach of Frieburg University and Christian Posthoff of the University of the West Indies. They win the $289 prize that Gasarch had offered for a solution.

Gasarch has posted more details on the Computational Complexity blog. But apparently we’re going to have to wait until May to learn how the coloring was found. The one interesting clue revealed so far is that the paper will be presented at the International Symposia on Multiple-Valued Logic.

Addendum 2012-02-11: For the benefit of those who don’t read the comments, I repeat a remark from reader Craig:

What I don’t like about this solution (or, indeed, the solutions to other related problems) is the arbitrariness. Is it not the case that you should be able to permute the rows and columns of any solution and arrive at a new solution? That being the case, I feel that you should be able to adjust the rows and columns here in order to highlight some kind of revealing pattern in the colouring.

Indeed, the matrix of dots shown above is one of (17!)² equivalent solutions. How should we choose one of those permutations to serve as a representative of the class?

Personally, I’m not optimistic about finding a “revealing pattern” in any of the 126513546505547170185216000000 permuted matrices. If there were some simple, concisely described rule governing the arrangement of the dots—other than the no-monochrome-rectangle criterion itself—then we could make use of that rule to find a solution, or at least to reduce the search space. When Steinbach and Posthoff reveal their secret method, maybe we’ll learn that such a rule exists, but I doubt it.

Even if we can’t make a pretty picture by permuting rows and columns, it would still be useful to have some canonical ordering, so that we could easily determine whether two arrays are members of the same equivalence class. I’m not sure how best to do that, but if we assign an ordering to the colors, we can at least sort them.

There is still some arbitrariness here. We have not dealt with the 4! orderings of the colors. Is there a smarter way to go about it?

I went to a magic show the other day. Nick Trefethen was giving a demo of Chebfun, a Matlab extension package he is building in collaboration with his Oxford students and colleagues. In the course of the talk, several mathematical rabbits were pulled out of numerical hats.

The key idea in Chebfun is to represent any function of a real variable by a polynomial approximation.

  >> f = chebfun('sin(x) + sin(x.^2)', [0 10]);
  >> plot(f)

That wiggly line looks like a graph of y = sin(x) + sin(x²), but that’s an illusion. What is being plotted here is a certain polynomial of degree 118 that happens to approximate sin(x) + sin(x²) with high precision.

As I understand it, the chebfun construction algorithm works something like this. First you select N+1 points in the interval where the function is defined, and construct the unique polynomial of degree N that passes through all the points. If the error of this approximation is below a threshold, you’ve found your chebfun. Otherwise, choose a larger sample of points and try again.

The sample points are not evenly spaced across the interval. They are Chebyshev points, whose distribution varies as a cosine function, denser at the extremes and sparser in the middle. In this case, the process converged with 119 Chebyshev points:

In one respect the example above is an easy one: The function is quite smooth. Here’s something more challenging:

  >> hat = 1-abs(x-5)/5;
  >> h = max(f, hat);
  >> plot(h)

This is where we pull the rabbit out of the hat—or at least several pairs of rabbit ears. To deal with the discontinuities sharp corners in this curve, the Chebfun system assembles 25 polynomial segments, each defined on a different interval. Some are linear, some of higher degree. But the entire structure is still treated as a single function, which can be operated on by other functions. For example, sum(h) calculates the integral over [0, 10], returning the result 8.598303617326401. And here’s the square root of those rabbit ears:

These are neat tricks, but why would one want to work with polynomial approximations to a function, rather than with the function itself? I’m too new to all this to answer that question with confidence, so I’ll quote the Chebfun Guide:

The aim of Chebfun is to “feel symbolic but run at the speed of numerics”. More precisely our vision is to achieve for functions what floating-point arithmetic achieves for numbers: rapid computation in which each successive operation is carried out exactly apart from a rounding error that is very small in relative terms.

For those who want to know more, I offer a few pointers:

The first published paper on Chebfun:

Battles, Zachary, and Lloyd N. Trefethen. 2004. An extension of MATLAB to continuous functions and operators. SIAM Journal on Scientific Computing 25:1743–1770. (PDF)

Trefethen’s argument favoring floating-point arithmetic over symbolic computation or exact rational arithmetic:

Trefethen, Lloyd N. 2007. Computing numerically with functions instead of numbers. Mathematics in Computer Science 1:9–19. (PDF)

A provocative account of why polynomial approximation is not as wonky as you may think:

Trefethen, Lloyd N. 2011. Six myths of polynomial interpolation and quadrature. Mathematics Today. (PDF)

Finally, Trefethen has a forthcoming book on Chebfun and related matters (which I have only just begun to read):

Trefethen, Lloyd N. To appear. Approximation Theory and Approximation Practice. (PDF)

Chebfun runs inside Matlab, the numerical computing environment from Mathworks. Chebfun itself has recently become open-source software (under a BSD license), but Matlab is proprietary. As far as I can tell, Chebfun does not not (yet?) run under Octave, the open-source alternative to Matlab.

The curious document above was produced sometime in the spring of 1980 by Don Knuth to show off the typographical prowess of his new programs, TeX and Metafont. The software was then being introduced to the mathematical community through the publication of TeX and Metafont: New Directions in Typesetting, and I was writing a news item about it for Scientific American. At the time it seemed like a quaint, quirky and quixotic project, worth a column of type in the magazine even if nothing came of it in the long run. I would not have guessed that 30 years later TeX would be the foundation of a huge software superstructure—and would still be a part of my own professional life.

TeX is not the oldest software still in widespread use, but it may be the most stable. In the core of the system—the typesetting engine—very little has changed since 1990. And there will be even fewer revisions going forward. The current version of TeX is 3.1415926. Knuth has decreed that on his death the version number should be set equal to π and no further changes should ever be made. “From that moment on, all ‘bugs’ will be permanent ‘features.’”

I think—though this is subject to interpretation—that what Knuth wants to protect from all future meddling is not the text of the program itself, or even the underlying algorithms and data structures, but rather its operational specification. His intent in freezing TeX is to ensure that the same input should always yield the same output. Specifically, any software that calls itself TeX is supposed to pass his TRIP test suite.

I am of two minds about this policy. Mind One agrees with Knuth’s declaration: “Let us regard these systems as fixed points, which should give the same results 100 years from now that they produce today.” It’s comforting to think that all the TeX documents I’ve written over the years will still be readable a century hence. But Mind Two reminds me that in practice I have trouble maintaining TeX documents even for a few months, much less decades or centuries. What about those presentations done with the foils class that stopped working after an upgrade and that I’ve never bothered to fix? Or the articles using the pstricks package that won’t compile under pdflatex? TeX itself may be a fixed point in the software universe, but everything else spins dizzily around it.

The skeptical Mind Two has another argument as well: Under Knuth’s edict it’s not just the TeX markup language that can’t change; it’s also the architecture of the system. Knuth created his flawless soufflés and dæmon diarrhœa at an ASCII terminal wired to a PDP-10, and the only way he could see the product of his labors was to walk down the hall and retrieve hard copy from the AlphaType machine. We are no longer accustomed to such barbarities. TeX has been hauled halfway into the world of modern computing. Front-end software such as TeXShop provides a pleasanter interface. But the core programs still run in batch mode, as they did in the Dark Ages. To make even the smallest change in a document, you still need to throw away all the existing output and run a whole file (or set of files) through the compiler tool chain. Sometimes you have to do it twice. Or four times. Isn’t this ridiculous in a world of event-driven, interactive, multithreaded software? Will we still have to press the Typeset button in 2111?

Mind One replies: Of course not. By then we’ll just throw Moore’s Law at it: Automatically rerun TeX n times for every keystroke in the editor.

At this point Mind Three pipes up. (Did I mention that I’m of three minds?) The problem here, she says, is not that we can’t or shouldn’t alter TeX. It’s the utterly depressing notion that we’re incapable of building anything better, and that TeX will still be the typesetter to beat after another century. Surely, if we just stand tippytoe on the shoulders of Don Knuth, we can see a little farther. Who was the architect who said that every great building should have a bomb in the basement, set to blow itself up after 50 years and thereby clear the land for something greater still? Let’s make a new improved TeX. We’ll call it TNT.

Minds One and Two pounce in unison: You think we haven’t thought of that? What about ε-TeX? NTS? ExTeX? What about LuaTeX…?

•     •     •

This trinitarian meditation was inspired by a blog post I stumbled upon last week, in which an entity named Valletta Ventures, publisher of TeXPad for the Macintosh, attempts to port TeX (and also LaTeX) to the iPad; in this venture, Valletta Ventures eventually concedes defeat. The failure could be blamed on the scrutineers at the Apple App Store, who insist that every iPad program must be bundled up in a single executable. (My current TeX /bin directory has 342 entries.) But even if we were to let Apple off the hook here, the project still seems truly quaint, quirky and quixotic. Mind One says you shouldn’t expect to run a system as large and complex as TeX on a puffed-up cellphone. But Mind Two says: Why not? The iPad probably has more computational oomph than Knuth’s 1980 PDP-10.

In the end my sympathies lie with Mind Three, who sees the barrier to putting TeX on the iPad not as a lost opportunity but as a thin, bright glimmer of hope on the horizon. Maybe this protected market—the walled garden of Cupertino—will induce some young genius to create the next great mathematical writing system, an iPad app so good it will induce envy in all of us poor TeX users.

Looking at the issue more broadly, I think we often value stability and reliability a little too highly, and innovation too lowly. The world of computer science is overpopulated by walking fossils—not just TeX but also Unix, the Intel 86 architecture, TCP/IP. Quoting myself:

What has everybody been doing for the past 35 years? Can it be true that technologies conceived in the era of time-sharing, teletypes and nine-track tape are the very best that computer science has to offer in the 21st century?

As a remedy for this situation, the bomb in the basement may be a bit extreme. But I wonder if we shouldn’t try something like a reverse patent, where the whole world gets free use of an invention for the first 17 years, but then there’s an escalating schedule of royalties or taxes for those who fail to come up with a brighter idea.

•     •     •

One final question. When Knuth counts LAZY FOXES in his typographic specimen, where does he get the peculiar number 854.9176302? I would have thought 85491.76320.

The area enclosed by a circle is πr². The volume inside a sphere is ⁴∕₃πr³. These are formulas I learned too early in life. Having committed them to memory as a schoolboy, I ceased to ask questions about their origin or meaning. In particular, it never occurred to me to wonder how the two formulas are related, or whether they could be extended beyond the familiar world of two- and three-dimensional objects to the geometry of higher-dimensional spaces. What’s the volume bounded by a four-dimensional sphere? Is there some master formula that gives the measure of a round object in n dimensions?

The text above is the opening paragraph of my new column in American Scientist. If you’d like to know how the story comes out, by all means go read the full column in the format of your choice: HTML, PDF, or ink-on-paper at better newsstands everywhere. For those in a hurry, here’s the gist in one equation, one code snippet and one graph:

The equation is the “master formula” mentioned above: Plug in the radius r and the number of spatial dimensions n, and you’ll get back the volume of the corresponding ball. (If the gamma function in the denominator is unfamiliar, think of it as a factorial that makes sense even when the argument is not an integer.)

        v[0, r_] := 1
        v[1, r_] := 2r
        v[n_,r_] := (2πr2/n) * v[n–2, r]

This version of the formula, given here in Mathematica notation, works only for integer n. It defines the volume of a 0-ball as 1 and the volume of a 1-ball as 2r. For larger n, the volume is calculated recursively: It’s 2πr²/n times the volume of a ball with the same radius in n–2 dimensions.

Finally, the graph shows the volume of a unit n-ball (i.e., r = 1) for values of n from 0 through 20. When I first saw these data, two things took me by complete surprise. First, I was perplexed to learn that the volume of an n-ball dwindles away to nothing as n gets large. Second, I was even more surprised that the relation is not monotonic but has a peak at finite n. If we consider only integer n, the unit 5-ball has the largest volume. If we allow the spatial dimension to become a continuous variable, the maximum is at approximately n = 5.26.

These facts still seem pretty weird to me. And, although they are hardly new discoveries—the formula cited above goes back to the middle of the 19th century—they seem not to be widely known. How come nobody ever told me about this stuff?

Well, it turns out somebody did tell me, long ago. A few days after the current issue of American Scientist was sent to the press, I came upon an old Martin Gardner column with the title “Circles and spheres, and how they kiss and pack.” Writing about the n-sphere (by which he means the same object I’m calling the n-ball), Martin remarks:

And something very queer happens to its n-volume as n increases. The area of the unit circle is, of course, π. The volume of the unit sphere is 4.1+. The unit 4-sphere’s hypervolume is 4.9+. In 5-space the volume is still larger, 5.2+, then in 6-space it decreases to 5.1+ and thereafter steadily declines. Indeed, as n approaches infinity the hypervolume of a unit n-sphere approaches zero!

These words were published in the May, 1968, issue of Scientific American. I was a faithful reader in those days and surely saw the column, but I retain no shred of memory.

In the same column Martin discusses another mind-boggler that I also mention. Consider this configuration of disks in a square:

The maroon disk in the middle, tangent to the four blue disks, has a radius of √2 – 1. In the analogous three-dimensional arrangement, with eight blue balls, the radius of the central maroon ball is √3 – 1; in n dimensions it is √n – 1. Now look at what happens when n = 9: The maroon ball, though still surrounded on all sides by blue balls, has expanded to a radius of 2 and thus reaches the edge of the enclosing cube. I learned of this conundrum from Barry Cipra, who gives an account of it in WHIMS I, the first volume in the AMS series What’s Happening in the Mathematical Sciences (1991). Barry wasn’t able to tell me anything about the provenance of the problem. Martin describes it as “an unpublished paradox discovered by Leo Moser,” a Canadian mathematician who died just a few years later. As far as I can tell, Moser never did publish anything about the problem. If anyone knows more about its origin, I’d be eager to hear about it.

A further note: The new American Scientist had not been out more than a day or two before I began getting letters arguing that the whole tale I’m telling is nonsensical because balls (or other shapes) that differ in dimension have volumes measured in different units. A unit 3-ball is neither larger nor smaller than a unit 2-ball, because one kind of volume is measured in cubic units and the other in square units. This issue is addressed in my column, though evidently not to the satisfaction of all readers. In retrospect, I think my discussion would have been clearer (and less controversial) if I had stated everything in terms of volume ratios rather than volumes. In other words, the numbers labeling the ordinate of the graph above should be understood as measuring the ratio of the volume of a unit n-ball to the volume of a unit n-cube. All measurements involve some such comparison, but in this case it’s really helpful to make it explicit.

I do believe that the curve in that graph is trying to tell us something important about geometry in higher-dimensional spaces. I have no clear idea what. Wisdom and insight are always welcome in the comments.

The ever-puzzling Peter Winkler offered three problems in the August Communications of the ACM:

1. Does every positive integer divide some number of the form 1{0,1}*—that is, a positive integer whose decimal representation includes no digits other than 0 and 1?

2. Does every positive integer divide a Fibonacci number?

3. Is there an odd perfect number (an odd integer equal to the sum of its proper divisors)?

Answers to Problems 1 and 2 have now been published in the September CACM, so I won’t worry too much about spoiling anyone’s fun with the discussion below. Still, if you’d like to take a crack at the first two problems, do so before you read on. (As for Problem 3, you needn’t worry about my giving away the secret.)

Winkler’s solutions are based on the pigeonhole principle. If you divide successive 1{01}* numbers or successive Fibonacci numbers by any fixed integer n, the remainders necessarily lie between 0 and n–1. Furthermore, the sequence of remainders repeats cyclically. For example, the Fibonacci numbers modulo 3 are:

0 1 1 2 0 2 2 1 0 1 1 2 0 2 2 1 0 . . .

The trick is to show that the cyclic sequence of remainders always includes zero. For details see Winkler’s solution page mentioned above. (CACM is behind a paywall, but I think these links will work for nonsubscribers.) A 2007 paper by Tanya Khovanova also explains what’s going on, and gives a couple of further enticing problems.

The pigeonhole argument answers the questions as posed, but it tells us very little about the structure of the solutions. Which 1{01}* numbers and which Fibonacci numbers are divisible by various integers n? Are there any interesting patterns in the results? I was curious, so I started computing.

The graph above shows the smallest 1{01}* numbers divisible by each n from 1 through 30. The standout pattern is the series of tall flagpoles for n a multiple of 9. It appears that 1{01}* numbers that include 9 among their divisors are rarities. I didn’t foresee this pattern, although I should have. It’s connected with the long-forgotten ritual of “casting out nines,” which in turn is based on the following fact: A decimal number is divisible by 9 if and only if the sum of its digits is divisible by 9. (Question: What are the smallest 1{01}* numbers divisible by 99 and by 999? Answers at the end of this article.)

Below is the analogous graph for Fibonacci numbers divisible by values of n between 1 and 30.

There are some interesting patterns here, too, but we need a bigger sample to see them clearly.

By the way, it’s important to notice that the ordinate axis of the Fibonacci graph gives the index of each Fibonacci number, not the Fibonacci number itself. I adopt this indexing convention :

The diagram below offers another way of looking at the mapping from integers n (on the left) to the smallest Fibonacci number F(m) divisible by n (on the right):

A few Fibonacci numbers are highly popular—notably F(12), F(24), F(30), F(60). Indeed, F(24) is the destination of 12 of the first 100 values of n. The reason for this clustering is not a deep mystery; Fibonacci numbers of the form F(6k) tend to be very “smooth” numbers, with an abundance of small factors. F(60) is equal to 1,548,008,755,920, a number that has 960 divisors. F(240) has more than 1.3 million divisors. These smooth numbers simply have more chances to be the smallest F(m) divisible by some n.

But the clustering also highlights an asymmetry. The solution of the Winkler problem says that we can draw a line from every n on the left to a specific F(m) on the right, the least Fibonacci number divisible by that n. What about the converse? Is every F(m) the least Fibonacci number divisible by some n? Can we draw a line from every F(m) on the right to some n on the left? The diagram as shown, which covers all n up to 100, has many gaps in the set of nodes on the right; for example, none of the numbers between F(61) and F(67) are among the smallest Fibonacci numbers divisible by an n ≤ 100. If we were to extend the computation to larger values of n, would all the gaps in the righthand column eventually be filled in? Let me state that question a little more formally: For every m, is there an n that divides F(m) but does not divide F(k) for any k < m?

This is a trick question. The answer is No because of F(2), which is “shadowed” by F(1), since F(1) = F(2) = 1. But F(2) is unique in this respect. If we set aside this one exception, is the statement true for all other F(m)? Now the answer is Yes, but trivially so. Every F(m) is divisible by F(m) itself, which cannot possibly divide any F(k) with k < m. (In the case of Fibonacci numbers that are prime, F(m) and 1 are obviously the only divisors.)

To avoid the trivial solution, we need to ask a more tightly constrained question, which I’ll phrase as a conjecture:

If F(m) has any divisors n with 1 < n < F(m), then at least one of those n does not divide any F(k) for k < m.

Is the conjecture true? If so, where do all those new divisors come from? What mechanism guarantees that every nonprime F(m) will introduce at least one divisor never seen before in the sequence of Fibonacci numbers? If the conjecture is false, then there are “unselfish” Fibonacci numbers that share all their proper divisors with their smaller siblings, keeping none for their own exclusive use. What is the smallest such unselfish F(m)? (For what it’s worth, a computational search shows that any counterexample to the conjecture must lie beyond F(382).)

I’m going to leave this question as a challenge. I’ll give an answer in an update—in the unlikely event that no one posts a complete solution in the comments section in the next 10 minutes. One further note: Unselfish numbers do exist among the 1{01}* numbers; the smallest example is 1111, whose only proper divisors are 11 and 101, both of which obviously divide lesser 1{01}* numbers. Thus if you want to assert that Fibonacci numbers behave differently in this respect, you might want to think about what distinguishes the two sequences.

Finally, more about patterns of divisibility in Fibonacci numbers. The dots in the figure below show the least m such that n divides F(m) for all n up to 1,000:

It’s interesting that the dots tend to line up along certain rays, namely those whose slope is a ratio of small integers. The slopes m/n = 1 and 1/2 are the most clearly delineated, but there are also aggregations detectable by eye at m/n = 1/4, 1/3, 2/3, 3/4 and 3/2. The ray at m/n = 2 has only four data points on it in the range up to n = 1,000, but it is significant for another reason: It marks the absolute boundary of the m/n ratio. In other words, not only is it true that every n divides some F(m), but furthermore the m in question is never greater than 2n.

There is no sign of such radial streaks or other distinctive patterns in the equivalent graph for the 1{01}* numbers:

As with the Fibonacci graphs, the vertical axis here represents not the numerical magnitude of an 1{01}* number but its index within the sequence. For example, the smallest 1{01}* number divisible by 18 is 1,111,111,110, which is the 1,022nd number in the 1{01}* sequence. (It’s more than coincidence that 1111111110₂ = 1022₁₀.) Hence there’s a dot at n = 18 and vertical coordinate 1,022. I have colored orange all the dots associated with n that are multiples of 9. The dots along the upper margin of the graph are off-scale and actually belong at much higher elevations. For example, the dot for n = 99 should be at height 262,143 (the index of 111,111,111,111,111,111). The dot at n = 999 belongs at height 134,217,727 (the index of 111,111,111,111,111,111,111,111,111).

Update 2011-10-09: More than a month ago I promised an answer to the question posed above: Is there a composite Fibonacci number for which all the proper divisors are also divisors of smaller Fibonacci numbers? When I asked the question, I had an answer for it. But a week later when I sat down to write up the proof, it fell apart like wet tissue. Since then the problem has been constantly with me. I’ve been waking up with it in the morning; I go to bed with it at night; it comes back to visit at idle moments during the day. Several times I’ve thought I had found a solution, but then the argument fell to pieces again. If some kindly reader had posted a full proof in the comments, I could have responded, “Yes, yes, exactly so. That’s just what I had in mind.” But only one reader came to my rescue (thanks, unekdoud!); although that suggestion seemed to be heading in the right direction, I wasn’t able to fill in all the details.

Now I have yet another proof. It’s the middle of the night as I write this, but I’m going to stay up and get this posted before the idea disintegrates again.

Here, copied from above, is a more precise statement of the problem, phrased as a conjecture:

If F(m) has any divisors n with 1 < n < F(m), then at least one of those n does not divide any F(k) for k < m.

I claim the conjecture is true, based on this assertion: If every divisor of F(m) also divides some smaller F(k), then the F(k) in question cannot be greater than F(m/2), while at least one of the divisors must be no smaller than √F(m). But this is impossible, because √F(m) > F(m/2) for all m > 2. (For odd m, take the ceiling of m/2.)

The key to the proof is again the cyclic pattern of remainders observed when the members of the Fibonacci sequence are taken modulo an integer. In particular, if an integer a divides F(m), then a also divides F(2m), F(3m), F(4m), . . .   For example, F(8) = 21 is divisible by 3 and 7, and these numbers are also divisors of F(16) = 987 and F(24) = 46,368.

An immediate consequence of this cyclic structure is the remarkable fact that F(k) divides F(m) if and only if k divides m. Again let me cite an example: F(15) = 610 is divisible by F(3) = 2 and by F(5) = 5 and by no other Fibonacci numbers. (The prime factors of 610 are 2, 5 and 61. Note that the factor 61 divides no smaller Fibonacci number, and so F(15) is a confirming instance of the conjecture.)

A further observation is that if m is prime, then F(m) cannot be divisible by any Fibonacci number.

Let’s look at the divisors of F(m) for composite values of m. We know that such divisors exist. They include every F(k) for which k divides m, as well as all the proper divisors of each such F(k). Suppose, contrary to the conjecture, that these known divisors comprise all the divisors of F(m). Then for each integer a that divides F(m) we can ask which F(k) it also divides. Actually, a given a might divide many F(k), but consider just the smallest member of this set. If a divides this minimal F(k), then it also divides F(2k), F(3k), and so on, but it divides no other Fibonacci numbers. Thus F(m) must be a member of this series, or in other words m must be a multiple of k. The smallest such multiple is m = 2k. This gives us half of the proof: If a divisor of F(m) also divides F(k), k can be no larger than m/2.

The second half is easier. Divisors come in pairs; they are integers a and b such that ab = F(m). Furthermore, if a ≤ √F(m), then b ≥ √F(m). Thus we conclude that b cannot be less than the square root of F(m) or more than F(m/2)—a contradiction.

The same reasoning applies with even greater force in the case of prime m. If we imagine that a divisor of F(m) is also a divisor of some smaller F(k), we are driven to the conclusion that k divides m, which can’t be so for prime m.

In the course of working all this out in my bumbling-stumbling way, while making lots of lists of Fibonacci numbers and their divisors, the patterns I was seeing suggested a slightly stronger conjecture:

Every Fibonacci number that is not a perfect power has at least one prime factor that appears in no smaller Fibonacci number.

The perfect-power exception excludes exactly five Fibonacci numbers: F(0) = 0, F(1) = 1, F(2) = 1, F(6) = 8 = 2³ and F(12) = 144 = 12². No other Fibonacci numbers are perfect powers; I find it interesting that this fact was proved only in the past few years, and only with the use of industrial-grade mathematical machinery. On the other hand, “my” conjecture was proved almost a century ago by the American mathematician R. D. Carmichael. If I had known that fact a few weeks ago, I would have slept better. But maybe learned less.

In simple games, one can calculate the exact probability of every outcome, and so the expected winnings can also be determined exactly….

When I wrote the words above in a recent American Scientist column, I didn’t think I was saying anything controversial. So I was taken by surprise when a reader objected to the very notion of exact probability. My correspondent argued that probabilities can never be determined exactly, only measured to within some error bound. He also ruled out the use of limits in defining probabilities, allowing only finite processes. After a brief correspondence with my critic, I set the matter aside; but it keeps coming back to haunt me in idle moments, and I think I should try to clarify my thoughts.

The “simple games” I had in mind were those based on coin-flipping or dice-rolling or card-dealing. For example, I would say that the exact probability of getting heads when you flip a fair coin is 1/2. (Indeed, that’s how I would define a fair coin.) Likewise the exact probability of rolling a 12 with a pair of unbiased dice is 1/36, and the exact probability of dealing four aces from a properly shuffled deck is 1/270,725. The arithmetic behind these numbers is straightforward. You’ll find a multitude of similar examples in the exercises of any introductory textbook on probability. The trouble is, if you ask me to show you a fair coin or an unbiased die or a properly shuffled deck, I can’t do it. I certainly can’t prove that any specific coin or die or deck has the properties claimed. So my critic has a point: Those exact probabilities I was talking about come from a suppositional world of ideal randomizing devices that don’t exist—or can’t be shown to exist—in the physical universe.

Of course mathematics is full of objects that we can’t construct out of Lego bricks and duct tape—dimensionless points, the real number line, Hilbert space. Just as I can’t exhibit a fair coin, I can’t show you an equilateral triangle—or rather I can’t draw you a triangle and then prove that the three sides of that particular triangle are equal. The existence of perfect circles and right angles and other such Platonic apparatus is something we just have to accept if we want to do a certain kind of mathematics. I’m happy to view the fair coin in this light—as a hypothetical device that comes out of the same cabinet where I keep my Turing machines and my Cantor sets. The question is whether we can (or should) take the more radical step of banishing such idealized paraphernalia altogether.

Suppose we insist that the only way of determining a probability is to measure it by experiment. Take a coin out of your pocket and flip it 100 times; if it comes up heads 55 times, then p(H) = 0.55. But when you repeat the experiment, you might get 51 heads, suggesting p(H) = 0.51. Or maybe you would now conclude that p(H) = 0.53. Or you might adopt some other method of inferring a probability from the experimental evidence, something more sophisticated than just taking the mean of a sample. There’s an elaborate and highly developed technology for just this purpose. It’s called statistics, and it works wonders. Still, to the extent that the assigned probability depends on the outcome of a finite number of trials (and remember: taking limits is out of bounds), we’re never going to settle on a single, definite and immutable value for the probability.

Alan Hájek, in an article in the Stanford Encyclopedia of Philosophy, calls this approach to probability “finite frequentism.”

Where the classical interpretation [i.e., the probability theory of Laplace, Pascal, et al.] counted all the possible outcomes of a given experiment, finite frequentism counts actual outcomes. It is thus congenial to those with empiricist scruples. It was developed by Venn (1876), who in his discussion of the proportion of births of males and females, concludes: “probability is nothing but that proportion.”

Hájek calls attention to several worrisome aspects of this doctrine. Most of the problems take us right back to where this discussion began, namely to the fact that we can never learn the exact probability of anything. And this ignorance leads to awkward consequences. In the standard calculus of probabilities, we know that if an event occurs with probability p, then two independent occurrences of the same event have probability p². How do we apply this rule in an environment where p changes every time we measure it? I suppose a stalwart empiricist might reply that if you want to know p(HH), then that’s what you should be measuring. The empiricist might also point out that the loss of the calculus is not a defect of the theory; it’s just the human condition. We really are ignorant of exact probabilities, and we’ll only get into trouble if we pretend otherwise.

We could adopt a new calculus based on probabilities of probabilities, in which p(H) is not a number but a distribution—maybe a normal distribution determined by the mean and variance of the experimental data. Then p² becomes the product of two such distributions. But beware: The shape of that normal curve we’ve just smuggled into our reasoning is defined by a process that involves the moral equivalent of flipping a fair coin, not to mention taking limits. Maybe we should instead use a discrete, experimental approximation to the normal distribution, created with a physical device such as a Galton board.

•     •     •

Reading on in Hájek’s long encyclopedia article, I find that the finite frequentists are not the only school of thought subject to withering criticism; Hájek finds deep flaws in every interpretation of probability theory, without exception. (That’s a philosopher’s job, I guess.)

Joseph Doob, writing 15 years ago in the American Mathematical Monthly, took the position that we have a perfectly sound mathematical theory of probability (formulated mainly by Kolmogorov in the 1930s, and founded on measure theory); the only problem is that it doesn’t connect very well with the world of everyday experience. I would like to quote at length what Doob has to say about the law of large numbers:

In a repetitive scheme of independent trials, such as coin tossing, what strikes one at once is what has been christened the law of large numbers. In the simple context of coin tossing it states that in some sense the number of heads in n tosses divided by n has limit 1/2 as the number of tosses increases. The key words here are in some sense. If the law of large numbers is a mathematical theorem, that is, if there is a mathematical model for coin tossing, in which the law of large numbers is formulated as a mathematical theorem, either the theorem is true in one of the various mathematical limit concepts or it is not. On the other hand, if the law of large numbers is to be stated in a real world nonmathematical context, it is not at all clear that the limit concept can be formulated in a reasonable way. The most obvious difficulty is that in the real world only finitely many experiments can be performed in finite time. Anyone who tries to explain to students what happens when a coin is tossed mumbles words like in the long run, tends, seems to cluster near, and so on, in a desperate attempt to give form to a cloudy concept. Yet the fact is that anyone tossing a coin observes that for a modest number of coin tosses the number of heads in n tosses divided by n seems to be getting closer to 1/2 as n increases. The simplest solution, adopted by a prominent Bayesian statistician, is the vacuous one: never discuss what happens when a coin is tossed. A more common equally satisfactory solution is to leave fuzzy the question of whether the context under discussion is or is not mathematics. Perhaps the fact that the assertion is called a law is an example of this fuzziness.

Note that the coins Doob is tossing seem to be drawn from the Platonic closet of ideal hardware.

None of my reading and pondering has made me a convert to finite frequentism, but at the same time I am grateful for this challenge to my easygoing confidence that I know what probabilities are and how to calculate with them. I surely know nothing of the sort. And on balance I think it might be a good idea if introductory accounts of probability theory put a little more emphasis on calculating from real-world data, with less reliance on fair coins and unbiased dice. In this connection I can recommend the probability section of Joseph Mazur’s diverting book Euclid in the Rainforest.

Four miscellaneous related notes, in lieu of a conclusion:

(1) One might guess that any discrepancies between real coins and ideal ones would amount to only minor biases (unless you’re wagering with Persi Diaconis). Perhaps so, but consider what happened a century ago when several eminent statisticians tried large-scale experiments in generating random numbers with dice, playing cards and numbered slips of paper drawn from a bowl or a bag. Not one of those efforts produced results that passed statistical tests of randomness (including the predictions of the law of large numbers). As late as 1955, even the big Rand Corporation table of a million random digits (generated by a custom-made electronic device) had to be fudged a little after the fact.

(2) Hájek’s indictment of finite frequentism includes this charge: The scheme “rules out irrational probabilities; yet our best physical theories say otherwise.” Elsewhere in the essay he elaborates on this point, mentioning that quantum mechanics posits “irrational probabilities such as 1/√2.” At first I thought this a very acute criticism, but now I’m not so sure. In the quantum contexts most familiar to me, 1/√2 is a commonly encountered amplitude; the corresponding probability is |1/√2|² = 1/2. Is it true that quantum mechanics necessarily requires irrational probabilities?

(3) Mark Kac, writing on probability in Scientific American (September 1964, p. 96) asks why probability theory was such a late-blooming flower among the branches of mathematics. It was neglected through most of the 18th and 19th centuries. Kac offers this explanation:

Why this apathy toward the subject among professional mathematicians? There were various reasons. The main one was the feeling that the entire theory seemed to be built on loose and nonrigorous foundations. Laplace’s definition of probability, for instance, is based on the assumption that all the possible outcomes in question are equally likely; since this notion itself is a statement of probability, the definition appears to be a circular one.

I’m skeptical of this hypothesis. It’s surely true that probability had shaky foundations, but so did other areas of mathematics. In particular, analysis was a ramshackle mess from the time of Newton and Leibniz until 1951, when Tom Lehrer finally gave the world the epsilon-delta notation. Yet analysis was the height of fashion all through that period.

(4) If you adhere strictly to the finite-frequentist doctrine that a probability does not exist until you measure it, can you ever be surprised by anything?

The image above shows the mesh top of a patio table, photographed after a soaking rain. Some of the openings in the mesh retain drops of water. What can we say about the distribution of those drops? Are they sprinkled randomly over the surface? The rainfall process that deposited them certainly seems random enough, but to my eye the pattern of occupied sites in the mesh looks suspiciously even and uniform.

For ease of analysis I have isolated a square piece of the tabletop image (avoiding the central umbrella hole), and extracted the coordinates of all the drops within the square. There are 394 drops, which I plot below as blue dots:

Again: Does this pattern look like the outcome of a random process?

I come to this question in the aftermath of writing an American Scientist column that explores two varieties of simulated randomness: pseudo and quasi. Pseudorandomness needs no introduction here. A pseudorandom algorithm for selecting points in a square tries to ensure that all points have the same probability of being chosen and that all the choices are independent of one another. Here’s an array of 394 pseudorandom dots constrained to lie on a skewed and rotated lattice somewhat like that of the mesh tabletop:

Quasirandomness is a less familiar concept. In selecting quasirandom points the aim is not equiprobability or independence but rather equidistribution: spraying the points as uniformly as possible across the area of the square. Just how to achieve this aim is not obvious. For the 394 quasirandom dots shown below, the x coordinates form a simple arithmetic progression, but the y coordinates are permuted by a digit-twiddling process. (The underlying algorithm was invented in the 1930s by the Dutch mathematician J. G. van der Corput, who worked with one-dimensional sequences, and extended to two dimensions in the 1950s by K. F. Roth. For more details, see my American Scientist column, page 286, or the splendid book by Jiri Matousek.)

Which of these point sets, the pseudo or the quasi, is a better match for the raindrops? Here are the three patterns in miniature, placed side-by-side as an aid to comparison:

Each of the panels has a distinctive texture. The pseudorandom pattern has both tight clusters and large voids. The quasirandom dots are more evenly spaced (though there are several close pairs of points), but they also form distinctive, small-scale repetitive motifs, most notably a hexagonal structure that repeats with not-quite-crystalline regularity. As for the raindrops, they appear to be spread over the area at almost uniform density (in this respect resembling the quasirandom pattern), but the texture shows hints of swirly rather than latticelike structures (more like the pseudorandom example).

Rather than just eyeballing the patterns, we could try a quantitative approach to describing or classifying them. There are lots of tools for this purpose—radial distribution functions, nearest-neighbor statistics, Fourier methods—but my main motive for bringing up this question in the first place is to play with a new toy that I learned about in the course of reading up on quasirandomness. It is a quantity called discrepancy, which attempts to measure how much a point set departs from a uniform spatial distribution.

There are lots of variations on the concept of discrepancy, but I’m going to discuss just one measurement scheme. The idea is to superimpose rectangles of various shapes and sizes on the pattern, allowing only rectangles with sides parallel to the x and y axes. Here are three example rectangles drawn on the raindrop pattern:

Now count the number of dots enclosed by each rectangle, and compare it with the number of dots that would be enclosed—based on the rectangle’s area—if the distribution of dots were perfectly uniform throughout the square. The absolute value of the difference is the discrepancy D(R) associated with rectangle R:

D(R) = | N · area(R) – #(P ∩ R) |,

where N is the total number of dots and #(P ∩ R) denotes the number of dots P in rectangle R. For example, the rectangle at the upper left covers 10 percent of the area of the square, so its fair share of dots would be 0.1 × 394 = 39.4 dots. The rectangle actually encloses only 37 dots, and so the discrepancy associated with the rectangle is |39.4 — 37| = 2.4. Note that the density of dots in the rectangle could be either higher or lower than the overall average; in either case the absolute-value operation would give a positive discrepancy.

For the pattern as a whole, we can define the global discrepancy D as the worst-case value of this measure, or in other words the maximum discrepancy taken over all possible rectangles drawn in the square. Van der Corput asked whether point sets could be constructed with arbitrarily low discrepancy, so that D would always remain below some fixed bound as N goes to infinity. The answer is No, at least in one and two dimensions; the minimal growth rate is O(log N). Pseudorandom patterns generally have even higher discrepancy, O(√N).

How can you find the rectangle that has maximum discrepancy for a given point set? When I first read the definition of discrepancy, I thought it would be impossible to compute exactly, because there are infinitely many rectangles to be considered. But after thinking about it a while, I realized there are only finitely many candidate rectangles that might possibly maximize the discrepancy. They are the rectangles in which each of the four sides passes through at least one dot. (Exception: Candidate rectangles can also have sides lying on the boundary of the enclosing square.)

Suppose we encounter the following rectangle:

The left, top and bottom sides each pass through a dot, but the right side lies in “empty space.” This configuration cannot be the rectangle of maximum discrepancy. We could push the right edge leftward until it just intersects a dot:

This change in shape reduces the area of the rectangle without altering the number of dots enclosed, and thus increases the density of dots. Alternatively, we could push the edge the other way:

Now we have increased the area, again without changing the count of enclosed dots, and thereby lowered the density. At least one of these actions must increase D(R), compared with the initial configuration. Thus every rectangle with all four sides touching dots or the edges of the square is a local maximum of the discrepancy function; by enumerating all rectangles in this finite set, we can find the global maximum.

There is also the irksome question of whether the rectangle is to be considered “closed” (meaning that points on the boundary are included in the area) or “open” (boundary points are excluded). I’ve sidestepped that problem by tabulating results for both open and closed boundaries. The closed form gives the highest discrepancy for densely populated rectangles, and the open form maximizes discrepancy for sparsely populated rectangles.

By considering only extrema of the discrepancy function, we make the counting problem finite—but not easy! In a square with N dots (all with distinct x and y coordinates), how many rectangles have to be considered? This turns out to be a really sweet little problem, with a simple combinatorial solution. I’m not going to reveal the answer here, but if you don’t feel like working it out for yourself, you could look it up in the OEIS or see a short paper by Benjamin, Quinn and Wurtz. What I will say is that for N = 394, the number of rectangles is 6,055,174,225—or double that if you count open and closed rectangles separately. For each rectangle, it’s necessary to figure out how many of the 394 points are inside and how many are outside. Pretty big job.

One way to reduce the computational burden is to retreat to a simpler measure of discrepancy. Much of the literature on quasirandom patterns in two or more dimensions uses a quantity called star discrepancy, or D*. The idea is to consider only rectangles “anchored” at the lower left corner of the square (which we can conveniently identify with the origin of the xy plane). In this case the number of rectangles is just N², or about 150,000 for N = 394.

Here is the rectangle that defines the global star discrepancy of the raindrop pattern:

The dark green rectangle at the bottom covers about 55 percent of the square and ought to encompass 216.9 dots, if the distribution were truly uniform. The actual number of dots included (assuming a “closed” rectangle) is 238, for a discrepancy of 21.1. No other rectangle anchored to the corner (0,0) has a greater discrepancy. (Note: Because of limited graphic resolution, the D* rectangle appears to extend horizontally all the way across the unit square; in fact the right edge lies at x = 0.999395.)

What does this result tell us about the nature of the raindrop pattern? Well, for starters, the discrepancy is fairly close to √N (which is 19.8 for N = 394) and not particularly close to log N (which is 6.0 for natural logs). Thus we get no support for the idea that the raindrop pattern might be more quasirandom than pseudorandom. The D* values for the other patterns shown above are in the ranges expected: 25.9 for the pseudorandom and 4.4 for the quasirandom. Contrary to the visual impression, the raindrop distribution seems to have more in common with a pseudorandom point set than a quasirandom one—at least by the D* criterion.

What about calculating the unrestricted discrepancy D—that is, looking at all rectangles rather than just the anchored rectangles of D*? A moment’s thought shows that this exhaustive enumeration of rectangles can’t change the basic conclusion in this case; D can never be less than D*, and so we can’t hope to move from √N toward log N. But I was curious about the computation anyway. Among those six billion rectangles, which one has the greatest discrepancy? Is it possible to answer this question without heroic efforts?

The obvious, straightforward algorithm for D generates all candidate rectangles in turn, measures their area, counts the dots inside, and keeps track of the extreme discrepancies seen along the way. I found that a program implementing this algorithm could determine the exact discrepancy of 100 pseudorandom or quasirandom dots in a few minutes. This outcome might seem to offer some encouragement for pushing on to higher N; however, the running time almost doubles every time N increases by 10, which suggests the computation would take a couple of centuries at N = 394.

I’ve invested a few days’ work in efforts to speed up this calculation. Most of the running time is spent in the routine that counts the dots in each rectangle. Deciding whether a given dot is inside, outside or on the boundary takes eight arithmetic comparisons; thus, at N = 394, there are more than 3,000 comparisons for each of the six billion rectangles. The most effective time-saving device I’ve discovered is to precompute all the comparisons. For each point that can become the lower left corner of a rectangle, I precompute a list of all the pattern dots above and to the right. For each potential upper right corner of a rectangle, I compile a similar list of dots below and to the left. These lists are stored in a hash table indexed by the corner coordinates. Given a rectangle, I can then count the number of interior dots just by taking the set intersection of the two lists.

With this trick, the estimated running time for N = 394 came down from two centuries to about two weeks. A big improvement—just enough encouragement to induce me to spend yet another day on further refinements. Replacing the hash table with an N × N array helped a little. And then I figured out a way to ignore all the smallest rectangles, those that cannot possibly be the max-D rectangle because they either contain too few dots or have too small an area. This improvement finally brought the running time down to the overnight range. The illustration below, which shows the rectangle of maximum discrepancy D for the raindrop pattern, took six hours to compute.

The max-D rectangle is clearly a slight refinement of the D* rectangle for the same point set. The D rectangle “should” contain 204.3 dots but actually has 229, for a discrepancy of D = 24.7.

Of course knowing that the exact discrepancy is 24.7 rather than 21.1 tells us nothing more about the nature of the raindrop pattern. As a matter of fact, I feel I know less and less about it as I compute more and more.

When I started this project, I had a pet theory about what might be happening in the tabletop to smooth out the distribution of drops and thereby make the pattern look more quasi- than pseudorandom. To begin with, think of droplets lying on a smooth pane of glass rather than a metal mesh. If two small droplets come close enough to touch, they merge into one larger drop, because that configuration has lower energy associated with surface tension. Perhaps something similar could happen in the mesh. If two adjacent cells of the mesh are both filled with water, and if the metal channel between them is wet, then water could flow freely from one drop to the other. The larger drop will almost surely grow at the expense of the smaller one, and the latter will eventually be annihilated. Thus we would expect a deficit of drops in adjacent cells, compared with a purely random distribution.

This idea still sounds pretty good to me. The only trouble is: It explains a phenomenon that may not exist. I don’t know whether my discrepancy measurements actually reveal anything important about the three patterns, but at the very least the measurements fail to provide evidence that the raindrop distribution is different from the pseudorandom distribution. True, the patterns look different, but how much should we trust our perceptual apparatus in a case like this? If you ask people to draw dots at random, most do a bad job of it, typically making the distribution too smooth and even. Maybe the brain is equally challenged when trying to recognize randomness.

Nevertheless, I suspect there is some mathematical property that will more effectively distinguish between these patterns. If anyone else would like to sink some time into the search, the xy coordinates for the three point sets are in a text file here.

Update 2011-06-24: This is just a brief note to suggest that if you’ve read this far, please go on and read the comments, too. There’s much of value there. I want to thank all those who took the trouble to propose alternative explanations or algorithms, and to point out weaknesses in my analysis. Special thanks to themathsgeek, who within 40 minutes after I first posted the item had come up with a far superior program for computing discrepancies. Also Iain, who pursued my offhand remarks about the perception of random patterns with actual experiments.

On the subject of the Collatz conjecture (also known as the 3x+1 problem), Paul Erdos remarked: “Mathematics is not yet ready for such problems.” Shizuo Kakutani joked that the problem was a Cold War invention of the Russians meant to slow the progress of mathematics in the West. Richard Guy listed it in an article titled “Don’t try to solve these problems!” All of these warnings to the unwary have had the expected effect: A bibliography compiled by Jeffrey Lagarias cites 200 works on the Collatz conjecture, and there are hundreds of other papers that didn’t make the list. This past week brought one more preprint: a claimed proof of the conjecture by Gerhard Opfer of the University of Hamburg.

The Collatz conjecture can be stated in terms of this little recursive program:

    procedure collatz(x)
        if x=1 then halt
        elseif even(x) then collatz(x/2)
        elseif odd(x) then collatz(3*x+1);

The conjecture makes the following claim: If x is any positive integer, then the program eventually halts. For example, starting with x=3, the successive values of x are 3, 10, 5, 16, 8, 4, 2, 1—and on reaching x=1 the program halts. You could try a few other starting values for yourself; x=27 is a popular choice; x=319,804,831 is even better. But please remember Guy’s advice. Also note that the Collatz conjecture has been verified numerically by Tomás Oliveira e Silva for all x up to 20 × 2⁵⁸ . Thus if you’re searching for a counterexample, you may as well start somewhere north of 5,764,607,523,034,234,880.

The conjecture is named for Lothar Collatz (1910–1990), who investigated the curious properties of the 3x+1 iteration when he was a young student, circa 1930. Opfer, the author of the new proposed proof, was a Ph.D. student of Collatz in the 1960s. This conjunction suggests a novelistic storyline: A mathematician struggles all his life with an intractable problem, then hands it on to his student, who dedicates his own career to the task, finally achieving triumphant success some 80 years after the story began. But apparently that’s not how it happened. Collatz never returned to the 3x+1 problem after the 1930s; almost all of his mature work was in numerical analysis. Opfer is also a numerical analyst and only recently turned to the 3x+1 problem. There’s no grand saga of a multigenerational obsession here.

Much of Opfer’s paper is beyond my understanding, but I can piece together a crude guide to a few of the basic ideas. The proof begins with a mathematical change of venue. A problem originally posed in terms of the simplest kind of arithmetic on the natural numbers is transported to the realm of holomorphic functions on the complex plane. It’s like being swept up from a farm in Kansas and set down in the Land of Oz. The idea for this transformation comes from the work of Lothar Berg and Günter Meinardus in the 1990s, who established a direct connection between these two realms. They set up a certain system of equations for functions of a complex variable z, then showed that the Collatz conjecture is true if and only if the solutions of the equations all lie in a certain region. In the simplest case, the region is the open unit disc—the disc centered at the origin with |z| < 1. Who’d've thunk it? What we do in Oz has consequences back in Kansas!

How can those two very different problems be yoked together? As I (tenuously) understand it, the complex functions of Berg and Meinardus can be represented by formal power series whose integer coefficients encode information about the sequence of numbers generated in the Collatz iteration. The rest of the Opfer proof is all about those coefficients. Thus we click our heels and return from the Emerald City to the land of number theory.

At this point Opfer begins reasoning in terms of algorithms that generate sets of coefficients. I’m on much friendlier terms with algorithms than I am with holomorphic functions, but strangely enough this is where I begin to lose my footing as I try to follow Opfer’s steps. His aim is to show that all coefficients vanish except for those whose indices lie in a certain congruence class. (Specifically, he is seeking to prove that all coefficients η_j = 0 except those for which j = 3k–1, k ∈ 1, 2, 3, … .) He argues that his algorithms for generating the coefficients yield exactly this property. But this is where I get lost.

Opfer is not the first to announce a proof of the Collatz conjecture. The earlier attempts did not stand up to scrutiny, and in various corners of nerdom there’s already skepticism about this try, too. As for me, I can’t say whether there are gaps in Opfer’s proof because there are such wide gaps in my understanding of it. The paper has been submitted to Mathematics of Computation, which is certainly an appropriate journal for this work, and I’m content to wait and see what comes of the referreeing process.

Like many others, I first learned of the 3x+1 problem from Martin Gardner’s Scientific American column in the early 1970s. A decade later, when I briefly had a chance to fill Martin’s space in the magazine after his retirement, 3x+1 was one of the first subjects I wrote about (nearly illegible PDF—sorry; it’s my only copy). I’m delighted to have this opportunity to poke at the problem again. Even if the Opfer proof comes to nothing, it has given me an incentive to read some of the recent literature, including that illuminating trip to Oz courtesy of Berg and Meinardus. I would also like to recommend a book by Günther J. Wirsching, The Dynamical System Generated by the 3n + 1 Function (Springer, 1998). A version of at least one chapter is available online.

Jeffrey Lagarias also has a recent book: The Ultimate Challenge: The 3x+1 Problem (AMS, 2010), but I haven’t seen it yet. The volume reprints a number of survey articles and historical documents, including a 1985 American Mathematical Monthly article by Lagarias himself that is still the best starting point for those who want to ignore all good advice and dive into the problem. I am particularly eager to see another chapter: an English translation of the only paper in which Collatz discusses his work on 3x+1; it is an account in Chinese of a talk by Collatz at Qufu Normal University in 1986.

I’m in Pittsburgh this weekend, attending a conference at Carnegie Mellon University. The sessions are being held in the Rashid Auditorium of the Gates Building.

The seats in the auditorium are upholstered with a pattern that seems apt for a computer science department, but it also begs for elucidation:

What is the patterning principle in these bits?

I’ve asked half a dozen people in the department—faculty, grad students, staff—but they all profess ignorance. Perhaps it’s a secret that’s never divulged to outsiders.

A quick web search turned up only one pertinent reference—a publication of the CMU chapter of the ACM. A photo caption on the last page includes this remark:

Do the binary codes written on the seats in Rashid Auditorium mean anything? After further investigation, we have concluded that while the binary patterns seem not to repeat, they do not map to any meaningful ASCII words.

Could it be true that the sequence has no repetition anywhere in the auditorium? I guess that depends on what you mean by repetition. Obviously short subsequences are repeated, and Axel Thue proved a century ago that no binary sequence can go on indefinitely without repeating some block of bits. But I have not tried to survey all 247 seats looking for the longest repeated block. (Most of the seats are occupied at the moment.)

I have a sneaking suspicion about what lies behind this pattern, but I’m trying to pay attention to a series of talks as I write this, so I’m not going to investigate further until I get home. In the meantime, I thought I’d throw open the question to anyone else who wants to speculate. To make the job a little easier, I’ve transcribed a few hundred bits:

1 0 1 0 1 1 0 1 1 1 0 1 0 1 0 0 0 1 1 0 1 1 0 1 0 1 1 0 1 1 1 0 1 0 1 0 1 0 0 0 1 0 1 0 1 1 0 1 0 1 0 0 0 1 1 0 1 1 0 0 1 0 1 0 1 1 0 1 1 1 0 1 0 1 0 0 0 1 1 1 0 1 0 0 1 1 1 0 1 1 0 1 0 1 0 1 1 0 1 1 1 0 1 1 0 1 1 0 1 0 1 1 1 0 1 1 0 1 0 1 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 1 1 0 1 1 0 1 0 0 1 1 1 0 1 1 0 1 0 1 0 1 1 0 1 0 1 1 0 1 0 1 0 0 1 1 0 1 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 1 0 0 1 0 1 0 1 1 1 0 0 1 1 0 1 0 1 0 0 1 0 0 0 1 0 1 0 1 1 0 1 0 1 0 0 1 1 0 1 0 1 0 0 1 0 1 0 1 0 0 1 1 1 0 1 0 1 0 1 1 0 1 0 0 1 0 0 1 0 1 0 1 0 1 1 1 0 1 0 0 1 0 1 0 1 0 0 0 1 0 1 0 1 0 1 1 0 1 0 0 1 0 0 1 0 1 0 1 0 0 1 1 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 0 0 1 0 1 0 0 0 1 1 1 0 1 0 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 0 1 0 0 1 0 1 0 0 0 1 1 1 0 1 0 0 0 1 1 0 1 0 1 0 1 0 1 1 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 1 0 0 1 1 0 1 0 1 0 0 1 1 1 0 1 0 1 1 0 1 1 1 0 1 0 1 0 1 0 0 1 0 1 0 1 1 0 1 0 1 0 0 1 1 1 0 1 0 1 1 0 1 0 0 1 0 1 0 0 1 0 0 1 1 0 1 0 1 0 0 1 1 0 1 0 1 0 1 0 0 0 1 0 1 0 0 1 0 1 0 1 1 0 1 1 1 0 1 0 1 0 0 0 1 1 1 1 1 0 1 0 1 1 0 1 1 0 0 1 0 1 0 1 1 0 1 1 1 0 1 1 1 0 1 0 1 0 1 0 0 0 1 0 1 0 0 1 0 1 0 1 1 1 1 0 1 1 0 1 0 1 0 0 0 1 1 0 1 0 0 1 1 1 0 1 1 0 1 0 1 0 1 1 1 0 1 1 0 1 1 0 1 1 0 1 0 1 1 0 1 0 0 1 1 1 0 1 1 0 1 0 1 1 1 0 1 1 0 1 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 0 1 0 1 0 1 1 1 0 1 0 1 1 0 1 0 1 0 0 1 1 0 1 0 1 0 0 0 1 1 0 1 0 0 1 0 0 0 1 1 0 1 0 1 1 0 1 0 1 0 0 1 1 0 1 0 1 0 1 0 0 1 0 1 0 1 1 1 0 1 0 1 1 0 1 0 1 0 0 1 0 1 0 1 0 0 0 1 0 1 0 1 0 0 1 1 1 0 1 0 1 0 1 1 0 1 0 1 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 1 1 1 0 1 0 1 1 1 0 1 0 0 1 0 1 0 1 0 0 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 0 1 0 1 1 0 1 0 1 0 1 0 1 1 0 0 0 1 0 1 0 0 0 1 0 1 0 1 0 0 1 0 1 0 0 1 1 0 1 0 1 0 1 0 1 1 0 1 0 1 1 0 1 0 1 1 1 0 1 0 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1 1

Any ideas?

Update 2011-04-12: The “sneaking suspicion” I had in mind the other day was ridiculously wrong. I had wanted the pattern to be a segment of the Thue-Morse sequence, which I obliquely alluded to above. (Obliquely and also clumsily, as one commenter rightly pointed out.) The Thue-Morse sequence is one of the little gems of discrete mathematics, and it seemed like a perfect choice for a temple of high nerdiness like the CMU CS department. Here’s how the sequence begins:

0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1

At first glance—just taking in the optical texture of 1s and 0s—it seemed a good match for the fabric in Rashid Auditorium. But a closer look at the pattern on the chairs shows that the bits there cannot possibly be drawn from the Thue-Morse sequence. The key property of the sequence is that it is “cube-free”: No block of bits w is repeated three times in succession, as in www. The block w can be of any length, including a length of just one bit. The fabric pattern includes subsequences of 000 and 111, both of which violate the cube-free constraint. (I should have noticed this before I even got up out of my seat, but I didn’t.)

If not Thue-Morse, then what?

Several commenters note that it cannot simply be bits chosen uniformly at random, and I totally agree. Here are the frequencies of subsequences from one to four bits long:

For random bits, all of these distributions are flat: Each k-bit subsequence occurs with expected frequency 2^–k. The pattern at CMU is anything but flat. It has prominent peaks and valleys, with a notable excess of alternating 1s and 0s, and a corresponding deficit of subsequences that repeat the same symbol.

Another way to look at the bit sequences is through the autocorrelation function, which measures how well the sequence matches up with itself when shifted along its length by some fixed distance. An autocorrelation of 1.0 indicates a perfect match, and –1.0 is perfect anticorrelation—all the bits are different. For any series, the autocorrelation has to be 1.0 at a shift of 0. As the graph below shows, the autocorrelation function for the Rashid sequence is strongly negative at a shift of 1, and positive at shift 2. These results are consistent with the observed prevalence of alternating bits. Interestingly, the correlations continue to oscillate at larger shifts, with little sign of damping. What’s even more curious, for shifts greater than 4, the sign of the correlation is the opposite of what you’ve expect for an alternating 01 sequence.

For comparison, the graph also shows the autocorrelation function of the Thue-Morse sequence, which has a fascinating structure of its own, and that of a random sequence of bits. Except at shift 0, the random sequence should converge on 0 autocorrelation everywhere.

The results above are based on a somewhat larger sample than the one I gave on Sunday. When I got home from Pittsburgh, I transcribed 35 rows of 79 digits each, for a total of 2,765 bits. I’ve treated the rows as 35 independent samples, since I don’t know how to join them without creating spurious conjunctions.

If you’d like to play with the bits for yourself, they are all here in a PDF that includes both an image of the fabric and my transcription of it. I should mention that typing 2,765 binary digits is not a lot of fun. Before embarking on that project, I struggled to get useful output from OCR services such as Online OCR, but the character-recognition algorithms try desperately to turn numerical data into English, producing stuff like this:

LOLOL010101.11.0110101.1.1010001010111.01.LoLotootoLoc t tot totot IMO /0t 100101 L LO LOLOt L tO1O 101000 OIOtOOlOLOtOlttOttOtOlttOOlOLOttOC

LOL indeed.

At this point, I admit I’m stumped. I just don’t know where all those bits came from.

The CMU-ACM magazine I mention above says the bit stream is not ASCII text. I don’t know how the author determined that, but I tend to agree. ASCII and most other byte-oriented encodings would show an autocorrelation spike at a shift of 8, and there’s no evidence of that.

I’m also sure the sequence is not Morse code. When you smush together letters and words in dot-dash encoding, the result has many more long runs than we see here.

Could it be the binary object code for some program? Rick Rashid was the principal author of the Mach operating system, created at CMU, so a fitting tribute would be to sew his work into the seats of the auditorium he funded. But I’ve never seen a core dump that looked anything like this. Most machine code has blocks of highly repetitive bit patterns.

Maybe the underlying message is text or an image that’s been run through a compression algorithm, such as gzip? That would raise the entropy of the signal and flatten the distribution of subsequences to some extent. But would it yield the specific pattern we see here? In particular, would it favor alternation of 0s and 1s? I don’t see why.

In the comments, Zvika suggests that the sequence looks like the product of a human operator trying to type randomly. I resist this idea. It’s just such an inhuman waste of human resources; I can’t stand to think of some poor schlub pecking away at a keyboard for hours, struggling to be mindless about it. But I suppose it could be true.

I came up with a slightly less barbaric alternative scenario. Suppose a fabric designer says to his programmer friend, “I need some random bits. Can you help me out?” The programmer goes away and fires up her RNG, and comes back with a million bits that pass all the usual tests of randomness. The designer says thanks, but later he complains, “These bits don’t look random. They’ve got all these long runs of 0s and 1s.” The programmer explains about independent choices from a uniform distribution, and the 1/2^k spectrum of run lengths, but the designer will have none of it. “I don’t care about the math; give me something that looks right,” he says. So the programmer goes away and creates some new bits, meant to satisfy people who believe that when a coin has come up heads three times in a row, it’s more likely to show tails on the next toss.

I made an attempt to create such a function myself. It’s a simple Markov process, in which each appearance of a 1 in the sequence reduces the probability p that the next symbol will also be a 1. Specifically, I start with p = 1/2. If the next bit is a 1, p is adjusted to p/k, where k is a constant greater than 1. If the new bit is instead a 0, p becomes 1 — p/k. When I set k = 2, this process generated a stream of bits that looked much like the fabric pattern. Here’s a small sample:

1 0 1 1 0 1 0 1 1 0 1 0 0 1 0 1 1 1 0 1 0 1 0 1 0 1 1 1 0 1 1 0 1 1 0 0 1 0 1 1 1 0 1 1 0 0 1 0 1 1 0 1 0 1 0 1 1 1 1 0 1 0 1 0 1 1 0 1 0 1 0 1 1 1 1 0 1 1 0 1

And the subsequence frequencies also seemed broadly similar to those of the Rashid sequence:

(The orange bars are the results for the Markov process; the green lollipops show the corresponding frequencies for the Rashid bits.) This outcome was at least mildly encouraging, but then I looked at the autocorrelations in the Markov-generated stream of bits:

At shifts of 1 and 2, the Markov autocorrelations match those of the Rashid sequence almost exactly, but at longer distances the Markov correlations fade away, as they must in any random process. The long-range structure in the Rashid sequence seems all the more peculiar when displayed in this context.

Still another question is whether the fabric pattern can be truly aperiodic at large scales. If it were a printed fabric, I would be highly skeptical of this proposition. The printing process is inherently repetitive, with the same pattern recurring at intervals determined by the size of the printing plate or cylinder. (Think of wallpaper patterns.) But the pattern on the upholstery cloth is not printed; it is woven into the fibers, and that changes everything. Looms have been programmable since the time of Jacquard, and there is no fundamental reason a modern loom could not be driven by a computer that supplies an arbitrarily long sequence of nonrepetitive instructions. The Thue-Morse sequence would do nicely for this purpose. So I can easily imagine an aperiodic upholstery pattern; I just don’t know if that’s what we’re seeing here.

Later this week I’ll go take a look at the Harvard version. (Thanks to Max Lin for discovering this second instance.)

Update 2011-04-13: I note here for the benefit of those who don’t read the comments: rouli has swept away all this speculation about looms driven by computers generating infinite aperiodic sequences. In the section of the pattern I transcribed, the last nine lines are identical to the first nine. I’ve checked a couple of other photos (of other seat backs) and confirmed that the whole pattern appears to repeat on a cycle of 26 lines.

How appalling that I could type more than 700 repeated characters and never notice the resemblance.

Update 2011-04-13, later:Yikes! And now Barry Cipra reveals that the pattern also repeats horizontally, with period 60.

All those books that Google has been scanning for the past ten years are surprisingly rich in numbers as well as words. The Google Books data set released last December by a Harvard-Google team includes (by my count) 9,620,835,344 occurrences of 458,794 distinct numbers. (Plus another 31,293 numeric values that have dollar signs attached.)

In recognition of pi day, I want to zero in on some successive approximations to the world’s favorite irrational:

In tabular form here are the closest approximations found in the files, along with the abundance of each value:

The data set includes only items that appear at least 40 times in the collection of scanned volumes. Closer approximations to pi evidently fell below that threshold. In particular there is no sign of William Shanks’s famous 707-digit calculation, which was published in 1873. So, just for the sake of celebrating 3.14, here are 707 digits of pi—but unlike the product of Shanks’s many years of labor, I think these digits may be correct:

3.1415926535897932384626433832795028841971693993751058209
74944592307816406286208998628034825342117067982148086513
282306647093844609550582231725359408128481117450284102701
938521105559644622948954930381964428810975665933446128475
648233786783165271201909145648566923460348610454326648213
393607260249141273724587006606315588174881520920962829254
0917153643678925903600113305305488204665213841469519415116
09433057270365759591953092186117381932611793105118548074462
3799627495673518857527248912279381830119491298336733624406
5664308602139494639522473719070217986094370277053921717629
3176752384674818467669405132000568127145263560827785771342
7577896091736371787214684409012249534301465495853710507922
796892589235420200