Normal forms of polynomials over a semiring

[icantadd]

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}$$<br /> Nothing other than sums and products defined under the above operations are in $$R[x_1,\ldots,x_n]$$<br /> <br /> 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.<br /> 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?[/tex]

 

[fresh_42]

This is a rather specific situation. Generally a polynomial equals another if and only if all coefficients are the same. This has nothing to do with inserting values. Inserting values is usually a ring homomorphism, will say I don't know what your restrictions to a semiring will damage, and should be regarded as such. And generally you cannot conclude that pre-images are identical if their images are. You have to show that the insertion or evaluation homomorphism is injective. I don't think this is possible without further assumptions on $R$.