Erdős Problem #18

Problem Number

From the inherited numbering in the previous rounds (Lemmas 18.1--18.11 and the earlier artifacts 18_v2.tex, 18_solutions.tex), the Erdős problem number here is $18$. This round is therefore exported as 18_solutions.tex.

ROUND-4 OBJECTIVE

Path (C): obstruction/correction.

Round 3 produced a sharp factorial obstruction, \[ h(n!) \gg (\log n)^2, \] but it still left the general question $Q1$ without any comparably sharp universal lower bound. In this round I pursue the obstruction route for the general practical-number problem:

• prove a new lower bound valid for every sufficiently large practical $m$, \[ h(m)\ge \left(\frac1{\log 2}-o(1)\right)\log\log m; \]
• deduce that every version of $Q1$ with exponent $C<1$ is false;
• combine this with the Round 3 factorial lower bound to isolate the minimal exponent ranges currently compatible with the problem: \[ C\ge 1 \text{ for (Q1)},\qquad C\ge 2 \text{ for (Q2)}; \]
• add a new structural lemma for factorials: \[ h((n+1)!)\le h(n!)+1, \] which gives a clean recursive upper envelope for the factorial sequence.

This is the most promising direction after Round 3 because it closes the remaining low-exponent loophole on the general side and isolates precisely what any future positive solution would still have to prove.

Round-3 FOUNDATION USED

I use the following earlier-round results as black boxes.

• Round-2 counting lemma and explicit corollary: for every practical $m$, \[ \sum_{t=0}^{h(m)} \binom{\tau(m)-1}{t}\ge m, \] hence \[ h(m)\ge \frac{\log m}{1+\log(\tau(m)-1)}. \]
• Round-3 factorial obstruction: there exists an absolute constant $c>0$ such that \[ h(n!)\ge c(\log n)^2 \] for all sufficiently large $n$.
• Round-3 exact value: \[ h(12!)=8, \] and also the inherited exact table through $n=12$, in particular $h(11!)=7$.

I do not re-prove these facts here.

NEW INSIGHT / TOOL (ROUND-4)

There are two genuinely new ingredients in this round.

1. A global practical-number obstruction from the maximal order of the divisor function. Combining the Round-2 counting lower bound with the classical Wigert maximal-order theorem \[ \log \tau(N)\le (\log 2+o(1))\frac{\log N}{\log\log N}, \] I obtain the new universal lower bound \[ h(m)\ge \left(\frac1{\log 2}-o(1)\right)\log\log m \] for all practical $m$.

2. An interval-divisibility extension lemma. If $m$ is practical and every integer $1\le r<A$ divides $m$, then \[ h(Am)\le h(m)+1. \] Applied with $m=n!$ and $A=n+1$, this gives the new factorial recursion \[ h((n+1)!)\le h(n!)+1. \]

The first item gives a new obstruction relevant to $Q1$; the second gives a new construction principle relevant to $Q2$.

ATTACK PLAN (ROUND-4)

After Round 3, the exact unresolved gap was this:

Nothing in the previous rounds excluded that possibility. The plan here is therefore:

• use the Round-2 counting lemma as the bridge from divisor counts to lower bounds for $h(m)$;
• import a sharp upper bound for $\tau(m)$ (Wigert) to force a lower bound of order $\log\log m$ for every practical $m$;
• deduce a rigorous obstruction: every $o(\log\log m)$ bound is impossible on the practical-number side;
• then return to factorials and prove a new exact recursion $h((n+1)!)\le h(n!)+1$, which complements the Round-3 lower bound by giving a clean structural upper-step inequality.

This overcomes the earlier obstacle because it no longer relies on factorial-specific input: it treats all practical numbers at once.

WORK (ROUND-4)

External theorem used. I use the following classical theorem on the divisor function.

Wigert maximal-order theorem. One has \[ \limsup_{N\to\infty}\frac{\log \tau(N)\,\log\log N}{\log N}=\log 2. \] Equivalently, for every $\varepsilon>0$, there exists $N_0(\varepsilon)$ such that \[ \log \tau(N)\le (\log 2+\varepsilon)\frac{\log N}{\log\log N} \qquad (N\ge N_0(\varepsilon)). \]

This theorem applies to arbitrary integers $N$, hence in particular to practical integers.

