2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Очень длинные периоды
Сообщение20.09.2013, 07:26 
Заслуженный участник
Аватара пользователя


03/12/11
640
Україна
Для любого натурального $n$ обозначим через $p(n)$ длину периода дроби $\frac 1 n$ в десятичной записи. Докажите, что $$\varlimsup_{n \to \infty} {\frac {p(n)} {\sqrt n}} = +\infty \, .$$

 Профиль  
                  
 
 Re: Очень длинные периоды
Сообщение20.09.2013, 18:02 
Заслуженный участник
Аватара пользователя


03/12/11
640
Україна
Похоже, что можно даже усилить (правда, пока не доказал):$$\varlimsup_{n \to \infty} {\frac {p(n)} n} > 0 .$$

 Профиль  
                  
 
 Re: Очень длинные периоды
Сообщение20.09.2013, 20:11 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Докажите гипотезу Артина, и всё получится :-)

 Профиль  
                  
 
 Re: Очень длинные периоды
Сообщение20.09.2013, 20:33 
Заслуженный участник


08/04/08
8556
whitefox в сообщении #765919 писал(а):
Докажите гипотезу Артина
, и всё получится :-)
Не, это понятно, но утверждения Dave несколько слабее и вообще более количественно выражены, чем гипотеза Артина. Надо подумать...

 Профиль  
                  
 
 Re: Очень длинные периоды
Сообщение21.09.2013, 06:14 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Ну если не гипотезу Артина, то можно попробовать доказать, что существует бесконечно много простых $q$ таких, что $n=2\cdot q+1$ тоже простое.

Тогда получим $$\varlimsup_{n \to \infty} {\frac {p(n)} n} \geqslant \frac 1 2$$

 Профиль  
                  
 
 Re: Очень длинные периоды
Сообщение21.09.2013, 06:56 
Заслуженный участник


08/04/08
8556
whitefox в сообщении #766059 писал(а):
Ну если не гипотезу Артина, то можно попробовать доказать, что существует бесконечно много простых $q$ таких, что $n=2\cdot q+1$ тоже простое.
Это известная гипотеза о бесконечности простых Жермен, тоже вряд ли тут докажем.

 Профиль  
                  
 
 Re: Очень длинные периоды
Сообщение21.09.2013, 07:26 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Да, действительно. Запамятовал.

 Профиль  
                  
 
 Re: Очень длинные периоды
Сообщение21.09.2013, 09:10 
Заслуженный участник


08/04/08
8556
Dave в сообщении #765630 писал(а):
Для любого натурального $n$ обозначим через $p(n)$ длину периода дроби $\frac 1 n$ в десятичной записи. Докажите, что $$\varlimsup_{n \to \infty} {\frac {p(n)} {\sqrt n}} = +\infty \, .$$
Могу доказать для показателя $\beta<1/2$:
Пусть $a$ - натуральное число, для $n:\gcd(a,n)=1$ определим $p(n)$ как наименьший показатель, для которого $a^{p(n)}\equiv 1\pmod n$.
Предположим, что $\varlimsup\limits_{n\to +\infty}\frac {p(n)} {n^{\beta}} < +\infty$, т.е. $(\exists C)(\forall m\leqslant n) p(m)\leqslant Cm^{\beta}$. Это значит, что все $a^{p(m)}-1$ делятся на $m$. Берем $\text{НОК}$:
$\operatorname{lcm}\limits_{m=1}^{n}(a^{p(m)}-1)\vdots e^{\psi(n)}$
В частности,
$\ln\operatorname{lcm}\limits_{m=1}^{n}(a^{p(m)}-1)\geqslant \psi(n)$
$\psi(n)=\ln\operatorname{lcm}\limits_{m=1}^{n}m\sim n$ - 2-я функция Чебышева.
Оцениваем правую часть:
$$\ln\operatorname{lcm}\limits_{m=1}^{n}(a^{p(m)}-1)=
\ln\operatorname{lcm}\limits_{k=1}^{p_{\max}}\Phi_{k}(a)\leqslant \sum\limits_{k=1}^{p_{\max}}\ln\Phi_{k}(a)$$
При $k\to+\infty$ $\ln\Phi_{k}(a)\sim \varphi(k)\ln a$, тогда
$\sum\limits_{k=1}^{p_{\max}}\ln\Phi_{k}(a)\sim \ln a \sum\limits_{k=1}^{p_{\max}}\varphi(k)\sim\ln a\cdot \frac{3}{\pi^2}p^2_{\max}$.
Если теперь $p_{\max}\leqslant Cn^{\beta}$, то при $2\beta < 1$ и достаточно большом $n$ получим ложное неравенство
$C^2n^{2\beta}\geqslant \ln\operatorname{lcm}\limits_{m=1}^{n}(a^{p(m)}-1)\geqslant \psi(n)\sim n$.

