8 Tertiary explicit estimates
8.1 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 8.1.12, Sublemma 8.1.13, Sublemma 8.1.14, Sublemma 8.1.15, and Sublemma 8.1.17 each contribute at most \((\varepsilon /5) n\). Then use Proposition 8.1.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\).-