Theorem 18.12 (general lower bound for practical numbers)

For every $\varepsilon>0$, there exists $M_0(\varepsilon)$ such that every practical integer $m\ge M_0(\varepsilon)$ satisfies \[ h(m)\ge \frac{\log m}{1+(\log 2+\varepsilon)\frac{\log m}{\log\log m}} = \frac{\log\log m}{(\log 2+\varepsilon)+\frac{\log\log m}{\log m}}. \] Consequently, \[ h(m)\ge \left(\frac1{\log 2+\varepsilon}+o(1)\right)\log\log m \qquad (m\to\infty,\ m\ \text{practical}), \] and therefore \[ \liminf_{\substack{m\to\infty\\ m\ \mathrm{practical}}} \frac{h(m)}{\log\log m}\ge \frac1{\log 2}. \]

Proof. Fix $\varepsilon>0$. By Wigert's theorem, for all sufficiently large integers $m$, \[ \log \tau(m)\le (\log 2+\varepsilon)\frac{\log m}{\log\log m}. \] Let $m$ now be practical and large enough that the above bound holds. The Round-2 counting corollary gives \[ h(m)\ge \frac{\log m}{1+\log(\tau(m)-1)}. \] Since $\tau(m)-1<\tau(m)$, we have \[ \log(\tau(m)-1)\le \log\tau(m)\le (\log 2+\varepsilon)\frac{\log m}{\log\log m}, \] hence \[ h(m)\ge \frac{\log m}{1+(\log 2+\varepsilon)\frac{\log m}{\log\log m}}. \] Multiplying numerator and denominator by $\frac{\log\log m}{\log m}$ yields \[ h(m)\ge \frac{\log\log m}{(\log 2+\varepsilon)+\frac{\log\log m}{\log m}}. \] Since $\frac{\log\log m}{\log m}\to 0$, this gives \[ h(m)\ge \left(\frac1{\log 2+\varepsilon}+o(1)\right)\log\log m. \] Because $\varepsilon>0$ was arbitrary, the stated $\liminf$ bound follows. $\square$

Corollary 18.13 (fatal obstruction for sublinear powers of $\log\log m$)

For every fixed $\delta>0$, there are only finitely many practical integers $m$ such that \[ h(m)\le (\log\log m)^{1-\delta}. \] Equivalently, every bound of the form \[ h(m)=o(\log\log m) \] is false on the practical numbers.

Proof. By Theorem 18.12, there exists $c>0$ such that $h(m)\ge c\log\log m$ for all sufficiently large practical $m$. But \[ c\log\log m > (\log\log m)^{1-\delta} \] for all sufficiently large $m$, since $(\log\log m)^\delta\to\infty$. Thus the displayed inequality can hold only finitely often. $\square$

Corollary 18.14 (minimal corrected form of Q1)

Any positive answer to $Q1$ must have exponent at least $1$. More precisely:

If there exists $C>0$ and infinitely many practical $m$ such that \[ h(m)\le (\log\log m)^C, \] then necessarily $C\ge 1$.

Thus the minimal exponent range still compatible with the current evidence is \[ C\ge 1. \]

Proof. If $C<1$, write $C=1-\delta$ with $\delta>0$. Then Corollary 18.13 gives a contradiction. $\square$

Corollary 18.15 (minimal corrected exponent range for Q2)

Using the Round-3 bound $h(n!)\gg (\log n)^2$, one immediately gets:

If there exists $C>0$ such that \[ h(n!)\le (\log n)^C \] for all sufficiently large $n$, then necessarily $C\ge 2$.

Equivalently, for every fixed $\delta>0$, the bound \[ h(n!)\le (\log n)^{2-\delta} \] fails for all sufficiently large $n$.

Proof. Round 3 showed that $h(n!)\ge c(\log n)^2$ for some $c>0$ and all large $n$. Since \[ c(\log n)^2>(\log n)^{2-\delta} \] for large $n$, any exponent $C<2$ is impossible. $\square$

Lemma 18.16 (interval-divisibility extension)

Let $m$ be practical and let $A\ge 2$ be an integer. Assume that every integer \[ 1\le r<A \] divides $m$. Then $Am$ is practical and \[ h(Am)\le h(m)+1. \]

