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

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

General discussion

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.

8947 reads
Subscribe

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

Sun, 19/04/2009 - 11:36 — gowers

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

Sun, 19/04/2009 - 11:41 — gowers

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

Mon, 20/04/2009 - 05:34 — dmoskovich

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!!!

Post new comment

(Note: commenting is not possible on this snapshot.)