Lattice points in a square pairwise-separated by integer distances

Question

Let $S_n$ be an $n \times n$ square of lattice points in $\mathbb{Z}^2$.

Q1. What is the largest subset $A(n)$ of lattice points in $S_n$ that have the property that every pair of points in $A(n)$ are separated by an integer Euclidean distance?

Is it simply that $|A(n)| = n$? And similarly in $\mathbb{Z}^d$ for $d>2$?

---

         
          ^{$5 \times 5$ lattice square, $5$ collinear points.}

---

Q2. What is the largest subset $B(n)$ of lattice points in $S_n$, not all collinear, that have the property that every pair of points in $B(n)$ are separated by an integer Euclidean distance?

---

         
          ^{$5 \times 5$ lattice square, $4$ noncollinear points.}

---

A $9 \times 9$ example with $5$ noncollinear points, also based on $3{-}4{-}5$ right triangles, is illustrated in the Wikipedia article Erdős–Diophantine graph.

Answer 1

Denote by $f(n)$ the maximal size $|A|$ of a subset $A\subset \{0,1,\dots,n-1\}^2$ with integer distances. We have $f(n)\leqslant 2f(\lceil n/2\rceil )$, $f(n)\leqslant 3f(\lceil n/3\rceil)$.

This follows from the following observation. $A$ can not contain two points $(a,b)$ and $(c,d)$ such that both $a-c$ and $b-d$ are odd, or both are not divisible by 3. Therefore either all abscissas of points of $A$ have the same parity (respectively, remainder modulo 3), or all ordinates. Hence $A$ is covered by two translates of $(2\mathbb{Z})\times (2\mathbb{Z})$ and by three translates of $(3\mathbb{Z})\times (3\mathbb{Z})$. This leads to above estimates.

This gives $f(n)\leqslant n$ for all $n$ of the form, say, $n=2^k3^m$ (or $n=5\cdot 2^k 3^m$ as $f(5)=5$.) Since the ratio of two consecutive numbers of this form tends to 1, we get $f(n)=n+o(n)$ for sure.

Answer 2

It is a theorem of Solymosi

Solymosi, József, Note on integral distances, Discrete Comput. Geom. 30, No. 2, 337-342 (2003). ZBL1047.52011.

(Theorem 2) that the diameter of a set of $n$ integral points in the plane is at least $c n.$ So, the trivial estimate you mention is within a constant factor of optimal.

Answer 3

@FedorPetrov's idea leads in fact to the solution of Q1. It seems that it may also provide some progress for Q2, but this is beyond this answer.

I denote $[n]=\{1,2,\dots,n\}$; with standard conventions, we have $2[n]=\{2,4,\dots,2n\}$ and $2[n]-1=\{1,3,5,\dots,2n-1\}$. Let $A$ be a subset in $[n]^2$ with integer pairwise distances. We show by the induction on $n$ that

(1) $|A|\leq n$, and (2) if $|A|=n$, then $A$ is collinear in a line parallel to a coordinate axis.

The base cases $n=1,2$ are clear. For the step, we use Fedor's observation that no two points in $A$ have opposite parities of abscissas and oppositve parities of ordinates. So we may assume all ordinates are odd. Now $A=A_0\sqcup A_1$, where the abscissas of the points in $A_0$ are even, and those for $A_1$ are odd.

Set $k=\lceil n/2\rceil\geq 2$. If $|A_0|, |A_1|\leq k-1$, then $|A|<n$, and we are done. Assume that, say, $|A_0|\geq k$. This means, by the induction hypothesis, that $A_0$ consists of all points with appropriate coordinates lying on some line $\ell$.

Assume that $A_1$ contains a point $x$ outside $\ell$. Then $A_0$ contains a $y$ such that both projections of the segment $xy$ onto the coordinate axes are segments of nonzero length, and one of those lengths is either $1$ or $2$. But there are no Pythagorean triples containing either $1$ or $2$ --- a contradiction.

Hence $A$ is collinear on $\ell$, and $|A|\leq n$, as desired.

Answer 4

Here are @AnthonyQuas's four points $\{o,p_1,p_2,p_3\}$ in $S(2) \subset \mathbb{Z}^{25}$: $$ \begin{array}{cccccccccccccccc ccccccccc} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \end{array} $$ You can see that $p_1$ has nine $1$'s in its coordinate representation, $p_2$ has sixteen $1$'s, and $p_3$ has twenty-five $1$'s: $3{-}4{-}5$ triangles again—very clever!