Largest Small Polytopes: New Solutions in Combinatorial Geometry

Original author: Ed Pegg Jr
  • Transfer

Ed Pegg Jr. post translation " Biggest Little Polyhedron — New Solutions in Combinatorial Geometry ".
You can download the file containing the text of the article, interactive models of the polyhedra, and the code provided in the article here .
I express my deep gratitude to Kirill Guzenko for help with the translation.

In many areas of mathematics, the answer is 1 . Squaring a non-negative number into a square that is greater or less than one will give a larger or smaller number, respectively. Sometimes, in order to determine if something is “large”, it is necessary to find out whether the unit is larger than the largest size of this object. For example, the giant hexagon of Saturn with a side length of 13,800 km could be attributed to large. A “small polygon" is one with a maximum distance between vertices of unity . In 1975, Ron Graham discovered the largest small hexagon., which, as shown below, has a larger area than that of a regular hexagon. Red diagonals have a unit length. All other (non-conducted) diagonals are shorter.

Regular hexagon, biggest little hexagon, biggest little octagon showing lengths of 1

I always wondered what the largest small polyhedron would look like. In Mathematica 10 new functional object was presented to the Volume [ ConvexHullMesh [points]] , and I thought that might solve this problem by choosing a random point. Below is the code for selecting, calculating and visualizing a random small polyhedron. Scrolling this code thousands of times, you can get a good approximation in the best of the results. Here, here I ran the code three times. One of the results is probably better than the rest.

Random solutions for picking points on a polyhedron

The image below shows the best solutions that were obtained through randomly selected points. I posted this in the Wolfram Community in the discussion of the largest small polyhedron (hereinafter - HMM) and received some useful comments from Robin Houston and Todd Roland. To find solutions, I decided to use the results of " visualization of the Thompson problem ." In the Thomson problem, electrons repel each other on a sphere. 12 points that repel each other tend to the vertices of the icosahedron, which is not effective for HMMs, since the greatest distances pass through the center of the sphere, as well as for regular hexagons in the two-dimensional case. I changed the code for the Thompson problem so that the points bounced off each other and from all the opposite ones, and this gave a good initial value.

Starting values ​​using modified Thomson code

For four points, the solution is the correct tetrahedron with volume / 12 = 0.117851.

For five points, the solution is an equilateral triangle with unit lengths of sides and a unit perpendicular to this triangle, and the volume is equal to / 12 = 0.1443375; this decision was received in 1976 [1].

Regular tetrahedron and equilateral triangle points

I will use the term 6-NMM to denote the largest small six-point polyhedron. In 2003, the 6-NMM volume was calculated with an accuracy of four digits [2,3]. Below are 6-NMM and 7-NMM; single diagonals are highlighted in red.

6-BLP and 7-BLP

In order to find them myself, first I selected the best options from more than a thousand, and then I used an annealing simulation algorithm(simulated annealing) (probabilistic task of finding a good approximation to the global optimum of a given function in a wide search space - approx. per.) to improve the results. For each of the points of optimal solutions, I went over the space around these points to find the best solution, not shifting them much. Then I further reduced the search space, and so on from time to time. Some of the solutions seemed to strive for mutual symmetry. For example, for seven points, the best solution sought this polyhedron with an r value of about half, which represents the relative size of the upper triangle △ 456.

Symmetrical solution for random polyhedron with seven points

The exact volume can be obtained through the tetrahedron, which is determined through the points {{2,3,4,7}, {2,4,6,7}, {5,4,7,6}}, and the volume of the first two should be tripled from symmetry considerations. Look at the volumes of the tetrahedrons, and replace any pair of numbers in the tetrahedron so that you get a negative volume.

Determining the exact volume of the tetrahedra by defined points

After we have changed the ratio in the last tetrahedron, we can calculate the exact value of r , which will give an accurate and optimal volume. We will use the same method for other cases.

Calculating r for solution6, solution7, solution8, solution9

The 16-NMM solution takes more than a minute, so I had to break it down.

Solution for 16-BLP

The first value in solutions is the optimal volume, is the object of Root , and the second is the optimal value of r . Now, this table will be more careful.

Table of values ​​for optimal value of r

And this is far beyond what I could have done manually. Using a random selection of points, an annealing simulation algorithm, symmetry search, Solve [] and Maximize [], I was able to find the exact values ​​of the volumes of n-HMMs (largest small polytopes) for n = 6, 7, 8, 9 and 16.

View 8- HMM from several sides, where single diagonals are highlighted in red.

Views of the 8-BLP with the red tubes showing unit-length diagonals

View 9-HMM from several sides:

Views of 9-BLP with the red tubes showing unit-length diagonals

View 16-HMM from several sides:

Views of 16-BLP with the red tubes showing unit-length diagonals

The following 8-HMM contains single perpendiculars 1-2 and 3-4 above and below the base, respectively. The 9-NMM shown below contains triangles △ 123, △ 456, and △ 789.

8-BLP featuring perpendicular line units and 9-BLP featuring stacked triangles

The 16-NMM below is a truncated tetrahedron consisting of points 1-12 with additional points 13-16.

16-BLP featuring a truncated tetrahedron

Pretty complicated, isn't it? Using the method of choosing points on a sphere , random numbers in the intervals [–Pi; Pi] and [–1; 1] on a unit sphere, you can specify a uniform distribution of points. Points on a unit sphere can be mapped back to points in the rectangle [–Pi; Pi] x [–1; 1]. This is what will happen for solutions 8,9,16-NMM.

Sphere point picking for solutions with 8, 9, and 16 points

For 10-NMM, I could not find the exact solution, but I can present a numerical solution with any degree of accuracy. Contact me if you have any idea how to find the root object here. In the executable version of this article on Wolfram Language in the initialization section you can find this very difficult expression.

10-BLP equation

Here are two types of 10-NMM from two different viewpoints.

Two different perspectives of the labeled view of 10-BLP

A numerical solution for 11-NMM can be found in a similar way.

11-BLP equation

View 11-NMM from two sides:

Two views of 11-BLP

Did I really get the right decisions? Maybe not. For these symmetries, I am sure that I found a local maximum . For example, here is a function with a local maximum of 5 at a value of 1.

Plot showing found local maximum of 5

And if you look a little further in the chart, you can find a global maximum of 32 at a value of -2.

Plot showing found global maximum of 32

In a similar Thompson problem, there is proof for 12 vertices of the icosahedron, in which a system of 12 electrons is at a potential minimum. But for 7, 8, 9, 10, 11, and 13+ electrons, the problem is considered unsolved. The Kepler conjecture is assumed that the hexagonal close packing has the densest packing for spheres, butrigorous evidence was obtained by Thomas Hales only on August 10, 2014. The densest packaging for regular tetrahedra - with the ratio 4000/4671 = 0.856347 ... - was opened only on July 27, 2010, but still has no rigorous proof. Any statements about the solution found should be taken with a certain degree of skepticism; geometric maximization problems are known to be very complex.

For several months, my best solution for 11 points was at a local maximum corresponding to an asymmetric HMM. Some (or most) of these solutions are most likely local, not global, but which ones? With this reservation, you can look at the most famous solutions for 12 or more points.

12-NMM has a vertex at point 12 and contains an irregular heptagon 11-6-7-10-8-5-9 and a quadrangle 1-4-3-2.

13-NMM has a vertex at point 13 and contains an irregular heptagon 12-8-10-6-7-9-11 and the same pentagon 1-2-3-4-5.

My attempts to add symmetry led to figures with a smaller volume.

12-BLP and 13-BLP

In theory, the solutions for 14-NMM should be very symmetrical, but I still haven’t succeeded. I spent some time optimizing the vertex-pentagon-pentagon system for 15-NMM, however, using the random point method, I got the best solution in which the symmetry was sacrificed to the volume.

14-BLP and 15-BLP

17-NMM, 18-NMM - I hope that in the first everything is in order with symmetry.

As for the 19-NMM and the 20-NMM, the 20-NMM is not a dodecahedron, since unit lines from the center are not the best option.

Symmetry for 17-BLP, 18-BLP, 19-BLP, and 20-BLP

Both the snub cube and half of the huge rhombocuboctahedron all have a smaller volume than 24-NMM.

Snub cube and half the vertices of the great rhombicuboctahedron have lower volume than 24-BLP

21-NMM and 22-NMM contain many seven- and nine-pointed stars.

23-NMM, 24-NMM - my best 24-NMM has tetrahedral symmetry.

21-BLP, 22-BLP, 23-BLP, 24-BLP symmetry

Here are some symmetries in the current best 24-NMM. Segments 1-12 and 13-24 have corresponding lengths of 0.512593 and 0.515168.

Symmetry in the current best 24-BLP

In 16-NMM and 17-NMM, unit segments define polygons. 16-NMM contains many seven-pointed stars.

16-BLP contains 7-pointed stars

Below are the same polyhedra presented as solid bodies by means of ConvexHullMesh[], for NMM 9-10-11-12, 13-14-15-16, 17-18-19-20, 21-22-23-24, respectively.

Polyhedra shown as solid objects using ConvexHullMesh

Here is a table of the best known values ​​at this time.

Current table of best known values

Here are the best solutions that I have found so far for 4-24 points.

Best solutions for 4 to 24 points

Let the points be located so that the maximum distance from the origin is as small as possible. The distribution presented below indicates the distances from the origin to the vertices of each polyhedron, in each of which from 8 to 24 vertices.

Distance from origin for vertices scatterplot

Using Mathematica10.1 succeeded in obtaining the exact values ​​for 6,7,8,9-NMM and 16-NMM. Also, with its help, very accurate, but numerical values ​​for 10-NMM and 11-NMM were found and managed to seriously advance with 24-NMM. Thus, we obtained solutions to seven previously unsolved problems in combinatorial geometry - all thanks to the combination Volume [ ConvexHullMesh [points]] . And what innovations in Mathematica 10 helped you personally?

List of references


[1] B. Kind and P. Kleinschmidt, “On the Maximal Volume of Convex Bodies with Few Vertices,” Journal of Combinatorial Theory , Series A, 21 (1) 1976 pp. 124-128.
doi: 10.1016 / 0097-3165 (76) 90056-X
[2] A. Klein and M. Wessler, “The Largest Small n-dimensional Polytope with n + 3 Vertices,” Journal of Combinatorial Theory , Series A, 102 (2 ), 2003 pp. 401-409.
doi: 10.1016 / S0097-3165 (03) 00054-2
[3] A. Klein and M. Wessler, “A Correction to 'The Largest Small n-dimensional Polytope with n + 3 Vertices,'” Journal of Combinatorial Theory , Series A, 112 (1), 2005 pp. 173-174.
doi: 10.1016 / j.jcta.2005.06.06.001

Also popular now: