Як порахувати перестановки. Лекція в Яндексі

Деякий час тому в московський офіс Яндекса приїжджав Ігор Пак — вчений з безліччю наукових робіт, випускник мехмату МГУ і аспірантури Гарварду. Зараз Ігор працює в Каліфорнійському університеті. Його лекція в Яндексі була присвячена різним класам послідовностей і перестановок. У тому числі прямо по ходу лекції він представив викладки, які спростовують гіпотезу Нунана і Зайлбергера — одну з ключових в області перестановок.



Під катом — детальна текстова розшифровка і більшість слайдів.



Доповідь у мене не про стандартні речі. На жаль, перечислительную комбінаторику вивчають не дуже серйозно — в Росії вона не входить в стандартну університетську програму. У першій, вступній половині доповіді я буду приводити знамениті класичні питання з перечислительной комбінаторики. А в другій половині підуть більш складні речі з тих, що ми недавно зрозуміли. Якщо ви будете мене зупиняти і задавати питання — нічого страшного.

Про що взагалі перечислительная комбінаторика? Зазвичай ми вивчаємо послідовності натуральних чисел. Вони бувають різні. Я виписав півдюжини послідовностей з енциклопедії «Online Encyclopedia of Integer Sequences». Я буду говорити по-російськи, але всі слайди складені на англійській.

Деякі послідовності більш комбінаторні, деякі — менше. Наприклад, число кінцевих груп, найперша послідовність у цій енциклопедії, — не дуже комбінаторна. Так виходить, що є дві групи 4 порядку. Наступна, більш проста послідовність — прості числа. Число розбиття цілого числа n, сума доданків — ми побачимо їх пізніше. Наступна послідовність — числа Фібоначчі. Потім число инволюций, числа Каталана, числа зв'язних графів.

Питання таке: чи є формула, яка описує числа в кожній послідовності? Це складне питання — він пов'язаний зі значенням формули. Я розповім про різних послідовностях і про те, якими бувають формули. Потім спробую це уніфікувати, розповісти теорію. Ми вивчаємо послідовності і намагаємося зрозуміти формули для містяться в них чисел.



Я почну зі стандартного введення. Сам я нічого не буду визначати — краще наведу цитати двох авторів. Перша цитата — Річарда Стенлі, читати її довго, але сенс такий: він вважає, що найцікавіше — це явні формули, коли можна написати, що «щось одно сума чогось помножити на що-то».

Херб Уилф каже, що ні, формули не мають відношення до того, сума це або твір, що так їх визначити не можна, що формула — насправді алгоритм. Для нас його ідея дуже важлива. Формула — якийсь алгоритм, який вважає числа, що стоять в послідовності, за час, полиномиальное від n.

Але насправді більш стара ідея в тому, щоб зрозуміти, хороша формула чи ні. Дивляться на формули, на асимптотику. Якщо ми можемо за формулою зрозуміти, що це за число, з точністю плюс-мінус 3%, то це хороша формула. Я перерахував три стандартних визначення того, що таке формула. Для нас будуть дуже важливі всі три, але алгоритмічний підхід буде найбільш важливий.



Почнемо з асимптотики. Це дуже стара річ, відома для всіх послідовностей. Наприклад, числа Фібоначчі ростуть дуже конкретним експоненціальним чином, числа Каталана теж ростуть експоненціально — там є поліноміальний множник. Мова йде про зовсім старих теоремах. Це теорема розподілу простих чисел, якій більше ста років. Для числа розбиття теж є чудова асимптотична формула. Її не дуже легко довести, але зрозуміти экспоненциональный член — трошки легше.

Для числа инволюций вже потрібно трошки аналізу, не занадто складного. А ось формула для числа груп порядку <= n — дуже складна. Щоб її довести, потрібно знати класифікацію простих кінцевих груп, це вже не зовсім комбінаторика, зовсім не комбінаторика.

Зате остання формула, навпаки, дуже проста. Число графів на n вершинах — приблизно 2 в ступені (...) коефіцієнт, n/2. І сенс її дуже проста: випадковий граф є зв'язним з великою ймовірністю, яка прагне до 1, коли n прямує до нескінченності.

Ці формули чудові, але це аналітичні формули, не комбінаторні. І вони не дають нам розуміння, як порахувати ці числа. А це те, чим ми займаємося. І щоб зрозуміти, чим саме ми займаємося, я почну з дуже стандартного класичного прикладу — чисел Фібоначчі.



Я дам одне з їхніх визначень. Число Фібоначчі кількість послідовностей з нулів і одиниць довжиною n мінус 1, у яких немає двох що стоять поспіль одиниць. Наприклад, послідовностей довжини 2, у яких немає двох одиниць поспіль, буде рівно 3. Ось вони: 00, 01, 10. Послідовностей довжини 3, в якій немає двох що стоять поспіль одиниць, буде п'ять.