Интересно, а где же я $\beta=1/2$ теряю? Неужели барьер квадратного корня?

 Профиль  
                  
 
 Re: Очень длинные периоды
Сообщение21.09.2013, 09:57 
Заслуженный участник
Аватара пользователя


03/12/11
640
Україна
Задача раздвоилась :-)

Докажите, что:
1.$$\varlimsup_{n \to \infty} {\frac {p(n)} n} > 0,99999999 .$$
2. Для любого натурального $n$ существует такое натуральное число $x$, состоящее не более чем из $2n$ цифр, что в десятичной записи дроби $\frac 1 x$ встречаются любые $n$ цифр подряд.

(Оффтоп)

Не так всё сложно, как кажется. Гипотезу Артина при решении нужно, конечно, держать в уме, но в конечном счёте можно обойтись и без неё. Кстати, кто-нибудь объяснит мне что написано в английской Википедии:
Wikipedia в Artin's_conjecture писал(а):
Roger Heath-Brown improved on their result and showed unconditionally that there are at most two exceptional prime numbers a for which Artin's conjecture fails.[4] This result is not constructive, as far as the exceptions go. For example, it follows from the theorem of Heath-Brown that one out of 3, 5, and 7 is a primitive root modulo p for infinitely many p. But the proof does not provide us with a way of computing which one.
Т.е. это означает, что гипотеза Артина доказана вообще для всех чисел, кроме максимум двух из множества $\{3,5,7\}$ (никто не знает, каких)? Т.к. 10 в это множество не входит то, теоретически, можно было бы использовать этот результат при решении первой части задачи?

 Профиль  
                  
 
 Re: Очень длинные периоды
Сообщение21.09.2013, 20:51 
Модератор
Аватара пользователя


11/01/06
5660
Dave в сообщении #766093 писал(а):
Кстати, кто-нибудь объяснит мне что написано в английской Википедии:
Wikipedia в Artin's_conjecture писал(а):
Roger Heath-Brown improved on their result and showed unconditionally that there are at most two exceptional prime numbers a for which Artin's conjecture fails.[4] This result is not constructive, as far as the exceptions go. For example, it follows from the theorem of Heath-Brown that one out of 3, 5, and 7 is a primitive root modulo p for infinitely many p. But the proof does not provide us with a way of computing which one.
Т.е. это означает, что гипотеза Артина доказана вообще для всех чисел, кроме максимум двух из множества $\{3,5,7\}$ (никто не знает, каких)? Т.к. 10 в это множество не входит то, теоретически, можно было бы использовать этот результат при решении первой части задачи?

Не совсем так. Доказано, что гипотеза Артина справедлива для всех простых чисел, за исключением возможно двух, но при этом неизвестно, каких именно. Поэтому для множества простых $\{3,5,7\}$ (да и вообще любого другого множества их трёх или более простых), мы можем утверждать, что гипотеза Артина справедлива по крайней мере для одного из его элементов (но опять же, неизвестно какого).

 Профиль  
                  
 
 Re: Очень длинные периоды
Сообщение22.09.2013, 07:50 
Заслуженный участник


