Author 
Topic: Polynomial Puzzle (Read 867 times) 

ThudnBlunder
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489


Polynomial Puzzle
« on: Jan 27^{th}, 2007, 6:46am » 
Quote Modify

How many nthorder polynomials are there with m variables such that i) all of their coefficients are either 0 or 1 ii) P(x_{1},x_{2}, x_{3},.......x_{m}) = 1 whenever x_{1} + x_{2} + x_{3} + ....... + x_{m} = 1?


IP Logged 
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.



Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Re: Polynomial Puzzle
« Reply #1 on: Mar 9^{th}, 2007, 11:31pm » 
Quote Modify

There are 2^{C(n+m,n)} polynomials in m variables with degree n satisfying (i) (equivalently, a homogenous polynomial of degree n in m+1 variables). Now, condition (ii) amounts to a system of C(n+m1,m1) linearly independent equations in C(n+m,m) variables. For example, if m=2, and n=4, then the matrix for the system of equations looks like 1 0 0 0 1 0 0 1 0 1 0 1 0 0 1 1 0 2 1 3 0 0 1 0 0 1 1 1 2 3 0 0 0 1 0 0 1 0 1 1, or like 1 0 1 0 0 1 0 0 0 1 0 1 1 0 1 2 0 0 1 3 0 0 0 1 1 1 0 1 2 3 0 0 0 0 0 0 1 1 1 1, whichever you prefer. If these were polynomials over an infinite field of characteristic 2 (with coefficients in the prime subfield), then there would be simply 2^{C(n+m1,m)} solutions, and so 2^{C(n+m1,m)}  2^{C(n+m2,m)} solutions with degree exactly n. But it's not that simple. For m=2, the number of solutions in degree n seems to be 1, 2, 4, 9, 23, 66, 206, ...? One way to generate solutions is to take a polynomial which is already a solution, pick a random term in it, and multiply it by X = x_{1}+...+x_{m}. If this creates coefficients larger than 1, then replace the extra terms similarly. In fact, this generates all solutions: Suppose P(X) is as required. Then P(X)1 must be divisible by X1. But if P(X)1 = (X1)g(X), where g(X) = a_{I}X^{I}, then this says that P(X) can be obtained from 1 = X^{0} by replacing X^{I} with XX^{I}, a_{I} times. Doing this in order of increasing I=i_{1}+...+i_{m}, it's clear that in order for P(X) to end up with nonnegative coefficients, then we can only replace X^{I} if it already appears with positive coefficient, and in order for P(X) to end up with coefficients 1, we must replace all but at most one copy of each X^{I}. Another way to look at it, for example when m=2, is to start with one checker at (0,0) in a semiinfinite checkerboard. Then repeatedly: pick a checker, and replace it with two checkers, one above and one to the right, if necessary repeating until there's no more than one checker in each square. Then we want to count positions that stay below the nth diagonal. Really the same thing, but using checkers for some reason.


IP Logged 



