# Socks, a matching game based on an additive combinatorics problem

Can you find a set of cards among these six, such that the socks on the chosen cards can be grouped into matching pairs? (Duplicate pairs of the same sock are OK)

Spoilers

If the cards are indexed as

1   2   3
4   5   6


Then the following three subsets work: $\{ 1, 2, 4, 5, 6 \}$, $\{ 2, 3, 6 \}$, and $\{ 1, 3, 4, 5 \}$. There might be more but I don’t see them.

This is the objective of the game Socks, a card game originally designed by Anna Varvak, a math professor at Soka University of America. I tweaked the rules slightly, and designed the deck above, and you can buy a copy. (I’m selling it with Anna’s permission)

The game consists of 63 cards, one for each possible nonempty subset of 6 distinct socks. Duplicate pairs of the same kind of sock are OK, so long as they can be grouped into pairs (e.g., 3 yellow socks is not allowed, but 4 is). Players deal some cards and race to find sets, and the player at the end of the game with the most sets wins. The natural math question is: how many cards are needed to guarantee there’s a set?

Mathematically, the cards can hence be viewed as elements of the additive group $(\mathbb{Z}/2\mathbb{Z})^6$ of length-6 binary vectors. An index corresponds to a sock type, and the value is one of the sock is present on the card, and zero otherwise.

I use the “additive group” structure because a set in Socks is a subset of $(\mathbb{Z}/2\mathbb{Z})^6$ that sums to zero in the group. In programmer terms, a card is a length-6 bitstring and a “sum” is a bitwise XOR. Either way, “summing” two cards can be thought of as producing the card consisting of only the socks that show up an odd number of times on the two cards. One implication here is that any set requires at least three cards: each group element is its own inverse, but no card shows up twice in the deck.

Then the natural math question becomes: how many cards do you need to guarantee there is a valid set? In math terms, what is the smallest integer $M$ such that every size-$M$ subset $S \subset (\mathbb{Z}/2\mathbb{Z})^6$ contains a nonempty zero-summing subset?

Theorem: $M = 7$.

Proof. The following set of size 6 has no zero-summing subset

$\{ (1, 0, \dots, 0), (0, 1, 0, \dots, 0), \dots, (0, 0, \dots, 1) \}$

So $M > 6$. On the other hand, consider any set $S$ of size 7. There are $2^{7} – 1$ distinct sums of nonempty subsets of $S$, but only $2^6$ group elements, so there must be two distinct subsets of $S$ that have the same sum. Suppose they are $X = {x_1, \dots, x_r}$ and $Y = {y_1, \dots, y_s}$, and $g = x_1 + \dots + x_r = y_1 + \dots + y_s$. Then adding the two equations, and noting that every element $x$ satisfies $x = -x$ in this group, we get

$x_1 + \dots + x_r + y_1 + \dots + y_s = g + g = 0$

In other words, we would like to use the “set” $\{ x_1, \dots, x_r, y_1, \dots, y_s \}$ and declare victory, but we can’t because some of the $x_i$ may coincide with some of the $y_j$. That is, $X$ and $Y$ can overlap, and we can’t “use” an element twice. But because the two sets are distinct (not equal), they cannot overlap completely. For any values that overlap, say $x_1 = y_2$, their sum is $x_1 + y_2 = 2x_1 = 0$, and those two elements can be removed without changing the sum. Hence, the final zero-summing subset is the symmetric difference $X \triangle Y$.

$\square$

Unfortunately, as I’ve played Socks, I’ve found that it’s no easier to find a zero-summing subset than it is to find two subsets that have the same sum. So while knowing this proof helps me win the hearts and minds of my opponents, it doesn’t help me win the game.

The next natural goal for a mathematician is to ask the same question of more general groups. The above proof argument naturally extends to $(\mathbb{Z}/2\mathbb{Z})^k$ having $M= k+1$. But for $(\mathbb{Z}/n\mathbb{Z})^k$, the problem is open.

Conjecture: Let $G = (\mathbb{Z}/n\mathbb{Z})^k$, then every set $S$ of $1 + k(n-1)$ elements of $G$ has a nonempty zero-summing subset.

The same argument from the previous theorem doesn’t quite apply: even though you can prove some distinct subsets of $S$ have the same sum, the difference gives different group elements that may not be in $S$.

