6.2: Topology- How many regions

The bond angle in methane (Section 6.1) can be calculated directly with analytic geometry (Problem 6.3), so reasoning by analogy does not show its full power. Therefore, try the following problem.

Question

Into how many regions do five planes divide space?

This formulation permits degenerate arrangements such as five parallel planes, four planes meeting at a point, or three planes meeting at a line. To eliminate these and other degeneracies, let’s place and orient the planes randomly, thereby maximizing the number of regions. The problem is then to find the maximum number of regions produced by five planes.

Five planes are hard to imagine, but the method of easy cases using fewer planes might produce a pattern that generalizes to five planes. The easiest case is zero planes: Space remains whole so \(R(0) = 1\) (where R(n) denotes the number of regions produced by n planes). The first plane divides space into two halves, giving \(R(1) = 2\). To add the second plane, imagine slicing an orange twice to produce four wedges: \(R(2) = 4\).

Question

What pattern(s) appear in the data?

A reasonable conjecture is that \(R(n) = 2^{n}\). To test it, try the case \(n = 3\) by slicing the orange a third time and cutting each of the four pieces into two smaller pieces; thus, \(R(3)\) is indeed 8. Perhaps the pattern continues with \(R(4) = 16\) and \(R(5) = 32\). In the following table for \(R(n)\), these two extrapolations are marked in gray to distinguish them from the verified entries.

n	0	1	2	3	4	5
r	1	2	4	8	16	32

Question

How can the \(R(n) = 2^{n}\) conjecture be tested further?

A direct test by counting regions is difficult because the regions are hard to visualize in three dimensions. An analogous two-dimensional problem would be easier to solve, and its solution may help test the three- dimensional conjecture. A two-dimensional space is partitioned by lines, so the analogous question is the following:

Question

What is the maximum number of regions into which n lines divide the plane?

The method of easy cases might suggest a pattern. If the pattern is \(2^{n}\), then the \(R(n) = 2^{n}\) conjecture is likely to apply in three dimensions.

Question

What happens in a few easy cases?

Zero lines leave the plane whole, giving \(R(0) = 1\). The next three cases are as follows (although see Problem 6.5):

Multiple problems

Problem 6.5 Three lines again

The \(R(3) = 7\) illustration showed three lines producing seven regions. Here is another example with three lines, also in a random arrangement, but it seems to produce only six regions. Where, if anywhere, is the seventh region? Or is \(R(3) = 6\)?

Problem 6.6 Convexity

Must all the regions created by the lines be convex? (A region is convex if and only if a line segment connecting any two points inside the region lies entirely inside the region.) What about the three-dimensional regions created by placing planes in space?

Until \(R(3)\) turned out to be 7, the conjecture \(R(n) = 2^{n}\) looked sound. However, before discarding such a simple conjecture, draw a fourth line and carefully count the regions. Four lines make only 11 regions rather than the predicted 16, so the \(2^{n}\) conjecture is dead.

A new conjecture might arise from seeing the two-dimensional data \(R_{2}(n)\) alongside the three-dimensional data \(R_{3}(n)\).

n	0	1	2	3	4
\(R_{2}\)	1	2	4	7	11
\(R_{3}\)	1	2	4	8

In this table, several entries combine to make nearby entries. For example, \(R_{2}(1)\) and \(R_{3}(1)\) the two entries in the \(n = 1\) column sum to \(R_{2}(2)\) or \(R_{3}(2)\). These two entries in turn sum to the \(R_{3}(3)\) entry. But the table has many small numbers with many ways to combine them; discarding the coincidences requires gathering further data and the simplest data source is the analogous one-dimensional problem.

Question

What is the maximum number of segments into which n points divide a line?

A tempting answer is that n points make n segments. However, an easy case that one point produces two segments reduces the temptation. Rather, \(n\) points make \(n + 1\) segments. That result generates the \(R_{1}\) row in the following table.

n	0	1	2	3	4	5	n
\(R_{1}\)	1	2	3	4	5	6	n + 1
\(R_{2}\)	1	2	4	7	11
\(R_{3}\)	1	2	4	8

Question

What patterns are in these data?

The 2n conjecture survives partially. In the \(R_{1}\) row, it fails starting at \(n = 2\). In the \(R_{2}\) row, it fails starting at \(n = 3\). Thus in the \(R_{3}\) row,it probably fails starting at \(n = 4\), making the conjectures\(R_{3}\)(4) = 16 and \(R_{3}(5) = 32\) improbable. My personal estimate is that, before seeing these failures, the probability of the \(R_{3}(4) = 16\) conjecture was 0.5; but now it falls to at most 0.01. (For more on estimating and updating the probabilities of conjectures, see the important works on plausible reasoning by Corfield [11], Jaynes [21], and Polya [36].)

