Erdős problem #821 — wave7n report

Access/recomputation date: 2026-07-27 (UTC).

Claim labels used throughout:

• (a) elementary-rigorous: proved below from elementary facts.
• (b) rigorous-modulo-named-theorem: depends on an explicitly named published/preprint theorem.
• (c) plausible/structural-unverified: heuristic or a diagnosis of a method, not a theorem.
• (d) computational-only: an observation or exhaustive finite result reproduced by the checker.

0. Mandatory live-page check

(d, live-page observation.) I fetched both /821 and its /forum/discuss/821 thread through a Bright Data browser, not datacenter curl. The page was last edited 2025-10-01 and was accessed on 2026-07-27.

Verbatim current statement (from the page's /latex/821 endpoint):

Let $g(n)$ count the number of $m$ such that $\phi(m)=n$. Is it true that, for every $\epsilon>0$, there exist infinitely many $n$ such that\[g(n) > n^{1-\epsilon}?\]

(d, live-page observation.) The status is OPEN. It displays “0 claimed proofs for this problem”, “Currently working on this problem: None”, and “Interested in collaborating: None”. Thus none of the mandatory skip conditions applies.

The complete displayed marker block was:

The database block says “Formalised statement? Yes” and links OEIS A014197.

Results listed on the live page

The following are the page's listed results, not inferences from the stale tracker:

1. (b) Pillai proved \(\limsup g(n)=\infty\), and Erdős

[Er35b] proved that some absolute \(c>0\) satisfies \(g(n)>n^c\) infinitely often.

1. (b) The conjecture would follow if, for every \(\epsilon>0\), there

were \(\gg_\epsilon x/\log x\) primes \(p<x\) all of whose prime factors of \(p-1\) were \(<p^\epsilon\).

1. (b) The page gives the current threshold as

\(0.71568\ldots\), based on Lichtman's result that \(P^+(p-1)\leq x^{0.2843\ldots}\) for at least \(x/(\log x)^{O(1)}\) primes \(p\leq x\). It says this improves the preceding Baker–Harman exponent.

1. (b) It says Luca and Pollack investigated the average size of the

associated multiplicity function, and it points to problem #416.

The page's bibliography lists Baker–Harman (1998), Erdős (1935), Lichtman (arXiv:2211.09641), and Luca–Pollack (2011).

Both displayed comments

(d, live-page observation.)

1. Boris Alexeev (2025-09-30) noted that page 3 of Kevin Ford's arXiv

version of The distribution of totients reports Erdős's positive exponent and the then-record \(0.7039\), with Baker–Harman as the cited source. He identified Ford's \(A\) with this page's \(g\), and explicitly said he had not verified that Baker–Harman itself contained the quoted consequence. The comment says the site was subsequently updated.

1. Thomas Bloom (2025-10-01) replied that Lichtman had recently improved

the result and that he would update the page.

The thread footer warns that comments are user responsibility and are not verified. There are no solution or partial-solution claims in them.

1. Primary-source audit and current-state search

(d, literature-search observation.) I searched by the exact problem wording, by the shifted-prime exponent, and forward through primary sources discussing Lichtman's threshold. I found no primary source claiming a proof or falsification of #821 and no later source claiming an improvement to the small largest-prime-factor threshold. This is a reported search miss, not a proof that no such paper exists.

• (b) Erdős's original 1974 source is

Remarks on some problems in number theory, pp. 201–202. It defines \(g(n)\), states the conjectural exponent \(1-\epsilon\), and gives exactly the smooth-\(p-1\) sufficient condition used on the live page.

• (b) The cited 1935 paper

On the normal number of prime factors of \(p-1\) and some related problems concerning Euler's \(\phi\)-function exists in Q. J. Math. 6 (1935), 205–213. Its final construction pigeonholes totients of squarefree products and obtains a fixed positive exponent.

• (b) Baker and Harman's

Shifted primes without large prime factors exists in Acta Arith. 83 (1998), 331–361. Lichtman's introduction explicitly identifies its threshold as \(0.2961\).

• (b) Lichtman's

arXiv:2211.09641, Theorem 1.1, proves that for every \[ \beta>\beta_0:=\frac{15}{32\sqrt e} =0.2843112467402969\ldots \] there is a \(C\) such that \[ \#\{x<p\leq2x:P^+(p-1)\leq x^\beta\} \gg \frac{x}{(\log x)^C}. \] Its Corollary 1.3 states the resulting \(0.7156\) multiplicity bound. The limiting complementary threshold is \[ \alpha_0=1-\beta_0 =0.7156887532597030\ldots . \] Because Theorem 1.1 has the strict condition \(\beta>\beta_0\), the precise direct formulation is “every fixed \(\alpha<\alpha_0\) is admissible”; the printed \(0.7156\) is a safe truncation.

• (b) Ford's

The distribution of totients really does say at the top of page 3 that the then-current exponent was \(0.7039\), so the first comment accurately described that paper's historical statement.

• (b) Luca and Pollack's

2011 paper exists and defines \(F(n)=g(\phi(n))\). It proves normal-order bounds for \(F\) and discusses its average order. I do not silently broaden this to an average-order theorem for \(g(v)\) over all integers \(v\).

• (b) Runbo Li's 2025 primary preprint

arXiv:2508.18285 improves a large-prime-factor result. Its appendix still lists Lichtman's \(0.2844\) as the record on the small-factor side and explicitly says its sieve inputs do not improve that record without distribution for multilinear moduli beyond \(x^{17/32}\).

• (b) For comparison with the finite algorithm below, Alekseyev's

2016 Journal of Integer Sequences paper gives a general exact algorithm for inverses of multiplicative functions. The checker here was written independently from the prime-power characterization.

2. A clean reduction showing exactly where the standard route stalls

Write \(P^+(t)\) for the largest prime factor of \(t\).

Fixed-cardinality collision lemma

Lemma (a, using only the standard Chebyshev bound \(\pi(y)\ll y/\log y\)). Fix \(0<\beta<1\). Suppose that for arbitrarily large \(X\) there are

primes \(p\leq X\) with \(P^+(p-1)\leq X^\beta\), where \(C\) is fixed. Then, for every fixed \(\delta>0\), there are infinitely many \(N\) with

Proof. Put \(y=X^\beta\) and \(r=\lfloor y\rfloor\). For every \(r\)-element subset \(S\) of the \(k\) primes, set

The integer \(M_S\) is squarefree, so \(\phi(M_S)=N_S\). There are \(\binom{k}{r}\) subsets.

Every \(N_S\) is \(y\)-smooth. For each prime \(q\leq y\),

Consequently the number \(D\) of possible products \(N_S\) is bounded by

Chebyshev's bound and \(r\sim y\) give

Also

and hence

Pigeonholing the subsets by \(N_S\), one value \(N\leq X^r\) has at least

distinct preimages \(M_S\). For large \(X\), this is greater than \(N^{1-\beta-\delta}\). These \(N\) are unbounded: the displayed multiplicities tend to infinity, whereas the inverse set of any fixed \(N\) is finite by the characterization in §3. ∎

(b) Applying the lemma to Lichtman's theorem proves that every fixed

occurs infinitely often as a lower exponent: \(g(N)>N^\alpha\). This reconstructs the complementarity between the two exponents without treating the page's decimal ellipsis as an attained endpoint.

Exact remaining analytic input for this route (c as a diagnosis, not an equivalence). To settle #821 by this collision mechanism it would suffice to prove, for every fixed \(\eta>0\),

along arbitrarily large \(x\) (the live page states the stronger expected \(\gg_\eta x/\log x\) version). Presently the named theorem only reaches \(\eta>\beta_0\). The exact missing lemma is therefore a near-full-density lower bound for shifted primes with arbitrarily small smoothness exponent. Other constructions could conceivably bypass it, so it is not claimed necessary for #821 itself.

3. Exact inverse-totient computation

Completeness of the finite search

Proposition (a). If \(\phi(m)=n\) and \(p^a\Vert m\), then

In particular \(p-1\mid n\), so every possible prime divisor of \(m\) is of the form \(p=d+1\) for a divisor \(d\mid n\). Conversely, selecting at most one power \(p^a\) for every such prime and requiring

is sufficient, by multiplicativity of \(\phi\). The choice \(p=2,a=1\) has contribution \(1\), and must be kept distinct from omitting \(2\). This is a finite, exhaustive characterization; it does not impose an unproved upper bound on \(m\).

The first checker engine processes the candidate primes one at a time. Its state states[t] is the number of ways to obtain contribution product \(t\), and it retains only \(t\mid n\). The core is:

def inverse_count_small(n, prime, spf):
    states = {1: 1}
    for d in divisors_from_spf(n, spf):
        p = d + 1
        if not prime[p]:
            continue
        contributions = []
        contribution = d
        while n % contribution == 0:
            contributions.append(contribution)
            contribution *= p
        old = tuple(states.items())
        updated = states.copy()              # omit p
        for product, ways in old:
            for contribution in contributions:  # select one p^a
                new_product = product * contribution
                if new_product <= n and n % new_product == 0:
                    updated[new_product] = (
                        updated.get(new_product, 0) + ways
                    )
        states = updated
    return states.get(n, 0)

Exhaustive range theorem

(d; completeness is proposition (a).) The checker evaluated every \(1\leq n\leq10^6\). It proves the finite statement

with \(n=967680\) the unique maximizer in that interval.

Selected prefix maxima are:

All strict records \((n,g(n))\) through \(10^6\) are:

(1,2), (2,3), (4,4), (8,5), (12,6), (24,10), (48,11),
(72,17), (144,21), (240,31), (432,34), (480,37), (576,38),
(720,49), (1152,54), (1440,72), (2880,98), (4320,126),
(5760,129), (8640,176), (11520,178), (17280,247),
(25920,276), (30240,281), (34560,331), (40320,359),
(51840,399), (60480,441), (69120,454), (80640,525),
(103680,558), (120960,692), (161280,718), (181440,734),
(207360,764), (241920,1023), (362880,1138), (483840,1485),
(725760,1755), (967680,2008)

(d, independent arithmetic check.) The script also materialized all 2,008 inverse values at \(n=967680\), found them distinct, and recomputed \(\phi(m)\) by separate trial division for every one. Their range is

Only after the local computation, I compared the record positions and values with OEIS A097942 and OEIS A131934; they agree through this range. The OEIS data was not an input to the scan.

A larger exact value with two counting engines

Let

(d, with Pocklington's theorem as the named certificate theorem.) The checker obtains the exact value

There are 2,002 divisors \(d\mid N_0\), and exactly 377 of their successors \(d+1\) are prime. Candidate classification is self-certifying:

• failure of a strong probable-prime test proves compositeness;
• a passing candidate is accepted only after, for every prime \(q\mid d\),

the code finds a Pocklington witness \(a\) with \[ a^d\equiv1\pmod{d+1},\qquad \gcd(a^{d/q}-1,d+1)=1. \] Since the fully factored part \(d=(d+1)-1\) exceeds \(\sqrt{d+1}\), Pocklington proves primality.

The grouped-product DP gives \(26\,819\,695\). A second engine recursively chooses the smallest prime divisor of a prospective \(m\), enforces strictly increasing later primes, and independently gives the same integer. It used 144,992 cached states. Thus no list of 26 million preimages and no probabilistic primality assumption is hidden in the claim.

4. Reproduction

The standalone checker is runs/erdos821_wave7n_reverify.py. It uses only the Python standard library.

python runs/erdos821_wave7n_reverify.py

Observed output:

Building exact sieve through 1,000,001...
Scanning every n <= 1,000,000...
Verified range theorem: max_{1<=n<=1,000,000} g(n)=2008, uniquely at n=967680.
Strict records:
((1, 2), (2, 3), (4, 4), (8, 5), (12, 6), (24, 10), (48, 11), (72, 17), (144, 21), (240, 31), (432, 34), (480, 37), (576, 38), (720, 49), (1152, 54), (1440, 72), (2880, 98), (4320, 126), (5760, 129), (8640, 176), (11520, 178), (17280, 247), (25920, 276), (30240, 281), (34560, 331), (40320, 359), (51840, 399), (60480, 441), (69120, 454), (80640, 525), (103680, 558), (120960, 692), (161280, 718), (181440, 734), (207360, 764), (241920, 1023), (362880, 1138), (483840, 1485), (725760, 1755), (967680, 2008))
Materializing and directly checking the 2,008 record inverses...
All materialized m are distinct and pass direct phi(m)=967680; min(m)=970289, max(m)=5225220.
Classifying d+1 for all d | 17,414,258,688,000,000 with certificates...
Verified large target: g(17414258688000000)=26,819,695; log(g)/log(n)=0.457391619401.
The two exact counts agree; recursive cache statistics: CacheInfo(hits=2693032, misses=144992, maxsize=None, currsize=144992).
ALL CHECKS PASSED

Runtime was 13.9 seconds on this VM. SHA-256 of the checker:

a534c536021ed1f60865da0c0cd3ff95d40a2f6352c423670dc92d63df5702aa

5. What remains and why the computation cannot close it

(a) Any finite table, including the exact \(10^6\) range theorem and the exact \(N_0\) value, says nothing uniform about infinitely many \(n\). It therefore cannot establish the quantifiers in #821.

(c, precise method wall.) The fixed-cardinality collision proof loses exactly the smoothness exponent \(\beta\): a supply of \(X^{1-o(1)}\) primes with \(P^+(p-1)\leq X^\beta\) produces exponent \(1-\beta-o(1)\). Current unconditional distribution technology stops at \(\beta_0=15/(32\sqrt e)\). The missing analytic theorem is the same near-full-count statement with every \(\beta>0\), not a larger finite inverse-totient search.

(d, cost estimate only; not run.) The observed scan cost is about 14 core-seconds per \(10^6\) targets. A direct extension to \(10^8\) would be roughly \(0.4\)–\(1\) core-hour and the present Python SPF list would require several GB; packed arrays would reduce memory below about 1 GB. At a representative \(0.10\) USD/core-hour this is well below one dollar, but it would still prove only another finite theorem and would not address the missing shifted-prime estimate. No such heavier run was needed for the results above.

PARTIAL: proved an exact exhaustive range theorem through \(10^6\), certified \(g(2^{21}3^{12}5^6)=26{,}819{,}695\) by two exact counts, and isolated the standard route's missing smooth-shifted-prime theorem; #821 remains open.