Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
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}$. –  Asaf Karagila Oct 10 '11 at 8:27
    
Sorry, @Tom. I didn't notice that you allow $q>2$ here also. –  Jyrki Lahtonen Oct 11 '11 at 12:35
    
@JyrkiLahtonen Oh, so in fact the problem is still open. Somehow I also forgot about the the possibility of $q>2$. –  Tom Oct 11 '11 at 13:57
    
@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. –  Jyrki Lahtonen Oct 12 '11 at 5:00
    
@JyrkiLahtonen Super ! that's exactly the part I was missing. –  Tom Oct 12 '11 at 7:05

1 Answer 1

up vote 3 down vote accepted

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}$.

share|improve this answer
    
Brilliant ! Funny I didn't make the connection. –  Tom Oct 10 '11 at 8:58

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.