2
$\begingroup$

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

  • 0
    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$?2011-09-07
  • 0
    @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 :)2011-09-07
  • 0
    Thanks for the comments ! I've edited the post accordingly.2011-09-07
  • 0
    Ok. @Srivatsan: Thanks for the clarification. Tom, looks clear now. In that case I will endorse toto's solution :-)2011-09-07

1 Answers 1

3

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