APPLYING CONSTRAINT PROGRAMMING TO MINIMAL

LOTTERY DESIGNS

DAVID CUSHING

Department of Mathematics, The University of Manchester, Manchester, UK

arXiv:2307.12430v3 [math.CO] 17 Jun 2024

DAVID I. STEWART*

Department of Mathematics, The University of Manchester, Manchester, UK

Abstract. We develop and deploy a set of constraints for the purpose of calculating
minimal sizes of lottery designs. Specifically, we find the minimum number of tickets of
size six which are needed to match at least two balls on any draw of size six, whenever
there are at most 70 balls.

1. Introduction

An (n, k, p, t; j)-lottery design is a hypergraph H = (X, B) where X denotes a set of

vertices of order n, and B a set of subsets of X with size |B| = j; furthermore, H should
be k-uniform—that is, |B| = k for any B ∈ B; and for any subset D of X of order p, we
have |D ∩ B| ≥ t for some B ∈ B. More colloquially, X is a set of balls labelled 1 to n,
and B is a set of j tickets each containing k of these numbers, such that for any draw
D of p distinct balls from X, we can find at least one ticket B ∈ B which matches D in
at least t places. Mostly because of a consequence of its application to the UK national
lottery, this paper is concerned with finding the minimum value L(n, k, p, t) of j when
k = p = 6 and t = 2.
In [BR98], the numbers L(n, 6, 6, 2) are calculated for n ≤ 54; however, the proof con-
tains some gaps. We correct and refine the methods of [BR98] both theoretically and
computationally, with the following result:
Main Theorem. The values of L(n, 6, 6, 2) for n ≤ 70 are listed in Table 3.

The proof of the theorem has two parts. One part is to supply a (n, 6, 6, 2; j)-lottery
design with j taking the claimed value for L(n, 6, 6, 2) in Table 3; the other, much harder
part, is to show that there is no lottery design using fewer blocks (i.e. tickets). The
first part we achieve by describing for each n a design constructed as a disjoint union
of covering designs—see Section 3.1 for the definition. We discovered that our upper

E-mail addresses: david.cushing@manchester.ac.uk, david.i.stewart@manchester.ac.uk.

* Corresponding author
1
2 CUSHING AND STEWART

bounds had been found already† but supplied without any rationale; by contrast, the
constructions in Table 3 are completely transparent.
Most of this paper is dedicated to the second part of the proof: finding tight lower bounds,
the majority of which are new. On rare occasions, we do get lucky by using a general
result. The Handbook of Combinatorial Designs [CD07, §32] gives the following theorem
[FSZ96, Thm. 1] as a highlight, which furnishes us with a highly useful lower bound.
Theorem 1.1 (Furedi–Székely–Zubor). We have
p−1  !
1 X ai − 1
L(n, k, p, 2) ≥ · Pp−1
min ai .
k i=1 ai =n i=1
k−1

Sometimes this lower bound for L(n, 6, 6, 2) is matched by an upper bound coming from
covering designs and so L(n, 6, 6, 2) is known without any work.
Corollary 1.2. For 32 ≤ n ≤ 70, there always exists a (n, 6, 6, 2; j)-lottery design with
j minimal which P is a disjoint union of five (ai , 6, 2)-covering designs. Hence there exist
{a1 , . . . , a5 } with ai = n and
X
L(n, 6, 6, 2) = C(ai , 6, 2).
i

Perhaps of most interest here is that we make substantial use of the constraint program-
ming library [COC97] in SICStus Prolog‡ [CM12]. In that respect, this paper comple-
ments our earlier work [CSS23] as another application of constraint programming to pure
mathematics problems; see also [Gen+15] for a novel approach using CP to a question
about permutation groups. It would be completely out of the question to approach this
problem by brute force, which is typically all one has in combinatorics if not deploying

c70
CP: to rule out the possibility that L(70, 6, 6, 2) = 34, one starts with all ∼ 108
6
possible tickets, from which one then needs to check every choice of 34—about 3.4 × 10237
cases, many orders of magnitude bigger than the number of atoms in the observable
universe.

The CP Model. Let us give a little more of an overview of the proof of the lower
bounds for the main theorem, which will be in practice the justification of the model
for the constraint solver we use; the model is designed to achieve an UNSAT conclusion
when looking for an (n, 6, 6, 2; j)-lottery design where j is one less than the value claimed
as best possible in Table 3.
For there is a philosophical principle guiding the design of the model that may be of
general interest to constraint programmers, particularly those working with combinatorial
designs. By way of giving it some contrast, let us start by imagining a naı̈ve model. To
rule out L(70, 6, 6, 2) = 34, one might take a 34 × 6 matrix of variables, each with
domain {1, . . . , 70}—perhaps breaking some symmetry  by constraining
 the matrix to be
c70
lex-chained and increasing—and such that each of the ≃ 108 possible draws has
6
an intersection of size at least two with at least one of the 34 tickets. Just to post all
these the constraints would need the order of terabytes of data.
†https://lottodesigns.altervista.org/
‡A free evaluation copy of SICStus can be downloaded from https://sicstus.sics.se/
 MINIMAL LOTTERY DESIGNS 3

Our alternative approach follows the basic thrust of [BR98]. Let a subset I ⊆ X of the
vertices be called an independent set if no block of the design intersects it more than
once; i.e. an independent set is a collection of balls no pair of which are found on the
same ticket. Then what we do in effect is to localise the constraint problem around a
maximal independent set I. Our model leverages a tension between the room available
in the blocks which intersect I non-trivially—which mostly depends on the number of
such blocks, naturally—and the size of I. The size of I is important, for if there is an
independent set of size 6 then it exhibits a draw for which our tickets fail: by definition
none of our tickets intersects it more than once.
Seen another way, we focus on constraining the topography of the design that surrounds
a well-chosen invariant feature of the design—in this case, a maximal independent set.
Spinning the design around so as to stare closely at I proves to be, in effect, a powerful
symmetry-breaking technique. In fact, it is so good that achieving UNSAT for the global
model requires no labelling of variables that represent the individual vertices of the design;
any such labelling work—which is non-trivial, but tractable—is subsumed by the local
data in Table 2 below.
It seems reasonable to imagine that in another combinatorial setting, a maximal inde-
pendent set might be profitably substituted by another (hyper)graph-theoretic feature;
one would look to localise around this new feature, using CP to do the hard work of
enumerating the possible configurations locally, and then show that none can be made to
work globally.

Remark 1.3. Let us finally describe the more mundane concern that inspired the paper.
In October 2015, the UK national lottery (where k = p = 6) underwent a change in
which the number of balls n was increased from 49 to 59. By way of compensation, a
‘lucky dip’ prize was introduced for matching two balls on a ticket. Consequently, the
value of L(59, 6, 6, 2)—namely 27 by our main theorem—is somewhat significant. For the
interested reader, Table 4 also lists a minimal set of tickets explicitly.
Having observed that the set of tickets we describe below would have netted £1810 in
the lottery draw of 21 June 2023, the authors were motivated to road-test the tickets
in the lottery draw of 1 July 2023; they matched just two balls on three of the tickets,
the reward being three lucky dip tries on a subsequent lottery, each of which came to
nothing. Since a ticket costs £2, the experiment represented a loss to the authors of £54.
This unfortunate incident therefore serves both as a verification of our result and of the
principle that one should expect to lose money when gambling.
For a more philosophical discussion of the National Lottery and its implementation for
supporting charitable causes, we recommend David Runciman’s article in the London
Review of Books [Run96].

2. Definitions and notation

A hypergraph H is a pair (X, B) with X a set and B a set of subsets of X. We will refer
to the elements x ∈ X as vertices and the elements B ∈ B as blocks. The order of H is
the cardinality of the set X. The size of H is the number of blocks; i.e. the cardinality
of the set B. A hypergraph is said to be k-uniform if each B ∈ B has order k. Note that
a 2-uniform hypergraph is a graph: a block B = {x, y} identifies with an edge x − y.
4 CUSHING AND STEWART

