Minimum length of a convex lattice polygon containing k lattice points? 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!
 A: 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.
A: 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)$.
