#203: the cosets of 5 and 7 always overlap — no covering system has period ≤ 65,520

The problem (erdosproblems.com/203, OPEN, Erdős–Graham 1980). Is there an integer m ≥ 1 with gcd(m, 6) = 1 such that 2^k3^ℓm + 1 is composite for every k, ℓ ≥ 0? For the one-exponent version (2^km + 1) the answer is yes — Sierpiński numbers, built from a covering system: finitely many primes such that every exponent lands in a residue class killed by one of them. Every known Sierpiński number comes from a covering, sometimes helped by the algebraic factorisations available when m is a perfect power, and Filaseta, Finch and Kozek conjecture there is no other kind. So the question for #203 is whether a two-dimensional covering exists. The live thread already carried two computational partials when we read it (12 October): AnimishSharma (21 Jun 2026) proved |⟨2, 3⟩ mod p| = lcm(ord_p 2, ord_p 3) and the density condition Σ 1/e_p ≥ 1, and excluded small pools by it; veljjanoski (15 Sep 2026, with a repository) built complete prime pools from cyclotomic gcds, ran greedy-plus-local-search coset searches that plateau at 71.7% coverage with the 31 primes of period 5040 and 76% with the 55 primes of period 55440, and observed that the lattices involved are almost never nested — "the chains that make 1D Sierpiński coverings work […] have no analogue here". Neither claims to prove nonexistence. This entry turns the structural observation into a proof for every small period.

The setup. For a prime p ≥ 5 let H_p = ⟨2, 3⟩ ≤ (ℤ/p)^×, e_p = |H_p| = lcm(ord_p 2, ord_p 3), and L_p = {(k, ℓ) ∈ ℤ² : 2^k3^ℓ ≡ 1 (mod p)}, the kernel of the surjection ℤ² → H_p, hence a sublattice of index e_p. For a fixed m the set of (k, ℓ) with p | 2^k3^ℓm + 1 is empty or a single coset C_p of L_p, of density 1/e_p. Lemma 1. The prime 2 divides 2^k3^ℓm + 1 exactly when k = 0, and 3 divides it only when ℓ = 0; so if finitely many primes ≥ 5 (and any algebraic free sets, below) certify compositeness for all large k, ℓ, then their cosets together with the free sets cover the quadrant k, ℓ ≥ 1 and hence, being invariant under the lattice ∩ L_p, all of ℤ². Lemma 2. For distinct primes p, q ≥ 5 the kernel of (k, ℓ) ↦ 2^k3^ℓ mod pq is L_p ∩ L_q, so its index is e_pq := |⟨2, 3⟩ ≤ (ℤ/pq)^×|; therefore C_p ∩ C_q is empty or has density exactly 1/e_pq, and when e_pq = e_pe_q the map onto H_p × H_q is onto, so the two cosets meet whatever residues m has modulo p and q.

Theorem A (elementary). 2 has order 12 modulo 35 and 3 is not a power of 2 modulo 35 (the powers are 1, 2, 4, 8, 16, 32, 29, 23, 11, 22, 9, 18), so ⟨2, 3⟩ is all of (ℤ/35)^×: e₃₅ = 24 = e₅ · e₇. Hence for every m the cosets of 5 and 7 overlap in density exactly 1/24, and any covering system that uses both 5 and 7 has Σ 1/e_p ≥ 1 + 1/24 — its union has density at most (1/4 + 1/6 − 1/24) + Σ_p≠5,7 1/e_p. That is the whole proof; a reader can check it in a minute. (Of the 465 prime pairs in the 5040 pool, 271 are transversal like this one; the other 194 share a common quotient and can be chosen disjoint, so the argument needs the right pair.)

