Erdoes #1004 - working report - Erdős Problem a Day

Erdős problem #1004 — wave 7z

Access and computation date: 2026-07-28 UTC.

Claim labels

(a) elementary-rigorous: proved here from definitions or checked by exact finite arithmetic.
(b) rigorous-modulo-named-theorem: the deduction is rigorous assuming the cited theorem exactly as published.
(c) plausible/structural-unverified: a heuristic, an unaudited preprint claim, or a structural interpretation not promoted to a theorem here.
(d) computational-only: exhaustive for the stated finite range, but with no asymptotic implication.

No claim below that is labelled (c) or (d) is used to declare the original problem solved.

0. Mandatory live-page check

I used the Bright Data browser route, not datacenter curl, to load the live

problem page, its raw-LaTeX view, all seven

comments, and the proof-claim page.

(a) Live status. The page said OPEN, “0 claimed proofs for this problem,” and

“Currently working on this problem: None.” The separate proof-claim page said “No

proof claims have been submitted yet.” Thus the requested stop condition did not

fire. The page said it was last edited 12 April 2026.

(a) Verbatim statement from the page's raw-LaTeX view:

> Let $c>0$. If $x$ is sufficiently large then does there exist $n\leq x$ such that the values of $\phi(n+k)$ are all distinct for $1\leq k\leq (\log x)^c$, where $\phi$ is the Euler totient function?

(a) Verbatim listed known result:

> Erd\H{o}s, Pomerance, and S\'{a}rk\"{o}zy \cite{EPS87} proved that if $\phi(n+k)$ are all distinct for $1\leq k\leq K$ then\[K \leq \frac{n}{\exp(c(\log n)^{1/3})}\]for some constant $c>0$.

(a) Other page markers.

Likes this problem: Alfaiz.
Interested in collaborating: None.
Currently working on this problem: None.
This problem looks difficult: None.
This problem looks tractable: None.
Results could be formalisable: None.
Working on formalising the results: None.
The page points to problem #945 for the divisor-function analogue.

(a) All seven comments, read rather than inferred from the count.

1. On 12 April, onetwothreefour corrected the spelling of Pomerance; the page says it was updated.

2. On 28 April, Svyable proposed a proof for every fixed exponent using an asserted uniform estimate $R_h(X)\ll_{A,B}X/(\log X)^A$.

3. Przemek Chojecki asked for a reference and said that asserted estimate did not look standard.

4. Nat Sothanaphan reported that a standard check likewise did not accept the estimate.

5. Svyable then agreed that the arbitrary-power estimate was false as stated and identified the $X/(\log X)^2$ structured part as the obstruction.

6. On 29 April, aditya linked a five-page note proving the partial result

$L\log(2L)=o((\log x)^2)$, hence every fixed exponent $c<2$, for almost all starts.

7. On 30 April, Nat Sothanaphan reported no issue in that note and thought its result implicit in Pollack–Pomerance–Treviño.

(a) Page-warning respected. The page explicitly says comments are not verified for

correctness. I therefore checked the linked note's cited inputs in the primary paper

before using them.

1. Primary-source search and what was actually verified

1.1 Original source and the page's historical bound

(a) Source verification. The page's [Er85e] bibliography resolves to Paul Erdős,

“Some problems and results in number theory,” *Number Theory and Combinatorics,

Japan 1984* (1985), 65–87, MR 827779. The

author-archive scan, p. 67, contains

the distinct-consecutive-totient question and announces the upper bound

