[All references to [Permission pending] refer to the same individual's
name or email address -- djr]
==============================================================================
From: [Permission pending]
Newsgroups: sci.math
Subject: Polynomial problem
Date: 3 Feb 1995 10:00:29 -0000
Keywords: linear independence, polynomials

Suppose we have the polynomial ring Q[X]=Q[x1,...,xn] in n 
indeterminants. Let P={p1,...,pk} be a Q-linearly independent set,
i.e. if

	a1*p1 + ... + ak*pk = 0   (for ai in Q)

then necessarily a1=...=ak=0. Note that this is Q-linear
dependence, *not* Q[X]-linear dependence.

Can we place a restriction on another polynomial p in Q[X] such
that the set P'={p1,...,pk,p} is still linearly independent over
Q ?? I'd like to be able to discuss the condition without
expanding polynomials if possible - I have my polynomials 
expressed as products of factors for brevity and would like to
keep them this way. Perhaps looking at leading terms/trailing
terms, etc. would be good. For example, if the leading term of
p is strictly bigger than the leading terms of p1,...,pk then
P' will certainly be linearly independent still.

Replies via e-mail or here would be appreciated.

[Permission pending]

==============================================================================
[I responded, something along the lines of evaluating the polynomials at
a number of points equal to the degrees, and looking for linear relations
among the values -- djr]
==============================================================================

To: rusin@math.niu.edu (Dave Rusin)
Subject: Re: Polynomial problem 
Date: Mon, 06 Feb 1995 14:02:10 +0000
From: [Permission pending]


Dear Dave,

Thanks for your reply to my sci.math posting. I include below an example
of what I had in mind to see whether you still feel that the approach you
suggested is applicable here:

A typical set of my polynomials may look something like this:

	p1 = x1x2(x1+x2)

	p2 = x1(x2+x3)(x1+x2+x3)
	
	p3 = (x1+x2)x3(x1+x2+x3)

	p4 = x2x3(x2+x3)

Now any three of these are Q-linearly independent - how can I decide
that I cannot add another of the pi's without destroying this independence?

Thanks again,

[Permission pending]

==============================================================================

Date: Wed, 15 Feb 95 16:23:24 CST
From: rusin (Dave Rusin)
To: [Permission pending]
Subject: Re: Polynomial problem

I must apologize for delaying so long in responding to you; your letter
got swept into another mailbox I thought I was done with.

You wrote:
>A typical set of my polynomials may look something like this:
>	p1 = x1x2(x1+x2)
>	p2 = x1(x2+x3)(x1+x2+x3)
>	p3 = (x1+x2)x3(x1+x2+x3)
>	p4 = x2x3(x2+x3)
>Now any three of these are Q-linearly independent - how can I decide
>that I cannot add another of the pi's without destroying this independence?

I had not realized you were posting about polynomials in several variables.

The statement that the  pi  are linearly dependent can be phrased by
noting there are nonzero constants  a1 a2 a3 a4  so that   Sum( ai pi(v) ) = 0
for all vectors  v=(x1,x2,x3). In particular, for any 4 vectors
v1 v2 v3 v4  we will have  det( pi(vj) ) = 0. This can be used to give a 
quick proof of the linear independence of sets -- just exhibit  4  vectors
vj  for which the determinant is not zero. 

Just what to do in the opposite direction depends on your goal. If you
need a quick test for independence, you could try choosing the  vj
randomly -- if the  pi  really are independent, the set of 4-tuples of
vectors vj making the determinant zero has measure zero in  (R^3)^4.
If instead you want to test independence for a proof of something
(that is, if you need 100% accuracy) you'll need collections of particular 
4-tuples of vectors which will collectively give an "iff" condition.

The corresponding statement for polynomials of 1 variable
goes like this: if  k  polynomials of degree at most  N  are given,
they are dependent iff the vectors wi=(pi(1), ..., pi(N)) are linearly
dependent in  R^N  for  i = 1, 2, ..., k. Indeed, one direction is
trivial, and in the other direction note that if  Sum( ai wi ) = 0, 
then  Sum( ai pi(j) )=0  for every  j,  so that the polynomial
Sum( ai pi ) has roots  1, 2, ..., N. But a polynomial of degree  N
or less can't have  N  distinct roots unless it's identically zero.
The dependence of these vectors in  R^N  is checked by computing all
determinants  det( pi(vj) ) where  {v1,...,vk}  runs over the various
subsets of  {1,...,N}  of cardinality  k.  You can stop as soon as
one of the determinants is nonzero -- then you know the pi  are
independent. Otherwise, keep going until you've checked all subdeterminants;
if all are zero, the vectors are dependent.

The corresponding statement for sets of polynomials of  d
variables of degree at most  N  would be to look at 
all the vectors  v  in  R^d  each of whose coordinates are in 
{1,2,...,N}. Let the number of such vectors be  M  (=N^d in this
setting). Then the polynomials are linearly dependent iff the
k vectors  wi=(pi(v_1),..., pi(v_M))  in  R^M  are linearly dependent.
Since  M  is probably large compared to  k,  you would test this
by checking the k x k determinants of portions of this k x M matrix
looking for a non-zero determinant, stopping either if
	some determinant is not zero (the polynomials are independent)
or	you've exhausted all determinants (the poly's are dependent)
or	you've exhausted your patience (the poly's are probably dependent)

In practice I think you can get away with a smaller  M  than I've
suggested since it appears your sets of polynomials will be
restricted in some way (e.g. be homogeneous). Also I think you can
check linear dependence a bit faster than I've indicated: each time
you get a determinant of zero you've shown some columns are dependent on
others, and so you can toss out other determinants involving these
columns.  I won't get far into discussions of efficiency unless you
tell me this is a critical issue for you (and why).

dave

==============================================================================

To: rusin@math.niu.edu (Dave Rusin)
Subject: Re: Polynomial problem 
Date: Tue, 21 Feb 1995 14:03:43 +0000
From: [Permission pending]


Dear Dave,

Thank you very much for your mail which I found very interesting - I have 
a few questions though. You were replying to the following:

