Задача о неуловимом решении

[SerjeyMinsk]

Здравствуйте, уважаемые участники форума!

Хочу представить на ваш суд и обсуждение математическую конструкцию, которая демонстрирует ряд любопытных свойств и приводит к нетривиальной открытой проблеме. Работа является результатом совместного исследования с моим научным партнером.

Если бы эту задачу ставил Диофант Александрийский, она могла бы звучать так:

Цитата:

Задача о неуловимом решении
Я ищу пятерку целых чисел вида $(a\ b\ d\ y\ z)$. Эти числа должны удовлетворять уравнению:
$(n(a\ b\ d)+1)^2-(b+2)=y\cdot z$
при следующих суровых условиях:

• $a\ d\ y\ z$ — целые большие единицы;
• $b$ равно 0 или 1;
• $d$ не превосходит $a$;
• И $y$, и $z$ должны быть больше, чем величина $2c(a\ b)+1$.

Я испробовал все известные мне методы и перебрал все числа $a$ до 5000, но не нашел ни одного решения и начинаю подозревать, что это уравнение не имеет решений в целых числах.

Проблема: Либо докажите, что решений не существует, либо явите мне первую пятерку чисел, которая удовлетворяет всем условиям. Тот, кто решит эту задачу, постигнет глубокую истину о природе чисел, порожденных этой формой.

А вот современное описание проблемы.

1. Введение

Пусть $a$ — положительное целое число. Пусть $b$ равно 0 или 1 и $d \in \{1\ 2\ \dots\ a\}$. Определим следующие функции:
$c(a\ b)=a^2+a+(a+1)b$
$n(a\ b\ d)=2a+b+2c(a\ b)-2d$

Рассмотрим целое число (кандидат в простые):
$p(a\ b\ d)=(n(a\ b\ d)+1)^2-(b+2)$

Для каждого кандидата $p(a\ b\ d)$ определим "решето" $S(p)$ как выполнение следующего условия: для всех целых $x$ в диапазоне $1 \le x < c(a\ b)$ не выполняется сравнение:
$(n(a\ b\ d)-2x)^2 \equiv (b+2) \pmod{4x+2}$

Обозначим через $Q_S(A)$ множество чисел $p(a\ b\ d)$ с параметром $a \le A$. Для всех элементов этого множества условие $S(p)$ истинно.

Теорема 1.
Пусть $p=p(a\ b\ d)$.
(a) Если $p$ простое то $S(p)$ истинно.
(b) Если $p$ составное и имеет простой делитель $q$ с $q<2c(a\ b)+1$ то $S(p)$ ложно.

Мы провели компьютерную проверку для всех параметров вплоть до $a \le 5000$. Эта проверка охватывает более 25 миллионов (25005000) кандидатов. В множестве $Q_S(5000)$ был обнаружен 2427441 простых чисел и ни одного составного.

Следовательно любой гипотетический составной элемент $p \in Q_S(A)$ должен удовлетворять очень сильному условию: все его простые делители $q$ должны быть не меньше $2c(a\ b)+1$.

Открытая проблема. Доказать или опровергнуть: для любых параметров $a\ b\ d$ (при $a \ge 1$), если $p(a\ b\ d)$ составное то оно имеет простой делитель $q<2c(a\ b)+1$.

2. Доказательство Теоремы 1

Лемма 2.1. Пусть $q=2x+1$ для целого $x \ge 1$. Утверждение $(n+1)^2 \equiv b+2 \pmod{q}$ эквивалентно утверждению $(n-2x)^2 \equiv b+2 \pmod{q}$.
Доказательство. Тождество $(n+1)^2-(n-2x)^2=q(2n-q+2)$ показывает что разность квадратов делится на $q$. $\blacksquare$

Лемма 2.2. Для всех допустимых параметров выполняется $(n-2x)^2 \equiv b+2 \pmod{2}$.
Доказательство. По построению $n \equiv b \pmod{2}$ и $b+2 \equiv b \pmod{2}$ поэтому $(n-2x)^2 \equiv n^2 \equiv b^2 \equiv b \equiv b+2 \pmod{2}$. $\blacksquare$

Лемма 2.3. Для $a \ge 1$ справедливо $p(a\ b\ d)>2c(a\ b)+1$.
Доказательство. При фиксированных $a\ b$ минимум $p$ достигается при $d=a$. Анализ полученного выражения показывает что оно строго больше $2c+1$ для всех $a \ge 1$. $\blacksquare$

