Kvant Math Problem 475
Assume that an equilateral triangle has all three vertices at lattice points.
Verified: yes
Verdicts: PASS + PASS
Solve time: 30m48s
Source on kvant.digital
Problem
- Prove that an equilateral triangle cannot be drawn on squared paper in such a way that its vertices lie exactly at lattice points (the vertices of the squares).
- Prove that on squared paper with side length 1, for any $\eps\gt0$, it is possible to draw an equilateral triangle whose vertices are at distances less than $\eps$ from three distinct lattice points.
- Is it true that for any polygon $M$ and any $\eps\gt0$, one can draw on squared paper a polygon similar to $M$ such that all its vertices are at distances less than $\eps$ from distinct lattice points?
V. Kalinnikov
Solution
1. Nonexistence of a lattice equilateral triangle
Assume that an equilateral triangle has all three vertices at lattice points.
After a translation, place one vertex at the origin and another at
$$A=(a,b), \qquad a,b\in\mathbb Z,$$
with $(a,b)\ne(0,0)$.
The third vertex is obtained by rotating $A$ through $\pm60^\circ$. Its coordinates are
$$\left(\frac a2-\frac{\sqrt3,b}{2}, \frac{\sqrt3,a}{2}+\frac b2\right)$$
or
$$\left(\frac a2+\frac{\sqrt3,b}{2}, -\frac{\sqrt3,a}{2}+\frac b2\right).$$
Suppose the first point has lattice coordinates. Then
$$\frac a2-\frac{\sqrt3,b}{2}\in\mathbb Z.$$
Hence
$$\sqrt3,b=a-2k$$
for some integer $k$, so $\sqrt3,b\in\mathbb Q$. Since $\sqrt3$ is irrational and $b\in\mathbb Z$, this implies $b=0$.
Substituting $b=0$ into the second coordinate gives
$$\frac{\sqrt3,a}{2}\in\mathbb Z.$$
Thus $\sqrt3,a\in\mathbb Q$, and again the irrationality of $\sqrt3$ yields $a=0$.
This contradicts $(a,b)\ne(0,0)$.
The same argument applies to the second possible position of the third vertex. Hence an equilateral triangle cannot have all three vertices at lattice points.
2. Approximate lattice equilateral triangles
Fix $\varepsilon>0$.
Continued fractions provide infinitely many rational approximations $n/m$ to $\sqrt3$ such that
$$\left|\sqrt3-\frac nm\right|<\frac1{m^2}.$$
Choose such a pair $(m,n)$ with $m>0$, and put
$$u=(m,n).$$
Let $\varphi$ be the direction angle of $u$. Since
$$\tan\varphi=\frac nm,$$
and $\arctan$ has nonzero derivative at $\sqrt3$,
$$\delta:=\left|\varphi-\frac{\pi}{3}\right| =O!\left(\frac1{m^2}\right).$$
Let $v$ be the vector obtained from $u$ by rotation through $60^\circ$. Then the triangle with vertices
$$0,\quad u,\quad v$$
is equilateral.
Define
$$w=(-m,n).$$
The vector $w$ is a lattice vector and
$$|w|=|u|=:L.$$
If $\varphi=\pi/3$, then the direction of $u$ is $60^\circ$, the direction of $v$ is $120^\circ$, and $w$ also has direction $120^\circ$. Thus $v=w$ in that case.
For general $\varphi$, the directions of $v$ and $w$ differ by $O(\delta)$. Let this angular difference be $\theta$. Since both vectors have length $L$,
$$|v-w| = 2L\sin\frac{\theta}{2} = O(L\delta).$$
Furthermore,
$$L=\sqrt{m^2+n^2}\asymp m,$$
hence
$$|v-w| = O!\left(m\cdot\frac1{m^2}\right) = O!\left(\frac1m\right) \to0.$$
Choose $m$ large enough that
$$|v-w|<\varepsilon.$$
The points $0$ and $u$ are lattice points, while $v$ lies within distance $\varepsilon$ of the lattice point $w$.
Since $m>0$, the lattice points
$$0,\qquad (m,n),\qquad (-m,n)$$
are distinct.
Thus for every $\varepsilon>0$ there exists an equilateral triangle whose vertices are within distance $\varepsilon$ of three distinct lattice points.
3. Arbitrary polygons
The answer is yes.
Let the vertices of the polygon $M$ be
$$P_1,P_2,\dots,P_k.$$
Translate the polygon so that
$$P_1=(0,0).$$
Write
$$P_i=(x_i,y_i), \qquad i=2,\dots,k.$$
Consider the vector
$$X=(x_2,y_2,\dots,x_k,y_k)\in\mathbb R^{2k-2}.$$
Kronecker's approximation theorem implies that the set
$${,N X \pmod 1 : N\in\mathbb N,}$$
is dense in the torus determined by the integer relations among the coordinates of $X$. In particular, the point $0$ belongs to the closure of this set if and only if every integer relation
$$m_1x_2+m_2y_2+\cdots+m_{2k-3}x_k+m_{2k-2}y_k\in\mathbb Z$$
actually has integer value already forced by the coordinates themselves. The theorem yields the following consequence: for every $\eta>0$ there exist infinitely many integers $N$ such that each coordinate of $NX$ is within $\eta$ of an integer.
Indeed, let
$$L={,m\in\mathbb Z^{2k-2}:m\cdot X\in\mathbb Z,}.$$
Kronecker's theorem states that a point $y$ can be approximated modulo $1$ by multiples of $X$ if and only if
$$m\cdot X\in\mathbb Z \quad\Longrightarrow\quad m\cdot y\in\mathbb Z$$
for every $m\in\mathbb Z^{2k-2}$.
Taking $y=0$, the condition is automatically satisfied, because $m\cdot0=0$ is always an integer. Hence $0$ lies in the closure of
$${,N X \pmod 1:N\in\mathbb N,}.$$
Therefore, for every $\eta>0$, there exists an integer $N$ such that every coordinate of $NX$ is within $\eta$ of an integer.
Choose
$$\eta=\frac{\varepsilon}{\sqrt2}.$$
For each vertex $P_i$, choose a lattice point $L_i$ whose coordinates are the nearest integers to those of $NP_i$. Then
$$|NP_i-L_i|<\varepsilon.$$
The polygon with vertices
$$NP_1,\dots,NP_k$$
is similar to the original polygon, since it is obtained by scaling $M$ by the factor $N$.
It remains to show that the lattice points $L_i$ are distinct.
Let
$$d=\min_{i\ne j}|P_i-P_j|.$$
Since the polygon has finitely many distinct vertices,
$$d>0.$$
Because $0$ is an accumulation point of the sequence ${NX\pmod1}$, there are infinitely many integers $N$ satisfying the approximation condition. Choose such an $N$ with
$$Nd>2\varepsilon.$$
Suppose that $L_i=L_j$ for some $i\ne j$. Then
$$|NP_i-NP_j| \le |NP_i-L_i|+|NP_j-L_j| < 2\varepsilon.$$
On the other hand,
$$|NP_i-NP_j| = N|P_i-P_j| \ge Nd > 2\varepsilon,$$
which is impossible.
Hence the lattice points $L_1,\dots,L_k$ are distinct.
Thus for every polygon $M$ and every $\varepsilon>0$ there exists a polygon similar to $M$ whose vertices are within distance $\varepsilon$ of distinct lattice points. ∎