Does the analogue of Moser's circle problem have a known solution in higher dimensions?

Briefly, the original question asks, "Given $k$ points on a circle, if each point is connected to every other by a chord, what is the maximum number of regions $R$ these points divide the circle into?" The answer has a neat little formula and a straightforward combinatorial interpretation:

$$R= {k\choose 0} + {k \choose 2} + {k \choose 4}$$ where ${k\choose 0}=1$ is the number of original regions, ${k\choose 2}$ is the number of lines, and ${k\choose 4}$ is the number of intersections of lines (this assumes the arrangement of points is not degenerate, so to speak).

The natural generalization is: Given $k$ points on an $n$-sphere, each subset of cardinality $n+1$ determines a hyperplane in $(n+1)$-space. What is the maximum number of regions these hyperplanes divide the sphere into?

In my estimation this is a much harder problem. One complication has to do with the special nature of a maximal solution. In the 1-sphere case, the arrangements of points which produce non-maximal regions have measure zero in the space of all arrangements (this can be made precise). In higher dimensions the situation is more or less reversed. Maximal arrangements, while probably not constituting a null set, are very unlikely. An arbitrary hyperplane arrangement will divide up the space into a predictable number of regions, but many of these regions don't intersect with the sphere at all, and the question of which do and which don't is sensitive to the specific constellation of points.

Here's hoping someone might have some insight.

  • $\begingroup$ I think the key search term is "hyperplane arrangements". $\endgroup$ – Gerry Myerson Mar 10 '15 at 10:05
  • $\begingroup$ I originally read this pdf on hyperplane arrangements. Granted it was several years ago, and I should revisit it, but I couldn't find a way to adapt the ideas to the particular constraints of this problem. $\endgroup$ – Eli Johnson Mar 10 '15 at 10:41
  • 1
    $\begingroup$ Another approach is to see if you can't calculate the answers for small $k$ (for, say, $n=3$) and then look it up in the Online Encyclopedia of Integer Sequences. $\endgroup$ – Gerry Myerson Mar 10 '15 at 11:28
  • $\begingroup$ @GerryMyerson I'll look into that. I am convinced that anything below $k = (n+1)^2$ does not reach the "base case" for a formula, because this value of $k$ allows you to have $n+1$ hyperplanes that are independent with respect to choice of points, the intersection of which is a point, which is used in the calculation of regions. $\endgroup$ – Eli Johnson Mar 10 '15 at 18:23
  • $\begingroup$ By the way, in this vein I wrote a simulation in Mathematica for when $n=2$, to scatter $k$ points randomly on the 2-sphere and calculate the number of resulting regions. With $k$ as low as 9 you get ${9\choose 3} = 84$ hyperplanes, ${84\choose 2}= 3486$ pairs of planes intersecting in lines, and ${84 \choose 3} = 95284$ points formed by the intersection of 3 planes. This gives a rough upper bound of 98855 when n=2, k=9. Some further small refinements can be made considering these planes are never in true "general position" (e.g. groups of 7 share common chords). $\endgroup$ – Eli Johnson Mar 10 '15 at 18:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.