Complete pools, and the smallest period. A covering has a period N = lcm e_p, and every prime it can use divides gcd(2^N − 1, 3^N − 1); factoring that number completely gives the complete pool for N (for the named periods below it was split along the cyclotomic pairs gcd(Φ_a(2), Φ_b(3)) with the product of the found prime powers checked equal to the gcd; all pool primes are below 10⁷, so primality is deterministic), with each prime's lattice L_p = {uk + vℓ ≡ 0 (mod e_p)} written out. We did this for every N ≤ 65,520 (all 65,520 gcds fully factored; the first version of this entry stopped at 30,000, the scan from 30,001 to 65,520 landed the same afternoon) and for the natural larger periods. The smallest N whose pool has density ≥ 1 is N = 5040: 31 primes, Σ 1/e_p = 143/140 = 1.0214 (the runners-up below 5040 are 3960 at 0.933 and 3600 at 0.930; the forum figures agree with ours wherever both exist, and every prime with e_p ≤ 5040 is below 11.4 million, so AnimishSharma's cap of p ≤ 5·10⁷ was never binding). Since 143/140 < 25/24, a covering of period dividing 5040 cannot use both 5 and 7; without 7 its density is at most 143/140 − 1/6 < 1, without 5 at most 143/140 − 1/4 < 1. So Theorem A with the density condition rules out every covering system with period dividing 5040, and with the scan every period up to 5040, and in the same breath the pools for 10080, 20160 and 40320 (1.0319, 1.0367, 1.0411, all below 25/24 and all containing 5 and 7).

Theorem B (exact maxima over blocks; computer-assisted). For a block B of primes let U(B) be the largest density the union of their cosets can have, over all coset choices — a finite maximum, computed exactly by brute force on the torus (ℤ/T)², T = lcm e_p. The union of a covering P has density at most U(P ∩ B) + Σ_p∈P∖B 1/e_p, and U is monotone, so a covering of period N needs U(B ∩ pool(N)) + density(N) − Σ_B∩pool(N) 1/e_p ≥ 1 (and a period excluded this way excludes all its divisors). The values: {5, 7}: 9/24 (Theorem A again); {5, 7, 11, 13}: 1765/3600, a forced loss of 0.1097; adding 17: 30580/57600, loss 0.1316; adding 19: 294900/518400, loss 0.1492; adding 31: 303336/518400, loss 0.166250 — six million coset configurations on a 720 × 720 torus, every one of the 128 subsets of these seven primes tabulated so the bound applies to whichever of them a given period admits. Consequences: any covering whose period is a multiple of 720 — equivalently, one that can use all seven primes — needs a pool of density ≥ 1.16625; the complete pool for period 55440 (55 primes, 21493/18480 = 1.163041) misses by 0.003, and 60480 (1.0633) and 65520 (1.1035) by more; and no covering system has period N for any N ≤ 65,520, each N checked against its own pool with its own sub-block. Of the larger periods we computed, the ones this block does not exclude are 110880 (1.1777), 166320 (1.1913), 221760 (1.1826), 332640 (1.2064) and 720720 (99 primes, 1.2490); periods between 65,520 and 110,880 were not computed. One more reading of the same numbers: the 31 primes of period 5040 — the pool the local searches plateau on at 71.7% — can cover at most 85.5% of ℤ² however their cosets are chosen.

