Triangles capturing many lattice points

Nicholas F. Marshall, Stefan Steinerberger

Published 2017-06-13Version 1

We study a combinatorial problem that recently arose in the context of shape optimization: among all triangles with vertices in $(0,0), (x,0), (0,y)$ and fixed area, which one encloses the most lattice points $\mathbb{N}_{>0}^2$? Moreover, does its shape necessarily converge to the isosceles triangle $(x=y)$ as the area becomes large? Laugesen & Liu suggested that, in contrast to similar problems, there might not be a limiting shape. We prove this statement and show that there exists an infinite set of slopes $y/x$ such that any associated triangle captures more lattice points than any other fixed triangle for infinitely many (and arbitrarily large) areas; this set of slopes is a fractal subset of $[1/3, 3]$ and has Minkowski dimension at most $3/4$.