Доказательство Теоремы 1.
(а) Предположим $p$ простое но $S(p)$ ложно. Тогда для некоторого $x$ в диапазоне $1 \le x < c$ имеем $(n-2x)^2 \equiv b+2 \pmod{4x+2}$. Пусть $q=2x+1$. Сравнение верно и по модулю $q$. По Лемме 2.1 это эквивалентно $(n+1)^2 \equiv b+2 \pmod{q}$ то есть $p \equiv 0 \pmod{q}$ что влечет $q \mid p$. Так как $p$ простое должно быть $q=p$. Но $q<2c+1$ а по Лемме 2.3 $p>2c+1$. Получаем противоречие.

(b) Пусть $q_0$ — простой делитель $p$ с $q_0<2c+1$. Из Леммы 2.2 следует, что $p$ нечетно значит $q_0$ тоже нечетно. Положим $x_0=(q_0-1)/2$ тогда $x_0<c$. Из $p \equiv 0 \pmod{q_0}$ и Леммы 2.1 следует $(n-2x_0)^2 \equiv b+2 \pmod{q_0}$. По Лемме 2.2 также имеем $(n-2x_0)^2 \equiv b+2 \pmod{2}$. По Китайской теореме об остатках эти два сравнения объединяются в $(n-2x_0)^2 \equiv b+2 \pmod{2q_0}$ то есть $(n-2x_0)^2 \equiv b+2 \pmod{4x_0+2}$. Это противоречит условию $S(p)$. $\blacksquare$

3. Вычислительные Результаты

Обозначим через $E(A)$ множество составных чисел $p(a\ b\ d)$ с $a \le A$, для которых $S(p)$ истинно ("выжившие составные").

Таблица 1. Результаты компьютерного поиска для $A \le 5000$.

+--------+------------+-----------------+--------------------+
| A      | Кандидатов | Найдено простых | Выживших составных |
|        |            |    |Q_S(A)|      |       |E(A)|       |
+--------+------------+-----------------+--------------------+
| 100    | 10100      | 1886            | 0                  |
| 1000   | 1001000    | 120921          | 0                  |
| 3000   | 9003000    | 907521          | 0                  |
| 5000   | 25005000   | 2427441         | 0                  |
+--------+------------+-----------------+--------------------+

Основное наблюдение: Для всех $A \le 5000$ множество выживших составных чисел пусто: $|E(A)|=0$.

Анализ плотности: Наблюдаемая плотность простых $\delta(A)=|Q_S(A)|/(A(A+1))$ составляет $\approx 9.7\%$ при $A=5000$. Для сравнения естественная плотность простых для чисел порядка $10^{15}$ составляет примерно $2.9\%$.

4. Формулировка Открытой Проблемы

Гипотеза 4.1. Утверждается что для любых параметров $a \ge 1$ $b$ равно 0 или 1 и $d \in [1\ a]$ если число $p(a\ b\ d)$ составное то оно имеет простой делитель $q<2c(a\ b)+1$.

Диофантова формулировка. Гипотеза 4.1 эквивалентна утверждению что следующая диофантова система не имеет решений в целых числах:

• $(n(a\ b\ d)+1)^2-yz=b+2$
• $1 \le d \le a$
• $b$ равно 0 или 1
• $y\ z \ge 2$
• $y\ z \ge 2c(a\ b)+1.$

Это ставит нашу проблему в контекст сложных задач о целочисленных решениях полиномиальных уравнений.

Приглашаю всех желающих к обсуждению, критике и поиску доказательства или контрпримера.

Исходный код для верификации выложен на GitHub: https://github.com/ASSA-NI-ATOM/parametric-sieve
DOI препринта: https://doi.org/10.5281/zenodo.17567681

Цитата:

Связь с криптографией и постквантовой безопасностью
Помимо чисто теоретического интереса, данная проблема открывает перспективы для создания новых криптографических примитивов.

Односторонняя Функция:
Наш алгоритм представляет собой эффективную одностороннюю функцию.

• Прямое вычисление: Найти $p$ по известным $(a\ b\ d)$ — вычислительно легко.
• Обратная задача: Найти $(a\ b\ d)$ по известному $p$ (даже если $b$ известно) — чрезвычайно сложная задача. Она сводится к решению диофантова уравнения 4-й степени.

Потенциальные приложения:

