Дивовижна поведінка рекурсивних послідовностей | Журнал Quanta

У математиці прості правила можуть відкрити всесвіти складності та краси. Візьмемо відому послідовність Фібоначчі, яка визначається так: вона починається з 1 і 1, і кожне наступне число є сумою двох попередніх. Перші кілька цифр:

1, 1, 2, 3, 5, 8, 13, 21, 34 …

Простий, так, але цей простий рецепт породжує візерунок далекосяжного значення, який, здається, вплетений у саму тканину світу природи. Його можна побачити в завитках раковин наутилуса, кістках у наших пальцях і розташуванні листя на гілках дерев. Його математичний охоплення поширюється на геометрію, алгебру та ймовірність, серед інших областей. Через вісім століть відтоді, як послідовність була представлена ​​на Заході — індійські математики вивчали її задовго до Фібоначчі — числа продовжують привертати інтерес дослідників, що свідчить про те, наскільки математична глибина може лежати в основі навіть найелементарнішої числової послідовності.

У послідовності Фібоначчі кожен термін ґрунтується на тих, що були перед ним. Такі рекурсивні послідовності можуть демонструвати широкий спектр поведінки, деякі з яких надзвичайно суперечать інтуїції. Візьмемо, наприклад, цікаве сімейство послідовностей, яке вперше описав у 1980-х роках американський математик Майкл Сомос.

Подібно до послідовності Фібоначчі, послідовність Сомоса починається з ряду одиниць. Сомос-k послідовність починається з k їх. Кожен новий термін Somos-k послідовність визначається паруванням попередніх членів, множенням кожної пари разом, додаванням пар, а потім діленням на термін k позиції назад у послідовності.

Послідовності не дуже цікаві, якщо k дорівнює 1, 2 або 3 — це лише серія повторюваних одиниць. Крім k = 4, 5, 6 або 7 послідовності мають дивну властивість. Навіть незважаючи на те, що поділу багато, дроби не з’являються.

"Зазвичай ми не маємо такого явища", - сказав Сомос. «Це оманливо просте повторення, схоже на Фібоначчі. Але за цією простотою стоїть багато».

Інші математики продовжують виявляти дивовижні зв’язки між послідовностями Сомоса та, здавалося б, не пов’язаними між собою областями математики. Одна стаття, опублікована в липні, використовує їх конструювати рішення до системи диференціальних рівнянь, які використовуються для моделювання всього, починаючи від взаємодії хижаків і жертв до хвиль, що поширюються у високоенергетичній плазмі. Вони також використовуються для вивчення структури математичних об'єктів, наз кластерні алгебри і підключені до еліптичні криві — які були ключем до злому останньої теореми Ферма.

Дженіс Малуф, аспірант Університету Іллінойсу, опублікував перший доказ того, що послідовності Сомос-4 і Сомос-5 є цілісними (це означає, що всі їхні члени є цілими числами) у 1992 році. Інші докази одного і того ж результату різними математиками з’явилися приблизно в той самий час разом із доказами того, що послідовності Сомос-6 і Сомос-7 є інтегральними.

Ця дивна властивість послідовностей Сомоса вразила математиків. «Послідовності Сомос заінтригували мене, як тільки я про них дізнався», — сказав Джеймс Пропп, професор математики Массачусетського університету, Лоуелл. «Той факт, що від Somos-4 до Somos-7 завжди дають цілі числа, незалежно від того, наскільки далеко ви зайшли, здавався дивом, якщо дивитися на речі з наївної точки зору. Тому потрібна була інша перспектива».

Пропп знайшов нову перспективу на початку 2000-х, коли він і його колеги виявили, що числа в послідовності Сомос-4 насправді щось підраховують. Терми в послідовності відповідають структурам, знайденим у певних графах. Для деяких графів можна поєднати вершини (точки) з ребрами (лініями), щоб кожна вершина була з’єднана рівно з однією іншою вершиною — немає неспарених вершин і жодної вершини, з’єднаної з більш ніж одним ребром. Члени в послідовності Somos-4 підраховують кількість різних ідеальних відповідностей для певної послідовності графів.

Відкриття не лише запропонувало новий погляд на послідовності Сомоса, але й запровадило нові способи думати про та аналізувати перетворення графів. Пропп і його учні святкували, виставивши результат на a Футболка.

