Witt Design
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).
Contact the MathWorld Team
coding theory
