Erdős Problem #688

Erdős Problem 688 --- collection record

PROVENANCE AND STATUS

Official problem: https://www.erdosproblems.com/688

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/688.tex.

REUSED SOURCE 1

Original attribution: gpt_pro_5.2. Original file: attacks/erdos/gpt_pro_5.2/688.tex.

Erdős Problem 688

1) FORMAL RESTATEMENT.

Fix an integer $n\ge 2$. For a real parameter $\epsilon\ge 0$, let \[ \mathcal P_\epsilon(n):=\{\,p:\ p\text{ prime},\ n^\epsilon<p\le n\,\}. \] We say $\epsilon$ is admissible if there exist residue classes $a_p\pmod p$ for every prime $p\in\mathcal P_\epsilon(n)$ such that every integer $m\in[1,n]$ satisfies at least one congruence $m\equiv a_p\pmod p$ with $p\in\mathcal P_\epsilon(n)$. Define \[ \epsilon_n:=\sup\{\epsilon\ge 0:\ \epsilon\text{ is admissible}\}. \] (The strict inequality $n^\epsilon<p$ means the supremum need not be attained; the problem asks for estimates as $n\to\infty$.)

Question: estimate $\epsilon_n$; in particular, is $\epsilon_n=o(1)$?

2) QUICK LITERATURE/CONTEXT CHECK.

The problem statement records Erdős's lower bound \[ \epsilon_n \gg \frac{\log\log\log n}{\log\log n}. \] No other external results are used or claimed here.

3) ATTACK PLAN.

• Reformulate admissibility in terms of a shift $t$ modulo the product of the primes in $\mathcal P_\epsilon(n)$ (Lemma 688.1).
• Derive simple necessary conditions from counting/coverage constraints (Lemma 688.2).
• Use small-$n$ computations to sanity check the definition and see when admissibility first appears.

4) WORK.

Lemma 688.1 (shift reformulation for a fixed prime set). Fix $n\ge 2$ and a set of primes $S\subseteq\{p:\ p\le n\}$, and let $P_S:=\prod_{p\in S}p$. Choosing residue classes $\{a_p\pmod p\}_{p\in S}$ is equivalent (by CRT) to choosing a residue class $t\pmod{P_S}$ such that $t\equiv -a_p\pmod p$ for all $p\in S$. With this $t$, an integer $m\in[1,n]$ is covered (i.e. $m\equiv a_p\pmod p$ for some $p\in S$) if and only if $m+t$ is divisible by some prime in $S$, equivalently \[ \gcd(m+t,P_S)>1. \] In particular, $\epsilon$ is admissible (for the set $S=\mathcal P_\epsilon(n)$) if and only if there exists $t$ such that \[ \gcd(t+1,P_S)>1,\ \gcd(t+2,P_S)>1,\ \dots,\ \gcd(t+n,P_S)>1. \]

Proof. Identical to Lemma 687.1, but with the prime set $S$ in place of $\{p\le x\}$. $\square$

Lemma 688.2 (simple counting necessary condition). Let $S=\mathcal P_\epsilon(n)$ and suppose $\epsilon$ is admissible, witnessed by residue classes $\{a_p\pmod p\}_{p\in S}$. Then \[ \sum_{p\in S}\left\lceil\frac{n}{p}\right\rceil \ge n. \]

Proof. For each $p\in S$, the chosen residue class $a_p\pmod p$ hits at most $\lceil n/p\rceil$ integers in $[1,n]$, because among any $p$ consecutive integers there is at most one representative of a fixed residue class, and the interval $[1,n]$ has length $n$. Let \[ C_p:=\#\{\,m\in[1,n]:\ m\equiv a_p\pmod p\,\}. \] Then $C_p\le \lceil n/p\rceil$ for each $p$. If every $m\in[1,n]$ is covered by at least one of the residue classes, then counting incidences gives \[ n \le \sum_{p\in S} C_p \le \sum_{p\in S}\left\lceil\frac{n}{p}\right\rceil, \] which is the stated inequality. $\square$

FAST REALITY CHECK (local computation for small $n$). For each $n\le 20$, I tested admissibility for prime sets of the form $S=\{p:\ p_{\min}\le p\le n\}$ (all primes in an upper tail), using the shift formulation (Lemma 688.1) and scanning residues modulo $P_S$ to find the maximum run of consecutive integers with gcd$>1$ with $P_S$. Results:

• For $n=4,6,10$, no choice of residue classes for all primes $p\le n$ covers $[1,n]$ (verified by brute force over all residue choices). Equivalently, even with $S=\{p\le n\}$, the maximum run length is $<n$.
• For $n=3,5,7,8,9,11,\dots,20$, covering is possible, but in all feasible cases found, the smallest prime in $S$ must be $2$ (i.e. excluding $p=2$ makes the maximum run $<n$). For example:

  n=17: S={3,5,7,11,13,17} gives maxrun=12 < 17  (so p_min=3 fails)
  n=17: S={2,3,5,7,11,13,17} gives maxrun=25 >=17 (so p_min=2 works)
  

These computations are only for small $n$ and do not address asymptotics.

5) VERIFICATION.

