The Pigeon-hole Principle
I've mentioned the "pigeon-hole principle" briefly before, and it crossed my radar again when James Tanton put up a video on it here:
It is one of those intuitive mathematical concepts that seems so obvious upon first glance that one wonders why it must even be stated, or how it could possibly be of any use... and yet that is the essence and beauty of mathematics: that basic, seemingly obvious ideas can be massaged by logic to produce significant and less obvious outcomes and ramifications.
If you're familiar with the pigeon-hole principle (it is especially used in combinatorics) you understand what I mean; if you're not familiar with it, then I won't even state it lest you think it too boring to bother with, but direct you instead to another link further elucidating it:
« During Cicada Boom, Birds Mysteriously VanishHow a Memory Game Can Multiply Your Brain’s Computing Power »
Primal Madness: Mathematicians’ Hunt for Twin Prime Numbers
By Amir Aczel | July 10, 2013 9:50 am
On April 17 of this year, a relatively unknown Chinese-born mathematician in his fifties—who since coming to the U.S. had to work odd jobs, including at a sandwich shop, before joining the faculty of the University of New Hampshire—announced a discovery that shocked the world of mathematics. Yitang (“Tom”) Zhang just solved one of the most persistent mysteries in the theory of numbers—of the kind that the famous British mathematician G. H. Hardy had described as being “at present beyond the resources of mathematics.”*
Ever since the Greek mathematician Euclid of Alexandria proved 2,300 years ago that there are infinitely many prime numbers, mathematicians have been intrigued by the existence of twin primes, a pair of prime numbers that differ by two—such as 11 and 13; 17 and 19; 29 and 31; and 41 and 43. Other than the first pair of prime numbers, 2 and 3, which are adjacent to each other, all further pairs of primes must be separated by at least one number because even numbers greater than two cannot be primes (since they are divisible by 2).
Mathematicians have wanted to learn about the behavior of pairs of primes, in particular pairs separated by one number, such as the twin primes in the examples above. Their hunt even has a name, the “twin prime conjecture,” which asks: are there an infinity of twin primes?
The reason for this interest is that prime numbers become rarer as the natural numbers (the positive integers) grow and progress toward infinity. For example, there are 25 prime numbers in the first set of 100 positive integers; the last block of 100 numbers below and including 1,000 has a little more than half this number, with 14 primes; the last block of 100 just below and including the number 1,000,000 has 8 primes; and the last 100 numbers below and including a trillion have only four prime numbers among them. So we notice a constant but slow decrease in the density of primes as the numbers move forward.
A theoretical estimate of the rate of decrease in the primes is given by the celebrated Prime Number Theorem, proposed by Carl Friedrich Gauss in 1792 and proved a century later by Jacques Hadamard and Charles de la Valée Poussin, which says that the number of primes up to a number n is approximately n/ln(n), where ln is the natural logarithm.
But what happens to prime pairs as primes thin out? Mathematicians have wondered that for generations. Do pairs of primes have ever-increasing gaps between them, as might be expected by the thinning-out of the primes themselves? Or are there always prime pairs with a constant gap between them as the numbers continue their march to infinity?
Prime number gaps
It is within this context that Zhang’s new theorem comes in, and from which it derives its importance: Zhang’s work showed that, as the numbers progress, there are always pairs of primes that are separated by at most 70,000,000. It thus says that there are, in fact, infinitely many pairs of prime numbers whose “distance,” meaning the gap of numbers between them, is at most 70,000,000.
This number is huge, of course, but it’s the principle that counts here. His proof showed that while the density of the prime numbers does decrease constantly, there are still prime pairs that maintain a given distance between them—rather than that distance becoming necessarily larger and larger as the numbers approach infinity.
That finding may be a step toward a similar proof on the infinitude of twin primes—and thus a solution to the famous “twin prime conjecture.”
A Herculean feat
Zhang was my colleague at the mathematics department of the University of New Hampshire when I taught there a few years ago, and I remember him wandering the corridors deep in thought over several years: it took a Herculean feat for a single mathematician—working all alone for days and nights on end—to come up with this stunning mathematical finding. But completing it, he launched a revolution in analytic number theory, the mathematical area that uses methods from analysis to prove results in number theory.
And the value of Zhang’s achievement goes beyond the fact he proved about prime number pairs. Through his work, Zhang inaugurated a new method (based on work pioneered by other mathematicians) for analyzing the behavior of prime pairs. In Zhang’s methodology, a delicate balance is kept between the competing needs of two terms in a complicated equation. One term needs an exponent Zhang employed to be not too far above 1/4, and the other “wants” it to be not too far below 1/4 (raising a term to the power 1/4 means taking its fourth root).
Zhang solved this problem by adding a small term, 1/1168, to the exponent 1/4. When we asked him why he used this particular number, he answered: “I was tired…and this number worked.”** It was the value 1/1168 that led to the gap of 70,000,000 between two primes. So number theorists have rushed to see if they could fiddle with the coefficient 1/1168 and thus reduce the gap between primes.
Hunting for prime numbers online
Prime number research has long used the Internet as a tool for collaborative work. Some may be aware of the Great Internet Mersenne Prime Search (GIMPS)—the ongoing quest to find larger and larger prime numbers. GIMPS works through distributed computing, meaning that many people around the world participate in this active search by contributing the use of their computers to perform partial tasks in a unified large-scale search for primes. The current record was achieved on January 25, 2013, when the prime number 257,885,161-1 was discovered. This is a number with 17,425,170 digits!
As soon as they learned about Zhang’s result, mathematicians working in the field of analytic number theory decided to band together similarly through the Internet, and to race to narrow the gap between successive primes. On June 5th, T. S. Trudgian of the Australian National University announced in a paper posted online that he had reduced the prime distance from Zhang’s 70 million to 60 million. Other results followed in quick succession, with mathematicians narrowing the gap further (by tweaking Zhang’s original constant of 1/1168, and using other technical refinements and improvements), first to several millions, then to a few hundred thousand, and now even lower.
Terence Tao of UCLA, a former child prodigy, MacArthur (“genius award”) Fellow, and a 2006 Fields Medal recipient, assumed leadership in this area and now coordinates the prime gap Internet race in a project called Polymath8. A recent e-mail from Tao announced the latest result: a gap of no more than 12,006 numbers between primes, and a provisional gap of only 6,966—conditional on the verification of some technical conditions. The details are in the link above.
Tao cautions on Polymath8 that the method of proof needed to clinch the celebrated “twin prime conjecture” may require far more complicated work. However, with so many brains now working collaboratively on this problem, perhaps we will see a definitive solution to this age-old mystery in the not-too-distant future–now that Zhang’s method has indicated a direction, provided a solution to a closely related question, and blazed the trail forward.
* G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 5th edition, Clarendon Press, Oxford, 1989, p. 5.
** Yitang Zhang, “Bounded Gaps Between Primes,” a presentation at the Department of Mathematics, University of Massachusetts, Boston, June 4, 2013.
Image courtesy pashabo / Shutterstock
CATEGORIZED UNDER: Space & Physics, Top Posts
MORE ABOUT: arithmetic, mathematics, number theory, prime number theorem, prime numbers