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.”

1. (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.

1. (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 erdos278_wave8q_reverify.py.

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<n_r\}\) be a finite set of positive integers. What is 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.

Known result printed on the page

(d, page transcription; b for the cited theorem.) The page says Simpson [Si86] observed that every choice has covered density at least

where brackets denote least common multiple, and that equality occurs when 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.

1. TerenceTao, 3 March 2026. Links to his exposition of Rogers' theorem.
2. 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.

1. 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: problem #278 discussion, 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 University of Adelaide thesis 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 Springer record confirms the reprint. I could not inspect the paywalled pages 242--244 directly. Tao's Rogers theorem exposition 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 Chvátal paper, 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

The union is \(L\)-periodic, so define

Thus the natural density exists and is exactly a finite rational number.

(a, generalized CRT criterion.) Two classes intersect if and only if

This is the standard two-modulus Chinese remainder criterion.

(a). Choosing all residues independently and uniformly gives

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,

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<n_i\). For every pair, compute the gcd and test the negation of (4). Euclid's algorithm and modular reduction take polynomial time in the binary input length.

Reduction from graph 3-colourability

(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<j\),

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.

Consequence for #278

(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.

Exact common-core formula

Theorem

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.

Proof

(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).

Examples

(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)\).

Exact divisibility-chain family

Theorem and construction

If

with strict inequalities, then

(a). Define

For \(j>1\), \(a_j-a_1\equiv1\pmod {n_1}\). For \(2\le i<j\),

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)\).

Exhaustive table for \(\max A\le10\)

Sets containing \(1\) have \(M(A)=1\) trivially, so the computation covers all 511 nontrivial nonempty sets \(A\subseteq\{2,\ldots,10\}\).

Exhaustive algorithm

(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.

Summary

“Disjoint” counts rows attaining the raw upper bound \(\sum_{n\in A}1/n\). No row in this range covers all integers.

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.

Independent structural checks

The same run also:

• brute-compared formula (1) against direct residue enumeration in 110

systematically generated common-core cases;

• checked explicit chain constructions;
• generated all 1099 labelled graphs on 1 through 5 vertices;
• for each graph, reconstructed (7), checked every gcd in (8), exhaustively

checked all \(3^r\) colourings, and verified the CRT disjointness witness whenever a colouring exists;

• checked the \(K_4\) no-colouring instance

\((15,21,33,39)\) and independently enumerated its exact maximum (14).

Reproduction:

python3 runs/erdos278_wave8q_reverify.py

The complete run took 11.2 seconds on this VM and ended with ALL CHECKS PASSED.

Exact general formulation and the remaining wall

(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:

Its optimum divided by \(L\) is exactly \(M(A)\). This is an effective 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.

1. 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.

1. 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.