9 Tertiary explicit estimates
9.1 The least common multiple sequence is not highly abundant for large \(n\)
9.1.1 Problem statement and notation
Definition
34
\(\sigma (n)\) is the sum of the divisors of \(n\).
Definition
35
A positive integer \(N\) is called highly abundant (HA) if
\[ \sigma (N) {\gt} \sigma (m) \]
for all positive integers \(m {\lt} N\), where \(\sigma (n)\) denotes the sum of the positive divisors of \(n\).
Definition
36
For each integer \(n \ge 1\), define
\[ L_n := \lcm (1,2,\dots ,n). \]
We call \((L_n)_{n \ge 1}\) the least common multiple sequence.
Original MathOverflow question. Is it true that every value in the sequence \(L_n = \lcm (1,2,\dots ,n)\) is highly abundant? Equivalently,
\[ \{ L_n : n \ge 1\} \subseteq HA? \]
In this note we record the structure of an argument showing that, for all sufficiently large \(n\), the integer \(L_n\) is not highly abundant. This argument was taken from this MathOverflow answer.
9.1.2 A general criterion using three medium primes and three large primes
In this subsection we assume that \(n \geq 1\) and that \(p_1,p_2,p_3,q_1,q_2,q_3\) are primes satisfiying
\[ \sqrt{n} {\lt} p_1 {\lt} p_2 {\lt} p_3 {\lt} q_1 {\lt} q_2 {\lt} q_3 {\lt} n \]
and the key criterion
\begin{equation} \label{eq:main-ineq} \prod _{i=1}^3\Bigl(1+\frac{1}{q_i}\Bigr) \le \Biggl( \prod _{i=1}^3 \Bigl(1+\frac{1}{p_i(p_i+1)}\Bigr) \Biggr) \Bigl(1 + \frac{3}{8n}\Bigr) \Biggl(1 - \frac{4 p_1 p_2 p_3}{q_1 q_2 q_3}\Biggr). \end{equation}
1
Lemma
128
We have \(4 p_1 p_2 p_3 {\lt} q_1 q_2 q_3\).
Proof
▶
Obvious from the non-negativity of the left-hand side of 1.
9.1.3 Factorisation of \(L_n\) and construction of a competitor
Lemma
129
Factorisation of \(L_n\)
There exists a positive integer \(L'\) such that
\[ L_n = q_1 q_2 q_3 \, L' \]
and each prime \(q_i\) divides \(L_n\) exactly once and does not divide \(L'\).
Proof
▶
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\).
Lemma
130
Normalised divisor sum for \(L_n\)
Let \(L'\) be as in Lemma 129. Then
\begin{equation} \label{eq:sigmaLn} \frac{\sigma (L_n)}{L_n} \; =\; \frac{\sigma (L')}{L'} \prod _{i=1}^3 \Bigl(1 + \frac{1}{q_i}\Bigr). \end{equation}
2
Proof
▶
Use the multiplicativity of \(\sigma (\cdot )\) and the fact that each \(q_i\) occurs to the first power in \(L_n\). Then
\[ \sigma (L_n) = \sigma (L') \prod _{i=1}^3 \sigma (q_i) = \sigma (L') \prod _{i=1}^3 (1+q_i). \]
Dividing by \(L_n = L' \prod _{i=1}^3 q_i\) gives
\[ \frac{\sigma (L_n)}{L_n} = \frac{\sigma (L')}{L'} \prod _{i=1}^3 \frac{1+q_i}{q_i} = \frac{\sigma (L')}{L'} \prod _{i=1}^3 \Bigl(1 + \frac{1}{q_i}\Bigr). \]
Lemma
131
There exist integers \(m \ge 0\) and \(r\) satisfying \(0 {\lt} r {\lt} 4 p_1 p_2 p_3\) and
\[ q_1 q_2 q_3 = 4 p_1 p_2 p_3 m + r \]
Proof
▶
This is division with remainder.
Definition
37
With \(m,r\) as above, define the competitor
\[ M := 4 p_1 p_2 p_3 m L'. \]
Lemma
132
Basic properties of \(M\)
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}. \]
Proof
▶
The first item is by construction of the division algorithm. For the second, note that
\[ L_n = q_1 q_2 q_3 L' = (4 p_1 p_2 p_3 m + r) L' {\gt} 4 p_1 p_2 p_3 m L' = M, \]
since \(r{\gt}0\). For the third,
\[ \frac{L_n}{M} = \frac{4 p_1 p_2 p_3 m + r}{4 p_1 p_2 p_3 m} = 1 + \frac{r}{4 p_1 p_2 p_3 m} = \Bigl(1 - \frac{r}{4 p_1 p_2 p_3 m + r}\Bigr)^{-1} = \Bigl(1 - \frac{r}{q_1 q_2 q_3}\Bigr)^{-1}. \]
Since \(0 {\lt} r {\lt} 4p_1p_2p_3\) and \(4p_1p_2p_3 {\lt} q_1q_2q_3\), we have
\[ 0{\lt}\frac{r}{q_1 q_2 q_3}{\lt}\frac{4p_1p_2p_3}{q_1 q_2 q_3}, \]
so
\[ \Bigl(1-\frac{r}{q_1 q_2 q_3}\Bigr)^{-1} {\lt} \Bigl(1-\frac{4p_1p_2p_3}{q_1 q_2 q_3}\Bigr)^{-1}. \]
9.1.4 A sufficient condition
We give a sufficient condition for \(\sigma (M) \geq \sigma (L_n)\).
Lemma
133
A sufficient inequality
Suppose
\[ \frac{\sigma (M)}{M} \Bigl(1 - \frac{4 p_1 p_2 p_3}{q_1 q_2 q_3}\Bigr) \; \ge \; \frac{\sigma (L_n)}{L_n}. \]
Then \(\sigma (M) \ge \sigma (L_n)\), and so \(L_n\) is not highly abundant.
Proof
▶
By Lemma 132,
\[ \frac{L_n}{M} {\lt} \Bigl(1 - \frac{4 p_1 p_2 p_3}{q_1 q_2 q_3}\Bigr)^{-1}. \]
Hence
\[ \frac{\sigma (M)}{M} \ge \frac{\sigma (L_n)}{L_n} \Bigl(1 - \frac{4 p_1 p_2 p_3}{q_1 q_2 q_3}\Bigr)^{-1} {\gt} \frac{\sigma (L_n)}{L_n} \cdot \frac{M}{L_n}. \]
Multiplying both sides by \(M\) gives
\[ \sigma (M) {\gt} \sigma (L_n) \cdot \frac{M}{L_n} \]
and hence
\[ \sigma (M) \ge \sigma (L_n), \]
since \(M/L_n{\lt}1\) and both sides are integers.
Combining Lemma 133 with Lemma 130, we see that it suffices to bound \(\sigma (M)/M\) from below in terms of \(\sigma (L')/L'\):
Lemma
134
Reduction to a lower bound for \(\sigma (M)/M\)
If
\begin{equation} \label{eq:sigmaM-lower} \frac{\sigma (M)}{M} \; \ge \; \frac{\sigma (L')}{L'} \Biggl( \prod _{i=1}^3 \Bigl(1+\frac{1}{p_i(p_i+1)}\Bigr) \Biggr) \Bigl(1 + \frac{3}{8n}\Bigr), \end{equation}
3
then \(L_n\) is not highly abundant.
Proof
▶
Insert 3 and 2 into the desired inequality and compare with the assumed bound 1; this is a straightforward rearrangement.
9.1.5 Effect of modifying prime powers
Now we estimate the effect on \(\sigma (\cdot )/(\cdot )\) of increasing certain prime exponents.
Lemma
135
Effect of increasing the exponent of \(p_i\)
Fix \(i \in \{ 1,2,3\} \). Suppose that in passing from \(L'\) to \(M\) we increase the exponent of \(p_i\) by exactly \(1\). Then the normalised divisor sum is multiplied by a factor
\[ \frac{(1+p_i+p_i^2)/p_i^2}{(1+p_i)/p_i} = 1 + \frac{1}{p_i(p_i+1)}. \]
Proof
▶
If the exponent of \(p_i\) in \(L'\) is \(e\), the contribution of \(p_i\) to \(\sigma (L')/L'\) is
\[ \frac{1 + p_i + \dots + p_i^e}{p_i^e}. \]
Increasing the exponent to \(e+1\) multiplies this factor by
\[ \frac{(1+p_i+\dots +p_i^{e+1})/p_i^{e+1}}{(1+p_i+\dots +p_i^e)/p_i^e} = \frac{1+p_i+\dots +p_i^{e+1}}{p_i(1+p_i+\dots +p_i^e)} = \frac{1+p_i+\dots +p_i^e + p_i^{e+1}}{p_i(1+p_i+\dots +p_i^e)}. \]
Since all terms \(1,p_i,\dots \) are positive, replacing \(e\) by \(1\) only decreases this ratio. Thus
\[ \frac{(1+p_i+p_i^2)/p_i^2}{(1+p_i)/p_i} \le \frac{(1+p_i+\dots +p_i^{e+1})/p_i^{e+1}}{(1+p_i+\dots +p_i^e)/p_i^e}. \]
In our application, the exponent is exactly increased by \(1\), and we may bound from below by the case \(e=1\), giving the claimed factor
\[ 1 + \frac{1}{p_i(p_i+1)}. \]
Lemma
136
Effect of increasing the exponent of \(2\)
Let \(k\) be the largest integer such that \(2^k \le n\). Then the exponent of \(2\) in \(L'\) is at least \(k\), and the exponent of \(2\) in \(M\) is at least \(k+2\). Consequently,
\begin{equation} \label{eq:2-lower} \frac{(1+2+\dots +2^{k+2})/2^{k+2}}{(1+2+\dots +2^k)/2^k} \ge 1 + \frac{3}{2^{k+3}-4} \ge 1 + \frac{3}{8n}. \end{equation}
4
Proof
▶
Since \(2^k \le n\), the number \(2^k\) divides \(\lcm (1,2,\dots ,n)\), hence \(2^k\) divides \(L_n\) and thus also divides \(L'\). The definition of \(M\) multiplies \(L'\) by \(4 = 2^2\), so the exponent of \(2\) in \(M\) is at least \(k+2\).
The ratio of contributions of \(2\) to \(\sigma (M)/M\) and \(\sigma (L')/L'\) is
\[ \frac{(1+2+\dots +2^{k+2})/2^{k+2}}{(1+2+\dots +2^k)/2^k}. \]
A direct calculation yields
\[ \frac{1+2+\dots +2^{k+2}}{1+2+\dots +2^k} = \frac{2^{k+3}-1}{2^{k+1}-1} = 1 + \frac{3(2^k-1)}{2^{k+1}-1} \ge 1 + \frac{3}{2^{k+3}-4}, \]
giving the first inequality in 4. Finally, since \(2^k \le n {\lt} 2^{k+1}\), we have \(2^{k+3} {\lt} 8n\), so
\[ \frac{3}{2^{k+3}-4} \ge \frac{3}{8n}, \]
giving the second inequality.
Lemma
137
Effect of the remaining factor \(m\)
The extra factor \(m\) in the definition of \(M\) can only increase the normalised divisor sum:
\[ \frac{\sigma (M)}{M} \ge \frac{\sigma (L')}{L'} \times \Bigl(\text{multiplicative factors coming from }p_i\text{ and }2\Bigr). \]
Proof
▶
Since \(m\) is a positive integer, any extra primes (or higher exponents) it introduces appear as multiplicative factors of the form
\[ \frac{1+p+\dots +p^e}{p^e} \ge 1. \]
Hence they can only increase the value of \(\sigma (M)/M\).
9.1.6 Conclusion of the criterion
Lemma
138
Lower bound for \(\sigma (M)/M\)
With notation as above,
\[ \frac{\sigma (M)}{M} \ge \frac{\sigma (L')}{L'} \Biggl( \prod _{i=1}^3 \Bigl(1 + \frac{1}{p_i(p_i+1)}\Bigr) \Biggr) \Bigl(1 + \frac{3}{8n}\Bigr). \]
Proof
▶
Multiply the contributions from Lemma 135 for \(i=1,2,3\), from Lemma 136 for the prime \(2\), and note that Lemma 137 allows us to ignore any additional (non-decreasing) contribution from \(m\). This gives exactly the stated lower bound.
Theorem
51
Let \(n \geq 1\). Suppose that primes \(p_1,p_2,p_3,q_1,q_2,q_3\) satisfy
\[ \sqrt{n} {\lt} p_1 {\lt} p_2 {\lt} p_3 {\lt} q_1 {\lt} q_2 {\lt} q_3 {\lt} n \]
and the key criterion
\begin{equation} \label{eq:main-ineq} \prod _{i=1}^3\Bigl(1+\frac{1}{q_i}\Bigr) \le \Biggl( \prod _{i=1}^3 \Bigl(1+\frac{1}{p_i(p_i+1)}\Bigr) \Biggr) \Bigl(1 + \frac{3}{8n}\Bigr) \Biggl(1 - \frac{4 p_1 p_2 p_3}{q_1 q_2 q_3}\Biggr). \end{equation}
5
Then \(L_n\) is not highly abundant.
Proof
▶
By Lemma 138, the condition 3 holds. By Lemma 134 this implies
\[ \frac{\sigma (M)}{M} \Bigl(1 - \frac{4 p_1 p_2 p_3}{q_1 q_2 q_3}\Bigr) \ge \frac{\sigma (L_n)}{L_n}. \]
Applying Lemma 133, 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.
9.1.7 Choice of six primes \(p_i,q_i\) for large \(n\)
Lemma
139
Choice of medium primes \(p_i\)
Let \(n \ge X_0^2\). Set \(x := \sqrt{n}\). Then there exist primes \(p_1,p_2,p_3\) with
\[ p_i \le x \Bigl(1 + \frac{1}{\log ^3 x}\Bigr)^i \]
and \(p_1 {\lt} p_2 {\lt} p_3\). Moreover, \(\sqrt{n} {\lt} p_1\)
Proof
▶
Apply Theorem 50 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.
Lemma
140
Choice of large primes \(q_i\)
Let \(n \ge X_0^2\). Then there exist primes \(q_1 {\lt} q_2 {\lt} q_3\) with
\[ q_{4-i} \ge n \Bigl(1 + \frac{1}{\log ^3 \sqrt{n}}\Bigr)^{-i} \]
for \(i = 1,2,3\), and \(q_1 {\lt} q_2 {\lt} q_3 {\lt} n\).
Proof
▶
Apply Theorem 50 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.
9.1.8 Bounding the factors in 5
Lemma
141
Bounds for the \(q_i\)-product
With \(p_i,q_i\) as in Lemmas 139 and 140, we have
\begin{equation} \label{eq:qi-upper} \prod _{i=1}^3 \Bigl(1 + \frac{1}{q_i}\Bigr) \le \prod _{i=1}^3 \Bigl(1 + \frac{\bigl(1 + \frac{1}{\log ^3 \sqrt{n}}\bigr)^i}{n} \Bigr). \end{equation}
6
Proof
▶
By Lemma 140, each \(q_i\) is at least
\[ n\Bigl(1 + \frac{1}{\log ^3 \sqrt{n}}\Bigr)^{-j} \]
for suitable indices \(j\), so \(1/q_i\) is bounded above by
\[ \frac{\bigl(1 + \frac{1}{\log ^3 \sqrt{n}}\bigr)^i}{n} \]
after reindexing. Multiplying the three inequalities gives 6.
Lemma
142
Bounds for the \(p_i\)-product
With \(p_i\) as in Lemma 139, we have for large \(n\)
\begin{equation} \label{eq:pi-lower} \prod _{i=1}^3 \Bigl(1 + \frac{1}{p_i(p_i+1)}\Bigr) \ge \prod _{i=1}^3 \Bigl( 1 + \frac{1}{\bigl(1 + \frac{1}{\log ^3 \sqrt{n}}\bigr)^{2i} (n + \sqrt{n})} \Bigr). \end{equation}
7
Proof
▶
By Lemma 139, \(p_i \le \sqrt{n} (1+1/\log ^3\sqrt{n})^i\). Hence
\[ p_i^2 \le n\bigl(1 + \tfrac {1}{\log ^3 \sqrt{n}}\bigr)^{2i} \quad \text{and}\quad p_i+1 \le p_i(1 + 1/\sqrt{n}) \le (1+1/\sqrt{n}) p_i. \]
From these one gets
\[ p_i(p_i+1) \le \bigl(1 + \tfrac {1}{\log ^3 \sqrt{n}}\bigr)^{2i} (n + \sqrt{n}), \]
and hence
\[ \frac{1}{p_i(p_i+1)} \ge \frac{1}{\bigl(1 + \tfrac {1}{\log ^3 \sqrt{n}}\bigr)^{2i} (n + \sqrt{n})}. \]
Taking \(1+\cdot \) and multiplying over \(i=1,2,3\) gives 7.
Lemma
143
Lower bound for the product ratio \(p_i/q_i\)
With \(p_i,q_i\) as in Lemmas 139 and 140, we have
\begin{equation} \label{eq:pq-ratio} 1 - \frac{4 p_1 p_2 p_3}{q_1 q_2 q_3} \ge 1 - \frac{4 \bigl(1 + \frac{1}{\log ^3 \sqrt{n}}\bigr)^{12}}{n^{3/2}}. \end{equation}
8
Proof
▶
We have \(p_i \le \sqrt{n} (1+1/\log ^3 \sqrt{n})^i\), so
\[ p_1 p_2 p_3 \le n^{3/2} \bigl(1 + \tfrac {1}{\log ^3 \sqrt{n}}\bigr)^{6}. \]
Similarly, \(q_i \ge n(1+1/\log ^3 \sqrt{n})^{-i}\), so
\[ q_1 q_2 q_3 \ge n^3 \bigl(1 + \tfrac {1}{\log ^3 \sqrt{n}}\bigr)^{-6}. \]
Combining,
\[ \frac{p_1 p_2 p_3}{q_1 q_2 q_3} \le \frac{n^{3/2} \bigl(1 + \frac{1}{\log ^3 \sqrt{n}}\bigr)^{6}}{n^3 \bigl(1 + \frac{1}{\log ^3 \sqrt{n}}\bigr)^{-6}} = \frac{\bigl(1 + \frac{1}{\log ^3 \sqrt{n}}\bigr)^{12}}{n^{3/2}}. \]
This implies 8.
9.1.9 Reduction to a small epsilon-inequality
Lemma
144
Uniform bounds for large \(n\)
For all \(n \ge X_0^2 = 89693^2\) we have
\[ \frac{1}{\log ^3 \sqrt{n}} \le 0.000675, \qquad \frac{1}{n^{3/2}} \le \frac{1}{89693}\cdot \frac{1}{n}. \]
Proof
▶
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.
Definition
38
For \(n \ge X_0^2\), define \(\varepsilon := 1/n\). Then
\[ 0 {\lt} \varepsilon \le \frac{1}{X_0^2} = \frac{1}{89693^2}. \]
Lemma
145
Polynomial approximation of the inequality
For \(0 \le \varepsilon \le 1/89693^2\), we have
\[ \prod _{i=1}^3 (1 + 1.000675^i \varepsilon ) \le \Bigl(1 + 3.01\varepsilon + 3.01\varepsilon ^2 + 1.01\varepsilon ^3\Bigr), \]
and
\[ \prod _{i=1}^3 \Bigl(1 + \frac{\varepsilon }{1.000675^{2i}}\Bigr) \Bigl(1 + \frac{3}{8}\varepsilon \Bigr) \Bigl(1 - \frac{4 \times 1.000675^{12}}{89693}\varepsilon \Bigr) \ge 1 + 3.37\varepsilon - 0.01\varepsilon ^2. \]
Proof
▶
Expand each finite product as a polynomial in \(\varepsilon \), estimate the coefficients using the bounds in Lemma 144, and bound the tails by simple inequalities such as
\[ (1+C\varepsilon )^k \le 1 + k C\varepsilon + \dots \]
for small \(\varepsilon \). All coefficients can be bounded numerically in a rigorous way; this step is a finite computation that can be checked mechanically.
Lemma
146
Final polynomial comparison
For \(0 \le \varepsilon \le 1/89693^2\), we have
\[ 1 + 3.01\varepsilon + 3.01\varepsilon ^2 + 1.01\varepsilon ^3 \le 1 + 3.37\varepsilon - 0.01\varepsilon ^2. \]
Proof
▶
This is equivalent to
\[ 3.01\varepsilon + 3.01\varepsilon ^2 + 1.01\varepsilon ^3 \le 3.37\varepsilon - 0.01\varepsilon ^2, \]
or
\[ 0 \le (3.37 - 3.01)\varepsilon - (3.01+0.01)\varepsilon ^2 - 1.01\varepsilon ^3. \]
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.
Proposition
8
Verification of 5 for large \(n\)
For every integer \(n \ge X_0^2 = 89693^2 \approx 8.04\times 10^9\), the primes \(p_i,q_i\) constructed in Lemmas 139 and 140 satisfy the inequality 5.
Proof
▶
Combine Lemma 141, Lemma 142, and Lemma 143. Then apply Lemma 144 and set \(\varepsilon = 1/n\). The products are bounded by the expressions in Lemma 145, and the inequality in Lemma 146 then ensures that 5 holds.
9.1.10 Conclusion for large \(n\)
Theorem
52
Non-highly abundant for large \(n\)
For every integer \(n \ge 89693^2\), the integer \(L_n\) is not highly abundant.
Proof
▶
By Proposition 8, there exist primes \(p_1,p_2,p_3,q_1,q_2,q_3\) satisfying the hypotheses of Theorem 51. Hence \(L_n\) is not highly abundant.
In combination with earlier arguments and computations for smaller \(n\), one can conclude that \(L_n\) is highly abundant only for finitely many indices \(n\), and these indices can be determined explicitly by exhaustive computation.