• Lemma 688.1 is an exact CRT equivalence.
• Lemma 688.2 is a necessary condition only (it ignores overlaps between the classes), so it cannot by itself prove admissibility.
• The computed "no" instances ($n=4,6,10$) were verified by exhaustive search over all residue choices for all primes $\le n$.

FINAL.

UNRESOLVED

(i) Strongest proved partial result. Admissibility for $\epsilon$ is equivalent to the existence of a shift $t$ such that $t+1,\dots,t+n$ are all divisible by at least one prime in $\mathcal P_\epsilon(n)$ (Lemma 688.1). Any admissible $\epsilon$ must satisfy the counting constraint $\sum_{n^\epsilon<p\le n}\lceil n/p\rceil\ge n$ (Lemma 688.2).

(ii) First gap (crisp statement). Prove any asymptotic upper bound on $\epsilon_n$ (e.g. $\epsilon_n=o(1)$) without invoking literature beyond what is stated in the problem file. Equivalently: show that if one excludes all primes $\le n^\epsilon$ for fixed $\epsilon>0$, then for $n$ large, some $m\in[1,n]$ avoids all chosen classes modulo primes $>n^\epsilon$.

(iii) Top 3 next moves.

1. Use Lemma 688.2 together with explicit estimates for $\sum_{p>n^\epsilon}1/p$ (if allowed) to obtain a quantitative upper bound on admissible $\epsilon$.
2. In the shift model, study runs of length $n$ of integers all having a prime factor $>n^\epsilon$ and attempt to upper-bound their length using sieve methods on $y$-rough numbers.
3. Extend computation to moderately larger $n$ (where $P_S$ remains tractable) to guess the growth of $\epsilon_n$ and identify extremal shifts $t$.

(iv) What a minimal counterexample would likely look like. If $\epsilon_n$ does not tend to $0$, there would exist a fixed $\epsilon_0>0$ and infinitely many $n$ with a shift $t$ such that every one of $t+1,\dots,t+n$ has a prime divisor in $(n^{\epsilon_0},n]$; this would force unusually long intervals consisting entirely of integers with a relatively large prime factor.

COMPLETION ESTIMATE

The primary source supplies no extractable numerical completion estimate. Its mathematical progress is not numerically assessed here.

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.

Erdős Problem 688

1) FORMAL RESTATEMENT.

Fix an integer $n\ge 2$. For a real parameter $\epsilon\ge 0$, let \[ \mathcal P_\epsilon(n):=\{\,p:\ p\text{ prime},\ n^\epsilon<p\le n\,\}. \] We say $\epsilon$ is admissible if there exist residue classes $a_p\pmod p$ for every prime $p\in\mathcal P_\epsilon(n)$ such that every integer $m\in[1,n]$ satisfies at least one congruence $m\equiv a_p\pmod p$ with $p\in\mathcal P_\epsilon(n)$. Define \[ \epsilon_n:=\sup\{\epsilon\ge 0:\ \epsilon\text{ is admissible}\}. \] (The strict inequality $n^\epsilon<p$ means the supremum need not be attained; the problem asks for estimates as $n\to\infty$.)

Question: estimate $\epsilon_n$; in particular, is $\epsilon_n=o(1)$?

2) QUICK LITERATURE/CONTEXT CHECK.

The problem statement records Erdős's lower bound \[ \epsilon_n \gg \frac{\log\log\log n}{\log\log n}. \] No other external results are used or claimed here.

3) ATTACK PLAN.

• Reformulate admissibility in terms of a shift $t$ modulo the product of the primes in $\mathcal P_\epsilon(n)$ (Lemma 688.1).
• Derive simple necessary conditions from counting/coverage constraints (Lemma 688.2).
• Use small-$n$ computations to sanity check the definition and see when admissibility first appears.

4) WORK.

Lemma 688.1 (shift reformulation for a fixed prime set). Fix $n\ge 2$ and a set of primes $S\subseteq\{p:\ p\le n\}$, and let $P_S:=\prod_{p\in S}p$. Choosing residue classes $\{a_p\pmod p\}_{p\in S}$ is equivalent (by CRT) to choosing a residue class $t\pmod{P_S}$ such that $t\equiv -a_p\pmod p$ for all $p\in S$. With this $t$, an integer $m\in[1,n]$ is covered (i.e. $m\equiv a_p\pmod p$ for some $p\in S$) if and only if $m+t$ is divisible by some prime in $S$, equivalently \[ \gcd(m+t,P_S)>1. \] In particular, $\epsilon$ is admissible (for the set $S=\mathcal P_\epsilon(n)$) if and only if there exists $t$ such that \[ \gcd(t+1,P_S)>1,\ \gcd(t+2,P_S)>1,\ \dots,\ \gcd(t+n,P_S)>1. \]

