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

[vicvolf]

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

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

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

Так. Если я правильно помню, здесь в основании треугольника лежит последовательность $\{2;3;...;p_r\}\cup\text{ПСВ}_m$.

Да, именно так.

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

Непонятно. У нас $k=k(r)$, $k$ не зависит больше ни от чего, в т.ч. не зависит и от неких разностей (я догадываюсь, что Вы сказать хотели, но хочу точной формулировки).

Надо по-другому сформулировать. Положение ИС. а следовательно величина k, определяется разностями треугольника Гильбрайта: $2, p_{r+1}-1, 2, p_{r+1}-1, 2$.

[vicvolf]

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

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

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

Цитата:

Так. Если я правильно помню, здесь в основании треугольника лежит последовательность $\{2;3;...;p_r\}\cup\text{ПСВ}_m$.

Да, и я еще добавлю, что если к ПСВ(m) добавить $2;3;...;p_r$, то номер строки ИС, а следовательно $p_k$ не возрастет по сравнению со случаем, когда в основании только ПСВ(m).
Возьмем ПСВ(210):
1 11 13 17 19 23 29 31 37 41
10 2 4 2 4 6 2 6 4
8 2 2 2 2 4 4 2
6 0 0 0 2 0 2
6 0 0 2 2 2
6 0 2 0 0
6 2 2 0
4 0 2
4 2
2
ИС в 8 строке разностей $p_k=41$

Теперь возьмем соответствующее решето Эратосфена:
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

ИС в 3 строке разностей $p_k=13$

[Sonic86]

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

Надо по-другому сформулировать. Положение ИС, а следовательно величина k, определяется разностями треугольника Гильбрайта: $2, p_{r+1}-1, 2, p_{r+1}-1, 2$.

Ну вот, я не об этом думал...
Тогда все равно непонятно. У нас $k=k(r)$, из пятерки $(2, p_{r+1}-1, 2, p_{r+1}-1, 2)$ выделяем 2-ю компоненту, прибавляем к ней $1$ - получаем $p_{r+1}$, вычисляем $\pi(p_{r+1})$ и вычитаем $1$ - получаем $r$. Т.е. $(\exists F)k=F(2, p_{r+1}-1, 2, p_{r+1}-1, 2)$. Но это тривиально, вряд ли отсюда что-то следует.
Т.е. надо указать какой-то алгоритм для вычисления $k$, отличный от описанного.

[vicvolf]

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

Т.е. надо указать какой-то алгоритм для вычисления $k$, отличный от описанного.

Здесь никакой алгоритм не нужен. Вариантов для m<2310 немного, их можно все перебрать и определить положение ИС и $p_k$.
Для m=2 ИC находится в первой строке разностей треугольника Гильбрайта и $p_k=3$.
Для m=6 ИС находится во второй строке треугольника Гильбрайта и $p_k=7<3^2$.
Для m=30 ИС1 находится в 2-ой строке разностей треугольника Гильбрайта, а ИС2 – в 3-ей строке разностей. Следовательно, ИС находится в 3-ей строке разностей треугольника Гильбрайта и $p_k=13<7^2$.
При $m=210=2 \cdot3...7$ ИС1 находится в 9-ой строке разностей треугольника Гильбрайта, а ИС2 – в 15-ой строке разностей. Следовательно, ИС находится в 15-ой строке разностей треугольника Гильбрайта $p_k=67<13^2$.

[Sonic86]

Часа два думал, все равно не понимаю.

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

Положение ИС, а следовательно величина k, определяется разностями треугольника Гильбрайта: $2, p_{r+1}-1, 2, p_{r+1}-1, 2.$

Вот возьмем число $0$ или $2$, лежащее в строке с максимальным номером (в вершине треугольника). Определим фигуру $F$, являющуюся подмножеством треугольника так:
1) число $0$ или $2$ из максимальной строки лежит в $F$.
2) если $x\in F$ и $y$ смежно с $x$ и $y\in\{0;2\}$, то $y\in F$. (что такое смежно, думаю, понятно)
Проще говоря - $F$, это связный кусок треугольника Гилбрайта, состоящий только из $0$ и $2$, основанный на вершине треугольника. Рассмотрим дополнение $\bar{F}$. В нем можно выделить несколько вершин, направленных вниз (не буду формальное определение писать - длинно будет). Для каждой такой вершины $j$ в $\bar{F}$ можно определить $\text{ИС}_j$. И тогда $\text{ИС}=\max_j\{\text{ИС}_j\}$.
Вот тут:

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

