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

[Sonic86]

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

Вы согласны, что номер строки ИС является $O(d_m)$, где $d_m$ - максимальная разность между вычетами при модуле m?

Не знаю Это тоже надо доказывать, если это верно.

[vicvolf]

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

Соотношение монотонно убывает: 3/4, 15/24, 10/240, 21/2800.

В знаменателе рост, сравнимый с факториальной последовательностью, а в числителе не более полиномиальной, учитывая, что в числителе последовательность вообще при некоторых значениях убывает.

-- 30.07.2012, 13:32 --

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

Слева номер простого числа (аналог количества элементов в треугольнике Гильбрайта), справа G(N):
25 5
168 15
1229 35
9552 65
76498 95
664579 135
5761455 175
50847534 249
455052511 329
4118054813 417
37607912018 481
346065536839 635

Здесь аналогично, только в числителе последовательность строго возрастающая. Учитывая, что разности между простыми числами растут значительно быстрее,чем между ПСВ по понятным причинам.

[vicvolf]

Спасибо Sonic86! Давайте пока оставим доказательство следствия 2 - я еще подумаю. Есть ли замечания к доказательству теоремы 4?

[Sonic86]

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

Есть ли замечания к доказательству теоремы 4?

Вроде нет.

[vicvolf]

Тогда продолжим.
Теорема 5
Треугольник Гильбрайта, в основании которого находятся простые числа: 2, 3,…$p_r$ и далее последовательность вычетов nПСВ$_m$, начиная с $p_{r+1}$, будет содержать ИС, которая расположена также, как в треугольнике Гильбрайта с основанием в виде последовательности вычетов nПСВ$_m$.
Доказательство. На основании теоремы 4 треугольник Гильбрайта, у которого в основании находится последовательность вычетов nПСВ$_m$ содержит ИС, которая является продолжение строка индикатора сходимости на интервале от 0 до 1,5m nПСВ$_m$.
Рассмотрим интервал между вычетами 1, $p_{r+1}$ с расстоянием между вычетами $p_{r+1}-1$.
Заменим вычет 1 в основании треугольника Гильбрайта на простое число 2, при этом расстояние уменьшится до $p_{r+1}-2$. Добавим в основание треугольника простые числа 3, 5,…$p_r$, при этом расстояние уменьшится до $p_{r+1}- p_r$.
Естественно, при уменьшении данного расстояния на интервале от 0 до m ПСВm строка ИС1 не должна опуститься. Если m<2310, то как было показано выше, номер строки ИС совпадает с номером строки ИС2, поэтому положение ИС на интервале от 0 до 1, 5m не должно измениться. При больших значениях m, как было показано выше, номер строки ИС совпадает с номером строки ИС1, но максимум интервала между ПСВ, который определяет положение ИС1, находится ближе к 0,5m, поэтому положение ИС на интервале от 0 до 1, 5m также не изменится.
Учитывая, что на всех остальных интервалах nПСВ$_m$ на основании теоремы 4 номер строки ИС такой же, поэтому положение ИС и для всей последовательности совпадает с положением ИС для nПСВ$_m$ ч.т.д.
В качестве примера на рис.6 рассмотрим треугольник Гильбрайта с основанием: 2, 3, 5 и далее 3ПСВ$_{30}$:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 49 53 59 61 67 71 73 77 79 83 89 91
1 2 2 4 2 4 2 4 6 2 6 4 2 4 2 4 6 2 6 4 2 4 2 4 6 2
1 0 2 2 2 2 2 2 4 4 2 2 2 2 2 2 4 4 2 2 2 2 2 2 4
1 2 0 0 0 0 0 2 0 2 0 0 0 0 0 2 0 2 0 0 0 0 0 2
Рис.6 Треугольник Гильбрайта с основанием: 2, 3, 5 и далее 3ПСВ$_{30}$
Из рис.6 видно, что ИС, выделенная жирным шрифтом, не изменила свое расположение (сравни с рис. 5).

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

[Sonic86]

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

Заменим вычет 1 в основании треугольника Гильбрайта на простое число 2, при этом расстояние уменьшится до $p_{r+1}-2$. Добавим в основание треугольника простые числа 3, 5,…$p_r$, при этом расстояние уменьшится до $p_{r+1}- p_r$.
Естественно, при уменьшении данного расстояния на интервале от 0 до m ПСВm строка ИС1 не должна опуститься.

Насколько я понимаю, тут неявно используется утверждение:
Если треугольник абсолютных разностей, построенный на возрастающей последовательности $a_1,...,a_n$ целых чисел, имеет ИС, то треугольник, построенный на последовательности $a_1,...,a_k,b,a_{k+1},...,a_n$, где $a_k<b<a_{k+1}$, также имеет ИС.
Доказать можете? Либо сформулировать явно то, что имеется ввиду?
Кстати, это оно:

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

Думается, что про рассуждениях неявно предполагалось, что чем больше длина пробела, тем ниже находится локальная ИС для данного пробела. Это требовало уточнений тоже.

- все-таки оно потребовалось

[vicvolf]

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

Если треугольник абсолютных разностей, построенный на возрастающей последовательности $a_1,...,a_n$ целых чисел, имеет ИС, то треугольник, построенный на последовательности $a_1,...,a_k,b,a_{k+1},...,a_n$, где $a_k<b<a_{k+1}$, также имеет ИС.
Доказать можете? Либо сформулировать явно то, что имеется ввиду?

А что тут доказывать.
Над строкой ИС всегда находится строка, расстояния между элементами которой не превышают числа 2. Если добавить элемент $a_k<b<a_{k+1}$, то тем более это условие сохранится и данная строка останется ИС, если строка выше не станет ИС. Например, если $a_{k+1}-a_k=4$, $b-a_k=2$, а остальные элементы строки выше не превосходили числа 2. Таким образом, строка ИС будет существовать и по крайней мере не опустится.

-- 01.08.2012, 13:37 --

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

Кстати, это оно:

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

Думается, что про рассуждениях неявно предполагалось, что чем больше длина пробела, тем ниже находится локальная ИС для данного пробела. Это требовало уточнений тоже.

- все-таки оно потребовалось

Нет пока не потребовалось!

[Sonic86]

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

А что тут доказывать.

Да просто потому, что это неверно, даже существование ИС не сохраняется:
Берем треугольник

$$ \begin{pmatrix} 1 & 3 & 9 & 13 \\ 2 & 6 & 4 & . \\ 4 & 2 & . & . \\ 2 & . & . & . \\ \end{pmatrix} $$

и добавляем число $11$:

$$ \begin{pmatrix} 1 & 3 & 9 & 11 & 13 \\ 2 & 6 & 2 & 2 & . \\ 4 & 4 & 0 & . & . \\ 0 & 4 & . & . & . \\ 4 & . & . & . & . \\ \end{pmatrix} $$

-- Ср авг 01, 2012 11:40:24 --

На самом деле это уже было - предлагалось использовать индукцию по модулю ПСВ, что гарантирует существование ИС в левой части треугольника.

[vicvolf]

Да. согласен. Уже понял, что доказательство ошибочно, когда отослал сообщение.

[vicvolf]

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

На самом деле это уже было - предлагалось использовать индукцию по модулю ПСВ, что гарантирует существование ИС в левой части треугольника.

Да, об этом говорилось и я действительно использую индукцию для доказательства окончательной теоремы о сходимости треугольника Гильбрайта, в основании которого находится последовательность решета Эратосфена. При доказательстве этого утверждения на k+1 шаге необходимо доказать сходимость действительно на левом интервале (последовательности простых чисел, до начала ИС) решета Эратосфена и правом интервале (последовательности ПСВ). Для доказательства сходимости на левом интервале предварительно доказывается лемма о номере простого числа, с которого начинается ИС. Для доказательства сходимости на правом интервале используется теорема 4. Теорема 5 нужна была для доказательства сходимости на объединенном интервале. Ваше мнение?

[vicvolf]

Наверно так.
Лемма 2
Для простого числа - $p_$k, с которого начинается ИС в треугольнике Гильбрайта на интервале от 0 до m, где $m=2 \cdot 3…p_r$, выполняется соотношение $p_k$< $p^2_{ r+1}$.
Доказательство. Из приведенных выше примеров видно, что номер строки ИС (k) при увеличении r может, как возрастать, так и убывать.При m<2310, как было показано выше, номер строки ИС совпадает с номером строки ИС2. Максимальное возрастание 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)$ (4). В основании треугольника Гильбрайта данному k соответствует простое число $p_k$, которое на основании асимптотической формулы простых чисел [3] можно представить в виде $p_k=O(k\ln (k))$ (5). Подставляя в (5) выражение (4) получаем: $p_k=O((p_{r+1}-3) \ln ((p_{r+1}-3)))$ (6).
Учитывая, что $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))$ (7).
Величина $p^2_{r+1}=O((r+1)^2\ln ^2(r+1)) $ больше, чем $p_k=O((r+1)\ln ^2(r+1)) $(8).
При больших значениях m, как было показано выше, номер строки ИС совпадает с номером строки ИС1, но максимум интервала между ПСВ – $d_m$, который определяет положение ИС1, находится ближе к 0,5m. Максимальное возрастание k будет при следующей последовательности первых разностей треугольника Гильбрайта: …,2, $d_m$, 2, …. При этом вторая разность принимает значение $d_m-2$ и k возрастает, как $d_m-2$ (9). В основании треугольника Гильбрайта данному k соответствует простое число $p_k$. Покажем, что величина $p_k$ меньше $p^2_{r+1}$. Для этого рассмотрим последовательность $d_m$ в A048670 Online Encyclopedia Sequences (QEIS) при m=2310 и более.
При $m=2\cdot3...11=2310$ - $d_m=14$, поэтому на основании (9) $p_{12}=37< p^2_{r+1}=13^2=169$. При $m=2\cdot3...13=30030$- $d_m=22$, $p_{20}=71<p^2_{r+1}=17^2=289$. При $m=2\cdot3...17$- $d_m=26, p_24=89<p^2_{r+1}=19^2=361$ и.т.д. При $m=2\cdot3...233$- $d_m=742, p_{742}=5647<p^2_{r+1}=239^2=57121$.
Теорема 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+1}, p_{k+2},…p_n<p^2_{r+1}$, при которых согласно предположению треугольник Гильбрайта сходится.
На основании леммы 2, строка ИС треугольника Гильбрайта начинается с простого числа $p_l<p^2_{r+1}$, поэтому, начиная с этого простого числа и далее на основании теоремы 4 для последовательности вычетов nПСВ$_m$ в основании, где $m=2\cdot3…p_{k+1}$, треугольник Гильбрайта также будет сходиться.

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