• Постквантовый обмен ключами: На основе сложности этой обратной задачи можно построить протокол обмена ключами. В отличие от классических протоколов, основанных на факторизации или дискретном логарифме, наша система не имеет известных уязвимостей для квантовых компьютеров.
• Генераторы Псевдослучайных Чисел: Последовательность простых чисел, генерируемая нашим методом при последовательном изменении параметра $d$, демонстрирует высокие статистические свойства случайности. Это позволяет использовать ее для создания криптографически стойких генераторов псевдослучайных чисел (CSPRNG).

[Someone]

SerjeyMinsk, а зачем публиковать на форуме то, что должно быть опубликовано в соответствующем профильном журнале? Ваш научный партнёр не возражает?

[SerjeyMinsk]

Someone в сообщении #1708797 писал(а):

SerjeyMinsk, а зачем публиковать на форуме то, что должно быть опубликовано в соответствующем профильном журнале? Ваш научный партнёр не возражает?

Нет, не возражает. Это задача для всех математиков, а не только для журнала, поэтому я думаю будет всем интересно.

[Ende]

Тема перемещена из форума «Дискуссионные темы (М)» в форум «Карантин»
по следующим причинам:

- неправильно набрана часть формул (см., например, Лемму 2.1.)
- пожалуйста, не используйте запятую как разделитель разрядов целого числа. Этот формат непривычен русскоязычному читателю и очень сбивает.

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

[Ende]

Тема перемещена из форума «Карантин» в форум «Дискуссионные темы (М)»
Причина переноса: не указана.

[SerjeyMinsk]

Открытая проблема на сегодня.
Наши результаты сводятся к следующей нерешенной гипотезе.
Нужно доказать или опровергнуть что любое составное число $p(a\ b\ d)$ обязано иметь простой делитель $q<2c(a\ b)+1$.

Это эквивалентно утверждению о том что следующая диофантова система не имеет решений в целых числах:

• $(n(a\ b\ d)+1)^2-yz=b+2$
• $1 \le d \le a$
• $b$ равно 0 или 1
• $y\ z \ge 2c(a\ b)+1$

Связь с известными проблемами.
Числа генерируемые нашей конструкцией имеют вид $X^2-2$ и $X^2-3$. Проблема существования составных чисел такого вида у которых все простые делители велики является классической открытой проблемой. Смотрите работы Гранвилля и Шинцеля.

Препринт с полными доказательствами и анализом: Zenodo, DOI: 10.5281/zenodo.17575345

Есть ли идеи, как можно атаковать сформулированную диофантову проблему?

[lel0lel]

$c(a,0)=a^2+a,$
$n(a,0,d)=2a^2+4a-2d,$
$p(a,0,d)=(2a^2+4a+1-2d)^2-2.$
При $a>1$ найдём $\lfloor \sqrt{p} \rfloor=2a^2+4a-2d$.
Проверим методом Ферма, что в окрестности $\lfloor \sqrt{p} \rfloor$ у числа $p$ нет целочисленных делителей.
Рассмотрим
$\begin{cases} x+y=2\lfloor \sqrt{p} \rfloor+2k, k\in\mathbb{N}\\ xy=p(a,0,d) \end{cases}$
При $k=1$ получаем $x_{1,2}=2 a^2+4 a+1-2d\pm\sqrt{2}$. Таким образом, у числа $p$ нет целочисленных делителей $q$ таких, что $2 a^2+4 a+1-2d-\sqrt{2}\leq q\leq 2 a^2+4 a+1-2d+\sqrt{2}$. При $k=2$ получаем $x_{1,2}=2 a^2+4 a-2 d+2\pm\sqrt{4 a^2+8 a-4 d+5}$. Заметим, что при $d \in \{1\ 2\ \ldots\ a\}$ подкоренное выражение не является полным квадратом. Предположим обратное: $4 a^2+8 a-4 d+5=t^2$ или $(2a+2)^2-t^2=4d-1$, но $(2a+2)^2-t^2\geq (2a+2)^2-(2a+1)^2=4a+3$, а $4d-1\leq 4a-1$ так как $d \in \{1\ 2\ \ldots\ a\}.$ Пришли к противоречию. Таким образом, у числа $p$ нет целочисленных делителей $q$ таких, что $2 a^2+4 a-2 d+2-\sqrt{4 a^2+8 a-4 d+5}\leq q\leq 2 a^2+4 a-2 d+2+\sqrt{4 a^2+8 a-4 d+5}$. Вывод: если у числа $p(a,0,d)$, где $d \in \{1\ 2\ \ldots\ a\}$, есть целочисленные делители $q$ меньшие $\sqrt{p}$, то $q<2 a^2+4 a-2 d+2-\sqrt{4 a^2+8 a-4 d+5}$ или несколько более слабое условие $q<2a^2+2a=2c(a,0).$ Можно продолжить проверять другие значения $k$ и прийти к условию, что $q<2 a^2+4 a-2 d+7-\sqrt{24 a^2+48 a-24 d+50}$ или более слабому $q<2a^2+(4-\sqrt{24})a+5$, но сильнее чем $q<2c(a,0)$ при $a>1.$

