Roots of Unity Filter Part 3 - Roots of Unity Filter

Note

This is a three part series I wrote back in 2019 on a technique applicable to certain competitive math problems: roots of unity filters. See the first two parts for a recap of complex numbers and roots of unity respectively. This post will actually go over the technique as well as what kind of problems it can be applied to.

Warning

Many of the explanations for this section will not be rigorous proofs.

Guiding Problem

The main problem we are trying to tackle in this section is the following from one of Thomas Mildorf's mock AIMEs:

Example

Problem from Thomas Mildorf's Mock AIME 1: #11

Let SS denote the value of the sum

∑n=0668(−1)n(20043n)\sum_{n = 0}^{668}(-1)^n{2004 \choose 3n}

Determine SS

We can tackle this problem in a variety of ways, but the approach we will be using here is a technique known as roots of unity filter.

Description

Roots of unity filter is a technique that allows us to find the sum of every kkth coefficient in a polynomial with any given offset less than kk. For instance, if you had a polynomial with a degree of 2020, you could find the sum of the 2nd, 5th, 8th, ..., and 20th coefficients. This would correspond to every 3rd coefficient with an offset of 22.

While on its own the roots of unity filter doesn't have a lot of applications, it is especially powerful when applied to the binomial theorem. For instance, with the guiding problem, we can expand the summation to find the following;

(20040)−(20043)+(20046)−(20049)+...+(20042004)={2004 \choose 0} - {2004 \choose 3} + {2004 \choose 6} - {2004 \choose 9} + ... + {2004 \choose 2004} =
(20040)+(20046)+...+(20042004)−((20043)+(20049)+...+(20042001)){2004 \choose 0} + {2004 \choose 6} + ... + {2004 \choose 2004} - \left({2004 \choose 3} + {2004 \choose 9} + ... + {2004 \choose 2001}\right)

We can see that this problem is asking us to calculate the sum of every 6th binomial coefficient with an offset of 00 and then subtract the sum of every 6th binomial coefficient with an offset of 33.

We can apply the roots of unity filter if we had a polynomial that had binomial coefficients as its coefficients. We can obtain this with the following polynomial:

(x+1)n=(n0)+(n1)+(n2)+...+(nn)(x + 1)^n = {n \choose 0} + {n \choose 1} + {n \choose 2} + ... + {n \choose n}

To solve our problem from above, we can utilize the root of unity filter on this polynomial with n=2004n = 2004 to determine the sum of every 6th coefficient with offset 00 and the sum of every 6th coefficient with offset 33. Then, we can subtract the latter from the former and obtain the answer.

No Offset Version

The simplest method to apply roots of unity filter is when you're dealing with an offset of 00 since you don't have to do much work. If you want to find the sum of every nnth coefficient with an offset of 00 for a polynomial P(x)P(x), you can calculate it with the following expression, where ω\omega represents the smallest nthnth root of unity:

P(1)+P(ω)+P(ω2)+...+P(ωn−1)n\dfrac{P(1) + P(\omega) + P(\omega^2) + ... + P(\omega^{n - 1})}{n}

Essentially, we just have to plug in the nnth roots of unity, where nn is the desired cycle length, and then take the average of the results.

Explanation

To see why this works, we can utilize the following two facts that we proved previously about roots of unity:

ωn+i=ωi\omega^{n + i} = \omega^i
1+ω+ω2+...+ωn−1=01 + \omega + \omega^2 + ... + \omega^{n - 1} = 0

Armed with this information, we can examine what happens when we plug the roots of unity into the polynomial P(x)P(x). For this section, we're going to use a polynomial P(x)P(x) with a degree of 1010 and calculate the sum of every third term. However, this can be generalized to any degree polynomial for any cycle length. First of all, let's write a polynomial P(x)P(x) with a degree of 1010 as the following:

P(x)=a0+a1x+a2x2+a3x3+...+a10x10P(x) = a_0 + a_1x + a_2x^2 + a_3x^3 + ... + a_{10}x^{10}

When we plug in ω\omega as our root of unity, we obtain the following:

P(ω)=a0+a1ω+a2ω2+a3ω3+...+a10ω10P(\omega) = a_0 + a_1\omega + a_2\omega^2 + a_3\omega^3 + ... + a_{10}\omega^{10}

