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 [tex] {\mathbf \alpha}_i = \alpha_1,\alpha_2,\ldots,\alpha_n [/tex]. The(adsbygoogle = window.adsbygoogle || []).push({}); n-variate indeterminateis 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 [tex] x_1^{\alpha_1}\cdots x_n^{\alpha_n} = {\mathbf x}^{{\mathbf \alpha}} [/tex], and [tex] x_i^0 = 1 [/tex], so that the string in the free monoid on 4 letters (for example), [tex] x_2x_3 [/tex] is written as [tex] x_1^0x_2^1x_3^1x_4^0 [/tex] or in the compact form [tex] {\mathbf x}^{0,1,1,0} [/tex]

Define [tex] R[x_1,\ldots,x_n] [/tex] to be the polynomial semiring in variables over R where

[tex] 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 \} [/tex] with the where

[tex] (\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} [/tex]

[tex] ((\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} [/tex]

Nothing other than sums and products defined under the above operations are in [tex] R[x_1,\ldots,x_n] [/tex]

Now, it seems reasonable to assert that two polynomials [tex] p = \sum_i r_i {\mathbf x}^{{\mathbf \alpha}_i} [/tex] and [tex] q = \sum_i s_i {\mathbf x}^{{\mathbf \alpha}_i} [/tex] are equal iff [tex] r_i = s_i [/tex] for each i. It is also reasonable to assert that polynomials in semiring are equal when viewed as functions of [tex] R^n [/tex] 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 [tex] r_i = s_i [/tex] 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 [tex] r_0 = s_0 [/tex]. But withouth the property that if [tex] a+b=a+c \Rightarrow b=c [/tex] How would one show the other coefficients are equal?

**Physics Forums - The Fusion of Science and Community**

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Normal forms of polynomials over a semiring

Can you offer guidance or do you also need help?

Draft saved
Draft deleted

Loading...

Similar Threads - Normal forms polynomials | Date |
---|---|

Jordan Normal Form & Generalized Eigenvectors | Apr 17, 2012 |

Jordan Normal Form Issues | Sep 13, 2011 |

Jordan Normal Form physical applications | Apr 29, 2011 |

Grammar to Chomsky Normal Form | Dec 12, 2010 |

Transform Grammer to Chomsky Normal Form | Oct 20, 2009 |

**Physics Forums - The Fusion of Science and Community**