Norman Do
The Joy of SET
1What is SET?

In his monumental compendium, The World of Mathematics [3], James Newman states that
Games are among the most interesting creations of the human mind, andthe analysis of their structure is full of adventure and surprises.
Certainly many a mathematician, from amateurs to professionals of some repute, havedabbled in the analysis of games. A particular one which has captured my own mathematicalcuriosity of recent times is the delightful, though little known, card game called SET1. Someof the Gazette’s readership may already be well-acquainted with the game, but for the
unenlightened, let us begin to answer the question, “What exactly is SET?”SET2 is a game played with a special deck of cards, each of which depicts either one,
two or three objects. These objects can be any of three different shapes — oval, squiggle or
diamond — and they are portrayed in one of three different colours — red, green or purple.
Furthermore, the objects come in three different shadings — empty, striped or solid. One
will never find two different shapes, colours or shadings on the same card. Therefore, eachcard can be described by the four attributes number, shape, colour and shading; and eachof these attributes can take on one of three values as listed in the table below. Of course,
you have probably already guessed that there are 34 = 81 cards in the standard SET deck,exactly one for every possible combination of number, shape, colour and shading.
NumberShapeColour1
oval
red
2
squiggle green
3diamond purple

Shading
empty
stripedsolid

The main aim of the game is to identify, among a number of cards dealt face up on thetable, three cards which form a SET. What exactly this means is described by. . .
The SET Rule: Three distinct cards form a SET if and only if they are alldifferent or all the same with respect to number, shape, colour and shading.
For example, the three cards below form a SET because they are all the same with respect
to number, all different with respect to shape, all the same with respect to colour3, and alldifferent with respect to shading.
1

SETr is a registered trademark of SET Enterprises Inc., and SET game play is protected intellectual
property. The images of SET cards have been taken from The Set Game Company Homepage [4] and areused here with permission.
2
I will continue to refer to the game SET in capital letters and reserve the lower case form to denote thewell-known mathematical concept of the same name.
3Given the monochromatic nature of the Gazette, I have written the colours of the cards immediately
below the symbols. Of course, the original SET cards come in vibrant red, green and purple and without
the accompanying text.

234

Norman Do

red

red

red

Another example of a SET is given by the following three cards, since they are all different
with respect to each of number, shape, colour and shading. Such SETs as these, in which
the three cards are all different with respect to all four attributes, are affectionately known
as beasts in some SET-playing circles.

purplered

green

However, the three cards shown below do not form a SET because they are neither all
different nor all the same with respect to shading.

green

purplered

Generally, SET is a non-competitive game for one or more players and play usuallyproceeds as follows.
◦ Twelve cards are dealt face up on the table so that they can be seen by all players.
◦ Players must look for a SET and once found, may remove the three cards involved.
Three more are then dealt in their place to restore the number of cards to twelve.
◦ If no SET appears, then three more cards are dealt face up, until one does appear.
When this SET is removed, no more cards need be dealt, since there will be at least
twelve cards remaining on the table.
◦ If there are no more cards to be dealt, then the game ends once no SET appears in
the remaining cards on the table.
The beauty of SET lies in its simplicity. With only one fundamental rule, children as
young as the age of five can enjoy the game. On the other hand, hardcore SET junkies
like to record their times and I have seen people flash through the deck in under ninety
seconds. From a mathematical viewpoint, the game of SET provokes a myriad of interesting
problems. This article will take us on a whirlwind tour of the mathematics of SET, fromfinite geometry to the Fourier transform and beyond.

Mathellaneous

235

Problem: Find all six SETs which appear in the twelve cards pictured below.

2

red

purple

red

green

red

purplered

purplegreen

purplered

purpleNaive SET Theory

It was not long after learning the game that I heard rumours from fellow SET addicts of
strange and beautiful mathematics lurking behind the cards — thus, I decided to embark
on my own naive exploration of SET theory. The primary connection between SET andmathematics is the correspondence between the SET deck and Z43 , the set of 4-tuples ofintegers modulo 3. There are many natural bijections between these two sets, although forthe sake of concreteness, let us fix the correspondence to be the one shown in the tablebelow.
Z3 Number
Shape
Colour Shading
0
1
oval
red
empty
1
2
squiggle green
striped2
3
diamond purple
solidSo, for example, the SET card with two ovals, coloured red and shaded solid, may be
represented as the 4-tuple (1, 0, 0, 2) ∈ Z43 . However, this is more than just a nifty shorthandfor communicating SET cards, since the additive group structure of Z43 actually encapsulates
the SET rule. To see this, consider the solutions to the equation a + b + c = 0, where a, b, c
are elements of Z3 . It should be reasonably clear that there are nine solutions for (a, b, c)given by the six permutations of (0, 1, 2) as well as (0, 0, 0), (1, 1, 1) and (2, 2, 2). In otherwords, three elements of Z3 sum to zero if and only if they are all different or all the same.
Therefore, a SET consists of three cards whose representatives in Z43 sum to zero in all four
components.
The Algebraic SET Rule: Three distinct elements A, B, C of Z43 form a SET
if and only if A + B + C = 0.
In light of the fact that we are working modulo 3, the equation A + B + C = 0 can be
written in the equivalent form A − B = B − C. Thus, when three elements of Z43 form a236