Положение ИС. а следовательно величина k, определяется разностями треугольника Гильбрайта: $2, p_{r+1}-1, 2, p_{r+1}-1, 2.$

Вы хотите сказать, что максимальная ИС среди всех $\text{ИС}_j$ лежит "под" подпоследовательностью $2, p_{r+1}-1, 2, p_{r+1}-1, 2$? Если да, то это не очевидно - это доказывать надо, доказательства я не вижу.

[vicvolf]

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

Часа два думал, все равно не понимаю.

Спасибо!

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

Положение ИС, а следовательно величина k, определяется разностями треугольника Гильбрайта: $2, p_{r+1}-1, 2, p_{r+1}-1, 2.$

Цитата:

Вот возьмем число $0$ или $2$, лежащее в строке с максимальным номером (в вершине треугольника). Определим фигуру $F$, являющуюся подмножеством треугольника так:
1) число $0$ или $2$ из максимальной строки лежит в $F$.
2) если $x\in F$ и $y$ смежно с $x$ и $y\in\{0;2\}$, то $y\in F$. (что такое смежно, думаю, понятно)
Проще говоря - $F$, это связный кусок треугольника Гилбрайта, состоящий только из $0$ и $2$, основанный на вершине треугольника. Рассмотрим дополнение $\bar{F}$. В нем можно выделить несколько вершин, направленных вниз (не буду формальное определение писать - длинно будет). Для каждой такой вершины $j$ в $\bar{F}$ можно определить $\text{ИС}_j$. И тогда $\text{ИС}=\max_j\{\text{ИС}_j\}$.

Можно конечно сделать доказательство, но не стоит, так как рассматривается только случай m<2310. Поэтому достаточно рассмотреть варианты, указанные мною в предыдущем сообщении.

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

Положение ИС. а следовательно величина k, определяется разностями треугольника Гильбрайта: $2, p_{r+1}-1, 2, p_{r+1}-1, 2.$

Цитата:

Вы хотите сказать, что максимальная ИС среди всех $\text{ИС}_j$ лежит "под" подпоследовательностью $2, p_{r+1}-1, 2, p_{r+1}-1, 2$? Если да, то это не очевидно - это доказывать надо, доказательства я не вижу.

Это основано на исследовании вариантов с m<2310, поэтому доказывать не надо. Давайте пойдем по доказательству леммы дальше.

[Sonic86]

А, ну так надо так сразу и формулировать :
Гипотеза: предполагаем, что $\max\limits_j\text{ИС}_j$ лежит под подпоследовательностью $(2, p_{r+1}-1, 2, p_{r+1}-1, 2)$.
И далее мы рассматриваем только те $m=m(r)$, для которых это верно. В частности, это верно при $r\leqslant 4$.
А Вы далее $r=4$ считали? Можно программулину написать - посмотреть, что там.

Дальше...

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

k возрастает пропорционально $p_{r+1}-3$, т.е. $k=O(p_{r+1}-3)$ (4)

А это откуда следует? Вроде уже обсуждали, что в этот вопрос упремся.

[vorvalm]

При $r=5$ нет
$(2,p_{r+1}-1,2,p_{r+1}-1,2)$
но есть
$(4,p_{r+1}-1,2,p_{r+1}-1,4)$ и
$(4,2p_{r-1},4)$

[vicvolf]

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

А Вы далее $r=4$ считали? Можно программулину написать - посмотреть, что там.

Конечно считал.
При $m=2310=2 \cdot...11$ ИС1 находится в 10-ой строке треугольника Гильбрайта, а ИС2 – в 9-ой строке разностей. Следовательно, ИС находится в 10-ой строке разностей треугольника Гильбрайта. Такое положение ИС1 определяется максимальным расстоянием между вычетами 113 и 127 и соответственно последовательностью первых разностей: ...4, 14, 4..., где $(14=2p_{r-1})$ .
При m=2310, номер строки ИС1 больше, чем номер строки ИС2.
При увеличении значения m данная тенденция - номер строки ИС1 больше номера строки ИС2 сохраняется. Это связано с тем, что максимум расстояния между вычетами теперь находится на интервале от 0 до m.
Например, для $m=30030=2 \cdot...13$ максимум первых разностей уже находится между вычетами 9439 и 9461 и определяется строкой первых разностей: …2,22,2….$(22=2p_{r-1})$ (имеется также симметричное значение относительно 0,5m). При m=30030 ИС1 находится в 21 строке разностей треугольника Гильбрайта, а ИС2 – в 15 строке разностей. Следовательно, ИС находится в 21-ой строке разностей треугольника Гильбрайта.