Далі є три формули. Перша формула — рекурентне від нас співвідношення числа Фібоначчі, що таке є сума двох попередніх. Друга формула виписує числа Фібоначчі в якості суми біноміальних коефіцієнтів. Третя формула — зовсім очевидна: вона пише їх як суму двох ступенів — золотого перерізу та його зворотного.

Далі питання, яка з цих формул краще? Коли я викладаю студентам першокурсникам і второкурсникам, то традиційно починаю з першої формули — кажу, що це визначення, а третю формули ми виводимо через деякий час і хвилин 30 доводимо.

Але якщо потрібно порахувати 117-е число Фібоначчі, то третя формула досить марна. Щоб його розрахувати, потрібно дуже чітко знати, чого саме одно це золотий перетин — його треба порахувати з великою кількістю знаків. А це знову складно. Як ви це будете робити? Якщо подумати, це не дуже хороша формула. Формула про суму біноміальних коефіцієнтів відмінна, але для розрахунків перша формула краще і простіше. Вважаєш одну за одною і все вийде.

Вже видно, в чому питання. Яка формула краще — не зовсім очевидно. З точки зору естетики, може, третя формула краще, а вже з точки зору асимптотики — напевно. Вона відразу говорить, яка у числа Фібоначчі асимптотика. Але перша формула краще для розрахунків, а друга більше підходить для того, щоб доводити деякі теореми.



Кількість заворушень — дуже стара послідовність. Візьмемо таке число перестановок, що елемент i завжди переходить в якийсь елемент не дорівнює i. Якщо у вас перестановка довжини 2, завжди існує тільки одна така перестановка. Одинична перестановка не підходить, {21} підходить. Коли у вас перестановка довжини три, існує дві рівні перестановки, обидва циклу. Інші не підходять зовсім — у них є нерухома точка.

І в загальному знову три формули. Перша чудова: це число є найближчим цілим числом до числа n!/e. Перед нами дуже проста формула. Проста, але асимптотичне досягнення чудове. Значення e дуже складно порахувати на комп'ютері, а щоб порахувати кількість заворушень довжини 117, потрібно знати e з дуже великою точністю. Друга формула пояснює першу. Грубо кажучи, якщо винести n! назовні, n вийде! помножити на суму перших k членів ряду Тейлора. З одного боку, це пояснює першу формулу, а з іншого боку, тут стоять цілі числа — їх легко можна явно порахувати.

Насправді, найкраща формула для розрахунків — третя. Вона дає трохи несподіване рекурентне співвідношення, яке найпростіше порахувати і яке абсолютно нічого не пояснює. Довести таку формулу з визначення — не дуже очевидне вправу. Незрозуміло, що з цим (-1) ступеня n робити. Така ось історія. Для числа заворушень видно, що не зовсім зрозуміло, яка формула гарна, а яка погана.



Ménage numbers, французьке слово. Завдання виглядає так: влаштовується старомодний званий обід XIX століття, покликали n подружніх пар і хочуть їх всіх розсадити, щоб здійснилися дві умови. Перша умова — чоловіки чергуються з жінками. Друга умова — подружжя не сидять поруч. Завдання XIX століття, може, хтось досі збирає такі звані обіди. Кажуть, на весіллях таке роблять.

Як порахувати це число? Якщо у вас є тільки дві подружні пари, то посадити їх не вийде. Щоб подружжя сиділи разом, вони повинні бути навпроти один одного — значить, не буде чергування. Послідовність починається з нуля, коли є дві подружні пари. Але коли у нас три подружні пари, таких рассадок вже досить багато. Ось одна з них. Припустимо, у нас є подружні пари 1А, 2В та 3С. А, У і З ми посадимо по-порядку, а 1, 2 і 3 посадимо більш складним чином. Видно, що 3 сидить між А і В та не є чоловіком ані А, ані Ст.

Цю задачу можна вирішити. З історичної точки зору є два рішення. Перше — складне, довге і рекурентне — історично було отримано раніше, в 1891 році. Друге рішення — явна формула суми біноміальних коефіцієнтів, факториалов, множників і т. д. Коли це співвідношення було отримано, ніхто особливо не зрадів. Вважалося, що це не дуже потрібна формула, хоча за нею легко все порахувати. А ось як тільки Тушард у 1934 році отримав формулу у вигляді змінної суми біноміальних коефіцієнтів, всі подумали, що задача вирішена. Хоча з обчислювальної точки зору друга формула набагато краще.

Я наводжу дуже класичні приклади з періодичної комбінаторики. Як ми з цим працюємо? Зараз ми намагаємося поліпшити розуміння того, що таке явна формула. Стандартний спосіб — брати виробляє функцію. Зробити це можна двома різними способами. Найлегший — просто взяти суму ось такого ряду і розглядати її як формальну функцію від t.