>A typical set of my polynomials may look something like this:
>	p1 = x1x2(x1+x2)
>	p2 = x1(x2+x3)(x1+x2+x3)
>	p3 = (x1+x2)x3(x1+x2+x3)
>	p4 = x2x3(x2+x3)
>Now any three of these are Q-linearly independent - how can I decide
>that I cannot add another of the pi's without destroying this independence?

which you did as follows:

> I had not realized you were posting about polynomials in several variables.
> 
> The statement that the  pi  are linearly dependent can be phrased by
> noting there are nonzero constants  a1 a2 a3 a4  so that   Sum( ai pi(v) ) = 0
> for all vectors  v=(x1,x2,x3). In particular, for any 4 vectors
> v1 v2 v3 v4  we will have  det( pi(vj) ) = 0. This can be used to give a 
> quick proof of the linear independence of sets -- just exhibit  4  vectors
> vj  for which the determinant is not zero. 
> 
> Just what to do in the opposite direction depends on your goal. If you
> need a quick test for independence, you could try choosing the  vj
> randomly -- if the  pi  really are independent, the set of 4-tuples of
> vectors vj making the determinant zero has measure zero in  (R^3)^4.
> If instead you want to test independence for a proof of something
> (that is, if you need 100% accuracy) you'll need collections of particular 
> 4-tuples of vectors which will collectively give an "iff" condition.
> 
> The corresponding statement for polynomials of 1 variable
> goes like this: if  k  polynomials of degree at most  N  are given,
> they are dependent iff the vectors wi=(pi(1), ..., pi(N)) are linearly
> dependent in  R^N  for  i = 1, 2, ..., k. Indeed, one direction is
> trivial, and in the other direction note that if  Sum( ai wi ) = 0, 
> then  Sum( ai pi(j) )=0  for every  j,  so that the polynomial
> Sum( ai pi ) has roots  1, 2, ..., N. But a polynomial of degree  N
> or less can't have  N  distinct roots unless it's identically zero.
> The dependence of these vectors in  R^N  is checked by computing all
> determinants  det( pi(vj) ) where  {v1,...,vk}  runs over the various
> subsets of  {1,...,N}  of cardinality  k.  You can stop as soon as
> one of the determinants is nonzero -- then you know the pi  are
> independent. Otherwise, keep going until you've checked all subdeterminants;
> if all are zero, the vectors are dependent.
> 
> The corresponding statement for sets of polynomials of  d
> variables of degree at most  N  would be to look at 
> all the vectors  v  in  R^d  each of whose coordinates are in 
> {1,2,...,N}. Let the number of such vectors be  M  (=N^d in this
> setting). Then the polynomials are linearly dependent iff the
> k vectors  wi=(pi(v_1),..., pi(v_M))  in  R^M  are linearly dependent.
> Since  M  is probably large compared to  k,  you would test this
> by checking the k x k determinants of portions of this k x M matrix
> looking for a non-zero determinant, stopping either if
	> some determinant is not zero (the polynomials are independent)
> or	you've exhausted all determinants (the poly's are dependent)
> or	you've exhausted your patience (the poly's are probably dependent)
> 
> In practice I think you can get away with a smaller  M  than I've
> suggested since it appears your sets of polynomials will be
> restricted in some way (e.g. be homogeneous). Also I think you can
> check linear dependence a bit faster than I've indicated: each time
> you get a determinant of zero you've shown some columns are dependent on
> others, and so you can toss out other determinants involving these
> columns.  I won't get far into discussions of efficiency unless you
> tell me this is a critical issue for you (and why).
> 

The efficiency problem is precisely why I've been looking for methods other
than the one I've been using to now. The polynomials will *always* be
homogeneous - how does this make M above smaller?  N^d is certainly going
to be very large in comparison to k, although even k itself can sometimes 
become quite large (~100) so checking the k x k determinants you suggest
above may become difficult too. I acknowledge that this is a difficult
problem in general and I appreciate your advice so far. Any further hints
would be welcomed, as would be suitable references for the ideas you have
presented (if they are well-known).

Regards,

[Permission pending]

==============================================================================

To: rusin@math.niu.edu (Dave Rusin)
Subject: Re: Polynomial problem 
Date: Tue, 04 Apr 1995 10:54:21 +0100
From: [Permission pending]


Hi Dave,

Sorry it's been such a long time but I've been organising a conference
and things have been a bit hectic. I have been using your method for
determining bases for polynomial spaces with quite some success. The
value of M=N^d which you said could be reduced (since for example my polys
are homogeneous) seems to be true. I have guessed at smaller values and
looked at whether a true basis is produced. It would be nice to have some
closed form bound for the "most" M need be.

