ERDŐS/DAILY ▸

← back to the ledger

ERDőS #467 · PARTIAL

Erdős problem #467 — wave 9l

Accessed and computed 2026-07-28 (UTC).

Result

[d — computational-only, backed by an exact checker] Under the standard finite interpretation

\[ 1\le n<x,\qquad n\in\mathbb Z, \]

no solution exists for any \(x\le 7012\). The proof reduces every possible partition to an exact fractional-knapsack obstruction. The relaxation first stops obstructing at \(x=7013\), with the potential prefix

\[ A\supset\{2,3,5,7\},\qquad B\supset\{11,13\}. \]

This is not a construction at \(7013\), and says nothing uniform as \(x\to\infty\).

The adjacent standalone verifier is erdos467_wave9l_reverify.py. It uses only Python's standard library, exact integer/rational arithmetic, direct small-residue enumeration, and an independent integral knapsack DP.

Claim labels used below:

Step 0: mandatory live-page check

[d — live browser observation] I fetched the live #467 page and its discussion thread through the Bright Data browser path on 2026-07-28. The gate passed:

[689]” followed by the observation that #689 is phrased as a question;

There was therefore no reason to trigger the requested SKIP.

Live statement, verbatim

Prove the following for all large \(x\): there is a choice of congruence classes \(a_p\) for all primes \(p\leq x\) and a decomposition \(\{p\leq x\}=A\sqcup B\) into two non-empty sets such that, for all \(n<x\), there exist some \(p\in A\) and \(q\in B\) such that \(n\equiv a_p\pmod{p}\) and \(n\equiv a_q\pmod{q}\).

[d — live-page observation] The page itself immediately warns that this is the owner's reconstruction of the intended question: the original source has missing quantifiers and may have been misinterpreted.

The lower-bound ambiguity matters

[a] If “for all \(n<x\)” is read literally as all \(n\in\mathbb Z\), the statement is false for every \(x\). Indeed, the union of finitely many congruence classes is periodic. If it covers the entire half-line \((-\infty,x)\), it covers all of \(\mathbb Z\): any uncovered integer could be shifted down by a sufficiently large multiple of the common period. However, one class modulo each distinct prime cannot cover \(\mathbb Z\). For each prime choose a different residue and apply the Chinese remainder theorem; the resulting integer avoids every chosen class. This already contradicts either colour being a cover.

The only nontrivial finite reading is therefore that \(n\) ranges over positive integers (or possibly nonnegative integers). Everything computed below explicitly uses \(1\le n<x\). I do not claim that the website's omitted lower quantifier has been authoritatively resolved.

Primary-source and literature audit

[d — source-checked] The cited source exists:

P. Erdős and R. L. Graham, Old and New Problems and Results in Combinatorial Number Theory, Monographies de L'Enseignement Mathématique 28 (1980), 128 pp.

I downloaded Ronald Graham's scan and inspected printed page 93 (PDF page 89). It contains a one-sentence “problem on sieves” asking whether the primes below \(n\) can be split into two classes so that suitable residues from both classes cover every integer below \(n\). The indices and the range of the integer are not fully quantified, exactly as the live page warns.

[d — search result, not an exhaustiveness theorem] Exact-phrase searches for the source sentence, its “problem on sieves” opening, and combinations of “split the primes”, “suitable choices”, and the two congruences found the 1980 monograph, but no later primary paper explicitly claiming to solve this specific two-colour problem. Searches were also run against arXiv-specific queries. This is an honest search miss, not proof that no such literature exists.

[d — live source check] The related #689 page currently remains OPEN and has one claimed-proof marker. Its pinned discussion says that two AI-assisted full solution claims for that weaker problem await expert or peer-reviewed validation. One accessible item is the 2026 working manuscript A greedy matching proof of Erdős's two-fold residue-class problem. I do not use it as a theorem.

[a] Even a correct proof of #689 would not by itself prove #467. Given residues, put

\[ W_n=\{p\le x:\ n\equiv a_p\pmod p\}. \]

Problem #689 asks for \(|W_n|\ge2\). Problem #467 asks in addition for a 2-colouring of the prime vertices such that every hyperedge \(W_n\) meets both colours—property B of this witness hypergraph. When every \(|W_n|=2\), this is exactly the requirement that the graph with edges \(W_n\) be bipartite. Multiplicity two alone gives no such conclusion.

