{\huge Finding Patterns In Ancient Objects}

Ancient mathematical objects can still contain secrets \vspace{.5in}

David Singmaster is a mathematician who is now retired from London South Bank University, England; but he is not British---he was born in the USA. As a metagrobologist, he has a huge collection of mechanical puzzles, books on puzzles, and more. For a quick puzzle, can you name another word---of definite relevance to this blog---that ends in ``-bology'' (and not ``-biology'')?

Today Ken and I want to talk about Pascal's Triangle, and a beautiful conjecture of Singmaster on the structure of the famous triangle.

We all know the famous Pascal Triangle formed from the binomial numbers $latex {{n \choose k}}&fg=000000$. The first row is $latex {1}&fg=000000$, the second is $latex {1,1}&fg=000000$, the third is $latex {1,2,1}&fg=000000$ and so on:

\includegraphics[width=4in]{pascal.png}

The Triangle is related to the equally famous Binomial Theorem:

Theorem 1 For any $latex {x}&fg=000000$ and $latex {y}&fg=000000$ real numbers and $latex {n \ge 0}&fg=000000$ a natural number,

$latex \displaystyle (x + y)^{n} = \sum_{k=0}^{n} {n \choose k} x^{k} y^{n-k}. &fg=000000$

Whoever discovered this wonderful theorem has our thanks. One unique claimant might be Isaac Newton, who in 1665 generalized the Binomial Theorem to allow real exponents. This was a new level of sophistication that required notions of convergence, since now the sum is not finite.

A pretty use of the Binomial Theorem is a short proof of Fermat's Little Theorem: Let $latex {p}&fg=000000$ be a prime. Then by the Binomial Theorem it follows that

$latex \displaystyle 2^{p} = (1+1)^{p} = \sum_{k=0}^{p} {p \choose k}. &fg=000000$

$latex \displaystyle 2^{p} \equiv 2 \bmod p. &fg=000000$

Who Invented The Triangle?

While Newton may be the inventor of the generalized Binomial Theorem, it far less clear who invented the Triangle and the original Binomial Theorem. Blaise Pascal is often credited with the discovery of the Triangle and the Binomial Theorem in the 1600's. Thus we call the former Pascal's Triangle.

As is often the case in mathematics---something we have noticed many times before---the name attached to a math concept, theorem, or object of any kind, is often not accurate. It is often just plain wrong.

A ``little bit'' earlier---that is, in the 4th century BCE---Euclid mentioned the special case when $latex {n=2}&fg=000000$. Then the 3rd century BCE Indian mathematician Pingala included the higher powers. And it goes on:

• In the 10th century CE the Indian mathematician Halayudha and the Persian mathematician Al-Karaji knew the result.
• Also in 11th century the Persian poet and mathematician Omar Khayyam did too.
• And also in the 13th century the Chinese mathematician Yang Hui did as well.

Magic Properties of The Triangle

There are many patterns to be found inside the Triangle. Of course the row sums are powers of $latex {2}&fg=000000$, which follows directly from the Binomial Theorem. The Triangular Numbers are found in the Triangle as a diagonal:

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

See this for many more interesting patterns, including the ``hockey stick'' pattern.

A Simple Conjecture

Given the Triangle has been known for hundred's of years, perhaps even thousand of years, it is quite amazing that a simple conjecture could be found in 1971 by Singmaster. The conjecture is quite easy to state, but appears to be one of those that is going to be very hard to resolve.

Given a number $latex {a > 1}&fg=000000$, let $latex {S(a)}&fg=000000$ be the number of times that $latex {a}&fg=000000$ occurs in the triangle. That this number is finite follows from the fact that $latex {a}&fg=000000$ must occur within the first $latex {a+1}&fg=000000$ rows of the triangle. Of course it occurs twice in that row, as the second and second-last entry; call these the ``trivial occurrences.''

Singmaster's conjecture is: There is an absolute constant $latex {C}&fg=000000$ so that for all $latex {a > 1}&fg=000000$, $latex {S(a) \le C}&fg=000000$. Paul Erdos said that Singmaster's conjecture is ``probably true,'' but he suspected it would be very hard to prove. Singmaster stated the conjecture in a Math Monthly article aptly titled ``How Often Does an Integer Occur as a Binomial Coefficient?'' He proved that for $latex {a>1}&fg=000000$,

$latex \displaystyle S(a) = O(\log a). &fg=000000$

A more recent paper is by Daniel Kane who proves that

$latex \displaystyle S(a) = O \left(\frac{(\log a)(\log\log\log a}{(\log\log a)^{3}} \right). &fg=000000$

This is impressive, but far from the absolute constant that is conjectured. Why is this conjecture hard?

Diofactine Analysis?

Often hardness in number theory is signalled early by weird jumps in concrete examples. For instance the Collatz ``$latex {3n+1}&fg=000000$'' problem has a suddenly long path for $latex {n = 27}&fg=000000$. In Singmaster's case the unusual small number is:

$latex \displaystyle 3003 = \binom{78}{2} = \binom{15}{5} = \binom{14}{6}. &fg=000000$

No other number is known to occur 8 times. The next-highest number above 24,310 that occurs 6 times is

$latex \displaystyle \href{http://oeis.org/A003015}{61,218,182,743,304,701,891,431,482,520}. &fg=000000$

Nor is it known whether any central element $latex {\binom{2m}{m}}&fg=000000$ occurs more than the statutory 3 times. Now multiple occurrences come from whole-number solutions to equations of the form

$latex \displaystyle \binom{n}{k} = \binom{q}{\ell} = \binom{r}{m} = \dots &fg=000000$

To be sure, $latex {n}&fg=000000$ is recoverable as $latex {n!/(n-1)!}&fg=000000$, so multiplying one side of an equation by $latex {(n-1)!}&fg=000000$ while the other has $latex {n!}&fg=000000$ allows one to simulate a variable $latex {n}&fg=000000$ in an ordinary Diophantine set of equations. Hence an unrestricted theory of sets of factorial equations would reduce to ordinary Diophantine analysis. But perhaps an appropriate cost penalty against this trick can yield a nice theory of what we might call ``Diofactine'' equations.

One distinctive feature of such a theory would be relaince on analyzing the extension of factorial called the Gamma function. The proofs of the above upper bounds on $latex {S(a)}&fg=000000$ exemplify this: the idea is to replace the binomial coefficient by a smooth function based on the Gamma function. Then one needs to count the number of lattice points on a certain curve. This can be pushed to yield the log-type growth of the $latex {S}&fg=000000$-function. Whether it can yield a constant seems unclear.

I also find it impressive that Singmaster's conjecture was noticed only in 1971, and not years or centuries earlier.

Open Problems

Who really invented the Triangle? Or who discovered the Triangle? Is the conjecture correct---perhaps with $latex {C = 8}&fg=000000$?

One approach that I played with and could not make work is to look at the properties of the binomial coefficients modulo primes. The famous Lucas Theorem allows us to compute the residue of $latex {{n \choose k}}&fg=000000$ modulo a prime from just information about $latex {n,k}&fg=000000$ modulo $latex {p}&fg=000000$. I thought for a while that it might be able to at least give an elementary proof that $latex {S(a)}&fg=000000$ grows slowly. But I was unable to make this work. Perhaps someone else can.

Good luck. And keep looking at the Triangle to see if there are other patterns to be discovered.

P.S.: Yesterday was the 150th anniversary of the Gettysburg Address. Since we have been discussing chalk talks versus PowerPoint recently, we can't resist noting Peter Norvig's hilarious sendup of how Abraham Lincoln's presentation would have come out using PowerPoint.