Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

Shift of polynomial sampling points

Revision en15, by adamant, 2023-05-04 13:35:10

Hi everyone!

Previously, I had a blog on how, given $s$ and a polynomial $f(x)$, to compute coefficients of the polynomial $f(x+s)$.

Today we do it in values space. Consider the problem Library Judge — Shift of Sampling Points of Polynomial. In this problem, you're given $s$ and the values $f(0), f(1), \dots, f(n)$ of a polynomial of degree at most $n$ and you need to find $f(s), f(s+1), \dots, f(s+n)$.

In particular, I used this to generate test cases for 1817C - Similar Polynomials, there might be other applications too.

#### General linear recurrence shift

If you have further questions about something here, please refer to this blog

Let's, for a moment, consider even more generic problem now. Let $f_0, f_1, \dots$ be a linear recurrence, such that

$f_m = a_1 f_{m-1} + \dots + a_{n+1} f_{m-(n+1)}.$

Given $s$ and $f_0, \dots, f_n$, we need to find $f_s, \dots, f_{s+n}$. The problem generalizes that of finding specific value $f_s$.

Generally, we can say that $f_s, \dots, f_{s+n}$ are the coefficients near $x^0, x^{-1}, \dots, x^{-n}$ of $x^s g(x^{-1})$, where

$g(x) = \sum\limits_{k=0}^\infty f_k x^k$

is the generating function of $f_k$. On the other hand, $g(x) = \frac{p(x)}{q(x)}$, where

$q(x) = 1-\sum\limits_{k=1}^{n+1} a_k x^k,$

and $p(x)$ is a polynomial of degree at most $n$. Let

$A(x) = x^{n+1} - \sum\limits_{k=1}^{n+1} a_k x^{(n+1)-k} = x^{n+1} q(x^{-1}),$

then $D(x) g(x^{-1}) = x^{n+1} p(x^{-1})$ only has positive powers of $x$ if $D(x)$ is divisible by $A(x)$. Thus, the coefficients near non-positive powers of $x^s g(x^{-1})$ will not change if we replace $x^s$ by its remainder modulo $A(x)$. So, we need coefficients near $x^0, x^{-1}, \dots, x^{-n}$ of the product $R(x) g(x^{-1})$, where $R(x) \equiv x^s \pmod{A}$. Note that only the first $2n+1$ coefficients of $g(x)$ affect the result, hence the whole problem may be solved in $O(n \log n \log s)$ for finding $R(x)$ and then $O(n \log n)$ to find $f_s, \dots, f_{s+n}$.

If you're not comfortable working with negative coefficients, a possibly simpler way to look on it is to notice that

$f_s = [x^{n+1}] \left(f_0 x^{n+1} + f_1 x^n + \dots + f_{n+1} \right) \cdot \left(x^s \bmod A\right).$

On the other hand, changing the first polynomial to $f_1 x^{n+1} + \dots + f_{n+2}$ would yield $f_{m+1}$ as a result. Altogether, it means that

$\left(f_0 x^{2n+1} + f_1 x^{2n} + \dots + f_{2n+1} \right) \cdot \left(x^s \bmod A\right)$

would yield the values $f_{s+n}, \dots, f_{s+1}, f_s$ in its coefficients near $x^{n+1}, x^{n+2}, \dots, x^{2n+1}$.

#### Shift in polynomials

In polynomials, it is possible to implement the solution above in $O(n \log n)$ instead of $O(n \log n \log s)$. For this we should note that $f(0), f(1), \dots$ also form a linear recurrence with a very specific characteristic polynomial $q(x) = (1-x)^{n+1}$.

Perhaps the simplest way to show it is by noticing that taking finite difference $\Delta f(k) = f(k) - f(k-1)$ for $n+1$ times will yield a zero polynomial, as $\Delta$ reduces the degree by $1$. Using a function $S$ such that $S f(k) = f(k-1)$, we can write it as

$\Delta^{n+1} f(k) = (1 - S)^{n+1} f(k) = \sum\limits_{i=0}^{n+1} (-1)^{i}\binom{n+1}{i} f(k-i) = 0,$

which shows that $(1-x)^{n+1}$ is the characteristic polynomial of the corresponding recurrence. Thus,

$R(x) \equiv x^s \pmod{(x-1)^{n+1}}$

can be transformed via substitution $x = t+1$ into

$R(t+1) \equiv (t+1)^s \pmod{t^{n+1}}.$

The identity above allows us to find

$R(t+1) = \sum\limits_{k=0}^n \binom{s}{k} t^k,$

from which we can obtain the final result by substituting $t=x-1$ back

$R(x) = \sum\limits_{k=0}^n \binom{s}{k} (x-1)^k,$

