2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу Пред.  1, 2, 3  След.
 
 Re: Вопрос по теории чисел
Сообщение03.11.2019, 10:55 
Аватара пользователя
Можно ли выбрать $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$ автоматически).

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

 
 
 
 Re: Вопрос по теории чисел
Сообщение03.11.2019, 11:22 
Насколько я понял, условия такие

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

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

 
 
 
 Re: Вопрос по теории чисел
Сообщение03.11.2019, 11:26 
Аватара пользователя
Shadow
А оба числа не могут быть равными $\frac{p}{2}$?

 
 
 
 Re: Вопрос по теории чисел
Сообщение03.11.2019, 11:46 
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 не попадают в этих интервалов...

 
 
 
 Re: Вопрос по теории чисел
Сообщение03.11.2019, 12:15 
Аватара пользователя
Shadow
Есть единственное чётное простое число $p=2.$ :-)

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

 
 
 
 Re: Вопрос по теории чисел
Сообщение03.11.2019, 12:38 
Тесты показывают что величина ошибки $\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$ улучшения точности не дают.

 
 
 
 Re: Вопрос по теории чисел
Сообщение03.11.2019, 13:18 
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}$

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

 
 
 
 Re: Вопрос по теории чисел
Сообщение03.11.2019, 13:33 
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$ так и есть.

 
 
 
 Re: Вопрос по теории чисел
Сообщение03.11.2019, 13:35 
Аватара пользователя
В знак $\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$.

 
 
 
 Re: Вопрос по теории чисел
Сообщение03.11.2019, 13:49 
Смотрите картинку метрики ошибок (ту что приводил выше) в зависимости от $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

 
 
 
 Re: Вопрос по теории чисел
Сообщение03.11.2019, 14:01 
Аватара пользователя
Спасибо

 
 
 
 Re: Вопрос по теории чисел
Сообщение03.11.2019, 14:11 
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)$ обязательно равен единице.

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

 
 
 [ Сообщений: 34 ]  На страницу Пред.  1, 2, 3  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group