$n$ lines cannot divide a plane region into $x$ regions, finding $x$ for $n$

I noticed that $3$ lines cannot divide the plane into $5$ regions (they can divide it into $2,3,4,6$ and $7$ regions). I have a line of reasoning for it, but it seems rather ad-hoc. I also noticed that there are no "gaps" in the number of divisions that can be made with $n=4$, i.e we can divide a plane into $\{2,3,\cdots,11\}$ using $4$ lines.

Is there anyway to know that if there are $n$ lines with $x$ being the possible number of divisions $\{ 2,\ldots, x,\ldots x_{max} \}$ where $x_{max}$ is the maximum number of divisions of the plane with $n$ lines, then what are the $x \lt x_{max}$ which are not possible?

For e.g, $n=3$, $x_{max}=7$, $x=5$ is not possible.

Solution 1:

See if you can find the paper, I N Schnurnikov, Into how many regions do $n$ lines divide the plane if at most $n-k$ of them are recurrent? The abstract says, inter alia,

Thus, a new proof of N. Martinov’s theorem is obtained. This theorem determines all pairs of integers $(n, f)$ such that there is an arrangement of $n$ lines dividing the projective plane into $f$ regions.

Or, if you read Bulgarian, look for Nikola Martinov, Solution of a Federov-Grünbaum problem, Annuaire Univ. Sofia Fac. Math. Inform. 87 (1993), no. 1-2, 73–85 (1999), MR1745340 (2000k:52020).

Wait a minute - it's also in English: Nicola Martinov, Classification of arrangements by the number of their cells, Discrete Comput. Geom. 9 (1993), no. 1, 39–46, MR1184692 (93g:52008).

EDIT 17 May: See also Oleg A Ivanov, On the number of regions into which $n$ straight lines divide the plane, Amer Math Monthly 117 (Dec. 2010) 881-888. Curiously, this paper does not reference Martinov's work.

Solution 2:

I don't have access to any papers, unfortunately, but I think I've found a handwavy proof sketch that shows there are no gaps other than $n = 3, x = 5$. Criticism is welcomed; I'm not sure how to make this argument rigorous, and I'm also curious if there's an article that already uses these constructions.

Suppose $n - 1$ lines can divide the plane into 2 through $\frac{(n-1)n}{2} + 1$ regions. For sufficiently large $n$, we will show that $n$ lines can divide the plane into $\frac{n(n-1)}{2} + 2$ through $\frac{n(n-1)}{2} + n + 1 = \frac{n(n+1)}{2} + 1$ regions.

Consider an arrangement of $n$ lines that splits the plane into $\frac{n(n+1)}{2} + 1$ regions, such that, for simplicity, lines are paired into groups of two, where each line in the $k$th pair has a root at $k$ and the negative slope of its partner.

If $n$ is odd, there will be one line left over which can't be paired; put this line horizontally underneath the roots of the pairs (e.g. $y = -1$). If $n$ is even, take the last pair and put one line horizontally as described, and the other vertically at $x = 0$.

We can hand-wave to "pull down" pairs one-by-one so their intersection rests on the horizontal line, subtracting one region for each pair "pulled down." This ends up removing $\frac{n-1}{2}$ regions for odd $n$, and $\frac{n}{2} - 1$ regions for even $n$.

Then we can go through each pair of lines and adjust the line with negative slope to have the same slope as the next pair's positively sloped line, shaving one region off each time (and removing the same number of regions as the previous operation).

So these operations will get us to $\frac{(n-1)n}{2} + 2$ for odd $n$, and $\frac{(n-1)n}{2} + 3$ for even $n$. To get to $\frac{(n-1)n}{2} + 2$ for even $n$, we take the last pair's positive line and put it parallel to the first two vertical lines (subtracting two regions), then nudge the first pair slightly above the horizontal line (adding back one).

Now we have to consider when such operations fail, for both odd and even cases. We certainly can't "pull down" when $n \le 2$. For $n = 3$, we have just one pair above the horizontal line, so we can't adjust slopes as suggested, giving us a gap at $x = 5$. For $n = 4$, we have only one pair, and we can't make up the gap at $\frac{(n-1)n}{2} + 2$ — but luckily, not only can we cover up the 8-region gap using 3 parallel lines and one non-parallel one, but 4 parallel lines cover the 5-region gap introduced when $n = 3$.

So we can use these techniques to complete the induction process for $n \ge 5$.