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?
Tags polynomials

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en15 English adamant 2023-05-04 13:35:10 2 Tiny change: 'rac{(-1)^{j-i} f(i)}{' -> 'rac{(-1)^{n-i} f(i)}{'
en14 English 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'
en13 English adamant 2023-05-03 23:21:23 4
en12 English adamant 2023-05-03 11:50:02 11 doesn't seem true
en11 English adamant 2023-05-03 11:35:22 266
en10 English adamant 2023-05-03 10:57:51 444
en9 English adamant 2023-05-02 13:36:12 2 Tiny change: 'inom{n+k}{k} x^k,\n$$' -> 'inom{n+k}{n} x^k,\n$$'
en8 English adamant 2023-05-02 13:32:45 617 Tiny change: ' there is much simp' -> ' there is a much simp'
en7 English adamant 2023-05-02 12:58:46 479 Tiny change: 'x)^{n+1}$. Perhaps th' -> 'x)^{n+1}$.\n\nPerhaps th'
en6 English adamant 2023-05-02 12:45:27 608 Tiny change: 'that only first $2n$ coeffici' -> 'that only the first $2n+1$ coeffici'
en5 English adamant 2023-05-02 12:34:36 620 Tiny change: '] = (-1)^{k-n}\binom{s-' -> '] = (-1)^{n-i}\binom{s-'
en4 English adamant 2023-05-02 03:17:34 103
en3 English adamant 2023-05-01 21:25:01 13 Tiny change: 's too.\n\n#### G' -> 's too.\n\n[cut]<br>\n\n#### G'
en2 English 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)
en1 English adamant 2023-05-01 18:48:47 1739 Initial revision (saved to drafts)