Erdős problem #278 — wave8q report
Date of live-page audit, literature search, and computation: 2026-07-28 UTC.
Outcome
This does not solve the general maximum-density question. It gives three
verifiable partial advances.
1. (b) Complexity reduction. The decision problem
> Given distinct moduli \(n_1,\ldots,n_r\), can one choose pairwise
> disjoint classes \(a_i\pmod {n_i}\)?
is NP-complete. The reduction below is elementary and uses only squarefree
moduli; NP-hardness is modulo the standard named theorem that graph
3-colourability is NP-complete. Since attaining
\(\sum_i1/n_i<1\) is equivalent to making the classes pairwise disjoint,
exact evaluation of the maximum in #278 is NP-hard in the usual binary
input model. This is a precise uniform obstruction, stronger than saying
merely that a formula “looks difficult.”
2. (a) Exact family. If \(n_i=mq_i\), where the \(q_i\) are pairwise
coprime and each is coprime to \(m\), then the maximum has the exact
\(m\)-bin product-partition formula
\[ M(mq_1,\ldots,mq_r) = 1-\frac1m\min_{\phi:[r]\to\mathbb Z/m\mathbb Z} \sum_{c=0}^{m-1} \prod_{\phi(i)=c}\left(1-\frac1{q_i}\right). \tag{1} \]
This includes \(q_i=1\), so it contains Cambie's
\(\{3\}\cup\{3p:p\in P\}\) family. Cambie states the prime-common-core
case; (1) allows an arbitrary composite core and arbitrary pairwise
coprime petals. A second elementary exact family is every strict
divisibility chain \(2\le n_1\mid n_2\mid\cdots\mid n_r\), for which
\(M=\sum_i1/n_i\), with explicit disjoint residues below.
3. (d) Exact finite table. Every one of the 511 nonempty sets
\(A\subseteq\{2,\ldots,10\}\) was exhaustively solved. The full table,
including a maximizing residue tuple for every row, is
erdos278_wave8q_table.csv. Its SHA-256 is
271706bf2cdb428370d74e6bd3b74f2710ede6739577fa77af392ce241bfca94.
A second, separately organized exhaustive computation reproduced all 511
answers. In particular,
\[ M(\{2,3,\ldots,10\})=\frac{69}{70}, \]
attained by residues
\[ (0,0,1,0,1,0,3,2,1) \quad\text{for moduli }(2,3,4,5,6,7,8,9,10). \]
The standalone standard-library checker is
Claim labels
- (a) elementary-rigorous: a complete proof is given here.
- (b) rigorous modulo the named theorem explicitly cited.
- (c) plausible/structural-unverified.
- (d) computational-only or source observation.
Step 0: mandatory live-page audit
(d) I fetched both the problem page and its discussion page through the
Bright Data anti-Cloudflare browser path. Direct datacenter curl was not
used for this audit.
The live page returned:
- status OPEN;
- 0 claimed proofs for this problem;
- Currently working on this problem: None;
- Interested in collaborating: None;
- likes, “looks difficult,” “looks tractable,” results-formalisable, and
working-on-formalisation markers: all None;
- formalised statement: No;
- four comments;
- last page edit: 20 January 2026.
Thus neither mandatory stop condition was present.
Exact current statement, verbatim
> Let \(A=\{n_1<\cdots > the maximum density of integers covered by a suitable choice of congruences > \(a_i\pmod{n_i}\)? > > Is the minimum density achieved when all the \(a_i\) are equal? Source: live problem #278, accessed 2026-07-28. (d, page transcription; b for the cited theorem.) The page says Simpson [Si86] observed that every choice has covered density at leastKnown result printed on the page
all \(a_i\) are equal. This settles the second question.
All four live comments
The site warns that comments are user content and are not verified.
1. JonahKlein, 3 March 2026. Simpson was apparently not first: the first
theorem of §5.3 of Halberstam--Roth, Sequences (1983 reprint), gives the
result and attributes it to a private communication from C. A. Rogers.
2. TerenceTao, 3 March 2026. Links to his exposition of Rogers' theorem.
3. Dogmachine, 26 August 2025. Gives an opinion that a simple universal
formula may not exist, comparing the issue with problems #345 and #434.
No proof or active-work declaration is made.
4. StijnC, 26 August 2025. Links arXiv:2508.18270 and explicitly describes
it as a non-waterproof argument that the first question may have no answer
“as hoped for.” It asks for opinions and does not claim a proof.
Discussion source:
accessed 2026-07-28.
Primary-source literature audit
The minimum half
(d) The original citation 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). The live page is used
as ground truth for the exact wording, as required.
(b) Simpson's cited paper exists:
R. J. Simpson, Exact coverings of the integers by arithmetic progressions,
Discrete Mathematics 59 (1986), 181--190,
DOI 10.1016/0012-365X(86)90079-890079-8).
The accessible primary
contains the result as Lemma 2.3. I read its proof: it counts intersections
over a common period by inclusion--exclusion and proves the minimum occurs
when every pair is compatible; all equal residues realize equality.
(b) Z. W. Sun's primary paper
A theorem concerning systems of residue classes,
Acta Math. Univ. Comenianae 60 (1991), 123--131, states the same inequality
as Lemma 1 and explicitly identifies it as Simpson's Lemma 2.3.
The JonahKlein comment is bibliographically consistent. Halberstam--Roth's
Sequences was first published by Clarendon Press in 1966 and reprinted with
minor corrections by Springer in 1983; the official
confirms the reprint. I could not inspect the paywalled pages 242--244
directly. Tao's
quotes the book's attribution as unpublished communication from C. A. Rogers
and gives a modern proof. None of the work below needs that inaccessible
copy, because Simpson's primary proof is accessible and was independently
checked.
The maximum half
(d, primary-source reading.) Stijn Cambie's three-page preprint is real:
Proving it is impossible; on Erdős problem #278,
arXiv:2508.18270 (2025). It does two relevant things:
- for \(\{3\}\cup\{3p:p\in P\}\), it reduces the optimum to partitioning
the factors \(1-1/p\) between the two unused classes modulo \(3\);
- it embeds instances satisfying conditions from V. Chvátal's
Hard knapsack problems.
Cambie's conclusion is evidence, not an impossibility theorem. The cited
Operations Research 28 (1980), 1402--1411, proves exponential lower bounds
for a specified class of algorithms combining branch-and-bound, dynamic
programming, and elementary divisibility arguments. It does not rule out all
algorithms or all forms of exact characterization. I therefore label the
preprint's “no general formula” conclusion (c), while its displayed
special-family calculation is (a).
(d, primary-source reading.) Geir Dahl,
Disjoint congruence classes and a timetabling application,
Discrete Applied Mathematics 157 (2009), 1702--1710, studies exactly the
pairwise-disjoint congruence feasibility problem motivated by subway
schedules. It proves special structural results and supplies an integer
programming model. The paper does not state that the general feasibility
problem is NP-complete. Exact-title and complexity searches found no source
containing the graph reduction below. This report does not assert
historical priority; it records the precise search miss.
(d) Filaseta--Ford--Konyagin--Pomerance--Yu,
Sieving by large integers and covering systems of congruences,
JAMS 20 (2007), 495--517, proves uniform positive uncovered-density results
for distinct moduli in \((N,KN]\). Those are strong asymptotic bounds for a
different restricted regime, not an exact formula for arbitrary finite
\(A\).
One tertiary March 2026 article surfaced in search claiming that ChatGPT
solved “#278,” but its names, date, Lean discussion, and Pomerance reference
all describe problem #728. The primary paper is explicitly
Resolution of Erdős Problem #728.
This is a numbering error in the tertiary article, not a claimed solution of
#278. The authoritative live #278 page remains OPEN with zero claimed proofs.
No primary paper located in exact-statement, title, citation, arXiv, and
disjoint-congruence searches claims a general answer to the maximum question.
(c) A literature search cannot prove absence of an unindexed result; this
is the scope of the miss.
Finite reformulation and elementary bounds
For a fixed set \(A=\{n_1,\ldots,n_r\}\), write
\[ L=[n_1,\ldots,n_r]. \]The union is \(L\)-periodic, so define
\[ M(A)=\frac1L\max_{0\le a_i(a, generalized CRT criterion.) Two classes intersect if and only if
\[ a_i\equiv a_j\pmod{\gcd(n_i,n_j)}. \tag{4} \]This is the standard two-modulus Chinese remainder criterion.
(a). Choosing all residues independently and uniformly gives
\[ 1-\prod_i\left(1-\frac1{n_i}\right) \le M(A)\le \min\left(1,\sum_i\frac1{n_i}\right). \tag{5} \]For the lower bound, fix \(x\). The probability that no chosen class contains
\(x\) is the product in (5); average over \(x\pmod L\). The upper bound is the
union bound.
(a). For two distinct moduli,
\[ M(\{m,n\})= \begin{cases} \dfrac1m+\dfrac1n,&\gcd(m,n)>1,\\[6pt] \dfrac1m+\dfrac1n-\dfrac1{mn},&\gcd(m,n)=1. \end{cases} \tag{6} \]When the gcd exceeds \(1\), choose incompatible residues. When it is \(1\),
the intersection is unavoidable and has density \(1/(mn)\).
NP-completeness of attaining the disjoint upper bound
Define DCC (Disjoint Congruence Classes):
> Input: pairwise distinct positive integers \(n_1,\ldots,n_r\), in binary.
> Decide whether residues \(a_i\pmod {n_i}\) can be chosen so that the
> resulting classes are pairwise disjoint.
Membership in NP
(a). A certificate is \(0\le a_i and test the negation of (4). Euclid's algorithm and modular reduction take polynomial time in the binary input length. (a, reduction; b for the source problem's NP-completeness.) Let \(G=(V,E)\), \(V=\{1,\ldots,r\}\). Use the common prime \(3\). Give every nonedge \(\{i,j\}\notin E\) its own prime \(q_{ij}\), and every vertex \(i\) its own private prime \(u_i>r\). Take all these auxiliary primes distinct and different from \(3\), and put These moduli are distinct and squarefree. Their pairwise gcds are Suppose \(G\) has a proper 3-colouring \(c_i\in\{0,1,2\}\). For each vertex, choose \(a_i\) by the ordinary CRT so that and, after orienting each nonedge \(i For an edge, its endpoints differ modulo \(3\); for a nonedge, they differ modulo \(q_{ij}\). Equations (4) and (8) therefore make every pair of classes disjoint. Conversely, suppose the classes are pairwise disjoint. If \(\{i,j\}\in E\), then (8) and (4) force Thus \(a_i\bmod3\) is a proper 3-colouring of \(G\). Hence There are only \(O(r^2)\) auxiliary primes. The first \(O(r^2)\) primes have polynomial magnitude, and each \(n_i\) has \(O(r\log r)\) bits, so (7) is a polynomial-time reduction. Graph 3-colourability is NP-complete by Garey--Johnson--Stockmeyer, Some simplified NP-complete graph problems90059-1), Theoretical Computer Science 1 (1976), 237--267. Therefore DCC is NP-complete. (a). Over one common period, let \(k_x\) be the number of chosen classes containing \(x\). Then Equality with \(\sum_i1/n_i\) occurs exactly when all classes are pairwise disjoint. In construction (7), \(n_i>3r\), so Consequently, Thus deciding whether the maximum reaches its simplest possible upper bound is NP-complete, and exact evaluation of \(M(A)\) is NP-hard. This does not prove that no formula exists. It proves the more precise conditional wall: a generally evaluable polynomial-time exact formula would imply \(P=NP\). A formula containing an NP-hard minimization, such as (1), is entirely possible. Let where \(\gcd(m,q_i)=1\) for every \(i\) and \(\gcd(q_i,q_j)=1\) for \(i\ne j\). The value \(q_i=1\) is allowed. Then (1) holds. (a). A common period is By the CRT, a residue \(x\pmod L\) has independent coordinates modulo \(m,q_1,\ldots,q_r\). A chosen class \(a_i\pmod {mq_i}\) fixes two coordinates: Fix a core fibre \(x\equiv c\pmod m\). Only indices with \(c_i=c\) can cover points in this fibre. Their petal coordinates are independent, so the conditional fraction left uncovered is Average over the \(m\) equally sized core fibres: The petal residues \(b_i\) do not affect (13). Conversely, every assignment \(\phi(i)=c_i\) is realizable: choose any \(b_i\) and apply the two-modulus CRT separately for each \(i\). Minimizing the uncovered expression proves (1). (a). For \(m=2\), \((q_1,q_2,q_3)=(3,5,7)\), the optimal partition is \(\{3\}\mid\{5,7\}\). Thus The classes attain this value. (a). The complete graph \(K_4\) in the reduction gives Four classes cannot be pairwise disjoint because all pairwise gcds are \(3\). Formula (1), with the optimal core buckets \(\{5\},\{7\},\{11,13\}\), gives One maximizing tuple is The checker counts exactly 2521 covered residues modulo 15015. When \(m=1\), (1) recovers the familiar fact that pairwise coprime moduli have choice-independent union density When \(m\ge r\), putting each index in a different core fibre makes the classes disjoint and reaches \(\sum_i1/(mq_i)\). If with strict inequalities, then (a). Define For \(j>1\), \(a_j-a_1\equiv1\pmod {n_1}\). For \(2\le i Since \(\gcd(n_i,n_j)=n_i\), criterion (4) shows that all classes are pairwise disjoint. They attain the union bound, proving (15). The reciprocal sum is automatically at most one because every strict divisibility step at least doubles the modulus. For example, \((2,4,12,24)\) uses residues \((0,1,3,7)\). Sets containing \(1\) have \(M(A)=1\) trivially, so the computation covers all 511 nontrivial nonempty sets \(A\subseteq\{2,\ldots,10\}\). (d). The global period is For every class \(a\pmod n\), the checker stores its 2520-bit incidence mask. It recursively chooses “exclude \(n\)” or “include \(n\) with residue \(a\).” For the first included modulus it fixes \(a=0\); this loses nothing, because translating all residues by the negative of that first residue is a bijection preserving union size. Every later included modulus tries all its residues. The number of normalized complete branches is exactly At every leaf the population count of the union mask updates the optimum for that subset. This proves exhaustiveness of the finite search, subject only to ordinary integer/bit-operation correctness. The second pass does not reuse the global masks or include/exclude tree. For each of the 511 sets separately it constructs new masks modulo that set's own lcm, fixes the first residue to zero, and enumerates the direct Cartesian product of all later residues. It reproduces every density in the CSV. “Disjoint” counts rows attaining the raw upper bound \(\sum_{n\in A}1/n\). No row in this range covers all integers. | \(|A|\) | sets | distinct maximum densities | disjoint rows | minimum \(M(A)\) | maximum \(M(A)\) | |---:|---:|---:|---:|---:|---:| | 1 | 9 | 9 | 9 | \(1/10\) | \(1/2\) | | 2 | 36 | 29 | 14 | \(1/5\) | \(3/4\) | | 3 | 84 | 49 | 4 | \(14/45\) | \(7/8\) | | 4 | 126 | 59 | 0 | \(43/105\) | \(11/12\) | | 5 | 126 | 57 | 0 | \(8/15\) | \(23/24\) | | 6 | 84 | 44 | 0 | \(67/105\) | \(35/36\) | | 7 | 36 | 22 | 0 | \(82/105\) | \(44/45\) | | 8 | 9 | 7 | 0 | \(94/105\) | \(59/60\) | | 9 | 1 | 1 | 0 | \(69/70\) | \(69/70\) | The four disjoint triples are For the full set, the witness printed above covers 2484 of 2520 residues. The verifier also checks the random lower bound and union upper bound in (5), formula (6) for all 36 pairs, every CSV witness, and the table hash. The same run also: systematically generated common-core cases; checked all \(3^r\) colourings, and verified the CRT disjointness witness whenever a colouring exists; \((15,21,33,39)\) and independently enumerated its exact maximum (14). Reproduction: The complete run took 11.2 seconds on this VM and ended with (a). Equation (3) is also the following exact 0--1 program. Use one variable \(x_{i,a}\) for choosing residue \(a\pmod {n_i}\), and one variable \(y_t\) for whether \(t\pmod L\) is covered: finite characterization, but \(L\) and the choice space can be exponential in the binary input. The precise barriers are now: 1. Rogers/Simpson compression solves the minimum by increasing compatibility. There is no reverse compression for the maximum: the construction (7) makes the required incompatibilities encode arbitrary graph 3-colourings. 2. Inclusion--exclusion is exact, but which intersections are nonempty depends on the global residue assignment. Optimizing those compatibility patterns already contains the NP-complete DCC subproblem. 3. Formula (1) shows that even a very structured common-core family reduces to a multiplicative multiway partition problem. Cambie's knapsack observation captures this phenomenon, but does not by itself prove unrestricted complexity. A naive extension of the global table illustrates, but does not define, the wall. The normalized branch counts would be 104,557,346 for moduli through 11 and 1,359,245,487 through 12. The common bit period jumps from 2520 to 27720 at 11. Scaling the measured bit-mask work linearly in branch count and period length gives roughly \(0.2\) core-hours for the through-11 table and about \(3\) core-hours for through-12 in this Python implementation. These were not run, in accordance with the few-CPU-minutes limit; C, SAT, or ILP implementations could change the constants. What remains open is a useful uniform characterization or set of sharp general bounds for \(M(A)\), not mere per-instance decidability. The NP-completeness theorem rules out a polynomial-time exact evaluator unless \(P=NP\), but it neither closes Erdős and Graham's open-ended question nor rules out formulas whose evaluation is itself exponential. PARTIAL: Proved an NP-complete upper-bound-attainment subproblem, derived exact common-core and divisibility-chain formulas, and exhaustively certified all 511 nontrivial sets with maximum modulus at most 10; the unrestricted maximum-density characterization remains open.Reduction from graph 3-colourability
Consequence for #278
Exact common-core formula
Theorem
Proof
Examples
Exact divisibility-chain family
Theorem and construction
Exhaustive table for \(\max A\le10\)
Exhaustive algorithm
Summary
Independent structural checks
python3 runs/erdos278_wave8q_reverify.py
ALL CHECKS PASSED.Exact general formulation and the remaining wall