# Moser circle problem: maximum case for N?

Moser's circle problem sets the upper bound of regions the chords connecting n points can divide a circle into at $${n \choose 4} + {n \choose 2} + 1$$. But how can we construct a set of points that gets there?

There must be infinitely many. For any set of n points, there are at most $$n{n-1 \choose 4}$$ points on the circle that might cause an intersection, e.g. you could pick any two intersecting chords and a point in the set, and the line between them would intersect the circle in one more place.

So this exists. But how to construct a set of points that provably works?

My guess is that if we have a list of the prime numbers $$p_1=2, p_2=3, p_3=5$$ etc. and a unit circle, we could have a set of points $$x_n=(cos(\pi/p_n), sin(\pi/p_n))$$. That seems like it would work, but I'm not sure how to prove it. And there might be something simpler, too. Any suggestions?

• Wouldn't the chords of every set of $n$ points on a circle divide the interior into $\binom{n}4+\binom{n}2+1$ regions? Can you give a single example of $n$ points which product fewer regions? – Mike Earnest Jan 11 at 18:28
• @Mike Earnest If you have 6 points a1-a6 that form, in order, a regular hexagon, then you would not have 31 regions, because at the very least, a1a4 and a2a5 and a3a6 would all intersect in one point. – aschultz Jan 12 at 5:08
• I see now, that was a brain fart on my part. – Mike Earnest Jan 12 at 5:11

The solution I found uses induction on N. Let's assume we have a circle with N points that maximize the number of regions. Then look at the arc between, say, $$x_n$$ and $$x_n-1$$, and pick a point $$x_j$$ where $$0. We will find a point on the arc that satisfies our condition.
There will be at most $${n \choose 4}$$ rays from j through to an intersection of two points that go through the arc $$x_n x_{n-1}$$ but don't touch $$x_n$$ or $$x_{n-1}$$, since there are at most $${n \choose 4}$$ intersections of chords. Let's say there are y such rays, and let's call their intersections $$z_0$$ to $$z_{y-1}$$, with $$z_0$$ being closest to $$x_{n-1}$$.
If y=0 it's easy. Any point on the arc works. If y=1 then it's also easy. We can just take the midpoint of the arc $$x_n z_0$$ or $$x_n z_1$$. In fact if y > 1 we can always take the midpoint of $$x_{n-1} z_0$$ or $$x_n z_{y-1}$$.
This is one construction. I suppose if we want the points spread out we could choose the midpoint of the arc between $$z_{y-1/2}$$ and $$z_{y+1/2}$$.
I also had an idea for having the points $$j_n= (\frac{2\sqrt{p_n}}{p_n + 1}, \frac{p_n-1}{p_n+1})$$, because each intersection of $$j_a j_b$$ and $$j_c j_d$$ will have $$\sqrt{a}$$, $$\sqrt{b}$$, $$\sqrt{c}$$, and $$\sqrt{d}$$ (or some product) terms in the x-coordinate + y-coordinate, and this sum is unique to any point pair, because if it were not, we would contradict this finding. Again, if we wanted to place things semi-evenly, we could let $$k_n$$ be $$(\cos{n\phi},\sin{n\phi})$$ where $$j_n = (\cos\phi,\sin\phi)$$. But this requires a lot of algebra.