Erdős Problem #1004 — 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?

Partial progress on Erdős Problem 1004

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

Define

$$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>0$,

$$F_\phi(x)\ge(\log x)^c$$

for all sufficiently large $x$.

1. Unconditional lower bound

For a block of length $L$, define its collision count by

$$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 $C_L(n)=0$.

For a shift $h$, write

$$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 $P_0(X;h)$ and an exceptional part $P_1(X;h)$. The published estimates give, uniformly in the polylogarithmic ranges needed here,

$$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)$ by

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

Let

$$\gamma(n)=\operatorname{rad}(n)$$

and

$$\rho(n)=\prod_{\substack{p\mid n\p>2}}\frac{p-1}{p-2}.$$

An exact reparametrization of the structured coefficient gives

$$\sum_{h\le H}c(h)=K_\phi\log H+O(1),$$

where

$$K_\phi=\sum_{\substack{a<b\\(a,b)=1}}\frac{\rho(ab(b-a))}{ab\,\gamma(ab)},\qquad 0<K_\phi<\infty.$$

Consequently,

$$\sum_{h<L}(L-h)c(h)=K_\phi L\log L+O(L).$$

A union bound over all possible collision shifts then gives

$$\left|\left\{n\le x:C_L(n)>0\right\}\right|\ll x\frac{L\log L}{(\log x)^2}+o(x).$$

Therefore, if

$$L\log(2L)=o((\log x)^2),$$

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

In particular,

$$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<2$. This argument does not reach $c=2$.

2. Structure of the same-support collisions

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

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

where

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

If

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

are prime, then

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

satisfy

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

This parametrization is also the source of the $L\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

$$2C_2K_\phi\frac{L\log L}{(\log x)^2},$$

where

$$C_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 $h$ is even, $p$ and $2p-1$ are prime, and

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

Then

$$\phi\!\left(h(2p-1)\right)=\phi(2hp).$$

The coprimality condition is essential.

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

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

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

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

$$\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 $\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 $\lambda_M$.

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

Under $\mathrm{BWHL}_M$,

$$\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,\qquad 2<c<3,$$

then

$$\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 $P_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_\phi(x)$.

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

$$\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 $\delta>0$,

$$U_M(X,L)\le X\exp\!\left(-(1-\delta)\lambda_{M,*}(X,L)\right)$$

uniformly for the required polylogarithmic $L$.

Under this unproved hypothesis,

$$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 $1$ 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>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 $C_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 $N$ such that

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

for every

$$\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\ge r-1,$$

and the minimal diagrams with $d=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_\phi(x)\gg\frac{(\log x)^2}{\log\log x},$$

so the problem is settled affirmatively for every fixed $c<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<3$;
4. a conditional Moser coverage theorem giving an upper scale near exponent $3$;
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 $\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>0$, and no unconditional upper bound of order $(\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.