Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $P\in\mathbb{Z}[x]$ be a given polynomial of degree $d$. I want to find the unique polynomial $Q\in\mathbb{Z}[x]$ of degree $d$ such that $Q(x)-Q(x-1)-Q(x-2)=P(x)$. It is possible to construct the solution writing $Q=\sum a_i x^i$ and solving the equation first for $a_n$, then for $a_{n-1}$ and so on, but this method requires $O(d^2)$ computations. I would like to solve it using $O(d)$ steps.

Motivation: Let us consider the recurrence $a_n=a_{n-1}+a_{n-2}+P(n)$ (with $a_0$ and $a_1$ given). It is easy to see that $a_n$ can be expressed as follows: $$ a_n=\alpha F_n + \beta F_{n+1} + Q(n), $$ with $\alpha=a_1-a_0+Q(0)-Q(1)$ and $\beta=a_0-Q(0)$. This comes from a problem in SPOJ.

One possible approach: Assume we want to compute $a_n$ modulo some prime $p$ (which is small compared with $d$). We can compute $P(0)$, $P(1)$, ...,$P(p-1)$ (this can be done with $O(pd)$ operations) and get a linear system of $p$ equations and $p$ variables $Q(0)$, $Q(1)$, ..., $Q(p-1)$. The matrix of this system is almost triangular and it is easy to solve the system.
Example: $p=5$ $$ \begin{pmatrix} 1 & 0 & 0 & -1 & -1 \\ -1 & 1 & 0 & 0 & -1 \\ -1 & -1 & 1 & 0 & 0 \\ 0 & -1 & -1 & 1 & 0 \\ 0 & 0 & -1 & -1 & 1 \\ \end{pmatrix}\begin{pmatrix}Q(0)\\Q(1)\\Q(2)\\Q(3)\\Q(4)\end{pmatrix}= \begin{pmatrix}P(0)\\P(1)\\P(2)\\P(3)\\P(4)\end{pmatrix} $$ This system can be solved in $O(p)$, by precomputing some Fibonacci numbers.
In this way, It is possible to compute $a_n\mod p$ using $O(dp)$ steps. The most expensive part is the computation of the values of $P$.

Question: Is it possible to get a nice closed expression for $Q$ which allows us to compute a particular value $Q(n)$ relatively fast? It does not matter if the answer is modulo $p$ (but it should work for any $p$).

share|improve this question
    
You lost me at "This system can be solved in $O(p)$, by precomputing some Fibonacci numbers." I would have thought solving $p$ linear equations, or congruences, would take $O(p^2)$. –  Gerry Myerson Jul 11 '13 at 10:23
2  
The system is not a general one. The matrix is almost triangular. I compute $Q(0)$ and $Q(1)$ (using those Fibonacci numbers) and then the rest of the values follow from $Q(x)=Q(x-1)+Q(x-2)+P(x)$. –  Quimey Jul 11 '13 at 10:58

1 Answer 1

This is mostly working.

Let me cosmetically change your equation to $-R(x) + R(x-1) +R(x-2) = P(x)$, where $R(x) = -Q(x)$.

As you mentioned, we could try and find certain values. Observe that:
If $P_0(x) = 1$, then $R_0(x) = 1$.
If $P_1(x) = x$, then $R_1(x) = x+3$.
If $P_2(x) = x^2$, then $R_2(x) = x^2 + 6x + 13$.
If $P_3(x) = x^3$, then $R_3(x) = x^3 + 9x^2 + 39x + 81 $.

We begin to see a pattern form. Observe that if $P_n(x) = x^n$, and we have an $R_n(x)$, then for $P_{n-1} (x) = x^{n-1} $, we have

$$ P_{n-1} (x) = \frac{ P_n ' (x)}{n} = \frac{ -R_n '(x) +R'(x-1)+R'(x-2) } {n} $$

Hence, this tells us that $R_{n-1} (x) = \frac{R_n ' (x)}{n} $ is a solution. From your claim of uniqueness (which is easily proved), this is the only solution. As such, this allows us obtain that $R_n(x) = n \int R_{n-1}(x) \, dx + C_n$, where $C_n=R_n(0)$ is to be determined.

Let $S_n (x) = R_n(x) - R_n(0)$, which is the indefinite integral of $R_{n-1}$. We get that

$$- S_n(1) - C_n + C_n + S_n(1) + C_n = 1 \Rightarrow C_n = 1 + S_n(1) - S_n(-1)$$

At this point in time, the calculations are still on the order of $O(n^2)$.

However, if we add the condition that we're only interested in mod $p$, then a lot of the calculations can be simplified / cancelled out. In particular, $R_p(x) \equiv x^p + 3 \pmod {p}$.

share|improve this answer
    
+1 for the trick with the integral, but I can't see how to reduce the computation time. Assume that you get all the $R_i$ for free. In order to get $R$ you have to take a linear combination of the $R_i$ and this is still $n^2$. –  Quimey Jul 12 '13 at 11:29
    
@Quimey I agree, as stated that was mostly working, and I can't get any aspect of it to shorten. –  Calvin Lin Jul 14 '13 at 19:07

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.