Points of $\mathbb{R}^n$ such that the distance between two points is an odd integer.

Question

I recently heard about the following result : "If there exists $x_1,\ldots,x_{n+2}\in\mathbb{R}^n$ such that for all $i\neq j$, $\|x_i-x_j\|$ is an odd integer (where $\|\cdot\|$ is the euclidean norm of $\mathbb{R}^n$), then $16$ divides $n+2$." I have absolutely no clue why it is true, some help would be appreciated to prove this result.

Answer 1

This looks like a contest question rather than an examination question. Had this been an examination question, it would be a very poor one, because its solution seems to rely on multiple tricks that are alien to most students.

Let $x_{n+2}=0$. Then $\|x_i\|\,(=\|x_i-x_{n+2}\|)$ and $\|x_i-x_j\|$ are odd integers when $i,j\le n+1$ and $i\ne j$. Since the square of any integer is congruent to $1$ modulo $8$ (because $(2k+1)^2=4k(k+1)+1$ and $k(k+1)$ is even), both $\|x_i\|^2$ and $2\langle x_i,x_j\rangle=\|x_i\|^2+\|x_j\|^2-\|x_i-x_j\|^2$ are congruent to $1$ modulo $8$. In turn, \begin{aligned} 2\|x_i\|^2&\equiv2&\mod16,\\ 2\langle x_i,x_j\rangle&\equiv1\ \text{ or }\ 9&\mod16. \end{aligned} Let $G=2X^TX$ where $X=\pmatrix{x_1&x_2&\cdots&x_{n+1}}$. The above congruences show that, modulo $16$, all diagonal entries of $G$ are congruent to $2$ and each off-diagonal entry is congruent to $1$ or $9$, but it can happen that some off-diagonal entries are congruent to $1$ and some are congruent to $9$.

Since $G$ is symmetric, if we replace some symmetric pair of off-diagonal entries by an indeterminate $t$, then $\det(G)$ is a polynomial of the form $p(t)=at^2+2bt+c$ for some integers $a,b$ and $c$. Since $p(1)$ is congruent to $p(9)$ modulo $16$, we may change all off-diagonal entries of $G$ to $1$ without changing the value of $\det(G)$ modulo $16$. (This clever argument is due to @S.Dolan.)

In other words, $\det(G)$ is congruent to $\det(I_{n+1}+ee^T)=n+2$ modulo $16$. Yet, we also have $\det(G)=\det(2X^TX)=0$ because $X$ has more columns than rows. Therefore $16|(n+2)$.

---

Update. I should have exercised due diligence first. A quick internet search reveals that this problem was posed and solved in Graham et al., Are there $n+2$ points in $E^n$ with odd integral distances? AMM 81(1):21-25, 1974. I haven't access to this journal, but in the preview of this article, it was written that

Theorem 1. For the existence of $n+2$ points in $E^n$ so that the distance between any two of them is an odd integer, it is necessary and sufficient that $n+2\equiv0\ (\operatorname{mod} 16)$.