Norman Do

SET, then they actually lie on a line. Conversely, any three distinct collinear points of Z43
will satisfy the equation A − B = B − C, and hence, will form a SET.
The Geometric SET Rule: Three distinct elements A, B, C of Z43 form a
SET if and only if they are collinear.
These two mathematical formulations of the game provide us with familiar foundations
for answering problems that arise from playing SET. For example, experienced players willknow that the game usually concludes with 12, 9, or sometimes 6 cards remaining on thetable with no SET among them. However, on one occasion, I was fortunate enough to spot
a SET in the final six cards and, to my surprise, found that the final three cards also formed
a SET. Not only did this leave the table satisfyingly clean, but it also seemed suspiciously
fortuitous — I decided to explore and arrived at the following. . .
Theorem 1 A game of SET cannot end with three cards.
Proof. First note that the 81 elements of Z43 sum to 0, since they can be partitioned into 27
SETs of the form (0, a, b, c), (1, a, b, c), (2, a, b, c), each of which sum to 0. Thus, no matter
which 26 SETs have been removed from the deck, the final 3 cards must have a zero sum.
So by the algebraic SET rule, the final three cards will also form a SET.
On another SET-playing occasion, a friend of mine cryptically exclaimed that he had
proved that a SET lay among the twelve cards, but could not see exactly where it was. His
delightfully non-constructive and purely existential statement intrigued the mathematician
within me so I decided to inquire. It turned out that he had hit upon the fact that 5 cards
which share 2 common attributes must always contain a SET. An equivalent statement isthat in a 2-dimensional version of SET, where there are only two varying attributes and thecards correspond to elements of Z23 , the maximum number of cards which do not contain a
SET is 4. This result was quickly confirmed given a few minutes, a pencil and the back ofan envelope. However, it also prompted me to think about d-dimensional SET, where there
are d varying attributes and the cards correspond to elements of Zd3 . And for various valuesof d, I wondered whether it was possible to answer the following question.
In d-dimensional SET, what is the largest number of cards which do notcontain a SET?
Combinatorialists interested in finite geometry will recognise the problem as determining
the maximum size of a cap in Zd3 . In general, a cap is a set of points with no 3 collinear andwe will define a d-cap to be a cap in Zd3 . The search for maximal caps is an active area ofmathematical research with many interesting combinatorial techniques and results. We willlearn more about maximal caps in the next section, but in the meantime, I encourage thereader to try the following problem.
Problem: Prove that a maximal 2-cap contains 4 points.

3

The Search for Maximal Caps

In this section, we will concentrate on determining the size of maximal d-caps and it will
pay to think of Zd3 geometrically. For example, the points of Z23 can be represented as thesquares on a tic-tac-toe board, where lines are allowed to “wrap around” to the other side, àla Pac Man. So apart from the usual 8 winning tic-tac-toe lines, there are 4 extra lines which
wrap around the board. However, since the enthusiastic reader will already have solved the
maximal cap problem in 2-dimensions, let us turn our attention to the 3-dimensional case.
In a similar fashion, the points of Z33 can be represented as the unit cubes in a 3 × 3 × 3
grid, and again, lines are allowed to “wrap around” to the other side. Note also that the 27

Mathellaneous

237

points can be decomposed into 3 layers, each one being a plane containing 9 points. There
are many ways to do this, one for each class of parallel planes, and three such planes which
partition the points of Z33 will subsequently be referred to as a triple plane decomposition.
The determination of the size of a maximal 3-cap involves a clever application of the age oldtrick known as double counting. The cleverness lies in finding objects which can be double
counted to give important information, and these objects turn out to be 2-pointed planes.
Given a subset C of Z43 , define a 2-pointed plane to be a pair (H, {x, y}) consisting of a plane
H in Z33 together with a set of two points {x, y} ⊆ C ∩ H. With these definitions under our
metaphorical belts, we are ready to see the proof of the following. . .
Theorem 2 A maximal 3-cap contains 9 points.
Proof. Suppose that there exists a 3-cap containing 10 points. In other words, assume that
there exists a subset C of Z33 such that |C| = 10 and C contains no three collinear points.
Note that the restriction of a 3-cap to a plane yields a 2-cap, so that every plane intersects
C in at most 4 points. Therefore, given a triple plane decomposition Z33 = H1 ∪ H2 ∪ H3 ,the triple (|H1 ∩ C|, |H2 ∩ C|, |H3 ∩ C|) must be (4, 4, 2) or (4, 3, 3), up to permutation. We
will refer to this triple as the type of a triple plane decomposition.
Now let a denote the number of triple plane decompositions of type (4, 4, 2) and let b
denote the number of triple plane decompositions of type (4, 3, 3). Note that each line
through the origin in Z33 uniquely determines the triple plane decomposition perpendicular
to it. Therefore, the number of triple plane decompositions is simply equal to the numberof lines through the origin. However, each line contains exactly two non-zero points, so the3number of lines is simply half the number of non-zero points, namely 3 2−3 = 13. Therefore,
we have the simple equationa + b = 13.
In order to derive another equation satisfied by a and b, let us double count 2-pointed
planes.
◦ Since there are 10 points in C, there are 10
2 = 45 pairs of points. And it is easy
to verify that through each pair of points in Z33 passes exactly 4 planes. Thus, thenumber of 2-pointed planes is simply 45 × 4 = 180.
◦ On the other hand, for each plane containing k points of C, there will be a contribution of k2 to the count of 2-pointed planes. Thus, for each triple plane decomposition of type (4, 4, 2), the contribution is 42 + 42 + 22 = 13, while for those
of type (4, 3, 3), the contribution is 42 + 32 + 32 = 12. Therefore, the number of
2-pointed planes can also be expressed as 13a + 12b.
Of course, combining these two facts yields the equation
13a + 12b = 180.
Simultaneously solving these two equations yields the unique solution: a = 24, b = −11.
Of course, the negativity of b is an absurdity, so we have reached the desired contradiction
from which we conclude that no 3-cap exists which contains 10 points. It suffices now toverify that the following diagram represents a 3-cap with 9 points.

238

Norman Do

Although the proof given here is not the simplest, it has the advantage of generalising toshow that a maximal 4-cap contains 20 points. The proof of this statement, however, will
involve triple hyperplane decompositions rather than triple plane decompositions, 2-pointed
hyperplanes rather than 2-pointed planes, as well as 3-pointed hyperplanes, all of which aredefined analogously.
Theorem 3 A maximal 4-cap contains 20 points.
Proof. Once again, let us begin by supposing that there exists a 4-cap containing 21 points.
In other words, assume that there exists a subset C of Z43 such that |C| = 21 and C contains
no three collinear points. Since the restriction of a 4-cap to a hyperplane yields a 3-cap,
every hyperplane intersects C in at most 9 points. In particular, every triple hyperplane
decomposition must have one of the following types:(9, 9, 3), (9, 8, 4), (9, 7, 5), (9, 6, 6), (8, 8, 5), (8, 7, 6), (7, 7, 7).
Let xijk denote the number of triple hyperplane decompositions of type (i, j, k). Using
the argument above, there are 40 triple hyperplane decompositions of Z43 , so we have theequationx993 + x984 + x975 + x966 + x885 + x876 + x777 = 40.
A similar double count of the number of 2-pointed hyperplanes provides us with theequation
75x993 + 70x984 + 67x975 + 66x966 + 66x885 + 64x876 + 63x777 = 2730.
And an entirely analogous double count of the number of 3-pointed hyperplanes gives us
still another equation
169x993 + 144x984 + 129x975 + 124x966 + 122x885 + 111x876 + 105x777 = 5320.
Alas, we still only have 3 equations in 7 variables, a far cry from the number we requireto actually solve the system. Fortunately, our variables must all be non-negative integers, a
restriction which we can take full advantage of. Taking a clever linear combination of thethree equations which we have derived gives the following.

12x993

+

5x984
7x984

+ 8x975+ 4x975+ 9x966+ 3x966+ 3x885+ 3x885+ 2x876+ x876= 0= 210.

Due to the non-negativity of the variables, the first equation implies that x984 = x975 =x966 = x885 = x876 = 0. And combining this with the second equation, we arrive at
12x993 = 210, contradicting the fact that x993 is an integer. From this contradiction, we canconclude that no 4-cap exists which contains 21 points. It suffices now to verify that thefollowing diagram represents a 4-cap with 20 points.

