0
$\begingroup$

I was going through the proof of zero sum problem in one dimension as provided by Abraham Ziv. The problem statement is to prove that given a set of $2n+1$ integers, we can find at least $n$ integers whose sum is divisible by $n$. The author first proved for the cases where $n$ is prime.

He chooses $\ s $ integers which are coprime to $p$, such that for no two $\ i , \ j \ \in \ N $ , $(\ a_i -\ a_j \ ) \equiv \ mod \ p $.

He starts up by proving in a set $\ A $, where any $x \in A$ is of the form $\sum_{i=1}^s \ c_i \ a_i$, where $\ c_i$ is either 1 or 0. The number of congruence classes modulo $\ p $ in $A$ are at least $\ s + 1$ congruent classes .

The proof is by induction. Now when he is trying to prove for $\ s +1$, he assumes there are minimum $ k $ congruent classes, $b_1 , b_2 , ... b_k $. By a particular congruence class modulo $\ p $ , I understand to be the set of numbers which leave the a same particular remainder when divided by $\ p $. What exactly are the integers $b_1, b_2, ... b_k $ here? Are they the remainders that are obtained after dividing by $\ p $?

Given the lack of clarity about these numbers, I am also confused by what he means when he says that "at least one of the integers $\ b_i + \ a_s $ is not congruent to all the $b $ 's." How can he ascertain this?

I hope someone can explain this to me.

$\endgroup$
2
  • $\begingroup$ Is there any particular reason you read the original paper? There are write ups that are easier to follows. $\endgroup$ – quid May 7 '16 at 20:59
  • $\begingroup$ What do you mean by $(\ a_i -\ a_j \ ) \equiv \ mod \ p $? Did you want to write $a_i-a_j \equiv 0 \pmod p$ $a_i-a_j \equiv 0 \pmod p$? $\endgroup$ – Martin Sleziak May 8 '16 at 3:54
1
$\begingroup$

What exactly are the integers $b_1, b_2, ... b_k $ here?

You can think of them as one representative of the class.

Are they the remainders that are obtained after dividing by $\ p $?

If you want you can take it to be the remainder.

Given the lack of clarity about these numbers, I am also confused by what he means when he says that "at least one of the integers $\ b_i + \ a_s $ is not congruent to all the $b $ 's." How can he ascertain this?

Suppose that $b_i + a_s $ equals some $b_j$ for all $i$.

This would yield that you have $b_1 + j a_s$ for $j=0,\dots, s$ in the set of residue classes formed by the $b_i$. Yet these are all distinct modulo $p$ so this is impossible, as there are $s+1$.

If you know the Cauchy—Davenport theorem you can use that instead.

$\endgroup$

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.