# Using Lagrange's Interpolation Formula to show that boolean functions over finite fields are polynomials

Let $F_2$ be the set of all the functions from the finite field $GF(2^n)$ of $2^n$ elements to $GF(2)$. I am reading a textbook that proves that the elements of $F_2$ can be represented by polynomials; the authors use the Lagrange Interpolation Formula.

They say:

Any function $f\in F_2$ using Lagrange interpolation and noticing that $x^{2^n}=x$ for $x\in GF(2^n)$ can be represented as a polynomial of degree $\leq 2^n-1$. In other words, we may define the (discrete) Fourier transform for functions in $F_2$ in terms of Lagrange interpolation.

Definition: For $f\in F_2$ the discrete Fourier Transform of $f$ is defined to be $$A_k=\sum_{x\in {GF(2^n)}^*} f(x)x^{-k},\quad k=1,\dots,\,2^n-1,\; A_0=f(0)$$

They also note that $A_{2^{n}-1}=\sum_{x\in {GF(2^n)}^*}f(x)$. So far so good. But then they simply state that:

The inverse of the formula [above] is given as follows: $$f(x)=\sum_{k=0}^{2^n-1}A_k x^k, x\in GF(x^n)^*$$

Then they go on and say that this means that $F_2$ consists of polynomials.

Could somebody please explain or give some hints about how they got that inverse above? In particular, how exactly was the Lagrange interpolation formula used?

-

It sounds like they're just using the Lagrange interpolation formula as an existence argument: you know there exists a polynomial in $x$ taking prescribed values on $GF(2^n)$, and because $x^{2^n}=x$ you know this polynomial can be taken to have degree at most $2^n-1$.
Then one verifies the inverse formula by hand. For any $c\in GF(2^n)^*$ we have $0=c-c^{2^n}=(c^1+\dots+c^{2^n-1})(1-c)$, so $c=1$ or $\sum_{k=1}^{2^n-1}c^k=0$. Thus $$\sum_{k=1}^{2^n-1}\sum_{y\in GF(2^n)^*} f(y) x^k y^{-k}=\sum_{y\in GF(2^n)^*} f(y) \sum_{k=1}^{2^n-1} x^k y^{-k}=(2^n-1)f(x)=f(x).$$
Note that this transform consists of a separate transformation between $f(0)$ and $A_0$ (actually equality) and a transformation between $(f(1),\dots,f(2^n-1))$ and $(A_1,\dots,A_{2^n-1})$.
Thanks you. What you say makes sense.. In fact, in a different part of this book they justify something very similar to the equation that you mentioned. There is one issue that still worries me. It seems to me that the text has a typo: $k$ should start from $1$ instead of $0$ as you stated (or end in $2^n-2$ instead of $2^n-1$). The problem is that they use the formula with $k$ starting from $0$ in order to do other things.. Can you confirm that it is a typo and your version ($k$ starts from $1$) is correct? So far I have been confirming that but maybe I'm wrong.. – geo909 Oct 12 '12 at 15:03
@geo909: I believe $k$ should be taken to be non-zero. So $f(0),A_0$ are treated completely separately from the terms $f(x)$ for $x\neq 0$ and $A_k$ for $k\neq 0$. My original formula was incorrect - it included $y=0$ in the sum. I've updated it. – Colin McQuillan Oct 13 '12 at 17:28