#203: along the lines of slope 1 the primes 5 and 7 leave half the lines to the rest of the pool — an elementary cut excludes every covering system of period ≤ 65,520 a second way and closes the five open pools up to 720720

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? The only known way to make such an m is the one that makes Sierpiński numbers — a covering system, possibly helped by the algebraic factorisations available when m is a perfect power: finitely many primes p, each killing one coset of the lattice L_p = {(k, ℓ) : 2^k3^ℓ ≡ 1 (mod p)} of index e_p = |⟨2, 3⟩ mod p|, the cosets together covering ℤ². Our 12 October entry proved that no covering system has period N = lcm e_p for any N ≤ 65,520 — by a forced overlap of the primes 5 and 7 (Theorem A) and exact maximum-union computations over blocks of up to seven primes (Theorem B) — and left five computed pools standing: periods 110880, 166320, 221760, 332640 and 720720, with 60 to 99 primes and Σ 1/e_p up to 1.249, because a seven-prime block cannot see what ninety other primes do. This entry projects the covering onto lines, where every prime is visible at once. One elementary consequence — the primes 5 and 7 seen along the lines of slope 1 — closes all five with a sum a reader can recompute; exact integer programs give sharper upper bounds at some periods (5040 to 51480, 110880, 720720) and weaker ones at others (55440, 166320–332640) — the page quotes both. No covering system has period N for any N ≤ 65,520, nor for any divisor of 110880, 166320, 221760, 332640 or 720720 = lcm(1, …, 16) — every period up to 65,520 and 17 periods above it (the four smaller named ones are not divisors of 720720: they carry 2⁵, 2⁶ or 3³), including every pool we know to have been computed. Pure covering systems only; the perfect-power variant, which the earlier entry left open at 55440 and 65520, is discussed below and stays open there — this entry claims nothing new for it. The problem stays open.

The lemma (standard; see attribution). Let Λ ≤ ℤ² be any subgroup, G = ℤ²/Λ, and for each prime let S_p = (L_p + Λ)/Λ ≤ G. A coset C_p of L_p meets a cell y + Λ either not at all or in a single coset of L_p ∩ Λ; so inside every cell it meets, C_p has the same density w_p(Λ) = 1/[Λ : L_p ∩ Λ] = [G : S_p]/e_p, and the cells it meets form one coset of S_p in G. Hence if the cosets cover ℤ², every cell g ∈ G receives intensity W(g) = Σ_{p : g ∈ π(Cp)} w_p(Λ) ≥ 1 — a covered cell is covered by the cosets that meet it, and their union has density at most the sum of their densities there. (Proof of the first sentence: (y + Λ) ∩ (x + L_p), if it contains z, equals z + (Λ ∩ L_p); and e_p = [ℤ² : L_p + Λ]·[L_p + Λ : L_p] = [G : S_p]·[Λ : Λ ∩ L_p] by the second isomorphism theorem.) Averaging over G gives back the density condition Σ 1/e_p ≥ 1; the lemma is sharper exactly when the images π(C_p) cannot be arranged to spread the intensity evenly. Writing V_Λ(P) for the largest value of min_g W(g) over all choices of the cosets (every choice arises from some m, independently prime by prime), V_Λ(P) < 1 means no covering system uses a subset of P — for P the complete pool of a period N, none has period N or any divisor of N. The family is monotone (on a coarse cell W is the average of W over the finer cells inside it, and a minimum is at most an average) and exact at the bottom (Λ = ∩ L_p is the covering problem itself); at the top, Λ = ℤ², it is the density condition.

Lines. Λ = ℤd for a primitive direction d = (a, b); the cells are the lines parallel to d, indexed by τ = bk − aℓ ∈ ℤ. Along a line 2^k3^ℓ runs through a coset of ⟨g_p⟩, g_p = 2^a3^b, so C_p meets one residue class of lines modulo i_p = [⟨2, 3⟩ : ⟨g_p⟩] and, on each of those lines, one residue class modulo ord_p(2^a3^b): intensity w_p = 1/ord_p(2^a3^b) = i_p/e_p on the lines it reaches, nothing on the others. In direction (1, 0) a prime kills, on the lines ℓ ≡ t_p (mod e_p/ord_p 2) and only there, the class k ≡ r (mod ord_p 2). Primes for which 2^a3^b generates ⟨2, 3⟩ reach every line and contribute a constant; the others are lumps the adversary must place. Coarsening — averaging over a progression τ ≡ c (mod M) — replaces i_p by gcd(i_p, M) and w_p by gcd(i_p, M)/e_p: the lemma again for a coarser Λ, so still necessary, and exact when lcm i_p divides M.

