Monday, August 24, 2015

Discovery of New Pentagonal Tiling With Computer

The problem: A Tiling of the plane


Motto: "The book of nature is written in the characters of geometryGalileo Galilei.

Note: Such concepts, forms and methods can be inspirational teachers to introduce these issues in textbooks and in preparing students in math. As always, the math (and informatics/computer science ) was developed to solve the problems in practice and in human life.
(In Romanian: Astfel de concepte, forme și metode pot fi inspirație pentru profesori care să introducă aceste aspecte în manuale și în pregătirea elevilor la matematică. Dintotdeauna, matematica (și informatica) s-au dezvoltat pentru rezolvarea problemelor din practică și din viața omului).

In Romanian: Dacă în domenii ca fizica, chimia, etc., multe descoperiri științifice au la bază experimentele științifice, iată că metodele informatice cu ajutorul calculatorului pot fi instrumente puternice și eficiente pentru experimentare și demonstrații. Ca exemple, se pot da rezolvările pentru următoarele probleme: problema celor 4 culori (anul 1977), problemă de combinatorică ce se află la baza metodei backtracking (metodă din inteligența artificială); programul inteligent pentru jocul de șah (înfrângerea istorică a campionului rus Gari Kasparov, în faţa lui Deep Blue, din mai 1997, la New York) ce a învins omul; definitivarea secvențelor pentru genomul uman-codul ADN (2005).


Tuesday 11 August, 2015, "Joy as mathematicians discover a new type of pentagon that can cover the plane leaving no gaps and with no overlaps. It becomes only the 15th type of pentagon known that can do this, and the first discovered in 30 years" - http://www.theguardian.com  
August 14, 2015, Washington, "A research team in the University of Washington Bothell School of Science, Technology, Engineering and Mathematics has become a part of math history. Using a computer program written by an undergraduate student on the team, they discovered the 15th kind of pentagon that can tile a plane." - http://www.uwb.edu/news/press/2015/081415  
August 15, 2015, Mike James, "But the pentagon is something else. The five fold symmetry of a regular pentagon is slightly irritating. You can't tile the plane with a regular pentagon because its internal angle is 108 degrees which is not a divisor of 360 degrees. You can also prove that a pentagon cannot be part of any tiling that involves any mix of regular pentagons." - http://www.i-programmer.info/news [Source of Image, by Casey Mann: http://www.npr.org/]