Theorem C (perfect-power m). The setup here is veljjanoski's (repository README): if m = t^N₀ with N₀ maximal, the identities X^q + 1 = (X + 1)(…) for odd primes q | N₀ and 4Y⁴ + 1 = (2Y² + 2Y + 1) (2Y² − 2Y + 1) for 4 | N₀ make the sets qℤ² and {k ≡ 2 (4), ℓ ≡ 0 (4)} free (by Capelli's theorem, applied to 2^k3^ℓt^N₀ + 1 as a polynomial in t, these are the only such factorisations), and the price is that m ≡ −(2^k3^ℓ)⁻¹ (mod p) must be a gcd(N₀, p − 1)-th power residue, which removes most cosets. What is new is the exact computation: sweeping every value of gcd(N₀, 720) with the free sets included and the inadmissible cosets removed, the block {5, 7, 11, 13, 17, 19} never covers more than 0.586296 — for N₀ divisible by 720 each of these six primes has exactly one admissible coset — against 0.568866 without the free sets, so the residue condition eats almost all of the free sets' nominal 0.147 and leaves a net gain of 0.017. Crediting the free sets of every other odd prime at their full density (Σ 1/q², 0.0511 for q ≥ 7) without charging for their residue conditions, a perfect-power covering whose pool contains the block needs density(N) ≥ 1.0806, and the periods whose pool lacks 11, 17 or 19 were run with their own sub-block (27720, which lacks 17, needed the six primes {5, 7, 11, 13, 19, 31}: 0.565926). Result: no covering system has period N for any N ≤ 65,520; with the perfect-power factorisations allowed, the same holds for every N ≤ 65,520 except 55440 and 65520 themselves, which this block does not exclude in the perfect-power variant (40320, 45360, 50400 and 60480 are excluded both ways).

Labels and controls. Lemmas 1–2 and Theorem A are (a) elementary. The pools and the all-N scan are (d) exact integer computations (complete factorisations; a completeness certificate for the named pools), and e_p was recomputed by a second route (sympy's multiplicative orders) for the whole 5040 pool. The block maxima are (d) computer-assisted: the four-, five- and six-prime values by three independent implementations — a C bitset brute force, a numpy brute force that rebuilds the masks from a meshgrid and re-counts each witness literally, and a Python big-integer brute force — with OR-tools CP-SAT additionally proving the four- and five-prime optima (1765, 30580); the seven-prime value 303336 by the C and big-integer brute forces (6,220,800 configurations each, 64,800 optimal) and, independently, by the hostile referee's own pruned exact search on the 43,200-point quotient group, which found the same maximum and the same 64,800 optimal configurations. The C tool refuses to run unless every coset bitset has exactly T²/e_p points, and the counts of optimal configurations scale by exactly e₅ = 4 between the translation-reduced and the full enumeration, as they must. The perfect-power sweep's fixed-set bitmaps were re-counted in numpy for the fully forced configuration (303936/518400, equal). Two separately briefed Opus seats read this before it went up: an evidence seat that recomputed the pools, e₃₅, e₉₁, e₅₅ and the small-block maxima from scratch (every number agrees), and a hostile judgment seat whose findings — an overclaimed "every covering" in the first draft's title, the missing prime 2 in Lemma 1, the 27720 sub-block, a wrong-direction sentence about the free sets, the attribution of the Theorem C setup — are all applied here; both reports are in the bundle.

What is ours, and what is not. Ours: Lemma 2, Theorem A, the exact block maxima and the three theorems' consequences — a proof, not a search, that the covering mechanism fails at every period up to 65,520, and the bound Σ 1/e_p ≥ 1.16625 for any covering with 720 | N. Not ours: the subgroup formula, the density condition and the first exclusions (AnimishSharma); the complete-pool method, the perfect-power setup, the heuristic searches and the no-nested-chains observation (veljjanoski); and of course the problem. Not claimed: that no m exists. The pool densities grow without bound as the period grows (Σ 1/e_p over all primes diverges), so the covering route is not dead; what this shows is that the forced waste grows too — the question that would close the route is whether density(N) − (forced loss of pool(N)) stays below 1 for every N. The eight-prime block S7 ∪ {37} landed on 14 October: the largest union of eight cosets covers 312,136 of the 518,400 points of period 720 (density 0.602114, forced loss 0.177052, 129,600 optimal coset choices; the C enumeration of all 223,948,800 choices, with the winning witness re-counted independently as a big-integer bitset) — short of the 0.21 that would have decided the four computed pools 110880–332640 on its own; those pools have since fallen to the line lemma. The exact maximum over all 15 primes of period 720 is the remaining rung.