Продолжение доказательства леммы.
При m>210, как было показано выше, номер строки ИС совпадает с номером строки ИС1, т.е. максимум интервала между ПСВ – dm, который определяет положение ИС1, находится теперь на интервале от 0 до m. Как было показано, максимальное возрастание k будет при следующей последовательности первых разностей треугольника Гильбрайта: …,2, dm, 2, …. При этом вторая разность принимает значение dm-2 и k возрастает, как dm-2 (9). В основании треугольника Гильбрайта данному k соответствует простое число $p_k$. Покажем, что величина $p_k$ меньше $p^2_{r+1}$. Для этого рассмотрим последовательность dm в A048670 Online Encyclopedia Sequences (QEIS) при m≥2310.
При $m=2 \cdot...11=2310$ - dm=14, поэтому на основании (9) $p_{12}=37< p^2_{r+1}=13^2=169$. При $m=2 \cdot...13=30030$ - dm =22, $p_{20}=71< p^2_{r+1}=17^2=289$. При $m=2 \cdot...17$ - dm=26, $p_{24}=89<p^2_{r+1}=19^2=361$ и.т.д. При $m=2 \cdot...233$ - dm=742, $p_{740}=5639< p^2_{r+1}=239^2=57121$.

[Sonic86]

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

При m>210, как было показано выше, номер строки ИС совпадает с номером строки ИС1

Это нигде вроде не показано это просто правдоподобное положение, основанное на опытных данных. Мы пока лишь знаем, что скорее всего (но тоже доказательства нет), что максимальный пробел между двумя последовательными числами из $\text{ПСВ}_m$ больше пробела "в начале" $\text{ПСВ}$. У нас также нет доказательства, что из второго следует первое. Скорее всего последнее и верно, но его надо доказывать.

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

Как было показано, максимальное возрастание k будет при следующей последовательности первых разностей треугольника Гильбрайта: …,2, dm, 2, ….

И где это показано? Я не видел
Кстати

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

…,2, dm, 2, …

А почему именно так? А $(2,d_m,4)$ не бывает?

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

максимальное возрастание k

т.е. прямо $\text{ИС}_{r+1,2}-\text{ИС}_{r,2}=\max\limits_j\text{ИС}_{r+1,j}-\text{ИС}_{r,j}$? (здесь $\text{ИС}_{r,2}$ - это локальный $\text{ИС}$ именно для максимального пробела между двумя последовательными числами из $\text{ПСВ}_{m(r)}$)

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

Для этого рассмотрим последовательность dm в A048670 Online Encyclopedia Sequences (QEIS) при m≥2310.

Это только для $p_r\leqslant 233$.

[vicvolf]

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

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

При m>210, как было показано выше, номер строки ИС совпадает с номером строки ИС1

Это нигде вроде не показано это просто правдоподобное положение, основанное на опытных данных. Мы пока лишь знаем, что скорее всего (но тоже доказательства нет), что максимальный пробел между двумя последовательными числами из $\text{ПСВ}_m$ больше пробела "в начале" $\text{ПСВ}$. У нас также нет доказательства, что из второго следует первое. Скорее всего последнее и верно, но его надо доказывать.

Это можно доказать, но в принципе не требуется и можно убрать из доказательства. Важна величина dm и разностей рядом.

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

Как было показано, максимальное возрастание k будет при следующей последовательности первых разностей треугольника Гильбрайта: …,2, dm, 2, ….

Цитата:

И где это показано? Я не видел