However, note that when the power of ω\omega exceeds 33, we can factor out ω3=1\omega^3 = 1. This means that after the term ω2\omega^2, the powers of ω\omega will repeat in a cycle of length 33. We can show this result with the other powers of ω\omega we are plugging in as well. Whenever we pass ω3i\omega^{3i} in our polynomial after passing in ωi\omega^i to the polynomial, we can factor out that ω3i=1\omega^{3i} = 1.

Since the terms of all of the polynomials are cyclic when plugging in the roots of unities, if we can show that summing all of the polynomials makes it so that only the coefficient of a0a_0 remain, it will necessarily apply to a3,a6,...a_3, a_6, ... as well. Therefore, we can direct our focus to what happens with the first 33 terms of the polynomial when we pass in 1,ω1, \omega, and ω2\omega^2.

We can make the following chart to look at what happens:

Root of Unitya0a_0a1a_1a2a_2
11111111
ω\omega11ω\omegaω2\omega^2
ω2\omega^211ω2\omega^2ω4\omega^4
Total Sum330000

The columns each correspond to what power we are raising each of the roots of unity, while the rows indicate each of the roots of unity. If we sum all of the columns, we will obtain how much of each coefficient we shall receive in the final sum.

Note that from the equation

1+ω+ω2+...+ωn−1=01 + \omega + \omega^2 + ... + \omega^{n - 1} = 0

all of the columns except for the one corresponding to a0a_0 end up with a sum of 00. In the third column, the equation is applied with just ω\omega plugged in, and in the fourth column, the equation is applied with ω2\omega^2 plugged in. Therefore, our result is just a0a_0 added 33 times, so we can divide by 33 to obtain our desired sum.

Again, remember that since the roots of unity are cyclic with a period of 33, the same values and chart will apply for a3a_3 through a5a_5, a6a_6 through a8a_8, etc. To see this, looking at the entire chart is useful, which is placed below for your convenience.

a0a_0a1a_1a2a_2a3a_3a4a_4a5a_5a6a_6a7a_7a8a_8a9a_9a10a_{10}
111111111111111111111111
ω\omega11ω\omegaω2\omega^2ω3=1\omega^3 = 1ω4=ω\omega^4 = \omegaω5=ω2\omega^5 = \omega^2ω6=1\omega^6 = 1ω7=ω\omega^7 = \omegaω8=ω2\omega^8 = \omega^2ω6=1\omega^6 = 1ω7=ω\omega^7 = \omega
ω2\omega^211ω2\omega^2ω4\omega^4ω6=1\omega^6 = 1ω8=ω2\omega^8 = \omega^2ω10=ω4\omega^{10} = \omega^4ω12=1\omega^{12} = 1ω14=ω2\omega^{14} = \omega^2ω16=ω4\omega^{16} = \omega^4ω18=1\omega^{18} = 1ω20=ω20\omega^{20} = \omega^{20}
Total Sum3300003300003300003300

Example

Find S=(100)+(104)+(108)S = {10 \choose 0} + {10 \choose 4} + {10 \choose 8} without calculating any binary coefficients

We can approach this problem by first realizing that we need to find the sum of every 4th coefficient in the polynomial:

(x+1)10(x + 1)^{10}

By applying the roots of unity filter, we can realize that this is equivalent to the following:

ω=cis(2π4)\omega = \text{cis}\left( \dfrac{2\pi}{4} \right)
(1+1)10+(ω+1)10+(ω2+1)10+(ω4+1)104\dfrac{(1 + 1)^{10} + (\omega + 1)^{10} + (\omega^2 + 1)^{10} + (\omega^4 + 1)^{10}}{4}
(2)10+(1+i)10+(0)10+(1−i)104\dfrac{(2)^{10} + (1 + i)^{10} + (0)^{10} + (1 - i)^{10}}{4}

We can then find this sum by converting each of the complex numbers to polar form, applying de Moivre's theorem, and then converting back to rectangular coordinates. While this may seem lengthy for a problem we could have just calculated the binomial coefficients for, it is a general technique that has the same number of terms even as the upper number increases to huge numbers.

We continue the calculation below for the sake of completeness:

(1+i)10=(2cis(π4))10=25cis(10π4)=25(0+i)=25i(1 + i)^{10} = \left(\sqrt{2}\text{cis}\left(\dfrac{\pi}{4}\right)\right)^{10} = 2^5\text{cis}\left(\dfrac{10\pi}{4}\right) = 2^5(0 + i) = 2^5i
(1−i)10=(2cis(−π4))10=25cis(−10π4)=25(0−i)=−25i(1 - i)^{10} = \left(\sqrt{2}\text{cis}\left(\dfrac{-\pi}{4}\right)\right)^{10} = 2^5\text{cis}\left(\dfrac{-10\pi}{4}\right) = 2^5(0 - i) = -2^5i
S=210+25i+0−25i4=28=256S = \dfrac{2^{10} + 2^5i + 0 - 2^5i}{4} = \boxed{2^8 = 256}

To check our answer, we can compute the binomial coefficients manually and get 1+210+45=2561 + 210 + 45 = 256.

Note

A frequent math competition technique is to plug 11 and −1-1 into a polynomial P(x)P(x), add them together, and then divide by 22 to cancel out all of the odd degree terms. This is actually the roots of unity filter being used with n=2n = 2 since 11 and −1-1 are the second roots of unity!

With Offset Version

While the previous version of roots of unity filter is already pretty powerful and can solve a lot of math problems, the more general version to find sums with offsets. Note that we still cannot solve our guiding problem because, in that problem, we have to be able to calculate the sum of the coefficients with a period pf 66, but with an offset of 33.

To get an idea of how this will work, we can once again look at the chart we created earlier that matches up what happens when we plug in each of the roots of unity for the terms in our polynomial.

Root of Unitya0a_0a1a_1a2a_2
11111111
ω\omega11ω\omegaω2\omega^2
ω2\omega^211ω2\omega^2ω4\omega^4
Total Sum330000

Note that the main reason this worked out was that we had 11 appear in every row for the term we wanted: a0a_0. That way, when we summed up the polynomial evaluated at each of the roots of unity, everything else would cancel out via the crucial identity

1+ω+ω2+...+ωn−1=01 + \omega + \omega^2 + ... + \omega^{n - 1} = 0

but the 11s would not.

This time, say that the desired coefficient is a1a_1, meaning that we want an offset of 11 instead of 00. To do this, the key is to add some coefficient in front of each term in our sum to ensure that our sum has 11s in the column for our desired term: a1a_1. Then, if we called those coefficients bib_i, the sum of every 3rd term with an offset of 1 would look like this:

b0P(1)+b1P(ω)+b2(ω2)3\dfrac{b_0P(1) + b_1P(\omega) + b_2(\omega^2)}{3}

To calculate these coefficients, we can use our table from above. Currently, it would look something like this, where all of our coefficients would be 11, meaning that the values for each row are not being changed.

Root of Unitybib_ia0a_0a1a_1a2a_2
1111111111
ω\omega1111ω\omegaω2\omega^2
ω2\omega^21111ω2\omega^2ω4\omega^4
Total Sum330000

However, by using the crucial property that ωn=1\omega^n = 1, we can adjust the coefficients for each row so that the 11s appear in the column for a1a_1 instead:

Root of Unitybib_ia0a_0a1a_1a2a_2
1111111111
ω\omegaω2\omega^2ω2\omega^211ω4\omega^4
ω2\omega^2ω\omegaω\omega11ω2\omega^2
Total Sum003300

With these coefficients chosen carefully, each sum now conveniently produces the values for a1a_1!

Note

I currently don't have a good explanation for why all of the other columns conveniently end up still canceling each other out no matter which column you choose to make the 11s generate in. To show that they do cancel out to 00 (they don't nicely use the equation shown before anymore), you have to do a bit of work, but it does work out.

With this, our equation to find the sum of every 3rd term with an offset of 11 looks like the following:

P(1)+ω2P(ω)+ωP(ω2)3\dfrac{P(1) + \omega^2 P(\omega) + \omega P(\omega^2)}{3}

Solving the Guiding Problem

Armed with this knowledge, we can know solve our guiding problem. If you need a refresher, the problem boils down to the following:

(20040)+(20046)+...+(20042004)−((20043)+(20049)+...+(20042001)){2004 \choose 0} + {2004 \choose 6} + ... + {2004 \choose 2004} - \left({2004 \choose 3} + {2004 \choose 9} + ... + {2004 \choose 2001}\right)

