Extending the logical-or function to a low degree polynomial over a finite field Let $x\in\{0,1\}^n$ be a binary vector of dimension $n$, and let $OR(x)$ be the "logical or" function (i.e., returns $1$ if at least one of the coordinates is $1$ and otherwise returns $0$).
Is there a way to extend $OR(x)$ to a low degree (that is, a constant degree that does not depends on $n$) polynomial over a finite field ?
(where in case the finite field contains more elements than $0,1$ - the polynomial only needs to extend $OR$, i.e., if there exists a coordinate $x_i\not\in\{0,1\}$ then the polynomial can return any element in the field)
e.g., if we ignore the low degree requirement, one can define (for a prime $q$)  $f:\mathbb{F}_q^n\to\mathbb{F}_q$ such that
$$f(x_1,\ldots,x_n)=1-(1-x_1)\cdot(1-x_2)\cdot\ldots\cdot(1-x_n)$$
Is it possible to do the same, only with low degree ? (maybe by using the fact the we can choose the finite field ?)
 A: I think that you have found the lowest degree polynomial there is. 
If $q=2$, then the result of your other recent question shows (among other things) that a polynomial of degree $\le n-1$ takes the value $1$ an even number of times on all of $\mathbf{Z}_2^n$ (=a cube of dimension $n$), but OR $=1$ exactly $2^n-1$ times.
=====================================
Added this to explain why allowing $q>2$ does not really change anything.
Let $S_n=\{0,1\}^n$, $q$ a prime (power), and $F_q=GF(q)$ the finite field of $q$ elements. Then we can view $S$ as a subset of $F_q^n$. An $n$-fold Lagrangian interpolation shows that any function $f:S\rightarrow F_q$ can be represented by a polynomial $g(x_1,x_2,\ldots,x_n)\in F_q[x_1,x_2,\ldots,x_n]$, i.e.
$f(b_1,b_2,\ldots,b_n)=g(b_1,b_2,\ldots,b_n)$ for all $(b_1,b_2,\ldots,b_n)\in S.$
Let us consider the set of polynomials $g$ yielding the same function $f$. These form a coset of the ideal $I$ of polynomials vanishing on all of $S$.
Theorem. The ideal $I$ is generated by polynomials $x_i^2-x_i$, $i=1,2,\ldots,n$.
Each coset of $I$ has a unique polynomial in the span of monomials of the set
$${\mathcal B}=\{x_{i_1}x_{i_2}\cdots x_{i_k}\mid i_1<i_2<\cdots<i_k, 0\le k\le n\}.$$
A polynomial $g$ in the $F_q$-span of ${\mathcal B}$ has the lowest possible degree in its coset $g+I$.
Proof. Obviously the polynomials $p_i=x_i^2-x_i$ all belong to $I$. Let $J$
be the ideal generated by $p_1,p_2,\ldots,p_n$, so $J\subseteq I$. Let $g$ be any polynomial. If any of the terms $a x_{i_1}^{e_1}x_{i_2}^{e_2}\cdots x_{i_k}^{e_k}$ of $g$
has a factor with exponent $e_i>1$ we can replace that factor with $x_i$. This is because
the polynomial functions $x_i$ and $x_i^{e_i}$ agree on all of $S$, whenever $e_i>1$. Because $x_i^{e_i}\equiv x_i \pmod{p_i}$, we are moving within the coset $g+J$. Doing this for all the terms of $g$ shows that $g$ can be replaced with a polynomial $g'$ 
such that 


*

*$\deg g'\le \deg g$,

*$g'\equiv g \pmod J$ (or, equivalently $g'+J=g+J$),

*$g'$ is in the span of ${\mathcal B}$.


But $|{\mathcal B}|=2^n=|S|$, and the dimension of the space $V$ of functions $S\rightarrow F_q$ is also $|S|=2^n$. Therefore 
$$
\dim F_q[x_1,x_2,\ldots,x_n]/I=|S|=\dim F_q[x_1,x_2,\ldots,x_n]/J,
$$
so it is impossible that $J$ would be a proper subset of $I$. Therefore $I=J$ and the above process of replacing $x_i^{e_i}$ with $x_i$ in all the terms of $g$ for all $i$ leads to the lowest degree polynomial $g'$
in the coset $g+I=g+J$. Q.E.D.
The claim that the lowest degree polynomial representing $OR(x_1,x_2,\ldots,x_n)$
is the one you gave follows from this. This is because your polynomial is in the span of
the monomials of ${\mathcal B}$.
