adamant's blog

Polynomials and roots of unity
By adamant, history, 3 years ago, In English

Hi everyone!

Today I'd like to write a bit on the amazing things you can get out of a power series by putting roots of unity into its arguments. It will be another short story without any particular application in competitive programming (at least I don't know of them yet, but there could be). But I find the facts below amazing, hence I wanted to share them.

You're expected to know some basic stuff about the discrete Fourier transform and a bit of linear algebra to understand the article.

Bisections

To begin with, let's start with the most simple non-trivial system of roots of unity. That is, with $$$\{1, -1\}$$$.

Let $$$f(x)$$$ be a formal power series of $$$x$$$. If you represent it as $$$f(x)=f_0(x^2)+x f_1(x^2)$$$, you might note that

$$$ \begin{matrix} f_0(x^2) = \frac{f(x)+f(-x)}{2},& f_1(x^2) = \frac{f(x)-f(-x)}{2x}. \end{matrix} $$$

The functions $$$f_0(x^2)$$$ and $$$xf_1(x^2)$$$ are called the bisections of $$$f(x)$$$. As you see, they're closely related to $$$f(x)$$$ and $$$f(-x)$$$.

Another interesting function you could get is by multiplying $$$f(x)$$$ and $$$f(-x)$$$:

$$$ f(x)f(-x) = f_0^2(x^2) - x^2 f_1^2(x^2). $$$

As you see, the result only depends on $$$x^2$$$, hence it is an even function.

Multisections

A multisection of a formal power series

$$$ f(x) = \sum\limits_{k=0}^\infty a_k x^k $$$

is a formal power series $$$x^r f_{r,m}(x^m)$$$, defined as

$$$ x^r f_{r,m}(x^m) = \sum\limits_{k=0}^\infty a_{km+r} x^{km+r}. $$$

In other words, a multisection is obtained by extracting equally spaced terms from the power series. From its definition it follows that

$$$ \boxed{f(x) = \sum\limits_{r=0}^{m-1} x^r f_{r,m}(x^m)} $$$

which is an equivalent way to define a multisection.

Discrete Fourier transform

As we saw, for $$$m=2$$$ it is possible to construct multisections as linear combinations of $$$f(x)$$$ and $$$f(-x)$$$. A natural question one might ask is if it is possible to construct a closed-form expression for the multisections knowing only $$$f(x)$$$. And it turns out, it is possible to do so.

Let $$$\omega$$$ be the $$$m$$$-th root of unity, that is $$$\omega^m=1$$$ and $$$\omega^k \neq 1$$$ for $$$k < m$$$. Then it holds that

$$$ f(\omega x) = \sum\limits_{r=0}^{m-1} \omega^r x^r f_{r,m}(x^m \omega^m) = \sum\limits_{r=0}^{m-1} \omega^r x^r f_{r,m}(x^m). $$$

Likewise, for $$$f(\omega^k r)$$$ we will get roughly the same formula except for $$$\omega^{rk}$$$ instead of $$$\omega^r$$$. It essentially means that if we let

$$$ F(y) = \sum\limits_{r=0}^{m-1} y^r x^r f_{r,m}(x^m), $$$

it would hold that $$$f(\omega^k x) = F(\omega^k)$$$, where $$$F(y)$$$ is, in fact, a polynomial in $$$y$$$. Let $$$F_r(x) = x^r f_{r,m}(x^m)$$$, then

$$$ F(\omega^k) = \sum\limits_{r=0}^{m-1} F_r(x) (\omega^k)^r = f(\omega^k x). $$$

In other words, $$$F(1), F(\omega), \dots, F(\omega^{m-1})$$$ is the Fourier transform of the sequence $$$F_0, F_1, \dots, F_{m-1}$$$.

From this follows that multisections $$$F_0(x), F_1(x), \dots, F_{m-1}(x)$$$ could be recovered with the inverse Fourier transform:

$$$ F_r(x) = \frac{1}{m} \sum\limits_{k=0}^{m-1} \omega^{-kr} F(\omega^k). $$$

Hence, the multisections are determined as

$$$ \boxed{x^r f_{r, m}(x^m) = \frac{1}{m} \sum\limits_{k=0}^{m-1} \omega^{-kr} f(\omega^kx)} $$$

For example, with $$$m=2$$$ we will get the same formulas for bisections that were derived above and for $$$m=3$$$ it will hold that

$$$ \begin{matrix} f_{0,3}(x^3) = \frac{f(x)+f(\omega x) + f(\omega^2 x)}{3},& f_{1,3}(x^3) = \frac{f(x)+ \omega^2 f(\omega x) + \omega^1 f(\omega^2 x)}{3x},& f_{2,3}(x^3) = \frac{f(x)+ \omega^1 f(\omega x) + \omega^2 f(\omega^2 x)}{3x^2}. \end{matrix} $$$

Kronecker delta

Another interesting way to explain this result is with the notion of Kronecker delta over $$$\mathbb Z_m$$$:

$$$ \delta_m(k) = \begin{cases} 1,&k \equiv 0 \pmod m,\\ 0,&\text{ otherwise}. \end{cases} $$$

In this notion,

$$$ x^r f_{r, m}(x^m) = \sum\limits_{k=0}^\infty \delta_m(k - r) a_k x^k. $$$

