# Normal forms of polynomials over a semiring

1. Sep 3, 2010

Let R be a commutative semiring. That is a triple (R,+,.) such that (R,+) is a commutative monoid and (R,.) is a commutative semigroup. Let $${\mathbf \alpha}_i = \alpha_1,\alpha_2,\ldots,\alpha_n$$. The n-variate indeterminate is just free monoid on n letters. However, it is common to introduce notation for indeterminates that makes them easier to work with. This notation is that we write every element in the form $$x_1^{\alpha_1}\cdots x_n^{\alpha_n} = {\mathbf x}^{{\mathbf \alpha}}$$, and $$x_i^0 = 1$$, so that the string in the free monoid on 4 letters (for example), $$x_2x_3$$ is written as $$x_1^0x_2^1x_3^1x_4^0$$ or in the compact form $${\mathbf x}^{0,1,1,0}$$

Define $$R[x_1,\ldots,x_n]$$ to be the polynomial semiring in variables over R where
$$R[x_1,\ldots,x_n] = \left\{ \sum_i r_i {\mathbf x}^{{\mathbf \alpha}_i} | r_i \in R , {\mathbf x}^{\mathbf \alpha}_i \text{ is an n-variate indeterminate} \right \}$$ with the where
$$(\sum_i r_i {\mathbf x}^{\mathbf \alpha}_i) + (\sum_i s_i {\mathbf x}^{{\mathbf \alpha}_i}) = \sum_i (r_i+s_i){\mathbf x}^{{\mathbf \alpha}_i}$$
$$((\sum_i r_i {\mathbf x}^{{\mathbf \alpha}_i}) )( (\sum_i s_i {\mathbf x}^{{\mathbf \alpha}_i})) = \sum_k (\sum_I[i=0}^kr_i s_i){\mathbf x}^{{\mathbf \alpha}_k}$$
Nothing other than sums and products defined under the above operations are in $$R[x_1,\ldots,x_n]$$

Now, it seems reasonable to assert that two polynomials $$p = \sum_i r_i {\mathbf x}^{{\mathbf \alpha}_i}$$ and $$q = \sum_i s_i {\mathbf x}^{{\mathbf \alpha}_i}$$ are equal iff $$r_i = s_i$$ for each i. It is also reasonable to assert that polynomials in semiring are equal when viewed as functions of $$R^n$$ to R. However, we require that all products and sums are in the semiring. So if we want the two reasonable notions of polynomial equality to coincide we must be able to assert that normal form is well defined, that is, if p and q (as above) are normal forms for a polynomial, f, then $$r_i = s_i$$ for each i.
But we do not have additive cancellations in general, so suppose suppose that p and q are two normal forms for some polynomial f. Then, we can certainly show that $$r_0 = s_0$$. But withouth the property that if $$a+b=a+c \Rightarrow b=c$$ How would one show the other coefficients are equal?

Last edited: Sep 3, 2010