2
$\begingroup$

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 ?)

$\endgroup$
  • 1
    $\begingroup$ Note that in the binary case $OR(x)=1\iff x\neq \langle 0\rangle$ (that is the $x$ is not the zero vector). This can be used to compute a similar $OR(x)$ function anywhere. Furthermore, since $\{0,1\}^n$ can be given a field structure we have that $OR(x)=1\iff x\text{ is invertible}$. $\endgroup$ – Asaf Karagila Oct 10 '11 at 8:27
  • $\begingroup$ Sorry, @Tom. I didn't notice that you allow $q>2$ here also. $\endgroup$ – Jyrki Lahtonen Oct 11 '11 at 12:35
  • $\begingroup$ @JyrkiLahtonen Oh, so in fact the problem is still open. Somehow I also forgot about the the possibility of $q>2$. $\endgroup$ – user15676 Oct 11 '11 at 13:57
  • $\begingroup$ @Tom I edited my answer. Hopefully it now explains, why using $q>2$ doesn't really change anything. The explanation is related to another question from you, where we discussed polynomials representing $F_q$-valued functions on $[\sqrt n]^m$, and concluded that we need to use all those monomials where all the exponents are $<\sqrt n$. This is essentialy the same argument. I should have seen it earlier. $\endgroup$ – Jyrki Lahtonen Oct 12 '11 at 5:00
  • $\begingroup$ @JyrkiLahtonen Super ! that's exactly the part I was missing. $\endgroup$ – user15676 Oct 12 '11 at 7:05
2
$\begingroup$

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

  1. $\deg g'\le \deg g$,
  2. $g'\equiv g \pmod J$ (or, equivalently $g'+J=g+J$),
  3. $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}$.

$\endgroup$
  • $\begingroup$ Brilliant ! Funny I didn't make the connection. $\endgroup$ – user15676 Oct 10 '11 at 8:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy