Michela Ceria edited section_Multivariate_polynomials_on_bits__.tex  about 6 years ago

Commit id: 0efc16d1f448fbd1389967c1775ff36ebe6b34c4

deletions | additions      

       

As for section \ref{Sec:Polynomials}, we start by defining terms (or monomials).  \\  A \emph{term} or \emph{monomial} in $n$ variables $x_1,...x_n$ is a product of powers of $x_1,...x_n$, i.e.   $x_1^{a_1}\cdots x_n^{a_n}$ $x_1^{i_1}\cdots x_n^{i_n}$  for some $a_1,...,a_n $i_1,...,i_n  \in \NN$.\\ For example, for three variables $x_1,x_2,x_3$, it is clear that $x_1^3x_2^8x_3^6$, $x_2x_3^4=x_1^0x_2x_3^4$ ,$x_1^4=x_1^4x_2^0x_3^0$ are all terms.  \\  With terms, we can define polynomials in $n$ variables $x_1,...x_n$ and coefficients in $\Fb$ (i.e. multivariate polynomials in the field of bits) as expressions of the form 

When (as we will usually do) we will deal with two or three variables, we will denote them as $x,y$ or $x,y,z$, so for example $xy+1\in \Fb[x,y]$, $x^4y-z^3 \in \Fb[x,y,z]$.  \\  For $1 \leq j\leq n$, the \emph{$j$-degree} of a term in $n$ variables $x_1^{i_1}\cdots x_n^{i_n}$ is the value $i_j$. In formulas   $$deg_j(x_1^{i_1}\cdots x_n^{i_n}).$$ x_n^{i_n})=i_j.$$  The \emph{total degree} (or, simply, degree)   of a term in $n$ variables $x_1^{i_1}\cdots x_n^{i_n}$ is the sum of all $deg_j$ for all $1 \leq j\leq n$, i.e.  $$deg(x_1^{i_1}\cdots x_n^{i_n}) =\sum_{j=1}^n deg_j(x_1^{i_1}\cdots x_n^{i_n}) =i_1+...+i_n.$$