Питання в тому, чи є якась формула для цієї функції. Часто для послідовності немає гарної формули, а для функції є. Тут наведено приклад, коли для чисел Фібоначчі у нас зовсім хороша формула — дуже раціональна для виробляючої функції. Але для чисел Каталана береться число триангуляций n+2-кутника. Їх Еллер придумав і вивчав в Санкт-Петербурзі в 1750-х роках. Твірна функція в даному випадку буде не раціональна, а алгебраїчна.



Давайте подивимося інші приклади — скажімо число инволюций. Інволюція — перестановка, яка в квадраті дорівнює одиниці. Це означає, що вона складається з циклів довжини або 1, або 2. Для числа таких инволюций немає гарної формули, яка б дозволила представити це як суму біноміальних коефіцієнтів. Проте існує дуже гарне рекурентне співвідношення. Зрозуміло, як таке доводити?

Беремо останній елемент n. Він або є нерухомою точкою — тоді число перестановок виходить на 1 менше, знаходиться в транспозиції з якимось ще елементом. Є n-1 способів вибрати такий елемент, і залишається n-2 елемента, з якими після цього потрібно зробити. З визначення виходить таке просте рекурентне співвідношення. У нього є чудова твірна функція, яку можна явно написати. Зауважимо, що це експоненціальна твірна функція. Ми беремо tn>an/n! — як ніби дивимося виробляє функцію для ймовірностей.

І тут є гарна формула et+t2/2.

Ось новий спосіб подивитися на явну формулу. Для числа розбиття n є кілька способів представити n як суми доданків. Наприклад, 4 = 3 + 1= 2 + 2 і т. д. — всього існує п'ять способів записати 4 у вигляді суми доданків. Але твірна функція теж чудова. Це теж придумав Еллер, в 1738 році. Нескінченне твір — ось що це буде. Перед нами не така хороша функція, як ми бачили раніше. Якщо у нас є нескінченне твір, то не дуже зрозуміло, що з ним робити. Мова йде про досить складної функції.

— Скажіть для графів.

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



Теорія. Ми хочемо розкласифікувати як можна більше послідовностей. Беремо кілька класів. Перший клас — раціональні послідовності. Вони є раціональними, якщо їх прозводящая раціональна функція, тобто являє собою співвідношення двох поліномів. Насправді це абсолютно еквівалентно простому рекуррентному співвідношенню на дані числа, яке узагальнює числа Фібоначчі. Ось найпростіше, що можна придумати. На диво, існує досить багато послідовностей, які задовольняють цим рекуррентным співвідношенням. А ось послідовностей простіше, ніж раціональні функції, — досить мало. У всіх раціональних послідовностей дуже проста асимптотика, їх дуже легко вивчати, про них відомо.

Наступний рівень — алгебраїчний. Це алгебраїчні послідовності, які узагальнюють формулу A(t) = 1 – √(1 – 4t)/2t.

Припустимо, наша твірна функція задовольняє якомусь алгебраическому рівнянню з полимиальными коефіцієнтами. Таких послідовностей теж досить багато: у чисел Каталана є така послідовність, у кількості Моцкіна, ще у багатьох інших. Але виявляється, що це не самий великий клас. Ми будемо вивчати клас побільше — биномиальные суми. Ми беремо суми, багато біноміальних коефіцієнтів. Я пишу — підсумувати по всіх векторах на решітці, але насправді те, де альфа і бета, — якісь лінійні функції. Якщо в биномиальном коефіцієнті якась функція стає негативною, то ми вважаємо, що це 0. Цікаво тільки, коли ці числа кінцеві. І таких випадків досить багато.

У цьому прикладі наведено як раз такий випадок. Перед нами сума якихось біноміальних коефіцієнтів. Тут — від 0 до n/2, але можна і відпустити, зробити більше, просто біноміальний коефіцієнт зникне, стане нулем.



В результаті у нас з'являється багато різних послідовностей, біноміальних сум. У них входять і числа заворушень, і числа рассадок за столом. Все це можна зрозуміти з точки зору таких біноміальних коефіцієнтів. Зверху багато факториалов, знизу теж — все можна зрозуміти. Мова йде про великому класі, але нас цікавить ще більший клас: P-рекурсивні послідовності. Їх можна визначити двома способами. Самий зрозумілий спосіб — коли існує рекурсивне співвідношення на ці числа, коли коефіцієнти не є константами, як у раціональному випадку, а поліномами, що залежать від n. Якщо ви пам'ятаєте, це складне і не дуже точно записане рекурентне співвідношення, придумане Лукасом, — є типовим. Але такі співвідношення є для багатьох інших послідовностей.



Типовий приклад — n!.. Він за визначенням -1! * n.

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

Це не дуже складна теорема. Вона означає, що виробляє функція задовольняє такому звичайному диференційному рівнянню з поліноміальними коефіцієнтами. Ось вам інший спосіб зрозуміти, як влаштовані послідовності. Для нас Р-рекурсивні послідовності будуть самим головним класом. У нього входять наступні теореми, які написані внизу і полягають у тому, що всі попередні класи лежать всередині цього. Мова про найбільший клас. Для алгебраїчних послідовностей це не зовсім очевидно, а довести таке для решти трохи простіше.

