11 Tertiary explicit estimates
11.1 The least common multiple sequence is not highly abundant for large \(n\)
11.1.1 Problem statement and notation
\(\sigma (n)\) is the sum of the divisors of \(n\).
A positive integer \(N\) is called highly abundant (HA) if
for all positive integers \(m {\lt} N\), where \(\sigma (n)\) denotes the sum of the positive divisors of \(n\).
Informally, a highly abundant number has an unusually large sum of divisors.
For each integer \(n \ge 1\), define
We call \((L_n)_{n \ge 1}\) the least common multiple sequence.
Clearly \(L_n\) has a lot of divisors, and numerical experiments for small \(n\) suggests that \(L_n\) is often highly abundant. This leads to the following question:
Original MathOverflow question. Is it true that every value in the sequence \(L_n = \mathrm{lcm}(1,2,\dots ,n)\) is highly abundant? Equivalently,\[ \{ L_n : n \ge 1\} \subseteq HA? \]
Somewhat surprisingly, the answer is no: not every \(L_n\) is highly abundant.
It has previously been verified in Lean that \(L_n\) is highly aboundant for \(n \leq 70\), \(81 \leq n \leq 96\), \(125 \leq n \leq 148\), \(169 \leq n \leq 172\), and not highly abondant for all other \(n ≤ 10^{10}\). The arguments here establish the non-highly-abundance of \(L_n\) for all \(n \geq 89683^2\) sufficiently large \(n\), thus completing the determination in Lean of all \(n\) for which \(L_n\) is highly abundant. This argument was taken from this MathOverflow answer.
11.1.2 A general criterion using three medium primes and three large primes
The key step in the proof is to show that, if one can find six primes \(p_1,p_2,p_3,q_1,q_2,q_3\) obeying a certain inequality, then one can find a competitor \(M {\lt} L_n\) to \(L_n\) with \(\sigma (M) {\gt} \sigma (L_n)\), which will demonstrate that \(L_n\) is not highly abundant. More precisely:
In the next few subsections we assume that \(n \geq 1\) and that \(p_1,p_2,p_3,q_1,q_2,q_3\) are primes satisfiying
and the key criterion
NOTE: In the Lean formalization of this argument, we index the primes from 0 to 2 rather than from 1 to 3.
We have \(4 p_1 p_2 p_3 {\lt} q_1 q_2 q_3\).
Obvious from the non-negativity of the left-hand side of 1.
11.1.3 Factorisation of \(L_n\) and construction of a competitor
There exists a positive integer \(L'\) such that
and each prime \(q_i\) divides \(L_n\) exactly once and does not divide \(L'\).
Since \(q_i {\lt} n\), the prime \(q_i\) divides \(L_n\) exactly once (as \(q_i^2 {\gt} n\)). Hence we may write \(L_n = q_1 q_2 q_3 L'\) where \(L'\) is the quotient obtained by removing these prime factors. By construction, \(q_i \nmid L'\) for each \(i\).
Let \(L'\) be as in Lemma 11.1.2. Then
Use the multiplicativity of \(\sigma (\cdot )\) and the fact that each \(q_i\) occurs to the first power in \(L_n\). Then
Dividing by \(L_n = L' \prod _{i=1}^3 q_i\) gives
There exist integers \(m \ge 0\) and \(r\) satisfying \(0 {\lt} r {\lt} 4 p_1 p_2 p_3\) and
This is division with remainder.
With \(m,r\) as above, define the competitor
With notation as above, we have:
\(M {\lt} L_n\).
- \[ 1 {\lt} \frac{L_n}{M} = \Bigl(1 - \frac{r}{q_1 q_2 q_3}\Bigr)^{-1} {\lt} \Bigl(1 - \frac{4 p_1 p_2 p_3}{q_1 q_2 q_3}\Bigr)^{-1}. \]
The first item is by construction of the division algorithm. For the second, note that
since \(r{\gt}0\). For the third,
Since \(0 {\lt} r {\lt} 4p_1p_2p_3\) and \(4p_1p_2p_3 {\lt} q_1q_2q_3\), we have
so
11.1.4 A sufficient condition
We give a sufficient condition for \(\sigma (M) \geq \sigma (L_n)\).
Suppose
Then \(\sigma (M) \ge \sigma (L_n)\), and so \(L_n\) is not highly abundant.
By Lemma 11.1.5,
Hence
Multiplying both sides by \(M\) gives
and hence
since \(M/L_n{\lt}1\) and both sides are integers.
Combining Lemma 11.1.6 with Lemma 11.1.3, we see that it suffices to bound \(\sigma (M)/M\) from below in terms of \(\sigma (L')/L'\):
If
then \(L_n\) is not highly abundant.
11.1.5 Conclusion of the criterion
With notation as above,
By multiplicativity, we have
The contribution of \(p=p_i\) is
The contribution of \(p=2\) is
where \(k\) is the largest integer such that \(2^k \le n\). A direct calculation yields
Finally, since \(2^k \le n {\lt} 2^{k+1}\), we have \(2^{k+3} {\lt} 8n\), so
So the contribution from the prime \(2\) is at least \(1 + 3/(8n)\).
Finally, the contribution of all other primes is at least \(1\).
We have thus completed the key step of demonstrating a sufficient criterion to establish that \(L_n\) is not highly abundant:
Let \(n \geq 1\). Suppose that primes \(p_1,p_2,p_3,q_1,q_2,q_3\) satisfy
and the key criterion 1. Then \(L_n\) is not highly abundant.
By Lemma 11.1.8, the condition 3 holds. By Lemma 11.1.7 this implies
Applying Lemma 11.1.6, we obtain \(\sigma (M) \ge \sigma (L_n)\) with \(M {\lt} L_n\), so \(L_n\) cannot be highly abundant.
Analogous arguments allow other pairs \((c,\alpha )\) in place of \((4,3/8)\), such as \((2,1/4)\), \((6,17/36)\), \((30,0.632\dots )\); or even \((1,0)\) provided more primes are used on the \(p\)-side than the \(q\)-side to restore an asymptotic advantage.
11.1.6 Choice of six primes \(p_i,q_i\) for large \(n\)
To finish the proof we need to locate six primes \(p_1,p_2,p_3,q_1,q_2,q_3\) obeying the required inequality. Here we will rely on the prime number theorem of Dusart [ 13 ] .
Let \(n \ge X_0^2\). Set \(x := \sqrt{n}\). Then there exist primes \(p_1,p_2,p_3\) with
and \(p_1 {\lt} p_2 {\lt} p_3\). Moreover, \(\sqrt{n} {\lt} p_1\)
Apply Proposition 10.12.4 successively with \(x, x(1+1/\log ^3 x), x(1+1/\log ^3 x)^2\), keeping track of the resulting primes and bounds. For \(n\) large and \(x = \sqrt{n}\), we have \(\sqrt{n} {\lt} p_1\) as soon as the first interval lies strictly above \(\sqrt{n}\); this can be enforced by taking \(n\) large enough.
Let \(n \ge X_0^2\). Then there exist primes \(q_1 {\lt} q_2 {\lt} q_3\) with
for \(i = 1,2,3\), and \(q_1 {\lt} q_2 {\lt} q_3 {\lt} n\).
Apply Theorem 10.12.4 with suitable values of \(x\) slightly below \(n\), e.g. \(x = n(1+1/\log ^3\sqrt{n})^{-i}\), again keeping track of the intervals. For \(n\) large enough, these intervals lie in \((\sqrt{n},n)\) and contain primes \(q_i\) with the desired ordering.
11.1.7 Bounding the factors in 1
With \(p_i\) as in Lemma 11.1.9, we have for large \(n\)
By Lemma 11.1.9, \(p_i \le \sqrt{n} (1+1/\log ^3\sqrt{n})^i\). Hence
From these one gets
and hence
Taking \(1+\cdot \) and multiplying over \(i=1,2,3\) gives 5.
We have \(p_i \le \sqrt{n} (1+1/\log ^3 \sqrt{n})^i\), so
Similarly, \(q_i \ge n(1+1/\log ^3 \sqrt{n})^{-i}\), so
Combining,
This implies 6.
11.1.8 Reduction to a small epsilon-inequality
For all \(n \ge X_0^2 = 89693^2\) we have
and
This is a straightforward calculus and monotonicity check: the left-hand sides are decreasing in \(n\) for \(n \ge X_0^2\), and equality (or the claimed upper bound) holds at \(n=X_0^2\). One can verify numerically or symbolically.
For \(0 \le \varepsilon \le 1/89693^2\), we have
and
Expand each finite product as a polynomial in \(\varepsilon \), estimate the coefficients using the bounds in Lemma 11.1.14, and bound the tails by simple inequalities such as
for small \(\varepsilon \). All coefficients can be bounded numerically in a rigorous way; this step is a finite computation that can be checked mechanically.
For \(0 \le \varepsilon \le 1/89693^2\), we have
This is equivalent to
or
Factor out \(\varepsilon \) and use that \(0{\lt}\varepsilon \le 1/89693^2\) to check that the resulting quadratic in \(\varepsilon \) is nonnegative on this interval. Again, this is a finite computation that can be verified mechanically.
11.1.9 Conclusion for large \(n\)
For every integer \(n \ge 89693^2\), the integer \(L_n\) is not highly abundant.
11.1.10 Bonus material
The following result is not needed for this application, but is worth recording nevertheless.
For every \(n\), \(\log L_n = \sum _{p \leq n} \lfloor \log n / \log p \rfloor \log p\).
Compute the number of times \(p\) divides \(L_n\) and use the fundamental theorem of arithmetic.
For every \(n\), \(\psi (n) = \sum _{p \leq n} \lfloor \log n / \log p \rfloor \log p\), where \(\psi \) is the Chebyshev psi function.
Compute the number of times \(p\) divides \(L_n\) and use the fundamental theorem of arithmetic.
For every \(n\), \(\log L_n = \psi (n)\), where \(\psi \) is the Chebyshev psi function.
Combine the previous results.
11.2 Erdos problem 392
The proof here is adapted from https://www.erdosproblems.com/forum/thread/392#post-2696 which in turn is inspired by the arguments in https://arxiv.org/abs/2503.20170.
We work with (approximate) factorizations \(a_1 \dots a_t\) of a factorial \(n!\).
The waste of a factorizations \(a_1 \dots a_t\) is defined as \(\sum _i \log (n / a_i)\).
The balance of a factorization \(a_1 \dots a_t\) at a prime \(p\) is defined as the number of times \(p\) divides \(a_1 \dots a_t\), minus the number of times \(p\) divides \(n!\).
If a factorization has zero total imbalance, then it exactly factors \(n!\).
The waste of a factorization is equal to \(t \log n - \log n!\), where \(t\) is the number of elements.
The score of a factorization (relative to a cutoff parameter \(L\)) is equal to its waste, plus \(\log p\) for every surplus prime \(p\), \(\log (n/p)\) for every deficit prime above \(L\), \(\log L\) for every deficit prime below \(L\) and an additional \(\log n\) if one is not in total balance.
If one is in total balance, then the score is equal to the waste.
If there is a prime \(p\) in surplus, one can remove it without increasing the score.
Locate a factor \(a_i\) that contains the surplus prime \(p\), then replace \(a_i\) with \(a_i/p\).
If there is a prime \(p\) in deficit larger than \(L\), one can remove it without increasing the score.
Add an additional factor of \(p\) to the factorization.
If there is a prime \(p\) in deficit less than \(L\), one can remove it without increasing the score.
Without loss of generality we may assume that one is not in the previous two situations, i.e., wlog there are no surplus primes and all primes in deficit are at most \(L\). If all deficit primes multiply to \(n\) or less, add that product to the factorization (this increases the waste by at most \(\log n\), but we save a \(\log n\) from now being in balance). Otherwise, greedily multiply all primes together while staying below \(n\) until one cannot do so any further; add this product to the factorization, increasing the waste by at most \(\log L\).
One can bring any factorization into balance without increasing the score.
Apply strong induction on the total imbalance of the factorization and use the previous three sublemmas.
Starting from any factorization \(f\), one can find a factorization \(f'\) in balance whose cardinality is at most \(\log n!\) plus the score of \(f\), divided by \(\log n\).
Now let \(M,L\) be additional parameters with \(n {\gt} L^2\); we also need the minor variant \(\lfloor n/L \rfloor {\gt} \sqrt{n}\).
We perform an initial factorization by taking the natural numbers between \(n-n/M\) (inclusive) and \(n\) (exclusive) repeated \(M\) times, deleting those elements that are not \(n/L\)-smooth (i.e., have a prime factor greater than or equal to \(n/L\)).
The number of elements in this initial factorization is at most \(n\).
The total waste in this initial factorization is at most \(n \log \frac{1}{1-1/M}\).
A large prime \(p \geq n/L\) cannot be in surplus.
No such prime can be present in the factorization.
A large prime \(p \geq n/L\) can be in deficit by at most \(n/p\).
This is the number of times \(p\) can divide \(n!\).
A medium prime \(\sqrt{n} {\lt} p ≤ n/L\) can be in surplus by at most \(M\).
Routine computation using Legendre’s formula.
A medium prime \(\sqrt{n} {\lt} p ≤ n/L\) can be in deficit by at most \(M\).
The number of times \(p\) divides \(a_1 \dots a_t\) is at least \(M \lfloor n/Mp \rfloor ≥ n/p - M\) (note that the removal of the non-smooth numbers does not remove any multiples of \(p\)). Meanwhile, the number of times \(p\) divides \(n!\) is at most \(n/p\).
A small prime \(p \leq \sqrt{n}\) can be in surplus by at most \(M\log n\).
Routine computation using Legendre’s formula, noting that at most \(\log n / \log 2\) powers of \(p\) divide any given number up to \(n\).
A small prime \(L {\lt} p \leq \sqrt{n}\) can be in deficit by at most \(M\log n\).
Routine computation using Legendre’s formula, noting that at most \(\log n / \log 2\) powers of \(p\) divide any given number up to \(n\).
A tiny prime \(p \leq L\) can be in deficit by at most \(M\log n + ML\pi (n)\).
In addition to the Legendre calculations, one potentially removes factors of the form \(plq\) with \(l \leq L\) and \(q \leq n\) a prime up to \(M\) times each, with at most \(L\) copies of \(p\) removed at each factor.
The initial score is bounded by
If \(M\) is sufficiently large depending on \(\varepsilon \), then \(n \log (1-1/M)^{-1} \leq \varepsilon n\).
Use the fact that \(\log (1-1/M)^{-1}\) goes to zero as \(M \to \infty \).
If \(L\) is sufficiently large depending on \(M, \varepsilon \), and \(n\) sufficiently large depending on \(L\), then \(\sum _{p \leq n/L} M \log n \leq \varepsilon n\).
Use the prime number theorem (or the Chebyshev bound).
If \(n\) sufficiently large depending on \(M, \varepsilon \), then \(\sum _{p \leq \sqrt{n}} M \log ^2 n / \log 2 \leq \varepsilon n\).
Crude estimation.
Given \(\varepsilon {\gt} 0\), choose \(a \neq 0\) with \(\varphi (a)/a {\lt} \varepsilon /2\) (using \(\prod _{p \leq n}(1 - 1/p) \to 0\)). For \(n \geq a + 2\),
Since \(\varphi (a)/a {\lt} \varepsilon /2\), for \(n\) large enough the constant terms are absorbed, giving \(\pi (n) {\lt} \varepsilon n\).
If \(n\) sufficiently large depending on \(L, \varepsilon \), then \(\sum _{n/L {\lt} p \leq n} \frac{n}{p} \log \frac{n}{p} \leq \varepsilon n\).
Bound \(\frac{n}{p}\) by \(L\) and use the prime number theorem (or the Chebyshev bound).
For all \(n \geq 2\), one has
By Chebyshev’s bound, \(\prod _{p \leq n} p \leq 4^n\), so \(\sum _{p \leq n} \log p \leq n \log 4\). The number of primes \(p \leq \sqrt{n}\) is trivially at most \(\sqrt{n}\). For primes \(p {\gt} \sqrt{n}\), we have \(\log p {\gt} \frac{1}{2} \log n\), hence
giving \(\pi (n) - \pi (\sqrt{n}) {\lt} \frac{2n \log 4}{\log n}\). Adding \(\pi (\sqrt{n}) \leq \sqrt{n}\) yields the result.
If \(n\) sufficiently large depending on \(M, L, \varepsilon \), then \(\sum _{p \leq L} (M \log n + M L \pi (n)) \log L \leq \varepsilon n\).
Use the prime number theorem (or the Chebyshev bound).
The score of the initial factorization can be taken to be \(o(n)\).
Pick \(M\) large depending on \(\varepsilon \), then \(L\) sufficiently large depending on \(M, \varepsilon \), then \(n\) sufficiently large depending on \(M,L,\varepsilon \), so that the bounds in Sublemma 11.2.12, Sublemma 11.2.13, Sublemma 11.2.14, Sublemma 11.2.15, and Sublemma 11.2.17 each contribute at most \((\varepsilon /5) n\). Then use Proposition 11.2.2.
One can find a balanced factorization of \(n!\) with cardinality at most \(n - n / \log n + o(n / \log n)\).-
One can factorize \(n!\) into at most \(n/2 - n / 2\log n + o(n / \log n)\) numbers of size at most \(n^2\).-
11.3 Numerical verification of Goldbach
We record here a simple way to convert prime in short interval theorems, together with numerical verification of even Goldbach, to numerical verification of odd Goldbach.
We say that the even Goldbach conjecture is verified up to height \(H\) if every even integer between \(4\) and \(H\) is the sum of two primes.
The even Goldbach conjecture is verified up to height 30.
This is a simple unit test, which can be verified by hand.
We say that the odd Goldbach conjecture is verified up to height \(H\) if every odd integer between \(5\) and \(H\) is the sum of three primes.
If the even Goldbach conjecture is verified up to height \(H\), then the odd Goldbach conjecture is verified up to height \(H+3\).
If \(n\) is an odd integer between \(7\) and \(H+3\), then \(n-3\) is an even integer between \(4\) and \(H\), so we can write \(n-3 = p + q\) for some primes \(p\) and \(q\), and hence \(n = p + q + 3\).
If every interval \((x(1-1/\Delta ), x]\) contains a prime for \(x \geq x_0\), the even Goldbach conjecture is verified up to height \(H\), and the odd Goldbach conjecture is verified up to height \(x_0+4\), then the odd Goldbach conjecture is verified up to height \((H-4)\Delta + 4\).
If \(x \leq x_0+4\) then we are done by hypothesis, so assume \(x_0+4 {\lt} x \leq H\Delta \). By hypothesis, there is a prime \(p\) with \((x-4)(1-1/\Delta ) {\lt} p \leq x-4\). Then \(x-p\) is even, at least \(4\), and at most \((x-4)/\Delta + 4 \leq H\), so is the sum of two primes, giving the claim.
[ 25 ] The even Goldbach conjecture is verified up to \(4 \times 10^{14}\).
Numerical verification.
[ 24 , Corollary 1 ] The odd Goldbach conjecture is verified up to \(1.13256 \times 10^{22}\).
[ 22 ] The even Goldbach conjecture is verified up to \(4 \times 10^{18}\).
Numerical verification.
[ 17 , Appendix C ] The odd Goldbach conjecture is verified up to \(1.1325 \times 10^{26}\).
The arguments in [ 17 , Appendix C ] push the bound further than this, but require unpublished estimates of Ramare. However, similar arguments were established in [ 19 ] , and we present them here.
[ 22 ] The even Goldbach conjecture is verified up to \(4 \times 10^{18} + 4\).
If \(N = 4 \times 10^{18}\), use the fact that \(211, 313, N-209, N-309\) are all prime.
[ 19 , Corollary 1.2 ] The odd Goldbach conjecture is verified up to \(1966196911 \times 4 \times 10^{18}\).
Combine Proposition 11.3.8, Proposition 11.3.2, and Theorem 10.13.19 with \(x_0 = e^{60}\) and \(\Delta = 1966090061\). (Actually, if one is only allowed to use the previous results listed here, one first needs to use the values \(x_0 = e^{59}\) and \(\Delta = 1946282821\) to cover an intermediate range of values.)
11.4 Ramanujan’s inequality
Use of prime number theorems to establish Ramanujan’s inequality
for sufficiently large \(x\), following [ 12 ] .
Let \(M_a \in \mathbb {R}\) and suppose that for \(x{\gt}x_a\) we have
Then for \(x {\gt} x_a\) we have
where
Direct calculation
Let \(m_a \in \mathbb {R}\) and suppose that for \(x{\gt}x_a\) we have
Then for \(x {\gt} e x_a\) we have
where
We have
Substituting
we obtain the claim.
[ 12 , Lemma 2.1 ] Let \(m_a, M_a \in \mathbb {R}\) and suppose that for \(x{\gt}x_a\) we have
Then Ramanujan’s inequality is true if
where \(x'_a := \exp ( \epsilon _{M_a} (x_{a}) - \epsilon '_{m_a} (x_{a}) )\).
Combine the previous two sublemmas.
If \(x \geq 2\), then
Follows from Sublemma 10.5.6 and the fundamental theorem of calculus.
Suppose that for \(x \geq 2\) we have \(|\theta (x)-x|\log ^{5} x\leq x a(x)\). Then
(cf. [ 23 , § 5 ] )
Follows from Lemma 11.4.1 and the triangle inequality.
Suppose that for \(x \geq 2\) we have \(|\theta (x)-x|\log ^{5} x\leq x a(x)\). Then
(cf. [ 23 , § 5 ] )
Follows from Lemma 11.4.1 and the triangle inequality.
For \(x \geq 2\) we have
Integrate by parts to write the left-hand side as \(\frac{x}{\log ^7 x} - \frac{2}{\log ^7 2} + 7 \int _2^x \frac{t}{\log ^8 t} dt\). Discard the middle term. For the final term, split between \(\int _2^{\sqrt{x}}\) and \(\int _{\sqrt{x}}^x\). For the first, use the bound \(\int _2^{\sqrt{x}} \frac{t}{\log ^8 t} dt {\lt} \int _2^{\sqrt{x}} \frac{t}{\log ^8 2} dt\), and for the second, use the bound \(\int _{\sqrt{x}}^x \frac{t}{\log ^8 t} dt {\lt} \int _{\sqrt{x}}^x \frac{t}{\log ^8 x} dt\).
For \(2 \leq x {\lt} 599\) we have
For \(x \in [2, 3)\) we have \(\theta (x) = \log 2\), so \(E_\theta (x) = 1 - \log 2 / x {\lt} 1 - \log 2 / 3\) since \(x {\lt} 3\). For \(x \in [3, 599)\) we use the LeanCert ChebyshevTheta engine: checkAllThetaRelErrorReal 3 599 (768/1000) 20 via native_decide gives \(|\theta (x) - x| \leq 0.768 x\), hence \(E_\theta (x) \leq 0.768 \leq 1 - \log 2 / 3\).
For \(599 {\lt} x \leq \exp (58)\) we have
This is [ 23 , Lemma 6 ] .
For \(\exp (58) {\lt} x {\lt} \exp (1169)\) we have
This follows from Corollary 10.13.1.
For \(\exp (1169) \leq x {\lt} \exp (2000)\) we have
This follows from Corollary 10.13.1.
For \(\exp (2000) \leq x {\lt} \exp (3000)\) we have
This follows from Corollary 10.13.1.
For \(x \geq 2\) we have
This follows from the previous five sublemmas.
The function \(a(x)\) is nonincreasing for \(x \geq x_a\).
Follows from Lemma 2.0.1.
For \(x \geq x_a\),
.
This follows from the previous lemmas and calculations, including Lemma 11.4.2.
For \(x \geq x_a\),
.
This follows from the previous lemmas and calculations, including Lemma 11.4.2.
We have \(\epsilon _{M_a} - \epsilon '_{m_a} {\lt} 0\).
This is a direct calculation.
For \(x \geq e x_a\) we have \(\pi (x)^2 {\lt} \frac{e x}{\log x} \pi \Big(\frac{x}{e}\Big)\).
[ 23 , Theorem 2 ] This follows from the previous lemmas and calculations, including the criterion for Ramanujan’s inequality.