Kvant Math Problem 742
Let the points be represented by vectors $x_1,\dots,x_n$ from the center of the circle or sphere.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m31s
Source on kvant.digital
Problem
- On a circle of radius 1,
- on a sphere of radius 1
there are $n$ points. Prove that the sum of the squares of the pairwise distances between them does not exceed $n^2$.
A. Mikhailovsky, V. V. Prasolov
Exploration
Let the points be represented by vectors $x_1,\dots,x_n$ from the center of the circle or sphere. In both situations the vectors satisfy $|x_i|=1$.
For two points,
$$|x_i-x_j|^2=|x_i|^2+|x_j|^2-2x_i\cdot x_j=2-2x_i\cdot x_j.$$
Hence
$$\sum_{i<j}|x_i-x_j|^2 = 2\binom n2-2\sum_{i<j}x_i\cdot x_j.$$
The problem becomes a statement about the scalar products of unit vectors.
Testing small cases suggests the bound is sharp. For $n=2$, two antipodal points give distance $2$, so the sum of squared distances equals $4=n^2$. For $n=3$, three vertices of an equilateral triangle on the unit circle have pairwise distance squared $3$, giving total $9=n^2$. For $n=4$, four points forming a square on the unit circle give
$$4\cdot 2+2\cdot 4=16=n^2.$$
These examples suggest that the desired inequality may come from a nonnegative square. The identity
$$\left|\sum_{i=1}^n x_i\right|^2 = \sum_{i=1}^n|x_i|^2+2\sum_{i<j}x_i\cdot x_j = n+2\sum_{i<j}x_i\cdot x_j$$
expresses the sum of scalar products in terms of a square, and this square is nonnegative.
Substituting this relation into the expression for the distance sum should yield the inequality immediately. The only step that could hide an error is the passage from the pairwise scalar products to the square of the vector sum, so that identity must be written out completely.
Problem Understanding
We are given $n$ points on either a unit circle or a unit sphere. For all unordered pairs of points, we form the square of the distance between the two points. The claim is that the sum of all these squared distances does not exceed $n^2$.
This is a Type B problem, a pure proof.
The core difficulty is to convert the geometric quantity, the sum of squared pairwise distances, into an algebraic expression involving vectors of length $1$, and then identify a nonnegative quantity that controls it.
Proof Architecture
Represent every point by its position vector $x_i$ from the center; then $|x_i|=1$ for all $i$.
For every pair $(i,j)$,
$$|x_i-x_j|^2=2-2x_i\cdot x_j,$$
because both vectors have length $1$.
The square of the vector sum satisfies
$$\left|\sum_{i=1}^n x_i\right|^2 = n+2\sum_{i<j}x_i\cdot x_j,$$
obtained by expanding the scalar square.
Combining the two identities yields
$$\sum_{i<j}|x_i-x_j|^2 = n^2-\left|\sum_{i=1}^n x_i\right|^2.$$
Since a squared norm is nonnegative,
$$\sum_{i<j}|x_i-x_j|^2\le n^2.$$
The lemma most likely to fail under scrutiny is the expansion of $\left|\sum x_i\right|^2$, because an incorrect coefficient in front of the pairwise scalar products would invalidate the final identity.
Solution
Let the given points be represented by vectors
$$x_1,x_2,\dots,x_n$$
drawn from the center of the circle or sphere. In either case,
$$|x_i|=1 \qquad (i=1,\dots,n).$$
Denote by
$$S=\sum_{i<j}|x_i-x_j|^2$$
the sum of the squares of all pairwise distances.
For every pair $i<j$,
$$|x_i-x_j|^2 = |x_i|^2+|x_j|^2-2x_i\cdot x_j = 2-2x_i\cdot x_j.$$
Summing over all pairs gives
$$S = 2\binom n2 - 2\sum_{i<j}x_i\cdot x_j = n(n-1)-2\sum_{i<j}x_i\cdot x_j.$$
Now expand the square of the vector sum:
$$\left|\sum_{i=1}^n x_i\right|^2 = \left(\sum_{i=1}^n x_i\right)\cdot \left(\sum_{j=1}^n x_j\right).$$
Multiplying out,
$$\left|\sum_{i=1}^n x_i\right|^2 = \sum_{i=1}^n |x_i|^2 + 2\sum_{i<j}x_i\cdot x_j.$$
Since $|x_i|=1$,
$$\left|\sum_{i=1}^n x_i\right|^2 = n+2\sum_{i<j}x_i\cdot x_j.$$
Hence
$$2\sum_{i<j}x_i\cdot x_j = \left|\sum_{i=1}^n x_i\right|^2-n.$$
Substituting this into the formula for $S$,
$$S = n(n-1) - \left(\left|\sum_{i=1}^n x_i\right|^2-n\right) = n^2-\left|\sum_{i=1}^n x_i\right|^2.$$
A squared norm is nonnegative, so
$$\left|\sum_{i=1}^n x_i\right|^2\ge 0.$$
Therefore
$$S\le n^2.$$
Thus the sum of the squares of all pairwise distances between $n$ points on a unit circle or on a unit sphere does not exceed $n^2$.
This completes the proof.
∎
Verification of Key Steps
The first delicate step is the identity
$$|x_i-x_j|^2=2-2x_i\cdot x_j.$$
Starting from the definition,
$$|x_i-x_j|^2=(x_i-x_j)\cdot(x_i-x_j) =|x_i|^2+|x_j|^2-2x_i\cdot x_j.$$
Because the points lie on the unit circle or unit sphere,
$$|x_i|^2=|x_j|^2=1.$$
This gives the stated formula. Forgetting that the radius equals $1$ would produce an incorrect constant term.
The second delicate step is the expansion of
$$\left|\sum_{i=1}^n x_i\right|^2.$$
Writing out the double sum,
$$\sum_{i,j}x_i\cdot x_j = \sum_i|x_i|^2+\sum_{i\ne j}x_i\cdot x_j.$$
Each unordered pair ${i,j}$ appears twice in the second sum, once as $(i,j)$ and once as $(j,i)$, hence
$$\sum_{i\ne j}x_i\cdot x_j = 2\sum_{i<j}x_i\cdot x_j.$$
The factor $2$ is essential.
The final step is
$$S=n^2-\left|\sum x_i\right|^2.$$
Since every squared norm is at least $0$, the right-hand side is at most $n^2$. No geometric property beyond $|x_i|=1$ is used, which explains why the same proof works for both the circle and the sphere.
Alternative Approaches
A coordinate approach gives the same identity in a different form. If the points have coordinates $x_i=(x_{i1},\dots,x_{im})$ with $m=2$ for the circle and $m=3$ for the sphere, then
$$\sum_{i<j}|x_i-x_j|^2 = n\sum_{i=1}^n|x_i|^2-\left|\sum_{i=1}^n x_i\right|^2.$$
Since $\sum |x_i|^2=n$, this becomes
$$n^2-\left|\sum x_i\right|^2,$$
yielding the same conclusion.
Another interpretation uses the centroid of the points. The quantity $\left|\sum x_i\right|^2$ is $n^2$ times the squared distance of the centroid from the center of the circle or sphere. The identity
$$\sum_{i<j}|x_i-x_j|^2 = n^2-n^2|G|^2$$
shows that the pairwise distance sum is maximized when the centroid coincides with the center. The vector proof is preferable because it derives the result in a few lines and works in any dimension.