Очень длинные периоды

[Dave]

Для любого натурального $n$ обозначим через $p(n)$ длину периода дроби $\frac 1 n$ в десятичной записи. Докажите, что

$$\varlimsup_{n \to \infty} {\frac {p(n)} {\sqrt n}} = +\infty \, .$$

[Dave]

Похоже, что можно даже усилить (правда, пока не доказал):

$$\varlimsup_{n \to \infty} {\frac {p(n)} n} > 0 .$$

[whitefox]

Докажите гипотезу Артина, и всё получится

[Sonic86]

whitefox в сообщении #765919 писал(а):

Докажите гипотезу Артина
, и всё получится

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

[whitefox]

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

Тогда получим

$$\varlimsup_{n \to \infty} {\frac {p(n)} n} \geqslant \frac 1 2$$

[Sonic86]

whitefox в сообщении #766059 писал(а):

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

Это известная гипотеза о бесконечности простых Жермен, тоже вряд ли тут докажем.

[whitefox]

Да, действительно. Запамятовал.

[Sonic86]

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$ теряю? Неужели барьер квадратного корня?

[Dave]

Задача раздвоилась

Докажите, что:
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 в это множество не входит то, теоретически, можно было бы использовать этот результат при решении первой части задачи?

[maxal]

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\}$ (да и вообще любого другого множества их трёх или более простых), мы можем утверждать, что гипотеза Артина справедлива по крайней мере для одного из его элементов (но опять же, неизвестно какого).

[Sonic86]

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, Вы используете подобный факт для доказательства исходного утверждения?

[Dave]

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, Вы используете подобный факт для доказательства исходного утверждения?

Результат, точнее доказательство второй задачи годится только для самого первого, слабого варианта задачи. Именно поэтому я впоследствии разделил задачу на две. Считаю, что не только асимптотика, но и периоды некоторых дробей представляют определённый интерес.

[Null]

$$\frac{p(9^n)}{9^n}=\frac{1}{9}$$

[Sonic86]

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, огромное Вам спасибо!