To do this, we need to find the sum of every 6th coefficient with an offset of 0 and the sum of every 6th coefficient with an offset of 3 for the polynomial

P(x)=(x+1)2004P(x) = (x + 1)^{2004}

We will call the first sum S1S_1 and the second sum S2S_2. We can apply the no offset roots of unity filter to calculate S1S_1:

ω=cis(2π6)=cis(π3)\omega = \text{cis}\left(\dfrac{2\pi}{6}\right) = \text{cis}\left(\dfrac{\pi}{3}\right)
S1=P(1)+P(ω)+P(ω2)+P(ω3)+P(ω4)+P(ω5)6S_1 = \dfrac{P(1) + P(\omega) + P(\omega^2) + P(\omega^3) + P(\omega^4) + P(\omega^5)}{6}

While we could plug this in and solve for S1S_1 directly, it would be incredibly difficult. However, we can proceed with calculating S2S_2 to see if we get any nice cancellations. We can apply our offsetted roots of unity filter to calculate S2S_2. To do so, we first need to find what our coefficients will be to get our column of 11s to shift to a3a_3, which will give us the offset of 33 that we need.

Root of Unitybib_iOriginal a3a_3Modified a3a_3
11111111
ω\omegaω3\omega^3ω3\omega^311
ω2\omega^211ω6\omega^611
ω3\omega^3ω3\omega^3ω9\omega^911
ω4\omega^411ω12\omega^{12}11
ω5\omega^5ω3\omega^3ω15\omega^{15}11

Note that the way we choose the coefficients bib_i is that we want the coefficient of ω\omega to increase so it becomes a multiple of n=6n = 6 and the coefficient evaluates to 11.

Then, we can calculate S2S_2 as:

ω3=cis(π)=−1\omega^3 = \text{cis}(\pi) = -1
S2=P(1)−P(ω)+P(ω2)−P(ω3)+P(ω4)−P(ω5)6S_2 = \dfrac{P(1) - P(\omega) + P(\omega^2) - P(\omega^3) + P(\omega^4) - P(\omega^5)}{6}

When we combine this with to get our total answer of S1−S2S_1 - S_2, we obtain the following:

S1−S2=P(1)+P(ω)+P(ω2)+P(ω3)+P(ω4)+P(ω5)−P(1)+P(ω)−P(ω2)+P(ω3)−P(ω4)+P(ω5)6S_1 - S_2 = \dfrac{\cancel{P(1)} + P(\omega) + \cancel{P(\omega^2)} + P(\omega^3) + \cancel{P(\omega^4)} + P(\omega^5) - \cancel{P(1)} + P(\omega) - \cancel{P(\omega^2)} + P(\omega^3) - \cancel{P(\omega^4)} + P(\omega^5)}{6}
S1−S2=P(ω)+P(ω3)+P(ω5)3S_1 - S_2 = \dfrac{P(\omega) + P(\omega^3) + P(\omega^5)}{3}

Now that our sum is greatly simplified, we can plug in P(x)=(x+1)2004P(x) = (x + 1)^{2004} and see what we can cancel out. The first thing we can notice is that ω3=−1\omega^3 = -1 as derived above, so our middle term cancels out to (1−1)2004=0(1 - 1)^{2004} = 0, so we can ignore that. The next thing we can do is calculate what ω\omega is in rectangular form so that we can add the 11 to it as part of P(x)P(x).

ω=cis(π3)=cos⁡(π3)+isin⁡(π3)=12+32i\omega = \text{cis}\left(\dfrac{\pi}{3}\right) = \cos\left(\dfrac{\pi}{3}\right) + i\sin\left(\dfrac{\pi}{3}\right) = \dfrac{1}{2} + \dfrac{\sqrt{3}}{2}i
P(ω)=(1+12+32i)2004=(32+32i)2004P(\omega) = \left(1 + \dfrac{1}{2} + \dfrac{\sqrt{3}}{2}i\right)^{2004} = \left(\dfrac{3}{2} + \dfrac{\sqrt{3}}{2}i\right)^{2004}

To calculate this, we can use de Moivre's theorem after converting 32+32i\dfrac{3}{2} + \dfrac{\sqrt{3}}{2}i to polar form.