The problem of classifying convex pentagons that tile the plane is a beautiful mathematical problem that is simple enough to state so that children can understand it, yet the solution to the problem has eluded us for over 100 years. The problem also has a rich history, connecting back to the 18th of David Hilbert’s (1862-1943) famous 23 problems (http://www.clarku.edu/~djoyce/hilbert/).
"Most math teachers know that the best way for students to improve at mathematics is for them to regularly practice solving mathematical problems. The challenge that teachers face is how to make practicing the same activity again and again, always seem new, interesting and engaging to students. One technique is to integrate educational games and puzzles into their lessons - provided the games are carefully chosen, students can learn while having fun. Casino games such as blackjack, poker and roulette are a great way to help students calculate simple math; more advance students can discuss the odds and probability of the game." - www.mathpuzzle.com.

Concepts of Tilings and Tessellations


Definition 1. If you can cover a flat surface using only identical copies of the same shape leaving neither gaps nor overlaps, then that shape is said to tile the plane.  
Definition 2. When you fit individual tiles together with no gaps or overlaps to fill a flat space like a ceiling, wall, or floor, you have a tiling. You can imagine that you can use a variety of shapes to do this. (http://mathforum.org/sum95/suzanne/whattile.html) [10].   
Definition 3. A Tessellation is created when a shape is repeated over and over again covering a plane without any gaps or overlaps. (http://mathforum.org/sum95/suzanne/whattess.html) [11, 20].  
Definition 4. A tiling is a partition of an infinite space (usually Euclidean) into pieces having a finite number of distinct shapes. Tilings can be divided into two types, periodic and aperiodic, depending on whether they have any translational symmetries. If these symmetries exist, they form a lattice. However there has been much recent research and excitement on aperiodic tilings (which lack such symmetries) and their possible realization in certain crystal structures. Tilings also have connections to much of pure mathematics including operator K-theory, dynamical systems, and non-commutative geometry - http://www.ics.uci.edu/~eppstein/ [15].

Another word for a tessellation is a tiling. A dictionary will tell you that the word "tessellate" means to form or arrange small squares in a checkered or mosaic pattern. The word "tessellate" is derived from the Ionic version of the Greek word "tesseres," which in English means "four."

The first tilings were made from square tiles.
Things get interesting with pentagons. The regular pentagon cannot tile the plane. But some non-regular pentagons can. Study of pentagonal tilings is interesting also because of its potential applications. Many structures that we see in nature, from crystals to viruses, are comprised of building blocks that are forced by geometry and other dynamics to fit together to form the larger scale structure. The researchers say that the new type of pentagon will have practical applications in many fields, including construction, biochemistry and structural design. (https://en.wikipedia.org/wiki/Pentagonal_tiling) - Source of image: Livio Zucca [17].

Research Findings (http://www.mathpuzzle.com/tilepent.html, http://demonstrations.wolfram.com/PentagonTilings/) [7, 9]:
  • The hunt to find and classify the pentagons that can tile the plane has been a century-long mathematical quest, begun by the German mathematician Karl Reinhardt, who in 1918 discovered five types of pentagon that do tile the plane.
  • Most people assumed Reinhardt had the complete list until half a century later in 1968 when R. B. Kershner found three more. This was the complete list until 1968, when Richard Kershner wrote about three more families of tiling pentagons (6-8).
  • Martin Gardner wrote about the complete list of eight tiling pentagons in 1975, and then got a message from Richard James III about another type (10).
  • Martin updated the readers of Mathematical Games, but then got a message from a housewife with no mathematical training, Marjorie Rice, who found four more families of tiling pentagons, in 1976-1977 (9, 11-13).
  • In 1985, Rolf Stein found a 14th convex pentagon that can tile the plane.
  • On July 29, 2015, a 15th type was announced by Professors Casey Mann, Jennifer McLoud-Mann, and MSc researcher David Von Derau.
Types 1-5 were found by K. Reinhardt in 1918. Types 6-8 were found by R. B. Kershner in 1968. Type 10 was found R. James in 1975. Types 9, 11-13 were found by M. Rice in 1976-1977. Type 14 was found by R. Stein in 1985. Type 15 was found by C. Mann, J. McLoud-Mann, and D. Von Derau in 2015.

About Tilings and Tessellations - Applications

"I have long had a love of nature, drawing, the patterns found in nature and their mathematical relationships. It was 1975 when I first entered the world of tessellations. Reading an article by Martin Gardner in my son's Scientific American sparked an interest in tessellations which continues to this day. It posed the question, were there any new pentagon types that would tile a plane? I found it an intriguing question. I've always enjoyed puzzles and thought maybe there were more types yet to be found. I started out by developing my own notation so that I could systematically approach the problem. Eventually I was rewarded in my search with finding four new types of Pentagons. I am still intrigued by the beautiful patterns of tessellations and it is my desire to share with others who are also intrigued by tessellations. In the connecting pages you will find some of my own work and also links to other pages that deal with tessellation. I hope you enjoy them." Marjorie Rice, https://sites.google.com/site/intriguingtessellations/home/
Marjorie Rice, an amateur mathematician with no training beyond high school, who had discovered the tile used in the background of this page and three others in 1976 and 1977. The entry foyer of the Mathematical Association of America’s building was designed using the congruent pentagons discovered by Marjorie Rice (Source of image: http://cdn.zmescience.com/)

A drone's eye view of the Andrew Wiles Building

The new Andrew Wiles building (housing the Mathematical Institute at the University of Oxford) has Penrose tiling in its courtyard. It's rather nice: https://www.maths.ox.ac.uk/node/14494
(Source of image: https://www.maths.ox.ac.uk/)



Heesch's Problem
The Heesch number of a shape in the plane is the maximum number of times that shape can be completely surrounded by copies of itself. What possible values can this number take? More formally, if one has a tiling of the plane (a collection of disjoint connected open sets the closures of which cover the plane), the first corona of a tile is the set of all tiles that have a common boundary point with the tile, including the original tile itself. The second corona is the set of tiles that share a point with something in the first corona, and so on. The Heesch number of a shape is the maximum value of k for which all tiles in the kth corona of any tiling are congruent to that shape.

The Heesch number of a triangle, quadrilateral, regular hexagon, or any other shape that can tile the plane, is infinity. Conversely, an argument based on the axiom of choice shows that a shape with infinite Heesch number must tile the plane. But the Heesch number of a circle is zero, because it can't even be surrounded once by copies of itself without leaving some uncovered space.

Heesch's Problem asks the following question: How many times can a tile be surrounded by congruent copies of itself? That is, how many layers made of copies of the tile can you place around the tile. The layers are called coronas, and the maximum number of coronas that can surround a tile is called the Heesch number of the tile. So the big question is this: Is there a maximum Heesch number? That is, is there some number N so that when any tile surrounds itself N times, then it must tile the plane? If so, what is N?

"At present, there is not an answer to this question. It has been conjectured by well-known and talented people in the field of tiling theory that there is a maximum (although they cannot say what that maximum is). I have also heard it conjectured that there is no bound on the Heesch number! I am reluctant to make a conjecture myself. But I can say that after Ammann's example was given, many people thought that there would not be another example with higher Heesch number. Heesch's problem has connections to a few well-known unsolved problems -- the domino problem and the "Einstein" problem. The domino problem asks if there exists an algorithm that, when given a prototile as input, decides if the prototile can be used tile the entire plane. If the Heesch number is in fact bounded, this gives a simple algorithm for deciding if a prototile can be used to tile the plane." Casey Mann [18].
Sorce of image: Heesch number 4 example (First discovered by W.R. Marshall, and later Casey Mann) [18] - http://math.uttyler.edu/cmann/. Heesch's Problem, http://www.ics.uci.edu/~eppstein/ [15]

The Hirschhorn Medallion by Bob Jenkins

"I got started on this because I saw an article in the paper about Marjorie Rice, an amateur mathematician with no training beyond high school, who had discovered the tile used in the background of this page and three others in 1976 and 1977. She used the same search strategy I'm using, but by hand. At any rate, I thought, "I can do that", so I did. (Thanks to H. Nelson Miller for refreshing my memory on the details. Martin Gardner's "Time Travel and Other Mathematical Bewilderments" covers Marjorie Rice.)" Bob Jenkins, http://burtleburtle.net/.


The New Pentagonal Tiling - 2015


In July Professors Casey Mann, Jennifer McLoud and Undergraduate student David Von Derau of the University of Washington Bothell announced that they discovered the 15th kind of pentagon that can tile a plane.
The nonregular pentagons with the angles pointing outward, that can "tile the plane": angles A=60, B=135, C=105, D=90, E=150 and a = 2b = (√6 - √2)c = 2d = 2e (Image by Prof. Casey Mann).
Using a computer program written by an undergraduate student on the team, they discovered the 15th kind of pentagon that can tile a plane. The pentagon tiles are all identical. The colouring shows how they tile the plane when arranged in identical groups of three (Illustration: Prof. Casey Mann).

There are now 15 known convex pentagons, or nonregular pentagons with the angles pointing outward, that can "tile the plane."

Monohedral convex pentagonal tilings [19]:
• Reinhardt (1918) - pentagon type 1-5
• Kershner (1968) and James (1975) - pentagon  type 6-8 and  pentagon type 10
• Rice (1977) -  pentagon type 9,11-3
• Stein (1985) and Mann/McLoud/Von Derau (2015) -  pentagon type 14,15.

Source of image: Ed Pegg Jr, "Pentagon Tilings", Wolfram Demonstrations Project, http://demonstrations.wolfram.com/PentagonTilings/. See and Coding new pentagon tiling by Ed Pegg Jr (Groups: Mathematics, Geometry, Graphics and Visualization, Wolfram Language). "With all the interest in pentagons, I figured I should make a Demonstration for tetratoid pentagons, where twelve irregular pentagons can make a polyhedron. But I haven't found the intersection between tetratoid pentagons and tiling pentagons. What sort of image can you make from these or other pentagons?" - http://community.wolfram.com/groups/-/m/t/550169.
Images suggestive of a demonstrative animation is at adress: http://imgur.com/gallery/gjSJx [22].

About this discovery

If you think that such major problems are solved by teams of scientists working directly on them, then you have no clue how science works. It's small, seemingly unconnected discoveries that eventually add to the tool box that engineers and scientists have to form solutions to major problems. Think about a smart phone...do you think some scientists in a lab "discovered" the smart phone? No, they took decades of applied science in many fields and put it all together to create the phone. Each little piece was necessary to the overall work of making a smart phone, all results of lots of research in all kinds of fields. That is how science and engineering works” comment by Keln, Columbus, United States [3].
In my experience in academia I have seen many different types of people. There are math brains really good at diving deeper and deeper into things like this, but impact on sciences are questionable. On the other hand there are people who are really creative, and come up with excellent solutions for everyday problems but they lack theoretical background. I prefer the latter because theoretical brains are the least creative and never see the big picture of problems. Mathematics is a tool that explains the nature of things, but sometimes problems we have not always mathematically expressed.” comment by H Poirot, London, United Kingdom [3].

REFERENCES 
  1. "Undergraduate student writes computer program to speed up the discovery process", The University of Washington Bothell School of Science, Technology, Engineering and Mathematics, Press Releases, http://www.uwb.edu/news/press/2015/081415
  2. Alex Bellos, Attack on the pentagon results in discovery of new mathematical tile, 11 august 2015, http://www.theguardian.com
  3. Ellie Zolfagharifard, Mathematicians find new 'perfect shape' that solves one of their most complex problems, http://www.dailymail.co.uk/
  4. Mike James, Computer Finds New Pentagonal Tiling - With Some Human Help, 15 August 2015, http://www.i-programmer.info/news/ 
  5. David E. Joyce, Mathematical Problems By Professor David Hilbert (International Congress of Mathematicians at Paris in 1900), http://www.clarku.edu/~djoyce/hilbert/
  6. Eyder Peralta, With Discovery, 3 Scientists Chip Away At An Unsolvable Math Problem, 14 August 2015, http://www.npr.org/
  7. Ed Pegg Jr, "Pentagon Tilings", Wolfram Demonstrations Project, http://demonstrations.wolfram.com/
  8. Ed Pegg Jr, "Pentagon Tilings", http://www.wolframalpha.com/
  9. Ed Pegg Jr, Material added on Martin Gardner's Centerary, www.mathpuzzle.com
  10. Suzanne Alejandre, What Is a Tiling, Drexel University, http://mathforum.org/l
  11. Suzanne Alejandre, What Is a Tessellation?, Drexel University, http://mathforum.org/
  12. Suzanne Alejandre, Tilings and Tessellations , Drexel University, http://www.scienceu.com/
  13. Marjorie Rice, https://sites.google.com/
  14. Bob Jenkins, http://burtleburtle.net/
  15. David Eppstein, Geometry Junkyard, computational and recreational geometry pointers, Theory Group, ICS, UC Irvine, http://www.ics.uci.edu/~eppstein/, http://www.ics.uci.edu/~eppstein/junkyard/heesch/
  16. Jaap Scherphuis, http://www.jaapsch.net/
  17. Livio Zucca, Equilateral Pentagons. That Tile The Plane And Their Different Tilings, http://web.archive.org/
  18. Casey Mann, Heesch's Problem, http://math.uttyler.edu/cmann/
  19. Pentagonal tiling, https://en.wikipedia.org/wiki/Pentagonal_tiling
  20. Tessellation, https://en.wikipedia.org/wiki/Tessellation
  21. Euclidean tilings of convex regular polygons, https://en.wikipedia.org/
  22. Animations Demo, http://imgur.com/gallery/gjSJx