Это связано с тем, что dm-2 > dm-4, поэтому разность dm-2 более критична и при ней строка ИС расположена ниже, чем при dm-4. Например, при m=210 при разностях …,2, dm, 2, …получаем ИС в 15 строке разностей, а при большем m=2310 при разностях …,4, dm, 4, ИС находится только в 10 строке разностей. Конечно, сочетание разностей...0, dm, 0, …было бы еще более критичным, но такого быть не может. Поэтому максимальный номер строки ИС определяется разностью dm-2. Соответственно, разностью dm-2 определяется максимально возможный номер k в p_k.

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

Для этого рассмотрим последовательность dm в A048670 Online Encyclopedia Sequences (QEIS) при m≥2310.

Цитата:

Это только для $p_r\leqslant 233$.

А дальше рост dm пропорционален росту $p_r$. До $m=2 \cdot...67$ - $dm<2p_r$. До $m=2 \cdot...179$ - $dm<3p_r$ и. т.д., т.е dm растет не более чем линейно. Соответственно, не более чем линейно, как dm-2 растет номер k в $p_k$, а $p^2_r$ растет как квадрат, поэтому выполняется неравенство $p_k<p^2_r$.

[Sonic86]

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

Это связано с тем, что dm-2 > dm-4, поэтому разность dm-2 более критична и при ней строка ИС расположена ниже, чем при dm-4.

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

И где это показано? Я не видел

И я опять же повторяю: у нас нет доказательство того, что "чем больше пробел, тем больше ИС". Нету и все.

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

До $m=2 \cdot...67$ - $dm<2p_r$. До $m=2 \cdot...179$ - $dm<3p_r$ и. т.д., т.е dm растет не более чем линейно.

Это называется популярная индукция: $P(x_1)\wedge...\wedge P(x_k)\to (\forall x)P(x)$. Это правило вывода неверно.

[vicvolf]

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

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

Это связано с тем, что dm-2 > dm-4, поэтому разность dm-2 более критична и при ней строка ИС расположена ниже, чем при dm-4.

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

И где это показано? Я не видел

И я опять же повторяю: у нас нет доказательство того, что "чем больше пробел, тем больше ИС". Нету и все.

Я не утверждаю, что чем больше dm тем ниже ИС. Я говорю, что важно соотношение dm и рядом стоящих первых разностей. Если рядом с разностью dm стоит также разность dm, то вторая разность под ними будет 0, но тут возникает вопрос, какие разности стоят с ними рядом. Если опять dm с обеих сторон, то под ними будут с обеих сторон вторые разности 0 и.т.д. Таким образом в этом случае ИС будет находится во 2-ой строке. Но так быть не может, так как рядом стоящие вычеты не повторяютя. Поэтому рядом с dm буде стоять отличная разность. Предположим dm-2, тогда под ними вторая разность будет 2. Если рядом с разностью dm-2 будет стоять разность dm-4, то под ними будет вторая разность опять 2. Может быть рядом с dm-4 разность dm-2, то под ними вторая разность тоже будет 2 и.т.д. Таким образом, если первые разности отличаются на 2 (на минимальную величину), то вторые разности будут 2 и следовательно, ИС будет во второй строке. Допустим рядом с dm стоит разность dm-4, то во второй строке стоит 4 и ИС уже не будет находится во 2-ой строке, а как минимум в третьей. Таким образом при увеличении расстояния между первыми разностями номер строки с ИС увеличился и.т.д.

Возможно более короткое доказательство от противного.
Предположим, что строка ИС находилась во 2-ой строке, т.е расстояние между рядом стоящими разностями не превышало 2. Предположим, что расстояние между какими-то двумя разностями увеличилось с 2 до n (n>2), но номер строки ИС не увеличился. Но в этом случае во 2-ой строке будет стоять число не менее 4 и следовательно ИС будет находиться, как минимум, в 3-ей строке, т.е номер строки ИС увеличился и мы пришли к противоречию.

[vicvolf]

Можно обобщить последнее доказательство от противного на случай, если ИС находится в k-ой строке.

[Sonic86]

Я вот 1-й абзац 3-4 раза прочел. Рассуждения есть, а утверждения нету Только это:

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

Таким образом при увеличении расстояния между первыми разностями номер строки с ИС увеличился и.т.д.

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

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

Возможно более короткое доказательство от противного.

Прочел. Верно только при $\text{ИС}=2$.

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

Можно обобщить последнее доказательство от противного на случай, если ИС находится в k-ой строке.

давайте.