This generalization opens the door to a decent subset of the number theory and additive combinatorics literature, in which this is called the Olson’s constant problem. Section F.3.3 of this survey of Bela Bajnok covers the literature quite well. Erdős originally worked on the problem in the 60’s. There have been a swath of results for groups with particular structure, for example in John Olson’s original 1969 paper, A Combinatorial Problem on Finite Abelian Groups, I, in which he proves the above conjecture for the special case of finite abelian $p$-groups. I will summarize a few results and conjectures below, most copied from Bajnok’s survey, and if you’re clever enough, each one could be the basis for a new card game. The hard part, it seems, is finding a theme that is cute and picking a small enough group so as to make it fun.

Theorem: For every even integer $n$, Olson’s constant for $\mathbb{Z}/n\mathbb{Z}$ is at least $1 + \lfloor \sqrt{2n – 3} \rfloor$.

For all even $n \leq 64$, this bound is known to be an equality. E.g., for $n=64$ it is 12, and for $n=50$ it is 10. There are no known values of $n$ for which this bound is not tight.

Theorem: For every prime $p$, Olson’s constant for $\mathbb{Z}/p\mathbb{Z}$ is exactly $1 + \lfloor \sqrt{2p} – 1 / 2 \rfloor$.

For example, for $p=53$, Olson’s constant is 10. (Deal ten cards containing…something both cute and interpretable mod 53! Good luck)

Odd composite values of $n$ is still an open problem, though a lower bound is known of $1 + \lfloor (\sqrt{8n + 9} – 1 ) /2 \rfloor$.

The case for products of cyclic groups involves various bounds (the $\tau$ below represents Olson’s constant minus 1).

Equality is known to hold for $k = 2, 3, 4, 5$.

Theorem: For any finite Abelian group of order $n$, Olson’s constant is less than $3 \sqrt{n} + 1$.

Conjecture [Erdős]: For any finite Abelian group of order $n$, Olson’s constant is less than $1 + \sqrt{2n}$.

Theorem: There is a constant $C$, such that for any finite Abelian group of order $n$, Olson’s constant is at most $1 + \sqrt{2n} + C \sqrt[3]{n} \log_e n$.

And finally, it is conjectured that cyclic groups have maximal Olson constant among all groups of a given order. So if you want to make your game hard, use cyclic groups. If you want to make it easy, use groups that are products of many small cyclic groups.

## The origin story

The story of how I came to make my own version of Socks is a funny little mix-up.

Though the original game was designed by Anna Varvak in 2012, I made the cards shown in the picture at the beginning of this article. A friend of mine originally told me about Socks about six months ago. She had heard about it from a friend of hers, but she couldn’t find a physical copy for sale. Socks is listed at BoardGameGeek, but it had a broken website link, www.socksgame.com. I assumed it was out of print. I thought making my own version would be fun! So I found The Game Crafter, a website for on-demand printing of game components, and threw together a design.

When I finished, I noticed the generated URL was www.thegamecrafter.com/games/socks2 and I thought, “That’s weird, someone else made a game called Socks!” And voila, https://www.thegamecrafter.com/games/socks points to Varvak’s original game, still for sale.

Luckily, I was able to get in contact with Anna, and she graciously gave me permission to sell my version under the same name, “Socks.” The official rules in each game are slightly different: in hers you deal 12 cards and a set must consist of exactly 3 cards. In mine you deal 7 cards, and a set can be formed from any subset of the cards. When you restrict the subsets to have size exactly 3, the problem is slightly different (see section F.3.1 of Bajnok’s survey), and the main result that applies is

Theorem: For all positive integers $k$, every set $S \subset (\mathbb{Z}/2\mathbb{Z})^k$ with size at least $2^{k-1} + 2$ has a zero-summing subset of size 3, and there is a set of size $2^{k-1} + 1$ with no zero-summing subset of size 3.

In Anna’s version, it appears, 12 cards is not enough. You need a whopping 34 to guarantee a set exists.

## Some playing notes

Some notes about what happens when actually playing the game:

