Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $f:\{1,2,\ldots,n\}\to\{-1,1\}$ be a boolean function. Can I extend $f$ to a polynomial of degree at most $n$ over $\mathbb{F}_q$, where $q\in[n,2n]$ is a prime number. i.e., is there a polynomial $p:\mathbb{F}_q\to\mathbb{F}_q$ such that $\deg(p)\leq n$ and for all $x\in\{1,2,\ldots,n\}$ holds $$p(x)=f(x)$$ where $p(x)$ can take other values than $-1,1$ for $x\not\in \{1,2,\ldots,n\}$

share|cite|improve this question
Presumably $[n]$ stands for the set $\{1,2,\ldots,n\}$? I've never seen that notation, but it is suggested. As toto says, Lagrangian interpolation polynomials will work in a way, but only if $[n]$ is a subset of $F_q$. I don't see a natural way of treating it as such, if $q$ is, say, a power of $2$. In that case $-1=1$, so may be those value of $q$ don't interest you at all? But what about the case $q=3^m$? – Jyrki Lahtonen Sep 7 '11 at 14:01
@Jyrki The notation $[n]$ is somewhat of a standard these days within theoretical CS. Also, I have seen some papers use $1, 2, \ldots, n$ as placeholders for some $n$ distinct elements of the field; as a shorthand for writing $x_1, x_2, \ldots, x_n$ or some similar notation. This is especially fine if $q$ happens to be a (or, for simplicity of presentation, chosen to be a) large prime number, and this too is a fairly common scenario. Of course, these things will be mentioned somewhere in the paper; I am not sure that that is intended here. In short: the OP should clarify a few things here :) – Srivatsan Sep 7 '11 at 14:33
Thanks for the comments ! I've edited the post accordingly. – User1234 Sep 7 '11 at 16:09
Ok. @Srivatsan: Thanks for the clarification. Tom, looks clear now. In that case I will endorse toto's solution :-) – Jyrki Lahtonen Sep 7 '11 at 17:00
up vote 3 down vote accepted

As $q>n$ you can use Lagrange interpolation polynomials.

share|cite|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.