← All problems

Erdős Problem #1004 — Let c>0c>0. If xx is sufficiently large then does there exist n≤xn\leq x such that the values of ϕ(n+k)\phi(n+k) are all distinct for 1≤k≤(log⁡x)c1\leq k\leq (\log x)^c, where ϕ\phi is the Euler totient function?

44 years old · traced to

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

References

Progress summary

Refreshed
Open · progress reported

An unverified submission claims the conjecture is proved for exponents below two, while the full question remains open.

Erdős Problem 1004 asks whether, for every fixed c>0c>0, sufficiently large xx contains a consecutive block of totients of length at least (log⁡x)c(\log x)^c that are all different. The formal catalogue records the main assertion as open.

Known results

Erdős, Pomerance, and Sárközy (1987) proved that every sufficiently large distinct-totient run beginning near nn has length at most n/exp⁡(c(log⁡n)1/3)n/\exp(c(\log n)^{1/3}) for some c>0c>0.

Community submission (unverified), August 23, 2026

A submitted argument claims an unconditional lower bound Fϕ(x)≫(log⁡x)2/log⁡log⁡xF_\phi(x)\gg(\log x)^2/\log\log x, based on collision estimates, and therefore claims the conjecture for every fixed c<2c<2. It explicitly does not reach c=2c=2 or settle the full conjecture.

Current status (as of August 2026): The full conjecture remains open, while an unverified community submission claims progress covering every fixed c<2c<2.

Sources

Solutions 1

This solution needs a summarySee full solutionHide full solution

Partial progress on Erdős Problem 1004

This records partial progress only. It does not solve Erdős Problem 1004.

Define

Fϕ(x)=max⁡{L:∃n≤x such that ϕ(n+1),…,ϕ(n+L) are pairwise distinct}.F_\phi(x)=\max\left\{L:\exists n\le x\text{ such that }\phi(n+1),\ldots,\phi(n+L)\text{ are pairwise distinct}\right\}.

The problem asks whether, for every fixed c>0c>0,

Fϕ(x)≥(log⁡x)cF_\phi(x)\ge(\log x)^c

for all sufficiently large xx.

1. Unconditional lower bound

For a block of length LL, define its collision count by

CL(n)=∣{(i,j):1≤i<j≤L, ϕ(n+i)=ϕ(n+j)}∣.C_L(n)=\left|\left\{(i,j):1\le i<j\le L,\ \phi(n+i)=\phi(n+j)\right\}\right|.

The block is good exactly when CL(n)=0C_L(n)=0.

For a shift hh, write

P(X;h)=∣{m≤X:ϕ(m)=ϕ(m+h)}∣.P(X;h)=\left|\left\{m\le X:\phi(m)=\phi(m+h)\right\}\right|.

The Graham–Holt–Pomerance parametrization and the Pollack–Pomerance–Treviño decomposition split these shifted collisions into a structured same-support part P0(X;h)P_0(X;h) and an exceptional part P1(X;h)P_1(X;h). The published estimates give, uniformly in the polylogarithmic ranges needed here,

P1(X;h)≪Xexp⁡ ⁣(−(log⁡X)1/3),P_1(X;h)\ll X\exp\!\left(-(\log X)^{1/3}\right),

while the structured part is bounded in terms of a coefficient c(h)c(h) by

P0(X;h)≪c(h)X(log⁡X)2.P_0(X;h)\ll c(h)\frac{X}{(\log X)^2}.

Let

γ(n)=rad⁡(n)\gamma(n)=\operatorname{rad}(n)

and

ρ(n)=∏p∣n\p>2p−1p−2.\rho(n)=\prod_{\substack{p\mid n\p>2}}\frac{p-1}{p-2}.

An exact reparametrization of the structured coefficient gives

∑h≤Hc(h)=Kϕlog⁡H+O(1),\sum_{h\le H}c(h)=K_\phi\log H+O(1),

where

Kϕ=∑a<b(a,b)=1ρ(ab(b−a))ab γ(ab),0<Kϕ<∞.K_\phi=\sum_{\substack{a<b\\(a,b)=1}}\frac{\rho(ab(b-a))}{ab\,\gamma(ab)},\qquad 0<K_\phi<\infty.

Consequently,

∑h<L(L−h)c(h)=KϕLlog⁡L+O(L).\sum_{h<L}(L-h)c(h)=K_\phi L\log L+O(L).

A union bound over all possible collision shifts then gives

