OpenMath Content Dictionary: polynomial3

Canonical URL:

http://www.openmath.org/cd/polynomial3.ocd

CD Base:

http://www.openmath.org/cd

CD File:

polynomial3.ocd

CD as XML Encoded OpenMath:

polynomial3.omcd

Defines:

factors, gcd, lcm, quotient, remainder

Date:

2004-07-12

Version:

0

Review Date:

2006-07-12

Status:

experimental

---

This CD holds a collection of basic modular arithmetic for polynomials over fields. The data structures for polynomials can be arithmetic expressions, for instance using the ring1.expression symbol, or DMP as in the CD polyd1.

---

gcd

Description:

The n-ary greatest common divisor for univariate polynomials over fields.

Example:

The gcd(X,Y,Z).

OpenMath XML (source)

<OMOBJ xmlns="http://www.openmath.org/OpenMath" version="2.0">
      <OMA>
        <OMS cd="polynomial3" name="gcd"/>        
        <OMV name="X"/>
        <OMV name="Y"/>
        <OMV name="Z"/>
      </OMA>
     </OMOBJ>

Strict Content MathML

<math xmlns="http://www.w3.org/1998/Math/MathML">
 <apply><csymbol cd="polynomial3">gcd</csymbol><ci>X</ci><ci>Y</ci><ci>Z</ci></apply>
</math>

Prefix

gcd ( X, Y, Z)

Popcorn

polynomial3.gcd($X, $Y, $Z)

Rendered Presentation MathML

$$\gcd (X,Y,Z)$$

Signatures:

sts

---

[Next: lcm] [Last: remainder] [Top]

---

lcm

Role:

application

Description:

The least common multiple of its polynomial arguments. This is unique up to units, but the choice must be compatible with that made for gcd, so that the product of the gcd and the lcm equals the product of all arguments.

Commented Mathematical property (CMP):

for all x,y we have lcm(x,y) = (x*y)/gcd(x,y)

Formal Mathematical property (FMP):

OpenMath XML (source)

<OMOBJ xmlns="http://www.openmath.org/OpenMath" version="2.0" cdbase="http://www.openmath.org/cd">
       <OMBIND>
         <OMS cd="quant1" name="forall"/>
	 <OMBVAR>
	   <OMV name="x"/>
	   <OMV name="y"/>
	 </OMBVAR>
	 <OMA>
	   <OMS name="eq" cd="relation1"/>
	   <OMA>
	     <OMS name="lcm" cd="polynomial3"/>
	     <OMV name="x"/>
	     <OMV name="y"/>
	   </OMA>
	   <OMA>
	     <OMS name="divide" cd="arith1"/>
	     <OMA>
	       <OMS name="times" cd="arith1"/>
	       <OMV name="x"/>
	       <OMV name="y"/>
	     </OMA>
	     <OMA>
	       <OMS name="gcd" cd="polynomial3"/>
	       <OMV name="x"/>
	       <OMV name="y"/>
	     </OMA>
	   </OMA>
	 </OMA>
       </OMBIND>
       </OMOBJ>

Strict Content MathML

<math xmlns="http://www.w3.org/1998/Math/MathML">
 <bind><csymbol cd="quant1">forall</csymbol>
  <bvar><ci>x</ci></bvar>
  <bvar><ci>y</ci></bvar>
  <apply><csymbol cd="relation1">eq</csymbol>
   <apply><csymbol cd="polynomial3">lcm</csymbol><ci>x</ci><ci>y</ci></apply>
   <apply><csymbol cd="arith1">divide</csymbol>
    <apply><csymbol cd="arith1">times</csymbol><ci>x</ci><ci>y</ci></apply>
    <apply><csymbol cd="polynomial3">gcd</csymbol><ci>x</ci><ci>y</ci></apply>
   </apply>
  </apply>
 </bind>
</math>

Prefix

forall [ x y ] . (eq (lcm ( x, y) , divide (times ( x, y) , gcd ( x, y) ) ) )

Popcorn

quant1.forall[$x, $y -> polynomial3.lcm($x, $y) = ($x * $y) / polynomial3.gcd($x, $y)]

Rendered Presentation MathML

$$\forall \hspace{0.17em}x,y.\mathrm{lcm}(x,y)=\frac{xy}{\gcd (x,y)}$$

