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 6 of 6: Restore the signs to finish

Previous step Next step

In plain words

Reattaching the sign of $x_i$ to $d_i$ was designed from the start to make $a_ix_i$ equal $d_iy_i$ exactly, so the bound proved for the $y_i$ 's in Step 5 transfers over unchanged.

a_i = \begin{cases} d_i, & x_i \ge 0 \\ -d_i, & x_i < 0 \end{cases} \implies \left|\sum_i a_ix_i\right| = \left|\sum_i d_iy_i\right| \le \frac{(k-1)\sqrt n}{k^n-1}

Detailed analysis

Set $a_i=d_i$ when $x_i\ge0$ and $a_i=-d_i$ when $x_i<0$ ; then $a_ix_i=d_i|x_i|=d_iy_i$ in every case, so $\sum a_ix_i=\sum d_iy_i$ , and $|a_i|=|d_i|\le k-1$ for every $i$ ; not all $a_i$ are zero because not all $d_i$ are zero. Combining this with Step 5 gives exactly $\left|\sum a_ix_i\right|\le\frac{(k-1)\sqrt n}{k^n-1}$ , completing the proof.