C(24,14,4)≥ 20

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.

Warm-up: a covering you can finish

Seven points, seven blocks of three. Cover every pair. Each row is a block; click cells to move points. You’re one move away.

13
23
33
43
53
63
73

2 of 21 pairs not covered

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.

Lemma A.3C(22,12,2) ≥ 6Corollary A.4Degrees ≥ 11,codegrees ≥ 6Equation (7)Low points have5 units of excessLemma 3.1Relations comefrom componentsProposition 3.2≥ 3 componentson ≤ 16 pointsLemma A.6Codegree-2 pairsform a matchingTheorem 2.1Eleven-blockrigidity: twinsCorollary 2.3Zero block sumsreverse on twinsSection 4.1Quadruples givetwo completionsProposition 4.1No balancedquadrupleLemma 5.1Five triples onsix positionsSection 5No remainingcomponentsTheorem 1.1C(24,14,4) ≥ 20C(25,15,5) ≥ 34
Arrows point from a result to the results that use it.

The paper’s introduction and notation

A structural lower bound for C(24,14,4)C(24,14,4), by James Chang, 11 October 2026.

We prove C(24,14,4)≥20C(24,14,4)\ge20 and hence C(25,15,5)≥34C(25,15,5)\ge34. 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 (22,12,3)(22,12,3) 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 (v,k,t)(v,k,t) cover is a family of kk-element subsets of a vv-element set in which every tt-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 C(v,k,t)C(v,k,t). Taking complements of blocks identifies covering numbers with Turán numbers of hypergraphs, C(v,k,t)=T(v,v−t,v−k)C(v,k,t)=T(v,v-t,v-k) [17]. Surveys of covering designs include [13, 6].

Permalink

Theorem 1.1. Every (24,14,4)(24,14,4) cover has at least twenty blocks. In particular,

C(24,14,4)≥20.C(24,14,4)\ge20.

The La Jolla Covering Repository [4] lists the lower bounds C(24,14,4)≥19C(24,14,4)\ge19 and C(25,15,5)≥32C(25,15,5)\ge32. 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 (24,14,4)(24,14,4) construction of Ochmat and the forty-two-block (25,15,5)(25,15,5) construction of Atzeni listed in the Covering Repository [3] gives

20≤C(24,14,4)≤23,34≤C(25,15,5)≤42.20\le C(24,14,4)\le23,\qquad 34\le C(25,15,5)\le42.

Neither covering number is determined here.

The starting point is an elementary pair-cover obstruction:

C(22,12,2)≥6.C(22,12,2)\ge6.

Its proof is included in Appendix A. Taking derivatives through points and counting incidences then gives

C(23,13,3)≥11,C(24,14,4)≥19.C(23,13,3)\ge11,\qquad C(24,14,4)\ge19.