which can then be computed as a regular Taylor shift by $-1$ of $R(t+1)$ in $O(n \log n)$.

You can also refer to my solution on the Library Judge.

UPD: It was brought to my attention that $R(x)$ can be computed in linear time, as

$[x^k] R(x) = \sum\limits_{i=k}^n \binom{s}{i} \binom{i}{k} (-1)^{i-k} = \binom{s}{k} \sum\limits_{i=k}^n \binom{s-k}{i-k}(-1)^{i-k}.$

Then, using $\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$, we transform the later sum into a telescopic one:

$\sum\limits_{i=k}^n (-1)^{i-k} \left[\binom{s-k-1}{i-k-1} + \binom{s-k-1}{i-k} \right] = (-1)^{n-k}\binom{s-k-1}{n-k}.$

Thus, the full expression for $R(x)$ is

$R(x) = \sum\limits_{k=0}^{n} (-1)^{n-k} \binom{s}{k} \binom{s-k-1}{n-k} x^k.$

UPD2: Golovanov399 mentioned in the comments that there is a much simpler way of doing it for polynomials using the representation

$g(x) = \frac{p(x)}{(1-x)^{n+1}}$

of the generating function. As $(1-x)^{n+1}$ is a very well-behaved function, one may notice that

$\frac{1}{(1-x)^{n+1}} = \sum\limits_{k=0}^\infty \binom{n+k}{n} x^k,$

then one can find $f(s), \dots, f(s+n)$ by multiplying $p(x)$, which is obtained as

$p(x) = g(x) (1-x)^{n+1} \bmod{x^{n+1}},$

with the corresponding segment of coefficients of $(1-x)^{-(n+1)}$ near the $s$-th coefficient.

UPD3: It was brought to my attention that it is possible to do this in just a single convolution. Upon some further discussion with Golovanov399, we found out that the Lagrange interpolation on $f(0), \dots, f(n)$ can actually be written simply as

$f(k) = \sum\limits_{i=0}^n \binom{k}{i} \binom{n-k}{n-i} f(i).$

In particular, it also gives a much simpler and more concise expression for $R(x)$ from above:

$x^k \equiv \sum\limits_{i=0}^n \binom{k}{i} \binom{n-k}{n-i} x^i \pmod{x^{n+1}}.$

We also derived the following formula:

$\boxed{\frac{\partial^{n+1}}{\partial x^{n+1}}\left(\frac{(xy-1)^n}{n!} \log \frac{1}{1-x}\right) \equiv \frac{y^{n+1}}{1-xy} \pmod{(y-1)^{n+1}}}$

Applying the function $T(y^i) = f(i)$ to it, we get the identity for $k \geq 1$:

$[x^{n+k}] \left( \sum\limits_{i=0}^n \frac{(-1)^{n-i} f(i)}{i!(n-i)!} x^i \right) \left(\sum\limits_{j=1}^{\infty} \frac{x^j}{j} \right) = \frac{(k-1)!}{(n+k)!} f(n+k),$

which allows to find $f(s), \dots, f(s+n)$ in a single convolution with a sub-range of the coefficients of $\log\frac{1}{1-x}$.

The result above can also be found directly from manipulating coefficients in Lagrange interpolation formula. I kind of like it, but unfortunately we do not yet know if there is any meaningful interpretation to the result in terms of $x$ and $y$.

#### Questions to audience

• Is there a simpler solution here, preferably without heavy low-level work with coefficients...
• Is it possible to compute $R(x)$ directly, rather than as a Taylor shift?
• Are there other viable applications to doing this?

#### History

Revisions

Rev. Lang. By When Δ Comment
en15 adamant 2023-05-04 13:35:10 2 Tiny change: 'rac{(-1)^{j-i} f(i)}{' -> 'rac{(-1)^{n-i} f(i)}{'
en14 adamant 2023-05-04 13:32:31 1261 Tiny change: 'e identity\n\n$$\n[x' -> 'e identity for k \geq 1:\n\n$$\n[x'
en9 adamant 2023-05-02 13:36:12 2 Tiny change: 'inom{n+k}{k} x^k,\n$$' -> 'inom{n+k}{n} x^k,\n$$'
en7 adamant 2023-05-02 12:58:46 479 Tiny change: 'x)^{n+1}$. Perhaps th' -> 'x)^{n+1}$.\n\nPerhaps th'
en6 adamant 2023-05-02 12:45:27 608 Tiny change: 'that only first $2n$ coeffici' -> 'that only the first $2n+1$ coeffici'
en2 adamant 2023-05-01 20:47:54 1561 Tiny change: 'R(x)$and$$.' -> 'R(x)$ and then $O(n \log n)$ to find $f_s, \dots, f_{s+n}$.' (published)