Найбільші малі многогранники: нові рішення в комбінаторної геометрії


Переклад поста Ed Pegg Jr."Biggest Little Багатогранник—New Solutions in Комбінаторної Geometry".
Завантажити файл, що містить текст статті, інтерактивні моделі многогранників і код, наведений у статті, можна тут.
Висловлюю величезну подяку Кирилу Гузенко за допомогу в перекладі.

У багатьох областях математики відповіддю буде одиниця 1. Зведення числа в квадрат, яке більше або менше одиниці, дасть більшу або меншу кількість відповідно. Іноді для того, щоб визначити, чи є щось «великим», необхідно з'ясувати, чи більше одиниці найбільший розмір цього об'єкта. Наприклад, гігантський гексагон Сатурна з довжиною сторони в 13,800 км можна було б віднести до великих. «Малий багатокутник» — це той, у якого максимальна відстань між вершинами дорівнює одиниці. У 1975 році Рон Грем відкрив найбільший малий шестикутник, який, як показано нижче, має більшу площу, ніж у правильного шестикутника. Червоні діагоналі мають одиничну довжину. Всі інші (непроведені) діагоналі мають меншу довжину.

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

Мені завжди було цікаво, як буде виглядати найбільший малий багатогранник. В Mathematica 10 був представлений новий функціональний об'єкт Volume[ConvexHullMesh[points]], і я подумав, що можна було б вирішити цю задачу, вибираючи випадкові точки. Нижче представлений код для вибору, обчислення і візуалізації випадкового малого багатогранника. Тисячі разів прокрутивши цей код можна буде отримати непоганий наближення в кращому результатів. Ось тут я три рази запускав код. Один з результатів, ймовірно, краще за інших.

Random solutions for picking points on a багатогранник

Нижче на зображенні наведено найкращі рішення, які були отримані через випадково вибрані точки. Я виклав це в Wolfram Community в обговоренні найбільший малий багатогранник (далі – НММ) і отримав кілька корисних коментарів від Робіна Х'юстона і Тодда Роланда. Для пошуку рішень я вирішив використовувати результати "візуалізації завдання Томпсона". У задачі Томсона електрони відштовхуються один від одного на сфері. 12 відштовхуються один від одного точок прагнуть до вершин ікосаедра, що не ефективно для НММ, так як найбільші відстані проходять через центр сфери, так само як і для правильних шестикутників в двовимірному випадку. Я змінив код для завдання Томпсона так, що точки відскакували один одного і від усіх, що протилежать, і це дало непогані початкові значення.

Starting values using modified Thomson code

Для правильного тетраедра з обсягом /12= 0.117851 потрібно чотири точки.

Для правильної піраміди з одиничним перпендикуляром потрібно 5 точок, а її обсяг дорівнює /12 = 0.1443375; це рішення було отримано в 1976-му році [1].

Regular tetrahedron and equilateral triangle points

Я буду використовувати термін 6-НММ для позначення найбільшого малого багатогранника з шістьма точками. У 2003-му році обсяг 6-НММ був обчислений з точністю до чотирьох знаків [2,3]. Нижче представлені 6-НММ і 7-НММ, поодинокі діагоналі виділені червоним.

6-BLP and 7-BLP

Для того щоб знайти їх самостійно, спершу я вибрав найкращі варіанти з більш ніж тисячі, а потім використовував алгоритм імітації відпалу (simulated annealing) (імовірнісна задача пошуку хорошого наближення до глобального оптимуму даної функції в широкому просторі пошуку – прим. пер.) для поліпшення результатів. Для кожної з точок оптимальних рішень я перебирав простір навколо цих точок для пошуку кращого рішення, ненабагато їх зміщуючи. Потім я ще більше зменшував простір пошуку, так і з разу в раз. Деякі з рішень, здавалося, прагнуть до взаємної симетричності. Наприклад, для семи точок найкраще рішення прагнуло до цього многограннику зі значенням r близько половини, який представляє відносний розмір верхнього трикутника △456.

Symmetrical solution for random багатогранник with seven points

Точний обсяг можна отримати через тетраедр, який визначається через точки{{2,3,4,7}, {2,4,6,7}, {5,4,7,6}}, а обсяг двох перших слід потроїти з міркувань симетрії. Подивіться на обсяги тетраедрів, і замініть будь-яку пару чисел в тетраэдре так, щоб вийшов негативний обсяг.

Determining the exact volume of the tetrahedra defined by points

Після того, як ми змінили співвідношення в останньому тетраэдре, ми можемо обчислити точне значення r, яке дасть точний і оптимальний обсяг. Цим же методом скористаємося і для інших випадків.

Calculating r for solution6, solution7, solution8, solution9

Рішення для 16-НММ займає більше хвилини, так що мені довелося розбити його.

Solution for 16-BLP

Перше значення у рішеннях — оптимальний обсяг, є об'єктом Root, а друге є оптимальним значенням r. Ось ця таблиця буде акуратніше.

Table of values for optimal value of r

І це далеко за межами того, що я зміг би зробити вручну. За допомогою випадкової вибірки точок, алгоритму моделювання відпалу, пошуку симетрії, Solve [] Maximize[] мені вдалося знайти точні значення обсягів n-НММ (найбільших малих багатогранників) для n = 6, 7, 8, 9 і 16.

Вид 8-НММ з декількох сторін, де червоним виділені поодинокі діагоналі.

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

Вигляд 9-НММ з декількох сторін:

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

Вид 16-НММ з декількох сторін:

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

Зазначений нижче 8-НММ містить одиничні перпендикуляри 1-2 і 3-4 над і під підставою відповідно. Нижче представлений 9-НММ містить трикутники △123, △456 і △789.

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

Наведений нижче 16-НММ являє собою усічений тетраедр, що складається з точок 1-12 з додатковими точками 13-16.

16-BLP featuring a truncated tetrahedron

Досить складно, чи не так? За допомогою методу вибору точок на сфері, випадковими числами в проміжках [–P; P] і [-1; 1] на одиничній сфері можна задати рівномірний розподіл точок. Точки на одиничній сфері можуть бути відображені назад до точки в прямокутнику [–Pi; Pi]x[-1; 1]. Ось, що відбудеться для рішень 8,9,16-НММ.

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

Для 10-НММ мені не вдалося знайти точне рішення, проте я можу уявити чисельне рішення з будь-яким ступенем точності. Зв'яжіться зі мною, якщо у Вас є здогади, як тут знайти root object. У виконуваній версії цієї статті на Wolfram Language в розділі ініціалізації можна знайти це дуже нелегка вираз.

10-BLP equation

Тут представлені два види 10-НММ з двох різних точок огляду.

Two different perspectives of the labeled view of 10-BLP

Чисельне рішення для 11-НММ можна знайти схожим чином.

11-BLP equation

Вид 11-НММ з двох сторін:

views of Two 11-BLP

Дійсно я отримав правильні рішення? Може бути і немає. Для цих симетрій я впевнений, що я знайшов локальний максимум. Наприклад, ось функція з локальним максимумом 5 при значенні 1.

Plot showing found local maximum of 5

А якщо заглянути в графіку трохи далі, то можна буде знайти глобальний максимум 32 при значенні -2.

Plot showing found global maximum of 32

У схожій завдання Томпсона є доказ для 12 вершин ікосаедра, перебуваючи в яких система з 12 електронів знаходиться в потенційному мінімумі. Але для 7, 8, 9, 10, 11 і 13+ електронів задача вважається вирішеною. гіпотезі Кеплера передбачається, що гексагональна щільна упаковка є плотнейшая упаковка для сфер, проте суворе доказ було отримано Томасом Хейлзом лише 10-го серпня 2014-го року. Плотнейшая упаковка для правильних тетраедрів — з відношенням 4000/4671 = 0.856347… — була відкрита лише 27-го липня 2010-го року, проте досі не має суворого докази. Будь-які заяви про знайдене рішення слід сприймати з певною часткою скептицизму; геометричні завдання максимізації, як відомо, дуже складні.