Theorem D (the 5–7 cut; elementary, no solver). Take direction (1, 1), so g_p = 6 and the lines are τ = k − ℓ. Since 6 ≡ 1 (mod 5), the prime 5 covers completely the lines τ ≡ t₅ (mod 4) and nothing else; since 6 has order 2 mod 7 and e₇ = 6, the prime 7 has intensity 1/2 on the lines τ ≡ t₇ (mod 3). Coarsen to M = 60 and look at the 30 of every 60 line classes that neither 5 nor 7 touches. On those the whole burden falls on the other primes of the pool, and the average intensity they can deliver there is at most B(P) = Σ_{p ≠ 5, 7} (gcd(i_p, 60)/e_p) · max_c |{τ in the 30 : τ ≡ c (mod gcd(i_p, 60))}|/30 — a finite sum over the pool, independent of how m places anything. A minimum is at most an average, so some line receives at most B. The values: every one of the 26 periods ≤ 65,520 whose pool has density ≥ 1 has B ≤ 3965/4752 = 0.8344 (at 55440; the other 25 are below 0.79), and 110880: 35303/41580 = 0.8490 · 166320: 0.8682 · 221760: 10823/12672 = 0.8541 · 332640: 0.8835 · 720720 (99 primes, density 1.249): 11255/12012 = 0.9370. All below 1, so none of these pools, nor any sub-pool, admits a covering system. Together with the earlier entry's scan (every other N ≤ 65,520 has pool density below 1) and its completeness certificates for the pools, that is the whole proof of the headline; the cut was found by the hostile referee of this entry and recomputed by us from the pool files (fivesevencut.py, forty lines; the two programs share no code). It is Theorem A's forced overlap of 5 and 7 (e₃₅ = 24 = e₅e₇) seen line by line: along slope 1 the two primes between them reach only half of the line classes, so the other half must be carried by the rest of the pool alone — where the earlier entry could only charge an overlap of 1/24 of the plane, here half the lines get nothing from either prime.

The solver values (computer-assisted; exact where the solver closed, otherwise proven upper bounds). V for a direction is a rational, computed as a max–min integer program (one-hot coset variables for the lumpy primes, one constraint per line class, CP-SAT; an OPTIMAL value is exact, and a proven upper bound below 1 is a proof whether or not the optimum closed), and as a feasibility program (every line ≥ 1 as hard constraints; INFEASIBLE is a proof). Sixteen directions were run for each of the 26 periods ≤ 65,520; the five open pools got direction (1, 1) (110880 also the two axes). Every one of the 26 periods ≤ 65,520 is excluded, and direction (1, 1) always does it (exact at 22 of them, a bound at 27720, 41580, 55440 and 65520): the worst line at 5040 gets exactly 2671/5040 = 0.530; at 55440 the proven bound is ≤ 3001/3465 = 0.866 (Theorem D: ≤ 0.834; best choice found 0.667). But not every direction excludes every period: at 55440 the adversary can balance the axis directions and (2, 3) (witnesses re-counted at 1.027, ≥ 1.064 and ≥ 1.030), at 65520 the direction (2, −3) (≥ 1.006), and over all 416 period–direction pairs of the 26 periods, 412 are excluded (a proven bound below 1 or a refuted feasibility program), 4 admit a balanced coset choice (re-counted witnesses ≥ 1: 55440 (1,0) 1.0637; 55440 (0,1) 1.0274; 55440 (2,3) 1.0301; 65520 (2,-3) 1.0062), and none is undecided. The feasibility program was run on 416 of them as the second instrument: CP-SAT refuted 412, HiGHS 347. The five open pools fall in direction (1, 1): 110880 (60 primes, density 1.1777): proven max ≤ 5977/7392 = 0.8086 · 166320 (72, 1.1913): ≤ 10883/11880 = 0.9161 · 221760 (68, 1.1826): ≤ 197957/221760 = 0.8927 · 332640 (80, 1.2064): ≤ 45847/47520 = 0.9648 · 720720 (coarsened to M = 27720): ≤ 651467/720720 = 0.9039; the best coset choices the solver found reach only 0.68–0.77 on their worst line; none of these five optima closed, and at 166320, 221760 and 332640 Theorem D's B is the sharper bound. The axis directions do not do it at 110880 ((0, 1) is feasible at 1.0528, re-counted; (1, 0) at ≥ 1.0929) — the adversary balances those; (1, 1) is where the heavy lumps live. The referee's own runs at the coarse modulus M = 60 close exactly (0.756 at 110880 to 0.842 at 720720, optimal in at most 3 s — sharper than the exact-modulus bounds above), and its feasibility versions were refuted by HiGHS and by its own branch-and-bound in 8–17 nodes. HiGHS on our max–min program: at 110880 its dual bound 101623/110880 = 0.9165 excludes independently; at 166320 it did not get below 1 in 25 minutes (1.160) — recorded as a failure of the second solver on that form, which is why the feasibility form was run. The feasibility form (every line ≥ 1, hard) on the five pools in direction (1, 1): 110880: CP-SAT INFEASIBLE in 12 s, HiGHS infeasible · 166320: CP-SAT INFEASIBLE in 24 s, HiGHS infeasible · 221760: CP-SAT INFEASIBLE in 28 s, HiGHS at its time limit · 332640: CP-SAT INFEASIBLE in 24 s, HiGHS at its time limit · 720720: CP-SAT INFEASIBLE in 36 s, HiGHS at its time limit.

