5
$\begingroup$

Let $f(k)$ denote the minimum length of a convex lattice polygon containing exactly $k$ lattice points (including lattice points on the boundary).

It is not too hard to show that $k = \frac{1}{4\pi} f(k)^2+o(f(k)^2)$ as $k \to \infty$.

Is it known whether in fact $k = \frac{1}{4\pi} f(k)^2+o(f(k))$? I naively expect this to be the case, but can not prove it [nor am I sure of it's validity]. Any help would be appreciated!

$\endgroup$
6
  • $\begingroup$ You can take convex hull of lattice points inside a circle. See mathworld.wolfram.com/GausssCircleProblem.html for the error term. $\endgroup$ Mar 28, 2016 at 5:01
  • $\begingroup$ It seems strange to express the asymptotics that way instead of something like $f(k) = O(\sqrt{k})$. $\endgroup$ Mar 28, 2016 at 6:24
  • $\begingroup$ Can't you just use the standard isoperimetric theorem (that the min perimeter figure for a given area is a disk) together with the observation that #lattice points $=$ area $\pm O($perimeter$)$? $\endgroup$ Mar 28, 2016 at 6:37
  • $\begingroup$ @AlexeyUstinov I had considered that, but does that really give the bound I want? That gives a nice upper bound on $f(k)$, but it seems you need a reasonable lower bound. How do you know, for example, that the convex hull of the set of lattice points in the circle of radius r doesn't have perimeter, say, $2\pi r - r^{2/3}$? $\endgroup$
    – Bent spoon
    Mar 28, 2016 at 21:14
  • $\begingroup$ @DavidEppstein I would think you could maybe get something like O(f(k)) that way, but o(f(k))? Did you have something specific in mind? Is there something I'm missing? $\endgroup$
    – Bent spoon
    Mar 28, 2016 at 21:21

2 Answers 2

5
$\begingroup$

This may be a delicate problem. I have a few comments but no real progress to a solution.

It might be worth trying to figure out what polygon(s) give $f(k).$

I think it is not the convex hull of the lattice points in circles centered at the origin (the Gauss circle problem.) More promising is circles centered at $(1/2,1/2).$ The number of points if the diameter is ${\sqrt{4n^2-4\sqrt{2}n+2}}$ is the series $4,12,24,44,68,\cdots$ obtained by quadrupling the Number of nonnegative solutions to $x^2 + y^2 \le n^2$.

For example a circle of radius $5$ centered at the origin seems promising since it has $12$ points on the boundary. It has $49$ points in all and the boundary has length $8\sqrt{10}+4\sqrt{2} \approx30.955$ But a $7 \times 7$ square gives length $28.$ The optimum may be $13+5\sqrt{2}+3\sqrt{5}\approx 23.779$ coming from columns of lengths $4,6,8,8,8,6,6,3.$ In other words, a $6 \times 6$ square with $4,3,3$ and $3$ additional points parallel to the sides.

It seem plausible that the optimum is the convex hull of the points in some circle but getting the right one may not be easy. Perhaps for larger numbers the jumps are not as extreme.

I do suspect that $\log_{f(k)}\left(k - \frac{1}{4\pi} f(k)^2\right)$ may oscillate. But that is just a guess.

$\endgroup$
1
$\begingroup$

It is not clear about $o(f(k))$, but $O(f(k))$ is easy.

We know that $k=\pi r^2+O(r)$. Vertices of convex hull are not very far from the circle, they lay outside the circle of radius $r-\sqrt 2$. Sides of convex lattice polygon are not very far from the circle as well: if the distance from midpoint $A$ of some side to the circle is greater than $2$ then you must have a lattice points inside a circle with center $A$ and radius $2$. So convex lattice polygon is outside the circle of radius $r-2$, $f(k)=2\pi r+O(1)$, $r=\frac{f(k)}{2\pi}+O(1)$ and $k= f(k)^2/(4\pi)+O(f(k))$.

From asymptotic formula $k=\pi r^2+O(r^{2/3})$ follows that your problem is equivalent to the formula $f(k)=2\pi r+o(1)$.

$\endgroup$
7
  • $\begingroup$ Thanks --- that's helpful. Do you think it actually is o(f(k))? Any opinion? $\endgroup$
    – Bent spoon
    Mar 29, 2016 at 5:24
  • $\begingroup$ @Bent spoon I think that it is $o(f(k))$, and I also think that question about asymptotic formula for $f(k)$ is more natural than your original question. $\endgroup$ Mar 29, 2016 at 5:40
  • $\begingroup$ Sorry, what circle are you talking about? $\endgroup$ Mar 29, 2016 at 21:05
  • $\begingroup$ @Fedor Petrov Any circle of radius $r$. $\endgroup$ Mar 30, 2016 at 0:14
  • $\begingroup$ And how is this any circle connected to minimal polygon? $\endgroup$ Mar 30, 2016 at 5:51

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.