An Interesting Subset Sum Problem

About a month ago, I came across an interesting 3Blue1Brown video. This video covered an interesting math olympiad problem about counting subsets. It asked the following:

Find the number of subsets of \( \{1,2,\ldots,2000\} \), the sum of whose elements is divisible by \( 5 \).

While the video brilliantly outlined a beautiful journey to finding the answer, \( \frac{1}{5}(2^{2000}+4\cdot2^400)\), I was left wanting more by the end. I wanted to know how to answer a more general question:

Let \(S\) be the set of consecutive integers from \(1\) to \(n\), \( \{1,2,\ldots,n\} \). Find the number of subsets with elements that sum to an integer divisible by \(k\).

My journey to solving this problem has surprisingly led me to some interesting truths about generating functions, roots of unity, and group theory. I'm still working on fully comprehending the connections of these subjects, but this problem has been very fun to work on.

The 3Blue1Brown Case

Before solving the more general case, it is definitely worth understanding the simpler case presented in the video that inspired all of this. It is worth watching the video for the best explanation of this problem, but I will do my best to summarize here.

Find the number of subsets of \( \{1,2,\ldots,2000\} \), the sum of whose elements is divisible by \( 5 \).

The Generating Function

First, consider the function \(f(x)=(1+x)(1+x^2)\cdots(1+x^{2000})\). What does each coefficient \(a_j\) represent in the following series?

\[ f(x)=\sum^{2001000}_{j=0}a_j x^j \]

One can think of each \(a_j\) as the number of times a subset has the sum \(j\). This is because the process of expanding out this polynomial and writing out subsets of \(S\) is the exact same.

Thus, in order to find the amount of subsets with sums divisible by 5, one is really just looking for the following:

\[\sum^{400200}_{j=0}a_{5j}=\text{answer}\]

But how does one get rid of those pesky coefficients with subscripts that aren't divisible by \(5\)? This is where complex numbers come in.

The Fifth Roots of Unity

Consider the equation \(x^5-1=0\). By the fundamental theorem of algebra, there are \(5\) solutions to this equation. A somewhat obvious solution is \(x=1\), but no other real numbers seem to work.

By Euler's formula, we know that \(e^{i\theta}=\cos{\theta}+i\sin{\theta}\). We already found our first solution, \(1=e ^0=e ^{2\pi i}\). Are there any obvious numbers that when multiplied \(5\) times gives \(e ^{2\pi i}\)?

After some thinking, one might see that \(e^{\frac{2}{5}\pi i}\) is one such number.

\[(e^{\frac{2}{5}\pi i}) ^5 = e ^{2\pi i} = 1\]

Further investigation reveals that any number of the form \(e^{\frac{2m}{5}\pi i}\) for \(m\in\mathbb{Z}\). However, there are actually only \(5\) unique numbers due to the periodic nature of the trigonometric functions.

Thus, denote the fifth roots of unity as follows:

\[\alpha ^0=e^{\frac{0}{5}\pi i}, \alpha ^1=e^{\frac{2}{5}\pi i},\alpha ^2=e^{\frac{4}{5}\pi i},\alpha ^3=e^{\frac{6}{5}\pi i},\alpha ^4=e^{\frac{8}{5}\pi i}\]

Note that \(\alpha ^5 = \alpha ^0\). An interesting question one might think of is evaluating the following sum:

\[\sum^{4}_{j=0}\alpha ^j=\text{?}\]

Multiply the sum by \(\alpha-1\), which we know isn't \(0\) because \(\alpha\neq 0\).

\[(\alpha-1)\sum^{4}_{j=0}\alpha ^j=\sum^{4}_{j=0}(\alpha ^{j+1} - \alpha ^ j)=\alpha ^ 5 - \alpha ^ 0 = 0\]

Thus, we know the sum was \(0\) in the first place, as multiplying by a nonzero term resulted in \(0\).

From here we can go back to our generating function for some interesting results.

Putting it all Back Together

We still need to figure out how to get rid of each \(a_j\) with \(j\) not divisible by \(5\). Let's try to use the fact that \(\alpha ^0 +\alpha ^1 +\alpha ^2 +\alpha ^3 +\alpha ^4=0\).

One might look at \(f(\alpha ^ 0) +f(\alpha ^ 1) +f(\alpha ^ 2) +f(\alpha ^ 3) +f(\alpha ^ 4)\). Evaluating further, one will see the following:

\[f(\alpha ^ 0) +f(\alpha ^ 1) +f(\alpha ^ 2) +f(\alpha ^ 3) +f(\alpha ^ 4)=\sum^{2001000}_{j=0}a_j(\alpha ^{0} +\alpha ^{j} +\alpha ^{2j} +\alpha ^{3j} +\alpha ^{4j})\]

Because \(5\) is prime, we know that \(\alpha ^{0} +\alpha ^{j} +\alpha ^{2j} +\alpha ^{3j} +\alpha ^{4j}=\alpha ^0 +\alpha ^1 +\alpha ^2 +\alpha ^3 +\alpha ^4=0\) whenever \(5\nmid j\). In the case of \(5\mid j\), we have \(\alpha ^{0} +\alpha ^{j} +\alpha ^{2j} +\alpha ^{3j} +\alpha ^{4j}=5\). Thus, we are one step closer to solving this problem.

\[f(\alpha ^ 0) +f(\alpha ^ 1) +f(\alpha ^ 2) +f(\alpha ^ 3) +f(\alpha ^ 4)=5\cdot\text{answer}\]

All that is left to do is to evaluate each of \(f(\alpha ^ 0),f(\alpha ^ 1),f(\alpha ^ 2),f(\alpha ^ 3),f(\alpha ^ 4)\). First,\(f(\alpha ^ 0)\) is trivial, since \(\alpha ^0 = 1\).

\[f(1)=(1+1)(1+1^2)\cdots(1+1^{2000})=2 ^{2000}\]

We can recognize that since \(5\) is prime, \(f(\alpha ^ 1)=f(\alpha ^ 2)=f(\alpha ^ 3)=f(\alpha ^ 4)\). Thus, only evaluate \(f(\alpha ^ 1)\).

\[f(\alpha^1)=(1+\alpha)(1+\alpha^2)\cdots(1+\alpha^{2000})\]

\[=\left((1+\alpha)(1+\alpha^2)(1+\alpha ^3)(1+\alpha ^4)(1 +\alpha^ 5)\right)^{400}=2 ^{400}\]

Where the last equality comes from expanding out \((1+\alpha)(1+\alpha^2)(1+\alpha ^3)(1+\alpha ^4)(1 +\alpha^ 5)\).

Thus, we finally have an answer, to the simpler case presented in the 3b1b video:

\[\frac{1}{5}(2^{2000}+4\cdot 2 ^{400})=\text{answer}\]

But what happens when \(n\neq 2000\) and \(k\neq 5\)? This is the question I set out to answer, and am still working on.

The General Case

Again, consider the function \(f(x)=(1+x)(1+x^2)\cdots(1+x^n)\). Also, note the series representation:

\[ f(x)=\sum^{N}_{j=0}a_j x^j \]

As an aside, note that \(N=\frac{n(n+1)}{2}\) because the highest degree term of the polynomial is the product \(x\cdot x^2\cdots x ^n=x ^{1+2+\cdots+n}=x ^N\).

In the 3b1b case, it was convenient that \(k\mid n\). So, as a start, consider just that general case.

The Simple General Case

Let \(k\) be an integer such that \(k\mid n\). Let \(\alpha=e^{\frac{2}{k}\pi i}\) so that \(\alpha ^k=1\).

Then \(\alpha\) is a primitive root of unity, meaning that the lowest integer \(x\) such that \(\alpha ^x=1\), is \(k\).

