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

1 Answer 1

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, 2021 at 22:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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