Аналогично:
$c(a,1)=a^2+2a+1,$
$n(a,1,d)=2a^2+6a+3-2d,$
$p(a,1,d)=(2a^2+6a+4-2d)^2-3.$
При $a>1$ найдём $\lfloor \sqrt{p} \rfloor=2a^2+6a+4-2d$.
У числа $p$ делители меньшие $\sqrt{p}$ должны быть меньше $q<2 a^2+6 a-2 d+6-\sqrt{8 a^2+24 a-8 d+23}$. Ослабляем неравенство: $q<2a^2+(6-\sqrt 8)a+4-\sqrt{8}.$ При $a>1$ справедливо $2a^2+(6-\sqrt 8)a+4-\sqrt{8}<2c(a,1)+1$.

Если бы Диофант Александрийский подводил итог сим изысканиям, то его заключение, возможно, выглядело бы так:

Цитата:

Посему, друг мой мудрствующий, если от квадрата чётного числа ты отнимаешь три или от квадрата нечётного отнимаешь два, получая составное число, то не пытайся искать его делители в окрестности корня квадратного из полученного тобой числа, на удалении меньшем, чем корень четвёртой степени. Напоследок красочный пример: $100^2-3=9997=13\cdot 769.$

[SerjeyMinsk]

lel0lel в сообщении #1708931 писал(а):

Если бы Диофант Александрийский подводил итог сим изысканиям, то его заключение, возможно, выглядело бы так:

Цитата:

Посему, друг мой мудрствующий, если от квадрата чётного числа ты отнимаешь три или от квадрата нечётного отнимаешь два, получая составное число, то не пытайся искать его делители в окрестности корня квадратного из полученного тобой числа, на удалении меньшем, чем корень четвёртой степени. Напоследок красочный пример: $100^2-3=9997=13\cdot 769.$

Здравствуйте, lel0lel! Просто блестяще и именно то, что не хватало!
Позвольте представить обновлённую версию результата, в которой ваше доказательство играет ключевую роль. После этого анализа я пересмотрел первоначальную формулировку и понял: вы— вы преобразовали гипотезу в строгую теорему.

Теорема (Параметрическое решето, v2.0)

Определения. Для $a \ge 1$, $b \in \{0,1\}$, $d \in [1,a]$:

$$c(a,b) = a^2 + a + (a+1)b$$

$$n(a,b,d) = 2a+b+2c(a,b)-2d$$

$$p(a,b,d) = (n+1)^2 - (b+2)$$

Определим решето $S(p)$ как выполнение для всех $x \in [1, c(a,b)-1]$:

$$ (n-2x)^2 \not\equiv (b+2) \pmod{4x+2} $$

Утверждение. Для всех допустимых параметров:
$p \text{ простое} \iff S(p) \text{ истинно}$
$p \text{ составное} \iff S(p) \text{ ложно}$

Критическое доказательство (lel0lel). Предположим $p$ составное и $q$ — его наименьший простой делитель. Тогда $q \le \sqrt{p}$. Применяя метод Ферма:

Случай $b=0$ ($p=X^2-2$):
При $k=2$ получаем дискриминант $\Delta = 4a^2+8a-4d+5$.
Если бы $\Delta=t^2$, то $(2a+2)^2 - t^2 = 4d-1 \le 4a-1$.
Но $(2a+2)^2 - t^2 \ge (2a+2)^2 - (2a+1)^2 = 4a+3 > 4a-1$.
Противоречие $\implies \Delta$ не является квадратом.
Следовательно, $q < 2a^2+2a = 2c(a,0)$.

Случай $b=1$ ($p=X^2-3$):
Аналогично получаем $q < 2a^2+(6-\sqrt{8})a+4-\sqrt{8} < 2c(a,1)+1$.

