3
$\begingroup$

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

$\endgroup$
5
  • 12
    $\begingroup$ 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? $\endgroup$ – Yoav Kallus Nov 12 '20 at 13:27
  • 3
    $\begingroup$ @YoavKallus: This would then suggest the bound of $2^d$ for $\mathbb{Z}^d$. $\endgroup$ – Joseph O'Rourke Nov 12 '20 at 13:30
  • 4
    $\begingroup$ 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})$). $\endgroup$ – YCor Nov 12 '20 at 13:30
  • $\begingroup$ @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. $\endgroup$ – Joseph O'Rourke Nov 12 '20 at 14:10
  • 2
    $\begingroup$ The problem for $\mathbb{Z}^3$ is Problem A1 on the 32nd Putnam exam (1971). See prase.cz/kalva/putnam/putn71.html. $\endgroup$ – Richard Stanley Nov 13 '20 at 0:23
7
$\begingroup$

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

$\endgroup$
1
  • 5
    $\begingroup$ Since this is your own answer, CW is surely not obligatory! $\endgroup$ – LSpice Jan 27 at 22:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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