Борис Алексеев, Эван Конвей, Матьё Розенфельд, Эндрю Сазерленд, Маркус Ур, Кевин Вентуло и я загрузили на arXiv вторую версию нашей статьи «Разложение факториала на крупные множители» 🧩. Это полностью переработанная и расширенная версия предыдущей работы с тем же названием. Благодаря новым теоретическим и численным данным от соавторов, нам удалось значительно уточнить ключевой параметр исследования, что позволило окончательно доказать все ранее выдвинутые гипотезы на эту тему 🔍.
Что изучали?
Как обсуждалось в предыдущем посте, \( f(n) \) — это наибольшее целое число, такое что факториал \( n! \) можно представить в виде произведения \( f(n) \) множителей, каждый из которых не меньше \( n \). Расчёт \( f(n) \) — частный случай NP-сложной задачи о покрытии (bin covering problem) 💻. До нашей работы \( f(n) \) была известна лишь для \( n \leq 10 \), теперь же мы вычислили её для всех \( n \leq 20 \) 🎯. Более того, мы получили точные асимптотики и границы для \( f(n) \) даже при больших \( n \), включая формулу
\[
f(n) = \frac{n}{\log n} \left( C + o(1) \right),
\]
где \( C \) — явная константа. Мы также предполагаем, что её можно улучшить до
\[
f(n) = \frac{n}{\log n} \left( \frac{\log \log n}{\log \log \log n} + o(1) \right).
\]
Доказанные гипотезы
Благодаря точным оценкам мы подтвердили гипотезы Гая и Селфриджа ✅:
1. \( f(n) \leq \frac{n}{2} \) для всех \( n \geq 2 \);
2. \( f(n) < \frac{n}{2} \) при \( n \geq 5 \);
3. \( f(n) < \frac{n}{3} \) при \( n \geq 162 \) (оказалось, это верно уже для \( n \geq 41 \), и этот порог нельзя улучшить).
⚠️ Интересный парадокс: Гая и Селфридж утверждали, что для больших \( n \) неравенство \( f(n) \leq \frac{n}{3} \) можно доказать, перегруппировывая множители \( 2 \) и \( 3 \) из стандартного разложения \( n! \). Однако выяснилось, что это утверждение не выполняется для всех \( n \geq 1 \) 🔄!
Методы достижения точности
- Жадные алгоритмы 🕹️: распределение простых множителей от больших к малым даёт быстрые (хотя и неоптимальные) нижние границы для небольших \( n \);
- Линейное и целочисленное программирование 📊: обеспечило сверхточные оценки для малых и средних \( n \);
- Асимптотический анализ перестановок 📈: эффективен для больших \( n \);
- Стратегия модифицированной факторизации 🔧: теперь использует гладкие числа (произведения \( 2 \) и \( 3 \)) вместо только степеней двойки.
Самым удивительным для нас стала невероятная точность методов линейного программирования 🤯. Благодаря множеству повторяющихся простых множителей в факториале, дискретная задача вела себя почти как непрерывная!