More blocks than points

The schedule essay settles which sizes admit a system of triples by two divisions, and the divisions are the whole answer: they are necessary by counting and sufficient by construction, with nothing in between.

That is unusually lucky. The general question — a design on $v$ points with blocks of size $k$, every pair of points in exactly $\lambda$ blocks — has counting conditions of the same shape, and they leave a great deal open. One thing they leave open is whether a design can be efficient: can it have fewer blocks than points?

The answer is no, and it is not a counting argument. It is a rank argument over the rational numbers, and nothing in the statement it proves mentions a number system at all.

What the counting says and does not #

Two counts follow from the definition and both are necessary.

From one point. A given point meets each of the other $v-1$ points, and each block through it introduces $k-1$ of them $\lambda$ times over. So every point lies in $r = \lambda(v-1)/(k-1)$ blocks, and that has to be a whole number.

From all pairs. There are $\binom{v}{2}$ pairs, each covered $\lambda$ times, and each block covers $\binom{k}{2}$. So the number of blocks is $b = \lambda v(v-1) / (k(k-1))$, which also has to be whole. Equivalently $bk = vr$, which is the count of point-in-block incidences taken both ways.

Those are the conditions the schedule essay uses. Neither says anything about $b$ against $v$. A design with $b < v$ would be a very efficient arrangement — more people than groups, every pair still meeting — and the arithmetic above does not forbid one at any parameters. What forbids it is Fisher’s inequality, proved by R. A. Fisher in 1940 in a paper about agricultural experiments.

The Gram matrix, and the one line that does it #

Write $N$ for the incidence matrix: a row per block, a column per point, a $1$ where the point is in the block. Then consider $N^{\mathsf T}N$, which is $v \times v$.

Its diagonal entry at point $p$ counts the blocks containing $p$, which is $r$. Its off-diagonal entry at points $p, q$ counts the blocks containing both, which is $\lambda$.

So the Gram matrix is $(r-\lambda)I + \lambda J$, where $J$ is all ones — a matrix with a constant on the diagonal and a different constant everywhere else. Such a matrix has a determinant that can be written down:

$$\det\big((r-\lambda)I + \lambda J\big) \;=\; (r-\lambda)^{\,v-1}\,\big(r + (v-1)\lambda\big).$$

The reason is that $J$ has one eigenvalue $v$ with the all-ones eigenvector and $v-1$ eigenvalues $0$ on its complement, so the whole matrix has eigenvalues $r + (v-1)\lambda$ once and $r - \lambda$ the rest of the time.

Both factors are positive whenever $r > \lambda$, which holds in any design with blocks smaller than everything — a point is in more blocks than it shares with any one other point. So the determinant is not nought, the Gram matrix is invertible, and $N$ has $v$ independent columns.

A matrix with $v$ independent columns has at least $v$ rows. That is the rank bound — or, since rows and columns are counted by the same number, the observation that $b$ rows cannot span more than $b$ dimensions — it is the only fact about matrices used, and it finishes the proof: $b \ge v$.

Where the argument gets its leverage #

It is worth being precise about what happened, because the manoeuvre is transferable and the transfer is the point.

The design is a combinatorial object: a set of sets. Nothing about it is a vector, and no addition is defined anywhere in its definition. The proof invents an addition — it puts the blocks in a vector space over the rationals, where a block is a $0/1$ vector — and then uses a fact about dimension that the combinatorics never mentions.

What makes that legitimate is that dimension bounds cardinality. A collection of $b$ vectors cannot span more than $b$ dimensions, and the design’s conditions force the span to be all $v$. That is the whole of the leverage, and it is why the argument gives an inequality rather than an equality — a rank argument bounds and does not construct.

And a design where the inequality is slack rather than tight, to show that the theorem is a floor rather than a prediction.

A design with fewer blocks would look like this #

It helps to see what is being ruled out, because fewer blocks than points is easy to say and hard to picture.

Suppose there were a design on thirteen points with blocks of four, every pair once, and only twelve blocks. The counting conditions would have to hold: each point in $r = 1 \cdot 12 / 3 = 4$ blocks, and $b = 13 \cdot 12 / 12 = 13$ blocks. So the count already gives thirteen, and twelve is arithmetically impossible at those parameters — the counting handles this case.

