This week I am in Bremen, where the 50th International Mathematical Olympiad is being held. A number of former Olympians (Béla Bollobás, Tim Gowers, Laci Lovasz, Stas Smirnov, Jean-Christophe Yoccoz, and myself) were invited to give a short talk (20 minutes in length) at the celebratory event for this anniversary. I chose to talk on a topic I have spoken about several times before, on “Structure and randomness in the prime numbers“. Given the time constraints, there was a limit as to how much substance I could put into the talk; but I try to describe, in very general terms, what we know about the primes, and what we suspect to be true, but cannot yet establish. As I have mentioned in previous talks, the key problem is that we suspect the distribution of the primes to obey no significant patterns (other than “local” structure, such as having a strong tendency to be odd (which is local information at the 2 place), or obeying the prime number theorem (which is local information at the infinity place)), but we still do not have fully satisfactory tools for establishing the absence of a pattern. (This is in contrast with many types of Olympiad problems, where the key to solving a problem often lies in discovering the right pattern or structure in the problem to exploit.)
The PDF of the talk is here; I decided to try out the Beamer LaTeX package for a change.
What's new 
18 comments
Comments feed for this article
20 July, 2009 at 5:33 am
buddy
Great talk T. I had a question which I found an answer to myself, but I’ll ask and answer it anyway:
If Vinogradov’s theorem says that the odd Goldbach conjecture is true for N sufficiently large, then why don’t we just check by computer all the remaining (finitely many) cases?
Answer, according to the wikipedia article, is that the number of remaining cases is still way too big to check. Vinogradov’s student Borozdin showed that there are about 3^14348907 cases that would need checking. In 2002 Liu Ming-Chit and Wang Tian-Ze lowered the threshold to about 10^1346.
Current computer implementations have only been able to check up to about 10^18, so there’s still a long way to go.
Thanks for a great read-
29 May, 2019 at 2:17 pm
YAW-MENSAH
je vais bien merci et vous
29 May, 2019 at 3:16 pm
pcaceres00
Not knowing patterns does not mean that patterns don’t exist. It just means that we are not intelligent enough to discover the patterns. Example: I keep reading that the non-trivial zeros of zeta in the critical line are random and unrelated, when there is a clear algebraic expression that links any two NT zeros and the Harmonic function.
20 July, 2009 at 5:52 am
Two gold medals in Bremen « Mathematics in Australia
[…] myself was at the event, giving a talk at the celebratory event for the 50th anniversary of the […]
22 July, 2009 at 9:33 pm
Manjil P. Saikia
Great talk, I enjoyed the pdf file.
24 July, 2009 at 2:26 am
weiyu
The slides are very enjoyable, like telling a story…
10 August, 2009 at 5:25 pm
hezhigang
Prof Tao’s lectures are wonderful, I have some naive conjectures and questions:
1. I notice the series of reciprocal squares converge to pi^2/6, smaller than twin prime constant which is 1.902160583104 approximately, does it deduce that twin primes are denser than squares?
2. some research show that prime sequence is chaotic, some research show that prime number is pseudorandom, which standpoint is more exact?
3. between additive number theory and multiplicative number theory, which branch is more essential?
11 August, 2009 at 9:23 am
Jonathan Vos Post
“twin primes are denser than squares” – but we don’t know if there are really an infinite number of twin primes, though no obstruction is known, and it’s generally considered extremely likely.
10 September, 2009 at 1:41 am
ippaso
Very interesting PDF. Can we found the text or a clip of the talk somewhere?
14 September, 2009 at 2:41 am
Structure and randomness in the prime numbers (IMO Festschrift submission) « What’s new
[…] in math.NT, paper | Tags: international mathematical olympiad | by Terence Tao A few months ago, I gave a talk at the IMO in Bremen on “Structure and randomness in the prime numbers”. I have now […]
18 March, 2010 at 5:17 am
Primes! And More Primes! And More Primes…. « Math Life
[…] If you’re interested in this sort of thing, I would recommend taking a look at a blog post by Fields Medalist Terry Tao on structure and randomness in primes. […]
26 July, 2011 at 6:28 am
IMO 2009 | Cogito
[…] the slide from Tao’s IMO lecture, Structure and Randomness in the Prime Numbers (pdf), on his blog. Or watch a 1-hour public seminar he gave on the topic in […]
2 July, 2013 at 9:27 am
Bogdan
You say “We believe that the primes do not observe any significant
pattern beyond the obvious ones”. Are there exist a formal conjecture which formalises this statement? This would be a “grand unifying conjecture” of the prime distribution theory, which would imply the prime tuples conjecture (including twin prime conjecture), the Riemann Hypothesis, the Cramér’s conjecture, and all other not-yet-asked questions which are easy to verify assuming that “the primes do not observe any significant pattern beyond the obvious ones”.
If not, what do you think is the major difficulty in the formulation of such a conjecture?
2 July, 2013 at 1:14 pm
Richard
Cramér’s model, providing heuristic motivation for numerous conjectures, is pretty much it.
3 July, 2013 at 3:20 am
Bogdan
No, it isn’t. I am asking about the formal conjecture, which can (in principle) be proved, and, after this, all these `heuristic motivation’ would become a strict proof. There is a formal definition of a random sequence ( see e.g.
http://mathdl.maa.org/images/upload_library/22/Ford/Volchan46-63.pdf ), and, for any random sequence A, all these “conjectures” (like there are infinitely many members p,q of A with |p-q|=2) are very easy theorems. This, however, is the formal definition of what is called “Basic heuristic” at https://terrytao.wordpress.com/2012/09/18/the-probabilistic-heuristic-justification-of-the-abc-conjecture/ Because primes is not completely random sequence, we need to formalise the notion of “Advanced heuristic” to formulate the iniversal conjecture…
2 July, 2013 at 10:38 pm
Terence Tao
I don’t think there is a formal one-size-fits-all conjecture for this, but I expand a little more on this heuristic at https://terrytao.wordpress.com/2012/09/18/the-probabilistic-heuristic-justification-of-the-abc-conjecture/
16 March, 2016 at 3:38 pm
Phil Timbrell
May I ask a simple question from a non mathematician who loves maths! All integers are either in the prime set or the non prime set. So if we consider the set of non primes, is it not true they are the result of a mathematical function – that is the multiplying together of any two integers. If they are the result of a function then surely there must exist a way to describe them mathematically. And if you can describe a set of non prime mathematically then there must be a function to describe primes (those that are not non primes). In short, whilst the function may be incredibly complex or even impossible to describe, there must exist a pattern to primes, no matter how complex. Sorry if this is garbage to exprts but it seems logical to me.
For 16 years now I have been on the track of the Collatz conjecture, and whilst I know the experts have been unable to solve it since 1937 using traditional methods, I have been employing some alternative methods and am finding distinct patterns emerge. I believe there is a solution to that conjecture as well and someone one day will solve it, maybe not me but there is a pattern there, it only has to be coded.
29 November, 2017 at 5:04 pm
Pedro Caceres
I have never accepted the idea that Prime numbers are random. After time of research I have been able to formulate an algorithm to understand where Primes lie.
The set of prime numbers can be expressed as (Caceres, 2017):
{Primes} =
{2,3}
∪
{6kn+1 | kn≠6xy+x+y and kn≠6xy-x-y for all x,y∈N}
∪
{6km-1 | km≠6xy-x+y for all x,y∈N}
The generation of primes using this algorithm is complete based on the following observation:
1: With k=6xy+x+y, we have 6k+1 = 36xy+6x+6y+1 = (6x+1)(6y+1), i.e. all products of two factors both equivalent to +1 (mod 6);
2: With k=6xy-x-y, we have 6k+1 = 36xy-6x-6y+1 = (6x-1)(6y-1), i.e. all products of two factors both equivalent to -1 (mod 6);
3: With k=6xy-x+y, we have 6k-1 = 36xy-6x+6y-1 = (6x+1)(6y-1), i.e. all products of two factors, one equivalent to +1 (mod 6) and the other equivalent to -1 (mod 6).
Starting with the integers equivalent to ±1 (mod 6) and excluding these three sets leaves those integers equivalent to ±1 (mod 6) which cannot be represented as a product of two factors equivalent to ±1 (mod 6), i.e. the primes p≥5.
The first numbers in the generator series kn:
kn= 1, 2, 3, 5, 7, 10, 11, 12, 13, 16, 17, 18, 21, …
Generating primes pn=6*kn+1:
pn= 7, 13, 19, 31, 43, 61, 67, 73, 79, 97, 103, 109, 127,…
The first numbers in the generator series km:
km= 1, 2, 3, 5, 7, 8, 9, 10, 12, 14, 15, 17, 18, 19, 22 …
Generating primes pm=6*km-1:
pm= 5, 11, 17, 29, 41, 47, 53, 59, 71, 83, 89, 101, 107, 113, 131…