*Note: This question aims to be a generalization of [Is it possible to create a polynomial $p(x)$ with this relation between $p(0)$ and $p(c)$?](https://mathoverflow.net/q/371972/165539) and [Is it possible to create a polynomial $p(x)$ with this relation between $p(0)$ and $p(c)$? -- Part 2](https://mathoverflow.net/q/372665/165539)*


Is there a family of functions $f\_n : \mathbb{Z}^n \to \mathbb{N}$ (or at least $\mathbb{Z}^n \to \mathbb{R}$) that takes in $n$ integers $f\_n \left(a\_1,a\_2,a\_3,...,a\_n \right) = 1$ if $\sum\_{i=1}^n a\_i=0$ and $0$ otherwise (or at least should be $\leq \epsilon$), such that $f\_n$ is a finite linear combination of functions (whose number of terms should grow at most $O(n^d)$ with $d$ not depending on $\epsilon$, $a\_i$ or $n$, though an answer that the number of terms is $O(1)$ would be preferred) that take finite products (whose degree is not restricted) of $a\_i$ as its inputs? You can assume that $\sum\_{i=1}^n a\_i \geq 0$.


**Edit:** As @QiaochuYuan pointed out,I should be clear that the terms themselves can change.



Is there a function $f$ that is a finite sum of functions with finite products of the inputs of $f$ as inputs with this property?
There's no such family of functions for $\epsilon = 0$, and even for $\epsilon\_n$ depending on $n$ decaying at a rate to be determined later. I don't know what happens if $\epsilon > 0$ is independent of $n$.


For a multiset of indices $I = \{ i\_1, \dots i\_n \}$ write $a\_I = \prod\_{i \in I} a\_i$ for the corresponding monomial. We're looking for a family of functions $f\_n$ which can be written


$$f\_n(a\_1, \dots a\_n) = \sum\_{i=1}^N f\_{n, i}(a\_{I\_{n, i}})$$


for some functions $f\_{n, i}$ and some indices $I\_{n, i}$, where $N = O(n^d)$ for some absolute constant $d$, such that $f\_n(a\_1, \dots a\_n) = 1$ if $\sum a\_i = 0$ and $|f\_n(a\_1, \dots a\_n)| < \epsilon\_n$ otherwise.
We'll restrict our attention to the Hamming cube $(a\_1, \dots a\_n) \in \{ -1, 1 \}^n$ and identify a point in this cube with the subset $S(a) = \{ i : a\_i = -1 \}$ of indices with coordinate $-1$. On this cube the monomials $a\_I$ behave very simply. Since $a\_i^2 = 1$ for $a\_i \in \{ -1, 1 \}$ we can restrict our attention to sets of indices $I$ rather than multisets. Then we have


$$a\_I = (-1)^{|S(a) \cap I|}$$


hence that $f\_{n, i}(a\_{I\_{n, i}})$ takes on one of two possible values depending on the parity of $|S(a) \cap I|$, and in fact we always just have


$$f(a\_I) = \frac{f(1) + f(-1)}{2} + \frac{f(1) - f(-1)}{2} a\_I$$


(since this identity holds for $a\_I = 1$ or $a\_I = -1$). It follows that any function of the form $\sum\_{i=1}^N f\_{n,i}(a\_{I\_{n,i}})$, when restricted to the Hamming cube, is a constant plus a linear combination of $N$ functions of the form $a\_I$.


The functions $a\_I$ are precisely the characters of $\{ -1, 1 \}^n$ regarded as a finite abelian group under pointwise multiplication, and now standard discrete Fourier analysis (the [Hadamard transform](https://en.wikipedia.org/wiki/Hadamard_transform)) tells us that any function $f : \{ -1, 1 \}^n \to \mathbb{R}$ on the Hamming cube can be represented uniquely as a linear combination of the $a\_I$, with coefficients determined by the inner products


$$\langle f, a\_I \rangle = \frac{1}{2^n} \sum\_{(a\_1, \dots a\_n) \in \{ -1, 1 \}^n} f(a\_1, \dots a\_n) (-1)^{|S(a) \cap I|}.$$


Our strategy from here will be to show that there are infinitely many $n$ such that exponentially many of the Fourier coefficients of $f\_n$ don't vanish. The points in the Hamming cube satisfying $\sum a\_i = 0$ are exactly the ${n \choose \frac n 2}$ points with the same number of $1$s as $-1$s, and in particular there are no such points if $n$ is odd; from here on we assume that $n$ is even. We have


$$\langle f\_n, a\_I \rangle = \frac{1}{2^n} \left( \sum\_{J \subseteq \{ 1, 2, \dots n \} : |J| = \frac n 2} (-1)^{|J \cap I|} + O(2^n \epsilon) \right).$$


If we replace $I$ by its complement the sum $\sum\_{J \subseteq \{ 1, 2, \dots n \} : |J| = n/2} (-1)^{|J \cap I|}$ is multiplied by $(-1)^n$, so to analyze this sum we can assume WLOG that $|I| \le \frac n 2$. By breaking it up depending on the possible values of $|J \cap I|$ we find that


$$\sum\_{J \subseteq \{ 1, 2, \dots n \} : |J| = \frac n 2} (-1)^{|J \cap I|} = \sum\_{k=0}^{|I|} (-1)^k {|I| \choose k} {n-|I| \choose \frac n 2 - k}.$$


This is the coefficient of $x^{\frac n 2}$ in $(1 - x)^{|I|} (1 + x)^{n-|I|}$, which is a little messy. This product simplifies as much as possible if $|I| = \frac n 2$, where it becomes $(1 - x^2)^{\frac n 2}$, which gives


$$\sum\_{k=0}^{\frac n 2} (-1)^k {\frac n 2 \choose k} {\frac n 2 \choose \frac n 2 - k} = \begin{cases} 0 \text{ if } \frac n 2 \equiv 1 \bmod 2 \\ (-1)^{\frac n 4} {\frac n 2 \choose \frac n 4} \text{ if } \frac n 2 \equiv 0 \bmod 2 \end{cases}$$


So from here we assume that $n = 4m$ is divisible by $4$. In this case we've shown that if $\epsilon\_{4m} = 0$ then at least ${4m \choose 2m} \sim \frac{2^{4m}}{\sqrt{2\pi m}}$ (by e.g. Stirling's formula) of the Fourier coefficients don't vanish, which is exponentially many in $n$, and in particular more than $N = O(n^d)$ for any $d$. We still get the same conclusion as long as $2^{4m} \epsilon\_{4m} < {2m \choose m} \sim \frac{2^{2m}}{\sqrt{\pi m}}$, hence as long as


$$\epsilon\_n = o \left( \frac{1}{2^{ \frac n 2} \sqrt{n}} \right).$$


If we only want to rule out $N = O(1)$ we can instead look at the ${n \choose 2}$ Fourier coefficients where $|I| = 2$; these are all equal to


$${n-2 \choose \frac n 2} - 2 {n-2 \choose \frac n 2 - 1} + {n-2 \choose \frac n 2 - 2}$$


which, after some simplifications I'll save you (I'm a little surprised I don't know an elegant way to do this), is equal to


$$\frac{(2n-1)}{(\frac n 2)(\frac n 2 + 1)} {n-2 \choose \frac n 2 -1} = \Theta \left( \frac{2^n}{n^{\frac 3 2}} \right)$$


so to guarantee that at least ${n \choose 2}$ of the Fourier coefficients are nonzero, which even rules out $N = O(n)$, it suffices to take


$$\epsilon\_n = o \left( n^{- \frac 3 2} \right).$$


Similar computations are available for other small values of $|I|$ and using more of these it ought to be possible to improve the bounds.


(Also, if we only want the conclusion for $\epsilon = 0$ there's a similar but much simpler argument given by restricting to the cube $\{ 0, 1 \}^n$ instead and observing that $f\_n(a\_1, \dots a\_n) = \prod\_{i=1}^n (1 - a\_i)$ on this cube, showing that the monomials $a\_I$ for $I$ a set (which are all we need to consider on $\{ 0, 1 \}^n$) are linearly independent, and arguing that this implies that $N \ge 2^n - 1$, for all $n$. But I don't know how to adapt this argument to the $\epsilon\_n \neq 0$ case.)


