# There are at most four mutually visible lattice points—?

Say that two lattice points $$a$$ and $$b$$ of $$\mathbb{Z}^2$$ are visible to one another if the line segment $$ab$$ contains no other lattice points. While exploring lattice polygons all of whose vertices are visible to one another, I noticed that it seems impossible to have more than $$4$$ mutually visible lattice points.

Q1. Prove that there is no set of $$\ge 5$$ distinct points of $$\mathbb{Z}^2$$ that are mutually visible to one another, or construct examples.

I suspect this is elementary, but I'm not seeing a proof or a refutation.

Q2. What is the higher-dimensional analog? What is the largest number $$f(d)$$ of mutually visible points of $$\mathbb{Z}^d$$ ?

• Is it simply that if a = b (mod 2) then a is not visible to b, and there are only 4 options for coordinates in Z^2 mod 2? Nov 12, 2020 at 13:27
• @YoavKallus: This would then suggest the bound of $2^d$ for $\mathbb{Z}^d$. Nov 12, 2020 at 13:30
• Indeed $f(d)=2^d$ is then immediate with this argument (achieved by $\{0,1\}^d$ as well as its images by elements of $\mathrm{GL}_d(\mathbf{Z})$).
– YCor
Nov 12, 2020 at 13:30
• @YoavKallus: Very nice observation! If $a \equiv b \pmod 2$ then $a-b \equiv 0 \pmod 2$ and $a-b$ has two even coordinates, and so the midpoint of $ab$ is a lattice point. Nov 12, 2020 at 14:10
• The problem for $\mathbb{Z}^3$ is Problem A1 on the 32nd Putnam exam (1971). See prase.cz/kalva/putnam/putn71.html. Nov 13, 2020 at 0:23

## 1 Answer

(Inspired by a meta thread on answers given in comments, I am recapping the answer given in the comments (1 2 3) as a CW answer.)

The largest number of mutually visible points in $$\mathbb{Z}^d$$ is $$2^d$$. This is achieved, for example, by the points $$\lbrace 0, 1\rbrace^d$$. Since there are $$2^d$$ orbits of $$(2\mathbb{Z})^d$$ in $$\mathbb{Z}^d$$ and two points in the same orbit are not mutually visble (the midpoint of the segment connecting them is a lattice point), no more than $$2^d$$ points can be pairwise mutually visible.

• Since this is your own answer, CW is surely not obligatory! Jan 27, 2021 at 22:16