{\huge Some Strange Math Facts}

Things we did not know \vspace{.25in}

Stanislaw Ulam was a Polish-American mathematician whose work spanned many areas of both continuous and discrete mathematics. He did pioneering research in chaos theory and Monte Carlo algorithms, and also invented the concept of a measurable cardinal in set theory. His essential modification of Edward Teller's original H-bomb design is used by nearly all the world's thermonuclear weapons, while he co-originated the Graph Reconstruction conjecture. His name is also associated with the equally notorious 3+1 conjecture}. Thus he was involved in some strange corners of math.

Today Ken and I want to talk about some strange facts observed by Ulam and others that we did not know or fully appreciate.

Perhaps you can use them, perhaps you may enjoy them, but they are all kind of fun. At least we think so. Ulam's autobiography Adventures of a Mathematician shows his sense of fun, and he was described by Gian-Carlo Rota in these words:

Ulam's mind is a repository of thousands of stories, tales, jokes, epigrams, remarks, puzzles, tongue-twisters, footnotes, conclusions, slogans, formulas, diagrams, quotations, limericks, summaries, quips, epitaphs, and headlines. [H]e simply pulls out of his mind the fifty-odd relevant items, and presents them in linear succession. A second-order memory prevents him from repeating himself too often before the same public.

There is another reason for discussing this today. Class is underway and we both are trying to get things going and we wanted to start a discussion out. We are working on a longer, more technical one, about---``that would be telling''---so let us do this now. Note: fifty extra points for where that phrase comes from---with a search.

Spirals Already

Even before we come to Ulam's famous observation about the pattern of prime numbers in a spiral, some things strike us as strange about spirals. Here we mean the simple spiral walk pattern starting from an origin square in the infinite planar lattice:

\includegraphics[width=2in]{200px-Ulam_spiral_howto_all_numbers_svg.png}

We can begin with any number $latex {c}&fg=000000$ in place of $latex {1}&fg=000000$---thus if we begin with $latex {41}&fg=000000$ this is the same as adding $latex {40}&fg=000000$ to all the numbers. One basic fact is that if we take any ray from the origin that goes through the center of another cell, then the $latex {m}&fg=000000$th number along that ray is given by a quadratic function of $latex {m}&fg=000000$. For instance, the horizontal ray $latex {1,2,11,28,\dots}&fg=000000$ is given by $latex {4m^2 - 3m + 1}&fg=000000$, the northeast ray $latex {1,3,13,31,\dots}&fg=000000$ by $latex {4m^2 - 2m + 1}&fg=000000$, and the ray of north-northeast knight's moves $latex {1,14,59,136\dots}&fg=000000$ by $latex {16 m^2 - 3m + 1}&fg=000000$. Similar rays originating from other squares also have quadratic formulas.

If we sequence the numbers that fall on full lines rather than rays, however, we do not get a quadratic function. For instance, the numbers that fall on the horizontal axis in order are $latex {1,2,6,11,19,28,\dots}&fg=000000$ They do not fit any polynomial formula at all---one has to do integer division by 2 (throwing away remainders) to get a formula. Indeed, this sequence doesn't have an entry in OEIS, the Online Encyclopedia of Integer Sequences. Likewise, the northwest-southeast line $latex {1,5,9,17,25,37,\dots}&fg=000000$ has all the odd squares but no nice formula. Nor does the line of knight moves $latex {1,14,22,59,75,136,160,\dots}&fg=000000$.

But there is a singular exception. The southwest-northeast diagonal gives $latex {1,3,7,13,21,31,43,\dots}&fg=000000$, which has the formula $latex {m^2 + m + 1}&fg=000000$. Why does this happen?

If we add $latex {40}&fg=000000$ to this sequence, we get:

$latex \displaystyle 41,43,47,53,61,71,83,97,113,131,151,173,197,223,251,281,313,347,383,421,461,503,\dots &fg=000000$

Ulam's Prime Plot

The story goes that Ulam became bored during a long lecture in 1963, doodled a number spiral like the one pictured above, and circled the primes to see what the plot would look like. He was struck by how many substantially long diagonal segments of primes there were, going northwest as well as northeast.

This also happens if we start the spiral with numbers $latex {c}&fg=000000$ other than $latex {1}&fg=000000$. Here is a plot for $latex {c = 0}&fg=000000$ from Helgi Rudd's beautiful website devoted to Ulam's spiral:

\includegraphics[width=3in]{600x600_Zoom25_Centre0_Numbers.png}

Of course, $latex {c = 41}&fg=000000$ gives Euler's sequence as a huge diagonal swath through the origin, but as Wikipedia's article notes, the effects of Euler's formula show up on other diagonals with larger values of $latex {m}&fg=000000$ even with $latex {c = 1}&fg=000000$.

Despite connections noted in both sources to earlier theorems and conjectures about quadratic polynomials, it is still considered that this affinity for diagonals has not been sufficiently ``explained.'' The larger picture that strikes us the most is given immediately on the front page of Rudd's site. Many unsolved problems in number theory, including the Riemann Hypothesis itself, involve the idea of how much the primes behave like a ``random'' sequence.

• If we randomly choose odd numbers with the same density as the primes, then a spiral plot of them looks like ``white noise''---nothing like Ulam's spiral.
• But if we note that odd numbers of the form $latex {6n+3}&fg=000000$ cannot be prime, and exclude them, then the randomly-generated plots of the same density begin to look streakier.
• Excluding other congruences, and other exclusions noted on the site, makes the pictures look closer and closer to Ulam's.

Thus the prime pictures exhibit some of their non-random structure, along lines of more-extreme deficiencies shown by George Marsaglia for some 1960s-vintage pseudorandom generators. How the primes can be random and non-random at the same time relates to that other post we're working on, but ``we're not telling.''

Binomial Coefficients

In 1947, Nathan Fine proved that almost all binomial coefficients are even. This seems strange to me. More precisely let $latex {T_{2}(n)}&fg=000000$ be the number of odd binomial coefficients $latex {\binom{m}{k}}&fg=000000$ with $latex {0 \le k \le m < n}&fg=000000$. Then $latex {T_{2}(n)=o(n)}&fg=000000$. Even stronger:

$latex \displaystyle .812556n^{\log_{2} 3} \le T_{2}(n) \le n^{\log_{2} 3}. &fg=000000$

Percentages

This one comes from here. Let's say you invest $10 in the market and you make a 10 percent return. You now have $11. Now, let's say you lose 10 percent. Out of $11, that's $1.10 leaving you with $9.90 which means you are down ten cents on the deal. You gained the same percentage as you lost yet you came out behind.

Well, you might speculate it has to do with the order of the transaction. After all, the 10 percent you lost was bigger than the 10 percent you gained because you were already up on the deal. That means reversing the order should have the opposite effect. Right?

Start with $10. Now lose 10 percent first. You have nine dollars. Then gain ten percent. That's 90 cents leaving you with...$9.90.

Yep. You lost money again.

Strange as it may seem, a gain and a loss of the exact same percentage will always leave you with less cash - regardless of the order in which they occur.

I wonder if we can use this simple but strange fact in some algorithm analysis?

Your Friends Have More Friends Than You Do

Suppose you take the average $latex {n}&fg=000000$ of the numbers of friends each of your friends has, and compare that with your own number $latex {m}&fg=000000$ of friends. Chances are $latex {n}&fg=000000$ will be significantly higher than $latex {m}&fg=000000$. This leaves a lot of people wondering, why are my friends more popular, more vivacious, more successful, than I am?

This phenomenon has been well documented on Facebook and other contexts where ``friend'' is rigorously quantified. It is ascribed to a 1991 paper (titled as above) by the sociologist Scott Feld, but Ken and I would be surprised if it hadn't already been noted in connection with the collaboration graph of mathematicians. Ken recalls a talk given by Donald Knuth on properties of this graph 30 years ago at Oxford, a few years after a paper by Tom Odda that also cites studies by Ron Graham and others, but has no recollection of this being mentioned.

It is easy to explain in those terms. Think of Paul Erd\H{o}s, who famously had hundreds of collaborators. Many people were touched by him. But each of them had averages $latex {n}&fg=000000$ that included Erd\H{o}s, which alone was probably enough to boost $latex {n}&fg=000000$ over their own valence $latex {m}&fg=000000$ in the graph. More generally, let us assign to every node $latex {u}&fg=000000$ a ``collaborativeness potential'' $latex {p_u}&fg=000000$, and consider various ways to generate random graphs in which the probability of an edge $latex {(u,v)}&fg=000000$ depends on $latex {p_u}&fg=000000$ and $latex {p_v}&fg=000000$. For instance, every node $latex {u}&fg=000000$ might pick a set $latex {S_u}&fg=000000$ of 100 potential co-authors $latex {v}&fg=000000$ at random, and the edge is placed with probability $latex {(p_u + p_v)/2}&fg=000000$. Potential connections within $latex {S_u}&fg=000000$ will have a higher chance of succeeding with those $latex {v}&fg=000000$ having $latex {p_v > p_u}&fg=000000$, who in turn will expect to have more successful connections.

The result is shown with more rigor by Steven Strogatz in this New York Times column. Still, we find it strange as a raw fact of life.

Open Problems

What is your favorite strange fact?