In $GF(2)$, any function from an n-dimensional vector to a number is equal to a polynomial function of n variables. (See proof below.)
Question: Is this true for other $GF$, especially $GF(2^8)$? Is there a constructive alogrithm for this?
If so: Does this show that finding the inverse of any invertible function on $GF$ vectors is equivalent to solving a system of nonlinear equations?
Proof: Polynomial funcs are a subset but have same cardinality, since $2^{2^n} = 2^{\sum{nCj}}$.
Constructive Proof: Represent any function as decision tree. In $GF(2)$, "if x then y else z" equals $xy + xz + z$. Recursively replace each branch of decision tree with that expression.
I am assuming that the question is about whether any function $F:GF(2^n)^k\to GF(2^n)$ can be represented as a polynomial $G(x_1,x_2,\cdots, x_k)$ in $k$ variables and with coefficients in $GF(2^n)$. The answer is well known to be affirmative. We can be more precise and say that the degree of the polynomial is at most $2^n-1$ in any one of the variables.
The proof is based on the following
Lemma. Let $a\in GF(2^n)$ be any element. Then there is a polynomial $f_a(x)\in GF(2^n)[x]$ of degree $2^n-1$ such that $f_a(a)=1$ and $f_a(y)=0$ for all $y\in GF(2^n), y\neq a$.
Proof (of Lemma). Let $$ g_a(x)=\prod_{y\in GF(2^n),y\neq a} (x-y). $$ Then $$ f_a(x)=\frac1{g_a(a)} g_a(x) $$ works as prescribed. Q.E.D.
[Edit: In fact here $g_a(a)$ is the product of non-zero elements of the field. This is easily seen to be $=1$ in the case of $GF(2^n)$ and $=-1$ for finite fields of odd characteristic.]
Let us then turn our attention to the main problem. Let $\vec{a}=(a_1,a_2,\ldots,a_k)$ be any vector from $GF(2^n)^k$. Then the polynomial $$ F_{\vec{a}}(x_1,x_2,\ldots,x_k)=f_{a_1}(x_1) f_{a_2}(x_2)\cdots f_{a_k}(x_k) $$ has the value $1$, when $\vec{x}=(x_1,x_2,\ldots,x_k)=\vec{a}$, but $F(\vec{x})=0$ whenever $\vec{x}$ is any other vector in $GF(2^n)^k$.
Therefore we can constructively answer the question by stating that the polynomial $$ G(x_1,x_2,\ldots,x_k)=\sum_{\vec{a}\in GF(2^n)} F(\vec{a})\cdot F_{\vec{a}}(x_1,x_2,\ldots,x_k) $$ satisfies the equation $G(\vec{a})=F(\vec{a})$ for all $\vec{a}\in GF(2^n)^k$. Furthermore, $G$ is a polynomial of the prescribed type.
It is nice to be able to sum over all the points in your universe.