Рубрика «теория чисел»

В распределении простых чисел обнаружена дифракционная картина, примерно как у квазикристаллов - 1

В марте 2016 года Роберт Дж. Лемке-Оливер и Каннан Соундарараджан из Стэнфордского университета открыли новый шаблон в распределении простых чисел. Оказалось, что простые числа специфически распределяются по числовому пространству. Подробнее см. перевод статьи «Структура и случайность простых чисел» на Хабре.

К изучению темы подключились специалисты из других областей, в том числе химии. И успешно. Профессор теоретической химии Сальваторе Торкуато вместе с теоретиком чисел Мэтью де Курси-Айрлэнд нашли новые шаблоны в распределении простых чисел, о которых раньше не было известно. Оказалось, что распределение простых чисел образует фракталоподобную дифракционную картину, чем-то похожую на картину дифракции у экзотических квазикристаллов.
Читать полностью »

После некоторых моих исследований простых чисел, я обнаружил интересную связь с иррациональными числами. Эта связь дает ответ на вопрос, почему простые числа расположены столь «хаотично» и почему они так сложно устроены. Под катом объяснение этой связи и вариант улучшенного алгоритма RSA. Читать полностью »

песочница

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

 

Так, формат 16-разрядных беззнаковых целых при размере такой таблицы около 13 килобайт вмещает всего лишь 6542 простых числа: вслед за числом 65531 идут значения более высокой разрядности. Такая таблица годится разве что в качестве игрушки.

 

Наиболее ходовой в программировании формат 32-разрядных целых выглядит значительно солиднее — он позволяет хранить около 203 млн простых. Но такая таблица занимает уже около 775 мегабайт.

 

Еще больше перспектив у 64-разрядного формата. Однако при теоретической мощности порядка 1e+19 значений, таблица имела бы размер 64 экзабайта.

Читать полностью »

Выдающийся математик раскрыл подробности того, как его успехи в изучении тысячелетних математических вопросах связаны с концепциями, взятыми из физики

Раскрыта тайная связь чистой математики и физики - 1
Миньон Ким

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

Миньон Ким, [Minhyong Kim] математик из Оксфордского университета, особенно интересуется вопросом того, какие рациональные числа подходят для решения уравнений определённого рода. Эта проблема стимулировала специалистов по теории чисел тысячелетиями. И они едва продвинулись по пути к её решению. Когда вопрос изучается так долго и без ответа, можно заключить, что единственным способом продвинуться в нём будет выдвинуть радикально новую идею. Именно это и проделал Ким.
Читать полностью »

Введение

В этой статье будет рассмотрена тема построения и работы с конечными полями (или полями Галуа), которые используются в криптографии, теории информации и кодирования и других науках, т.е. имеют широкое практическое применение.
Сухую теорию о группах/кольцах/полях можно прочитать по ссылке Поля Галуа, а здесь будет больше практики и реализации на языке Scala.

Типы и ограничения

Для начала следует обсудить технические проблемы связанные с представлением полиномов в памяти, с учетом размеров типа Int в языке Scala. Требования сформулированы в списке ниже.

  • Тип Int в Scala/Java имеет размер 32 бита
  • Использовать можно биты: 0..30 — 31, поскольку 32-ой бит является знаковым
  • Полиномы должны быть представлены числами в диапозоне 0..29
  • Неприводимые полиномы (или модули) имеют диапозон 1..30
  • Конечное поле имеет Поле Галуа на Scala - 1 элементов

Реализация

Сначала опишем класс Polynomial, который реализует полином и 4 операции.
Этот вид полинома является «полуфабрикатом» и не привязан к конечному полю.

Читать полностью »

Кем был Рамануджан? - 1

Перевод поста Stephen Wolfram "Who Was Ramanujan?".
Выражаю огромную благодарность Полине Сологуб за помощь в переводе и подготовке публикации


Содержание

Удивительное письмо
Начало истории
Кем был Харди?
Письмо и его последствия
Стиль работы Рамануджана
Видеть то, что важно
Истина или объяснение
Переход в Кембридж
Рамануджан в Кембридже
Что было дальше
Что стало с Харди?
Математика Рамануджана
Факты — случайные или нет?
Автоматизация работ Рамануджана
Современные Рамануджаны?
Что было бы, если бы у Рамануджана была Mathematica?


На этой неделе вышел фильм "Человек, который познал бесконечность" (который мне показали еще прошлой осенью Манджул Бхаргава и Кен Оно), так что я не мог не написать о его главном герое — Сринивасе Рамануджане.

Кем был Рамануджан? - 2

Удивительное письмо

Раньше они приходили по обычной почте. Сейчас — по электронной. В течение многих лет со всего мира ко мне стекаются письма, в которых содержатся смелые утверждения о простых числах, теории относительности, искусственном интеллекте, сознании и множестве других вещей. Глядя на эти сообщения, я вспоминаю историю Рамануджана и неизменно откладываю свои идеи и проекты, чтобы хотя бы просмотреть их.

