Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

1 Answer 1

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.