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 1 of 6: Reduce to nonnegative weights

Previous step Next step

In plain words

Working with $|x_i|$ instead of $x_i$ removes all the sign headaches; we can always put the correct sign back on $a_i$ at the very end without changing $|a_ix_i|$ .

y_i = |x_i| \ge 0, \qquad y_1^2+\cdots+y_n^2 = 1

Detailed analysis

Set $y_i=|x_i|\ge0$ for each $i$ ; then $\sum y_i^2=\sum x_i^2=1$ still holds. It suffices to find integers $d_1,\ldots,d_n$ , not all zero, with $|d_i|\le k-1$ and $\left|\sum d_i y_i\right|\le \frac{(k-1)\sqrt n}{k^n-1}$ : once such $d_i$ are found, set $a_i=d_i$ when $x_i\ge0$ and $a_i=-d_i$ when $x_i<0$ ; then $a_ix_i=d_iy_i$ for every $i$ , so $\sum a_ix_i=\sum d_iy_i$ has the same absolute value, and $|a_i|=|d_i|\le k-1$ .