, 2023

Proof 1. For any $(x_i)$ and $(y_j)$ satisfying the given conditions, we define
$$X_k = \sum_{i,j=1}^{n} a_{ijk} x_i y_j.$$
Since we can always choose $z_k$ with the same sign as $X_k$, we have
$$\sum_{i=1}^{n} \sum_{j=1}^{n} \sum_{k=1}^{n} a_{ijk} x_i y_j z_k = \sum_{k=1}^{n} |X_k|.$$
Note that (summing over all possible $(x_i)$ and $(y_j)$)
$$\begin{aligned} \sum_{(x_i),(y_j)} |X_k|^2 &= \sum_{(x_i),(y_j)} \sum_{i_1,i_2} \sum_{j_1,j_2} a_{i_1j_1k} a_{i_2j_2k} x_{i_1} x_{i_2} y_{j_1} y_{j_2} \\ &= \sum_{i_1,i_2} \sum_{j_1,j_2} a_{i_1j_1k} a_{i_2j_2k} \sum_{(x_i),(y_j)} x_{i_1} x_{i_2} y_{j_1} y_{j_2}, \end{aligned}$$
and the last line has non-zero value only when $i_1 = i_2$ and $j_1 = j_2$, so
$$\sum_{(x_i),(y_j)} |X_k|^2 = (2^n)^2 \sum_{i,j=1}^{n} a_{ijk}^2 = 2^{2n} n^2.$$
(To obtain a lower bound estimate for $\sum_{(x_i),(y_j)} |X_k|$, we need to estimate $\sum_{(x_i),(y_j)} |X_k|^n$ for some large $n$ greater than 2.) Similarly, we have
$$\sum_{(x_i),(y_j)} |X_k|^4 = \sum_{i_1,i_2,i_3,i_4} \sum_{j_1,j_2,j_3,j_4} a_{i_1j_1k} a_{i_2j_2k} a_{i_3j_3k} a_{i_4j_4k} \sum_{(x_i),(y_j)} x_{i_1} x_{i_2} x_{i_3} x_{i_4} y_{j_1} y_{j_2} y_{j_3} y_{j_4}.$$
In the last summation, it is non-zero only when $(i_1, i_2, i_3, i_4)$ and $(j_1, j_2, j_3, j_4)$ are paired up in pairs, and each term is repeated when all 4 items are the same, so we have
$$\sum_{i_1,i_2,i_3,i_4} \sum_{j_1,j_2,j_3,j_4} a_{i_1j_1k} a_{i_2j_2k} a_{i_3j_3k} a_{i_4j_4k} \sum_{(x_i),(y_j)} x_{i_1} x_{i_2} x_{i_3} x_{i_4} y_{j_1} y_{j_2} y_{j_3} y_{j_4} < 9n^4(2^n)^2.$$
Now, by Hölder's inequality,
$$\left( \sum_{(x_i),(y_j)} \left( |X_k|^{2/3} \right)^{3/2} \right)^{2/3} \left( \sum_{(x_i),(y_j)} \left( |X_k|^{4/3} \right)^3 \right)^{1/3} \geq \sum_{(x_i),(y_j)} |X_k|^2 = 2^{2n} n^2,$$
so
$$\left( \sum_{(x_i),(y_j)} |X_k| \right)^{2/3} \cdot (2^{2n} \cdot 9n^4)^{1/3} > 2^{2n} n^2.$$
Hence,
$$\sum_{(x_i),(y_j)} |X_k| > \left( (2^{2n})^{2/3} \frac{n^{2/3}}{3^{2/3}} \right)^{3/2} = 2^{2n} \cdot \frac{n}{3},$$
summing over $k$ yields
$$(*) \qquad \sum_{(x_i),(y_j)} \sum_k |X_k| > 2^{2n} \cdot \frac{n^2}{3},$$
which implies the existence of $(x_i, y_j)$ such that $\sum_k |X_k| > \frac{n^2}{3}$. The proposition holds. $\Box$