Proof. Fix $x$ with $1\le x<Am$. Write \[ x=Aq+r,\qquad 0\le q<m,\quad 0\le r<A. \] Because $m$ is practical and $q<m$, there exist distinct divisors $d_1,\dots,d_t\mid m$ such that \[ q=d_1+\cdots+d_t,\qquad t\le h(m). \] Multiplying by $A$, we get \[ Aq=Ad_1+\cdots+Ad_t, \] where $Ad_1,\dots,Ad_t$ are distinct divisors of $Am$.

If $r=0$, this already represents $x$ using at most $h(m)$ divisors of $Am$.

If $r>0$, then by hypothesis $r\mid m$, hence $r\mid Am$. Also \[ r<A\le Ad_i \] for every $i$, so $r$ is distinct from all of the divisors $Ad_i$. Therefore \[ x=(Ad_1+\cdots+Ad_t)+r \] is a representation of $x$ as a sum of at most $h(m)+1$ distinct divisors of $Am$.

Since this holds for every $1\le x<Am$, the number $Am$ is practical and $h(Am)\le h(m)+1$. $\square$

Corollary 18.17 (one-step factorial recursion)

For every $n\ge 1$, \[ h((n+1)!)\le h(n!)+1. \]

Proof. Apply Lemma 18.16 with $m=n!$ and $A=n+1$. Indeed every integer $1\le r<n+1$ divides $n!$. $\square$

Corollary 18.18 (a new recursive upper envelope for factorials)

For all $n\ge 11$, \[ h(n!)\le n-4. \]

Proof. Round 3 established the exact value $h(11!)=7$. Now iterate Corollary 18.17: \[ h(n!)\le h(11!)+(n-11)=7+(n-11)=n-4 \] for every $n\ge 11$. $\square$

ADVERSARIAL VERIFICATION

I now test the new work for hidden gaps.

• Use of external input. The only outside theorem is Wigert's maximal-order bound for $\tau(N)$. I stated it in a form exactly sufficient for the argument. Its hypothesis is simply that $N$ is a large positive integer, which is satisfied when $N=m$ is a large practical integer.

• Dependence on earlier rounds. Theorem 18.12 uses only the Round-2 counting corollary and no other unproved structural claim. Corollary 18.15 uses only the Round-3 lower bound $h(n!)\gg(\log n)^2$. Corollary 18.18 uses only the exact Round-3 value $h(11!)=7$.

• Lemma 18.16 distinctness issue. This is the only delicate point. If $r>0$, then $r<A$, whereas every divisor $Ad_i$ is at least $A$. Hence $r$ cannot coincide with any $Ad_i$. Distinctness among the $Ad_i$ follows from distinctness among the $d_i$.

• Boundary cases in Lemma 18.16. If $q=0$, the representation reduces to $x=r$, and since $r<A$ divides $m$, it is a divisor of $Am$. If $r=0$, no extra divisor is added. The case $x=0$ is irrelevant because $h(Am)$ only concerns $1\le x<Am$.

• Could Corollary 18.13 fail because the constant from Theorem 18.12 is ineffective? No. Effectivity is unnecessary. The theorem gives an eventual linear lower bound $h(m)\ge c\log\log m$ for some positive $c$, and that already dominates every power $(\log\log m)^{1-\delta}$.

• Interaction with the original questions. The new results do not disprove the original forms of $Q1$ or $Q2$. They only prove that any positive answer must lie above the exponent thresholds $1$ and $2$, respectively. So there is no logical conflict with the inherited unresolved status.

No contradiction or gap was found in the new argument.

FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

This round makes two substantive advances beyond Round 3.

• General obstruction for practical numbers. For all sufficiently large practical $m$, \[ h(m)\ge \left(\frac1{\log 2}-o(1)\right)\log\log m. \] Therefore every sublinear power of $\log\log m$ is impossible, and any positive answer to $Q1$ must have exponent $C\ge 1$.

• New structural factorial lemma. For every $n\ge 1$, \[ h((n+1)!)\le h(n!)+1. \] Combining this with the inherited exact value $h(11!)=7$ yields the new unconditional upper envelope \[ h(n!)\le n-4\qquad (n\ge 11). \] Together with the Round-3 lower bound $h(n!)\gg (\log n)^2$, this shows that any positive answer to the stronger factorial question must have exponent $C\ge 2$.

