Michela Ceria edited section_Multivariate_polynomials_on_bits__.tex  about 6 years ago

Commit id: f19ae039685834b5906b8b24592ab1fc1ff2706d

deletions | additions      

       

In $\Fb[x,y]$, let $f=x^3y+xy+1 $, $g=y^3+xy+1 $ and $h=xy+1$. It holds  \begin{itemize}  \item $f+g=(x^3y+xy+1)+(y^3+xy+1)=x^3y+y^3 $  \item $hf=(xy+1)*(x^3y+xy+1)=x^4y^2+x^2y^2+x^3y+1$ $hf=(xy+1)(x^3y+xy+1)=x^4y^2+x^2y^2+x^3y+1$  \end{itemize}  \end{Example}  \begin{Exercise}\label{operazionibivar} 

In $\Fb[x,y,z]$, let $f=x^3z+1 $, $g=y^3+xyz+1 $ and $h=xyz$. It holds  \begin{itemize}  \item $f+g=(x^3z+1)+(y^3+xyz+1)= x^3z+y^3+xyz $  \item $hf=(xyz)*(x^3y+xy+1)=x^4y^2z+x^2y^2z+xyz$ $hf=(xyz)(x^3y+xy+1)=x^4y^2z+x^2y^2z+xyz$  \end{itemize}  \end{Example}  \begin{Exercise}\label{operazionibivar} 

Then, we can see that, in $\Fb[x,y]$, $x^3+0y^{12}=x^3=x^3+0xy^{32}$.  \\  As seen in section \ref{Sec:Polynomials} for univariate polynomials, the sum and the product of polynomials in $\Fb[x_1,...x_n]$ are defined as for multivariate polynomials over $\RR$, only taking into account that their coefficients are bits.  \begin{Example}\label{SumEProdF2Multivar}  In $\Fb[x,y,z]$, let $f=x^2+y+1$, $g=x^3+x^2y+y$ and $h=xyz+1$. It holds  \begin{itemize}  \item $f+g=(x^2+y+1)+(x^3+x^2y+y)=x^3+x^2+x^2y+1$  \item $hf=(xyz+1)(x^2+y+1)=x^3yz+xy^2z+xyz+x^2+y+1$  \end{itemize}  \end{Example}  \begin{Exercise}\label{operazionimultivar}  Compute the following sums and products in $\Fb[x,y,z]$ and find the degree of the final result:  \begin{itemize}  \item $(xy^3+y)+(xy^3+x^2z+)$  \item $(x+y+z^3)(x+y+z^3)$  \item $\big((x+y+z)(xy^3+y)\big)+(xy+y^2+yz+1)$  \item $\big((x+1)(y+z)\big)+\big((xy+y^2+yz+1)(xz+1)\big)$  \end{itemize}  \end{Exercise}  Since we can multiply multivariate polynomials, we can raise them at a power $m$ as well, with the usual meaning.  \\  If, for example, we take the polynomial $f(x,y)=x^3+y+1\in \Fb[x,y]$, $f(x_1,x_2,x_3,x_4)=x_3x_1+x_4+1\in \Fb[x_1,x_2,x_3,x_4]$,  we have that $$f(x,y)^2=(x^3+y+1)^2=f(x,y)f(x,y)=(x^3+y+1)(x^3+y+1)$$  $$x^6+x^3y+x^3+x^3y+y^2+y+x^3+y+1=x^6+y^2+1 $$f(x_1,x_2,x_3,x_4)^2=(x_3x_1+x_4+1)^2=f(x_1,x_2,x_3,x_4)f(x_1,x_2,x_3,x_4)=(x_3x_1+x_4+1)(x_3x_1+x_4+1)$$  $$x_3^2x_1^2+x_4^2+1  = (x^3)^2+(y)^2+(1)^2.$$ (x_3x_1)^2+(x_4)^2+1^2.$$  As in the univariate case, raising a multivariate polynomial in $\Fb[x_1,...,x_n]$ to the power 2 is the same  as raising to the power 2 its monomials and summing them.