deletions | additions
diff --git a/section_Multivariate_polynomials_on_bits__.tex b/section_Multivariate_polynomials_on_bits__.tex
index ee9f7c0..361471b 100644
--- a/section_Multivariate_polynomials_on_bits__.tex
+++ b/section_Multivariate_polynomials_on_bits__.tex
...
\end{Exercise}
Two polynomials $f,g \in \Fb[x,y]$ are called \emph{equal} if
\begin{center}
\emph{a term
$x_1^iy^j$ ${x_1}^iy^j$ appears in $f$ with nonzero coefficient $a_{i,j}$ \\
if and only if \\
$x_1^iy^j$ ${x_1}^iy^j$ appears in $g$ with coefficient $a_{i,j}$.}
\end{center}
Then, we can see that, in $\Fb[x,y]$, $x^3+0y^{12}=x^3=x^3+0xy^{32}$.
\\
...
\end{Exercise}
Two polynomials $f,g \in \Fb[x,y,z]$ are called \emph{equal} if
\begin{center}
\emph{a term
$x_1^iy^hz^l$ ${x_1}^iy^hz^l$ appears in $f$ with nonzero coefficient $a_{i,h,l}$ \\
if and only if \\
$x_1^iy^hz^l$ ${x_1}^iy^hz^l$ appears in $g$ with coefficient $a_{i,h,l}$.}
\end{center}
Then, $x^3+0y^{12}=x^3=x^3+0xyz^{32}$ and $xyz=0x^3+xyz+0y^4+0z$.
\\
...
as raising to the power 2 its monomials and summing them.
\\
\underline{Now we are ready to tackle the generic case of $n$ variables:
$x_1,x_2,...,x_n$}\\ ${x_1},{x_2},...,x_n$}\\
%
A \emph{term} or \emph{monomial} in the $n$ variables
$x_1,...,x_n$ ${x_1},...,x_n$ is a product of powers of
$x_1,...,x_n$, ${x_1},...,x_n$, i.e.
$x_1^{i_1}\cdots ${x_1}^{i_1}\cdots x_n^{i_n}$ for some $i_1,...,i_n \in \NN$.\\
For example, for three variables
$x_1,x_2,x_3$, ${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$ ${x_1}^3{x_2}^8{x_3}^6$, ${x_2}{x_3}^4={x_1}^0{x_2}{x_3}^4$ ,${x_1}^4={x_1}^4{x_2}^0{x_3}^0$ are all terms.
\\
With terms, we can define polynomials in $n$ variables
$x_1,...,x_n$ ${x_1},...,x_n$ and coefficients in $\Fb$ (i.e. multivariate polynomials in the field of bits) as expressions of the form
$$f(x_1,...,x_n)=\sum_{i_1,...,i_n $$f({x_1},...,x_n)=\sum_{i_1,...,i_n \in \NN} a_{i_1,...,i_n}
x_1^{i_1}\cdots {x_1}^{i_1}\cdots x_n^{i_n} $$
such that
\begin{itemize}
\item for each $i_1,...,i_n \in \NN$, $ a_{i_1,...,i_n} \in \Fb$,
\item only a finite number of coefficients is nonzero.
\end{itemize}
The set containing all polynomials in $n$ variables
$x_1,...,x_n$ ${x_1},...,x_n$ with coefficients in
$\Fb$ is denoted by
$\Fb[x_1,...,x_n]$.\\ $\Fb[{x_1},...,x_n]$.\\
Note that
\begin{itemize}
\item
$x_2^2x_3+x_1$ ${x_2}^2{x_3}+{x_1}$ is a polynomial in
$\Fb[x_1,x_2,x_3]$; $\Fb[{x_1},{x_2},{x_3}]$; but it is \textbf{not} a polynomial in
$\Fb[x_1,x_2]$; $\Fb[{x_1},{x_2}]$;
\item
$x_1-\frac{1}{2}x_2$ ${x_1}-\frac{1}{2}{x_2}$ is not a polynomial in
$\Fb[x_1,x_2]$; $\Fb[{x_1},{x_2}]$;
\item
$x_1x_2{x_3}^3+1$ ${x_1}{x_2}{{x_3}}^3+1$ is a polynomial in
$\Fb[x_1,x_2,x_3]$. $\Fb[{x_1},{x_2},{x_3}]$.
\end{itemize}
When (as we have done before) we will deal with two or three variables, we may denote them as $x,y$ or $x,y,z$.
\\
For $1 \leq j\leq n$, the \emph{$x_j$-degree} of a term in $n$ variables
$x_1^{i_1}\cdots ${x_1}^{i_1}\cdots x_n^{i_n}$ is the value $i_j$. To simplify the expression we can use $\deg_j=\deg_{x_j}$ i.e.
$$\deg_{x_j}(x_1^{i_1}\cdots x_n^{i_n})=\deg_{j}(x_1^{i_1}\cdots $$\deg_{x_j}({x_1}^{i_1}\cdots x_n^{i_n})=\deg_{j}({x_1}^{i_1}\cdots x_n^{i_n})=i_j.$$
The \emph{total degree} (or, simply, degree)
of a term $t$ in $n$ variables
$t=x_1^{i_1}\cdots $t={x_1}^{i_1}\cdots x_n^{i_n}$ is the sum of all $\deg_j(t)'$s for all $1 \leq j\leq n$, i.e.
$$\deg(x_1^{i_1}\cdots $$\deg({x_1}^{i_1}\cdots x_n^{i_n}) =\sum_{j=1}^n
\deg_j(x_1^{i_1}\cdots \deg_j({x_1}^{i_1}\cdots x_n^{i_n}) =i_1+...+i_n.$$
If we consider
$x_1x_3^5x_4^2$, ${x_1}{x_3}^5{x_4}^2$, then
$\deg_1(x_1x_3^5x_4^2)=1$, $\deg_2(x_1x_3^5x_4^2)=0$,
$\deg_3(x_1x_3^5x_4^2)=5$, $\deg_4(x_1x_3^5x_4^2)=2$ $\deg_1({x_1}{x_3}^5{x_4}^2)=1$, $\deg_2({x_1}{x_3}^5{x_4}^2)=0$,
$\deg_3({x_1}{x_3}^5{x_4}^2)=5$, $\deg_4({x_1}{x_3}^5{x_4}^2)=2$ and
$\deg(x_1x_3^5x_4^2)=8$. $\deg({x_1}{x_3}^5{x_4}^2)=8$. \\
The \emph{degree of a polynomial} $f\in
\Fb[x_1,...,x_n] \Fb[{x_1},...,x_n] $ is the highest degree of the monomials appearing
in $f$ with nonzero coefficient, so, if
$f=x_1^3x_2+x_1x_2^6-x_3^{10}x_2$, $f={x_1}^3{x_2}+{x_1}{x_2}^6-{x_3}^{10}{x_2}$, then
$\deg(f)=\deg(x_3^{10}x_2)=11$. $\deg(f)=\deg({x_3}^{10}{x_2})=11$.
\begin{Exercise}\label{Gradi}
In
$\Fb[x_1,x_2x_3,x_4]$ $\Fb[{x_1},{x_2}{x_3},{x_4}]$ what is...
\begin{itemize}
\item the $2$-degree of
$x_2^3x_3$? ${x_2}^3{x_3}$?
\item the $4$-degree of
$x_2^3x_3$? ${x_2}^3{x_3}$?
\item the degree of
$x_2^3x_3+x_2x_4$? ${x_2}^3{x_3}+{x_2}{x_4}$?
\item the degree of
$x_1^7+x_2^4x_3^3+x_4^3x_1$? ${x_1}^7+{x_2}^4{x_3}^3+{x_4}^3{x_1}$?
\end{itemize}
\end{Exercise}
Two polynomials $f,g \in
\Fb[x_1,...,x_n]$ \Fb[{x_1},...,x_n]$ are called \emph{equal} if
\begin{center}
\emph{a term
$x_1^{i_1}\cdots ${x_1}^{i_1}\cdots x_n^{i_n}$ appears in $f$ with nonzero coefficient $a_{i_1...i_n}$ \\
if and only if \\
$x_1^{i_1}\cdots ${x_1}^{i_1}\cdots x_n^{i_n}$ appears in $g$ with coefficient $a_{i_1...i_n}$ as well.}
\end{center}
Note that $x^3+0y^{12}=x^3=x^3+0xy^{32}$ and
$x_5x_4-x_2=x_5x_4+0x_3-x_2$. ${x_5}{x_4}-{x_2}={x_5}{x_4}+0{x_3}-{x_2}$.
\\
The sum, the product and the powers of polynomials in
$\Fb[x_1,...x_n]$ $\Fb[{x_1},...x_n]$ follow the usual rules.
\\
If, for example, we take the polynomial
$f=x_3x_1+x_4+1$, $f={x_3}{x_1}+{x_4}+1$, we have that
$$f^2=(x_3x_1+x_4+1)^2=f\cdot f=(x_3x_1+x_4+1)(x_3x_1+x_4+1)$$
$$x_3^2x_1^2+x_4^2+1 $$f^2=({x_3}{x_1}+{x_4}+1)^2=f\cdot f=({x_3}{x_1}+{x_4}+1)({x_3}{x_1}+{x_4}+1)$$
$${x_3}^2{x_1}^2+{x_4}^2+1 =
(x_3x_1)^2+(x_4)^2+1^2.$$ ({x_3}{x_1})^2+({x_4})^2+1^2.$$
\begin{Exercise}
In
$\Fb[x_1,x_2,x_3,x_4,x_5]$ $\Fb[{x_1},{x_2},{x_3},{x_4},{x_5}]$ compute
\begin{itemize}
\item
$(x_1^{12}x_5+x_3^3+x_4+x_2^6x_3)+(x_4^5+x_3^3+x_2^6x_3+x_5^6x_1)$ $({x_1}^{12}{x_5}+{x_3}^3+{x_4}+{x_2}^6{x_3})+({x_4}^5+{x_3}^3+{x_2}^6{x_3}+{x_5}^6{x_1})$
\item
$(x_1^{10}x_2^6+x_3x_4x_5+x_2^5x_5)(x_1^3x_4+x_2x_5+x_3^5)$ $({x_1}^{10}{x_2}^6+{x_3}{x_4}{x_5}+{x_2}^5{x_5})({x_1}^3{x_4}+{x_2}{x_5}+{x_3}^5)$
\item
$(x_1+x_5)^3$ $({x_1}+{x_5})^3$
\end{itemize}
\end{Exercise}