[Sonic86]

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

Для простого числа - $p_$k, с которого начинается ИС в треугольнике Гильбрайта на интервале от 0 до m, где $m=2 \cdot 3…p_r$, выполняется соотношение $p_k$< $p^2_{ r+1}$.

Ааа, я не понял , как может ИС начинаться с простого числа? Простые числа у нас же в 1-й строке треугольника, а ИС - в какой-то строке ниже. Уточните, пожалуйста.

Кстати, зачем Вы пишите соотношения типа

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

$p^2_{r+1}=O((r+1)^2\ln ^2(r+1)) $

Почему не $p_{r+1}^2=O(r^2 \ln ^2 r)$? Это сильно отвлекает. И другие соотношения аналогично.

[vicvolf]

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

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

Для простого числа - $p_$k, с которого начинается ИС в треугольнике Гильбрайта на интервале от 0 до m, где $m=2 \cdot 3…p_r$, выполняется соотношение $p_k$< $p^2_{ r+1}$.

Ааа, я не понял , как может ИС начинаться с простого числа? Простые числа у нас же в 1-й строке треугольника, а ИС - в какой-то строке ниже. Уточните, пожалуйста.

Первый элемент строки ИС является одной из вершин равностороннего треугольника. Противоположную сторону данного треугольника образуют простые числа от 2 до $p_k$.
Например -
2 3 5 7 11 13 17 19 23 29 31 37 41.....
1 2 2 4 2 4 2 4 6 2 6 4.......
1 0 2 2 2 2 2 2 4 4 2......
1 2 0 0 0 0 0 2 0 2....... строка ИС
Строка ИС в этом примере начинается с числа 7.

Цитата:

Кстати, зачем Вы пишите соотношения типа

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

$p^2_{r+1}=O((r+1)^2\ln ^2(r+1)) $

Почему не $p_{r+1}^2=O(r^2 \ln ^2 r)$? Это сильно отвлекает. И другие соотношения аналогично.

Согласен, с точки зрения асимптотики это одно и тоже, но я хочу подчеркнуть соотношение r и r+1 шагов решета Эратосфена. На r+1 шаге мы остаемся по номеру простого числа в пределах r шага, т.е. $p_k<p^2_{r+1}$.

[vicvolf]

Попробуем определить асимптотику $0,5\varphi(M)=4\cdot 6....p_r-1$.
По Мертенсу (Бухштаб стр. 355) получаем:
П$(1-{p}^{-1}) \sim e^{- c}/\ln x$, где с-постоянная Эйлера, а произведение берется при p не больше x.
Преобразуем:
\sum_{p \leq x}{ln(p-1)}-\sum_{p \leq x}{ln(p)}\sim -c-ln(ln(x))
На основании интегральной формулы Чебышева:
$\sum_{p \leq x}{ln(p)} \sim x$, поэтому:
$ \sum_{p \leq x}{ln(p-1)} \sim x-c-ln(ln(x))$.
Отсюда получаем:
П$(p-1) \sim e^{-c}e^{x-ln(ln(x))}$, где произведение берется при p не больше x, а $e^{-c}=0,56$ - постоянная Мертенса.
При $x=p_r$ получаем:
П$(p_i -1) \sim 0,56e^{p_r-ln(ln(p_r))}$, где i в произведении берется от 1 до r.

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

[vorvalm]

Преобразование хорошее, но что оно дает?