Definition 2.1. An (n, k, p, t; j)-lottery design is a k-uniform hypergraph H = (X, B) of

order n and size j such that for any subset D ⊆ X with |D| = p, there is at least one
B ∈ B with |B ∩ D| ≥ t.
An (n, k, p, t)-lottery design is an (n, k, p, t; j)-lottery design in which j is minimal; we
denote this minimal integer by L(n, k, p, t).
Remark 2.2. Thinking of X as a set of balls, B as a set of tickets, and D as a draw, the
definition says that in any draw of p balls, at least one ticket matches at least t of the
balls in D.

In order to avoid vacuous or incorrect statements we shall always insist n ≥ k ≥ t ≥ 2.

We say a block B is an x-block —or that B is incident with a vertex x—if x ∈ B. The
set Bx of all x-blocks is the star of x. We define the function
d : X → Z≥0 ; x 7→ |Bx |
so that d(x) is the degree of x; i.e. the number |Bx | of blocks incident with x. More
generally, if I is any subset S of the vertices, then B S is an I-block if it is an x-block for
some x ∈ I. We let BI = x∈I Bx , and d(I) = x∈I d(x) its degree. We will denote
by di := |d−1 (i)| the number of vertices of degree i in H. We also need to analyse the
multiset of degrees of vertices in a subset I ⊆ X, so we define the function from the
power set P(X) of X to non-decreasing sequences of non-negative integers:
[n
δ : P(X) → (Z≥0 )r ; I 7→ (d(x1 ), . . . , d(xn )), such that d(x1 ) ≤ d(x2 ) ≤ · · · ≤ d(xn ).
r=0
It will be convenient to assume that the elements of I are always listed in order of their
degree, so for example we may have I = {x1 , . . . , x5 } such that δ(I) = (2, 2, 3, 3, 4)
indicating d(x1 ) = 2, . . . , d(x5 ) = 4.
Two vertices x, y ∈ X are adjacent if they are contained in a common block. The set of
all vertices adjacent to x is its neighbourhood N(x). A subset I of X is an independent
set or coclique if no pair of elements in I are adjacent. An independent set is maximal if
there is no independent set J ⊆ X with I ( J.
Remarks 2.3. (i) If I is an independent set in an (n, k, p, t; x)-lottery design, then |I| < p
or else there would be a draw D = I matching at most 1 vertex in any block (noting
t > 1).
(ii) If I is a maximal independent set then we must have BI = X or else there is another
element y ∈ X which is not adjacent to any x ∈ I; which would imply there were a larger
maximal independent set I ∪ {y}.
(iii) It is easy to see that maximal independent sets need not have the same order. For
example, in the graph x − y − z, {y} is maximal independent, but {x, z} is a maximal
independent set of higher cardinality.

A set B′ ⊆ B of blocks is disjoint if B1 ∩ B2 = ∅ for any B1 , B2 ∈ B′ . In the literature,

such a B′ is also referred to as a matching. A block B ∈ B is isolated if B is disjoint from
all other blocks in B. (Of course, each vertex of an isolated block has degree 1.) If d0 = 0
and each vertex of degree 1 is contained in an isolated block, then we say H is segregated.
We will show later that H may be assumed segregated under the hypotheses of our main
theorem. In that case, the interesting analysis reduces to the full subhypergraph induced
 MINIMAL LOTTERY DESIGNS 5

by the vertices of degree at least 2. With that in mind, we give a further couple of
definitions which will prove central to our argument. Let I be an independent set. Then
a toe, or more explicitly I-toe is a vertex z of degree at least 2 appearing in just one block
of BI . For x ∈ I, we say z Sis an x-toe if it is adjacent to x; the set of all x-toes is denoted
Fx , and the union FI := x∈I Fx is the foot or I-foot. (Note that an {x}-toe may fail
to be an I-toe for {x} ( I.) Suppose I = {x1 , . . . , xℓ }, with δ(I) = (d(x1 ), . . . , d(xℓ )),
where d(x1 ) > 1. Then set
 [ [ 
τ (I) = FI ∩ Bx1 , . . . , FI ∩ Bxℓ ,

which denotes the distribution of toes among the x-blocks as x ranges over the vertices
in I.

3. Preliminaries

We use this section to collect a miscellany of results on hypergraphs and lottery designs of
varying generality that we use in the proof of the main theorem. Our strategy is heavily
influenced by the paper [BR98] and we use most of its results in one form or another.
However, we noticed a number of infelicities among the statements and proofs in [BR98]
and so we take the opportunity here to make some corrections. Happily, it follows this
paper is largely self-contained.

3.1. Upper bounds. There are several websites that collect information about the val-
ues of L(n, k, p, t)§; typically one finds there is much better information known about
upper bounds than lower bounds, though often little about how these were arrived at.
Mostly they can be generated from covering designs.
An (n, k, t)-covering design is a k-uniform hypergraph H = (X, B) such that every subset
of X of size t appears as a subset in at least one block of B; we assume n ≥ k ≥ t.
Define C(n, k, t) as the minimal size of an (n, k, t)-covering design. Obviously, an (n, k, t)-
covering design is equivalently an (n, k, t, t)-lottery design, so L(n, k, p, t) ≤ C(n, k, t).
Lemma 3.1. We have
p−1
!
X
L(n, k, p, 2) ≤ Pp−1
min C(ai , k, 2) .
i=1 ai =n
i=1

Proof. Let Hi = (Xi , Bi ) be (ai , k, 2)-covering designs of size C(ai , k, 2) such that X =
F p−1
i=1 Xi , and let D be a draw of p vertices. Then at least two vertices of D lie in at least
one Xi , and there is a block B of Bi containing those two vertices. 

Lemma 3.1 can be deployed using the entries from Table 1. The table lists upper bounds
for C(n, 6, 2) for n ≥ 6 which were harvested from https://www.dmgordon.org/cover/;
these upper bounds are all known to be sharp except when n = 23 or 24.
Secondly, it is useful to know that lottery numbers increase mononotonically with n.
Lemma 3.2. We have L(n, k, p, t) ≤ L(n + 1, k, p, t).
§https://lottodesigns.altervista.org/ is one of the most up to date
6 CUSHING AND STEWART

n C(n, 6, 2) ≤ n C(n, 6, 2) ≤
6 1 17 12
7 3 18 12
8 3 19 15
9 3 20 16
10 4 21 17
11 6 22 19
12 6 23 21
13 7 24 22
14 7 25 23
15 10 26 24
16 10 27 27
Table 1. Upper bounds for C(n, 6, 2)

Proof. Take an (n + 1, k, p, t; j)-lottery design H = (X, B) with |B| = j. Pick x ∈ X

and construct j subsets C of X \ {x} from those of B by replacing x ∈ B with any other
vertex of X \ B, where necessary. Then it is clear that the hypergraph H0 = (X \ {x}, C)
is an (n, k, p, t; j)-lottery design. 

3.2. Reductions and constraints.

Lemma 3.3. Let H = (X, B) be an (n, k, p, t; j)-lottery design S with j ≥ n/k. Then
there exists an (n, k, p, t; j)-lottery design H0 = (X, B0 ) with B0 = X; i.e. there are no
elements of degree 0.

Proof. Let H be a counterexample with d0 > 0 minimal. Suppose x ∈ X has degree 0.

Since jk ≥ n, there must be y ∈ X with d(y) ≥ 2. Suppose y ∈ B for some block B of
B and set B0 = (B \ {y}) ∪ {x}. Now set H0 = (X, B0 ), where B0 is B with the block
B replaced by B0 . Then H0 is a k-uniform hypergraph of order n and size j. If D is
any subset of X of order p, then either there is C ∈ B0 with |C ∩ D| ≥ t or we may
assume |B ∩ D| = t, y ∈ D and |B0 ∩ D| = t − 1. This implies also x 6∈ D; but then the
alternative draw (D \ {y}) ∪ {x} cannot intersect a block of B in t elements. 
Lemma 3.4. If H = (X, B) is an (n, k, p, t; j)-lottery design with n ≥ k(p − 1) and
d0 = 0, then there exists a segregated (n, k, p, t; j)-lottery design.

Proof. Suppose there are r isolated blocks in H. Then taking one vertex from each yields
an independent set I, so r ≤ p − 1 by Remarks 2.3(i). If r = p − 1 then the isolated
blocks supply all kr = k(p − 1) vertices of X and the statement holds.
Suppose r = p − 2; then there are n − k(p − 2) elements not in isolated blocks. A draw
of order p containing one vertex from each isolated block together with two non-isolated
vertices can only intersect a non-isolated block in at least t places. Thus the non-isolated
blocks must between them contain every pair of the non-isolated vertices. This means
that each appears at least twice, or n − k(p − 2) = 2 and they both appear exactly once.
But the latter says they are themselves in an isolated block, a contradiction.
Hence we may assume r ≤ p − 3, leaving at least 2k elements not in isolated blocks. Let
B be a non-isolated block and assume that there are x, y ∈ B with d(x) = 1 and d(y) > 1.
We modify H to give a lottery design H0 with d(y) = 1. By an evident induction, this
implies the existence of the required design.
 MINIMAL LOTTERY DESIGNS 7

Let B = B1 , . . . , Bℓ be the blocks containing y. For 2 ≤ i ≤ ℓ, find a non-isolated element

zi such that zi 6∈ Bi ; this is possible since there are at least 2k non-isolated elements.
Form Ci by replacing y with zi and let C1 = B1 . Then we claim we get a new (n, k, p, t; j)-
lottery design H0 = (X, C) with d0 = 0 by letting C = (B \ {B1 , . . . , Bℓ }) ∪ {C1 , . . . , Cℓ }.
To prove the claim, take a draw D and assume D does not intersect any block C ∈ C in
at least t elements. Then we may assume D contains y, |D ∩ Bi | = t for some 2 ≤ i ≤ l
and |D ∩ Ci | = t − 1. Furthermore, since d(x) = 1, if x ∈ D, then D ∩ B1 = D ∩ C1 has
at least t elements, so we may assume x 6∈ D. Then replacing y with x in D gives a draw
D0 which intersects no block of B in at least t elements. 

The above results are essentially the same as [BR98, Lem. 3.2, Thm. 3.5]. In between
is [BR98, Lem. 3.4] which shows (correctly) that given an (n, k, p, 2)-lottery design with
n > k(p − 2), then there is another with a maximal independent set of size p − 1. It is
combined with the above two results to claim the existence of a lottery design satisfying
the conclusions of all three results. Unfortunately the methods of proof go by altering the
degrees of vertices in the design, and it is unclear whether this can be done compatibly.
There is a further issue in the proof of [BR98, Prop. 4.6] where it incorrectly assumed
that an independent set I with d2 (I) maximal can be extended to an independent set of
maximal cardinality.
We resolve these issue in Proposition 3.9 below, with a stronger result. As in [BR98],
we make use of Shannon’s bound [Sha49] on the chromatic number of a graph, though
we get better results by using a sharpness result due to Vizing. (Both Shannon’s and
Vizing’s theorems are given a good exposition in [SS09].)
Let G = (V, E) be a finite undirected graph possibly with multiple edges between distinct
vertices but with no loops. A c-edge colouring of G is an assignment of a colour to each
edge in G such that no two adjacent edges have the same colour and at most c different
colours are used. The chromatic index χ′ (G) of G is the smallest integer c such that G
admits a c-edge colouring. From the definition it follows immediately that the maximum
degree ∆(G) is a lower bound for the chromatic index. In fact,
Theorem 3.5 (Shannon’s bound). We have χ′ (G) ≤ 32 ∆(G) .
 

For x, y ∈ V , let µG (x, y) denote the number of edges between x and y. Then a Shannon
  d ≥ 2 is a graph d+1
graph of degree G consisting of three vertices x, y, z such that µG (x, y) =
µG (y, z) = d2  and

µ
 G (x, z) = 2
. For a Shannon graph of degree d we have ∆(G) = d
′ 3
and χ (H) = 2 d , so that the bound in Theorem 3.5 is sharp. More generally:

Theorem 3.6 (Vizing). Suppose χ′ (G) = 23 ∆(G) where ∆ = ∆(G) ≥ 4. Then G

 
contains a Shannon graph of degree ∆ as a subgraph.

For our situation we need a dual version for hypergraphs. Let H = (X, B) be a hypergraph
with blocks of order at most k and let H0 = (X0 , B0 ) of H be a subhypergraph. We say
H0 is k-Shannon if B0 = {B1 , B2 , B3 }, X0 = B1 ∪ B2 ∪ B3 , there is at most 1 vertex
 in
k k+1
X0 of degree not 2, and where |B1 ∩ B2 | = |B2 ∩ B3 | = 2 and |B1 ∩ B3 | = 2 . If
k = 2m then this means there are 3m vertices in X0 and H = H0 ⊔ H1 is a disjoint union
of H0 with another subhypergraph H1 . If k = 2m + 1 then there are 3m + 1 vertices of
degree 2 and at most one further vertex v, where only v may appear in blocks outside of
B0 .
8 CUSHING AND STEWART

Proposition 3.7. Let H = (X, B) be a hypergraph whose blocks B ∈ B are of order at

most k ≥ 3 and suppose H contains precisely s distinct k-Shannon subhypergraphs. Then
there exists an independent set I containing
&  '
d2 − 3k+1

s
s+  3k  2
2
−1
vertices of degree 2.

Proof. Let H0 = (X0 , B0 ) be the subhypergraph of H induced by the vertices not con-
tained in k-Shannon subhypergraphs. The sizes of the blocks of H0 are still at most of
size k. Furthermore H0 contains no k-Shannon subhypergraphs. - Form a graph G whose
vertex set is B0 and there is an edge between B1 and
 B2 for each element x ∈ B1 ∩ B2
3k+1
of degree 2. Note that G has at most d2 − 2
s edges, and contains no Shannon
subgraphs of degree k. Suppose
 3k ∆(G) ≤ 3. Then Theorem 3.5 implies the existence of
a c-colouring with c ≤ 4 ≤ 2 − 1. Otherwise we may apply Theorem 3.6 to find a
c-colouring with c ≤ 32 k − 1.
So in any case, there must exist a set of edges with size at least
&  ' &  3k+1  '
d2 − 3k+1

2
s d 2 − s
≥  3k  2
c 2
−1
having the same colour. Any monochromatic set of m edges of G represent m independent
vertices of H0 of degree 2.
Observe that every k-Shannon subhypergraph S of H has at least one vertex of degree 2
which is not adjacent to any vertex outside of S; adding these s vertices gives the lower
bound in the theorem. 

An elementary rearrangement of the bound above yields the following.

Corollary 3.8. With the hypotheses of the proposition, let δ2 be the maximum number
of independent vertices in H of degree 2 and let k = 2m + ρ with ρ ∈ {0, 1}. Then
  
3k
d2 ≤ δ2 − 1 + (1 + ρ)s
2
Proposition 3.9. Let H = (X, B) be a segregated k-uniform hypergraph with |X| = n,
|B| = j, d1 = kr, k = 2m + ρ and ρ ∈ {0, 1}. Suppose H contains s distinct k-Shannon
subhypergraphs. Then there is an independent set I0 ⊆ X containing r vertices of degree
1 and &  '
d2 − 3k+1

s
κ := s +  3k  2
2
−1
vertices of degree 2. Furthermore, I0 can be extended to an independent set I ⊆ X of
order π ≥ κ + r whose vertices have degree at most 3, provided
(*) 4n − jk − (2 − m) s − (3k + m − 2)(π − 1) + (m − 2)r > 0.

Before giving the proof of the proposition, let us make some elementary observations that
are used several times in the sequel.
 MINIMAL LOTTERY DESIGNS 9

Let H = (X, B) be a k-uniform hypergraph with |X| = n and |B| = j. Recall di is the
number of vertices having degree i. Clearly

X
(1) di = n.
i≥0

F
Let B denote the multiset Bi , which contains the vertices of the hypergraph counted
with their multiplicities in the blocks B. As there are j blocks we have |B| = jk. Of
course a vertex x will occur in exactly d(x) of the blocks, and so:

X
(2) idi = jk.
i≥1

Proof of Proposition 3.9. The existence of I0 is immediate from Proposition 3.7 and seg-
regation. Moreover, we may assume s of vertices of I0 each live in distinct k-Shannon
subhypergraphs, whose union accounts for at most ⌊ 3k+1 2
⌋ · s vertices. Now take I ⊇ I0
maximal subject to d(I) ⊆ {1, 2, 3} and assume for a contradiction that |I| ≤ π − 1. let
δi denote the number of vertices of I of degree i; note that δ1 = r, again by segregation.
We now bound from above and below the number d2 + d3 of vertices in X having degrees
2 or 3.
Let J ⊆ I denote set of vertices not in isolated blocks. Then BJ contains at most
 
3k
(2k − 1)(δ2 − s) + s + (3k − 2)δ3
2
S
distinct elements. Now if there were a vertex of degree 2 or 3 not in BJ , then I was
not maximal. Therefore,
 
3k
d2 + d3 ≤ (2k − 1)(δ2 − s) + s + (3k − 2)δ3 ,
2
 
3k
≤ (2k − 1)(δ2 − s) + s + (3k − 2)(π − 1 − r − δ2 ),
2
since δ1 + δ2 + δ3 ≤ π − 1,
  
3k
≤ (1 − k)δ2 + − 2k + 1 s + (3k − 2)(π − 1 − r),
2

2−k

(3) ≤ (1 − k)δ2 + s + (3k − 2)(π − 1 − r)
2
F
On the other hand, consider the multiset B = B∈B B, of order jk. The I-blocks
contribute exactly δ1 k + 2δ2 k + 3δ3 k of these elements. Since there are 2d2 + 3d3 elements
of degrees 2 or 3, there are 2δ2 k + 3δ3 k − 2d2 − 3d3 elements of B of order at least 4
coming from the I-blocks. The remaining (j −δ1 −2δ2 −3δ3 ) blocks all consist of elements
of order at least 4. Thus the multiset |B≥4 | of all elements of degrees 4 and above has
order
|B≥4 | = (j − δ1 − 2δ2 − 3δ3 )k + 2δ2 k + 3δ3 k − 2d2 − 3d3 = jk − rk − 2d2 − 3d3 .
10 CUSHING AND STEWART
P
Since |B≥4 | = i≥4 idi , we get
X jk − rk − 2d2 − 3d3
di ≤ .
i≥4
4
So
X jk − rk − 2d2 − 3d3
n= di ≤ rk + d2 + d3 + .
4
Rearranging gives d2 + d3 ≥ 4n − jk − d2 − 3rk, which combines with (3) to give

2−k

(1 − k)δ2 + s + (3k − 2)(π − 1 − r) ≥ 4n − jk − d2 − 3rk;
2

2−k

i.e. d2 + (1 − k)δ2 ≥ 4n − jk − s − (3k − 2)(π − 1) − 2r.
2
Now using Corollary 3.8 we get
   
2−k

3k
δ2 − 1 + (1 + ρ)s + (1 − k)δ2 ≥ 4n − jk − s − (3k − 2)(π − 1) − 2r
2 2
  
2−ρ
 
k
δ2 ≥ 4n − jk − + 1 + ρ − m s − (3k − 2)(π − 1) − 2r
2 2
 
k
δ2 ≥ 4n − jk − (2 − m) s − (3k − 2)(π − 1) − 2r.
2
Using δ1 + δ2 ≤ π − 1, with equality if and only if δ3 = 0, then
 
k
(π − 1 − r) ≥ 4n − jk − (2 − m) s − (3k − 2)(π − 1) − 2r;
2
so
4n − jk − (2 − m) s − (3k + m − 2)(π − 1) + (m − 2)r ≤ 0,
which is a contradiction, proving the proposition. 

The following results are all used to give constraints to Prolog. The first two respectively
bound above and below the number of isolated blocks.
Lemma 3.10. Let (X, B) be a segregated (n, k, p, 2; j)-lottery design. Suppose that B has
r isolated blocks. Then, 
2n − jk

r≥ .
k
P
Proof. We have jk = d1 + i≥2 idi ≥ d1 + 2(n − d1 ). Write d1 = rk and rearrange to get
the formula above. 
Lemma 3.11. Let H = (X, B) be a segregated (n, k, p, t; j)-lottery design with k = 2m,
at least r isolated blocks and at least s disjoint k-Shannon subhypergraphs. Then
L(n − 2mr − 3ms, k, p − s − r, t) ≤ j − r − 3s

Proof. Suppose B1 , . . . , Br are isolated and H1 . . . Hs are the disjoint k-Shannon sub-
hypergraphs of H, with Hi = (Xi , {Ci1, Ci2 , Ci3 }). Let Y be the remaining vertices
inducing a subhypergraph H0 = (Y, B0 ) of H where |B0 | = j − r − 3s. Fix one vertex
vi ∈ Bi for 1 ≤ i ≤ r and vr+1 . . . vr+s in each of the Ci1 with 1 ≤ i ≤ s. For any choice
{vr+s+1 , . . . , vp } of vertices from Y , the draw D = {v1 , . . . , vp } intersects with some B ∈ B
 MINIMAL LOTTERY DESIGNS 11

in at least t vertices. By construction of D, B is neither isolated nor one of the Cij . But
this means B must match t of the remaining p − r − s elements of D. Hence H0 is an
(n − 2mr − 3ms, k, p − s − r, t; j − r − 3s)-lottery design, which implies the inequality as
shown. 
Lemma 3.12. Let H be a segregated k-uniform hypergraph. Then
d2 ≥ 3n − 2rk − jk
P P
Proof. We recall di = n and idi = jk, which implies
X X
jk − n = d2 + (i − 1)di ≥ d2 + 2 di = −2d1 − d2 + 2n. 
i≥3

Lemma 3.13. Let (X, B) be a k-uniform hypergraph with maximal independent set I.
Then 
n−p+1

|BI | ≥ .
k−1
S
Proof. We must have BS I = X or I is not maximal. For x ∈ I, two blocks B, C ∈ Bx
intersect in at least x so | Bx | ≤ (k − 1)|Bx | + 1. Since |I| ≤ p − 1, then summing over
x ∈ I yields n ≤ (k − 1)|BI | + p − 1. 

3.3. Excess, toes and webbings. For the values of (n, k, p) under consideration, one
tends to find L(n, k, p, 2) ∼ n/2. Thus, on average, the degree of a vertex in an (n, k, p, 2)-
lottery design is about 2. The next definition follows [BR98] with a view to bounding
the extent of departure from this average value.
Definition 3.14. For a set of vertices Y ⊆ X, the excess of Y is the sum
X
E(Y ) = (i − 2) · |d−1 (i) ∩ Y |.
i>2

P
Note that if Y = X, we get E(X) = i>2 (i − 2) · di . The following gives an easy
characterisation of E(X).
Lemma 3.15. Let H = (X, B) be a segregated hypergraph with r isolated blocks. Then
E(X) = jk + rk − 2n.
P P
Proof. We have jk = idi . Since n =
di , we get
X
jk − 2n = −d1 + (i − 2)di = −d1 + E(X). 
i≥3

The possible number of toes is constrained by the value of the excess E(X), in a manner
we now describe. First, the following is [BR98, Lem. 4.7] after the removal of a significant
typo.
Lemma 3.16. Let (X, B) be a segregated (n, k, p, 2; j)-lottery design with maximal inde-
pendent set I and FI its foot. Suppose further that B has r isolated blocks. Then,
|FI | ≥ 2n − 2p + 2 − (k − 1)(|BI | + r).
12 CUSHING AND STEWART
S
Proof. As I is maximal, we have BI = X. The multiset
G
R := B \ {x}
x∈I,d(x)>1,B∈Bx

contains the kj − rk − |I| vertices which are neither isolated nor contained in I, and
by definition, the toes are the elements of multiplicity 1 in R. Therefore each of the
remaining kj − rk − |I| − |FI | vertices appears at least twice in R. Since |R| = (k −
1)(|BI | − r), we have
|FI | + 2(n − rk − (|I| − r) − |FI |) ≤ (k − 1)(|BI | − r).
Rearranging and using |I| ≤ p − 1, we get the inequality as claimed. 

Now suppose x ∈ I for I a maximal independent set, with Fx the set of x-toes. Let us
assume
(*) |Fx | ≥ k.
Then it follows there are at least two blocks B, C ∈ Bx , say, containing (necessarily
distinct) toes; say y ∈ B and z ∈ C. If y and z were not adjacent, then replacing x with
y, z in I would yield a larger independent set, a contradiction. Thus there is a block W
with y, z ∈ W . We refer to such blocks as webbings. Formally, W is an x-webbing if
W 6∈ BI and W contains distinct x-toes; the set of x-webbings is later denoted Wx . Note
that under the assumption (*), each toe appears at least once in a webbing, so that it
must have degree at least 2.
More precisely, suppose
P there are τi toes in distinct x-blocks Bi with τ1 ≥ τ2 · · · ≥ τs ≥ 1.
Then each of the i<j τi τj pairs of toes must appear in some webbing. In the case k = 6
and |Fx | ≥ 7, one can see that some toes must have degree at least 3, for example. This
implies non-trivial lower bounds on the excess E(Fx ) ≤ E(X).
Lemma 3.17. Let x ∈ X with x of degree 2 or 3 and Fx the set of x-toes. The table
below gives minimum values of E(Fx ) in terms of |Fx |.

|Fx | ≤ 5 6 7 8 9 10 11 12 13 14 15
min(E(Fx )) 0 0 2 3 7 10 11 12 20 25 27
Table 2. Minimal excesses implied by numbers of toes

If moreover Fx is known to contain no elements of degree 2, then min(E(Fx )) ≥ |Fx |.

Proof. For the second statement of the lemma, just observe that any x-toe of degree at
least 3 contributes at least 1 to E(Fx ).
For the table itself, suppose |Fx | = τ1 + τ2 + τ3 is a partition of |Fx | into summands of size
at most 6. If |Fx | ≤ 6, then one webbing W suffices to cover all toes, and so the minimum
possible excess of 0 is a achieved by a configuration of x-blocks and one webbings in which
each toe appears just twice. Otherwise suppose there are w > 1 webbings, containing
each of the τ1 τ2 + τ1 τ3 + τ2 τ3 pairs of toes, so that
 
τ1 τ2 + τ1 τ3 + τ2 τ3
.
3
 MINIMAL LOTTERY DESIGNS 13

is an upper limit for w.

To save some time, we used the powerful linear programming solver Gurobi to solve the
following problem. let M be a w × |Fx |-matrix of variables taking values in 0 and 1, with
the rows representing webbings and a 1 appearing in the (i, j)-th entry if a toe labelled
j is in the ith webbing. Since |Fx | > 6, we know that toe j appears once in the x-blocks
and at least once in the webbings, so E(Fx ) + |Fx | is the sum S of all entries of the M.
Furthermore, the rows of M must all sum up to integers less than or equal to k = 6,
and columns j1 and j2 must have scalar product at least 1 whenever j1 and j2 come from
different parts of the partition
{1, . . . , n} = {1, . . . , τ1 } ∪ {τ1 + 1, . . . , τ1 + τ2 } ∪ {τ1 + τ2 + 1, . . . , τ1 + τ2 + τ3 }.
We ask Gurobi to minimise the sum S subject to these constraints, and it results in the
table in the lemma.
Since Gurobi only gives answers up to a percentage accuracy, its output does not amount
to a proof of optimality, and so we wrote some additional Prolog code to check that the
values of min(Fx ) one below those in the table are infeasible.¶ 
Remarks 3.18. (i) This improves the bound in [BR98, Table 1] for min(|Fx |) when |Fx | =
13 from 16 to 20. Since Gurobi outputs a feasible configuration of webbings for each
value of |Fx |, we know that the minima can be achieved.
(ii) Establishing the values in Table 2 is by far the most computationally intensive task
required in the paper—for the value n = 15, the solver took about 6 hours to rule out
the possibility of an excess of 26. By contrast, the main Prolog program that uses this
precomputed data only takes about 2 minutes to do all the cases from n = 30 to n = 70
on an M1 Macbook Air, running Sicstus Prolog (currently only availabel on an Intel
build) in emulation mode. It is highly likely another CP solver running natively on a
better computer would do this in a fraction of the time.

The following rather specific two results lead to some surprisingly effective constraints.
The first is an easy check left to the reader.
Lemma 3.19. Let H = (X, B) be a hypergraph and I ⊆ X an independent set. Let
x, y ∈ I with d(x) = 2, d(y) = 3 and z another vertex of degree 2 adjacent to x and
y. Suppose there exists a toe w of degree 2 adjacent to x but not adjacent to z. Then
I ′ = I \ {x, y} ∪ {w, z} is an independent set.
Lemma 3.20. Let H = (X, B) be a hypergraph and I ⊆ X an independent set of maximal
order. Let x, y ∈ I with d(x) = 2, d(y) = 3 and z another vertex of degree 2 adjacent to
x and y. Suppose there exists a toe w adjacent to x but not adjacent to z. Let v be a toe
adjacent to y but not adjacent to z. Then w and v are adjacent.

Proof. Suppose w and v are not adjacent. Then I ′ = I \ {x, y} ∪ {v, w, z} is independent
of larger order than I. 

In the following let τr = |τ −1 (r)| be the number of vertices x in I such that |Fx | = r. Say
an independent set I is 2-max if it is of maximal order and contains a maximal order
subset of independent vertices of degree 2.
¶Code is available at github.com/cushydom88/lottery-problem
14 CUSHING AND STEWART

Lemma 3.21. Let H = (X, B) be a (n, 6, 6, 2; j)-lottery design containing r isolated

blocks and s Shannon subhypergraphs. Let I be a 2-max independent set whose vertices
have degree at most 3, containing δ2 vertices of degree 2. Then

6j − 3n + s + 8δ2 + 12r ≥ 7τ13 + 11τ14 + 12τ15 .

Proof. For Y ⊆ X, let F(Y ) = i≥4 (i − 3)|d−1(i) ∩ Y |. In particular,

P

X
F(X) = (i − 3)di = E(X) − n + rk + d2 = 6j + 12r − 3n + d2 ,
i≥4

where we use Lemma 3.15. Let x ∈ I with τ (x) = 13. Then all x-toes have degree at
least 3: one observes that each toe t ∈ Fx is opposite at least 8 ≥ 6 others; thus there
must be at least two x-webbings containing. From Lemma 3.17 we have E(Fx ) ≥ 20.
Thus
F(Fx ) ≥ E(Fx ) − 13 ≥ 20 − 13 = 7.
Similar arguments for τ (x) = 14 or 15 yield

F(X) ≥ 7τ13 + 11τ14 + 12τ15 .

Since I is 2-max, Corollary 3.8 gives d2 ≤ 8δ2 + s and we are done. 
Lemma 3.22. Let H = (X, B) be a (n, 6, p, 2; j)-lottery design containing r isolated
blocks and s Shannon subhypergraphs. Let I be an independent set of order p − 1 and
take x ∈ I with d(x) = 3, τ (x) = 12 and E(Fx ) ≤ 14. Then at least one of the following
holds:
(1) there exists y ∈ X with d(y) = 3 such that I ′ = I \ {x} ∪ {y} is independent with
τ (y) ≤ 11;
(2) there exists an (n − 14, 6, p − 2, 2; j − 7)-lottery design.

Proof. Assume (1) does not hold.

It can be shown that the hypotheses imply, up to isomorphism, that

Bx = {{x, 1, 2, 3, 4, }, {x, 5, 6, 7, 8, }, {x, 9, 10, 11, 12, }}, and

Wx ⊇ {{1, 2, 5, 6, 9, 10}, {1, 2, 7, 8, 11, 12}, {3, 4, 5, 6, 11, 12}, {3, 4, 7, 8, 9, 10}},
where Fx = {1, . . . , 12}. Since E(Fx ) ≤ 14, at least one of the toes in Fx must have degree
3; say, with label 1. Now B1 = {{1, x, 2, 3, 4, z}, {1, 2, 5, 6, 9, 10}, {1, 2, 7, 8, 11, 12}}. Since
(1) does not hold, it follows that z is a toe. Moreover,

W1 ⊇ V1 := {{x, z, 5, 6, 7, 8}, {x, z, 9, 10, 11, 12}, {3, 4, 5, 6, 11, 12}, {3, 4, 7, 8, 9, 10}}.

Hence the vertices Y := {x, z, 1, 2 . . . , 12} induce a subhypergraph of H containing a

(14, 6, 2, 2; 7)-lottery design with blocks C = B1 ∪ V1 . For each block B ∈ B \ C, replace
any occurrence of a vertex in Y with a vertex in X \ (Y ∪ B). For any draw of size p − 1
from X \ Y , create one of size p by appending the vertex 1 to it. This must intersect
a block of B \ C in at least 2 vertices and hence gives the lottery design as specified in
(2). 
 MINIMAL LOTTERY DESIGNS 15

4. Proof of the main theorem

We now indicate how the constraints established in the previous section are transcribed
into Prolog code for the constraint solver to establish the theorem on our behalf. In
summary, the CP solver works upwards through values of n, first finding the best upper
bound on the size of B = j arising from a disjoint union of five covering designs; often
the solver discovers that j is the same as the previous number L(n − 1, 6, 6, 2) and from
Lemma 3.2, we know this must be optimal. Otherwise the CP solver assumes the existence
of a lottery design with |B| = j − 1 and looks to bind variables to values describing
viable configurations for the blocks connected to a maximal independent set I; in order
words. the I blocks. By configuration, we mean:
(1) the degrees of the vertices in the independent set—in other words, the number
of I-blocks incident with each vertex; these values must obey the constraints
established above, for example Proposition 3.7.
(2) the distribution of toes among the I-blocks, which must obey the constraints
established in Section 3.3.
In each case, the solver returns unsat and the theorem is proved. After we give a detailed
account of the Prolog code in the next section, we give an illustrative example in case
n = 47,

4.1. SICStus Prolog code. The code is available to download from github.com/cushydom88/lottery
which implements the constraints described in the previous section. We give a description
of the strategy and its functionality.
The user first loads SICStus Prolog and consults the file lottery.pl through the command
?- ['$PATH_TO_DIRECTORY/lottery.pl'].

Then one queries Prolog at the command line by asking it to solve (for any unbound
variables) in a conjunction of predicates. The following is an example of the output
produced from the main predicate in our code:
| ?- lottery_numbers_in_range( 69, 71).
% L(69,6,6,2) = 35
% L(70,6,6,2) = 35
% Conjecture L(71,6,6,2) = 38.
% Bad RSTuples [R,S,A,B]:
% [0,0,0,32]
% [0,1,9,33]
% [0,2,18,34]
% [1,0,0,24]
% Delta(I) exceptions [R,S,D2L,D2U,Delta]:
% [0,0,0,0,[3,3,3,3,3]]

Figure 1. Example output

The principal predicates are:

lottery_numbers_in_range( NMin,NMax). This predicate writes output to the terminal of
the form given in Fig. 1; i.e. it works sequentially with n from the value of NMin to the
value of NMax either outputting a line stating the value of L(n, 6, 6, 2) or a conjectured
16 CUSHING AND STEWART

value of it, which is correct modulo a list of exceptional cases which could perhaps be
checked by hand. The conjectured value for NMin is first computed from scratch, using
a lower bound of 1; for efficiency, from that point onwards, it then passes the (in some
cases, conjectured) value of L(n, 6, 6, 2) as a lower bound for L(n + 1, 6, 6, 2), invoking
Lemma 3.2.
upper_bound( N,Guess,UB ) is called by the previous predicate, and is checked recursively.
It holds when N = n and the integer Guess can be achieved as a sum of at most p − 1 = 5
values C(ai , 6, 2) in Table 1. Then UB is bound to Guess. Otherwise it is declared that
upper_bound( N,Guess+1,UB ) should hold.
This predicate is first asserted with Guess as the (conjectured) value jn−1 of L(n−1, 6, 6, 2).
In many cases, it turns out that jn−1 can be achieved as a sum of at most 5 values
C(ai , 6, 2) and so UB is bound to jn−1 . In that case, by Lemma 3.2, we conclude im-
mediately L(n, 6, 6, 2) = L(n − 1, 6, 6, 2)—modulo any previous cases that remain to be
checked by hand.
Otherwise, UB > jn−1 and we seek to rule out L(n, 6, 6, 2) = UB−1. Assume therefore,
in search of a contradiction, that there is a lottery design H = (X, B) with |B| = UB−1.
Then further predicates are engaged which either generate the sought contradiction, or
progressively collect a list of information about possible cases that cannot be ruled out.
bound_isolated_blocks_and_num_shans( N,UB,Rs,RSPairs ) takes the value of UB from the
above predicate and binds RSPairs to a list of plausible pairs (r, s)where r = d1 /6 is the
number of isolated blocks in H, and s is the number of Shannon subhypergraphs in H—a
pair will be determined as plausible by the following: Assume H is a (n, 6, 6, 2; UB − 1)-
lottery design with (r, s) its number of isolated blocks and Shannon subhypergraphs.
Then r + s ≤ 5 (or else there exists I of order 6); r must satisfy the inequality in
Lemma 3.10; and (r, s) must satisfy the inequality in Lemma 3.11, implying there exists
a (n − 6r − 6s, 6, 6 − s − r, 2; UB − 1 − r − 3s)-lottery design which in turn constrains r
and s by appeal to Theorem 1.1.
get_deltaI_exceptions( N,UB,MinNumIBlocks,[R,S],DeltaExceptions ). Here we assume that
the bound labelled (*) in Proposition 3.9 holds with π = 5 and consider independent sets
I satisfying its conclusion. We find all possibilities for δ(I) satisfying a long list of
constraints. More specifically, for any given pair [R,S] in RSPairs, this predicate binds
DeltaExceptions to a list whose entries are tuples

DeltaException=[R,S,D2L,D2U,Delta]

where Delta represents a tuple δ(I) satisfying our system of constraints. It is accompanied
by the extra data D2L and D2U, which are lower and upper bounds for the value of d2 —
these arise as by-products of the calculations we describe below. Delta always takes the
following form:

(1) the first r = R elements are 1;

(2) the next s = S elements are 2;
(3) the next q elements are each 2, where q is the minimum value implied by Propo-
sition 3.7;
(4) the remaining 5 − r − s − q elements of Delta are either 2 or 3;
(5) the sum of Delta, equal to |BI |, satisfies the bound in Lemma 3.13 with π = 5;
 MINIMAL LOTTERY DESIGNS 17

(6) letting J be the last 5−r−s elements of I, and DeltaTail the corresponding sublist
δ(J) ⊆ δ(I), then DeltaTail satisfies the predicate can_populate_toes_in_Iblocks
as we describe next.
can_populate_toes_in_Iblocks(N,UB,R,S,DeltaTail,[DeltaTail,D2L,D2U]). This binds a vari-
able Excess to the value E(X) = 6(UB − 1 + R) − 2N (see Lemma 3.15), and a variable
MinToes to the lower bound on |FJ | supplied by Lemma 3.16. Suppose there are δ3 vertices
in I of degree 3. Each contributes 1 to E(X), and since these vertices are not toes by
definition, the contribution to the excess E(X) from toes must be at most E(X) − δ3 .
Hence a variable FootExcess is created and bound to Excess-NumThrees.
populate_toes_in_Iblocks( DeltaTail,MinToes,Excess,Vs ) binds Vs to a solution of a con-
straint problem to determine τ (J); in other words, to determine viable distributions of
toes among the J-blocks. (If it fails, the case (Delta,R,S) will not feature in the list
DeltaExceptions.) The constraint problem is as follows:

(1) Vs is a sequence of variables taking values (τ (x1 ), . . . , τ (x5−r−s )) where J =

{x1 , . . . , x5−r−s } and the P
ith entry in DeltaTail is d(xi );
(2) the total number of toes τ (J) represented by sum(Vs) is at least the calculated
lower bound MinToes;
(3) the sum over 1 ≤ i ≤ 5 − r − s of the minimum values for E(Fxi ) implied by
Lemma 3.17 is at most FootExcess.
The solutions Vs are then compelled to satisfy d3_excess_check, which implements the
constraint Lemma 3.21; and twos_lie_with_twos, which implements the constraints from
Lemma 3.19 and Lemma 3.20. Finally changing_socks implements Lemma 3.22 repeatedly.
get_bad_RS_tuples(N,UB,RSPairs,BadRSTuples1 ). Here we suppose the inequality (*) in
Proposition 3.9 does not hold with π = 5.
This predicate binds BadRSTuples1 to a list of tuples [R,S,A,B,C] where:
(1) [R,S] is a member of RSPairs representing the pair (r, s) such that the bound (*)
in Proposition 3.9 fails, with j = UB − 1;
(2) A is a lower bound for d2 implied by Lemma 3.12; and
(3) B is an upper bound for d2 achieved by setting δ2 = 4 − r in Corollary 3.8.
Take a tuple [R,S,A,B] in BadRSTuples1, and assume it satisfies the bound in Proposition 3.9
with π = 4. Then it is possible to find an independent set I of size 4 with R elements
of degree 1 and at least S of degree 2 and the rest of degree 2 or 3. For every value of
d2 lying between B and C a list of possible values of d3 are calculated. For each such
pair (d2 , d3 ), we then solve a constraint problem to find solutions for δ(I)—or δ2 , which
amounts to the same thing. More specifically, we let DeltaTail represent the last 4 − r − s
entries of δ(I) with δ2 − s of degree 2 and δ3 of degree 3, corresponding to the subset
J ⊆ I. We have |BJ \ J| = 2(δ2 − s) + 3δ3 . These must contain at least one each of the
d2 − 9s vertices of degree 2 not in Shannon subhypergraphs and each of the d3 vertices
of degree 3. Hence we may bound below the size of the I-foot by
|FI | ≥ 2(d2 − 9s + d3 − 4 + r + s) − 10(δ2 − s) − 15δ3
= 2d2 − 6s + 2d3 − 8 + 2r − 10δ2 − 15δ3 .
Now E(FI ) ≥ d3 − δ3 . Finally the predicate populate_toes_in_Iblocks is invoked. If there
are no solutions for any pair (d2 , d3 ), then the tuple is excluded from BadRSTuples1 to form
BadRSTuples.
18 CUSHING AND STEWART

The list BadRSTuples is displayed on the user output stream. (In case n ≤ 70 this list is
empty.)

4.2. Example: n = 47. Suppose n = 47 and the previous value L(46, 6, 6, 2) = 16.
Since a disjoint covering design configuration exists with 17 blocks, we must rule out
the possibility of a (47, 6, 6, 2; 16)-lottery design. So the variables N and UB are bound
to 47 and 17, respectively, Now bound_isolated_blocks_and_num_shans( N,UB,Rs,RSPairs )
binds RSPairs to the list [[0,0],[0,1],[0,2],[0,3],[0,4],[1,0],[1,1],[2,0]] representing
possible pairs (r, s) where r is the number of isolated blocks and s is the number of
k-Shannon subhypergraphs. Fix one such pair, and assume it is possible to take one
vertex from each of the asssociate blocks and complete to an independent set of size 5.
The set of ways of doing this is computed by get_deltaI_exceptions and the possibilities
bound to DeltaExceptions. Assume (r, s) = (1, 1), for example. Take r = 1 vertex
from the isolated blocks, and s = 1 vertex from the k-Shannon subhypergraphs, say
x1 and x2 ; these have degrees 1 and 2 respectively. Now get_deltaI_exceptions uses
Proposition 3.7 to establish that there must exist an independent set I extending {x1 , x2 },
with δ(I) = (1, 2, 2, 2, 2). We now want to see if this can be consistent with the data
in Table 2. Lemma 3.15 implies E(X) = 8, and Lemma 3.16 tells us that there must
be at least 28 I-toes. So populate_toes_in_Iblocks( DeltaTail,MinToes,Excess,Vs ) is run,
with DeltaTail=[2,2,2], MinToes=28, Excess=8, but this is found to be infeasible by the
solver. (The other cases in RSPairs are even easier to dismiss.) Finally, get_bad_RS_tuples
confirms that Proposition 3.9 does always hold with π = 5 for the entries in RSPairs and
so the proof in case n = 47 is complete.

5. Configurations for minimal lottery designs

In all cases for 30 ≤ n ≤ 70, each minimal (n, 6, 6, 2) lottery design is achieved through
a disjoint union of covering designs appearing in Table 3. (There may be several ways
to do this and the table gives just one.) For example, when n = 54, the configuration
(A, A, E, E, E) gives rise to 23 tickets by the disjoint union of two diagrams of type (A)
and three of type (E) from Fig. 2.
Let us be more explicit. Recall the Fano plane, or projective plane of order 2—perhaps
the most well-known finite geometry; this is depicted as (E) in Table 3. It contains 7
‘lines’ (one being represented by a circle) that satisfy the property that any two points lie
in exactly one line, and two lines intersect in exactly one point. Since there are 3 points
on each line, we see in particular that the Fano plane is a (7, 3, 2)-covering design; and
we have made it into a (14, 6, 2)-covering design by having each point represent a pair of
vertices. A set of blocks (tickets) may be read off from diagram (E) by concatenating the
labels on the points in each of the 7 lines. So each diagram (E) contributes 7 blocks to
the minimal design and the (E) diagram accounts for 14 distinct vertices (or balls). On
the other hand, each (A) diagram contributs just one ticket, containing 6 vertices; note
that 54 = 6 + 6 + 14 + 14 + 14 and 23 = 1 + 1 + 7 + 7 + 7. Now, to recover a complete
set of tickets for any given value of n, one may simply write the numbers 1, . . . , n in any
order above a blank set of the 5 appropriate diagrams. We do this for n = 59 in Table 4
below.
Theorem 5.1. Table 3 lists j = L(n, 6, 6, 2) together with configurations described in
Fig. 2 which afford an (n, 6, 6, 2; j)-lottery design.
 MINIMAL LOTTERY DESIGNS 19

(B) 3,4
(A) (1,2,3,4,5,6)
(1,2,3,4,7,8)
(1,2,5,6,7,8)

1,2,3 4,5,6 {∅}

(1,2,3,4,5,6) 1,2
5,6 7,8

(D) 3,4
(C) 1,2,3
(1,2,3,4,5,6)
(1,2,3,7,8,9) 5,6
(4,5,6,7,8,9) 1,2 9,10

(1,2,3,4,9,10)
7,8 (1,2,5,6,9,10)
4,5,6 7,8,9 (1,2,7,8,9,10)
(3,4,5,6,7,8)

(E) 1,2
(1,2,3,4,9,10)
(1,2,5,6,13,14)
(1,2,7,8,11,12)
3,4 5,6 (3,4,5,6,11,12)
7,8 (3,4,7,8,13,14)
(5,6,7,8,9,10)
(9,10,11,12,13,14)
9,10 13,14
11,12

(F) 4,5,6 (1,2,3,4,5,6)

(1,2,3,7,8,9)
(1,2,3,10,11,12)
1,2,3 10,11,12 (4,5,6,7,8,9)
(4,5,6,10,11,12)
(7,8,9,10,11,12)

7,8,9

(G) as in (E) but replacing each occurrence of 14 with a number from 1 to 13 which
leaves a valid ticket.

Figure 2. Ticket configurations

20 CUSHING AND STEWART

n L(n, 6, 6, 2) Configuration n L(n, 6, 6, 2) Configuration

32 7 (A, A, A, A, B) 52 21 (A, C, C, E, E)
33 7 (A, A, A, A, C) 53 22 (A, C, D, E, E)
34 8 (A, A, A, A, D) 54 23 (A, A, E, E, E)
35 9 (A, A, A, B, C) 55 23 (C, C, C, E, E)
36 9 (A, A, A, C, C) 56 24 (C, C, D, E, E)
37 10 (A, A, A, C, D) 57 25 (A, C, E, E, E)
38 11 (A, A, A, A, E) 58 26 (A, D, E, E, E)
39 11 (A, A, C, C, C) 59 27 (B, C, E, E, E)
40 12 (A, A, C, C, D) 60 27 (C, C, E, E, E)
41 13 (A, A, A, C, E) 61 28 (C, D, E, E, E)
42 13 (A, C, C, C, C) 62 29 (D, D, E, E, E)
43 14 (A, C, C, C, D) 63 30 (C, E, E, E, F )
44 15 (A, A, C, C, E) 64 31 (D, E, E, E, F )
45 15 (C, C, C, C, C) 65 31 (C, E, E, E, E)
46 16 (C, C, C, C, D) 66 32 (D, E, E, E, E)
47 17 (A, C, C, C, E) 67 34 (E, E, E, F, G)
48 18 (A, C, C, D, E) 68 34 (E, E, E, E, F )
49 19 (A, A, C, E, E) 69 35 (E, E, E, E, G)
50 19 (A, A, A, A, E) 70 35 (E, E, E, E, E)
51 20 (A, A, A, D, E)
Table 3. Lottery numbers and their configurations

1, 2, 3, 4, 5, 6 9, 10, 11, 12, 13, 14 18, 19, 20, 21, 26, 27 32, 33, 34, 35, 40, 41 46, 47, 48, 49, 54, 55
1, 2, 3, 4, 7, 8 9, 10, 11, 15, 16, 17 18, 19, 22, 23, 30, 31 32, 33, 36, 37, 44, 45 46, 47, 50, 51, 58, 59
1, 2, 5, 6, 7, 8 12, 13, 14, 15, 16, 17 18, 19, 24, 25, 28, 29 32, 33, 38, 39, 42, 43 46, 47, 52, 53, 56, 57
20, 21, 22, 23, 28, 29 34, 35, 36, 37, 42, 43 48, 49, 50, 51, 56, 57
20, 21, 24, 25, 30, 31 34, 35, 38, 39, 44, 45 48, 49, 52, 53, 58, 59
22, 23, 24, 25, 26, 27 36, 37, 38, 39, 40, 41 50, 51, 52, 53, 54, 55
26, 27, 28, 29, 30, 31 40, 41, 42, 43, 44, 45 54, 55, 56, 57, 58, 59
Table 4. One set of 27 tickets for n = 59 balls using configuration (B, C, E, E, E).

6. Conclusion

Using constraint programming, we calculated a large set of new lottery design numbers:
minimal configurations of tickets that guarantee winning a prize under common lottery
rules. In doing so we hope to have offered a basic blueprint for an approach to modelling
combinatorial designs in CP, where it is clear that naive approaches would be unviable.
Namely, we show the fruitfulness of eschewing a global model of a combinatorial design
in favour of a local one. By this we mean that one should not seek to design the variables
of one’s model to satisfy the direct definition of the required design; but instead to
focus attention on a well-chosen small piece of it—one that is characterised by a property
relevant to detecting a global unsat conclusion. Developing and analysing the constraints
that the definitions place on the local data should then in reasonable time allow the
solver to achieve unsat or at least return a drastically reduced set of possibilities from
which further analysis can proceed. In effect, what we propose is a general approach to
 REFERENCES 21

symmetry breaking in combinatorial designs that is far more powerful than one would
get from a typical lex-chain constraint.
We note that there are dozens of different general types of designs in [CD07] leading to
tens of thousands of different constraint problems to model. We hope that deploying a
local-based strategy of the sort described here could generate significant improvements
to the state of knowledge thereof.
Declarations: The authors are supported by the Leverhulme Trust Research Project
Grant number RPG-2021-080. The authors have no competing interests to declare that
are relevant to the content of this article.
Acknowledgement: We would like to thank Leo Storme for helpful comments and
corrections on an earlier version. Many thanks also to the referee and editor who helped
hone the paper to be useful for the readership of this journal.

References
[BR98] J. A. Bate and G. H. J. van Rees. “Lotto designs”. Vol. 28. Papers in honour of Anne
Penfold Street. 1998, pp. 15–39.
[CD07] Charles J. Colbourn and Jeffrey H. Dinitz, eds. Handbook of combinatorial designs. Second.
Discrete Mathematics and its Applications (Boca Raton). Chapman & Hall/CRC, Boca
Raton, FL, 2007, pp. xxii+984. isbn: 978-1-58488-506-1; 1-58488-506-8.
[CM12] Mats Carlsson and Per Mildner. “SICStus Prolog—the first 25 years”. Theory Pract. Log.
Program. 12.1-2 (2012), pp. 35–66. issn: 1471-0684. doi: 10.1017/S1471068411000482.
url: https://doi.org/10.1017/S1471068411000482.
[COC97] M. Carlsson, G. Ottosson, and B. Carlson. An open-ended finite domain constraint solver.
English. Vol. 1292. Lecture Notes in Computer Science (including subseries Lecture Notes
in Artificial Intelligence and Lecture Notes in Bioinformatics). 1997, pp. 191–206.
[CSS23] David Cushing, George W. Stagg, and David I. Stewart. “A Prolog assisted search for
new simple Lie algebras”. Math. Comp. (2023), to appear. eprint: arxiv:2207.01094. url:
https://arxiv.org/pdf/2207.01094.pdf.
[FSZ96] Zoltán Füredi, Gábor J. Székely, and Zoltán Zubor. “On the lottery problem”. J. Combin.
Des. 4.1 (1996), pp. 5–10. issn: 1063-8539,1520-6610. doi: 10.1002/(SICI)1520-6610(1996)4:1<5::AID-JC
url: https://doi.org/10.1002/(SICI)1520-6610(1996)4:1%3C5::AID-JCD2%3E3.3.CO;2-W.
[Gen+15] Ian Gent et al. “S-crucial and bicrucial permutations with respect to squares”. J. Integer
Seq. 18.6 (2015), Article 15.6.5, 22. issn: 1530-7638.
[Run96] D. Runciman. “The Plot to Make Us Stupid”. London Review of Books 18.4 (Feb. 1996).
[Sha49] Claude E. Shannon. “A theorem on coloring the lines of a network.” J. Math. Physics
(1949), pp. 148–151.
[SS09] Diego Scheide and Michael Stiebitz. “On Vizing’s bound for the chromatic index of a multi-
graph”. Discrete Mathematics 309 (Aug. 2009), pp. 4920–4925. doi: 10.1016/j.disc.2008.04.046.