- #1
Phred Willard
- 7
- 0
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?
icantadd said: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
[tex]\{x_1,x_2,x_3\}[/tex]
Then the power set is
[tex] \{ \{x_1,x_2,x_3\} , \{x_1,x_2\} , \{x_1,x_3\} , \{x_2,x_3\} , \{x_1\} , \{x_2\} , \{x_3\} \} [/tex]
Then we have for the three element class only one element so we just have the product
[tex] x_1x_2x_3 [/tex]
For the two element class we have
[tex]x_1x_2 + x_1x_3 + x_2x_3[/tex]
And for the three element class we have
[tex] x_1 + x_2 + x_3 [/tex]
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 [tex](\alpha_1,\ldots,\alpha_n)[/tex] and represents [tex] x_1^{\alpha_1}x_2^{\alpha_2}\cdots x_n^{\alpha_n}[/tex]
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 throught 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 [tex]\mathbb{Z}_m[/tex] 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 [tex]\mathbb{Z}_m[/tex] (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 [tex] \mathbb{Z}_m [/tex] 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 [tex]2^j[/tex] element set. This should give a way to construct a formula to answer your question.
Phred Willard said: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.
Polynomials in Zn[x] are expressions in the variable x with coefficients from the set of integers modulo n. This means that the coefficients can only take on values from 0 to n-1, and any coefficients that exceed n-1 will be reduced to their remainder when divided by n.
The degree of a polynomial in Zn[x] is the highest power of x that appears in the polynomial. For example, in the polynomial 4x^3 + 2x^2 + 5x + 1, the degree is 3. In Zn[x], the degree can never exceed n-1.
The value of n^2 indicates the maximum degree that a polynomial in Zn[x] can have. This is because the degree of a polynomial can never exceed n-1, and when multiplied by x, it creates a term with a power of n, which is then reduced to n-1.
No, a polynomial in Zn[x] can only have non-negative integer exponents. This is because the set of integers modulo n only includes non-negative integers, and any negative exponents would result in fractions, which are not allowed in Zn[x].
The main difference between polynomials in Zn[x] and polynomials in Q[x] is the set of coefficients used. In Zn[x], the coefficients are from the set of integers modulo n, while in Q[x], the coefficients are from the set of rational numbers. This means that the coefficients in Zn[x] are limited to a smaller range of values, while the coefficients in Q[x] can take on any rational number.