Finding Patterns In Ancient Objects

Ancient mathematical objects can still contain secrets

Recreational Mathematics source

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 wish to talk about Pascal’s Triangle, and a beautiful conjecture of Singmaster on the structure of the famous triangle.

We all know that Pascal’s famous triangle is formed from the binomial numbers . The first row is , the second is , the third is , then comes , and so on:

“Poetic Mind” source

The Triangle is related to the equally famous Binomial Theorem:

Theorem 1 For any and real numbers and a natural number,

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 be a prime. Then by the Binomial Theorem it follows that

But the sum is easily shown to be congruent to . This uses that for prime and . Thus,

The general case can be proved in the same manner.

Who Invented This 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 . 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.

Probably others also knew the Triangle and the theorem, and some even had proofs.

Magic Properties of Pascal’s Triangle

There are many patterns to be found inside the Triangle. Of course the row sums are powers of , which follows directly from the Binomial Theorem. The Triangular Numbers are found in the Triangle as a diagonal:

See the page “All You Ever Wanted to Know About Pascal’s Triangle and More” for many more interesting patterns, including a recurring “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 , let be the number of times that occurs in the triangle. That this number is finite follows from the fact that must occur within the first 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 so that for all , .

Paul Erdős 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 ,

A more recent paper by Daniel Kane proves that

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 “” problem has a suddenly long path for . In Singmaster’s case the unusual small number is:

Together with the two trivial occurrences this makes 8 appearances for 3003. There is an infinite family of numbers occurring 6 times, but:

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

61,218,182,743,304,701,891,431,482,520.

Nor is it known whether any central element occurs more than the statutory 3 times. Now multiple occurrences come from whole-number solutions to equations of the form

The constituents of these equations are all factorials. Diophantine equations are ones required to be solved in whole numbers. We wonder if there is a particular theory of equations that must be solved in factorial numbers.

To be sure, is recoverable as , so multiplying one side of an equation by while the other has allows one to simulate a variable 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 reliance on analyzing the extension of factorial called the Gamma function. The proofs of the above upper bounds on 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 -function. Whether it can yield a constant seems unclear.

We 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 ?

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 modulo a prime from just information about modulo . I thought for a while that it might be able to at least give an elementary proof that 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.

[added needed qualifier “known to occur” for 6-time numbers, fixed erroneous entry 186->286 in triangle diagram (original).]