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
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)$$$:
As you see, the result only depends on $$$x^2$$$, hence it is an even function.
Multisections
A multisection of a formal power series
is a formal power series $$$x^r f_{r,m}(x^m)$$$, defined as
In other words, a multisection is obtained by extracting equally spaced terms from the power series. From its definition it follows that
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
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
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
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:
Hence, the multisections are determined as
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
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
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
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:
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
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) — x^9 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:
