5
$\begingroup$

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$?


          5x5
          $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?


          3-4-5
          $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.

$\endgroup$
7
  • 2
    $\begingroup$ Note that $\sqrt{x\cdot x}$ is rational if and only if it’s integral, so you may as well ask for integer distances. $\endgroup$ Oct 13, 2018 at 0:17
  • $\begingroup$ @AnthonyQuas: Thanks! Revised rational$\rightarrow$integer. $\endgroup$ Oct 13, 2018 at 1:01
  • 3
    $\begingroup$ I believe the current record for points in the plane, no three in a line, no four on a circle, all distances integral, is seven, as in Tobias Kreisel and Sascha Kurz, There are integral heptagons, no three points on a line, no four on a circle, Discrete Comput. Geom. 39 (2008), no. 4, 786–790, MR2413160 (2009d:52021) $\endgroup$ Oct 13, 2018 at 3:01
  • 1
    $\begingroup$ The Kreisel & Kurz paper is available at wm-archive.uni-bayreuth.de/fileadmin/Sascha/Publikationen2/… $\endgroup$ Oct 13, 2018 at 3:12
  • 3
    $\begingroup$ If $d=25$, then in $S(2)$, the four points: the origin: $e_1+....+e_9$, $e_{10}+....+e_{25}$ and $e_1+....+e_{25}$ are each separated by integer distances $\endgroup$ Oct 13, 2018 at 5:28

4 Answers 4

6
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
5
  • 2
    $\begingroup$ Within a factor it is obvious: any diagonal $y-x=C$ may contain at most 1 point. $\endgroup$ Oct 13, 2018 at 22:01
  • 1
    $\begingroup$ With that observation one has 3n/2 as an easy upper bound. Care to post that observation, @Fedor? Gerhard "Wish I Had Observed That" Paseman, 2018.10.13. $\endgroup$ Oct 13, 2018 at 22:20
  • $\begingroup$ @FedorPetrov Your observation is correct for lattice points, but Solymosi's result is for any point set with integral distances (as in the OP's Q2). $\endgroup$
    – Igor Rivin
    Oct 14, 2018 at 0:09
  • $\begingroup$ @IgorRivin in Q2 they are also lattice points. $\endgroup$ Oct 14, 2018 at 9:34
  • 1
    $\begingroup$ @FedorPetrov You are right. Anyway, the reason for the nontriviality of Solumosi's result is that he does not assume lattice points. $\endgroup$
    – Igor Rivin
    Oct 14, 2018 at 15:36
3
$\begingroup$

@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.

$\endgroup$
2
$\begingroup$

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!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.