The Number of Intersection Points Made by the Diagonals of a Regular Polygon.
We give a formula for the number of interior intersection points made by the diagonals of a regular n-gon. The answer is a polynomial on each residue class modulo 2520. We also compute the number of regions formed by the diagonals, by using Euler's formula 2.
Introduction
We will find a formula for the number I(n) of intersection points formed inside
a regular n-gon by its diagonals. The case depicted in Figure 1. For a
generic convex n-gon, the answer would be
, because every four vertices would
be the endpoints of a unique pair of intersecting diagonals. But I(n) can be less,
because in a regular n-gon it may happen that three or more diagonals meet at an
interior point, and then some of the
intersection points will coincide. In fact,
if n is even and at least 6, I(n) will always be less than
, because there will be
diagonals meeting at the center point. It will result from our analysis that
4, the maximum number of diagonals of the regular n-gon that meet at a
point other than the center is
3 if n is even but not divisible by 6;
5 if n is divisible by 6 but not 30, and;
7 if n is divisible by 30:
with two exceptions: this number is 2 if In particular, it is
impossible to have 8 or more diagonals of a regular n-gon meeting at a point other
than the center. Also, by our earlier remarks, the fact that no three diagonals meet
when n is odd will imply that
for odd n.
Date: January 30, 1995.
1991 Mathematics Subject Classification. Primary 51M04; Secondary 11R18.
Key words and phrases. regular polygons, diagonals, intersection points, roots of unity, adventi-
tious quadrangles.
The first author is supported by an NSF Mathematical Sciences Postdoctoral Research Fellowship.
Part of this work was done at MSRI, where research is supported in part by NSF grant DMS-9022140.

Figure

1. The 30-gon with its diagonals. There are 16801 interior
intersection points: 13800 two line intersections, 2250 three line inter-
sections, 420 four line intersections, 180 five line intersections, 120 six
line intersections, seven line intersections, and 1 fifteen line intersection