∣{n≤x:CL(n)>0}∣≪xLlog⁡L(log⁡x)2+o(x).\left|\left\{n\le x:C_L(n)>0\right\}\right|\ll x\frac{L\log L}{(\log x)^2}+o(x).

Therefore, if

Llog⁡(2L)=o((log⁡x)2),L\log(2L)=o((\log x)^2),

then almost all starts n≤xn\le x give good blocks.

In particular,

Fϕ(x)≫(log⁡x)2log⁡log⁡x.F_\phi(x)\gg\frac{(\log x)^2}{\log\log x}.

Hence Erdős Problem 1004 has an affirmative answer for every fixed exponent c<2c<2. This argument does not reach c=2c=2.

2. Structure of the same-support collisions

The structured Graham–Holt–Pomerance family can be written as follows. Let

j=ga,j+h=gb,j=ga,\qquad j+h=gb,

where

a<b,(a,b)=1,h=g(b−a),γ(ab)∣g.a<b,\qquad (a,b)=1,\qquad h=g(b-a),\qquad \gamma(ab)\mid g.

If

ar+1andbr+1ar+1\qquad\text{and}\qquad br+1

are prime, then

m=ga(br+1),m+h=gb(ar+1)m=ga(br+1),\qquad m+h=gb(ar+1)

satisfy

ϕ(m)=ϕ(m+h).\phi(m)=\phi(m+h).

This parametrization is also the source of the Llog⁡LL\log L factor in the first-moment estimate above.

Under the usual prime-pair asymptotic, the full same-support process is heuristically expected to have block intensity of order

2C2KϕLlog⁡L(log⁡x)2,2C_2K_\phi\frac{L\log L}{(\log x)^2},

where

C2=∏p>2p(p−2)(p−1)2C_2=\prod_{p>2}\frac{p(p-2)}{(p-1)^2}

is the twin-prime constant.

This intensity statement is heuristic. The unconditional argument above uses only upper bounds.

3. The Moser subfamily

A particularly simple subfamily is obtained as follows. Suppose hh is even, pp and 2p−12p-1 are prime, and

gcd⁡(h,p(2p−1))=1.\gcd(h,p(2p-1))=1.

Then

ϕ ⁣(h(2p−1))=ϕ(2hp).\phi\!\left(h(2p-1)\right)=\phi(2hp).

The coprimality condition is essential.

For a block of length LL, this collision rules out every start in the interval

Ih,p(L)=[2hp−L, 2hp−h−1].I_{h,p}^{(L)}=[2hp-L,\,2hp-h-1].

Let YM(n)Y_M(n) count the corrected Moser intervals containing the start nn.

For bulk starts x/2<n≤xx/2<n\le x, the corresponding expected-intensity model is

λM(n)=(C22+o(1))Llog⁡L(log⁡x)2,\lambda_M(n)=\left(\frac{C_2}{2}+o(1)\right)\frac{L\log L}{(\log x)^2},

uniformly in the polylogarithmic ranges considered below.

4. Conditional Moser lower tail

A precise growing-rank signed Hardy–Littlewood/Bateman–Horn hypothesis, denoted BWHLM\mathrm{BWHL}_M, has been formulated for the Moser process. It controls the alternating aggregate error in the factorial-moment expansion through rank comparable to λM\lambda_M.

This assumption is substantially stronger than ordinary fixed-rank Bateman–Horn.

Under BWHLM\mathrm{BWHL}_M,

∣{n∈(x/2,x]:YM(n)=0}∣≥14∑x/2<n≤xe−λM(n).\left|\left\{n\in(x/2,x]:Y_M(n)=0\right\}\right|\ge\frac{1}{4}\sum_{x/2<n\le x}e^{-\lambda_M(n)}.

Consequently, if

L=(log⁡x)c,2<c<3,L=(\log x)^c,\qquad 2<c<3,

then

∣{n∈(x/2,x]:YM(n)=0}∣=x1−o(1).\left|\left\{n\in(x/2,x]:Y_M(n)=0\right\}\right|=x^{1-o(1)}.

Thus, conditionally, very many blocks of these lengths avoid every collision in the Moser subfamily.

This does not imply that those blocks are good. Other same-support collisions and the exceptional P1P_1 collisions remain uncontrolled.

5. Conditional Moser coverage in the opposite direction

The same Moser intervals can also be used to seek an upper bound for Fϕ(x)F_\phi(x).