The first two bounds are sharp: C(22,12,2)=6C(22,12,2)=6 and C(23,13,3)=11C(23,13,3)=11 [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 (24,14,4)(24,14,4) cover occurs in at least eleven blocks. Nineteen blocks would supply 19⋅14=26619\cdot14=266 incidences, only two more than the required 24⋅11=26424\cdot11=264. Thus at least twenty-two points have degree exactly eleven. Their incidence vectors lie in R19\RR^{19}, 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 C(12,6,4)=41C(12,6,4)=41 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 B=(Bi)i∈I\calB=(B_i)_{i\in I}, 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

dB(p)=#{i:p∈Bi},λB(p,q)=#{i:p,q∈Bi}.d_{\calB}(p)=\#\{i:p\in B_i\},\qquad \lam_{\calB}(p,q)=\#\{i:p,q\in B_i\}.

Thus λB(p,p)=dB(p)\lam_{\calB}(p,p)=d_{\calB}(p). Subscripts are omitted when the family is clear. For kk-element blocks, double counting gives

∑pd(p)=k∣I∣,∑qλ(p,q)=k d(p).(1)\sum_p d(p)=k|I|, \qquad \sum_q\lam(p,q)=k\,d(p).\tag{1}

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 {p,q}\{p,q\} or i<ji<j.

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.

The move the whole proof reuses

Pick a point. The blocks through it, with the point taken out, still cover something smaller.

1234567
1
2
3
4
5
6
7

The Fano plane from the warm-up: every pair of the 7 points is in exactly one block.

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.

Try to cover the 100 cross pairs

Each of the three other blocks has room for 12 points of X ∪ Y. It covers the pairs in the rectangle its X points × its Y points. Toggle points in and out of each block.

First block · 12/12
X
Y
Second block · 12/12
X
Y
Third block · 12/12
X
Y

Rows: points of X. Columns: points of Y.

96 of 100 pairs covered

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.

Where 19 comes from

Schönheim’s bound: the blocks through any point form a smaller covering, so C(v, k, t) ≥ ⌈v/k × C(v−1, k−1, t−1)⌉. Each row uses the one above it.

Covering numberLower boundFrom
C(22,12,2)6Mills, 1979
C(23,13,3)11⌈23 × 6 / 13⌉
C(24,14,4)19⌈24 × 11 / 14⌉
C(25,15,5)32⌈25 × 19 / 15⌉

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

Permalink

Lemma A.1 (Two-rectangle capacity). Let X,YX,Y be disjoint nonempty sets of sizes a,ba,b. Suppose two sets of size at most kk cover every cross-pair {x,y}\{x,y\}, x∈Xx\in X, y∈Yy\in Y. Then at least one of

a+b≤k,2a+b≤2k,a+2b≤2ka+b\le k,\qquad 2a+b\le2k,\qquad a+2b\le2k

holds.

Proof. Call the two sets A,BA,B. If both contain XX, their intersections with YY together cover YY, giving 2a+b≤∣A∣+∣B∣≤2k2a+b\le |A|+|B|\le2k. If neither contains XX, a point of X∖AX\setminus A forces Y⊆BY\subseteq B, and a point of X∖BX\setminus B forces Y⊆AY\subseteq A. Also X⊆A∪BX\subseteq A\cup B, giving a+2b≤2ka+2b\le2k. In the remaining case exactly one, say AA, contains XX. A point of X∖BX\setminus B forces Y⊆AY\subseteq A, so a+b≤ka+b\le k. ∎

Permalink

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 36<4036<40. Some point therefore occurs in exactly one set, say x∈Xx\in X occurs only in AA. Then Y⊆AY\subseteq A, so ∣A∩X∣≤2|A\cap X|\le2. There are at least eight points of XX outside AA. The other two sets must cover every cross-pair between these points and the ten points of YY. The three alternatives in Lemma A.1 all fail: 8+10>128+10>12, 2⋅8+10>242\cdot8+10>24, and 8+2⋅10>248+2\cdot10>24. ∎

Permalink

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 60<3⋅2260<3\cdot22, so some point pp has degree at most two. The blocks through pp must cover all twenty-two points between them, and one twelve-element block cannot do so. Hence pp has degree exactly two. Call its two blocks A,BA,B. They satisfy A∪B=VA\cup B=V and ∣A∩B∣=2|A\cap B|=2.

The sets X=V∖AX=V\setminus A and Y=V∖BY=V\setminus B are disjoint and both have size ten. Neither AA nor BB covers a cross-pair from XX to YY. The remaining three blocks would cover all these cross-pairs, contrary to Lemma A.2. ∎

Permalink

Corollary A.4 (Degree and codegree lower bounds). A (23,13,3)(23,13,3) cover has at least eleven blocks. In any (24,14,4)(24,14,4) cover, every point has degree at least eleven and every pair of distinct points has codegree at least six.

Proof. In a (23,13,3)(23,13,3) cover, the derivative through any point is a (22,12,2)(22,12,2) cover, so every point has degree at least six. If there are bb blocks, 13b≥23⋅6=13813b\ge23\cdot6=138, and thus b≥11b\ge11. Taking one-point and two-point derivatives of a (24,14,4)(24,14,4) cover proves the other assertions. ∎

In Lean

Checked by Lean6 Lean declarations

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.

(a) one point of degree 13(b) two points of degree 12
Each column is a point and each square one block containing it. Every point needs at least 11 blocks, and 19 blocks of 14 points have 266 = 24 × 11 + 2 incidences, so only two extra squares are left over.

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.

Degrees and codegrees of the best attempt

This is the 19-block arrangement from the home page. Each bar is a point’s degree, the number of blocks containing it. In a real covering every bar would reach 11, and every pair would share at least 6 blocks. Here 4 points fall short and 42 pairs share only 5. Click a point to see its codegrees.

From the paper

3 Near-equality forces balanced components

From now on suppose that T\calT is a (24,14,4)(24,14,4) cover with nineteen indexed blocks. The elementary bounds in Corollary A.4 give

d(p)≥11,λ(p,q)≥6(p≠q),∑p(d(p)−11)=2.d(p)\ge11,\qquad \lam(p,q)\ge6\quad(p\ne q), \qquad \sum_p(d(p)-11)=2.

Call a point low if its degree is eleven, and high otherwise. Write LL 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

wpq=λ(p,q)−6,wpp=0.w_{pq}=\lam(p,q)-6,\qquad w_{pp}=0.

Equation (1) gives the full weighted row sums

∑qwpq=13d(p)−138.(7)\sum_qw_{pq}=13d(p)-138.\tag{7}

In particular, each low point has total excess weight five.

In Lean

Checked by Lean3 Lean declarations

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.

Which signings cost nothing?

Give each point +1, −1 or 0 by clicking it. Identity (8) adds up three costs: the total squared, every point with unused excess (δ above 0) that isn’t 0, and every edge whose two ends don’t cancel. Find a signing that costs nothing and isn’t all zeros.

233252220u · δ 00v · δ 00s · δ 00t · δ 00q · δ 00q′ · δ 00a · δ 10b · δ 10c · δ 1

total 0 + unused excess 0 + edges 0 = ‖Σ ap rp‖² 0

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 rp∈{0,1}19r_p\in\{0,1\}^{19} be the incidence vector of a low point pp: its iith coordinate records whether p∈Bip\in B_i. Join two low points whenever wpq>0w_{pq}>0. 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

δp=5−∑q∈Lwpq≥0.\delta_p=5-\sum_{q\in L}w_{pq}\ge0.

For arbitrary real coefficients (ap)p∈L(a_p)_{p\in L}, we have

∥∑p∈Laprp∥2=6(∑p∈Lap)2+∑p∈Lδpap2+∑{p,q}⊆Lwpq(ap+aq)2.(8)\boxed{\begin{aligned} \left\|\sum_{p\in L}a_pr_p\right\|^2 ={}&6\left(\sum_{p\in L}a_p\right)^2 +\sum_{p\in L}\delta_pa_p^2\\ &+\sum_{\{p,q\}\subseteq L}w_{pq}(a_p+a_q)^2. \end{aligned}}\tag{8}

To verify it, expand the left side using ⟨rp,rp⟩=11\langle r_p,r_p\rangle=11 and ⟨rp,rq⟩=6+wpq\langle r_p,r_q\rangle=6+w_{pq} for p≠qp\ne q. On the right side, the edge-square terms contribute ∑q∈Lwpq\sum_{q\in L}w_{pq} to the coefficient of ap2a_p^2; this combines with δp\delta_p to give five. The remaining six comes from the first square. The cross terms agree as well.

Define the incidence map

A:RL⟶R19,A(a)=∑p∈Laprp.A:\RR^L\longrightarrow\RR^{19},\qquad A(a)=\sum_{p\in L}a_pr_p.

Call a connected component of the low-point graph balanced if it is bipartite and all its vertices have δp=0\delta_p=0. For such a component, choose a bipartition C+,C−C^+,C^- and let bC=1C+−1C−∈RLb_C=\one_{C^+}-\one_{C^-}\in\RR^L be its signed indicator vector.

Permalink

Lemma 3.1 (The incidence relation space). Every balanced component has equally large nonempty parts. The vectors bCb_C, one for each balanced component CC, form a basis of ker⁡A\ker A. In particular,

#{balanced components}=dim⁡ker⁡A≥∣L∣−19≥3.\#\{\text{balanced components}\}=\dim\ker A\ge |L|-19\ge3.

Proof. All terms on the right of (8) are nonnegative. If A(a)=0A(a)=0, the first square gives ∑p∈Lap=0\sum_{p\in L}a_p=0, and the other terms give

δp>0 ⟹ ap=0,wpq>0 ⟹ aq=−ap.(9)\delta_p>0\ \Longrightarrow\ a_p=0, \qquad w_{pq}>0\ \Longrightarrow\ a_q=-a_p.\tag{9}

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 ap=−apa_p=-a_p and hence ap=0a_p=0, so such a component must be bipartite. Every vertex must also have δp=0\delta_p=0. 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

5∣C+∣=5∣C−∣.5|C^+|=5|C^-|.

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 a=bCa=b_C. The total coefficient sum is zero by equality of the part sizes. There is no unused excess on CC, every positive-weight edge within CC joins opposite signs, and no edge joins CC to another low-point component. Every term vanishes, so bC∈ker⁡Ab_C\in\ker A. Equivalently,

∑p∈C+rp=∑p∈C−rp.(10)\sum_{p\in C^+}r_p=\sum_{p\in C^-}r_p.\tag{10}

Coordinate by coordinate, this says that every block is balanced:

∣Bi∩C+∣=∣Bi∩C−∣.(11)|B_i\cap C^+|=|B_i\cap C^-|.\tag{11}

The propagation rule (9) shows that any element of ker⁡A\ker A 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 rank⁡A≤19\operatorname{rank}A\le19 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

λ(p,q)=6(12)\lam(p,q)=6\tag{12}

whenever pp lies in a balanced component and qq lies outside it, or whenever distinct p,qp,q lie on the same side of a component.

3.2 There is room for at most sixteen balanced points

Let UU 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 UU, by (12). A low point can receive at most five units, so at least seven low points lie outside UU. Thus ∣U∣≤23−7=16|U|\le23-7=16.

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 UU. Each receives at most five, so at least five low points lie outside UU. Hence ∣U∣≤17|U|\le17, and evenness improves the bound to sixteen.

Permalink

Proposition 3.2. A hypothetical nineteen-block cover has at least three balanced components, all of positive even size, with total size at most sixteen. Their equal parts satisfy blockwise balance (11), and their points satisfy the codegree rule (12).

In Lean

Checked by Lean5 Lean declarations

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 shape Theorem 2.1 forces

Eleven blocks of 12 covering every triple of 22 points, every point in 6 blocks. Click a point, then another, to see how many blocks they share. Click a block number to compare it with the others.

Columns come in pairs: point 1 and point 2 are twins, then 3 and 4, and so on.

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.

Two counts that leave no room

Eleven blocks (rows) on 22 points (columns), every point in 6 blocks. It starts as the doubled design. A swap moves one point out of a block and another in, which keeps every row and column count. The double count (5) holds after every swap; the covering doesn’t.

Energy Ep of each point. Lemma 2.2: at most 9 in a covering.

(5) Σ Ep = 198  and  198 + 2 Σ (sij − 6)² = 198 + 2 × 0 = 198

(6) Σ (9 − Ep) + 2 Σ (sij − 6)² = 0 + 0 = 0

cover triples of points in no block: 0 of 1,540

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.

Permalink

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 σ(p)\sigma(p) for the twin of pp. Thus σ\sigma is a fixed-point-free involution, and

λ(p,q)={6,q=p or q=σ(p),3,otherwise.(2)\lam(p,q)= \begin{cases} 6,&q=p\text{ or }q=\sigma(p),\\ 3,&\text{otherwise}. \end{cases}\tag{2}

Compressing each twin pair to one point produces eleven six-element blocks on eleven points, with every pair in exactly three blocks: a symmetric 22-(11,6,3)(11,6,3) 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 pp, with pp retained, cover every pair of the twenty-two points: extend the pair with pp to a triple when necessary. Since the total degree is 11⋅12=22⋅611\cdot12=22\cdot6, all point degrees are exactly six.

For distinct p,qp,q, the blocks through both must cover the other twenty points, ten at a time. Hence

2≤λ(p,q)≤6.2\le\lam(p,q)\le6.

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 pp. It follows that, for a fixed pp, at most one qq has λ(p,q)=2\lam(p,q)=2. In other words, the pairs of codegree two form a matching.

For distinct points put epq=λ(p,q)−3e_{pq}=\lam(p,q)-3, and put epp=0e_{pp}=0. These deviations are symmetric, and every row has sum

∑qepq=11⋅6−21⋅3=3.(3)\sum_q e_{pq}=11\cdot6-21\cdot3=3.\tag{3}

The energy at pp is

Ep=∑qepq 2.E_p=\sum_q e_{pq}^{\,2}.

We will bound this energy in two ways: locally from the covering constraints, and globally by counting the same configurations through pairs of blocks.

Permalink

Lemma 2.2. For every point, Ep≤9E_p\le9. If its row contains a negative deviation, then Ep=5E_p=5.

Proof. For a nonnegative row, the sum of squares is at most the square of the sum, so (3) gives Ep≤9E_p\le9.

Otherwise the row has a unique negative entry, epq=−1e_{pq}=-1. The two blocks containing both p,qp,q partition the other twenty points after p,qp,q are deleted. Thus each point z∉{p,q}z\notin\{p,q\} occurs in exactly one of these two blocks. Exactly one of the eleven blocks contains neither pp nor qq, since 6+6−2=106+6-2=10 contain at least one of them. For any such zz, inclusion–exclusion in its six incident blocks, counting the block through p,q,zp,q,z twice, gives

λ(p,z)+λ(q,z)+#{i:z∈Bi, p,q∉Bi}=7.\lam(p,z)+\lam(q,z) +\#\{i:z\in B_i,\ p,q\notin B_i\}=7.

The last term is zero or one. The matching restriction implies λ(p,z),λ(q,z)≥3\lam(p,z),\lam(q,z)\ge3, so each is three or four. The row at pp therefore has one entry −1-1, with all remaining entries zero or one. Its sum is three, so exactly four entries are one. Thus Ep=1+4=5E_p=1+4=5. ∎

2.2 A double count makes every defect vanish

Put sij=∣Bi∩Bj∣s_{ij}=|B_i\cap B_j|. Count a choice of two distinct points and two distinct block indices containing them in two ways:

∑{p,q}(λ(p,q)2)=∑i<j(sij2).(4)\sum_{\{p,q\}}\binom{\lam(p,q)}2 =\sum_{i<j}\binom{s_{ij}}2.\tag{4}

The first moments are equally simple:

∑{p,q}λ(p,q)=11(122)=726,∑i<jsij=22(62)=330.\sum_{\{p,q\}}\lam(p,q)=11\binom{12}{2}=726, \qquad \sum_{i<j}s_{ij}=22\binom62=330.

Using 2(n2)=n2−n2\binom n2=n^2-n in (4) and expanding the squared deviations now gives

∑pEp=198+2∑i<j(sij−6)2.(5)\sum_p E_p=198+2\sum_{i<j}(s_{ij}-6)^2.\tag{5}

For completeness, the expansion is

∑pEp=2∑{p,q}λ(p,q)2−12⋅726+18(222),2∑i<j(sij−6)2=2∑i<jsij2−24⋅330+72(112);\begin{aligned} \sum_pE_p &=2\sum_{\{p,q\}}\lam(p,q)^2-12\cdot726+18\binom{22}{2},\\ 2\sum_{i<j}(s_{ij}-6)^2 &=2\sum_{i<j}s_{ij}^2-24\cdot330+72\binom{11}{2}; \end{aligned}

subtracting these expressions and using (4) yields (5).

Together with Lemma 2.2, this becomes

 ∑p(9−Ep)+2∑i<j(sij−6)2=0. (6)\boxed{\ \sum_p(9-E_p)+2\sum_{i<j}(s_{ij}-6)^2=0.\ }\tag{6}

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

(∑qepq)2−∑qepq 2=2∑{q,r}epqepr=0,\Bigl(\sum_q e_{pq}\Bigr)^2-\sum_q e_{pq}^{\,2} =2\sum_{\{q,r\}}e_{pq}e_{pr}=0,

at most one entry can be positive. There is therefore exactly one entry equal to three. Denote its column by σ(p)\sigma(p).

The diagonal entry is zero, so σ(p)≠p\sigma(p)\ne p. Symmetry and uniqueness give σ(σ(p))=p\sigma(\sigma(p))=p. 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). ∎

Permalink

Corollary 2.3 (Zero block sums reverse weights on twins). Assign real weights zpz_p to the points of an eleven-block (22,12,3)(22,12,3) cover. If every block has total weight zero, then zσ(p)=−zpz_{\sigma(p)}=-z_p for each point pp.

Proof. Summing all block weights gives 6∑pzp=06\sum_pz_p=0. For a fixed point pp, sum the weights of the blocks containing it and use (2):

0=∑i:p∈Bi∑q∈Bizq=3(zp+zσ(p))+3∑qzq.0=\sum_{i:p\in B_i}\sum_{q\in B_i}z_q =3\bigl(z_p+z_{\sigma(p)}\bigr)+3\sum_qz_q.

The final sum vanishes, proving the assertion. ∎

Permalink

Remark 2.4. Theorem 2.1 determines the eleven-block (22,12,3)(22,12,3) covers up to isomorphism. Compressing twin pairs gives a symmetric 22-(11,6,3)(11,6,3) design, whose complementary design is a 22-(11,5,2)(11,5,2) 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 (22,12,3)(22,12,3) 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 33-set SS of the biplane; since two biplane blocks share exactly two points, at most one block contains SS, and inclusion–exclusion shows that at least 11−3⋅5+3⋅2−1=111-3\cdot5+3\cdot2-1=1 biplane block is disjoint from SS. Since C(22,12,3)=11C(22,12,3)=11 [4], the optimal (22,12,3)(22,12,3) cover is therefore unique up to isomorphism. We are not aware of a previous statement of this uniqueness.

A.2 The matching restriction

Permalink

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 R,YR,Y are the parts and D1,D2,D3D_1,D_2,D_3 give such a cover. Add three fresh points a,b,ca,b,c. The following five twelve-element sets would pair-cover the resulting twenty-two-element set:

R∪{a,b,c},Y∪{b,c},D1∪{a},D2∪{a},D3∪{a}.R\cup\{a,b,c\},\qquad Y\cup\{b,c\},\qquad D_1\cup\{a\},\quad D_2\cup\{a\},\quad D_3\cup\{a\}.

Pairs internal to RR or YY and pairs involving b,cb,c are covered by the first two blocks; cross-pairs are covered by the last three. Every point of YY occurs in some DiD_i, because its cross-pairs with the nonempty set RR are covered, so pairs from aa to YY are also covered. This contradicts Lemma A.3. ∎

Permalink

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 p,qp,q both have degree two. The two blocks through pp cover all points, so their intersection is exactly {p}\{p\}. Label them A,BA,B with q∈Aq\in A. The other block through qq, denoted by CC, satisfies A∩C={q}A\cap C=\{q\}. Consequently there is a partition of the other nineteen points into sets R,YR,Y with ∣R∣=9|R|=9, ∣Y∣=10|Y|=10, such that

A={p,q}∪R,B={p}∪Y,C={q}∪Y.A=\{p,q\}\cup R,\quad B=\{p\}\cup Y,\quad C=\{q\}\cup Y.

The remaining three blocks avoid p,qp,q and must cover all cross-pairs between RR and YY, contrary to Lemma A.5. ∎

In Lean

Checked by Lean6 Lean declarations

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:

Fit the balanced components into 16 points

Step 3 gives the rules: every component has an even number of points (at least 2), together they fit in 16 points, and there are at least 3 of them, or at least 4 if some point lies in 13 blocks. Add components and see what you get.

Add a component of size

Every possibility

With two points of degree 12 there are 42 ways to choose the component sizes. All but two contain a 4 or two 2s, which give a balanced quadruple. The two that don’t are {2, 6, 6} and {2, 6, 8}: the remaining components of Step 7. With a point of degree 13 there are 26 ways, and every one gives a quadruple.

  • {2, 2, 2}
  • {2, 2, 2, 2}
  • {2, 2, 2, 2, 2}
  • {2, 2, 2, 2, 2, 2}
  • {2, 2, 2, 2, 2, 2, 2}
  • {2, 2, 2, 2, 2, 2, 2, 2}
  • {2, 2, 4}
  • {2, 2, 2, 4}
  • {2, 2, 2, 2, 4}
  • {2, 2, 2, 2, 2, 4}
  • {2, 2, 2, 2, 2, 2, 4}
  • {2, 4, 4}
  • {2, 2, 4, 4}
  • {2, 2, 2, 4, 4}
  • {2, 2, 2, 2, 4, 4}
  • {4, 4, 4}
  • {2, 4, 4, 4}
  • {2, 2, 4, 4, 4}
  • {4, 4, 4, 4}
  • {2, 2, 6}
  • {2, 2, 2, 6}
  • {2, 2, 2, 2, 6}
  • {2, 2, 2, 2, 2, 6}
  • {2, 4, 6}
  • {2, 2, 4, 6}
  • {2, 2, 2, 4, 6}
  • {4, 4, 6}
  • {2, 4, 4, 6}
  • {2, 6, 6}
  • {2, 2, 6, 6}
  • {4, 6, 6}
  • {2, 2, 8}
  • {2, 2, 2, 8}
  • {2, 2, 2, 2, 8}
  • {2, 4, 8}
  • {2, 2, 4, 8}
  • {4, 4, 8}
  • {2, 6, 8}
  • {2, 2, 10}
  • {2, 2, 2, 10}
  • {2, 4, 10}
  • {2, 2, 12}

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.

FamilyBlocksContainsPoints of X
𝓗6u v s t10
𝓔5u, s or t12
𝓕5v, s or t12
𝓖3none14
How the 19 blocks split around a balanced quadruple u, v, s, t, sorted by which of u, v they contain. The balance condition then decides how many of s, t each block contains, and so how many of the other 20 points, X.

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 u,v,s,tu,v,s,t such that every block satisfies

1u∈B+1v∈B=1s∈B+1t∈B.(13)\one_{u\in B}+\one_{v\in B}=\one_{s\in B}+\one_{t\in B}.\tag{13}

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

Permalink

Proposition 4.1. A nineteen-block (24,14,4)(24,14,4) 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 1u∈B\one_{u\in B} and sum over all blocks:

11+λ(u,v)=λ(u,s)+λ(u,t),wus+wut=5+wuv.11+\lam(u,v)=\lam(u,s)+\lam(u,t), \qquad w_{us}+w_{ut}=5+w_{uv}.

The full excess row at uu is five, so wuv+wus+wut≤5w_{uv}+w_{us}+w_{ut}\le5. Nonnegativity forces wuv=0w_{uv}=0, and hence λ(u,v)=6\lam(u,v)=6.

Let XX be the twenty points outside the quadruple. Partition the blocks according to membership of u,vu,v, and use the same symbols for their traces on XX:

H\calHE\calEF\calFG\calG
Membership of u,vu,vbothuu onlyvv onlyneither
Number of blocks6553
Size of a trace on XX10121214

The numbers of blocks are ∣H∣=λ(u,v)=6|\calH|=\lam(u,v)=6, ∣E∣=∣F∣=11−6=5|\calE|=|\calF|=11-6=5, and ∣G∣=19−6−5−5=3|\calG|=19-6-5-5=3. 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 u,vu,v also contains s,ts,t; a block containing exactly one of u,vu,v contains exactly one of s,ts,t; a block containing neither contains neither.

The family H\calH covers every pair of XX, by attaching u,vu,v to that pair. Similarly H∪E\calH\cup\calE and H∪F\calH\cup\calF each cover every triple of XX, by attaching uu or vv.

For either D=E\calD=\calE or D=F\calD=\calF, add two new points a,ba,b to each of the six blocks of H\calH, and leave the five blocks of D\calD unchanged. The result is an eleven-block (22,12,3)(22,12,3) cover. Old triples are covered by H∪D\calH\cup\calD; triples containing exactly one new point are covered because H\calH covers pairs; triples containing both new points are covered because pair coverage also ensures that every old point occurs in H\calH.

Apply Theorem 2.1. The new points occur together in precisely the six enlarged H\calH-blocks, so they are twins. An old point xx is not their twin, and its codegree with aa is therefore three. That codegree is exactly dH(x)d_{\calH}(x). Its total degree in the completion is six, so dD(x)=3d_{\calD}(x)=3 as well. Thus

dH(x)=dE(x)=dF(x)=3(x∈X).(14)d_{\calH}(x)=d_{\calE}(x)=d_{\calF}(x)=3\qquad(x\in X).\tag{14}

All three degree identities have come from the completions; no separate regularity calculation for H\calH is needed.

In Lean

Checked by Lean3 Lean declarations

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.

Seven points, room for six

A six-regular graph on 20 points, standing in for Γ. The two dashed points lie in all three 𝓖-blocks; the others are ordinary, each with one colour. Click a point to colour it and its neighbours, which must match.

1234567891011121314151617181920

14 points are special or next to one, at most 2 + 6 + 6 = 14.

special or next to one forced to share a colour

From the paper

4.2 The completions have the same twin pairs

The twin involution of either completion restricts to XX, since the new points are twins of each other. For distinct old points,

λH(x,y)+λD(x,y)={6,x,y are twins in the completion,3,otherwise.(15)\lam_{\calH}(x,y)+\lam_{\calD}(x,y)= \begin{cases} 6,&x,y\text{ are twins in the completion},\\ 3,&\text{otherwise}. \end{cases}\tag{15}

Both summands are at most three by (14). Also λH(x,y)≥1\lam_{\calH}(x,y)\ge1 from pair coverage, and λD(x,y)≥1\lam_{\calD}(x,y)\ge1: each point occurs in three of the five D\calD-blocks, so their sets of incident indices must intersect.

It follows that x,yx,y are twins exactly when λH(x,y)=3\lam_{\calH}(x,y)=3. In one direction, a total of six forces both summands to be three. In the other, an H\calH-codegree of three makes the total at least four, so it cannot be the non-twin value three. This criterion depends only on H\calH. Therefore the two completions have the same twin pairs. Every other distinct pair has H\calH-codegree one or two.

Let Γ\Gamma be the simple graph on XX in which distinct x,yx,y are adjacent when λH(x,y)=2\lam_{\calH}(x,y)=2. This graph is six-regular. Indeed, the codegree row sum, including the diagonal, is 10⋅3=3010\cdot3=30. 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

dT(x)=9+dG(x).d_{\calT}(x)=9+d_{\calG}(x).

Thus 2≤dG(x)≤32\le d_{\calG}(x)\le3. The total G\calG-degree is 3⋅14=423\cdot14=42, so exactly two of the twenty points have G\calG-degree three; the other eighteen have degree two. Call the latter points ordinary.

Color each ordinary point by the unique G\calG-block omitting it. Every color class has size at most six, because that block contains fourteen of the twenty points. If ordinary x,yx,y are adjacent in Γ\Gamma, then λH(x,y)=2\lam_{\calH}(x,y)=2, and (15) gives

λE(x,y)=λF(x,y)=1.\lam_{\calE}(x,y)=\lam_{\calF}(x,y)=1.

The full codegree is at least six, so λG(x,y)≥2\lam_{\calG}(x,y)\ge2. Each point occurs in exactly two G\calG-blocks, so they occur in the same two and have the same color.

The two nonordinary points together with their neighbors in Γ\Gamma occupy at most 2+6+6=142+6+6=14 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

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:

Fit the missing triples

Six blocks, drawn as dots. Each of the five chosen points misses three of them, a triangle here, and any two triangles must share exactly one corner. Step 7 needs five triangles. Pick as many as you can.

123456

0 of 5 triangles · 0 corners on 6 blocks, at most 2 each

From the paper

5 Excluding the remaining components

We first record the elementary set-system obstruction that will end the proof.

Permalink

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 2+6+6+6=202+6+6+6=20 points. Their sizes, in increasing order, must therefore be

(2,6,6)or(2,6,8).(2,6,6)\quad\text{or}\quad(2,6,8).

There are exactly three balanced components, so Lemma 3.1 gives ∣L∣−19≤3|L|-19\le3. Since ∣L∣≥22|L|\ge22, we have ∣L∣=22|L|=22. The two high points therefore both have degree twelve, because the total degree excess is two.

Let {p,q}\{p,q\} be that size-two component, and choose two other components C,DC,D. Their equal parts satisfy

∣C+∣=∣C−∣≥3,∣D+∣=∣D−∣≥3.|C^+|=|C^-|\ge3,\qquad |D^+|=|D^-|\ge3.

Blockwise balance implies that p,qp,q occur in exactly the same eleven blocks. Delete p,qp,q from those blocks and call the resulting family on twenty-two points P\calP. It consists of eleven twelve-element blocks covering every triple: attach pp to the triple and use the original four-cover property. The remaining eight original blocks form a family R\calR; these all avoid p,qp,q.

Theorem 2.1 applies to P\calP. Assign weight +1+1 to C+C^+, −1-1 to C−C^-, and zero to all remaining points. Every P\calP-block has weight zero by (11). Corollary 2.3 therefore puts the P\calP-twin of each point of C+C^+ in C−C^-. Likewise the twins of points in D+D^+ lie in D−D^-. In particular, no two points of C+∪D+C^+\cup D^+ are P\calP-twins.

5.2 Subtracting the eleven-block cover

Choose five points S⊆C+∪D+S\subseteq C^+\cup D^+. This is possible because the union has at least six points. Also choose either of the two high points, denoted by hh.

All selected points are low. The high point is outside every balanced component, so (12) applies to its codegrees with SS. No two distinct selected points are P\calP-twins, and hh is not the P\calP-twin of a selected point because that twin lies in the opposite side of its component. The degrees and codegrees now follow by subtraction:

QuantityOriginal T\calTEleven blocks P\calPEight blocks R\calR
Degree of x∈Sx\in S1165
Codegree of distinct x,y∈Sx,y\in S633
Degree of hh1266
Codegree of x∈Sx\in S and hh633

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 xx, let MxM_x be the set of residual block indices omitting it. Inclusion–exclusion gives

∣Mx∣=3(x∈S),∣Mh∣=2,|M_x|=3\quad(x\in S),\qquad |M_h|=2,
∣Mx∩My∣=8−5−5+3=1(x≠y in S),∣Mx∩Mh∣=8−5−6+3=0.|M_x\cap M_y|=8-5-5+3=1\quad(x\ne y\text{ in }S), \qquad |M_x\cap M_h|=8-5-6+3=0.

Thus the five MxM_x, for x∈Sx\in S, are triples on the same six indices outside MhM_h, and every two meet in exactly one index. This contradicts Lemma 5.1.

In Lean

Checked by Lean3 Lean declarations

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:

One step changes the whole ladder

Schönheim’s bound: the blocks through any point form a smaller covering, so C(v, k, t) ≥ ⌈v/k × C(v−1, k−1, t−1)⌉. Each row uses the one above it.

Covering numberOld boundFromNew boundFrom
C(23,13,3)11⌈23 × 6 / 13⌉—
C(24,14,4)19⌈24 × 11 / 14⌉20this proof
C(25,15,5)32⌈25 × 19 / 15⌉34⌈25 × 20 / 15⌉
C(26,16,6)52⌈26 × 32 / 16⌉56⌈26 × 34 / 16⌉
C(27,17,7)83⌈27 × 52 / 17⌉89⌈27 × 56 / 17⌉
C(28,18,8)130⌈28 × 83 / 18⌉139⌈28 × 89 / 18⌉

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 d(p)≥11d(p)\ge11 gives 14∣I∣≥24⋅11=26414|I|\ge24\cdot11=264, and hence ∣I∣≥19|I|\ge19. Excluding equality proves C(24,14,4)≥20C(24,14,4)\ge20. ∎

Permalink

Corollary 5.2. Every (25,15,5)(25,15,5) cover has at least thirty-four blocks. Thus C(25,15,5)≥34C(25,15,5)\ge34.

Proof. The derivative through any point is a (24,14,4)(24,14,4) cover, so every point has degree at least twenty. If the original cover has bb blocks, then

15b=∑pd(p)≥25⋅20=500,b≥⌈50015⌉=34.15b=\sum_p d(p)\ge25\cdot20=500, \qquad b\ge\left\lceil\frac{500}{15}\right\rceil=34.

∎

In Lean

Checked by Lean3 Lean declarations

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. [1] P. J. Cameron, Biplanes, Mathematische Zeitschrift 131 (1973), 85–101. doi:10.1007/BF01213827.
  2. [2] J. Chang, Lean formalization of C(24,14,4)≥20C(24,14,4)\ge20 and C(25,15,5)≥34C(25,15,5)\ge34, ancillary files to this article (2026); also at github.com/jamesyc/covering.
  3. [3] Covering Repository, construction records for (24,14,4)(24,14,4) and (25,15,5)(25,15,5), 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. [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. [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. [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. [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. [8] D. Horsley and R. Singh, New lower bounds for tt-coverings, Journal of Combinatorial Designs 26 (2018), no. 8, 369–386. doi:10.1002/jcd.21591.
  9. [9] Q. M. Hussain, On the totality of the solutions for the symmetrical incomplete block designs: λ=2\lambda=2, k=5k=5 or 66, Sankhyā 7 (1945), 204–208.
  10. [10] C. Krug, The covering number C(12,6,4)C(12,6,4) is 4141, preprint (2026). arXiv:2607.23766.
  11. [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. [12] W. H. Mills, Covering designs I: Coverings by a small number of subsets, Ars Combinatoria 8 (1979), 199–315.
  13. [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. [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. [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. [16] J. Schönheim, On coverings, Pacific Journal of Mathematics 14 (1964), 1405–1411. doi:10.2140/pjm.1964.14.1405.
  17. [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. [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.

Notation

d(p), λ(p,q)
Degree and codegree: the number of blocks containing p, and containing both p and q.
wpq
Excess: λ(p,q) − 6, how far a pair sits above its floor.
L
The low points: those of degree 11.
rp, δp
The incidence vector of a low point, and the part of its 5 units of excess it does not spend on other low points.
C⁺, C⁻
The two sides of a balanced component.
epq, Ep
Section 2: the deviation λ(p,q) − 3, and the energy, the sum of a point’s squared deviations.
sij
Section 2: the number of points blocks i and j share.
σ
The twin pairing: σ(p) is the twin of p.
𝓗, 𝓔, 𝓕, 𝓖
Section 4: the blocks with both u and v, only u, only v, neither.
X, Γ
Section 4: the 20 points outside the quadruple, and the graph joining pairs that share two 𝓗-blocks.
𝒫, ℛ
Section 5: the 11 blocks through the two-point component, and the other 8.
Mx
Section 5: the blocks of ℛ that omit x.