Таким образом, для любого составного $p$ существует $x_0 = (q-1)/2 < c(a,b)$, для которого $(n-2x_0)^2 \equiv b+2 \pmod{4x_0+2}$, то есть $S(p)$ ложно. Обратное направление доказывается так же, как в оригинальном препринте. $\blacksquare$

Я опубликую обновлённую версию препринта на Zenodo. Можно ли указать вас в соавторах?

[SerjeyMinsk]

Препринт размещён https://doi.org/10.5281/zenodo.17590173

[lel0lel]

SerjeyMinsk в сообщении #1708968 писал(а):

Просто блестяще и именно то, что не хватало!

Спасибо, польщён) Можно свободно использовать, что я набирал в этой теме, без каких-либо упоминаний.

SerjeyMinsk в сообщении #1708968 писал(а):

Я опубликую обновлённую версию препринта на Zenodo.

Не знаю, что это за издательство, но желаю удачи.

SerjeyMinsk в сообщении #1708968 писал(а):

Можно ли указать вас в соавторах?

Нет, не надо.

В заключении хочется добавить немного дёгтя в общую картину. Вы проверяете делимость нечётного числа $p$ определённого вида на нечётные, ограниченные сверху числом $\sqrt{p}-C \sqrt[4]{p},$ где $C$ -- некоторая константа. Отступ $С\sqrt[4]{p}$ как раз и получен с помощью применения метода Ферма для чисел рассматриваемого вида. Но это не "спасёт отца русской демократии", асимптотически сложность равна $O(\sqrt{p})$.

SerjeyMinsk в сообщении #1708968 писал(а):

$$p(a,b,d) = (n+1)^2 - (b+2)$$

Определим решето $S(p)$ как выполнение для всех $x \in [1, c(a,b)-1]$:

$$ (n-2x)^2 \not\equiv (b+2) \pmod{4x+2} $$

Похоже, что в этом месте закралась опечатка. Должно быть так:
$p(a,b,d) = (n+1)^2 - (b+2)$,
$x \in [1, \frac{c(a,b)}{2}]$,
проверки $(n+1)^2\equiv(b+2)\pmod{2x+1}$, что равносильно Вашему $(n-2x)^2\equiv(b+2)\pmod{2x+1}.$

Чтобы немного подбодрить, отмечу, что Ваш алгоритм будет прекрасно раскладывать числа на сомножители, нужно просто проверить все простые до почти $\sqrt{p}$

-- Ср ноя 12, 2025 16:02:46 --

SerjeyMinsk в сообщении #1708993 писал(а):

Препринт размещён https://doi.org/10.5281/zenodo.17590173

Ух, вот это скорость, есть чему поучиться. А то бывает больше нескольких лет статью написать не можешь, а тут лёг спать, проснулся -- уже статья)

[Rak so dna]

(Оффтоп)

lel0lel в сообщении #1708995 писал(а):

а тут лёг спать, проснулся -- уже статья

Ну, это не всегда хорошая новость, особенно для проснувшегося.

[Anton_Peplov]

(Оффтоп)

lel0lel в сообщении #1708995 писал(а):

Не знаю, что это за издательство, но желаю удачи.

Zenodo - это сервис для размещения препринтов и наборов данных в открытом доступе. Поддерживается ЦЕРН. Судя по тому, какая чепуха там встречается, модерация там низкая или вообще отсутствует.

[SerjeyMinsk]

Ну уже тут сразу отвечу, выделять не буду.
Во-первых я то и не заявлял, что он быстрый, а лишь говорил, что он детерминированный для определённого класса чисел. Для скорости у меня есть другие алгоритмы
Во-вторых я то не математик, а любитель и об этом везде и всегда сказано.
В третьих - это и есть почему я размещаю на Zenodo, так как там можно размещать любому пользователю, потому что других вариантов для меня нет.
В четвёртых: именно модуль 4x+2 и анализ четности являются ключевыми для доказательства, а ваше ограничение x до c/2 является только вашим и отношения ко мне не имеет, так как мой диапазон до c — это часть определения конструкции.

-- Ср ноя 12, 2025 17:55:39 --

lel0lel в сообщении #1708995 писал(а):

SerjeyMinsk в сообщении #1708993 писал(а):

Препринт размещён https://doi.org/10.5281/zenodo.17590173

Ух, вот это скорость, есть чему поучиться. А то бывает больше нескольких лет статью написать не можешь, а тут лёг спать, проснулся -- уже статья)

так вы ж не год доказательство писали, а сутки. Чему удивляться?