Let UM(X,L)U_M(X,L) be the number of starts in (X/2,X](X/2,X] not covered by any corrected Moser interval, and let λM,∗(X,L)\lambda_{M,*}(X,L) denote the minimum Moser intensity on that shell. The predicted intensity is

λM,∗(X,L)=(C22+o(1))Llog⁡L(log⁡X)2.\lambda_{M,*}(X,L)=\left(\frac{C_2}{2}+o(1)\right)\frac{L\log L}{(\log X)^2}.

Assume the following deterministic near-Poisson coverage estimate: for every fixed δ>0\delta>0,

UM(X,L)≤Xexp⁡ ⁣(−(1−δ)λM,∗(X,L))U_M(X,L)\le X\exp\!\left(-(1-\delta)\lambda_{M,*}(X,L)\right)

uniformly for the required polylogarithmic LL.

Under this unproved hypothesis,

Fϕ(x)≤(23C2+ε+o(1))(log⁡x)3log⁡log⁡x.F_\phi(x)\le\left(\frac{2}{3C_2}+\varepsilon+o(1)\right)\frac{(\log x)^3}{\log\log x}.

The hypothesis is much stronger than a first-moment or high-average-multiplicity estimate: it must force the number of uncovered starts below 11 on every sufficiently large dyadic shell.

If such a coverage theorem were proved, it would in particular give a negative answer to the original Erdős question for every fixed c>3c>3.

6. Higher moments and an obstruction to finite-moment arguments

Fixed-rank upper bounds for the factorial moments of the collision count have also been established. These are upper bounds only; they do not imply a lower bound for the probability that CL(n)=0C_L(n)=0.

There is a concrete obstruction to deriving such a lower tail from finitely many approximately Poisson factorial moments.

At rank six, an exact moment-cone construction gives a positive-integer random variable NN such that

E(N)r=λr,1≤r≤6,\mathbb{E}(N)_r=\lambda^r,\qquad 1\le r\le6,

for every

λ≥9.3950709123….\lambda\ge9.3950709123\ldots.

Thus the first six Poisson factorial moments alone cannot force a positive atom at zero in this intensity range.

This is a finite-dimensional probabilistic obstruction, not an arithmetic statement about the totient function.

A separate finite-prime product-cumulant expansion has been proved for the Moser local-factor model. For a connected prime-row diagram, the defect satisfies

d≥r−1,d\ge r-1,

and the minimal diagrams with d=r−1d=r-1 have incidence-tree structure. The minimal class and the first two-block positive-excess class are controlled.

The remaining cumulant problem involves arbitrary positive-excess diagrams, structural primes, zero-resultant strata, and resonant cycle configurations.

In particular, a proposed pointwise bound for arbitrary three-cycle intervals is false: explicit prime arithmetic-progression resonances produce counterexamples. The corresponding aggregate problem for the actual tied Moser ranges remains open.

7. Current status

The rigorous conclusion is

Fϕ(x)≫(log⁡x)2log⁡log⁡x,F_\phi(x)\gg\frac{(\log x)^2}{\log\log x},

so the problem is settled affirmatively for every fixed c<2c<2.

Beyond this, the present work gives:

  1. an exact average formula for the same-support collision coefficient;
  2. an exact description of the structured collision family;
  3. a conditional Moser lower-tail theorem for 2<c<32<c<3;
  4. a conditional Moser coverage theorem giving an upper scale near exponent 33;
  5. fixed-rank factorial-moment bounds and explicit finite-moment obstructions;
  6. a finite-prime cumulant expansion identifying the growing-rank correlation problem more precisely.

The main unresolved steps are to obtain arithmetic lower-tail control weaker than BWHLM\mathrm{BWHL}_M, extend the analysis from the Moser subfamily to the full same-support process, control the remaining growing-rank and resonant correlations, and prove an interval-coverage theorem if pursuing the upper-bound direction.

No result here proves Erdős Problem 1004 for all c>0c>0, and no unconditional upper bound of order (log⁡x)3/log⁡log⁡x(\log x)^3/\log\log x is claimed.

References

  • S. W. Graham, J. J. Holt, and C. Pomerance, On the solutions to phi(n)=phi(n+k), Number Theory in Progress, vol. 2, 1999, pp. 867–882.
  • P. Pollack, C. Pomerance, and E. Treviño, Sets of monotonicity for Euler's totient function, Ramanujan Journal 30 (2013), 379–398.