But at the same time, $$$\delta_m (x)$$$ can be expressed in a following way:

$$$ \delta_m(x) = \frac{1}{m} \sum\limits_{k=0}^{m-1} \omega^{kx}. $$$

Indeed, when $$$x \equiv 0 \pmod{m}$$$, every summand is $$$1$$$, and otherwise the sum equates to $$$\frac{1-\omega^{xm}}{1-\omega^x}=0$$$.

Putting it in the expression above, we get

$$$ x^r f_{r,m}(x^m) = \frac{1}{m}\sum\limits_{k=0}^\infty \sum\limits_{i=0}^{m-1}\omega^{i(k-r)} a_k x^k = \frac{1}{m}\sum\limits_{i=0}^{m-1}\omega^{-ir} \sum\limits_{k=0}^\infty \omega^{ik} a_k x^k = \frac{1}{m}\sum\limits_{i=0}^{m-1}\omega^{-ir} f(\omega^i x), $$$

which is the same formula as above.

Sums and products

I promise that the following problem is somewhat related to what's going on:

102129G - Permutant. Each row of the matrix $$$A$$$ is the same permutation of the previous row. Find $$$\det A$$$.

From the formulas above it follows that

$$$ \sum\limits_{k=0}^{m-1} f(\omega^k x) = m f_{0,m}(x^m). $$$

It's even more interesting that the product of such functions is also a function of $$$x^m$$$, same as $$$f(x)f(-x)$$$ is a function of $$$x^2$$$. Let

$$$ T(x) = \prod\limits_{k=0}^{m-1} f(\omega^k x) = \prod\limits_{k=0}^{m-1} F(\omega^k). $$$

For such $$$T(x)$$$ it holds that $$$T(\omega x) = T(x)$$$, as it just reorders the quotients. It, in turn, implies that whenever there is an $$$a_k x^k$$$ summand it must hold that $$$a_k = a_k \omega^k$$$, which only happens when $$$m$$$ divides $$$k$$$. By definition, it is equivalent to $$$T(x)$$$ being a function of $$$x^m$$$.

Is there any way to define this function explicitly in terms of the multisections $$$x^r f_{r,m}(x^r)$$$, as it was done with $$$f(x)f(-x)$$$? Yes, there is! Turns out, $$$T(x)$$$ can be represented as the determinant of the following circulant matrix:

$$$ T(x) = \det \begin{pmatrix} F_0 & F_{1} & \cdots & F_{m-2} & F_{m-1} \\ F_{m-1} & F_0 & F_{1} & & F_{m-2} \\ \vdots & F_{m-1} & F_0 & \ddots & \vdots \\ F_{2} & & \ddots & \ddots & F_{1} \\ F_{1} & F_{2} & \cdots & F_{m-1} & F_0 \\ \end{pmatrix} $$$

This is due to the fact that $$$F(1), F(\omega),\dots, F(\omega^{m-1})$$$ are the eigenvalues of such matrix (follows from generic circulant matrix properties) and thus its determinant is the product of its eigenvalues. So, in particular

$$$ f(x)f(-x) = \det\begin{pmatrix} f_{0,2} & x f_{1,2} \\ x f_{1,2} & f_{0,2} \end{pmatrix} = f_0^2(x^2) - x^2 f_1^2(x^2). $$$

and for $$$m=3$$$ it holds that

$$$\begin{align} f(x)f(\omega x)f(\omega^2 x) &= \det\begin{pmatrix} f_{0,3} & x f_{1,3} & x^2 f_{2,3} \newline x^2 f_{2,3} & f_{0,3} & x f_{1,3} \newline x f_{1,3} & x^2 f_{2,3} & f_{0,3} \newline \end{pmatrix} \newline &= f_{0,3}^3(x^3) + x^3 f_{1,3}^3(x^3) + x^6 f_{2,3}^3(x^3) - 3x^3 f_{0,3}(x^3) f_{1,3}(x^3) f_{2,3}(x^3). \end{align}$$$

From this follows that the product of $$$f(\omega^k x)$$$ is not only the function of $$$x^m$$$, but also preserves the ring of coefficients of the original series. In other words, if $$$f(x)$$$ is, for example, a power series with integer coefficients, so will be the product of $$$f(\omega^k x)$$$.

Another convenient and compact way to denote the product of $$$f(\omega^k x) = F(\omega^k)$$$ is as the resultant:

$$$ \prod\limits_{k=0}^{m-1} F(\omega^k) = \text{Res}(F(y), y^m-1). $$$
  • Vote: I like it
  • +72
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +22 Vote: I do not like it

Nice blog! I am not aware of a lot of applications in competitive programming myself, however this trick is well-known, among people who do mathematical Olympiads, as the roots of unity trick. It has been mentioned on Codeforces at least once (for instance, this blog). It's used in a wide variety of contexts, such as hard number theory problems (like this, this and this), tiling and similar stuff in combinatorics (like this).

As noted in the blog, it is the reason why Fourier transform works. Generalizations via Pontryagin duality also exist (and are discussed in this blog). Another way of looking at the continuous form of the roots of unity filter is to note that the Cauchy integral formula for a circle around a point essentially gives a similar statement (more here).

→ Reply