So the current rigorous picture is:

\[ \boxed{\text{Q1 can only possibly hold with } C\ge 1,} \qquad \boxed{\text{Q2 can only possibly hold with } C\ge 2.} \]

The original existence questions remain open.

COMPLETION ESTIMATE

COMPLETION: 72%

REFERENCES

• Round-2 output for Problem 18, specifically the counting lemma and its explicit corollary $h(m)\ge \frac{\log m}{1+\log(\tau(m)-1)}$.
• Round-3 output for Problem 18, specifically the lower bound $h(n!)\gg (\log n)^2$ and the exact values $h(11!)=7$, $h(12!)=8$.
• Paul Pollack, The maximal size of the $k$-fold divisor function for very large $k$, Introduction, for the quoted Wigert bound \[ \log d(N)\le (1+o(1))\,\log 2\,\frac{\log N}{\log\log N}. \]
• Christian Elsholtz, Marc Technau, Niclas Technau, The maximal order of iterated multiplicative functions, Mathematika 65 $2019$, abstract, which records the sharp maximal-order formula \[ \max_{n\le x}\log d(n)=\frac{\log x}{\log\log x}(\log 2+o(1)). \]

Problem Number

From the inherited numbering in the previous rounds (Lemmas 18.1, 18.2, …, together with the prior artifact name 18_v2.tex), I identify the Erdős problem number here as $18$. Accordingly this round is exported as 18_solutions.tex.

ROUND-3 OBJECTIVE

Path (A): proof-oriented progress.

Round 2 produced a general counting lower bound for $h(m)$, but for factorials it only yielded \[ h(n!) \gg \log n. \] That still left open the possibility that $h(n!)$ might even be $O(\log n)$. In this round I target the sharpest accessible obstruction: I strengthen the Round 2 factorial divisor-count estimate from \[ \log \tau(n!) = O(n) \quad\text{to}\quad \log \tau(n!) = O\!\left(\frac{n}{\log n}\right), \] and then feed this into the Round 2 counting lemma to prove the new unconditional lower bound \[ h(n!) \gg (\log n)^2. \] This rules out the entire class of hoped-for bounds $h(n!) = O(\log n)$. I also extend the exact computation from Round 2 by proving computationally that \[ h(12!) = 8. \]

ROUND-2 FOUNDATION USED

I use the following Round 2 results as black boxes.

• Round-2 counting lemma (Lemma 18.4 and its explicit corollary): if $m$ is practical, then \[ \sum_{t=0}^{h(m)} \binom{\tau(m)-1}{t} \ge m, \] and in particular \[ h(m) \ge \frac{\log m}{1+\log(\tau(m)-1)}. \]
• Round-2 exact computations: \[ h(10!)=7,\qquad h(11!)=7, \] with the full table already established for $1\le n\le 11$.

I do not reuse the Round 2 estimate $\log\tau(n!)=O(n)$; the main point of this round is to strengthen it.

NEW INSIGHT / TOOL (ROUND-3)

The new ingredient is an elementary prime-counting input, proved directly from binomial coefficients, which is strong enough to improve the factorial divisor-count estimate by a full factor of $\log n$.

More precisely, the new chain is: \[ \pi(x) \ll \frac{x}{\log x} \Longrightarrow \log\tau(n!) \ll \frac{n}{\log n} \Longrightarrow h(n!) \gg (\log n)^2. \]

This is a genuine advance over Round 2. It does not solve $Q2$, but it proves a sharp obstruction: any eventual upper bound of the form \[ h(n!)\le (\log n)^C \] must have $C\ge 2$. In particular, the tempting exponent-$1$ target $h(n!)=O(\log n)$ is impossible.

A second new item is the exact extension of the computed table by one step: \[ h(12!)=8. \]

ATTACK PLAN (ROUND-3)

The exact gap left after Round 2 was this: there was no serious lower-bound obstruction to a logarithmic upper bound for $h(n!)$. The Round 2 result $h(n!)\gg \log n$ was too weak to rule out $h(n!)\asymp \log n$.

To close that gap as far as possible in this round, I prove the following claims.