[b — modulo the cited theorem] Modern large-gap machinery is relevant but does not immediately bridge this colour requirement. Ford, Konyagin, Maynard, Pomerance and Tao, Long gaps in sieved sets, JEMS 23 (2021), 667–700, corrigendum JEMS 25 (2023), assumes a one-dimensional sieving system:

\[ \prod_{p\le z}\left(1-\frac{|I_p|}{p}\right)\sim\frac{C}{\log z}. \]

If the primes are regularly split into two positive-density halves and each colour is allowed one class only at its own primes, each separate product has dimension about \(1/2\), not \(1\). For example, Mertens' theorem in fixed progressions gives a product of order \((\log z)^{-1/2}\) for a standard half-density split. Restoring dimension one would require roughly two classes per available prime, which is forbidden here. Thus the named one-dimensional theorem cannot simply be run once on each colour.

New finite obstruction

Let

\[ N=x-1,\qquad I_N=\{1,\ldots,N\},\qquad C_p=\{n\in I_N:n\equiv a_p\pmod p\}, \]

and put \(c_p=\lceil N/p\rceil\).

Two-anchor lemma

[a] For three distinct primes \(p,q,r\), define

\[ d_{p;q,r}= \max\left( 0,\, \left\lfloor\frac N{pq}\right\rfloor+ \left\lfloor\frac N{pr}\right\rfloor- \left\lceil\frac N{pqr}\right\rceil \right). \]

Then, for every choice of the three residues,

\[ |C_q\cup C_r| \le c_q+c_r-\left\lfloor\frac N{qr}\right\rfloor \tag{1} \]

and

\[ |C_p\setminus(C_q\cup C_r)|\le c_p-d_{p;q,r}. \tag{2} \]

Proof. A residue class modulo \(s\) has at most \(\lceil N/s\rceil\) members in any interval of \(N\) consecutive integers. By the Chinese remainder theorem, the intersection of classes modulo distinct primes \(u,v\) is one class modulo \(uv\), so it has at least \(\lfloor N/(uv)\rfloor\) members. This proves (1). Furthermore,

\[ |C_p\cap(C_q\cup C_r)| =|C_p\cap C_q|+|C_p\cap C_r|-|C_p\cap C_q\cap C_r|. \]

The first two terms have the corresponding floor lower bounds and the last term has the ceiling upper bound. Taking the maximum with zero and subtracting from \(|C_p|\le c_p\) proves (2). \(\square\)

Write

\[ b(q,r)=c_q+c_r-\left\lfloor\frac N{qr}\right\rfloor,\qquad w_{q,r}(p)=c_p-d_{p;q,r}. \]

If \(q,r\) are two fixed anchor primes of a colour, (1)–(2) give

\[ \left|\bigcup_{p\in S}C_p\right| \le b(q,r)+\sum_{p\in S\setminus\{q,r\}}w_{q,r}(p). \tag{3} \]

This deliberately ignores overlaps among the non-anchor classes, so it is a valid upper bound.

Exhausting the possible anchor prefixes

[a] Swap the colour names if necessary so that \(2\in A\). In the range being scanned, either colour needs at least two primes to cover \(I_N\). Look along the increasing primes and stop when both colours have appeared twice. There are only two forms:

  1. A-late. Before \(A\)'s second prime \(\ell\), its only prime is \(2\).

Thus all primes \(3\le p<\ell\) are in \(B\); the anchors are \((2,\ell)\) for \(A\) and \((3,5)\) for \(B\).

  1. B-late. If \(b<\ell\) are the first two \(B\)-primes, every other

prime below \(\ell\) is in \(A\). The \(A\)-anchors are \((2,5)\) when \(b=3\), and \((2,3)\) otherwise.

After \(\ell\), every prime is free. These cases are exhaustive, and the verifier separately enumerates all short binary colour words to audit this classification.

Exact fractional-knapsack certificate

Fix one prefix. Apply (3) to its forced primes. Let \(B_A,B_B\) be the two resulting forced-base upper bounds. For every free prime \(p\), let \(\alpha_p\) be its upper marginal if assigned to \(A\), and \(\beta_p\) its upper marginal if assigned to \(B\).

If \(T\) is the set of free primes assigned to \(B\), both colours covering \(I_N\) would force

\[ \sum_{p\in T}\alpha_p\le L:=B_A+\sum_{\text{free }p}\alpha_p-N, \tag{4} \]
\[ \sum_{p\in T}\beta_p\ge D:=N-B_B. \tag{5} \]

[a] Relax the indicator of \(p\in T\) from \(\{0,1\}\) to \([0,1]\). The maximum possible left side of (5), subject to (4), is the fractional knapsack value \(F(L)\), obtained by sorting the exact ratios \(\beta_p/\alpha_p\). Hence

