Equidissection

Last updated
A 6-equidissection of a square Square dissected into 6 equal area triangles no border.svg
A 6-equidissection of a square

In geometry, an equidissection is a partition of a polygon into triangles of equal area. The study of equidissections began in the late 1960s with Monsky's theorem, which states that a square cannot be equidissected into an odd number of triangles. [1] In fact, most polygons cannot be equidissected at all. [2]

Contents

Much of the literature is aimed at generalizing Monsky's theorem to broader classes of polygons. The general question is: Which polygons can be equidissected into how many pieces? Particular attention has been given to trapezoids, kites, regular polygons, centrally symmetric polygons, polyominos, and hypercubes. [3]

Equidissections do not have many direct applications. [4] They are considered interesting because the results are counterintuitive at first, and for a geometry problem with such a simple definition, the theory requires some surprisingly sophisticated algebraic tools. Many of the results rely upon extending p-adic valuations to the real numbers and extending Sperner's lemma to more general colored graphs. [5]

Overview

Definitions

A dissection of a polygon P is a finite set of triangles that do not overlap and whose union is all of P. A dissection into n triangles is called an n-dissection, and it is classified as an even dissection or an odd dissection according to whether n is even or odd. [5]

An equidissection is a dissection in which every triangle has the same area. For a polygon P, the set of all n for which an n-equidissection of P exists is called the spectrum of P and denoted S(P). A general theoretical goal is to compute the spectrum of a given polygon. [6]

A dissection is called simplicial if the triangles meet only along common edges. Some authors restrict their attention to simplicial dissections, especially in the secondary literature, since they are easier to work with. For example, the usual statement of Sperner's lemma applies only to simplicial dissections. Often simplicial dissections are called triangulations , although the vertices of the triangles are not restricted to the vertices or edges of the polygon. Simplicial equidissections are therefore also called equal-area triangulations. [7]

The terms can be extended to higher-dimensional polytopes: an equidissection is set of simplexes having the same n-volume. [8]

Preliminaries

It is easy to find an n-equidissection of a triangle for all n. As a result, if a polygon has an m-equidissection, then it also has an mn-equidissection for all n. In fact, often a polygon's spectrum consists precisely of the multiples of some number m; in this case, both the spectrum and the polygon are called principal and the spectrum is denoted . [2] For example, the spectrum of a triangle is . A simple example of a non-principal polygon is the quadrilateral with vertices (0, 0), (1, 0), (0, 1), (3/2, 3/2); its spectrum includes 2 and 3 but not 1. [9]

Affine transformations of the plane are useful for studying equidissections, including translations, uniform and non-uniform scaling, reflections, rotations, shears, and other similarities and linear maps. Since an affine transformation preserves straight lines and ratios of areas, it sends equidissections to equidissections. This means that one is free to apply any affine transformation to a polygon that might give it a more manageable form. For example, it is common to choose coordinates such that three of the vertices of a polygon are (0, 1), (0, 0), and (1, 0). [10]

The fact that affine transformations preserve equidissections also means that certain results can be easily generalized. All results stated for a regular polygon also hold for affine-regular polygons; in particular, results concerning the unit square also apply to other parallelograms, including rectangles and rhombuses. All results stated for polygons with integer coordinates also apply to polygons with rational coordinates, or polygons whose vertices fall on any other lattice. [11]

Best results

Monsky's theorem states that a square has no odd equidissections, so its spectrum is . [1] More generally, it is known that centrally symmetric polygons and polyominos have no odd equidissections. [12] A conjecture by Sherman K. Stein proposes that no special polygon has an odd equidissection, where a special polygon is one whose equivalence classes of parallel edges each sum to the zero vector. Squares, centrally symmetric polygons, polyominos, and polyhexes are all special polygons. [13]

For n > 4, the spectrum of a regular n-gon is . [14] For n > 1, the spectrum of an n-dimensional cube is , where n! is the factorial of n. [15] and the spectrum of an n-dimensional cross-polytope is . The latter follows mutatis mutandis from the proof for the octahedron in [2]

Let T(a) be a trapezoid where a is the ratio of parallel side lengths. If a is a rational number, then T(a) is principal. In fact, if r/s is a fraction in lowest terms, then . [16] More generally, all convex polygons with rational coordinates can be equidissected, [17] although not all of them are principal; see the above example of a kite with a vertex at (3/2, 3/2).

At the other extreme, if a is a transcendental number, then T(a) has no equidissection. More generally, no polygon whose vertex coordinates are algebraically independent has an equidissection. [18] This means that almost all polygons with more than three sides cannot be equidissected. Although most polygons cannot be cut into equal-area triangles, all polygons can be cut into equal-area quadrilaterals. [19]

