Исследование гипотезы Гильбрайта

[vicvolf]

Цитата:

Теперь при доказательстве утверждений используется строка индикатор сходимости (ИС). ИС находится значительно выше нулевой строки. Например, при r=4 (m=2*3*5*7=210) ИС находится в 15 строке разностей треугольника Гильбрайта под строкой первых разностей - 2,10,2,10,2. 15 строка соответствует вычету 67 на интервале от 0 до 0,5m, который значительно меньше $p^2_{r+1}=11^2=121$. Таким образом, если треугольник Гильбрайта сходится до числа 67 (с решетом Эратосфена в основании треугольника при r=4), то из-за наличия ИС в15 строке далее он сходится везде.
При r=5 (m=2*3*5*7*11=2310) ИС находится в 9 строке разностей треугольника Гильбрайта, т.е выше чем при m=210, так как находится под строкой первых разностей: 4,12,2,12,4. 9-ая строка соответствует вычету 41 на интервале от 0 до 0,5m, который значительно меньше $p^2_{r+1}=13^2=169$. При r=6 (m=2*3*5*7*11*13=30030) ИС находится опять в 15 строке разностей треугольника Гильбрайта, так как находится под строкой первых разностей: 2,16,2,16,2. 15-ая строка соответствует вычету 67 на интервале от 0 до 0,5m, который значительно меньше $p^2_{r+1}=17^2=289$ и.т.д.

Приведенный выше анализ показывает, что строка ИР на r+1 шаге решета Эратосфена начинается раньше, чем $p^2_{r+1}$. Например, при r+1=5 ИС находится в 9 строке, соответствующей вычету $49<11^2=121$, а при r+1=6 ИС находится в 15 строке, соответствующей вычету $67<13^2=169$.

Буду благодарен за замечания и предложения.

[vicvolf]

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

Цитата:

Теперь при доказательстве утверждений используется строка индикатор сходимости (ИС). ИС находится значительно выше нулевой строки. Например, при r=4 (m=2*3*5*7=210) ИС находится в 15 строке разностей треугольника Гильбрайта под строкой первых разностей - 2,10,2,10,2. 15 строка соответствует вычету 67 на интервале от 0 до 0,5m, который значительно меньше $p^2_{r+1}=11^2=121$. Таким образом, если треугольник Гильбрайта сходится до числа 67 (с решетом Эратосфена в основании треугольника при r=4), то из-за наличия ИС в15 строке далее он сходится везде.
При r=5 (m=2*3*5*7*11=2310) ИС находится в 9 строке разностей треугольника Гильбрайта, т.е выше чем при m=210, так как находится под строкой первых разностей: 4,12,2,12,4. 9-ая строка соответствует вычету 41 на интервале от 0 до 0,5m, который значительно меньше $p^2_{r+1}=13^2=169$. При r=6 (m=2*3*5*7*11*13=30030) ИС находится опять в 15 строке разностей треугольника Гильбрайта, так как находится под строкой первых разностей: 2,16,2,16,2. 15-ая строка соответствует вычету 67 на интервале от 0 до 0,5m, который значительно меньше $p^2_{r+1}=17^2=289$ и.т.д

Приведенный выше анализ показывает, что строка ИР на r+1 шаге решета Эратосфена начинается раньше, чем $p^2_{r+1}$. Например, при r+1=5 ИС находится в 9 строке, соответствующей вычету $49<11^2=121$, а при r+1=6 ИС находится в 15 строке, соответствующей вычету $67<13^2=169$.

А теперь докажем это. Из приведенных выше примеров видно, что номер строки ИС (k) при увеличении r может, как возрастать, так и убывать. Нас интересует случай его максимального возрастания, который бывает при следующей последовательности первых разностей треугольника Гильбрайта: $2, p_{r+1}-1, 2, p_{r+1}-1, 2$. При этом вторая разность принимает значение $p_{r+1}-1-2= p_{r+1}-3$ и k возрастает пропорционально $p_{r+1}-3$, т.е. $k=O(p_{r+1}-3)$ (1).
В основании треугольника Гильбрайта данному k соответствует простое число $p_k$, которое на основании асимптотической формулы простых чисел [3] можно представить в виде $p_k=O(kln(k))$ (2).
Подставляя в (2) выражение (1) получаем:
$p_k=O((p_{r+1}-3) ln((p_{r+1}-3)))$ (3).
Учитывая, что $p_{r+1}-3=O((r+1)ln(r+1))$, получаем:
$p_k=O((p_{r+1}-3) ln((p_{r+1}-3)))=O((r+1)ln(r+1)ln[(r+1)ln(r+1)])=O((r+1)ln^2(r+1))$ (4).

