способов выбора j и к для мини-шагов: выбираем t различных пар (ji, fci),..., (jt, kt) индексов в диапазоне О < fc/i < j/, < г меньшим числом способов, которые заданы в (33). Затем для каждого мини-шага г используем пару индексов {jh, кн), такую, что

a) Jh < г;

b) uj +akh принимает наименьшее возможное значение среди еще неиспользованных для меньших мини-пгагов г пар;

c) щ = uj + o,kh удовлетворяет определению мини-шага.

Если таких пар {jh, kh) не существует, аддитивная цепочка не будет получена; с другой стороны, любая аддитивная цепочка с мини-шагами на назначенных местах должна быть выбрана одним из этих способов, так что (33) представляет собой верхнюю границу имеющихся возможностей.

Таким образом, общее количество возможных аддитивных цепочек, удовлетворяющих (26), ограничено сверху величиной (31), умноженной на (32) и на (33), которая просуммирована по всем подходящим s, t, и и v. Доказательство теоремы Е теперь может быть завершено стандартными оценками этих функций (см. упр. 18).

Следствие. Величина 1{п) асимптотически равна А(п) + А(п)/АА(п) для почти всех п. Более строго говоря, существует функция f{n), такая, что f{n) -+ О при

П - 00 и

Рг(\1{п) - А(п) - А(п)/АА(п) > /(n)A(n)/AA(n)) = 0. (34)

(См. определение вероятности "Рг" в разделе 3.5.)

Доказательство. Верхняя граница (25) показывает, что (34) вьшолняется без знаков абсолютного значения. Нижняя граница вытекает из теоремы Е, если положить следующее: /(п) уменьшается до нуля достаточно медленно, чтобы при /(п) < е значение Л было настолько велико, чтобы не более eN значений п < N имели 1{п)<Х{п) + {1-е)Х{п)/ХХ{п). I

*3вездные цепочки. Оптимисты сочтут оправданным предположение о том, что 1{п) = 1*(п); трудно поверить, что по данной аддитивной цепочке минимальной длины 1{п) нельзя найти цепочку той же длины, удовлетворяющую условию звезд-ности (по-видимому, слабому). Однако в 1958 году Вальтер Хансен (Walter Hansen) доказал замечательную теорему о том, что для определенных больших значений п значение 1(п) строго меньше, чем 1*{п), а также ряд связанных с ней теорем, которые мы сейчас и рассмотрим.

Теоремы Хансена начинаются с исследования детальной структуры звездных цепочек. Пусть п = 2" -- 2 -- • -Ь 2, где ео > ei > • • • > et > О, и пусть I = ао < ai < < Or = п - звездная цепочка для п. Если в этой цепочке имеется d удвоений, определим вспомогательную последовательность

0 = do<di<d2<---<dr = d, (35)

где di-количество удвоений среди шагов 1, 2, i. Также определим последовательность "мультимножеств" So, Si, Sr, которая будет отслеживать наличие степеней 2 в цепочке. (Мультимножество (multiset) представляет собой математический объект, подобный множеству, но он может содержать одинаковые элементы. Объект может быть элементом мультимножества несколько раз, причем кратность его появления в множестве имеет важное значение. Более подробно с

мультимножествами вы ознакомитесь в упр. 19.) Мультимножества Si определены следующими правилами:

a) So = {0};

b) если Oj+i = 2ai, то Si+i =5j + l = {a; + la;G Si};

c) если Oi+i = Oi + uk, к < i, то Si+i = 5, i+l Sk-

(Символ l±l означает, что мультимножества объединяются со сложением крат-ностей.) Из этого определения следует, что

а, = 2 (36)

где члены суммы необязательно различны, в частности

71 = 2*°+2"+--- + 2" = 2. (37)

Число элементов в последней сумме не превышает 2, где f = г - d-количество неудвоений.

Поскольку п имеет два различных бинарных представления в (37), мультимножество Sr можно разбить на мультимножества Мо, Mi, ..., Mt, такие, что

2 = 2 0<j<t. (38)

Данную операцию можно выполнить, разместив элементы Sr в порядке неубывания Xl < Х2 < ••И взяв Mt = {xi,X2i-.-,Xk], Где 2 -I-• • •-I-2- = 2. Это должно быть возможно, поскольку et-наименьшее из всех е. Аналогично Mt i = {xk+i,Xk+2,---,Xk] И Т. Д. Процесс легко визуализируется в двоичной системе счисления, как показано в следующем примере.

Пусть Mj содержит nij элементов (с учетом кратности); тогда ruj < 2 - t, поскольку Sr имеет не более 2 элементов и разбито на f -I-1 непустых мультимножеств. Из (38) видно, что

Cj > X > ej - rrij для всех х е Mj. (39)

Наше исследование структуры звездных цепочек завершается построением мультимножеств Mij, в которых записана история Mj. Мультимножество Si разбито K&t+l мультимножеств следующим образом:

a) Mrj = Mj]

b) если Oj+i = 2ai, то Mij = M(i+i) j - l = {x-l\xe Mi+i)j};

c) если ai+i=ai+ak, k<i, то, поскольку Si+i=SiSSk, полагаем, что Mij = M(j+i)j минус Sk, т. е. мы удаляем элементы Sk из M(i+i)j. Если некоторый элемент Sk появляется в двух или более различных мультимножествах M(i+i)j, удаляем его из множества с наибольшим возможным значением j. Это правило однозначно определяет Му для каждого j, когда г фиксировано.

Из данного определения следует, что

Cj + di - d > X > Cj + di - d - rUj для всех x £ Mij. (40)

в качестве примера такой детализированной конструкции рассмотрим звездную цепочку 1, 2, 3, 5, 10, 20, 23, для которой t = 3, г = 6, d = 3, / = 3. Получим следующий набор мультимножеств.

So Si S2 S3 S4 Sb Sg

Таким образом, M40 = {2,2} и т. д. Из построения можно увидеть, что dj является наибольшим элементом S;; следовательно.

di е Mio.

(41)

Наиболее важная часть этой структуры следует из (40) и одним из непосредственных ее следствий является лемма К.

Лемма К. Если Mij и Muv оба содержат общее число х, то -тпу < {cj - ву) - {du - di) < rrij. I

(42)

Хотя лемма К и не выглядит особо "сильной", она утверждает (когда rrij и обоснованно малы и когда Mij содержит общий с Muv элемент), что количество удвоений между шагами и и i примерно равно разности между показателями е,, и Cj. Это производит впечатление некоторой регулярности в аддитивной цепочке и наводит на мысль о том, что можно доказать результат, аналогичный приведенной выше теореме В, а именно - что 1*{п) = во + t, если показатели степеней ej достаточно различны. Следующая теорема показывает, как это можно сделать.

Теорема Н (W. Hansen, Creiie 202 (1959), 129-136). Пусть п = 2"° +2 + + 2, где во > et > > et >0. Если

Со > 2ei--2.271(t-1) и ei i > е,-I-2m для 1 < г < t, (43) где т = 2L3-27i(t-i)J =eo+t.

Доказательство. Положим, что t > 2, поскольку результат теоремы при t < 2 истинен без наложения ограничений на е. Допустим, что имеется звездная цепочка 1 = Оо < 01 < • • < Or = п для ncr<eo-l-t-l. Пусть ее структуру отражают целые числа d, f, do, ..., dr я мультимножества My и Si, как было определено выше. Согласно следствию из теоремы А известно, что / < [3.271 (t- 1)J. Поэтому значение m является настоящей верхней гранью числа элементов rrij каждого мультимножества Mj.

В сумме

ui =

+ ... +