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

[Sonic86]

Блин

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

$dm=p_n-p_{n-1}$

я вот это условие проморгал.
Тогда так: берем последовательность $1;3;7;17;27;43;67$, для нее правый край $24;8;2;4;4;2$, $I=6$, а для $1;3;7;17;27;43;69$ правый край $26;10;4;2;2;0$ (3-й элемент стал больше) и $I=4<6$. Так что

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

Лемма
... тогда с ростом dm растет номер строки индикатора сходимости (НСИС).

вообще неверна: $dm$ изменилось с $24$ до $26$, а $I$ упал с $6$ до $2$.

[vicvolf]

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

Блин

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

$dm=p_n-p_{n-1}$

я вот это условие проморгал.
Тогда так: берем последовательность $1;3;7;17;27;43;67$, для нее правый край $24;8;2;4;4;2$, $I=6$, а для $1;3;7;17;27;43;69$ правый край $26;10;4;2;2;0$ (3-й элемент стал больше) и $I=4<6$

Так и знал, что если не прошел пример на отрицательную разность в первой строке, то последует пример на отрицательную разность в строке ниже. Но котрпример не совсем удачен, так как исходный треугольник расходится.
1 3 7 17 27 43 67
2 4 10 10 16 24
2 6 0 6 8
4 6 6 2
2 0 4
2 4
2
Условие сходимости исходного треугольника надо включить в условие леммы.
Если сделать исходный треугольник сходящимся:
1 3 7 15 23 37 61
2 4 8 8 14 24
2 4 0 6 10
2 4 6 4
2 2 2
НСИС=4
и добавить 2:
1 3 7 15 23 37 63
2 4 8 8 14 26
2 4 0 6 12
2 4 6 6
2 2 0
НСИС=4
При наличии отрицательной разности номер НСИС не строго возрастает и поэтому тем более меньше dm.

[Sonic86]

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

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

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

Условие сходимости исходного треугольника надо включить в условие леммы.

Очевидно, что это бесполезно. Допишите тогда к последовательности $1;3;7;17;27;43;67$ член $-1$: для последовательности $-1;1;3;7;17;27;43;67$ получите все то же самое, но со сходящимся треугольником.

[vicvolf]

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

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

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

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

Условие сходимости исходного треугольника надо включить в условие леммы.

Очевидно, что это бесполезно. Допишите тогда к последовательности $1;3;7;17;27;43;67$ член $-1$: для последовательности $-1;1;3;7;17;27;43;67$ получите все то же самое, но со сходящимся треугольником.

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

[vicvolf]

Согласен. В лемме необходимо добавить условие, что под $p_n$ находятся только положительные разности. я действительно рассматривал реальные dm в ПСВ и там находятся только положительные разности.

Вот, например, треугольник Гильбрайта для ПСВ(30030):

9367
9371 4
9377 6 2
9379 2 4 2
9389 10 8 4 2
9391 2 8 0 4 2
9397 6 4 4 4 0 2
9403 6 0 4 0 4 4 2
9407 4 2 2 2 2 2 2 0
9409 2 2 0 2 0 2 0 2 2
9413 4 2 0 0 2 2 0 0 2 0
9419 6 2 0 0 0 2 0 0 0 2 2
9421 2 4 2 2 2 2 0 0 0 0 2 0
9431 10 8 4 2 0 2 0 0 0 0 0 2 2
9433 2 8 0 4 2 2 0 0 0 0 0 0 2 0
9437 4 2 6 6 2 0 2 2 2 2 2 2 2 0 0
9439 2 2 0 6 0 2 2 0 2 0 2 0 2 0 0 0
9461 22 20 18 18 12 12 10 8 8 6 6 4 4 2 2 2 2

имеет разности между 9439 и 9461 (dm=22) только положительные, т.е идет возрастание по всем разностям при переходе от колонки под вычетом 9439 к колонке под вычетом 9461- они выделены жирным шрифтом.

[vicvolf]

