Combinatorial representation of the sum of the weighted equal powers of members of an arithmetical progression

Full Text

Исходным выражением для суммы взвешенных одинаковых степеней (СВОС) членов арифметической прогрессии будем считать равенство p ξ p ν Φ (p, ν) = bι ((ι−1)+ξ)ν ; p, ν, ι ∈ N, bι = b0 , d, ξ ∈ R. (1) ι bι (ι+d) = ι=1 ι=1 Первый член, разность, количество членов арифметической прогрессии составляют здесь соответственно ξ, 1, p. Применительно к сфере шифрования достоинство использования СВОС членов арифметической прогрессии заключается в наличии дополнительно вводимого параметра ξ, который может принимать любые значения из множества R, что создает соответственно дополнительное препятствие в раскрытие шифра, формируемого на основе данной СВОС. Ниже устанавливается справедливость равенства, позволяющего выразить сумму (1), используя свободные, вида α, и весовые, вида H, компоненты СВОС: max l ν(i) c ξ j(i) Hi (p) + Hl (p) αj(i) , Φξ (p, ν) = (2) l=1 j(i)=1 184 Комбинаторное представление суммы взвешенных . . . где l = 1, . . . , max l, max l = min(p, ν), i = l − 1; j(i) = 1, . . . , max j(i), max j(i) = ν − i; Hi (p) = bl = 0 p−l k=0 p−l bi p−i−k , i 0; Hl (p) = τ =0 bl p−l−τ , причём [1, 2] max j(i−1) i αj(i) j(i) i−1 αj(i−1) Cj(i−1) , = i 1; (3) j(i−1)=j(i)+1 0: 1: 0 αj(0) = j(0) < ν, j(0) = ν. (4) Равенство (1) назовем истинным представлением рассматриваемой СВОС членов арифметической прогрессии, а равенство (2) — её гипотетическим представлением. Далее будем снабжать истинные величины индексами «и» и «l», а гипотетические величины — индексами «г» и r = t + 1. Индекс r выполняет здесь ту же роль, что и аналогичный ему индекс l в известном представлении СВОС [1, 2]. Положим сначала, что ν p, то есть max l = ν. Проводя при этом доказательство гипотетического равенства (2), будем сравнивать между собой соответствующие друг другу фрагменты из (1) и (2). Такие действия должны привести нас к благоприятным результатам выполнения указанных сравнений для случаев принятия степенями величины ξ значения j = 0 (случай с индексом 0) и совокупности значений j = 1, . . . , ν (случай с индексом 1/ν). Часть истинного комбинаторного представления СВОС [1, 2], соответствующая нулевой степени величины ξ, может быть выражена как p Φξ (ν и0 ν bι (ι − 1)ν = ξ 0 p) = ι=1 l Φp−1−l0 α0 ; (5) l=1 p−1−l bl p−1−l−τ . Φp−1−l0 = τ =0 Часть же гипотетического представления СВОС членов арифметической прогрессии, также соответствующая нулевой степени ξ, имеет вид ν Φξ (ν г0 ν−t t Hr (p)αj(t) . p) = (6) r=1 j(t)=1 Зададимся следующими равенствами, в которых отразим соотношения индексов истинного и гипотетического представлений: r = l = l(j) = t + 1. Тогда, преобразуя (6), получим ν Φξ (ν г0 p) = ν−t t αj(t) . Hl (p) l=1 (7) j(t)=1 185 А. И. Н и к о н о в Согласно выражению (3), второй сомножитель, находящийся под знаком l суммы из (7), имеет тот же вид, что и соотвествующий сомножитель α0 из (5). Располагая известным комбинаторным представлением [3] p−l l Cp−k b0 , p−k Φp−l0 = k=0 нетрудно получить следующие соотношения: p−l−1 l Cp−1−k b0 , p−k Hl (p) = k=0 p−i−1 i Cp−1−k b0 , p−k Hl−1 (p) = k=0 p−1−l l Cp−1−k b0 . p−k Φp−1−l0 = k=0 В последней из данных сумм, где сравнительно с величиной Φp−l0 взята аналогичная величина со сниженным индексным значением (p − 1 − l), в качестве сомножителей биномиальных коэффициентов оставлены именно весовые коэффициенты с большими индексами. Итак, в рамках случая j = 0 имеет место равенство Hl (p) = Φp−1−l0 , а вместе с ним и равенство друг другу величин (5) и (7): Φξ (ν г0 p) = Φξ (ν и0 p). (8) Далее исследуем случай j = 1, . . . , ν с индексом 1/ν. Части истинного комбинаторного [1, 2] и гипотетического представлений суммы (1) в данном случае выражаются таким образом: ξ1 Φξ и1/ν = Φи1/ν (ν p) + Φξ2 (ν и1/ν p) = ν−j ν−1 = ξ j=1 j j Cν p l Φp−1−l0 α0 (ν ν ι=1 = Φp−1−l0 l=0 = Φp−10 ; Φξ г1/ν b0 ; (9) ι ι=1 l=1 p b0 ι − j) + ξ ν ν−t t ξ j Ht (p)αj(t) . = (10) r=1 j(t)=1 Здесь в рамках рассматриваемого случая приняты индексные соотношения r − 1 = t = l = l(j). Поскольку min r = 1, наименьшее значение l(j) должно принимать в данном случае нулевое значение. 186 Комбинаторное представление суммы взвешенных . . . Сопоставляя (9) и (10), выделяем компоненты, первая пара которых относится к истинным, а вторая пара — к гипотетическим величинам: j l ξ j Cν Φp−1−l0 α0 (ν − j), 1 ν − 1; j (11) p ξν b0 , ι j = ν; (12) ι=1 p−t−1 t Cp−1−k b0 × p−k t ξ j Ht (p)αj(t) = ξ j k=0 t × χ (−1)t+χ Ct χν−j(t) , j(t) Cν 1 j = j(t) ν − 1; (13) χ=1 p−1 t ξ ν Ht (p)αj(t) t=0,j(t)=ν = ξν b0 , p−k j = ν. (14) k=0 При выполненном таким образом выделении компонентов, относящихся к гипотетическим величинам, с учётом принятых выше индексных соотношений нами использовалось равенство вида l l αj(l) = j(l) (−1)1+χ Clχ χν−j(l) Cν , (15) χ=1 которое обобщает ранее полученное соотношение [3]. Продолжим здесь изложение общих результатов производимого анализа случая с индексом 1/ν, а к строгому доказательству (15) в рамках настоящей мы вернемся позже. Рассматривая пределы суммирования в выражениях (9), (10), можно установить, что количество попарно сравниваемых там объектов суммирования Oи1/ν (ν p), Oг1/ν (ν p) составляет как для Φξ (ν p), так и для и1/ν Φξ (ν г1/ν p) одну и ту же величину Oи1/ν (ν p) = Oг1/ν (ν p) = 0,5ν(ν − 1) + 1. При этом из величины Oг1/ν вычитается число объектов (равное ν − 1), которым, согласно выражению (4), исходно ставятся в соответствие нулевые значения; наличие или отсутствие таких компонентов никак не сказывается на результате количественного определения рассматриваемой СВОС. Итак, поскольку наблюдается попарное совпадение друг с другом выражений (11) и (13), (12) и (14) при наличии баланса объектов суммирования, относящихся к истинным и гипотетическим величинам, действительными оказываются также следующие равенства: ν−1 ν−t ξ j Ht (p) j=1 t αj(t) = Φи1/ν (ν p), j = 1, . . . , ν − 1; j(t)=1 187 А. И. Н и к о н о в p ξ 0 H0 (p)αν = Φξ2 (ν и1/ν ν p), j = ν; ι=1 Φξ (ν г1/ν p) = Φξ (ν и1/ν p). В целом же с учётом выражения (8), наконец, имеем Φξ (ν г0 p) + Φξ (ν г1/ν p) = Φξ (ν и0 p) + Φξ (ν и1/ν p). Перейдём к рассмотрению случая p ν, в рамках которого число l ограничивается сверху значением p, а число i — значением (p − 1). Здесь сохраняется прежняя справедливость равенства друг другу истинной Φξ и гипои0 тетической Φξ сумм взвешенных степеней, определяемых как модификации г0 выражений (5) и (7), где вводятся соответствующие поправки на обозначения верхних пределов суммирования, учитывающие особенность рассматриваемого случая. Таким образом, нетрудно убедиться, что Φξ (p ν) = Φξ (p ν). и0 г0 Остаются в силе также и вышеприведённые соотношения, связанные с попарными сравнениями друг с другом выражений вида (11) и (13), (12) и (14). Уточнения требует лишь количество сравниваемых объектов суммирования. Подсчёт объектов суммирования в истинной величине Φξ (p ν), анаи1/ν логичной (9), применительно к настоящему условию p ν даёт значение Oи1/ν (p ν) = 0,5(2ν − p)(p − 1) + 1, а подсчёт объектов суммирования в величине гипотетического характера Φξ (p ν), аналогичной (10), с учётом указанного условия приводит нас к г1/ν равенству, сходному с прежним: Oг1/ν (p ν) = Oи1/ν (p ν). Как и для прежнего случая ν p, из данного результата изъяты (ν − 1) объектов суммирования, которые соответствуют нулевым свободным компонентам, указываемым выражением (4). Следовательно, и в данном случае p ν сохраняется общий баланс объектов суммирования истинного и гипотетического представления СВОС членов арифметической прогрессии. Теперь, чтобы окончательно убедиться в истинности общей гипотезы (2), остаётся доказать справедливость равенства (15) для используемых диапазонов чисел l, j(l), что будет выполнено ниже с использованием метода математической индукции. Сперва рассмотрим случай ν p и в рамках базы индукции определим l 1 параметр αj(1) = αj(1) . Согласно истинному соотношению (3), c учётом исходной системы равенств (4) данный параметр может быть представлен как [1] ν j(1) 1 αj(1) = 0 Cj(0) αj(0) . j(0)=1 188 Комбинаторное представление суммы взвешенных . . . Отсюда видно, что членам конечной последовательности (j(1)) = 0, . . ., ν − 1 j(1) 1 соответствует совокупность чисел αj(1) = Cν . Согласно же заявленному — пока гипотетическому — утверждению (15) имеем для l = 1 1 j(1) (−1)1+1 Cll 1ν Cν . 1 αj(1) = χ=1 То есть для конечной последовательности (j(1)) получена та же конечная последовательность, что и при использовании истинного соотношения (3). Следовательно, для l = 1 наше гипотетическое утверждение (15) следует обоснованно считать истинным, а при max l = 1 (ν = 1 или p = 1) — ещё и окончательным. Далее будем рассматривать случай ν p, ν > 1. Предваряя осуществление индукционного шага, найдём отношение велиl+1 l чин αj(l) и αj(l) , первоначально представляемых в заявленном гипотетическом виде: l+1 αj(l+1)=j(1) (ν) l αj(1) (ν) 0 = j(l) = j(l + 1) l l+1+χ C χ χν−j(l) χ=1 (−1) l+1 ; l l+χ C χ χν−j(l) χ=1 (−1) l ν−l−1⇒l ν − 1, l+1 ν. Как видим, число (l + 1) остаётся здесь в интервале индексов определяемых l+1 l параметров вида αj(l) , αj(l) . Доказанное ранее [3] позволяет утверждать, что ψ ψ χ (−1)ψ+χ Cψ αν−j(l) = α0 (ν − j(l)), ψ ∈ {l, l + 1}. χ=1 Но тогда l+1 αj(l) (ν) l αj(l) = l α0 (ν − j(l)) . l α0 (ν − j(l)) (16) Выявление отношения истинных значений параметров из правой части (16) оказалось возможным исходя из отношения параметров гипотетического характера из левой части (16), т.е. гипотетическое отношение определилось истинными величинами. Это позволяет облегчить завершение производимого доказательства. Теперь, непосредственно выполняя шаг индукции, положим, что утверждение (15) для случая ν p истинно. Тогда с учётом (16) параметр l+1 αj(l) = l+1 l αj(l) α0 (ν − j(l)) l α0 (ν − j(l)) , l занимающий следующую за l позицию в последовательности αj(l) (v) с фиксированным значением j(l), должен полагаться истинным, а данный индукционный шаг — уже законченным. 189 А. И. Н и к о н о в Для случая p ν (max l = p) все вышеприведённые соотношения, касающегося базы индукции, получения частного (16), выполнения шага индукции, остаются в силе. Имеем также 0 ν−l−1 j(l) = j(l + 1) ⇒ l ν − 1, l+1 ν, однако более сильные ограничения, накладываемые на l, l + 1, могут быть представлены в виде p ν: l p − 1, l+1 p. Как и прежде, число (l + 1) остаётся в интервале индексов определяемых величин. На этом доказательство справедливости равенства (15), а вместе с тем и доказательство истинности общей гипотезы (2) можно считать завершённым. l В заключение укажем на одну особенность набора величин αj(l) (ν), l + j(l) = ν, которые представляют собой, с одной стороны, согласно выражеj(l) нию (15), произведения сумм компонентов (−1)l+χ Clχ χl и Cν , а с другой — размещения из ν элементов по l [4], то есть l αj(l) (ν) = Al = ν ν! , (ν − l)! l + j(l) = ν. Итак, убывающий факториал Al может быть представлен здесь именно ν как сумма компонентов, входящих в выражение (15).

About the authors

Alexander I Nikonov

Samara State Technical University

Email: nikonovai@mail.ru
(Dr. Techn. Sci.), Professor, Dept. of Electronic Systems and Information Security 244, Molodogvardeyskaya st., Samara, 443100, Russia

References

Supplementary files