Perfect powers. The free sets of Theorem C (qℤ² for odd primes q | N₀, and the coset (2, 0) + 4ℤ²) are cosets of lattices too, so the lemma applies with them credited in full and their residue price (which Theorem C showed eats almost all of them) ignored — more generous to the adversary than the truth, hence still a proof: qℤ² is a fixed-class lump on the lines τ ≡ 0 (mod q) of intensity 1/q, uniform 1/q² after coarsening by a modulus it does not divide, and we credit every odd prime at once (closed form Σ_{q odd} 1/q² = P(2) − 1/4 with P(2) = Σ_p 1/p² the prime zeta value, rounded up). Result so far: with the free sets credited in full this relaxation excludes the variant for 65520 (direction (1,1): max 0.8322, 3 of 15 directions exclude); 5040 (direction (1,1): max 0.6937, 12 of 16 directions exclude); 7920 (direction (1,1): max 0.7139, 9 of 16 directions exclude); 10080 (direction (1,1): max 0.7042, 10 of 16 directions exclude); 15120 (direction (1,1): max 0.7472, 8 of 16 directions exclude); 15840 (direction (1,1): max 0.7173, 9 of 16 directions exclude); 18480 (direction (1,1): max 0.6473, 11 of 16 directions exclude); 20160 (direction (1,1): max 0.7088, 10 of 16 directions exclude); 23760 (direction (1,1): max 0.7366, 8 of 16 directions exclude); 25200 (direction (1,1): max 0.7681, 6 of 16 directions exclude); 27720 (direction (1,1): max 0.7306, 10 of 16 directions exclude); 30240 (direction (1,1): max 0.7679, 5 of 16 directions exclude); 31680 (direction (1,1): max 0.7201, 9 of 16 directions exclude); 35280 (direction (1,1): max 0.7024, 9 of 16 directions exclude); 36960 (direction (1,1): max 0.6587, 11 of 16 directions exclude); 39600 (direction (1,1): max 0.7499, 8 of 16 directions exclude); 40320 (direction (1,1): max 0.7135, 8 of 16 directions exclude); 41580 (direction (1,1): max 0.6730, 11 of 16 directions exclude); 45360 (direction (1,1): max 0.7912, 5 of 16 directions exclude); 46800 (direction (1,1): max 0.7118, 9 of 16 directions exclude); 47520 (direction (1,1): max 0.7400, 8 of 16 directions exclude); 50400 (direction (1,1): max 0.7815, 6 of 16 directions exclude); 51480 (direction (1,3): max 0.7223, 9 of 16 directions exclude); 60480 (direction (1,1): max 0.7737, 5 of 16 directions exclude); 63360 (direction (1,1): max 0.7250, 9 of 16 directions exclude) — label (c), plausible but unverified: the perfect-power encoding (fixed-class lumps + the rounded-up tail) was not part of the referee's review and has had no second seat; it is in the bundle for one. It does NOT exclude it for 55440 (balanced coset choices exist in several directions, the best found 1.2461; the (1, 1) bound sits above 1) — crediting every free set without its residue price is simply too generous there, so the perfect-power variant stays exactly where the 12 October entry left it: open at 55440 and 65520, excluded below by Theorem C. This entry claims nothing new for it.