Вношу исправления в лемму.
Лемма
Пусть в основании треугольника Гильбрайта находится строго возрастающая последовательность нечетных чисел с возможными пропусками: $p_1,p_2,...p_{n-1},p_n.$ и $dm=p_n-p_{n-1}$, предположим также, что все разности, находящиеся под dm строки ИС положительны. Тогда с ростом dm растет номер строки индикатора сходимости (НСИС).
Доказательство
Проведем доказательство методом математической индукции.
Пусть НСИС=1, тогда по определению строки индикатора сходимости все элементы в первой строке разностей треугольника Гильбрайта не превышают 2. Так как последовательность нечетных чисел в основании треугольника Гильбрайта строго возрастающая, то в первой строке разностей нет нулевых элементов, т.е все $a_{1j}=2$, где $j=1,...n.$
Следовательно, в данном случае $dm=p_n-p_{n-1}=2$. Увеличим $p_n$ на 2, т.е $p'_n=p_n+2$. Тогда $dm=p'_n-p_{n-1}=4$ и НСИС станет больше 1, так как первая строка будет содержать 4 и будет не соответствовать определению строки индикатора сходимости.
Пусть НСИС=k. Увеличим $p_n$ на 2, т.е $p'_n=p_n+2$. Тогда все элементы треугольника Гильбрайта, находящиеся под $p_{n-1}$ $(a_{1,n-1}, ....a_{n-1,n-1})$ останутся без изменения. По условию $dm= p_n-p_{n-1}$ все разности $a_{1,n-1}-a_{1,n-2}\geq 0$, $a_{2,n-1}-a_{2,n-2}\geq 0$,.... Поэтому все элементы треугольника Гильбрайта, находящиеся под $p'_{n}$ $(a_{1,n}, ....a_{n,n})$ увеличатся на 2, поэтому разность $|a_{i,n}-a_{i,n-1}|$ также увеличится на 2. Поэтому , если в k-ой элемент $a_{k,n}$ был равен 2 (больше он не может быть по определению строки индикатора сходимости), то он станет равным 4 и НСИС станет больше k. Обратим внимание, что элемент $a_{k,n}$ не мог быть равным 0, т.к. в этом случае над ним должны были находиться две 4, но тогда НСИС не был бы ранее равен k.
Итак мы доказали, что НСИС увеличился, но на сколько?
Если в k+1 строке элемент под $p_{n-1}$, который не менялся, $a_{k+1,n-1}=2$, то НСИС=k+1.
Если в k+1 строке элемент под $p_{n-1}$, который не менялся, $a_{k+1,n-1}=0$, то НСИС=k+2.

[Sonic86]

Так, я последнее сообщение пока не читал.
Пока про это:

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

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

Я вот такой менее тривиальный пример нашел: берем последовательность $2;2;...;2;2n;2n;...;2n$ ($n>1$, число двоек и $2n$-ок произвольно). Для нее $dm=2n$. Однако варьируя число двоек и $2n$-ок можно получать как сходящиеся треугольники, так и расходящиеся, причем для сходящихся ИС прыгает туда-сюда экспоненциально. Т.е. ИС от $dm$ здесь не зависит. Обратно, можно фиксировать треугольник (а значит фиксируется ИС), но при варьировании $n$ $dm$ вырьируется как угодно. Т.е. в общем $dm$ от ИС тоже не зависит.
Дописывая сверху строки, сохраняя свойство треугольника Гилбрайта, получаем еще менее тривиальный пример.
Т.е. для использования связи между $dm$ и ИС надо какие-то существенные условия добавлять. Какие - не знаю.

-- Вс окт 28, 2012 17:59:26 --

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

Лемма
Пусть в основании треугольника Гильбрайта находится строго возрастающая последовательность нечетных чисел с возможными пропусками: $p_1,p_2,...p_{n-1},p_n.$ и $dm=p_n-p_{n-1}$, предположим также, что все разности, находящиеся под dm строки ИС положительны. Тогда с ростом dm растет номер строки индикатора сходимости (НСИС).

Пусть даже верно. Как ее использовать, если лемма не общая (т.е. для треугольников с отрицательными разностями)?

[vicvolf]

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

Пусть даже верно.

Не пусть, а верно. В последнем сообщении доказательство.

Цитата:

Как ее использовать, если лемма не общая (т.е. для треугольников с отрицательными разностями)?

Лемма справедлива для ПСВ. Я это могу доказать.

[Sonic86]

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

Лемма справедлива для ПСВ. Я это могу доказать.

А как применять лемму к треугольнику Гилбрайта, построенном на ПСВ, если в этом треугольнике есть отрицательные разности?

[vicvolf]

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

А как применять лемму к треугольнику Гилбрайта, построенном на ПСВ, если в этом треугольнике есть отрицательные разности?

Под dm отрицательных разностей выше строки ИС нет, есть только положительные.

[vicvolf]

