Штурм множин без арифметичних прогресій штучним інтелектом: реєстр того, що зайшло в глухий кут

TL;DR. ШІ-асистент працював над двома задачами про множини без прогресій: побудовою аргументу для задачі про суму обернених величин та квазіполіноміальною оцінкою для кожної фіксованої довжини прогресії.

Ключові висновки

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

Найкорисніше, що може сказати незавершене доведення - це те, де саме воно ламається, і це доведення ламається приблизно в дюжині конкретних місць.

Резюме для керівників

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

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

Було випробувано багато підходів: структуровані охоплюючі множини, одночасне вирівнювання частот, леми про розріджений підрахунок, згладжування Крута-Сісаска, підняття та ітерація, кути та ентропія на масштабі p = log M. Кожен із них зустрів зафіксовану перешкоду.

Фінальне обчислення залишилося незавершеним, без леми про обмеження чи принципу розрідженого підрахунку.

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

Дві задачі, і лише одна з них взагалі заявлялася як виконана #

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

Асистент не починає з нуля. Він використовує тричленний результат Блума та Сісаска для суми обернених величин як базовий рівень. Усе, що йде далі - це спроба просунутися далі за базовий рівень, або до довших прогресій, або до сильнішого кількісного твердження. Позначення фіксуються на початку. Для кожного k величина r_k(N) є найбільшим розміром підмножини {1, ..., N} без нетривіальної k-членної прогресії. Множина A щільності α = |A|/N є об'єктом дослідження, а нормалізована функція має вигляд f = 1_A/α.

Ця нормалізація визначає більшу частину того, що відбувається далі. Визначимо μ = 1_A/α так, що E[μ] = 1, і покладемо M = α^-1. Тоді логарифмічна розрідженість дорівнює p = log(1/α), що те саме, що й log M. Що розрідженішою є множина, то більшими стають M і p. Кожна наведена нижче перешкода у тій чи іншій формі є твердженням про те, що відбувається зі зростанням цієї розрідженості.

Спадання щільності - це не те саме, що сумовність #

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

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

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

Збереження структури, і чому випадок трьох членів не узагальнюється #

Один із запропонованих засобів - зберігати структуру під рукою. Асистент пропонує зберігати структуровані охоплюючі множини (ambient sets) через послідовні прирости. Ідея, обережно висловлена в джерелі, полягає в тому, що ви не повинні викидати структуровану множину, знайдену на одному етапі, переходячи до наступного.

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

Запис містить начерк із тензорним добутком щодо того, чи можуть фіксовані норми однорідності (uniformity norms) контролювати розріджені нормалізовані функції. Асистент не завершує цей начерк. Я волію повідомити про це, ніж натякати, ніби питання вирішене в той чи інший бік.

Вирівнювання частот один раз замість багатьох #

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

Далі в нотатці вказано, чого досі бракує. Величину S_h потрібно було б відновлювати з частот із великими кореляціями, принаймні exp(-poly). Це залишається вимогою, а не результатом. Кореляції, що впорядковуються, є кореляціями парних добутків f(x)f(x + h), де f = 1_A/α і α = |A|/N.

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

Рідкісні порожні фрагменти та ціна адаптивного заповнення #

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

Однією з відповідей є адаптивне заповнення (adaptive filling), і воно виставляє власний рахунок. Адаптивне заповнення вводить додаткові умови здійсненності, яких асистент не довів. Мажоранта є природним способом виключити рідкісні погані фрагменти. У цитованому тексті асистента сказано, що мажоранта на всіх рідкісних атомах, імовірно, є нереалістичною. Зауваження сформульоване обережно, але воно вказує геть від найпрямішого виправлення.

Саме цей патерн пояснює решту записів. Дешевий аргумент десь потребує нижньої оцінки, наявні інструменти дають верхні оцінки, а проміжок між ними заповнений рідкісними, розрідженими, порожніми об'єктами.

Запозичення апарату розрідженого підрахунку і виявлення того, що запозиченого недостатньо #

Асистент звернувся до наявної літератури з розрідженого підрахунку в пошуках переправи. Спробу сформували два джерела.

Щодо ущільнення (densification) Конлона-Фокса-Чжао асистент виявив, що воно спирається на двосторонні оцінки лінійних форм. Це важливо, оскільки тутешня постановка має структуру верхньої оцінки, а не двосторонню. Метод, побудований на двосторонньому контролі, недоступний, коли відома лише одна сторона.

Лема про підрахунок у розріджених графах Фільмуса, Хатамі, Хоссейні та Кельмана дала модель для асиметричних сіткових моментів та додатно напіввизначеного розбалансування. Тобто вона слугувала шаблоном, а не готовою теоремою для прямої підстановки. Та навіть попри це повернулася та сама трудність. Самі лише верхні оцінки неодноразово натикалися на розріджені діри. Додатковий нюанс ускладнює інтерпретацію сіткових моментів: великі центровані сіткові моменти можуть відображати відсутню масу, а не концентрацію вгору. Великий момент виглядає як свідчення концентрації, але він так само може породжуватися масою, якої там немає. Ця неоднозначність є проблемою розріджених дір, якщо дивитися на неї з боку моментів.

Далі асистент розглянув малі степеневі втрати за M. Він не отримав придатної теореми про підрахунок. Це чистий негативний результат, і він звужує поле пошуку: навіть дозволивши аргументу втратити малий степінь M, придатної теореми про підрахунок знайдено не було.

Згладжування виявилося надто дорогим для застосування #

Згладжування Крута-Сісаска (Croot-Sisask smoothing) є стандартним шляхом до регуляризації множини перед підрахунком. Асистент розглянув його і виявив, що необхідна точність є надто витратною в запропонованому застосуванні. Метод не був хибним. Його ціна перевищувала те, що міг заплатити аргумент.

Та сама економіка керує й іншими шляхами. Для розшарованих (fibre) аргументів оцінки на шарах не перемножувалися автоматично, а сфери сталої норми перешкоджали очікуваному сильному спаданню над фіксованими цифровими алфавітами. Структура добутку підказує, що оцінки на частинах мали б поєднуватися в оцінку на цілому, але тут цього не сталося. Спроби підняття (lifting) та ітерації все одно втрачали надто багато кількісно.

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

Один рядок оптимізму, і арифметика, яка його підірвала #

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

Потім асистент помітив у ньому проблему. Знакозмінні розклади могли мати абсолютну масу порядку 2^p, що повністю перекриває поліноміальну точність. Нагадаємо, що p = log M. Поліноміальна точність за M є скромною ціллю, тоді як знакозмінний розклад із масою порядку 2^p є експоненційно більшим. Точність реальна, але взаємне скорочення, на яке вона покладається, не може поглинути таку масу.

Я вважаю цей запис найповчальнішим у реєстрі, оскільки він показує, як працює самоперевірка. Твердження зі знаком оклику було переглянуто, і арифметика, на якій воно трималося, виявилася недостатньою. Саме так виглядає чесний робочий протокол. Ентузіазм і виправлення містяться в одному документі.

Кути та коробки не складаються в довші прогресії #

Інша стратегія полягала у використанні сильнішого відомого результату як сходинки. Квазіполіноміальна оцінка для кутів (corners) є відповідним інструментом, але отримані кути не складалися автоматично в довші прогресії. Кут - це двовимірний патерн, а довга прогресія - одновимірний, і перехід між ними не є автоматичним.

Чотиричленний коробковий підрахунок (box count) створює споріднену трудність. Додатність чотиричленного коробкового підрахунку не контролювала його виняткову діагональ. Додатний підрахунок усе ще може домінуватися виродженими конфігураціями, і саме на діагоналі вони живуть.

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

Перехід до ентропії на масштабі p = log M #

Коли прямі шляхи підрахунку виявилися заблокованими, дослідження повернуло в бік ентропії на масштабі p = log M, спираючись на використання високих моментів за методом Келлі-Меки. Вибір масштабу не є довільним: p = log M - це саме та логарифмічна розрідженість, визначена на початку.

У цитованому тексті асистента пропонується використовувати ентропію замість L2 завдяки невід'ємності та частотній дисоціативності (Чанг). Це пропозиція, а не результат. Міркування полягає в тому, що μ = 1_A/α є невід'ємною, а дисоціативність Чанга дає структуру на частотному боці, тож ентропія могла б виконати роботу, на яку не здатна величина в L2.

Щоб це спрацювало, асистенту були потрібні конкретні аналітичні вхідні дані. Асистент шукав оцінку обмеження Фур'є ||g_hat||_q = O(1) для обмеженої g та фіксованого q > 2 за відповідних локальних верхніх оцінок. Це була ціль. Її не було встановлено.

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

Обчислення, яке підійшло найближче #

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

Але воно не може перетнути поріг показника три, необхідний для запропонованого аргументу підрахунку. У витягу асистента відзначається слабка оцінка в l3 зі згортки та обмеження (cap), а також те, що для інтерполяції потрібен строго кращий показник (менший за 3). Простими словами, обчислення приземляється якраз по неправильний бік лінії. Оцінки з показником три недостатньо, і інтерполяція потребує чогось строго кращого.

Спокусливо трактувати такий близький промах як "майже біля цілі". Я б утримався від цього. У записі не сказано, наскільки далеко обчислення перебуває від порога, а розрив в один показник усе ще може становити всю проблему. Про що запис справді говорить, то це про те, що асистент залишив обчислення незавершеним, не вивівши ані леми про обмеження, ані принципу розрідженого підрахунку. Ці дві відсутні ланки є відкритим боргом проєкту.

Чого вартий цей реєстр #

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

Документ конкретний. Він називає перешкоду на кожному роздоріжжі: рідкісні порожні фрагменти, відсутня маса в сіткових моментах, двосторонні оцінки у Конлона-Фокса-Чжао, експоненційна за p знакозмінна маса, виняткова діагональ чотиричленного коробкового підрахунку, від'ємні кубічні внески. Він відрізняє продемонстроване обмеження від очікуваного механізму. Він позначає рекурентне співвідношення для сумовності як те, що могло б спрацювати, а другу задачу - як те, що шукається. Він прямо каже, чого асистент не завершив.

Для засновника чи технічного лідера, який оцінює дослідження за допомогою ШІ, саме це і варто шукати. Систему, яка повертає впевнений, завершений на вигляд аргумент, важко перевірити. Систему, яка повертає список названих невдач, де єдиний майже успіх чітко позначений як такий, що не дотягнув до порога, можна перевірити рядок за рядком. Хтось може взятися за проблему показника три або за проблему залежних кластерів і точно знати, якою є стартова позиція.

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

Отже, відкрите питання, яке порушує цей запис, є вузьким і придатним до перевірки. Чи можна отримати оцінку, строго кращу за показник три, за тих самих гіпотез згортки, які вже дають граничну оцінку? Якщо так, то інтерполяція матиме з чим працювати. Якщо ні, то шлях обмеження Фур'є та принцип розрідженого підрахунку, жоден із яких не було виведено, є тими місцями, куди слід дивитися далі.

Часті запитання #

Які дві математичні задачі досліджував ШІ-асистент?

Асистент працював над двома пов'язаними завданнями щодо множин без арифметичних прогресій: розбудовою аргументу для задачі про суму обернених величин та пошуком квазіполіноміальної оцінки для кожної фіксованої довжини прогресії k. Хоча він використовував тричленний результат Блума та Сісаска як базовий рівень, квазіполіноміальної оцінки для довільних довжин прогресії досягнуто не було.

Чому верхні оцінки щільності не змогли дати необхідну лему про підрахунок?

Верхні оцінки щільності на структурованих фрагментах допускають рідкісні порожні фрагменти, тобто верхня оцінка того, скільки елементів множини A лежить усередині фрагмента, не гарантує, що там взагалі є елементи A. Упродовж кількох спроб самі лише верхні оцінки неодноразово натикалися на розріджені діри, а великі центровані сіткові моменти могли відображати відсутню масу, а не концентрацію вгору.

Де саме зупинилося фінальне обчислення?

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

Джерела #

Thomas F. Bloom and Olof Sisask, (2020). Breaking the logarithmic barrier in Roth's theorem on arithmetic progressions ⧉. arXiv.
Zander Kelley and Raghu Meka, (2023). Strong Bounds for 3-Progressions ⧉. arXiv.
David Conlon, Jacob Fox, and Yufei Zhao, (2014). A relative Szemerédi theorem ⧉. Geometric and Functional Analysis.
Ernie Croot and Olof Sisask, (2010). A probabilistic technique for finding almost-periods of convolutions ⧉. Geometric and Functional Analysis.

Останній перегляд 2026-11-01.

Перевидати цю статтю

Штурм множин без арифметичних прогресій штучним інтелектом: реєстр того, що зайшло в глухий кут — Sebastien Rousseau

ШІ-асистент працював над двома задачами про множини без прогресій: побудовою аргументу для задачі про суму обернених величин та квазіполіноміальною оцінкою для кожної фіксованої довжини прогресії.

Ця стаття поширюється за ліцензією Creative Commons Attribution 4.0 International. Перевидання вимагає посилання на канонічну URL-адресу.

Штурм множин без арифметичних прогресій штучним інтелектом: реєстр того, що зайшло в глухий кут — Sebastien Rousseau

ШІ-асистент працював над двома задачами про множини без прогресій: побудовою аргументу для задачі про суму обернених величин та квазіполіноміальною оцінкою для кожної фіксованої довжини прогресії.

Originally published at https://sebastienrousseau.com/uk/2026-10-24-shturm-mnozhyn-bez-aryfmetychnykh-prohresiy-shtuchnym/ by Sebastien Rousseau.
Licensed under CC-BY-4.0.

SEBASTIEN ROUSSEAU FOUNDER · ENGINEER