\[ F(L)<D \tag{6} \]

is a rigorous obstruction for that entire prefix, all residue choices, and all completions of the partition. The verifier compares ratios and the single fractional item by cross-multiplication; it uses no floating point.

A one-anchor version of the same argument first becomes inconclusive at \(x=2447\). The two-anchor version continues much farther.

Exact computation

[d] It is enough to test prime endpoints. If a solution existed at some \(x\), let \(r\le x\) be the largest prime. The available prime set at \(x\) and \(r\) is identical, and restricting the covered interval to \(\{1,\ldots,r-1\}\) would give a solution at \(r\). This endpoint reduction itself is [a].

The checker found:

through \(7001\);

Thus every \(x\le7012\) reduces to a rejected prime endpoint.

For transparency, here is the fractional arithmetic for the prefix that eventually becomes admissible,

\[ A\supset\{2,3,5,7\},\quad B\supset\{11,13\}. \]

The table's \(F\) is the fractional optimum, not a cover:

| \(x\) | \(\pi(x)\) | \(L\) | \(D\) | \(F(L)\) | \(F-D\) | |---:|---:|---:|---:|---:|---:| | 6991 | 899 | 2623 | 5864 | 5858 | \(-6\) | | 6997 | 900 | 2627 | 5869 | \(11733/2\) | \(-5/2\) | | 7001 | 901 | 2630 | 5872 | 5869 | \(-3\) | | 7013 | 902 | 2634 | 5883 | 5884 | \(1\) |

[d] An independent integral \(0/1\) DP gives optimum \(5869<5872\) at \(x=7001\), and \(5883=5883\) at \(x=7013\). The equality at \(7013\) only says that the coarse marginal budgets can be partitioned; it neither chooses residues nor covers the interval.

Reproduction

python runs/erdos467_wave9l_reverify.py

Observed with Python 3.12.3:

PASS direct residue-set and prefix-classification audits
PASS first one-anchor relaxation admission = 2447
PASS two-anchor scan: 539 rejected prime endpoints; first admission = 7013 via B anchors 11,13
PASS exact fractional table for the boundary prefix
PASS independent integral-DP boundary audit
VERIFIED: under 1 <= n < x, no solution can exist for any integer x <= 7012.
NOTE: 7013 is only where this necessary condition first admits a case; no construction at 7013 is claimed.
elapsed_seconds=34.685

Script SHA-256: a2ce9d7ca42e2e49dd74883a127d0f1e435d0b04ae8d49b322e6ef97817d4912.

Discarded searches

[d] I also encoded the exact problem as SAT, with one variable for each \((p,\text{colour},\text{residue})\). CaDiCaL did not decide the tight \(x=137\) instance within about one minute, did not decide \(x=500\) within 60 seconds, and OR-Tools CP-SAT returned UNKNOWN for \(x=500\) after 55 seconds. These timeouts are not mathematical evidence. They were abandoned in favour of the certifiable capacity obstruction above.

What remains

[a] The original asymptotic question is untouched by the finite cutoff. The exact remaining object can be stated in either of two equivalent ways:

  1. choose residues so that the witness hypergraph

\(\{W_n:1\le n<x\}\) has property B; or

  1. by the Chinese remainder theorem, choose an integer \(R\) and colour the

primes \(p\le x\) so that every \(R+n\), \(1\le n<x\), has a small prime divisor of each colour.

[a] The second equivalence uses \(R\equiv-a_p\pmod p\): then \(n\equiv a_p\pmod p\) exactly when \(p\mid R+n\).

The precise missing lemma is therefore a two-pool covering theorem: construct one residue class per prime together with a prime 2-colouring so that both complementary prime pools cover the same interval. A two-fold uncoloured cover (#689) is insufficient, while the published one-dimensional long-gap theorem cannot be applied independently to two half-dimensional pools. Proving such a two-pool hypergraph-covering lemma, or adding a bipartiteness/property-B invariant to the proposed #689 matching machinery, is the concrete uniform step still missing.

[c] A natural next finite improvement is to use three least-prime anchors per colour. It should extend the cutoff, but it remains only a stronger finite obstruction and offers no evident route to the required uniform two-pool theorem.

PARTIAL: Exact anchor/knapsack certificates rule out every x<=7012 under 1<=n<x; 7013 is only the first relaxation admission, and the asymptotic two-colour problem remains open.

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger