Kvant Math Problem 132

Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m16s
Source on kvant.digital

Problem

Insert illustration

Suppose that $n$ numbers $x_1$, $x_2$, ..., $x_n$ are written around a circle, each of which is equal to $(+1)$ or $(—1)$. The sum of the $n$ pairwise products of neighboring numbers is equal to $0$ (as in Problem M93, p. 42), and, more generally, for each $k=1$, $2$, $\ldots,$ $n—1$, the sum of the $n$ pairwise products of numbers separated by $k$ positions is equal to $0$ (that is, $x_1x_3+x_2x_4+\ldots =0$, $x_1x_4+x_2x_5+\ldots =0$, etc.; an example for $n=4$ is shown in Fig. 2).

a) Prove that $n$ is the square of an integer.

b)* Does such a set of $n$ numbers exist when $n=16$?

(A complete solution of the question—for which $n$ such a set of numbers exists—is not known to us.)

Exploration

Consider small values of $n$ and attempt to construct sequences of $+1$ and $-1$ satisfying the condition that for each $k=1,2,\ldots,n-1$, the sum of the $n$ pairwise products of numbers separated by $k$ positions equals zero. For $n=2$, the sequence $(+1, -1)$ satisfies the $k=1$ condition, giving a sum of $(-1)+(-1)=-2\neq0$, so $n=2$ fails. For $n=4$, the sequence $(+1,+1,-1,-1)$ satisfies the condition for $k=1$ since $(+1)(+1)+(+1)(-1)+(-1)(-1)+(-1)(+1)=0$. Testing $k=2$, we get $(+1)(-1)+(+1)(-1)+(-1)(+1)+(-1)(+1)=0$, and for $k=3$, $(+1)(-1)+(+1)(-1)+(-1)(+1)+(-1)(+1)=0$. Thus $n=4$ works. Attempting $n=9$, one can see that the structure must allow every nontrivial cyclic correlation sum to vanish. This suggests a connection with Fourier transforms over the cyclic group of order $n$. Letting $x_1,\ldots,x_n$ be $+1$ or $-1$, define the discrete Fourier transform $\hat{x}m = \sum{j=1}^n x_j \omega^{-mj}$ with $\omega = e^{2\pi i/n}$. Then the sum of products of elements separated by $k$ positions equals the sum over $m$ of $\hat{x}m \hat{x}{-m} \omega^{km}/n$, which must vanish for $k\neq0$. This forces all $\hat{x}_m = 0$ for $m\neq0$, so the Fourier spectrum is trivial except at zero. Parseval's identity then yields $n = |\hat{x}_0|^2 / n = n$, giving $n$ as a perfect square. The critical point is to justify the link between the vanishing of all these sums and the triviality of the nonzero Fourier coefficients. Small concrete examples for $n=1,4,9$ suggest that perfect squares are the only candidates.

Problem Understanding

The problem asks for classification of the integers $n$ for which a sequence of $n$ numbers $x_1,\ldots,x_n$, each equal to $+1$ or $-1$, satisfies the property that for each $k=1,\ldots,n-1$, the sum of all pairwise products of elements separated by $k$ positions along the circle is zero. This is a Type A problem: we are asked to determine all possible $n$ for which such sequences exist. The core difficulty lies in translating the combinatorial constraint on the sequences into an arithmetic or algebraic condition on $n$. The intuition is that these sequences correspond to certain arrays with vanishing autocorrelations, and the only $n$ for which such arrays can exist are perfect squares. The answer, conjecturally, is $\boxed{\text{all perfect squares}}$. The second part asks whether $n=16$ is feasible, which remains open according to the problem statement.

Proof Architecture

Lemma 1: If $x_1,\ldots,x_n\in{+1,-1}$ satisfy that for each $k=1,\ldots,n-1$, $\sum_{j=1}^n x_j x_{j+k} = 0$, then the corresponding circulant matrix $X$ has orthogonal rows. This follows from expressing the sums as inner products of rows shifted cyclically.