Около 31 января 1913 года математик по имени Харди из Кембриджа, Англия, получил пакет документов с сопроводительным письмом, которое начиналось так: "Дорогой сэр, хочу представиться вам: я клерк из бухгалтерии порта в Мадрасе с зарплатой £20 в год. Мне 23 года....». И продолжал: писал о том, что достиг «поразительного» прогресса в теории расходящихся рядов по математике и решил давнишнюю проблему распределения простых чисел. Сопроводительное письмо заканчивалось словами: "Я беден; если вы решите, что здесь есть что-нибудь ценное, я хотел бы, чтобы мои теоремы были опубликованы… Я неопытен, и любые ваши советы ценны для меня. Прошу извинить меня за доставленные неудобства. Искренне ваш, с уважением, С. Рамануджан".
Читать полностью »

В свои 28 лет Петер Шольце раскрывает глубинные связи между теорией чисел и геометрией

Оракул от арифметики - 1

В 2010 году по сообществу людей, изучающих теорию чисел, прошёл поразительный слух – и дошёл до Джареда Вайнштейна [Jared Weinstein]. Якобы какой-то аспирант из Боннского университета в Германии опубликовал работу, в которой 288-страничное доказательство теоремы из теории чисел ужато всего до 37 страниц. 22-летний студент Петер Шольце нашёл способ обойти одну из самых сложных частей доказательства, сопоставив теорию чисел и геометрию.

«Просто невероятно, что такой молодой человек смог сделать нечто настолько революционное,- говорит Вайнштейн, 34-летний специалист по теории чисел из Бостонского университета. – Это несомненный повод для уважения».

Математики из Боннского университета, присвоившие Шольце звание профессора всего два года спустя, уже знали о его экстраординарных умственных способностях. После публикации работы его начали замечать эксперты и по теории чисел, и по геометрии.

С того момента Шольце, которому сейчас 28, дорос до высокого положения уже в более широком математическом сообществе. Его называют "одним из самых влиятельных математиков мира", и "редким талантом, появляющимся раз в несколько десятилетий". О нём говорят, как о фаворите среди претендентов на Филдсовскую премию, одну из высочайших наград для математика.

Ключевому нововведению Шольце – классу фрактальных структур, названных им перфектоидными пространствами – исполнилось всего несколько лет, но оно уже ведёт к далеко идущим последствиям в области арифметической геометрии, в которой сливаются теория чисел и геометрия. Вайнштейн говорит, что работа Шольце была провидческой. «Он смог увидеть последствия до того, как те начали происходить».
Читать полностью »

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

24 марта сего года произошло событие, которого мы все так давно ждали: в сервисе цифровой дистрибуции компьютерных игр Steam вышел очередной шедевр польского игростроя — Hydra Slayer. И хотя шедевр этот местами кривоват, да и ждали его далеко не все, а скорее три с половиной человека, всё же я полагаю его достойным своей статьи на Хабре. «Постойте-ка, любезный автор, — воскликнет сейчас человек по другую сторону монитора от меня, — а не спутали ли вы часом столь уважаемый сайт, как Хабрахабр, с каким-нибудь игровым порталом, где юноши от четырнадцати лет и младше делятся своими успехами в Майнкрафте, обильно используя ненормативную лексику?». Нет, не спутал. Этому материалу суждено особое место в хабе «Математика».

image
Читать полностью »

Давеча снова увлекся простыми числами. Манит меня их тайна.

Написал алгоритм, похожий на решето Эратосфена. За 3 часа программа нашла 700 тысяч первых простых чисел. А мне надо хотя бы 14 миллионов простых чисел, чтобы перемножив их, получить число с количеством десятичных цифр, равным 100 миллионам штук.

Из статьи «Еще раз о поиске простых чисел», написанной пользователем Bodigrim, узнал о существовании быстрой программы primegen, которая работает используя решето Аткина. Установил ее в виртуальной машине LUbuntu (VirtualBox). Действительно, primegen очень быстро работает!

Тогда встал вопрос, как сохранить 14 миллионов простых чисел? Можно просто каждое простое число записать в файл как int32. А если простое число будет больше мощности 32-х бит?
Читать полностью »

В Интернете мной найдено описание множительного устройства Слонимского и брусков Иоффе [2], заимствованное из книги «История вычислительной техники» И.А. Апокин, Л.Е. Майстров, «Наука» 1990 г. Описание не раскрывает принцип действия приборов. Литературу, на которую ссылается автор книги, достать неприемлемо сложно. Я решил вскрыть алгоритм работы прибора самостоятельно, а для демонстрации — изготовить собственный аналог.
Читать полностью »