Пробив в математиката на дисбаланса след 30 години

Двама теоретични информатици постигнаха първия голям напредък по един от най-упоритите въпроси в теорията на дисбаланса от близо 30 години насам. Никхил Бансал от Университета на Мичиган и Хаотиан Дзян от Чикагския университет свалиха горната граница за дисбаланс от квадратен корен от log(N) до четвърти корен от log(N) — резултат, който колегите им наричат „огромна стъпка напред“. За случая писа Quanta Magazine на 21 август 2026 г.

Важно уточнение още в началото: самата хипотеза на Комлош не е доказана. Бансал и Дзян се приближиха до нея драстично и по пътя решиха друга известна хипотеза — тази на Бек и Фиала — за определени диапазони на параметрите. Пълното твърдение остава отворено.

Снимка: Ada Zejun Shen / Quanta Magazine

Какво всъщност мери „дисбалансът“

Представете си, че делите група хора на два отбора за викторина. Всеки участник е добър в различни неща — история, музика, природа, кино. Искате двата отбора да са равни не общо, а по всяка категория поотделно.

Математически всеки човек е вектор с координати за отделните умения. Пращате ли го в отбор А, векторът остава какъвто е; пращате ли го в отбор Б, всички координати се умножават по −1. Целта е сборът на векторите да е възможно най-близо до нулата. Колкото по-далеч от нулата, толкова по-голям е дисбалансът.

Звучи като салонна задача, но същата структура се появява при планиране на клинични изпитвания, разпределяне на стоки между складове, оптимизация и машинно обучение.

Хипотезата на Комлош

В началото на 80-те унгарският математик Янош Комлош предположи нещо, което дори на него самия му се струва прекалено смело: дисбалансът никога не надхвърля една универсална константа — независимо колко са обектите и колко са измеренията.

Това е контраинтуитивно. Очаквате, че с повече категории задачата става по-трудна. Комлош твърди, че размерността няма значение. Години по-късно самият той се шегува пред Quanta: „Бях млад и глупав, когато я формулирах.“

Две стъпки за четири десетилетия

Напредъкът дотук се събира на един ред:

• 1985 г. — Джоел Спенсър доказва граница от порядъка на log(N), където N е броят вектори.
• 1998 г. — Войчех Баначчик я подобрява до квадратен корен от log(N).
• 2010 г. — Бансал показва, че задачата изобщо може да се атакува алгоритмично, което дотогава мнозина смятат за невъзможно. До 2016 г. алгоритмичният подход настига границата на Баначчик.

И там всичко засяда. Границата на Баначчик стои като рекорд почти три десетилетия.

Как падна рекордът

Пробивът идва през февруари 2025 г., когато Дзян гостува на Бансал в Ан Арбър за една седмица. Още на втория ден двамата имат следа.

Техниката им, наречена decoupling via affine spectral-independence, комбинира дискретно брауново движение с полуопределено програмиране. Алгоритъмът тръгва, като „разцепва“ всеки вектор наполовина между двата отбора, и после постепенно го прави цял чрез случайни стъпки.

Новото е, че двамата следят не само общия дисбаланс, а и зависимостта: ако разклатите една координата, колко се променя дисбалансът по останалите. Оказва се, че макар категориите да изглеждат силно преплетени, стъпките могат да се подберат така, че да не си пречат.

„Някак си, макар повърхностно да са свързани, можете да се движите така, че наистина да не си пречат“, обяснява Бансал.

Статията „Decoupling via Affine Spectral-Independence“ е качена в arXiv на 5 август 2025 г. и беше представена на STOC 2026 — 58-ият симпозиум по теория на изчисленията на ACM, проведен от 22 до 26 юни 2026 г. в Солт Лейк Сити.

Защо четвъртият корен е почти константа

Тук е практическата част. Четвъртият корен от log(N) расте мъчително бавно. За N = 10 стойността е около 1. За N = 10^81 — приблизително броят атоми в наблюдаемата Вселена — тя е едва около 3.

„Като в живота си няма да видите число, за което четвъртият корен от log(N) е повече от 5“, коментира Даниел Спилман от Йейл.

С други думи: за всяка задача, която реално ще срещнете, границата вече е константа във всичко освен в името.

Какво остава отворено

Бансал е скептичен, че неговият алгоритмичен подход ще стигне докрай: „Ударихме стена при четвъртия корен. Да се мине отвъд нея, определено ще изисква нещо съвсем ново.“

Резултатът обаче промени настроението в областта. Александър Николов от Университета в Торонто, който преди клонял към мнението, че хипотезата е невярна, казва, че сега е „доста по-уверен, че вероятно хипотезата всъщност е вярна“.

Има и техническа подсказка: четвърти корени рядко се появяват като естествени граници в подобни задачи. Това само по себе си подсказва, че последната дума не е казана.

Заключение

Не е доказателство и никой от участниците не го представя като такова. Но е първото истинско движение по проблем, който стоеше замразен от 1998 г., и то с метод, който вероятно ще намери приложение далеч отвъд конкретната задача — в оптимизацията, в дизайна на експерименти, в машинното обучение.

Такива резултати рядко излизат по новините, но точно те местят границата на познанието — както рекордът за квантово заплитане през 420 км оптично влакно, който също не променя нищо утре, но променя какво е възможно вдругиден.