Кілька місяців моє найкраще рішення для 11 точок було в асиметричному локальному максимумі. Деякі (або більшість) з цих рішень, швидше за все, локальні, а не глобальні, але які з них? З цієї застереженням можна подивитися на найвідоміші рішення для 12-ти і більше точок.

12-НММ має вершину в точці 12 і містить у собі декілька кривоватый семиугольник 11-6-7-10-8-5-9 і чотирикутник 1-4-3-2.

13-НММ має вершину в точці 13 і містить у собі декілька кривоватый семиугольник 12-8-10-6-7-9-11 і такий же п'ятикутник 1-2-3-4-5.

Мої спроби додати симетрію призвели до фігур з меншим обсягом.

12-BLP and 13-BLP

По ідеї, рішення для 14-НММ повинні бути досить симетричні, однак вони в мене поки-що не вийшли. Я витратив деякий час на оптимізацію системи вершина-пентагон-п'ятикутник для 15-НММ, проте методом випадкових точок було отримано найкраще рішення, в якому симетрія була принесена в жертву обсягом.

14-BLP and 15-BLP

17-НММ, 18-НММ — я сподіваюся, що в першому все в порядку з симетрією.

Що стосується 19-НММ і 20-НММ, то 20-НММ — не додекаедр, так як поодинокі лінії з центру — не кращий варіант.

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

Як «кирпатий куб» (snub cube), так і половина величезного ромбокубоктаэдра — всі мають менший обсяг, ніж 24-НММ.

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

21-НММ і 22-НММ містять безліч семи — і девятиконечных зірок.

23-НММ, 24-НММ — мій кращий 24-НММ має тетраэдрическую симетрію.

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

Ось деякі симетрії в поточному кращому 24-НММ. Відрізки 1-12 і 13-24 мають відповідні довжини 0.512593 і 0.515168.

Symmetry in the current best 24-BLP

У 16-НММ і 17-НММ одиничні відрізки визначають багатокутники. 16-НММ містить безліч семиконечных зірок.

16-BLP contains 7-pointed stars

Нижче представлені ті ж самі многогранники, представлені як суцільні тіла, за допомогою ConvexHullMesh[], для НММ 9-10-11-12, 13-14-15-16, 17-18-19-20, 21-22-23-24, відповідно.

Багатогранників shown as solid objects using ConvexHullMesh

Тут представлена таблиця найкращих відомих на даний момент значень.

Current table of best known values

Ось кращі рішення, які я знайшов на даний момент, для 4-24 точок.

Best solutions for to 4 24 points

Нехай точки будуть розташовані так, щоб максимальна відстань від початку координат було як можна менше. Розподіл, представлене нижче, вказує на відстані від початку координат до вершин кожного багатогранника, у кожному з яких від 8 до 24 вершин.

Distance from origin for vertices scatterplot

За допомогою Mathematica 10.1 вдалося отримати точні значення для 6,7,8,9-НММ і 16-НММ. Так само з її допомогою були знайдені дуже точні, але чисельні значення для 10-НММ та 11-НММ і вдалося серйозно просунутися з 24-НММ. Таким чином, ми отримали рішення семи раніше невирішених задач комбінаторної геометрії — все, завдяки комбінації Volume[ConvexHullMesh[points]]. А які нововведення в Mathematica 10 допомогли особисто Вам?

Список літератури
[1] B. Kind and P. Kleinschmidt, «On the Maximal Volume of Convex Bodies with Few Vertices,» Journal of Комбінаторної 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 Комбінаторної 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 Комбінаторної Theory, Series A, 112(1), 2005 pp. 173-174.
doi:10.1016/j.jcta.2005.06.001

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.