• A set is worth 1 point, no matter how many cards are in it. I have no idea if it is a better strategy to look for smaller or larger sets.
• A set must have size at least three, and sets of size exactly three are easy-ish to find by XOR-summing pairs of cards.
• Each sock type is in the same location on the cards, which makes it easier to visualize.
• Often you can locate small groups of cards (say, 1-2) that are unusable because their inclusion forces an odd number of some sock. This seems to drastically diminish the size of the search space.
• A set using all the cards is not that uncommon, so it seems to help to start by summing all the socks and identifying the socks that break that possibility, or else claim a quick set.
• It does not appear to be easier to find sets when the cards are “sparse” (1-3 socks per card) vs “dense” (4-6 socks per card).
• When the last card is dealt you can immediately claim “Socks”, as long as every claimed set in the game was valid. This makes the last round boring, and it is slightly more interesting to leave the last card undealt, and then “infer” what is on that card by inverting the sum of the remaining cards. This is similar to the parlor trick for SET I wrote about a while back. Doing this trick for Socks is not nearly as hard as it is for SET, but might be impressive to players who have not thought about the math.

# The Gadget Decomposition in FHE

Lately I’ve been studying Fully Homomorphic Encryption, which is the miraculous ability to perform arbitrary computations on encrypted data without learning any information about the underlying message. It’s the most comprehensive private computing solution that can exist (and it does exist!).

The first FHE scheme by Craig Gentry was based on ideal lattices and was considered very complex (I never took the time to learn how it worked). Some later schemes (GSW = Gentry-Sahai-Waters) are based on matrix multiplication, and are conceptually much simpler. Even more recent FHE schemes build on GSW or use it as a core subroutine.

All of these schemes inject random noise into the ciphertext, and each homomorphic operation increases noise. Once the noise gets too big, you can no longer decrypt the message, and so every now and then you must apply a process called “bootstrapping” that reduces noise. It also tends to be the performance bottleneck of any FHE scheme, and this bottleneck is why FHE is not considered practical yet.

To help reduce noise growth, many FHE schemes like GSW use a technical construction dubbed the gadget decomposition. Despite the terribly vague name, it’s a crucial limitation on noise growth. When it shows up in a paper, it’s usually remarked as “well known in the literature,” and the details you’d need to implement it are omitted. It’s one of those topics.

So I’ll provide some details. The code from this post is on GitHub.

## Binary digit decomposition

To create an FHE scheme, you need to apply two homomorphic operations to ciphertexts: addition and multiplication. Most FHE schemes admit one of the two operations trivially. If the ciphertexts are numbers as in RSA, you multiply them as numbers and that multiplies the underlying messages, but addition is not known to be possible. If ciphertexts are vectors as in the “Learning With Errors” scheme (LWE)—the basis of many FHE schemes—you add them as vectors and that adds the underlying messages. (Here the “Error” in LWE is synonymous with “random noise”, I will use the term “noise”) In LWE and most FHE schemes, a ciphertext hides the underlying message by adding random noise, and addition of two ciphertexts adds the corresponding noise. After too many unmitigated additions, the noise will grow so large it obstructs the message. So you stop computing, or you apply a bootstrapping operation to reduce the noise.

Most FHE schemes also allow you to multiply a ciphertext by an unencrypted constant $A$, but then the noise scales by a factor of $A$, which is undesirable if $A$ is large. So you either need to limit the coefficients of your linear combinations by some upper bound, or use a version of the gadget decomposition.

The simplest version of the gadget decomposition works like this. Instead of encrypting a message $m \in \mathbb{Z}$, you would encrypt $m, 2m, 4m, …, 2^{k-1} m$ for some choice of $k$, and then to multiply $A < 2^k$ you write the binary digits of $A = \sum_{i=0}^{k-1} a_i 2^i$ and you compute $\sum_{i=0}^{k-1} a_i \textup{Enc}(2^i m)$. If the noise in each encryption is $E$, and summing ciphertexts sums noise, then this trick reduces the noise growth from $O(AE)$ to $O(kE) = O(\log(A)E)$, at the cost of tracking $k$ ciphertexts. (Calling the noise $E$ is a bit of an abuse—in reality the error is sampled from a random distribution—but hopefully you see my point).

