gpt pro 5.2 attempt on Math-5820

Erdős Problem 687

1) FORMAL RESTATEMENT.

Let $x\ge 2$ be real, and let $\mathcal P(x):=\{p:\ p\text{ prime},\ p\le x\}$. For each $p\in\mathcal P(x)$ choose a residue class $a_p\pmod p$. Say that an integer $n$ is covered if $n\equiv a_p\pmod p$ for at least one prime $p\le x$. Define $Y(x)$ to be the maximal integer $y\ge 0$ for which there exist choices $\{a_p\}_{p\le x}$ such that every integer in $[1,y]$ is covered.

The problem asks for good estimates for $Y(x)$ as $x\to\infty$, in particular whether one can prove $Y(x)=o(x^2)$ or even $Y(x)\ll x^{1+o(1)}$.

2) QUICK LITERATURE/CONTEXT CHECK.

The problem statement already records:

• an upper bound due to Iwaniec: $Y(x)\ll x^2$,
• a lower bound due to Ford--Green--Konyagin--Maynard--Tao: $Y(x)\gg x\frac{\log x\log\log\log x}{\log\log x}$,
• a conjecture of Maier--Pomerance: $Y(x)\ll x(\log x)^{2+o(1)}$.

No additional literature is used or claimed here.

3) ATTACK PLAN.

• Main reformulation: encode the residue choices by a single shift $t$ modulo the primorial $P(x):=\prod_{p\le x}p$ (Lemma 687.1), so that the problem becomes: maximize the length of an interval of consecutive integers containing no number coprime to $P(x)$.
• Proof-track: try to upper-bound the longest run of consecutive integers all having a prime factor $\le x$ (i.e. all non-coprime to $P(x)$), using sieve bounds on gaps between $x$-rough numbers.
• Disproof-track (for very strong conjectures): attempt to build explicit residue choices/shift producing intervals of length close to $x^2$ or larger, guided by constructions for large prime gaps.

4) WORK.

Lemma 687.1 (CRT shift reformulation). Let $P(x):=\prod_{p\le x}p$. Given a choice of residue classes $\{a_p\pmod p\}_{p\le x}$, there exists a unique residue class $t\pmod{P(x)}$ such that \[ t\equiv -a_p \pmod p\quad\text{for every prime }p\le x. \] For this $t$, an integer $n$ satisfies $n\equiv a_p\pmod p$ for some $p\le x$ if and only if $n+t$ is divisible by some prime $p\le x$, i.e. \[ \exists\,p\le x:\ n\equiv a_p\pmod p\quad\Longleftrightarrow\quad \gcd(n+t,P(x))>1. \] Consequently, $Y(x)$ equals the maximum length of a run of consecutive integers all not coprime to $P(x)$: \[ Y(x)=\max_{t\in\mathbb Z}\ \max\{\,y\ge 0:\ \gcd(t+1,P(x))>1,\dots,\gcd(t+y,P(x))>1\,\}. \]

Proof. For distinct primes $p\le x$, the moduli are coprime, so by the Chinese remainder theorem there exists a unique $t\pmod{P(x)}$ solving the simultaneous congruences $t\equiv -a_p\pmod p$.

For a fixed prime $p\le x$ and integer $n$, we have \[ n\equiv a_p\pmod p\quad\Longleftrightarrow\quad n-a_p\equiv 0\pmod p \quad\Longleftrightarrow\quad n+t\equiv 0\pmod p \] because $t\equiv -a_p\pmod p$. Thus $n$ is covered by at least one congruence class $a_p\pmod p$ if and only if $n+t$ is divisible by at least one prime $p\le x$. Since $P(x)$ is the product of all primes $\le x$, this is equivalent to $\gcd(n+t,P(x))>1$.

The final displayed formula for $Y(x)$ is exactly the definition of $Y(x)$ rewritten in terms of this equivalence (covering $[1,y]$ corresponds to choosing $t$ such that $t+1,\dots,t+y$ are all divisible by some prime $\le x$). $\square$

Lemma 687.2 (elementary lower bound $Y(x)\ge x-1$). For every real $x\ge 2$, one has $Y(x)\ge \lfloor x\rfloor-1$.

Proof. Let $X:=\lfloor x\rfloor$ and set $t=1$ in the reformulation of Lemma 687.1. We claim that every integer $n\in[1,X-1]$ is covered by the residue choices $a_p\equiv -1\equiv p-1\pmod p$ for all primes $p\le x$. Indeed, for such $n$ we have $n+1\le X\le x$, hence $n+1$ has some prime divisor $p\le n+1\le x$. Then $p\mid (n+1)$ implies $n\equiv -1\equiv p-1\pmod p$, so $n$ lies in the chosen class for that prime $p$. Thus $[1,X-1]$ is fully covered and $Y(x)\ge X-1$. $\square$