The parameters where the counting does not decide are the ones with $\lambda$ above one. Take $v = 16$, $k = 6$, $\lambda = 2$: then $r = 2 \cdot 15/5 = 6$ and $b = 2\cdot 16 \cdot 15 / 30 = 16$, so $b = v$ exactly and the counting permits it. Nudge the parameters to $v = 16$, $k = 8$, $\lambda = 7$ and the counts give $r = 7\cdot15/7 = 15$ and $b = 7\cdot16\cdot15/56 = 30$, comfortably above.

What the counting never produces is a $b$ below $v$, and the reason is that it cannot: rearranging $bk = vr$ and $r(k-1) = \lambda(v-1)$ gives $b = v$ exactly when $k = r$, and $b < v$ exactly when $k > r$ — a design whose blocks are larger than the number of blocks through a point. That is not forbidden by any count, and Fisher’s inequality is the statement that it is forbidden.

So the theorem’s content is precise: $k \le r$ always, blocks are never bigger than the number of blocks a point sits in. Said that way it sounds like something a clever counting argument ought to reach, and after eighty years nobody has found one.

What equality means #

A design where $b = v$ is called symmetric, and the name earns itself: in such a design every block has the same size as every point has blocks ($k = r$), and any two blocks meet in exactly $\lambda$ points — the dual statement, which was not assumed.

That last fact is not obvious and it comes from the same matrix. When $b = v$ the incidence matrix is square and invertible, so $N N^{\mathsf T}$ can be computed from $N^{\mathsf T} N$ by conjugation, and it comes out with the same shape — $r$ on the diagonal and $\lambda$ off it — which says exactly that two blocks meet $\lambda$ times.

So the duality of a projective plane — two points on one line, two lines through one point — is a consequence of squareness rather than a second axiom, and the seven-point plane states it as an axiom because that is how the geometry is usually set up. The matrix reading derives it.

Two figures are worth putting beside the argument before it is generalised, because between them they say what it is made of and what it is not made of.

Beside it, the instrument that settles the schedule question and is silent about this one.

The same technique, and the harder theorem it leads to #

The rank argument’s natural continuation is the one result that genuinely restricts which projective planes exist, and it is worth naming because it uses the same matrix and a great deal more.

Bruck–Ryser, 1949. If a projective plane of order $n$ exists and $n \equiv 1$ or $2 \pmod 4$, then $n$ is a sum of two squares. So there is no plane of order $6$, none of order $14$, none of order $21$.

The proof starts exactly where this essay’s does — with $N^{\mathsf T}N = nI + J$ — and then asks a question about rational equivalence of quadratic forms rather than about rank. The matrix equation says a certain form represents certain values over the rationals, a theorem of Minkowski and Hasse says when that is possible, and the condition it produces is the two-square condition.

That is the same two-square theorem that belongs to the number theory here, arriving in a question about schedules by way of a determinant. The connection is not decorative: it is the only known general obstruction to the existence of planes, and it says nothing at all when $n \equiv 0$ or $3 \pmod 4$ — which is why order $10$ needed thousands of hours of computer search to rule out and order $12$ is open.

Why the field matters, and which field #

The proof uses the rational numbers and nothing else, and it is worth asking what would happen over a different one, because the answer is not what the smoothness of the argument suggests.

Over the rationals the argument works and gives $b \ge v$. The determinant $(r-\lambda)^{v-1}(r + (v-1)\lambda)$ is a positive integer, so it is not zero and the rank is full.

Over a finite field of characteristic $p$ it can fail, and the failure is informative rather than a technicality. If $p$ divides $r - \lambda$, the Gram matrix becomes $\lambda J$ modulo $p$, which has rank one. So the incidence matrix’s rank over that field can be as small as one, and Fisher’s inequality is simply not available there.

That is not a defect; it is a different theorem. The rank of a design’s incidence matrix modulo $p$ is a genuine invariant, called the $p$-rank, and it distinguishes designs that are identical by every counting measure. The two non-isomorphic planes of order nine, for instance, have different $2$-ranks, and computing $p$-ranks is a standard way to separate designs a computer search has produced and cannot otherwise tell apart.

So the choice of field is the choice of which question is being asked. Over the rationals the rank is always $v$ and the information is the inequality; over $\mathbb{F}_p$ the rank varies and the information is about the design’s structure. Running the same computation over two fields gives two unrelated facts, which is the most useful thing to know about this technique.

Where the bound is used #

