deletions | additions
diff --git a/bits4.tex b/bits4.tex
index c86bdb1..d3f6ffe 100644
--- a/bits4.tex
+++ b/bits4.tex
...
By Definition \ref{ANF}, in the ANF of a boolean function $f:(\Fb)^3 \rightarrow \Fb$ there are $8$ coefficients $a, b, c, d, e, f, g, h \in \Fb$. Each of them may hold value $0$ or $1$, depending on
the function $f$, so we have two
choices for each coefficient. Thus, we have at most $2^8$ functions in $B_3$ with
ANF.
They are exactly The number of functions in $B_3$ with
ANF may be less than $2^8$
since in the case that two different choices on the coefficients of the ANF
lead to the same function, but this is impossible: if $f, g \in \Fb[x]$ are in ANF and $f \neq g$ in $\Fb[x]$, then $f \neq g$ in $B_3 $, i.e. there is at least a $3$-tuple of bits $(a,b,c)\in (\Fb)^3$
such that $f(a,b,c)\neq g(a,b,c)$ (we do not prove this, leaving it as a useful exercise to the reader).
\\ Now, pointing out that
the size of $B_3$ is $\vert B_3 \vert =
...
= B 3,$$
hence every function from $(\Fb)^3$ to $\Fb$ can be written in Absolute Normal Form.
\begin{Example}
Consider the
following function $f:(\Fb)^3 \rightarrow \Fb$
defined by \\
$f(0,0,0)=0,\, f(0,0,1)=0,\, f(0,1,0)=1$\\
$f(0,1,1)=1,\, f(1,0,0)=1,\, f(1,0,1)=1$\\
...
The absolute norm form of $f$ is
$$f (x, y, z) = axyz + bxy + cxz + dzy + ex + f y + gz + h,$$
where $a, b, c, d, e, f, g, h \in
\Fb$ , \Fb$, so
by evaluation we see that
$f (0, 0, 0) = h$.
By definition of
$f$ , Since $f (0, 0, 0)
=0$, hence $ is defined to be $0$, we can conclude $h =
0$.
By evaluating 0$.\\
Evaluating $f$ in
weight-$1$ vectors,
then in vectors with
increasing weight, the other $3$-tuples of bits
we can find all the other coefficients
with analogous arguments (hint: start with $3$-tuples s.t. the
bit $1$ appears only once, then evaluate on the $3$-tuples where $1$ appears twice and conclude with $(1,1,1)$) and we obtain
$f (x, y, z) = x + y$
\end{Example}
In general we have