Величина $p^2_{r+1}=O((r+1)^2ln^2(r+1))$ растет быстрее, чем $O((r+1)ln^2(r+1))$ ч.т.д.

Буду благодарен за замечания и предложения!

[Sonic86]

Опр. Отрезком возрастающей последовательности $A=\{a_1,...a_n\}$ называется любая подпоследовательность вида $A\cap [a,b]$.
Так, я вроде схему рассуждения в целом понял: ГГ верна $\Leftrightarrow$ для любой конечной последовательности $p_1,...,p_s$ из первых простых чисел треугольник Гилбрайта имеет индикатор сходимости (далее ИС) (т.е. первую строку в треугольнике, все элементы которой $\leqslant 2$). Для доказательства последовательность $p_1,...,p_s$ разбивается на два отрезка: $p_1,...,p_r$ и $p_{r+1},...,p_s$, где $r$ - такое, что $p_r$ - наибольшее простое число, не превосходящее $\sqrt{p_s}$. Далее пытаемся доказывать так: доказываем, что ИС существует для 1-й последовательности $p_1,...,p_r$, доказываем, что ИС существует для 2-й последовательности $p_{r+1},...,p_s$, а затем пытаемся делать вывод, что если ИС есть для 1-й последовательности и ИС есть для 2-й последовательности, то ИС есть для всей последовательности (т.е. надо 3 факта доказать).
1-й факт (существование ИС для $p_1,...,p_r$) Вы пытаетесь доказать через добавление простых в начало $\text{ПСВ}_{p_1...p_r}$, рассмотрением там расстояний и т.п.. Я не уверен в истинности приведенного доказательства (могу написать почему), но мне кажется, что его можно просто не доказывать, если вести доказательство индукцией по $r$. Т.е. явно доказываем базу, а потом, предполагая, что для начального отрезка последовательности простых чисел ИС уже есть, добавляем еще простые числа (из ПСВ) и доказываем существование общего ИС для нового (более длинного) отрезка.
2-й факт (существование ИС для $p_{r+1},...,p_s$) Вы доказываете через ПСВ. $\{p_{r+1},...,p_s\}$ - это отрезок $\text{ПСВ}_{p_1...p_r}$ (т.е. $(\exists a,b)\{p_{r+1},...,p_s\}=[a,b]\cap\text{ПСВ}_{p_1...p_r}$). Для всей ПСВ существует ИС, тогда и для отрезка ПСВ существует ИС. Здесь не совсем понятно, откуда следует, что если ИС есть во всей ПСВ, то ИС есть и в более маленьком треугольнике. Самый простой пример - берем $\text{ПСВ}_{30}=\{1;7;11;13;17;19;23;29\}$, для которой ИС есть, и берем в ней очень маааленький отрезок $23;29$ - треугольник Гилбрайта на нем не содержит ИС. Т.е. в общем случае неверно - надо еще что-то брать. Но даже это не главное (по-моему).
3-й факт: если последовательность разбить на 2 отрезка, и если 1-й отрезок имеет ИС (обозначу ее ИС1) и 2-й отрезок имеет ИС (обозначу ее ИС2), то откуда следует, что есть общая ИС для всей последовательности? Давайте для простоты предположим, что номера строк ИС1 и ИС2 равны. По Вашему следствию номер ИС всей последовательности будет тем же. Однако, общая ИС лишь содержит объединение $\text{ИС}_1\cup\text{ИС}_2$ (это ее края, а серединка - нет). А что находится в середине? - неизвестно. Конкретнее. пусть 1-й отрезок - $a_1,...,a_k$, 2-й отрезок - $b_1,...,b_l$, вся последовательность - $a_1,...,a_k,b_1,...,b_l$. Тогда наличие общей ИС зависит не только от ИС1, ИС2, но еще и от $b_1-a_k$. А какова эта разность? - неизвестно. Вот следуя этой логике легко строится контрпример. Пусть последовательность имеет вид $1;3;5;7;101;103;105;107$. Номер ИС1 и ИС2 - $1$, а треугольник вообще не сходится.
Как-то так

[vicvolf]

