Uniformly at Random

The Fine-Wilf Theorem

leave a comment »

The Fine-Wilf Theorem is as follows. Supppose (a_n)_{n \geq 0} and (b_n)_{n \geq 0} are two infinite periodic sequences with periods p and q respectively. If (a_n)_{n \geq 0} and (b_n)_{n \geq 0} agree on their first p+q-\gcd(p,q) terms then the two sequences are identical.

We present here the elegant algebraic proof given as the solution to Problem 134 in Bollobas’ book The Art of Mathematics and attributed by Bollobas to Ernst Straus.

We first define formal power series F(X) = \sum_{n \geq 0} a_n X^n and G(X) = \sum_{n \geq 0} b_n X^n. By the periodicity hypothesis, we have F(X) = P(X)/(1-X^p) and G(X) = Q(X)/(1-X^q) for some polynomials P,Q of maximum degrees p-1 and q-1 respectively. However, since (1-X^{\gcd(p,q)}) divides each of (1-X^p) and (1-X^q), we also have

F(X) - G(X) = [(1-X^q)P(X) - (1-X^p)Q(X)](1-X^p)^{-1}(1-X^q)^{-1} = (1-X^{\gcd(p,q)})R(X)(1-X^p)^{-1}(1-X^q)^{-1}

where R(X) is some polynomial of degree at most p+q-\gcd(p,q)-1. If the first p+q-\gcd(p,q) coefficients of F and G coincide, then the first p+q-\gcd(p,q) coefficients of F(X) - G(X) are zero, whence the polynomial R is the zero polynomial. It follows that F(X) - G(X) is identically zero, so that F and G and hence (a_n)_{n \geq 0} and (b_n)_{n \geq 0} are identical, as claimed.

We should point out that several other results that we have discussed in previous posts appear as problems in the previously mentioned book by Bollobas.


Written by uncudh

February 19, 2009 at 5:56 pm

Posted in math

Tagged with

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: