For integer numbers $x_1, x_2, y_1, y_2, y_3$ suppose that $$ x_1 + x_2 \equiv y_1 + y_2 + y_3 \pmod 3. $$ For $k=0, 1, 2$ define $$ s_k = \Big| \{ y_i \,|\, y_i \equiv k \pmod 3 \} \Big| - \Big| \{ x_i \,|\, x_i \equiv k \pmod 3 \} \Big|, $$ Show that $$ (s_2 - s_1 )/3 + (1 - (-1)^{s_0}) / 2 \leq 1 . $$

Is there any idea for proving this inequality other than case by case checking of first equation's solutions?


In fact similar problem stated for many other equations in $\mathbb{Z_3}$. For example, $$ x_1 + x_2 + x_3 + x_4\equiv y_1 \pmod 3 $$ and $$ x_1 + 1 \equiv y_1 +y_2 + y_3 \pmod 3.$$ I'm looking for a solution that can be extended for other equations!


We can assume that $x_1,x_2,y_1,y_2,y_3\in\{0,1,-1\}$. Then we can use the indicator functions \begin{align*} f_0(t) &= 1-t^2 = \begin{cases} 1 & t=0 \\ 0 & t\in\{-1,+1\} \end{cases}\\ f_1(t) &= \frac{t(t+1)}2 = \begin{cases} 1 & t=1 \\ 0 & t\in\{-1,0\} \end{cases}\quad\text{and}\\ f_2(t) &= \frac{t(t-1)}2 = \begin{cases} 1 & t=-1 \\ 0 & t\in\{0,1\} \end{cases} \end{align*} to count the numbers in the remainder classes: $$ s_k = \sum_{i=1}^3 f_k(y_i) - \sum_{i=1}^2 f_k(x_i). $$ Plugging the definition of $f_k$, we obtain $$ s_0 = 1 +x_1^2+x_2^2 -y_1^2-y_2^2-y_3^2, $$ and $$ s_2-s_1 = x_1+x_2-y_1-y_2-y_3. $$ Obviously, $|s_2-s_1|\le 5$. By the assumption, $3|s_2-s_1$. Moreover, due to $x_i^2\equiv x_i\pmod2$ and $y_i^2\equiv y_i\pmod2$, $s_2-s_1\equiv s_0-1\pmod2$.

If $s_0$ is odd then $s_2-s_1$ is even, so $6|s_2-s_1$. Therefore, $s_2-s_1=0$.

If $s_1$ is even then $s_2-s_1$ is odd, so $s_2-s_1\equiv3\pmod6$, and $|s_2-s_1|=3$.


Your congruences have the general form $$\sum_{i=1}^r x_i + c\equiv\sum_{j=1}^s y_j \quad(\textrm{mod } m).$$

This implies the following three relations among the $s_k$'s:

  1. $\sum_k k\, s_k \equiv c \ (\textrm{mod } m)$
  2. $\sum_k s_k = s - r$
  3. $\sum_k |s_k| \le r+s$, with equality iff no $x_i$ takes the same value as a $y_j$.

(The first is just the original congruence restated, and the second says that if you sum up the $s_k$'s you get the number of $y$'s minus the number of $x$'s. The third isn't needed for your example but seems useful in some larger cases; it follows since $$|s_k|\le \#\{y_j\mid y_j=k\}+\#\{x_i\mid x_i=k\}.)$$

In addition, we know that, for each $k$, $-r\le s_k\le s$.

Specializing to your example: $r=3$, $s=2$, $m=3$, $c=0$, so equations (1) and (2) reduce to

  1. $ s_1-s_2 \equiv 0 \ (\textrm{mod } 3)$
  2. $s_0+s_1+s_2 = -1 $

where $-3\le s_k\le 2$.

Equation (1) says $s_1$ and $s_2$ are congruent mod 3, but since the $s_k$'s are constrained to an interval of length 5, $|s_1-s_2|$ is either 0 or 3. In the former case, $s_1$ and $s_2$ have the same parity, so we conclude $s_0$ is odd (taking equation (2) mod 2). In the latter case, $s_1$ and $s_2$ have opposite parity, so $s_0$ is even. Thus, in both cases, we have

$$\frac{|s_1-s_2|}{3}+ \frac{1-(-1)^{s_0}}{2}= 1$$

since one of the summands is 1, and the other is 0. The desired inequality follows.


Note that $(s_2 - s_1 )$ is ($\#y_i\equiv2)-(\#y_i\equiv1)+(\#x_i\equiv1)-(\#x_i\equiv2)$. A bit of checking shows that this can be at most $3$.

Therefore $(s_2 - s_1 )/3\le1$, and the only way the inequality could fail is when $(1 - (-1)^{s_0}) / 2 = 1$. This happens when $s_0$ is odd. For the inequality to fail, it would also have to be the case that $s_2>s_1$ for the same $x_i,y_i$.

Consider the cases when $s_0$ is odd. If $s_0 = (\#y_i\equiv0)-(\#x_i\equiv0)=3-0$, $x_1$ and $x_2$ are not divisible by $3$, but their sum is, so $s_1=s_2=-1$. Similarly, if $s_0=3-2$, $s_1=s_2=0$. If $s_0=2-1$, $s_1=s_2=0$ as well, and if $s_0=1-2$, it must be the case that $s_1=s_2=-1$.

In other words, if $s_0$ is odd, then $s_1=s_2$, and the inequality always holds.

The following Excel calculations for all combinations of congruence classes mod $3$ satisfying the equal-sum requirement helped show the way to a proof.

enter image description here


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.