Block of a Steiner system 2026-10-14
A designated subset in a Steiner system is a Steiner block. In a system , each Steiner block contains points and each -point subset belongs to exactly one Steiner block. For , this is the pair-coverage condition used in a cyclotomic construction of a Steiner 2-design.
Put , take odd , and let be the index- multiplicative subgroup. If a -set has its unordered pair differences in distinct -cosets, choose containing exactly one element from each pair . Then is a difference family for a Steiner 2-design. Indeed one unordered pair supplies each coset, and its two difference orientations multiplied by cover that coset once. Translations yield a - Steiner system. The cyclotomic pattern extension by a second-moment bound supplies suitable for all sufficiently large in this progression.
Difference family for a Steiner 2-design 2026-10-14
In a finite additive group, a family of -subsets is a difference family of index one if each nonzero group element occurs exactly once among all their ordered within-block differences. Translating its Steiner blocks by every group element gives a Steiner system with parameters -: the unique representation of a difference determines the unique translated Steiner block through two specified points.
Mathieu group Created 2026-10-14 Updated 2026-11-05
The five simple Mathieu groups are the exceptional finite simple groups . Their natural permutation group degrees are the displayed subscripts, with transitivity degrees , respectively.
One concrete definition of is the subgroup of generated byThese are the explicit generators of a group in the official Chapter 50, section 50.1-13, MathieuGroup example. Its order is , and its natural group action is sharply four-transitive.
The larger groups have useful design and coding realizations. is the automorphism group of the small Witt design; a point stabilizer is . The coordinate permutations preserving the extended binary Golay code form ; its one-point and two-point pointwise stabilizers are and . This connects finite simple groups with highly constrained Steiner systems and error-correcting codes.[ref]
Sporadic simple groups by Robert A. Wilson. Lecture 5, Mathieu groups and the Golay-code realization
Past exam of the mathematics course of the University of Cambridge 2007 iii Paper 7 4 iv Solution Created 2026-10-03 Updated 2026-10-14
A Steiner system consists of 12 points and a collection of six-element blocks such that every five-element subset lies in exactly one block. The blocks are often called hexads. Necessarily their number is . We give the synthematic construction of the small Witt design explicitly and prove this defining property.
Write and . For an unordered pair , let denote the unique syntheme shared by its two synthematic totals. A duad belongs to three synthemes. The corresponding three pairs partition : every synthematic total contains in exactly one of its synthemes, and each syntheme lies in exactly two synthematic totals. Thus the incidence gives a perfect matching of the six synthematic totals for each duad.
To describe the blocks with three points in each half, take an unordered partition into triples. A syntheme is cross if each of its three duads joins to . Form a graph on by declaring an edge exactly when is cross. This graph is the union of two disjoint triangles. Indeed a synthematic total partitions the nine cross duads; every syntheme has either one or three cross duads, so if of its five synthemes are cross, then , giving . Each vertex therefore has degree two. The stronger assertion about its components follows directly for , when the two triangles areany other triple partition is obtained by relabelling , which also permutes the synthematic totals. Denote the two components by .
The complete block collection is given by the following three rules:
There are distinct blocks. The first two rules have different intersection sizes with from the third; within the third, a block determines its triple and its component. We next verify the Steiner system property, rather than relying solely on this count.
We need one further consequence of the triangle construction. The three synthemes attached to the three pairs within are pairwise disjoint, since any two belong to their common synthematic total, and together they are all nine cross duads of the complete bipartite graph between and . Thus determines the unordered partition uniquely: it is the bipartition of this connected graph. There are 10 such partitions, each giving two different components, hence 20 different triples in . Since , each triple in corresponds to exactly one triple partition of . The same reasoning applies to .
Let be any five-point set and put . If , only can contain it; if , only can contain it, because no other block has five points in either half.
If , set and write . The three pairs attached to partition , so exactly one contains ; its block is the unique block through . If , put and write . The three duads of partition , so exactly one contains ; this gives the unique block .
If , write and . A syntheme has either one or three duads crossing . In the one-cross case, has exactly one duad internal to , and the unique block is . No block with three points in each half is possible, since is then not an edge of either triangle. In the three-cross case, is an edge of exactly one triangle , giving the unique block ; no duad of is internal to , so a block with four points in is impossible.
Finally let , write and , and use the uniquely associated partition just proved. If crosses this partition, the three synthemes belonging to the pairs inside contain each cross duad exactly once. Thus the matching of attached to has exactly one pair internal to . It has exactly one pair internal to as well, since a matching must leave equal numbers of vertices in the two halves for cross pairs. The unique block containing is then ; is not contained in either or , so no block of the third rule applies. If is internal to or , none of its attached pairs lies inside or , since the synthemes attached to these internal pairs are cross. Thus the second rule gives no block. The third rule gives exactly one, namely or , according to which part contains .
All possibilities have now been exhausted, provingThis is the small Witt design; the construction uses only duads, synthemes, their synthematic totals, and the induced action on those synthematic totals.
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 3 4 c Solution Created 2026-10-03 Updated 2026-10-07
A Steiner system is an -point set together with -element blocks such that every -element subset is contained in exactly one block. On , define the following six-element blocks using the incidence extensions of .
Take the two blocks and . For each duad of and each duad in the syntheme , takeThese give forty-five blocks of type and forty-five of type . Finally, for every corresponding partition pair and , take all four unionsThere are ten partition pairs and forty blocks of type . Distinct indexing data give distinct blocks within each family, and different types have different intersection sizes with . Thus the total is
If or , only or can contain it. If , write and with . A containing block must have type and its omitted duad is . The total has exactly one syntheme containing ; the other total containing that syntheme determines a unique second point . Thus the unique block is .
If , write and . A containing block must have type , with omitted duad . Exactly one duad contains , so is the unique block.
If , write and , where . There are only two possible types. A block exists exactly when the matching has a duad contained in . There is then exactly one such duad, since two disjoint duads cannot fit inside a triple. For a perfect matching on two triples, either all three pairs are cross, or there is one internal pair in each triple and one cross pair. Thus a block exists precisely when is not entirely cross for .
On the other hand, a block containing must use the unique partition of corresponding to . It exists precisely when is contained in one of that partition's triples, and is then unique. By the partition incidence rule in part (b), this happens precisely when is entirely cross. Hence exactly one of the two possible block types exists, always uniquely.
For , interchange the roles of and and use the inverse partition incidence rule proved in part (b). More explicitly, the duad either has an inverse syntheme with an internal pair in the complement of the triple , yielding a unique block, or its inverse syntheme is entirely cross, yielding the unique block. These alternatives are exclusive and exhaustive for the same matching-on-two-triples reason.