Звичайно, цей клас не включає всі приклади. Скажімо, прості числа сюди не входять — для них немає ніякого поліноміального співвідношення. Точно так само немає поліноміального співвідношення числа зв'язних графів. З ними — більш складний приклад, який сюди не відноситься. Погано, що є такі приклади, коли число розбиття сюди не входить, але чудово, що Р-рекурсивні послідовності просто за визначенням можна порахувати за полиномиальное час. Те, що тут написано, буде важливо для нас. У нас є клас послідовностей, всі з яких можна порахувати.



Перш ніж ми почнемо їх вважати, наведу якесь слідство. Воно полягає в тому, що в даному класі вже все добре з точки зору асимптотики. Якщо у вас є Р-рекурсивна послідовність, то асимптотична поведінка вже дуже добре: є константа, n!, якісь мірі, λnnα(log n)β. Все чудово працює, але, на жаль, ця теорема не доведена. Деякі вважають її теоремою, але вона їй є лише в окремих випадках. Однак для нас, в принципі, якраз і такий важливий окремий випадок — якщо є невід'ємна Р-рекурсивна цілочисельна послідовність, місяць не вище, ніж експонента, поведінку у неї дуже просте: λnnα(log n)β. У неї хороша і проста асимптотика. Цей клас дуже великий і включає багато різних комбінаторних послідовностей, які ми хочемо вивчати. Р-рекурсивні послідовності — найважливіший для нас клас.



Є ще один більш загальний клас, про який мало що відомо. Мова йде про послідовностях, у яких твірна функція задовольняє алгебраическому диференціальному рівнянню. Якщо взяти якусь кількість похідних цієї виробляючої функції, то всі разом вони будуть відповідати якомусь полиномиальному рівнянню. Це більш загальний клас. На жаль, результатів про його асимптотику існує досить мало. Ось один приклад. Візьмемо альтернирующие перестановки, які починаються з якогось числа, а потім йдуть більше-менше, більше-менше. Наприклад, існує рівно два таких перестановки довжиною 3 — 1, 3, 2 і 2, 3, 1. Існує п'ять перестановок довжиною 4 і т. д.

Для числа таких перестановок є досить складне рекурентне співвідношення. Його можна переписати як рівняння, яке є не звичайним диференціальним, а алгебраїчним диференціальних: 2A' = A2 + 1. У такому вигляді воно вирішується — виробляє функцію можна записати явним чином: tan(t) + sec(t). Перед нами стандартний приклад комбінаторної задачі, у якої є явне рішення для виробляючої функції, але про самі числа нічого хорошого сказати не можна, це дуже погані числа. Їх можна порахувати, але все послідовності, які задовольняють алгебраїчним диференціальних рівнянь, можна порахувати за полиномиальное час — n-й член послідовності вважається прямо з визначення. Якщо ви візьмете рівняння і розпишете його, то головний член в цьому співвідношенні завжди буде з коефіцієнтами.

В якості прикладу або ілюстрації того, що ці алгебраїчні диференціальні рівняння — досить складна штука, наведу теорема Якобі. Якобі довів, що така функція Діріхле задовольняє нікому алгебраическому диференціальному рівнянню, але воно досить складний і займає більше, ніж один рядок, тому я вирішив його не виписувати. Ця задача була вирішена 150 років тому, але, з іншого боку, якщо взяти не tn2, а tn3, то така задача відкрита і відкрита вона вже 150 років. Невідомо, чи задовольняє ця сутність алгебраическому диференціальному рівнянню. Сформулювати дуже легко, а довести дуже складно. Мова йде про настільки складному класі, що про нього досить складно щось сказати. Ми про нього нічого не знаємо.

Розповім про 4 класі. Про нього багато чого відомо, зокрема про асимптотики і т. д. Кінець прикладів і теорій. Перш ніж я почну розповідати більш складні речі про перестановки, відповім на питання.

— А в четвертому експоненціальна провідна функція?

— Це неважливо. Це легко зрозуміти з рекурентного співвідношення, там можна завжди на n множити.

— Питання про виробляє функцію. Якщо використовувати апарат періодичних чисел, напевно, вони краще будуть сходитися?

— Поняття не маю. Питання не в тому, як вони сходяться, а в тому, чи можна формально записати в якомусь явному вигляді, якому рівнянню вони будуть задовольняти.

Якщо у вас послідовність представлена як сума n! * tn, вона взагалі ніде не сходиться. З комбінаторної точки зору це чудова твірна функція, ми з нею класно працюємо, вона defined, коефіцієнт n! задовольняє полиномиальному рівнянню, все добре. Питання збіжності нас не хвилює ніяк, це формальна функція.

