# What is the degree of a symmetric boolean function?

(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)

-
What would you suggest for p_1 and p_2? Gerhard "They Look Constant To Me" Paseman, 2011.08.31 –  Gerhard Paseman Aug 31 '11 at 19:33
I just noticed the big N. Never miNd. Gerhard "Time To Get Different Glasses" Paseman, 2011.08.31 –  Gerhard Paseman Aug 31 '11 at 19:58
For odd n the relation is satisfied if $p_n(i)+p_n(n-i)=0$ for all $i$. In this case, there are at least $\frac{n+1}{2}$ choices for pn. So your question concerns even $n$ only, right? –  Pietro Majer Aug 31 '11 at 20:00
(with - instead of + I guess) –  Pietro Majer Aug 31 '11 at 20:05
On the $14$-th line of the Pascal triangle, we have $1-14+91-364-1001+2002-3003-3432+3003+2002+1001-364+91-14+1=0$. This leads to a nonconstant $p_{14}$. I am not sure whether this is a sporadic or a recurring phenomenon. Anyway I propose tagging the question "additive-number-theory". –  darij grinberg Sep 1 '11 at 8:00

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.

-
Thanks. A useful reference is the survey of Buhrman and de Wolf on complexity measures of boolean functions, where current results and some proofs appear. –  Shir Sep 1 '11 at 19:29
When looking at the Cohen-Shpilka-Tal paper I mentioned above you will see that the relevant results in Buhrman and de Wolf hold for a slightly more general setting, and they emphasize the point that current lower bounds on the degree come from mod p considerations and no technique is known that distinguishes between a very small range and a comparably sized range. –  Gjergji Zaimi Sep 1 '11 at 20:12
Your "simple argument" that there are no nontrivial ways to assign the signs for $n=p-1$, $p$ prime, solves the question as stated, since it shows that there is no $N$ so that there are nontrivial solutions for $n\gt N$. –  Douglas Zare Sep 2 '11 at 0:11
I agree with Douglas, why isn't your "simple argument" in fact showing that, as you wrote, B(n)=2 for infinitely many n? –  Shir Sep 2 '11 at 5:21
Great, I edited the answer to reflect that. –  Gjergji Zaimi Sep 2 '11 at 7:09