Вероятность и теория чисел.

[maxal]

Вот еще открытая проблемка про свободность от квадратов:

верно ли, что для простого p число $2^p - 1$ всегда свободно от квадратов?

Кстати, легко видеть, что если $q^2$ делит $2^p - 1$, то $q$ - это Wieferich prime, а их на данный момент известно всего лишь две штуки.

[juna]

Это мало отличается от предыдущего: по abc гипотезе
$2^p\leqslant K({\epsilon})(2p_1p_2..p_n)^{1+\epsilon}$, где $\epsilon$ - некоторая константа и $K(\epsilon})$ - константа, зависящая от $\epsilon$, $p_1,p_2,...p_n$ - простые делители числа $2^p-1$ без степени. Это неравенство выполняется, если начиная с некоторого $p$ все степени простых $p_1,p_2,...p_n$ в разложении $2^p-1$ единичны.

[vbn]

Руст, Вы могли бы дать словесное описание на примере, скажем, простого $p=7.$

Так понимаю, нужно доказать, что $7^2$ не делит никакое $M(x)+1$.
Для этого используется сравнение $M(x)$ с числом $48=7^2-1$.
Но ведь $M(x)$ делится на простые $p_0=2, p_1=3$.

Чего-то здесь я не понял...

[Руст]

vbn писал(а):

Руст, Вы могли бы дать словесное описание на примере, скажем, простого $p=7.$

Так понимаю, нужно доказать, что $7^2$ не делит никакое $M(x)+1$.
Для этого используется сравнение $M(x)$ с числом $48=7^2-1$.
Но ведь $M(x)$ делится на простые $p_0=2, p_1=3$.

Чего-то здесь я не понял...

Сравнивается M(x) c p^2-1 по модулю p^2 (а не по модулю p^2-1).

[maxal]

Статья Г. Дж. Чейтин. Случайность в арифметике., хотя она немного про другой ракурс случайности.

[vbn]

Артамонов Ю.Н. писал(а):

Если я не ошибаюсь, то из abc следует, что начиная с некоторого $n$ в числе $M^n(x)+1$ все простые числа в первой степени.

Артамонов Ю.Н. писал(а):

Просто это показывает, что искомая гипотеза много сильнее abc гипотезы.
А как из abc показать, что именно при $n>2$ выражение $M^n(x)+1$ свободно от квадратов?

Так это же следует из Вашего первого поста.
Что-то не пойму, какая же гипотеза все-таки сильнее.
Наверняка abc, раз из нее следует простота x# (и, автоматически, "свободность" от квадратов)

[juna]

Из abc свободность от квадратов для $M(x)+1$ как раз не следует. А для того, чтобы утверждать, что для $n>2$ $M^n(x)+1$ свободно от квадратов нужно оценивать $\epsilon$. Вот я и спрашивал у Руста, как это сделать.

[vbn]

Что же, в таком случае, следует из abc касательно x#?

[maxal]

Обнаружилась такая статья:

A. M. Vershik, The asymptotic distribution of factorizations of natural numbers into prime divisors, Dokl. Akad. Nauk SSSR 289 (1986), 269-272; English transl. in Soviet Math. Dokl. 34 (1987), 57-61.

Интересно было бы почитать, но PDF пока не нашел.

[vbn]

Руст писал(а):

Сравнивается M(x) c p^2-1 по модулю p^2 (а не по модулю p^2-1).

Хорошо, значит мы сравниваем $M(x)$ c $48=7^2-1$ по модулю $49=7^2:$
$M(x) \ne 48 \ (mod \ 49).$

1) Правильно ли я Вас понял?
2) Если да, то каков будет алгоритм для данного конкретного случая?

[Руст]

Правильно поняли. Вначале присваеваем M(x)=1 и начинаем цикл по простым
p1=7*7;g=p1-1;
for i=0;i<3;i++){
M(x)*=p[i],M(x)%=p1;
if(M(x)==g) print (i,p[i],p1);}

[Егор]

maxal писал(а):

Обнаружилась такая статья:

A. M. Vershik, The asymptotic distribution of factorizations of natural numbers into prime divisors, Dokl. Akad. Nauk SSSR 289 (1986), 269-272; English transl. in Soviet Math. Dokl. 34 (1987), 57-61.

Интересно было бы почитать, но PDF пока не нашел.

Вот эта статья в форматах DjVu и LaTeX.

[vbn]

vbn писал(а):

Мы сравниваем $M(x)$ c $48=7^2-1$ по модулю $49=7^2.$ Нужно доказать, что
$M(x) \ne 48 \ (mod \ 49).$

Согласно алгоритму, мы убеждаемся, что:
$M(1)=2 \ne 48 \ (mod \ 49); $M(2)=2 \cdot 3 \ne 48 \ (mod \ 49); $M(3)=2 \cdot 3 \cdot 5 \ne 48 \ (mod \ 49).$
На этом вычисления останавливаются.
Но какие тогда гарантии, что $M(x>3) \ne 48 \ (mod \ 49)?$

[Руст]

vbn писал(а):

Но какие тогда гарантии, что $M(x>3) \ne 48 \ (mod \ 49)?$

Дальше M(x)=0(mod 7), а значит не может M(x)+1 делится не только на 49, но и на 7.

[vbn]

vbn писал(а):

Руст писал(а):

Я проверил, что для простых $p<2^{24}$ нет делимости на квадрат.

Не подскажете, каким же способом Вы это проверили,
на примере, скажем, простого $p=16 777 213.$

Получается, что для $p_{1077870}=16 777 213<2^{24}$ программа перемножает все простые вплоть до $p_{1077869}=16 777 199.$
Следовательно, программа имеет дело с числами вплоть до $\alpha>2^{\pi (p_{1077869})}=2^{1077869}>10^{300000}$.
Руст, это действительно так?