Бесконечность простых в последовательности многочленов

[vicvolf]

nnosipov в сообщении #707047 писал(а):

vicvolf в сообщении #707044 писал(а):

Приведенный пример к данному типу многочленов не относится.

Ну, другой пример есть: $x^3+5x+3$. Этот многочлен принимает только нечётные значения. И в то же время все его значения кратны трём.

Спасибо за контрпример. Но я что-то не мойму. Теорема 148 Бухштаб - Сравнение степени n по простому модулю p с коэффициентом при старшем члене, не делящимся на p, может иметь не более n решений.
В нашем случае многочлен $x^3+5x+3$ имеет коэффициент при старшем члене 1, который не делится на 3. Почему сравнение его с 0 по модулю 3 имеет больше 3 решений?
С другой стороны Теорема 149 Бухштаб -Если сравнение степени n по простому модулю p имеет больше, чем n решений, то все коэффициенты сравнения делятся на p. Чтобы этого не было я в условиях и потребовал, чтобы все коэффициенты многочлена были взаимнопростыми числами.

[nnosipov]

vicvolf в сообщении #707280 писал(а):

Теорема 148 Бухштаб - Сравнение степени n по простому модулю p с коэффициентом при старшем члене, не делящимся на p, может иметь не более n решений.

Здесь под решением подразумевается класс вычетов по модулю $p$. То есть, у сравнения степени $n$ может быть не более $n$ решений --- классов вычетов по модулю $p$.

[vicvolf]

nnosipov в сообщении #707293 писал(а):

vicvolf в сообщении #707280 писал(а):

Теорема 148 Бухштаб - Сравнение степени n по простому модулю p с коэффициентом при старшем члене, не делящимся на p, может иметь не более n решений.

Здесь под решением подразумевается класс вычетов по модулю $p$. То есть, у сравнения степени $n$ может быть не более $n$ решений --- классов вычетов по модулю $p$.

А в этом примере сколько классов вычетов будет - один?

[nnosipov]

Нет, все три класса вычетов и будут решениями сравнения $x^3+5x+3 \equiv 0 \pmod{3}$. Это и означает, что любое целое число $x$ удовлетворит данное сравнение.

[vicvolf]

nnosipov в сообщении #707302 писал(а):

Нет, все три класса вычетов и будут решениями сравнения $x^3+5x+3 \equiv 0 \pmod{3}$. Это и означает, что любое целое число $x$ удовлетворит данное сравнение.

Но это не совсем соответствует теореме 150 Бухштаб. Там для того, чтобы сравнение n-ой степени по модулю p с многочленом с коэффициентом при наибольшей степени равным 1 имело ровно n решений, то одним из требований является, чтобы свободный член многочлена не делился на p. А в Вашем примере свободный член многочлена равный 3 делится на p=3?

[nnosipov]

Не понимаю, о чём Вы. Приведите формулировку теоремы буквально и сформулируйте, что не так с примером.

Посмотрел формулировку теоремы 150. К сравнению $x^3+5x+3 \equiv 0 \pmod{3}$ эта теорема просто неприменима.

-- Пн апр 08, 2013 19:49:48 --

vicvolf в сообщении #707333 писал(а):

Там для того, чтобы сравнение n-ой степени по модулю p с многочленом с коэффициентом при наибольшей степени равным 1 имело ровно n решений, то одним из требований является, чтобы свободный член многочлена не делился на p.

Нет, это Вы неправильно понимаете формулировку теоремы 150.

[vicvolf]

nnosipov в сообщении #707337 писал(а):

Посмотрел формулировку теоремы 150. К сравнению $x^3+5x+3 \equiv 0 \pmod{3}$ эта теорема просто неприменима.

Почему же не применима? Там рассматривается случай, когда сравнение имеет ровно n решений, т.е в данном случае 3. Вы написали, что в этом примере 3 решения. Первый коэффициент многочлена по теореме равен 1, как и в примере. Вы имеете ввиду, что оба остальных требования теоремы не выполняются?

[nnosipov]

vicvolf в сообщении #707356 писал(а):

Почему же не применима?

Потому что критерий формулируется только для сравнений, у которых свободный коэффициент не ноль по модулю $p$. Об этом сказано в первом предложении формулировки теоремы 150.

[vicvolf]

Как Вы просили, даю определение условной вероятности.
Пусть $A,B\in \sigma$ и $P(B)>0,$ то
$P(A/B)=\frac {P(A \cap B)} {P(B)}.$
Теперь к теме.
Значит действительно нужны дополнительные необходимые условия, накладываемые на многочлен, кроме указанных: многочлен 3 типа, неприводимый над кольцом целых чисел, с взаимнопростыми коэффициентами, чтобы выделить класс многочленов 3 типа, последовательность, которых не будет полностью содержать только составные числа. Возможно те, которые назвал Руст, надо подумать, но эти условия точно есть. Вот для этой последовательности и проводить доказательство.
Можно вообще пока не выделять класс таких многочленов, так как это немного другая проблема, а взять конкретный многочлен 3-его типа, удолетворяющий данным требованиям и с ним проводить доказательство. Например, предложенный Вами, многочлен $4x^2+1$.

[nnosipov]

vicvolf в сообщении #707390 писал(а):

Например, предложенный Вами, многочлен $4x^2+1$.