Proof. Identical to Lemma 687.1, but with the prime set $S$ in place of $\{p\le x\}$. $\square$

Lemma 688.2 (simple counting necessary condition). Let $S=\mathcal P_\epsilon(n)$ and suppose $\epsilon$ is admissible, witnessed by residue classes $\{a_p\pmod p\}_{p\in S}$. Then \[ \sum_{p\in S}\left\lceil\frac{n}{p}\right\rceil \ge n. \]

Proof. For each $p\in S$, the chosen residue class $a_p\pmod p$ hits at most $\lceil n/p\rceil$ integers in $[1,n]$, because among any $p$ consecutive integers there is at most one representative of a fixed residue class, and the interval $[1,n]$ has length $n$. Let \[ C_p:=\#\{\,m\in[1,n]:\ m\equiv a_p\pmod p\,\}. \] Then $C_p\le \lceil n/p\rceil$ for each $p$. If every $m\in[1,n]$ is covered by at least one of the residue classes, then counting incidences gives \[ n \le \sum_{p\in S} C_p \le \sum_{p\in S}\left\lceil\frac{n}{p}\right\rceil, \] which is the stated inequality. $\square$

FAST REALITY CHECK (local computation for small $n$). For each $n\le 20$, I tested admissibility for prime sets of the form $S=\{p:\ p_{\min}\le p\le n\}$ (all primes in an upper tail), using the shift formulation (Lemma 688.1) and scanning residues modulo $P_S$ to find the maximum run of consecutive integers with gcd$>1$ with $P_S$. Results:

• For $n=4,6,10$, no choice of residue classes for all primes $p\le n$ covers $[1,n]$ (verified by brute force over all residue choices). Equivalently, even with $S=\{p\le n\}$, the maximum run length is $<n$.
• For $n=3,5,7,8,9,11,\dots,20$, covering is possible, but in all feasible cases found, the smallest prime in $S$ must be $2$ (i.e. excluding $p=2$ makes the maximum run $<n$). For example:

  n=17: S={3,5,7,11,13,17} gives maxrun=12 < 17  (so p_min=3 fails)
  n=17: S={2,3,5,7,11,13,17} gives maxrun=25 >=17 (so p_min=2 works)
  

These computations are only for small $n$ and do not address asymptotics.

5) VERIFICATION.

• Lemma 688.1 is an exact CRT equivalence.
• Lemma 688.2 is a necessary condition only (it ignores overlaps between the classes), so it cannot by itself prove admissibility.
• The computed "no" instances ($n=4,6,10$) were verified by exhaustive search over all residue choices for all primes $\le n$.

FINAL.

UNRESOLVED

(i) Strongest proved partial result. Admissibility for $\epsilon$ is equivalent to the existence of a shift $t$ such that $t+1,\dots,t+n$ are all divisible by at least one prime in $\mathcal P_\epsilon(n)$ (Lemma 688.1). Any admissible $\epsilon$ must satisfy the counting constraint $\sum_{n^\epsilon<p\le n}\lceil n/p\rceil\ge n$ (Lemma 688.2).

(ii) First gap (crisp statement). Prove any asymptotic upper bound on $\epsilon_n$ (e.g. $\epsilon_n=o(1)$) without invoking literature beyond what is stated in the problem file. Equivalently: show that if one excludes all primes $\le n^\epsilon$ for fixed $\epsilon>0$, then for $n$ large, some $m\in[1,n]$ avoids all chosen classes modulo primes $>n^\epsilon$.

(iii) Top 3 next moves.

1. Use Lemma 688.2 together with explicit estimates for $\sum_{p>n^\epsilon}1/p$ (if allowed) to obtain a quantitative upper bound on admissible $\epsilon$.
2. In the shift model, study runs of length $n$ of integers all having a prime factor $>n^\epsilon$ and attempt to upper-bound their length using sieve methods on $y$-rough numbers.
3. Extend computation to moderately larger $n$ (where $P_S$ remains tractable) to guess the growth of $\epsilon_n$ and identify extremal shifts $t$.

(iv) What a minimal counterexample would likely look like. If $\epsilon_n$ does not tend to $0$, there would exist a fixed $\epsilon_0>0$ and infinitely many $n$ with a shift $t$ such that every one of $t+1,\dots,t+n$ has a prime divisor in $(n^{\epsilon_0},n]$; this would force unusually long intervals consisting entirely of integers with a relatively large prime factor.