— Якщо за ультраметрике все вирішується, може, деякі випадки вирішуються радикально простіше?

— Нічого не можу сказати. Я не дуже розумію, про що ви говорите.

Будуть ще питання? Я вам розповів приблизно двосеместровий курс комбінаторики за півгодини. Всі ви з'ясували?

— Тобто якщо ми можемо обчислити всі за кінцеве час або записати формулу — то це гарне розуміння?

— Я про це поки що нічого не сказав, але в принципі, всі ці класи можна порахувати за полиномиальное час. Але існують послідовності, наприклад число всіх графів на n вершинах — 2 в ступені біноміальний коефіцієнт n/2, — які не входять в цей список і ростуть швидше, ніж факторіал. Звичайно, порахувати таку послідовно дуже легко — питання в тому, що ми захочемо зробити з теорією. Я розписав чотири головних класу. Один клас — самий великий, про нього відомо поменше. Але для всіх них можна все порахувати за полиномиальное час.

З іншого боку, зрозуміло, що існують послідовності, де підрахунок буде дуже складним. Якщо ми візьмемо, наприклад, число груп порядку n, то як ви будете їх рахувати? Давайте візьмемо що-небудь простіше, зв'язні графи, тільки замість labeled напишемо unlabeled. Це означає, що ви берете графи з точністю до ізоморфізму. І як ви будете це вважати? Перевірити ізоморфізм у такій моделі не складно: en туди чи сюди — не проблема. Просто число цих графів таке велике, що ви втомитеся перебирати кожен. Хотілося б зрозуміти, які послідовності можна порахувати, а які не можна. У всіх цих графах — можна.



Тепер розглянемо класи перестановок. З цього моменту я буду говорити тільки про перестановки. Дам наступне визначення. Співробітники Яндекса мене насварили — я не знав потрібного слова по-російськи. Я буду використовувати слово «патерн». Ми говоримо, що одна перестановка містить іншу, коли вона записана як 0-1-матриця, що містить іншу як подматрицу. Наприклад, перестановка (5674321) містить подматрицу (321) — її просто видно.

З іншого боку, вона не містить (4321), тому що в цій перестановці немає спадної підпослідовності довжини 4. А (321) — містить. Викидаємо перший стовпець, п'ятий, сьомий, те ж саме з рядками.

Так от, цю маленьку перестановку ми будемо називати паттерном. Ми її або кілька таких зафіксуємо, після чого почнемо вивчати послідовність числа перестановок, які не містять жодного патерну. Не містити патерну — значить уникати його, σ avoids ω.

Це дуже важливе визначення. Я хочу, щоб хтось підняв руку і сказав: «Так, я зрозумів».

Окей, ще раз. Ми скажемо, що одна перестановка містить іншу, якщо відповідна 0-1-матриця містить іншу. Є дві перестановки — велика і маленька, і видно, як одна містить іншу як подперестановку. Після чого ми вважаємо перестановки, які уникають деяких інших перестановок. Простий приклад. Припустимо, патерн — перестановка (12). Скільки існує перестановок довжини 7, які уникають такого патерну? Одна. Професор Карасьов знає, що якщо уникати патерну (12), то перестановка повинна бути всюди спадною, ніякі два не повинні зростати. А така перестановка тільки одна: (7654321).

Але у нас може бути не один, а кілька патернів. Тоді ми намагаємося уникати їх усіх.



Давайте наведу конкретний приклад. Розглянемо перестановки, які уникають патерну (123), тобто в перестановці немає зростаючої підпослідовності довжини 3. Знаючи стандартну комбінаторику, можна відповісти так: це означає, що вона складається з об'єднання двох спадних послідовностей, які таким чином перемішані. Виявляється, це стара теорема Макмахона 1915 року — кількість перестановок дорівнює числа Каталана. Тому якщо взяти іншу перестановку довжини 3, неважливо яку, то для них це буде число Каталана. І число перестановок, які уникають патерну (213), теж буде числом Каталана. Це теорема Батога, яку він довів, але з точністю до симетрії, що є два типи патернів довжиною 3: один такий і один такий. Інші виходять переворотом. Чи можна відняти 4, 4, 4 — всю перестановку. Тоді підрахунок буде точно таким же.

Я не довів теорему, це хороша вправа, особливо ось ця частина не так очевидно вважається. Але порахувати можна. Це настільки знаменита теорема, що у неї зараз є десятки доказів. Деякі з них дуже гарні, об'єктивні, деякі досить складні, рекурентні, але перед нами досить стандартна теорема, з якої все починається.

Наука, якою ми займаємося, досить велика. Є чимало інших випадків. Наприклад, якщо у нас є пункт 2, три перестановки — значить, ми уникаємо і такого патерну, і такого, і такого. Число виявиться досить маленьким, послідовність буде рівною послідовності Фібоначчі. Виявляється, що з допомогою цього можна отримати багато різних інших послідовностей. Зокрема, можна вивчати послідовності, які виходять у тому випадку, якщо ви уникаєте патерну (1342). І для кожного патерну або набору шаблонів можна спробувати порахувати, до якого класу належить виходить послідовність чисел перестановок, яких уникають зазначені патерни.

І спільне завдання — зрозуміти, як від безлічі патернів залежить клас, куди потрапляють ці послідовності. Ми вважаємо перестановки, які не містять якихось подперестановок, і намагаємося зрозуміти, як вони влаштовані.



Гіпотеза Нунана і Зайлбергера, якій багато років, звучить приблизно так: якщо у нас є будь-який набір паттернів, то послідовність числа перестановок, які уникають цього набору шаблонів, завжди буде Р-рекурсивну, а еквівалентна твірна функція буде задовольняти звичайному диференційному рівнянню.

Причина цієї гіпотези полягає в тому, що є кілька сотень прикладів, для яких це твердження вірне. Деякі з них я навів на попередньому слайді. Але теорема, яку ми нещодавно довели, полягає в тому, що гіпотеза невірна, хоча спростувати її досить складно. Ми придумали набір з приблизно 31 тисячі перестановок 80 елементів і довели, що для зазначеної послідовності немає рекурсивного співвідношення з поліноміальними коефіцієнтами.

Я не можу вам привести 31 тис. перестановок — навіть не буду намагатися. Трохи поясню, звідки все береться, але ми не намагалися нічого поліпшити. Може, можна зробити менше. Що таке кілька тисяч перестановок між друзями? Дурниця. Тим більше, що мова про перестановки всього 80 елементів. Така наша головна теорема.



Щоб ви спробували її зрозуміти, спочатку поясню історію, а потім наведу деякі теореми, що ілюструють, звідки все береться і як це в принципі довести. Питання, про яке йде мова, — старий. Він виник у 90-х роках, коли ця область стала бурхливо розвиватися. Не буду розповідати, що таке посилена версія, але Апкинсон довів: питання Нунана і Зайлбергера еквівалентний питання Гесселя — гіпотезою 1990 року. Але сам Зайлбергер передумав і в якийсь момент вирішив, що гіпотеза, швидше за все, невірна. Але вже в цьому конкретному випадку, якщо є тільки одна перестановка довжини 4, (1324), послідовність перестановок, не містять такий патерн, не буде Р-рекурсивну. Однак це відкрита завдання.

Наш приклад складається з 31 тис. перестановок, а тут тільки одна перестановка довжини 4. Здавалося, якась нісенітниця, можна сісти і порахувати, а от не виходить. Навіть для Р-рекурсивних послідовностей дуже складно щось довести. Якщо послідовність Р-рекурсивна, то ви можете привести співвідношення в явному вигляді. Якщо послідовність не Р-рекурсивна, то як ви це доведете? У цьому і полягає складність.



Що ж ми насправді зробили? Ми довели більш сильний результат. Він полягає в тому, що для досить великого класу функцій існує два таких набору шаблонів F і F', що різниця між числом перестановок, які містять один і інший по модулю 2, якраз і буде тією самою функцією, яку ми обрали. Для приблизного розуміння: це буде вычислимая функція. Для всіх вычислимых і дуже поганих функцій ми можемо придумати два дуже поганих набору шаблонів.

Теорема 2. Припустимо, у нас є два набору шаблонів, F і F'. Ми хочемо зрозуміти, чи завжди їх різниця є парної? Мова про різницю для числа перестановок, яке містить один патерн, мінус число перестановок, що містить інший патерн. Інакше кажучи, у них завжди буде одна і та ж парність чи ні?

Виявляється, це нерозв'язна задача. Немає жодної машини Тьюринга, яка може вирішити її — в яку ви покладете F і F' у якості вхідних даних і вихідний відповідь буде «Так» або «Ні». У якийсь момент парність зміниться.

Завдання про те, яка парність у кількості перестановок, уникають цього набору шаблонів, може бути як завгодно складною. Я навів саме такий приклад — не дуже хотів багато писати, тут і без того багато ступенів двійки. Думаю, що їх може бути і більше.



Отже, для будь-якого k існує два таких набору перестановок, що в перший раз вони поміняють парність дуже далеко. Якщо б вони змінили її близько, можна було б написати машину Тюрінга і перевірити парність до цього місця. Отже, існує два набори, у яких багато-багато однакової парності. А потім — раз, стали різні. Для цього немає ніякої причини, але саме так все і працює.

Перейдемо до іншого, стандартного слідства з тієї ж теореми розв'язності. Існує два набори перестановок, для яких не можна ні довести, ні спростувати, що парність у них завжди однакова. Вона не залежить від вашої аксіоматики. Такі набори патернів — в них можна засунути будь-яку логіку. Це приблизно те ж саме, що і континуум-проблема. Мова йде про задачі, яка є незалежною від теореми Франкліна і Чойза.