Some folks call the mapping $\textup{PowersOf2}(m) = m \cdot (2^0, 2^1, 2^2, \dots, 2^{k-1})$, and for the sake of this article let’s call the operation of writing a number $A$ in terms of its binary digits $\textup{Bin}(A) = (a_0, \dots, a_{k-1})$ (note, the first digit is the least-significant bit, i.e., it’s a little-endian representation). Then PowersOf2 and Bin expand an integer product into a dot product, while shifting powers of 2 from one side to the other.

$\displaystyle A \cdot m = \langle \textup{Bin}(A), \textup{PowersOf2}(m) \rangle$

This inspired the following “proof by meme” that I can’t resist including.

Working out an example, if the message is $m=7$ and $A = 100, k=7$, then $\textup{PowersOf2}(7) = (7, 14, 28, 56, 112, 224, 448, 896)$ and $\textup{Bin}(A) = (0,0,1,0,0,1,1,0)$ (again, little-endian), and the dot product is

$\displaystyle 28 \cdot 1 + 224 \cdot 1 + 448 \cdot 1 = 700 = 7 \cdot 2^2 + 7 \cdot 2^5 + 7 \cdot 2^6$

One can generalize the binary digit decomposition to different bases, or to vectors of messages instead of a single message, or to include a subset of the digits for varying approximations. I’ve been puzzling over an FHE scheme that does all three. In my search for clarity I came across a nice paper of Genise, Micciancio, and Polyakov called “Building an Efficient Lattice Gadget Toolkit: Subgaussian Sampling and More“, in which they state a nice general definition.

Definition: For any finite additive group $A$, an $A$-gadget of size $w$ and quality $\beta$ is a vector $\mathbf{g} \in A^w$ such that any group element $u \in A$ can be written as an integer combination $u = \sum_{i=1}^w g_i x_i$ where $\mathbf{x} = (x_1, \dots , x_w)$ has norm at most $\beta$.

The main groups considered in my case are $A = (\mathbb{Z}/q\mathbb{Z})^n$, where $q$ is usually $2^{32}$ or $2^{64}$, i.e., unsigned int sizes on computers for which we get free modulus operations. In this case, a $(\mathbb{Z}/q\mathbb{Z})^n$-gadget is a matrix $G \in (\mathbb{Z}/q\mathbb{Z})^{n \times w}$, and the representation $x \in \mathbb{Z}^w$ of $u \in (\mathbb{Z}/q\mathbb{Z})^n$ satisfies $Gx = u$.

Here $n$ and $q$ are fixed, and $w, \beta$ are traded off to make the chosen gadget scheme more efficient (smaller $w$) or better at reducing noise (smaller $\beta$). An example of how this could work is shown in the next section by generalizing the binary digit decomposition to an arbitrary base $B$. This allows you to use fewer digits to represent the number $A$, but each digit may be as large as $B$ and so the quality is $\beta = O(B\sqrt{w})$.

One commonly-used construction is to convert an $A$-gadget to an $A^n$-gadget using the Kronecker product. Let $g \in A^w$ be an $A$-gadget of quality $\beta$. Then the following matrix is an $A^n$-gadget of size $nw$ and quality $\sqrt{n} \beta$:

$\displaystyle G = I_n \otimes \mathbf{g}^\top = \begin{pmatrix} g_1 & \dots & g_w & & & & & & & \\ & & & g_1 & \dots & g_w & & & & \\ & & & & & & \ddots & & & \\ & & & & & & & g_1 & \dots & g_w \end{pmatrix}$

Blank spaces represent zeros, for clarity.

An example with $A = (\mathbb{Z}/16\mathbb{Z})$. The $A$-gadget is $\mathbf{g} = (1,2,4,8)$. This has size $4 = \log(q)$ and quality $\beta = 2 = \sqrt{1+1+1+1}$. Then for an $A^3$-gadget, we construct

Now given a vector $(15, 4, 7) \in \mathbb{A}^3$ we write it as follows, where each little-endian representation is concatenated into a single vector.

$\displaystyle \mathbf{x} = \begin{pmatrix} 1\\1\\1\\1\\0\\0\\1\\0\\1\\1\\1\\0 \end{pmatrix}$

And finally,

To use the definition more rigorously, if we had to write the matrix above as a gadget “vector”, it would be in column order from left to right, $\mathbf{g} = ((1,0,0), (2,0,0), \dots, (0,0,8)) \in A^{wn}$. Since the vector $\mathbf{x}$ can be at worst all 1’s, its norm is at most $\sqrt{12} = \sqrt{nw} = \sqrt{n} \beta = 2 \sqrt{3}$, as claimed above.

