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
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:
| Marker | Displayed value |
|---|---|
| Likes this problem | None |
| Interested in collaborating | None |
| Currently working on this problem | None |
| This problem looks difficult | None |
| This problem looks tractable | None |
| The results on this problem could be formalisable | None |
| I am working on formalising the results on this problem | None |
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.
2. (b) The conjecture would follow if, for every \(\epsilon>0\), there
were \(\gg_\epsilon x/\log x\) primes \(p factors of \(p-1\) were \( 3. (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. 4. (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). (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. 2. 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. (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. 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. [*On the normal number of prime factors of \(p-1\) and some related problems concerning Euler's \(\phi\)-function*](https://users.renyi.hu/~p_erdos/1935-08.pdf) exists in Q. J. Math. 6 (1935), 205–213. Its final construction pigeonholes totients of squarefree products and obtains a fixed positive exponent. Shifted primes without large prime factors exists in Acta Arith. 83 (1998), 331–361. Lichtman's introduction explicitly identifies its threshold as \(0.2961\). 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 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. 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. 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\). 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}\). 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. Write \(P^+(t)\) for the largest prime factor of \(t\). **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\), \(\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. 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 product \(t\), and it retains only \(t\mid n\). The core is: (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: | \(B\) | \(\max_{n\leq B}g(n)\) | first/unique endpoint record | |---:|---:|---:| | \(10\) | 5 | 8 | | \(100\) | 17 | 72 | | \(1{,}000\) | 49 | 720 | | \(10{,}000\) | 176 | 8640 | | \(100{,}000\) | 525 | 80640 | | \(1{,}000{,}000\) | 2008 | 967680 | All strict records \((n,g(n))\) through \(10^6\) are: (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. 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: 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. The standalone checker is It uses only the Python standard library. Observed output: Runtime was 13.9 seconds on this VM. SHA-256 of the checker: (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.Both displayed comments
1. Primary-source audit and current-state search
2. A clean reduction showing exactly where the standard route stalls
Fixed-cardinality collision lemma
3. Exact inverse-totient computation
Completeness of the finite search
states[t] is the number of ways to obtain contributiondef 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
(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)
A larger exact value with two counting engines
4. Reproduction
runs/erdos821_wave7n_reverify.py.python runs/erdos821_wave7n_reverify.py
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
a534c536021ed1f60865da0c0cd3ff95d40a2f6352c423670dc92d63df5702aa
5. What remains and why the computation cannot close it