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

Improve this question
$\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
    Commented Nov 12, 2020 at 13:27
  • 3
    $\begingroup$ @YoavKallus: This would then suggest the bound of $2^d$ for $\mathbb{Z}^d$. $\endgroup$
    – Joseph O'Rourke
    Commented Nov 12, 2020 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
    Commented Nov 12, 2020 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
    Commented Nov 12, 2020 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
    Commented Nov 13, 2020 at 0:23

1 Answer 1

Reset to default
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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .