Tricki
a repository of mathematical know-how

Proving linear independence of polynomials asymptotically

Quick description

If you need to prove that a family of polynomials are linearly independent, examine their asymptotic behaviour as the variables tend to \infty.

Prerequisites

High-school algebra

Note iconAttention This article is in need of attention. This article needs to be properly classified.

General discussion

Note iconContributions wanted This section could use additional contributions. This article needs more (and better) examples. Is there a traceable origin to this trick? Is it an example of a more general trick?

If you need to prove linear independence of a big family of frightening-looking polynomials over \Q or over \R, replace your variables x_1,\ldots,x_n with polynomials in t^{a_1},\ldots,t^{a_n} with a_1>a_2>\cdots>a_n>0 real numbers, with a_{i}-a_{i+1}< a_{i+1}-a_{i+2} < 2(a_{i}-a_{i+1}) for i=1,\ldots,n-2 or some permutation thereof, and examine the leading terms of your polynomials as t tends to \infty. If each polynomial in your family behaves differently `at \infty', you know that they cannot be linearly dependent— and only the leading terms need to be considered! Experiment with different substitutions in order to uncover the relevant asymptotic properties.

Example 1

This example is from Section 4 of math/0511602.

Set

P_2(y_1,y_2,y_3) = (y_1-y_2)^2 + (y_2-y_3)^2 + (y_3-y_1)^2 ,
P_3(y_1,y_2,y_3) = (y_1-y_2)(y_2-y_3)(y_3-y_1) ,
P_4(y_1,y_2,y_3,y_4) = (y_1-y_3)(y_2-y_3)(y_1-y_4)(y_2-y_4),

where y_1+y_2+y_3+ y_4= 0. We would like to show that the following polynomials are linearly independent over \Q

Q^{n,m,k} = \big( P_2(y_1,y_2,y_3)^n P_3(y_1,y_2,y_3)^{2m+3} + P_2(y_4,y_3,y_2)^n P_3(y_4,y_3,y_2)^{2m+3}  \quad + P_2(y_3,y_4,y_1)^n P_3(y_3,y_4,y_1)^{2m+3} + P_2(y_2,y_1,y_4)^n P_3(y_2,y_1,y_4)^{2m+3} \big)  \times \big( P_4(y_1,y_2,y_3,y_4)^k + P_4(y_1,y_3,y_2,y_4)^k + P_4(y_1,y_4,y_2,y_3)^k \big)

with n+2k+3m=d and k>0 for some fixed d\in \N.

We first make the substitution

y_1 = (3 t^a - t^b - t^c)/4,
y_2 = (- t^a +3 t^b - t^c)/4,
y_3 = (- t^a - t^b +3 t^c)/4,
y_4 = -(t^a + t^b + t^c)/4,

where a>b>c>0 are real numbers and a-b< b-c < 2(a-b). Although other substitutions were also possible, we chose this substitution so as to keep expressions of the form y_i-y_j (with i,j=1,2,3,4) as simple as possible, because the polynomials P_2, P_3, and P_4 which make up Q^{n,m,k} are given in terms of such expressions. Thus

y_1-y_4 = t^a,
y_2-y_4 = t^b,
y_3-y_4 = t^c.

A routine calculation gives the leading term of Q^{n,m,k} as 2^n(2m+3)t^{2(n+2m+k+3)a+2(m+k+1)b+c}. This implies that the only possible linear relations between the Q^{n,m,k}'s are between those having the same value of (n+2m+k,m+k).

Repeat the same trick again, this time making the substitution

y_1 = (2 t^a - t^c)/4 + t^b/2 ,
y_2 = (2 t^a - t^c)/4 - t^b/2 ,
y_3 = (-2 t^a + 3 t^c)/4 ,
y_4 = -(2 t^a + t^c)/4 ,

where this time a>b>c>0 are real numbers satisfying b-c< a-b < 2(b-c). Again, we chose this substitution to keep the differences y_i-y_j as simple as possible, while being different from the first substitution. In this case

y_1-y_4 = t^a + t^b/2,
y_2-y_4 = t^a - t^b/2,
y_3-y_4 = t^c,
y_1-y_2 = t^b.

This time the leading term of Q^{n,m,k} in terms of these new variables is 2^{n+1}(n+2m+3)t^{(2(n+2m+2k)+5)a+(2m+3)b+c}. This implies that the only possible linear relations between the Q^{n,m,k}'s are between those having the same value of (n+2m+2k,m). Combining both results proves linear independence of the Q^{n,m,k}'s.

Comments

Inline comments

The following comments were made inline in the article. You can click on 'view commented text' to see precisely where they were made.

Am I right in thinking that

Am I right in thinking that the words "are linearly independent" are missing at the end of this sentence?

Inline comments

The following comments were made inline in the article. You can click on 'view commented text' to see precisely where they were made.

I feel as though if I thought

I feel as though if I thought about this for long enough and checked all the calculations then I would eventually see why you chose this particular substitution. But it would be nice if you could add a little here, to say something like, "We are trying to do such-and-such, so we want the P_i to be in such-and-such a form. This gives us the following equations ... and solving those equations we arrive at the following substitution." Is it possible to present a fully motivated account along these lines? By the way, this is a great trick to have on the site: starting with something that looks terrifying and showing that in fact it isn't.

It's to make the differences

It's to make the differences y_i-y_j as simple as possible, as these are what the polynomials are built up out of. I added that into the text- thanks!!!