Вопрос по теории чисел

[alisa-lebovski]

Можно ли выбрать $k,l\sim p/2$, $p\to\infty$ (тогда $m\sim p/4$ автоматически)?
Эквивалентная формулировка: $m\sim p/4$ и $l-k=o(p)$, $p\to\infty$ (тогда $k,l\sim p/2$ автоматически).

[angor6]

alisa-lebovski
Какой смысл Вы вкладываете в знак $\sim$? Как я понимаю, приблизительно равно. Чтобы доказать для заданных Вами условий существование двух чисел, приблизительно равных одному и тому же заданному числу $\frac{p}{2},$ по-моему, нужно знать, насколько эти числа могут отличаться одно от другого.

[Shadow]

Насколько я понял, условия такие

$k\in \left(\dfrac{p-\sqrt p}{2};\dfrac p 2\right)$

$l\in \left(\dfrac p 2;\dfrac{p+\sqrt p}{2}\right)$

[angor6]

Shadow
А оба числа не могут быть равными $\frac{p}{2}$?

[Shadow]

angor6 в сообщении #1423702 писал(а):

Shadow
А оба числа не могут быть равными $\frac{p}{2}$?

Ни одно из них ме может быть равным $p/2$, потому что числа $k,l$ целые, а простые обычно нечетные.
Но такие $k,l$ не существуют для $p=11$
Наверное нужно расширить

$k,l\in \left(\dfrac{p-\sqrt p}{2};\dfrac{p+\sqrt p}{2}\right)$

хотя что будет тогда с $m$...

-- 03.11.2019, 11:07 --

И решения в табице alisa-lebovski не попадают в этих интервалов...

[angor6]

Shadow
Есть единственное чётное простое число $p=2.$

Может быть, есть смысл рассмотреть по отдельности уравнения $kl-mp=1$ и $mp-kl=1$ при положительных $k,~l,~m$?

[Dmitriy40]

Тесты показывают что величина ошибки $\dfrac{|k-p/2|+|l-p/2|}{p}$ меньше 20% для $p>47$, меньше 10% для $p>467$, меньше 5% для $p>2477$, меньше 3% для $p>11551$, меньше 2% для $p>30449$.
Что интересно, с данной метрикой ошибок вполне можно ограничиться $l \ge k \ge p/2$, значения $k<p/2$ улучшения точности не дают.

[Shadow]

Dmitriy40, оценки в процентах хорошо, они гарантирют

$\dfrac{p}{2}<l<\alpha p$ для некоторого $\alpha\approx \dfrac 1 2$

но не и

$\lim\limits_{p\to \infty} \dfrac{p}{l}=2$

выполняется ли, хотя бы для больших $p$ условие

$l<\dfrac{p+\sqrt p}{2}$

[Sonic86]

Предлагаю задачу попроще:
$(\forall p)(\exists k,l) kl\equiv 1\pmod p, |k-l|\leqslant 6$
Проверил для $p\leqslant 10^5$ - верно, если я не ошибся в скрипте.

[Shadow]

Shadow в сообщении #1423711 писал(а):

$\dfrac{p}{2}<l<\alpha p$ для некоторого $\alpha\approx \dfrac 1 2$

но не и

$\lim\limits_{p\to \infty} \dfrac{p}{l}=2$

Не, глупость написал, если с увеличением $p,\; \alpha$ приближается к $\dfrac 1 2$ так и есть.

[alisa-lebovski]

В знак $\sim$ я вкладываю смысл асимптотической эквивалентности, т.е. должно выполняться $k/p\to 1/2$, $l/p\to 1/2$, $m/p\to 1/4$, $p\to\infty$. Точных ограничений на $l-k$ не ставится, кроме $l-k=o(p)$. Может быть, эту разность можно выбрать асимптотически ограниченной корнем (было такое предположение), а может и нет. Она сильно колеблется. Важно не только, чтобы $k$ и $l$ были близки между собой (этого добиться проще), но и чтобы они были близки к $p/2$.

[Dmitriy40]

Смотрите картинку метрики ошибок (ту что приводил выше) в зависимости от $p$ в двойном логарифмическом масштабе:

Хорошо видно что ошибка линейно (в этих координатах) падает, для нижней границы более точно, для верхней менее, но всё же. Это конечно не доказательство, но неслабый такой намёк, что предел таки вероятно 0, т.е. и $k$ и $l$ приближаются к $p/2$.

Shadow в сообщении #1423711 писал(а):

выполняется ли, хотя бы для больших $p$ условие $l<\dfrac{p+\sqrt p}{2}$

Нет, считайте сами (два первых попавшихся примера больших $p$ с наибольшим отношением $l/p$):

p=72287: k=36165, l=36984, k/p=0.5003, l/p=0.5116, err=0.0119
p=72949: k=36497, l=37285, k/p=0.5003, l/p=0.5111, err=0.0114

[alisa-lebovski]

Спасибо

[nnosipov]

Sonic86 в сообщении #1423713 писал(а):

Предлагаю задачу попроще:
$(\forall p)(\exists k,l) kl\equiv 1\pmod p, |k-l|\leqslant 6$

Ну, это сильно проще: можно взять $k=l=1$ Но если добавить условие $k \not\equiv l \pmod{p}$, будет в самый раз.

-- Вс ноя 03, 2019 18:20:18 --

Sonic86 в сообщении #1423713 писал(а):

Проверил для $p\leqslant 10^5$ - верно

Верно для всех $p$. Ибо один из символов Лежандра $(2/p)$, $(5/p)$ и $(10/p)$ обязательно равен единице.

[DeBill]

Вообще, если считать, что отображение $x \mapsto x^{-1}$ в нашей группе размазывает числа равномерно, то верятность того, что хотя бы одно число из $\varepsilon$-окрестности данной точки при таком отображении вернется в ту же окрестность, равна примерно $1-\exp (-\frac{4\varepsilon^2}{p})$ (по Пуассону). Эти прикидки говорят о том, что размер $\varepsilon =O(\sqrt{p})$ - самый что ни есть пограничный: если брать уже - облом, если ширше - гарантия успеха. а если ровно так - таки облом, но не факт (все же с простыми числами не все так просто). Так что выглядит это все - как убойная задача по ТЧ....