In this entry we will see a young mathematician rejecting his old professor’s advice: stop thinking about this impossible problem, leaving a little aside the problem that his thesis director assigned him, and getting away with it all the same.
We will see the solution of a problem of Erdös that everyone considered difficult, but with an elementary though ingenious solution.
Erdös primitive set conjecture
A set of natural numbers \(A\) is said to be primitive if no number in \(A\) divides another. In 1935 Erdös proved that $$\sup_{A,\text{ primitive}}\quad\sum_{n\in A}\frac{1}{n\log n}=C<+\infty.$$ The concept of primitive set was introduced by Erdös to prove in an elementary way a theorem of Davenport that states that the upper asymptotic density of the set of abundant numbers is positive $$\limsup_{x\to+\infty}\frac{\text{card}\{n\le x\colon n \text{ abundant}\}}{x}>0.$$ (Recall that a number \(n\) is abundant if the sum of its divisors is \(>2n\)).
An obvious primitive set is the set \(\mathcal P\) of prime numbers. In 1988 Erdös conjectured that the supremum \(C\) is attained for the primitive set \(\mathcal P\) of primes. That is, for any primitive set \(A\) it is satisfied $$f(A):=\sum_{a\in A}\frac{1}{a\log a}\le \sum_{p\in \mathcal P}\frac{1}{p\log p}.$$ In February 2022 Jared Duker Lichtman has uploaded to arXiv his proof of this conjecture.
This conjecture gives a defining property of the set of primes. A global definition. Distinguishing the primes from any other primitive sets, because the sum for any other primitive set is strictly less than the sum for the primes.
Erdös theorem
We will start by explaining Erdös result on the finiteness of the supremum of $$f(A):=\sum_{a\in A}\frac{1}{a\log a}$$ for primitive \(A\). The first idea is to replace \(\log a\) by \(\log P(a)\) where \(P(a)\) is the largest prime number that divides \(a\). Since \(a\ge P(a)\) we will have $$f(A)=\sum_{a\in A}\frac{1}{a\log a}\le \sum_{n\in A}\frac{1}{a\log P(a)}.$$Now let us recall Mertens theorem $$\lim_{x\to+\infty}(\log x)\prod_{p\le x}\Bigl(1-\frac{1}{p}\Bigr)=e^{-\gamma},$$ where \(p\) runs only through prime numbers and \(\gamma\) is the Euler constant. In particular, there exists a constant \(c\) such that for every number \(x\ge 2\)$$c \prod_{p\le x}\Bigl(1-\frac{1}{p}\Bigr)\ge \frac{1}{\log x}.$$Consequently $$f(A)\le c\sum_{a\in A}\frac{1}{a}\prod_{p< P(a)}\Bigl(1-\frac{1}{p}\Bigr).$$
In Eratosthenes’ sieve when we cross out the multiples of 2, the odd numbers are left which is a set of density \(1-\frac12\), when we cross out the multiples of \(3\) we are left with a set of numbers of density \((1-\frac12)(1-\frac13)\). Likewise \(\prod_{p< P(a)}(1-\frac{1}{p})\) represents the density of the numbers not divisible by any prime less than \(P(a)\) and \(\frac1a\prod_{p< P(a)}(1-\frac{1}{p})\) the density of the set $$L_a=\{ma\in\mathbf N\colon p\mid m\Longrightarrow p\ge P(a)\}.$$ When \(a\ne b\) are elements of \(A\), since \(A\) is primitive it follows that \(L_a\cap L_b=\emptyset\). Which implies that the sum of their densities is \(\le 1\), that is,$$f(A)\le c\sum_{a\in A}\frac{1}{a}\prod_{p< P(a)}\Bigl(1-\frac{1}{p}\Bigr)\le c.$$
Jared Duker Lichtman
In his first year at Dartmouth College he met Carl Pomerance. The last course Carl taught before he retired. It was Jared who asked Carl to direct a research project for him.Carl directed his bachelor’s thesis on primitive nondeficient numbers. It was just at this time (2018 when Jared was 22 years old) that he became aware of Erdös’s conjecture on primitive sets. “I immediately thought it was an absolutely beautiful problem and started thinking about it ever since.”
In 2018 he was also appointed Churchill scholar to do a Master at Cambridge, which later brought him to Oxford to pursue his career and work for his Ph.D. under the supervision of James Maynard (Field medal in 2022). Ph.D. supervision is something serious. The director sets a problem that has to be carefully chosen. Not simple but not out of reach either, in a subject with potential. It will usually keep the student busy for two to four years.But Jared already had a problem in mind and it wasn’t easy for him to give it up. He didn’t inform Maynard about it until he had the solution. Jared himself recounts the moment in a Numberphile youtube video
What did your advisor say when you sent it through?
So, uh, he actually didn’t know I was working on this problem.I kind of half was thinking that he’d be angry at me for not working on the problem that he’d set for me, and this was like something I’d been doing by candlelight at night surreptitiously. But so I’d let him know back in this winter that I’d solved… or I’d come up with this proof and he, uh, he took time over several months to look at it and kind of set all the steps there, you know, dot all the i’s and, cross all the t’s, but he, he was, uh, also veryhappy for me and I was…,it was…, it was just a very nice moment.
(Numberphile youtube video13:34–14:19)
Everyone thinks that \(P\ne NP\), they fail to recognize the overwhelming number of experimental facts that corroborate the efficacy of the algorithm I presented in Artistic creation and mathematical creation, Sección The algorithm nobody wants to see.
A good implementation of my algorithm for P=NP
So the algorithm is: take young people who are motivated by mathematics, show them the conjectures, propose related problems that are within their reach. Suggest that they study the related works and related tools. Let them dream and in a few years they will have found the proofs or built tools with which the next generation will be better equipped.
Starting and notations
For any natural number \(n>1\), we denote by \(P(n)\) the largest prime factor of \(n\) and by \(p(n)\) the least one.
We put \(f(A):=\sum_{a\in A}\frac{1}{a\log a}\), \(f(p)=f(\{p\})=\frac{1}{p\log p}\), $$L_a=\{an\colon p\mid n\Longrightarrow p\ge P(a)\},\quad a\in \mathbf N.$$ Then for any \(A\subset \mathbf N\), and \(n\in \mathbf N\) we put \(A_n=A\cap L_n\). For any \(A\subset \mathbf N\), the number \(d(A):=\lim_{x\to\infty}|A\cap[1,x]|/x\) when the limit exists.
In summary Erdös proof have three steps:\begin{align*} \sum_{a\in A}\frac{1}{a\log a}&\le \sum_{a\in A}\frac{1}{a\log P(a)}&&\text{subst. $a\to P(a)$}\\&\le c\sum_{a\in A}\frac{1}{a}\prod_{p<P(a)}\Bigl(1-\frac{1}{p}\Bigr) &&\text{Mertens thm.}\\&=c\sum_{a\in A}d(L_a)= c\; d\Bigl(\bigcup_{a\in A} L_a\Bigr)\le c &&\text{disjoint $L_a$} \end{align*}
General strategy and strong Erdös primes
If \(A\) is a primitive we want to prove that $$\sum_{a\in A}\frac{1}{a\log a}\le \sum_p\frac{1}{p\log p}.$$ If some prime \(q\in A\), then one summand on the left is equal to one of the summands on the right. Also any other member of \(A\) is not a multiple of \(q\). So we only have to show that $$\sum_{a\in A\smallsetminus\{q\}}\frac{1}{a\log a}\le \sum_{p\ne q}\frac{1}{p\log p}$$ and we may proceed as if the prime \(q\) doesn’t exists.
A strategy to prove the conjecture will be to separate \(A=\bigcup_p A_p\) into disjoints sets one for each prime \(p\) and then prove that \(f(A_p)\le f(p)\). Good candidates for \(A_p\) will be the sets$$A_p=\{a\in A\colon p \text{ is the least prime dividing } a\}.$$ We will say that a prime \(p\) is Erdös strong if $$\sup_{A\text{ primitive}} \Bigl(\sum_{a\in A_p}\frac{1}{a\log a}\Bigr)\le \frac{1}{p\log p}.$$ Jared prove in this paper that any odd prime is Erdös strong and conjecture that \(p=2\) is also Erdös strong. The proof of the conjecture consists in showing that any odd prime is Erdös strong, and then a special treatment of the case of \(p=2\).
If \(p\in A\), then \(A_p=\{p\}\) and the inequality\(f(A_p)\le f(p)\) is trivial, being an equality. In other case when \(p\not\in A\), we have to show that \(f(A_p)< f(p)\) with strict inequality, so the proof consists into getting a sufficiently good upper bound of \(f(A_p)\).
Since \(f(A)=\lim_{x\to\infty} f(A\cap[1,x])\) we may usually assume from here on, without loss of generality, that \(A\) is finite. We do not repeat this anymore.
Improving Erdös’ three steps
In the intermediate step, that of Mertens, the most we can aim for is to lower the constant to \(e^\gamma\) and this was achieved in a paper published in 2018 by Jared and Pomerance. The two most difficult steps to improve were the first and last one.
In the first step we see clearly the difference between \(a\) and \(P(a)\). There is an exponent \(\kappa\) such that \(a=P(a)^\kappa\). Therefore \(\log a=\kappa \log P(a)\). But \(\kappa\) can vary greatly depending on the value of \(a\). “I worked on several approaches to this problem over multiple years.”
It is very interesting how Jared’s proof has evolved. I asked Jared about it (When you solved the conjecture, was there a moment of enlightenment? Can you give any details?)and in his answer he has explained his mental process to arrive at the solution. I think his answer is very instructive.
In the proof of Erdös the sets \(L_a\) are disjoint because \(A\) is a primitive set. But Jared notes that we may extend the concept of primitive set to that of \(L\)-primitive sets, as those sets \(A\) such that the sets \(L_a\) with \(a\in A\) are disjoint. And this leads to the concept of \(L\)-multiples: \(b\) is an \(L\)-multiple of \(a\) if \(b\in L_a\). These concepts are the key to the improvement of steps 1 and 3 in Erdös proof [Lemma 3.1 and the sets \(C_a^v\) of which he speaks here will be explained later after the section “To know more”].
I worked on several approaches to this problem over multiple years. Gradually I realized there should be an explicit definition of sets of \(L\)-multiples and (most importantly) \(L\)-primitive sets. Once I had these definitions, then it became natural to seek a result like Lemma 3.1, during the proof of which the exact definition of \(C_a^v\) becomes essentially forced upon you. After Lemma 3.1 is obtained, the rest of the proof flows quickly, and it is quite a simple matter to deduce the final result (with a bit of extra casework for \(p=2\)). As such, I would emphasize that the key difficulty for me was to develop the right framework and definitions that would make Lemma 3.1 appear natural (Indeed, imagine the statement of Lemma 3.1 without mentioning sets of \(L\)-multiples, or \(L\)-primitive sets!)
(Jared, personal communication January 21, 2023)
In his write-up to me Jared ends giving some explanations of the proof and the reasons why the set of primes is the best primitive set:
there are 2 steps that are potentially inefficient, (1) the substitution “\(a \to P(a)\)” and (2) the “disjointness of \(L_a\)”. In my proof, a primitive set of composite numberscan either improve step (1) easily (if say \(a > P(a)^2\) for all \(a \in A\)), or else can improve step (2) by Lemma 3.1 and its consequences. The final integral (\(= \pi/4\)) represents the worst-case savings from combining these steps. Moreover, in the case of the primes themselves, steps (1) and (2) are actually perfectly efficient in Erdös’ argument (indeed for (1) \(p=P(p)\), and for (2) the collection \(\{L_p\}\) cannot be enlarged while remaining pairwise disjoint).
Hence this gives a conceptual explanation for why the primes are maximal among all primitive sets in Erdos’ conjecture: namely, composites enjoy savings from either step (1) or (2), but primes have no such savings.
(Jared, personal communication January 21, 2023)
Jared’s proof does not use complicated mathematical concepts. It therefore allows a more detailed exposition. But this entry is already long, so after the usual “To know more” section we will include a more detailed analysis of the proof.
To know more
We can see Jared Duker Lichtman in two youtube videos:Exposing his thesis in 3 minutes, and a highly recommended interview in Numberphile. Also it is very nice the entry in Quanta magazine on the solution of Erdös’ conjecture.
Facts about his student life can be seen in the web page Jared named Churchill scholar.
The paper is very readable, since it uses no complicated mathematical concepts, only Riemann sums, elementary divisibility. It can be found in arXiv:
Jared Duker Lichtman, A proof of the Erdös primitive set conjecture, february 2022 arXiv:2202.02384v1.
It is also a good reading the paper of Erdös, that can be seen as a streamlined/rough version of the paper by Jared:
P. Erdös, Note on Sequences of integers no one of which is divisible by any other, J. London Math. Soc. 10 (1935) 126-128. (pdf of this paper).
The paper of Rosser and Schoenfeld which is used by Jared, maybe one of the most cited papers in Number Theory is also open in the web now:
There is a previous paper with Carl Pomerance where they improve on the constant \(C\) substituting it by \(e^\gamma\).
The featured image of today is inspired in a quotation of Carleson: If you want to solve problems, as in my case, the most important property is to be very very stubborn. If not those of Pomerance and Maynard, this advice, at least, has been followed by Jared. Four years after an almost impossible proof. Carleson’s phrase brings to mind these weeds that grow on the pavement in spite of all the inconveniences.
Changing the constant \(C\) into \(e^\gamma\)
Being \(A\) primitive implies that \(L_a\) are disjoint two by two for \(a\in A\). But in general, it is very easy to prove for \(a\ne b\) there are only three possibilities, either \(L_a\) and \(L_b\)are disjoint or \(L_a\subset L_b\) or \(L_b\subset L_a\). So if we call a set \(A\) \(L\)-primitive when \(L_a\) with \(a\in A\) are disjoint, then the last step in Erdös proof holds for \(A\) \(L\)-primitive.
We will need a variant of Mertens theorem due to Rosser and Schoenfeld $$\prod_{p<x}\Bigl(1-\frac{1}{p}\Bigr)\ge \frac{e^{-\gamma}}{\log 2x}.$$ Then we may prove
Lemma 1. Let \(A\) be an \(L\)-primitive set and \(n\) an integer \(>1\) with \(n\notin A\), then \(f(A_n):=f(A\cap L_n)<e^\gamma d(L_n)\).
(Recall that we need to prove \(f(A_q)< f(q)\) when \(q\) is a prime not in \(A\). This is a step in the wright direction but still \(e^\gamma\) is too large for us).
Proof. Any \(a\in A\cap L_n\) is a multiple of \(n\), and since \(n\notin A\), \(a\) is composite, in particular \(a\ge 2P(a)\). Hence by Mertens’ variant \begin{align*}\frac{1}{a\log a}&\le \frac{1}{a\log(2P(a))}\\ &\le \frac{e^\gamma}{a}\prod_{p<P(a)}\Bigl(1-\frac{1}{\log p}\Bigr)\le e^{\gamma}d(L_a).\end{align*} Then $$f(A\cap L_n)\le \sum_{a\in A\cap A_n}\frac{1}{a\log a}\le e^\gamma\sum_{a\in A\cap L_n} d(L_a).$$ The \(L_a\) are disjoint so that this is $$=e^\gamma d\Bigl(\bigcup_ {a\in A\cap L_n}L_a\Bigr)\le e^\gamma d(L_n).\quad \square$$
Given a primitive set\(A\) and \(q\notin A\) we want to prove the inequality \(f(A_q)\le f(q)\). By Lemma 1 we have $$f(A_q)\le e^\gamma d(L_q)= \frac{e^\gamma }{q}\prod_{p<q}\Bigl(1-\frac{1}{p}\Bigr).$$ Rosser and Schoenfeld results from 1962 allow one to get bounds for \(m_q\) and \(M_q\) where \begin{align*}\mu_x:=e^\gamma \log x&\prod_{p<x}\Bigl(1-\frac{1}{p}\Bigr),\\ m_q=\inf_{p\ge q}\mu_p,\quad &M_x=\max_{p\ge x}\mu_p.\end{align*} In fact \begin{align*}m_q &\ge \begin{cases}\mu_7 = 0.9242\cdots & q \le 7\\\mu_{19} = 0.9467\cdots & 7< q \le 300\\1- \frac{1}{2(\log q)^2} & q> 300.
\end{cases}\\
M_x &\le \begin{cases}\mu_2 = 1.235\cdots & x \le 2\\1 + \frac{1}{2\log(2\cdot10^9)^2} & 2< x \le 2\cdot10^9\\1 + \frac{1}{2(\log x)^2} & x> 2\cdot10^9.\end{cases}\end{align*} So that $$f(A_q)\le \frac{e^\gamma }{q}\prod_{p<q}\Bigl(1-\frac{1}{p}\Bigr)=\frac{\mu_q}{q\log q}.$$ Since \(M_q\) is only slightly greater than \(1\), we need to improve a little this bound to get that \(q\) is Erdös strong. This is achieved in two steps.
First step: Improving the substitution \(a\to P(a)\) in Erdös proof
Looking at the first line of Erdös reasoning we see a point where the inequality can be improved is when we substitute \(\log a\) by \(\log P(a)\). There is an exponent \(\kappa\ge 1\) such that \(P(a)^\kappa =a\). Putting \(\kappa=1+v\) we get the following improvement
Lemma [Lemma 2.5 in the paper]. Let \(A\) be an \(L\)-primitive set. Let \(v\ge0\) and \(n\) be an integer \(n\notin A\), and denote by \(q=P(n)\). If \(P(a)^{1+v}\le a\) for all \(a\in A_n\), then $$f(A_n)=\sum_{a\in A_n}\frac{1}{a\log a}\le \frac{e^\gamma}{m_q}\frac{d(L_{A_n})}{1+v}.$$
Proof. Since \(n\notin A\) all elements of \(A_n\) are composite. We have \begin{align*}\frac{1}{a\log a}&\le \frac{1}{1+v}\frac{1}{a\log P(a)}\\ &=\frac{e^\gamma}{\mu_{P(a)}}\frac{1}{1+v}\frac{1}{a}\prod_{p<P(a)}\Bigl(1-\frac{1}{P(a)}\Bigr)\\&=\frac{e^\gamma}{\mu_{P(a)}}\frac{d(L_a)}{1+v}\end{align*} Now by definition of the \(m_q\) we have \(\mu_{P(a)}\ge m_{P(a)}\ge m_q\) for \(a\in A\subset L_n\). Hence we conclude $$f(A)=\sum_{a\in A}\frac{1}{a\log a}\le \frac{e^{\gamma}}{m_q}\frac{1}{1+v}\sum_{a\in A} d(L_a)= \frac{e^{\gamma}}{m_q}\frac{d(L_A)}{1+v}.\quad \square$$
This inequality is sufficient for our purposes (to prove that the odd primes are strong Erdös primes) when \(v\ge 1\), but for not for \(v\) near \(0\), so that we still require another idea. We concentrate on the case \(0<v\le 1\).
Second step: Improving the disjoint of \(L_a\) step in Erdös proof
Here is the key point of the proof. When \(A\subset L_n\) and \(A\) is primitive we get disjoint sets \(L_a\) all of them in \(L_n\). But assuming that \(P(a)^{1+v}\ge a\) for all elements in \(A\), we may get an \(L\)-primitive set larger than \(A\) and still contained in \(L_n\). Hence we look
for a Lemma as
Lemma [Lemma 3.1 in the paper]. Let \(A\) be a primitive set of composite numbers, and take \(v\in(0,1)\). If \(P(a)^{1+v}\ge a\) for all \(a\in A\), then the collection of sets \(L_{ac}\), ranging over \(a\in A\), \(c\in C_{av}\), are pairwise disjoint.
Here $$C_{a,v}:=\{c\in \mathbf N\colon p\mid c\Longrightarrow p\in [P(a^*),P(a^*)^{1/\sqrt{v}})\}$$ where \(a^*=a/P(a)\). Also\(p(ac)=p(a)\) and \(P(a)>P(c)\).We start without a good definition of the \(C_{a,v}\), but the proof imposes the election, and then the proof is relatively easy.
Proposition 1. Let \(A\) be a finite primitive set. Take \(v\in(0,1)\), and integer \(n>1\) with \(n\notin A\), and denote \(q=P(n)\ge 3\). If \(P(a)^{1+v}>a\) for all \(a\in A\cap L_n\) then $$d\Bigl(\bigcup_{a\in A\cap L_n} L_a\Bigr)\le \sqrt{v}\frac{M_q}{m_q}d(L_n).$$ (For \(q=2\), the same is true but replacing \(M_2/m_2\) by \(M_3/m_3\)).
Proof[Idea of proof]. As before we may assume \(A=A\cap L_n\), by the previous observation we have $$L_n\supset\bigcup_{a\in A}\bigcup_{c\in C_{a,v}}L_{ac},$$ with disjoint union.
Then\begin{align*}{\rm d}({\rm L}_n) & \ge\sum_{a\in A}\sum_{c\in C_{a,v}}{\rm d}({\rm L}_{ac}) = \sum_{a\in A}{\rm d}({\rm L}_a)\,\sum_{c\in C_{a,v}}\frac{1}{c},\end{align*} And we compute\begin{align*} \sum_{c\in C_a^v}\frac{1}{c}& = \prod_{p\in [P(a^*), P(a^*)^{1/\sqrt{v}})}\Big(1-\frac{1}{p}\Big)^{-1}\\ & = \prod_{p<P(a^*)^{1/\sqrt{v}}}\Big(1-\frac{1}{p}\Big)^{-1}\prod_{p<P(a^*)}\Big(1-\frac{1}{p}\Big) \nonumber\\
&= \frac{\log P(a^*)^{1/\sqrt{v}}}{\mu_{P(a^*)^{1/\sqrt{v}}}} \frac{\mu_{P(a^*)}}{\log P(a^*)}\\ & = \frac{\mu_{P(a^*)}}{\mu_{P(a^*)^{1/\sqrt{v}}}}\frac{1}{\sqrt{v}}
\ge \frac{m_q}{M_q}\frac{1}{\sqrt{v}}.\quad \square\end{align*}
With this we may get a factor \(\frac{\pi}{4}\) that is sufficient to prove that any odd prime is Erdös strong. The factor \(\frac{\pi}{4}\) appears nicely as a limit of a Riemann sums.
Proposition. For any primitive set \(A\), and any integer \(n\notin A\) with \(q=P(n)\ge3\), \begin{align*} f(A_n) \ \le \ \frac{\pi}{4}\frac{M_q}{m_q^2}\;e^\gamma {\rm d}({\rm L}_n).\end{align*}
Proof [Sketch of proof]. Consider a partition of the interval \([0,1]\), \(0=v_0<v_1<\cdots<v_k=1\) and separate accordingly the set \(A=\bigcup_{0\le i\le k} A_{(i)}\), where $$A_{(i)} = \{a\in A :P(a)^{1+v_{i}} \le a < P(a)^{1+v_{i+1}}\},\quad 0\le i\le k-1,$$ and \(A_{(k)}=\{a\in A\colon P(a)^2\le a\}\).By the above results we get\begin{align*} f(A) & = \sum_{0\le i\le k} f(A_{(i)}) \ \le \ \frac{e^\gamma}{m_q} \sum_{0\le i\le k} \frac{{\rm d}({\rm L}_{A_{(i)}})}{1+v_i}\\ \end{align*} By means of a trick of partial summation and using Proposition 1 we may get that $$\sum_{0\le i\le k} \frac{{\rm d}({\rm L}_{A_{(i)}})}{1+v_i}\le \sum_{0\le i\le k}\frac{\sqrt{v_{i+1}}-\sqrt{v_i}}{1+v_i}.$$ This is a Riemann’s sum for the integral $$\int_0^1\frac{dv}{2\sqrt{v}(1+v)}=\frac{\pi}{4}.$$ Hence taking limits when the width of the partition tends to \(0\) we get the result. \(\square\)
The prime \(2\) needs a special treatment, but there is no main important idea in it.
Leave a Reply