In Elegia's blog How to composite (some) polynomials faster, we know how to compose some special power series in $$$\mathcal O(n\log n)$$$ time, especially for the quadratic rational fraction $$$(ax^2+bx+c)/(dx^2+ex+f)$$$ and the cubic polynomial $$$ax^3+bx^2+cx+d$$$. In this blog I will show how to use this method to calculate $$$\prod_{i=1}^n(x-g(i))$$$ in $$$\mathcal O(n\log n)$$$ time, where $$$g(x)$$$ is a quadratic rational fraction, written as $$$(ax^2+bx+c)/(dx^2+ex+f)$$$.

Basic Knowledge

Let's review how to calculate $$$f_n(x):=\prod_{i=1}^n(x-i)$$$ in $$$\mathcal O(n\log n)$$$ time. We solve this problem by recursion.

If $$$n$$$ is even, assuming we have already computed $$$f_{n/2}$$$, then $$$f_n(x)=f_{n/2}(x)\cdot f_{n/2}(x-n/2)$$$, which could be calculated in $$$\mathcal O(n\log n)$$$ time.

If $$$n$$$ is odd, assuming we have already computed $$$f_{n-1}$$$, then $$$f_n(x)=f_{n-1}(x)\cdot (x-n)$$$, which could be calculated in $$$\mathcal O(n)$$$ time.

Hence, we know that the time complexity of this algorithm is $$$T(n)=T(n/2)+\mathcal O(n\log n)$$$. According to Master Theorem, $$$T(n)=\mathcal O(n\log n)$$$.

Also, this is the classic solution for calculating (signed) Stirling numbers of the first kind $$${n\brack k}, 1\le k\le n$$$ in $$$\mathcal O(n\log n)$$$ time.

Main Tricks

For convenience, we may assume that $$$g(i)\neq0,\forall 1\le i\le n$$$.

From the above, we know how to find $$$\prod_{i=1}^n (x-g(i))$$$ when $$$g(x)=x$$$. At the same time, we know that we can use $$$ax+b,x^2,x^{-1}$$$ to construct a composition chain for any quadratic rational fractions. For example,

Therefore, it remains to show that if we can calculate $$$\prod_{i=1}^n (x-g(i))$$$ in $$$\mathcal O(n\log n)$$$ time, then so are $$$\prod_{i=1}^n [x-(ag(i)+b)],\prod_{i=1}^n (x-g(i)^2),\prod_{i=1}^n (x-1/g(i))$$$. Here, we regard $$$g(x)$$$ as some unknown function, not necessarily the quadratic rational fractions.

Let $$$G(x)=\prod_{i=1}^n (x-g(i))$$$.

For the first one, notice that

so we are done.

For the second one, notice that

so we are done.

For the third one, notice that

so we are done.

Quite easy!

As a reminder, $$$\prod_{i=1}^n (x-g(i)^k)$$$ could also be calculated in $$$\mathcal O(n\log n)$$$ time (omit $$$k$$$ in time complexity), if we acknowledge the existence of $$$k$$$-th primitive root.

Some Application

Using the ln-exp tricks, we can also calculate $$$\sum_{i=1}^n h(g(i)x)\bmod x^n$$$, where $$$g$$$ is quadratic rational fraction, $$$h$$$ is any power series. The key is to find out $$$\sum_{i=1}^n g(i)^j,1\le j\le n$$$, which is $$$-j[x^j]\log \prod_{i=1}^n(1-g(i)x)$$$. Therefore we are done!

Further Discussion

Compared to the basic element in the composition for cubic polynomial, we found that we didn't discuss how to calculate $$$\prod_{i=1}^n(x-g(i)^{1/2})$$$ yet! The main obstacle is that though it's easy to find $$$F(x)$$$ in the function equation $$$G(x)G(-x)=F(x^2)$$$ when $$$G(x)$$$ is known, we do not know how to solve $$$G(x)$$$ when $$$F(x)$$$ is given. Therefore, for any cubic polynomial $$$g(x)$$$, I don't know how to calculate $$$\prod_{i=1}^n(x-g(i))$$$ in $$$\mathcal O(n\log n)$$$ time.

Unfortunately!

Given that the function $$$f$$$ satisfies $$$f (1)=1 $$$, and for $$$n\ge 2$$$,

where $$$\varphi$$$ is Euler totient function.

You can find this sequence on OEIS.

The first 10 items of $$$f$$$ are: $$$1,1,2,3,4,6,6,9,10,12$$$.

The question is that how to find $$$f(1),f(2),\cdots,f(n)$$$ in $$$\mathcal O(n\log \log n)$$$ time.

I think this is a quite interesting problem, you can think for a while before see the solution below.

A wrong approach is assuming that $$$f$$$ is a multiplicative function, and trying to find $$$f(p),f(p^2),\cdots$$$ for every prime $$$p$$$.

Because from the example above, $$$f(6)=6\neq 1\times 2=f(2)\times f(3)$$$. The relaxed multiplication eliminates the multiplicative property.

Now here is the algorithm I found to solve this problem.

Firstly, we can rewrite this recursive formula as the DGF (Dirichlet Generating Function) form, that is

where $$$\tilde f$$$ stands for the DGF of $$$f$$$.

According to the Newton's method of DGF (I do not intend to elaborate on its principle here), if the first $$$\sqrt n$$$ items of $$$\tilde {f_0}$$$ are correct, we can find $$$f$$$ whose first $$$n$$$ items are correct through the following iterative formula.

In this formula, the time complexity for calculating $$$\tilde {f_0} ^ 2$$$ brutely is $$$\mathcal O(n) $$$, and the time complexity for multiplying by $$$2-\tilde \varphi$$$ is $$$\mathcal O(n \log \log n) $$$. As for $$$\tilde {f_0}$$$, we can directly calculate it through the definition in $$$\mathcal O(\sqrt n\log n)$$$ time.

In summary, we have an algorithm for calculating $$$f(1),f(2),\cdots,f(n)$$$ in $$$\mathcal O(n\log \log n)$$$ time, which is unexpected.