Mathellaneous239

This clever method of counting pointed hyperplanes by triple hyperplane decompositions,despite serving us well thus far, has now reached the end of its tether. In fact, the problem
of determining the size of a maximal 5-cap eluded mathematicians until as recently as 2002
when Edel, Ferret, Landjev and Storme [2] proved that a maximal 5-cap contains 45 points.
Rather than elementary counting, the basis for their result was the Fourier transform, whichassigns to a given function f : Zd3 → C, the function fˆ : Zd3 → C defined byXfˆ(z) =
f (x)ω z·x ,
x∈Zd
3
2πi

where ω = e 3 . In fact, their proof relied on the following amazing formula.
Theorem 4 Let S be a subset of Zd3 that contains P points and L lines. Then
1 X
P + 6L = d[χ̂(x)]3 ,
3
d
x∈Z3

where χ̂ is the Fourier transform of the characteristic function4 for S.
The theorem also provides a strong bound for the size of a 6-cap, although it gives
progressively worse bounds for higher values of d. Amazingly enough, the size of a maximal
6-cap is still unknown, and the extent of our knowledge on the size of maximal d-caps is
encapsulated in the following table.
d
1 2 3 4
5
6
size of a maximal d-cap 2 4 9 20 45 112–114
Problem: Show that you cannot have exactly 4 SETs among 7 cards in the original
4-dimensional version of SET.
4For a subset S of Zd , define the characteristic function χ : Zd → C by3

χ(x) =

 0 if x ∈/ C
1 if x ∈ C

3

240

4

Norman Do

Final Thoughts

Despite being so intricately related to mathematics, the story of SET began in 1974 withepileptic dogs and a population geneticist by the name of Marsha Jean Falco. At the time,
she was working on the problem of whether German Shepherds who had epilepsy might haveinherited it. This research involved spotting patterns in large amounts of data. Thus, tomake the job easier, Falco decided to represent blocks of information by coloured symbols
drawn on small file cards. In a stroke of brilliance, she realised the potential for this to be
the basis of a game and created the first ever SET deck with an engineering stencil and adeck of blank cards. For many years, the game of SET lay dormant to the world at large,
only to be played by Falco and a small circle of family and friends. It was only in 1991,
spurred on by her children, that she decided to reveal the game to the general public. Thus,
SET was born.
Little did the creator of SET know that the game would have such deep connections withfinite geometry and that the game would spawn so many mathematical problems. As wehave seen, some of these have been solved with both elegant and complicated mathematics.
However, many still remain unsolved, perhaps to be the mathematical fodder for future
generations of mathematicians. The interested reader may like to try their hand at thefollowing problem and to consult the article [1] for more SET theory.
It would be nice to know how large, in some sense, maximal caps can be. To this end,
we can measure
the size of a cap C ⊆ Zd3 by its solidity, which is defined to be thepdnumber |C|. If f (d) is the size of a maximal d-cap, note that f (d) ≥ 2d , since thepoints in Zd3 whose coordinates are all 0 and 1 form a cap. Combined with the trivial
bound f (d) ≤ 3d , we deduce that the solidity of a maximal cap is always in the interval[2, 3].
p(1) (Solved) Prove that limd→∞ d f (d) exists — this number is known as the asymptotic solidity.
(2) (Unsolved) It is known that the asymptotic solidity is greater than 2, but is it
less than 3?
Let us come full circle and close the article with the very same quote with which webegan.
Games are among the most interesting creations of the human mind, and theanalysis of their structure is full of adventure and surprises. Unfortunately
there is never a lack of mathematicians for the job of transforming delectable
ingredients into a dish that tastes like a damp blanket.
My hope is that I have been able to reveal some of the adventure and surprises in themathematical analysis of SET without exposing too much of the damp blanket.

References[1] B.L. Davis and D. Maclagan, The card game SET!, Math. Intelligencer 25 (2003), No 3.
[2] Y. Edel, S. Ferret, I. Landjev and L. Storme, The classification of the largest caps in AG(5, 3), J.
Combin. Theory Ser. A 99 (2002), 95–110.
[3] J.R. Newman, The World of Mathematics (Simon and Schuster New York 1956).
[4] The Set Game Company Homepage, http://www.setgame.com.
Department of Mathematics and Statistics, The University of Melbourne, VIC 3010
E-mail: N.Do@ms.unimelb.edu.au