DIAGONALS OF A REGULAR POLYGON 3
A careful analysis of the possible configurations of three diagonals meeting will
provide enough information to permit us in theory to deduce a formula for I(n). But
because the explicit description of these configurations is so complex, our strategy
will be instead to use this information to deduce only the form of the answer, and
then to compute the answer for enough small n that we can determine the result
precisely.
In order to write the answer in a reasonable form, we define
Theorem 1. For n - 3,
Further analysis, involving Euler's formula
the number R(n) of regions that the diagonals cut the n-gon into.
Theorem 2. For n - 3,
These problems have been studied by many authors before, but this is apparently
the first time the correct formulas have been obtained. The Dutch mathematician
Gerrit Bol [1] gave a complete solution in 1936, except that a few of the coefficients in
his formulas are wrong. misprints and omissions in Bol's paper are mentioned
in [11].)
The approaches used by us and Bol are similar in many ways. One difference
(which is not too substantial) is that we work as much as possible with roots of
unity whereas Bol tended to use more trigonometry (integer relations between sines
of rational multiples of -). Also, we relegate much of the work to the computer,
whereas Bol had to enumerate the many cases by hand. The task is so formidable
that it is amazing to us that Bol was able to complete it, and at the same time not
so surprising that it would contain a few errors!
Bol's work was largely forgotten. In fact, even we were not aware of his paper
until after deriving the formulas ourselves. Many other authors in the interim solved
special cases of the problem. Steinhaus [14] posed the problem of showing that no
three diagonals meet internally when n is prime, and this was solved by Croft and
Fowler [3]. (Steinhaus also mentions this in [13], which includes a picture of the
23-gon and its diagonals.) In the 1960s, Heineken [6] gave a delightful argument
which generalized this to all odd n, and later he [7] and Harborth [4] independently
enumerated all three-diagonal intersections for n not divisible by 6.
The classification of three-diagonal intersections also solves Colin Tripp's problem
[15] of enumerating "adventitious quadrilaterals," those convex quadrilaterals
for which the angles formed by sides and diagonals are all rational multiples of -.
See Rigby's paper [11] or the summary [10] for details. Rigby, who was aware of
Bol's work, mentions that Monsky and Pleasants also each independently classified
all three-diagonal intersections of regular n-gons. Rigby's papers partially solve
Tripp's further problem of proving the existence of all adventitious quadrangles using
only elementary geometry; i.e., without resorting to trigonometry.
All the questions so far have been in the Euclidean plane. What happens if we
count the interior intersections made the diagonals of a hyperbolic regular n-gon?
The answers are exactly the same, as pointed out in [11], because if we use Bel-
trami's representation of points of the hyperbolic plane by points inside a circle in
the Euclidean plane, we can assume that the center of the hyperbolic n-gon corresponds
to the center of the circle, and then the hyperbolic n-gon with its diagonals
looks in the model exactly like a Euclidean regular n-gon with its diagonals. It is
equally easy to see that the answers will be the same in elliptic geometry.
2. When do three diagonals meet?
We now begin our derivations of the formulas for I(n) and R(n). The first step
will be to find a criterion for the concurrency of three diagonals. Let A; B; C; D; E; F
be six distinct points in order on a unit circle dividing up the circumference into arc
lengths u; x; v; z and assume that the three chords AD;BE;CF meet at P (see

Figure

2).
By similar triangles,
Multiplying these together yields
(AF
and so
Conversely, suppose six distinct points A; B; C; D; E; F partition the circumference
of a unit circle into arc lengths u; x; v; z and suppose that (1) holds. Then the
three diagonals AD;BE;CF meet in a single point which we see as follows. Let lines
DIAGONALS OF A REGULAR POLYGON 5
z
y
A
x
F

Figure

2.
AD and BE intersect at P 0 . Form the line through F and P 0 and let C 0 be the other
intersection point of FP 0 with the circle. This partitions the circumference into arc
lengths As shown above, we have
and since we are assuming that (1) holds for u; x; v; z we get
sin(y 0 =2)
Substituting above we get
sin(y 0 =2)
and so
cot(y
Now . Thus, the three diagonals
AD;BE;CF meet at a single point.
So (1) gives a necessary and sufficient condition (in terms of arc lengths) for the
chords AD;BE;CF formed by six distinct points A; B; C; D; E; F on a unit circle to
meet at a single point. In other words, to give an explicit answer to the question in
6 BJORN POONEN AND MICHAEL RUBINSTEIN
the section title, we need to characterize the positive rational solutions to
(Here This is a trigonometric diophantine equation in the sense
of [2], where it is shown that in theory, there is a finite computation which reduces
the solution of such equations to ordinary diophantine equations. The solutions to
the analogous equation with only two sines on each side are listed in [9].
If in (2), we substitute multiply both sides by (2i) 3 , and
expand, we get a sum of eight terms on the left equalling a similar sum on the right,
but two terms on the left cancel with two terms on the right since U
leaving
\Gammae i-(V +W \GammaU
\Gammae i-(Y +Z \GammaX
If we move all terms to the left hand side, convert minus signs into e \Gammai- , multiply by
we obtainX
in which
Conversely, given rational numbers
necessarily positive) which sum to 1 and satisfy (3), we can
recover U; V; W;X;Y;Z, (for example, but we must check
that they turn out positive.
3. Zero as a sum of 12 roots of unity
In order to enumerate the solutions to (2), we are led, as in the end of the last
section, to classify the ways in which 12 roots of unity can sum to zero. More
generally, we will study relations of the form
a
DIAGONALS OF A REGULAR POLYGON 7
where the a i are positive integers, and the j i are distinct roots of unity. (These
have been studied previously by Schoenberg [12], Mann [8], Conway and Jones [2],
and others.) We call
a i the weight of the relation S. (So we shall be
particularly interested in relations of weight 12.) We shall say the relation (4) is
minimal if it has no nontrivial subrelation; i.e., if
implies either b By induction on the weight, any
relation can be represented as a sum of minimal relations (but the representation
need not be unique).
Let us give some examples of minimal relations. For each n - 1, let
exp(2-i=n) be the standard primitive n-th root of unity. For each prime p, let R p be
the relation
Its minimality follows from the irreducibility of the cyclotomic polynomial. Also
we can "rotate" any relation by multiplying through by an arbitrary root of unity
to obtain a new relation. In fact, Schoenberg [12] proved that every relation (even
those with possibly negative coefficients) can be obtained as a linear combination
with positive and negative integral coefficients of the R p and their rotations. But we
are only allowing positive combinations, so it is not clear that these are enough to
generate all relations.
In fact it is not even true! In other words, there are other minimal relations. If we
subtract R 3 from R 5 , cancel the 1's and incorporate the minus signs into the roots
of unity, we obtain a new relation
which we will denote (R 5 In general, if S and are relations, we
will use the notation to denote any relation obtained by rotating
the T i so that each shares exactly one root of unity with S which is different for each i,
subtracting them from S, and incorporating the minus signs into the roots of unity.
For notational convenience, we will write (R
example. Note that although (R 5 unambiguously (up to rotation) the
relation listed in (5), in general there will be many relations of type
up to rotational equivalence. Let us also remark that including R 2 's in the list of T 's
has no effect.
It turns out that recursive use of the construction above is enough to generate all
minimal relations of weight up to 12. These are listed in Table 1. The completeness
and correctness of the table will be proved in Theorem 3 below. Although there are
107 minimal relations up to rotational equivalence, often the minimal relations within
Weight Relation type Number of relations of that type
6 (R 5
(R
9 (R
(R
(R
(R
(R
(R
(R
(R
(R
(R
(R

Table

1. The 107 minimal relations of weight up to 12.
one of our classes are Galois conjugates. For example, the two minimal relations of
type (R are conjugate under Gal(Q (i 15
)=Q ), as pointed out in [8].
The minimal relations with defined as in (4)) had been previously catalogued
in [8], and those with k - 9 in [2]. In fact, the a i in these never exceed 1, so
these also have weight less than or equal to 9.
Theorem 3. Table 1 is a complete listing of the minimal relations of weight up to
12 (up to rotation).
The following three lemmas will be needed in the proof.
Lemma 1. If the relation (4) is minimal, then there are distinct primes
so that each j i is a -th root of unity, after the relation has
been suitably rotated.
Proof. This is a corollary of Theorem 1 in [8].
Lemma 2. The only minimal relations (up to rotation) involving only the 2p-th roots
of unity, for p prime, are R 2 and R p .
DIAGONALS OF A REGULAR POLYGON 9
Proof. Any 2p-th root of unity is of the form \Sigmai i . If both +i i and \Gammai i occurred in
the same relation, then R 2 occurs as a subrelation. So the relation has the form
By the irreducibility of the cyclotomic polynomial,
are independent
over Q save for the relation that their sum is zero, so all the c i must be equal. If
they are all positive, then R p occurs as a subrelation. If they are all negative, then
rotated by -1 (i.e., 180 degrees) occurs as a subrelation.
Lemma 3. Suppose S is a minimal relation, and are picked as
in Lemma 1 with (or a rotation) is
of the form (R ps are minimal relations not equal to R 2
and involving only roots of unity, such that
Proof. Since every p 1 -th root of unity is uniquely expressible as a p 1
th root of unity and a p s -th root of unity, the relation can be rewritten as
ps
where each f i is a sum of p 1 roots of unity, which we will think of as a
sum (not just its value).
Let Km be the field obtained by adjoining the p 1 roots of unity to Q .
the only linear
relation satisfied by ps
ps over K s\Gamma1 is that their sum is zero. Hence (6)
forces the values of the f i to be equal.
The total number of roots of unity in all the f i 's is w(S) ! 2p s , so by the pigeonhole
principle, some f i is zero or consists of a single root of unity. In the former case,
each f j sums to zero, but at least two of these sums contain at least one root of
unity, since otherwise s was not minimal, so one of these sums gives a subrelation
of S, contradicting its minimality. So some f i consists of a single root of unity. By
rotation, we may assume f sums to 1, and if it is not simply the
single root of unity 1, the negatives of the roots of unity in f i together with 1 form
a relation T i which is not R 2 and involves only roots of unity, and it
is clear that S is of type (R ps
If one of the T 's were not minimal,
then it could be decomposed into two nontrivial subrelations, one of which would not
share a root of unity with the R ps , and this would give a nontrivial subrelation of S,
contradicting the minimality of S. Finally, w(S) must equal the sum of the weights
of R ps and the T 's, minus 2j to account for the roots of unity that are cancelled in
the construction of (R ps
Proof of Theorem 3. We will content ourselves with proving that every relation of
weight up to 12 can be decomposed into a sum of the ones listed in Table 1, it then
being straightforward to check that the entries in the table are distinct, and that
none of them can be further decomposed into relations higher up in the table.
Let S be a minimal relation with w(S) - 12. Pick
In particular, p s - 12, so
Case 1:
Here the only minimal relations are R 2 and R 3 , by Lemma 2.
Case 2:
If w(S) ! 10, then we may apply Lemma 3 to deduce that S is of type (R
Each T must be R 3 (since p by the last
equation in Lemma 3. The number of relations of type (R 5 : jR 3 ), up to rotation,
is
=5. (There are
ways to place the R 3 's, but one must divide by 5 to avoid
counting rotations of the same relation.)
as in (6). If some f i consists of zero or one
roots of unity, then the argument of Lemma 3 applies, and S must be of the form
(R which contradicts the last equation in the Lemma. Otherwise
the numbers of (sixth) roots of unity occurring in f must be 2,2,2,2,2
or 2,2,2,2,3 or 2,2,2,3,3 or 2,2,2,2,4 in some order. So the common value of the f i
is a sum of two sixth roots of unity. By rotating by a sixth root of unity, we may
assume this value is 0, 1, or 1 If it is 0 or 1, then the arguments in the proof of
Lemma 3 apply. So assume it is 1 . The only way two sixth roots of unity can
sum to 1+ i 6 is if they are 1 and i 6 in some order. The only ways three sixth roots of
unity can sum to 1 are
6 or i 6
6 . So if the numbers of roots
of unity occurring in f are 2,2,2,2,2 or 2,2,2,2,3, then S will contain R 5
or its rotation by i 6 , and the same will be true for 2,2,2,3,3 unless the two f i with
three terms are 1
6 , in which case S contains (R 5
Finally, it is impossible to as a sum of sixth roots of unity without using
1 or i 6 , so if the numbers are 2,2,2,2,4, then again S contains R 5 or its rotation by
. Thus there are no minimal relations S with
Case 3:
7, we can apply Lemma 3. Now the sum of w(T
required to be w(S) \Gamma 7 which at most 5, so the T 's that may be used are R 3 , R 5 ,
(R and the two of type (R
and 5, respectively. So the problem is reduced to listing the partitions of w(S) \Gamma 7
into parts of size 1, 3, 4, and 5.
If all parts used are 1, then we get (R 7, and there are
=7 distinct relations in this class. Otherwise exactly one part of size 3, 4, or 5 is
used, and the possibilities are as follows. If a part of size 3 is used, we get (R 7
DIAGONALS OF A REGULAR POLYGON 11
Partition Relation type
(R
(R
(R
(R
(R
(R
(R
(R
(R
(R
Partition Relation type
(R
R 7 +R 5
(R

Table

2. The types of relations of weight 12.
(R weights 10, 11, 12 respectively. By rotation, the
R 5 may be assumed to share the 1 in the R 7 , and then there are
ways to place the
R 3 's where i is the number of R 3 's. If a part of size 4 is used, we get (R
of weight 11 or (R 7 By rotation, the (R 5 may be
assumed to share the 1 in the R 7 , but any of the six roots of unity in the (R 5
may be rotated to be 1. The R 3 can then overlap any of the other 6 seventh roots
of unity. Finally, if a part of size 5 is used, we get (R There are two
different relations of type (R that may be used, and each has seven roots of
unity which may be rotated to be the 1 shared by the R 7 , so there are 14 of these all
together.
Case 4:
Applying Lemma 3 shows that the only possibilities are R 11 of weight 11, and
(R
Now a general relation of weight 12 is a sum of the minimal ones of weight up to 12,
and we can classify them according to the weights of the minimal relations, which form
a partition of 12 with no parts of size 1 or 4. We will use the notation (R
for example, to denote a sum of three minimal relations of type (R
and R 3 .

Table

2 lists the possibilities. The parts may be rotated independently,
so any category involving more than one minimal relation contains infinitely many
relations, even up to rotation (of the entire relation). Also, the categories are not
mutually exclusive, because of the non-uniqueness of the decomposition into minimal
relations.

Figure

3. A surprising trivial solution for the 16-gon. The intersection
point does not lie on any of the 16 lines of symmetry of the 16-gon.
4. Solutions to the trigonometric equation
Here we use the classification of the previous section to give a complete listing of
the solutions to the trigonometric equation (2). There are some obvious solutions
to (2), namely those in which U; V; W are arbitary positive rational numbers with
sum 1=2, and X; Y; Z are a permutation of U; V; W . We will call these the trivial
solutions, even though the three-diagonal intersections they give rise to can look
surprising. For example, see Figure 3 for an example on the 16-gon.
The twelve roots of unity occurring in (3) are not arbitrary; therefore we must
go through Table 2 to see which relations are of the correct form, i.e., expressible
as a sum of six roots of unity and their inverses, where the product of the six is -1.
Because of the large number of cases, we perform this calculation using Mathematica.
Each entry of Table 2 represents a finite number of linearly parameterized (in the
exponents) families of relations of weight 12. For each parameterized family, we check
to see what additional constraints must be put on the parameters for the relation to
be of the form of (3). Next, for each parameterized family of solutions to (3), we
calculate the corresponding U; V; W;X;Y;Z and throw away solutions in which some
of these are nonpositive. Finally, we sort U; V; W and X; Y; Z and interchange the
two triples if U ? X, in order to count the solutions only up to symmetry.
The results of this computation are recorded in the following theorem.
DIAGONALS OF A REGULAR POLYGON 13
U

Table

3. The nontrivial infinite families of solutions to (2).
Theorem 4. The positive rational solutions to (2), up to symmetry, can be classified
as follows:
1. The trivial solutions, which arise from relations of type 6R 2 .
2. Four one-parameter families of solutions, listed in Table 3, which arise from
relations of type
3. Sixty-five "sporadic" solutions, listed in Table 4, which arise from the other types
of weight 12 relations listed in Table 2. The only duplications in this list are
that the second family of Table 3 gives a trivial solution for 1=12, and that
the first and fourth families of Table 3 give the same solution when
both.
Some explanation of the tables is in order. The last column of Table 3 gives
the allowable range for the rational parameter t. The entries of Table 4 are sorted
according to the least common denominator of U; V; W;X;Y;Z, which is also the
least n for which diagonals of a regular n-gon can create arcs of the corresponding
lengths. The reason 11 does not appear in the least common denominator for any
sporadic solution is that the relation (R 11 : R 3 ) cannot be put in the form of (3) with
the ff j summing to 1, and hence leads to no solutions of (2). (Several other types of
relations also give rise to no solutions.)

Tables

3 and 4 are the same as Bol's tables at the bottom of page 40 and on page 41
of [1], in a slightly different format.
The arcs cut by diagonals of a regular n-gon have lengths which are multiples of
2-=n, so U , V , W , X, Y and Z corresponding to any configuration of three diagonals
meeting must be multiples of 1=n. With this additional restriction, trivial solutions
to (2) occur only when n is even (and at least 6). Solutions within the infinite families
of

Table

occur when n is a multiple of 6 (and at least 12), and there t must be a
multiple of 1=n. Sporadic solutions with least common denominator d occur if and
only if n is a multiple of d.
5. Intersections of more than three diagonals
Now that we know the configurations of three diagonals meeting, we can check
how they overlap to produce configurations of more than three diagonals meeting.
14 BJORN POONEN AND MICHAEL RUBINSTEIN
1=15 1=6 4=15 1=10 1=10 3=10
1=15 1=15 7=15 1=15 1=10 7=30
1=42 3=14 5=14 1=21 1=6 4=21
1=42 1=6 19=42 1=14 2=21 4=21
1=42 1=6 13=42 1=21 1=14 8=21
1=42 1=21 13=21 1=42 1=14 3=14
1=12 2=15 19=60 1=10 3=20 13=60
1=15 11=60 13=60 1=12 1=10 7=20
1=60 4=15 23=60 1=12 1=10 3=20
1=60 4=15 3=10 1=20 1=12 17=60
1=60 13=60 9=20 1=12 1=10 2=15
1=60 13=60 5=12 1=20 2=15 1=6
1=60 1=6 31=60 1=15 1=10 2=15
1=60 1=6 5=12 1=20 1=15 17=60
84 1=12 3=14 19=84 11=84 13=84 4=21
1=14 11=84 23=84 1=12 2=21 29=84
1=42 1=12 7=12 1=21 1=14 4=21
1=84 25=84 5=14 5=84 1=12 4=21
1=84 5=21 5=12 5=84 1=14 17=84
1=84 3=14 37=84 1=21 1=12 17=84
1=84 1=6 43=84 1=21 1=14 4=21
90 1=18 13=90 7=18 11=90 2=15 7=45
1=90 23=90 31=90 2=45 1=15 5=18
1=90 17=90 47=90 1=18 4=45 2=15
1=12 19=120 29=120 1=10 13=120 37=120
1=60 13=120 73=120 1=20 1=12 2=15
1=120 7=20 43=120 7=120 11=120 2=15
1=120 13=60 61=120 1=20 1=12 2=15
1=35 2=15 97=210 1=14 17=210 47=210

Table

4. The solutions to (2).
DIAGONALS OF A REGULAR POLYGON 15
We will disregard configurations in which the intersection point is the center of the
n-gon, since these are easily described: there are exactly n=2 diagonals (diameters)
through the center when n is even, and none otherwise.
When k diagonals meet, they form 2k arcs, whose lengths we will measure as a
fraction of the whole circumference (so they will be multiples of 1=n) and list in
counterclockwise order. (Warning: this is different from the order used in Tables 3
and 4.) The least common denominator of the numbers in this list will be called the
denominator of the configuration. It is the least n for which the configuration can be
realized as diagonals of a regular n-gon.
Lemma 4. If a configuration of k - 2 diagonals meeting at an interior point other
than the center has denominator dividing d, then any configuration of diagonals meeting
at that point has denominator dividing LCM(2d; 3).
Proof. We may assume 2. Any other configuration of diagonals through the
intersection point is contained in the union of configurations obtained by adding one
diagonal to the original two, so we may assume the final configuration consists of
three diagonals, two of which were the original two. Now we need only go through
our list of three-diagonal intersections.
It can be checked (using Mathematica) that removing any diagonal from a sporadic
configuration of three intersecting diagonals yields a configuration whose denominator
is the same or half as much, except that it is possible that removing a diagonal from a
three-diagonal configuration of denominator 210, yields one of denominator 70, which
proves the desired result for this case. The additive group generated by 1=6 and the
normalized arc lengths of a configuration obtained by removing a diagonal from a
configuration corresponding to one of the families of Table 3 contains 2t where t is the
parameter, (as can be verified using Mathematica again), which means that adding
that third diagonal can at most double the denominator (and throw in a factor of 3, if
it isn't already there). Similarly, it is easily checked (even by hand), that the subgroup
generated by the normalized arc lengths of a configuration obtained by removing one
of the three diagonals of a configuration corresponding to a trivial solution to (2) but
with intersection point not the center, contains twice the arc lengths of the original
configuration.
Corollary 1. If a configuration of three or more diagonals meeting includes three
forming a sporadic configuration, then its denominator is 30, 42, 60, 84, 90, 120,
168, 180, 210, 240, or 420.
Proof. Combine the lemma with the list of denominators of sporadic configurations
listed in Table 4.
For k - 4, a list of 2k positive rational numbers summing to 1 arises this way if
and only if the lists of length 2k \Gamma 2 which would arise by removing the first or second
diagonal actually correspond to intersecting diagonals. Suppose 4. If we
Range

Table

5. The one-parameter families of four-diagonal configurations.
specify the sporadic configuration or parameterized family of configurations that arise
when we remove the first or second diagonal, we get a set of linear conditions on the
eight arc lengths. Corollary 1 tells us that we get a configuration with denominator
among 30, 42, 60, 84, 90, 120, 168, 180, 210, 240, and 420, if one of these two is
sporadic. Using Mathematica to perform this computation for the rest of possibilities
in Theorem 4 shows that the other four-diagonal configurations, up to rotation and
reflection, fall into 12 one-parameter families, which are listed in Table 5 by the eight
normalized arc lengths and the range for the parameter t, with a finite number of
exceptions of denominators among 12, 18, 24, 30, 36, 42, 48, 60, 84, and 120.
We will use a similar argument when 5. Any five-diagonal configuration containing
a sporadic three-diagonal configuration will again have denominator among
30, 42, 60, 84, 90, 120, 168, 180, 210, 240, and 420, again. Any other five-diagonal
configuration containing one of the exceptional four-diagonal configurations will have
denominator among 12, 18, 24, 30, 36, 42, 48, 60, 72, 84, 96, 120, 168, and 240, by
Lemma 4. Finally, another Mathematica computation shows that the one-parameter
families of four-diagonal configurations overlap to produce the one-parameter families
listed (up to rotation and reflection) in Table 6, and a finite number of exceptions of
denominators among 12, 18, 24, and 30.
For six-diagonal configuration containing a sporadic three-
diagonal configuration will again have denominator among 30, 42, 60, 84, 90, 120,
168, 180, 210, 240, and 420. Any six-diagonal configuration containing one of the
exceptional four-diagonal configurations will have denominator among 12, 18, 24,
30, 36, 42, 48, 60, 72, 84, 96, 120, 168, and 240. Any six-diagonal configuration
containing one of the exceptional five-diagonal configurations will have denominator
among 12, 18, 24, 30, 36, 48, and 60. Another Mathematica computation shows that
DIAGONALS OF A REGULAR POLYGON 17
Range

Table

6. The one-parameter families of five-diagonal configurations.
the one-parameter families of five-diagonal configurations cannot combine to give a
six-diagonal configuration.
Finally for k - 7, any k-diagonal configuration must contain an exceptional configuration
of 3, 4, or 5 diagonals, and hence by Lemma 4 has denominator among 12,
We summarize the results of this section in the following.
Proposition 1. The configurations of k - 4 diagonals meeting at a point not the
center, up to rotation and reflection, fall into the one-parameter families listed in

Tables

5 and 6, with finitely many exceptions (for fixed of denominators among
12, 18, 24, 30, 36, 42, 48, 60, 72, 84, 90, 96, 120, 168, 180, 210, 240, and 420.
In fact, many of the numbers listed in the proposition do not actually occur as
denominators of exceptional configurations. For example, it will turn out that the
only denominator greater than 120 that occurs is 210.
6. The formula for intersection points
Let a k (n) denote the number of points inside the regular n-gon other than the center
where exactly k lines meet. Let b k (n) denote the number of k-tuples of diagonals
which meet at a point inside the n-gon other than the center. Each interior point
at which exactly m diagonals meet gives rise to
such k-tuples, so we have the
relationship
m-k
am (n) (7)
Since every four distinct vertices of the n-gon determine one pair of diagonals which
intersect inside, the number of such pairs is exactly
, but if n is even, then
of these are pairs which meet at the center, so
(Recall that ffi m (n) is defined to be 1 if n is a multiple of m, and 0 otherwise.)
We will use the results of the previous two sections to deduce the form of b k (n)
and then the form of a k (n). To avoid having to repeat the following, let us make a
definition.
Definition . A function on integers n - 3 will be called tame if it is a linear combination
(with rational coefficients) of the functions n 3 ,
Proposition 2. For each k - 2, the function b k (n)=n on integers n - 3 is tame.
Proof. The case handled by (8), so assume k - 3. Each list of 2k normalized
arc lengths as in Section 5 corresponding to a configuration of k diagonals meeting
at a point other than the center, considered up to rotation (but not reflection),
contributes n to b k (n). (There are n places to start measuring the arcs from, and
these n configurations are distinct, because the corresponding intersection points
differ by rotations of multiples of 2-=n, and by assumption they are not at the
center.) counts such lists.
3. When n is even, the family of trivial solutions to the trigonometric
equation (2) has are positive integers
with sum n=2, and X, Y , and Z are some permutation of U , V , W . Each permutation
gives rise to a two-parameter family of six-long lists of arc lengths, and the number
of lists with each family is the number of partitions of n=2 into three positive parts,
which is a quadratic polynomial in n. Similarly each family of solutions in Table 3
gives rise to a number of one-parameter families of lists, when n is a multiple of 6,
each containing dn=6e \Gamma 1 or dn=12e \Gamma 1 lists. These functions of n (extended to be
when 6 does not divide n) are expressible as a linear combination of nffi 6 (n), ffi 6 (n),
and Finally the sporadic solutions to 2 give rise to a finite number of lists,
having denominators among 30, 42, 60, 84, 90, 120, and 210, so their contribution to
3 (n)=n is a linear combination of ffi
But these families of lists overlap, so we must use the Principle of Inclusion-Exclusion
to count them properly. To show that the result is a tame function, it
suffices to show that the number of lists in any intersection of these families is a tame
function. When two of the trivial families overlap but do not coincide, they overlap
where two of the a, b, and c above are equal, and the corresponding lists lie in one of
the one-parameter families (t; t; t; t;
(with 1=4), each of which contain dn=4e \Gamma 1 lists (for n even). This function
of n is a combination of nffi 2 (n), hence it is tame. Any other intersection
of the infinite families must contain the intersection of two one-parameter
families which are among the two above or arise from Table 3, and a Mathematica
computation shows that such an intersection consists of at most a single list of denominator
among 6, 12, 18, 24, and 30. And, of course, any intersection involving a
single sporadic list, can contain at most that sporadic list. Thus the number of lists
DIAGONALS OF A REGULAR POLYGON 19
within any intersection is a tame function of n. Finally we must delete the lists which
correspond to configurations of diagonals meeting at the center. These are the lists
within the trivial two-parameter family (t; u;
number is also a tame function of n, by the Principle of Inclusion-Exclusion again.
Thus b 3 (n)=n is tame.
Next suppose 4. The number of lists within each family listed in Table 5, or
the reflection of such a family, is (when n is divisible by 6) the number of multiples
of 1=n strictly between ff and fi, where the range for the parameter t is ff
This number is dfine the table shows that ff and fi are always
multiples of 1=24, this function of n is expressible as a combination of nffi 6 (n) and a
function on multiples of 6 depending only on n mod 24, and the latter can be written
as a combination of ffi 6 (n), so it is tame. Mathematica
shows that when two of these families are not the same, they intersect in at most a
single list of denominator among 6, 12, 18, and 24. So these and the exceptions of
Proposition 1 can be counted by a tame function. Thus, again by the Principle of
Inclusion-Exclusion, b 4 (n)=n is tame.
The proof for identical to that of 4, using Table 6 instead of Table 5,
and using another Mathematica computation which shows that the intersections of
two one-parameter families of lists consist of at most a single list of denominator 24.
The proof for k - 6 is even simpler, because then there are only the exceptional
lists. By Proposition 1, b k (n)=n is a linear combination of ffi m (n) where m ranges
over the possible denominators of exceptional lists listed in the proposition, so it is
tame.
Lemma 5. A tame function is determined by its values at
10, 12, 18, 24, 30, 36, 42, 48, 54, 60, 66, 72, 84, 90, 96, 120, 168, 180, 210, and
420.
Proof. By linearity, it suffices to show that if a tame function f is zero at those
values, then f the zero linear combination of the functions in the definition of a tame
function. The vanishing at forces the coefficients of n 3 ,
1 to vanish, by Lagrange interpolation. Then comparing the values at
shows that the coefficient of ffi 4 (n) is zero. The vanishing at
forces the coefficients of to vanish. Comparing the values
at shows that the coefficient of nffi 6 is zero. Comparing the values
at shows that the coefficient of
At this point, we know that f(n) is a combination of ffi m (n), for
30, 36, 42, 48, 60, 72, 84, 90, 96, 120, 168, 180, 210, and 420. For each m in turn,
now implies that the coefficient of ffi m (n) is zero.
Proof of Theorem 1. Computation (see the appendix) shows that the tame function
b 8 (n)=n vanishes at all the numbers listed in Lemma 5. Hence by that lemma, b 8
0 for all n. Thus by (7), a k (n) and b k (n) are identically zero for all k - 8 as well.
By reverse induction on k, we can invert (7) to express a k (n) as a linear combination
of b m (n) with m - k. Hence a k (n)=n is tame as well for each k - 2. Computation
shows that the equations
a
a 3
a 4
a 5
a 6
a 7
hold for all the n listed in Lemma 5, so the lemma implies that they hold for all
- 3. These formulas imply the remarks in the introduction about the maximum
number of diagonals meeting at an interior point other than the center. Finally
a k (n)
a k (n);
which gives the desired formula. (The in the expression for I(n) is to account
for the center point when n is even, which is the only point not counted by the
a k .)
7. The formula for regions
We now use the knowledge obtained in the proof of Theorem 1 about the number
of interior points through which exactly k diagonals pass to calculate the number of
regions formed by the diagonals.
Proof of Theorem 2. Consider the graph formed from the configuration of a regular
n-gon with its diagonals, in which the vertices are the vertices of the n-gon together
with the interior intersection points, and the edges are the sides of the n-gon together
DIAGONALS OF A REGULAR POLYGON 21
with the segments that the diagonals cut themselves into. As usual, let V denote the
number of vertices of the graph, E the number of edges, and F the number of regions
formed, including the region outside the n-gon. We will employ Euler Formula's
2.
I(n). We will count edges by counting their ends, which are 2E
in number. Each vertex has the center (if n is even) has n edge
ends, and any other interior point through which exactly k diagonals pass has 2k
edge ends, so
So the desired number of regions, not counting the region outside the n-gon, is
Substitution of the formulas derived in the proof of Theorem 1 for a k (n) and I(n)
yields the desired result.
Appendix: computations and tables
In

Table

7 we list I(n); R(n); a To determine
the polynomials listed in Theorem 1 more data was needed especially for
The largest n for which this was required was 420. For speed and memory conser-
vation, we took advantage of the regular n-gon's rotational symmetry and focused
our attention on only 2-=n radians of the n-gon. The data from this computation is
found in Table 8. Although we only needed to know the values at those n listed in
Lemma 5 of Section 6, we give a list for so that the nice patterns
can be seen.
The numbers in these tables were found by numerically computing (using a C
program and 64 bit precision) all possible
intersections, and sorting them by
their x coordinate. We then focused on runs of points with close x coordinates,
looking for points with close y coordinates.
Several checks were made to eliminate any fears (arising from round-off errors) of
distinct points being mistaken as close. First, the C program sent data to Maple
which checked that the coordinates of close points agreed to at least 40 decimal
places. Second, we verified for each n that close points came in counts of the form
diagonals meeting at a point give rise to
close points. Hence, any run
whose length is not of this form indicates a computational error).
A second program was then written and run on a second machine to make the
computations completely rigorous. It also found the intersection points numerically,
sorted them and looked for close points, but, to be absolutely sure that a pair of close
22 BJORN POONEN AND MICHAEL RUBINSTEIN
points were actually the same, it checked that for the two pairs of diagonals
respectively, the triples l 1
each divided the circle into arcs of lengths consistent with Theorem 4. Since this test
only involves comparing rational numbers, it could be performed exactly.
A word should also be said concerning limiting the search to 2-=n radians of
the n-gon. Both programs looked at slightly smaller slices of the n-gon to avoid
problems caused by points near the boundary. More precisely, we limited our search
to points whose angle with the origin fell between [c 1
of made sure not to include the origin in the count. Here
" was chosen to be :00000000001 and c 1 was chosen to be :00000123 would
have led to problems since there are many intersection points with angle 0 or 2-=n).
To make sure that no intersection points were omitted, the number of points found
(counting multiplicity) was compared with (

Acknowledgements

We thank Joel Spencer and Noga Alon for helpful conversations. Also we thank
Jerry Alexanderson, Jeff Lagarias, Hendrik Lenstra, and Gerry Myerson for pointing
out to us many of the references below.



--R

Beantwoording van prijsvraag No.
Trigonometric Diophantine equations (On vanishing sums of roots of unity)
On a problem of Steinhaus about polygons
Diagonalen im regularen n-Eck
Number of intersections of diagonals in regular n-gons


On linear relations between roots of unity
Rational products of sines of rational angles
Adventitious quadrangles: a geometrical approach
Multiple intersections of diagonals of regular polygons
A note on the cyclotomic polynomial
Mathematical Snapshots
Problem 225
Adventitious angles
--TR
intersection points;diagonals;adventitious quadrangles;regular polygons;roots of unity