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

[Руст]

В теории чисел имеется много проблем, к которым нет никакого подхода в настоящее время. При этом справедливость можно как то оценить только вероятностными соображениями. Вот один из таких примеров.
Пусть M(x) означает произведение всех простых не превосходящих х (иногда называют примиалом и даже особенным образом обозначают х#). Ещё Евклид доказал бесконечность простых чисел рассматривая M(x)+1. Некто выдвинул гипотезу, что M(x)+1 всегда свободно от квадратов. Если оценить грубо, числа свободные от квадратов составляют долю не больше 2/3, а следовательно вероятность того, что все они свободны от квадратов равна нулю. Но здесь не учли, что M(x)+1 не делится на простое число не превосходящее х. Более точная прикидка даёт, что вероятность того, что для простого числа р найдётся хоть одно простое х, что p|(M(x)+1) равна приблизительно 1/ln(p) (примерно p/ln(p) кандидатов M(x)), соответственно вероятность того, что ни один из них не делится на p^2 оценивается как:

$$P=\prod_p (1-\frac{1}{p ln(p)})$$

(произведение сходится). Я проверил, что для простых $p<2^{24}$ нет делимости на квадрат. Поэтому, в вышеприведённой оценке можно начать с 25 битных простых чисел, что даёт оценку справедливости утверждения P>0.93.

[juna]

Как по-честному подступиться к этой проблеме я не вижу. Возможно, есть еще не открытые очень сильные теоремы на ограничения порядка простых в различных выражениях, что гипотеза abc отдыхает.
А может это относится к утверждениям, которые нельзя ни доказать ни опровергнуть?

[Brukvalub]

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

...соответственно вероятность того, что ни один из них не делится на p^2 оценивается как:

$$P=\prod_p (1-\frac{1}{p ln(p)})$$

(произведение сходится)...

Не сочтите за придирку, но мне действительно непонятно, почему все факты неделимости можно считать независимыми событиями? (ведь эта оценка предполагает их независимость?)

[ИСН]

Строго говоря, нельзя. То есть можно для эвристических оценок, как это и было проделано, но это не оценка сверху и не оценка снизу - это оценка "что-то типа".

[Руст]

Я и хотел возбудить интерес к этой тематике. С одной стороны ответ или да или нет (тогда должен быть контрпример) или не доказуемо. То, что я проверил, вроде бы не имеет никакого отношения к ответу. Тем не менее, после этой проверки чаша весов в некотором смысле отклонилась в сторону скорее да. Может случиться, что ещё несколько вычислений и найдётся контрпример. Как это формализовать отношение вероятности конкретно к проблемам теории чисел, когда ответ должен быть чётким, как указано выше, я не знаю.

[Macavity]

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

Я проверил, что для простых нет делимости на квадрат.

А как часто встречалась делимость на простое число.

[Руст]

Делимость на простое р примерно соответствует вероятностному, в среднем на одно из ln(p) простых одного порядка. Хотя специально эту статистику не вёл.

[juna]

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

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

Если еще не читали, то вот две книги, которые я хотел прочитать, но все еще не осилил.
М.Кац Статистическая независимость в теории вероятностей, анализе и теории чисел
Й.Кубилюс Вероятностные методы в теории чисел

[Macavity]

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

Делимость на простое р примерно соответствует вероятностному, в среднем на одно из ln(p) простых одного порядка. Хотя специально эту статистику не вёл.

Несколько вопросов.

Интересно, а существуют ли аналогичные гипотезы для кубов и более высоких степеней. Или исходя из оценки для квадратов эти гипотезы считаются "очевидно истинными". Или для старших степеней существует аналитическое доказательство? Если нет, то изменит ли отношение к старшим степеням нахождение контрпримера для квадратов?

При расчете вероятности для гипотезы квадратов учитывалась ли независимость появления разных простых делителей? То есть считается ли, что вероятность встречи p*p такой же, что и вероятность встречи p*q? В принципе, наверное, полезна статистика проверки делимости на несколько различных простых чисел.

[Руст]

Для кубов и больших степеней в произведении увеличатся степени p, и соответственно сходимость к 1 будет более быстрой. Соответственно можно говорить с вероятностью 0.99999999 ни одно из этих чисел не делится на куб простого числа. Плохая сходимость только для квадратов.
Но главное, как я уже говорил, в применении вероятности к ответу да, нет, недоказуема.
Традиционно в теории чисел вероятности применяются к оценке плотности некоторого подмножества натуральных чисел.

[juna]

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

[Руст]

Это так. Но тут нет связи с предыдущей задачей. Можно даже говорить, что при фиксированном n>=3 начиная с некоторого х все свободны от квадратов (согласно гипотезе abc).

[juna]

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

[vbn]

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

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

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

[Руст]

Алгоритм такой.
1. Создаются простые числа pl[i] (pl[0]=2,pl[1]=3,...) массив из N чисел.
2. Создается подпрограмма умножения двух чисел a,b по модулю p M(a,b,p). Я рассматривал когда все величины имеют не больше 24 битов, для дальнейшего надо переделать до 32 битов.
3. Создается подпрограмма умножения по модулю p^2 M2(a,b,p_1), p_1=p^2, здесь а и p1 - числа 48 битов (в дальнейшем нужно 64 бита), b - число 24 бита (в дальнейшем 32) бита.
Сам алгоритм:
for(i=1;i<N;i++){p=pl[i]; g=p-1; a=1; d=0;
for(j=0;j<i;j++){a=M(a,pl[j],p); if(a==g)d=j;}
if(d){a1=1;p1=p^2; g1=p1-1; (большие числа)
for(j=0;j<=d;j++){a1=M2(a1,pl[j],p1); if(a1==g1)cout<<pl[j]<<p[i]; // печать и в файл}
}
Так как для большинства простых нет делимости и на первую степень отделение расчёта по модулю p^2 в отдельную подпрограмму существенно экономит время.
Делимость M(x)+1 на p или p^2 заменяется сравнением M(x) с p-1 или с p^2-1.
Можете продолжить вычисления сами.
Можете сами