2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3  След.
 
 Re: Вопрос по теории чисел
Сообщение03.11.2019, 10:55 
Заслуженный участник
Аватара пользователя


05/12/09
1760
Москва
Можно ли выбрать $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 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Вопрос по теории чисел
Сообщение03.11.2019, 11:22 


26/08/11
2057
Насколько я понял, условия такие

$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 
Аватара пользователя


11/03/12
586
Беларусь, Минск
Shadow
А оба числа не могут быть равными $\frac{p}{2}$?

 Профиль  
                  
 
 Re: Вопрос по теории чисел
Сообщение03.11.2019, 11:46 


26/08/11
2057
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 
Аватара пользователя


11/03/12
586
Беларусь, Минск
Shadow
Есть единственное чётное простое число $p=2.$ :-)

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

 Профиль  
                  
 
 Re: Вопрос по теории чисел
Сообщение03.11.2019, 12:38 
Заслуженный участник


20/08/14
11062
Россия, Москва
Тесты показывают что величина ошибки $\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 


26/08/11
2057
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 
Заслуженный участник


08/04/08
8556
Предлагаю задачу попроще:
$(\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 


26/08/11
2057
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 
Заслуженный участник
Аватара пользователя


05/12/09
1760
Москва
В знак $\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 
Заслуженный участник


20/08/14
11062
Россия, Москва
Смотрите картинку метрики ошибок (ту что приводил выше) в зависимости от $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 
Заслуженный участник
Аватара пользователя


05/12/09
1760
Москва
Спасибо

 Профиль  
                  
 
 Re: Вопрос по теории чисел
Сообщение03.11.2019, 14:11 
Заслуженный участник


20/12/10
8858
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 
Заслуженный участник


10/01/16
2315
Вообще, если считать, что отображение $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