Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Normal forms of polynomials over a semiring

  1. Sep 3, 2010 #1
    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 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 [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?
    Last edited: Sep 3, 2010
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted