Таблица 1

ЗНАЧЕНИЯ п ДЛЯ СПЕЦИАЛЬНЫХ АДДИТИВНЫХ ЦЕПОЧЕК

Пусть d{r) обозначает количество решений п уравнения 1{п) = г. В следующей таблице перечислено несколько первых значений этой функции согласно Фламмен-кампу.

Конечно, d{r) должно быть возрастающей функцией от г, но не существует ясного способа доказательства этого кажущегося таким простым утверждения и тем более- определения асимптотического роста d{r) для больших г.

Наиболее знаменитая проблема, связанная с аддитивными цепочками и все еще нерешенная, - гипотеза Шольца-Брауэра, гласящая, что

/(2"-1) <п-1+/(п). (49)

Компьютерные вычисления показывают, что в действительности в (49) вьшолняется равенство для 1 < п < 24. Вычисления, проведенные Э. Г. Тюрбером [Discrete Math. 16 (1976), 279-289], показали, что равенство справедливо также для п = 32. Множество исследований аддитивных цепочек посвящено попыткам доказать (49). Аддитивные цепочки для чисел 2" - 1, которые имеют так много единиц в их двоичном представлении, вызывают особый интерес, поскольку они являются наихудшим случаем для бинарного метода. Арнольд Шольц (Arnold Scholz), придумавший название "аддитивные цепочки", поставил в 1937 году задачу (49) [Jahresbericht der deutschen Mathematiker-Vereinigung, Abteilung II, 47 (1937), 41-42]; Альфред Врауэр (Alfred Brauer) в 1939 году доказал, что

/•(2"-1) <n-l + /*(n). (50)

Теоремы Хансена показывают, что 1{п) может быть меньше, чем 1*{п), так что, определенно, потребуется много работы, чтобы доказать или опровергнуть (49). В качестве шага в этом направлении Хансен определил концепцию 1°-цепочки, которая лежит "между" I- и /-цепочками. В /°-цепочке некоторые элементы подчеркнуты; условие заключается в том, что а, = Oj -HOfc, где Oj -наибольший подчеркнутый элемент, меньший, чем а,.

В качестве примера /"-цепочки (конечно, не минимальной) рассмотрим

1,2,4,5,8,10,12,18. (51)

Легко убедиться, что разность между каждым элементом и предшествующим ему подчеркнутым элементом принадлежит цепочке. Обозначим через /°(п) минимальную длину /°-цепочки для п. Ясно, что 1{п) < 1°{п) < 1*{п).

Цепочка, построенная в теореме F, является /"-цепочкой (см. упр. 22); атедова-тельно, имеем /°(п) < 1*{п) для некоторого п. Неизвестно, вьшолняется ли равенство 1{п) = /°(п) во всех случаях. Если оно истинно, то предположение Шольца-Брауэра должно быть справедливо вследствие еще одной теоремы Хансена.

Теорема G. /«(2" - 1) < п - 1 + /«(п).

Доказательство. Пусть 1 = uq, Oi, ..., = п - /"-цепочка минимальной длины для п и пусть 1 - Ьо, bl, ..., bt = п - последовательность подчеркнутых элементов. (Можно считать, что п подчеркнуто.) Тогда /"-цепочку для 2" - 1 можно получить следующим образом.

a) Включить /°(п) + 1 чисел 2 - 1 для О < г < г, подчеркнуть их тогда и только тогда, когда будет подчеркнуто.

b) Включить числа 2*(2. - 1) для 0<j<t иО <i<bj+i - bj и подчеркнуть их все. (Теперь всего имеется 6i - 6о Н-----\-bt - bt-i = n - 1 чисел.)

c) Рассортировать числа из (а) и (Ь) в порядке возрастания.

Можно легко проверить, что это дает /"-цепочку: числа из (Ь) равны некоторым удвоенным элементам из (а) или (Ь); кроме того, данный элемент представляет собой предшествующий подчеркнутый элемент. Если а, = bj + йк, где bj-наибольший подчеркнутый элемент, меньший, чем Oj, то ак = Oj - bj < bj+i - bj, поэтому 2"(2j - 1) = 2" - 2"* в цепочке подчеркнут и предшествует 2"- - 1. Поскольку 2" -1 равно (2" - 2") -Ь (2"» -1), где оба эти значения содержатся в цепочке, имеем аддитивную цепочку со свойством /°.

Цепочка, соответствующая (51) и построенная в доказательстве теоремы G, такова:

1,2,3,6,12,15,30,31,60,120,240,255,510,1020,1023,2040,

4080.4095,8160,16320,32640.65280.130560.261120.262143.

Графическое представление. Аддитивная цепочка (1) естественным образом соответствует ориентированному графу, вершины которого помечены как а, для О < г < г и в которо.м мы рисуем дуги от Uj к Oj и от Ofc к Oj в качестве представления каждого шага = Oj+Uk из (2).- Например, аддитивная цепочка 1, 2, 3, 6, 12, 15, 27, 39, 78, 79, которая может быть получена из рис. 15, соответствует ориентированному графу

Я 2)-Н 3 У-Н 6 >-Н12)-НЩ-Н27)-Н39>-Н78)->{79

Если Qi - Oj + ак для более чем одной пары индексов {j, к), выбираем определенные j и к для нашего построения.

В целом, все вершины такого ориентированного графа, кроме первой, будут началом ровно двух дуг. Однако в действительности это не важное свойство графа, потому что оно маскирует тот факт, что различные аддитивные цепочки, по сути.

являются эквивалентными. Если вершина имеет выходную степень 1, то она используется только в одном последующем шаге, и поэтому подобный шаг представляет собой сумму Uj+ak+am, которая может быть вычислена либо как {aj+ak)+am, либо как aj + {ak+am), либо как ak + {aj+am)- Какой именно вариант выбран, не важно, но соглашения об аддитивных цепочках заставляют нас их различать. Можно избежать такой избыточности, удалив все вершины, выходная степень которых равна 1 и которые соединены дугами со своими предшественницей и преемницей. Например, приведенный выше граф должен принять вид

?(3j (е)=0(==Щ)--Щ . (52)

Также можно удалить любую вершину, выходная степень которой равна О, за исключением, естественно, конечной вершины Сг, поскольку она соответствует неиспользуемому шагу Б аддитивной цепочке.

Таким образом, каждая аддитивная цепочка дает приводимый ориентированный граф, который содержит одну вершину-источник, помеченную как 1, и одну вершину-сток, помеченную как п. Каждая вершина, кроме источника, имеет входную степень > 2, и каждая вершина, кроме стока, имеет выходную степень > 2. И наоборот, любой такой ориентированный граф без ориентированных циклов соответствует минимум одной аддитивной цепочке, поскольку можно топологически рассортировать вершины и записать d - 1 дополнительных шагов для каждой вершины входной степени d > 0. Длина аддитивной цепочки без учета неиспользуемых шагов может быть определена в процессе просмотра приведенного графа. Она равна

(число дуг) - (число вершин) + 1, (53)

поско.г1ьку удаление вершины выходной степени 1 удаляет также одну дугу.

Две аддитивные цепочки эквивалентны, если они имеют один и тот же приведенный граф. Например, аддитивная цепочка 1, 2, 3, б, 12, 15, 24, 39, 40, 79 эквивалентна цепочке, о которой шла речь в начале этого раздела, поскольку она также сводится к графу (52). Этот пример показывает, что незвездная цепочка может быть эквивалентна звездной цепочке. Аддитивная цепочка эквивалентна звездной цепочке тогда и только тогда, когда ее приведенный ориентированный граф может быть топологически рассортирован лишь одним-единственным образом.

Важное свойство такого графического представления аддитивных цепочек указано Н. Пиппенгером (N. Pippenger): метка каждой вершины в точности равна количеству ориентированных путей от источника к данной вершине. Таким образом, задача поиска оптимальной аддитивной цепочки для п эквивалентна задаче минимизации величины (53) по всем ориентированным графам, имеющим одну вершину-источник и одну вершину-сток и в точности п ориентированных путей от источника к стоку.

Такая характеристика имеет удивительное следствие в связи с симметричностью ориентированного графа. Если обратить направления всех дуг, источник и сток поменяются местами и получится другой ориентированный граф, соответствующий множеству аддитивных цепочек для того же значения п. Эти аддитивные цепочки имеют такую же длину (53), как и первоначальная цепочка. Например, если развернуть все стрелки в (52) справа налево и пометить вершины в соответствии с числом