The proof
More than 19 blocks are required
The argument assumes a covering of the 4-point subsets of 24 points by 19 blocks of 14, and squeezes it until it breaks. Each step opens with the idea, in plain words and with things to try. The paper’s full argument and the Lean code are one click away.
The paper (PDF)TeX sourceNot yet reviewed by a mathematicianThe argument was developed with the assistance of AI agents. Lean checks the formal proof, not the prose.
Before the proof
A covering picks blocks, sets of points, so that every small set of points sits inside at least one block. Here is one you can finish yourself.
Why not let a computer check?
There are 1,961,256 ways to choose 14 of 24 points, so about 10102 ways to choose 19 blocks. No search can try them all. The best arrangement a computer search found still misses 264 of the 10,626 four-point sets (try it). Only a proof can say that 19 blocks never work.
The map
Eight steps, 13 numbered results of the paper. Click one to jump to it. As you read, the step you’re on lights up.
The paper’s introduction and notation
A structural lower bound for , by James Chang, 11 October 2026.
We prove and hence . The proof excludes a hypothetical nineteen-block covering by exploiting its two excess point incidences. A sum-of-squares identity describes the linear relations among minimum-degree incidence vectors and forces at least three balanced components on at most sixteen points. We show that the point set of every eleven-block covering partitions into eleven twin pairs. Applying this rigidity to suitable completions and derivatives reduces the remaining cases to two elementary counting contradictions. The proof is self-contained, and a companion Lean formalization establishes both bounds.
MSC 2020: 05B40 (primary); 05B05, 05D05, 68V20 (secondary).
Keywords: covering designs, covering numbers, Turán numbers, rigidity, Lean.
1 Introduction and the shape of the proof
A cover is a family of -element subsets of a -element set in which every -element subset is contained in a member of the family. The members are called blocks, and the smallest possible number of blocks is the covering number . Taking complements of blocks identifies covering numbers with Turán numbers of hypergraphs, [17]. Surveys of covering designs include [13, 6].
Theorem 1.1. Every cover has at least twenty blocks. In particular,
The La Jolla Covering Repository [4] lists the lower bounds and . We strengthen these bounds to twenty and thirty-four, respectively. Theorem 1.1 excludes the nineteen-block equality case; the second improvement follows from Schönheim's recursive bound [16] and is stated in Corollary 5.2. Combining these lower bounds with the twenty-three-block construction of Ochmat and the forty-two-block construction of Atzeni listed in the Covering Repository [3] gives
Neither covering number is determined here.
The starting point is an elementary pair-cover obstruction:
Its proof is included in Appendix A. Taking derivatives through points and counting incidences then gives
The first two bounds are sharp: and [4, 6]. Our task is to exclude equality in the third inequality.
Here is the reason the equality case is accessible. Every point of a cover occurs in at least eleven blocks. Nineteen blocks would supply incidences, only two more than the required . Thus at least twenty-two points have degree exactly eleven. Their incidence vectors lie in , so they satisfy at least three independent linear relations. A sum-of-squares identity shows that these relations come from disjoint groups of points, each split into two equal parts met equally often by every block. There are at most sixteen points in all these groups together.
The rest of the proof explains why these balanced groups cannot exist. A group of size four, or two groups of size two, gives a balanced quadruple. Completing suitable restrictions to eleven-block covers forces a six-regular graph on twenty points. Its neighborhoods would put seven points in an omission class of size at most six. Once balanced quadruples have been excluded, the component sizes force one two-point group and two larger groups. Restricting to the eleven blocks through the two-point group leaves eight blocks whose omission sets would give five triples on six positions, any two meeting once. Such triples require fifteen incidences, but only twelve are possible.
Coverings with a small number of blocks have been studied systematically by Mills [12] and Todorov [18]. Horsley [7] generalized Fisher's inequality to coverings, and Horsley and Singh [8] obtain lower bounds from the ranks of incidence Gram matrices, using positive definite principal submatrices. Krug [10] recently determined by excluding the equality case of a counting bound with a certified satisfiability search. Many of the best known upper bounds come from the constructions of Gordon, Kuperberg and Patashnik [5]. The present argument describes the entire relation space among low-point incidence vectors in the nineteen-block equality case. A sum-of-squares identity identifies its basis with balanced components (Lemma 3.1); the eleven-block rigidity theorem of Section 2 then controls completions and derivatives of the covering. This combination yields the two counting contradictions used to exclude equality. All auxiliary lower bounds are proved in Appendix A, so the lower-bound proof does not rely on tabulated values. A Lean formalization of the proof accompanies this article as ancillary files [2]; see Section 6.
Notation and multiplicities. We allow an indexed family , so two distinct indices may specify the same subset. Every count retains these indices, including after restriction. This avoids silently discarding multiplicities when two original blocks have the same trace. A lower bound for indexed families also applies to ordinary families of distinct blocks.
Write
Thus . Subscripts are omitted when the family is clear. For -element blocks, double counting gives
The derivative through a set retains the blocks containing that set and deletes its points. The trace on a set intersects each retained block with that set. All sums over unordered pairs below explicitly use either or .
Step 1 of 8 · Appendix A.1
Counting floors
Covering pairs of 22 points with blocks of 12 takes at least 6 blocks. Restricting a covering to the blocks through one point, or two, turns that into the old bound of 19, and into two facts used everywhere below.
The idea
Everything starts with counting. Take any covering and keep only the blocks through one point x, with x removed. Any three other points, together with x, make a 4-point set, and the block covering it contains x. So these blocks still cover every 3-point set of the other 23 points: a smaller covering, the derivative through x.
Doing it at two points x and y leaves the blocks through both, which cover every pair of the other 22 points with blocks of 12. Lemma A.3 says that takes at least 6 blocks, so any two points share at least 6 blocks. Its proof is a counting puzzle. With only 5 blocks, some point lies in just two of them, and those two split the other 20 points into two groups of 10 whose 100 cross pairs the remaining three blocks would have to cover.
Counting incidences turns 6 into 11, and 11 into 19 (Corollary A.4). Every point of a (23,13,3) covering lies in at least 6 blocks, so the covering has at least 23 × 6 / 13 blocks, rounded up: 11. So every point of a (24,14,4) covering lies in at least 11 blocks, and there are at least 24 × 11 / 14 of them, rounded up: 19. That is Schönheim’s bound, and where the old lower bound of 19 came from.
From the paper
A Elementary covering lemmas
This appendix proves the small covering bounds and the matching restriction used above. It is independent of the rigidity and component arguments.
A.1 The pair-cover bound
Lemma A.1 (Two-rectangle capacity). Let be disjoint nonempty sets of sizes . Suppose two sets of size at most cover every cross-pair , , . Then at least one of
holds.
Proof. Call the two sets . If both contain , their intersections with together cover , giving . If neither contains , a point of forces , and a point of forces . Also , giving . In the remaining case exactly one, say , contains . A point of forces , so . ∎
Lemma A.2. Three sets of size at most twelve cannot cover all cross-pairs between two disjoint ten-element sets.
Proof. Every one of the twenty points must occur, but the total number of point occurrences is at most . Some point therefore occurs in exactly one set, say occurs only in . Then , so . There are at least eight points of outside . The other two sets must cover every cross-pair between these points and the ten points of . The three alternatives in Lemma A.1 all fail: , , and . ∎
Lemma A.3 (The pair-cover floor). A family of twelve-element subsets covering all pairs of a twenty-two-element set has at least six blocks.
Proof. If a cover had at most five blocks, repeat a block until it has exactly five. Its total degree is , so some point has degree at most two. The blocks through must cover all twenty-two points between them, and one twelve-element block cannot do so. Hence has degree exactly two. Call its two blocks . They satisfy and .
The sets and are disjoint and both have size ten. Neither nor covers a cross-pair from to . The remaining three blocks would cover all these cross-pairs, contrary to Lemma A.2. ∎
Corollary A.4 (Degree and codegree lower bounds). A cover has at least eleven blocks. In any cover, every point has degree at least eleven and every pair of distinct points has codegree at least six.
Proof. In a cover, the derivative through any point is a cover, so every point has degree at least six. If there are blocks, , and thus . Taking one-point and two-point derivatives of a cover proves the other assertions. ∎
In Lean
Checked by Lean6 Lean declarations
Covering.CrossGrid.crossTwo_capacity_disjunctionCovering/PairCover/TwoSets.lean:65Lemma A.1.
theorem crossTwo_capacity_disjunction {n k : Nat} (X Y R S : Block n) (hX : X.Nodup) (hY : Y.Nodup) (hXY : Disjoint X Y) (hx : 0<X.length) (hy : 0<Y.length) (hR : R.length≤k) (hS : S.length≤k) (hcross : CrossTwo X Y R S) : X.length+Y.length≤k ∨ 2*X.length+Y.length≤2*k ∨ X.length+2*Y.length≤2*kCovering.CrossGrid.crossThree_impossibleCovering/PairCover/ThreeSets.lean:129Lemma A.2.
theorem crossThree_impossible {n : Nat} (X Y R S T : Block n) (hX : X.Nodup) (hY : Y.Nodup) (hXY : Disjoint X Y) (hx : 10≤X.length) (hy : 10≤Y.length) (hR : R.length≤12) (hS : S.length≤12) (hT : T.length≤12) (hcross : CrossThree X Y R S T) : FalseCovering.PairLowerBound.pair_cover_22_12_ge_sixCovering/PairCover/PairFloor.lean:135Lemma A.3: C(22,12,2) ≥ 6.
theorem pair_cover_22_12_ge_six (F : Family 22) (hrows : ∀ R, R ∈ F → ValidBlock 12 R) (hcover : IsCovering 2 F) : 6≤F.lengthCovering.Floors.triple_cover_23_13_ge_elevenCovering/PairCover/Floors.lean:37Corollary A.4: C(23,13,3) ≥ 11.
theorem triple_cover_23_13_ge_eleven (F : Family 23) (hrows : ∀ R, R ∈ F → ValidBlock 13 R) (hcover : IsCovering 3 F) : 11≤F.lengthCovering.Nineteen.point_floor_elevenCovering/Components/Floors.lean:18Corollary A.4: every point lies in at least 11 blocks.
theorem point_floor_eleven (T : Family 24) (hrows : ∀ R, R ∈ T → ValidBlock 14 R) (hcover : IsCovering 4 T) (p : Fin 24) : 11 ≤ degree T pCovering.Floors.pair_floor_sixCovering/PairCover/Floors.lean:56Corollary A.4: every pair lies in at least 6 blocks.
theorem pair_floor_six (T : Family 24) (hrows : ∀ R, R ∈ T → ValidBlock 14 R) (hcover : IsCovering 4 T) (p q : Fin 24) (hpq : p≠q) : 6≤pairDegree T p q
The Paper tab is the paper’s own text, rendered from its TeX source at 36ec6e6. Spotted a mistake? Open an issue.
Step 2 of 8 · Section 3, opening
Degrees and excess
With only 19 blocks there is almost no slack: all but one or two points lie in exactly 11 blocks, and each of those has exactly 5 units of excess codegree to share out.
The idea
Now suppose 19 blocks were enough, and squeeze. Nineteen blocks of 14 points have 266 places. Every point needs at least 11, which uses 264, so only 2 are left: either one point is in 13 blocks, or two points are in 12. The other 22 or 23 points are in exactly 11. Call those the low points.
Pairs are just as tight. Every pair needs 6 shared blocks; call anything above that the pair’s excess. A low point is in 11 blocks with 13 other points each: 143 slots shared with the other 23 points. They need 6 each, 138 in all, so a low point has exactly 5 units of excess to hand out. That is equation (7), and the rest of the proof follows where that excess goes.
From the paper
3 Near-equality forces balanced components
From now on suppose that is a cover with nineteen indexed blocks. The elementary bounds in Corollary A.4 give
Call a point low if its degree is eleven, and high otherwise. Write for the low points. There are at least twenty-two low points, and at least one high point.
For distinct points define the nonnegative excess weights
Equation (1) gives the full weighted row sums
In particular, each low point has total excess weight five.
In Lean
Checked by Lean3 Lean declarations
Covering.Nineteen.degree_patternsCovering/Components/Excess.lean:59One point of degree 13, or two of degree 12.
lemma degree_patterns (T : Family 24) (hrows : ∀ R, R ∈ T → ValidBlock 14 R) (hcover : IsCovering 4 T) (hlen : T.length = 19) : (∃ p, degree T p = 13 ∧ ∀ q, q ≠ p → degree T q = 11) ∨ (∃ p q, p ≠ q ∧ degree T p = 12 ∧ degree T q = 12 ∧ ∀ r, r ≠ p → r ≠ q → degree T r = 11)Covering.Nineteen.fullExcess_row_sumCovering/Components/Excess.lean:101Equation (7): the excess of a point adds up to 13 d(p) − 138.
lemma fullExcess_row_sum (T : Family 24) (hrows : ∀ R, R ∈ T → ValidBlock 14 R) (p : Fin 24) : ∑ q, fullExcess T p q = 13 * (degree T p : ℝ) - 138Covering.Nineteen.lowExcess_row_le_fiveCovering/Components/Excess.lean:127lemma lowExcess_row_le_five (T : Family 24) (hrows : ∀ R, R ∈ T → ValidBlock 14 R) (hcover : IsCovering 4 T) (p : LowPoint T) : ∑ q, lowExcess T p q ≤ 5
The Paper tab is the paper’s own text, rendered from its TeX source at 36ec6e6. Spotted a mistake? Open an issue.
Step 3 of 8 · Sections 3.1–3.2
Balanced components
Twenty-two or more incidence vectors in 19 dimensions must satisfy linear relations. A sum-of-squares identity shows that every relation comes from a balanced component: a group of points split into two equal sides that every block meets equally.
The idea
This is the key idea. Write each low point as its incidence vector: 19 entries, a 1 for each block that contains it. That is 22 or more vectors in 19 dimensions, so they satisfy at least 3 independent linear relations: ways to give each low point a number so that, in every block, the numbers add up to zero.
Identity (8) says what those relations can look like. It writes the squared length of the combination as three sums of squares: one for the total of the numbers; one for each point that sends some of its 5 units of excess to a high point, its unused excess δ; and one for each pair of low points with excess, weighted by it. A relation makes the left side zero, so every term vanishes: the numbers add up to zero, they are 0 wherever δ is positive, and they flip sign across every edge.
That only works on balanced components: groups of low points whose excess stays among themselves, split into two equal sides. Lemma 3.1 shows they account for every relation, one each, so there are at least 3 of them. Each one says that every block contains as many points from one side as from the other: that is equation (11). A point of a balanced component spends all its excess inside it, so by equation (12) it shares exactly 6 blocks with every point outside. And the high points’ excess has to land on low points outside, which leaves room for at most 16 balanced points (Proposition 3.2).
From the paper
3.1 One identity describes all linear relations
Let be the incidence vector of a low point : its th coordinate records whether . Join two low points whenever . The resulting graph records which low-point pairs have codegree above six.
Some of a low point's five units of excess may go to high points. Define its unused internal excess by
For arbitrary real coefficients , we have
To verify it, expand the left side using and for . On the right side, the edge-square terms contribute to the coefficient of ; this combines with to give five. The remaining six comes from the first square. The cross terms agree as well.
Define the incidence map
Call a connected component of the low-point graph balanced if it is bipartite and all its vertices have . For such a component, choose a bipartition and let be its signed indicator vector.
Lemma 3.1 (The incidence relation space). Every balanced component has equally large nonempty parts. The vectors , one for each balanced component , form a basis of . In particular,
Proof. All terms on the right of (8) are nonnegative. If , the first square gives , and the other terms give
Thus coefficients reverse sign along edges. On a connected component, a nonzero coefficient propagates with the same absolute value to every vertex. An odd cycle would force and hence , so such a component must be bipartite. Every vertex must also have . All other components have zero coefficients.
In a balanced component, each vertex has weighted degree five within the component. Counting edge weight from its two sides gives
The parts are nonempty because the weighted degree is positive, and they are equally large. In particular, the component has positive even size.
Conversely, evaluate (8) at . The total coefficient sum is zero by equality of the part sizes. There is no unused excess on , every positive-weight edge within joins opposite signs, and no edge joins to another low-point component. Every term vanishes, so . Equivalently,
Coordinate by coordinate, this says that every block is balanced:
The propagation rule (9) shows that any element of is a linear combination of these signed vectors. Their supports are disjoint, so they are independent. Each already has total coefficient sum zero, so that condition imposes no further restriction. Finally, rank–nullity and give the stated bound. ∎
A point of a balanced component spends all five units of its full excess within that component. Its excess with any outside point is therefore zero, as is the excess between two points on the same side. Consequently
whenever lies in a balanced component and lies outside it, or whenever distinct lie on the same side of a component.
3.2 There is room for at most sixteen balanced points
Let be the union of all balanced components. Its size is even. Since the total degree excess is two, only two high-point patterns are possible.
If one point has degree thirteen, the other twenty-three points are low. Its excess row sum is thirty-one by (7). None of this weight goes to , by (12). A low point can receive at most five units, so at least seven low points lie outside . Thus .
Otherwise two points have degree twelve and the other twenty-two are low. Their combined excess row sum is thirty-six. Their mutual excess is at most six, since their codegree is at most twelve. This accounts for at most twelve units in the combined row sum. At least twenty-four units must therefore go to low points outside . Each receives at most five, so at least five low points lie outside . Hence , and evenness improves the bound to sixteen.
In Lean
Checked by Lean5 Lean declarations
Covering.Nineteen.incidence_vector_energyCovering/Components/IncidenceIdentity.lean:57Identity (8).
theorem incidence_vector_energy (S : System V) (c : ℝ) (M : Matrix V B ℝ) (hGram : S.gram c = M * M.transpose) (a : V → ℝ) : (∑ b, (∑ p, M p b * a p) ^ 2) = c * (∑ p, a p) ^ 2 + (∑ p, (S.d - rowSum S.W p) * a p ^ 2) + (∑ p, ∑ q, S.W p q * (a p + a q) ^ 2) / 2WeightedKernelComponents.System.card_sub_rank_le_balanced_componentsCovering/Kernel/Gram.lean:77Lemma 3.1, for any weighted graph.
lemma card_sub_rank_le_balanced_components (hd : S.d ≠ 0) (c : ℝ) (hc : 0 ≤ c) : Fintype.card V - (S.gram c).rank ≤ Nat.card {a // S.BalancedBipartite a}Covering.Nineteen.at_least_three_componentsCovering/Components/RelationSpace.lean:57Lemma 3.1: at least |L| − 19 ≥ 3 balanced components.
lemma at_least_three_components (T : Family 24) (hrows : ∀ R, R ∈ T → ValidBlock 14 R) (hcover : IsCovering 4 T) (hlen : T.length = 19) : 3 ≤ Nat.card {c // (lowSystem T hrows hcover).BalancedBipartite c}Covering.Nineteen.component_slot_balance_with_edgesCovering/Components/Balance.lean:19Equations (10)–(12).
lemma component_slot_balance_with_edges (T : Family 24) (hrows : ∀ R, R ∈ T → ValidBlock 14 R) (hcover : IsCovering 4 T) (c : (lowSystem T hrows hcover).graph.ConnectedComponent) (hc : (lowSystem T hrows hcover).BalancedBipartite c) : ∃ s t : Finset (LowPoint T), s.Nonempty ∧ t.Nonempty ∧ _root_.Disjoint s t ∧ s.card = t.card ∧ (∀ p, (lowSystem T hrows hcover).graph.connectedComponentMk p = c ↔ p ∈ s ∨ p ∈ t) ∧ (∀ j : Fin T.length, (s.filter fun p => p.val ∈ T.get j).card = (t.filter fun p => p.val ∈ T.get j).card) ∧ (∀ p q, (lowSystem T hrows hcover).graph.connectedComponentMk p = c → (lowSystem T hrows hcover).graph.Adj p q → (p ∈ s ∧ q ∈ t) ∨ (p ∈ t ∧ q ∈ s))Covering.Nineteen.good_vertices_le_sixteenCovering/Components/AtMostSixteen.lean:134Proposition 3.2: at most 16 balanced points.
lemma good_vertices_le_sixteen (T : Family 24) (hrows : ∀ R, R ∈ T → ValidBlock 14 R) (hcover : IsCovering 4 T) (hlen : T.length = 19) : (lowSystem T hrows hcover).goodVertices.card ≤ 16
The Paper tab is the paper’s own text, rendered from its TeX source at 36ec6e6. Spotted a mistake? Open an issue.
Step 4 of 8 · Section 2 and Appendix A.2
Eleven-block rigidity
Eleven blocks of 12 covering every triple of 22 points must pair the points into twins. Two counts of the same quantity, and a cap on each point’s energy, leave no room for anything else.
The idea
Both of the remaining cases run into the same object: 11 blocks of 12 points that cover every triple of 22 points. Theorem 2.1 says it is rigid. The points split into 11 pairs of twins that lie in exactly the same 6 blocks, points from different pairs share exactly 3 blocks, and any two blocks share 6 points. Squeeze each twin pair to one point and you get a symmetric 2-(11,6,3) design.
The proof counts one quantity two ways. Every point lies in 6 blocks and any two share between 2 and 6, so look at how far each pair is from 3. By equation (3), a point’s deviations add up to 3, and their squares add up to its energy. The covering caps the energy at 9 (Lemma 2.2): if no deviation is negative, the squares add up to at most 3² = 9, and a negative one forces energy 5. That uses Lemma A.6: a point shares only 2 blocks with at most one other.
The other count is exact. Counting pairs of points inside pairs of blocks both ways gives (5): the energies add up to 198 plus twice the squared distances of the block intersections from 6. Since 22 × 9 = 198, the cap leaves no room, as equation (6) shows: every point has energy exactly 9, and any two blocks share exactly 6 points. Whole numbers, none negative, adding up to 3 with squares adding up to 9 must be a single 3. That 3 is the twin.
One consequence does the work later (Corollary 2.3): if numbers on the points add up to zero on every block, twins get opposite numbers. Remark 2.4 adds that the rigid shape is unique up to relabelling.
From the paper
2 Eleven blocks force inseparable pairs
We first state the structural result in the form used later.
Theorem 2.1 (Eleven-block rigidity). Let eleven twelve-element blocks cover every triple of a twenty-two-element set. Then the points split into eleven pairs such that every block contains either both points of a pair or neither. Each point occurs in six blocks, and points from different pairs occur together in exactly three blocks. Any two distinct block indices have intersection size six.
We call the two members of a pair twins, and write for the twin of . Thus is a fixed-point-free involution, and
Compressing each twin pair to one point produces eleven six-element blocks on eleven points, with every pair in exactly three blocks: a symmetric - design. We need only the paired structure, not a classification of these designs.
2.1 Local restrictions on codegrees
The pair-cover bound in Lemma A.3 forces every point to occur at least six times. Indeed, the blocks through a fixed point , with retained, cover every pair of the twenty-two points: extend the pair with to a triple when necessary. Since the total degree is , all point degrees are exactly six.
For distinct , the blocks through both must cover the other twenty points, ten at a time. Hence
We also need the following elementary fact, proved in Lemma A.6: in a cover of all pairs of twenty-one points by six eleven-element blocks, at most one point has degree two. Apply this to the derivative through . It follows that, for a fixed , at most one has . In other words, the pairs of codegree two form a matching.
For distinct points put , and put . These deviations are symmetric, and every row has sum
The energy at is
We will bound this energy in two ways: locally from the covering constraints, and globally by counting the same configurations through pairs of blocks.
Lemma 2.2. For every point, . If its row contains a negative deviation, then .
Proof. For a nonnegative row, the sum of squares is at most the square of the sum, so (3) gives .
Otherwise the row has a unique negative entry, . The two blocks containing both partition the other twenty points after are deleted. Thus each point occurs in exactly one of these two blocks. Exactly one of the eleven blocks contains neither nor , since contain at least one of them. For any such , inclusion–exclusion in its six incident blocks, counting the block through twice, gives
The last term is zero or one. The matching restriction implies , so each is three or four. The row at therefore has one entry , with all remaining entries zero or one. Its sum is three, so exactly four entries are one. Thus . ∎
2.2 A double count makes every defect vanish
Put . Count a choice of two distinct points and two distinct block indices containing them in two ways:
The first moments are equally simple:
Using in (4) and expanding the squared deviations now gives
For completeness, the expansion is
subtracting these expressions and using (4) yields (5).
Together with Lemma 2.2, this becomes
Every term is nonnegative. Consequently every point has energy nine, and any two distinct block indices intersect in six points.
Completion of the proof of Theorem 2.1. A negative deviation would give energy five, so every row is nonnegative. Each has sum three and sum of squares nine. Since
at most one entry can be positive. There is therefore exactly one entry equal to three. Denote its column by .
The diagonal entry is zero, so . Symmetry and uniqueness give . This proves (2). Finally, both twins have degree six and their codegree is six, so they occur in exactly the same blocks. The intersection assertion follows from (6). ∎
Corollary 2.3 (Zero block sums reverse weights on twins). Assign real weights to the points of an eleven-block cover. If every block has total weight zero, then for each point .
Proof. Summing all block weights gives . For a fixed point , sum the weights of the blocks containing it and use (2):
The final sum vanishes, proving the assertion. ∎
Remark 2.4. Theorem 2.1 determines the eleven-block covers up to isomorphism. Compressing twin pairs gives a symmetric - design, whose complementary design is a - biplane, and the biplane on eleven points is unique up to isomorphism [9, 1]. Conversely, doubling every point of the complementary design of this biplane gives an eleven-block cover; this is the doubling construction of [5]. Indeed, a triple meeting only two twin pairs corresponds to a pair, which lies in three blocks, and a triple meeting three twin pairs corresponds to a -set of the biplane; since two biplane blocks share exactly two points, at most one block contains , and inclusion–exclusion shows that at least biplane block is disjoint from . Since [4], the optimal cover is therefore unique up to isomorphism. We are not aware of a previous statement of this uniqueness.
A.2 The matching restriction
Lemma A.5. Three eleven-element subsets of a nineteen-element set cannot cover all cross-pairs of a partition into parts of sizes nine and ten.
Proof. Suppose are the parts and give such a cover. Add three fresh points . The following five twelve-element sets would pair-cover the resulting twenty-two-element set:
Pairs internal to or and pairs involving are covered by the first two blocks; cross-pairs are covered by the last three. Every point of occurs in some , because its cross-pairs with the nonempty set are covered, so pairs from to are also covered. This contradicts Lemma A.3. ∎
Lemma A.6. In a pair cover of twenty-one points by six eleven-element blocks, at most one point has degree two.
Proof. Suppose distinct both have degree two. The two blocks through cover all points, so their intersection is exactly . Label them with . The other block through , denoted by , satisfies . Consequently there is a partition of the other nineteen points into sets with , , such that
The remaining three blocks avoid and must cover all cross-pairs between and , contrary to Lemma A.5. ∎
In Lean
Checked by Lean6 Lean declarations
Covering.Matching.codegree_two_matchingCovering/PairCover/Matching.lean:103Lemma A.6: the pairs of codegree 2 form a matching.
theorem codegree_two_matching (F : Family 22) (hrows : ∀ R, R ∈ F → ValidBlock 12 R) (hcover : IsCovering 3 F) (u v w : Fin 22) (huv : u≠v) (huw : u≠w) (hu : degree F u=6) (hv : pairDegree F u v=2) (hw : pairDegree F u w=2) : v=wCovering.RowEnergy.energy_le_nineCovering/Rigidity/SignedEnergy.lean:44Lemma 2.2: every energy is at most 9.
lemma energy_le_nine (W : Matrix (Fin 22) (Fin 22) ℝ) (h : SignedData W) (i : Fin 22) : energy W i≤9Covering.Rigidity.incidence_deficit_identityCovering/Rigidity/Energy.lean:140Identity (6).
theorem incidence_deficit_identity (F : Family 22) (hrows : ∀ R, R ∈ F → ValidBlock 12 R) (hregular : ∀ p, degree F p = 6) (hlen : F.length = 11) : (∑ p, (9 - energy (coverWeights F) p)) + (∑ i : Fin F.length, ∑ j : Fin F.length, (if i = j then 0 else ((incidence F).transpose * incidence F) i j - 6)^2) = 0Covering.Rigidity.eleven_block_rigidityCovering/Rigidity/Twins.lean:38Theorem 2.1: the twin pairs.
theorem eleven_block_rigidity (F : Family 22) (hrows : ∀ R, R ∈ F → ValidBlock 12 R) (hcover : IsCovering 3 F) (hlen : F.length=11) : ∃ σ : Fin 22 → Fin 22, (∀ p, σ p≠p) ∧ (∀ p, σ (σ p)=p) ∧ (∀ p q, pairDegree F p q=if p=q ∨ q=σ p then 6 else 3) ∧ (∀ p R, R ∈ F → (p ∈ R ↔ σ p ∈ R))Covering.Rigidity.eleven_block_intersectionsCovering/Rigidity/Twins.lean:82Theorem 2.1: any two blocks share 6 points.
theorem eleven_block_intersections (F : Family 22) (hrows : ∀ R, R ∈ F → ValidBlock 12 R) (hcover : IsCovering 3 F) (hlen : F.length = 11) (i j : Fin F.length) (hij : i ≠ j) : ((incidence F).transpose * incidence F) i j = 6Covering.RowEnergy.twin_balance_from_pair_dataCovering/Rigidity/TwinBalance.lean:46Corollary 2.3.
theorem twin_balance_from_pair_data (F : Family 22) (hregular : ∀ p, degree F p=6) (σ : Fin 22 → Fin 22) (hne : ∀ p, σ p≠p) (hpair : ∀ p q, pairDegree F p q=if p=q ∨ q=σ p then 6 else 3) (z : Fin 22 → ℝ) (hz : (incidence F).transpose *ᵥ z=0) : ∀ p, z (σ p) = -z p
The Paper tab is the paper’s own text, rendered from its TeX source at 36ec6e6. Spotted a mistake? Open an issue.
Step 5 of 8 · Sections 4–4.1
Balanced quadruples
A balanced component of four points, or two of two, gives a balanced quadruple. Its blocks fall into four classes, and two of them complete to eleven-block covers that rigidity controls.
The idea
Step 3 left at least 3 balanced components, of even sizes, inside 16 points. Two shapes give the proof a handle. A component of 4 points, or two components of 2, give a balanced quadruple: four low points u, v, s, t such that every block contains as many of u, v as of s, t, as in equation (13). Most ways of packing the components contain one of these shapes:
Suppose there is a balanced quadruple. Counting the blocks through u shows that u and v share exactly 6. Sort the 19 blocks by which of u and v they contain: 6 contain both (𝓗), 5 only u (𝓔), 5 only v (𝓕) and 3 neither (𝓖). Balance then decides how many of s, t each block holds, and so how many of the other 20 points.
| Family | Blocks | Contains | Points of X |
|---|---|---|---|
| 𝓗 | 6 | u v s t | 10 |
| 𝓔 | 5 | u, s or t | 12 |
| 𝓕 | 5 | v, s or t | 12 |
| 𝓖 | 3 | none | 14 |
On those 20 points, 𝓗 covers every pair, and 𝓗 with 𝓔 covers every triple. Add two new points to each block of 𝓗. With the five blocks of 𝓔 that makes 11 blocks of 12 covering every triple of 22 points, the object of Step 4, so rigidity applies. The two new points are twins, so every old point shares 3 blocks with them. That puts it in exactly 3 blocks of 𝓗 and, since it lies in 6 in all, in 3 of 𝓔: that is equation (14). Doing the same with 𝓕 gives a second completion.
From the paper
4 Excluding balanced quadruples
A balanced quadruple consists of four distinct low points such that every block satisfies
A balanced component of size four supplies such a quadruple using its two parts. Two components of size two also supply one: put one point from each component on either side of (13).
Proposition 4.1. A nineteen-block cover has no balanced quadruple.
We prove the proposition in three steps. The first produces two small completions, the second shows that they share the same twin pairs, and the third gives a neighborhood-count contradiction.
4.1 Four block classes and two completions
Multiply (13) by and sum over all blocks:
The full excess row at is five, so . Nonnegativity forces , and hence .
Let be the twenty points outside the quadruple. Partition the blocks according to membership of , and use the same symbols for their traces on :
| Membership of | both | only | only | neither |
| Number of blocks | 6 | 5 | 5 | 3 |
| Size of a trace on | 10 | 12 | 12 | 14 |
The numbers of blocks are , , and . All unions of these families retain their disjoint original index sets, even if traces coincide. The trace sizes follow from the balance equation: a block containing both also contains ; a block containing exactly one of contains exactly one of ; a block containing neither contains neither.
The family covers every pair of , by attaching to that pair. Similarly and each cover every triple of , by attaching or .
For either or , add two new points to each of the six blocks of , and leave the five blocks of unchanged. The result is an eleven-block cover. Old triples are covered by ; triples containing exactly one new point are covered because covers pairs; triples containing both new points are covered because pair coverage also ensures that every old point occurs in .
Apply Theorem 2.1. The new points occur together in precisely the six enlarged -blocks, so they are twins. An old point is not their twin, and its codegree with is therefore three. That codegree is exactly . Its total degree in the completion is six, so as well. Thus
All three degree identities have come from the completions; no separate regularity calculation for is needed.
In Lean
Checked by Lean3 Lean declarations
Covering.Quadruple.BalancedQuadrupleCovering/Quadruple/Basic.lean:16A balanced quadruple.
structure BalancedQuadruple (T : Family 24) where u : LowPoint T v : LowPoint T s : LowPoint T t : LowPoint T distinct : u ≠ v ∧ u ≠ s ∧ u ≠ t ∧ v ≠ s ∧ v ≠ t ∧ s ≠ t row_balance : ∀ R, R ∈ T → (if u.val ∈ R then (1:ℕ) else 0) + (if v.val ∈ R then 1 else 0) = (if s.val ∈ R then 1 else 0) + (if t.val ∈ R then 1 else 0)Covering.Nineteen.quadruple_of_two_size_two_componentsCovering/Quadruple/FromTwoPairs.lean:59Two components of size 2 give one.
lemma quadruple_of_two_size_two_components (T : Family 24) (hrows : ∀ R, R ∈ T → ValidBlock 14 R) (hcover : IsCovering 4 T) (c d : (lowSystem T hrows hcover).graph.ConnectedComponent) (hcd : c ≠ d) (hc : (lowSystem T hrows hcover).BalancedBipartite c) (hd : (lowSystem T hrows hcover).BalancedBipartite d) (hsizec : (lowSystem T hrows hcover).componentSize c = 2) (hsized : (lowSystem T hrows hcover).componentSize d = 2) : HasQuadruple TCovering.Quadruple.completion_from_rigidityCovering/Quadruple/CompletionDegrees.lean:83Section 4.1: the completion and the degrees (14).
theorem completion_from_rigidity (H E : Family 20) (hHl : H.length = 6) (hEl : E.length = 5) (hHr : ∀ R, R ∈ H → ValidBlock 10 R) (hEr : ∀ R, R ∈ E → ValidBlock 12 R) (hHc : IsCovering 2 H) (hEc : IsCovering 3 (H ++ E)) : Completion H E
The Paper tab is the paper’s own text, rendered from its TeX source at 36ec6e6. Spotted a mistake? Open an issue.
Step 6 of 8 · Sections 4.2–4.3
No balanced quadruple
Both completions have the same twins, and the pairs sharing two 𝓗-blocks form a six-regular graph on 20 points. Neighbours must miss the same 𝓖-block, which misses only 6 points, yet some point and its six neighbours all need one.
The idea
The two completions have the same twins. By equation (15), two of the 20 points share 6 blocks of 𝓗 and 𝓔 if they are twins and 3 otherwise, with between 1 and 3 from each family. So they are twins exactly when they share 3 blocks of 𝓗, which doesn’t involve 𝓔 or 𝓕 at all. Every other pair shares 1 or 2 blocks of 𝓗.
Join two points when they share exactly 2 blocks of 𝓗, and call the graph Γ. Adding up a point’s 𝓗-codegrees shows it has exactly 6 neighbours: Γ is six-regular.
Now the three 𝓖-blocks. Every point lies in 3 blocks of each of 𝓗, 𝓔 and 𝓕 and needs at least 11 in all, so it lies in 2 or 3 of the 𝓖-blocks, and counting shows that exactly two points lie in all three. Every other point misses exactly one 𝓖-block, its colour. A 𝓖-block contains 14 of the 20 points, so a colour holds at most 6. But neighbours in Γ share only 2 blocks of 𝓗 and 1 each of 𝓔 and 𝓕, so they need at least 2 more from 𝓖, which gives them the same colour.
From the paper
4.2 The completions have the same twin pairs
The twin involution of either completion restricts to , since the new points are twins of each other. For distinct old points,
Both summands are at most three by (14). Also from pair coverage, and : each point occurs in three of the five -blocks, so their sets of incident indices must intersect.
It follows that are twins exactly when . In one direction, a total of six forces both summands to be three. In the other, an -codegree of three makes the total at least four, so it cannot be the non-twin value three. This criterion depends only on . Therefore the two completions have the same twin pairs. Every other distinct pair has -codegree one or two.
Let be the simple graph on in which distinct are adjacent when . This graph is six-regular. Indeed, the codegree row sum, including the diagonal, is . The diagonal and the twin contribute three each. The remaining eighteen entries are one or two and have sum twenty-four, so exactly six of them are two.
4.3 A neighborhood cannot fit in an omission class
For every old point, the four block classes and (14) give
Thus . The total -degree is , so exactly two of the twenty points have -degree three; the other eighteen have degree two. Call the latter points ordinary.
Color each ordinary point by the unique -block omitting it. Every color class has size at most six, because that block contains fourteen of the twenty points. If ordinary are adjacent in , then , and (15) gives
The full codegree is at least six, so . Each point occurs in exactly two -blocks, so they occur in the same two and have the same color.
The two nonordinary points together with their neighbors in occupy at most vertices. Choose a vertex outside that set. It and all six of its neighbors are ordinary and have the same color. This puts seven distinct points in a class of size at most six, a contradiction. Proposition 4.1 follows.
In Lean
Checked by Lean4 Lean declarations
Covering.Completions.completions_share_pairingCovering/Quadruple/SharedTwins.lean:119Section 4.2: both completions have the same twins.
theorem completions_share_pairing (H E F : Family 20) (_hE : Completion H E) (hF : Completion H F) (σ τ : Fin 20 → Fin 20) (hσ : TwinData H E σ) (hτ : TwinData H F τ) : σ=τCovering.Colors.color_fiber_capacityCovering/Quadruple/Colors.lean:106Each colour holds at most 6 points.
theorem color_fiber_capacity (F : Family 20) (hlen : F.length=3) (hr : ∀ R, R ∈ F → ValidBlock 14 R) (L : Finset (Fin 20)) (hL : ∀ p, p∈L → degree F p=2) (c : Finset (Fin F.length)) : (L.filter (fun p => color F p=c)).card≤6Covering.Quadruple.local_seven_vs_sixCovering/Quadruple/SevenVsSix.lean:45Section 4.3: seven points in a colour of six.
theorem local_seven_vs_six {C : Type*} [DecidableEq C] (N : Fin 20 → Finset (Fin 20)) (hn : ∀ x, x ∉ N x) (hs : ∀ x y, y ∈ N x ↔ x ∈ N y) (hc : ∀ x, (N x).card=6) (a b : Fin 20) (color : Fin 20 → C) (hedge : ∀ x y, x ≠ a → x ≠ b → y ≠ a → y ≠ b → y ∈ N x → color x = color y) (hcap : ∀ c, (univ.filter (fun x => x ≠ a ∧ x ≠ b ∧ color x=c)).card ≤ 6) : FalseCovering.Quadruple.no_balanced_quadrupleCovering/Quadruple/NoQuadruple.lean:24Proposition 4.1.
theorem no_balanced_quadruple (T : Family 24) (hr : ∀ R, R ∈ T → ValidBlock 14 R) (hc : IsCovering 4 T) (hlen : T.length=19) (balanced : BalancedQuadruple T) : False
The Paper tab is the paper’s own text, rendered from its TeX source at 36ec6e6. Spotted a mistake? Open an issue.
Step 7 of 8 · Section 5
The remaining components
Without quadruples the components have sizes 2, 6, 6 or 2, 6, 8. The two-point component lies in 11 blocks that rigidity controls, and the other 8 blocks would need five triples on six positions, any two meeting once.
The idea
Without a balanced quadruple, Step 5’s packing leaves two possibilities: components of sizes 2, 6 and 6, or 2, 6 and 8. With exactly 3 components, Lemma 3.1 allows only 22 low points, so there are two high points, each of degree 12.
The two-point component is balanced, so every block contains both of its points or neither: they lie in the same 11 blocks. Remove them from those blocks, and the 11 blocks cover every triple of the other 22 points, the object of Step 4 again. Its twins split the larger components. Give one side of a component +1 and the other −1: every one of the 11 blocks adds up to zero by balance, so by Corollary 2.3 each point’s twin is on the opposite side.
Now take five points from the + sides of the two larger components, and a high point h. Subtracting the 11 blocks from the covering leaves 8 blocks, and the subtraction is exact: each chosen point lies in 5 of them, h in 6, and any two of them share 3. So each chosen point misses 3 of the 8 blocks, h misses 2 that no chosen point misses, and any two chosen points miss exactly one block in common. That makes five triples on the six other blocks, any two meeting once, which Lemma 5.1 forbids:
From the paper
5 Excluding the remaining components
We first record the elementary set-system obstruction that will end the proof.
Lemma 5.1 (Five triples on six positions). There are no five three-element subsets of a six-element set such that every two have intersection size exactly one.
Proof. No position can occur in three of the subsets: after removing that common position, the three remaining pairs would have to be disjoint, requiring six further positions. Thus each of the six positions occurs in at most two subsets. There are at most twelve incidences, whereas five triples require fifteen. ∎
5.1 A two-point component and two larger components
Proposition 4.1 excludes both a component of size four and two distinct components of size two. There is therefore at most one size-two component, and every other component has size at least six. Since there are at least three components with total size at most sixteen, some component must have size two: otherwise three components already contain at least eighteen points. There are exactly three components, since four would contain at least points. Their sizes, in increasing order, must therefore be
There are exactly three balanced components, so Lemma 3.1 gives . Since , we have . The two high points therefore both have degree twelve, because the total degree excess is two.
Let be that size-two component, and choose two other components . Their equal parts satisfy
Blockwise balance implies that occur in exactly the same eleven blocks. Delete from those blocks and call the resulting family on twenty-two points . It consists of eleven twelve-element blocks covering every triple: attach to the triple and use the original four-cover property. The remaining eight original blocks form a family ; these all avoid .
Theorem 2.1 applies to . Assign weight to , to , and zero to all remaining points. Every -block has weight zero by (11). Corollary 2.3 therefore puts the -twin of each point of in . Likewise the twins of points in lie in . In particular, no two points of are -twins.
5.2 Subtracting the eleven-block cover
Choose five points . This is possible because the union has at least six points. Also choose either of the two high points, denoted by .
All selected points are low. The high point is outside every balanced component, so (12) applies to its codegrees with . No two distinct selected points are -twins, and is not the -twin of a selected point because that twin lies in the opposite side of its component. The degrees and codegrees now follow by subtraction:
| Quantity | Original | Eleven blocks | Eight blocks |
|---|---|---|---|
| Degree of | 11 | 6 | 5 |
| Codegree of distinct | 6 | 3 | 3 |
| Degree of | 12 | 6 | 6 |
| Codegree of and | 6 | 3 | 3 |
The full codegree six for two selected points follows because they are on the same side of a component or in different components.
For each point , let be the set of residual block indices omitting it. Inclusion–exclusion gives
Thus the five , for , are triples on the same six indices outside , and every two meet in exactly one index. This contradicts Lemma 5.1.
In Lean
Checked by Lean3 Lean declarations
Covering.LinearTriples.five_triples_on_six_positionsCovering/Basic/LinearTriples.lean:134Lemma 5.1.
theorem five_triples_on_six_positions {n : Nat} (W : Block n) (F : Family n) (hW : ValidBlock 6 W) (hF : F.length = 5) (hrows : ∀ R, R ∈ F → ValidBlock 3 R ∧ Covering.Subset R W) (hpairs : F.Pairwise (fun R S => (hits R S).length = 1)) : FalseCovering.Components.remaining_component_sizesCovering/Components/Sizes.lean:63Section 5.1: the sizes, and |L| = 22.
theorem remaining_component_sizes {α : Type*} [DecidableEq α] (s : Finset α) (f : α → ℕ) (hcard : 3 ≤ s.card) (hmin : ∀ a ∈ s, 2 ≤ f a) (heven : ∀ a ∈ s, Even (f a)) (htotal : ∑ a ∈ s, f a ≤ 16) (hfour : ¬ ∃ a ∈ s, f a = 4) (htwo : ¬ ∃ a ∈ s, ∃ b ∈ s, a ≠ b ∧ f a = 2 ∧ f b = 2) : ∃ a ∈ s, ∃ b ∈ s, ∃ c ∈ s, a ≠ b ∧ a ≠ c ∧ b ≠ c ∧ f a = 2 ∧ 6 ≤ f b ∧ 6 ≤ f cCovering.Remaining.remaining_components_impossibleCovering/Remaining/Exclusion.lean:32Section 5: the contradiction.
lemma remaining_components_impossible (T : Family 24) (hrows : ∀ R, R ∈ T → ValidBlock 14 R) (hcover : IsCovering 4 T) (hlen : T.length = 19) (E : RemainingComponents T hrows hcover) : False
The Paper tab is the paper’s own text, rendered from its TeX source at 36ec6e6. Spotted a mistake? Open an issue.
Step 8 of 8 · Section 5, end
Conclusion
No 19-block covering exists, and counting rules out fewer, so at least 20 blocks are needed. Counting through one point of a (25,15,5) covering then gives 34.
The idea
Both cases fail, so no covering has exactly 19 blocks. Fewer are ruled out by counting alone: every point lies in at least 11 blocks of 14, so there are at least 24 × 11 / 14 blocks, rounded up: 19. Every covering needs at least 20 blocks (Theorem 1.1).
The bound climbs from there (Corollary 5.2). The blocks through any point of a (25,15,5) covering form a (24,14,4) covering, so every point is in at least 20 of them, and 25 × 20 / 15 rounds up to 34. The same step keeps going:
From the paper
Conclusion of Theorem 1.1. Every hypothetical nineteen-block cover yields the balanced components of Proposition 3.2. Balanced quadruples are impossible by Section 4, and the remaining component sizes have just led to a contradiction. Hence nineteen blocks do not suffice.
The elementary degree bound gives , and hence . Excluding equality proves . ∎
Corollary 5.2. Every cover has at least thirty-four blocks. Thus .
Proof. The derivative through any point is a cover, so every point has degree at least twenty. If the original cover has blocks, then
∎
In Lean
Checked by Lean3 Lean declarations
Covering.exact_nineteen_excludedCovering/Main.lean:26theorem exact_nineteen_excluded : ExactNineteenExcludedCovering.covering_24_14_4Covering/Main.lean:44Theorem 1.1.
theorem covering_24_14_4 (𝒯 : Finset (Finset (Fin 24))) (hk : ∀ B ∈ 𝒯, B.card = 14) (hcov : ∀ S : Finset (Fin 24), S.card = 4 → ∃ B ∈ 𝒯, S ⊆ B) : 20 ≤ 𝒯.cardCovering.covering_25_15_5Covering/Main.lean:51Corollary 5.2.
theorem covering_25_15_5 (𝒯 : Finset (Finset (Fin 25))) (hk : ∀ B ∈ 𝒯, B.card = 15) (hcov : ∀ S : Finset (Fin 25), S.card = 5 → ∃ B ∈ 𝒯, S ⊆ B) : 34 ≤ 𝒯.card
The Paper tab is the paper’s own text, rendered from its TeX source at 36ec6e6. Spotted a mistake? Open an issue.
6 Formalization
The ancillary files [2] contain a formalization of Theorem 1.1 and Corollary 5.2 in Lean 4 [14] using Mathlib [11]. The finite-set statements are
Covering.covering_24_14_4
Covering.covering_25_15_5.
Their hypotheses require only the prescribed block sizes and coverage of every four- or five-element subset, respectively; the structural properties used in this paper are derived in the proofs, and the only axioms used are the standard ones of Lean and Mathlib. The formal proof follows the argument of this paper, with some differences in organization and in intermediate formulations. Its README lists the Lean declaration corresponding to each numbered result and explains how to build the project.
The formalization is also maintained at github.com/jamesyc/covering. It is registered in the Palomar registry of machine-checked Lean proofs as entry PALOMAR-2026-10-04-000003, version 2 [15].
6.1 Use of AI tools
The mathematical arguments and Lean proofs were developed with substantial assistance from AI research agents in OpenAI Dots. The author selected the problem, directed the research, and prepared the manuscript. OpenAI Codex and Claude were used to revise the exposition and the Lean sources. The author takes responsibility for the final manuscript and its mathematical claims. At the time of writing, the proof has been checked in Lean but has not yet been independently reviewed by a human mathematician.
Questions
What does Lean actually check?
Lean’s kernel checks every step of the formal proof, starting from the definitions of a covering, and the final theorems use only Lean’s three standard axioms. Comparator checks that the proved statement is exactly the textbook one. What Lean doesn’t check is the prose: the paper and the explanations on this page. More on what’s checked.
Why does the paper allow repeated blocks?
Restricting a covering to some of its blocks, or to some of its points, can make two different blocks look the same. The paper keeps every block with its own index, so such copies are never silently merged. A lower bound for these indexed families also holds for ordinary families of distinct blocks.
What is a symmetric 2-(11,6,3) design?
Eleven points and eleven blocks of six points each, such that every two points lie in exactly three common blocks. Any two blocks then share exactly three points. It is the complement of the biplane on eleven points, whose blocks are the translates of the squares 1, 3, 4, 5, 9 modulo 11. Step 4’s figure shows it with every point doubled, and Remark 2.4 of the paper shows that, up to relabelling, this doubled shape is the only eleven-block (22,12,3) covering.
Is this result new?
The covering repositories list 19 as the best lower bound for C(24,14,4), derived from C(22,12,2) = 6 by Schönheim’s bound, and a literature search found no published proof of 20. A mathematician’s review is still pending.
Does this say what C(24,14,4) is?
No. It is at least 20, and the best known covering has 23 blocks. Whether 20, 21 or 22 blocks can work is open.
References
- [1] P. J. Cameron, Biplanes, Mathematische Zeitschrift 131 (1973), 85–101. doi:10.1007/BF01213827.
- [2] J. Chang, Lean formalization of and , ancillary files to this article (2026); also at
github.com/jamesyc/covering. - [3] Covering Repository, construction records for and , credited to A. Ochmat (23 blocks, 20 July 2004) and F. Atzeni (42 blocks, 6 September 2026), respectively; accessed 11 October 2026. 23-block record; 42-block record.
- [4] D. M. Gordon, La Jolla Coverings Repository (formerly the La Jolla Covering Repository), dataset, version 1.2, Zenodo, 2026. doi:10.5281/zenodo.19735294.
- [5] D. M. Gordon, G. Kuperberg and O. Patashnik, New constructions for covering designs, Journal of Combinatorial Designs 3 (1995), no. 4, 269–284. doi:10.1002/jcd.3180030404.
- [6] D. M. Gordon and D. R. Stinson, Coverings, in C. J. Colbourn and J. H. Dinitz (eds.), Handbook of Combinatorial Designs, 2nd ed., Chapman & Hall/CRC, Boca Raton, 2007, 365–372.
- [7] D. Horsley, Generalising Fisher's inequality to coverings and packings, Combinatorica 37 (2017), no. 4, 673–696. doi:10.1007/s00493-016-3326-9.
- [8] D. Horsley and R. Singh, New lower bounds for -coverings, Journal of Combinatorial Designs 26 (2018), no. 8, 369–386. doi:10.1002/jcd.21591.
- [9] Q. M. Hussain, On the totality of the solutions for the symmetrical incomplete block designs: , or , Sankhyā 7 (1945), 204–208.
- [10] C. Krug, The covering number is , preprint (2026). arXiv:2607.23766.
- [11] The mathlib Community, The Lean mathematical library, in Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs (CPP 2020), ACM, 2020, 367–381. doi:10.1145/3372885.3373824.
- [12] W. H. Mills, Covering designs I: Coverings by a small number of subsets, Ars Combinatoria 8 (1979), 199–315.
- [13] W. H. Mills and R. C. Mullin, Coverings and packings, in J. H. Dinitz and D. R. Stinson (eds.), Contemporary Design Theory: A Collection of Surveys, Wiley, New York, 1992, 371–399.
- [14] L. de Moura and S. Ullrich, The Lean 4 theorem prover and programming language, in Automated Deduction – CADE 28, Lecture Notes in Computer Science 12699, Springer, 2021, 625–635. doi:10.1007/978-3-030-79876-5_37.
- [15] Palomar, a registry of machine-checked Lean proofs, entry PALOMAR-2026-10-04-000003, version 2; accessed 12 October 2026.
palomar-registry.org/entry?id=PALOMAR-2026-10-04-000003. - [16] J. Schönheim, On coverings, Pacific Journal of Mathematics 14 (1964), 1405–1411. doi:10.2140/pjm.1964.14.1405.
- [17] A. Sidorenko, What we know and what we do not know about Turán numbers, Graphs and Combinatorics 11 (1995), 179–199. doi:10.1007/BF01929486.
- [18] D. T. Todorov, On some covering designs, Journal of Combinatorial Theory, Series A 39 (1985), 83–101. doi:10.1016/0097-3165(85)90084-6.