Return to Answer

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.

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.

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 $p-1$ and the previously mentioned finite list. 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)$, 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.

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.

It was already pointed out in the comments that this is an open problem. I thought I'd give a bit of context and my understanding on what is known so far.

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. 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 this is open. As I mentioned above it is equivalent to proving for infinitely many $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)$, but conjecturally this can be improved upon. One thing that is surprising is that 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.

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 $p-1$ and the previously mentioned finite list. 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)$, 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.