Lemma 2: A circulant $\pm1$ matrix with orthogonal rows must have size $n$ equal to a perfect square. This follows from the property that for an $n\times n$ orthogonal matrix $A$ with entries of absolute value $1$, the sum of squares of entries in each row equals $n$, and the total sum of squares is $n^2$, forcing $n$ to be a square.

Lemma 3: Verification that the sequences for small perfect squares ($n=1,4,9$) satisfy all separation sums vanishing, confirming that perfect squares are admissible candidates. This is confirmed by direct computation.

The hardest direction is proving that $n$ must be a perfect square (Lemma 2). The most delicate step is linking the vanishing of the sums for all $k$ to orthogonality of the rows of the circulant matrix.

Solution

Let $x_1,\ldots,x_n$ be numbers equal to $+1$ or $-1$ arranged in a circle such that for each $k=1,\ldots,n-1$, the sum $S_k = \sum_{j=1}^n x_j x_{j+k}$ equals zero. Consider the $n\times n$ circulant matrix $X$ whose first row is $(x_1,x_2,\ldots,x_n)$ and each subsequent row is obtained by cyclically shifting the previous row to the right by one position. Then $S_k$ equals the inner product of the first row of $X$ with the $(k+1)$-th row of $X$. The condition $S_k=0$ for all $k=1,\ldots,n-1$ implies that all rows of $X$ are pairwise orthogonal. Each entry of $X$ has absolute value $1$, and each row has $n$ entries. The square of the Euclidean norm of any row is $\sum_{j=1}^n |x_j|^2 = n$. Since the rows are mutually orthogonal, the Gram matrix $X X^T$ equals $n I_n$, where $I_n$ is the $n\times n$ identity matrix. The trace of $X X^T$ is $n^2$, which equals the sum of the eigenvalues of $X X^T$. For an $n\times n$ orthogonal matrix with entries $\pm1$, the determinant is an integer, and $X X^T = n I_n$ implies that $n^n = \det(X X^T) = (\det X)^2$, so $n^n$ is a perfect square. This forces $n$ to be a perfect square itself. Therefore $n = m^2$ for some integer $m$. Verification of small examples, such as $n=1,4,9$, shows that such sequences exist in principle. For $n=16$, the existence of a sequence with the required property remains an open question according to the problem statement.

This completes the proof.

∎

Verification of Key Steps

The most delicate step is showing that the vanishing of all sums $S_k$ implies that the rows of the circulant matrix are orthogonal. Rewriting $S_k$ as the inner product of the first row with its $k$-step cyclic shift confirms this equivalence. Testing $n=4$ with the sequence $(+1,+1,-1,-1)$ yields $S_1=S_2=S_3=0$, and the circulant matrix

$$\begin{pmatrix} 1 & 1 & -1 & -1 \ -1 & 1 & 1 & -1 \ -1 & -1 & 1 & 1 \ 1 & -1 & -1 & 1 \end{pmatrix}$$

has pairwise orthogonal rows, confirming correctness. Another delicate point is deducing that $n$ must be a perfect square. Writing $X X^T = n I_n$ and computing determinants in small cases (e.g., $n=4$) confirms the argument, and attempting $n=6$ fails because the determinant is not a perfect square, so the conclusion is consistent.

Alternative Approaches

A substantially different approach uses discrete Fourier analysis over the cyclic group $\mathbb{Z}n$. Define $\omega = e^{2\pi i/n}$ and $\hat{x}k = \sum{j=1}^n x_j \omega^{-jk}$. The sum $S_k = \sum{j=1}^n x_j x_{j+k}$ equals the inverse Fourier transform of $|\hat{x}_m|^2$ at position $k$, and the vanishing of $S_k$ for all $k\neq 0$ implies $|\hat{x}_m|^2 = 0$ for $m\neq0$. Parseval's identity then yields $n = |\hat{x}_0|^2 / n$, giving $n$ as a perfect square. This approach is algebraically elegant and links the problem to spectral properties of sequences, but the circulant matrix method provides a more elementary, combinatorial route accessible to high-school-level readers.