Subset sums, generating functions, and roots of unity

The problem:

Find the number of subsets of whose sum of elements is divisible by .

On the surface it looks innocent: “just subsets and sums.” But if you try to attack it directly, you quickly drown in cases.

The way out is to package everything into a polynomial and then use roots of unity to “filter” the coefficients we care about.

This post is basically my handwritten solution cleaned up, with ideas inspired by Dr. Pragel and a 3Blue1Brown video.

1. A tiny example: subsets of

Let’s warm up with the set

We can list all subsets, compute their sums, and look at those that are multiples of 5:

  • and so on…

You can literally draw boxes grouping subsets with the same sum. The sums that are multiples of 5 are easy to spot for this tiny example.

But for this approach is hopeless. We need a way to encode all subsets at once.

2. The “magical step”: a generating function

Consider the polynomial

Why this particular product?

  • In the factor , the term corresponds to “don’t include ”,
  • and the term corresponds to “include ”.

When we expand the product, every subset appears exactly once as a monomial

So if

then is exactly the number of subsets whose elements sum to .

In the small case you can expand by hand and see terms like

and you can circle the coefficients of as the subsets whose sum is a multiple of 5.

For the original problem we do the same thing conceptually:

If we could expand this monstrosity, we’d get

where counts subsets of with sum .

What we want is the sum

(the coefficients of where is a multiple of 5).

Actually expanding is impossible. So we do something sneakier: we evaluate at clever values of .

3. Warmup: using and (mod 2)

Before we jump to 5th roots of unity, here’s a simpler version of the same idea with modulus .

Let

be any polynomial where counts subsets with sum (for any finite set).

Then:

is just the total number of subsets (every subset contributes ).

In our big problem,

Now evaluate at .

In factored form:

  • If is odd, .
  • There are odd numbers between 1 and 2000, so at least one factor is 0.

So:

In expanded form:

So we have

Add them:

Divide by 2:

which is exactly the number of subsets whose sum is even.

In our case,

This is the mod-2 version of the trick: evaluating at and lets us isolate even exponents.

We’d like something similar for mod 5: a way to extract coefficients where the exponent is .

That’s where roots of unity show up.

4. Enter 5th roots of unity

Let be a primitive 5th root of unity, so

The five 5th roots of unity are

Again write

Look at the values:

Now add these five values:

Collect coefficients of each . The coefficient in front of is:

Call this sum

We can understand using basic facts about roots of unity:

  • If , then , so
  • If , then the powers are just a permutation of and we know So

So the big sum collapses to

Therefore,

This is the root-of-unity filter for multiples of 5.

So our answer is

where

We already know . What’s left is to compute , , , .

5. Evaluating in factored form

Recall

Now note that . Among the integers each residue modulo 5 appears exactly 400 times.

So we can group the product by residue class:

  • numbers ,
  • numbers ,
  • numbers ,
  • numbers ,
  • numbers .

If , write . Then

So each residue class contributes the same factor repeated 400 times. We get

Let

Then

Now we compute using the polynomial .

The 5th roots of unity are the roots of . The four nontrivial ones are roots of

Then

Evaluate at :

Now multiply by to include the factor:

So:

The same argument works for because multiplying exponents by just permutes the residues .

Thus:

6. Putting it all together

From before:

  • ,
  • .

So the number of subsets of whose sum is divisible by 5 is

So the final answer is

Behind the scenes, we:

  1. Encoded all subsets in a polynomial,
  2. Used evaluation at special points (, , roots of unity) to filter the exponents we care about,
  3. And exploited symmetry when the size of the set is a multiple of the modulus.

This is exactly the kind of trick that shows up all over combinatorics, number theory, and eventually in representation theory of cyclic groups.