10 Tertiary explicit estimates
10.1 The least common multiple sequence is not highly abundant for large \(n\)
10.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.
10.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.
10.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 10.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
10.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 10.1.5,
Hence
Multiplying both sides by \(M\) gives
and hence
since \(M/L_n{\lt}1\) and both sides are integers.
Combining Lemma 10.1.6 with Lemma 10.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.
10.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 10.1.8, the condition 3 holds. By Lemma 10.1.7 this implies
Applying Lemma 10.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.
10.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 [ 12 ] .
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 9.9.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 ?? 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.
10.1.7 Bounding the factors in 1
With \(p_i\) as in Lemma 10.1.9, we have for large \(n\)
By Lemma 10.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.
10.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 10.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.
10.1.9 Conclusion for large \(n\)
For every integer \(n \ge 89693^2\), the integer \(L_n\) is not highly abundant.
10.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 10.2.12, Sublemma 10.2.13, Sublemma 10.2.14, Sublemma 10.2.15, and Sublemma 10.2.17 each contribute at most \((\varepsilon /5) n\). Then use Proposition 10.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\).-