Given a pick-7 lottery with 23 numbers that pays a prize to anyone matching at least 4 of the 7 numbers, there is a set of 253 tickets that guarantees a win. This set corresponds to the Witt design.
More formally, the Witt design on 23 points is a 4-(23,7,1) block design (Witt 1938). It is one of the most remarkable structures in all of combinatorics
(Godsil and Royle 2001). It can be constructed by factoring 
over GF(2), into 
, where
 |
The 2048 powers 
,
, 
, ..., 
are then computed, mod 
. This set of vectors happens to be the [23,12,7] Golay code with 253 weight-7 vectors, 1288 weight-11 vectors,
and 506 weight-15 vectors. For example, 
is a weight-7 vector.
The Witt design is the set of 253 weight-7 vectors acting on 23 points.
Consider as vertices the 253 vectors (
) and 23 points (
). Set edges such that 
are adjacent if 
, and 
are adjacent if they share a single term. Select
an arbitrary vertex. For all 176 neighbors of that vertex, change edges to non-edges,
and non-edges to edges. Eliminate the now isolated vertex, and the remaining 275
vertex graph is the McLaughlin graph, a distance-regular
graph.
From the Witt design, 77 vectors contain 0 (0 chosen arbitrarily from 0-22). Eliminating the 0's (
)
gives the unique size 77 Steiner system 
on points 1 to 22. Consider as vertices the 77 vectors
(
), with 
adjacent if share no terms. This gives a 77-vertex
graph known as the M22 graph.
Consider as vertices the 77 vectors (
), 22 points (
), and new symbol 
. Set edges such that 
is adjacent to all 
, 
are adjacent if 
,
and 
are adjacent if share no terms.
The resulting 100-vertex graph is the Higman-Sims
graph, a distance-regular graph.
From 
on 77 vectors above, let the 56 vectors
that do not contain the arbitrarily chosen point 22 be vertices, and connect disjoint
vertices. This constructs the Gewirtz graph, a distance-regular graph on 56 nodes with intersection
array 
.
The large Witt design is the 759 weight-8 vectors of the Golay code, frequently called the octads. The large
Witt graph treats the 759 vectors of the large Witt design as vertices, with
an edge connecting disjoint vectors. This is a distance-regular
graph with intersection array 
.
The truncated Witt graph on 506 points is constructed by removing all vectors of the large Witt design containing an arbitrarily
chosen symbol. This produces a distance-regular
graph with intersection array 
.
The doubly truncated Witt graph on 330 points is constructed by removing all vectors of the large Witt design containing
any two arbitrarily chosen symbols. This is a distance-regular
graph with intersection array 
.
A similar construction factors 
over 
, producing the 
vectors of the Leech lattice
(Conway and Sloane 1999).