Note: The last part using Hölder's inequality can also be proved using the lemma. When $X \ge 0$, $(X - 3)^2(X + 6)X = X^4 - 27X^2 + 54X \ge 0$. Hence, we have $X^4 - 27n^2X^2 + 54n^3X \ge 0$. Thus,
$$\sum_{(x_i),(y_j)} |X_k|^4 - 27n^2 \sum_{(x_i),(y_j)} |X_k|^2 + 54n^3 \sum_{(x_i),(y_j)} |X_k| \ge 0.$$
Therefore,
$$\sum_{(x_i),(y_j)} |X_k| \ge \frac{1}{54} \cdot 2^{2n} \cdot \frac{(27n^2 \cdot n^2 - 9n^4)}{n^3} = \frac{1}{3} \cdot 2^{2n} n.$$
Summing over $k$ yields $(*)$.

Proof 2. We first prove two lemmas.
Lemma 1: Let $n$ be a positive integer, and let $a_1, a_2, \dots, a_n$ be real numbers. Then we have
$$\sum_{x_1,x_2,\dots,x_n \in \{-1,1\}} \left| \sum_{i=1}^n a_i x_i \right| \ge 2 \binom{n-1}{\lfloor \frac{n-1}{2} \rfloor} \sum_{i=1}^n |a_i|.$$
Proof of Lemma 1: Since each $x_i$ takes values from $-1, 1$, replacing $a_i$ with $|a_i|$ does not change the original expression. Therefore, without loss of generality, we can assume that $a_i \ge 0$ for $i = 1, 2, \dots, n$. Notice that when all $x_i$ simultaneously change sign, the value of $|\sum_{i=1}^n a_i x_i|$ remains the same. Thus, we have:
$$\begin{aligned} \sum_{x_1,x_2,\dots,x_n \in \{-1,1\}} \left| \sum_{i=1}^n a_i x_i \right| &\ge \sum_{\substack{x_1,x_2,\dots,x_n \in \{-1,1\} \\ x_1+x_2+\dots+x_n \ne 0}} \left| \sum_{i=1}^n a_i x_i \right| \\ &= 2 \sum_{\substack{x_1,x_2,\dots,x_n \in \{-1,1\} \\ x_1+x_2+\dots+x_n > 0}} \left| \sum_{i=1}^n a_i x_i \right| \\ &\ge 2 \sum_{\substack{x_1,x_2,\dots,x_n \in \{-1,1\} \\ x_1+x_2+\dots+x_n > 0}} \sum_{i=1}^n a_i x_i \\ &= 2 \sum_{i=1}^n \left( \sum_{\substack{x_1,x_2,\dots,x_n \in \{-1,1\} \\ x_1+x_2+\dots+x_n > 0}} x_i \right) a_i. \end{aligned}$$
Furthermore, notice that due to symmetry, the value of
$$\sum_{\substack{x_1, x_2, \dots, x_n \in \{-1, 1\} \\ x_1 + x_2 + \dots + x_n > 0}} x_i$$
does not depend on $i$. Let's consider the case when $i = n$. The value of this sum is given by
$$\begin{aligned} \sum_{\substack{x_1, x_2, \dots, x_n \in \{-1, 1\} \\ x_1 + x_2 + \dots + x_n > 0}} x_n &= \sum_{\substack{x_1, x_2, \dots, x_{n-1} \in \{-1, 1\} \\ x_1 + x_2 + \dots + x_{n-1} > -1}} 1 + \sum_{\substack{x_1, x_2, \dots, x_{n-1} \in \{-1, 1\} \\ x_1 + x_2 + \dots + x_{n-1} > 1}} (-1) \\ &= \sum_{\substack{x_1, x_2, \dots, x_{n-1} \in \{-1, 1\} \\ x_1 + x_2 + \dots + x_{n-1} \in \{0, 1\}}} 1 \\ &= \binom{n-1}{\lfloor \frac{n-1}{2} \rfloor}. \end{aligned}$$
The final step is due to the fact that $x_1, x_2, \dots, x_{n-1} \in -1, 1$ satisfy $x_1 + x_2 + \dots + x_{n-1} \in 0, 1$ if and only if exactly $\lfloor \frac{n-1}{2} \rfloor$ numbers among $x_1, x_2, \dots, x_{n-1}$ take the value 1 and exactly $\lfloor \frac{n-1}{2} \rfloor$ numbers take the value -1. Thus, Lemma 1 is proven.