Рассмотрим контрпример:
3 5 7 11 21 31 47 71
2 2 4 10 10 16 24
0 2 6 0 6 8
2 4 6 6 2
2 2 0 4
0 2 4
2 2
НСИС=6.
Обратим внимание, что разности в 10-ой строке соизмеримы по величине (они выделены жирным шрифтом), отсюда получаются такие разности во 2-ой строке и в результате в 3-ей строке отрицательная разность.
Если уменьшить первые разности, чтобы dm стала с ними соизмерима:
3 5 7 11 21 31 41 47 71
2 2 4 10 10 10 6 24
0 2 6 0 0 4 18
2 4 6 0 4 14
2 2 6 4 10
0 4 2 6
4 2 4
2 2
Все выделенные жирным шрифтом разности станут положительны и лемму можно применить.

Докажем, что в ПСВ(m) под dm до строки ИС все разности положительны.

Для dm в ПСВ(m) выполняется соотношение - $dm \geq p_{r+1}-1$.
Рассмотрим случай $dm = p_{r+1}-1$.
Рядом с dm находятся разности:$ ...., p_{r+i} -p_{r+i-1}, ...,p_{r+3}-p_{r+2}, p_{r+2}-p_{r+1}, dm=p_{r+1}-1.$
Разность dm образуеися, как результат пропуска простых чисел от 2 до $p_r$, а разности рядом являются разностями рядом стоящих вычетов. Самым критичным является случай когда разница между dm и остальными первыми разностями минимальна. Это достигается при r=1.
Действительно, в этом случае, все разности равны, так как $p_{r+1}-1=p_{2}-1=3-1=2$. Это соответствует ПСВ(2).
Проверим ПСВ(2):
1 3 5 7 9 11 ....
2 2 2 2 2 .....
все разности положительны.
Следовательно для больших значений dm тем более все разности положительны.

Пример ПСВ(2510):

163 167 169 173 179 181 187 191 193 197 199 209
4 2 4 6 2 6 4 2 4 2 10
2 2 2 4 4 2 2 2 2 8
0 0 2 0 2 2 0 0 6
0 2 2 2 0 2 0 6
2 0 0 2 2 2 6
2 0 2 0 0 4
2 2 2 0 4
0 0 2 4
0 2 2
Все разности, которые находятся под dm выше строки ИС положительны. Они выделенны жирным шрифтом. Другой пример для ПСВ(30030) был приведен ранее.

[Sonic86]

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

Докажем, что в ПСВ(m) под dm до строки ИС все разности положительны.
...
все разности положительны.
Следовательно для больших значений dm тем более все разности положительны.

А куда делся случай $dm>p_{r+1}-1$?

Вообще, тут длинный кусок уже собирается. Надо его целиком охватить как-то...

-- Пн окт 29, 2012 17:31:24 --

Ладно. Мы проверяем это (не помню уж, почему):

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

Лемма
Пусть в основании треугольника Гильбрайта находится строго возрастающая последовательность нечетных чисел с возможными пропусками: $p_1,p_2,...p_{n-1},p_n.$ и $dm=p_n-p_{n-1}$, предположим также, что все разности, находящиеся под dm строки ИС положительны. Тогда с ростом dm растет номер строки индикатора сходимости (НСИС).

сначала я ее переформулирую, ибо

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

Тогда с ростом dm растет номер строки индикатора сходимости (НСИС).

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

Лемма. Рассмотрим 2 треугольника Гилбрайта $T_1, T_2$, пусть $T_1$ построен на некоторой последовательности нечетных чисел $p_1,...,p_{n-1},p_n$, а $T_2$ построен на последовательности нечетных чисел $p_1,...,p_{n-1},p'_n$, где $p_n'=p_n+2$. Пусть $\max (p_{j+1}-p_j)=p_{n+1}-p_n$, обозначим этот максимум $dm$. И пусть все разности под последним членом последовательности в $T_1$ положительны. Тогда $I(T_1)\leqslant I(T_2)$ (а не $I(T_1)<I(T_2)$, о чем узнаете ниже).

(Оффтоп)

(кстати, фразы типа "треугольник $T_1$ построен на последовательности $a_1,...,a_n$" можно обозначать $T_1=T(a_1,...,a_n)$ - так короче и понятнее)

В таком случае лемма верна, только доказательство производится не методом матиндукции (потому что индуктивная посылка вообще не используется), а просто тупо в лоб: пусть $I(T_1)=k$, тогда ... - все что во 2-й части написано.
Исключая:

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