I am currently preparing a paper on my work and would like to include this
approach -- do you have any references I could use?? Or is this your own
work?? I would also like to acknowledge your assistance and hence can you
provide your full name and affiliation (if you've no objections of course!).

Hope to hear from you soon,

[Permission pending]

==============================================================================

Date: Wed, 5 Apr 95 11:59:27 CDT
From: rusin (Dave Rusin)
To: [Permission pending]
Subject: Re: Polynomial problem

When I returned to my computer it said to type ntalk but that seems to
have no effect right now. Sorry if I missed you.

>The
>value of M=N^d which you said could be reduced (since for example my polys
>are homogeneous) seems to be true. I have guessed at smaller values and
>looked at whether a true basis is produced. It would be nice to have some
>closed form bound for the "most" M need be.

OK, try this. If I recall right you're looking at homogeneous
polynomials in  d variables of degree N. I can probably do it homogeneously
and preserve some symmetry but let's go ahead and set  x1=1  to get
elements of what I'll call  P(d-1,N), the polynomials of d-1 variables of 
degree at most  N. 

I will show that linear independence of elements of  P(m,N) can be tested
unambiguously by checking the values of the polynomials at the 
points  (i_1, ..., i_m)  where each  i_j  is taken from {0,...,m}
and  Sum(i_j) <= N. This is the smallest such collection of points.
There are  {(N+1) choose m}  of them.

Of course one basis for  P(m,N) is the set of monomials x^I = Prod((x_j)^(i_j))
But another basis is the set of polynomials  x_I = Prod( binom((x_j),(i_j )) ).
By comparing the highest-order terms,
it is clear that these are linearly independent and by proceeding recursively
on degree (starting with the highest-degree terms), one can write any 
polynomial as a linear combination of these, showing that they are a spanning
set (or, of course, one could just count the number of elements in each basis).

But this basis is just transitional. What you really want is the basis of
polynomials  y_I  which have the property  y_I(J) = 0 unless the multi-indices
I  and  J  are equal. The relationship with the  x_I  is straightforward
but this time "_upper_-triangular": already  x_I(J) = 0 unless  I <= J, and so
you can work your way down to the multiset  0  and write  y_I  as a linear
combination of the x_J  with  J <= I.

Now it's clear what the dual space of the vector space  P(m,N) is: we have
the functionals  P --> P(I)  where  I  ranges over these multisets; the
collection of these evaluations is then a basis dual to the  y_I. In
particular, an element  P  in P(m,N)  is zero iff  P(I) = 0 for all I.
This gives you a test for linear independence.

Here's the situation for  (m,N) = (2,3). The natural basis of monomials of
degree at most  3  in  2  variables is
	{1, x, y, x^2, xy, y^2, x^3, x^2y, xy^2, y^3}
corresponding to  ten  multi-indices  I  =
	{(0,0), (1,0), (0,1), (2,0), (1,1), (0,2), (3,0), (2,1), (1,2), (0,3)}
respectively.

The next basis  x_I  is simply
	{1, x, y, x(x-1)/2, xy, y(y-1)/2, x(x-1)(x-2)/6, x(x-1)y/2, 
		xy(y-1)/2, y(y-1)(y-2)/6}
whose elements are easy linear combinations of the previous basis:
	x_I=x^I first for I=(0,0), then for (1,0) and (0,1).
	x_(2,0) = (1/2)x^(2,0) + (1/2)x^(1,0), and more generally  x_I  is
(1/I!)x^I + linear combinations of  x^J  with  J  of smaller total degree 
than  I.

Then we compute the  y_I  as follows: 
	y_I = x_I for  I = (3,0), (2,1), (1,2), and (0,3);
Then, evaluating at all possible  I  we see
	x_(2,0) = y_(2,0) + y_(2,1) + 3 y_(3,0)
so that  y_(2,0) = x(2,0) - x_(2,1) - 3 x_(3,0), and in general y_I  is
x_I + linear combinations of  x_J  where  J  has larger total degree than I.

(You could combine the two change-of-basis matrices into one by multiplying
the lower-triangular and upper-triangular matrices which result, but I
don't see any virtue in doing so.)

To get the dimension of the vector space, you need to be able to count the
number  p(m,N)  of monomials of degree at most  N  in  m  variables.
The monomials of degree less than  N  total  p(m,N-1); those of degree
exactly  N  are homogeneous and so by reusing a previous trick, they are
in one-to-one correspondence with the  p(m-1,N) monomials of degree N or less
in  m-1  variables. Thus  p(m,N) = p(m-1,N)+p(m,N-1), which is the recurrence
for the binomial coefficients. Indeed, checking for starting values we
find  p(m,N) = binomial(N+1, m).  If  m  is small compared to  N  this is
about  (N+1)^m / m!, and is actually a bit less.

OK, so my estimate  N^d/d!  is a little off -- (N+1)^(d-1) / (d-1)!  is better.

>I am currently preparing a paper on my work and would like to include this
>approach -- do you have any references I could use?? Or is this your own
>work?? I would also like to acknowledge your assistance and hence can you
>provide your full name and affiliation (if you've no objections of course!).

I'm sure this is well known, but the size of the mathematical literature is
now such that it's more work to find a reference than to recreate the
observations from scratch.

Thanks for the mention. I'm
	Dave Rusin (Department of Mathematical Sciences)
	Northern Illinois University
I'd like to see the paper when you've got something written up. It gives
me my jollies to see how people use what help I offer.

dave

==============================================================================

To: rusin@math.niu.edu (Dave Rusin)
Subject: Re: Polynomial problem 
Date: Mon, 10 Apr 1995 09:19:15 +0100
From: [Permission pending]


Hi Dave,

Many thanks for your long and considered reply. Apologies for my lethargic
response but as I mentioned I am organising a conference and people start
arriving today. In view of that, I probably won't do much of my own work
before Easter when I will look in detail at what you said, it looks very
interesting. With regard to my paper, I have almost completed my first
draft and I must finish by May 15th so you won't have to wait too long -
your work will be the original stuff you sent as I haven't time to re-do
with the new work of last week. I'll be in touch again when I've had chance
to read your new work.

Thanks again,

[Permission pending]

==============================================================================

Date: Fri, 28 Apr 95 01:00:31 CDT
From: rusin (Dave Rusin)
To: rusin
Subject: old file found

>Thank you very much for your mail
They pay me "to do mathematics". That's all I'm doing.

>The efficiency problem is precisely why I've been looking for methods other
>than the one I've been using to now. The polynomials will *always* be
>homogeneous - how does this make M above smaller?

If you have only homogeneous equations of the same degree, you can 
substitute  x1=1  into all of them and get the same number of equations,
of the same degree, but using one fewer variable. The new set is linearly
independent iff the original set was.

>N^d is certainly going
>to be very large in comparison to k, although even k itself can sometimes 
>become quite large (~100) so checking the k x k determinants you suggest
>above may become difficult too. I acknowledge that this is a difficult
>problem in general and I appreciate your advice so far. Any further hints
>would be welcomed, as would be suitable references for the ideas you have
>presented (if they are well-known).

Well, my estimate of the number  M  of vectors you need in the test is
too large, though not by much, perhaps. The dimension of the space of
homogeneous polynomials of degree  N  in  d  variables is more like
M = N^(d-1)/(d-1)! (I don't recall the exact computation) but if indeed
N^d is much larger than k ~ 100, I think this is still going to be
devastatingly large, unless perhaps  N  is quite small and  d  is the
large part. (For  N=2, the correct  M  is  (d^2+3d-2)/2, for example).

Am I correct in understanding, then, that it is important to know that
polynomials really are linearly dependent, rather than being
probably dependent? If we know there exist constants such that
Sum (ai pi) vanishes at a really large number of points, that makes it
rather likely that  Sum(ai pi) really is zero

==============================================================================

To: rusin@math.niu.edu (Dave Rusin)
Subject: Re: Polynomial problem 
Date: Mon, 08 May 1995 10:32:13 +0100
From: [Permission pending]


Hi Dave,

I'm so sorry that I've taken so long to get back to you. Things got a bit
hectic last week when I got asked to attend a job interview at short notice.
Anyway, onto work. As a reminder, I'm looking at homogeneous polynomials of
degree N in d variables and want tests for linear independence. Your last 
message appears at the end of this for reference. It could well be that the
problems I am experiencing in following what you said are more to do with
notation than anything else -- I set out my difficulties below.

You said: "I will show that linear independence of elements of  P(m,N) 
           can be tested unambiguously by checking the values of the 
           polynomials at the points  (i_1, ..., i_m)  where each i_j 
           is taken from {0,...,m} and  Sum(i_j) <= N. This is the 
           smallest such collection of points. There are  {(N+1) choose m}  
           of them."

I assume that P(m,N) means homogeneous polynomials in m variables of degree N.
What does "checking the values of the polynomials at the points..." mean in
this setting? Later you refer to multi-indices I, are these the
I=(i_1, ..., i_m) above? In your example for (m,N)=(2,3), you get ten such
I however, whereas (N+1) choose m = 4 choose 2 = 6......

Also, should the above read "points  (i_1, ..., i_m)  where each i_j is taken
from {0, ..., N}" rather than "from {0,...,m}"? Even then, I don't see where
your (N+1) choose m comes from. Perhaps I should make clear, I use

	(N+1) choose m =  (N+1)!
                         ----------
                         m!(N+1-m)!

You then discuss two bases, one a monomial basis, the other a polynomial basis.
Later you say: "...an element P in P(m,N) is zero iff P(I)=0 for all I. This
gives a test for linear independence." Firstly, I need to be sure of what the
I's really are (see my previous remarks), referred to as multi-indices/
multisets. Then, how is this a test for linear independence?

Finally, you remark that the better estimate of how large my collection
of "checking points" need be is (N+1)^(d-1)/(d-1)!, I assume obtained by
putting m=d-1 with your previous result.

Sorry to be so particular but I need to be clear in my mind what exactly is
going on before I try to write up this improvement.

My paper is now completed and will soon be mounted on a dedicated WWW server
in postscript format. If you don't have Web access, let me know and I'll
mail you the postscript file (or whatever format you prefer).

With thanks for your continued help,

[Permission pending]

------------------------------------------------------------------------------

In reply to the following:

OK, try this. If I recall right you're looking at homogeneous
polynomials in  d variables of degree N. I can probably do it homogeneously
and preserve some symmetry but let's go ahead and set  x1=1  to get
elements of what I'll call  P(d-1,N), the polynomials of d-1 variables of 
degree at most  N. 

I will show that linear independence of elements of  P(m,N) can be tested
unambiguously by checking the values of the polynomials at the 
points  (i_1, ..., i_m)  where each  i_j  is taken from {0,...,m}
and  Sum(i_j) <= N. This is the smallest such collection of points.
There are  {(N+1) choose m}  of them.

Of course one basis for  P(m,N) is the set of monomials x^I = Prod((x_j)^(i_j))
But another basis is the set of polynomials  x_I = Prod( binom((x_j),(i_j )) ).
By comparing the highest-order terms,
it is clear that these are linearly independent and by proceeding recursively
on degree (starting with the highest-degree terms), one can write any 
polynomial as a linear combination of these, showing that they are a spanning
set (or, of course, one could just count the number of elements in each basis).

But this basis is just transitional. What you really want is the basis of
polynomials  y_I  which have the property  y_I(J) = 0 unless the multi-indices
I  and  J  are equal. The relationship with the  x_I  is straightforward
but this time "_upper_-triangular": already  x_I(J) = 0 unless  I <= J, and so
you can work your way down to the multiset  0  and write  y_I  as a linear
combination of the x_J  with  J <= I.

Now it's clear what the dual space of the vector space  P(m,N) is: we have
the functionals  P --> P(I)  where  I  ranges over these multisets; the
collection of these evaluations is then a basis dual to the  y_I. In
particular, an element  P  in P(m,N)  is zero iff  P(I) = 0 for all I.
This gives you a test for linear independence.

Here's the situation for  (m,N) = (2,3). The natural basis of monomials of
degree at most  3  in  2  variables is
	{1, x, y, x^2, xy, y^2, x^3, x^2y, xy^2, y^3}
corresponding to  ten  multi-indices  I  =
	{(0,0), (1,0), (0,1), (2,0), (1,1), (0,2), (3,0), (2,1), (1,2), (0,3)}
respectively.

The next basis  x_I  is simply
	{1, x, y, x(x-1)/2, xy, y(y-1)/2, x(x-1)(x-2)/6, x(x-1)y/2, 
		xy(y-1)/2, y(y-1)(y-2)/6}
whose elements are easy linear combinations of the previous basis:
	x_I=x^I first for I=(0,0), then for (1,0) and (0,1).
	x_(2,0) = (1/2)x^(2,0) + (1/2)x^(1,0), and more generally  x_I  is
(1/I!)x^I + linear combinations of  x^J  with  J  of smaller total degree 
than  I.

Then we compute the  y_I  as follows: 
	y_I = x_I for  I = (3,0), (2,1), (1,2), and (0,3);
Then, evaluating at all possible  I  we see
	x_(2,0) = y_(2,0) + y_(2,1) + 3 y_(3,0)
so that  y_(2,0) = x(2,0) - x_(2,1) - 3 x_(3,0), and in general y_I  is
x_I + linear combinations of  x_J  where  J  has larger total degree than I.

(You could combine the two change-of-basis matrices into one by multiplying
the lower-triangular and upper-triangular matrices which result, but I
don't see any virtue in doing so.)

To get the dimension of the vector space, you need to be able to count the
number  p(m,N)  of monomials of degree at most  N  in  m  variables.
The monomials of degree less than  N  total  p(m,N-1); those of degree
exactly  N  are homogeneous and so by reusing a previous trick, they are
in one-to-one correspondence with the  p(m-1,N) monomials of degree N or less
in  m-1  variables. Thus  p(m,N) = p(m-1,N)+p(m,N-1), which is the recurrence
for the binomial coefficients. Indeed, checking for starting values we
find  p(m,N) = binomial(N+1, m).  If  m  is small compared to  N  this is
about  (N+1)^m / m!, and is actually a bit less.

OK, so my estimate  N^d/d!  is a little off -- (N+1)^(d-1) / (d-1)!  is better.

>I am currently preparing a paper on my work and would like to include this
>approach -- do you have any references I could use?? Or is this your own
>work?? I would also like to acknowledge your assistance and hence can you
>provide your full name and affiliation (if you've no objections of course!).

I'm sure this is well known, but the size of the mathematical literature is
now such that it's more work to find a reference than to recreate the
observations from scratch.

Thanks for the mention. I'm
	Dave Rusin (Department of Mathematical Sciences)
	Northern Illinois University
I'd like to see the paper when you've got something written up. It gives
me my jollies to see how people use what help I offer.

dave

==============================================================================

To: rusin@math.niu.edu (Dave Rusin)
Subject: Re: Polynomial problem 
Date: Tue, 23 May 1995 11:19:46 +0100
From: [Permission pending]


Hi Dave,

Did my last message get through? The address I'm using is

	rusin@math.niu.edu

Should I be using something more direct to your machine?

Regards,

[Permission pending]

==============================================================================

Date: Wed, 24 May 95 13:19:55 CDT
From: rusin (Dave Rusin)
To: [Permission pending]
Subject: Re: Polynomial problem

Well, I never did find my response to your previous letter so I'll try
to recreate it. It began with an apology for being so careless in some
details; had you not appended my previous letter I wouldn't believe I
had done it.

First off: I did indeed misquote the dimension of the vector space: the
set  P(m,N) of (not necessarily homogeneous) polynomials of degree N or less
in  m  variables  has dimension  {(N+m) choose  m}. This agrees with the
examples I worked out: m=2, N=3.

Furthermore, I did indeed mistype here as you suggested:
>Also, should the above read "points  (i_1, ..., i_m)  where each i_j is taken
>from {0, ..., N}" rather than "from {0,...,m}"? 

Now let me clarify the main intent of the method. The main theorem is as
I wrote to you before [correcting as in the previous paragraphs]:
          "I will show that linear independence of elements of  P(m,N) 
           can be tested unambiguously by checking the values of the 
           polynomials at the points  (i_1, ..., i_m)  where each i_j 
           is taken from {0,...,N} and  Sum(i_j) <= N. This is the 
           smallest such collection of points. There are  {(N+m) choose m}  
           of them."

This caused you to respond
>What does "checking the values of the polynomials at the points..." mean in
>this setting?
...and then...
>Later you say: "...an element P in P(m,N) is zero iff P(I)=0 for all I.
>This gives a test for linear independence." ... how is this a
>test for linear independence?

Let me illustrate using an example you once sent me:

>        p1 = x1x2(x1+x2) 
>        p2 = x1(x2+x3)(x1+x2+x3) 
>        p3 = (x1+x2)x3(x1+x2+x3) 
>        p4 = x2x3(x2+x3) 
>Now any three of these are Q-linearly independent - how can I decide
>I cannot add another of the pi's without destroying this independence? 

The first trick I suggested (and I still think this is not the most
elegant approach) is to set one variable to  1, to get a set of
2-variable cubics (fortunately also fitting the case  m=2, N=3  discussed
in other examples):
	p1 = x1x2(x1+X2)
	p2 = x1(x2+1)(x1+x2+1)
	p3 = (x1+x2)(x1+x2+1)
	p4 = x2(x2+1)

The main theorem says we can determine dependence by evaluating these
polynomials at all points with  x1  and  x2 being non-negative integers
summing to  N=3. Here's the table:

    (0,0) (1,0) (0,1) (2,0) (1,1) (0,2) (3,0) (2,1) (1,2) (0,3)
p1    0     0     0     0     2     0     0     6     6     0
p2    0     2     0     6     6     0     12    16    12    0
p3    0     2     2     6     6     6     12    12    12    12
p4    0     0     2     0     2     6     0     2     6     12

Here's how we use this to test for linear independence. A glance at, say,
columns 3, 4, and 5 shows that  p1 p2 and p3  are linearly indpendent
because there are no constants  a1 a2 a3  making  a1 p1 + a2 p2 + a3 p3
equal zero at each of these points Z1=(0,1), Z2=(2,0), and Z3=(1,1). On the 
other hand, p1 - p2 + p3 - p4  vanishes at each of the ten points above; the 
theorem says that this means  p1-p2+p3-p4  is in fact identically zero.

As a practical matter, I guess I would try a number of these points until
I found a Z1  where  p1  does not vanish. Then I would try again searching
for another point  Z2  making the values of p1 and p2 linearly independent;
then add p3, p4, and so on. If at some stage you have that, say,
p1, p2, and p3 take on independent values at points  Z1, Z2, Z3, then there
will be a unique set of constants  a1 a2 a3  (easily found) such that  
p = p4 - (a1 p1 + a2 p2 + a3 p3)  vanishes at  Z1, Z2, and  Z3. I guess what
I would do is to pick a few choices for  Z4  at random and see if  p
vanishes there, too. If not, then  p1 p2 p3 p4  are linearly independent.
If  p  does vanish at a lot of these points, I would probably quit at some
point and declare the four  p_i  to be "probably linearly dependent"; I
wouldn't know for sure until I had checked all  {(N+m) choose  m} possible
points  Z4.

Whether this approach is better than expanding out the polynomials in
the first place is not clear. If you really do have independent polynomials,
you should be able to discover this with just a few function evaluations
(as above), although you would also be likely to discover it just be finding
the coefficients of just a few of the monomials in the expansion. In this
case I guess you have to ask whether your particular  p_i  allow an
especially easy expansion or an especially easy evaluation at points.
If on the other hand you really do have _dependent_ polynomials, you can't
tell that for certain unless you expand the polynomials completely, or
unless you evaluate them at all the points  Z_i. Either way, you need to
show that a matrix (of the same size with both methods) has less than
maximal rank. Again, there may be some savings in time depending on 
whether expansion or evaluation is quicker, but the total time needed
for a definitive (rather than probabilisitic) answer is in either case
going to depend mightily on the size of that matrix.

If the polynomials you gave in the same are indeed typical, I would imagine
the evaluations are faster than expansions, so you might find this method of
use.

That said, I should add that if the polynomials you gave are typical, there
may be _much more_ rapid ways to assess independence. I do not have an
idea about what to do, but I do note that your polynomials are not
"arbitrary" polynomials in a certain number of variables, of a certain
degree. Instead they are _products of linear polynomials_, every one of
which is a _zero-one_ sum of the variables. Given that your polynomials are
of a very restricted type like this, there may well be other, faster
ways to check independence, since as far as I know the general case cannot
be reduced to this. If indeed this is the situation perhaps you should
let me know. That would likely change the problem from a linear-algebra
one to a combinatorics one.

>My paper is now completed and will soon be mounted on a dedicated WWW server
>in postscript format. If you don't have Web access
I do. A URL would be fine.

dave

==============================================================================

To: rusin@math.niu.edu (Dave Rusin)
Subject: Re: Polynomial problem 
Date: Thu, 25 May 1995 14:52:48 +0100
From: [Permission pending]


Hi Dave,

Many thanks for your very interesting e-mail message. I will take a while
to think on the things you said before replying to it, plus I will soon
be away at a conference in France for two weeks. I do however include
the URL for the site of my paper - go to

	http://cartan.u-strasbg.fr/~slc

and click on 'Works in Progress' to find my paper in postscript format.
I hope you find it of interest and it may even answer some of your questions
about the polynomials arising in my problem.

Thanks again,

[Permission pending]

==============================================================================

Date: Sat, 27 May 95 01:03:38 CDT
From: rusin (Dave Rusin)
To: [Permission pending]
Subject: Re: Polynomial problem

Thanks for the pointer; I've found and read the paper. I'm rusty on
root systems so I'll not comment on that part directly. I do observe
a similarity to another construction you might enjoy. L E Dickson (~1910?)
determined the invariants of the general linear group over a finite
field as follows: to find the polynomials in  n  variables x1,...,xn with
coefficients in the finite field  F  one looks at the product  P(X)  in
F[x1,...,xn][X] (the ring of polynomials in  n+1  variables) defined
as    Prod( X-v )  where the product runs over all vectors v  in the
vector space of linear polynomials over  F. If  |F|=q, this is a
vector space with  q^n  elements, so  P(X)  is a polynomial of degree
q^n  in  X  with coefficients in  F. It is immediately clear that
P(X)  is invariant under any linear change of variables (which will
just permute the  v 's) so in fact the coefficients of  P(X)  are all
invariant polynomials in the  xi. What's a lot less trivial is that
these polynomials are all zero except for the coefficients of  X^(q^j)
(j=0,1,...,n) and that these polynomials generate the ring of all
invariant polynomials as a polynomial ring in  n  generators (they are
called the Dickson invariants). For example when  q=2 and n=2 we have
P(X) =(X-0)(X-x1)(X-x2)(X-x1-x2)=X^4 + (x1^2+x1x2 + x2^2) X^2 + 
x1x2(x1+x2) X  = X^4 + u1 X^2 + u2 X, say,  and indeed the ring of invariants
F[x1,x2] ^ GL(2,2)  is precisely the polynomial ring  F[u1, u2].
Moreover, the original polynomial ring is a module over both this
subring and over the linear group; I think its free over both.

A lot of people have jumped in on this and generalized the idea. The
basic pattern always seems to be breaking the vectors  v  into orbits
so as to factor  P(X)  into factors each of which is invariant under
a group action. The optimal pattern seems to be when the the group
is generated by reflections. I guess  Stanley  is the person who keeps
the books on invariant rings, but you'll find a lot of work on
Dickson- and other invariants by algebraic topologists, who have used
an awful lot of this. You'll find readable summaries by  Wilkerson,
an outline of the general construction of invariants this way by
(Larry) Smith   and applications to, um, I think it was the upper-triangular
subgroups of  GL(n,q)  by  Huynh Mui.

(Stanley had a survey article in the bulletin of the AMS about 5 yrs ago
which might provide additional references).

These people are mostly looking at the invariants under the action
rather than attempting to decompose the whole action into summands, but
it looks like their techniques are similar to the ones you generalized
from Macdonald. Perhaps this will help clarify the construction of the
modules Macdonald missed.

Let me now turn to the part of your paper with which I am most familiar:
sect. 4.3 (p.13) et seq. To begin with, I think you can tighten definition
4.12, possibly by adjoining the condition  "Sum(v_i)=N"  (I haven't
checked the details yet); certainly a description is possible with
M=|V_0| reduced to  ((N+d-1) choose (d-1)), since that is the dimension
of the set of all homogeneous polynomials in  d  variables of degree  N.

In the context of your work I have to concede that "probably linearly dependent"
is an inappropriate notion. (Somewhere I had gotten the idea that you were
making an application to optimization in some applied field, so that something
which is "probably" optimal was likely to be good enough).

Your example 4.15 is probably quite telling as a comparison of the methods
at hand. For example, you note in the monomial method that there are  42
monomials. Of course this is an a posteriori calculation. A priori you
would have expected  9 choose 3 = 84 monomials, and cleared scratch space
to accomodate a  5 x 84  matrix  (your suggestion to invoke MAPLE is perhaps
ill-advised, as it, like its competitors, tends to expand literally -- that is,
as symbol strings -- rather than numerically, for example by ticking off
coefficients in the 5 x 84 matrix. Your success so far is certainly due to the
compact presentation of the polynomials in question; for 5 "random"
polyonomials in 4 variables, homogeneous of degree  6, you would expect
many strings of monomials, which would require a lot of pattern matching by
MAPLE.)
	The leading monomial method you propose is really just a bookkeeping
device to  compress data: your ordering of the monomials is just an
ordering of the columns of the matrix; you are scanning for the first and
last nonzero terms in each row and relying on luck to provide an
upper-triangular portion, which then exhibits independence. As I indicated in
a previous letter, this is an excellent approach as long as you do indeed
have independence; it's the proof of dependence which is tricky. Indeed,
you begin p.15 with the observation that p2=p1+p3-p4+p5, but this would
be very difficult to judge just from a look at the leading monomials
(even keeping a few of the highest terms in each polynomial); it would
certainly be absolutely necessary to use somehow the special nature of
your polynomials if you wanted to prove this relation without multiplying
out all 5 polynomials.
	This, really, is the same situation as you face in the rational
vector method. Again we will test for independence by examining a
5 x 84 matrix. Again there is a natural ordering for the  84  columns;
you;ve selected the 5 smallest ones for  V_0; again the matrix for
p1 p2 p3 p4 is nonsingular which shows these to be independent; moreover,
looking at the 5th row as well here suggests the relation
p2=p1+p3-p4+p5. Unfortunately, you again would have to carry out some
calculation  84  times to be able to state definitely that this
relation holds on the nose, unless somehow you can use the special nature
of the  p_i.
	(There are nowhere near 1296 tests to run here; you're relying
on earlier estimates I had sent.)

I have been deliberately vague on what I mean by "special nature". I
think I have convinced myself that you can find a basis for the set of
all polynomials of a given degree in a given number of variables
such that the basis consists only of products of linear terms. If so,
then I would say the methods so far proposed cannot be made more
efficient at proving linear _dependence_  -- you still need a
computation time proportional to that binomial coefficient -- unless
you can observe something else about the set of  p_i  with which
you deal. The two factors on your side seem to be that the
_coefficients_ in the linear factors of the  p_i  are very special
(I guess they're  0  or  1  in the  A_n  cases, for example) and that
the  p_i  are closely linked (translates of each other under  W).
The first factor has helped when using the leading monomial technique,
since it assures that polynomials which look similar really are
the same. The second  factor has helped when using the total
monomial technique, since it reduced the number of distinct
monomials which would arise. Both observations can be brought to
bear on the rational vector method as well. Indeed, one can
argue that the method of all monomials amounts to evaluating the
p_i at roots of the linear factors, and the leading monomial method
amounts to evaluating them at points with the  x_i  of wildly
different magnitude, so it should generalize those other methods.

I intend to give this matter a little more thought now that I know
what you're doing with it. As I see it, one is given a collection
of  k  products of  d  linear forms in  N  variables. By any of
the three methods it can be quickly decided that the  k  are
"probably" dependent, and indeed by the rational vector test it's
easy to guess the dependence. What you still need is a way to 
use the special form of these polynomials to find a quick way
to demonstrate the putative relation really does hold.

I'l see what I can come up with.

dave

PS - YOu mis-expanded the abbreviation "Math Z." in your bibliography.

==============================================================================

To: rusin@math.niu.edu
Subject: Re: Polynomial problem 
Date: Fri, 23 Jun 1995 14:28:55 +0100
From: [Permission pending]

Dear Dave,

Firstly I must apologise for the long delay in getting back to you. As I
mentioned, I had a conference in France for two weeks at the end of May/
start of June. However, during my stay there, I contracted chicken pox and came
home early. The last couple of weeks have been spent in relative isolation
so as not to pass it on. At least the time off has given me chance to consider
your replies in some detail, which I now go on to discuss.

Your message before you had read my paper cleared up the problems I had been
experiencing with your previous claims, so thanks for that. It is your last
message after having read my paper, though, on which I will concentrate as
I feel it has raised some poignant questions while at the same time clearing up
some less than perfect understanding I had of what I was really doing with my
methods.

The pointers you gave to Dickson, Stanley, etc. will be followed up. 
Interestingly, Macdonald has also done some work on invariants which I studied,
but it didn't really get me anywhere with my work. We at Aberystwyth consider
ourselves as algebraic combinatorialists above all and my supervisor has been
known to claim that all of combinatorics stems from Stanley! By the way, the
man that calls Ian Macdonald a combinatorialist does so at his peril!

I will go through the three methods as they appear in my paper. Firstly, the
all-monomial method. This approach has proved to be remarkably useful, in view
of the facts both that it is very inefficient and that Maple has been used
throughout. Your comments on the way Maple handles things via 'literal 
expansion' are particularly valid but I've found no better system for doing the
calculations I have as a whole. My code takes a given subsystem, implements
GENSET to find a generating set then implements one of the basis methods
to determine explicitly the corresponding matrix representation. Provided
|W| and |S| are 'fairly small' the all-monomial method will do the job
surprisingly quickly. As |S| increases so the number of monomials increases and
soon the corresponding systems of equations become too hot for Maple to handle.
Your comment concerning my a posteriori claim about the number of monomials
arising in Example 4.15 is of course true -- it would be nice to be able to
give this number just from the initial, unexpanded polynomials; this perhaps
would rely upon their "special nature" !

Your comments on the next approach, the leading monomial method, were very 
useful to my understanding. I had not linked the monomial order with the
column order of a matrix (essentially, the coefficient matrix of the
decomposition of the polynomials of P into monomials). The problem, of course,
is that of establishing dependence and the corresponding linear relations,
and I agree that, once again, we need the "special nature" of the polynomials
in question.

That leaves perhaps the most important work till last, viz. the rational
vector method. It seems that we've had so many slight alterations and
improvements since your initial idea that I'm a bit confused now! You
commented in your mail that I had quoted far too high a figure for the number
of test points required for an example (Example 4.15 in fact) -- the only
reason this happened was that I had to submit my paper before I'd had chance
to absorb your newer ideas. This situation will be remedied in my thesis
where everything will be covered -- I have a complete Chapter on these basis 
methods, which I would like you to see. When I have completed to the point
of my understanding, I'll forward a postscript copy if that's OK. The sections
concerning the all-monomial and leading monomial methods should be fairly 
complete (but for any improvements which come from the polynomials'
"special nature") but the rational vector method section will not be meant
as final and I'm sure you will find something to comment on there. I should
point out that the Chapter includes some representation theory of the
symmetric group since what I really want to do is mimic the basis of standard
tableaux if possible (for details of this theory, see e.g. "Representation 
theory of the symmetric group" by G. de B. Robinson or "The symmetric group : 
representations, combinatorial algorithms, and symmetric functions" by Bruce 
E. Sagan). This work should be ready in the next few weeks once I've written
up the rational vector method to take into account your latest ideas. I should
also point out that at some point I'll need proofs for the rational vector
method and so we'll need to agree on something in that respect.

I'll leave it at that for now. I must thank you for your continued help and
ideas, your work has certainly been invaluable to my progress. I'll be in
touch again when I've something decent written up.

Regards,

[Permission pending]

==============================================================================

To: rusin@math.niu.edu (Dave Rusin)
Subject: Re: Polynomial problem 
Date: Mon, 03 Jul 1995 12:18:51 +0100
From: [Permission pending]

Hi again Dave,

As promised, my Chapter on basis methods follows at the end of this
intro (in postscript). References to Chapter 3 refer to my algorithm
GENSET as seen in my paper -- you can ignore that stuff if you want 
and just think of the polynomial problem as before.Section 4.2 is just
some general material on polynomials and orderings needed in what follows.
4.3 covers the all-monomial method, 4.4 the leading monomial method and
4.5 the rational vector method, I conclude with a comparison of the methods.
Any comments/suggestions for improvements would be very gratefully received.
Hope you find it of interest.

Regards,

[Permission pending]

------------------------------------------------------------------------------

%!PS-Adobe-2.0
%%Creator: dvips 5.47 Copyright 1986-91 Radical Eye Software
%%Title: root.dvi
%%Pages: 19 1
%%BoundingBox: 0 0 596 843
%%EndComments
[deleted - djr]
%%Trailer
end
userdict /end-hook known{end-hook}if
%%EOF

==============================================================================

To: rusin@math.niu.edu (Dave Rusin)
Subject: Basis methods for polynomial spaces
Date: Mon, 11 Sep 1995 16:48:13 +0100
From: [Permission pending]

Hi Dave,

I saw your posting on sci.math.research about conjugacy classes in group
theory and so thought I'd drop you a line about the material I sent you
a while ago. I think I sent my whole chapter on basis methods for polynomial
spaces. I'm almost ready to submit my thesis for a first reading and so
any comments/errors/etc on that work in particular would be welcome. I can
forward another copy if you need it.

Regards,

[Permission pending]

==============================================================================

Date: Mon, 11 Sep 95 12:45:27 CDT
From: rusin (Dave Rusin)
To: [Permission pending]
Subject: Re:  Basis methods for polynomial spaces

Hi, sorry if I've let the correspondence lapse. I was looking at your
chapter a few weeks ago; it looks fine. I was trying to decide if there
was any a priori advantage to any of the methods proposed. As far as I can tell,
the issue depends on the expected number of vectors and the expected
number of them which will be independent. The method I proposed makes it
easy to demonstrate independence; to prove dependence is also in a 
probabilistic sense easy until the number of independent vectors is nearly
the dimension of possible vectors. It seems to me that in your context the
number of independent vectors tends to be small, but I didn't see why that
had to be.
For the record, I think there is value to altering the method I proposed a bit.
Rather than investigating the values of the functions at those finitely many
integer points, you can go ahead and evaluate them at random points (real or
rational or integer-- doesn't matter). Indeed, if you have  N  vectors which
you have already proven to be independent, and you evaluate  N+1  vectors
at  N+1  points, then two outcomes can occur: either you get linearly
independent function values, which proves the   N+1  functions are still
independent, or else you get linearly dependent function values. In the last
case, there will be a unique linear relation among them, which you can 
compute. This relation is now a polynomial of a certain degree vanishing at
N+1  points. What you don't know for sure is whether it's identically
zero or not. Well, the zero set of a non-zero polynomial is always a
subvariety, and in particular a set of measure zero. If you plug in any
randomly selected point, the polynomial will have a nonzero value with
probability  1 .  (Of course, this doesn't mean you're _guaranteed_ to have
a nonzero value. An annoying feature of probability!) So, forget integrality;
forget positivity; forget the bounds on the variables. Go ahead and plug
in any old point into the linear combination of the polynomials. It would
be essentially miraculous if you got a function value of  zero  unless the
linear relation held identically.

(Of course, miracles do happen...)

Anyway, your proposed chapter seems fine to me. I don't think it makes 
much sense to try to make a choice of method unless you intend to write
code to actually carry out these calculations for a general family of
situations. If you get to that point, we can look at the code to decide
what the distribution of likely inputs will be and the optimize code based
on that distribution.

Good luck

dave

==============================================================================

To: rusin@math.niu.edu
Subject: Basis methods chapter
Date: Fri, 15 Sep 1995 14:37:41 +0100
From: [Permission pending]

Hi Dave,

Thanks for your mail and the consideration you've given to my chapter about
basis methods for polynomial spaces. You suggest using random points as
our evaluation points rather than the fixed set which we have described. In
fact, this is precisely what I first tried before we made contact and it is
why I had faith in this kind of approach. However, I will stick to the method
as proposed with a fixed set of evaluation points, more to please my supervisor
than anything else as he likes things to be quite precise.  

I have already written code for each of the methods using Maple, as I said
somewhere in that chapter. The all-monomial method runs out of steam when the
number of factors in the polynomials in question increases (indeed, sometimes
Maple will not even expand the polynomials so I can't get hold of the monomials
in the first place). The leading monomial method is easy to code and fairly
efficient even in Maple! The rational vector method is OK provided I really
restrict the set of evaluation points even beyond the improved bound of
(N+d-1) choose (d-1) (which is of course generally large). It's a bit late in
the day to start major improvements/changes to my code, all the results I
want I now have anyway.

You commented that the number of independent polynomials I usually get from
my large generating set is small - this is always the case in actual fact. The
reason for this is quite simple. The number of ind. polys is the dimension of
the corresponding module, this is exactly the degree of the corresponding
irreducible representation. Now, the character tables of all the Weyl groups
are well known and so are these degrees - and they are small compared to the
group order. For example, in E_6 type (which has order 51840) the maximal
character degree is only 90, small compared to the order of the group and indeed
the generating sets. Hence, I am always looking for a small linearly
independent subset of a large generating set.

Thanks again for all your help. You will be formally acknowledged in my thesis,
which hopefully will be submitted and examined by Christmas.

Regards,

[Permission pending]