«Для мене велика частина привабливості математики полягає в тому, коли ви прибуваєте в той самий пункт призначення різними шляхами, і здається, що відбувається щось дивовижне або глибоке», — сказав Пропп. «Класна річ у цих послідовностях полягає в тому, що існують різні точки зору, які пояснюють, чому ви отримуєте цілі числа. Там є приховані глибини».

Історія змінюється для послідовностей Somos з більшим номером. Перші 18 членів Somos-8 є цілими числами, але 19-й член є дробом. Кожна послідовність Somos після цього також містить дробові значення.

Інший тип послідовності, розроблений німецьким математиком Фріцем Гебелем у 1970-х роках, є цікавим контрапунктом послідовностей Сомоса. The nчлен послідовності Гебеля визначається як сума квадратів усіх попередніх членів, плюс 1, поділена на n. Подібно до послідовностей Сомоса, послідовність Гебеля передбачає ділення, тому ми можемо очікувати, що члени не залишаться цілими числами. Але деякий час — оскільки послідовність стає величезною — вони, здається, є.

10-й член у послідовності Гебеля становить приблизно 1.5 мільйона, 11-й 267-десь мільярда. 43-й член занадто великий для обчислення — він містить приблизно 178 мільярдів цифр. Але в 1975 р. голландський математик Хендрік Ленстра показав, що на відміну від перших 42 членів, цей 43-й член не є цілим числом.

Послідовності Гебеля можна узагальнити, замінивши квадрати в сумі кубами, четвертими степенями або навіть старшими показниками. (Згідно з цією угодою, його оригінальна послідовність називається послідовністю 2 Гебеля.) Ці послідовності також демонструють дивовижну тенденцію починатися з розширеної частини цілих членів. У 1988 році Генрі Ібштедт показав що перші 89 членів послідовності 3 Гебеля (в якій використовуються куби замість квадратів) є цілими числами, а 90-й – ні. Подальші дослідження інших послідовностей Гебеля виявили ще більші відрізки. Послідовність 31 Гебеля, наприклад, починається з колосальних 1,077 цілих членів.

У липні математики з університету Кюсю Рінносуке Мацухіра, Тосікі Мацусака і Кокі Цучіда поділився папером показуючи, що для a k-Послідовність Гебеля, незалежно від вибору k, перші 19 членів послідовності завжди цілі числа. Їх надихнула вивчити це питання японська манга під назвою Сейсу-тан, що перекладається як «Повість про цілі числа». А кадр у коміксі попросив читачів визначити мінімально можливе значення N_k, точка, в якій a k-Послідовність Гебеля перестає створювати цілі члени. Троє математиків взялися відповідати на запитання. «Неочікувана стійкість цілих чисел протягом такого тривалого періоду суперечить нашій інтуїції, — сказав Мацусака. — Коли явища відбуваються всупереч інтуїції, я вважаю, що завжди присутня краса».

Вони знайшли модель повторюваної поведінки як k збільшується. Зосередившись на кінцевій кількості повторюваних випадків, вони зробили обчислення зрозумілими, і вони змогли завершити доказ.

Подивіться ближче на послідовність N_k показує ще один сюрприз: N_k є простим числом набагато частіше, ніж можна було б очікувати, якби воно було чисто випадковим. «З k«Послідовність Гебеля — це не просто цілі числа, — сказав він Річард Грін, математик Університету Колорадо. «Що примітно, так це те, що прості числа з’являються так часто. Це створює враження, що може відбуватися щось глибше».

Хоча нова стаття є доказом цього N_k завжди принаймні 19, невідомо, чи завжди скінченний, чи існує a k для яких послідовність необмежено містить цілі числа. «N_k поводиться загадково. … Є фундаментальне бажання зрозуміти його основну закономірність», — сказав Мацусака. «Це може бути схоже на радість, яку я відчував у дитинстві, коли розгадував головоломки, які давали вчителі. Навіть зараз у мені живуть ті відчуття того часу».

Quanta проводить серію опитувань, щоб краще обслуговувати нашу аудиторію. Візьміть наші опитування читачів з математики і ви будете введені, щоб виграти безкоштовно Quanta мерч.