Твердження OpenAI про швидше перетворення Фур'є викликає критику галактичного алгоритму

Що каже пост

Пост Бена Рехта від 12 жовтня 2026 року на arg min розглядає частину математичного репозиторію OpenAI, яка заявляє про швидше перетворення Фур'є. Він пише, що це твердження менш проривне і більш схоже на зловмисну експлуатацію, і каже, що роботу не читав. Натомість він використав чат-бота, щоб витягти головні факти з того, що називає математикою AI-слоп.

Перетворення Фур'є вимірює частотний склад за допомогою скалярних добутків. Для цифрового сигналу довжини n потрібно лише n скалярних добутків на кратних 2π/n. На перший погляд, наївний розрахунок вимагає операцій у квадраті n. Швидке перетворення Фур'є, розроблене Джеймсом Кулі та Джоном Тьюкі у 1965 році, розбиває вхід, обчислює два перетворення довжини n/2 і знову об'єднує результати. При повторенні log₂ n разів воно використовує менше ніж 5 n log₂ n операцій. Коли n дорівнює 1000, квадрат n становить 1 000 000, тоді як 5 n log n становить приблизно 50 000, тобто прискорення в 20 разів. Коли n дорівнює 1 000 000, прискорення становить 10 000 разів.

Чому прискорення галактичне

Рехт каже, що результат OpenAI лише трохи зменшує член log n у big O. Він стверджує, що big O може приховувати настільки великі константи, що алгоритм стає галактичним. За його оцінкою, C дорівнювала 10^100, коли N дорівнювала 10^12. За його ж словами, навіть коли n дорівнює 10^100, FFT Кулі та Тьюкі був би в 10^99 разів швидшим.

Модель також передбачає точну комплексну арифметику. Вона вимагає множення таких комплексних чисел, модулі яких разом із n ростуть суперполіноміально за одну операцію. При зберіганні у бітах вимога до пам'яті практично стає експоненційною залежно від довжини вхідних даних. Рехт зазначає, що Джек Моргенштерн у 1973 році довів, що перетворення Фур'є не може працювати швидше, ніж за n log n / 2, якщо комплексні коефіцієнти мали б обмежений модуль. Сорок років потому Нір Айлон показав, що обчислення FFT швидше, ніж за n log n, спричинило б важку числову нестабільність.

Ширша критика

Рехт пов'язує твердження про FFT з іншими результатами того самого репозиторію, зокрема з галактичним алгоритмом множення матриць O(n^2,25). За його словами, конструкція навіть не дає читачеві можливості оцінити константу, приховану в big O. Його ширша думка в тому, що теоретична комп'ютерна наука часто винагороджує доведення існування алгоритму без його запису або запуску на комп'ютері. На його думку, AI тепер може автоматизувати цю тенденцію та виробляти роботи, які формально оформлені, але призначені для комп'ютерів, які люди реально не будують.

Джерела: Arg Min