\(k_n

(a) Citation mismatch found honestly. The live page's raw bibliography identifies

[EPS87] as Erdős–Pomerance–Sárközy, “On locally repeated values of certain

arithmetic functions. III,” Proc. Amer. Math. Soc. 101 (1987), 1–7,

DOI 10.1090/S0002-9939-1987-0897061-6.

The retrieved scan exists, but a

full-text read did not locate the displayed block-length theorem in it; that paper's

totient remark instead points back to part II for a unit-shift count. The original

Erdős source does announce the bound. Per the task instruction, I retain the live

page's listed result as ground truth, but I do not claim that I independently

located it in the paper to which the page currently links.

1.2 Shifted equal-totient literature

(a) GHP family verified. Graham, Holt, and Pomerance,

“On the solutions to $\varphi(n)=\varphi(n+k)$,”

author PDF, Theorem 1, gives the

following structured family. If

$\operatorname{rad}(j)=\operatorname{rad}(j+h)$, $g=(j,j+h)$, and

\[ A r+1,\quad B r+1,\qquad A=\frac{j+h}{g},\quad B=\frac jg \]

are suitable primes, then

\[ m=j(Ar+1),\qquad m+h=(j+h)(Br+1) \]

satisfy $\varphi(m)=\varphi(m+h)$. This paper is S. W. Graham, J. J. Holt,

and C. Pomerance, Number Theory in Progress, vol. 2 (1999), 867–882,

DOI 10.1515/9783110285581.867.

(b) Uniform decomposition verified in the cited primary paper. Let

\[ P(X;h)=\#\{m\le X:\varphi(m)=\varphi(m+h)\}=P_0(X;h)+P_1(X;h), \]

where $P_0$ is the GHP family and $P_1$ its complement. Pollack,

Pomerance, and Treviño, “Sets of monotonicity for Euler's totient function,”

author PDF,

Ramanujan J. 30 (2013), 379–398,

DOI 10.1007/s11139-012-9386-6,

states:

Theorem 3.1:

\[ P_1(X;h)

uniformly for $h\le \exp((\log X)^{1/3})$.

Theorem 3.3: for every $\epsilon(X)\to0$ with

$X^{\epsilon(X)}\to\infty$, uniformly for even

$2\le h\le X^{\epsilon(X)}$,

\[ P_0(X;h)\le (16C_2+o(1))\,c(h)\frac{X}{(\log X)^2}. \]

These are the two inputs used in the April note, and they really do have the

uniformity needed for polylogarithmic $h$.

(c) Post-page-edit preprint. Eric Li's 36-page preprint

arXiv:2606.23681, submitted 22 June 2026,

claims substantially stronger off-diagonal estimates and arbitrary fixed

logarithmic saving uniformly for odd polylogarithmic shifts (Corollary 1.3).

Its Theorems 1.1 and 1.4 still retain the same GHP diagonal for even shifts.

I verified that the preprint exists and that it states these results, but I did not

audit its full proof and do not use it below. It does not by itself settle #1004.

(a) Search miss reported. Exact-title, exact-equation, arXiv, author-page, and

journal searches found the sources above but no primary paper explicitly settling

the pairwise-distinct block problem. This is a report of the search performed, not

a claim that no uncatalogued result exists.

2. An endpoint positive-proportion theorem

(b) This strengthens the April comment in one narrow but genuine direction. The comment

gets almost all starts when $L\log L=o((\log x)^2)$. Keeping constants gives some

fixed multiple of $(\log x)^2/\log\log x$, at the cost of replacing “almost all” by

a positive proportion.

2.1 An explicit average bound for the structured constants

For even $h$, write the PPT constant as

\[ c(h)= \sum_{\substack{j\ge1\\ \operatorname{rad}(j)=\operatorname{rad}(j+h)}} \frac{(j,j+h)}{j(j+h)} \prod_{\substack{p>2\\p\mid jh(j+h)/(j,j+h)^3}}\frac{p-1}{p-2}, \]

and put $c(h)=0$ for odd $h$.

Lemma 1 (a). For every $L\ge3$,

\[ \sum_{h\le L}c(h)<3{,}000{,}000\log L. \]

Also,

\[ \sum_{h\le L}c(h)\ge \frac14 H_{\lfloor L/2\rfloor}. \]

Thus the order $\log L$ cannot be improved.

Proof (a). Define

\[ F(t)=\prod_{\substack{p\mid t\\p>2}}\frac{p-1}{p-2}. \]

For a term of $c(h)$, put

\[ g=(j,j+h),\qquad j=ga,\qquad j+h=gb. \]

Then $(a,b)=1$, $h=g(b-a)$, and

\[ \operatorname{rad}(j)=\operatorname{rad}(j+h) \quad\Longleftrightarrow\quad \operatorname{rad}(ab)\mid g. \]

Moreover,

\[ \frac{jh(j+h)}{g^3}=ab(b-a),\qquad \frac{g}{j(j+h)}=\frac1{gab}. \]

Consequently

\[ \sum_{h\le L}c(h) =\sum_{\substack{aFor $q=\operatorname{rad}(ab)$,

\[ \sum_{\substack{g\le Y\\q\mid g}}\frac1g =\frac1q H_{\lfloor Y/q\rfloor} \le \frac{1+\log L}{q} \le \frac{2\log L}{q}. \]

For $p\ge5$,

\[ \frac{p-1}{p-2}\le p^{1/4}, \]

because

$\log((p-1)/(p-2))\le1/(p-2)\le(\log p)/4$; the last inequality holds

at $p=5$, and $p\mapsto(p-2)\log p$ is increasing thereafter. The $p=3$

factor is $2$, so $F(t)\le2t^{1/4}$. Since \(b-a \[ \frac{F(ab(b-a))}{ab\operatorname{rad}(ab)} \le \frac{2}{a^{3/4}\operatorname{rad}(a)\, b^{1/2}\operatorname{rad}(b)}. \]

For $s>0$, set

\[ S_s=\sum_{n\ge1}\frac{n^{-s}}{\operatorname{rad}(n)} =\prod_p\left(1+\frac{p^{-1-s}}{1-p^{-s}}\right). \]

Using $\log(1+u)\le u$ and an integral tail,

\[ \log S_s \le \frac{1}{1-2^{-s}} \left(2^{-1-s}+\frac{2^{-s}}s\right). \]

At $s=3/4$, the right side is $<11/2$, so $S_{3/4}<245$.

At $s=1/2$, it is $<8$, so $S_{1/2}<3000$. Therefore

\[ \sum_{h\le L}c(h) \le4S_{3/4}S_{1/2}\log L <2{,}940{,}000\log L <3{,}000{,}000\log L. \]

For the lower bound, take $j=h$ for every even $h$. Then

$\operatorname{rad}(h)=\operatorname{rad}(2h)$; the Euler product is empty,

and this single term contributes $1/(2h)$. Hence

\[ \sum_{h\le L}c(h) \ge\sum_{m\le L/2}\frac1{4m} =\frac14H_{\lfloor L/2\rfloor}. \qquad\square \]

2.2 The positive-proportion endpoint

Theorem 2 (b). Let logarithms be natural and set

\[ \delta=10^{-10},\qquad L=\left\lfloor\delta\,\frac{(\log x)^2}{\log\log x}\right\rfloor. \]

For all sufficiently large $x$, at least $x/2$ integers $n\le x$ have

\[ \varphi(n+1),\ldots,\varphi(n+L) \]

pairwise distinct.

Proof (b). Call $n\le x$ bad if a collision occurs. If

$\varphi(n+i)=\varphi(n+j)$, put $h=j-i$ and $m=n+i$. Each fixed

collision $(m,m+h)$ spoils at most $L-h$ starts, so, since $x+L\le2x$

for large $x$,

\[ B(x,L)\le\sum_{hUse $\epsilon(X)=1/\sqrt{\log X}$ in PPT Theorem 3.3. Its uniform range

contains every \(h

For even $h$, since $C_2<2$, for all sufficiently large $x$,

\[ P_0(2x;h)\le66\,c(h)\frac{x}{(\log x)^2}. \]

Lemma 1 gives

\[ \begin{aligned} B_0(x,L) &\le 66\frac{xL}{(\log x)^2}\sum_{hFor large $x$, $\log L\le2\log\log x$, and therefore

\[ B_0(x,L)<396{,}000{,}000\,\delta x=0.0396x. \]

PPT Theorem 3.1 applies to all \(h \[ B_1(x,L) < \frac{xL^2}{\exp((\log(2x))^{1/3})} =o(x). \]

In particular \(B_1(x,L)

\(B(x,L)<0.29x

(b) What is new relative to the April comment. The linked note proves “almost

all” for $L\log L=o((\log x)^2)$, which requires

\[ L=o\!\left(\frac{(\log x)^2}{\log\log x}\right). \]

Theorem 2 permits a fixed positive multiple of this endpoint, but proves only a

positive proportion. It still falls short of $L=(\log x)^2$, so it does not settle

the case $c=2$.

3. Exact reduction and the remaining wall

Reduction (b). Fix any $C>0$ and let $L=\lfloor(\log x)^C\rfloor$.

PPT Theorem 3.1 implies that the number of starts spoiled by a non-GHP collision is

\[ \sum_{hThus, modulo a density-$o(1)$ exceptional set, the whole problem is an avoidance

problem for the explicit even-shift GHP family.

For every structured edge $(m,m+h)$, define its interval of spoiled starts

\[ I_{m,h}=[m+h-L,m-1]\cap[1,x]. \]

Let

\[ \mathcal U_L(x)= \bigcup_{\substack{1\le hExact missing lemma (b). A sufficient statement that would finish #1004 is:

for every fixed $C>0$, with $L=(\log x)^C$,

\[ \bigl|[1,x]\setminus\mathcal U_L(x)\bigr|\gg_C x. \]

The $o(x)$ off-diagonal starts could then be removed while leaving a valid start.

A weaker lower bound larger than the known off-diagonal error would also suffice.

First-moment wall (a). The elementary term $c(h)\ge1/(2h)$ for even $h$

gives

\[ \sum_{hHence the $L\log L$ loss in the April argument is intrinsic to summing individual

edge intervals. Better averaging of $c(h)$ cannot cross the

$(\log x)^2/\log\log x$ scale.

Structural diagnosis (c). Bateman–Horn predicts that many of these structured

prime-pair families really have order $x/(\log x)^2$, so a uniform improvement of

each pair count is not the expected escape route. What is missing is a coverage or

overlap theorem for the union $\mathcal U_L(x)$, or an explicit construction of a

start avoiding all its linear-prime families. Neither PPT nor the June 2026 preprint

provides that lemma.

4. Exact computation through $10^9$

Define the problem-aligned finite quantity

\[ D(n)=\max\{K:\varphi(n+1),\ldots,\varphi(n+K) \text{ are pairwise distinct}\}, \qquad A(X)=\max_{1\le n\le X}D(n). \]

Unlike a prefix-only statistic, arguments $n+k$ are allowed to exceed $X$, just as

in the live problem.

Exact table (d).

| $X$ | $A(X)$ | attaining $n$ | distinct argument interval |

|---:|---:|---:|---:|

| $10$ | 5 | 10 | $[11,15]$ |

| $10^2$ | 10 | 45 | $[46,55]$ |

| $10^3$ | 29 | 740 | $[741,769]$ |

| $10^4$ | 57 | 8,826 | $[8,827,8,883]$ |

| $10^5$ | 111 | 73,317 | $[73,318,73,428]$ |

| $10^6$ | 194 | 900,978 | $[900,979,901,172]$ |

| $10^7$ | 321 | 9,491,694 | $[9,491,695,9,492,015]$ |

| $10^8$ | 489 | 72,730,446 | $[72,730,447,72,730,935]$ |

| $10^9$ | 691 | 427,197,852 | [427,197,853,427,198,543] |

(d) Exhaustiveness. The verifier computes every totient through

$10^9+20{,}000$ by a linear Euler sieve. For each $a=n+1$, a two-pointer

window is extended until the next totient repeats; that endpoint is exactly $D(n)$.

The right pointer never moves backwards, so all $10^9$ starts are checked in linear

scan time. At termination it was $1{,}000{,}000{,}023$, strictly below the allocated

$1{,}000{,}020{,}000$, proving that the margin truncated no start.

The core scan in the standalone verifier is:

for (uint32_t a = 2; a <= X + 1; ++a) {
    if (r < a - 1) r = a - 1;
    while (r < N && !present[phi[r + 1]]) {
        ++r;
        present[phi[r]] = 1;
    }
    const uint32_t len = r - a + 1;  // exactly D(a-1)
    if (len > best) {
        best = len;
        best_a = a;
        best_b = r;
    }
    if (a <= r) present[phi[a]] = 0;
}

(d) Independent arithmetic check of the record witness. A separate Python

trial-division implementation factored and recomputed $\varphi$ for all 693

integers from one before to one after the record block. The 691 interior values are

distinct. Packed as little-endian unsigned 64-bit integers, their SHA-256 is

162209d09f9bcc37a2ca0817328ca2be47a88d97891e1024e03af16de5141dbc

(a) Both one-step extensions fail by certified GHP collisions. On the left,

\[ \begin{aligned} 427197852&=2^2\,3^2\,47\cdot252481,\\ 427198416&=2^4\,3\,47\cdot189361,\\ \varphi(427197852)&=\varphi(427198416)=139368960. \end{aligned} \]

This has $h=564,j=1692,g=564,r=63120$, with

$\operatorname{rad}(1692)=\operatorname{rad}(2256)=282$,

\[ 4r+1=252481,\qquad3r+1=189361 \]

both prime.

On the right,

\[ \begin{aligned} 427198532&=2^2\cdot106799633,\\ 427198544&=2^4\cdot26699909,\\ \varphi(427198532)&=\varphi(427198544)=213599264. \end{aligned} \]

This has $h=12,j=4,g=4,r=26699908$, with

\[ 4r+1=106799633,\qquad r+1=26699909 \]

both prime. The standalone script trial-divides the four asserted primes and checks

the complete GHP identities.

(d) Finite relevance only. At $x=10^9$,

\[ \frac{\log 691}{\log\log(10^9)}=2.1569071098411325\ldots. \]

Thus this one finite witness handles every $c$ up to that displayed value at this

particular $x$. It supplies no “for all sufficiently large $x$” statement.

5. Reproduction

The complete standalone verifier is

runs/erdos1004_wave7z_reverify.py (326 lines; SHA-256

a1e0a07b661542f3ef26b36273fb62956c992b1570374c1049a791026d31e66e).

It writes only into an automatically removed temporary directory.

Run:

python runs/erdos1004_wave7z_reverify.py

(d) Recorded independent run. It exited successfully in 71.96 wall seconds,

used 5,085,136 KiB maximum RSS, reproduced every row in the table, recomputed the

691-value witness hash by trial factorization, checked both boundary certificates,

and ended:

PASS: all requested checks succeeded in 71.91s

For a lower-memory smoke test:

python runs/erdos1004_wave7z_reverify.py --limit 100000000

6. Conclusion

(b) The original arbitrary-$c$ question remains open. The verified analytic

progress is an explicit positive-proportion result at

$10^{-10}(\log x)^2/\log\log x$, and the verified exact reduction isolates the

even-shift GHP coverage lemma as the remaining obstacle after an $o(x)$

off-diagonal set. (d) The exact finite computation gives $A(10^9)=691$, with

a fully factor-checked witness and boundary collisions.

PARTIAL: proved a positive-proportion $L=10^{-10}(\log x)^2/\log\log x$ theorem modulo PPT, reduced all polylogarithmic lengths to GHP-diagonal coverage, and exactly certified $A(10^9)=691$; the arbitrary-$c$ problem remains open.

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger