Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?


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?

share|improve this question
add comment

2 Answers

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}.$$

share|improve this answer
The first one seems more asymptotic than my query, the second though does seem to cover it... Although, and maybe I'm being a bit thick here, I can't seem to get his bound for the width of a lattice 10-gon: he says "The reader will have no diffculty finding a convex lattice polygon with n vertices having lattice width exactly $\lciel n/2 \rceil- 1$". I am having difficulty. Is it possible he saw n=1-8 attaining his lower bound and assumed the rest? I am probably just being a pillock- can you fit a convex 10-gon in a lattice width of 4? –  Tom Boardman Jun 11 '10 at 14:17
I mean, you can do it easily if you don't need general position- but he seems to use g.p. in his definition of convex "since every lattice line contains at most 2 vertices of P...". –  Tom Boardman Jun 11 '10 at 14:23
Oh, in that case I believe he is only considering width in one direction, which shouldn't be of much interest to you, since you are considering points in convex position in a confined area (square). I was referring to the section "maximal polytopes in K", being of interest, but I figured the new article I added above is a much better reference. –  Gjergji Zaimi Jun 11 '10 at 14:38
+1 I came here to point to Barany's work on exactly this problem (I saw him speak on it at IPAM last fall) but I see you've already done so. –  David Eppstein Jun 11 '10 at 15:42
Bah... that last result looks like the business but I can't see it without forking out $30. Damn those journal subscription fees... it really bugs me when I don't get to see the solution- it's like watching half of a movie- +1 though. Ps. I think your index might be upside-down- my bound isn't great- but it's nowhere near as bad as o(n^2) vs o(n^2/3) ! –  Tom Boardman Jun 11 '10 at 18:51
show 1 more comment

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.]

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.