Sonic86, большое спасибо за подробный анализ!
Очевидно надо переформулировать свойство ИС.
Если в основании треугольника Гильбрайта находится ограниченная, возрастающая последовательность, у которой существует ИС, состоящая из нескольких интервалов, при этом на каждом интервале ИС располагается в разных строках треугольника, то ИС для всей последовательности находится в строке треугольника Гильбрайта с наибольшим номером.
Также надо переформулировать следствие 1 теоремы 3.
Следствие
Треугольник Гильбрайта, у которого в основании находится последовательность вычетов nПСВm содержит ИС на интервале от 0,5m до 1,5m*n, которая является продолжением ИС на интервале от 0,5m до 1,5m.
Доказательство. На основании теоремы 3 треугольник Гильбрайта, у которого в основании находится последовательность вычетов nПСВm на интервале от 0,5m до 1,5m содержит ИС.По определению nПСВm данная последовательность содержит разности в треугольнике Гильбрайта периодически повторяющиеся с периодом m, в том числе и ИС на интервале от 0,5m до 1,5m, поэтому последовательность вычетов nПСВm содержит ИС на интервале от 0,5m до 1,5m*n, которая является продолжением ИС на интервале от 0,5m до 1,5m.

А следствие 2 наверно можно убрать!

[vicvolf]

Продолжение.
Теперь рассмотрим сходимость треугольника Гильбрайта, в основании которого находится последовательность натуральных чисел, получаемых после r-ого шага решета Эратосфена.
Если рассматривать сходимость треугольника Гильбрайта с основанием - последовательность вычетов nПСВ$_m$ на втором интервале (более 0,5m), то треугольник Гильбрайта сходится по следствию теоремы 3, так как под ИС находятся строки, состоящие только из чисел 0 и 2.
Осталось определить сходится ли треугольник Гильбрайта на первом интервале (до 0,5m).
Лемма.
Для простого числа $p_k$, с которого начинается ИР на r+1 шаге решета Эратосфена, выполняется соотношение $p_k< p^2_{r+1}$.
Доказательство.
Из приведенных выше примеров видно, что номер строки ИС (k) при увеличении r может, как возрастать, так и убывать. Максимальное возрастание k будет при следующей последовательности первых разностей треугольника Гильбрайта: $2, p_{r+1}-1, 2, p_{r+1}-1, 2$. При этом вторая разность принимает значение $p_{r+1}-1-2= p_{r+1}-3$ и k возрастает пропорционально $p_{r+1}-3$, т.е. $k=O(p_{r+1}-3)$ (1).
В основании треугольника Гильбрайта данному k соответствует простое число $p_k$, которое на основании асимптотической формулы простых чисел [3] можно представить в виде $p_k=O(kln(k))$ (2).
Подставляя в (2) выражение (1) получаем:
$p_k=O((p_{r+1}-3) ln((p_{r+1}-3)))$ (3).
Учитывая, что $p_{r+1}-3=O((r+1)ln(r+1))$, получаем:
$p_k=O((p_{r+1}-3) ln((p_{r+1}-3)))=O((r+1)ln(r+1)ln[(r+1)ln(r+1)])=O((r+1)ln^2(r+1))$ (4).
Величина $p^2_{r+1}=O((r+1)^2ln^2(r+1))$ растет быстрее, чем $O((r+1)ln^2(r+1))$ ч.т.д.

Теорема 5. Треугольник Гильбрайта, в основании которого находится последовательность, получаемая после любого наперед заданного числа шагов решета Эратосфена, сходится.
Доказательство. Проведем доказательство теоремы 5 методом математической индукции. Рассмотрим треугольник Гильбрайта, в основании которого находится последовательность решета Эратосфена при r=1:
2 3 5 7 и далее вычеты ПСВ по модулю $m=2^n$
1 2 2 …….
1 0 …….
Далее в строках треугольника будет первый элемент - 1, а остальные 0, поэтому треугольник Гильбрайта сходится.
Предположим, что треугольник Гильбрайта сходится для r=k и покажем, что в этом случае он будет сходиться при r=k+1.
Действительно, если треугольник сходится для r=k, т.е с последовательностью, полученной после k шагов решета Эратосфена, то в основании треугольника Гильбрайта будут простые числа 2, 3,...p_{k+1},...p_n <p^2_{r+1} [3], при которых согласно предположению треугольник сходится.
При r=k+1 (после k+1 шага решета Эратосфена) в основании треугольника Гильбрайта будут простые числа 2, 3,...p_{k+2},...p_n <p^2_{r+1}, при которых согласно предположению треугольник Гильбрайта сходится.
На основании леммы, строка ИС треугольника Гильбрайта начинается с простого числа $p_l<p^2_{r+1}$, поэтому, начиная с этого простого числа и далее для последовательности вычетов nПСВ$_m$ в основании, где $m=2*3*…*p_{k+1}$, треугольник Гильбрайта также будет сходиться.

