What is the maximum number of points $p_i\in\mathbb{Z}^2$ such that no three points are co-linear and $d(p_i,p_j)\in\mathbb{Z}\forall i,j\in[k]?$

67 Views Asked by At

What is $k,$ the maximum number of points $p_i = (x_i, y_i)\in\mathbb{Z}^2,\ i\in \{1,\ldots,k\},\ $ such that no three points $p_{i_1},\ p_{i_2},\ p_{i_3},\ $ are co-linear, and $d(p_i,p_j):= \sqrt{ { (x_i-x_j)}^2 + {(y_i-y_j)}^2 }\in\mathbb{Z}\ \forall\ i,j\in \{1,\ldots,k\}\ ? $

The best I can think of is $k=4,$ for example any upright rectangle with vertices on lattice points such that two vertices on a diagonal forms a Pythagorean triangle with a third point. Is it possible to do better than this?

I looked at this question, but I don't think the answers require the points to be on lattice points.

Lindemann-Weierstrass or (less likely) Niven's theorem might be relevant, or perhaps I'm missing something more obvious?

1

There are 1 best solutions below

0
On

I don't know if you can find an infinite set, but any finite number is possible. Take $\varphi$ with $\sin (\varphi)=\frac35, \cos (\varphi)=\frac45$.

The points $(x_n,y_n) = (\cos(2n\varphi),\sin(2n\varphi))$ then are all rational (the summation theorems for $\sin$ and $\cos$ make them just sums of products of $\sin (\varphi),\cos (\varphi)$). They are all on a circle with radius $1$ (so no $3$ on a line) and the distance between $(x_n,y_n)$ and $(x_m,y_m)$ is $2|\sin((n-m)\varphi)|$, which is again rational.

What needs to be shown is that there are as many different points among those as desired. I guess they are all different, but the formula

$$\cos (2x)=2\cos^2(x)-1$$

at least shows that if $\cos(x)=\frac{p}q \in \mathbb Q$ is lowest terms with $q>2$, then $\cos(2x)$ in lowest terms has a larger denominator. That makes at least all the $(x_{2^k},y_{2^k})$ mutally different.

So pick as many of those $(x_{2^k},y_{2^k})$ as you want, find the common denominator of all the coordinates and distances and multiply the coordinates with it. That gives you integer coordinates and distances, as requested.