What is the degree of a symmetric boolean function?

Question

(previous title " Zero sum of binomials coefficients - a stronger version ") This is a stronger version of another question.

Is there an $N\in \mathbb N$ and a sequence of non-constant functions $ \left\{ p_n:[n] \to \{ 1,-1 \} \right\}_{n=N} ^{\infty}$ such that for all $n>N$ we have:

$$ \sum _{i=0} ^{n} (-1)^{i} p_n(i) \cdot \binom {n} {i} = 0$$

For instance, for all odd values of n, we may choose $p_{n}(i)=\begin{cases} (-1)^{i} & i\leq\frac{n-1}{2}\\\ (-1)^{i+1} & i\geq\frac{n+1}{2}\end{cases}$. This simply means we sum the first half of the binomial coefficients and subtract the second half. The fact that for odd values we can partition the set of binomial coefficients evenly allows us to do that, so I don't see how the same trick may be applied for even values.

To my understanding, the methods that solved the previous question (for which I thank darij grinberg and Mikael de la Salle) are not applicable here.

My guess, as before, is that there is no such sequence (in which all functions are non-constant), any ideas on how to prove it?

(a counter example would surprise me, but is of interest as well)

Answer 1

It was already pointed out in the comments that determining for which $n$ one can find a non-constant $p_n$ is an open problem. I thought I'd give a bit of context and my understanding on what is known so far. The problem as stated has a negative answer because when $n+1$ is prime, $p_n$ must be constant.

The sums $\sum_{i=0}^n \varepsilon_i \binom{n}{i}$ are the leading coefficients of the polynomials we get from Lagrange interpolation on points $(i,\alpha(i))$ where $0\le i\le n$ and $\alpha(i)\in \lbrace 0,1\rbrace$. So the question is equivalent to

Is there a polynomial that sends $\lbrace 0,1,\dots,n\rbrace$ to $\lbrace 0,1\rbrace$, that is not constant but has degree $\le n-1$?

Let us denote the number of such polynomials by $\mathcal B(n)$. Some examples are given by $\varepsilon_i=(-1)^i$ when $n$ is even and $\varepsilon_i=-\varepsilon_{n-i}$ for odd $n$. This implies that $\mathcal B(n)\geq 2$ when $n$ is even and $\mathcal B(n)\geq 2^{\frac{n+1}{2}}$ when $n$ is odd. Finding non-trivial solutions to the problem implies improving on these lower bounds.

Here is a simple argument, that when $p$ is an odd prime $\mathcal B(p-1)=2$, so there are no non-trivial solutions. This is because $\binom{p-1}{i}\equiv (-1)^i\pmod{p}$ so the only way for the sum to be divisible by $p$ is if the sequence $(-1)^i\varepsilon_i$ is constant. This includes the examples $n=16,18$ that you confirmed with a computer search. However there are even values of $n$ for which $k(n)\geq 3$. The first example is $$\binom{8}{0}-\binom{8}{1}-\binom{8}{2}+\binom{8}{3}+\binom{8}{4}-\binom{8}{5}-\binom{8}{6}-\binom{8}{7}+\binom{8}{8}=0$$ and the next one is the one given by Darij in the comments for $n=14$. The even values of $n$ for which $\mathcal B(n)\geq 3$ and $n\le 128$ were found in J. von zur Gathen and J. Roche, "Polynomials with two values", Combinatorica 17, no. 3 (1997), 345–362. The sequence is $\lbrace 24,34,48,54\rbrace$ and numbers $2\pmod{6}$.

Your question is really about proving that $\mathcal B(n)=2$ for infinitely many $n$, and it is an open to determine such $n$ besides the values found in the von Zur Gathen-Roche paper. As I mentioned above it is equivalent to proving for such $n$ that the minimum degree of a non-constant polynomial sending $\lbrace 0,1,\dots,n\rbrace\to \lbrace 0,1\rbrace$ is $n$. The best results known so far are that the degree is $n-o(n)$, where the $o(n)$ comes from the gaps in consecutive primes (so one can take $O(n^{.525})$), but conjecturally this can be improved to $n-O(1)$.

One thing that is surprising is the following threshold phenomenon. If we look at non-constant polynomials sending $\lbrace 0,1,\dots,n\rbrace\to \lbrace 0,1,\dots,n\rbrace$, the minimum degree is $1$ (for instance $f(x)=x$), but as soon as we look at $\lbrace 0,1,\dots,n\rbrace\to \lbrace 0,1,\dots,n-1\rbrace$ the degree is at least $n-o(n)$. The current methods don't seem to make use of the fact that in the boolean case the range is simply $\lbrace 0,1\rbrace$, as they give the same bound for larger ranges. A recent paper on the topic is "On the Degree of Univariate Polynomials Over the Integers" by G. Cohen, A. Shpilka and A. Tal.