Making 'circles' on a lattice/ Making distinct fractions from partitions of a number

Question

First formulation: discrete geometry

Pick your favourite 2D square lattice (I'm sure we all have one...) and try to place n points 'in a circle' (that is: in general position [no 3 should be colinear] and forming the vertices of a convex polygon). Easy-peasy (assuming your favourite lattice is infinite- I know mine is). But now make your lattice smaller- finite even- say, $K \times K$- can you still do it? What is K is smaller? Bigger? Clearly the answer depends on n, so we ask:

What is the smallest $K=K(n)$ such that this can be done?

Motivation?

This little problem- way out of my comfort zone in terms of field- was sort of inspired by this question. It initially looked like an interesting problem but, sadly, turned out to be rather trivial- putting points in a circle spelled trouble, it seemed, and I idly suggested a finite lattice to stop it happening- idle suggestion turned to idle speculation and I began to wonder how small the lattice had to be to stop the circle forming- beyond that, intrigue is the only reason why I am pursuing it.

So far my progress has been scant, but I have found a rather interesting reformulation: by focusing on the most densely populated 'quadrant' of the lattice and observing that the gradients of the edges within it must all differ. Modulo some suitable considerations of n mod 4 we can get-

Reformulation: number theory

Given $\hat{n}$ what is the smallest $\hat{K}$ such that we may find $\hat{n}$ distinct fractions $\frac{p_1}{q_1},....\frac{p_n}{q_n}$ with $\Sigma_i q_i \leq \Sigma_i p_i = \hat{K}$?

Here $\hat{n}$ would be the number of points in the quadrant $\hat{K} \times \hat{K}$ the smallest size of that quadrant.

If we set $\hat{n}=\lceil \frac{n}{4} \rceil$, assume $\hat{K}=\frac{K}{2}$ and let the $p_i$, $q_i$ be the first $\hat{n}$ natural numbers we get a [really crappy] upper bound of $K \leq \lceil \frac{n}{4} \rceil (\lceil \frac{n}{4} \rceil +1)$- this fails to be sharp by the time n=5 for obvious reasons- 1) There has been no real consideration of the mod 4 behaviour and 2) By no means is this the most efficient way to make differing fractions.

Fixing 1) seems pretty easy (we can look at 2 different quadrants), but I didn't want to clog up the question with numerics when 2) is the real toughie. As mentioned above, I am neither a discrete geometer nor a number theorist, so this may unwind to be as trivial as the question that inspired it- still, to me it seems intriguing- and I am sufficiently invested to be hankering for an answer.

Edit: Gjergji's answer seems to be pretty great as a problem posed for polytopes, but I haven't accepted it yet because I am curious- can the number theory formulation do better? Is there a sharper result in that context?

Answer 1

I believe your question (and many other variations) are answered here. Also see this survey by I. Barany about extremal problems for convex lattice polytopes.

Actually the problem for the convex polygon inside the square was considered earlier than that. See here for an article that seems to be written more in the lines of your question. The result is that $$K(n)\sim 2\pi \left(\frac{n}{12}\right)^{2/3}.$$

Answer 2

Just thinking about prime denominators: you should be able to take K to be n to the power 2/3, up to some logarithmic stuff. This is just greedily taking a bunch of primes in some interval. There is a little to be gained by using the whole Farey series.

[The condition on the numerators looks slightly troublesome. Just taking the p/q where q is fixed and p coprime to q is going to have the sum of p's around half the sums of q's, on average (or a bit less ...). But this can be worked round: take the "second half" of the p/q with p at least q/2, with the 1 + p/q for the "first half" where p is less than q/2.]