Signatures:

sts

---

[Next: factors] [Previous: gcd] [Top]

---

factors

Description:

This symbol is a unary function, whose argument should be a polynomial f. When applied to f, it represents a complete list of irreducible factors of f.

Example:

The following expression represents the list [X+1,X+1] of rational polynomials.

OpenMath XML (source)

<OMOBJ xmlns="http://www.openmath.org/OpenMath" version="2.0" cdbase="http://www.openmath.org/cd">
    <OMA><OMS cd="polynomial3" name="factors"/>        
         <OMA><OMS cd="ring1" name="expression"/>
              <OMA><OMS cd="ring1" name="expression"/>
                   <OMA><OMS cd="ring3" name="poly_ring"/>
                        <OMS cd="fieldname1" name="Q"/>
                        <OMV name="X"/>
                   </OMA>
                   <OMA><OMS cd="arith1" name="plus"/>
                        <OMA><OMS cd="arith1" name="power"/>
                             <OMV name="X"/><OMI>2</OMI>
                        </OMA>
                        <OMA><OMS cd="arith1" name="times"/>
                             <OMI>2</OMI><OMV name="X"/>
                        </OMA>
                        <OMI>1</OMI>
                   </OMA>
              </OMA>
         </OMA>
    </OMA>
  </OMOBJ>

Strict Content MathML

<math xmlns="http://www.w3.org/1998/Math/MathML">
 <apply><csymbol cd="polynomial3">factors</csymbol>
  <apply><csymbol cd="ring1">expression</csymbol>
   <apply><csymbol cd="ring1">expression</csymbol>
    <apply><csymbol cd="ring3">poly_ring</csymbol><csymbol cd="fieldname1">Q</csymbol><ci>X</ci></apply>
    <apply><csymbol cd="arith1">plus</csymbol>
     <apply><csymbol cd="arith1">power</csymbol><ci>X</ci><cn type="integer">2</cn></apply>
     <apply><csymbol cd="arith1">times</csymbol><cn type="integer">2</cn><ci>X</ci></apply>
     <cn type="integer">1</cn>
    </apply>
   </apply>
  </apply>
 </apply>
</math>

Prefix

factors (expression (expression (poly_ring (Q, X) , plus (power ( X, 2) , times (2, X) , 1) ) ) )

Popcorn

polynomial3.factors(ring1.expression(ring1.expression(ring3.poly_ring(fieldname1.Q, $X), $X ^ 2 + 2 * $X + 1)))

Rendered Presentation MathML

$$\mathrm{factors}\left(\mathrm{expression}\left(\mathrm{expression}(\mathrm{poly\_ring}(Q,X),X^2+2X+1)\right)\right)$$

Signatures:

sts

---

[Next: quotient] [Previous: lcm] [Top]

---

quotient

Role:

application

Description:

This symbol represents the binary division operator on univariate polynomials over fields. That is, for univariate polynomials a and b, quotient(a,b) denotes the polynomial q such that a=b*q+r, with degree(r) less than degree(b).

Commented Mathematical property (CMP):

For all a,b with a,b univariate polynomials over a field F we have a = b * quotient(a,b) + remainder(a,b) and degree(remainder(a,b)) is less than degree(b).

Formal Mathematical property (FMP):

