7
$\begingroup$

Let $p$ be a prime number, and $n$ be an integer such that $n \geq p$. Let $a_1,...,a_n$ be arbitrary integers. Let $s_0 = 1$, and for every $k \ge 1$, let $$s_k=|\{B \subset \{1,2,...,n\} : p\mid\sum_{i \in B}a_i \text{ and }|B|=k\}|.$$ Show $$p\mid\sum_{k=0}^n(-1)^ks_k.$$

Attempt so far: $\sum_{k=0}^n(-1)^ks_k$ is the number of even subsets of $\{a_1,...,a_n\}$ that is divisible by $p$ minus the number of odd subsets that is divisible by $p$.

If we view the $a_i$s in mod $p$, then clearly, all single subset that is divisible by $p$ is $o$ mod $p$.

then the subset with $2$ elements whose sum is divisible by $p$ are inverse of each other under addition mod $p$

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ This is hard to parse, like it was cut and pasted from a more general discussion. What does $f_0$ have to do with anything, for instance? $\endgroup$ – lulu May 2 at 19:36
  • $\begingroup$ it is $s_0$ sorry , I corrected it $\endgroup$ – user 6663629 May 2 at 19:37
  • $\begingroup$ Why doesn't $k$ appear anywhere in the definition of $s_k$? $\endgroup$ – lulu May 2 at 19:37
  • 2
    $\begingroup$ Sorry, I don't know a solution. As I suggested, I'd first do it for $p=2$. In that case you just need to know how many of the $a_i$ are even. If that case is too hard, the general problem won't be easier (I suspect). Beyond that, I'd look at maximal chains of good subsets. See if you can characterize what all those look like. That seems problematic though, because the maximal chains aren't necessarily disjoint. $\endgroup$ – lulu May 4 at 15:53
  • 2
    $\begingroup$ For the case $p=2$, with all the indices odd, the argument is easy: The sum over all the binomial coefficients is $2^n$, and the alternating sum of the binomial coefficients is exactly $0$. Adding we see that the sum over the even binomial coefficients is even (in fact it is $2^{n-1}$). I expect the case where some are even and some are odd is similar. $\endgroup$ – lulu May 4 at 16:07
3
+250
$\begingroup$

Let $\sum_{i \in \emptyset} a_i = 0$ for ease. Then, $$\sum_{k=0}^n (-1)^k s_k = \sum_{k=0}^n (-1)^k \sum_{\substack{B \subseteq [n] \\ |B| = k}} 1_{p \mid \sum_{i \in B} a_i} \equiv \sum_{k=0}^n (-1)^k \sum_{\substack{B \subseteq [n] \\ |B| = k}} \left[1-(\sum_{i \in B} a_i)^{p-1}\right] \pmod{p}.$$ Since $$\sum_{k=0}^n (-1)^k\sum_{\substack{B \subseteq [n] \\ |B| = k}} 1 = \sum_{k=0}^n (-1)^k {n \choose k} = (1+(-1))^n = 0,$$ it suffices to show $$\sum_{k=0}^n (-1)^k\sum_{\substack{B \subseteq [n] \\ |B| = k}} \sum_{(i_1,\dots,i_{p-1}) \in B^{p-1}} a_{i_1}\dots a_{i_{p-1}} = 0.$$ The left hand side is $$\sum_{k=0}^n (-1)^k\sum_{\substack{1 \le t \le p-1 \\ t \le k}} \sum_{\substack{(i_1,\dots,i_{p-1}) \in [n]^{p-1} \\ |\{i_1,\dots,i_{p-1}\}| = t}} a_1\dots a_{p-1} \sum_{\substack{B \subseteq [n] \\ |B| = k}} 1_{B \ni i_1,\dots,i_{p-1}}$$ $$= \sum_{k=0}^n (-1)^k\sum_{\substack{1 \le t \le p-1 \\ t \le k}} \sum_{\substack{(i_1,\dots,i_{p-1}) \in [n]^{p-1} \\ |\{i_1,\dots,i_{p-1}\}| = t}} a_{i_1}\dots a_{i_{p-1}} {n-t \choose k-t}$$ $$ = \sum_{1 \le t \le p-1} \sum_{\substack{(i_1,\dots,i_{p-1}) \in [n]^{p-1} \\ |\{i_1,\dots,i_{p-1}\}| = t}} a_{i_1}\dots a_{i_{p-1}} \sum_{t \le k \le n} (-1)^k{n-t \choose k-t}.$$ And luckily, the inner sum is $$\sum_{m=0}^{n-t} (-1)^{m+t}{n-t \choose m} = (-1)^t(1+(-1))^{n-t} = 0,$$ where the last equality used $n > t$, which is true since $t \le p-1 \le n-1 < n$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Re: the equation after "it suffices to show..." -- did you obtain it by considering the expansion of $(\sum a_i)^{p-1}$? But if you expand it, what happened to the terms e.g. $a_1 a_1 a_2$? Your indexing seems to only include terms where each $i$ is distinct. Or am I misunderstanding what you said? $\endgroup$ – antkam May 6 at 4:40
  • $\begingroup$ @antkam It's not the case that my indexing only includes terms where each $i$ is distinct. I think this is clear right after I say "the left hand side is". Let me know if I'm misunderstanding your comment. $\endgroup$ – mathworker21 May 6 at 5:33
  • $\begingroup$ Haha, I will be honest: I did not understand what you wrote after "The LHS is..." :D I got stuck trying to understand the line before that. The notation $i_1, i_2, \dots, i_{p-1} \in B$ would normally suggest each $i_j$ is distinct, right? $\endgroup$ – antkam May 6 at 5:37
  • $\begingroup$ @antkam it's ambiguous; I just edited it though. the point of right after "the LHS is" is that we do casework based on how many $i_j$'s are distinct. $\endgroup$ – mathworker21 May 6 at 5:38
  • $\begingroup$ It was NOT ambiguous! The old version was wrong and I was right! :D More seriously, thanks for fixing it. Now it makes sense. Lemme try to understand the following lines... (BTW I keep thinking there should be a combinatorial proof of this...) $\endgroup$ – antkam May 6 at 5:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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