08/04/08
8556
Dave в сообщении #766093 писал(а):
2. Для любого натурального $n$ существует такое натуральное число $x$, состоящее не более чем из $2n$ цифр, что в десятичной записи дроби $\frac 1 x$ встречаются любые $n$ цифр подряд.
Видимо, так:
$x$ имеет не более $2n$ цифр $\Leftrightarrow x<10^{2n+1}$. Берем число $x=10^{2n+1}-a, a>0$, тогда $\frac{1}{x}=0,\underbrace{0...0}_{n}\underbrace{b_1...b_n}_{n}...$, где $b_1,...,b_n$ - такие цифры, что $\overline{b_1...b_n}+a=10^n$, и тогда если $a$ пробегает $1,2,3,...$, то группа цифр $b_1...b_n$ пробегает комбинации $9..99, 9..98, 9..97, ...$. Докажем, что так получатся именно все комбинации:
$\frac{1}{x}=\frac{1}{10^{2n+1}-a}=10^{-(2n+1)}\left(1+\frac{a}{10^{2n+1}}+\epsilon\right)$, где $\epsilon=\frac{1}{t}-(1+t)=\frac{t^2}{1-t}<t^2$ и $\epsilon>0$. Для того, чтобы получались все комбинации, нужно, чтобы $\epsilon$ был достаточно мал, а именно: $\epsilon<\frac{1}{10^{2n}}$. Это будет верно, если $t^2=\frac{a^2}{10^{4n+2}}<\frac{1}{10^{2n}}$, т.е. при $a<10^{n+1}$. Число таких $a$ как раз равно $10^n-1$ - не хватает еще одного.
Осталось еще один $a$ найти...

Dave, Вы используете подобный факт для доказательства исходного утверждения?

 Профиль  
                  
 
 Re: Очень длинные периоды
Сообщение22.09.2013, 08:12 
Заслуженный участник
Аватара пользователя


03/12/11
640
Україна
maxal в сообщении #766368 писал(а):
Не совсем так. Доказано, что гипотеза Артина справедлива для всех простых чисел, за исключением возможно двух, но при этом неизвестно, каких именно. Поэтому для множества простых $\{3,5,7\}$ (да и вообще любого другого множества их трёх или более простых), мы можем утверждать, что гипотеза Артина справедлива по крайней мере для одного из его элементов (но опять же, неизвестно какого).
Теперь понятно. Стало быть результат Heath-Brown составных оснований степени не касается вообще. Спасибо, maxal.

Sonic86 в сообщении #766511 писал(а):
Берем число $x=10^{2n+1}-a, a>0$, ... и тогда если $a$ пробегает $1,2,3,...$
$x$ должно быть только одно для заданного $n$, т.е. соответствующая ему дробь должна покрывать сразу все $10^n$ комбинаций цифр.

Sonic86 в сообщении #766511 писал(а):
Dave, Вы используете подобный факт для доказательства исходного утверждения?
Результат, точнее доказательство второй задачи годится только для самого первого, слабого варианта задачи. Именно поэтому я впоследствии разделил задачу на две. Считаю, что не только асимптотика, но и периоды некоторых дробей представляют определённый интерес.

 Профиль  
                  
 
 Re: Очень длинные периоды
Сообщение23.09.2013, 18:19 
Заслуженный участник


12/08/10
1608
$$\frac{p(9^n)}{9^n}=\frac{1}{9}$$

 Профиль  
                  
 
 Re: Очень длинные периоды
Сообщение23.09.2013, 19:01 
Заслуженный участник


08/04/08
8556
Null в сообщении #767042 писал(а):
$$\frac{p(9^n)}{9^n}=\frac{1}{9}$$
Точно! Вот я тупанул!:
Если $g$ - образующая по модулю $p^k, k\geqslant 2$, то $g$ - образующая по модулю $p^{k+1}$. Обозначив $p_a(m)$ - период $a$ по модулю $m$ получим $p_g(p^k)=\varphi(p^k)=p^k(1-p^{-1})$, т.е. $\frac{p_{10}(p^k)}{p^k}=1-\frac{1}{p}$. Остается только вручную подобрать такое достаточно большое $p$, для которого $10$ - образующая по модулю $p^2$, последнее верно, если $10$ - образующее по модулю $p$ и не удовлетворяет сравнению $10^{p-1}\equiv 1\pmod{p^2}$ (по гипотезе Артина - найдем обязательно, для строгости нужно воспользоваться компом).
Есс-но, число $10$ никакой роли не играет.
Null, огромное Вам спасибо!

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 14 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group