Labels and controls. The lemma, its instances, the coarsening rule and Theorem D are (a) elementary; B(P) is a finite sum recomputed by two independent programs (the referee's and ours), and the lattice-image claim of the torus instance was checked by enumeration. The solver values are (d) computer-assisted: CP-SAT with exact integer scaling, every witness it returns re-counted on every line by a loop that shares nothing with the solver (it uses the (i_p, w_p) data, whose formulas the referee verified by 448 direct enumerations of 2^k3^ℓ mod p); HiGHS solving the same program as a second solver on every direction of the 5040 pool (15 of 16 to optimality, agreeing; the 16th agreeing at its time limit), on three directions of the 720 pool (agreeing), on 110880 and 166320 as said above, and on the feasibility form where it finished; exhaustive enumeration only on the controls and the first seven primes of the 720 pool on a 12 × 12 torus (every published row has more coset choices than that allows). Controls: the classical covering 0 (2), 0 (3), 1 (4), 3 (8), 7 (12), 23 (24) as full-weight classes gives V = 1 and the moduli {2, 3, 4, 8}, which leave a point bare, give 0; shifting the constant part by 1/7 shifts V by exactly 1/7; the four cosets of L₅ entered as four primes give V = 1 in all 17 directions, plus the six of L₇ give 2, and dropping one of those in direction (0, 1) gives exactly 11/6; the torus value did not exceed its line projection on the instance tested. A hostile Opus referee with tools read the lemma, the encoding and the verdict logic before this went up: it recomputed every pool from scratch (33 pools, 0 errors), verified the line formulas and the coarsening rule by 448 direct enumerations of 2^k3^ℓ mod p (primes with e_p ≤ 240 from three pools, eight directions), ran its own 2-D brute force on (ℤ/60)² with real primes against the solver (31 instances on five- and six-prime sub-pools, 0 mismatches), matched three of our optima with its own enumerator, and returned HOLDS WITH FIXES. Its fixes: a false "every direction" sentence (gone), controls that never exercised fractional weights (the partition controls above), a re-count test wrong on time-limited runs (fixed), overstated claims about which second checks had run (this paragraph now says exactly what ran), the missing scope sentence (added), the attribution (below), and its finding that the second solver had failed to bound 166320's max–min form (reported above) — and its Theorem D is now the proof. Not decided by solver: the coarse torus (ℤ/60)² with all 99 primes of 720720 — CP-SAT neither found a coset choice reaching 1 on every cell nor proved there is none in 25 minutes, although Theorem D shows it is infeasible.

What is ours, and what is not. The lemma is the classical restriction of a coset cover to the cosets of a subgroup (B. H. Neumann 1954; Tomkinson; Z.-W. Sun); on this very thread AnimishSharma observed that ℓ = 0 makes m a Sierpiński number (the lemma on one line, unweighted) and veljjanoski used a shear and a "strip" family of primes aligned with one direction. Ours: the weighted condition on every line of every direction over the whole pool, its exact max–min and feasibility forms, the computed exclusions — the second proof for every period up to 65,520 and, as far as we and the referee found, the first for the five open pools and their divisors — and, with the referee, Theorem D. Not ours: the setup (AnimishSharma's subgroup formula and density condition; veljjanoski's complete pools and perfect-power setup), and of course the problem. Not claimed: that no m exists. What the lemma probably cannot do: for a fixed direction the constant part Σ 1/e_p over the primes for which 2^a3^b generates ⟨2, 3⟩ should grow without bound with the pool (heuristically a positive proportion of primes qualify; in direction (1, 1) it creeps from 0.36 at 5040 to 0.53 at 720720 — we have not proved it, and even the unboundedness of the pool density itself is not known to us), in which case no single direction excludes every period and a proof for all N would need Λ to shrink with N, i.e. the exact covering problem itself. The frontier is the pool of the next natural period (12252240 = lcm(1, …, 17), which as far as we know nobody has computed; the cyclotomic gcds are millions of bits) and, as a question, whether the 5–7 cut or a cut on another pair keeps B below 1 for every period.