adamant's blog

By adamant, history, 14 months ago, In English

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?
  • Vote: I like it
  • +179
  • Vote: I do not like it

| Write comment?
14 months ago, # |
  Vote: I like it +124 Vote: I do not like it

bro really wants the top contributors' first spot

14 months ago, # |
  Vote: I like it +129 Vote: I do not like it

adamant got that "obscure math blogs" pipeline working overtime

14 months ago, # |
Rev. 4   Vote: I like it +26 Vote: I do not like it

[there was a mistake in the text here which I can't seem to fix]

14 months ago, # |
  Vote: I like it +18 Vote: I do not like it

I don't understand. If you know that your recurrence is $$$p(x) / (1-x)^n$$$, then you can find $$$p(x)$$$ by multiplying the recurrence by $$$(1-x)^n$$$ and dropping the coefficients above the $$$n$$$-th. Then, to find the values from some $$$s$$$-th, you divide by $$$(1-x)^s$$$ or something, which is multiplying with

$$$\displaystyle (1-x)^{-s} = \sum\binom{-s}{i}\cdot(-x)^i = \sum\binom{s+i-1}{i}\cdot x^i,$$$

and these binomials are computed one by one with $$$O(1)$$$ time for recomputing the next one (with some care to wrap around zero, though). You use Q.inv(m) in your attached solution, while you could do it without polynomial division. And if this is what the UPD section is about, then you juggle with formulas that I don't really want to read into, and I hope that I clarified this moment a bit.

  • »
    14 months ago, # ^ |
    Rev. 5   Vote: I like it +1 Vote: I do not like it

    Huh? I'm not sure I understand. Why divide by $$$(1-x)^s$$$? In my implementation, I find $$$p(x)$$$ and then expand $$$p(x) / (1-x)^n$$$ to find first $$$2n$$$ values of $$$f(k)$$$, rather than the first $$$n$$$. Yes, this particular part could be done in a more efficient way as you described, but it's not what I'm doing in the UPD section, the UPD section is about computing $$$x^s \bmod (x-1)^{n+1}$$$ in $$$O(n)$$$.

    • »
      14 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Sorry, yes, I meant divide by $$$(1 - x)^n$$$, which is multiplying by $$$\sum\binom{n+i-1}{n-1}x^i$$$, and then taking coefficients from $$$s$$$ to $$$s + m - 1$$$; but this is the same as multiplying with the fps above, but starting with $$$(s-m+1)$$$-th coefficient, and then taking some coefficients from the result. Anyway, it can be done without the polynomial division, and what is happening is you multiply with $$$(1-x)^{-n}$$$ with the first $$$s-m$$$ coefficients dropped.

      • »
        14 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Ohh, I get it now. Yeah, that makes a lot of sense, thanks!

14 months ago, # |
  Vote: I like it -37 Vote: I do not like it