Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

Shift of polynomial sampling points

Revision en6, by adamant, 2023-05-02 12:45:27

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),,f(n) of a polynomial of degree at most n and you need to find f(s),f(s+1),,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 f0,f1, be a linear recurrence, such that

fm=a1fm1++an+1fm(n+1).

Given s and f0,,fn, we need to find fs,,fs+n. The problem generalizes that of finding specific value fs.

Generally, we can say that fs,,fs+n are the coefficients near x0,x1,,xn of xsg(x1), where

g(x)=k=0fkxk

is the generating function of fk. On the other hand, g(x)=p(x)q(x), where

q(x)=1n+1k=1akxk,

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

A(x)=xn+1n+1k=1akx(n+1)k=xn+1q(x1),

then D(x)g(x1)=xn+1p(x1) only has positive powers of x if D(x) is divisible by A(x). Thus, the coefficients near non-positive powers of xsg(x1) will not change if we replace xs by its remainder modulo A(x). So, we need coefficients near x0,x1,,xn of the product R(x)g(x1), 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}. 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-n-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-n-1}{n-k} x^k.

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)