Обобщение задачи Брокара

История


Гильберт в 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.


Источники


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

  • +18
  • 5,3k
  • 8
Поделиться публикацией

Похожие публикации

AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама

Комментарии 8

    +2
    Интересно! Я и не знал об этой задаче. Шум с ВТФ утих давно уже, с ABC — всё неясно, а вот еще есть красивые вещи оказывается.
    А на архив.орг выложили уже?
      +1
      Спасибо за отзыв! На архив готовится дополненная статья с программной реализацией 2-теста и проверкой корней упомянутого в работе уравнения минимум до n<=10^11
      +1

      Пара вопросов про необходимое условие(2):


      1. Пусть n! не превышает некоторой степени k простого числа p — имеется ввиду, что n! <= p^k?
      2. На все степени p очевидно делится m^2 — 1, а не m^2
      3. F(k) — почему единственный параметр k, а не n и p?
        0
        Здравствуйте!
        1. Да
        2. Опечатка, поправил
        3. Потому что рассматривается необходимое условие для постоянного p. В общем виде, действительно можно исследовать некоторую функцию G(n,p). Пока не считаю необходимым менять этот пункт в статье.

        Спасибо за редактуру!
          0
          Уважаемый автор!
          Можно ли всю вашу работу свести к одному утверждению:
          Факториальные числа в десятичной записи после 7! заканчиваются на такое количество нулей, что алгоритмически невозможно найти точный квадрат целого числа, и, уменьшив его на единицу, получить такое же количество нулей?
            +1
            Здравствуйте! Нельзя. В целых:
            1. Квадратных чисел вида k1 00..001, имеющих ровно k2 нулей в десятичной записи, бесконечно много. Так, квадрат числа, оканчивающегося k2 нулями и единицей будет также оканчиваться на k2 нулей и единицу. Суть в том, что ни один из таких квадратов, вероятно, не попадает в промежуток (ai, bi), содержащий факториал некоторого числа.
            2. Учитывая свойства факториала, достаточно большое значение m^2, претендующее на выполнение равенства 1, будет иметь вид k1j 00..001 с k2j нулями в системах исчисления с основаниями 2..c, где j — основание системы исчисления, c — константа. Акцент на десятичную систему исчисления в работе не делается. Более того, для программной реализации рекомендован 2-тест.
              +1
              Уважаемый автор, ответ понят.
              Но, извините, давайте глянем свойство полного квадрата из Википедии:
              «Две последние цифры квадрата в десятичной записи могут принимать значения 00, 01, 04, 09, 16, 21, 24, 25, 29, 36, 41, 44, 49, 56, 61, 64, 69, 76, 81, 84, 89 или 96 (квадратичные вычеты по модулю 100).»
              Тогда понятно, что вам нужен хороший критерий на проверку k1j 00..001 на то, что это — полный квадрат. Допустим теоретико-числовой «квадрат не может оканчиваться нечётным количеством нолей», «квадрат либо делится на 4, либо при делении на 8 даёт остаток 1; „квадрат либо делится на 9, либо при делении на 3 даёт остаток 1.“
              Кстати, можно рассмотреть еще один способ.
              Сумма цифр у любого квадрата есть 9n,9n+1,9n+4,9n+7.
              Но только сумма цифр 9n дает в квадрате число, похожее на искомый вами факториал: (10^n-1)^2=(Число 9 повторенное n-1 раз)8(число 0 повторенное n-1 раз)1.
              Но факториала такого вида не существует. Проверяется построением факториала.
              Теорема доказана, за изъятием случаев из вашей статьи.
                0
                Спасибо за ответ!
                В моём понимании, решение задачи Брокара разбивается на 2 части: увеличение нижней границы для новых корней уравнения 1 и доказательство его (уравнения) неразрешимости для достаточно больших n.
                1. Временная сложность О от количества цифр в числе для алгоритма, проверяющего любое из необходимых условий: «квадрат не может оканчиваться нечётным количеством нолей», «квадрат либо делится на 4, либо при делении на 8 даёт остаток 1» «квадрат либо делится на 9, либо при делении на 3 даёт остаток 1», «Сумма цифр у любого квадрата есть 9n,9n+1,9n+4,9n+7» будет больше, чем временная сложность алгоритма, реализующего 2-тест. При прямом переборе всех значений m^2-1 из промежутка (ai, bi) можно комбинировать несколько необходимых условий. Например для каждых восьми последовательных чисел подвергать p-тесту те три, которые делятся на 4 или дают остаток 1 при делении на 8. Но комбинирование известных свойств квадрата между собой не даёт такой средней скорости проверки значений n, как 2-тест в чистом виде. Это связано, прежде всего, со средней длиной цепочки последних цифр, необходимой для того, чтобы заключить, что число m не обладает P-свойством. Статистические данные опубликую, когда закончу эффективную реализацию 2-теста.
                2. С теоретической точки зрения, я считаю утверждение об отсутствии корней уравнения 1 для n>7 недостаточно сильным и предполагаю в своей работе, что для целых m>71 множество M1 чисел вида m^2-1 не пересекается с некоторым множеством целых чисел M2, включающим n! для всех n>7 и «некоторые другие» числа, имеющие вид k1j 00..001 при записи с системах исчисления с основаниями 2..c, где с — константа. По этой причине числа вида "(цифра 9, повторённая n-1 раз) 8 (цифра 0, повторённая n-1 раз) 1" не исключаются из рассмотрения.

                «Тогда понятно, что вам нужен хороший критерий на проверку k1j 00..001 на то, что это — полный квадрат», «Теорема доказана, за изъятием случаев из вашей статьи» — рассмотрите ту же задачу за пределами десятичной системы исчисления. С интересом жду следующего комментария!

      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

      Самое читаемое