Given ANF (Algebraic Normal Form) as following:
$$f(x) = \oplus_{I \in P(N)} a_I (\sqcap_{i \in I} x_i) = \oplus_{I \in P(N)} a_I x^I$$..
The definition is taken from here and from the same source he says that to prove uniqueness we use Lagrange's interpolation. Can someone explain how this works.
Thank you!
The author already gave the algorithm (here he uses "Lagrange interpolation") that every Boolean function $f:\{0,1\}^n \to \{0,1\}$ has at least one ANF, that is what the adding of the elementary functions is (the worked out example on page 9/10).
This then shows that the map that sends $f$ to the polynomial ANF, is wll-defined and being onto is clear (as an ANF clearly defines a Boolean fucntion) (and it's clearly linear too). Then it is stated that the set of all ANF-like functions (the polynomial space quotient) has the same dimension as $\mathcal{BF}_n$, so linear algebra (not Lagrange) tells us the unicity, not Lagrange.