In better news, the apparent coincidences contain a robust pattern:

Question

If the pattern continues, into how many regions can five planes divide space?

According to the pattern,

\[R_{3}(4) = \underbrace{R_{2}(3)}_{7} + \underbrace{R_{3}(3)}_{8} = 15 \label{6.2} \]

and then

\[R_{3}(5) = \underbrace{R_{2}(4)}_{11} + \underbrace{R_{3}(4)}_{15} = 26. \label{6.3} \]

Thus, five planes can divide space into a maximum of 26 regions.

This number is hard to deduce by drawing five planes and counting the regions. Furthermore, that brute-force approach would give the value of only \(R_{3}\)(5), whereas easy cases and analogy give a method to compute any entry in the table. They thereby provide enough data to conjecture expressions for \(R_{2}\)(n) (Problem 6.9), for \(R_{3}\)(n) (Problem 6.10), and for the general entry \(R_{d}\)(n) (Problem 6.12).

Multiple problems

Problem 6.7 Checking the pattern in two dimensions

The conjectured pattern predicts \(R_{2}(5) = 16\): that five lines can divide the plane into 16 regions. Check the conjecture by drawing five lines and counting the regions.

Problem 6.8 Free data from zero dimensions

Because the one-dimensional problem gave useful data, try the zero-dimensional problem. Extend the pattern for the \(R_{3}\), \(R_{2}\), and \(R_{1}\) rows upward to construct an \(R_{0}\) row. It gives the number of zero-dimensional regions (points) produced by partitioning a point with n objects (of dimension −1). What is \(R_{0}\) if the row is to follow the observed pattern? Is that result consistent with the geometric meaning of trying to subdivide a point?

Problem 6.9 General result in two dimensions

The \(R_{0}\) data fits \(R_{0}(n) = 1\) (Problem 6.8), which is a zeroth-degree polynomial. The \(R_{1}\) data fits \(R_{1}(n) = n + 1\), which is a first-degree polynomial. Therefore, the \(R_{2}\) data probably fits a quadratic.

Test this conjecture by fitting the data for \(n = 0 . . . 2\) to the general quadratic \(An^{2} + Bn + C\), repeatedly taking out the big part (Chapter 5) as follows.

a. Guess a reasonable value for the quadratic coefficient A. Then take out (sub- tract) the big part \(An^{2}\) and tabulate the leftover, \(R^{2}(n) − An^{2}\), for \(n = 0 . . . 2\). If the leftover is not linear in n, then a quadratic term remains or too much was removed. In either case, adjust A.

b. Once the quadratic coefficient A is correct, use an analogous procedure to find the linear coefficient B.

c. Similarly solve for the constant coefficient C.

d. Check your quadratic fit against new data (\(R_{2}(n)\) for \(n \geqslant 3\)).

Problem 6.10 General result in three dimensions

A reasonable conjecture is that the \(R_{3}\) row matches a cubic (Problem 6.9). Use taking out the big part to fit a cubic to the \(n = 0 . . . 3\) data. Does it produce the conjectured values \(R_{3}(4) = 15\) and \(R_{3}(5) = 26\)?

Problem 6.11 Geometric explanation

Find a geometric explanation for the observed pattern. Hint: Explain first why the pattern generates the \(R_{2}\) row from the \(R_{1}\) row; then generalize the reason to explain the \(R_{3}\) row.

Problem 6.12 General solution in arbitrary dimension

The pattern connecting neighboring entries of the \(R_{d}(n)\) table is the pattern that generates Pascal’s triangle [17]. Because Pascal’s triangle produces binomial coefficients, the general expression \(R_{d}(n)\) should contain binomial coefficients.

Therefore, use binomial coefficients to express \(R_{0}(n)\) (Problem 6.8), \(R_{1}\)(n), and \(R_{2}\)(n) (Problem 6.9). Then conjecture a binomial-coefficient form for \(R_{3}\)(n) and \(R_{d}\)(n), checking the result against Problem 6.10.

Problem 6.13 Power-of-2 conjecture

Our first conjecture for the number of regions was \(R_{d}(n) = 2\). In three dimensions, it worked until \(n = 4\).

In \(d\) dimensions, show that \(R_{d}(n) = 2^{n}\) for \(n \leqslant d\) (perhaps using the results of Problem 6.12).