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

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. Каждое описанное ниже препятствие в той или иной форме представляет собой утверждение о том, что происходит по мере роста этой разреженности.

Убывание плотности - это не то же самое, что суммируемость #

Первое препятствие возникает на уровне архитектуры доказательства, еще до всякого анализа Фурье. В записях прямо сказано, что качественное убывание плотности само по себе не обеспечивает нужную суммируемость. Недостаточно просто знать, что плотности сжимаются при переходе от масштаба к масштабу. Для задачи о сумме обратных величин необходимо, чтобы это сжатие оценивалось достаточно точно для суммирования ряда.

Заманчивый выход - рекуррентное соотношение. В заметках говорится, что достаточно сильная рекуррентность для экстремальных плотностей множеств без прогрессий могла бы дать суммируемость по экспоненциальным масштабам. Эта фраза сформулирована осторожно, и такой она и должна оставаться. Она описывает, что могла бы дать гипотетическая сильная рекуррентность, но не предъявляет ее.

Вторая издержка отделена от первой. Ассистент указывает на накопление множества слабых корреляций как на дополнительную плату. Каждая отдельная корреляция может быть безобидной, тогда как их сумма - уже нет. Эта тема повторяется вновь и вновь: шаг, который обходится дешево один раз, становится дорогим, когда его приходится повторять.

Сохранение структуры и почему случай трех членов не обобщается #

Одно из предложенных средств - не выбрасывать найденную структуру. Ассистент предлагает сохранять структурированные объемлющие множества на протяжении последовательных приращений. Идея, осторожно сформулированная в источнике, состоит в том, что не следует отбрасывать структурированное множество, найденное на одном шаге, при переходе к следующему.

У трехчленного случая есть особенность, которой лишены более длинные прогрессии. Механизм положительности, полезный для трехчленных прогрессий, не переносится напрямую на более длинные корневые подсчеты. Это первое из нескольких мест, где препятствие специфично именно для k больше трех. В более поздней заметке та же мысль высказана в общих чертах: более длинные прогрессии порождают дополнительные препятствия высших порядков.

В записях есть набросок через тензорные произведения по вопросу о том, могут ли фиксированные нормы равномерности контролировать разреженные нормированные функции. Ассистент не доводит этот набросок до конца. Я предпочитаю зафиксировать это прямо, а не создавать впечатление, будто вопрос решен в ту или иную сторону.

Выравнивание частот за один раз вместо множества шагов #

Последовательное выравнивание частотных функций - именно то место, где проблема накопления потерь бьет сильнее всего. Если каждое выравнивание стоит немного, то длинная цепочка таких шагов обходится очень дорого. Ассистент предлагает выравнивать несколько частотных функций одновременно вместо того, чтобы накапливать потери при последовательном выравнивании. Пометка на полях формулирует это предельно прямо: «Никаких итеративных потерь, если выровнять все частоты сразу». Как и само предложение, которое она резюмирует, эта фраза условна: она описывает, какую выгоду дало бы одновременное выравнивание, если бы оно сработало.

Затем в заметке указывается, чего все еще не хватает. Величину S_h нужно было бы восстанавливать по частотам с большими корреляциями, по меньшей мере порядка exp(-poly). Это остается требованием, а не доказанным результатом. Упорядочиваемые корреляции относятся к попарным произведениям f(x)f(x + h), где f = 1_A/α и α = |A|/N.

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

Редкие пустые куски и цена адаптивного заполнения #

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

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

Именно эта схема объясняет всю остальную часть архива. Экономному рассуждению где-то нужна нижняя оценка, доступные инструменты дают верхние оценки, а зазор между ними заполняют редкие, разреженные, пустые объекты.

Заимствование аппарата разреженного подсчета и обнаружение того, что заимствованного недостаточно #

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

В отношении уплотнения Конлона-Фокса-Чжао ассистент обнаружил, что оно опирается на двусторонние оценки линейных форм. Это критично, поскольку в рассматриваемой задаче структура оценок односторонняя (верхняя), а не двусторонняя. Метод, построенный на двустороннем контроле, недоступен, когда известна только одна сторона.