Значить, порахувати число дуже складно, але ми не можемо довести, що це складно. Ми можемо довести це тільки по модулю 2.



Ми досі не знаємо, чи є справедливим вислів Р = NP. Зате ми знаємо багато інших обчислювальних завдань: ми знову ж таки не знаємо, чому вони відповідають, але можемо багато чого написати.

Що таке NP? Наприклад, якщо завдання містять Гамільтонів цикл, то вона лежить у NP. Якщо я дам вам Гамільтонів цикл і скажу перевірити, чи є він насправді Гамильтоновым, то таке завдання можна виконати за полиномиальное час.

Далі є ⊕P. Ми говоримо, що хочемо порахувати парність числа Гамильтонова циклу в графі. Це дуже проста і природна річ. Але виявляється, що завдання Р = ⊕P доволі схожа на Р = NP — чи ні. Якщо сказане було б правдою, якби Р дорівнювало ⊕P — тоді вся поліноміальна ієрархія схлопывается, все можна вирішити за полиномиальное час на машині з ймовірностями. Тобто виявляється, що здатність вказати парність числа Гамільтонових циклів в графі дуже показово. Якщо ви таке можете зробити, то ви можете взагалі все порахувати, зокрема — число Гамільтонових циклів в графі і т. д. Парність — дуже цінна річ.

Мені потрібно те ж саме, але коли у нас все експоненційний. Пам'ятайте, що нам треба за полиномиальное час порахувати n-ий елемент послідовності. Але imput size n складається з log (n) bits, тобто n можна записати за допомогою log (n) нулів і одиниць. Тому завдання, яке вирішується за полимиальное час від n, насправді вирішується за експоненційний час від input. Тому нам потрібно все те ж саме, але замість P ≠ ⊕P ми пишемо EXP ≠ ⊕EXP. Можна подумати, що у нас input вводиться в unary, not in binary. Такий ось вам двохвилинний курс Computation Complexity.



Ось наша третя теорема, яку ми довели. Якщо EXP ≠ ⊕EXP, то існує кінцевий набір — теж приблизно 31 тисяча — таких патернів, що послідовність числа перестановок, не містять ці патерни, не може бути отримана за час, полиномиальное від n. Зокрема, є випадки, коли не буде ні defined, ні AD, але це теорема 1 без додаткової умови, а це — при умовах з Computation Complexity. Мова йде про умовну теорема, теорема один була безумовна. У якомусь сенсі та сильніше, в якомусь сенсі — ця.

Отже, якщо у вас є завдання і ви, наприклад, впевнені, що порахувати парність певного числа зв'язних графів на n елементів з точністю до ізоморфізму — складно і неможливо за полиномиальное час, то порахувати послідовність цих перестановок теж дуже складно.

Я навів один з можливих відповідей на старе питання 1982 року: чи існує якась розумна комбінаторна послідовність, для якої не було б алгоритму підрахунку за полиномиальное час? Наскільки вона природна чи ні? У нас все-таки 31 тис. перестановок довжини 80 — тут можна сперечатися, природна це завдання чи ні. Але, принаймні, весь клас досить природний і ми при додаткових умовах з Computation Complexity можемо сказати, що так, ці числа не можна порахувати за полиномиальное час, і що навіть парність не можна порахувати за полиномиальное час.



Давайте я пропущу всякі автомати і наведу лемму, зрозуміти яку досить легко. Це дуже важлива лемма, на її доказ ми витратили кілька годин, а придумували ми її десь півроку. Отже, лема 1. Візьмемо поліноміальну рекурсивні послідовність. Запишемо нескінченну послідовність нулів і одиниць — просто будемо дивитися на парність елементів цієї Р-рекурсивну послідовності. Перша парна — поставимо 0, друга непарна — поставимо 1 і в підсумку напишемо нескінченне слово з нулів та одиниць. І виявляється, що існує кінцеве слово з нулів і одиниць, яке не є подсловом зазначеної нескінченної послідовності. Ось така лема. В принципі, не важка, але дуже важлива.

Повернемося до визначення Р-рекурсивну послідовності. Якщо всі ці співвідношення дорівнюють нулю, то r0(n)an + r1(n)an-1 дорівнюватиме нулю. Але це не працює. Оскільки треба ділити, лема виходить досить складною, але не занадто.



Рішення таке. Ми будуємо явну машину Тюрінга. Вона в якомусь формальному сенсі записує послідовність 0, 1, 0,0, 0,1, 1,0 1,1, 0,0,0, 0,0,1 0,1,0, яка суперечить сказаному і містить всілякі кінцеві подслова.



Тепер найскладніша лема. Вона полягає в наступному: для будь-якої машини Тюрінга ми можемо створити два набору шаблонів і емулювати машину патернами так, щоб записувалася будь-яка послідовність нулів і одиниць. Я досить мало що сказав, не хочу розписувати докладно. Але щоб було трохи зрозуміліше, звідки береться матриця 80 на 80, ось.