If a is an algebraic irrational number, then T(a) is a trickier case. If a is algebraic of degree 2 or 3 (quadratic or cubic), and its conjugates all have positive real parts, then S(T(a)) contains all sufficiently large n such that n/(1 + a) is an algebraic integer. [20] It is conjectured that a similar condition involving stable polynomials may determine whether or not the spectrum is empty for algebraic numbers a of all degrees. [21]

History

The idea of an equidissection seems like the kind of elementary geometric concept that should be quite old. Aigner & Ziegler (2010) remark of Monsky's theorem, "one could have guessed that surely the answer must have been known for a long time (if not to the Greeks)." [22] But the study of equidissections did not begin until 1965, when Fred Richman was preparing a master's degree exam at New Mexico State University.

Monsky's theorem

Richman wanted to include a question on geometry in the exam, and he noticed that it was difficult to find (what is now called) an odd equidissection of a square. Richman proved to himself that it was impossible for 3 or 5, that the existence of an n-equidissection implies the existence of an (n + 2)-dissection, and that certain quadrilaterals arbitrarily close to being squares have odd equidissections. [23] However, he did not solve the general problem of odd equidissections of squares, and he left it off the exam. Richman's friend John Thomas became interested in the problem; in his recollection,

"Everyone to whom the problem was put (myself included) said something like 'that is not my area but the question surely must have been considered and the answer is probably well known.' Some thought they had seen it, but could not remember where. I was interested because it reminded me of Sperner's Lemma in topology, which has a clever odd-even proof." [24]

Thomas proved that an odd equidissection was impossible if the coordinates of the vertices are rational numbers with odd denominators. He submitted this proof to Mathematics Magazine , but it was put on hold:

"The referee's reaction was predictable. He thought the problem might be fairly easy (although he could not solve it) and was possibly well-known (although he could find no reference to it)." [25]

The question was instead given as an Advanced Problem in the American Mathematical Monthly ( Richman & Thomas 1967 ). When nobody else submitted a solution, the proof was published in Mathematics Magazine( Thomas 1968 ), three years after it was written. Monsky (1970) then built on Thomas' argument to prove that there are no odd equidissections of a square, without any rationality assumptions. [25]

Monsky's proof relies on two pillars: a combinatorial result that generalizes Sperner's lemma and an algebraic result, the existence of a 2-adic valuation on the real numbers. A clever coloring of the plane then implies that in all dissections of the square, at least one triangle has an area with what amounts to an even denominator, and therefore all equidissections must be even. The essence of the argument is found already in Thomas (1968), but Monsky (1970) was the first to use a 2-adic valuation to cover dissections with arbitrary coordinates. [26]

Generalizations

The first generalization of Monsky's theorem was Mead (1979), who proved that the spectrum of an n-dimensional cube is . The proof is revisited by Bekker & Netsvetaev (1998).

Generalization to regular polygons arrived in 1985, during a geometry seminar run by G. D. Chakerian at UC Davis. Elaine Kasimatis, a graduate student, "was looking for some algebraic topic she could slip into" the seminar. [6] Sherman Stein suggested dissections of the square and the cube: "a topic that Chakerian grudgingly admitted was geometric." [6] After her talk, Stein asked about regular pentagons. Kasimatis answered with Kasimatis (1989), proving that for n > 5, the spectrum of a regular n-gon is . Her proof builds on Monsky's proof, extending the p-adic valuation to the complex numbers for each prime divisor of n and applying some elementary results from the theory of cyclotomic fields. It is also the first proof to explicitly use an affine transformation to set up a convenient coordinate system. [27] Kasimatis & Stein (1990) then framed the problem of finding the spectrum of a general polygon, introducing the terms spectrum and principal. [6] They proved that almost all polygons lack equidissections, and that not all polygons are principal. [2]

Kasimatis & Stein (1990) began the study of the spectra of two particular generalizations of squares: trapezoids and kites. Trapezoids have been further studied by Jepsen (1996), Monsky (1996), and Jepsen & Monsky (2008). Kites have been further studied by Jepsen, Sedberry & Hoyer (2009). General quadrilaterals have been studied in Su & Ding (2003). Several papers have been authored at Hebei Normal University, chiefly by Professor Ding Ren and his students Du Yatao and Su Zhanjun. [28]

Attempting to generalize the results for regular n-gons for even n, Stein (1989) conjectured that no centrally symmetric polygon has an odd equidissection, and he proved the n = 6 and n = 8 cases. The full conjecture was proved by Monsky (1990). A decade later, Stein made what he describes as "a surprising breakthrough", conjecturing that no polyomino has an odd equidissection. He proved the result of a polyomino with an odd number of squares in Stein (1999). The full conjecture was proved when Praton (2002) treated the even case.

The topic of equidissections has recently been popularized by treatments in The Mathematical Intelligencer ( Stein 2004 ), a volume of the Carus Mathematical Monographs ( Stein & Szabó 2008 ), and the fourth edition of Proofs from THE BOOK ( Aigner & Ziegler 2010 ).

Sakai, Nara & Urrutia (2005) consider a variation of the problem: Given a convex polygon K, how much of its area can be covered by n non-overlapping triangles of equal area inside K? The ratio of the area of the best possible coverage to the area of K is denoted tn(K). If K has an n-equidissection, then tn(K) = 1; otherwise it is less than 1. The authors show that for a quadrilateral K, tn(K) ≥ 4n/(4n + 1), with t2(K) = 8/9 if and only if K is affinely congruent to the trapezoid T(2/3). For a pentagon, t2(K) ≥ 2/3, t3(K) ≥ 3/4, and tn(K) ≥ 2n/(2n + 1) for n ≥ 5.

Günter M. Ziegler asked the converse problem in 2003: Given a dissection of the whole of a polygon into n triangles, how close can the triangle areas be to equal? In particular, what is the smallest possible difference between the areas of the smallest and largest triangles? Let the smallest difference be M(n) for a square and M(a, n) for the trapezoid T(a). Then M(n) is 0 for even n and greater than 0 for odd n. Mansow (2003) gave the asymptotic upper bound M(n) = O(1/n2) (see Big O notation). [29] Schulze (2011) improves the bound to M(n) = O(1/n3) with a better dissection, and he proves that there exist values of a for which M(a, n) decreases arbitrarily quickly. Labbé, Rote & Ziegler (2018) obtain a superpolynomial upper bound, derived from an explicit construction that uses the Thue–Morse sequence.

Related Research Articles

<span class="mw-page-title-main">Kite (geometry)</span> Quadrilateral symmetric across a diagonal

In Euclidean geometry, a kite is a quadrilateral with reflection symmetry across a diagonal. Because of this symmetry, a kite has two equal angles and two pairs of adjacent equal-length sides. Kites are also known as deltoids, but the word deltoid may also refer to a deltoid curve, an unrelated geometric object sometimes studied in connection with quadrilaterals. A kite may also be called a dart, particularly if it is not convex.

In mathematics, a presentation is one method of specifying a group. A presentation of a group G comprises a set S of generators—so that every element of the group can be written as a product of powers of some of these generators—and a set R of relations among those generators. We then say G has presentation

In Riemannian geometry, the sectional curvature is one of the ways to describe the curvature of Riemannian manifolds. The sectional curvature K(σp) depends on a two-dimensional linear subspace σp of the tangent space at a point p of the manifold. It can be defined geometrically as the Gaussian curvature of the surface which has the plane σp as a tangent plane at p, obtained from geodesics which start at p in the directions of σp. The sectional curvature is a real-valued function on the 2-Grassmannian bundle over the manifold.

<span class="mw-page-title-main">Sperner's lemma</span> Theorem on triangulation graph colorings

In mathematics, Sperner's lemma is a combinatorial result on colorings of triangulations, analogous to the Brouwer fixed point theorem, which is equivalent to it. It states that every Sperner coloring of a triangulation of an -dimensional simplex contains a cell whose vertices all have different colors.

<span class="mw-page-title-main">Sphenocorona</span> 86th Johnson solid (14 faces)

In geometry, the sphenocorona is a Johnson solid with 12 equilateral triangles and 2 squares as its faces.

In geometry, a dissection problem is the problem of partitioning a geometric figure into smaller pieces that may be rearranged into a new figure of equal content. In this context, the partitioning is called simply a dissection. It is usually required that the dissection use only a finite number of pieces. Additionally, to avoid set-theoretic issues related to the Banach–Tarski paradox and Tarski's circle-squaring problem, the pieces are typically required to be well-behaved. For instance, they may be restricted to being the closures of disjoint open sets.

In mathematics, a Witt group of a field, named after Ernst Witt, is an abelian group whose elements are represented by symmetric bilinear forms over the field.

Geometry is a branch of mathematics concerned with questions of shape, size, relative position of figures, and the properties of space. Geometry is one of the oldest mathematical sciences.

In mathematics, a Pfister form is a particular kind of quadratic form, introduced by Albrecht Pfister in 1965. In what follows, quadratic forms are considered over a field F of characteristic not 2. For a natural number n, an n-fold Pfister form over F is a quadratic form of dimension 2n that can be written as a tensor product of quadratic forms

In mathematics, the Bolza surface, alternatively, complex algebraic Bolza curve, is a compact Riemann surface of genus with the highest possible order of the conformal automorphism group in this genus, namely of order 48. The full automorphism group is the semi-direct product of order 96. An affine model for the Bolza surface can be obtained as the locus of the equation

<span class="mw-page-title-main">Pythagorean theorem</span> Relation between sides of a right triangle

In mathematics, the Pythagorean theorem or Pythagoras' theorem is a fundamental relation in Euclidean geometry between the three sides of a right triangle. It states that the area of the square whose side is the hypotenuse is equal to the sum of the areas of the squares on the other two sides.

<span class="mw-page-title-main">Inscribed square problem</span> Unsolved problem about inscribing a square in a Jordan curve

The inscribed square problem, also known as the square peg problem or the Toeplitz' conjecture, is an unsolved question in geometry: Does every plane simple closed curve contain all four vertices of some square? This is true if the curve is convex or piecewise smooth and in other special cases. The problem was proposed by Otto Toeplitz in 1911. Some early positive results were obtained by Arnold Emch and Lev Schnirelmann. The general case remains open.

<span class="mw-page-title-main">Rep-tile</span> Shape subdivided into copies of itself

In the geometry of tessellations, a rep-tile or reptile is a shape that can be dissected into smaller copies of the same shape. The term was coined as a pun on animal reptiles by recreational mathematician Solomon W. Golomb and popularized by Martin Gardner in his "Mathematical Games" column in the May 1963 issue of Scientific American. In 2012 a generalization of rep-tiles called self-tiling tile sets was introduced by Lee Sallows in Mathematics Magazine.

<span class="mw-page-title-main">Biggest little polygon</span>

In geometry, the biggest little polygon for a number n is the n-sided polygon that has diameter one and that has the largest area among all diameter-one n-gons. One non-unique solution when n = 4 is a square, and the solution is a regular polygon when n is an odd number, but the solution is irregular otherwise.

In geometry, Monsky's theorem states that it is not possible to dissect a square into an odd number of triangles of equal area. In other words, a square does not have an odd equidissection.

In geometry, an affine-regular polygon or affinely regular polygon is a polygon that is related to a regular polygon by an affine transformation. Affine transformations include translations, uniform and non-uniform scaling, reflections, rotations, shears, and other similarities and some, but not all linear maps.

<span class="mw-page-title-main">Zonogon</span> Convex polygon with pairs of equal, parallel sides

In geometry, a zonogon is a centrally-symmetric, convex polygon. Equivalently, it is a convex polygon whose sides can be grouped into parallel pairs with equal lengths and opposite orientations.

Sherman Kopald Stein is an American mathematician and an author of mathematics textbooks. He is a professor emeritus at the University of California, Davis. His writings have won the Lester R. Ford Award and the Beckenbach Book Prize.

Algebra and Tiling: Homomorphisms in the Service of Geometry is a mathematics textbook on the use of group theory to answer questions about tessellations and higher dimensional honeycombs, partitions of the Euclidean plane or higher-dimensional spaces into congruent tiles. It was written by Sherman K. Stein and Sándor Szabó, and published by the Mathematical Association of America as volume 25 of their Carus Mathematical Monographs series in 1994. It won the 1998 Beckenbach Book Prize, and was reprinted in paperback in 2008.

Elaine Ann Kasimatis was an American mathematician specializing in discrete geometry and mathematics education. She was a professor in the Department of Mathematics & Statistics at California State University, Sacramento.

References

  1. 1 2 Monsky 1970.
  2. 1 2 3 4 Kasimatis & Stein 1990.
  3. ↑ Stein 2004.
  4. ↑ Stein & Szabó 2008, pp. 108–109.
  5. 1 2 Stein 2004, p. 17.
  6. 1 2 3 4 Stein & Szabó 2008, p. 120.
  7. ↑ Schulze 2011.
  8. ↑ Mead 1979, p. 302.
  9. ↑ Stein & Szabó 2008, p. 126.
  10. ↑ Stein & Szabó 2008, pp. 121, 128, 131.
  11. ↑ Stein 2004, pp. 12–20.
  12. ↑ Monsky 1990; Praton 2002
  13. ↑ Stein 2004, p. 20.
  14. ↑ Kasimatis 1989.
  15. ↑ Mead 1979.
  16. ↑ Stein & Szabó 2008, p. 122.
  17. ↑ Su & Ding 2003.
  18. ↑ See Su & Ding (2003) for more precise statements of this principle.
  19. ↑ Hales & Straus 1982, p. 42.
  20. ↑ Jepsen & Monsky 2008.
  21. ↑ Stein 2004 , p. 21; Jepsen & Monsky 2008 , p. 3
  22. ↑ Aigner & Ziegler 2010, p. 131.
  23. ↑ Thomas 1968, p. 187.
  24. ↑ Stein & Szabó 2008, p. 107.
  25. 1 2 Stein & Szabó 2008, p. 108.
  26. ↑ Monsky 1970 , p. 251; Bekker & Netsvetaev 1998 , p. 3492
  27. ↑ Stein 2004, p. 18.
  28. ↑ Su & Ding 2003; Du & Ding 2005
  29. ↑ Schulze 2011, p. 2.

Bibliography

Secondary sources
Primary sources
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.