Our whole life is a succession of problems that we solve more or less successfully. Our brain has evolved precisely to solve these problems. Problem solving is one of the most characteristic human activities. Mathematics can be defined as the art of solving problems. That is why it is so useful and why we are so adapted to be mathematicians. Every person has a mathematician within.
Mathematics abstracts the problems of life by eliminating the passion, desire, feelings,… that often prevent us from seeing daily situations clearly. But they are the same problems. Geometry is one of the branches that developed first because of the practical importance of geometrical problems.
We have learned a lot about how to pose and solve problems. The Hungarian mathematician George Pólya put a lot of effort into isolating problem solving techniques – in my opinion with great success. He wrote a book that I cannot recommend highly enough.
G. Pólya, How to solve it, Princeton University Press 2004.
In this book Pólya considers general techniques, analogy, generalisation, etc. A fundamental idea of the book is: If you can’t solve a problem, then there is an easier problem that you can’t solve either – find it. The point of this advice is that the solution of the easier problem may be the key to the solution of the harder one. This in the practice of mathematicians translates into using techniques that others have been able to use in solving similar problems.
Mathematicians follow this general procedure. When faced with a new problem, the mathematician tries to look for simpler analogous problems that he already knows how to solve and tries to see if the solution of the known problem inspires him how to solve his initial problem. Often the help of an analogous problem is not enough and a new idea has to be added. In this way the solution methods are refined over time.
When someone finds the solution to a problem that has already been considered unsuccessfully by other mathematicians, it is certain that the solution contains some new idea and everyone tries to apply it to the solution of other similar problems, which they did not know how to solve before. This is usually successful and the new technique is incorporated into the mathematician’s toolbox.
Today we will see one of these tools in action. The first idea for the method we are dealing with came from Eratosthenes. The problem he wanted to solve was to give a list of all the prime numbers less than a given number. Suppose we want to list all the prime numbers less than 30. To do this, we write a list of all the numbers less than 30. We start with the first prime number \(2\), we cross out all the multiples of \(2\), that is, all the pairs, except \(2\). All the crossed out numbers are composites because they are divisible by \(2\) and different from \(2\). Next we look for the first number not crossed out, \(3\), and we cross out the multiples of \(3\), that is, 6, 9, 12, 15, 18, 21, 24, 27 and 30. Continue the process with the multiples of 5. The next number not crossed out is 7, but since \(7^2=49>30\), any composite number \(<30\) has a prime divisor \(<7\) and is already crossed out. Therefore all numbers not crossed out are prime and are all numbers less than 30.
This little technique of sifting the numbers so that only the ones we are interested in are left, has received numerous variations and extensions until it has become one of the most powerful tools of Number Theory.
Henryk Iwaniec and John Friedlander, two experts on the subject, published in 2010 the monograph Opera de Cribro (a 527-page book) presenting the method and its variants. In the introduction they write:
What possesses us to write a book on sieve methods? Hopefully we have something to say that is worth listening to and, if we didn’t write it, maybe a little something would be lost.
Eratosthenes, around 300 BC, had this first idea for tabulating the primes. After a long space of time Legendre used it to give an exact formula for \(\pi(x)\) the number of primes \(\le x\). This formula seemed of very little practical value.
The first to use it to good effect was Brunn in 1915, who managed to prove that, whether the set of twin primes (that is, those primes \(p\) such that \(p+2\) is also prime) is finite or infinite in number, the sum of their inverses \(\sum{1\over p}<+\infty\). Landau was the referee of Brunn’s article. At first glance, and seeing that its starting point was Legendre’s formula, Landau thought it must be the work of a madman and kept the article in his desk drawer for months without reading it. Landau finally read it and recognised the value of Brunn’s work.
Over many years the method has continued to receive new ideas, coming from very important mathematicians, such as Selberg, Bombieri, and others.
This can serve as an example of how mathematics evolves. New techniques emerge which are then refined and over time make it possible to solve problems that at first seemed impossible to solve.
This is why mathematics becomes a profession. There is a professional way of working. By learning each time new techniques and applying them successively to more and more complicated problems. But let’s go a little further to get closer to the problem I want to talk about today.
Diophantus and Fermat
It seems that Diophantus already knew that the primes which when divided by 4 give remainder 1 can be put as the sum of two squares \(5=4+1\), \(13=9+4\), \(17=16+1\), \(29=25+4\),… while the primes which give remainder \(3\) such as \(7\), \(11\), \(19\), \(23\),… cannot be written in this way. Apparently Fermat succeeded in proving this result, which is the model for many other similar theorems.
Let us define a function \(\chi\) on the set of natural numbers, in such a way that \(\chi\) is worth \(1\) in the numbers that when divided by \(4\) give remainder \(1\), it is worth \(-1\) if the remainder is \(3\) and it is worth \(0\) if the number is even. This function has an interesting property related to the observation of Diophantus and Fermat. Given any natural number \(n\) let \(r(n)\) be the number of solutions of the equation \(n=x^2+y^2\), where \(x\) and \(y\) are positive or negative integers. Well, we have an exact expression $$r(n)=4\sum_{d\mid n}\chi(d),$$ where the sum refers to all the positive divisors \(d\) of the number \(n\).
For example, the divisors of 45 are 1, 3, 5, 9, 15, 45 and then \begin{align*}4\sum_{d\mid n}\chi(d)&=4(\chi(1)+\chi(3)+\chi(5)+\chi(9)+\chi(15)+\chi(45))\\&=4(1+(-1)+1+1+(-1)+1)=8.\end{align*} And indeed \(45 = x^2+y^2\) has the \(8\) solutions $$\{x,y\}=\{\pm\,6,\pm 3\},\quad \{x,y\}=\{\pm\,3,\pm 6\}.$$
Hardy and Littlewood conjectures
The pair of English mathematicians published in 1922/23 their paper Some problems in ‘Partitio Numerorum’ III in which they attack Goldbach’s conjecture: every even number greater than 2 is the sum of two primes. They succeed in proving, assuming the generalised Riemann hypothesis, that every sufficiently large odd number is a sum of three prime numbers. To do so, they use the circle method, which has nothing to do with the sieve method. What they do is to give an approximate expression for the number of representations \(n=p_1+p_2+p_3\). What interests us here is that although they cannot finish off the application of their method when they apply it to other problems, they are able to predict what the asymptotic approximation to the number of solutions will be. In this way they formulate numerous conjectures. We are interested in one of their conjectures:
Conjecture J. Let \(N(n)\) be the number of solutions of the equation \(n=x^2+y^2+p\) with \(p\) prime and \(x\) and \(y\) integers, then $$N(n)\sim C A(n) \frac{n}{\log n},\qquad C=\pi\prod_{p>2} \Bigl(1+\frac{\chi(p)}{p(p-1)}\Bigr),$$ where \(A(n)\) is the rational number $$A(n)=\prod_{p\mid n, p>2 }\Bigl(\frac{(p-1)(p-\chi(n))}{p^2-p+\chi(p)}\Bigr).$$
In 1957 Hooley succeeded in proving the J conjecture by assuming that the generalised Riemann hypothesis is true. In 1960 the Russian mathematician Linnik introduced his dispersion method with which he was able to prove this conjecture, without making use of any additional hypothesis. In 1963 the Russian mathematician B. M. Bredihin, following the pattern of applying new methods to similar problems, applied Linnik’s method of dispersion to a related problem. He succeeded in proving:
Bredihin Theorem. Let \(a\in\mathbf{Z}\) be fixed, for \(x>1\) let \(S(x)\) be the number of solutions of $$p=u^2+v^2+a,$$ where \(u\), \(v\in\mathbf Z\) and \(p\le x\) is a prime number. Then $$S(x)=C B(a)\frac{x}{\log x}+R(x), \qquad C=\pi\prod_{p>2}\Bigl(1+\frac{\chi(p)}{p(p-1)}\Bigr),$$ $$B(a)=\prod_{p\mid a, p>2 }\Bigl(\frac{(p-1)(p-\chi(n))}{p^2-p+\chi(p)}\Bigr),$$ and finally \(R(x)=O(x(\log x)^{-1.042})\).
In particular Bredihin’s work proved for the first time the existence of infinite primes of the form \(u^2+v^2+1\). The proof is long and very technical.
What has prompted me to talk about this theorem is a paper published by Friedlander and Iwaniec in which they give a proof of a particular case of Bredihin’s work. Practically in one page they give the proof of the case \(a=1\). The main ingredient of this simplified proof is Theorem 22.1 from their book “Opera de cribo”. This is a version of the Bombieri-Vinogradov theorem on the distribution of primes in arithmetic progressions. Using sieving methods, a slightly higher Bombieri-Vinogradov theorem is obtained than would be obtained assuming the Riemann hypothesis. This is what they need in the proof.
Friedlander and Iwaniec’s proof is short and begins by making use of the observation of Diophantus and Fermat and the subsequent solution discussed above. We want to find the number of pairs \((u,v)\) such that the number \(p=u^2+v^2+1\) is prime and also \(p\le x\).
For each fixed \(p\) the number of solutions of \(p-1=u^2+v^2\) is $$ r(p-1)=4\sum_{d\mid p-1} \chi(d).$$ Moreover, since \(\chi(2n)=0\), we will have that \(r(p-1)=r(\frac{p-1}{2})\). Therefore the number \(S(x)\) of primes in the form \(p=u^2+v^2+1\) will be equal to $$S(x)=4\sum_{p\le x}r\Bigl(\frac{p-1}{2}\Bigr).$$
This is essentially the starting point of Friedlander and Iwaniec’s proof. If you want to see how it culminates in just one page you can consult the reference J. Friedlander and H. Iwaniec, On a Theorem of Bredihin and Linnik, arXiv:1807.06648.
Learn more
The reference of the book by Friedlander and Iwaniec is
J. Friedlander y H. Iwaniec, Opera de Cribro, American Mathematical Society, Providence, Rhode Island, 2010.
The paper we discuss can be found on the web, as the authors indicate it shows well how proofs can be simplified by applying refined techniques. The work is easy to understand modulo the acceptance of Bombieri’s result.
J. Friedlander y H. Iwaniec, On a Theorem of Bredihin and Linnik, arXiv:1807.06648.
Bredihin’s article is not translated from Russian. The original is
B. M. Bredihin, Binary additive problems of indeterminate type. II. Analogue of the problem of Hardy and Littlewood, Izv. Akad. Nauk SSSR Ser. Mat. 27 (1963) 577-612.
The highlighted image is taken from Wikimedia Commons: Sieve in the Museum of Castillo de Guadalest. It is a sieve in the Museu Etnològic del Castell de Guadalest. The author of the picture is Joanbanjo.
Leave a Reply