# Low degree polynomials over finite fields with no roots

Let $q$ be some prime. Is there a low* (preferably constant) degree multivariate polynomial over $GF(q)$ that does not have 0,1 roots?

In other words, is there a low degree $f(X)\in \mathbb{F}_q[X]$, for $X:=\{x_1,\ldots x_n\}$, such that for all $X\in\{0,1\}^n$, $f(X)\neq 0$?

Furthermore, is there a symmetric such $f(X)$ ?

(*) low degree here means logarithmic in $n$, i.e., $O(\log n)$ ($q$ is constant, so the constant hidden in the $O$ notation may depend on $q$). Constant degree (i.e., a degree independent of $n$) is even better. Also, $O(\log^c n)$ degree for a constant $c$ independent of $n$ is interesting.

Comment: Other simple examples of such $f(X)$, even if they are of high degree are also interesting to me. For instance, a "simple" polynomial would be one with few monomials. I could only find high degree, but not extremely simple, such polynomials $f$. For instance, based on exclusion-inclusion principle one can show that $1+x_1+x_2+x_1x_2$ has no 0,1 roots over $GF(3)$; this example generalizes to a degree $n$ polynomial when the number of variables is $n$, and thus it is not a low-degree polynomial (and not very simple).

• What does low mean here? As a function of $q$? Of $n$? Polynomial in these? Logarithmic? Commented Aug 25, 2016 at 21:24
• I meant if $p$ is a prime and $q$ is a power of $p$ so $\mathbb{F}_p$ is a subfield of $\mathbb{F}_q$. The point being that $0$ and $1$ are in $\mathbb{F}_p$ so you can plug them into any polynomial in $\mathbb{F}_p[X]$ and get something in $\mathbb{F}_p$ adding something in $\mathbb{F}_q \backslash \mathbb{F}_p$ lands you in $\mathbb{F}_q \backslash \mathbb{F}_p$ and in particular not zero.
– Nate
Commented Aug 25, 2016 at 23:20
• Oh oops. My bad, I didn't see that. Okay how about the polynomial $(x_1+x_2+\dots+x_n)^2 - c$ where $c$ is not a quadratic residue mod $q$? That has no roots in $\mathbb{F}_q^n$ even.
– Nate
Commented Aug 25, 2016 at 23:28
• I like Nate's suggestion. Observe that when you restrict the inputs to $\{0,1\}^n$, you can replace $x_i^2$ with $x_i$. Also observe that Jack's example bivariate polynomial over $GF(3)$ can be rewritten as $1+(x_1-x_2)^2$ (modulo the above replacements), so it comes from Nate's family. Nate's polynomial will have $n(n+1)/2+1$ terms, but the symmetry requirement forces that level of complexity anyway. Commented Aug 26, 2016 at 10:04
• OTOH, if you want a polynomial with smaller number of terms, then we can cheat and use $$f(x_1,x_2,\ldots,x_n)=1+\sum_{i=1}^n(x_i^2-x_i)$$ that obvious takes value $1$ whenever $(x_1,x_2,\ldots,x_n)\in\{0,1\}^n$. I say this is cheating, because undoubtedly the intention is that the polynomial should not become trivial upon reducing it modulo the ideal generated by $x_i^2-x_i, i=1,2,\ldots,n$. It is probably a good idea to edit the question, and add all such requirements to your list. Commented Aug 26, 2016 at 10:15

Example, where this exists: Let $q=3$ and $n=1$, then $f(x) = (x-2)$ is a polynom with one root ($x_0 = 2$) with $f(0) \neq 0$ and $f(1) \neq 0$. $f$ is also symmetric (since there is only 1 entry).
• But is degree $1$ low, in comparison to $n=1$? I think OP is well aware of this example but wants something better than degree $n$ for $n$ variables.
• Nice example, but as quid said, relative to $n=1$, this is of full degree, i.e., a high degree polynomial. And thus when you generalize this you get a degree $n$ polynomial. Indeed, it seems like this is the base case for the exclusion-inclusion polynomial I mentioned.
• Perhaps I should have said indeed that $n>q$ to avoid such polynomials: $2+x_1+x_2+\ldots+x_{q-1}$ over $GF(q)$.