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$

$\endgroup$
9
  • $\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, 2020 at 19:36
  • $\begingroup$ it is $s_0$ sorry , I corrected it $\endgroup$ May 2, 2020 at 19:37
  • $\begingroup$ Why doesn't $k$ appear anywhere in the definition of $s_k$? $\endgroup$
    – lulu
    May 2, 2020 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, 2020 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, 2020 at 16:07

1 Answer 1

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$.

$\endgroup$
9
  • $\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, 2020 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$ May 6, 2020 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, 2020 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$ May 6, 2020 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, 2020 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.