Буду благодарен за замечания и предложения.

[vicvolf]

Цитата:

1-й факт (существование ИС для $p_1,...,p_r$) Вы пытаетесь доказать через добавление простых в начало $\text{ПСВ}_{p_1...p_r}$, рассмотрением там расстояний и т.п.. Я не уверен в истинности приведенного доказательства (могу написать почему), но мне кажется, что его можно просто не доказывать, если вести доказательство индукцией по $r$. Т.е. явно доказываем базу, а потом, предполагая, что для начального отрезка последовательности простых чисел ИС уже есть, добавляем еще простые числа (из ПСВ) и доказываем существование общего ИС для нового (более длинного) отрезка.

Если бы это было просто доказать по индукции, то это было было бы доказательство ГГ и ничего больше доказывать не надо

Цитата:

2-й факт (существование ИС для $p_{r+1},...,p_s$) Вы доказываете через ПСВ. $\{p_{r+1},...,p_s\}$ - это отрезок $\text{ПСВ}_{p_1...p_r}$ (т.е. $(\exists a,b)\{p_{r+1},...,p_s\}=[a,b]\cap\text{ПСВ}_{p_1...p_r}$). Для всей ПСВ существует ИС, тогда и для отрезка ПСВ существует ИС. Здесь не совсем понятно, откуда следует, что если ИС есть во всей ПСВ, то ИС есть и в более маленьком треугольнике. Самый простой пример - берем $\text{ПСВ}_{30}=\{1;7;11;13;17;19;23;29\}$, для которой ИС есть, и берем в ней очень маааленький отрезок $23;29$ - треугольник Гилбрайта на нем не содержит ИС. Т.е. в общем случае неверно - надо еще что-то брать. Но даже это не главное (по-моему).

Я сначала доказываю, что существует ИС для всей nПСВ$_m$ на основании симметрии ПСВ и периодичности nПСВ$_m$. При этом я доказываю, что ИС для первого ПСВ начинается с определенного простого числа - $p_k$ и в лемме даю его оценку, т.е для начального треугольника до этого $p_k$ ИС не существует. Затем я перехожу к ИС последовательности решета Эратосфена. Я доказываю, что ИС для решета Эратосфена будет расположена не ниже. Доказательство провожу не по отрезкам, а сразу для всего интервала, поэтому надо доказать один факт, а не три. При этом наличие ИС не доказывает сходимость треугольника Гильбрайта для решета Эратосфена. Доказательство этого факта я провожу по индукции.

[vicvolf]

Переформулируем свойство строки индикатора сходимости (ИС).
Если в основании треугольника Гильбрайта находится ограниченная, возрастающая последовательность, состоящая из двух пересекающихся интервалов, при этом на каждом интервале ИС располагается в разных строках треугольника, то ИС для всей последовательности находится в строке треугольника Гильбрайта с наибольшим номером.

Это дает возможность уточнить доказательство теоремы.
Теорема 4
Треугольник Гильбрайта, у которого в основании находится последовательность вычетов nПСВ$_m$ содержит ИС на интервале от 0, до nm, которая является продолжением ИС на интервале от 0,5m до 1,5m.
Доказательство. На основании теоремы 3 треугольник Гильбрайта, у которого в основании находится последовательность вычетов nПСВ$_m$ на интервале от 0 до m содержит ИС. На основании следствия теоремы 3 треугольник Гильбрайта, у которого в основании находится последовательность вычетов nПСВ$_m$ на интервале от 0,5m до 1,5m содержит ИС.
Из-за больших расстояний между вычетами, находящимися на интервале 0,5m до 1,5m последовательности nПСВ$_m$ :$…, m-p_{r+1}, m-1, m+1, m+p_{r+1},…. $ИС на этом интервале расположена ниже ИС на интервале от 0 до m в треугольнике Гильбрайта, где важное значение для расположения ИС имеет расстояние между вычетами $1, p_{r+1}$.
По определению nПСВ$_m$ данная последовательность содержит разности в треугольнике Гильбрайта периодически повторяющиеся с периодом m, в том числе и ИС на интервале от 0,5m до 1,5m, поэтому последовательность вычетов nПСВ$_m$ содержит ИС на интервале от 0 до nm, которая является продолжением ИС на интервале от 0,5m до 1,5m. Таким образом, мы имеем два пересекающихся интервала от 0 до m и от 0,5m до nm, на которых существуют ИС. Поэтому на основании свойства ИС на интервале от 0 до nm, существует ИС, которая является продолжением ИС на интервале от 0,5m до 1,5m.

