Problem 3

Let

x_1, x_2, \ldots, x_n

be real numbers satisfying

x_1^2 + x_2^2 + \cdots + x_n^2 = 1

. Prove that for every integer

k \ge 2

there are integers

a_1, a_2, \ldots, a_n

, not all

0

, such that

|a_i| \le k - 1

for all

i

and

|a_1 x_1 + a_2 x_2 + \cdots + a_n x_n| \le \dfrac{(k-1)\sqrt{n}}{k^n - 1}

Step 3 of 6: Bound every S(c) by Cauchy–Schwarz

Previous step Next step

In plain words

Cauchy–Schwarz says a weighted sum can never be much bigger than the sizes of its two ingredient vectors multiplied together — here that ceiling is exactly $(k-1)\sqrt n$ .

0 \le S(c) \le (k-1)\sqrt{n} \quad \text{for every } c \in \{0,\ldots,k-1\}^n

Detailed analysis

Since $y_i\ge0$ and $c_i\ge0$ , clearly $S(c)\ge0$ . By the Cauchy–Schwarz inequality, $S(c)=\sum c_iy_i\le\sqrt{\sum c_i^2}\cdot\sqrt{\sum y_i^2}\le\sqrt{n(k-1)^2}\cdot1=(k-1)\sqrt n$ , using $c_i\le k-1$ and $\sum y_i^2=1$ . So every one of the $k^n$ values $S(c)$ lies in the interval $[0,(k-1)\sqrt n]$ .