Bound on multi-variable polynomial interpolation with integer coefficient

Let $\vec x=(x_1,\ldots,x_s)$ and $\vec b\in\{-1,1\}^s$. We aim to find an integer coefficient multi-variable polynomial $f(\vec x)$ such that $f(\vec x)=0$ for all $\vec x\in \{-1,1\}^s\backslash\{\vec b\}$ and $0<|f(\vec b)|\le g(s)$. It is easy to see for $g(s)=2^s$ we can construct such a polynomial $f$. My question is what is the lower bound of $g(s)$ such that $f$ exists for sufficient large $s$?

flag	asked May 13 2011 at 12:04 Regularity 1

$2^s$ it is. Indeed, we may always think that your polynomial is just a linear combination of $P_I=\prod_{i\in I}x_i$ (because $x_i^2=1$). $P_I$ ($I\subset\{1,\dots,n\}$ form an orthonormal basis on the cube and the Fourier decomposition is unique, so you really have no choice whatsoever in your construction. – fedja May 13 2011 at 14:01

Browse other questions tagged polynomials interpolation or ask your own question.

question feed