# 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? – Yoav Kallus Nov 12 '20 at 13:27
• @YoavKallus: This would then suggest the bound of $2^d$ for $\mathbb{Z}^d$. – Joseph O'Rourke Nov 12 '20 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 '20 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. – Joseph O'Rourke Nov 12 '20 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. – Richard Stanley Nov 13 '20 at 0:23

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! – LSpice Jan 27 at 22:16