Lemma 2: For any positive integer $n$, we have
$$\binom{n-1}{\lfloor \frac{n-1}{2} \rfloor} \ge \frac{2^{n-1}}{\sqrt{2n}}.$$
Proof of Lemma 2: It can be easily verified that the inequality holds for $n = 1, 2, 3$ (with equality holding for $n = 2$). For even $n = 2m \ge 4$, the inequality is equivalent to $\binom{2m}{m} \ge \frac{2^{2m}}{\sqrt{4m+2}}$; for odd $n = 2m + 1 \ge 5$, the inequality is equivalent to $\binom{2m}{m} \ge \frac{2^{2m}}{\sqrt{4m+2}}$. Thus, it suffices to prove that for any integer $m \ge 2$, we have
$$\binom{2m}{m} \ge \frac{2^{2m-1}}{\sqrt{m}}.$$
Indeed, note that
$$\binom{2m}{m} = \prod_{k=1}^{m} \frac{2k(2k-1)}{k^2} = 2^{2m} \prod_{k=1}^{m} \frac{2k-1}{2k}.$$
Let
$$A = \prod_{k=2}^{m} \frac{2k-1}{2k}, \quad B = \prod_{k=2}^{m} \frac{2k-2}{2k-1},$$
then $A > B$ and $AB = \frac{2}{2m} = \frac{1}{m}$. Hence, $A > \frac{1}{\sqrt{m}}$, which implies
$$\binom{2m}{m} = 2^{2m} \cdot \frac{1}{2} A > 2^{2m} \cdot \frac{1}{2\sqrt{m}} = \frac{2^{2m-1}}{\sqrt{m}}.$$
Lemma 2 is proven.

From the two lemmas above, we immediately obtain the following result: for any $n$ real numbers $a_1, a_2, \dots, a_n$, we have
$$\sum_{x_1, x_2, \dots, x_n \in \{-1, 1\}} \left| \sum_{i=1}^{n} a_i x_i \right| \ge \frac{2^{2n}}{\sqrt{2n}} \sum_{i=1}^{n} |a_i|.$$
By applying this result twice, we can conclude that for any $n^2$ real numbers $a_{ij}$, ($i, j = 1, 2, \dots, n$), we have
$$\text{(*) x 1, , x n, y 1, , y n -1, 1 | i=1 n j=1 n a ij x i y j | = x 1, , x n -1, 1 ( y 1, , y n -1, 1 | j=1 n ( i=1 n a ij x i ) y j | ) x 1, , x n -1, 1 ( 2 n 2n j=1 n | i=1 n a ij x i | ) = 2 n 2n j=1 n x 1, , x n -1, 1 | i=1 n a ij x i | 2 n 2n j=1 n 2 n 2n i=1 n |a ij | = 2 2n 2n i=1 n j=1 n |a ij |.}$$
Back to the original question, for a fixed set of $x_1, \dots, x_n, y_1, \dots, y_n$, we can choose $z_k \in \{-1, 1\}$ such that $z_k \sum_{i=1}^n \sum_{j=1}^n a_{ijk} x_i y_j \ge 0$ for $k=1, 2, \dots, n$. In this case,
$$\left| \sum_{i=1}^{n} \sum_{j=1}^{n} \sum_{k=1}^{n} a_{ijk} x_i y_j z_k \right| = \sum_{k=1}^{n} \left| \sum_{i=1}^{n} \sum_{j=1}^{n} a_{ijk} x_i y_j \right| \stackrel{\text{denoted as}}{=} T_{x_1, \dots, x_n, y_1, \dots, y_n}.$$
According to (*), we have
$$\sum_{x_1, \dots, x_n, y_1, \dots, y_n \in \{-1, 1\}} T_{x_1, \dots, x_n, y_1, \dots, y_n} \ge \sum_{k=1}^{n} \frac{2^{2n}}{2n} \sum_{i=1}^{n} \sum_{j=1}^{n} |a_{ijk}| = 2^{2n} \cdot \frac{n^2}{2}.$$
Thus, by the principle of averages, there exists a set of $x_1, \dots, x_n, y_1, \dots, y_n \in \{-1, 1\}$ such that
$$T_{x_1, \dots, x_n, y_1, \dots, y_n} \ge \frac{n^2}{2}.$$
Therefore, the original problem is proved. $\square$