In the same way that \(\alpha ^0 +\alpha ^1 +\alpha ^2 +\alpha ^3 +\alpha ^4=0\) for fifth roots of unity, it is also true that \(\sum^{k-1}_{j=0}\alpha ^j\). Thus, the same trick of adding each \(f(\alpha ^j)\) and then dividing by \(k\) will give us the correct answer. But what is \(f(\alpha ^j)\)?

Using the periodicity of roots of unity, one can group the factors of \(f(\alpha ^j)\) to see that it is the following:

\[f(\alpha ^j)=\left((1+\alpha ^0)(1 +\alpha ^1)\cdots(1 +\alpha ^{k-1})\right) ^{n/k}\]

To evaluate this, consider the following part of the product excluding \((1+\alpha ^0)\) which is clearly \(2\).

\[\prod_{j=1} ^{k-1}(1+\alpha ^j)\]

This looks difficult to evaluate, and I struggled at this stage a lot until I came across this theorem (note that this link is using similar variables for different things). For \(z\in\mathbb{C}\),

\[\sum_{j=0} ^{k-1}z ^j = \prod_{j=1} ^{k-1}(z-\alpha ^j)\]

Set \(z=-1\) and factor out a negative from each factor on the left side. Then one will see that for even values of \(k\)

\[\prod_{j=1} ^{k-1}(1+\alpha ^j)=0\text{,}\]

and for odd values of \(k\)

\[\prod_{j=1} ^{k-1}(1+\alpha ^j)=1\text{.}\]

Thus, we already have the answer for this specific case:

\[\frac{1}{k}\left(2 ^n + 2 ^{n/k}(k-1)\left(2\left\lceil\frac{k}{2}\right\rceil-k\right)\right)\]

What if n is not divisible by k?

It seems as if a lot of my argument depends on the trick of grouping the factors of \(f(\alpha ^j)\), but this is usually not possible. Thus, how is evaluation possible in this case?

At this point, I still have not figured this problem out. I have tried a multitude of ideas, and have gotten some good guesses, but proving anything has been incredibly challenging.

I first started using the idea of the division algorithm to group parts of factors with \(q\) and \(r\), but this led to the problem that each \(f(\alpha ^j)\) had a different value, meaning they needed to be summed together to get a real number. I think this is the way to proceed, but I have not wrinkled out any of the details. I also thought about an idea of creating isomorphisms to move this problem into the realm of abstract algebra where I am more comfortable, but this also led nowhere.

In trying out a few specific cases, I was able to come up with a few conjectures, but I was able to find counterexamples for all of them with a Python script I wrote. However, they definitely produced a similarly looking curve to the one generated by doing brute-force calculations of subsets.

My best conjecture was the following guess:

\[\frac{1}{k}\left(2 ^n + 2 ^q(\text{max}(k - 2 ^ r, 1))\left(2\left\lceil\frac{k}{2}\right\rceil-k\right)\right)\]

Conclusion

After working on this problem for about a month, I've learned so much about complex numbers and roots of unity. Although I still haven't found the answer, my process of learning about this area of math has been incredibly fun.

I think I want to revisit this problem after I study more complex analysis. I think there's a lot of well-known ideas that would directly apply to the problems I was having. Regardless, this was a really interesting challenge.

So if you've read this far, thanks for checking this out! Recently, I've been focusing more on some computer science stuff, so I might be writing about that soon! I've been going through Coursera's deep learning specialization and I'm working on an artificial intelligence for Mancala using a minimax algorithm. I've also been working on some classes at my local community college.

My sophomore year at Berkeley is going to start in about a month, and I'm really looking forward to writing about my classes. My schedule isn't finalized yet, but I'm thinking about taking Machine Structures (CS 61C), Efficient Algorithms and Intractable Problems (CS 170), Spanish 3, and either Real Analysis (MATH 104) or Probability and Random Processes (EECS 126). Whatever schedule I end up choosing, I'm hoping to use this platform as a way to write about things I find interesting and reinforce my understanding of things.

Anyways, I hope you enjoyed reading this article, and be sure to check back here soon for my next post!