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

Consider the following high-degree extension of $OR(x)$: Choose a prime $q\in[n,2n]$ and let $p:\mathbb{F}_q^n\to\mathbb{F}_q$ such that $$p(x_1,\ldots,x_n)=1-(1-x_1)\cdot(1-x_2)\cdot\ldots\cdot(1-x_n)$$ Note that $p$ is a polynomial of degree $n$. In [ Extending the logical-or function to a low degree polynomial over a finite field ] it was concluded that there is no polynomial of degree less than $n$ which extends the $OR$ function.

Now, lets call a polynomial $p':\mathbb{F}_q^n\to\mathbb{F}_q$ an $\epsilon$-approximation of $p$ if $$\Pr_{x\in\mathbb{F}_q^n}[p(x)\neq p'(x)]<\epsilon$$

Is there a way to construct a low-degree polynomial which approximates $p$ (the high degree extension of $OR$) well ?

Just to clarify, by low-degree I mean a constant degree (which is not a function of $n$). And by approximate well, I'm aiming for $\epsilon$ which is as small as possible (hopefully there is a degree vs. approxmation-ratio tradeoff).

share|improve this question

2 Answers 2

What is the reason for selecting $q$ in that range $[n,2n]$? As in the case of the previous question(s) I think that $q=2$ is simplest. I mean, the values of OR-function are binary, the inputs are binary???

If we go with $q=2$ as before, then the theory of the Reed-Muller codes gives you the following answer: a polynomial $p\in GF(2][x_1,\ldots,x_n]$ of degree $k$ yielding a non-constant function takes the value $0$ at least $2^{n-k}$ times, and the set of zeros can be any coset of any $(n-k)$-dimensional subspace. This is equivalent to saying that the minimum Hamming distance of the Reed-Muller code $R(k,n)$ is $2^{n-k}$ and that all the minimum weight codewords have supports that are cosets of a subspace of dimension $n-k$. These facts can be found in e.g. MacWilliams & Sloane.

Therefore a polynomial of degree $k$ makes at least $2^{n-k}-1$ errors when estimating $OR(x_1,x_2,\ldots,x_n)$. So the lowest possible error probability is $(2^{n-k}-1)/2^n=2^{-k}-2^{-n}$. This is attained by e.g. the polynomial $$ p=1-(1-x_1)(1-x_2)\cdots (1-x_k), $$ and the available variation comes from replacing the $x_i$:s with binary linear combinations of them. So to get error probabilities close to $2^{-n}$ (= the smallest non-zero error probability) I'm afraid you must let $k$ grow.

I don't know the answer, if we use polynomials with coefficients from a bigger field. I very much doubt that it would help, but I may be wrong. Sorry, I seem to be answering the wrong questions today :-)

share|improve this answer
No, in this case I'm actually interested in the case of a field which is larger than $n$. I'm looking for a field with more elements than the amount of roots of the polynomial, which maintain an error rate of say - less than 1/2. –  User1234 Oct 11 '11 at 14:38
thanks for the Reed-Muller perspective though, it really made me understand the problem better. –  User1234 Oct 12 '11 at 7:34
up vote 1 down vote accepted

Well, apparently this is not possible at all for any polynomial of degree less than $n$. To see why, consider $\hat p=p-p'$. If $deg(p')<n$ then $\hat p$ is a non-zero polynomial of degree at most $n$. By the Schwartz-Zippel Lemma we get (assuming $q>n$, and $\epsilon<1$) $$\Pr_{x\in\mathbb{F}_q^n}[p(x)=p'(x)]=\Pr_{x\in\mathbb{F}_q^n}[\hat p(x)=0]\leq \frac{deg(\hat p)}{q}\leq \frac{n}{q}<1-\epsilon$$ Thus $$\Pr_{x\in\mathbb{F}_q^n}[p(x)\neq p'(x)]\geq \epsilon$$ Bummers...

share|improve this answer

Your Answer


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.