OpenMath XML (source)

   <OMOBJ xmlns="http://www.openmath.org/OpenMath" version="2.0" cdbase="http://www.openmath.org/cd">
     <OMBIND><OMS cd="quant1" name="forall"/>
          <OMBVAR>     <OMV name="a"/>         <OMV name="b"/>       </OMBVAR>
          <OMA><OMS cd="logic1" name="implies"/>
               <OMA><OMS cd="logic1" name="and"/>
                    <OMA><OMS cd="set1" name="in"/>
                         <OMV name="a"/>
                         <OMA id="pr"><OMS cd="polyd1" name="poly_ring_d"/>
                              <OMV name="F"/><OMI>1</OMI>
                         </OMA>
                    </OMA>
                    <OMA><OMS cd="set1" name="in"/>
                         <OMV name="b"/>
                         <OMR href="#pr"/>
                    </OMA>
               </OMA>
               <OMA><OMS cd="logic1" name="and"/>
                    <OMA><OMS cd="relation1" name="eq"/>
                         <OMV name="a"/>
                         <OMA><OMS cd="arith1" name="plus"/>
                              <OMA><OMS cd="arith1" name="times"/>
                                   <OMV name="b"/>
                                   <OMA id="q"><OMS cd="polynomial3" name="quotient"/>
                                        <OMV name="a"/><OMV name="b"/>
                                   </OMA>
                              </OMA>
                              <OMA><OMS cd="polynomial3" name="remainder"/>
                                   <OMV name="a"/><OMV name="b"/>
                              </OMA>
                         </OMA>
                    </OMA>
                    <OMA><OMS cd="relation1" name="lt"/>
                         <OMA><OMS cd="polynomial1" name="degree"/>
                              <OMR href="#r"/>
                         </OMA>
                         <OMA><OMS cd="polynomial1" name="degree"/>
                              <OMV name="b"/>
                         </OMA>
                    </OMA>
	       </OMA>
          </OMA>
     </OMBIND>
   </OMOBJ>

Strict Content MathML

<math xmlns="http://www.w3.org/1998/Math/MathML">
 <bind><csymbol cd="quant1">forall</csymbol>
  <bvar><ci>a</ci></bvar>
  <bvar><ci>b</ci></bvar>
  <apply><csymbol cd="logic1">implies</csymbol>
   <apply><csymbol cd="logic1">and</csymbol>
    <apply><csymbol cd="set1">in</csymbol>
     <ci>a</ci>
     <apply id="pr"><csymbol cd="polyd1">poly_ring_d</csymbol><ci>F</ci><cn type="integer">1</cn></apply>
    </apply>
    <apply><csymbol cd="set1">in</csymbol><ci>b</ci><share src="#pr"/></apply>
   </apply>
   <apply><csymbol cd="logic1">and</csymbol>
    <apply><csymbol cd="relation1">eq</csymbol>
     <ci>a</ci>
     <apply><csymbol cd="arith1">plus</csymbol>
      <apply><csymbol cd="arith1">times</csymbol>
       <ci>b</ci>
       <apply id="q"><csymbol cd="polynomial3">quotient</csymbol><ci>a</ci><ci>b</ci></apply>
      </apply>
      <apply><csymbol cd="polynomial3">remainder</csymbol><ci>a</ci><ci>b</ci></apply>
     </apply>
    </apply>
    <apply><csymbol cd="relation1">lt</csymbol>
     <apply><csymbol cd="polynomial1">degree</csymbol><share src="#r"/></apply>
     <apply><csymbol cd="polynomial1">degree</csymbol><ci>b</ci></apply>
    </apply>
   </apply>
  </apply>
 </bind>
</math>

Prefix

forall [ a b ] . (implies (and (in ( a, poly_ring_d ( F, 1) ) , in ( b, ) ) , and (eq ( a, plus (times ( b, quotient ( a, b) ) , remainder ( a, b) ) ) , lt (degree () , degree ( b) ) ) ) )

Popcorn

quant1.forall[$a, $b -> set1.in($a, polyd1.poly_ring_d($F, 1):pr) and set1.in($b, #pr) ==> $a = $b * polynomial3.quotient($a, $b):q + polynomial3.remainder($a, $b) and polynomial1.degree(#r) < polynomial1.degree($b)]

Rendered Presentation MathML

$$\forall \hspace{0.17em}a,b.a\in \mathrm{poly\_ring\_d}(F,1)\wedge b\in \mathrm{poly\_ring\_d}(F,1)\Rightarrow a=b\mathrm{quotient}(a,b)+\mathrm{remainder}(a,b)\wedge \mathrm{degree}\left(\right)<\mathrm{degree}\left(b\right)$$

Signatures:

sts

---

[Next: remainder] [Previous: factors] [Top]

---

remainder

Role:

application

Description:

The symbol represents a binary function, whose arguments should be univariate polynomials in the same polynomial ring whose coefficient ring is a field. When applied to a and b, it represents the polynomial remainder after division of a by b.

For univariate polynomials a and b, remainder(a,b) denotes r such that a=b*q+r, with degree(r) less
than degree(b).
See the definition of the symbol quotient for a formal statement of this property.

Signatures:

sts

---

[First: gcd] [Previous: quotient] [Top]