Michela Ceria edited bits2.tex  over 7 years ago

Commit id: 6ed7dae4b1400c5a106acc9b9a6d8b9f1816213e

deletions | additions      

       

How many functions $\Fb \rightarrow \Fb$ are there? exist?  \\  To answer this question, we will follow the following steps:  \begin{enumerate}  \item as we already know, given a polynomial $p(x) \in \Fb[x]$, we can evaluate it in the elements of $\Fb$, i.e. we can compute   $p(0)$ and $p(1)$, which clearly belong to $\Fb$, by mere substitution. The first question is: can Can  you find two different polynomials $f(x),g(x) \in \Fb[x]$ s.t. they have the same evaluations, i.e. $f(0)=g(0)$ and $f(1)=g(1)$? \item Let us think now about the possible values we can have via evaluation.  Given $p(x) \in \Fb[x]$ suppose we evaluate it in $0$. $p(0)$ can be either $0$ or $1$ and, in the same way, $p(1)$ can be either $0$ or $1$.  \\ 

\end{table}  As an example, if we consider the polynomial $p(x)=x^2+x$, $p(0)=0$ and $p(1)=0$ as in column $2$ of the table; if we take   $q(x)=x^2+x+1$, $q(0)=q(1)=1$ as in the third column. If we take $r(x)=x^3$, we have $r(0)=0$ and $r(1)=1$ as in column four. Finally, if we take $s(x)=x^2+1$ we have $s(0)=1$ and $s(1)=0$, as in the last column of the table.\\  Can you find the four polynomials $p(x),q(x),r(x),s(x)\in \Fb[x]$ \emph{of \textbf{of  minimal degree} such that, evaluated in $0,1$ behave exactly as in the corresponding column of the table? \item Looking at the table \ref{FourFunctions}, decide how many functions $\Fb\rightarrow \Fb$ are there. exist.  \end{enumerate}