2014 dxdy logo

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

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




На страницу 1, 2, 3  След.
 
 Вопрос по теории чисел
Сообщение01.11.2019, 20:15 
Аватара пользователя
Сама я не по теории чисел, поэтому заранее извиняюсь за возможно глупый вопрос. Он возник в связи с одной задачей дискретной теории вероятностей.

Верно ли, что для любого простого числа $p$ можно подобрать такие целые числа $1\le m\le k\le l< p$, что $|kl-pm|=1$, причем их можно выбрать так, чтобы асимптотически получалось $m\sim p/4$; $k,l\sim p/2$, $p\to\infty$. Численно вроде получается, примерно так: $k\approx(p-\sqrt{p})/2$, $l\approx(p+\sqrt{p})/2$.

 
 
 
 Re: Вопрос по теории чисел
Сообщение02.11.2019, 12:12 
Аватара пользователя
alisa-lebovski
По-моему, требования "для любого простого числа $p$" и "чтобы асимптотически получалось" противоречивы.

 
 
 
 Re: Вопрос по теории чисел
Сообщение02.11.2019, 12:48 
Я, в общем, тоже не по теории чисел, но коли уж числа от нуля до $p-1$ образуют группу, то у каждого в ней есть обратное в группе, а стало быть, для любого $k$ можно подобрать $l$ и $m$; неравенства будут выполняться автоматически (за исключением, возможно, $k$ и $l$), так что вполне вероятно...

 
 
 
 Re: Вопрос по теории чисел
Сообщение02.11.2019, 14:52 
Аватара пользователя
Да, тут я протупила: если $p$ - простое число больше 3, то и $p-1$, и $p+1$ будут составными (по крайней мере четными), их можно разложить на множители $k,l$ (при этом $m=1$). Так что первый вопрос снимается.

Остается второй. главный: можно ли выбрать $m\sim p/4$; $k,l\sim p/2$, $p\to\infty$?

 
 
 
 Re: Вопрос по теории чисел
Сообщение02.11.2019, 15:07 
alisa-lebovski в сообщении #1423603 писал(а):
$m\sim p/4$
Это бесплатно, если нужные $k$ и $l$ уже найдены. Но вопрос о существовании таких $k$ и $l$ не кажется очевидным.

 
 
 
 Re: Вопрос по теории чисел
Сообщение02.11.2019, 16:14 
Аватара пользователя
Просчитала на простых числах до 1000, вот конец:

$   \begin{tabular}{|c|c|c|c|r|c|c|c|}
\hline
$p$  &    $k$  &   $l$  &    $m$  & $mp-kl$ & $k/p$  &   $l/p$ &   $m/p$ \\
\hline
    937 & 434 & 516 & 239 &  -1$ &  .4632  & .5507 &  .2551   \\
    941 & 453 & 484 & 233  &  1 &  .4814 &  .5143 &  .2476   \\
    947 & 485 & 494 & 253  &  1 &  .5121 &  .5216 &  .2672   \\
    953 & 491 & 493 & 254  & -1$ &  .5152  & .5173 &  .2665   \\
    967 & 442 & 466  & 213 & -1$ &  .4571 &  .4819 &  .2203   \\
    971 & 466 & 498 & 239 &   1 &  .4799 &  .5129 &  .2461   \\
    977 & 493 & 543 & 274 &  -1$ &  .5046  & .5558 &  .2805   \\
    983 & 468 & 481 & 229 &  -1$ &  .4761  & .4893  & .2330   \\
    991 & 472 & 506 & 241 &  -1$ &  .4763  & .5106  & .2432   \\
    997 & 505 & 537 & 272 &  -1$ &  .5065  & .5386 &  .2728 \\
\hline
\end{tabular}
$

 
 
 
 Posted automatically
Сообщение02.11.2019, 18:47 
 i  Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
по следующим причинам:

- неправильно набраны формулы (краткие инструкции: «Краткий FAQ по тегу [math]» и видеоролик Как записывать формулы);


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

 
 
 
 Posted automatically
