Polynomials and roots of unity

#	User	Rating
1	tourist	4009
2	jiangly	3821
3	Benq	3736
4	Radewoosh	3631
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3388
10	gamegame	3386

#	User	Contrib.
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	161
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

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 a 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(r - k) 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). $$$