Буду благодарен за замечания и предложения!

[vorvalm]

По-моему, у вас интервалы (0,m) и (0,5m,nm) не пересекаются, но объединяются.

[vicvolf]

vorvalm в сообщении #593329 писал(а):

По-моему, у вас интервалы (0,m) и (0,5m,nm) не пересекаются, но объединяются.

Добрый день! Конечно они объединятся. Но и пересекаются тоже на интервале (0,5m, m). Это мне нужно, чтобы между ними не было разрыва, где не существует ИС, как в контрпримере у Sonic86.

[vorvalm]

Да, но интервал (0,5m,m) - зеркальное отражение интервала (0,0,5m).

[vicvolf]

vorvalm в сообщении #593344 писал(а):

Да, но интервал (0,5m,m) - зеркальное отражение интервала (0,0,5m).

Да с ПСВ все так, но в общем случае свойство ИС, которое я переформулировал выше.

[Sonic86]

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

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

Не, не понимаю. Буду формально выяснять: ИС по определению - это некоторая строка треугольника (с одним номером). Но тогда если

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

на каждом интервале ИС располагается в разных строках треугольника

то ИС не существует. Попробуйте точнее сформулировать.

[vicvolf]

Добрый день Sonic 86!
Это старая формулировка. Я в последнем сообщении давал новую -

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

Переформулируем свойство строки индикатора сходимости (ИС).
Если в основании треугольника Гильбрайта находится ограниченная, возрастающая последовательность, состоящая из двух пересекающихся интервалов, при этом на каждом интервале ИС располагается в разных строках треугольника, то ИС для всей последовательности находится в строке треугольника Гильбрайта с наибольшим номером.

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

-- 08.07.2012, 14:58 --

Sonic86 в сообщении #593385 писал(а):

Буду формально выяснять: ИС по определению - это некоторая строка треугольника (с одним номером). Но тогда если

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

на каждом интервале ИС располагается в разных строках треугольника

то ИС не существует. Попробуйте точнее сформулировать.

Нет это не значит, что у объединенного интервала ИС не существует. В этом случае ИС будет расположена в строке с наибольшим номером, так как по определению, там будет строка содержащая на объединенном интервале только числа 0 и 2. Если взять строку с меньшим номером, то на одном из отрезков будут числа большие 2, а если взять номер строки больше, то не проходит по определению , так как ИС эта строка с наименьшим номером, содержащая 0 и 2.

[vicvolf]

Пример.
1 7 11 13 17 19 23 29 31 37 41 43 47
6 4 2 4 2 4 6 2 6 4 2
2 2 2 2 2 2 4 4 2 2 - ИС1
0 0 0 0 0 2 0 2 0 - ИС2
0 0 0 0 2 2 2 2
0 0 0 2 0 0 0
0 0 2 2 0 0
0 2 0 2 0
2 2 2 2
0 0 0
На рис ИС1 для интервала (0,m), ИС2 для интервала (0,5m, 1,5m), где m=30. На объединенном интервале продолжение ИС2.

[Sonic86]

Я просто не очень понял - у Вас ИС-ов несколько - они соответствуют частям последовательности в 1-й строке треугольника или нет? Если да, то как ставится соответствие? (может так: часть последовательности - прообраз данной ИС? Тогда прообразы могут пересекаться - это нормально? Если да, то хотелось бы явно это увидеть написанным в тексте - а то приходится додумывать наугад)

(Оффтоп)

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

Нет это не значит, что у объединенного интервала ИС не существует. В этом случае ИС будет расположена в строке с наибольшим номером, так как по определению, там будет строка содержащая на объединенном интервале только числа 0 и 2. Если взять строку с меньшим номером, то на одном из отрезков будут числа большие 2, а если взять номер строки больше, то не проходит по определению , так как ИС эта строка с наименьшим номером, содержащая 0 и 2.

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