Феофан это бот, умеющий рассуждать логически на русском языке ФРЯ Например, если Феофану сообщить, что все люди смертны, а Сократ это человек, то он сообразит, что Сократ тоже смертен. См. Примеры

Saturday, July 22, 2017

Thursday, January 12, 2017

ПэЧэ, граф Кэли, кубик Рубика и универсалии

Универсального свойства достаточно, чтобы определить объект с точностью до изоморфизма. Таким образом, появляется ещё один способ доказать, что два объекта изоморфны, а именно доказать, что они обладают одинаковым универсальным свойством.

Определение некоего свойства не гарантирует существование объекта, ему удовлетворяющего. Если однако, такой (A, φ) существует, то он единственен. Точнее говоря, он единственен с точностью до единственного изоморфизма.


Свобо́дная гру́ппа в теории групп — группа , для которой существует подмножество  такое, что каждый элемент  записывается единственным образом как произведение конечного числа элементов  и их обратных

Возможно предъявить явную конструкцию свободных групп, доказав тем самым их существование[1][2]


... любая группа обладает заданием. Задание не обязано быть единственным. Доказать или опровергнуть, что два задания определяют одну и ту же группу сложно (старое название проблемы — одна из проблем Дэна). В общем случае эта проблема алгоритмически неразрешима. ...  Ввиду алгоритмической неразрешимости проблемы, поиск цепочки преобразований Титце одного представления в другое является своего рода искусством.
По заданию группы также сложно определить и другие свойства группы, например её порядок или подгруппу кручения.

Граф Кэли симметрической группы S4

Гру́ппа ку́бика Ру́бика — подгруппа симметрической группы S48

Каждый из поворотов граней кубика Рубика может рассматриваться как элемент симметрической группы множества 48 этикеток кубика Рубика, не являющихся центрами граней. 

Порядок группы  равен[2][3][4][5][6]


Unionpedia is a concept map or semantic network organized like an encyclopedia – dictionary. It gives a brief definition of each concept and its relationships.


Если p — простое число, то любая группа порядка p циклическая и единственна с точностью до изоморфизма


Thursday, January 20, 2011

New theories reveal the nature of numbers

A key creative breakthrough occurred when Emory mathematicians Ken Ono, left, and Zach Kent were hiking. As they walked, they noticed patterns in clumps of trees and began thinking about what it would be like to "walk" amid partition numbers. 

By Carol Clark

For centuries, some of the greatest names in math have tried to make sense of partition numbers, the basis for adding and counting. Many mathematicians added major pieces to the puzzle, but all of them fell short of a full theory to explain partitions. Instead, their work raised more questions about this fundamental area of math.

Now, Emory mathematician Ken Ono is unveiling new theories that answer these famous old questions. (Click here to watch a video of Ono's lecture on the topic.)

Ono and his research team have discovered that partition numbers behave like fractals. They have unlocked the divisibility properties of partitions, and developed a mathematical theory for “seeing” their infinitely repeating superstructure. And they have devised the first finite formula to calculate the partitions of any number.

“Our work brings completely new ideas to the problems,” Ono says. “We prove that partition numbers are ‘fractal’ for every prime. These numbers, in a way we make precise, are self-similar in a shocking way. Our ‘zooming’ procedure resolves several open conjectures, and it will change how mathematicians study partitions.”

The problems of partition numbers "have long fascinated mathematicians," Ono says.

The work was funded by the American Institute of Mathematics (AIM) and the National Science Foundation. Last year, AIM assembled the world’s leading experts on partitions, including Ono, to attack some of the remaining big questions in the field. Ono, who is a chaired professor at both Emory and the University of Wisconsin at Madison, led a team consisting of Jan Bruinier, from the Technical University of Darmstadt in Germany; Amanda Folsom, from Yale; and Zach Kent, a post-doctoral fellow at Emory.

“Ken Ono has achieved absolutely breathtaking breakthroughs in the theory of partitions,” says George Andrews, professor at Pennsylvania State University and president of the American Mathematical Society. “He proved divisibility properties of the basic partition function that are astounding. He went on to provide a superstructure that no one anticipated just a few years ago. He is a phenomenon.”

Child’s play

On the surface, partition numbers seem like mathematical child’s play. A partition of a number is a sequence of positive integers that add up to that number. For example, 4 = 3+1 = 2+2 = 2+1+1 = 1+1+1+1. So we say there are 5 partitions of the number 4.

It sounds simple, and yet the partition numbers grow at an incredible rate. The amount of partitions for the number 10 is 42. For the number 100, the partitions explode to more than 190,000,000.

“Partition numbers are a crazy sequence of integers which race rapidly off to infinity,” Ono says. “This provocative sequence evokes wonder, and has long fascinated mathematicians.”

By definition, partition numbers are tantalizingly simple. But until the breakthroughs by Ono’s team, no one was able to unlock the secret of the complex pattern underlying this rapid growth.

The work of 18th-century mathematician Leonhard Euler (below) led to the first recursive technique forcomputing the partition values of numbers. The method was slow, however, and impractical for large numbers. For the next 150 years, the method was only successfully implemented to compute the first 200 partition numbers.

“In the mathematical universe, that’s like not being able to see further than Mars,” Ono says.

A mathematical telescope

In the early 20th century, Srinivasa Ramanujan and G. H. Hardy invented the circle method, which yielded the first good approximation of the partitions for numbers beyond 200. They essentially gave up on trying to find an exact answer, and settled for an approximation.

“This is like Galileo inventing the telescope, allowing you to see beyond what the naked eye can see, even though the view may be dim,” Ono says.

Ramanujan also noted some strange patterns in partition numbers. In 1919 he wrote: “There appear to be corresponding properties in which the moduli are powers of 5, 7 or 11 … and no simple properties for any moduli involving primes other than these three.”

The legendary Indian mathematician died at the age of 32 before he could explain what he meant by this mysterious quote, now known as Ramanujan’s congruences.

In 1937, Hans Rademacher found an exact formula for calculating partition values. While the method was a big improvement over Euler’s exact formula, it required adding together infinitely many numbers that have infinitely many decimal places. “These numbers are gruesome,” Ono says.

In the ensuing decades, mathematicians have kept building on these breakthroughs, adding more pieces to the puzzle. Despite the advances, they were unable to understand Ramanujan’s enigmatic words, or find a finite formula for the partition numbers.

“We were standing on some huge rocks, where we could see out over this valley and hear the falls, when we realized partition numbers are fractal,” Ono says. Photo by Zach Kent.

Ono’s “dream team” wrestled with the problems for months. “Everything we tried didn’t work,” he says.

A eureka moment happened in September, when Ono and Zach Kent were hiking to Tallulah Falls in northern Georgia. As they walked through the woods, noticing patterns in clumps of trees, Ono and Kent began thinking about what it would be like to “walk” amid partition numbers.

“We were standing on some huge rocks, where we could see out over this valley and hear the falls, when we realized partition numbers are fractal,” Ono says. “We both just started laughing.”

The term fractal was invented in 1980 by Benoit Mandelbrot, to describe what seem like irregularities in the geometry of natural forms. The more a viewer zooms into “rough” natural forms, the clearer it becomes that they actually consist of repeating patterns (see youtube video, below). Not only are fractals beautiful, they have immense practical value in fields as diverse as art to medicine.

Friday, January 6, 2017

ПэЧэ и КуРу (p-адические числа и кубик Рубика)

однажды элементарные понятия абстрактной алгебры помогли мне собрать кубик рубика, который никак не собирался исходя из "здравого смысла" (слишком сложно было "увидеть" решение)

подумал, что изучение p-адических чисел можно превратить в игру и развлечение на основе идеи кубика Рубика

итак, читаем вики https://ru.wikipedia.org/wiki/Группа_кубика_Рубика


Гру́ппа ку́бика Ру́бика — подгруппа симметрической группы S48


Порядок группы  равен[2][3][4][5][6]
Пусть  — граф Кэли группы  с 18 образующими, которые соответствуют 18 ходам метрики FTM.
Каждая из  конфигураций может быть решена не более чем за 20 ходов FTM. Другими словами, эксцентриситет вершины графа , соответствующей «собранному» состоянию головоломки, равен 20[7].

Диаметр графа  также равен 20[8].


грубо говоря, интуитивно РАССТОЯНИЕ для КР - это минимальное число поворотов, за которое он собирается  (максимальное - это 20)


9 сентября 2010 в 00:56

Разработка → Кубик Рубика за 20 шагов


Любая позиция Кубика Рубика может быть решена не более, чем за 20 шагов.

Несколько лет назад было доказано, что для Кубика Рубика есть решение за 23 хода. Теперь это число сократилось до 20. Чтобы это сделать, потребовалось 35 (тридцать пять) лет компьютерного времени, пожертвованного Гуглом.

Каждый блок решения использовал свой алгоритм — последовательность шагов для достижения нужной конфигурации. Например, один алгоритм предназначался для решения верхней грани, а другой — для позиционирования средних краев. Есть множество различных алгоритмов, различающихся по степени сложности и количеству требуемых шагов, но те, которые может запомнить человек, обычно требуют больше 40 шагов.

Разумно полагать, что Бог может использовать более эффективный алгоритм, который решает задачу за наикратчайшее число шагов. Этот алгоритм известен как “алгоритм Бога”. Число шагов в худшем случае называется числом Бога. В конце концов, было показано, что это число — 20.

После изобретения Кубика Рубика пятнадцать лет ушло на поиск позиции, которая наверняка решается за 20 шагов. Через 15 лет после этого мы докажем, что 20 шагов достаточно для любой позиции.

История числа Бога

К 1980 году было установлено, нижняя граница — 18, а верхняя — вероятно, около 80. В таблице ниже собраны все результаты:

Как мы это сделали

Как мы справились с 43 252 003 274 489 856 000 позициями Кубика Рубика?
  • Мы разделили все позиции на 2 217 093 120 множеств — по 19 508 428 800 позиций в каждом.
  • Мы уменьшили число множеств для решения до 55 888 296 на основе симметрии и покрытии множества.
  • Мы не искали оптимальное решение, а только решения с длиной 20 или менее шагов.
  • Мы написали программу, находящее решение для одного множества за 20 секунд.
  • Потребовалось 35 лет компьютерного времени для поиска решений всех конфигураций в каждом из 55 888 296 множеств.

Деление пространства позиций

Мы разбили большую задачу на 2 217 093 120 меньших подзадач: в каждую входило по 19,508,428,800 различных позиций. Одна такая подзадача легко помещается в память современного компьютера, и этот метод позволил достаточно быстро получить решение.


Если повертеть Кубик Рубика влево-вправо или вверх-вниз, то, по сути, ничего не изменится: число шагов в решении останется тем же самым. Вместо того, чтобы решать все эти позиции, можно получить решение для одной и распространить его на повернутые позиции. Есть 24 различных ориентации в пространстве и 2 зеркальных положения Кубика для каждой позиции, что позволяет уменьшить число решаемых позиций в 48 раз. Если использовать аналогичные рассуждения и воспользоваться поиском задачи “покрытия множества”, то число подзадач уменьшается от 2 217 093 120 до 55 882 296.

Хорошие и оптимальные решения

Оптимальное решение содержит достаточное количество шагов, но не больше, чем надо. Так как уже известна одна позиция, для которой требуется 20 шагов, то мы можем не искать оптимальное решение для каждой позиции, а только решения в 20 или менее шагов. Это многократно убыстряет задачу.


У нас была возможность решить 55 882 296 подзадач на мощностях Гугла и выполнить все вычисления за несколько недель. Гугл не раскрывает характеристики компьютеров, но было затрачено 1.1 миллиард секунд компьютерного времени (Intel Nehalem, four-core, 2.8GHz) на выполнение расчетов.

Самая трудная позииция

Мы знали в течении 15 лет, что есть позиции, которые требует 20 шагов, но мы доказали, что ни для одной позиции и не надо больше.

Позиции с решениями в 20 шагов редки, но их вполне возможно встретить в реальности. Вероятность встретить такую позицию варьируется от 10^(-9) до 10^(-8). Мы точно не знаем точное количество таких позиций. Таблица дает оценку числа позиций для каждой длины решения.

Для длин от 16 и больше, числа являются примерными. Наши исследования подтвердили все первоначальные данные до 14 строки включительно, а 15 строка — новый результат. На 11 августа мы обнаружили 12 миллионов позиций с длиной решения 20. Эта позиция была самой сложной для наших программ:


теперь попробуем сформулировать проблему в терминах ПэЧэ

с учётом степеней свободы и того, что поворот навлево равен трём поворотам направо мы можем построить 5-адическое дерево для всех возможных переходов (одну грань можно считать фиксированной и крутить только 5 остальных)

на этом дереве 5-адических чисел вводим отображение (функцию) и "расстояние"

любая "загогулина" на этом дереве (ПэЧэ), повторенная определенное число раз, возвращает чило "к себе" (визуально можно представить себе стрелочки в обратную сторону)

получается что-то типа  неориентированного графа - как в детской игре - когда бросают кости, выпадает число, игрок шагает по карте (тропинка с позициями) и там есть "хитрые места", где игрок "телепортируется" в другое место (задача игру - попасть точно в "выигрышную" позицию "финиш")

игру можно переделать в форму "бродилки со стрелками телепортации"

на 5-адическом дереве для любой "загогулины" (кусочка пути) вводится автоматический эффект телепортации - "возврат в исходную позицию" (задаётся формулой, матрицей или графом) - целочисленная фонкция от "загогулины" - сколько раз нужно повторить "заггогулину", чтобы вернуться в ту же позицию

на полпути "траектория" возврата почти соприкасается с исходной точкой - именно это позволило найти путь к сборке (не самый короткое но всё же решение)

короче, цель головоломки - за минимально число шагов (20 шагов - это вроде с возможностью поворачивать в обе стороны и на 180 градусов - т.е. для 5-алического дерева наверно нужно не больше 52 движений ? ) с учётом автоматической "телепортации" с любой ветки "слезть на землю" (т.е. очутиться в корне 5-адического дерева)

тут можно даже игру бродилку нарисовать - пусть дети с малолетства приучаются мыслить в адических понятиях о расстоянии

ибо как говорил Козьма Прутков - "Бросая в воду камешки, смотри на круги, ими образуемые; иначе такое бросание будет пустою забавою.":-)