Лемма о подсчете разреженных графов Фильмуса, Хатами, Хоссейни и Кельмана послужила моделью для асимметричных сеточных моментов и положительно полуопределенной разбалансировки. Таким образом, она выступила в роли шаблона, а не готовой к подстановке теоремы. Но даже при этом вернулась та же самая трудность. Одни лишь верхние оценки раз за разом натыкались на разреженные дыры. Дополнительная тонкость затрудняет интерпретацию сеточных моментов: большие центрированные сеточные моменты могут отражать недостающую массу, а не концентрацию вверх. Большой момент выглядит как свидетельство концентрации, но с тем же успехом он может порождаться массой, которой там нет. Эта двусмысленность - проблема разреженных дыр, увиденная со стороны моментов.

Далее ассистент рассмотрел малые степенные потери по M. Подходящей теоремы о подсчете он не получил. Это чистый отрицательный результат, и он сужает поле поиска: даже если позволить аргументу потерять малую степень M, подходящая теорема о подсчете не находится.

Сглаживание оказалось слишком дорогим в применении #

Сглаживание Крута-Сисаска - стандартный способ регуляризовать множество перед подсчетом. Ассистент рассмотрел его и обнаружил, что требуемая точность обходится слишком дорого в предлагаемом применении. Сам метод не был ошибочным. Просто его цена превышала то, что могло заплатить рассуждение.

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

Следующим был рассмотрен подход приближенной двойственности Бен-Сассона-Рон-Зеви. Ассистент обнаружил, что рассматриваемая итерация теряет слишком много количественно. Это тот же самый вердикт, что и при попытке подъема, но полученный с другой стороны; это наводит на мысль, что корень трудности кроется в самой итерации, а не в какой-то одной конкретной конструкции. Я оставлю это как наблюдение о закономерности, а не как доказанный диагноз.

Одна строчка оптимизма и арифметика, которая ее подорвала #

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

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

Я считаю эту запись самой поучительной во всем реестре, потому что она показывает, как работает самопроверка. Утверждение, сделанное с восклицательным знаком, было пересмотрено, и арифметика, на которой оно держалось, оказалась несостоятельной. Именно так выглядит честный рабочий журнал. И энтузиазм, и исправление находятся в одном и том же документе.

Углы и коробки не собираются в более длинные прогрессии #

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

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

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

Переход к энтропии на масштабе p = log M #

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

Цитируемый текст ассистента предлагает использовать энтропию вместо L2 за счет неотрицательности и диссоциативности частот (по Чанг). Это предложение, а не готовый результат. Логика состоит в том, что функция μ = 1_A/α неотрицательна, а диссоциативность Чанг дает структуру на частотной стороне, поэтому энтропия могла бы выполнить ту работу, с которой не справляется L2-величина.

Чтобы это сработало, ассистенту требовался конкретный аналитический вход. Ассистент искал оценку ограничения Фурье ||g_hat||_q = O(1) для ограниченной функции g и фиксированного q > 2 при подходящих локальных верхних оценках. Это была цель, но она не была доказана.

Препятствие проявилось на следующем шаге. Извлечение структуры из старших моментов теряло слишком много массы. Старшие моменты - именно то место, где аргументы в стиле Келли-Меки набирают силу, а здесь они оказались местом, где рассуждение растеряло то, что ему необходимо было удержать.

Вычисление, которое подошло ближе всего #

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

Однако оно не преодолевает порог показателя три, необходимый для предлагаемого аргумента подсчета. В выдержке ассистента отмечается слабая оценка в l3 из свертки и шапки, а также то, что для интерполяции нужен строго лучший показатель (ниже 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. При повторной публикации требуется указание канонической ссылки.

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

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

Originally published at https://sebastienrousseau.com/ru/2026-10-24-shturm-mnozhestv-bez-progressiy-silami/ by Sebastien Rousseau.
Licensed under CC-BY-4.0.

SEBASTIEN ROUSSEAU FOUNDER · ENGINEER