## A signed representation in base B

As we’ve seen, the gadget decomposition trades reducing noise for a larger ciphertext size. With integers modulo $q = 2^{32}$, this can be fine-tuned a bit more by using a larger base. Instead of PowersOf2 we could define PowersOfB, where $B = 2^b$, such that $B$ divides $2^{32}$. For example, with $b = 8, B = 256$, we would only need to track 4 ciphertexts. And the gadget decomposition of the number we’re multiplying by would be the little-endian digits of its base-$B$ representation. The cost here is that the maximum entry of the decomposed representation is 255.

We can fine tune this a little bit more by using a signed base-$B$ representation. To my knowledge this is not the same thing as what computer programmers normally refer to as a signed integer, nor does it have anything to do with the two’s complement representation of negative numbers. Rather, instead of the normal base-$B$ digits $n_i \in \{ 0, 1, \dots, B-1 \}$ for a number $N = \sum_{i=0}^k n_i B^i$, the signed representation chooses $n_i \in \{ -B/2, -B/2 + 1, \dots, -1, 0, 1, \dots, B/2 – 1 \}$.

Computing the digits is slightly more involved, and it works by shifting large coefficients by $-B/2$, and “absorbing” the impact of that shift into the next more significant digit. E.g., if $B = 256$ and $N = 2^{11} – 1$ (all 1s up to the 10th digit), then the unsigned little-endian base-$B$ representation of $N$ is $(255, 7) = 255 + 7 \cdot 256$. The corresponding signed base-$B$ representation subtracts $B$ from the first digit, and adds 1 to the second digit, resulting in $(-1, 8) = -1 + 8 \cdot 256$. This works in general because of the following “add zero” identity, where $p$ and $q$ are two successive unsigned digits in the unsigned base-$B$ representation of a number.

\displaystyle \begin{aligned} pB^{k-1} + qB^k &= pB^{k-1} – B^k + qB^k + B^k \\ &= (p-B)B^{k-1} + (q+1)B^k \end{aligned}

Then if $q+1 \geq B/2$, you’d repeat and carry the 1 to the next higher coefficient.

The result of all this is that the maximum absolute value of a coefficient of the signed representation is halved from the unsigned representation, which reduces the noise growth at the cost of a slightly more complex representation (from an implementation standpoint). Another side effect is that the largest representable number is less than $2^{32}-1$. If you try to apply this algorithm to such a large number, the largest digit would need to be shifted, but there is no successor to carry to. Rather, if there are $k$ digits in the unsigned base-$B$ representation, the maximum number representable in the signed version has all digits set to $B/2 – 1$. In our example with $B=256$ and 32 bits, the largest digit is 127. The formula for the max representable integer is $\sum_{i=0}^{k-1} (B/2 – 1) B^i = (B/2 – 1)\frac{B^k – 1}{B-1}$.

max_digit = base // 2 - 1
max_representable = (max_digit
* (base ** (num_bits // base_log) - 1) // (base - 1)
)


A simple python implementation computes the signed representation, with code copied below, in which $B=2^b$ is the base, and $b = \log_2(B)$ is base_log.

def signed_decomposition(
x: int, base_log: int, total_num_bits=32) -> List[int]:
result = []
base = 1 << base_log
digit_mask = (1 << base_log) - 1
base_over_2_threshold = 1 << (base_log - 1)
carry = 0

for i in range(total_num_bits // base_log):
unsigned_digit = (x >> (i * base_log)) & digit_mask
if carry:
unsigned_digit += carry
carry = 0

signed_digit = unsigned_digit
if signed_digit >= base_over_2_threshold:
signed_digit -= base
carry = 1
result.append(signed_digit)

return result


In a future article I demonstrate the gadget decomposition in action in a practical setting called key switching, which allows one to convert an LWE ciphertext encrypted with key $s_1$ into an LWE ciphertext encrypted with a different key $s_2$. This operation increases noise, and so the gadget decomposition is used to reduce noise growth. Key switching is used in FHE because some operations (like bootstrapping) have the side effect of switching the encryption key.

Until then!