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 $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|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. –  Tom 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
add comment

1 Answer

up vote 3 down vote accepted

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

share|improve this answer
add comment

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.