Polynomials in Zn[x]: Degree & n^2

[Phred Willard]

I am wondering how you determine how many polynomials of degree, let's say b, are in Zn[x]. From what I gather, it looks like it does not depend on what b is, but rather what n is. Namely, n^2. Is this correct?

 

[eok20]

Surely it depends on b. What is the general form of a polynomial of degree b?

 

[icantadd]

Here is a sort of idea I have for counting polynomials. Let's generalize the problem a bit. Suppose we have n variables.

One can think of the set of elementary symmetric polynomials in n variables as the power set of the n element set and factoring out by size. Then pick any partition, for each set in the partition, say for size m,
take each m-element set, and take the product of the elements. Then for each of these partitions take the sum of the resulting products. An example here is nice.
Take the 3 variable case
Suppose we start with
\{x_1,x_2,x_3\}
Then the power set is
\{ \{x_1,x_2,x_3\} , \{x_1,x_2\} , \{x_1,x_3\} , \{x_2,x_3\} , \{x_1\} , \{x_2\} , \{x_3\} \}
Then we have for the three element class only one element so we just have the product
x_1x_2x_3
For the two element class we have
x_1x_2 + x_1x_3 + x_2x_3
And for the three element class we have
x_1 + x_2 + x_3

And we have the three elementary symmetric polynomials in 3 variables.

A similar approach works for arbitrary polynomials.
Definition: A term in a n-variate polynomial is given by a tuple (\alpha_1,\ldots,\alpha_n) and represents x_1^{\alpha_1}x_2^{\alpha_2}\cdots x_n^{\alpha_n}

One can visuallize polynomials in n variables as the powerset of the powerset of the product of an n element set with the set of natural numbers. The first powerset can be through of as all products of pairs variable-natural number pairs (thought of as variable raised to power). This means that the first powerset gives all terms. The second powerset can be thought of as all sums of all terms. This gives all the multivariate polynomials with no non-one coefficients and no additive constant terms. How does one get the constants from the ring \mathbb{Z}_m in there as well?

We have to impose two additional layers to the algorithm. So after taking the product of the n element set with the natural numbers, and then take the powerset we have all n variate terms, call this set T. Now take the product of T and \mathbb{Z}_m (the set-theoretic product to be more perspicous). Now we have all terms with all possible coefficients, call this set T'. Now when we take the powerset of T' we get the sum of all terms of all n-variate polynomials, call this set P. We only have to add in additive constants. Again take the set theoretic product of P with \mathbb{Z}_m and this gives a way to add in all the additive constants.

To limit this to polynomials of degree less than or equal to b, replace the natural numbers with the b-element set. Note that the size of an j-element set with a k-element set is a j*k-element set. The size of the powerset of a j element set is a 2^j element set. This should give a way to construct a formula to answer your question.

 

[eok20]

Here is a sort of idea I have for counting polynomials. Let's generalize the problem a bit. Suppose we have n variables.

One can think of the set of elementary symmetric polynomials in n variables as the power set of the n element set and factoring out by size. Then pick any partition, for each set in the partition, say for size m,
take each m-element set, and take the product of the elements. Then for each of these partitions take the sum of the resulting products. An example here is nice.
Take the 3 variable case
Suppose we start with
\{x_1,x_2,x_3\}
Then the power set is
\{ \{x_1,x_2,x_3\} , \{x_1,x_2\} , \{x_1,x_3\} , \{x_2,x_3\} , \{x_1\} , \{x_2\} , \{x_3\} \}
Then we have for the three element class only one element so we just have the product
x_1x_2x_3
For the two element class we have
x_1x_2 + x_1x_3 + x_2x_3
And for the three element class we have
x_1 + x_2 + x_3

And we have the three elementary symmetric polynomials in 3 variables.

A similar approach works for arbitrary polynomials.
Definition: A term in a n-variate polynomial is given by a tuple (\alpha_1,\ldots,\alpha_n) and represents x_1^{\alpha_1}x_2^{\alpha_2}\cdots x_n^{\alpha_n}

One can visuallize polynomials in n variables as the powerset of the powerset of the product of an n element set with the set of natural numbers. The first powerset can be through of as all products of pairs variable-natural number pairs (thought of as variable raised to power). This means that the first powerset gives all terms. The second powerset can be thought of as all sums of all terms. This gives all the multivariate polynomials with no non-one coefficients and no additive constant terms. How does one get the constants from the ring \mathbb{Z}_m in there as well?

We have to impose two additional layers to the algorithm. So after taking the product of the n element set with the natural numbers, and then take the powerset we have all n variate terms, call this set T. Now take the product of T and \mathbb{Z}_m (the set-theoretic product to be more perspicous). Now we have all terms with all possible coefficients, call this set T'. Now when we take the powerset of T' we get the sum of all terms of all n-variate polynomials, call this set P. We only have to add in additive constants. Again take the set theoretic product of P with \mathbb{Z}_m and this gives a way to add in all the additive constants.

To limit this to polynomials of degree less than or equal to b, replace the natural numbers with the b-element set. Note that the size of an j-element set with a k-element set is a j*k-element set. The size of the powerset of a j element set is a 2^j element set. This should give a way to construct a formula to answer your question.

This is wwwwaaaayyyyy too complicated an answer and will surely only confuse the original poster, since the original questions admits an explanation of about two lines.

 

[Phred Willard]

eok20 is right. That did blow my head up when I read it. But, I think I figured my question out. Polynomials of degree b are of the form a0+a1x+a2x^2+...+abx^b in Zn[x]. So you take the number of coefficients, b, and there are only n choices for each coefficient to be (0 to n-1) so the number of polynomials of degree b in Zn[x] is b^n.

Hope that is correct.

 

[eok20]

eok20 is right. That did blow my head up when I read it. But, I think I figured my question out. Polynomials of degree b are of the form a0+a1x+a2x^2+...+abx^b in Zn[x]. So you take the number of coefficients, b, and there are only n choices for each coefficient to be (0 to n-1) so the number of polynomials of degree b in Zn[x] is b^n.

Hope that is correct.

Your reasoning is correct but your conclusion is a little off (or maybe it was a typo): it should be n^b since you have n choices for each of the b many coefficients. That gives n*n*... = n^b possibilities.

 

[Phred Willard]

Typo.