Erdős problem #1200 — live check, exact finite computation, and wall

Date: 2026-07-27 (UTC)

Claim labels

• [a] elementary-rigorous: proved below from elementary facts.
• [b] rigorous modulo named theorem: the theorem and source are named.
• [c] plausible/structural-unverified: heuristic, search miss, or cost projection.
• [d] computational-only: exactly reproducible by the companion program, but not a uniform theorem.

0. Mandatory live-page check

I loaded https://www.erdosproblems.com/1200 through the Bright Data browser path, not datacenter curl, on 2026-07-27. [d] The page was last edited 08 April 2026 and showed:

• status: OPEN;
• claimed proofs: 0;
• “Interested in collaborating”: None;
• “Currently working on this problem”: None;
• “Likes this problem”: Dogmachine;
• “This problem looks difficult”: None;
• “This problem looks tractable”: None;
• “The results on this problem could be formalisable”: None;
• “I am working on formalising the results on this problem”: None;
• formalised statement: No; related OEIS sequences: Possible.

Thus the mandatory no-collision gate passed. [d]

Verbatim live statement

> There exists a constant \(C\) such that for all large \(x\) there is a collection of primes \(p_1<\ldots

The cited source is Paul Erdős, A survey of problems in combinatorial number theory, Annals of Discrete Mathematics 6 (1980), 89–115, p.106 (primary PDF). The source's context makes “integer \(n[b: Er80]

Everything else listed on the live page

The page calls this a “surprising” conjecture of Erdős and Ruzsa. It says a uniform lower bound \(\epsilon_n\ge c>0\) in problem #688 would imply it by using all primes in \([x^c,x]\). [b: Er80]

The page records the alternative question from Erdős–Ruzsa: for primes of bounded reciprocal sum and arbitrary classes, must \(\gg x\) integers remain unsifted, with the implied constant depending only on the reciprocal-sum budget? A positive answer would disprove #1200. It also records their result that zero residue classes can cover a positive proportion with a suitable bounded-reciprocal set of primes. See P. Erdős and I. Z. Ruzsa, On the small sieve. I. Sifting by primes, J. Number Theory 12 (1980), 385–394, especially p.386, Problem 2, DOI 10.1016/0022-314X(80)90032-390032-3) (primary author-hosted PDF). [b: ErRu80]

The page links related problems #783 and #784. [d: live-page observation]

There is exactly one unverified user comment. Adenwalla (18 June 2026) writes: “In the second paragraph below the question, it says \(\gg_Kx\) but this should be \(\gg_kx\).” It contains no proof or construction. The original Erdős–Ruzsa paper itself writes \(c=c(K)>0\), so no mathematical step below relies on the comment's proposed typography. [d: live-page observation; b: comparison with ErRu80]

1. Literature check

I searched exact fragments of the statement and of “What happens if we sift by other residue classes?”, the exact paper title and DOI, and combinations of “small sieve”, “arbitrary residue classes”, “bounded reciprocal sum”, Erdős, and Ruzsa. I checked the primary 1980 sources above and citation/search results leading to the zero-class work of Hildebrand and to modern interval-sieve work. [d]

The closest modern primary source found was W. Banks, K. Ford, and T. Tao, Large prime gaps and probabilistic models, Invent. Math. 233 (2023), 1471–1518, DOI 10.1007/s00222-023-01199-0. In §1.4 they define

and record

The lower bound is attributed there to Iwaniec's linear-sieve theory. [b: Iwaniec/Banks–Ford–Tao]

This does not settle #1200: it uses every prime up to \((y/\log y)^{1/2}\), whose reciprocal sum tends to infinity by Mertens' theorem, and it does not control the additional classes with prime moduli extending up to \(y\). [b: Mertens' theorem; a: comparison of hypotheses]

No primary source surfaced in these searches that proves or disproves the bounded-reciprocal, arbitrarily shifted statement. This is a report of a search miss, not a claim that such a source cannot exist. [c]

2. Exact reduction

For \(N\ge1\), define

with \(\mu(N)=+\infty\) if no cover exists.

Problem #1200 is equivalent to

Indeed, for a real \(x\), put \(N=\lceil x\rceil-1\); then the positive integers below \(x\) are exactly \([1,N]\), and every prime \(p\le N\) satisfies \(p[a]

This reduction is the reason the finite computation below directly measures the conjectured quantity, rather than an adjacent statistic. [a]

3. Elementary constraints and the precise structural bottleneck

3.1 The limiting budget cannot be below 1

A class modulo \(p\) contains at most \(\lceil N/p\rceil\le N/p+1\) elements of \([1,N]\). Therefore every cover satisfies

and hence

[a] By the prime number theorem, \(\liminf\mu(N)\ge1\), so no constant \(C<1\) can work in #1200. [b: prime number theorem]

3.2 CRT turns the question into an extreme-gap question

Fix \(P\), residues \(a_p\), and \(Q=\prod_{p\in P}p\). The Chinese remainder theorem gives exactly

residue classes modulo \(Q\) which avoid every \(a_p\bmod p\). Thus the globally unsifted set is periodic with density

[a] Since \(\log(1-t)\ge-2t\) for \(0\le t\le1/2\), a budget \(\sum1/p\le C\) leaves global density at least \(e^{-2C}\). [a]

Consequently #1200 is not about global density: it asks whether such a positive-density periodic set can be made to have a gap of length \(N\) while all its prime moduli are at most \(N\) and their reciprocal sum stays bounded. [a]

In particular, every cover has \(Q>N\). If \(Q\le N\), an avoiding CRT residue has a representative in \([1,Q]\subseteq[1,N]\). [a]

There is also the following exact necessary condition. For every \(S\subseteq P\), put \(Q_S=\prod_{p\in S}p\). The classes for \(S\) leave exactly \(\prod_{p\in S}(p-1)\) points in each complete block of length \(Q_S\). Hence any cover must satisfy

[a] Formula (1) cleanly separates the periodic small-prime survivors from the total capacity of the remaining large-prime classes, but it is not strong enough to decide the uniform problem. [a for insufficiency as a logical observation]

3.3 Exact missing input

The disproof route needs a shift-uniform small-sieve lemma: for each fixed \(C\), a positive \(\delta(C)\) such that every choice with \(\sum1/p\le C\) leaves at least \(\delta(C)N\) points of \([1,N]\). This is precisely the arbitrary-residue question on p.386 of ErRu80. [a: implication; b: identification with ErRu80]

The proof route needs the opposite kind of result: a uniform construction showing that the small-prime survivor set can always be finished by large-prime residue classes with bounded additional reciprocal mass. No such matching/construction theorem was found. [c]

Standard CRT density estimates stop at period \(Q>N\); the linear sieve handles the small-prime range but its known survivor lower bound is \(o(N)\), while a bounded reciprocal mass of large primes has crude capacity \(\Theta(N)\). The unresolved issue is the arithmetic incidence between those survivors and the available large-prime classes, not their total cardinalities alone. [a: diagnosis from the displayed bounds]

4. Exact finite result

4.1 Table

The companion program proves the following complete table. Every value, including every \(+\infty\), is [d: computational-only].

| \(N\) | exact \(\mu(N)\) | decimal |

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

| 1, 2, 4, 6, 10 | \(+\infty\) | — |

| 3 | \(5/6\) | 0.833333333333 |

| 5 | \(31/30\) | 1.033333333333 |

| 7–9 | \(247/210\) | 1.176190476190 |

| 11–12 | \(2927/2310\) | 1.267099567100 |

| 13 | \(5153/4290\) | 1.201165501166 |

| 14–16 | \(40361/30030\) | 1.344022644023 |

| 17 | \(91891/72930\) | 1.259989030577 |

| 18 | \(60887/46410\) | 1.311937082525 |

| 19–21 | \(2435549/1939938\) | 1.255477752382 |

| 22 | \(1203263/881790\) | 1.364568661473 |

| 23–25 | \(57957565/44618574\) | 1.298956013251 |

| 26–27 | \(28556839/20281170\) | 1.408046922342 |

| 28 | \(24403493/17160990\) | 1.422032936328 |

| 29–30 | \(1725387959/1293938646\) | 1.333438771872 |

| 31–33 | \(3083613541/2359535178\) | 1.306873306976 |

| 34–36 | \(54780965375/40112098026\) | 1.365696836388 |

| 37 | \(104678672837/78113032998\) | 1.340092284468 |

| 38–39 | \(86744262653/62359143990\) | 1.391043191146 |

| 40 | \(2067007816901/1484147626962\) | 1.392723863415 |

The largest finite value in this prefix is

[d] The sequence is not monotone because a new endpoint prime supplies a new allowed modulus; for example the value drops at \(N=13,17,19,23,29,31,37\). [d]

4.2 An explicit endpoint witness

For \(N=40\), the verifier checks the following cover:

Its exact reciprocal cost is \(2067007816901/1484147626962\), and every integer \(1,\ldots,40\) lies in at least one displayed class. [d] The standalone file contains and checks witnesses for every finite row, not just \(N=40\). [d]

4.3 Why the lower certificate is exact

The full source is runs/erdos1200_wave6x_verify.py, SHA-256

f8c8c0bc1509108ceeecec765b0f9bb1db146ae24bea1ad8b7c66455534f505d.

It uses only the Python standard library. It recomputes primes by trial division, recomputes all objective values with fractions.Fraction, and checks coverage with integer bit masks. [d]

For the lower bound, at any search node choose an uncovered \(n\). Any completion must use some unused prime \(p\) with the forced residue \(n\bmod p\); branching over all unused \(p\) is therefore exhaustive. [a] Failed states (covered_mask, remaining_primes) are memoized. [d]

The only nontrivial prune is rigorous. If a class for \(p\) can cover at most \(g_p\) currently uncovered points, relax it to a divisible item of capacity \(g_p\) and cost \(1/p\). Fractional knapsack gives a lower bound on every completion. Each contribution is rounded down at scale \(10^{15}\), and the result is compared to the exact Fraction budget by integer cross-multiplication. Thus floating-point error cannot prune a genuine cheaper cover. [a]

For even \(N\), reflection \(n\mapsto N+1-n\) swaps the two parity classes, so the verifier checks separately (i) covers omitting modulus 2 and (ii) covers using \(0\bmod2\). For odd \(N\), it checks omission and both parity classes. These cases are exhaustive. [a]

Run:

cd /home/exedev/MathDyad
python runs/erdos1200_wave6x_verify.py

The recorded full run finished successfully in 34.180 seconds and reported the table above. [d]

Candidate witnesses were initially scouted with integer programming, but no solver status or floating objective is trusted by the report: the delivered program independently proves coverage and absence of every strictly cheaper cover. [d]

5. Honest limit and computation cost

This does not prove boundedness of \(\mu(N)\), and the observed maximum \(1.422\ldots\) through 40 is not evidence strong enough to extrapolate a uniform constant. [a for non-implication; c for any extrapolation]

With the same pure-Python search, the modulus-2-omission branch for \(N=50\) exceeded five million states and 107 seconds and did not finish before a 120-second cap; it was not included as an exact result. [d] At the observed rate, \(10^8\) states would cost roughly 0.6 core-hours and \(10^9\) roughly 6 core-hours, before memory growth; whether either is enough for \(N=50\)–100 is unknown. [c: extrapolated cost] A serious larger computation should use a compiled solver with a checkable UNSAT/optimization certificate rather than merely trusting a solver's “optimal” flag. [c: methodological recommendation]

The concrete progress is therefore: an exact reformulation, two elementary necessary bounds including (1), and a fully re-runnable exact table through \(N=40\). The exact asymptotic missing lemma remains the arbitrary-shift, bounded-reciprocal small-sieve statement identified above. [a+d]

PARTIAL: Exact standard-library certification of the direct invariant \(\mu(N)\) for every \(1\le N\le40\) (maximum \(1.422032936328\ldots\)); the uniform arbitrary-shift large-prime lemma needed for Erdős #1200 remains open.