# Determining when a certain binomial sum vanishes

Consider the following sum of signed binomial coefficients: $$S_{n,a,p} = \sum_{i \equiv a \mod p} \binom{n}{i}(-1)^i$$

($n$ is a positive integer, $p$ is an odd prime, $a$ is between $0$ and $p-1$.)

I want to understand when it is zero, i.e., for any value of $p$ and $a$ to be given the set of $n$ for which $S_{n,a,p} = 0$. I have 4 observations:

1. Using the generating function $(1-x)^{n}$, one finds that $pS_{n,a,p} = \sum_{i=0}^{p-1} (1-\omega_{p}^{i})^{n} \omega_p^{-ia}$, where $\omega_p$ is a primitive root of unity of order $p$, say $e^{2 \pi i /p}$. This creature is actually the trace of $(1-\omega_{p})^{n} \omega_p^{-a}$, as an element of $\mathbb{Q}(\omega_p) / \mathbb{Q}$.

2. Using Lucas's Theorem, it is a technical manner to show that this sum is divisible by $p$ when $n \ge p$. I suspect that perhaps considering it mod higher powers of $p$ will help to solve this problem, or maybe even p-adic methods. Equation 1.12 here contains a generalization of my observation, and it has a short nice proof.

3. When $n=2a+pk$ where $k$ is odd, the symmetry $\binom{n}{i}=\binom{n}{n-i}$ shows that $S_{n,a,p} = 0$. I suspect that this is the only case.

4. When $p=3$, $S_{n,a,3}$ factors as $(1-\omega_3)^n \omega_{3}^{2a} (1+(-\omega_{3}^{2})^{n}\omega_{3}^{2a})$, and from this form it can be shown that the third observation holds.

I don't know if the algebraic formulation helps.

EDIT: The following more specific question is also of interest for me-

Do we have either $S_{n,0,p} \neq 0$ or $S_{n,1,p} \neq 0$ for any $n$ and odd prime $p$? In other words, solving this for $a=0,1$ interests me.

-
Note that if there are an even number of terms, the sum is non-zero by a straighforward application of the $i\leftrightarrow n-i$ symmetry except in your case $3$; so attention can be restricted to the case with an odd number of terms. –  joriki Jan 28 '13 at 11:41
Obviously, the sum will be zero when $n$ is extremely small compared to $a$ and $p$ (because then the sum will be empty). –  Ewan Delanoy Jan 28 '13 at 14:16
For your edit, I can't quite parse your quantifiers. Are you asking if for every $n$ and $p$ one of those two quantities is non-zero? –  JSchlather Feb 5 '13 at 14:24
Assuming you're asking for every $n$ and $p$. In the situation I mention in my answer it certainly can't be the case that both are zero. I think the only instance in which both are zero is when $2p \mid n$, this is a degenerate case because $PC_q$ is constant so the two sums that break off are equal hence $S_n$ is identically zero as a function of $a$ in this case. –  JSchlather Feb 5 '13 at 19:11

This is bizarre, I have a paper that I work on during very rainy days on this topic. What you have is a difference of two periodic binomial coefficients of period $2p$. I use the notation

$$PC_q(n,r,k)=\sum_{j \in \mathbb Z} C_q(n,k+rj)$$

where $C_q(n,k)$ denotes the exponent of $x^k$ in $(1+x+\cdots+x^{q-1})^n$. In your particular instance we're interested in the function up to a sign change

$$\Gamma_2(n,2p,p,k)=PC_2(n,2p,k)-PC_2(n,2p,k+p).$$ I've proved the following result, in a paper that I can send you, although it's in a rough state. The function $\Gamma_q(n,r,j,k)$ is positive on the interval

$$\left(\frac{N-r+j}{2},\frac{N+j}{2}\right)$$ if $q>1$, $r>2(q-1)$ and $n\geq r/(q-1)+1$ where $N=n(q-1)$. The function $\Gamma_q(n,r,j,\cdot)$ is anti-symmetric so it follows that it's negative on the interval $$\left(\frac{N+j}{2},\frac{N+j+r}{2}\right).$$ In your case for sufficiently large $n$ you'll have that $\Gamma_2(n,2p,p,k)$ will be zero if $(n+p)/2$ is an integer and it will be zero only at integers congruent to $(n+p)/2$ and $(n-p)/2$.

They behave a bit badly when $n$ is less than that and end up being zero quite a bit of the time. The behavior stabilizes as $n$ grows so I've been more concerned about that, but I have some notes about the behavior for small $n$ laying around somewhere. The proof of this result is fairly painful, the main point is determining when $PC_q(n,r,k)$ is increasing and decreasing from which the $\Gamma_q$ result follows easily.

Periodic generalized binomial coefficients were first studied by Ramus [1], although he was only concerned binomial coefficients he gave a closed form. The next bit of work on them came from Hoggatt who gave a formula for PC_q(n,r,k). Then my adviser ran into them because the Hilbert Series of the associated graded ring of the ring of functions in $n$ variables over a finite field of order $q$ is $(1+x+\cdots+x^{q-1})^n$. So they naturally showed up while we were computing the dimensions of some homologies associated to certain elements [3]. For further references on generalized binomial coefficients you can refer to Bondarenko's book [4].

I am very interested though in what context you found them.

Bibliography - [2] and [4] may be found on the fibonacci quarterlies website, [3] is available on mine or my advisers website.

[1] C. Ramus, Solution generale d'un probleme d'analyse combinatoire, J. Reine Ang. Math. 11 (1834), 352-55

[2] V. E. Hoggatt, G. L. Alexanderson. Sums of partition sets in generalized Pascal triangles. I. Fibonacci Quart. 14 (1976), no. 2, 117-125

[3] T. Hodges, J Schlather, The degree of regularity of a quadratic polynomial, Journal of Pure and Applied Algebra, Volume 217, Issue 2, February 2013, Pages 207-217,2013

[4] Bondarenko BA (1993) Generalized Pascal triangles and pyramids, their fractals, graphs and applications. Bollinger RC, translator and editor. Santa Clara, California: The Fibonacci Association. 190 p.

Note [2]: As far as I can tell the second paper they apparently intended to write was never finished. For reference Hoggatt died in 1980. Although Hoggatt did have a graduate student who wrote a master's thesis on the topic, I checked it out on inter-library loan but didn't find much of anything useful in it.

-
I would be interested in your paper, please send it to my mail, appearing on my profile. Regarding your first line - this is not bizarre, this is exactly the purpose of MO and MSE - to connect mathematicians. Similar things happened to me before on those sites... –  Ofir Jan 29 '13 at 17:40
Regarding the origins of this problem - it all started with the problem: math.stackexchange.com/questions/151623/… . I found it very interesting. I solved it by induction and reduced it to showing the following: proving there's a $c$ such that the function $f(x)=(-1)^{\langle x, \vec{1} \rangle}$ (where $\vec{1} = (1,\cdots, 1) \in \mathbb{Z}^{n}$) is not orthogonal to the function $g_c(x) = (-1)^{\sum_{i=1}^{n} x_i \equiv c \mod p}$, where the domain of $f$ and $g$ is $\{0, 1\}^{n}$ and $p$ is an odd prime. [see next comment] –  Ofir Jan 29 '13 at 17:43
[cont.] The inner-product is $\langle f_1, f_2 \rangle = \sum_{x} f_1(x)f_2(x)$. In our case, $\langle g_a, f \rangle$ equals my expression! Then I became interested in the following question: can we restrict $a$, i.e., find a small set of values such that the $g_a$ is not orthogonal to $f$ for at least one of those $a$'s? This lead me to post this question here. I asked Gadi and he told me his problem arose when he tried constructing boolean circuits from modulo-gates. –  Ofir Jan 29 '13 at 17:48
@Ofir Interesting, emails connected with profiles don't actually appear on their profile page. My email is on my homepage if you want to send me an email and I can reply. –  JSchlather Jan 29 '13 at 19:00
I am reading your papers, thanks. I've also edited my question to add a more concrete problem. –  Ofir Jan 31 '13 at 5:49