Да пожалуйста. Надеюсь, Вы понимаете, на что себя обрекаете.

[vicvolf]

nnosipov в сообщении #707409 писал(а):

vicvolf в сообщении #707390 писал(а):

Например, предложенный Вами, многочлен $4x^2+1$.

Да пожалуйста. Надеюсь, Вы понимаете, на что себя обрекаете.

Я бы только просил, чтобы меня критиковали конструктивно. Не писали, что это не верно, а показали, почему это не верно. Дали возможность исправить обнаруженные ошибки, которые я смогу исправить.

[nnosipov]

vicvolf в сообщении #707439 писал(а):

Я бы только просил, чтобы меня критиковали конструктивно. Не писали, что это не верно, а показали, почему это не верно.

А мы пока занимались предварительной работой --- выясняли точный смысл тех понятий, которыми Вы намереваетесь оперировать (различные виды плотности последовательностей, вероятностная мера, условная вероятность). Разве это было неконструктивно? Нельзя надеяться на строгое доказательство, если опираться на терминологию с размытым смыслом. Теперь, располагая строгими определениями вероятности и условной вероятности, Вы можете по-новому взглянуть на то обоснование ключевого для доказательства неравенства, которое Вы привели в начале темы. И самостоятельно понять, почему это обоснование ошибочно (ошибка состояла в некорректном применении понятия "условная вероятность").

[vicvolf]

nnosipov в сообщении #707474 писал(а):

vicvolf в сообщении #707439 писал(а):

Вы можете по-новому взглянуть на то обоснование ключевого для доказательства неравенства, которое Вы привели в начале темы. И самостоятельно понять, почему это обоснование ошибочно (ошибка состояла в некорректном применении понятия "условная вероятность").

Да, я думал об этом. Здесь надо сначала поговорить о просеивании простых чисел последовательностями. Рассмотреть вопрос об изменении плотности простых чисел при данной операции. Сейчас нам хорошо известен вопрос о просеивании простых чисел арифметическими прогрессиями. С него я и начну. А затем....

Утверждение 1
Асимптотическая плотность простых чисел в натуральном ряде является минимальной в последовательностях арифметических прогрессий $f(n)=kn+l$ при целых положительных k,l и $(k,l)=1$.

Доказательство
Ранее было показано, что асимптотическая плотность простых чисел в последовательности арифметической прогрессии определяется по формуле:
$P(f,2,x) \sim \frac {k} {\varphi(k)\ln(x)}.(1)$.
Для натурального ряда при $k=1$ получаем:
$P(f,2,x) \sim \frac {1} {\ln(x)}$, т.е. $\frac {1} {\varphi(1)}=1$.
Пусть каноническое разложение k для других случаев:
$k=p_1^{a_1}\cdot p_2^{a_2}\cdot ...\cdot p_s^{a_s},$
где $p_i$ - простое число с номером i.
Рассмотрим отношение:
$\frac {k} {\varphi(k)}=\frac {p_1^{a_1}\cdot p_2^{a_2}\cdot ...\cdot p_s^{a_s}} {p_1^{a_1-1}\cdot p_2^{a_2-1}\cdot ...\cdot p_s^{a_s-1}(p_1-1)(p_2-1)...(p_s-1)}=\frac {p_1\cdot p_2\cdot ...\cdot p_s}{(p_1-1)\cdot (p_2-1)\cdot ...\cdot (p_s-1)}>1,(2)$
т.е. больше, чем для натурального ряда ч.т.д.

Следствие
Асимптотическая плотность простых чисел в арифметической прогрессии $f(n)=kn+l$ при целых положительных (k,l)=1 не зависит от степеней $a_1,a_2,...a_s$ в каноническом разложении k.
Доказательство следует напрямую из формулы (2).

Таким образом при просеивании простых чисел в натуральном ряде арифметическими прогрессиями $f(n)=kn+l$ при целых положительных k,l и $(k,l)=1$ плотность простых чисел в данных прогрессиях возрастает.

[vicvolf]

Из этого следствия вытекает, например, что все последовательности вида $f_a(n)=(2^a)n+1$ имеют одинаковую асимптотическую плотность. Асимптотическая плотность последовательностей $f_a(n): P(f_a,2,x) \sim \frac {2} {\ln(x)}$ (3).
Таким образом, асимптотическая плотность простых чисел в последовательности нечетных чисел равна удвоенной плотности простых чисел в натуральном ряде. Это понятно, так как количество членов натурального ряда уменьшилось вдвое (удалились четные числа), а количество простых чисел в последовательности нечетных чисел по сравнению с натуральным рядом не изменилось.
Интересно, что если дальше просеивать последовательность нечетных чисел в последовательности 4n+1, то асимптотическая плотность простых чисел не изменится. Если продолжить такое просеивание дальше, то асимптотическая плотность простых чисел также не изменится (см. следствие).
Обратите внимание, что асимптотическая плотность простых чисел в последовательности (3) является не самой большой, поэтому числа Мерсена или числа Ферма не являются последовательностями с наибольшей асимптотической плотностью простых чисел.
Например, асимптотическая плотность простых чисел в последовательности f(n)=6n+1 равна: $P(f,2,x) \sim \frac {3} {\ln(x)}$ (4), что конечно больше чем (3).

[nnosipov]

vicvolf, у Вас сменился смысл обозначения $P(f,2,x)$.