Let $T$ be a lattice triangle in $\Bbb R^2$ (i.e. the convex hull of three noncolinear points in $\Bbb Z^2$), and assume it has at least one interior lattice point. Is it always possible to find a point $p\in \operatorname{interior}(T)\cap \Bbb Z^2$ satisfying the following condition:

(*) $\operatorname{conv}(p,v)\cap \Bbb Z^2 = \{p,v\}$ for every vertex $v\in T$, where $\operatorname{conv}$ is convex hull.

For example: In this picture:


$p=D$ works, whereas in this picture:

enter image description here

$p=D$ does not work because the line segment $DC$ passes through $E$.

Edit: In light of fedja's counterexample (the triangle with vertices $(0,0)$, $(3,2)$, and $(1,3)$, and at their suggestion, I'm modifying the question to ask if (*) holds when $T$ contains "sufficiently many" points in the interior.

  • $\begingroup$ It looks to me like your definition of $T$ is a bit ambiguous, as it first refers to the entire triangle (with interior), but later (possibly) refers to only the three vertices of it. $\endgroup$ – Marcus M Dec 12 '18 at 21:15
  • $\begingroup$ @MarcusM I'm not sure what you mean. $\endgroup$ – Avi Steiner Dec 12 '18 at 21:16
  • $\begingroup$ When you say $p \in T \cap \mathbb{Z}^2$, it looks like you mean for $T$ to include the interior of the triangle; however, your condition for $p$ that you seek is more ambiguous. It says $\text{conv}(p,v) = \{p,v\}$ for all $v \in T$, however in your image you only tested in for $v$ being the extreme points (i.e. the three vertices) of the triangle. Is that the condition that you seek? $\endgroup$ – Marcus M Dec 12 '18 at 21:18
  • 3
    $\begingroup$ How about (0,0), (3,2),(1,3) for the vertices of $T$? $\endgroup$ – fedja Dec 13 '18 at 0:09
  • 1
    $\begingroup$ There are general visibility results by Adikhari which may be a start on this. Essentially, if an integer interval is large enough, it contains an integer coprime to a given integer N, and this has implications to your problem. Search for work of Granville in this area too. Gerhard "Will Help Look For Forest" Paseman, 2018.12.12. $\endgroup$ – Gerhard Paseman Dec 13 '18 at 2:06

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.