[Из песочницы] Обобщение задачи Брокара16.06.2019 15:32

История

Гильберт в 1900 году на II Международном конгрессе математиков в Париже отметил практическую важность теории чисел. Решение абстрактных задач часто приводило к появлению нового математического аппарата. Ярким примером служит Великая Теорема Ферма, в ходе доказательства которой в конце XX-ого века были исследованы мероморфные функции, применяющиеся современными инженерами-конструкторами на авто- и авиазаводах, а также IT-специалистами в рамках имитационного моделирования. Задачи о «красивых числах» — простых близнецах и совершенных числах, считавшиеся в Древней Греции практически бесполезными, теперь обеспечивают современную криптографию устойчивыми алгоритмами генерации ключей.

В 1913 году Рамануджан популяризирует неопределённое уравнение:

$n!+1=m^2 (1)$


Ранее оно фигурировало в работах Анри Брокара. Как утверждают историки, два математика занялись изучением указанного уравнения независимо друг от друга. Очевидно, факториал растёт быстрее квадрата, поэтому первые решения можно быстро получить перебором значений n. Получим:

$4!=5^2-1$

$5!=11^2-1$

$7!=71^2-1$

В 2000-ом году компьютерным перебором были проверены значения $n$ до $10^9$, и новых решений не удалось найти. В статье предлагается мой подход к проверке частных случаев задачи Брокара, а также формулируется обобщённый вариант математической проблемы, разрешение которой позволит, независимо от ABC-гипотезы, решать уравнения вида:

$n!=P(x)$


Необходимые условия

Модулярная арифметика является мощным инструментом для предварительной оценки сложности задачи и выделения частных случаев. Например, легко показать, что для чётных $m$ задача Брокара не имеет решения, так как факториал любого натурально числа, кроме единицы, чётный. Необходимым условием для пары значений $(n,m)$ в уравнении Брокара является делимость факториала на выражение:

$m^2-1$

Факториал, по определению представляет собой произведение последовательных натуральных чисел. Используя свойства натурального ряда, можно определить степень того или иного простого числа в каноническом разложении факториала на множители. Например, $16!$ содержит 16 последовательных множителей. Каждый второй множитель делится на 2, каждый 4-ый — на 4, каждый 8-ой на 8, а каждый 16-ый на 16. Таким образом, разложение $16!$ на множители содержит 2 в степени $1+2+4+8=15$. Отсюда, если существует пара $(16, m)$, являющееся решением задачи Брокара, то $m^2$ должен давать остаток 1 при делении на любую степень двойки до 15-ой включительно. Сформулируем необходимое условие для $m$ при решении уравнения 1:

Пусть $n!$ не превышает некоторой степени $k$ простого числа $p$ и существует число $m$, при котором пара $(n,m)$ является решением уравнения 1. Тогда $m^2-1$ необходимо делится на все степени $p$ до $F(k)$, где $F$ — функция подсчёта степени $p$ в разложении $n!$. (2)


P-свойство

Пусть существует алгоритм А, проверяющий необходимое условие 2 для некоторого простого числа $p$. Назовём такой алгоритм P-тестом. Пусть также существует натуральное $n$, удовлетворяющее условию: $(n-1)! < m^2 < n!$
Тогда будем говорить, что число $m$ обладает P-свойством.

Рассмотрим процесс 2-теста для произвольного $m$ между $1023!$ и $1024!$. Для $m^2$ будут справедливы утверждения:


  1. $m^2$ даёт в остатке 1 при делении на все степени двойки до $2^{1023-10=1013}$ включительно;
  2. $m^2-1$ не делится на $2^{1024-10=1014}$.