∣32+32i∣=(32)2+(32)2=3\left|\dfrac{3}{2} + \dfrac{\sqrt{3}}{2}i\right| = \sqrt{\left(\dfrac{3}{2}\right)^2 + \left(\dfrac{\sqrt{3}}{2}\right)^2} = \sqrt{3}
arg(32+32i)=atan(33)=π6\text{arg}\left(\dfrac{3}{2} + \dfrac{\sqrt{3}}{2}i\right) = \text{atan}\left(\dfrac{\sqrt{3}}{3}\right) = \dfrac{\pi}{6}
P(ω)=(32+32i)2004=(3cis(π6))2004=31002cis(334π)=31002P(\omega) = \left(\dfrac{3}{2} + \dfrac{\sqrt{3}}{2}i\right)^{2004} = \left(\sqrt{3}\text{cis}\left(\dfrac{\pi}{6}\right)\right)^{2004} = 3^{1002}\text{cis}(334\pi) = 3^{1002}

We can do this with ω5\omega^5 as well.

ω5=cis(5π3)=cos⁡(5π3)+isin⁡(5π3)=12−32i\omega^5 = \text{cis}\left(\dfrac{5\pi}{3}\right) = \cos\left(\dfrac{5\pi}{3}\right) + i\sin\left(\dfrac{5\pi}{3}\right) = \dfrac{1}{2} - \dfrac{\sqrt{3}}{2}i
P(ω5)=(1+12−32i)2004=(32−32i)2004P(\omega^5) = \left(1 + \dfrac{1}{2} - \dfrac{\sqrt{3}}{2}i\right)^{2004} = \left(\dfrac{3}{2} - \dfrac{\sqrt{3}}{2}i\right)^{2004}
∣32−32i∣=(32)2+(32)2=3\left|\dfrac{3}{2} - \dfrac{\sqrt{3}}{2}i\right| = \sqrt{\left(\dfrac{3}{2}\right)^2 + \left(\dfrac{\sqrt{3}}{2}\right)^2} = \sqrt{3}
arg(32−32i)=atan(3−3)=−π6\text{arg}\left(\dfrac{3}{2} - \dfrac{\sqrt{3}}{2}i\right) = \text{atan}\left(\dfrac{\sqrt{3}}{-3}\right) = \dfrac{-\pi}{6}
P(ω5)=(32−32i)2004=(3cis(−π6))2004=31002cis(−334π)=31002P(\omega^5) = \left(\dfrac{3}{2} - \dfrac{\sqrt{3}}{2}i\right)^{2004} = \left(\sqrt{3}\text{cis}\left(\dfrac{-\pi}{6}\right)\right)^{2004} = 3^{1002}\text{cis}(-334\pi) = 3^{1002}

Therefore, our final sum evaluates to:

S1−S2=P(ω)+P(ω3)+P(ω5)3=31002+0+310023=2∗31001S_1 - S_2 = \dfrac{P(\omega) + P(\omega^3) + P(\omega^5)}{3} = \dfrac{3^{1002} + 0 + 3^{1002}}{3} = \boxed{2 * 3^{1001}}

Note

The original problem was part of a mock AIME and asked for the answer mod 10001000. Since this post is about roots of unity filter, we won't cover that part in depth, but to calculate the value mod 10001000, you could apply the Euler's Totient Theorem with ϕ(1000)=40\phi(1000) = 40 to find that 31001≡3 (mod 1000)3^{1001} \equiv 3 \text{ } (\text{mod } 1000). Then, the answer is (2∗3) mod 1000=006(2 * 3) \text{ mod 1000} = \boxed{006}.

Final Notes

Roots of unity filter is a super useful technique on some problems, but it can involve a lot of calculations and is not applicable to everything. For our guiding problem, we were fortunate enough to have all of our complex roots of unities dissipate nicely, which is something that you will frequently see for math competition problems that use roots of unity filter. Roots of unity filter can also be especially powerful when combined with generating functions. I might write an article on generating functions later, so stay tuned for that!

Generally, most problems will use the 4th roots of unity, which makes it incredibly convenient since all of the roots of unities are either entirely imaginary or entirely real. For less convenient problems, a calculator or some other clever insight may be necessary to evaluate the result.