Ми беремо матрицю розміром не більше, ніж 8х8. Але це блокові матриці, і в них ми розставляємо якісь літери, відповідні певним блокам 10х10, які ми забороняємо. Один набір містить трохи більше, ніж інший, але в результаті у нас виходять матриці приблизно такого розміру:



Єдині матриці, які уникають підматриць, — ті, які йдуть уздовж діагоналі і прямо кодують те, що машина Тьюрінга робить. Загальна ідея полягає в тому, що ми беремо машину Тюрінга і симулируем її з допомогою найпростіших комбінаторних об'єктів, патернів. Ми робимо так, щоб великі матриці, які уникають підматриць, мали такий вигляд, схожий на те, як працювала сама машина Тюрінга.



Не можу нічого сказати про доказ — воно досить довге і технічне. Ми використовуємо досить багато всього. Я сказав про блоки 8х8 і про матриці 10х10. Гіпотеза, яку я можу сформулювати… Пам'ятаєте лемму 1 про послідовність нулів і одиниць? Це дуже слабкий результат. Його достатньо для нашої теореми, але ми думаємо, що якщо ця послідовність Р-рекурсивна, то число можливих подслов з нулів і одиниць, наявних там в принципі, — не більше, ніж лінійне. Ми не можемо це довести, навіть полиномиально. Все, що ми можемо, стосується числа менше, ніж 2n. Але також ми можемо взяти число менше, ніж 1 + εn або ніж якесь ε, але ми не можемо довести, що для числа з подслов нулів і одиниць у Р-рекурсивну послідовності знайдеться субэкспоненциальная функція. І як раз цю гіпотезу ми довели.



Ми доказ ще навіть поки не опублікували. Воно посилює попередню теорему. Ми вміємо доводити, що наш набір не тільки не буде Р-рекурсивным, але не буде навіть ADE. Це останній клас, який ми сформулювали. За допомогою шаблонів можна задавати дуже погані послідовності. Ключова ідея полягає в тому, що не існує послідовності, що задовольняє алгебри диференціальних рівнянь, які є парними тільки для K! + K і тільки для таких n.

Це дуже динамічна послідовність. Йдеться про функцію Діріхле, там були n2. Це випадок, коли одні були непарними, а решта — парними. Це До! + До, і ми говоримо, що послідовність, непарна в цьому разі і парна в інших випадках, ніколи не задовольняє алгебри диференціальних рівнянь. Ось я вам і розповів про лемму, яку ми довели і використовуємо.



Звідки все це береться? Як до такого можна додуматися? Є дві причини, за якими ми до цього додумалися. Одна полягає в тому, що ми досить добре розуміємо, як працює замощення або Wang tiles. Ми замощаем величезний квадрат маленькими квадратиками 1х1. Припустимо, межі квадрата розписані деяким періодичним чином. Є кінцевий набір цих Wang tiles, маленьких подквадратиков. Мова про дуже стандартну і знамениту завдання: чи можна замостити всю площину у випадку, коли у нас немає межі, а є просто набір? Це нерозв'язна задача, а крім того, це ще й знаменита теорема.

Але у випадку, коли у нас є кінцевий квадрат з зафіксованими межами, цю задачу теж досить багато вивчали. Про неї все зрозуміло. Ця задача така ж, як наша, вони трохи схожі. В ній все можна робити скільки завгодно складно. Але з-за того, що об'єкти простіше, про них все досить добре відомо.

Завдання Концевича не буду розповідати.





Швидко розповім кілька гіпотез. Перша така: я вам дам два набору заборонених патернів і число перестановок, які забороняють 1. Чи вірно, що воно завжди дорівнює тій, яка не містить інше? Ми вважаємо, що така задача нерозв'язна, але це не випливає з того, що ми довели. З того, що ми довели, випливає, що вона нерозв'язна по модулю 2, тобто що парність нерозв'язна. Може бути, вони відразу починають бути дуже різними, рости дуже по-різному? Ми не знаємо, чи вірно це чи ні.

З іншого боку, ми вважаємо, що якщо у нас є тільки одна перестановка, то всі завдання розв'язані. Можна зрозуміти, що число таких дорівнює числу таких. Це, може бути, навіть можна зрозуміти за полиномиальное час — ми не знаємо. У нас набір з 31 тисячі патернів. Що буде, коли перестановка тільки одна, сказати складно.

Однак ми думаємо, що Зайлбергер прав і послідовність перестановок, не містять таку подперестановку, не буде Р-рекурсивну.

Остання гіпотеза говорить про те, що завдання порахувати числа, які не містять патерни, складна у своєму обчислювальному класі. Навіть щоб її просто сформулювати, потрібен деякий час.

Власне, все. Всім спасибі.
Джерело: Хабрахабр

0 коментарів

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