Combinatorial Design Theory studies how to arrange finite sets of objects so that prescribed patterns of overlap, balance, and symmetry occur. The subject sits at the intersection of combinatorics, algebra, and geometry, and it asks questions that are both structural and constructive: when do such designs exist, how can they be built, and what do they reveal about the underlying finite system? Throughout the course, the central objects include Latin squares, quasigroups, block designs, projective and affine planes, Steiner systems, difference sets, and the codes naturally associated with them. The chapters develop the theory in a deliberately cumulative way. The course begins with Latin squares and orthogonality, then moves to quasigroups and loops as algebraic language for construction. From there it introduces incidence structures and block designs, using Fisher’s inequality and linear algebra to obtain foundational constraints. Projective and affine planes provide a geometric setting, while Steiner triple systems and small designs offer concrete families and examples. Later chapters focus on resolvable designs and scheduling, cyclic constructions via difference sets, and the links between designs and error-correcting codes. The course closes with existence theorems and modern perspectives, tying together the algebraic, geometric, and coding-theoretic threads that run through the subject. # Introduction This opening chapter sets the direction for the course. Combinatorial design theory studies finite arrangements whose small pieces satisfy exact incidence rules: each symbol appears once in each row and column, each pair of points lies in a prescribed number of blocks, or each line in a finite geometry has a fixed size. The course begins with Latin squares and then moves toward block designs, Steiner systems, finite geometries, and existence theorems, with the recurring question of how local regularity forces global structure. The emphasis is on constructions, necessary counting conditions, and structural obstructions. Some designs arise from algebraic systems such as groups and finite fields; others are ruled out by parity, divisibility, or linear algebra. Applications to experiments, tournaments, error-correcting codes, and finite projective planes will appear as motivation, but the course treats them through the common language of incidence. ## What Counts as a Design? A first difficulty is that the word "design" covers several related objects rather than a single definition. The course will use it as an organising idea: a finite set of points, symbols, positions, or treatments is arranged so that prescribed patterns occur with controlled multiplicity. [explanation: Incidence As The Organising Principle] Most designs in this course can be read as incidence structures. There is a collection of objects of one type, such as points, and a collection of objects of another type, such as blocks, lines, rows, columns, or symbols. The mathematical content lies in the incidence relation between them. For Latin squares, incidence records which symbol occurs in which row-column position. For block designs, incidence records which points lie in which blocks. For finite projective planes, incidence records which points lie on which lines. The surface notation changes, but the same questions recur: how many objects must exist, how many incidences are forced, and when can a partial pattern be completed? [/explanation] This viewpoint lets us compare objects that first look unrelated. A Latin square controls ordered pairs of row and column coordinates, while a balanced incomplete block design controls unordered pairs of points inside blocks. Both impose a uniformity condition on small subconfigurations. [example: Three Small Incidence Rules] A Latin square of order $3$ can be seen explicitly by taking symbols $\{0,1,2\}$ and using the three rows $(0,1,2)$, $(1,2,0)$, and $(2,0,1)$. Each row contains each symbol once, and the three columns are \begin{align*} (0,1,2), \qquad (1,2,0), \qquad (2,0,1), \end{align*} so each column also contains each symbol once. A block design with block size $3$ can ask for every pair of points to occur together in exactly one block. For example, on points $\{1,2,3,4,5,6,7\}$, take the seven triples \begin{align*} 123,\quad 145,\quad 167,\quad 246,\quad 257,\quad 347,\quad 356. \end{align*} The triples containing $1$ give the pairs $12,13,14,15,16,17$; the triples containing $2$ give $21,23,24,26,25,27$; continuing through the listed triples shows that each point occurs with each of the other six points exactly once. A finite projective plane of order $2$ has seven points and seven lines, each line containing three points, and the seven triples above may be read as its seven lines. There are \begin{align*} \binom{7}{2}=21 \end{align*} pairs of distinct points, while the seven lines contain \begin{align*} 7\binom{3}{2}=7\cdot 3=21 \end{align*} point-pairs in total. Since the displayed triples account for each point-pair once, every pair of points lies on exactly one line. These three examples use different surfaces: arrays, triples, and lines, but in each case the local incidence counts are fixed before the whole configuration is built. [/example] The next question is how to extract information before constructing anything. Counting incidences in two ways is the first technique, and it will appear throughout the course. [quotetheorem:5718] [citeproof:5718] The principle is elementary, but its hypotheses are exactly what make the conclusion sharp. Finiteness ensures that the incidence set has a well-defined cardinality, and exact uniformity ensures that every fibre over $X$ has the same size $a$ and every fibre over $Y$ has the same size $b$. If either uniformity condition is weakened to an average or an upper bound, the equality need not survive. For instance, take $X=\{x_1,x_2\}$, $Y=\{y_1,y_2\}$, and $I=\{(x_1,y_1),(x_1,y_2),(x_2,y_1)\}$. The $X$-fibres have sizes $2$ and $1$, while the $Y$-fibres have sizes $2$ and $1$, so there is no common pair of constants $a,b$ for which $a|X|=b|Y|$ records the incidence count. [example: A First Divisibility Obstruction] Suppose a finite incidence structure has point set $X$ with $|X|=v$ and block set $\mathcal{B}$ with $|\mathcal{B}|=b$. Assume every block has size $k$ and every point lies in exactly $r$ blocks. Let \begin{align*} I=\{(x,B)\in X\times \mathcal{B}: x\in B\} \end{align*} be the point-block incidence relation. Counting $I$ by points gives \begin{align*} |I|=\sum_{x\in X} r=vr, \end{align*} because each of the $v$ points is incident with exactly $r$ blocks. Counting the same set $I$ by blocks gives \begin{align*} |I|=\sum_{B\in \mathcal{B}} |B|=\sum_{B\in \mathcal{B}} k=bk, \end{align*} because each of the $b$ blocks contains exactly $k$ points. Hence, by the *[Double Counting Principle For Incidences](/theorems/5718)*, \begin{align*} vr=bk. \end{align*} Therefore a proposed regular incidence structure must have \begin{align*} r=\frac{bk}{v}, \end{align*} so $v$ must divide $bk$. For the proposed parameters $v=5$, $k=3$, and $b=6$, this would require \begin{align*} r=\frac{bk}{v} =\frac{6\cdot 3}{5} =\frac{18}{5}. \end{align*} Since a point cannot lie in a non-integer number of blocks, no incidence structure with these exact regularities exists. If the five points were allowed to lie in different numbers of blocks, then six triples would still have total incidence count \begin{align*} 6\cdot 3=18, \end{align*} but the point-side count would be a sum of five possibly different fibre sizes rather than $5r$, so the divisibility obstruction comes specifically from requiring one common replication number $r$. [/example] ## Latin Squares as the First Model How can a multiplication table be useful if the operation is not the main object? The answer is that its row-column-symbol pattern is already a design, and many later constructions begin by forgetting algebraic operations while retaining their incidence regularity. [definition: Latin Square] A Latin square of order $n$ on a symbol set $S$ with $|S|=n$ is a map \begin{align*} L: \{1,\dots,n\} \times \{1,\dots,n\} \to S \end{align*} such that, for each fixed row index $i$, the map $j \mapsto L(i,j)$ is a bijection from $\{1,\dots,n\}$ to $S$, and, for each fixed column index $j$, the map $i \mapsto L(i,j)$ is a bijection from $\{1,\dots,n\}$ to $S$. [/definition] The definition isolates the cancellation property of a multiplication table without requiring associativity, an identity, or inverses in a group-theoretic sense. This separation is important because Latin squares form a much larger class than group tables. [example: Cyclic Latin Square Of Order Three] Let $S=\mathbb{Z}/3\mathbb{Z}$, and define \begin{align*} L:S\times S\to S, \qquad L(i,j)=i+j \pmod 3. \end{align*} We compute the entries by reducing each sum modulo $3$. In row $0$, \begin{align*} L(0,0)=0,\qquad L(0,1)=1,\qquad L(0,2)=2. \end{align*} In row $1$, \begin{align*} L(1,0)=1,\qquad L(1,1)=2,\qquad L(1,2)=0. \end{align*} In row $2$, \begin{align*} L(2,0)=2,\qquad L(2,1)=0,\qquad L(2,2)=1. \end{align*} Thus the three rows are \begin{align*} (0,1,2), \qquad (1,2,0), \qquad (2,0,1). \end{align*} The columns are obtained from the same entries. Column $0$ is \begin{align*} (L(0,0),L(1,0),L(2,0))=(0,1,2). \end{align*} Column $1$ is \begin{align*} (L(0,1),L(1,1),L(2,1))=(1,2,0). \end{align*} Column $2$ is \begin{align*} (L(0,2),L(1,2),L(2,2))=(2,0,1). \end{align*} Each displayed row and each displayed column contains the three elements $0,1,2$ exactly once, so $L$ is a Latin square of order $3$. This example shows the cyclic construction: addition modulo $3$ shifts each row and each column while preserving one occurrence of every symbol. [/example] Group tables give dependable examples, but they do not exhaust the subject. Chapter 1 compares Latin squares up to relabelling and coordinate changes, then asks when two Latin squares can be superimposed so that all ordered pairs of symbols occur once. [definition: Orthogonal Latin Squares] Two Latin squares \begin{align*} L: \{1,\dots,n\} \times \{1,\dots,n\} \to S, \qquad M: \{1,\dots,n\} \times \{1,\dots,n\} \to T \end{align*} of order $n$ are orthogonal if the map \begin{align*} \Phi:\{1,\dots,n\} \times \{1,\dots,n\} \to S \times T, \qquad \Phi(i,j)=(L(i,j),M(i,j)) \end{align*} is a bijection. [/definition] Orthogonality is the first place where the course moves from one regular array to a coordinated family of arrays. It asks whether two independent Latin constraints can coexist without repeating any pair of outcomes. [example: Orthogonal Latin Squares Over A Field] Let $F=\mathbb{F}_3=\{0,1,2\}$, with all arithmetic modulo $3$. Define \begin{align*} L(i,j)=i+j,\qquad M(i,j)=i+2j \end{align*} for $i,j\in F$. Each array is Latin: for fixed $i$, the maps $j\mapsto i+j$ and $j\mapsto i+2j$ are bijections of $F$, since addition by $i$ is a translation and multiplication by $2$ is invertible in $\mathbb{F}_3$; for fixed $j$, the maps $i\mapsto i+j$ and $i\mapsto i+2j$ are translations of $F$. We show that $L$ and $M$ are orthogonal. Suppose two cells $(i,j)$ and $(i',j')$ give the same ordered pair: \begin{align*} (L(i,j),M(i,j))=(L(i',j'),M(i',j')). \end{align*} Equality of first coordinates gives \begin{align*} i+j=i'+j'. \end{align*} Equality of second coordinates gives \begin{align*} i+2j=i'+2j'. \end{align*} Subtracting the right-hand side from the left-hand side in the first equation gives \begin{align*} (i-i')+(j-j')=0. \end{align*} Doing the same in the second equation gives \begin{align*} (i-i')+2(j-j')=0. \end{align*} Now subtract the equation $(i-i')+(j-j')=0$ from the equation $(i-i')+2(j-j')=0$: \begin{align*} \bigl((i-i')+2(j-j')\bigr)-\bigl((i-i')+(j-j')\bigr)=0-0. \end{align*} The left-hand side expands as \begin{align*} (i-i')+2(j-j')-(i-i')-(j-j')=j-j', \end{align*} so \begin{align*} j-j'=0. \end{align*} Thus $j=j'$. Substituting $j-j'=0$ into $(i-i')+(j-j')=0$ gives \begin{align*} i-i'=0, \end{align*} so $i=i'$. Therefore no two distinct cells give the same ordered pair. Since there are $3^2=9$ cells and $|F\times F|=3\cdot 3=9$ possible ordered pairs, the map $(i,j)\mapsto (L(i,j),M(i,j))$ is bijective, so the two Latin squares are orthogonal. [/example] This field calculation previews a major construction. Linear algebra over finite fields produces many mutually orthogonal Latin squares, and Chapter 2 will turn complete such families into affine planes by the Bose construction. ## Block Designs and Pair Balance Latin squares control rows and columns, but many applications ask for subsets rather than arrays. In an experiment, for instance, each block may contain several treatments, and the fairness condition concerns how often pairs of treatments appear together. [definition: Balanced Incomplete Block Design] A balanced incomplete block design with parameters $(v,b,r,k,\lambda)$ consists of a finite point set $X$ with $|X|=v$ and a collection $\mathcal{B}$ of $b$ subsets of $X$, called blocks, such that each block has size $k$, each point lies in exactly $r$ blocks, and each pair of distinct points lies together in exactly $\lambda$ blocks. [/definition] The adjective "balanced" refers to the pair condition, while "incomplete" refers to $k<v$. Once these regularities have been specified, the first task is to determine which numerical parameters could possibly occur, so we now count the incidences forced by the definition. [quotetheorem:5719] [citeproof:5719] These equations are necessary conditions, not a construction. Each hypothesis has a separate role: exact block size $k$ makes the block-side incidence count equal to $bk$, exact replication number $r$ makes the point-side incidence count equal to $vr$, and exact pair multiplicity $\lambda$ makes the second count independent of the chosen point $x$. The two equations also have different strengths: $vr=bk$ only balances total incidences, while $r(k-1)=\lambda(v-1)$ uses the pair-balance hypothesis and can fail even when the first equation holds. For example, $v=6$, $b=4$, $r=2$, and $k=3$ satisfy $vr=bk=12$, but with $\lambda=1$ the second equation would require $2(3-1)=1(6-1)$, which is false. Thus a regular point-block incidence count alone does not guarantee pair balance, and the equations do not prove existence even when both are satisfied. [example: The Fano Plane Parameters] For the finite projective plane of order $2$, take the seven lines as blocks. Thus \begin{align*} v=7,\qquad b=7,\qquad k=3,\qquad r=3. \end{align*} The point-block incidence count from the point side is \begin{align*} vr=7\cdot 3=21, \end{align*} and the same incidence count from the line side is \begin{align*} bk=7\cdot 3=21. \end{align*} Hence the first block-design parameter equation is satisfied: \begin{align*} vr=bk. \end{align*} To determine the pair parameter, fix a point $x$. There are $r=3$ lines through $x$, and each such line contains $k-1=3-1=2$ points other than $x$. Therefore the number of pairs $(y,L)$ with $y\neq x$ and both $x,y$ on $L$ is \begin{align*} r(k-1)=3(3-1)=3\cdot 2=6. \end{align*} If each of the other $v-1=7-1=6$ points lies with $x$ on exactly $\lambda$ lines, the same number is \begin{align*} \lambda(v-1)=\lambda(7-1)=6\lambda. \end{align*} Equating the two counts gives \begin{align*} 6=6\lambda, \end{align*} so \begin{align*} \lambda=1. \end{align*} Thus the Fano plane is a $(7,7,3,3,1)$ block design: every pair of distinct points lies together on exactly one line. [/example] The Fano plane will return as the smallest projective plane and as a Steiner triple system. It is a useful test case because it is small enough to draw but rich enough to display the main incidence phenomena. [illustration:fano-plane-seven-lines] ## Existence, Nonexistence, and Constructions Once the parameter equations are known, the central problem becomes existence. Given admissible numerical parameters, does a design with those parameters exist, and can it be constructed in a systematic way? [explanation: The Three Kinds Of Results] The course repeatedly separates three kinds of results. A construction gives an explicit design, often using groups, finite fields, or recursive methods. A nonexistence theorem proves that no design with certain parameters can exist, often using parity, modular arithmetic, eigenvalues, or counting. An asymptotic existence theorem says that, after the divisibility obstructions are satisfied, designs exist for all sufficiently large parameter values in a specified family. This separation matters because necessary conditions are often much easier to find than actual designs. For Latin squares, every order $n$ has examples, but mutually orthogonal families have sharp obstructions at small orders and strong finite-field constructions at prime-power orders. For block designs, pair-counting gives immediate equations, while general existence is a deeper theorem. [/explanation] The first construction problem is to produce not just one Latin square, but a large family whose members are pairwise orthogonal. The obstruction is that two squares must not merely be Latin separately: when superimposed, every ordered pair of symbols must occur exactly once. Finite fields provide enough invertible differences between slopes to force this stronger condition, and this is the mechanism later used to build affine planes. [quotetheorem:5720] [citeproof:5720] This theorem explains why prime powers behave well in the Latin square part of the course. The proof uses the field structure in two essential places: nonzero slopes make $x \mapsto ax+y$ bijective in each column, and distinct slopes make $a-b$ invertible when comparing two squares. If $a=0$, the array $L_0(x,y)=y$ has identical entries down each column and is not Latin. If two slopes are equal, then comparing $L_a$ with itself repeats only diagonal ordered pairs of the form $(s,s)$ rather than all pairs in $F \times F$. The theorem does not classify all mutually orthogonal Latin squares, and it gives no construction for orders that are not prime powers. It also foreshadows the bridge from mutually orthogonal Latin squares to affine planes. [example: Four Latin Squares Of Order Five] Over $F=\mathbb{F}_5=\{0,1,2,3,4\}$, with arithmetic modulo $5$, define \begin{align*} L_a(x,y)=ax+y \end{align*} for each $a\in\{1,2,3,4\}$. For a fixed row value $x$, the entries in that row are obtained from $y\mapsto ax+y$, which is translation by $ax$; as $y$ runs through $F$, the values $ax+y$ also run through $F$ exactly once. For a fixed column value $y$, if \begin{align*} ax+y=ax'+y, \end{align*} then subtracting $y$ from both sides gives \begin{align*} ax=ax', \end{align*} so \begin{align*} a(x-x')=0. \end{align*} Since $a\in\{1,2,3,4\}$ is nonzero in $\mathbb{F}_5$, multiplication by $a$ is invertible, hence $x-x'=0$ and $x=x'$. Thus each $L_a$ is a Latin square of order $5$. To see orthogonality, compare two distinct slopes $a,b\in\{1,2,3,4\}$. Suppose two cells $(x,y)$ and $(x',y')$ give the same ordered pair: \begin{align*} (L_a(x,y),L_b(x,y))=(L_a(x',y'),L_b(x',y')). \end{align*} Equality of first coordinates gives \begin{align*} ax+y=ax'+y', \end{align*} so \begin{align*} a(x-x')+(y-y')=0. \end{align*} Equality of second coordinates gives \begin{align*} bx+y=bx'+y', \end{align*} so \begin{align*} b(x-x')+(y-y')=0. \end{align*} Subtracting the first displayed equation from the second gives \begin{align*} \bigl(b(x-x')+(y-y')\bigr)-\bigl(a(x-x')+(y-y')\bigr)=0-0, \end{align*} and the left-hand side expands to \begin{align*} b(x-x')+(y-y')-a(x-x')-(y-y')=(b-a)(x-x'). \end{align*} Hence \begin{align*} (b-a)(x-x')=0. \end{align*} Because $a\neq b$, the element $b-a$ is nonzero in $\mathbb{F}_5$, so it is invertible; therefore \begin{align*} x-x'=0, \end{align*} and $x=x'$. Substituting $x-x'=0$ into \begin{align*} a(x-x')+(y-y')=0 \end{align*} gives \begin{align*} y-y'=0, \end{align*} so $y=y'$. Thus no two distinct cells give the same ordered pair. There are $5^2=25$ cells and $|F\times F|=5\cdot 5=25$ possible ordered pairs, so each distinct pair $L_a,L_b$ is orthogonal. Consequently the four squares $L_1,L_2,L_3,L_4$ form a family of four mutually orthogonal Latin squares of order $5$. [/example] The finite-field construction gives many designs, but it does not answer whether all admissible parameter sets can be realised. We therefore need a benchmark theorem that distinguishes elementary constructions from the general existence theory. The next result is quoted as a landmark statement rather than as a proof checkpoint for these notes; its role here is to fix the asymptotic quantifier pattern that the later chapters will return to. [quotetheorem:5721] For the rest of the course, the important distinction is conceptual: counting congruences are immediate necessary tests, while Wilson's theorem says that, after fixing the local parameters and taking $v$ large enough, those tests eventually become complete. Small designs remain delicate, and explicit constructions still matter. ## How The Course Will Develop The course now has its guiding questions. What are the natural equivalences between designs, which constructions produce large families, which parameter sets are impossible, and when do general existence theorems take over? [explanation: Route Through The Syllabus] The first part studies Latin squares, reduced forms, isotopy, orthogonality, transversals, and completion problems. The second part translates Latin squares into quasigroups and loops, then uses finite fields to build mutually orthogonal families and affine planes. The middle part introduces balanced incomplete block designs, [Fisher's inequality](/theorems/5738), symmetric designs, Steiner systems, and finite projective planes. The later lectures connect designs to codes and graph theory, including incidence matrices, strongly regular graphs, Hadamard matrices, and tactical decompositions. The final part discusses recursive constructions and modern existence theorems, with Wilson's theorem serving as the main landmark. Throughout, small examples remain essential: they test definitions, expose obstructions, and keep the parameter calculations anchored. [/explanation] A useful habit is to ask the same four questions whenever a new design appears. What are the objects and incidences? Which parameters are forced by counting? Which examples come from algebra or geometry? Which admissible parameters still fail to exist? [remark: Reading Designs By Their Parameters] Parameters are not bookkeeping after the fact; they are part of the mathematical object. In a block design, $(v,b,r,k,\lambda)$ records enough incidence data to force strong equations. In a Latin square, the order $n$ determines the size of the array, the number of symbols, and the number of cells. Later, symmetric designs, projective planes, and Steiner systems will be recognised by especially rigid parameter patterns. [/remark] The first chapter begins with the most concrete model: Latin squares. They provide arrays to compute with, algebraic examples from groups, and the first serious nonexistence phenomenon through Euler's order $6$ problem. # 1. Latin Squares and Orthogonality Latin squares are the first objects in the course because they turn a local incidence rule into a rigid global arrangement. The prerequisites are basic finite set notation, elementary group theory, and comfort with bijections and counting arguments; no finite geometry is assumed. Each row and each column must contain every symbol exactly once, so the same array can be read as a combinatorial design, a multiplication table, or a schedule with no repeated conflict. Building on the incidence viewpoint and examples from Chapter 0, this chapter introduces the basic equivalence operations on Latin squares, explains orthogonality and mutually orthogonal families, and closes with partial Latin squares and completion problems. ## The Latin Condition and Multiplication Tables The first question is how to encode the idea that two coordinates determine a unique symbol. A Latin square is the finite version of this rule: rows, columns, and symbols are three sets of the same size, and every row-symbol and column-symbol incidence occurs once. [definition: Latin Square] Let $S$ be a set with $|S|=n$. A Latin square of order $n$ on symbol set $S$ is an $n \times n$ array $L=(L_{ij})_{i,j\in S}$ with entries in $S$ such that, for each fixed $i\in S$, the map $j\mapsto L_{ij}$ is a bijection $S\to S$, and, for each fixed $j\in S$, the map $i\mapsto L_{ij}$ is a bijection $S\to S$. [/definition] The row and column bijection conditions are symmetric, but they control different kinds of repetition. Rows prevent a symbol from repeating against the same first coordinate, while columns prevent repetition against the same second coordinate. [example: Cyclic Latin Square of Order Three] Take $S=\mathbb Z/3\mathbb Z$, with addition computed modulo $3$, and define $L_{ij}=i+j$. Substituting each row index gives \begin{align*} i=0:\quad (0+0,0+1,0+2)=(0,1,2). \end{align*} For the second row, $1+0=1$, $1+1=2$, and $1+2=3\equiv 0\pmod 3$, so \begin{align*} i=1:\quad (1+0,1+1,1+2)=(1,2,0). \end{align*} For the third row, $2+0=2$, $2+1=3\equiv 0\pmod 3$, and $2+2=4\equiv 1\pmod 3$, so \begin{align*} i=2:\quad (2+0,2+1,2+2)=(2,0,1). \end{align*} Thus every row contains the three elements $0,1,2$ exactly once. The same check down the columns gives \begin{align*} j=0:\quad (0+0,1+0,2+0)=(0,1,2), \end{align*} \begin{align*} j=1:\quad (0+1,1+1,2+1)=(1,2,0), \end{align*} and \begin{align*} j=2:\quad (0+2,1+2,2+2)=(2,0,1). \end{align*} Therefore each map $j\mapsto i+j$ and each map $i\mapsto i+j$ is a bijection $S\to S$, so $L$ is a Latin square. Modular addition supplies the Latin condition because adding a fixed residue modulo $3$ permutes the three residues instead of repeating one. [/example] Since relabelling rows, columns, and symbols usually does not change the combinatorial content, the example raises a classification problem: when should two displayed arrays count as the same square for enumeration? Without a normal form, the same incidence pattern may be counted many times merely because the row names, column names, or symbol names have been permuted. The first normal form fixes the labels in the top row and left column. [definition: Reduced Latin Square] A Latin square $L$ of order $n$ on $S=\{1,\dots,n\}$ is reduced if $L_{1j}=j$ for all $j\in S$ and $L_{i1}=i$ for all $i\in S$. [/definition] Reduction is a normal form for many calculations, especially enumeration. It records one square from a family obtained by permuting labels, while preserving the incidence structure that matters for most questions in the course. [example: A Reduced Latin Square of Order Four] On $S=\{1,2,3,4\}$, define \begin{align*} i\oplus j = 1 + ((i+j-2) \bmod 4). \end{align*} For the first row, \begin{align*} 1\oplus1=1+((1+1-2)\bmod4)=1+0=1. \end{align*} Also, \begin{align*} 1\oplus2=1+((1+2-2)\bmod4)=1+1=2. \end{align*} Similarly, \begin{align*} 1\oplus3=1+((1+3-2)\bmod4)=1+2=3. \end{align*} Finally, \begin{align*} 1\oplus4=1+((1+4-2)\bmod4)=1+3=4. \end{align*} Thus the first row is $(1,2,3,4)$. For the second row, the four entries are \begin{align*} 2\oplus1=1+((2+1-2)\bmod4)=1+1=2. \end{align*} Then \begin{align*} 2\oplus2=1+((2+2-2)\bmod4)=1+2=3. \end{align*} Next, \begin{align*} 2\oplus3=1+((2+3-2)\bmod4)=1+3=4. \end{align*} And \begin{align*} 2\oplus4=1+((2+4-2)\bmod4)=1+(4\bmod4)=1+0=1. \end{align*} So the second row is $(2,3,4,1)$. The remaining rows are computed in the same formula: \begin{align*} (3\oplus1,3\oplus2,3\oplus3,3\oplus4)=(3,4,1,2). \end{align*} Here $3\oplus3=1+((3+3-2)\bmod4)=1+0=1$ and $3\oplus4=1+((3+4-2)\bmod4)=1+1=2$. Also, \begin{align*} (4\oplus1,4\oplus2,4\oplus3,4\oplus4)=(4,1,2,3). \end{align*} Here $4\oplus2=1+((4+2-2)\bmod4)=1+0=1$, $4\oplus3=1+1=2$, and $4\oplus4=1+2=3$. Thus the rows are $(1,2,3,4)$, $(2,3,4,1)$, $(3,4,1,2)$, and $(4,1,2,3)$, so every row contains each symbol exactly once. Reading down the columns gives the same four cyclic lists: the first column is $(1,2,3,4)$, the second is $(2,3,4,1)$, the third is $(3,4,1,2)$, and the fourth is $(4,1,2,3)$. Hence every column also contains each symbol exactly once, so the array is a Latin square. The first row satisfies $1\oplus j=j$ for every $j\in S$, and the first column satisfies $i\oplus1=i$ for every $i\in S$. Therefore the square is reduced. This is the cyclic group table of order $4$ with the identity labelled $1$, so reduction here is a convention on labels rather than a new construction. [/example] The reduced cyclic square suggests a second question: when does an array come from a genuine operation on its symbol set? This viewpoint is needed because it turns row-column-symbol incidence into algebra and lets us compare Latin squares with group multiplication tables. [definition: Multiplication Table of a Binary Operation] Let $S$ be a finite set and let $\ast:S\times S\to S$ be a binary operation. The multiplication table of $\ast$ is the array $L$ with $L_{ij}=i\ast j$ for $i,j\in S$. [/definition] A multiplication table need not be Latin, since a fixed row could repeat a value. The first structural theorem asks which familiar algebraic operations automatically have the required cancellation in every row and column. [quotetheorem:5722] [citeproof:5722] This theorem is the bridge from algebra to combinatorial designs. It gives a dependable source of Latin squares because group multiplication has enough symmetry to make every row and every column a permutation of the same symbol set. In Cayley-table language, the entries are not arbitrary labels: the table records how multiplication by a fixed group element rearranges the group. The result should be read in the constructive direction. Every finite group supplies a Latin square, but many Latin squares do not come from groups, and the Latin condition alone does not impose associativity, an identity element, or inverse laws. Later uses of group tables therefore provide controlled examples, while the classification of Latin squares requires equivalence notions adapted to rows, columns, and symbols rather than only group isomorphism. This leaves a separate reverse question: does every Latin square come from a group after relabelling? The answer is no. The Latin condition gives row and column cancellation, but it does not impose associativity, a two-sided identity, or inverse laws. The simplest way to see the distinction is to test associativity in a Latin multiplication table. [example: A Nonassociative Latin Square] Let $S=\{0,1,2,3,4\}$, with rows and columns indexed in the order $0,1,2,3,4$, and define $i\ast j$ by the five rows $(0,1,2,3,4)$, $(1,0,3,4,2)$, $(2,3,4,0,1)$, $(3,4,1,2,0)$, and $(4,2,0,1,3)$. Each listed row contains the five symbols $0,1,2,3,4$ exactly once. Reading down the columns gives $(0,1,2,3,4)$, $(1,0,3,4,2)$, $(2,3,4,1,0)$, $(3,4,0,2,1)$, and $(4,2,1,0,3)$, so each column also contains the five symbols exactly once. Therefore the row maps $j\mapsto i\ast j$ and the column maps $i\mapsto i\ast j$ are bijections $S\to S$, and the array is a Latin square. Now compare the two parenthesizations of $2\ast2\ast3$. From row $2$ and column $2$, the entry is $4$, so \begin{align*} 2\ast2=4. \end{align*} From row $4$ and column $3$, the entry is $1$, hence \begin{align*} (2\ast2)\ast3=4\ast3=1. \end{align*} On the other hand, from row $2$ and column $3$, the entry is $0$, so \begin{align*} 2\ast3=0. \end{align*} From row $2$ and column $0$, the entry is $2$, hence \begin{align*} 2\ast(2\ast3)=2\ast0=2. \end{align*} Since $1\ne2$, the operation is not associative. Thus this Latin square cannot be a group table with this operation, showing that the Latin condition is weaker than the group axioms. [/example] This nonassociative example shows that classification cannot rely only on group isomorphism. We therefore need equivalence notions that are native to the three-coordinate incidence structure of a Latin square. [definition: Isotopy and Paratopy] Let $L$ be a Latin square with row set $R_L$, column set $C_L$, and symbol set $S_L$, and let $M$ be a Latin square with row set $R_M$, column set $C_M$, and symbol set $S_M$, all of order $n$. They are isotopic if there exist bijections $\alpha:R_L\to R_M$, $\beta:C_L\to C_M$, and $\gamma:S_L\to S_M$ such that $M_{\alpha(i),\beta(j)}=\gamma(L_{ij})$ for all $i\in R_L$ and $j\in C_L$. They are paratopic if, in addition to such bijections between corresponding coordinate classes after relabelling, there is a permutation $\pi\in S_3$ of the three coordinate classes such that the triples $(i,j,L_{ij})$ of $L$ are carried to the triples defining $M$ after applying $\pi$ to the row, column, and symbol positions. [/definition] Isotopy preserves the Latin incidence structure while allowing independent relabelling of the three coordinate types. Paratopy is coarser because it treats a Latin square as a symmetric ternary incidence relation rather than as a privileged row-column array. ## Orthogonal Latin Squares and Euler's Problem The next question is what it means for two Latin squares to be compatible. If two squares of the same order are superimposed, we ask whether the ordered pairs of symbols distinguish all positions. [definition: Orthogonal Latin Squares] Let $L$ and $M$ be Latin squares of order $n$ on symbol sets $S$ and $T$. They are orthogonal if the $n^2$ ordered pairs $(L_{ij},M_{ij})$ are all distinct as $(i,j)$ ranges over the $n^2$ cells. [/definition] Orthogonality says that knowing the two symbols in a cell recovers the cell. This is the combinatorial core behind scheduling interpretations, where two classifications must occur together exactly once. [example: Two Orthogonal Latin Squares over $\mathbb F_3$] Let rows and columns be indexed by $\mathbb F_3=\{0,1,2\}$, and define \begin{align*} L_{ij}=i+j,\qquad M_{ij}=i+2j, \end{align*} with all operations in $\mathbb F_3$. For fixed $i$, the row map of $L$ is $j\mapsto i+j$. If $i+j=i+j'$, then subtracting $i$ from both sides gives $j=j'$, so this row map is injective; since $\mathbb F_3$ has three elements, it is bijective. For fixed $j$, the column map of $L$ is $i\mapsto i+j$. If $i+j=i'+j$, then subtracting $j$ from both sides gives $i=i'$, so this column map is also bijective. Hence $L$ is a Latin square. For $M$, fix $i$ and suppose \begin{align*} i+2j=i+2j'. \end{align*} Subtracting $i$ from both sides gives \begin{align*} 2j=2j'. \end{align*} Since $2^{-1}=2$ in $\mathbb F_3$, multiplying both sides by $2$ gives \begin{align*} j=j'. \end{align*} Thus each row map $j\mapsto i+2j$ is injective, hence bijective. For fixed $j$, if $i+2j=i'+2j$, then subtracting $2j$ from both sides gives $i=i'$, so each column map $i\mapsto i+2j$ is bijective. Therefore $M$ is also a Latin square. To check orthogonality, suppose two cells have the same ordered pair: \begin{align*} (L_{ij},M_{ij})=(L_{i'j'},M_{i'j'}). \end{align*} Then the first coordinates of the ordered pairs are equal, so \begin{align*} i+j=i'+j'. \end{align*} The second coordinates are also equal, so \begin{align*} i+2j=i'+2j'. \end{align*} Subtracting the equation $i+j=i'+j'$ from the equation $i+2j=i'+2j'$ gives \begin{align*} j=j'. \end{align*} Substituting $j=j'$ into $i+j=i'+j'$ gives \begin{align*} i+j=i'+j. \end{align*} Subtracting $j$ from both sides gives \begin{align*} i=i'. \end{align*} Thus equality of superimposed symbol pairs forces equality of the row and column indices. Therefore all nine ordered pairs $(L_{ij},M_{ij})$ are distinct, so the two Latin squares are orthogonal. [/example] The field example gives more than an isolated pair: different nonzero slopes produce several squares on the same row-column set. A family is useful only if no two squares in it lose the cell-recovery property when superimposed; otherwise adding a new square could destroy the scheduling or geometric interpretation supplied by the previous ones. In experimental design language, the row and column coordinates are two blocking factors, while each Latin square records a treatment factor; orthogonality says that every pair of factors is balanced. In finite geometry language, a complete set of MOLS will later supply the parallel classes of lines in an affine plane. This motivates the family version of orthogonality, where compatibility is required for every pair in the family. [definition: Mutually Orthogonal Latin Square Family] A set $\{L_1,\dots,L_m\}$ of Latin squares of order $n$ on symbol sets of size $n$ is a set of mutually orthogonal Latin squares, or MOLS, if $L_a$ and $L_b$ are orthogonal for every $a\ne b$. [/definition] The abbreviation MOLS will occur throughout the course. Later chapters connect MOLS of order $n$ to affine planes of order $n$, which makes the existence problem central in finite geometry. [quotetheorem:5723] [citeproof:5723] The upper bound is universal: it depends only on pairwise orthogonality and the Latin condition, not on any algebraic construction. Each hypothesis is needed for the counting argument. If the arrays are not Latin, a column of the associated orthogonal array can have repeated pairs with the row coordinate; for instance, the constant $n\times n$ array repeats the same symbol in every row, so the incidence-vector orthogonality used in the proof breaks down. If the squares do not have a common order and common row-column grid, then the $n^2$ cells and the dimension count are not even defined for a single parameter $n$. If pairwise orthogonality is weakened, repeated ordered pairs may occur after superimposing two squares; taking two identical Latin squares of order $n>1$ gives only the pairs $(a,a)$, so the proof cannot produce mutually orthogonal column classes. The theorem also does not assert that $n-1$ MOLS exist for every $n$; attaining the bound is a separate existence problem, and non-prime-power orders require different arguments. When the bound is attained, the row classes, column classes, and symbol classes behave like the parallel classes of an affine plane of order $n$, which is why MOLS become finite geometry in the next chapter. More concretely, the $n^2$ cells become the points of the affine plane; the $n$ cells in a fixed row, the $n$ cells in a fixed column, and the $n$ cells carrying a fixed symbol in each Latin square become the lines. The Latin and orthogonality conditions say that lines from different parallel classes meet in exactly one point. For now we keep a small instance in view: over $\mathbb F_3$, the formulas $i+aj$ with $a\in\mathbb F_3^\times$ give $2=n-1$ MOLS. [quotetheorem:5724] Euler formulated this as the problem of arranging $36$ officers of $6$ ranks and $6$ regiments in a $6\times6$ square so that each row and column contains every rank and every regiment exactly once. The theorem concerns pairs of orthogonal squares, not the existence of Latin squares of order $6$ themselves; for example, the addition table of $\mathbb Z/6\mathbb Z$ is still a Latin square. Order $2$ also has no orthogonal pair, for a different small-order reason: up to relabelling there is only one Latin square of order $2$, and superimposing it with itself repeats ordered pairs. By contrast, nearby prime-power orders such as $5$ and $7$ have complete sets of MOLS from finite fields. In this chapter the result serves as the first serious warning that two valid Latin constraints may be incompatible when imposed together. [remark: The Scope of Euler's Obstruction] Order $6$ is exceptional but not representative of all orders congruent to $2$ modulo $4$. The later theorem of Bose, Shrikhande, and Parker states that pairs of orthogonal Latin squares exist for every order $n\ne 2,6$. This course uses the order $6$ case as a warning that local Latin constraints do not guarantee orthogonal compatibility. [/remark] ## Transversals, Partial Squares, and Completion After full squares and orthogonal pairs, the natural next problem is how much structure can be forced from a partial selection of cells. Transversals and partial Latin squares are the two basic languages for this question. [definition: Latin Transversal] Let $L$ be a Latin square of order $n$. A Latin transversal is a set of $n$ cells containing exactly one cell from each row, exactly one cell from each column, and exactly one occurrence of each symbol. [/definition] A transversal is a diagonal-like object adapted to the square rather than to the displayed order of rows and columns. Orthogonality can be interpreted through transversals: the positions carrying a fixed symbol in one square form a transversal in the other square. [example: Transversals in the Order Three Cyclic Square] In the cyclic square $L_{ij}=i+j$ over $\mathbb Z/3\mathbb Z$, first consider the cells $(0,0)$, $(1,2)$, and $(2,1)$. Their row indices are $0,1,2$, and their column indices are $0,2,1$, so each row and each column is used exactly once. The symbols in these cells are \begin{align*} L_{00}=0+0=0. \end{align*} Also, \begin{align*} L_{12}=1+2=3\equiv 0 \pmod 3. \end{align*} Finally, \begin{align*} L_{21}=2+1=3\equiv 0 \pmod 3. \end{align*} Thus the symbol $0$ occurs three times, while the symbols $1$ and $2$ do not occur, so these three cells do not form a Latin transversal. By contrast, consider the cells $(0,0)$, $(1,1)$, and $(2,2)$. Their row indices are $0,1,2$, and their column indices are also $0,1,2$, so they again use each row and each column exactly once. Their symbols are \begin{align*} L_{00}=0+0=0. \end{align*} Next, \begin{align*} L_{11}=1+1=2. \end{align*} And \begin{align*} L_{22}=2+2=4\equiv 1 \pmod 3. \end{align*} The symbols obtained are $0,2,1$, which are exactly the three elements of $\mathbb Z/3\mathbb Z$ with no repetition. Therefore the cells $(0,0)$, $(1,1)$, and $(2,2)$ form a Latin transversal. [/example] The example shows that selecting one cell from each row and column is not enough to control symbols. This leads to the broader completion question: if only some cells are prescribed, what local conditions must those prescribed symbols satisfy before a full Latin square could contain them? [definition: Partial Latin Square] A partial Latin square of order $n$ on symbol set $S$ is an $n\times n$ array in which some cells are filled with elements of $S$, such that no symbol occurs more than once in any row and no symbol occurs more than once in any column. [/definition] The definition imposes only the conditions that could hold inside a completed Latin square. Completion theorems ask whether these local constraints are enough, perhaps after increasing the order. [definition: Completion of a Partial Latin Square] Let $P$ be a partial Latin square of order $n$ on symbol set $S$. A completion of $P$ is a Latin square $L$ of order $n$ on $S$ such that every filled cell of $P$ has the same symbol in $L$. [/definition] Completion is often impossible at the same order, because early choices may block an entire row or column. The natural repair is to ask whether the partial square can be preserved inside a larger square, where new rows, columns, and symbols give room to route around those conflicts. The key issue is how much enlargement is enough for every partial Latin square, not just for specially arranged examples. [quotetheorem:5725] Here embedding means that the original partial square appears in a specified $n\times n$ subarray of the larger Latin square with its filled entries unchanged. The condition $t\ge 2n$ is a sufficient enlargement threshold for arbitrary partial Latin squares, and in general one cannot expect every partial square to complete at the original order $n$. The theorem therefore does not remove local obstructions inside the given $n\times n$ array; it says that those obstructions can be bypassed by adding enough new rows, columns, and symbols. Its role here is conceptual: partial Latin squares are flexible once enough room is allowed. [example: A Partial Square That Needs Care] Let $S=\{1,2,3\}$, and fill a $3\times3$ partial array by \begin{align*} P_{11}=1,\qquad P_{12}=2,\qquad P_{21}=2,\qquad P_{22}=1. \end{align*} The filled entries in row $1$ are $1$ and $2$, which are distinct; the filled entries in row $2$ are $2$ and $1$, which are distinct; row $3$ has no filled entries. In column $1$ the filled entries are $1$ and $2$, and in column $2$ they are $2$ and $1$, so no column repeats a filled symbol. Thus $P$ is a partial Latin square. Suppose $P$ had a completion $L$. Since row $1$ of $L$ must contain each element of $S$ exactly once and already has \begin{align*} L_{11}=1,\qquad L_{12}=2, \end{align*} the remaining entry in that row must be \begin{align*} L_{13}=3. \end{align*} Similarly, row $2$ already has \begin{align*} L_{21}=2,\qquad L_{22}=1, \end{align*} so its remaining entry must be \begin{align*} L_{23}=3. \end{align*} But then column $3$ contains \begin{align*} L_{13}=3,\qquad L_{23}=3, \end{align*} so the symbol $3$ repeats in the same column. This contradicts the column condition for a Latin square. Therefore this partial Latin square satisfies all local non-repetition rules but has no completion of order $3$, showing why completion cannot be tested by greedily finishing rows alone. [/example] The chapter has introduced the three recurring viewpoints on Latin squares: arrays with row-column-symbol incidence rules, multiplication tables with algebraic structure, and partial designs with extension questions. Orthogonality raises the problem from one square to compatible families, and the order $6$ obstruction shows that existence questions can be delicate even for small parameters. The next chapter reinterprets these arrays algebraically through quasigroups, loops, and finite field constructions, giving tools that produce large families of MOLS when the order is a prime power. # 2. Quasigroups, Loops, and Algebraic Constructions This chapter turns Latin squares into algebra. In the first chapter, Latin squares were arrays with strong row and column constraints; here we treat the entry in row $x$ and column $y$ as a product $x \circ y$. That shift lets us use algebraic language, especially division, identity elements, isotopy, and affine formulae over finite fields, while still keeping the combinatorial question of orthogonality in view. ## Quasigroups as Latin Square Multiplication Laws What algebraic structure is exactly encoded by the rule that every symbol appears once in every row and once in every column? If the row set, column set, and symbol set are all identified with the same finite set $Q$, then a Latin square is the same data as a binary operation on $Q$ for which left and right division are always possible and unique. [definition: Quasigroup] A quasigroup is a set $Q$ equipped with a binary operation $\circ:Q\times Q\to Q$ such that for every $a,b\in Q$ there exist unique elements $x,y\in Q$ satisfying \begin{align*} a\circ x&=b, & y\circ a&=b. \end{align*} [/definition] The definition translates the Latin condition into the language of solvable equations, but there is a possible mismatch to rule out. A Latin square is an array condition about rows and columns, while a quasigroup is an operation with two solvability requirements. The equivalence below checks both directions of that mismatch: row uniqueness gives unique solutions to left equations, column uniqueness gives unique solutions to right equations, and conversely those solvability properties force every row and column of the table to contain each symbol exactly once. [quotetheorem:5726] [citeproof:5726] This equivalence explains why quasigroups are the natural algebraic objects behind Latin squares rather than groups. The finiteness hypothesis is needed for the statement as written: a finite Latin square is an $n\times n$ array, while an infinite quasigroup such as $(\mathbb{Z},-)$ still has unique left and right division but is no longer represented by a finite array of symbols. The division hypotheses are also necessary. On $Q=\{0,1\}$, the operation $x\circ y=x$ has constant columns, so the equation $y\circ 0=1$ has no solution; its table fails the column condition and is not a Latin square. Associativity is a separate issue rather than a hidden consequence of the Latin condition, and the next example shows that even a very small Latin square can fail to come from a group table. [example: A Nonassociative Quasigroup Of Order Three] On $Q=\{0,1,2\}$, define $\circ$ by listing its rows. For row $0$ the values in columns $0,1,2$ are $0,1,2$; for row $1$ they are $2,0,1$; and for row $2$ they are $1,2,0$. Thus every row contains each element of $Q$ exactly once. Reading down the columns, the column values are $0,2,1$ in column $0$, $1,0,2$ in column $1$, and $2,1,0$ in column $2$, so every column also contains each element of $Q$ exactly once. Hence the multiplication table is a Latin square, and therefore defines a quasigroup by *[Quasigroup Latin Square Equivalence](/theorems/5726)*. This quasigroup is not associative. Using the defining entries, \begin{align*} (1\circ 1)\circ 2=0\circ 2=2 \end{align*} because $1\circ 1=0$ and $0\circ 2=2$. On the other hand, \begin{align*} 1\circ(1\circ 2)=1\circ 1=0 \end{align*} because $1\circ 2=1$ and $1\circ 1=0$. Since $2\ne 0$ in $Q$, the two parenthesizations of $1\circ 1\circ 2$ give different values. Thus the Latin condition gives unique left and right division, but it does not force associativity. [/example] Quasigroups need not have an identity element. When a distinguished element behaves like a two-sided identity, the corresponding Latin square has a first row and first column that reproduce the indexing set after a suitable ordering. [definition: Loop] A loop is a set $L$ equipped with a binary operation $\circ:L\times L\to L$ such that $(L,\circ)$ is a quasigroup and there exists an element $e\in L$ satisfying \begin{align*} e\circ x&=x, & x\circ e&=x \end{align*} for all $x\in L$. [/definition] The identity is forced to be unique: if $e$ and $f$ are both two-sided identities, then $e=e\circ f=f$. Loops sit between quasigroups and groups: they retain division and an identity, but do not require associativity. [example: Group Tables As Loops] Let $G$ be a finite group with operation written multiplicatively, and form its Cayley table by putting $xy$ in row $x$ and column $y$. Fix a row element $g\in G$. If $gh_1=gh_2$, then multiplying both sides on the left by $g^{-1}$ gives \begin{align*} g^{-1}(gh_1)=g^{-1}(gh_2). \end{align*} By associativity in the group, \begin{align*} (g^{-1}g)h_1=(g^{-1}g)h_2. \end{align*} Since $g^{-1}g=e$, this becomes \begin{align*} eh_1=eh_2. \end{align*} Using the identity law gives $h_1=h_2$. Thus the row map $h\mapsto gh$ is injective, and because $G$ is finite, it is bijective. The same argument works in columns. Fix $g\in G$. If $h_1g=h_2g$, then multiplying both sides on the right by $g^{-1}$ gives \begin{align*} (h_1g)g^{-1}=(h_2g)g^{-1}. \end{align*} By associativity, \begin{align*} h_1(gg^{-1})=h_2(gg^{-1}). \end{align*} Since $gg^{-1}=e$, this becomes \begin{align*} h_1e=h_2e. \end{align*} Using the identity law gives $h_1=h_2$. Hence the column map $h\mapsto hg$ is also injective, and therefore bijective. Every row and every column of the Cayley table contains each element of $G$ exactly once, so the table is a Latin square. Finally, the group identity $e$ satisfies $ex=x$ and $xe=x$ for every $x\in G$, so it is a two-sided loop identity; every finite group therefore gives a loop, with its identity row and identity column reproducing the elements of $G$. [/example] The example shows that group tables have especially orderly Latin-square normal forms. The next issue is whether an arbitrary quasigroup can at least be coordinatised with an identity after independent relabelling of the rows, columns, and symbols. In this paragraph, "isotopic" means related by such independent bijections on rows, columns, and symbols; the formal definition is given in the next section. [quotetheorem:5727] [citeproof:5727] The theorem shows that the lack of an identity is often a matter of coordinatisation rather than a structural obstruction: row and column permutations can normalise one chosen element into an identity. The quasigroup hypothesis is essential. For example, on $Q=\{0,1\}$ with $x\circ y=x$, the equation $0\circ z=1$ has no solution, so the construction cannot define the required column relabelling; no independent relabelling can repair the missing Latin column, since relabelling preserves repeated entries in a column. The theorem also has a limitation: it produces a loop only up to isotopy, not an isomorphic copy of the original quasigroup with an identity inserted. Associativity is different again: relabelling rows, columns, and symbols may turn some Latin squares into group tables, but many Latin squares remain non-group-like under every such relabelling. ## Isotopy And Group Tables When should two Latin squares count as the same algebraic construction? Ordinary isomorphism relabels the underlying set in the same way everywhere, but Latin squares naturally allow independent relabellings of rows, columns, and symbols. This leads to isotopy, the [equivalence relation](/page/Equivalence%20Relation) used when comparing quasigroups as coordinatisations of the same incidence pattern. [definition: Isotopy Of Quasigroups] Let $(Q,\circ)$ and $(Q',*)$ be quasigroups. An isotopy from $(Q,\circ)$ to $(Q',*)$ is a triple of bijections \begin{align*} \alpha&:Q\to Q', & \beta&:Q\to Q', & \gamma&:Q\to Q' \end{align*} such that \begin{align*} \gamma(x\circ y)=\alpha(x)*\beta(y) \end{align*} for all $x,y\in Q$. [/definition] In the Latin square picture, $\alpha$ relabels rows, $\beta$ relabels columns, and $\gamma$ relabels symbols. The equation says that after these three independent relabellings, the first multiplication table becomes the second. [example: Isotoping A Square To Put A Symbol In Normal Position] Take a Latin square $L$ on a finite set $Q$, choose a row $r\in Q$, a column $c\in Q$, and put $s=L(r,c)$. Choose an element $q_0\in Q$ to serve as the first row label, first column label, and first symbol label in the new display. Since $Q$ is finite, we can choose bijections $\alpha,\beta,\gamma:Q\to Q$ such that $\alpha(r)=q_0$, $\beta(c)=q_0$, and $\gamma(s)=q_0$. Define the relabelled square $L'$ by \begin{align*} L'(u,v)=\gamma\!\left(L(\alpha^{-1}(u),\beta^{-1}(v))\right). \end{align*} Then the chosen entry moves to the upper-left corner: \begin{align*} L'(q_0,q_0)=\gamma\!\left(L(\alpha^{-1}(q_0),\beta^{-1}(q_0))\right). \end{align*} Because $\alpha(r)=q_0$ and $\beta(c)=q_0$, we have $\alpha^{-1}(q_0)=r$ and $\beta^{-1}(q_0)=c$, so \begin{align*} L'(q_0,q_0)=\gamma(L(r,c)). \end{align*} Since $L(r,c)=s$, this becomes \begin{align*} L'(q_0,q_0)=\gamma(s)=q_0. \end{align*} The square $L'$ is still Latin. Fix a row label $u\in Q$. As $v$ runs through $Q$, the element $\beta^{-1}(v)$ runs through $Q$ exactly once because $\beta$ is a bijection. Since $L$ is Latin, the values $L(\alpha^{-1}(u),\beta^{-1}(v))$ therefore run through $Q$ exactly once. Applying the bijection $\gamma$ sends those values to all elements of $Q$ exactly once, so row $u$ of $L'$ contains each symbol exactly once. The same argument for a fixed column label $v$ uses that $\alpha^{-1}(u)$ runs through $Q$ exactly once as $u$ runs through $Q$, so every column of $L'$ also contains each symbol exactly once. If $\circ$ is the operation encoded by $L$ and $*$ is the operation encoded by $L'$, then for every $x,y\in Q$, \begin{align*} \alpha(x)*\beta(y)=L'(\alpha(x),\beta(y)). \end{align*} Using the definition of $L'$ gives \begin{align*} \alpha(x)*\beta(y)=\gamma(L(x,y)). \end{align*} Since $L(x,y)=x\circ y$, we get \begin{align*} \alpha(x)*\beta(y)=\gamma(x\circ y). \end{align*} Thus the relabelled square is isotopic to the original one, and the selected incidence $L(r,c)=s$ has been put into normal position without changing the underlying Latin incidence pattern. [/example] The example uses three independent bijections, so it preserves incidence more than multiplication. To distinguish this from genuine algebraic sameness of binary operations, we need the stricter relation where one bijection controls all three roles. [definition: Isomorphism Of Quasigroups] An isomorphism from a quasigroup $(Q,\circ)$ to a quasigroup $(Q',*)$ is a bijection $\varphi:Q\to Q'$ such that \begin{align*} \varphi(x\circ y)=\varphi(x)*\varphi(y) \end{align*} for all $x,y\in Q$. [/definition] Every isomorphism is an isotopy, namely $(\varphi,\varphi,\varphi)$, but isotopy is broader. The broader relation is the one relevant to the next question: when does a Latin square become a group table after the allowed row, column, and symbol relabellings? [definition: Group Isotope] A quasigroup $(Q,\circ)$ is a group isotope if there exists a group $(G,\cdot)$ and an isotopy from $(Q,\circ)$ to $(G,\cdot)$. [/definition] Being a group isotope means that the Latin square is obtained from a group Cayley table by independently permuting rows, columns, and symbols. The next formula makes this testable by writing every such multiplication as a group operation surrounded by three permutations. [quotetheorem:5728] [citeproof:5728] This formula is useful because it separates the group operation from the arbitrary relabellings. It also marks a limitation of isotopy: the displayed operation need not inherit associativity from $+$, because the three permutations do not have to respect the group law. The quasigroup hypothesis in the theorem is not cosmetic: if an operation has a repeated row or column entry, no choice of permutations can turn its table into a group table, since relabellings preserve repetition patterns. The group-isotope hypothesis is also substantive, since many finite quasigroups are not isotopic to any group. If all three permutations are the same group automorphism, then the formula is much closer to an isomorphism of groups; with unrelated permutations, the result can be a Latin square whose multiplication is not a group operation. The next example gives a concrete group isotope where associativity fails, so group isotope does not mean group. [example: A Nonassociative Isotope Of A Cyclic Group] Let $G=\mathbb{Z}/5\mathbb{Z}$, with addition modulo $5$, and define \begin{align*} x\circ y=2x+y \pmod 5. \end{align*} For fixed $x\in G$, the row map is $y\mapsto 2x+y$. If \begin{align*} 2x+y_1\equiv 2x+y_2 \pmod 5, \end{align*} then subtracting $2x$ gives $y_1\equiv y_2\pmod 5$, so the row map is injective and therefore bijective on the finite set $G$. For fixed $y\in G$, the column map is $x\mapsto 2x+y$. If \begin{align*} 2x_1+y\equiv 2x_2+y \pmod 5, \end{align*} then $2x_1\equiv 2x_2\pmod 5$. Since $2^{-1}\equiv 3\pmod 5$, multiplying by $3$ gives $x_1\equiv x_2\pmod 5$, so the column map is also bijective. Thus $(G,\circ)$ is a quasigroup. It is isotopic to the cyclic group $(G,+)$ by the bijections $\alpha(x)=2x$, $\beta(y)=y$, and $\gamma(t)=t$. Indeed, \begin{align*} \gamma(x\circ y)=x\circ y. \end{align*} Using the definition of $\circ$, \begin{align*} x\circ y=2x+y. \end{align*} Using the definitions of $\alpha$ and $\beta$, \begin{align*} 2x+y=\alpha(x)+\beta(y). \end{align*} Hence \begin{align*} \gamma(x\circ y)=\alpha(x)+\beta(y), \end{align*} so the isotopy identity holds. The operation is not associative. For arbitrary $x,y,z\in G$, \begin{align*} (x\circ y)\circ z=2(x\circ y)+z. \end{align*} Substituting $x\circ y=2x+y$ gives \begin{align*} (x\circ y)\circ z=2(2x+y)+z=4x+2y+z. \end{align*} On the other hand, \begin{align*} x\circ (y\circ z)=2x+(y\circ z). \end{align*} Substituting $y\circ z=2y+z$ gives \begin{align*} x\circ (y\circ z)=2x+(2y+z)=2x+2y+z. \end{align*} Taking $x=1$, $y=0$, and $z=0$ yields \begin{align*} (1\circ 0)\circ 0\equiv 4 \pmod 5. \end{align*} For the other parenthesization, \begin{align*} 1\circ(0\circ 0)\equiv 2 \pmod 5. \end{align*} Since $4\not\equiv 2\pmod 5$, the operation is a nonassociative quasigroup even though it is isotopic to the cyclic group. [/example] The affine example points toward the main construction of this chapter. Finite fields provide many such operations at once, and their linear algebra makes orthogonality testable by solving a small system of equations. ## Affine Latin Squares Over Finite Fields How can we construct many Latin squares of the same order and prove they are pairwise orthogonal without checking all ordered pairs by hand? Over a finite field, affine linear formulae give Latin squares, and orthogonality becomes invertibility of a $2\times 2$ linear system. [definition: Affine Latin Square] Let $F$ be a finite field and let $a\in F^\times$. The affine Latin square with slope $a$ is the map $L_a:F\times F\to F$ defined by \begin{align*} (x,y)\mapsto L_a(x,y)=ax+y \end{align*} for $x,y\in F$, viewed as an array whose rows, columns, and symbols are indexed by $F$. [/definition] The condition $a\ne 0$ is designed to make multiplication by $a$ reversible. If $a=0$, every column would be constant as a function of $x$, so the column rule would fail as soon as $|F|>1$. The first point to verify is that nonzero slope is exactly enough to make the affine array satisfy the Latin row and column rules. [quotetheorem:5729] [citeproof:5729] This theorem uses both parts of the affine formula. Translation by $y$ or by $ax$ only shifts symbols, while the nonzero coefficient $a$ is what prevents two different rows from producing the same column entry. If $a=0$ and $|F|>1$, then $L_0(x,y)=y$ is independent of $x$, so every column is constant and the Latin condition fails. The theorem therefore supplies Latin squares one slope at a time; the next question is when two different slopes interact without repeating an ordered pair of symbols. Now the Latin property has been reduced to invertibility in one variable. Orthogonality asks for simultaneous control of two affine equations, so the relevant obstruction is whether the two slopes produce an invertible linear system. If the slopes are equal, the two squares are identical rather than orthogonal: the ordered pairs in their superposition have the form $(u,u)$ only, so most pairs in $F^2$ never appear. [quotetheorem:5720] [citeproof:5720] The hypotheses are sharp for this affine family. Distinctness of slopes is needed because equal slopes give identical squares, while nonzero slopes were already needed for the individual Latin property. The proof also shows why fields, rather than arbitrary rings, are convenient here: the difference $a-b$ must be invertible whenever two slopes are compared. The quoted family theorem packages this pairwise calculation for all nonzero slopes at once, since a finite field of order $n$ has $n-1$ nonzero slopes and the same linear-system argument works for every pair of them. The affine construction therefore produces one square for each nonzero field element, so its natural output is a whole family rather than an isolated orthogonal pair. To turn this into an existence theorem by order alone, we need the standard existence fact for finite fields: a field with $n$ elements exists exactly when $n$ is a prime power. This is the point at which the algebraic construction becomes a design-theoretic theorem about MOLS of specified orders. The finite-field hypothesis is doing real work. For a non-prime-power order there is no field of that size, so this particular affine construction has no ambient field in which to run. The theorem below therefore asserts existence in prime-power orders; it does not assert nonexistence in the remaining orders. [quotetheorem:5730] [citeproof:5730] The number $n-1$ is also the largest possible number of MOLS of order $n$, the upper bound proved in Chapter 1 by the orthogonal-array incidence-vector argument. Thus finite fields attain the design-theoretic maximum whenever $n$ is a prime power. The theorem says nothing by itself about $n=6$, because $6$ is not a prime power and no field of order $6$ exists. That is a limitation of this method rather than a general obstruction: the absence of a field prevents the affine field construction, while other combinatorial or algebraic methods may still produce MOLS in non-prime-power orders. This is why the affine construction is not merely a supply of examples when it applies: it produces the complete parallel-class data needed for a classical affine plane and displays the meeting point of algebra, combinatorics, and incidence geometry. [example: Four MOLS Of Order Five] Work over $F=\mathbb{F}_5$. For each nonzero slope $a\in\{1,2,3,4\}$, define \begin{align*} L_a(x,y)=ax+y \pmod 5. \end{align*} For fixed $a\ne 0$ and fixed row $x$, suppose two entries in that row are equal: \begin{align*} ax+y_1\equiv ax+y_2 \pmod 5. \end{align*} Subtracting $ax$ from both sides gives $y_1\equiv y_2\pmod 5$, so the row map $y\mapsto ax+y$ is injective, hence bijective on the finite set $\mathbb{F}_5$. For fixed column $y$, suppose \begin{align*} ax_1+y\equiv ax_2+y \pmod 5. \end{align*} Subtracting $y$ gives \begin{align*} ax_1\equiv ax_2 \pmod 5. \end{align*} Since $a\in\{1,2,3,4\}$ is invertible modulo $5$, multiplying by $a^{-1}$ gives $x_1\equiv x_2\pmod 5$. Thus each $L_a$ is a Latin square of order $5$. For example, in $L_2$ the row with $x=3$ is \begin{align*} L_2(3,y)\equiv 2\cdot 3+y\equiv 6+y\equiv 1+y \pmod 5. \end{align*} Evaluating this for $y=0,1,2,3,4$ gives $1,2,3,4,5$, respectively, and $5\equiv 0\pmod 5$. Hence the row is $1,2,3,4,0$. Now take distinct slopes $a,b\in\{1,2,3,4\}$ and a target ordered pair $(u,v)\in\mathbb{F}_5^2$. A cell $(x,y)$ gives the superposed symbols $(u,v)$ exactly when \begin{align*} ax+y=u \quad\text{and}\quad bx+y=v. \end{align*} Subtracting the second equation from the first gives \begin{align*} (a-b)x=u-v. \end{align*} Because $a\ne b$, the element $a-b$ is nonzero in $\mathbb{F}_5$, so it has an inverse. Therefore \begin{align*} x=(a-b)^{-1}(u-v). \end{align*} With this value of $x$, the first equation forces \begin{align*} y=u-ax. \end{align*} Thus every ordered pair $(u,v)$ occurs in exactly one cell in the superposition of $L_a$ and $L_b$. Therefore $L_1,L_2,L_3,L_4$ are four mutually orthogonal Latin squares of order $5$. [/example] The linear-equation proof is often the most efficient way to check orthogonality in examples. It avoids listing all $25$ ordered pairs for each pair of squares. [example: Checking Orthogonality By Solving Equations] In $\mathbb{F}_5$, compare $L_2$ and $L_4$. We find the cell where the superposed symbols are $(u,v)=(3,1)$ by solving \begin{align*} 2x+y=3 \quad\text{and}\quad 4x+y=1 \end{align*} in $\mathbb{F}_5$. Subtract the second equation from the first: \begin{align*} (2x+y)-(4x+y)=3-1. \end{align*} Expanding the left side gives \begin{align*} 2x+y-4x-y=2. \end{align*} The $y$ terms cancel, so \begin{align*} -2x=2. \end{align*} In $\mathbb{F}_5$, $-2\equiv 3$, hence \begin{align*} 3x=2. \end{align*} Since $3\cdot 2=6\equiv 1\pmod 5$, the inverse of $3$ is $2$. Multiplying both sides by $2$ gives \begin{align*} x=2\cdot 2=4. \end{align*} Substitute $x=4$ into $2x+y=3$: \begin{align*} 2\cdot 4+y=3. \end{align*} Since $2\cdot 4=8\equiv 3\pmod 5$, this becomes \begin{align*} 3+y=3. \end{align*} Subtracting $3$ gives \begin{align*} y=0. \end{align*} Checking the two symbols at this cell, \begin{align*} L_2(4,0)=2\cdot 4+0=8\equiv 3\pmod 5 \end{align*} and \begin{align*} L_4(4,0)=4\cdot 4+0=16\equiv 1\pmod 5. \end{align*} The coefficient difference $2-4=-2\equiv 3$ is nonzero in $\mathbb{F}_5$, so the equation for $x$ has exactly one solution, and then $y$ is forced by $2x+y=3$. Thus the ordered pair $(3,1)$ occurs at the unique cell $(4,0)$. [/example] ## From MOLS To Affine Planes Why are mutually orthogonal Latin squares a central object in design theory rather than only a pleasant algebraic construction? A complete set of $n-1$ MOLS of order $n$ encodes the incidence structure of an affine plane of order $n$: the rows, columns, and Latin square symbols become parallel classes of lines. [definition: Affine Plane Of Order n] An affine plane of order $n$ is an incidence structure with $n^2$ points and $n^2+n$ lines such that each line contains $n$ points, each point lies on $n+1$ lines, any two distinct points lie on a unique common line, and the lines split into $n+1$ parallel classes of $n$ pairwise disjoint lines. [/definition] The parallel classes are the combinatorial shadow of slopes. In the construction below, two classes come from rows and columns, and the remaining $n-1$ classes come from the $n-1$ Latin squares. [quotetheorem:5731] [citeproof:5731] For affine squares over a finite field, this reproduces the usual affine plane $\mathbb{F}_n^2$: vertical lines, horizontal lines, and lines of nonzero finite slope. The hypotheses in the Bose construction have precise roles. The Latin property makes each symbol class a line of size $n$ and makes each symbol class partition the point set; pairwise orthogonality makes symbol lines from different squares meet in exactly one point; completeness supplies enough symbol classes through a fixed point to cover every point outside its row and column. With fewer than $n-1$ squares, the construction still gives several parallel classes of lines, but some pairs of points with distinct row and column coordinates are not joined by any constructed line. The Latin square equation $L_a(x,y)=s$ is the line equation $ax+y=s$. [example: The Affine Plane From The Four Squares Of Order Five] Using the four squares $L_a(x,y)=ax+y$ over $\mathbb{F}_5$, where $a\in\mathbb{F}_5^\times=\{1,2,3,4\}$, take the point set to be $\mathbb{F}_5^2$. The listed lines are the vertical lines $V_c=\{(c,y):y\in\mathbb{F}_5\}$, the horizontal lines $H_c=\{(x,c):x\in\mathbb{F}_5\}$, and the slope lines \begin{align*} S_{a,s}=\{(x,y)\in\mathbb{F}_5^2:ax+y=s\} \end{align*} with $c,s\in\mathbb{F}_5$ and $a\in\mathbb{F}_5^\times$. Each vertical line has the five points $(c,0),(c,1),(c,2),(c,3),(c,4)$, and each horizontal line has the five points $(0,c),(1,c),(2,c),(3,c),(4,c)$. For a slope line $S_{a,s}$, once $x\in\mathbb{F}_5$ is chosen, the equation \begin{align*} ax+y=s \end{align*} forces \begin{align*} y=s-ax. \end{align*} Thus $S_{a,s}$ contains exactly one point above each $x\in\mathbb{F}_5$, hence five points total. For fixed $a$, the five lines $S_{a,s}$ are disjoint: if a point $(x,y)$ lay in both $S_{a,s}$ and $S_{a,t}$, then $ax+y=s$ and $ax+y=t$, so $s=t$. Therefore the vertical lines, the horizontal lines, and each fixed-slope family form parallel classes of five disjoint lines. Now take two distinct points $P=(x_1,y_1)$ and $Q=(x_2,y_2)$. If $x_1=x_2$, then both points lie on $V_{x_1}$. No slope line contains both when $y_1\ne y_2$, because \begin{align*} ax_1+y_1=ax_1+y_2 \end{align*} would imply $y_1=y_2$. If $y_1=y_2$ and $x_1\ne x_2$, then both points lie on $H_{y_1}$. No slope line contains both, because \begin{align*} ax_1+y_1=ax_2+y_1 \end{align*} implies \begin{align*} a(x_1-x_2)=0. \end{align*} Since $a\ne 0$ in $\mathbb{F}_5$, this would force $x_1=x_2$, contradicting the assumption. It remains to handle the case $x_1\ne x_2$ and $y_1\ne y_2$. A slope line $S_{a,s}$ contains both points exactly when $ax_1+y_1=s$ and $ax_2+y_2=s$. Subtracting the second equation from the first gives \begin{align*} a(x_1-x_2)+y_1-y_2=0, \end{align*} so \begin{align*} a(x_1-x_2)=y_2-y_1. \end{align*} Because $x_1-x_2\ne 0$ in $\mathbb{F}_5$, it has an inverse, and therefore \begin{align*} a=(y_2-y_1)(x_1-x_2)^{-1}. \end{align*} Since $y_2-y_1\ne 0$, this value of $a$ is nonzero. With this unique slope, the symbol is forced by \begin{align*} s=ax_1+y_1. \end{align*} Thus any two distinct points determine exactly one of the listed lines, so the four Latin squares of order five produce the affine plane of order $5$. [/example] This closes the loop between algebra and incidence geometry. Quasigroups give the algebraic language of Latin squares, isotopy explains why relabelling matters, finite fields supply complete sets of MOLS in prime-power orders, and Bose's construction turns those MOLS into affine planes. The algebra of quasigroups gives us a systematic way to build Latin squares, but the course now broadens the viewpoint to incidence itself. We move from binary operations and orthogonality to points and blocks, where the same counting ideas appear in a more geometric form. # 3. Incidence Structures and Block Designs This chapter moves from the Latin squares, MOLS, and affine planes of Chapter 2 to the broader language of incidence: points, blocks, and the rule telling us which points lie on which blocks. The only prerequisites are finite counting, binomial coefficients, and the idea that a finite field $\mathbb F_q$ has $q$ elements when $q$ is a prime power. The main question is how much global arithmetic is forced by local uniformity assumptions. We shall see that the defining conditions of a balanced incomplete block design already impose strong equations on the number of blocks through a point and the number of blocks in total. ## Counting Incidences in Point-Block Systems What data must be retained if we want to forget the internal nature of the objects and remember only which points belong to which blocks? For design theory, the essential information is not whether a block is a line, a committee, or a treatment group, but the incidence relation between a finite point set and a finite family of subsets. [definition: Incidence Structure] An incidence structure is a triple $(X, \mathcal B, I)$ where $X$ is a finite set, $\mathcal B$ is a finite set, and $I \subset X \times \mathcal B$ is a relation. [/definition] When $(x,B) \in I$, we say that $x$ is incident with $B$. In most block-design examples, a block $B$ is identified with the subset $\{x \in X : (x,B) \in I\}$, but keeping $\mathcal B$ as a separate set allows repeated blocks. This bare relation is too flexible to compare different examples numerically. We therefore need two basic measurements: the number of points carried by a block and the number of blocks passing through a point. More formally, each element $B \in \mathcal B$ determines the subset $X_B:=\{x \in X : (x,B)\in I\}$ of $X$. Distinct elements of $\mathcal B$ may determine the same subset of $X$, and in that case they are still counted as distinct blocks. To extract numerical constraints from this data, the next definition names the two local counts that every later double-counting argument will compare. [definition: Block Size And Replication Number] Let $(X, \mathcal B, I)$ be an incidence structure. The size of a block $B \in \mathcal B$ is \begin{align*} |B| := |\{x \in X : (x,B) \in I\}|. \end{align*} The replication number of a point $x \in X$ is \begin{align*} r_x := |\{B \in \mathcal B : (x,B) \in I\}|. \end{align*} [/definition] The block sizes count incidences from the block side, while the replication numbers count the same incidences from the point side. The first useful test is whether these two ways of counting the same incidence data agree. To make that comparison cleanly, we next package a point-block incidence as a single object. [definition: Flag] A flag in an incidence structure $(X, \mathcal B, I)$ is an ordered pair $(x,B) \in X \times \mathcal B$ such that $(x,B) \in I$. [/definition] Flags are useful because they are the atomic point-block incidences. The first test of any incidence calculation is that counting all flags by their points and counting all flags by their blocks must give the same number. This turns the two measurements from the previous definition into a single identity, and later it will become the equation $vr=bk$. The following theorem records this double count before any balanced-design assumptions are imposed. [quotetheorem:5732] [citeproof:5732] This identity does not require uniformity, but it does require finiteness so that both sides are ordinary finite sums. If $X=\mathbb N$ and there is one block containing every point, then the point-side and block-side counts are both infinite cardinal counts, and the numerical equation no longer gives the finite arithmetic constraint needed for designs. The identity also does not assert that the summands are equal term-by-term: block sizes may vary from block to block, and replication numbers may vary from point to point. It is therefore best viewed as a finite double-counting principle: it survives uneven block sizes and uneven point replication, but it becomes a useful parameter equation only after uniformity has been imposed. The next example shows the boundary between a valid incidence count and a genuine design condition. [example: Uneven Incidence Structure] Let $X=\{1,2,3,4\}$ and let $\mathcal B=\{B_1,B_2,B_3\}$, where $B_1=\{1,2\}$, $B_2=\{2,3,4\}$, and $B_3=\{1,4\}$. Counting elements in each block gives \begin{align*} |B_1|=|\{1,2\}|=2,\qquad |B_2|=|\{2,3,4\}|=3,\qquad |B_3|=|\{1,4\}|=2. \end{align*} For the replication numbers, point $1$ lies in $B_1$ and $B_3$, point $2$ lies in $B_1$ and $B_2$, point $3$ lies only in $B_2$, and point $4$ lies in $B_2$ and $B_3$. Hence \begin{align*} r_1=2,\qquad r_2=2,\qquad r_3=1,\qquad r_4=2. \end{align*} Counting flags by points gives \begin{align*} \sum_{x\in X} r_x=r_1+r_2+r_3+r_4=2+2+1+2=7. \end{align*} Counting the same flags by blocks gives \begin{align*} \sum_{B\in\mathcal B}|B|=|B_1|+|B_2|+|B_3|=2+3+2=7. \end{align*} Thus the two flag counts agree, even though the block sizes are not all equal and the replication numbers are not all equal; the identity is a counting principle rather than a design condition. [/example] Pair counts provide a second way to measure incidence. Instead of asking how often a single point occurs, we ask how often two distinct points occur together. [definition: Pair Count] Let $(X, \mathcal B, I)$ be an incidence structure in which blocks are viewed as subsets of $X$. For distinct points $x,y \in X$, the pair count of $\{x,y\}$ is \begin{align*} \lambda_{xy} := |\{B \in \mathcal B : x \in B \text{ and } y \in B\}|. \end{align*} [/definition] Uniform pair counts are the central extra condition in a balanced block design. They say that the incidence structure treats every pair of points in the same way. ## Balanced Incomplete Block Designs How can a finite set of points be sampled by smaller blocks so that no point and no pair of points is favoured? The answer is a balanced incomplete block design: all blocks have common size $k$, and every two distinct points occur together exactly $\lambda$ times. [definition: Balanced Incomplete Block Design] A balanced incomplete block design, or BIBD, with parameters $2-(v,k,\lambda)$ is an incidence structure $(X,\mathcal B,I)$ such that $|X|=v$, $2 \le k < v$, every block is incident with exactly $k$ points, and every two distinct points of $X$ are together incident with exactly $\lambda$ blocks. [/definition] The prefix $2$ records that pairs of points are controlled. Some authors relax the inequality $k<v$ and then discuss the complete case separately, but in these notes the phrase balanced incomplete block design includes the inequality in the definition. [remark: Repeated Blocks] The set $\mathcal B$ may be a multiset in many treatments. If two blocks contain the same subset of $X$ but are distinct elements of $\mathcal B$, they are counted separately in block counts, replication numbers, and pair counts. [/remark] The definition requires uniformity for block sizes and pairs, but it does not explicitly require each point to lie in the same number of blocks. That omission is not harmless a priori: a design could seem to balance pairs while still favouring one point in many blocks. The counting result below removes this ambiguity in the nondegenerate case by showing that the pair condition and the common block size already force a single replication number for every point. [quotetheorem:5733] [citeproof:5733] This proof also explains why the quantity $r$ is not an extra parameter in the notation $2-(v,k,\lambda)$: it is forced by the pair condition and block size. The same forced value will be inserted into the flag-count equation $vr=bk$ below, producing a formula for the number of blocks and the divisibility tests that rule out many proposed parameter sets before any construction is attempted. The hypothesis $k\ge 2$ is essential because the argument divides by $k-1$; when $k=1$, no block contains a pair of distinct points, so the pair condition cannot determine how often a single point appears unless $\lambda=0$ and further conventions are imposed. The case $v=1$ is also degenerate, since there are no distinct pairs of points to balance. Finally, the theorem is only conditional: it says that any existing design must have this replication number, not that the resulting number is integral or that blocks with the required incidences can be constructed. [example: Complete Pair Design] Let $X$ be a set of size $v\ge 3$, and let $\mathcal B=\{\{x,y\}:x,y\in X,\ x\ne y\}$ be the set of all two-element subsets of $X$. Every block $B\in\mathcal B$ has the form $B=\{x,y\}$ with $x\ne y$, so $|B|=2$. Now fix two distinct points $x,y\in X$. The block $\{x,y\}$ belongs to $\mathcal B$ and contains both points. If another block $C\in\mathcal B$ contains both $x$ and $y$, then $C$ has exactly two elements and contains the two distinct elements $x$ and $y$, so $C=\{x,y\}$. Thus every pair of distinct points appears in exactly one block, so the incidence structure is a $2-(v,2,1)$ design. The number of blocks is the number of two-element subsets of a $v$-element set: \begin{align*} b=|\mathcal B|=\binom v2=\frac{v(v-1)}2. \end{align*} For a fixed point $x\in X$, the blocks through $x$ are exactly \begin{align*} \{x,y\}\qquad \text{with } y\in X\setminus\{x\}. \end{align*} There are $|X\setminus\{x\}|=v-1$ choices of $y$, and different choices of $y$ give different blocks, so $r_x=v-1$ for every $x$. Hence the common replication number is $r=v-1$. [/example] The complete pair design is the smallest possible block-size case for a genuine pair-balanced design: blocks of size $1$ cannot contain any pair, while blocks of size $2$ record pairs directly. The next example is the smallest projective-plane case, and it shows a design where every block has three points and every point also lies on three blocks. [example: Fano Plane] Let $X=\{1,2,3,4,5,6,7\}$. Take the seven blocks $B_1=\{1,2,3\}$, $B_2=\{1,4,5\}$, $B_3=\{1,6,7\}$, $B_4=\{2,4,6\}$, $B_5=\{2,5,7\}$, $B_6=\{3,4,7\}$, and $B_7=\{3,5,6\}$. Each displayed block has three elements, so the common block size is $k=3$. To verify the pair condition, list the pairs occurring in each block. The block $B_1$ contains $\{1,2\}$, $\{1,3\}$, and $\{2,3\}$. The block $B_2$ contains $\{1,4\}$, $\{1,5\}$, and $\{4,5\}$. The block $B_3$ contains $\{1,6\}$, $\{1,7\}$, and $\{6,7\}$. The block $B_4$ contains $\{2,4\}$, $\{2,6\}$, and $\{4,6\}$. The block $B_5$ contains $\{2,5\}$, $\{2,7\}$, and $\{5,7\}$. The block $B_6$ contains $\{3,4\}$, $\{3,7\}$, and $\{4,7\}$. The block $B_7$ contains $\{3,5\}$, $\{3,6\}$, and $\{5,6\}$. This list has one entry for each pair lying inside one of the seven triples, namely \begin{align*} 7\binom 32=7\cdot 3=21 \end{align*} listed pairs. The set $X$ has \begin{align*} \binom 72=\frac{7\cdot 6}{2}=21 \end{align*} two-element subsets. Since the displayed list contains no repeated pair and has the same size as the full set of two-element subsets of $X$, every pair of distinct points occurs in exactly one block. Thus the incidence structure is a $2-(7,3,1)$ design. There are exactly the seven listed blocks, so $b=7$. The blocks through the points are as follows: $1$ lies in $B_1,B_2,B_3$; $2$ lies in $B_1,B_4,B_5$; $3$ lies in $B_1,B_6,B_7$; $4$ lies in $B_2,B_4,B_6$; $5$ lies in $B_2,B_5,B_7$; $6$ lies in $B_3,B_4,B_7$; and $7$ lies in $B_3,B_5,B_6$. Each point lies in exactly three blocks, so the common replication number is $r=3$. [/example] [illustration:fano-plane-seven-lines] The Fano plane is symmetric in the sense that it has the same number of points and blocks. Affine planes give another family of examples in which parallel classes appear, and the order-$3$ case fits the same $2$-design language. [example: Affine Plane Of Order Three] Let $X=\mathbb F_3^2$, so $|X|=3\cdot 3=9$. Use the four coefficient classes \begin{align*} (1,0),\qquad (0,1),\qquad (1,1),\qquad (1,2), \end{align*} because every nonzero pair $(a,b)\in \mathbb F_3^2$ is a nonzero scalar multiple of exactly one of these. For each class and each $c\in\mathbb F_3$, take the line \begin{align*} L_{a,b,c}=\{(x,y)\in\mathbb F_3^2: ax+by=c\}. \end{align*} Thus there are \begin{align*} 4\cdot 3=12 \end{align*} blocks. Each line has $3$ points. Indeed, the four types are \begin{align*} x=c,\qquad y=c,\qquad x+y=c,\qquad x+2y=c. \end{align*} For $x=c$, the points are $(c,0),(c,1),(c,2)$. For $y=c$, the points are $(0,c),(1,c),(2,c)$. For $x+y=c$, choosing $y\in\mathbb F_3$ determines $x=c-y$, giving the three points \begin{align*} (c-0,0),\qquad (c-1,1),\qquad (c-2,2). \end{align*} For $x+2y=c$, choosing $y\in\mathbb F_3$ determines $x=c-2y$, giving the three points \begin{align*} (c-2\cdot 0,0),\qquad (c-2\cdot 1,1),\qquad (c-2\cdot 2,2). \end{align*} So the common block size is $k=3$. Now take two distinct points $P=(x_1,y_1)$ and $Q=(x_2,y_2)$. Put \begin{align*} u=x_2-x_1,\qquad v=y_2-y_1. \end{align*} Since $P\ne Q$, the vector $(u,v)$ is not $(0,0)$. A line $ax+by=c$ contains both $P$ and $Q$ exactly when \begin{align*} ax_1+by_1=c \end{align*} and \begin{align*} ax_2+by_2=c. \end{align*} Subtracting these equations gives \begin{align*} a(x_2-x_1)+b(y_2-y_1)=0, \end{align*} that is, \begin{align*} au+bv=0. \end{align*} If $v=0$, then $u\ne 0$, so $au=0$ forces $a=0$, and the coefficient class is $(0,1)$. The unique line is then $y=y_1$. If $v\ne 0$, then after scaling the coefficients we may set $b=1$, and the equation $au+v=0$ gives \begin{align*} a=-uv^{-1}. \end{align*} Thus the coefficient class is uniquely determined, and then the constant is forced to be \begin{align*} c=ax_1+by_1. \end{align*} Therefore every pair of distinct points lies on exactly one block, so $\lambda=1$ and the incidence structure is a $2-(9,3,1)$ design. For a fixed point $(x_0,y_0)$, there is exactly one line through it in each of the four coefficient classes, namely the line with \begin{align*} c=ax_0+by_0. \end{align*} Hence every point lies on $4$ blocks, so $r=4$. The affine plane of order three therefore has $v=9$, $k=3$, $\lambda=1$, $b=12$, and $r=4$. [/example] [illustration:affine-plane-f3-parallel-classes] This example connects back to the finite-field constructions from the previous chapter. More generally, if $q$ is a prime power, then the affine plane over $\mathbb F_q$ has point set $\mathbb F_q^2$ and lines of size $q$. Orthogonal Latin squares of order $q$ encode the parallel classes of this affine plane, and the affine plane then supplies a $2-(q^2,q,1)$ design. ## Parameter Equations And Divisibility Conditions Which triples $(v,k,\lambda)$ can even pass the first arithmetic tests for being design parameters? The two main counts are flags and point-pair incidences, and together they force integrality conditions before any construction is attempted. [definition: Design Parameters] For a $2-(v,k,\lambda)$ design, write $b:=|\mathcal B|$ for the number of blocks and write $r$ for the common replication number of a point. [/definition] The parameters $b$ and $r$ are not independent once $v,k,\lambda$ are fixed. Before trying to construct blocks, there is a basic consistency problem: the same incidences can be counted from the point side or the block side, and the same point-pair incidences can be counted through a fixed point or through the blocks containing it. If these counts do not agree, the proposed parameters cannot describe any balanced incomplete block design. [quotetheorem:5734] [citeproof:5734] These equations are necessary conditions, not existence theorems. Their hypotheses encode exactly the uniformities used in the double counts: without constant block size, the block-side flag count is $\sum_{B\in\mathcal B}|B|$ rather than $bk$, and without the pair condition there is no reason for a common $r$ to exist. For instance, the uneven incidence structure above has $v=4$ and $b=3$, but there is no single $k$ and no single $r$ for which $vr=bk$ expresses its flag count. The exclusions $v\ge 2$ and $k\ge 2$ remove specific degenerate behaviours. If $v=1$, there are no pairs of distinct points, so the pair-balance condition imposes no restriction on how many copies of the one-point block are present; choosing three copies gives $b=3$ and $r=3$, while choosing five copies gives $b=5$ and $r=5$, with no pair count distinguishing them. If $k=1$ and $v\ge 2$, every block is a singleton and no block contains a pair, so a pair-balanced structure can only have $\lambda=0$; the equation $\lambda(v-1)=r(k-1)$ then reads $0=0$ and does not determine the point replication numbers. These examples explain why the nondegenerate hypotheses are part of the theorem rather than cosmetic restrictions. Before looking for blocks, we can at least ask whether the formulas give integer values for the quantities that must count actual points, blocks, and incidences. [quotetheorem:5735] [citeproof:5735] The divisibility conditions are the first filter in a design search. The assumptions $v\ge 2$ and $k\ge 2$ are the same nondegeneracy assumptions needed for the parameter equations. When $v=1$, the expression $\lambda(v-1)$ is always $0$, so the first divisibility condition gives no information and the second condition only tests divisibility of $0$; it cannot distinguish one copy of the single block from many repeated copies. When $k=1$, the divisibility statement involving $k-1$ is not meaningful as a positive divisor condition, and the formula for $b$ would require division by $0$. Passing the nondegenerate test only says that the forced values of $r$ and $b$ are integers; it says nothing about arranging the incidences themselves. A standard illustration is the parameter set $2-(36,6,1)$: the divisibility checks pass, but such a design would be an affine plane of order $6$, and its nonexistence requires structural arguments beyond these counts. [example: Testing Proposed Parameters] Consider the proposed parameters $2-(10,4,1)$. If such a design existed, then by *Necessary Divisibility Conditions For Two Designs* it would have to satisfy \begin{align*} k-1 \mid \lambda(v-1) \end{align*} and \begin{align*} k(k-1) \mid \lambda v(v-1). \end{align*} Substituting $v=10$, $k=4$, and $\lambda=1$ into the first condition gives \begin{align*} k-1=4-1=3, \qquad \lambda(v-1)=1(10-1)=9, \end{align*} and $3\mid 9$ because $9=3\cdot 3$. Substituting the same values into the second condition gives \begin{align*} k(k-1)=4(4-1)=4\cdot 3=12, \end{align*} while \begin{align*} \lambda v(v-1)=1\cdot 10\cdot (10-1)=10\cdot 9=90. \end{align*} If $12$ divided $90$, then $90=12m$ for some integer $m$. But \begin{align*} 90=12\cdot 7+6, \end{align*} so $90$ is not a multiple of $12$. The second necessary divisibility condition fails, and therefore no $2-(10,4,1)$ design exists. [/example] For the examples above, the equations recover the advertised values of $b$ and $r$. In the Fano plane, \begin{align*} r=\frac{\lambda(v-1)}{k-1}=\frac{6}{2}=3, \qquad b=\frac{vr}{k}=7. \end{align*} In the affine plane of order three, \begin{align*} r=\frac{8}{2}=4, \qquad b=\frac{9\cdot 4}{3}=12. \end{align*} [remark: Necessary Versus Sufficient] The parameter equations should be treated as arithmetic constraints. Their value is that they translate a proposed incidence problem into quantities that must be compatible with integer counts before any construction begins. Later chapters add structural tools, including finite geometries and Wilson-type existence results, that explain when admissible parameters are realised by actual designs. [/remark] The incidence identities from the previous chapter tell us when a design is numerically plausible, but they do not yet explain how to prove impossibility. Linear algebra strengthens those counting arguments by turning block incidence into matrix relations, ranks, and orthogonality conditions. # 4. Fisher's Inequality and Linear Algebra Methods The previous chapter introduced BIBDs, equivalently $2$-designs with constant block size and pair multiplicity, through their incidence conditions and the basic counting identities relating $v$, $b$, $r$, $k$, and $\lambda$. This chapter studies what linear algebra adds to those counting arguments. The main point is that an incidence matrix does not only record containment; its products encode intersections, ranks, and positivity constraints that force global inequalities such as Fisher's inequality. ## Incidence Matrices and Gram Matrices How can the condition that every pair of points lies in exactly $\lambda$ blocks be stored in a single algebraic object? The answer is to arrange all point-block incidences into a matrix and then multiply it by its transpose. This turns intersection counting into a rank computation. [definition: Incidence Matrix] Let $\mathcal D=(X,\mathcal B)$ be a block design with $X=\{x_1,\dots,x_v\}$ and $\mathcal B=\{B_1,\dots,B_b\}$. The incidence matrix of $\mathcal D$ is the $v\times b$ matrix $N=(N_{ij})$ such that $N_{ij}=1$ if $x_i\in B_j$ and $N_{ij}=0$ if $x_i\notin B_j$. [/definition] Rows of $N$ correspond to points and columns correspond to blocks. Thus the row [inner product](/page/Inner%20Product) counts how many blocks contain two given points, while the column inner product counts the intersection size of two given blocks. [example: Incidence Matrix of the Fano Plane] Let the seven points be $100,010,001,110,101,011,111$ in that order. The seven blocks are the triples $\{u,w,u+w\}$ obtained from pairs of distinct nonzero vectors; explicitly they are $\{100,010,110\}$, $\{100,001,101\}$, $\{010,001,011\}$, $\{100,011,111\}$, $\{010,101,111\}$, $\{001,110,111\}$, and $\{110,101,011\}$. Each block has $3$ points because the nonzero part of $\operatorname{span}(u,w)$ is exactly $\{u,w,u+w\}$. With this ordering, the rows of the incidence matrix $N$ are $1101000$, $1010100$, $0110010$, $1000011$, $0100101$, $0011001$, and $0001110$. For instance, the first row says that $100$ lies in the blocks $\{100,010,110\}$, $\{100,001,101\}$, and $\{100,011,111\}$. The row sums are \begin{align*} 3,3,3,3,3,3,3, \end{align*} and the column sums are also \begin{align*} 3,3,3,3,3,3,3, \end{align*} so every point lies in $3$ blocks and every block contains $3$ points. The $(i,j)$ entry of $NN^\top$ is the dot product of row $i$ and row $j$. For the first diagonal entry, \begin{align*} (NN^\top)_{11}=1^2+1^2+0^2+1^2+0^2+0^2+0^2=3. \end{align*} For a typical off-diagonal entry, \begin{align*} (NN^\top)_{12}=(1)(1)+(1)(0)+(0)(1)+(1)(0)+(0)(1)+(0)(0)+(0)(0)=1. \end{align*} The same off-diagonal value occurs for any two distinct rows: if $u$ and $w$ are distinct nonzero vectors in $\mathbb F_2^3$, then the unique block containing both is $\{u,w,u+w\}$. Therefore \begin{align*} (NN^\top)_{ij}=3\text{ if }i=j,\quad\text{and}\quad (NN^\top)_{ij}=1\text{ if }i\ne j. \end{align*} The matrix $2I+J$ has diagonal entries $2+1=3$ and off-diagonal entries $0+1=1$, where $J$ is the $7\times 7$ all-one matrix. Hence \begin{align*} NN^\top=2I+J. \end{align*} This Gram matrix records exactly that each point occurs in $3$ blocks and each pair of distinct points occurs together in $1$ block. [/example] The example shows that multiplying the incidence matrix by its transpose recovers the two numbers that define pairwise point incidence. To use this observation beyond the Fano plane, we need a formula for this Gram matrix in an arbitrary $2$-design. [quotetheorem:5736] [citeproof:5736] This formula packages all pairwise point incidences into one matrix, and the hypotheses of a $2$-design are exactly what make the off-diagonal entries uniform. Without the pair condition, the Gram matrix would still count common blocks, but it would not have the simple form $(r-\lambda)I+\lambda J$. Fisher's inequality will require more than identifying the entries: we need nonsingularity, because nonsingularity forces the rows of $N$ to be independent. That question is decided by the eigenvalues of matrices of the form $aI+cJ$. [quotetheorem:5737] [citeproof:5737] The positivity of these eigenvalues is the bridge from combinatorics to rank. The condition $1<k<v$ is used exactly here: it rules out the degenerate cases in which the Gram matrix can lose rank for reasons unrelated to the design's pair structure. Since $NN^\top$ is invertible, the rows of $N$ must be linearly independent over $\mathbb R$. This converts local incidence regularity into a global lower bound on the number of columns of $N$, which is the number of blocks. ## Fisher's Inequality A $2$-design is defined locally: every pair of points appears in exactly $\lambda$ blocks. Fisher's inequality answers a global question: how many blocks are forced by this local regularity? For nontrivial designs, the number of blocks cannot be smaller than the number of points. [definition: Nontrivial Two Design] A $2$-$(v,k,\lambda)$ design is nontrivial if \begin{align*} 1<k<v. \end{align*} [/definition] The hypotheses exclude degenerate cases where blocks have size $1$ or every block is the whole point set. With those cases removed, the eigenvalue calculation above says that the point Gram matrix is invertible, so the incidence matrix must have at least $v$ independent rows. This is exactly the rank obstruction needed for Fisher's inequality. [quotetheorem:5738] [citeproof:5738] This proof is short, but it is stronger than a counting argument because it detects [linear independence](/page/Linear%20Independence). The nontriviality hypothesis is not cosmetic: the rank argument depends on $r-\lambda>0$, which is exactly where degenerate block sizes would break the conclusion. Fisher's inequality is only a necessary condition, so satisfying $b\ge v$ does not guarantee that a design exists. It also explains why equality is special: if $b=v$, then the incidence matrix is square and has full rank, making it possible to compare rows and columns symmetrically. [example: Ruling Out Parameters by Fisher Inequality] Suppose a proposed nontrivial $2$-design has parameters $2$-$(10,4,2)$. Let $r$ be the replication number and let $b$ be the number of blocks. The counting identity $r(k-1)=\lambda(v-1)$ gives \begin{align*} r(4-1)=2(10-1). \end{align*} Thus \begin{align*} 3r=18. \end{align*} Dividing by $3$ gives \begin{align*} r=6. \end{align*} The counting identity $bk=vr$ now gives \begin{align*} 4b=10\cdot 6. \end{align*} Since $10\cdot 6=60$, this is \begin{align*} 4b=60. \end{align*} Dividing by $4$ gives \begin{align*} b=15. \end{align*} Since \begin{align*} 15\ge 10, \end{align*} the necessary condition from *Fisher Inequality* is satisfied, so Fisher's inequality alone does not rule out these parameters. In contrast, if a proposed nontrivial $2$-design had $v=9$ and $b=8$, then *Fisher Inequality* would require $b\ge v$. Substituting $b=8$ and $v=9$ gives \begin{align*} 8\ge 9. \end{align*} This inequality is false, so no nontrivial $2$-design with $v=9$ and $b=8$ exists, regardless of the values of $k$ and $\lambda$. [/example] The example illustrates the role of Fisher's inequality as a necessary condition rather than a complete existence criterion. Parameter sets that survive it may still fail divisibility, congruence, or deeper arithmetic tests. [remark: Field of the Rank Argument] The rank proof above is over $\mathbb R$, where positivity of $NN^\top$ is available. Similar incidence-matrix methods can be used over finite fields, but then the rank may change after reducing entries modulo a prime. Those modular rank arguments are a separate source of nonexistence theorems. [/remark] Fisher's inequality is the first linear algebra obstruction in the course. The next question is what happens in the equality case, where the design has exactly as many blocks as points. ## Symmetric Designs and Dual Designs When Fisher's inequality is sharp, the incidence matrix is square. This raises two connected questions: do blocks behave like points, and can we interchange the roles of points and blocks? Symmetric designs are precisely the designs where this dual viewpoint preserves the same parameters. [definition: Symmetric Design] A $2$-$(v,k,\lambda)$ design with $b$ blocks is symmetric if \begin{align*} b=v. \end{align*} [/definition] The word symmetric refers to the balance between the number of points and the number of blocks. To make that balance useful, we first need to translate it into the replication parameter, because duality will exchange blocks with points. [quotetheorem:5739] [citeproof:5739] Once $r=k$, the row and column sums of the incidence matrix agree. This conclusion uses only the basic counting identity $bk=vr$, so it remains much weaker than saying that blocks behave like points. Equal row and column sums do not control intersections between two different blocks; nonsymmetric designs can have blocks meeting in different numbers of points. The next issue is therefore whether column inner products also match row inner products, which is the missing condition needed before blocks can be treated as points. [quotetheorem:5740] [citeproof:5740] This theorem turns the nontrivial equality case into a genuine point-block duality: the columns of the incidence matrix satisfy the same pairwise inner product conditions as the rows. The nontriviality assumption is needed because the proof imports the invertibility established in Fisher's inequality, and that invertibility depends on $k>\lambda$. The result is stronger than equal row and column sums; it says that every pair of distinct blocks has the same intersection size. The natural next construction is therefore to swap points and blocks and ask whether the design axioms survive the swap. [definition: Dual Design] Let $\mathcal D=(X,\mathcal B)$ be an incidence structure. The dual incidence structure $\mathcal D^*$ has point set $\mathcal B$, block set $X$, and incidence relation \begin{align*} B\text{ is incident with }x\text{ in }\mathcal D^* \quad\iff\quad x\in B\text{ in }\mathcal D. \end{align*} [/definition] The incidence matrix of the dual design is $N^\top$. Thus duality exchanges point counts with block counts and row conditions with column conditions. For a general design the result may not be a $2$-design, so we now use the symmetric hypotheses to check the axioms after dualising. [quotetheorem:5741] [citeproof:5741] Duality explains why symmetric designs are the natural equality cases of Fisher's inequality. The theorem depends on the block-intersection result, so it is not true for an arbitrary $2$-design merely because one can formally transpose the incidence matrix. In a nonsymmetric design, dual blocks may have unequal sizes or pairs of dual points may lie in different numbers of dual blocks. This is why projective planes fit the theory so well: their incidence axioms already make lines and points interchangeable. [example: The Projective Plane of Order Two] For a projective plane of order $2$, the standard projective-plane counts give \begin{align*} v=2^2+2+1=4+2+1=7. \end{align*} The same count applies to the lines, so \begin{align*} b=2^2+2+1=4+2+1=7. \end{align*} Each line contains \begin{align*} k=2+1=3 \end{align*} points, and each point lies on \begin{align*} r=2+1=3 \end{align*} lines. Since any two distinct points determine exactly one line, the pair multiplicity is \begin{align*} \lambda=1. \end{align*} Thus the incidence structure is a $2$-$(7,3,1)$ design. Since \begin{align*} b=7=v, \end{align*} it is symmetric. In the dual incidence structure, the original lines become points and the original points become blocks. Saying that any two dual points lie together in exactly one dual block translates back to saying that any two original lines meet in exactly one original point. This is the line-intersection axiom for the projective plane of order $2$, so the dual incidence structure has the same $2$-$(7,3,1)$ parameters. [/example] The Fano plane is the smallest nontrivial symmetric design and is the model case for the theory. Larger symmetric designs exist, but their parameters are constrained by arithmetic conditions that do not appear in Fisher's inequality. The course records the main such obstruction for symmetric designs as a theorem to be used as a parameter test. [quotetheorem:5742] The course states this theorem as a major arithmetic obstruction rather than proving it. Unlike Fisher's inequality, it is not a rank consequence of the incidence matrix over $\mathbb R$; its proof uses quadratic forms and number-theoretic input beyond the linear algebra developed here. The theorem is also only a necessary condition, so passing the displayed Diophantine test does not by itself construct a symmetric design. Its value in the course is as a sharper parameter test once Fisher's inequality and symmetry have already narrowed the possibilities. [example: A Bruck Ryser Chowla Obstruction] A projective plane of order $6$ would have parameters \begin{align*} v=6^2+6+1=36+6+1=43,\qquad k=6+1=7,\qquad \lambda=1. \end{align*} It would therefore be a symmetric $2$-$(43,7,1)$ design. In the notation of *[Bruck Ryser Chowla Theorem for Symmetric Designs](/theorems/5742)*, this gives \begin{align*} n=k-\lambda=7-1=6. \end{align*} Also \begin{align*} \frac{v-1}{2}=\frac{43-1}{2}=\frac{42}{2}=21, \end{align*} which is odd, so \begin{align*} (-1)^{(v-1)/2}=(-1)^{21}=-1. \end{align*} Thus the theorem would require a nonzero integer solution $(x,y,z)\in\mathbb Z^3$ to \begin{align*} z^2=6x^2-y^2. \end{align*} Adding $y^2$ to both sides gives the equivalent equation \begin{align*} z^2+y^2=6x^2. \end{align*} We show that this equation has no nonzero integer solution. Reducing both sides modulo $3$ gives \begin{align*} z^2+y^2\equiv 6x^2\equiv 0\pmod 3. \end{align*} For any integer $a$, the residue of $a$ modulo $3$ is $0$, $1$, or $2$, and therefore \begin{align*} a^2\equiv 0^2,1^2,\text{ or }2^2\equiv 0,1,\text{ or }4\equiv 0,1,\text{ or }1\pmod 3. \end{align*} Thus every square is congruent to $0$ or $1$ modulo $3$. Since \begin{align*} z^2+y^2\equiv 0\pmod 3, \end{align*} the only possible pair of square residues is \begin{align*} z^2\equiv 0\pmod 3,\qquad y^2\equiv 0\pmod 3, \end{align*} because $1+0\equiv 1\pmod 3$ and $1+1\equiv 2\pmod 3$. Hence $3\mid z$ and $3\mid y$. Write \begin{align*} z=3z_1,\qquad y=3y_1 \end{align*} for integers $z_1$ and $y_1$. Substituting these expressions into $z^2+y^2=6x^2$ gives \begin{align*} (3z_1)^2+(3y_1)^2=6x^2. \end{align*} Expanding the squares gives \begin{align*} 9z_1^2+9y_1^2=6x^2. \end{align*} Factoring the left side gives \begin{align*} 9(z_1^2+y_1^2)=6x^2. \end{align*} Dividing by $3$ gives \begin{align*} 3(z_1^2+y_1^2)=2x^2. \end{align*} The left side is divisible by $3$, so $3\mid 2x^2$. Since $3\nmid 2$, it follows that $3\mid x^2$, and hence $3\mid x$. Write $x=3x_1$ for some integer $x_1$. Substituting $x=3x_1$ into \begin{align*} 9(z_1^2+y_1^2)=6x^2 \end{align*} gives \begin{align*} 9(z_1^2+y_1^2)=6(3x_1)^2. \end{align*} Expanding the square gives \begin{align*} 9(z_1^2+y_1^2)=54x_1^2. \end{align*} Dividing by $9$ gives \begin{align*} z_1^2+y_1^2=6x_1^2. \end{align*} Thus any integer solution $(x,y,z)$ produces another integer solution $(x_1,y_1,z_1)$ with \begin{align*} x=3x_1,\qquad y=3y_1,\qquad z=3z_1. \end{align*} Repeating the same argument shows that $3^m$ divides $x$, $y$, and $z$ for every positive integer $m$. A nonzero integer cannot be divisible by every power of $3$, so the only integer solution is $(0,0,0)$. The required nonzero solution does not exist, so *Bruck Ryser Chowla Theorem for Symmetric Designs* rules out a projective plane of order $6$. [/example] This final example shows the hierarchy of necessary conditions. Fisher's inequality forces enough blocks; symmetry turns equality into duality; Bruck-Ryser-Chowla adds arithmetic restrictions on the remaining symmetric parameter sets. Once linear algebra enters, the familiar finite geometries reappear as especially symmetric designs. The next chapter makes that connection explicit by treating projective and affine planes as central examples of the incidence structures already studied. # 5. Projective and Affine Planes Projective and affine planes are the finite geometries that sit behind the strongest examples of block designs and mutually orthogonal Latin squares. The previous chapters built incidence structures from algebraic tables and from balanced block systems; here the same objects reappear as points and lines. The guiding question is how a small list of incidence axioms can force the numerical parameters of a design, and how finite fields provide models attaining those parameters. ## Incidence Axioms for Finite Planes What should a finite geometry retain from the ordinary Euclidean plane? We keep points, lines, unique joining lines, and parallelism in the affine case; in the projective case we remove parallelism by adding points at infinity. To make those statements countable and suitable for designs, we first isolate the affine incidence axioms. [definition: Finite Affine Plane] A finite affine plane is an incidence structure $(P, L, I)$ consisting of a finite set $P$ of points, a finite set $L$ of lines, and an incidence relation $I \subset P \times L$ satisfying: 1. Any two distinct points lie on a unique common line. 2. For every point $p \in P$ and every line $\ell \in L$ with $p$ not incident with $\ell$, there is a unique line through $p$ disjoint from $\ell$. 3. There exist three points not lying on a common line. [/definition] The second axiom is the finite version of Euclid's parallel postulate. To use it in counting arguments and later in the construction of Latin squares, we need a name for the directions determined by disjoint lines. [definition: Parallel Lines and Parallel Classes] In a finite affine plane, two lines are parallel if they are equal or disjoint. A parallel class is an equivalence class of lines under this relation. [/definition] Parallel classes organize the affine plane into families of lines that cover the point set without overlap. Without the uniqueness in the parallel axiom, this organization can fail: through a point off a line there might be several disjoint candidates, so there would be no well-defined direction class. The next theorem is needed because later constructions use affine planes as designs and as Latin-square arrays, where the number of points on each line, the number of directions, and the size of each direction class must be known rather than assumed. The proof therefore turns the qualitative incidence axioms into uniform numerical data: first a common line size, then a common point degree, and finally the full count of points, lines, and parallel classes. [quotetheorem:5743] [citeproof:5743] This theorem is the first place where the affine axioms show their full force: they do not merely describe a geometry, they force all incidence numbers from one integer $n$. The non-collinearity axiom is necessary, since a degenerate structure with all points on one line satisfies the joining property but has no two-dimensional parameter count. The limitation is equally important: the theorem proves necessary parameters, not existence for every $n$. Projective geometry removes the exceptional behaviour of parallel lines, and the appropriate axioms need a second incidence condition saying that lines meet just as points join. [definition: Finite Projective Plane] A finite projective plane is an incidence structure $(P,L,I)$ consisting of a finite set $P$ of points, a finite set $L$ of lines, and an incidence relation $I \subset P \times L$ satisfying: 1. Any two distinct points lie on a unique common line. 2. Any two distinct lines meet in a unique common point. 3. There exist four points such that no three of them lie on a common line. [/definition] The third axiom rules out pencil-like geometries and ensures that the plane has enough dimension to behave like a two-dimensional geometry. Without it, one can make incidence structures where all lines pass through a single point; such examples have line intersections but do not resemble a plane and do not give the design parameters below. With every pair of lines now meeting, the affine parameter count has a projective analogue that will later become the symmetric design parameter count. [quotetheorem:5744] [citeproof:5744] This theorem is the projective counterpart of the affine parameter theorem, with the missing affine directions now counted as ordinary points on lines. The four-point axiom is necessary because the first two projective incidence axioms alone allow degenerate pencil-like examples where the formula $n^2+n+1$ is not forced. The result still gives only a necessary numerical shape: it does not assert that a projective plane exists for every integer $n$. The equality $|P|=|L|$ is the bridge to symmetric designs, while the difference from the affine count suggests adding or deleting a line at infinity. [quotetheorem:5745] [citeproof:5745] This theorem explains why affine and projective planes have nearly identical parameter formulas: they are two presentations of the same incidence structure with one line toggled on or off. The hypothesis that the affine structure is a genuine affine plane is necessary; for example, if two disjoint lines $\ell_1,\ell_2$ have a third line meeting $\ell_1$ but disjoint from $\ell_2$, then disjointness does not define a direction class, so a single point at infinity cannot be assigned consistently to that family. The converse also depends on deleting an entire line, not an arbitrary set of points: scattered deleted points create missing intersections in unrelated directions, so the remaining disjoint lines do not assemble into parallel classes indexed by the deleted points of a single line. This line-at-infinity construction is the conceptual link between directions in coordinate geometry and the algebraic models over finite fields. [example: The Affine Plane AG(2,3)] Let $\mathbb F_3=\{0,1,2\}$ with arithmetic modulo $3$, and take the point set to be $\mathbb F_3^2$, so \begin{align*} |\mathbb F_3^2|=|\mathbb F_3|\cdot |\mathbb F_3|=3\cdot 3=9. \end{align*} For each $a,b\in \mathbb F_3$, define \begin{align*} L_{a,b}=\{(x,ax+b):x\in \mathbb F_3\}, \end{align*} and for each $c\in \mathbb F_3$, define the vertical line \begin{align*} V_c=\{(c,y):y\in \mathbb F_3\}. \end{align*} There are $3$ choices for $a$ and $3$ choices for $b$, giving $3\cdot 3=9$ non-vertical lines, and there are $3$ vertical lines, so the total number of lines is \begin{align*} 9+3=12. \end{align*} For a fixed slope $a$, the three lines $L_{a,0},L_{a,1},L_{a,2}$ are disjoint: if a point $(x,y)$ lay on both $L_{a,b}$ and $L_{a,b'}$, then \begin{align*} y=ax+b \quad\text{and}\quad y=ax+b', \end{align*} so subtracting gives $b=b'$ in $\mathbb F_3$. They also cover all $9$ points, because for any $(x,y)\in \mathbb F_3^2$ the value \begin{align*} b=y-ax \end{align*} puts $(x,y)$ on exactly one line $L_{a,b}$. Thus each fixed slope $a=0,1,2$ gives one parallel class of three lines. The vertical lines $V_0,V_1,V_2$ are also pairwise disjoint, since a point cannot have two different first coordinates, and they cover all points because every $(x,y)$ lies on $V_x$. Hence $AG(2,3)$ has four parallel classes: the three slope classes and the vertical class, each consisting of three disjoint lines covering all nine points. [/example] ## Finite Field Coordinates and Latin Squares How do we build finite planes instead of only counting them? The most important construction replaces real coordinates by coordinates in a finite field. The algebraic operations in the field then guarantee the same unique-solution properties that lines have in ordinary coordinate geometry. [definition: Affine Plane Over a Finite Field] Let $q$ be a prime power and let $\mathbb F_q$ be the finite field of order $q$. The affine plane $AG(2,q)$ has point set $\mathbb F_q^2$ and line set consisting of all subsets of the forms \begin{align*} \{(x, ax+b):x\in \mathbb F_q\}, \qquad \{(c,y):y\in \mathbb F_q\}, \end{align*} where $a,b,c \in \mathbb F_q$. [/definition] The two displayed families are the non-vertical and vertical lines. To prove that this coordinate recipe really satisfies the affine axioms, we check that pairs of coordinate equations over $\mathbb F_q$ have the required unique solutions. [quotetheorem:5746] [citeproof:5746] The finite-field hypothesis is doing real work here: the inverse $(x_2-x_1)^{-1}$ is what gives a unique slope between two points with different first coordinates. Over a ring with zero divisors, the same formulas can fail to give unique solutions, so the construction is not a construction over arbitrary finite coordinate sets. The theorem supplies examples for every prime power order, but it leaves open the much harder question of non-prime-power orders. The finite-field plane is also the geometric version of the affine Latin square construction from Chapter 2, so we next recall the language for a whole family of Latin squares whose superposed ordered pairs distinguish all cells. [definition: Mutually Orthogonal Latin Squares] A collection $L_1,\dots,L_t$ of Latin squares of order $n$ on the same symbol set is mutually orthogonal if, for every pair $L_i,L_j$ with $i \ne j$, the ordered pairs \begin{align*} (L_i(r,c),L_j(r,c)) \end{align*} as $(r,c)$ ranges over all cells occur exactly once each. [/definition] Orthogonality records the same uniqueness condition as the intersection of two non-parallel lines. By choosing two affine directions as row and column directions, every other direction becomes a Latin square, which leads to the central equivalence between affine planes and complete sets of MOLS. [quotetheorem:5747] [citeproof:5747] The number $n-1$ is forced because two of the $n+1$ affine directions have already been used for rows and columns. If fewer Latin squares are present, the construction gives only some of the required parallel classes, so it need not produce an affine plane. Orthogonality is also essential: Latin squares alone control intersections with rows and columns, but without orthogonality two symbol lines from different squares can meet twice or not at all. Concretely, if two Latin squares have the same ordered pair $(a,b)$ in two different cells, then the $a$-symbol line from the first square and the $b$-symbol line from the second square meet in both cells; if an ordered pair never occurs, the corresponding two symbol lines are disjoint. For prime powers, this recovers the finite-field lower bound on MOLS in geometric language, and the order-four case shows how the remaining affine directions become actual squares. [example: Parallel Classes in AG(2,4)] Let $\mathbb F_4=\{0,1,\alpha,\alpha+1\}$, where $\alpha^2=\alpha+1$. The affine plane $AG(2,4)$ has point set $\mathbb F_4^2$, so \begin{align*} |\mathbb F_4^2|=|\mathbb F_4|\cdot |\mathbb F_4|=4\cdot 4=16. \end{align*} For each slope $a\in \mathbb F_4$, the lines in that direction are \begin{align*} L_{a,b}=\{(x,ax+b):x\in \mathbb F_4\}, \qquad b\in \mathbb F_4. \end{align*} For fixed $a$, there are $4$ choices of $b$, so this direction contains $4$ lines. If $(x,y)$ lies on both $L_{a,b}$ and $L_{a,b'}$, then \begin{align*} y=ax+b \quad\text{and}\quad y=ax+b', \end{align*} and subtracting the two equations in $\mathbb F_4$ gives \begin{align*} 0=(ax+b)-(ax+b')=b-b', \end{align*} so $b=b'$. Thus the four lines with fixed slope $a$ are pairwise disjoint. They cover all points because, for any $(x,y)\in \mathbb F_4^2$, the value \begin{align*} b=y-ax \end{align*} is the unique intercept for which $(x,y)\in L_{a,b}$. The vertical direction consists of the four lines \begin{align*} V_c=\{(c,y):y\in \mathbb F_4\}, \qquad c\in \mathbb F_4. \end{align*} If a point lay on both $V_c$ and $V_{c'}$, its first coordinate would be both $c$ and $c'$, so $c=c'$. Also every point $(x,y)$ lies on the unique vertical line $V_x$. Hence the parallel classes are exactly the four slope classes indexed by \begin{align*} 0,\ 1,\ \alpha,\ \alpha+1 \end{align*} together with the vertical class, giving \begin{align*} 4+1=5 \end{align*} parallel classes, each containing $4$ lines. Choose the vertical class as the column class and the slope-$0$ class as the row class. The remaining slope classes $1,\alpha,\alpha+1$ give \begin{align*} 5-2=3 \end{align*} Latin squares of order $4$ by *Affine Planes and MOLS*. Concretely, for slope $a\in\{1,\alpha,\alpha+1\}$, the symbol assigned to the cell $(x,y)$ is the intercept \begin{align*} b=y-ax. \end{align*} If $a\ne a'$ and prescribed symbols $b,b'\in\mathbb F_4$ are given, the equations \begin{align*} y-ax=b, \qquad y-a'x=b' \end{align*} imply \begin{align*} (a-a')x=b'-b. \end{align*} Since $a-a'\ne 0$ in the field $\mathbb F_4$, this has the unique solution \begin{align*} x=(b'-b)(a-a')^{-1}, \end{align*} and then \begin{align*} y=ax+b. \end{align*} Thus each ordered pair of symbols occurs in exactly one cell, so the three remaining directions give $3$ mutually orthogonal Latin squares of order $4$. [/example] ## Projective Planes as Symmetric Designs Why do projective planes belong in a course on block designs? The answer is that their incidence axioms are exactly the axioms of a symmetric balanced incomplete block design with special parameters. Points become treatments, lines become blocks, and unique joining lines become the condition $\lambda=1$. [definition: Symmetric Two Design] A symmetric $2$-$(v,k,\lambda)$ design is a $2$-$(v,k,\lambda)$ design with exactly $v$ blocks. [/definition] Symmetry means that the number of blocks equals the number of points, matching the projective-plane equality $|P|=|L|$. Without symmetry, a $2$-design with $\lambda=1$ need not have any reason for two blocks to meet in exactly one point, so the line-intersection axiom would be missing. The next theorem turns the projective incidence axioms into design parameters and also explains how such a design can be read back as a geometry. [quotetheorem:5748] [citeproof:5748] This equivalence explains why projective planes are central examples in design theory: their geometric axioms are exactly the symmetric $2$-design equations with $\lambda=1$. Symmetry is necessary, since a general $2$-$(v,k,1)$ design controls pairs of points but does not force distinct blocks to meet in one point. The theorem is an equivalence of structures, not an existence theorem; it says that constructing such a symmetric design is as hard as constructing the corresponding projective plane. The design interpretation gives abstract parameters, but it does not by itself produce examples, motivating the finite-field definition below. [definition: Projective Plane Over a Finite Field] Let $q$ be a prime power. The projective plane $PG(2,q)$ has as points the one-dimensional subspaces of $\mathbb F_q^3$ and as lines the two-dimensional subspaces of $\mathbb F_q^3$, with incidence given by containment. [/definition] The vector-space model is the cleanest construction of projective planes. To prove the projective axioms, the required uniqueness statements become dimension statements about subspaces of $\mathbb F_q^3$. [quotetheorem:5749] [citeproof:5749] The vector-space model works because subspace span and intersection give the two projective uniqueness axioms directly. The finite-field condition is again essential for finiteness and for the count of one-dimensional subspaces; over an infinite field the same construction gives a projective plane, but not a finite one. The theorem constructs projective planes for prime power orders only and therefore does not settle whether planes exist in other orders. The smallest projective plane is the order-two case, compact enough to draw and still the standard test example for every definition in this chapter. [example: The Fano Plane PG(2,2)] In $PG(2,2)$, points are one-dimensional subspaces of $\mathbb F_2^3$. Since $\mathbb F_2=\{0,1\}$, the nonzero vectors of $\mathbb F_2^3$ are $(1,0,0)$, $(0,1,0)$, $(0,0,1)$, $(1,1,0)$, $(1,0,1)$, $(0,1,1)$, and $(1,1,1)$. If $v$ is any one of these nonzero vectors, then \begin{align*} \langle v\rangle=\{0\cdot v,1\cdot v\}=\{0,v\}. \end{align*} Thus each one-dimensional subspace contains exactly one nonzero vector, so these seven vectors represent the seven points of $PG(2,2)$. Lines are two-dimensional subspaces of $\mathbb F_2^3$. If $u$ and $v$ are linearly independent, then the subspace they span is \begin{align*} \langle u,v\rangle=\{au+bv:a,b\in\mathbb F_2\}=\{0,u,v,u+v\}. \end{align*} The zero vector is not a projective point, so this projective line contains exactly the three points represented by $u$, $v$, and $u+v$. For example, \begin{align*} \langle (1,0,0),(0,1,0)\rangle=\{(0,0,0),(1,0,0),(0,1,0),(1,1,0)\}. \end{align*} Therefore the corresponding projective line contains the three points represented by $(1,0,0)$, $(0,1,0)$, and $(1,1,0)$. The seven projective lines are represented by the triples $\{(1,0,0),(0,1,0),(1,1,0)\}$, $\{(1,0,0),(0,0,1),(1,0,1)\}$, $\{(0,1,0),(0,0,1),(0,1,1)\}$, $\{(1,0,0),(0,1,1),(1,1,1)\}$, $\{(0,1,0),(1,0,1),(1,1,1)\}$, $\{(0,0,1),(1,1,0),(1,1,1)\}$, and $\{(1,1,0),(1,0,1),(0,1,1)\}$. Hence $PG(2,2)$ has $7$ points and $7$ lines, with $3$ points on each line. Since any two distinct one-dimensional subspaces span a unique two-dimensional subspace, any two points lie on a unique line; this is the Fano plane, viewed as a symmetric $2$-$(7,3,1)$ design. [/example] [illustration:fano-plane-seven-lines] The chapter has now connected the three languages of this part of the course. Latin squares encode affine parallel classes, affine planes become projective planes by adding a line at infinity, and projective planes are symmetric designs with parameters $2$-$(q^2+q+1,q+1,1)$. These same finite geometries also reappear beyond the design-theory setting, especially in finite geometry, error-correcting codes built from incidence matrices, and extremal configurations where controlled intersections are the central constraint. Projective and affine planes provide the richest examples of balanced designs, but they are not the smallest nontrivial ones. The next chapter narrows the focus to Steiner triple systems, where the same pairwise incidence rule becomes the cleanest possible test case for existence and classification. # 6. Steiner Triple Systems and Small Designs This chapter moves from general block designs to the most economical nontrivial Steiner systems: triple systems in which every pair of points lies in exactly one block. The guiding question is how much global structure is forced by the local rule “each pair occurs once”. We focus on necessary arithmetic constraints, small geometric examples, and the first recursive and cyclic constructions that make the existence theorem believable. ## From Balanced Designs to Steiner Systems Balanced incomplete block designs allow repeated pair incidence with parameter $\lambda$. The natural sharpening is to ask for designs where each prescribed small subset is contained in exactly one block, so that the incidence rule determines as much as possible from local data. [definition: Steiner System] A Steiner system $S(t,k,v)$ is a pair $(X,\mathcal B)$ where $X$ is a finite set with $|X|=v$ and $\mathcal B$ is a collection of $k$-element subsets of $X$ such that every $t$-element subset of $X$ is contained in exactly one block $B\in\mathcal B$. [/definition] This definition contains a large family of exact incidence structures, but the first case with both nontrivial constraints and manageable examples is the pair-covering case with triples as blocks. In that case the design can be read as a decomposition of pairs into three-point blocks, which is the smallest setting where the Steiner condition has real combinatorial force. This motivates isolating the pair-and-triple case as a named object for the rest of the chapter. [definition: Steiner Triple System] A Steiner triple system of order $v$, denoted $\operatorname{STS}(v)$, is a Steiner system $S(2,3,v)$. [/definition] Thus an $\operatorname{STS}(v)$ consists of triples, and each unordered pair of points appears in exactly one triple. This is a sparse structure: once two points are chosen, the third point in their block is forced. [example: The Fano Plane Triple System] Let $X=\mathbb F_2^3\setminus\{0\}$, so \begin{align*} |X|=2^3-1=7. \end{align*} For each two-dimensional subspace $U\le \mathbb F_2^3$, take the block $U\setminus\{0\}$. Since a two-dimensional [vector space](/page/Vector%20Space) over $\mathbb F_2$ has $2^2=4$ vectors, each such block has \begin{align*} |U\setminus\{0\}|=4-1=3 \end{align*} points. There are seven two-dimensional subspaces. Indeed, every nonzero linear functional $\ell:\mathbb F_2^3\to\mathbb F_2$ has a two-dimensional kernel, and there are $2^3-1=7$ nonzero linear functionals. If two nonzero functionals have the same kernel, then they differ by a nonzero scalar; over $\mathbb F_2$ that scalar is $1$, so the functionals are equal. Thus the seven kernels give seven distinct two-dimensional subspaces. Now take distinct points $x,y\in X$. Over $\mathbb F_2$, two distinct nonzero vectors are linearly independent: if $x=\lambda y$ with $\lambda\in\mathbb F_2$, then $\lambda\ne 0$, so $\lambda=1$ and $x=y$, a contradiction. Hence $\langle x,y\rangle$ is a two-dimensional subspace, and its block $\langle x,y\rangle\setminus\{0\}$ contains both $x$ and $y$. If another block $U\setminus\{0\}$ contains $x$ and $y$, then $\langle x,y\rangle\subseteq U$; both spaces have dimension $2$, so $U=\langle x,y\rangle$. Therefore every pair of points lies in exactly one block, and these seven triples form an $\operatorname{STS}(7)$, the Fano plane. [/example] This example is the smallest nontrivial triple system. It also shows how finite geometry naturally supplies designs: lines become blocks, and the geometric axiom that two points determine a line becomes the Steiner condition. [remark: Triple Systems as Pair Decompositions] An $\operatorname{STS}(v)$ is the same data as a decomposition of the edge set of the complete graph $K_v$ into edge-disjoint triangles. Each block $\{x,y,z\}$ contributes the three edges $xy$, $xz$, and $yz$, and the condition that each pair appears once says that every edge is used exactly once. [/remark] The graph interpretation is especially useful for divisibility conditions, because it turns the design problem into an exact packing problem for the edges of $K_v$. ## Counting Restrictions on Triple Systems Before constructing triple systems, we should ask which values of $v$ are even possible. The pair condition gives two independent integer constraints: the total number of pairs must be divisible by the number of pairs in a triple, and the number of triples through a fixed point must be integral. [quotetheorem:5750] [citeproof:5750] The theorem rules out many orders at once, including $v=4,5,6,8,10,11,12$. The two integrality hypotheses are genuinely different: $v=5$ has integral replication number $r=2$ but would require $b=10/3$ blocks, while $v=4$ already fails because a point would have to lie in $3/2$ blocks. These obstructions are only necessary conditions, so the theorem does not by itself build a single block or prove that an admissible order such as $v=13$ can actually occur. It leaves a sharper existence question: are there any hidden restrictions beyond these divisibility conditions, or does the elementary arithmetic already capture the full obstruction? The classical answer is one of the central starting points of the theory. [quotetheorem:5751] Kirkman's theorem is not proved in this chapter. It is an existence theorem, not a uniqueness theorem: for larger admissible orders there may be many non-isomorphic triple systems, and the statement does not choose a canonical one. It also does not provide a compact block list or an efficient algorithm for a given value of $v$. Later existence theorems in design theory give systematic methods for turning the necessary congruence conditions into constructions, while the small examples below show how such constructions can look in concrete cases. [example: Checking Small Orders] Using *[Divisibility Conditions for Steiner Triple Systems](/theorems/5750)*, any $\operatorname{STS}(v)$ must have \begin{align*} b=\frac{v(v-1)}{6},\qquad r=\frac{v-1}{2}. \end{align*} For $v=7$, we have \begin{align*} 7=6\cdot 1+1, \end{align*} so the congruence condition permits an $\operatorname{STS}(7)$. Its parameters would be \begin{align*} b=\frac{7(7-1)}{6}=\frac{7\cdot 6}{6}=7,\qquad r=\frac{7-1}{2}=\frac{6}{2}=3. \end{align*} The Fano plane example has exactly seven triples and each point lies on three of them, so it realizes these parameters. For $v=9$, we have \begin{align*} 9=6\cdot 1+3, \end{align*} so the congruence condition also permits an $\operatorname{STS}(9)$. The required block count and replication number are \begin{align*} b=\frac{9(9-1)}{6}=\frac{9\cdot 8}{6}=\frac{72}{6}=12,\qquad r=\frac{9-1}{2}=\frac{8}{2}=4. \end{align*} For $v=13$, we have \begin{align*} 13=6\cdot 2+1, \end{align*} and the corresponding parameters are \begin{align*} b=\frac{13(13-1)}{6}=\frac{13\cdot 12}{6}=13\cdot 2=26,\qquad r=\frac{13-1}{2}=\frac{12}{2}=6. \end{align*} Thus the later cyclic construction for order $13$ must produce $26$ triples, with each point occurring in exactly $6$ triples. [/example] The parameter formulas are not merely bookkeeping. They tell us what any proposed construction must deliver, and they often reveal mistakes in candidate block lists. ## The Affine Plane Example of Order Nine The next small admissible order after $7$ is $9$. A direct search for twelve triples is possible, but the better question is whether the finite-geometric construction behind the Fano plane has an affine analogue. [example: Triple System from the Affine Plane AG(2,3)] Let $X=\mathbb F_3^2$, so \begin{align*} |X|=|\mathbb F_3|^2=3^2=9. \end{align*} For $a\in\mathbb F_3^2$ and $v\in\mathbb F_3^2\setminus\{0\}$, define the affine line with base point $a$ and direction $v$ by \begin{align*} L(a,v)=\{a+tv:t\in\mathbb F_3\}. \end{align*} This set has three points: if $a+t_1v=a+t_2v$, then \begin{align*} (t_1-t_2)v=0. \end{align*} Since $v\ne 0$ and $\mathbb F_3$ is a field, this forces $t_1-t_2=0$, hence $t_1=t_2$. Thus the three values $t=0,1,2$ give three distinct points. We now check that every pair of distinct points lies on exactly one such line. Let $p,q\in X$ with $p\ne q$. Then $q-p\ne 0$, so \begin{align*} L(p,q-p)=\{p+t(q-p):t\in\mathbb F_3\} \end{align*} contains $p$, because $p+0(q-p)=p$, and contains $q$, because \begin{align*} p+1(q-p)=q. \end{align*} For uniqueness, suppose $p,q\in L(a,v)$. Then there are $s,t\in\mathbb F_3$ such that \begin{align*} p=a+sv,\qquad q=a+tv. \end{align*} Since $p\ne q$, we have $s\ne t$, and \begin{align*} q-p=(a+tv)-(a+sv)=(t-s)v. \end{align*} Because $t-s\ne 0$ in $\mathbb F_3$, the scalar $(t-s)^{-1}$ exists, so \begin{align*} v=(t-s)^{-1}(q-p). \end{align*} Hence the direction of any line through $p$ and $q$ is a nonzero scalar multiple of $q-p$, and such scalar multiples define the same point set: \begin{align*} \{p+u((t-s)^{-1}(q-p)):u\in\mathbb F_3\} = \{p+w(q-p):w\in\mathbb F_3\}, \end{align*} where $w=u(t-s)^{-1}$. Therefore $p$ and $q$ lie on exactly one affine line. It remains to count the lines. There are $9$ choices for $a$ and $8$ choices for nonzero $v$, giving $9\cdot 8=72$ descriptions $L(a,v)$. Each actual line has $3$ choices for its base point, and its direction may be either of the two nonzero scalar multiples of a fixed direction, since $\mathbb F_3^\times=\{1,2\}$. Thus each line is counted $3\cdot 2=6$ times, so the number of distinct lines is \begin{align*} \frac{72}{6}=12. \end{align*} The twelve affine lines are therefore twelve triples on nine points, and the uniqueness argument shows that each unordered pair of points appears in exactly one triple. Hence they form an $\operatorname{STS}(9)$. [/example] This construction is best viewed as an affine geometry design rather than an isolated list of triples. The four parallel classes of lines each partition the nine points, and together they cover every pair once. [remark: Resolvability in the Order Nine Example] The $\operatorname{STS}(9)$ from $\operatorname{AG}(2,3)$ is resolvable: its twelve blocks split into four classes of three disjoint blocks, each class covering all nine points. This additional structure is not required in a Steiner triple system, but it is important in scheduling interpretations and in later constructions of Kirkman triple systems. [/remark] The affine plane example suggests a larger pattern: if an incidence geometry has lines of size $3$ and two points determine one line, then its lines form a triple system. The obstruction is that most finite affine and projective planes have lines larger than $3$. ## Recursive Constructions Small examples become more useful when they can be enlarged. The general problem is to turn one or more known triple systems into a new one while preserving the exact pair-covering rule. [quotetheorem:5752] [citeproof:5752] The construction has a useful interpretation: every old point is split into two copies, the new point $\infty$ ties the copies together, and every old triple is replaced by four parity-compatible triples. The hypothesis that the original design is already an $\operatorname{STS}(v)$ is essential, because pairs with distinct first coordinates are covered by referring back to the unique old block containing those first coordinates. If the old block list missed or repeated a pair, the same defect would be copied into the doubled construction. The construction is also only a partial existence machine: it sends $v$ to $2v+1$, so starting from $7$ reaches $15,31,63,\dots$ but does not explain the admissible order $13$. [example: From Seven to Fifteen] Starting with the Fano plane $\operatorname{STS}(7)$, apply *Doubling Construction for Triple Systems* to the point set $X$ of the Fano plane. The new point set is \begin{align*} (X\times \mathbb F_2)\cup\{\infty\}, \end{align*} so its size is \begin{align*} |X\times \mathbb F_2|+1=|X|\cdot |\mathbb F_2|+1=7\cdot 2+1=14+1=15. \end{align*} Each Fano block $\{a,b,c\}$ produces the triples \begin{align*} \{(a,0),(b,0),(c,0)\},\quad \{(a,0),(b,1),(c,1)\},\quad \{(a,1),(b,0),(c,1)\},\quad \{(a,1),(b,1),(c,0)\}, \end{align*} because these are exactly the four choices $(i,j,k)\in\mathbb F_2^3$ with \begin{align*} i+j+k=0. \end{align*} The Fano plane has $7$ blocks, so these contribute \begin{align*} 7\cdot 4=28 \end{align*} new triples. The construction also adds one vertical triple \begin{align*} \{\infty,(x,0),(x,1)\} \end{align*} for each $x\in X$, and there are \begin{align*} |X|=7 \end{align*} such triples. Hence the total number of blocks is \begin{align*} 28+7=35. \end{align*} For an $\operatorname{STS}(15)$, the required block count from *Divisibility Conditions for Steiner Triple Systems* is \begin{align*} \frac{15(15-1)}{6} = \frac{15\cdot 14}{6} = \frac{210}{6} = 35. \end{align*} Thus the doubled Fano plane has the correct order and block count, and the doubling construction supplies the exact pair-covering property, so it is an $\operatorname{STS}(15)$. [/example] Recursive constructions are useful because they build infinite families from small seeds. They do not by themselves prove Kirkman's theorem, but they explain why the admissible orders are not isolated accidents. ## Cyclic Steiner Triple Systems A different construction asks for symmetry from the outset. Instead of listing all blocks independently, we try to generate them from a few starter blocks by adding a fixed element of a cyclic group. [definition: Cyclic Steiner Triple System] A cyclic $\operatorname{STS}(v)$ is an $\operatorname{STS}(v)$ on the point set $\mathbb Z/v\mathbb Z$ whose block set is invariant under the translation $x\mapsto x+1$. [/definition] This definition turns a long block list into a short list of starter blocks plus all their translates. To decide whether the translated blocks cover pairs once, we need a criterion that records exactly which pair-differences occur inside the starters. [definition: Difference Family for a Cyclic Triple System] A collection of triples $\mathcal S$ in $\mathbb Z/v\mathbb Z$ is a cyclic difference family for an $\operatorname{STS}(v)$ if the multiset of nonzero differences \begin{align*} \{a-b: a,b\in S,\ a\ne b,\ S\in\mathcal S\} \end{align*} contains each nonzero element of $\mathbb Z/v\mathbb Z$ exactly once. [/definition] The definition records the exact data needed to control translated blocks, but one still has to justify why differences are the right data. A pair in a translate of a starter triple is determined by its modular difference, while translating the block changes the pair's location without changing that difference. Thus the possible failure of the construction is exactly a duplicate difference, which would cover some pair twice, or a missing difference, which would leave some pair uncovered. [quotetheorem:5753] [citeproof:5753] This criterion reduces a design construction to modular arithmetic, but the exact ordered-difference condition is doing real work. If a nonzero residue occurs twice as an ordered difference, then some translated pair is covered by two blocks; if a residue is missing, then the corresponding translated pair is not covered at all. The word ``ordered'' matters because the pair $\{x,y\}$ may be viewed through the differences $y-x$ and $x-y$, and both orientations must be accounted for consistently in the starter data. The block count is also delicate: the number of starter triples must be $(v-1)/6$ when no starter block has a nontrivial stabiliser under translation, while stabilised starters require separate orbit-size bookkeeping. [example: A Cyclic STS(13)] Work in $\mathbb Z/13\mathbb Z$, and take the starter triples \begin{align*} S_1=\{0,1,4\},\qquad S_2=\{0,2,7\}. \end{align*} For $S_1$, the ordered differences are $1-0=1$, $0-1=-1\equiv 12\pmod{13}$, $4-0=4$, $0-4=-4\equiv 9\pmod{13}$, $4-1=3$, and $1-4=-3\equiv 10\pmod{13}$. Thus $S_1$ contributes \begin{align*} \{1,3,4,9,10,12\}. \end{align*} For $S_2$, the ordered differences are $2-0=2$, $0-2=-2\equiv 11\pmod{13}$, $7-0=7$, $0-7=-7\equiv 6\pmod{13}$, $7-2=5$, and $2-7=-5\equiv 8\pmod{13}$. Thus $S_2$ contributes \begin{align*} \{2,5,6,7,8,11\}. \end{align*} Combining the two lists gives \begin{align*} \{1,2,3,4,5,6,7,8,9,10,11,12\}, \end{align*} so every nonzero residue modulo $13$ occurs exactly once as an ordered difference among the two starter triples. Now translate each starter by every $t\in\mathbb Z/13\mathbb Z$. If $S_i+t=S_i$ for some nonzero $t$, then applying the same translation repeatedly gives \begin{align*} S_i=S_i+t=S_i+2t=\cdots=S_i+12t. \end{align*} Since $13$ is prime and $t\ne 0$, the residues $0,t,2t,\ldots,12t$ are all distinct modulo $13$, so the translation $x\mapsto x+t$ has an orbit of size $13$, impossible inside a three-point set. Hence each starter has $13$ distinct translates. The two translation orbits are disjoint, because translation preserves ordered differences, while residue $1$ occurs among the ordered differences of $S_1$ and does not occur among those of $S_2$. Therefore the construction gives \begin{align*} 13+13=26 \end{align*} distinct triples. By *Difference Family Criterion*, these translates cover every unordered pair of points exactly once, so they form a cyclic $\operatorname{STS}(13)$. [/example] The cyclic construction is compact: two starter triples encode the whole order-thirteen system. It also gives a practical way to check the design, since difference coverage is shorter than pair-by-pair verification. ## Skolem-Type Constructions in Basic Cases The congruence condition splits admissible orders into $v=6n+1$ and $v=6n+3$. Skolem-type constructions give explicit block recipes for these families by arranging pairs of integers so that prescribed differences occur. [definition: Skolem Sequence] A Skolem sequence of order $n$ is a sequence $(s_1,\dots,s_{2n})$ in which each integer $i\in\{1,\dots,n\}$ occurs exactly twice, say in positions $a_i<b_i$, and satisfies $b_i-a_i=i$. [/definition] Skolem sequences turn difference information into block information, because the two positions of each symbol prescribe a controlled separation. The next question is not how to use such a sequence, but when this source of controlled separations exists at all. The answer is an arithmetic criterion, and it is the input that makes Skolem-style Steiner triple constructions possible. [quotetheorem:5754] This theorem is quoted as a standard ingredient rather than proved in this course. Its relevance here is that the congruence classes match part of the arithmetic needed for explicit Steiner triple constructions. [example: A Skolem Sequence of Order Four] Consider the sequence \begin{align*} (s_1,s_2,s_3,s_4,s_5,s_6,s_7,s_8) = (4,2,3,2,4,3,1,1). \end{align*} We verify that it is a Skolem sequence of order $4$ by checking the two required conditions for each value $i\in\{1,2,3,4\}$. The entries equal to $1$ occur at positions $7$ and $8$, and \begin{align*} 8-7=1. \end{align*} The entries equal to $2$ occur at positions $2$ and $4$, and \begin{align*} 4-2=2. \end{align*} The entries equal to $3$ occur at positions $3$ and $6$, and \begin{align*} 6-3=3. \end{align*} The entries equal to $4$ occur at positions $1$ and $5$, and \begin{align*} 5-1=4. \end{align*} Thus each integer $i\in\{1,2,3,4\}$ occurs exactly twice, and the distance between its two occurrences is exactly $i$. This list therefore encodes the four separations $1,2,3,4$ in one sequence. [/example] The actual Skolem construction of Steiner triple systems adds modular placement rules to this sequence data. At the level of this course, the important point is that difference control and pair coverage are the same problem in two languages. [explanation: Skolem Data as a Construction Template] A Skolem sequence should not be read here as a complete theorem producing all Steiner triple systems by itself. The sequence supplies controlled differences: the two occurrences of $i$ in positions $a_i<b_i$ encode the separation $i$, and this is exactly the kind of information needed for cyclic starter blocks. To turn that data into an $\operatorname{STS}(v)$, one must additionally specify the point set, the starter triples, and the treatment of the exceptional congruence classes where hooked Skolem sequences are used. For example, in the cyclic setting the verification has the same shape as the difference family criterion: the proposed starters must produce every nonzero residue exactly once as an ordered difference. If a repeated symbol placement leads to a repeated residue, some pair will be covered twice; if a required residue is absent, some pair will not be covered. Thus Skolem sequences are best understood in these notes as an organising device for explicit constructions, while the precise construction theorem belongs to the later, more technical existence theory. [/explanation] ## What the Small Designs Teach The small Steiner triple systems in this chapter show three complementary methods. The Fano plane and $\operatorname{AG}(2,3)$ come from finite geometry, the doubling construction uses doubling and parity to enlarge known systems, and cyclic constructions compress pair coverage into modular differences. [explanation: Three Ways to Control Pairs] A geometric design controls pairs by incidence axioms: two points determine a unique line. A recursive construction controls pairs by splitting them into types and assigning each type to an existing design or to parity data. A cyclic construction controls pairs by differences, replacing a long pair check with a short modular calculation. These viewpoints recur throughout combinatorial design theory. Existence theorems often combine them: local arithmetic conditions suggest the parameters, small base cases supply seeds, and recursive or algebraic machinery builds large designs without losing the exact incidence rule. [/explanation] Steiner triple systems show how local pair coverage can force strong global organisation, and now we add a scheduling constraint on top of that structure. Resolvability asks not just for blocks, but for a partition into parallel classes, so the design can be arranged in rounds. # 7. Resolvable Designs and Scheduling A balanced block design controls how often pairs occur together, but many applications also ask for a second kind of organisation: the blocks should be schedulable in rounds. In this chapter the new object is a partition of the block set into parallel classes, each of which covers every point exactly once. This turns incidence theory into a timetable: pupils are grouped for several days, matches are arranged in rounds, and experiments are split into complete replicates. ## Parallel Classes in Balanced Designs The first scheduling question is whether the blocks of a design can be grouped so that each group is a full partition of the point set. For a BIBD, written here as a $2$-$(v,k,\lambda)$ design as in Chapter 3, this imposes arithmetic conditions stronger than the ordinary divisibility conditions. [definition: Parallel Class] Let $(X,\mathcal B)$ be a block design whose blocks all have size $k$. A parallel class is a subset $\mathcal P\subseteq \mathcal B$ such that every point of $X$ lies in exactly one block of $\mathcal P$. [/definition] A parallel class is one complete round of the design. Since its blocks are disjoint and cover $X$, it is possible only when $k$ divides $v$. [example: A Parallel Class on Six Points] Let $X=\{1,2,3,4,5,6\}$ and let \begin{align*} \mathcal P=\bigl\{\{1,2\},\{3,4\},\{5,6\}\bigr\}. \end{align*} Each block in $\mathcal P$ has size $2$. The blocks are pairwise disjoint, because \begin{align*} \{1,2\}\cap\{3,4\}=\varnothing. \end{align*} Also, \begin{align*} \{1,2\}\cap\{5,6\}=\varnothing. \end{align*} Finally, \begin{align*} \{3,4\}\cap\{5,6\}=\varnothing. \end{align*} Their union is the whole point set: \begin{align*} \{1,2\}\cup\{3,4\}\cup\{5,6\}=\{1,2,3,4,5,6\}=X. \end{align*} Thus every point of $X$ lies in exactly one block of $\mathcal P$, so $\mathcal P$ is a parallel class of $2$-subsets of $X$. If the blocks had size $4$ instead, a parallel class on the same point set would have to partition $6$ points into disjoint $4$-element blocks. If there were $m$ such blocks, counting the points in the disjoint union would give \begin{align*} 4m=6. \end{align*} This equation has no integer solution, since \begin{align*} m=\frac{6}{4}=\frac{3}{2}. \end{align*} Therefore no parallel class of $4$-subsets of $X$ exists. The example shows both a valid round when $2\mid 6$ and the divisibility obstruction when $4\nmid 6$. [/example] A single parallel class solves one round of a scheduling problem, but a design usually contains many more blocks than one round can hold. The next question is whether every block can be placed into some round without breaking the partition condition. This is the extra structure needed for a design to become a complete schedule. [definition: Resolvable Design] A block design $(X,\mathcal B)$ is resolvable if $\mathcal B$ can be partitioned into parallel classes. [/definition] A resolution turns the block set into a collection of equal-sized rounds, so the BIBD parameters should determine how many rounds are available. The previous definition is structural, but before building examples we need a parameter test: if the proposed timetable has the wrong number of blocks per round or the wrong number of rounds through each point, no resolution can exist. [quotetheorem:5755] [citeproof:5755] These conditions are only necessary. The condition $k\mid v$ is local to a single round: without it, even one parallel class cannot partition the point set. The equality between the number of classes and $r$ is global: every point must appear once in every round, so a proposed resolution has no freedom to change the number of time slots. Passing these counts still does not construct a resolution. For example, there are Steiner triple systems on $15$ points whose parameters satisfy all the displayed divisibility conditions, but whose triples cannot be partitioned into five-triple parallel classes. The counts remove the first obstruction; they do not decide whether the block set has the extra partition structure. [example: Parameters Passing the Divisibility Test] For a Steiner triple system, the parameters are $k=3$ and $\lambda=1$. The replication formula for a resolvable $2$-$(v,k,\lambda)$ design gives \begin{align*} r=\frac{\lambda(v-1)}{k-1}=\frac{1\cdot(v-1)}{3-1}=\frac{v-1}{2}. \end{align*} A resolution also requires each parallel class to partition the $v$ points into triples, so each class would contain $v/3$ triples and therefore \begin{align*} 3\mid v. \end{align*} The ordinary congruence condition for a Steiner triple system is \begin{align*} v\equiv 1 \text{ or } 3 \pmod 6. \end{align*} The additional condition $3\mid v$ says \begin{align*} v\equiv 0 \text{ or } 3 \pmod 6. \end{align*} The only residue class common to these two lists is \begin{align*} \{1,3\}\cap\{0,3\}=\{3\}. \end{align*} Thus a resolvable Steiner triple system can only have \begin{align*} v\equiv 3\pmod 6. \end{align*} For $v=15$, we have \begin{align*} 15=6\cdot 2+3, \end{align*} so $15\equiv 3\pmod 6$. The required replication number would be \begin{align*} r=\frac{15-1}{2}=\frac{14}{2}=7, \end{align*} and each parallel class would contain \begin{align*} \frac{v}{k}=\frac{15}{3}=5 \end{align*} triples. Thus $v=15$ passes the parameter test, and after $v=3$ and $v=9$ it is the next candidate in the congruence class $v\equiv 3\pmod 6$. This conclusion is not yet a timetable: it says only that the arithmetic obstruction has disappeared, not that the triples can actually be arranged into parallel classes. [/example] ## Kirkman Triple Systems The central historical problem is to arrange triples so that every pair meets once overall and every day partitions the whole set into triples. This is the resolvable form of a Steiner triple system. [definition: Kirkman Triple System] A Kirkman triple system of order $v$ is a resolvable $2$-$(v,3,1)$ design. [/definition] Thus a Kirkman triple system has $v$ points, blocks of size $3$, every pair of points occurs in exactly one block, and the blocks are arranged into parallel classes. The parameters force $v\equiv 3\pmod 6$, and the following existence theorem says that this condition is also sufficient. [quotetheorem:5756] The necessity follows from the previous parameter count and the ordinary divisibility conditions for Steiner triple systems. For instance, an STS$(7)$ exists, but it cannot be resolvable because $3\nmid 7$, so there is no way for a single day to partition the seven points into triples. The sufficiency is a deeper existence theorem in design theory; in this course it is quoted rather than proved, because its standard proofs use recursive constructions beyond the present chapter. The theorem is special to triples with $\lambda=1$: it is not a general existence criterion for resolvable $2$-$(v,k,\lambda)$ designs. [example: The Schoolgirl Problem] The classical schoolgirl problem asks for $15$ schoolgirls to walk in $5$ rows of $3$ on each of $7$ days, with no pair walking together twice. In design language, the schoolgirls are the $v=15$ points, each row is a block of size $k=3$, each day must be a parallel class, and the condition on pairs is $\lambda=1$. On one day, the $5$ rows of $3$ account for \begin{align*} 5\cdot 3=15 \end{align*} schoolgirl appearances, so that day covers all $15$ schoolgirls exactly once when the rows are disjoint. Equivalently, the number of triples in each parallel class is \begin{align*} \frac{v}{k}=\frac{15}{3}=5. \end{align*} For a Steiner triple system, the replication number is \begin{align*} r=\frac{\lambda(v-1)}{k-1} =\frac{1\cdot(15-1)}{3-1} =\frac{14}{2} =7. \end{align*} Thus each schoolgirl must appear in $7$ triples overall, and in a resolution this means there are $7$ parallel classes, one for each day. A resolvable STS$(15)$ therefore has exactly the required form: $7$ days, $5$ disjoint triples per day, every schoolgirl used once per day, and every pair of schoolgirls appearing together in exactly one triple across the whole week. [/example] The schoolgirl formulation is useful because it separates the two incidence requirements. The pair condition says no pair repeats across the entire week; the parallel-class condition says that every girl appears once each day. [remark: Scheduling Interpretation] In a resolvable $2$-$(v,k,\lambda)$ design, points are participants, blocks are groups, and parallel classes are time slots. The BIBD condition controls fairness across the whole schedule, while the resolution controls feasibility within each time slot. [/remark] ## Latin Squares and Complete Round-Robin Schedules Resolvable designs also appear when the blocks have size $2$. The natural object is a decomposition of the edges of a complete graph into perfect matchings, which is the graph-theoretic version of a resolution. [definition: One-Factor] Let $G$ be a graph with vertex set $V(G)$. A one-factor of $G$ is a set of pairwise disjoint edges that covers every vertex of $G$. [/definition] A one-factor is a parallel class for a block design whose blocks are edges. To schedule a round-robin tournament, each round should be a one-factor: every player plays exactly once. A complete tournament also requires every possible match to be used, so we need a way to decompose the whole edge set into such rounds. [definition: One-Factorization] A one-factorization of a graph $G$ is a partition of $E(G)$ into one-factors. [/definition] This definition packages a proposed round-robin schedule as a mathematical object: the one-factors are rounds and their union is the full list of matches. The remaining problem is existence. For complete graphs of even order, the next theorem is needed to show that the desired schedule can always be built and that it has the minimum possible number of rounds. [quotetheorem:5757] [citeproof:5757] This theorem is the scheduling engine for an even number of players. Since $K_{2n}$ has $2n-1$ edges incident with each vertex, each player must play in $2n-1$ rounds, and the theorem supplies exactly that many rounds. The even-order hypothesis is essential for one-factors: a one-factor covers vertices in pairs, so no graph on an odd number of vertices can have a one-factor covering every vertex. The theorem also concerns complete graphs only; arbitrary graphs and schedules with forbidden matches require separate existence conditions. [illustration:cyclic-one-factorization-k6] [example: Round-Robin Schedule for Six Players] Let the players be $\infty,0,1,2,3,4$, with arithmetic modulo $5$ on the finite labels, and write $ab$ for the match $\{a,b\}$. The five proposed rounds are \begin{align*} R_0=\{\infty0,14,23\}. \end{align*} \begin{align*} R_1=\{\infty1,20,34\}. \end{align*} \begin{align*} R_2=\{\infty2,31,40\}. \end{align*} \begin{align*} R_3=\{\infty3,42,01\}. \end{align*} \begin{align*} R_4=\{\infty4,03,12\}. \end{align*} Each round contains three disjoint matches and covers all six players. Explicitly, \begin{align*} \{\infty,0\}\cup\{1,4\}\cup\{2,3\}=\{\infty,0,1,2,3,4\}. \end{align*} \begin{align*} \{\infty,1\}\cup\{2,0\}\cup\{3,4\}=\{\infty,0,1,2,3,4\}. \end{align*} \begin{align*} \{\infty,2\}\cup\{3,1\}\cup\{4,0\}=\{\infty,0,1,2,3,4\}. \end{align*} \begin{align*} \{\infty,3\}\cup\{4,2\}\cup\{0,1\}=\{\infty,0,1,2,3,4\}. \end{align*} \begin{align*} \{\infty,4\}\cup\{0,3\}\cup\{1,2\}=\{\infty,0,1,2,3,4\}. \end{align*} Thus every player appears exactly once in each round. The matches involving $\infty$ are \begin{align*} \infty0,\ \infty1,\ \infty2,\ \infty3,\ \infty4, \end{align*} so each finite player meets $\infty$ exactly once. The finite matches appearing in the schedule are \begin{align*} 14,\ 23,\ 20,\ 34,\ 31,\ 40,\ 42,\ 01,\ 03,\ 12. \end{align*} Writing each finite match in increasing order gives \begin{align*} 14,\ 23,\ 02,\ 34,\ 13,\ 04,\ 24,\ 01,\ 03,\ 12. \end{align*} Reordering this list gives \begin{align*} 01,\ 02,\ 03,\ 04,\ 12,\ 13,\ 14,\ 23,\ 24,\ 34, \end{align*} which is exactly the set of all $\binom{5}{2}=10$ pairs among $0,1,2,3,4$. Together with the five matches involving $\infty$, this accounts for \begin{align*} 5+10=15=\binom{6}{2} \end{align*} matches, the total number of pairs of six players. Therefore the displayed rounds form a complete round-robin schedule: every player plays once per round, and every pair of players meets exactly once across the five rounds. [/example] Latin squares enter because a round-robin table is a structured array recording opponents or rounds. For odd order, Latin squares give cyclic schedules after adding a bye; for even order, the one-factorization above can be displayed as a Latin-style array whose rows are players and whose columns are rounds. [example: Latin Square View of Cyclic Opponents] On the group $\mathbb Z/5\mathbb Z$, define $L(x,y)=x+y$. For a fixed row $x$, if two entries in that row are equal, then \begin{align*} x+y_1=x+y_2. \end{align*} Adding $-x$ to both sides in $\mathbb Z/5\mathbb Z$ gives \begin{align*} (-x)+(x+y_1)=(-x)+(x+y_2). \end{align*} By associativity and the inverse law, this becomes \begin{align*} ((-x)+x)+y_1=((-x)+x)+y_2. \end{align*} Since $(-x)+x=0$, we get \begin{align*} 0+y_1=0+y_2, \end{align*} and therefore \begin{align*} y_1=y_2. \end{align*} Thus no symbol repeats in the row. Since the row has five entries and $\mathbb Z/5\mathbb Z$ has five elements, each symbol occurs exactly once in that row. The same cancellation argument works in a fixed column: from \begin{align*} x_1+y=x_2+y \end{align*} we add $-y$ to both sides and obtain \begin{align*} x_1=x_2. \end{align*} Thus $L$ is a Latin square. Now interpret the column value $y$ as a round parameter. In round $y$, pair two finite players $x$ and $x'$ when \begin{align*} x+x'=y. \end{align*} Solving for $x'$ in $\mathbb Z/5\mathbb Z$ gives \begin{align*} x'=y-x. \end{align*} This rule pairs $x$ with itself exactly when \begin{align*} x'=x. \end{align*} Substituting $x'=y-x$ gives \begin{align*} y-x=x. \end{align*} Adding $x$ to both sides gives \begin{align*} y=2x. \end{align*} Since $2\cdot 3=6\equiv 1\pmod 5$, the inverse of $2$ in $\mathbb Z/5\mathbb Z$ is $3$. Multiplying $y=2x$ by $3$ gives \begin{align*} 3y=3(2x). \end{align*} By associativity, \begin{align*} 3(2x)=(3\cdot 2)x=6x\equiv x\pmod 5, \end{align*} so the unique self-paired player is \begin{align*} x=3y. \end{align*} This player is the bye in round $y$. Add one extra player $\infty$ and pair $\infty$ with the bye. If we write $y=2t$, then the bye is \begin{align*} 3y=3(2t)=6t\equiv t\pmod 5, \end{align*} so $\infty$ is paired with $t$. The remaining finite players are paired by \begin{align*} x+x'=2t. \end{align*} For $i=1$, the pair is $t+1$ with $t-1$, because \begin{align*} (t+1)+(t-1)=2t. \end{align*} For $i=2$, the pair is $t+2$ with $t-2$, because \begin{align*} (t+2)+(t-2)=2t. \end{align*} Thus round $t$ is \begin{align*} \{\infty t,\ (t+1)(t-1),\ (t+2)(t-2)\}, \end{align*} with arithmetic modulo $5$. As $t$ runs through $0,1,2,3,4$, these are exactly the five cyclic rounds for $K_6$: each round covers all six players once, and together the five rounds schedule every pair of players exactly once. [/example] The same theme connects the first chapter of the course with the block-design chapters: Latin squares organise symbols in arrays, while resolutions organise blocks in rounds. In both settings the main constraint is that local uniqueness must coexist with a global partition condition. ## Resolutions as Design-Theoretic Schedules The final scheduling problem is not just to choose good blocks, but to decide whether those blocks can be divided into usable time slots. A BIBD can have the correct pair counts while still failing to provide a timetable, because the incidence axioms do not say that the blocks split into partitions of the point set. Thus a resolution is extra structure on top of a design, not merely a convenient listing. Two designs can have the same BIBD parameters while only one admits a useful resolution, and different resolutions of the same block set can encode different schedules. [definition: Resolution] Let $(X,\mathcal B)$ be a resolvable design. A resolution of $(X,\mathcal B)$ is a partition \begin{align*} \mathcal B=\mathcal P_1\cup\cdots\cup\mathcal P_s \end{align*} where each $\mathcal P_i$ is a parallel class and the classes are pairwise disjoint as sets of blocks. [/definition] The notation makes the scheduling content explicit: $s$ is the number of time slots. In a resolvable BIBD, the theorem above identifies $s$ with the replication number $r$. [example: Resolvable Pair Designs] Let $V$ be the vertex set of $K_{2n}$, so $|V|=2n$. Use the edges of $K_{2n}$ as blocks. Each block has size $2$, and for any two distinct vertices $x,y\in V$, the complete graph contains exactly one edge joining them, namely $\{x,y\}$. Hence these blocks form a $2$-$(2n,2,1)$ design. A one-factor of $K_{2n}$ is a set of pairwise disjoint edges covering every vertex of $V$, so it is exactly a parallel class for this block design: every point lies in exactly one block of the class. A one-factorization partitions the whole edge set $E(K_{2n})$ into one-factors, and since the blocks of the design are precisely the edges of $K_{2n}$, this is exactly a resolution of the $2$-$(2n,2,1)$ design. Here the parameters are $v=2n$, $k=2$, and $\lambda=1$. The replication formula from *Necessary Conditions for Resolvable BIBDs* gives \begin{align*} r=\frac{\lambda(v-1)}{k-1}. \end{align*} Substituting $v=2n$, $k=2$, and $\lambda=1$ gives \begin{align*} r=\frac{1\cdot(2n-1)}{2-1}. \end{align*} Since $2-1=1$, this becomes \begin{align*} r=\frac{2n-1}{1}=2n-1. \end{align*} Thus a resolution has $2n-1$ parallel classes. In tournament language, these are the $2n-1$ rounds needed for every one of the $2n$ players to play every other player exactly once. [/example] Resolvable scheduling problems often begin with the same checklist. First verify the BIBD counting equations, then check that $k\mid v$, and then search for a construction or an existence theorem. The examples in this chapter show two model outcomes: Kirkman triple systems require a deep existence theorem, while complete round-robin schedules follow from an elementary cyclic construction. Resolvable designs show how blocks can be grouped into coherent rounds, and cyclic methods give an efficient way to build such patterns. The next chapter turns that symmetry into an arithmetic construction, using difference sets to encode incidence in a single modular pattern. # 8. Difference Sets and Cyclic Designs This chapter continues the course by adding an algebraic construction method to the counting methods of Chapters 3 and 4 and the geometric methods of Chapter 5. The standing prerequisites are the parameters of a balanced incomplete block design, the interpretation of $\lambda$ as a pair-counting constant, and basic finite abelian groups, especially residue groups $\mathbb{Z}/v\mathbb{Z}$. The guiding question in this chapter is whether the additive structure of a finite group can generate an entire incidence structure from a small list of base blocks. Difference sets and difference families answer this question by turning pair incidence into a uniform difference count. ## Difference Families in Abelian Groups Suppose a finite abelian group $G$ is available as a set of labels for points. The first problem is to encode pairwise balance using group subtraction, so that the condition on all ordered pairs of points is replaced by a condition on differences inside blocks. The abelian hypothesis keeps left and right translation from diverging and lets the same additive notation describe both the base blocks and their translates. In a nonabelian group, the ordered quotients $xy^{-1}$ and $x^{-1}y$ lead to different bookkeeping, so the direct additive argument below would need separate left-right conventions. [definition: Difference Multiset] Let $G$ be a finite abelian group and let $B \subset G$. The difference multiset of $B$ is the multiset \begin{align*} \Delta B = \{x-y : x,y \in B,\ x \ne y\}. \end{align*} [/definition] The multiplicity of an element $g \in G$ in $\Delta B$ counts the ordered pairs of distinct elements of $B$ separated by $g$. This ordered convention matches the ordered-pair count in a balanced incomplete block design, so a small difference calculation can certify many pair-incidence conditions at once. [example: Differences Of A Three-Point Subset] In $G=\mathbb{Z}/7\mathbb{Z}$, take $B=\{0,1,3\}$. The ordered pairs of distinct elements of $B$ give the following differences modulo $7$: \begin{align*} 1-0\equiv 1,\quad 3-0\equiv 3,\quad 0-1\equiv -1\equiv 6. \end{align*} The remaining three ordered pairs give \begin{align*} 3-1\equiv 2,\quad 0-3\equiv -3\equiv 4,\quad 1-3\equiv -2\equiv 5. \end{align*} Thus, with multiplicities counted, \begin{align*} \Delta B=\{1,3,6,2,4,5\}. \end{align*} These are exactly the six nonzero residues modulo $7$, each appearing once. Therefore $B$ is a $(7,3,1)$ difference set in $\mathbb{Z}/7\mathbb{Z}$, and this uniform difference count is the arithmetic certificate that translating $\{0,1,3\}$ produces the Fano-plane incidence pattern. [/example] The example shows what a perfect difference distribution looks like for one block, but in larger parameter sets a single block may not be enough. We therefore allow several base blocks and ask the combined list of their internal differences to cover every nonzero group element uniformly. This is the algebraic form of the pair-balance condition for a design that will later be developed by translations. [definition: Difference Family] Let $G$ be a finite abelian group of order $v$. A $(v,k,\lambda)$ difference family in $G$ is a collection $\mathcal{B}=\{B_1,\dots,B_t\}$ of $k$-subsets of $G$ such that every nonzero element of $G$ occurs exactly $\lambda$ times in the multiset union \begin{align*} \Delta B_1 \cup \cdots \cup \Delta B_t. \end{align*} [/definition] The definition of a difference family captures the general situation where several base blocks share the work of representing differences. Counting the elements in all difference multisets gives the necessary parameter relation \begin{align*} tk(k-1)=\lambda(v-1). \end{align*} This relation is often the first test for whether proposed parameters can be realised by a difference family. It motivates isolating the most economical case, where one base block alone carries the whole difference count. [definition: Difference Set] Let $G$ be a finite abelian group of order $v$. A $(v,k,\lambda)$ difference set in $G$ is a $k$-subset $D \subset G$ such that every nonzero element of $G$ occurs exactly $\lambda$ times in $\Delta D$. [/definition] The definition of a difference set is the one-block version of the previous definition, so it is much more restrictive than a general difference family. Since all nonzero group elements must appear with the same multiplicity inside a single difference multiset, the parameters cannot be chosen independently. This motivates a first theorem obtained by counting the same multiset in two ways. [quotetheorem:5758] [citeproof:5758] This parameter equation is a necessary arithmetic test, not an existence theorem. It explains why the example in $\mathbb{Z}/7\mathbb{Z}$ has parameters $(7,3,1)$, since the equation reads $3\cdot 2=1\cdot 6$, but it does not say that every solution of $k(k-1)=\lambda(v-1)$ is realised by a difference set. The hypothesis that every nonzero group element occurs with the same multiplicity is doing real work: in $\mathbb{Z}/7\mathbb{Z}$, the set $\{0,1,2\}$ has six ordered differences, but the multiset is $\{1,2,6,1,5,6\}$, so the residues $1$ and $6$ appear twice while $3$ and $4$ do not appear. This is why the equation is used later only as a first filter; the construction theorems require the full uniform difference condition, not just the right total number of differences. ## Cyclic BIBDs From Difference Sets The next question is how a difference condition becomes a block design. The group operation supplies the construction: translate the base block by every group element and use the translates as the blocks. [definition: Translate Of A Block] Let $G$ be an abelian group and let $B \subset G$. For $g \in G$, the translate of $B$ by $g$ is \begin{align*} g+B=\{g+x:x\in B\}. \end{align*} [/definition] The definition of a translate gives the mechanism for turning one block into a full orbit of blocks. Translation preserves block size and transports differences without changing their multiplicities. Thus a point pair $\{a,b\}$ is contained in a translate precisely when the difference $b-a$ appears inside the base block with the right orientation. This motivates the key construction theorem: a difference set packages the whole pair-balance condition into one orbit of blocks under the regular action of $G$. [quotetheorem:5759] [citeproof:5759] The theorem is the main bridge from algebra to design theory in this chapter, and it also shows why the hypotheses cannot be weakened to a size count alone. If $D=\{0,1,2\}\subset \mathbb{Z}/7\mathbb{Z}$ is translated by every group element, then the pair whose difference is $1$ lies in two translated triples, while a pair whose difference is $3$ lies in none. Thus the development has constant block size and cyclic symmetry, but it fails the defining pair-balance condition of a $2$-design. The theorem also allows repeated blocks because different translates can coincide when a base block has a nontrivial period; in that case the construction is a design with multiplicities unless repeated blocks are deliberately identified. When $G$ is cyclic and the difference-set condition holds, the resulting design has a cyclic automorphism acting regularly on the point set, so it is useful to name this symmetry as a property of the design rather than of the construction. [definition: Cyclic Design] A block design on $v$ points is cyclic if it admits an automorphism of order $v$ acting transitively on the point set, where an automorphism is a bijection from the point set to itself that sends blocks to blocks. [/definition] For a cyclic design we may label the points by $\mathbb{Z}/v\mathbb{Z}$ so that this automorphism acts as addition of $1$. Base blocks then describe the full design by translation, and the Fano plane gives the model example. [example: The Fano Plane From One Difference Set] Let $D=\{0,1,3\}\subset \mathbb{Z}/7\mathbb{Z}$. Translating $D$ by each residue gives \begin{align*} 0+D&=\{0,1,3\}, \end{align*} \begin{align*} 1+D&=\{1,2,4\}, \end{align*} \begin{align*} 2+D&=\{2,3,5\}, \end{align*} \begin{align*} 3+D&=\{3,4,6\}, \end{align*} \begin{align*} 4+D&=\{4,5,0\}, \end{align*} \begin{align*} 5+D&=\{5,6,1\}, \end{align*} \begin{align*} 6+D&=\{6,0,2\}. \end{align*} The ordered differences inside $D$ are \begin{align*} 1-0&\equiv 1 \pmod 7, \end{align*} \begin{align*} 3-0&\equiv 3 \pmod 7, \end{align*} \begin{align*} 0-1&\equiv -1\equiv 6 \pmod 7, \end{align*} \begin{align*} 3-1&\equiv 2 \pmod 7, \end{align*} \begin{align*} 0-3&\equiv -3\equiv 4 \pmod 7, \end{align*} \begin{align*} 1-3&\equiv -2\equiv 5 \pmod 7. \end{align*} Thus every nonzero residue modulo $7$ occurs exactly once in $\Delta D$. Now take distinct residues $a,b\in \mathbb{Z}/7\mathbb{Z}$. Since $b-a\ne 0$, the displayed difference list gives a unique ordered pair $(x,y)$ of distinct elements of $D$ such that \begin{align*} y-x&\equiv b-a \pmod 7. \end{align*} Set $g=a-x$. Then \begin{align*} g+x&=(a-x)+x\equiv a \pmod 7, \end{align*} and \begin{align*} g+y&=(a-x)+y\equiv a+(y-x)\equiv a+(b-a)\equiv b \pmod 7. \end{align*} So the translate $g+D$ contains both $a$ and $b$. Conversely, if a translate $h+D$ contains both $a$ and $b$, then $a=h+u$ and $b=h+v$ for some distinct $u,v\in D$. Subtracting gives \begin{align*} v-u&\equiv (h+v)-(h+u)\equiv b-a \pmod 7. \end{align*} By the uniqueness of the ordered pair in the difference list, $(u,v)=(x,y)$, and then \begin{align*} h&\equiv a-u\equiv a-x\equiv g \pmod 7. \end{align*} Hence every unordered pair of distinct residues lies in exactly one translated triple. The development is therefore the Fano plane, a $2$-$(7,3,1)$ design. [/example] This example also gives the smallest cyclic Steiner triple system beyond the degenerate cases. The word Steiner here means $\lambda=1$ and $k=3$, so every pair of points appears in a unique triple. [example: A Cyclic Steiner Triple System] Let $D=\{0,1,3\}\subset \mathbb{Z}/7\mathbb{Z}$, and take the seven translates $g+D$ for $g\in \mathbb{Z}/7\mathbb{Z}$. These blocks are closed under the cyclic shift $x\mapsto x+1$, since \begin{align*} 1+(g+D)=\{1+(g+x):x\in D\}=\{(g+1)+x:x\in D\}=(g+1)+D. \end{align*} The six ordered differences inside $D$ are \begin{align*} 1-0\equiv 1 \pmod 7. \end{align*} \begin{align*} 3-0\equiv 3 \pmod 7. \end{align*} \begin{align*} 0-1\equiv -1\equiv 6 \pmod 7. \end{align*} \begin{align*} 3-1\equiv 2 \pmod 7. \end{align*} \begin{align*} 0-3\equiv -3\equiv 4 \pmod 7. \end{align*} \begin{align*} 1-3\equiv -2\equiv 5 \pmod 7. \end{align*} Thus \begin{align*} \Delta D=\{1,2,3,4,5,6\}, \end{align*} with each nonzero residue modulo $7$ appearing exactly once. Now fix an unordered pair $\{a,b\}$ with $a\ne b$. Since $b-a\not\equiv 0\pmod 7$, the displayed difference list gives a unique ordered pair $(x,y)$ of distinct elements of $D$ such that \begin{align*} y-x\equiv b-a \pmod 7. \end{align*} Set $g=a-x$. Then \begin{align*} g+x\equiv (a-x)+x\equiv a \pmod 7. \end{align*} Also, \begin{align*} g+y\equiv (a-x)+y\equiv a+(y-x)\equiv a+(b-a)\equiv b \pmod 7. \end{align*} So the translate $g+D$ contains both $a$ and $b$. Conversely, suppose $h+D$ contains both $a$ and $b$. Then there are $u,v\in D$ with \begin{align*} a\equiv h+u \pmod 7 \end{align*} and \begin{align*} b\equiv h+v \pmod 7. \end{align*} Because $a\ne b$, we have $u\ne v$. Subtracting the two congruences gives \begin{align*} v-u\equiv (h+v)-(h+u)\equiv b-a \pmod 7. \end{align*} By uniqueness of the ordered pair in the difference list, $(u,v)=(x,y)$. Hence \begin{align*} h\equiv a-u\equiv a-x\equiv g \pmod 7. \end{align*} Therefore the translate containing $\{a,b\}$ is unique. The seven cyclic translates of $D$ form a Steiner triple system on $\mathbb{Z}/7\mathbb{Z}$: every block has size $3$, and every unordered pair of distinct points lies in exactly one block. [/example] A single base block is not always available, even when a cyclic or abelian construction exists. The difference-family definition was introduced to handle this situation, and now the same translation argument gives the corresponding design construction. The only change is that the count of blocks through a pair is summed over all base blocks. [quotetheorem:5760] [citeproof:5760] This theorem is often called development: the small list of base blocks is developed under the [group action](/page/Group%20Action) into a complete design. The difference-family hypothesis is essential because the number of developed blocks through a pair depends only on the multiplicity of the corresponding group difference in the base blocks. If a nonzero element is missing from the combined difference multiset, then every pair with that difference is omitted from the developed incidence structure; if it appears too often, those pairs occur in too many blocks. It is also necessary to translate all base blocks by the whole group: translating by only a subset of group elements usually destroys the uniformity between pairs in different orbits. The theorem guarantees a BIBD with repeated blocks allowed, but it does not guarantee simplicity, uniqueness of the base family, or existence for every numerically admissible parameter set. ## Singer Difference Sets and Finite Projective Planes The final question in this chapter is where large families of difference sets come from. Finite projective planes provide the most important source, and the construction due to Singer shows that their incidence can be made cyclic when the plane is coordinatised over a finite field. [definition: Projective Plane Parameters] A finite projective plane of order $q$ is a $2$-$(q^2+q+1,q+1,1)$ design. [/definition] The parameter definition connects projective geometry to the BIBD language developed earlier in the course. In geometric language, the points are one-dimensional subspaces of a three-dimensional vector space over $\mathbb{F}_q$, and the lines are two-dimensional subspaces. The design parameters say that each line has $q+1$ points and any two points determine a unique line. This motivates Singer's theorem, which strengthens the construction by showing that the lines may be obtained as translates of one cyclic difference set. [quotetheorem:5761] One construction route uses the multiplicative group of $\mathbb{F}_{q^3}$ acting on the one-dimensional subspaces of $\mathbb{F}_{q^3}$ over $\mathbb{F}_q$. Multiplication by a nonzero element of $\mathbb{F}_{q^3}$ sends each one-dimensional $\mathbb{F}_q$-subspace to another such subspace, while multiplication by an element of $\mathbb{F}_q^{\times}$ fixes every projective point because it only rescales representatives inside the same line. Therefore the effective cyclic symmetry on projective points is the quotient $\mathbb{F}_{q^3}^{\times}/\mathbb{F}_q^{\times}$, which has order $(q^3-1)/(q-1)=q^2+q+1$. A chosen projective line then gives the required set of exponents. The full verification belongs to finite geometry and finite field theory, so the theorem is used here as a construction source. [example: Singer Set For The Fano Plane] When $q=2$, the Singer parameters are \begin{align*} q^2+q+1=2^2+2+1=4+2+1=7. \end{align*} Also, \begin{align*} q+1=2+1=3. \end{align*} We now see explicitly why the block $\{0,1,3\}$ appears from the field model of the Fano plane. Work in $\mathbb{F}_8=\mathbb{F}_2[\alpha]$ with $\alpha^3=\alpha+1$. The powers of $\alpha$ are \begin{align*} \alpha^0=1. \end{align*} \begin{align*} \alpha^1=\alpha. \end{align*} \begin{align*} \alpha^2=\alpha^2. \end{align*} \begin{align*} \alpha^3=\alpha+1. \end{align*} \begin{align*} \alpha^4=\alpha(\alpha+1)=\alpha^2+\alpha. \end{align*} \begin{align*} \alpha^5=\alpha(\alpha^2+\alpha)=\alpha^3+\alpha^2=(\alpha+1)+\alpha^2=\alpha^2+\alpha+1. \end{align*} \begin{align*} \alpha^6=\alpha(\alpha^2+\alpha+1)=\alpha^3+\alpha^2+\alpha=(\alpha+1)+\alpha^2+\alpha=\alpha^2+1. \end{align*} \begin{align*} \alpha^7=\alpha(\alpha^2+1)=\alpha^3+\alpha=(\alpha+1)+\alpha=1. \end{align*} Thus multiplication by $\alpha$ cycles the seven nonzero elements of $\mathbb{F}_8$, so exponent labels are residues modulo $7$. Since $\mathbb{F}_2^\times=\{1\}$, the projective points of $PG(2,2)$ may be identified with the seven nonzero elements of $\mathbb{F}_8$. The two-dimensional $\mathbb{F}_2$-subspace spanned by $1$ and $\alpha$ has exactly the nonzero elements \begin{align*} 1,\quad \alpha,\quad 1+\alpha. \end{align*} Because $\alpha^3=\alpha+1$, these are \begin{align*} \alpha^0,\quad \alpha^1,\quad \alpha^3. \end{align*} So this projective line has exponent set \begin{align*} D=\{0,1,3\}\subset \mathbb{Z}/7\mathbb{Z}. \end{align*} The ordered differences inside $D$ are \begin{align*} 1-0\equiv 1 \pmod 7. \end{align*} \begin{align*} 3-0\equiv 3 \pmod 7. \end{align*} \begin{align*} 0-1\equiv -1\equiv 6 \pmod 7. \end{align*} \begin{align*} 3-1\equiv 2 \pmod 7. \end{align*} \begin{align*} 0-3\equiv -3\equiv 4 \pmod 7. \end{align*} \begin{align*} 1-3\equiv -2\equiv 5 \pmod 7. \end{align*} Hence \begin{align*} \Delta D=\{1,2,3,4,5,6\}, \end{align*} with each nonzero residue modulo $7$ appearing exactly once. Therefore $D$ is a $(7,3,1)$ difference set. Multiplying the line by $\alpha^g$ sends the three points $\alpha^0,\alpha^1,\alpha^3$ to \begin{align*} \alpha^g,\quad \alpha^{g+1},\quad \alpha^{g+3}. \end{align*} Because exponents are taken modulo $7$, the corresponding exponent set is \begin{align*} g+D=\{g,g+1,g+3\}\subset \mathbb{Z}/7\mathbb{Z}. \end{align*} Thus the seven translates of $\{0,1,3\}$ are exactly the seven cyclic images of one projective line. The Singer description records the Fano plane by powers of a field generator: one projective line gives the base block $\{0,1,3\}$, and multiplication by $\alpha$ moves that line through all seven lines. [/example] Singer's theorem explains why the Fano plane is not an isolated coincidence. It is the first member of an infinite prime-power family of cyclic projective planes. [remark: Cyclic Symmetry As Compression] A cyclic difference set stores a projective plane of order $q$ using only $q+1$ residues rather than listing all $q^2+q+1$ lines. The group action recovers the remaining lines, and the difference condition verifies the pair-incidence axiom. This compression is useful both conceptually and computationally. [/remark] The chapter's main lesson is that a design with many blocks can sometimes be controlled by a single arithmetic object. Difference sets turn pair incidence into a uniform difference count, cyclic development turns that count into a BIBD, and Singer's theorem supplies a major family coming from finite projective planes. Difference sets compress an entire design into one algebraic seed, and that same seed can be translated into linear algebra. The next chapter explains how incidence matrices become codes, and how code structure can in turn recover designs with uniform intersection properties. # 9. Codes from Designs and Designs from Codes This chapter explains how incidence structures can be translated into linear codes, and how special families of codewords can recover block designs. Chapters 3 through 8 built designs directly from incidence axioms, finite geometries, recursive constructions, and difference sets; here we add a coding-theoretic linear algebra viewpoint over finite fields. The guiding question is: when does a geometric or design-theoretic incidence pattern become an error-correcting code, and when do the words of a code themselves form a design? Only a modest amount of coding theory is needed for the examples that follow. A code is treated as a finite-dimensional vector space over a finite field, a parity-check matrix records linear equations, and a dual code is the orthogonal complement under the usual dot product. The deeper tools named later, such as MacWilliams identities and association schemes, are used as context for external structure theorems rather than developed from scratch in this course. ## Incidence Vectors and Linear Codes over Finite Fields A block design records which points lie in which blocks. To connect this information with coding theory, we first need a way to replace each block by an algebraic object that can be added, scaled, and tested by linear equations. [definition: Incidence Vector] Let $X=\{x_1,\dots,x_v\}$ be a finite point set and let $B \subset X$. For a finite field $\mathbb F_q$, the incidence vector of $B$ over $\mathbb F_q$ is the vector $\mathbf{1}_B \in \mathbb F_q^v$ whose $i$th coordinate is $1$ if $x_i \in B$ and $0$ if $x_i \notin B$. [/definition] The same subset gives different algebraic behaviour over different fields, because intersections are counted modulo the characteristic. For binary codes, the sum of two incidence vectors is the incidence vector of the symmetric difference of the two blocks. Since a single vector only remembers one block, the next construction collects every block vector into one linear object whose dimension, dual, and minimum distance can be studied. [definition: Code Generated by a Design] Let $\mathcal D=(X,\mathcal B)$ be an incidence structure with $X=\{x_1,\dots,x_v\}$, and let $\mathbb F_q$ be a finite field. The code generated by $\mathcal D$ over $\mathbb F_q$ is \begin{align*} C_q(\mathcal D) = \operatorname{span}_{\mathbb F_q}\{\mathbf{1}_B : B \in \mathcal B\} \subseteq \mathbb F_q^v. \end{align*} [/definition] This code packages all linear relations among the block incidence vectors. Its dimension depends on the rank of the incidence matrix over $\mathbb F_q$, so the same design may produce codes of different dimensions in different characteristics. To compare such codes with the standard language of error correction, we need their length, dimension, and minimum distance. [definition: Linear Code Parameters] A linear $q$-ary code of length $n$ is a subspace $C \le \mathbb F_q^n$. Its dimension is $k=\dim_{\mathbb F_q} C$, its minimum distance is \begin{align*} d(C)=\min\{d_H(c,c') : c,c' \in C,\ c \ne c'\}, \end{align*} and its minimum weight is \begin{align*} w(C)=\min\{|\operatorname{supp}(c)| : c \in C,\ c \ne 0\}. \end{align*} [/definition] For a linear code, distance is controlled by weights because $d_H(c,c')=|\operatorname{supp}(c-c')|$. Thus the design-theoretic problem of understanding which point sets occur as supports becomes the coding-theoretic problem of understanding low-weight codewords. [example: Binary Span of Blocks] Let $X=\{1,2,3,4\}$, with coordinates ordered as $1,2,3,4$, and let $B_1=\{1,2\}$, $B_2=\{2,3\}$, and $B_3=\{3,4\}$. Over $\mathbb F_2$, their incidence vectors are \begin{align*}\mathbf 1_{B_1}=(1,1,0,0),\quad \mathbf 1_{B_2}=(0,1,1,0),\quad \mathbf 1_{B_3}=(0,0,1,1).\end{align*} Adding the first two vectors coordinate by coordinate in $\mathbb F_2$ gives \begin{align*}\mathbf 1_{B_1}+\mathbf 1_{B_2}=(1,1,0,0)+(0,1,1,0).\end{align*} The four coordinates are \begin{align*}(1+0,\;1+1,\;0+1,\;0+0)=(1,0,1,0),\end{align*} because $1+1=0$ in $\mathbb F_2$. Therefore \begin{align*}\mathbf 1_{B_1}+\mathbf 1_{B_2}=(1,0,1,0).\end{align*} The support of this vector is $\{1,3\}$. This is the symmetric difference of the two blocks, since \begin{align*}B_1\setminus B_2=\{1\},\quad B_2\setminus B_1=\{3\},\quad B_1\triangle B_2=\{1\}\cup\{3\}=\{1,3\}.\end{align*} Thus $\{1,3\}$ occurs as the support of a codeword in $C_2(\mathcal D)$ even though it is not one of the original blocks $B_1,B_2,B_3$; taking the linear span of block incidence vectors can create new visible subsets. [/example] The example shows that linear combinations change the collection of visible subsets. The next question is how incidence regularity survives this translation into vectors. The first invariant to examine is the dot product, since it records common coordinates and therefore common points. [quotetheorem:5762] [citeproof:5762] This observation is the first bridge between designs and dual codes, but the congruence condition is essential and must be read in the characteristic of the field. If every block size and every pairwise block intersection is $0$ in $\mathbb F_q$, then all block generators are mutually orthogonal, and bilinearity forces the whole generated code to be self-orthogonal. Without those congruences, the conclusion can fail even for a highly regular design: in the Fano plane over $\mathbb F_2$, two distinct lines meet in one point, so their incidence vectors have dot product $1$, and the span of the line vectors is not forced by this argument to be self-orthogonal. Thus the theorem computes the obstruction to orthogonality; it does not say that incidence vectors from a design are automatically orthogonal. [example: Parity from Even Intersections] Suppose every block has even size and any two distinct blocks meet in an even number of points. For blocks $B$ and $C$, *Incidence Dot Products* gives \begin{align*}\mathbf 1_B\cdot \mathbf 1_C=|B\cap C|\cdot 1_{\mathbb F_2}.\end{align*} If $B=C$, then $|B\cap C|=|B|$ is even, so $\mathbf 1_B\cdot \mathbf 1_B=0$ in $\mathbb F_2$. If $B\ne C$, then $|B\cap C|$ is even by assumption, so again $\mathbf 1_B\cdot \mathbf 1_C=0$. Now take arbitrary codewords $u,v\in C_2(\mathcal D)$. Since $C_2(\mathcal D)$ is the span of the block incidence vectors over $\mathbb F_2$, there are coefficients $\alpha_B,\beta_C\in\mathbb F_2$ such that \begin{align*}u=\sum_{B\in\mathcal B}\alpha_B\mathbf 1_B.\end{align*} \begin{align*}v=\sum_{C\in\mathcal B}\beta_C\mathbf 1_C.\end{align*} By bilinearity of the dot product, \begin{align*}u\cdot v=\left(\sum_{B\in\mathcal B}\alpha_B\mathbf 1_B\right)\cdot\left(\sum_{C\in\mathcal B}\beta_C\mathbf 1_C\right).\end{align*} Expanding the two sums gives \begin{align*}u\cdot v=\sum_{B\in\mathcal B}\sum_{C\in\mathcal B}\alpha_B\beta_C(\mathbf 1_B\cdot \mathbf 1_C).\end{align*} Each factor $\mathbf 1_B\cdot \mathbf 1_C$ is $0$, so \begin{align*}u\cdot v=\sum_{B\in\mathcal B}\sum_{C\in\mathcal B}\alpha_B\beta_C\cdot 0=0.\end{align*} Thus every two codewords in $C_2(\mathcal D)$ are orthogonal, which is exactly $C_2(\mathcal D)\subseteq C_2(\mathcal D)^\perp$. The parity conditions on block sizes and intersections therefore become self-orthogonality of the generated binary code. [/example] ## Hamming Codes, Simplex Codes, and the Fano Plane The smallest projective plane already contains one of the central examples of coding theory. The problem is to see why the seven lines of the Fano plane are exactly the right parity checks for a binary single-error-correcting code. [definition: Binary Hamming Code of Length Seven] Let $H$ be the $3 \times 7$ matrix over $\mathbb F_2$ whose columns are the seven nonzero vectors of $\mathbb F_2^3$. The binary Hamming code of length $7$ is \begin{align*} \operatorname{Ham}(7,2)=\{c \in \mathbb F_2^7 : Hc^\top=0\}. \end{align*} [/definition] The order of the columns only labels the coordinate positions. The key point is that every nonzero syndrome in $\mathbb F_2^3$ occurs as exactly one column, so a single error can be located by its syndrome. [example: Parity-Check Matrix of the Hamming Code] Use the seven nonzero binary triples as columns, in the order $001,010,011,100,101,110,111$. Thus the first coordinates of the columns are $0,0,0,1,1,1,1$, the second coordinates are $0,1,1,0,0,1,1$, and the third coordinates are $1,0,1,0,1,0,1$. Hence the three rows of $H$ are $0001111$, $0110011$, and $1010101$. Let $r=c+e_i$, where $c\in \operatorname{Ham}(7,2)$ and $e_i$ is the $i$th standard basis vector. Since $c$ is in the Hamming code, $Hc^\top=0$ by the definition of $\operatorname{Ham}(7,2)$. Therefore, using linearity of matrix multiplication over $\mathbb F_2$, \begin{align*} Hr^\top=H(c+e_i)^\top=H(c^\top+e_i^\top)=Hc^\top+He_i^\top=0+He_i^\top=He_i^\top. \end{align*} If the $i$th column of $H$ is $h_i$, then multiplying $H$ by $e_i^\top$ selects that column, because the product is $0h_1+\cdots+1h_i+\cdots+0h_7=h_i$. For example, an error in position $5$ gives \begin{align*} He_5^\top=0h_1+0h_2+0h_3+0h_4+1h_5+0h_6+0h_7=h_5=101. \end{align*} The syndrome is therefore the column labelled $101$, so the decoder identifies position $5$ as the error position. Since the seven columns of $H$ are distinct and nonzero, every nonzero syndrome identifies exactly one single-coordinate error; this is the single-error-correction mechanism of the binary $[7,4,3]$ Hamming code. [/example] We now connect this parity-check matrix with the projective plane $PG(2,2)$. Its points are the one-dimensional subspaces of $\mathbb F_2^3$, which may be represented by the seven nonzero column vectors of $H$. To identify its lines inside the code, we need the vector-space description of the Fano plane. [definition: Fano Plane in Vector Form] The Fano plane is the incidence structure whose points are the nonzero vectors of $\mathbb F_2^3$, and whose lines are the triples \begin{align*} \{u,v,u+v\}, \qquad u,v \in \mathbb F_2^3 \setminus \{0\},\ u \ne v. \end{align*} [/definition] Over $\mathbb F_2$, each two-dimensional subspace has exactly three nonzero vectors. Thus the displayed triples are precisely the projective lines of $PG(2,2)$. The coding-theoretic question is whether the parity-check equations recover this geometry from the code alone. A weight-three support passes the parity check exactly when the three indexed column vectors sum to zero, so the obstruction is to distinguish genuine Fano lines from arbitrary triples of coordinates. [quotetheorem:5763] [citeproof:5763] This theorem reconstructs the Fano plane from the minimum-weight words of the Hamming code, but each hypothesis is doing work. The coordinates must be indexed by the seven nonzero vectors of $\mathbb F_2^3$; a relabelling is harmless, but adding a zero column or repeating a column would create supports that no longer describe projective lines. The field is also essential: the equation $u+v+w=0$ over $\mathbb F_2$ is exactly the statement that three projective points lie on a Fano line, while over larger fields a projective line has more than three points. Finally, weight $3$ matters because higher-weight Hamming codewords are sums of line vectors and need not themselves be incidence vectors of lines. The result is therefore a precise minimum-weight reconstruction, not a statement about every support in the code. [example: The Seven Weight Three Words] With columns labelled in the order $001,010,011,100,101,110,111$, a weight-$3$ word with support $\{a,b,c\}$ lies in $\operatorname{Ham}(7,2)$ exactly when the corresponding three columns satisfy \begin{align*}a+b+c=0.\end{align*} Since addition in $\mathbb F_2^3$ has $c+c=0$, this equation is equivalent to \begin{align*}a+b+c+c=0+c,\end{align*} so \begin{align*}a+b=c.\end{align*} Thus every weight-$3$ codeword is supported on a triple of the form $\{u,v,u+v\}$. The seven such triples, written in the displayed coordinate order, are \begin{align*}\{001,010,011\}\mapsto 1110000.\end{align*} \begin{align*}\{001,100,101\}\mapsto 1001100.\end{align*} \begin{align*}\{001,110,111\}\mapsto 1000011.\end{align*} \begin{align*}\{010,100,110\}\mapsto 0101010.\end{align*} \begin{align*}\{010,101,111\}\mapsto 0100101.\end{align*} \begin{align*}\{011,100,111\}\mapsto 0011001.\end{align*} \begin{align*}\{011,101,110\}\mapsto 0010110.\end{align*} For example, the first support gives $001+010+011=000$, and the second gives $001+100+101=000$, so the listed incidence vectors satisfy the Hamming parity-check equation. No weight-$1$ word lies in the code, because a single nonzero column of $H$ cannot sum to $0$. No weight-$2$ word lies in the code, because if two distinct nonzero columns $a,b$ satisfied $a+b=0$, then adding $b$ to both sides would give $a=b$. Therefore the minimum nonzero weight is $3$, and these seven weight-$3$ words are exactly the minimum-weight words of $\operatorname{Ham}(7,2)$. Their supports are precisely the seven Fano lines. [/example] The preceding example used the nullspace of $H$. There is also information in the row space of $H$: it records all parity checks as codewords. This dual viewpoint leads to the simplex code, whose supports are complements of Fano lines. [definition: Binary Simplex Code of Dimension Three] The binary simplex code of dimension $3$ is the row space of the $3 \times 7$ matrix $H$ whose columns are the nonzero vectors of $\mathbb F_2^3$. [/definition] The simplex code is the dual of the Hamming code because the Hamming code is defined as the nullspace of $H$. Its nonzero words are evaluations of nonzero linear functionals on the seven nonzero vectors of $\mathbb F_2^3$. This motivates the next theorem, which computes the weight of every nonzero simplex word and shows that the dual code gives complements of Fano lines. [quotetheorem:5764] [citeproof:5764] The simplex code complements the Fano-line picture: instead of lines of size $3$, its nonzero supports are complements of lines, each of size $4$. This interpretation depends on using all seven nonzero columns of $\mathbb F_2^3$ exactly once. If the zero column were included, every functional would vanish there and the support-complement count would change; if a nonzero column were omitted or repeated, the uniform weight-$4$ conclusion would fail in general. The restriction to nonzero functionals is also necessary, since the zero functional gives the zero word of weight $0$, not a complement of a line. Thus the theorem is a uniformity statement for the full projective point set of $PG(2,2)$, rather than for an arbitrary parity-check matrix. [example: Complements of Fano Lines] For $\ell(x_1,x_2,x_3)=x_1$, evaluate $\ell$ on the seven columns in the order \begin{align*} 001,\ 010,\ 011,\ 100,\ 101,\ 110,\ 111. \end{align*} The first three columns have first coordinate $0$, so \begin{align*} \ell(001)=\ell(010)=\ell(011)=0. \end{align*} The last four columns have first coordinate $1$, so \begin{align*} \ell(100)=\ell(101)=\ell(110)=\ell(111)=1. \end{align*} Hence the simplex codeword determined by $\ell$ is \begin{align*} 0001111, \end{align*} with support \begin{align*} \{100,101,110,111\}. \end{align*} The zero positions are the nonzero vectors satisfying $x_1=0$. Among the seven displayed nonzero vectors, these are exactly \begin{align*} 001,\ 010,\ 011. \end{align*} They form a Fano line because \begin{align*} 001+010=011 \end{align*} in $\mathbb F_2^3$, so the triple is of the form $\{u,v,u+v\}$. Thus this nonzero simplex word has support equal to the complement of the Fano line $\{001,010,011\}$ in the seven-point Fano plane. [/example] ## Supports of Codewords as Block Designs The Fano plane example suggests a reverse construction: begin with a code, take all codewords of a fixed weight, and use their supports as blocks. The central question is when these supports satisfy the uniform incidence axioms of a block design. [definition: Support Design of a Code at Weight] Let $C \le \mathbb F_q^n$ be a linear code and let $w$ be a positive integer. The support design of $C$ at weight $w$ is the incidence structure with point set $\{1,\dots,n\}$ and block set \begin{align*} \mathcal B_w(C)=\{\operatorname{supp}(c) : c \in C,\ |\operatorname{supp}(c)|=w\}. \end{align*} [/definition] The definition records supports as a set, so repeated supports are identified. This matters over non-binary fields, where $c$ and $\lambda c$ have the same support for every $\lambda \in \mathbb F_q^\times$. If multiplicities are retained instead, the same construction gives a multidesign; in these notes, the default is the simple support design unless stated otherwise. A fixed weight layer need not be a design: for the binary code $C=\operatorname{span}\{1100,0010\}\le \mathbb F_2^4$, the weight-$2$ supports include $\{1,2\}$ and $\{3,4\}$ but not any block containing both $1$ and $3$, so pairs of points are not covered uniformly. Before asking when a fixed weight layer is design-like, we need notation for the number of words at each weight, since empty or sparse layers cannot support much incidence structure. [definition: Weight Enumerator] Let $C \le \mathbb F_q^n$ be a linear code. The weight enumerator of $C$ is the polynomial $W_C(y) \in \mathbb Z[y]$ defined by \begin{align*} W_C(y)=\sum_{c \in C} y^{|\operatorname{supp}(c)|} = \sum_{i=0}^n A_i y^i, \end{align*} where $A_i=|\{c \in C : |\operatorname{supp}(c)|=i\}|$. [/definition] The numbers $A_i$ measure how many words of each weight occur, but the design question asks how their supports are distributed across coordinate subsets. The main quoted result of the chapter is an external bridge from coding theory to design theory: under strong restrictions on the weight distribution of a code and its dual, the coordinate distribution is forced to be design-like. [quotetheorem:5765] In these notes, the theorem is used as a black-box rigidity principle. The weight-distribution hypothesis prevents a fixed weight layer from clustering around some coordinates and avoiding others, as the small code $\operatorname{span}\{1100,0010\}$ already shows. This is why exceptional codes, such as Golay codes, can produce highly symmetric designs rather than merely many blocks of the same size. [example: Hamming Code Gives the Fano Plane] Let the seven coordinate positions be labelled by the nonzero vectors of $\mathbb F_2^3$. For $C=\operatorname{Ham}(7,2)$, a word with support $S$ lies in $C$ exactly when the columns indexed by $S$ sum to $0$, because $C=\{c\in\mathbb F_2^7:Hc^\top=0\}$. No word of weight $1$ lies in $C$, since a single nonzero column $a$ gives syndrome $a\ne 0$. No word of weight $2$ lies in $C$, since if distinct nonzero columns $a,b$ satisfied \begin{align*} a+b=0, \end{align*} then adding $b$ to both sides gives \begin{align*} a+b+b=0+b, \end{align*} so \begin{align*} a=b, \end{align*} because $b+b=0$ in $\mathbb F_2^3$, contradicting distinctness. Thus every nonzero codeword has weight at least $3$. For any two distinct nonzero columns $a,b$, the vector $a+b$ is nonzero and is distinct from both $a$ and $b$: if $a+b=0$ then $a=b$, if $a+b=a$ then $b=0$, and if $a+b=b$ then $a=0$. The three columns \begin{align*} a,\quad b,\quad a+b \end{align*} therefore determine a weight-$3$ word, since \begin{align*} a+b+(a+b)=a+a+b+b=0+0=0. \end{align*} Conversely, if a weight-$3$ word has support $\{a,b,c\}$, then \begin{align*} a+b+c=0. \end{align*} Adding $c$ to both sides gives \begin{align*} a+b+c+c=0+c, \end{align*} hence \begin{align*} a+b=c. \end{align*} So the weight-$3$ supports are exactly the triples $\{a,b,a+b\}$. Every pair $\{a,b\}$ of coordinate positions lies in the block $\{a,b,a+b\}$. It lies in no other block: any weight-$3$ support containing $a$ and $b$ must have third point $c$ satisfying $a+b+c=0$, and the calculation above forces $c=a+b$. Hence each pair lies in exactly one block. The support design at weight $3$ therefore has block size $3$ and pair multiplicity $1$, so it is the Steiner triple system $S(2,3,7)$, namely the Fano plane recovered from the minimum-weight codewords of the binary Hamming code. [/example] The Hamming example is small enough to verify by hand. Larger examples are where the theorem becomes useful, because the supports of codewords may be too numerous to list directly. [example: Ternary Golay Code Connection] For the ternary Golay code $C\le \mathbb F_3^{11}$, the parameter notation $[11,6,5]$ means that $C$ has length $11$, dimension $6$, and minimum distance $5$. Since $C$ is linear, its minimum distance is its minimum nonzero weight, so every nonzero codeword has weight at least $5$, and the minimum-weight codewords are exactly the weight-$5$ codewords. The standard weight enumerator of the ternary Golay code is \begin{align*} W_C(y)=1+132y^5+132y^6+330y^8+110y^9+24y^{11}. \end{align*} Thus there are $132$ codewords of weight $5$. Over $\mathbb F_3$, the two nonzero scalar multiples of a word $c$ are $c$ and $2c$, and they have the same support because a coordinate is nonzero in $c$ exactly when it is nonzero in $2c$. Therefore the number of distinct minimum-weight supports is \begin{align*} \frac{132}{2}=66. \end{align*} If these supports form a Steiner system $S(4,5,11)$, then each block has size $5$, and every $4$-subset of the $11$ coordinate positions must lie in exactly one block. The required number of blocks is forced by counting incident pairs $(T,B)$ where $T$ is a $4$-subset and $T\subseteq B$: \begin{align*} \binom{11}{4}=330 \end{align*} counts the possible $4$-subsets, while each block contains \begin{align*} \binom{5}{4}=5 \end{align*} such $4$-subsets. Hence the number of blocks must be \begin{align*} \frac{\binom{11}{4}}{\binom{5}{4}}=\frac{330}{5}=66. \end{align*} This matches the $66$ distinct supports obtained from the $132$ weight-$5$ codewords after identifying scalar multiples, so the minimum-weight support layer has exactly the right size for $S(4,5,11)$; the defining Golay-code incidence theorem states that these $66$ supports cover each $4$-subset once. Thus the minimum words of the ternary Golay code recover the Steiner system $S(4,5,11)$, showing how a strong code can encode a highly symmetric block design. [/example] The chapter therefore gives two complementary constructions. From a design, form a code by spanning incidence vectors and study ranks, orthogonality, and low-weight combinations. From a code, form designs by collecting supports in fixed weight layers, with the [Assmus-Mattson theorem](/theorems/5765) explaining why strong coding-theoretic regularity forces uniform incidence. Coding theory gives a new language for designs, but it also sets the stage for the final perspective of the course. We close by comparing constructive examples with general existence theorems, so the earlier counting, geometric, and algebraic tools can be seen as parts of one existence theory. # 10. Existence Theorems and Modern Perspective This chapter closes the course by comparing explicit constructions with general existence theorems. The prerequisites are the BIBD counting conditions from Chapter 3, the linear-algebraic obstructions from Chapter 4, the affine and projective examples from Chapter 5, and the recursive constructions from Chapters 6 and 7. The main question is no longer how to construct one attractive example, but whether the arithmetic divisibility conditions are eventually the only obstruction to existence. The results in this final chapter are intentionally read at a higher level than the earlier construction theorems. [Wilson's fundamental construction](/theorems/5766) is proved in the course because it is a usable recursive mechanism; Wilson's and Keevash's asymptotic existence theorems are quoted as landmarks that explain what the mature theory achieves beyond explicit small constructions. ## Direct Constructions and Asymptotic Existence A direct construction gives an explicit design on a specified point set, often using algebraic structure. The limitation is that algebraic constructions usually live at special parameter values: prime powers, cyclic groups with suitable difference sets, or recursive families seeded by small examples. Existence theory asks a different question: for a fixed local rule, do all sufficiently large admissible parameter values occur? [definition: Direct Construction] A direct construction of a design is a construction which explicitly specifies the point set and block set, together with a verification that the required incidence conditions hold. [/definition] Direct constructions are valuable because they produce usable objects and reveal structure. They are also sensitive to the arithmetic of the chosen model, so failure of a familiar construction is not evidence that the desired design fails to exist. [example: Algebraic Construction With Sparse Parameters] Let $q$ be a prime power, take $X=\mathbb F_q^2$, and use as blocks all affine lines \begin{align*} L_{m,b}=\{(x,mx+b):x\in\mathbb F_q\}\quad(m,b\in\mathbb F_q) \end{align*} together with the vertical lines \begin{align*} V_a=\{(a,y):y\in\mathbb F_q\}\quad(a\in\mathbb F_q). \end{align*} There are $q^2$ points. Each line $L_{m,b}$ has $q$ points because $x$ is chosen freely, and each line $V_a$ has $q$ points because $y$ is chosen freely. Now let $(x_1,y_1)\ne (x_2,y_2)$. If $x_1=x_2$, then $y_1\ne y_2$, and both points lie on $V_{x_1}$. No nonvertical line contains both, because $y=mx+b$ gives only one value of $y$ for the fixed value $x=x_1$. The vertical line containing them is also unique, since $V_a$ contains a point with first coordinate $x_1$ only when $a=x_1$. If $x_1\ne x_2$, then $x_2-x_1\ne 0$ in $\mathbb F_q$, so define \begin{align*} m=\frac{y_2-y_1}{x_2-x_1} \end{align*} and \begin{align*} b=y_1-mx_1. \end{align*} Then \begin{align*} mx_1+b=mx_1+(y_1-mx_1)=y_1 \end{align*} and \begin{align*} mx_2+b=mx_2+y_1-mx_1=y_1+m(x_2-x_1)=y_1+(y_2-y_1)=y_2. \end{align*} Thus both points lie on $L_{m,b}$. If another nonvertical line $L_{m',b'}$ contained both points, then \begin{align*} y_2-y_1=(m'x_2+b')-(m'x_1+b')=m'(x_2-x_1), \end{align*} so \begin{align*} m'=\frac{y_2-y_1}{x_2-x_1}=m. \end{align*} Using the first point gives \begin{align*} b'=y_1-m'x_1=y_1-mx_1=b. \end{align*} Hence $L_{m',b'}=L_{m,b}$, so the line is unique. Therefore the construction gives a $2-(q^2,q,1)$ design. Since there are infinitely many prime powers $q$, this produces designs for infinitely many values $v=q^2$. It still leaves gaps: for example, $v=36$ would require $q=6$, but there is no field $\mathbb F_6$, so this finite-field construction gives no design at that order. [/example] The example separates two tasks: producing designs at structured orders and deciding existence across an entire congruence class. To make the second task precise, we first record the arithmetic tests that every BIBD must pass. [definition: Admissible Parameters for a BIBD] Let $v,k,\lambda \in \mathbb N$ with $v > k \ge 2$. The parameters $(v,k,\lambda)$ are admissible for a $2-(v,k,\lambda)$ design if \begin{align*} \lambda(v-1) &\equiv 0 \pmod{k-1}, & \lambda v(v-1) &\equiv 0 \pmod{k(k-1)}. \end{align*} [/definition] These are exactly the integrality conditions obtained from the replication number and number of blocks. They are necessary for every BIBD, but early examples suggest they might not be sufficient at small values. [example: Testing Admissibility for Triple Systems] For a Steiner triple system, the desired parameters are $2-(v,3,1)$. The admissibility conditions for a $2-(v,k,\lambda)$ design are \begin{align*} \lambda(v-1)\equiv 0 \pmod{k-1} \end{align*} and \begin{align*} \lambda v(v-1)\equiv 0 \pmod{k(k-1)}. \end{align*} Substituting $k=3$ and $\lambda=1$ gives \begin{align*} v-1\equiv 0 \pmod 2 \end{align*} and \begin{align*} v(v-1)\equiv 0 \pmod 6. \end{align*} The first congruence says that $v$ is odd, so modulo $6$ the possible odd residues are $1$, $3$, and $5$. Checking the second congruence on these residues gives \begin{align*} 1(1-1)=0\equiv 0\pmod 6, \end{align*} \begin{align*} 3(3-1)=6\equiv 0\pmod 6, \end{align*} and \begin{align*} 5(5-1)=20\equiv 2\pmod 6. \end{align*} Thus the admissible orders for Steiner triple systems are exactly \begin{align*} v\equiv 1\text{ or }3\pmod 6. \end{align*} For the listed values, $7\equiv 1\pmod 6$, $9\equiv 3\pmod 6$, and $8\equiv 2\pmod 6$. Hence $v=7$ and $v=9$ pass the necessary counting test, while $v=8$ does not. The Fano plane realizes the admissible case $v=7$, and the affine plane over $\mathbb F_3$ realizes the admissible case $v=9$; admissibility rules out some parameters, but it does not by itself construct the design. [/example] This admissibility test gives a necessary filter, while the examples show that construction still has to be proved. We therefore need language for results that allow finitely many small exceptions but settle all large admissible orders. [definition: Asymptotic Existence] A family of designs with parameter set $P$ has asymptotic existence subject to admissibility if there is an integer $v_0$ such that every admissible parameter choice in $P$ with $v \ge v_0$ is realised by a design. [/definition] The definition deliberately does not give an explicit threshold. In many existence theorems, the known bound is far larger than the first true threshold, and the theorem is used for its structural message: beyond a finite range, divisibility is the whole obstruction. ## Pairwise Balanced Designs and Wilson's Fundamental Construction How can one build a large design when the available ingredients have different block sizes? Pairwise balanced designs answer this by allowing several block sizes while retaining the same pair-covering rule. They serve as a flexible skeleton into which smaller designs can be inserted. [definition: Pairwise Balanced Design] Let $X$ be a finite set, let $K \subset \mathbb N$ with each $k \in K$ satisfying $k \ge 2$, and let $\mathcal B$ be a collection of subsets of $X$. A pairwise balanced design with block sizes in $K$, written $\operatorname{PBD}(v,K,1)$, consists of $|X|=v$, $|B| \in K$ for every $B \in \mathcal B$, and for every two distinct points $x,y \in X$ there is a unique block $B \in \mathcal B$ with $x,y \in B$. [/definition] A BIBD is the special case in which all block sizes are equal. Allowing several sizes makes recursive constructions much more powerful because a large design can be assembled from ingredients whose orders match the skeleton block sizes. [example: A PBD With Two Block Sizes] Let $X=\{1,2,3,4,5\}$, and let \begin{align*} \mathcal B=\{\{1,2,3\},\{1,4,5\},\{2,4\},\{2,5\},\{3,4\},\{3,5\}\}. \end{align*} Every block has size $2$ or $3$, since \begin{align*} |\{1,2,3\}|&=3, & |\{1,4,5\}|&=3, \end{align*} and \begin{align*} |\{2,4\}|=|\{2,5\}|=|\{3,4\}|=|\{3,5\}|=2. \end{align*} The unordered pairs contained in $\{1,2,3\}$ are \begin{align*} \{1,2\},\quad \{1,3\},\quad \{2,3\}, \end{align*} and the unordered pairs contained in $\{1,4,5\}$ are \begin{align*} \{1,4\},\quad \{1,5\},\quad \{4,5\}. \end{align*} The four blocks of size $2$ contribute exactly the four pairs \begin{align*} \{2,4\},\quad \{2,5\},\quad \{3,4\},\quad \{3,5\}. \end{align*} Together these are \begin{align*} \{1,2\},\{1,3\},\{1,4\},\{1,5\},\{2,3\},\{2,4\},\{2,5\},\{3,4\},\{3,5\},\{4,5\}, \end{align*} which is the full list of the $\binom{5}{2}=10$ unordered pairs of distinct points in $X$, with no pair repeated in the list. Therefore every pair of distinct points of $X$ lies in exactly one block, so $(X,\mathcal B)$ is a $\operatorname{PBD}(5,\{2,3\},1)$. This example shows that pair balance can be maintained even when the block sizes are mixed rather than uniform. [/example] Mixed block sizes give the master design flexibility, but a recursive construction needs a way to replace each master point by a cluster of new points. The next definition records this expansion data so that each master block can later be filled by an ingredient design on the corresponding clusters. [definition: Weighted Fibre Set] Let $(X,\mathcal B)$ be a PBD and let $w:X\to \mathbb Z_{\ge 0}$ be a weight function. The fibre over $x\in X$ is a set $F_x$ with $|F_x|=w(x)$, and the expanded point set is \begin{align*} Y=\bigcup_{x\in X} F_x, \end{align*} where the fibres are pairwise disjoint. [/definition] The expanded point set has replaced a single point by several copies, or by no copy if the weight is zero. The problem is now to transfer pair balance from the master PBD to the expanded fibres without making two different master blocks cover the same expanded pair. Wilson's fundamental construction is the theorem needed for this transfer: it states exactly when compatible ingredient designs can be pasted together into one larger incidence structure. [definition: Group Divisible Design] A group divisible design consists of a finite point set $Y$, a partition $\mathcal G$ of $Y$ into groups, and a block set $\mathcal A$ such that no block contains two points from the same group, and every pair of points from distinct groups occurs in exactly one block. [/definition] This is the ingredient object used in Wilson's construction. The groups are the fibres replacing the master points, and the condition says that ingredient blocks cover cross-fibre pairs while deliberately avoiding pairs that lie inside a single fibre. With the fibres and ingredient designs now named, the central construction question becomes precise: if every master block has a compatible group divisible ingredient on its fibres, can all of those local ingredients be pasted into one global design without duplicating or missing cross-fibre pairs? Wilson's fundamental construction answers exactly this question. [quotetheorem:5766] [citeproof:5766] The bookkeeping behind the result depends essentially on its hypotheses. If the master design did not contain each pair $x,y$ in a unique block, then a pair chosen from $F_x$ and $F_y$ would either be missed or would be covered by two different ingredient designs. If an ingredient block were allowed to contain two points from the same fibre, then the final structure would violate the group condition immediately. The theorem also has a clear limitation: it does not supply the master PBD or the ingredient GDDs. Its role is to certify that, once those local objects have been found, their pair-covering properties paste together without interference. This is the recursive engine behind Wilson's existence theory: large designs are reached by choosing flexible skeletons and then filling their blocks with a controlled finite stock of smaller designs. [example: Small Ingredient Designs in a Recursive Construction] Suppose the master design is a $\operatorname{PBD}(v,\{3,4\},1)$ on point set $X$, and give every master point weight $2$. For each $x\in X$, choose a fibre $F_x$ with \begin{align*} |F_x|=2. \end{align*} Since the fibres are pairwise disjoint, the expanded point set \begin{align*} Y=\bigcup_{x\in X}F_x \end{align*} has size \begin{align*} |Y|=\sum_{x\in X}|F_x|=\sum_{x\in X}2=2|X|=2v. \end{align*} To apply *Wilson Fundamental Construction* with $K'=\{3\}$, each master block of size $3$ must be replaced by a group divisible design on three groups \begin{align*} F_{x_1},\ F_{x_2},\ F_{x_3}, \end{align*} each of size $2$, and each master block of size $4$ must be replaced by a group divisible design on four groups \begin{align*} F_{x_1},\ F_{x_2},\ F_{x_3},\ F_{x_4}, \end{align*} again each of size $2$. In both ingredients, every block has size $3$, so every block chooses points from three distinct fibres and therefore meets each fibre in at most one point. Now take two points $p\in F_x$ and $q\in F_y$ with $x\ne y$. Since the master design is a PBD, there is a unique master block $B$ with $x,y\in B$. The ingredient design placed on $B$ covers the cross-fibre pair $\{p,q\}$ exactly once, and no ingredient placed on a different master block can contain both $p$ and $q$, because that would require a second master block containing the pair $\{x,y\}$. Thus every pair from distinct fibres is covered exactly once in the expanded design, while pairs inside a single fibre are not covered because ingredient blocks never contain two points from one group. This shows how having just the two ingredient types, one for master blocks of size $3$ and one for master blocks of size $4$, is enough to expand any such master PBD into a larger group divisible design on $2v$ points. [/example] This definition captures the local object needed inside each master block. The fundamental construction then becomes a machine for pasting together these local objects without creating conflicts between different parts of the master design. ## Wilson's Theorem and BIBD Existence The fundamental construction is useful because there are enough master designs and enough ingredients to prove general existence. The central result of the classical theory says that, for fixed allowed block sizes, the elementary divisibility conditions for PBDs are eventually sufficient. [definition: PBD Divisibility Parameters] For a set $K\subset \mathbb N$ with every $k\in K$ satisfying $k\ge 2$, define \begin{align*} \alpha(K)&=\gcd\{k-1:k\in K\}, & \beta(K)&=\gcd\{k(k-1):k\in K\}. \end{align*} A positive integer $v$ is admissible for $\operatorname{PBD}(v,K,1)$ if \begin{align*} v-1 &\equiv 0 \pmod{\alpha(K)}, & v(v-1)&\equiv 0 \pmod{\beta(K)}. \end{align*} [/definition] These congruences come from counting, for a fixed point, the other points paired with it, and from counting ordered pairs of distinct points globally. The theorem asserts that no further obstruction remains beyond finitely many small values. [quotetheorem:5767] [citeproof:5767] The finiteness of $K$ and the lower bound $k\ge 2$ are important. If $K$ were allowed to vary with $v$, the theorem would no longer be a fixed local rule, and the threshold statement would lose its content; if blocks of size $1$ were allowed, they would contribute no pairs and would not fit the counting congruences. Even for fixed $K$, the theorem is asymptotic rather than a compact recipe for the smallest cases: the value of $v_0(K)$ supplied by the proof may be far larger than the true first admissible order. Its force is that congruence conditions, which began as necessary arithmetic checks, become eventually complete. The next step is to transfer this philosophy from mixed block sizes back to the BIBDs studied throughout the course, where every block has one prescribed size and every pair must occur exactly $\lambda$ times. [example: Why Congruence Conditions Become Sufficient] For $K=\{3\}$, a $\operatorname{PBD}(v,K,1)$ has only blocks of size $3$, so it is exactly a Steiner triple system on $v$ points. The divisibility parameters are computed from the definition: \begin{align*} \alpha(K)=\gcd\{k-1:k\in K\}=\gcd\{3-1\}=\gcd\{2\}=2. \end{align*} Similarly, \begin{align*} \beta(K)=\gcd\{k(k-1):k\in K\}=\gcd\{3(3-1)\}=\gcd\{6\}=6. \end{align*} Thus admissibility means \begin{align*} v-1\equiv 0\pmod 2 \end{align*} and \begin{align*} v(v-1)\equiv 0\pmod 6. \end{align*} The first congruence says that $v$ is odd, so modulo $6$ the possible residues are $1$, $3$, and $5$. Testing these in the second congruence gives \begin{align*} 1(1-1)=0\equiv 0\pmod 6. \end{align*} Also, \begin{align*} 3(3-1)=6\equiv 0\pmod 6. \end{align*} Finally, \begin{align*} 5(5-1)=20\equiv 2\pmod 6. \end{align*} Therefore the admissible values are exactly \begin{align*} v\equiv 1\text{ or }3\pmod 6. \end{align*} By the *Wilson Existence Theorem for PBDs*, every sufficiently large $v$ satisfying these congruences has a Steiner triple system. The classical *Kirkman theorem* is sharper in this special case: every $v\equiv 1$ or $3\pmod 6$ with $v\ge 7$ is realised, so here the eventual sufficiency promised by Wilson's theorem is already visible at the first nontrivial admissible orders. [/example] The PBD theorem handles pair coverage with possibly varying block sizes, while BIBDs require every block to have the same size and every pair to occur $\lambda$ times. The next theorem is the fixed-block-size existence result that connects Wilson's machinery back to the main BIBD parameters of the course. [quotetheorem:5768] [citeproof:5768] This is the classical answer to the existence question for BIBDs, but the quantifiers matter. The integers $k$ and $\lambda$ are fixed before $v$ tends to infinity; the theorem does not give one uniform threshold for all block sizes and multiplicities. The admissibility conditions also remain genuine obstructions: for instance, failure of integrality of $r$ means a point would have to lie in a non-integer number of blocks, while failure of integrality of $b$ means the total pair count cannot be distributed among blocks of size $k$. The theorem does not construct a canonical design on a prescribed labelled point set, and it does not identify the smallest admissible orders. What it gives is the decisive asymptotic bridge from the examples of earlier chapters to a general existence principle: once $k$ and $\lambda$ are fixed, all sufficiently large parameter sets passing the counting tests are realised. [example: Ruling Out and Then Trusting the Conditions] For a $2-(10,4,1)$ design, the replication number forced by the BIBD counting equations is \begin{align*} r=\frac{\lambda(v-1)}{k-1} =\frac{1(10-1)}{4-1} =\frac{9}{3} =3. \end{align*} The number of blocks would then have to be \begin{align*} b=\frac{vr}{k} =\frac{10\cdot 3}{4} =\frac{30}{4} =\frac{15}{2}. \end{align*} Since $b$ counts blocks, it must be an integer, but $\frac{15}{2}$ is not an integer. Therefore no $2-(10,4,1)$ design exists. For $k=4$ and $\lambda=1$, the BIBD admissibility congruences become \begin{align*} \lambda(v-1)\equiv 0\pmod{k-1} \quad\Longleftrightarrow\quad v-1\equiv 0\pmod 3, \end{align*} and \begin{align*} \lambda v(v-1)\equiv 0\pmod{k(k-1)} \quad\Longleftrightarrow\quad v(v-1)\equiv 0\pmod{4\cdot 3} \quad\Longleftrightarrow\quad v(v-1)\equiv 0\pmod{12}. \end{align*} Thus the same counting conditions that rule out $v=10$ become sufficient in the large-order range: by the *Wilson Existence Theorem For BIBDs*, every sufficiently large $v$ satisfying these two congruences supports a $2-(v,4,1)$ design. [/example] ## Keevash's Theorem and the Modern View of Designs Wilson's theorem concerns pairwise conditions, where the local rule is about pairs of points. Modern design theory asks the same question for higher uniformity: when should every $t$-subset of a point set occur in exactly $\lambda$ blocks of size $k$? Keevash's theorem gives the corresponding asymptotic answer for general designs. [definition: General t Design] Let $1\le t<k<v$ and let $\lambda\in\mathbb N$. A $t-(v,k,\lambda)$ design is a pair $(X,\mathcal B)$ with $|X|=v$, each block $B\in \mathcal B$ satisfying $|B|=k$, and every $t$-element subset of $X$ contained in exactly $\lambda$ blocks. [/definition] The BIBDs of this course are the case $t=2$. For larger $t$, the same counting idea must be applied not only to points and pairs but to every smaller subset size, which leads to the full divisibility test. [definition: Divisibility Conditions for t Designs] Let $1\le t<k<v$ and let $\lambda\in\mathbb N$. The parameters $(t,v,k,\lambda)$ satisfy the divisibility conditions if, for each $0\le i\le t-1$, \begin{align*} \binom{k-i}{t-i} \mid \lambda \binom{v-i}{t-i}. \end{align*} [/definition] These conditions count the number of blocks containing a fixed $i$-subset. They are necessary because each such number must be integral, and the modern question is whether they are also eventually sufficient for every fixed strength $t$. The next theorem is quoted as the modern endpoint of this question, not as a result proved from the elementary tools developed in the course. [quotetheorem:5769] For this course, Keevash's theorem is used as context: it shows that the Wilson philosophy extends from pairwise balance to arbitrary fixed strength $t$. Its proof uses probabilistic and algebraic absorption methods that are not developed in these notes. [remark: Modern Perspective] Wilson's theorem and Keevash's theorem have the same conceptual form: local counting divisibility is eventually sufficient. The difference is methodological. Wilson's proof is rooted in recursive design constructions, while Keevash's proof uses modern randomised construction with absorption to handle the higher-dimensional compatibility constraints. [/remark] Keevash's result reframes the subject. The small examples from Latin squares, affine planes, projective planes, difference sets, and codes are not isolated curiosities; they are the visible low-dimensional part of a broad existence theory. [example: The Case of Steiner Quadruple Systems] A Steiner quadruple system is a $3-(v,4,1)$ design. Substituting $t=3$, $k=4$, and $\lambda=1$ into the divisibility conditions gives three requirements, one for each $i=0,1,2$: \begin{align*} \binom{4}{3}\mid \binom v3,\qquad \binom{3}{2}\mid \binom{v-1}{2},\qquad \binom{2}{1}\mid \binom{v-2}{1}. \end{align*} Since \begin{align*} \binom{4}{3}=4,\qquad \binom{3}{2}=3,\qquad \binom{2}{1}=2,\qquad \binom{v-2}{1}=v-2, \end{align*} these become \begin{align*} 4\mid \binom v3,\qquad 3\mid \binom{v-1}{2},\qquad 2\mid v-2. \end{align*} The last condition says that $v$ is even. For the middle condition, \begin{align*} \binom{v-1}{2}=\frac{(v-1)(v-2)}{2}. \end{align*} Because $2$ is invertible modulo $3$, this gives \begin{align*} 3\mid \binom{v-1}{2}\quad\Longleftrightarrow\quad 3\mid (v-1)(v-2). \end{align*} Thus $v\equiv 1$ or $2\pmod 3$. Combining this with $v$ even leaves exactly \begin{align*} v\equiv 4\pmod 6\quad\text{or}\quad v\equiv 2\pmod 6. \end{align*} It remains to check that the first divisibility condition is automatic in these two residue classes. If $v=6n+2$, then \begin{align*} \binom{6n+2}{3}=\frac{(6n+2)(6n+1)(6n)}{6}=(6n+2)(6n+1)n=2(3n+1)(6n+1)n. \end{align*} If $n$ is even, the factor $n$ supplies a second factor of $2$; if $n$ is odd, then $3n+1$ is even. In either case $4\mid \binom{6n+2}{3}$. If $v=6n+4$, then \begin{align*} \binom{6n+4}{3}=\frac{(6n+4)(6n+3)(6n+2)}{6}=2(3n+2)(2n+1)(3n+1). \end{align*} The two integers $3n+1$ and $3n+2$ are consecutive, so one is even, and therefore $4\mid \binom{6n+4}{3}$. Hence the divisibility conditions for Steiner quadruple systems are exactly \begin{align*} v\equiv 2\text{ or }4\pmod 6. \end{align*} By *[Keevash Existence Theorem for Designs](/theorems/5769)*, every sufficiently large $v$ satisfying these congruences has a Steiner quadruple system; the calculation identifies precisely which arithmetic classes the theorem eventually realizes. [/example] The modern endpoint of the course is therefore not a single construction but a principle. For fixed design strength and block size, the arithmetic conditions forced by counting are eventually complete; the remaining mathematical work lies in understanding thresholds, explicit constructions, symmetry, algorithms, and applications. ## Beyond and Connected Topics Combinatorial design theory connects most directly to finite fields and Galois theory. The constructions of affine planes, projective planes, mutually orthogonal Latin squares, and cyclic difference sets all rely on the arithmetic of finite fields and finite cyclic groups. A reader who wants the algebra underneath those constructions should next compare these notes with [Cambridge II Galois Theory](/page/Cambridge%20II%20Galois%20Theory), especially the material on finite fields and field automorphisms. The course also sits beside combinatorial optimisation. Designs impose exact balance conditions, while optimisation often asks for an extremal or best feasible object subject to graph, matching, flow, or matroid constraints. The common language is finite incidence: points versus blocks here, vertices versus edges and independent sets there. Fisher-type inequalities, incidence matrices, and rank arguments are especially useful bridges between the two viewpoints. Finite geometry provides another continuation. Projective and affine planes are the rank-two examples of a broader incidence-geometric world, where one studies polar spaces, generalized polygons, spreads, ovoids, and blocking sets. In that direction, the small Fano-plane and affine-plane examples in these notes become prototypes for much richer geometries over finite fields. Coding theory is the application thread that keeps the incidence-vector viewpoint alive. A block design gives a structured family of binary or $q$-ary vectors; conversely, many highly symmetric codes have supports that form designs. This is why the Assmus-Mattson philosophy is natural: distance regularity in a code can force uniformity among supports, turning an algebraic object into a combinatorial design. Algebraic combinatorics gives a final organizing framework. Incidence matrices lead to association schemes, strongly regular graphs, eigenvalue bounds, and symmetric-function methods for highly regular finite structures. From this perspective, Wilson's and Keevash's theorems are not isolated existence results but part of a larger theme: local algebraic or counting constraints can control global combinatorial structure once the ambient set is large enough. ## References Beth, Jungnickel, and Lenz, *Design Theory*. Colbourn and Dinitz, eds., *Handbook of Combinatorial Designs*. van Lint and Wilson, *A Course in Combinatorics*. Wilson, "An existence theory for pairwise balanced designs". Keevash, "The existence of designs".