Обратим внимание, что элемент $a_{k,n}$ не мог быть равным 0

Это неверно: достаточно взять $p_1;p_2;p_3=1;5;9$. И в данном случае видим, что $I(T_1)=I(T_2)=3$, потому следует, например, ослабить $I(T_1)<I(T_2)$ до $I(T_1)\leqslant I(T_2)$.

Попробуйте из кусков что-то цельное собрать хотя бы кратко. Мне неохота.

[vicvolf]

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

куда делся случай $dm>p_{r+1}-1$?

Этот случай можно сравнить со случаем $dm=p_{r+1}-1$, для которого все разности положительны. Если dm больше, то тем более это выполняется.

Цитата:

Вообще, тут длинный кусок уже собирается. Надо его целиком охватить как-то...

Новая лемма будет отдельно, а это войдет в старую лемму 2, в которой будет ссылка на новую.

[vicvolf]

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

Лемма. Рассмотрим 2 треугольника Гилбрайта $T_1, T_2$, пусть $T_1$ построен на некоторой последовательности нечетных чисел $p_1,...,p_{n-1},p_n$, а $T_2$ построен на последовательности нечетных чисел $p_1,...,p_{n-1},p'_n$, где $p_n'=p_n+2$. Пусть $\max (p_{j+1}-p_j)=p_{n+1}-p_n$, обозначим этот максимум $dm$. И пусть все разности под последним членом последовательности в $T_1$ положительны. Тогда $I(T_1)\leqslant I(T_2)$.

Спасибо!
Лемма. Рассмотрим 2 треугольника Гилбрайта $T_1, T_2$, пусть $T_1$ построен на строго возрастающей последовательности нечетных чисел с возможными пропусками $p_1,...,p_{n-1},p_n$, а $T_2$ построен на последовательности нечетных чисел $p_1,...,p_{n-1},p'_n$, где $p_n'=p_n+2$. Пусть $\max (p_{j+1}-p_j)=p_{n+1}-p_n$, обозначим этот максимум $dm$. И пусть все разности под dm в $T_1$ положительны. Тогда $I(T_1)\leqslant I(T_2)$, где I(T) - номер строки ИС треугольника Гильбрайта Т.
Доказательство
Пусть $I(T_1)=k.$ Увеличим $p_n$ на 2, т.е $p'_n=p_n+2$. Тогда все элементы треугольника Гильбрайта, находящиеся под $p_{n-1}$ $(a_{1,n-1}, ....a_{n-1,n-1})$ останутся без изменения. По условию $dm= p_n-p_{n-1}$ все разности $a_{1,n-1}-a_{1,n-2}\geq 0$, $a_{2,n-1}-a_{2,n-2}\geq 0$,.... Поэтому все элементы треугольника Гильбрайта, находящиеся под $p'_{n}$ $(a_{1,n}, ....a_{n,n})$ увеличатся на 2, поэтому разность $|a_{i,n}-a_{i,n-1}|$ также увеличится на 2. Поэтому , если в k-ой элемент $a_{k,n}$ был равен 2 (больше он не может быть по определению строки индикатора сходимости), то он станет равным 4 и $I(T_2)$ станет больше k. Обратим внимание, что если элемент $a_{k,n}$ равен 0, тогда $I(T_2)=k$.
Если элемент $a_{k,n}$ не равен 0, то:
если в k+1 строке элемент под $p_{n-1}$, который не менялся, $a_{k+1,n-1}=2$, то $I(T_2)=k+1$.
если в k+1 строке элемент под $p_{n-1}$, который не менялся, $a_{k+1,n-1}=0$, то $I(T_2)=k+2$.

[vicvolf]

Следствие 1
Если все элементы треугольника гильбрайта T: $a_{l,n-1}=0$ при l>k+1 , то $I(T)$ равен бесконечности, т.е. треугольник Гильбрайта расходится.
Это еще раз подтверждает правильность выбранного термина - сходимость треугольника Гильбрайта. Треугольник Гильбрайта также будет расходиться при не выполнении признака сходимости треугольника Гильбрайта (см. признак сходимости треугольника Гильбрайта в начале темы).
Следствие 2
Если в треугольнике Гильбрайта T существует ИС, то $I(T)< dm$.
Это следует из того, что при увеличении dm на 2 $I(T)$ максимально увеличивается также на 2, а при dm=2 $I(T)=1$, если в полученном треугольнике существует ИС.