Hi everyone!
The task of finding the minimum linear recurrence for the given starting sequence is typically solved with the Berlekamp-Massey algorithm. In this article I would like to highlight another possible approach, with the use of the extended Euclidean algorithm.
Tl'dr.
The procedure below is essentially a formalization of the extended Euclidean algorithm done on $$$F(x)$$$ and $$$x^{m+1}$$$.
If you need to find the minimum linear recurrence for a given sequence $$$F_0, F_1, \dots, F_m$$$, do the following:
Let $$$F(x) = F_m + F_{m-1} x + \dots + F_0 x^m$$$ be the generating function of the reversed $$$F$$$.
Compute the sequence of remainders $$$r_{-2}, r_{-1}, r_0, \dots, r_k$$$ such that $$$r_{-2} = F(x)$$$, $$$r_{-1}=x^{m+1}$$$ and
Let $$$a_k(x)$$$ be a polynomial such that $$$r_k = r_{k-2} - a_k r_{k-1}$$$.
Compute the auxiliary sequence $$$q_{-2}, q_{-1}, q_0, \dots, q_k$$$ such that $$$q_{-2} = 1$$$, $$$q_{-1} = 0$$$ and
Pick $$$k$$$ to be the first index such that $$$\deg r_k < \deg q_k$$$. Let $$$q_k(x) = a_0 x^d - \sum\limits_{k=1}^d a_k x^{d-k}$$$, then it also holds that
for any $$$n \geq d$$$ and $$$d$$$ is the minimum possible. Thus, $$$q_k(x)$$$ divided by $$$a_0$$$ is the characteristic polynomial of the minimum linear for $$$F$$$.
More generally, one can say for such $$$k$$$ that
Linear recurrence interpolation
In the previous article on linear recurrences we derived that the generating function of the linear recurrence always looks like
where $$$P(x)$$$ and $$$Q(x)$$$ are polynomials and $$$\deg P < \deg Q$$$. In this representation, $$$Q(x) = 1 - \sum\limits_{k=1}^d a_k x^k$$$ corresponds to
Typical competitive programming task of recovering linear recurrence is formulated as follows:
Find Linear Recurrence. You're given $$$F_0, \dots, F_{m}$$$. Find $$$a_1, \dots, a_d$$$ with minimum $$$d$$$ such that $$$F_n = \sum\limits_{k=1}^d a_k F_{n-k}$$$.
In formal power series terms it means that we're given $$$F(x) = F_0 + F_1 x + \dots + F_{m}x^{m}$$$ and we need to find $$$\frac{P(x)}{Q(x)}$$$ such that
and $$$d$$$ is the minimum possible. Note that in this particular problem it is not required for $$$a_d$$$ to be $$$0$$$, hence $$$\deg Q \leq d$$$.
In this terms, as we will see later, what the problem asks us to find is essentially the Padé approximant of $$$F(x)$$$.
Padé approximants
Given a formal power series $$$f(x) = \sum\limits_{k=0}^\infty f_k x^k$$$, its Padé approximant of order $$$[p/q]$$$ is the rational function
such that $$$f(x) Q(x) \equiv P(x) \pmod{x^{p+q+1}}$$$. The Padé approximant is denoted $$$[p/q]_{f}(x) = R(x)$$$.
For normalization purposes, we will demand $$$b_q = 1$$$, that is $$$\deg Q(x) = q$$$, but it is acceptable to have $$$\deg P(x) \leq p$$$.
Explanation: The definition of Padé approximants requires some normalization, as you could obtain different representations of the same rational function by multiplying its numerator and denominator with the same polynomial. Most commonly used normalization is $$$b_0 = 1$$$. However, to guarantee $$$q = \deg Q$$$ and to easier deal with possible trailing zeros in the recurrence, we will use the normalization $$$b_q = 1$$$.
These definitions are different in terms of whether the Padé approximant for the given normalization exists. However, when $$$\deg P < \deg Q$$$, they're equivalent in a sense that when $$$Q(x) = 1-b_1 x - \dots - b_q x^q$$$ defines the linear recurrence
the reversed polynomial $$$x^q Q(x^{-1}) = b_q - b_{q-1}x - \dots - x^q$$$ defines the recurrence
Thus to find the first kind recurrence for $$$F_0,F_1,\dots,F_m$$$, we could find the second kind recurrence for $$$F_m, F_{m-1}, \dots, F_0$$$ instead.
Online Judge — Rational Approximation. Given $$$f(x)$$$, compute $$$p(x)$$$ and $$$q(x)$$$ of degrees at most $$$m-1$$$ and $$$n-1$$$ such that
Extended Euclidean algorithm
Let's look again on the condition
It translates into the following Bézout's identity:
where $$$K(x)$$$ is a formal power series. When $$$P(x)$$$ is divisible by $$$\gcd(F(x), x^{m+1})$$$ the solution to this equation can be found with the extended Euclidean algorithm. Turns out, the extended Euclidean algorithm can also be used to enumerate all $$$[p/q]_F$$$ with $$$p+q=m$$$.
Formalizing the algorithm
Let's formalize the extended Euclidean algorithm of $$$A(x)$$$ and $$$B(x)$$$. Starting with $$$r_{-2} = A$$$ and $$$r_{-1} = B$$$, we compute the sequence
If you're familiar with continued fractions, you could recognize, that this sequence corresponds to the representation
Same as with rational numbers, for such sequence it is possible to define the sequence of convergents
starting with
Now, one can prove the following identity:
In other words, we get three sequences $$$r_k$$$, $$$p_k$$$ and $$$q_k$$$ that define a family of solutions to the Bézout's identity.
Using $$$A(x) = x^{m+1}$$$ and $$$B(x) = F(x)$$$, we conclude that
Enumerating approximants
Let's estimate the degrees of $$$r_k$$$ and $$$q_k$$$ to estimate how they relate with Padé approximants.
It follows from the recurrence that $$$\deg q_{k} - \deg q_{k-1} = \deg a_k = \deg r_{k-2} - \deg r_{k-1}$$$, therefore
and
Multiplying both the numerator and the denominator of $$$\frac{(-1)^k r_k}{q_k}$$$ by $$$1,x,x^2,\dots,x^{\deg a_{k+1}-1}$$$, we get the Padé approximants $$$[p/q]_F$$$ for all $$$q$$$ from $$$\deg q_k$$$ to $$$\deg q_k + \deg a_{k+1}-1 = \deg q_{k+1}-1$$$, while also maintaining the inequality $$$p \leq m - q$$$.
Joining it together for all $$$q_k$$$ we see that all $$$[(m-q)/q]_F$$$ for $$$q$$$ from $$$0$$$ to $$$m$$$ are covered.
Thus, if you find $$$k$$$ such that $$$\deg q_k \leq q$$$ and $$$\deg q_{k+1} > q$$$, assuming $$$p+q=m$$$, it will hold that
Note that the Padé approximant is not necessarily unique (for example, $$$0 = \frac{0}{1+x} = \frac{0}{1+2x}$$$). However, if
then it is also true that
Assuming that both approximants satisfy the definition of $$$[(m-q)/q]_f$$$, we can conclude that
and
otherwise the identity
won't hold. That being said, $$$[(m-q)/q]_f$$$ found by the Euclidean algorithm provides the minimum possible $$$\deg P$$$ for a fixed $$$\deg Q = q$$$.
Finding the linear recurrence
In this notion, the minimum recurrence is defined by the first $$$k$$$ such that $$$\deg r_k < \deg q_k$$$ and has a characteristic polynomial $$$q_k$$$.
I have implemented the $$$O(n^2)$$$ algorithm as a part of my polynomial algorithms library:
// Returns the characteristic polynomial
// of the minimum linear recurrence for
// the first d+1 elements of the sequence
poly min_rec(int d = deg()) const {
// R1 = reversed (Q(x) mod x^{d+1}), R2 = x^{d+1}
auto R1 = mod_xk(d + 1).reverse(d + 1), R2 = xk(d + 1);
auto Q1 = poly(T(1)), Q2 = poly(T(0));
while(!R2.is_zero()) {
auto [a, nR] = R1.divmod(R2); // R1 = a*R2 + nR, deg nR < deg R2
tie(R1, R2) = make_tuple(R2, nR);
tie(Q1, Q2) = make_tuple(Q2, Q1 + a * Q2);
if(R2.deg() < Q2.deg()) {
return Q2 / Q2.lead(); // guarantee that the highest coefficient is 1
}
}
assert(0);
}
You can see this Library Judge submission for further details.
Also here is a library-free version, if you prefer it.
Half-GCD algorithm
The notion above provides the basis to construct the $$$O(n \log^2 n)$$$ divide and conquer algorithm of computing $$$\gcd(P, Q)$$$ in polynomials and finding the minimum linear recurrence. I have a truly marvelous demonstration of this proposition that this margin is, unfortunately, too narrow to contain. I hope, I will be able to formalize the process for good and write an article about it sometime...
As a teaser, here's an example of the problem, that (probably) requires Half-GCD:
Library Checker — Inv of Polynomials. You're given $$$f(x)$$$ and $$$h(x)$$$. Compute $$$f^{-1}(x)$$$ modulo $$$h(x)$$$.
Let $$$\frac{f(x)}{h(x)} = [a_0; a_1, \dots, a_k]$$$ and $$$\frac{p_{k-1}}{q_{k-1}} = [a_0; a_1, \dots, a_{k-1}]$$$, then $$$f q_{k-1} - h p_{k-1} = (-1)^{k-2} r_k = (-1)^{k-2} \gcd(f, p)$$$.
Therefore, if $$$r_{k} = \gcd(f, h)$$$ is non-constant, the inverse doesn't exist. Otherwise, the inverse is $$$(-1)^{k-2} q_{k-1}(x)$$$.
In the problem, $$$n \leq 5 \cdot 10^4$$$, therefore you need to do something better than $$$O(n^2)$$$ Euclidean algorithm.