Experimental design, which is where it came from. Fisher’s question was about comparing $v$ treatments in blocks of $k$ plots — a field divided into strips, a batch of material split between machines — and balanced means every pair of treatments is compared equally often, so that no comparison is made more precisely than any other. The inequality says such an arrangement cannot economise on blocks, which has immediate practical content: blocks are fields or batches or days, and each one costs something. An experimenter asking for sixteen treatments in blocks of four, balanced, is told by this theorem that at least sixteen blocks will be needed before any construction is attempted.

Fingerprinting and pooled testing. Testing $v$ samples with $b$ pooled tests so that any single positive is identified needs the pools to be a design of this kind, and Fisher’s bound says how few tests can possibly do — which is the same counting-and-bounding structure a code’s parity checks have, with samples in place of bits.

Coding theory. The rows of an incidence matrix are codewords of constant weight with controlled pairwise overlap, and the rank bound limits how many such codewords can exist. Several bounds on codes are Fisher’s inequality with the field changed.

Resolvable designs and tournaments. A schedule in rounds needs $b$ at least $v$ and usually much more; Fisher’s bound is the floor a league’s fixture list is measured against, and the resolvable version of the triple system is the case where the extra structure pushes it further up.

And extremal set theory. The generalisation — that a family of sets with all pairwise intersections of the same size has at most $v$ members — is the Fisher inequality for $\lambda$-designs, and its proof is this one with the design conditions weakened. That version has no combinatorial proof either, which is the fact worth carrying: several statements in this area are known only by linear algebra, and the absence of a counting proof after eighty years is evidence that the linear structure is doing something real.

The generalisation that is one line shorter #

There is a version of the argument that drops the design conditions almost entirely, and it is worth having because it shows how little the proof was using.

The Frankl–Wilson / Fisher-type inequality: let $A_1, \dots, A_m$ be subsets of a $v$-element set such that every two distinct ones meet in exactly $\lambda$ elements, for one fixed $\lambda$. Then $m \le v$.

No block size is required to be constant, no point is required to lie in a fixed number of sets, and the counting conditions of this essay’s first section do not hold. What survives is the shape of the Gram matrix: its off-diagonal entries are all $\lambda$ and its diagonal entries are the sizes $|A_i|$, which now vary. That is $D + \lambda J$ with $D$ a positive diagonal, and such a matrix is positive definite provided no $|A_i|$ equals $\lambda$ — which is to say provided no set is contained in every other.

Positive definite implies invertible implies full rank implies $m \le v$. The same three steps, with a slightly more careful first one.

This is the version worth remembering, because it applies where no design is in sight: a family of sets any two of which share exactly seven elements has at most as many members as there are elements, whatever the sets look like. A statement about arbitrary set systems, with no construction, no counting and no combinatorial proof known.

Four designs that exist, and a bound about the rest #

The determinant is computed and the eigenvalue argument is not drawn. The figures perform an exact elimination and compare against the closed form; the reason the closed form holds — that $J$ has one large eigenvalue and $v-1$ zeros — is prose, and there is no picture of an eigenvalue of a $13 \times 13$ matrix.

The rank is implied rather than exhibited. What is shown is a non-zero determinant; that this forces $b \ge v$ is the rank bound, argued in a sentence, and no figure shows independent columns.

The four designs drawn have four different shapes and one argument. The Gram matrix’s form — a constant on the diagonal, another off it — is what every panel has in common, and it is the only thing the proof reads. A reader could take the four figures as four cases and they are one case, drawn four times because the parameters vary and the structure does not.

And every design here exists. The inequality is a statement about all designs, including the ones nobody has built, and the four drawn are four that do. A figure of the theorem would be a figure of something impossible, which is the standing difficulty with drawing a bound.

Still open: a plane in one line of numbers #

Fisher’s inequality says a plane cannot have fewer lines than points. The other direction asks how little it takes to write one down — and the answer is that a projective plane of order $n$ can be compressed into a single list of $n+1$ residues whose differences hit every non-zero residue exactly once. The whole plane is that list’s shifts, and that is a plane in a list of numbers.

Counting, and the thing counting cannot reach #

The habit is about when to leave a subject.

The schedule essay’s answer is entirely combinatorial: two divisions, necessary by counting and sufficient by construction. This answer is not available that way, and eighty years of looking has not produced one — so the honest description is that the statement is about sets and the proof is about dimensions, and nothing translates it back.

That happens often enough to be a method rather than an accident. When a combinatorial question resists counting, the move is to put the objects in a vector space and count dimensions instead, because a dimension bounds a cardinality and a cardinality does not bound a dimension. The cost is that the proof explains nothing about the sets — and the benefit is an inequality that no amount of cleverness with counts was going to find.