На практике, большинство квадратных чисел между $1023!$ и $1024!$ проваливают 2-тест в первые 200 итераций. Если число $m^2$ из указанного промежутка и $m$ обладает 2-свойством, то в двоичной системе исчисления $m^2$ оканчивается на $100..001$, где нулей ровно 1012. Тогда для проверки условия 2 можно вычислить $m^2$ с точностью до последних 8-и знаков и проверить последние 8 цифр. Если будет последовательность, отличная от $0000 0001$, то 2-тест не пройден. Последовательно вычисляя каждое тестируемое значение с точностью до 8, 16, 24 и т.д. знаков можно быстро проверить условие 2 для большого набора значений, задействовав минимум системных ресурсов. Размеры цепочек, кратные 8-и обоснованны байтовой структурой оперативной памяти современных компьютеров: для хранения меньших цепочек будет задействован целый байт. Для больших цепочек не кратных 8-и также будут неиспользуемые биты памяти.

Пусть нужно проверить утверждение:
Среди $n$ из отрезка $[k_1,k_2]$ нет решений уравнения 1 ни при каких $m$, где $n,m,k_1,k_2$ — натуральные.

Используя формулу Стирлинга, определим промежутки $(a_1, b_1), (a_2, b_2),..,(a_l, b_l)$, где $l=k_2-k_1+1$. Для i-ого промежутка:

$a_i={(s/e)}^s e^{1/{12s+1}} {\sqrt {2\pi s}}$

$b_i={(s/e)}^s e^{1/{12s}} {\sqrt {2\pi s}}$

$s=k_1+i-1$

Тогда справедливо утверждение:
Если среди квадратных чисел из $(a_1, b_1), (a_2, b_2),..,(a_l, b_l)$ ни одно не прошло 2-тест, то уравнение 1 не имеет решения на отрезке $[k_1,k_2]$. Обратное не верно.


Обобщение задачи Брокара по необходимому условию

В общем виде, квадратное число, обладающее p-свойством, имеет в системе исчисления с основанием $p$ вид: $t00..001$, с числом нулей $F(k)-1$. Тогда можно обобщить задачу о P-свойстве:
Пусть описаны две функции: $F$ и $G$, возвращающие натуральные значения при любом натуральном аргументе, и $G$ не представима в виде многочлена с целыми коэффициентами. Тогда необходимо сформулировать критерий, при котором среди чисел $m$, лежащих между $G(t)$ и $G(t+1)$ и имеющих в записи в системе исчисления с основанием p вид:

$k_100..00k_2 (3)$

можно выбрать только те, которые имеют натуральный корень n-ой степени, где число нулей в записи 3 задано функцией $F$, зависящей от $t$. При этом, $k_1$ может быть параметром, произвольным значением или константой, а $k_2$ — всегда константа. (4)

Например, можно поставить задачу об извлекаемости кубического корня из чисел $n$, имеющих в шестнадцатеричной системе исчисления вид $k00..001$, где $k$ любое шестнадцатеричное число больше 1, а количество нулей для конкретного $n$ равно наибольшему $t$, для которого выполняется неравенство:

$2^t+3t-1< n$

Основанием для написания статьи послужило утверждение о прямой зависимости между числом нулей в записи 3 в произвольной системе исчисления для значения левой части уравнения 1 при подстановке уже найденных корней и числом $n$. Если уравнение 1 имеет ровно 3 корня, этот факт может быть доказан при решении соответствующего частного случая задачи 4. Обратное не верно.


Заключение

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

$11+({2^{n^2-1}-2^{3n-3}})/(2^{n-1}-1)\equiv 0 \pmod {2^{m+1}-1} (5)$

Это уравнение логически вытекает из попыток приблизить числа Люка нерекуррентным методом. Решение задачи 5 поможет открыть новые свойства чисел Мерсенна и сформулировать необходимые условия для ускорения работы программ распределённого поиска больших простых чисел, основанных на тесте Люка-Лемера.

По аналогии со слабой проблемой Гольдбаха, предполагается, что P-тесты помогут получить большую нижнюю границу для целых корней уравнения 1, отличных от $(4, 5), (5, 11)$ и $(7, 71)$, а исследование проблемы 3 приведёт к доказательству неразрешимости уравнения 1 в целых числах для достаточно больших значений n.


Источники

Проблемы Гильберта
Задача Брокара

© Habrahabr.ru