On solutions of an equation in $\mathbb{Z}_3$

Question

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?

Edit:

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!

Answer 1

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

Answer 2

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.

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