Lemma 687.3 (trivial upper bound from counting totatives). Let $P(x)=\prod_{p\le x}p$ and $\varphi$ be Euler's totient function. Then \[ Y(x)\le P(x)-\varphi(P(x)). \]

Proof. By Lemma 687.1, for any shift $t$ the pattern of coprimality of $t+1,t+2,\dots$ with $P(x)$ is periodic modulo $P(x)$. In a complete residue system modulo $P(x)$, there are exactly $\varphi(P(x))$ residues coprime to $P(x)$ and hence $P(x)-\varphi(P(x))$ residues that are not coprime.

If an interval of consecutive integers contains no number coprime to $P(x)$, then within one period of length $P(x)$ it can cover at most all the non-coprime residues, i.e. it cannot have length exceeding $P(x)-\varphi(P(x))$; otherwise, among the first $P(x)-\varphi(P(x))+1$ distinct residues in $[1,P(x)]$ one would be coprime (pigeonhole, since only $P(x)-\varphi(P(x))$ residues are non-coprime). Thus the maximal such run length is at most $P(x)-\varphi(P(x))$, which equals the stated bound on $Y(x)$. $\square$

FAST REALITY CHECK (local computation). Using the Lemma 687.1 reformulation, I computed $Y(x)$ for small $x$ by scanning residues modulo $P(x)$ and finding the maximal gap between consecutive totatives of $P(x)$. The exact values for integer $x\le 19$ are:

x= 2  Y(x)= 1
x= 3  Y(x)= 3
x= 4  Y(x)= 3
x= 5  Y(x)= 5
x= 6  Y(x)= 5
x= 7  Y(x)= 9
x= 8  Y(x)= 9
x= 9  Y(x)= 9
x=10  Y(x)= 9
x=11  Y(x)=13
x=12  Y(x)=13
x=13  Y(x)=21
x=14  Y(x)=21
x=15  Y(x)=21
x=16  Y(x)=21
x=17  Y(x)=25
x=18  Y(x)=25
x=19  Y(x)=33

These are exact for the computed $x$ and are consistent with the easy bound $Y(x)\ge x-1$.

5) VERIFICATION.

• Lemma 687.1 is a direct CRT equivalence; the key point is that choosing one residue class mod each prime is equivalent to choosing a single shift $t$ modulo their product.
• Lemma 687.2 is checked: for each $n\le x-1$, the integer $n+1$ has some prime factor $\le x$, guaranteeing coverage by $a_p\equiv -1$.
• Lemma 687.3 is very weak asymptotically because $P(x)$ grows super-exponentially in $x$, but it is logically correct.

FINAL.

UNRESOLVED

(i) Strongest proved partial result. An exact reformulation: $Y(x)$ is the maximum length of a run of consecutive integers all not coprime to the primorial $P(x)=\prod_{p\le x}p$ (Lemma 687.1). In particular, $Y(x)\ge \lfloor x\rfloor-1$ (Lemma 687.2) and $Y(x)\le P(x)-\varphi(P(x))$ (Lemma 687.3).

(ii) First gap (crisp statement). Prove a nontrivial upper bound improving $Y(x)\ll x^2$ (e.g. $Y(x)=o(x^2)$) from only the covering/CRT formulation, without assuming any results not already in the problem statement.

(iii) Top 3 next moves.

1. Translate $Y(x)$ bounds into bounds on maximal gaps between integers coprime to $P(x)$, and attempt to apply/derive sieve bounds on gaps between $x$-rough numbers (integers with no prime factor $\le x$).
2. Perform more computations for larger $x$ (as far as feasible) to see whether $Y(x)$ appears closer to $x(\log x)^2$ or to $x^2$.
3. Try to prove that any run of length $L$ with all numbers divisible by primes $\le x$ forces the existence of a prime gap of comparable length; then import (only) those prime-gap bounds explicitly allowed by the problem statement.

(iv) What a minimal counterexample would likely look like. A counterexample to $Y(x)=o(x^2)$ would require a sequence $x_j\to\infty$ and shifts $t_j$ such that the interval $[t_j+1,t_j+Y(x_j)]$ contains no integer coprime to $P(x_j)$, with $Y(x_j)$ of order $c\,x_j^2$ or larger; equivalently, extremely long gaps between integers coprime to the primorials.