GPT-5.4 Pro впервые решила задачу из «зелёного списка» Бена Грина

GPT-5.4 Pro совместно с математиком Лиамом Прайсом решила задачу #1202 из базы Эрдёша — она же Problem 44 из «100 Open Problems» Бена Грина. Грин — соавтор знаменитой теоремы Грина — Тао о простых числах и один из ведущих специалистов по аддитивной комбинаторике; его личную подборку ключевых открытых задач неформально называют «зеленым списком». ИИ уже решал задачи из общей базы Эрдёша, но из курированной сотни Грина — впервые. Ответ оказался отрицательным: вопрос Эрдёша 1980 года получил контрпример.

Суть задачи: если для каждого из k простых чисел p запретить половину классов вычетов по модулю p, «схлопнется» ли множество целых чисел от 1 до n почти до нуля? Интуиция подсказывала, что да — и для простых меньше √n это действительно легко следует из большого сита. Но Эрдёш спрашивал про более широкий диапазон — вплоть до n^(1−ε). Сам он писал, что задача «кажется неразрешимой на данный момент», вероятно, потому что пытался доказать положительный ответ.

Прайс и GPT-5.4 Pro показали обратное: можно подобрать простые порядка √(n log n) и запрещённые классы так, что выживает линейно большая доля чисел — около (1/2 − c)n вместо ожидаемых ≤ εn. Конструкция использует интервалы, а «выжившее» множество содержит длинную арифметическую прогрессию.

На странице задачи теперь стоит статус «resolved in the negative». Это не первый AI-успех на задачах Эрдёша — в вики проекта erdosproblems зафиксированы десятки случаев разной степени значимости, — но первый результат из списка Грина.

P.S. Поддержать меня можно подпиской на канал «сбежавшая нейросеть,» где я рассказываю про ИИ с творческой стороны.