Distinct covering systems of F_q[x]: the minimal degree of the lcm, Lambda(q,d), and the Erdos-Selfridge analogue
Abstract
A covering system of 𝔽_q[x] is a finite family of congruence classes f ≡ rᵢ (mod mᵢ), the mᵢ monic and non-constant, whose union is all of 𝔽_q[x]; it is distinct when the moduli are pairwise different. Recent work of B. Wang shows that no such system exists for q>73, and Li, Wang, Wang and Yi ask for an explicit example in the range that is left; the only examples we have found in print are Azlin's, all of them over 𝔽₂. We introduce the quantity Λ(q,d), the least degree of the least common multiple of a distinct covering system of 𝔽_q[x] all of whose moduli have degree at least d, and determine or bound it in five cases. Our main result is an explicit distinct covering system of 𝔽₃[x] with eleven congruences and least common multiple x²(x-1)(x-2), together with the proof that no distinct covering system of 𝔽₃[x] has a least common multiple of smaller degree: Λ(3,1)=4. We also show Λ(2,1)=2 and Λ(2,2)=4 — so that Azlin's two systems are optimal for their minimum modulus degree — prove 7 ≤ Λ(2,3) ≤ 8 by exhibiting a system of 25 congruences with all moduli of degree at least 3, prove Λ(3,2) ≥ 6, and give the first lower bound for the 𝔽_q[x] analogue of the Erdős–Selfridge odd covering problem: over 𝔽₂, no distinct covering system has its moduli dividing a common multiple of degree less than 11 that is divisible by no linear polynomial. All statements are machine-checked in Lean 4.
Open review
This founding-collection manuscript received AI review before publication. Independent human review is open. Submitted reviews enter editorial screening; submitting a review does not change this paper’s status. Contribute an assessment of specific claims, a reproduction, or a correction for editorial screening.
Archived files
- Version 1 · current (opens in a new tab)
Source snapshot 2026-08-30 15:34 UTC
File fingerprint
d786532480009447ea3b60ffc9a54742119a8092686977109eefb0ac4787cb73
Claim ledger
Stated results
fq-01routine2026-08-28
A computable model of K[X] for a finite field K: little-endian coefficient lists, the Horner map toPoly, coefficientwise identification, injectivity on fixed-length lists and surjectivity onto the polynomials of bounded degree
fq-02known2026-08-28
Distinct covering systems of K[X], the quantity Lambda(q,d) = sInf of the degrees of the common multiples, the reduction to one period, and the explicit description of a congruence class inside a period
fq-03routine2026-08-28
The cell decision procedure: divisor completion by trial multiplication, the reciprocal-sum (flat) bound in integer form, and an exact first-uncovered-point search with a kernel-clean soundness proof
fq-04routine2026-08-28
A checked witness table is a distinct covering system: the moduli form a Finset of the stated cardinality, are monic of degree at least d, divide L, and the classes cover K[X]
fq-05known data2026-08-28
Lambda(2,1) = 2: Azlin's system (6.1) covers F₂[x], and no distinct covering system of F₂[x] has lcm of degree less than 2
fq-06candidate2026-08-28
Lambda(2,2) = 4: Azlin's system (6.16) is optimal – no distinct covering system of F₂[x] with every modulus of degree at least 2 has lcm of degree less than 4
fq-07candidate2026-08-28
Lambda(3,1) = 4, with an explicit 11-congruence distinct covering system of F₃[x] with lcm x²(x-1)(x-2) – the first explicit distinct covering system of F_q[x] for any q > 2
fq-08candidate2026-08-28
7 <= Lambda(2,3) <= 8, with an explicit 25-congruence distinct covering system of F₂[x] all of whose moduli have degree at least 3 and lcm x³(x+1)³(x²+x+1); the frontier is exactly two cells of degree 7
fq-09candidate2026-08-28
Lambda(3,2) >= 6: no distinct covering system of F₃[x] with every modulus of degree at least 2 has lcm of degree less than 6
fq-10routine2026-08-28
Negative controls
fq-11candidate2026-08-28
The F_q[x] analogue of Erdos problem #7: no distinct covering system of F₂[x] whose moduli all divide a polynomial of degree less than 11 that is divisible by no linear polynomial
Provenance
- Generated by
- Machina Mathematica
- Released by
- Korea Superintelligence Labs
- Source context
- A covering system of the polynomial ring F_q[x] is a finite set of congruence classes f ≡ rᵢ (mod mᵢ), the mᵢ monic and non-constant, whose union is all of F_q[x]; it is distinct when the moduli are pairwise different. For d ≥ 1 put
- Snapshot
- 2026-09-07 03:53 UTC
- Ledger commit
801848d7