Сообщение02.11.2019, 19:21 
 i  Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

 
 
 
 Re: Вопрос по теории чисел
Сообщение02.11.2019, 20:43 
$kl=mp\pm1$ - арифметическая прогрессия с шагом $p$
Если $m\sim \frac{p}{4}$, то для выбора имеется $o(p)$ значений $m$.
В $r$ подряд идущих значений арифметической прогрессии хотя бы одно делится на некоторое простое $q:q=O(r)$.
Значит найдется хотя бы одно $m: mp+1=kl, k=o(p), l=\Omega(p)$.
Это не то, что требуется доказать, но это демонстрация того, что утверждение недалеко от истины. А дальше анализ становится труднее.
Если оно ложно, то опровергнуть его численным примером будет трудно.

 
 
 
 Re: Вопрос по теории чисел
Сообщение03.11.2019, 00:31 
Как то очень хочется притянуть за уши примитивные корни из мультипликативной группы $\mathbb{Z}_p$ (Вики грит, что Виноградов доказал, что наименьший примитивный корень как раз типа $O(\sqrt{p})$(а если гипотеза Римана справедлива, то даже и $O(\log p)$)), но моего незнания теории чисел оказалось недостаточно для.

-- 03.11.2019, 02:41 --

Есть еще последовательность A046145 в OEIS : может, в ней есть что-то коррелирующее с таблицей ТС ?

 
 
 
 Re: Вопрос по теории чисел
Сообщение03.11.2019, 01:03 
Аватара пользователя
alisa-lebovski в сообщении #1423493 писал(а):
... можно подобрать такие целые числа $1\le m\le k\le l< p$, что $|kl-pm|=1$, причем их можно выбрать так, чтобы асимптотически получалось $m\sim p/4$; $k,l\sim p/2$, $p\to\infty$

Перепишем требование $|kl-pm|=1$ так: $kl \sim pm$, тогда из требования $k,l\sim p/2$ следует $m \sim kl/p \sim (p/2)^2/p \sim p/4$. То есть требование $m\sim p/4$ лишнее. Вопрос сводится к поиску маленьких расстояний между обратными величинами по $\mod p$, что нормально, но еще и близких к точке $p/2$, что избыточно. Наименьшее расстояние между тремя точками — это, знаете ли, дело вкуса.
Условие $|kl-pm|=1$ можно переписать еще так: $kl=\pm 1 \mod p$. Положим $l=k+a$, где $a$ — некоторая маленькая величина, которую задаем в процессе перебора. Предыдущее сравнение тогда выглядит так: $k^2+ak=1 \mod p$ или $k^2+ak=-1 \mod p$. В таком виде это можно заводить в Вольфрам и выбирать $k$ наиболее близкие к точке $p/2$. Ваше решение для $p=953$ можно получить при $a=2$, а для $p$ вида $4n+1$ возможно и $a=0$ (с минус единицей, конечно). Не знаю что тут еще посоветовать.

 
 
 
 Re: Вопрос по теории чисел
Сообщение03.11.2019, 09:36 
Аватара пользователя
Мне надо не находить конкретные $k,l$ при заданном $p$ (с этим уже справилась), а доказать, что они существуют асимптотически. Что касается разности между ними, то она не является равномерно ограниченной, а мала только по сравнению с $p$.

 
 
 
 Re: Вопрос по теории чисел
Сообщение03.11.2019, 09:40 
Аватара пользователя
alisa-lebovski в сообщении #1423691 писал(а):
доказать, что они существуют асимптотически.

То есть?

 
 
 
 Re: Вопрос по теории чисел
Сообщение03.11.2019, 09:57 
Аватара пользователя
Вопрос в том, можно ли выбрать $k,l\sim p/2$, $p\to\infty$?
Ну или что то же самое, $l-k=o(p)$, $p\to\infty$.

 
 
 
 Re: Вопрос по теории чисел
Сообщение03.11.2019, 10:05 
Аватара пользователя
alisa-lebovski
Тогда, наверное, есть смысл уточнить, насколько могут отличаться $k$ и $l$?

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


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