Two principles on the finite/infinite relation
One of the axioms of mathematics is that there exists an infinite set. Without this axiom our mathematics would be much weaker. Many of our theorems would fall like a house of cards. Newton or Gauss would probably have hesitated to accept our axiom (although without being aware that they were using it). We have accepted it for our comfort. Faith, that some people say …
With time we have learned to handle infinity properly. We can summarize our experience in two principles. The first one is due to André Bloch (1893-1948), to whom I dedicated an entry. He was a peculiar mathematician. Bloch’s principle tells us that in reality the infinite brings us nothing new, that everything we find in the infinite, we can see in the finite:
Nihil est in infinito quod non prius fuerit in finito:
There is nothing in the infinite that does not exist before in the finite.
The second principle is due to Frank P. Ramsey (1903-1930), a mathematician who shattered all preconceived ideas about our profession. We have long missed a movie about his life. Ramsey’s principle is like an opposite of Bloch’s principle. It tells us that in infinity we can find everything.
Complete disorder is impossible; in a sufficiently large structure we will always find order.
A lemma in one of Ramsey’s papers in logic has given rise to a whole branch of combinatorics, the Ramsey Theory. According to the principle we can find everything in infinity. To illustrate this, consider the problem we are dealing with today,. The ordered structure, which we will search for at infinity, will be a finite set \(S\) of natural numbers such that $$\sum_{n\in S}\frac1n=1.\qquad \text{($*$)}$$ The corresponding Ramsey type problem would be:
(1) If we color all natural numbers with \(r\) colors, then there exists a finite, single-colored set \(S\) that satisfies \(\sum_{n\in S}\frac1n=1\).
This statement was posed as a conjecture by Erdös and Graham in 1980. Even if we prove it to be true, we will not know which color we will find the ordered structure \(S\). In the same article Erdös and Graham conjecture the density version of the conjecture.
(2) If we have a set \(D\) of natural numbers with positive density, then there exists \(S\subset D\) such that \(\sum_{n\in S}\frac1n=1\).
This is general feature: Ramsey type problems have a stronger version assuming density. A set \(A\subset\mathbf{N}\) is said to have density \(d(A)\) if the following limit exists $$\lim_{N\to\infty}\frac{\text{cardinal}\{n\in A \colon n\le N\}}{N}=d(A).$$
For this type of problems usually there is also a Turán version. In the Turán type version one look for a set as large as possible that does not contain the ordered structure.
Later (Sao Paulo, 1994) Erdös posed the corresponding Turán-type problem:
Problem. Given \(\delta>0\), for \(N\) sufficiently large and \(D\subset \{2,3,\dots, N\}\) such that $$\sum_{n\in D}\frac1n>\delta\log N,$$ is it true that there exists \(S\subset D\) such that \(\sum_{n\in S}\frac1n=1\)?
Here Erdös does not dare to conjecture, he just asks and shows his interest in the problem by offering a prize of $ 100 for a positive or negative solution to the problem.
We will see how Bloch’s principle works in the proofs of these conjectures. One is left with a finite, but sufficiently large, part of the structure, and in that finite set tries to find \(S\). It is as if we discard infinity.
Ernest S. Croot III’s Solution
The positive solution of the first conjecture of Erdös and Graham was published in 2003 by the journal Annals of Mathematics. An article of only 11 pages but with a very delicate construction.
Following Bloch’s principle, we must find a finite set \(U\) of naturals such that if we color its elements with \(r\) colors, there is necessarily a single-colored set \(S\) such that \(\sum_{n\in S}\frac1n=1\). Croot proves that if \(b=e^{167000}\), then the set of natural numbers \(U\) contained in the interval \([2, b^r]\) has that property.
Our infinity has become finite, transformed into that gigantic number \(b\). It is not necessary to color all the natural numbers, it is enough to color the set \(U=[2, b^r]\cap\mathbf{N}\) which is finite (although very large).
In the proof a detector of sets \(S\subset D\) with the property that the sum \(\sum_{n\in S}\frac1n\) is an integer is used, searching for subsets of a prefixed set \(D\) (the detector is Fourier analysis). Let \(P\) be the least common multiple of the numbers in \(D\). For each \(S\subset D\) we will have $$\sum_{n\in S}\frac{1}{n}=\frac{a}{P}, \qquad a\in \mathbf{N}.$$ The basic idea of the detector is to observe that $$\frac{1}{P}\sum_{h\bmod P}e^{2\pi i\frac{a}{P} h}=\begin{cases}1 & \text{ if $a/P$ is an integer}\\0 & \text{ if $a/P$ is not an integer}\end{cases}$$ because the sum of the \(n\)-th roots of unity is \(0\) (unless \(n=1\)).
Now let’s consider the product $$E(h)=\prod_{n\in D}(1+e^{2\pi i h/n})=\sum_{S\subset D}\exp\Bigl(2\pi i h\sum_{n\in S}\frac{1}{n}\Bigr).$$ Each subset \(S\) of \(D\) contributes with one summand. If we now add for the \(h\) modulo \(P\), each \(S\subset D\) with \(\sum_{n\in S}\frac1n\in\mathbf{Z}\) contributes one unit to the sum. It turns out then that $$\text{cardinal} \Bigl\{S\subset D\colon \sum_{n\in S}\frac1n\in\mathbf{Z}\Bigr\}$$ is equal to $$L:=-1+\frac{1}{P}\sum_{P/2<h\le P/2}E(h).$$
The \(-1\) comes from the fact that we do not want to count the set \(S=\emptyset\), which also gives a \(1\) in the sum.
We can write $$E(h)=\exp\Bigl(\pi i h\sum_{n\in D}\frac1n\Bigr)\cdot2^{|D|}\prod_{n\in D}\cos(\pi h/n).$$ Now the remaining problem is to find a set \(D\) such that we can prove that the sum \(L\) is positive and furthermore that $$\sum_{n\in D}\frac1n<2.$$ If we achieve this, the sum \(L\) is a natural number, but each non-zero summand is \(1\) (because it is less than \(2\). Each summand \(=1\) corresponds to a subset \(S\subset D\) verifying \(\sum_{n\in S}\frac1n=1\).
The choice of the set \(D\) is complicated. Croot sets \(N\) large and takes \(D\) a subset of another set \(C\). Fix two positive numbers \(\delta\) and \(\theta\) with \(\delta+\theta<\frac14\) and take \(C\) such that
- The elements of \(C\) are large numbers: \(C\) is a subset of the interval \([N, N^{1+\delta}]\).
- The elements of \(C\) have enough prime factors: each element of \(C\) has on the order of \(\log\log N\) prime factors.
- The numbers in \(C\) are smooth: Every prime power \(p^a\) that divides some \(n\) in \(C\) is small: \(p^a\le N^\theta\).
- \(C\) is sufficiently large: \(\sum_{n\in C}\frac1n>6\).
The main theorem of Croot states that such a set \(C\) always contains a subset \(S\) with \(\sum_{n\in S}\frac1n=1\). Simply because it contains a suitable \(D\).
Thanks to a theorem of Hardy and Ramanujan condition 2 is satisfied by practically any number. They proved that practically all numbers of size \(N\) have of the order of \(\log\log N\) prime factors. To obtain enough numbers satisfying conditions 1, 2 and 3 so that 4 is still satisfied it is necessary to use Dickman’s function \(\rho(x)\) and the following theorem.
Theorem. For fixed \(a>0\) it is the case that for all \(0<b<a\): the cardinal of the set of natural numbers \(n\le x\) such that all their prime factors are \(\le x^{1/b}\) is of order \(x\rho(b)\).
The Dickman function is defined to be \(\rho(t)=1\) for \(0\le t\le 1\), and for \(t>1\) it satisfies the equation $$t\rho'(t)=-\rho(t-1).$$
It is by using Dickman’s theorem that the giant number \(e^{163550}\) appears such that if \(N>e^{163550r}\) , there exists a single-colored set \(C\) such that $\sum_{n\in C} \frac1n>6$.
Erdös’ second conjecture
Erdös and Graham conjectured that if we have \(A\subset \mathbf{N}\) with density \(d>0\), then there must exist a subset \(S\subset A\) such that \(\sum_{n\in S}\frac1n=1\).
Croot’s solution does not work in this case because the non-smooth numbers, that is to say those \(n\) that have some prime factor \(\ge n^{1/4}\) have positive density. In that set, in spite of having positive density, Croot’s argument does not achieves anything.
In one of his papers Erdös even enunciates the finite result leading to that of density.
Erdös’ conjecture. If \(N\) is sufficiently large and \(A\subset\{2,3,\dots, N\}\) is such that $$\sum_{n\in A}\frac1n>\delta\log N,$$ then there is a subset \(S\subset A\) such that $$\sum_{n\in S}\frac1n=1.$$
Thomas F. Bloom’s solution
Last December Thomas F. Bloom uploaded to arXiv his positive solution to the density conjecture and also to the Erdös question.
It is known that Erdös sometimes offered a cash prize to whoever solved some of his conjectures. After Erdös’ death, Graham kept these offers at his own expense. But Graham died in 2020. This is why Thomas F. Bloom will not receive the prize, although he certainly deserves it.
Bloom notes that the logarithmic density is better suited to the problem $$\delta(A)=\lim_{N\to\infty}\frac{1}{\log N}\sum_{n\in A, n\le N}\frac1n.$$ In fact, when \(d(A)\) exists then \(\delta(A)\) exists and they are equal. This is why we can work with the logarithmic density.
But Bloom proves more. He proves that if a set has positive upper density, i.e., if $$\limsup_{N\to\infty}\frac{\text{cardinal}\{n\in A \colon n\le N\}}{N}>0$$ then it contains a finite set \(S\) with \(\sum_{n\in S}\frac1n=1\).
Again the problem is reduced to a finite statement. Bloom’s main result is a direct answer to the last of Erdös’s problems.
Theorem. There exists a constant \(C\) such that if \(A\subset\{1,2,\dots, N\}\) and $$\sum_{n\in A}\frac{1}{n}\ge C\frac{\log\log \log N}{\log\log N}\log N$$ then there is a subset \(S\subset A\) such that $$\sum_{n\in S}\frac1n=1.$$
Thus solving the Erdös problem for any value of \(\delta\).
The proof broadly follows Croot’s argument. More precise and technical hypotheses are needed to overcome the difficulties. The smoothness condition has to be much weaker, because as we already said the non-\(N^\theta\)-smooth numbers have positive density; there may not be any \(N^\theta\)-smooth in our set \(A\). The conditions to be required on \(A\) now are
- The elements of \(A\) are big numbers \(A\subset[N^{1-1/\log\log N},N]\).
- The elements of \(A\) have enough prime factors: $$\frac{99}{100}\log\log N\le \omega(n)\le 2\log\log N.$$ But in addition, every \(n\in A\) is divisible by a prime \(p\) such that \(5\le p\le (\log N)^{1/100}\).
- The elements of \(A\) are smooth: Every prime power \(p^a\) that divides some \(n\in A\) is small \(p^a\le N^{1-6/\log\log N}\).
- \(A\) is large enough $$\sum_{n\in A}\frac1n\ge (\log N)^{1/200}.$$
With these conditions \(A\) contains a subset \(S\subset A\) with \(\sum_{n\in S}\frac1n=1\).
As we can see, condition 3 has been relaxed a lot, now the powers of the primes dividing the elements of \(A\) can be much larger, but condition 4 is more demanding. The proof uses the same artifice to detect \(S\)-sets.
Bloom’s proof needs to overcome many technical difficulties. For example, one of the differences is that it sets an interval \([y,z]\) small in the sense that \(1\le y\le z\le (\log N)^{1/500}\) and proves first that there exists a finite \(S\) such that \(\sum_{n\in S}\frac1n=d\) a natural number with \(x\le d\le z\). This gives him more flexibility for finding \(S\). Then with an iterative process he gets the set with \(d=1\); this step is crucial in the solution of the density problem.
On the role of publications in mathematics
One way to distinguish a scientific article by a physicist from that of a mathematician is to look at the references. A physicist cites the authors, the year of publication and the initials of the journal. A mathematician cites the authors, the title of the paper, clearly indicates the journal, the volume, the year and the pages. The physicist’s references do not seem to be aimed at allowing anyone locating them, a mathematician instead tries to ensure that the reader is able to find the theorems he uses, and check the differences with similar results. It is clear that the mathematician needs the references to read the work. Results that appeared 20, 50 or 100 years ago are still valid and useful. This is why journals and their permanent and free access are so essential.
We are sure that Bloom has worked on a copy of Croot’s work. So much so that his copy will be full of comments and alternative suggestions. Croot’s paper was published in 2003, 19 years ago, but for Bloom it was the hottest news when he tried to overcome Croot’s results to get the density theorem. This is a good example of how to work in mathematics. Pólya’s first suggestion: Have you ever seen a similar problem solved before? Can you use that method?
To this end, it is essential that mathematical publications be permanent and freely accessible.
To learn more
Erdös’ second conjecture is taken from a paper that was published in the proceedings of a conference at the Mathematics Institute of the University of Sao Paulo (Nov. 1994). It can be downloaded from the web page: Papers by Erdös.
Graham and Erdös’ conjectures are contained in their book:
P. Erdös y R. L. Graham, Old and new problems and results in Combinatorial Number Theory, l’Enseignement Mathématique,
Croot’s original paper is readable with some mathematical background: basic Number Theory theorems. Dickman’s result is more complicated, but it is easy to understand and is clearly stated.
Ernest S. Croot III, On a coloring conjecture about unit fractions, Ann. Math. 157 (2003) 545-556.
Thomas F. Bloom’s work is a bit more difficult to understand, not because he uses complicated mathematics; simply because it requires prolonged attention.
Thomas F. Bloom. On a Density Conjecture about Unit Fractions, arXiv:2112.03726. Dic. 2021.
The websites of Croot and Bloom are worth visiting, we can find their work and presentations of topics of their interest.
Ramsey is an interesting character. Despite his untimely death he was able to change the views of two important people: John Maynard Keynes on probability, and to Ludwig Wittgensteint about his retirement from philosophy. Notes on his biography on the Internet can be read at (Biography1,Biography2). Apart from this there are two books dedicated to his life and works:
Karl Sabbagh, Shooting star: The brief and brilliant life of Frank Ramsey, Kindle, 2013.
Cheryl Misak, Frank Ramsey: A sheer excess of powers, Oxford University Press, United Kingdom 2020.
Groot’s photo is due to George Bergman, GFDL 1.2 licencia, via Wikimedia Commons. The featured image is the work of Xavier Blanquer (Jeanloui) I found it on the website fractal brocoli o Romanesco.
Leave a Reply