1. An elementary Chebyshev-type bound \[ \pi(x) \ll \frac{x}{\log x}. \]
2. A strengthened factorial divisor-count estimate \[ \log\tau(n!) \ll \frac{n}{\log n}. \]
3. A new unconditional lower bound \[ h(n!) \gg (\log n)^2. \]
4. An exact computation extending the data table to \[ h(12!)=8. \]

This overcomes the Round 2 obstacle because the strengthened divisor-count estimate feeds directly into the already-established counting lemma, and the resulting lower bound rules out the entire $O(\log n)$ proof strategy family.

WORK (ROUND-3)

Lemma 18.8: a Chebyshev-type upper bound for $\pi(x)$

Proposition 18.9: sharpening $\log\tau(n!)$

Corollary 18.10: the new lower bound $h(n!)\gg (\log n)^2$

Proposition 18.11: exact computation of $h(12!)$

Combining Proposition Proposition (Proposition 18.11) with the inherited Round 2 data yields the exact table \[ \begin{array}{c|c} n & h(n!)\\\hline 10 & 7\\ 11 & 7\\ 12 & 8 \end{array} \] for the newest range not already settled in Round 1.

ADVERSARIAL VERIFICATION

I now try to break the new work.

• Lemma 18.8: the only subtle point is passage from the dyadic increment estimate (eq:dyadic-prime-increment) to a bound for all $x$. This is handled by bounding $\pi(x)$ through the next power of two. Small values $2\le x<16$ are absorbed by enlarging the absolute constant.

• Proposition 18.9: the estimate \[ v_p(n!)\le \frac{2n}{p} \] is valid for every prime $p\ge 2$, since \[ \sum_{a\ge 1}\frac1{p^a}=\frac1{p-1}\le \frac2p. \] For the dyadic intervals $I_j$, the denominator comparison \[ \log(n/2^j)\ge \tfrac12\log n \] is correct because only indices $0\le j\le \lfloor \tfrac12\log_2 n\rfloor$ occur, i.e. $n/2^j\ge \sqrt n$.

• Corollary 18.10: the Round 2 counting inequality applies because every factorial $n!$ is practical. This was part of the original problem context and was also verified computationally for small $n$ in earlier rounds. No new unproved practicality claim is inserted here.

• Interaction with Round 2: there is no conflict with the Round 2 lower bound $h(n!)\gg \log n$; the new bound strictly strengthens it. I am not discarding the Round 2 result, only improving the divisor-count input that fed into it.

• Proposition 18.11: the computation is exact, not heuristic. Minimality of $8$ is verified by one failure run ($H=7$) and one success run ($H=8$). No probabilistic or approximate step occurs.

No contradiction or hidden assumption remains after these checks.

FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

The main new theorem of this round is the unconditional lower bound \[ h(n!) \gg (\log n)^2. \] This is a substantial advance over Round 2, which only had $h(n!)\gg \log n$. Consequently:

• any proof strategy aiming for $h(n!)=O(\log n)$ is now rigorously ruled out;
• any eventual positive result of the form $h(n!)\le (\log n)^C$ must have $C\ge 2$.

In addition, the exact computation has been extended by one step: \[ h(12!)=8. \]

What remains open is the genuine upper-bound problem: does one have \[ h(n!)\le (\log n)^{O(1)} \quad\text{or even}\quad h(n!)<n^{o(1)}? \] Round 3 does not settle that, but it isolates a sharp obstruction: the factorial problem cannot have logarithmic order of growth.

COMPLETION ESTIMATE

COMPLETION: 60%

REFERENCES

• Round 2 output for Problem 18, specifically the counting lemma (Lemma 18.4 and its explicit corollary) and the exact values of $h(n!)$ through $n=11$.
• Standard binomial estimate: $\binom{2m}{m}\le 4^m$.
• Standard integral identity: $\int_1^n \log x\,dx = n\log n-n+1$.
• Exact computations performed in this round for $h(12!)$ via bounded-cardinality subset-sum dynamic programming over the divisor set of $12!$.

Erdős Problem #18: independent continuation

1) OBJECTIVE AND ALL-VERSION AUDIT

2) A PRODUCT INEQUALITY

3) WHAT THIS CONSTRUCTION DOES NOT ACHIEVE

4) INDEPENDENT FINITE VERIFICATION

7) FINAL

8) COMPLETION ESTIMATE