Доказательство. Когда 1(п) = А(п) + 2, существует аддитивная цепочка для п, имеющая только два малых шага. Она состоит из одного из шести типов, перечисленных в доказательстве теоремы В, малого шага и последовательности немалых шагов. Будем говорить, что п "специально", если п = 2"* -Ь 2 -ь 2 -Ь 2 для одного из четырех случаев, перечисленных в теореме. Можно получить аддитивные цепочки требуемого вида для каждого специального п, как показано в упр. 13, поэтому остается доказать, что не существует цепочек с точно двумя малыми шагами, содержащих любые элементы с u{ai) > 4, за исключением специального Oj.

Назовем цепочкой-контрпримером аддитивную цепочку с двумя малыми шагами, такую, что и{аг) > 4, но не является специальным. Если цепочка-контрпример существует, то рассмотрим цепочку 1 = оо < ai < • • • < = п наименьшей возможной длины. Тогда шаг г не является малым шагом, поскольку ни один из типов цепочек из доказательства теоремы В не может предшествовать малому шагу с и{п) > 4, за исключением специального п. Кроме того, шаг г не является удвоением, так как более коротким контрпримером была бы цепочка оо, ..., a-i. Наконец, шаг г является звездным, так как иначе цепочка оо, ..., аг-2, представляла бы собой более короткую цепочку-контрпример. Таким образом.

Or = Or-i + Ог-к, к>2, и А(аг) = A(ar-i)-Ы. (21)

Обозначим число переносов, встречающихся при сложении a-i и Ог-к в двоичной системе счисления по алгоритму 4.3.1А, как с. Используя фундаментальное соотношение

и{аг) = u{ar-i) + и{аг-к) - с, (22)

можно доказать, что шаг г - 1 не является малым (см. упр. 14).

Пусть т = A(ar i). Поскольку ни г, ни г - 1 не является малым шагом, с > 2; равенство с = 2 может быть справедливо только тогда, когда a-i > 2™ -Ь 2"~.

Теперь предположим, что г - 1 - не звездный шаг. Тогда г - 2 - малый шаг и ао, Ог-з, Or-i представляет собой цепочку с только одним малым шагом. Следовательно, i/(ar i) < 2 и 1(0-2) < 4. Соотношение (22) может выполняться, только если i/(ar) = 4, 1/(0-1) = 2, = 2, с = 2, 1/(0-2) =4. Из с = 2 можно заключить, что a-i = 2" -Ь 2""; следовательно, ао, ai, ..., а-з - 2"~ + 2"" является адйитиврюй цепочкой с только одним малым шагом и эта цепочка должна быть первого типа, так что а относится к случаю 3. Таким образом, г - 1 является звездным шагом.

Теперь предположим, что a-i = 2аг-к для некоторого t. Если i/(ar-i) < 3, то в соответствии с (22) с = 2, fc = 2 и а должно относиться к случаю 3. С другой стороны, если u{ar-i) - 4, то a-i будет специальным, и при рассмотрении каждого случая легко видеть, что а также относится к одному из четырех случаев. (Случай 4 возникает, например, когда Or-i = 90, Ог-к = 45 или когда Or-i - 120, йг-к = 15.) Поэтому можно заключить, что Or-i ф 2аг-к для любого t.

Мы доказали, что a-i = 0-2 + Or-q для некоторого q > 2. Если fc = 2, то g > 2 и ао, ai, ..., аг-2, 20-2, 2аг-2 + a,r-q = Ог представляет контрпример последовательности, у которой fc > 2. Поэтому можно считать, что fc > 2.

Теперь предположим, что Х{аг-к) = m - 1. Случай, когда A(ar-ife) < т - I, может быть исключен в результате подобного рассмотрения, как показано в упр. 14. Если fc = 4, тоиг - 2, иг - 3 являются малыми шагами; следовательно, Ог-л = 2"*"

и (22) невозможно. Поэтому к = 3; шаг г - 2 является малым, и{аг-з) = 2, с = 2, Or-i > 2" -Ь 2""~ и 1/(0-1) = 4. Должно существовать как минимум два переноса при сложении чисел а-г и a-i - 0-2. Значит, 1/(0-2) = 4 и а-г (будучи специальным и > ar i) имеет вид 2"" -i-2™-+2+2 для некоторого d. Теперь Or-i равно либо 2™ -2"~ -ь2+1 +2, либо 2" +2"" + 2*+ -2+ и в обоих случаях Ог-з должно быть равно 2"*" + 2""2 так что относится к случаю 3.

Э. Г. Тюрбер [Pacific J. Math. 49 (1973), 229-242] расширил теорему С для показа того, что 1{п) > Х{п) + 4 при и{п) > 8. Представляется обоснованным предположение, что 1{п) > Х{п) + lgi/(n) в общем случае, поскольку А. Шёнхаге (А. Schonhage) очень близко подошел к доказательству этого факта (см. упр. 28).

*Асимптотические значения. Из теоремы С следует, что получение точных значений 1(п) при больших п является, по всей видимости, очень трудной задачей. Однако можно определить приближенное поведение функции в предельном случае, когда п 00.

Теорема D (А. Вгаиег, Bull. Amer. Math. Soc. 45 (1939), 736-739).

lim Г{п)/Х{п) = lim l{n)/X{n) = 1. (23)

П-ЮО п-юо

Доказательство. Аддитивная цепочка (4) для 2*-арного метода является звездной, если удалить из нее все вторые вхождения каждого элемента, встречающегося в цепочке дважды. Если at - первый элемент среди 2do, ido, ... второй строки, который отсутствует в первой строке, имеем ai < 2(m - 1); следовательно, Oj = (m - 1) -Ь Oj для некоторого Oj в первой строке. Суммируя обшую длину цепочки, получаем

А(п)</(п)<Г(п) < (l + l/fc)lgn + 2 (24)

для всех к > 1. Утверждение теоремы можно получить, если, например, выбрать fc=LilgA(n)J. I

Если положить к = АА(п) - 2ААА(п) в (24) для больших п, где АА(п) означает А(А(п)), получим более строгую асимптотическую границу

1{п) < Г{п) < Х{п) + Х{п)/ХХ{п) + 0{Х{п)ХХХ{п)/ХХ{п)). (25)

Второй член А(п)/АА(п) является, по существу, лучшим из того, что можно получить из (24). Можно провести более глубокий анализ нижних границ, чтобы показать, что этот член А(п)/АА(п) является неотъемлемой частью (25). Чтобы понять, почему это так, рассмотрим следующую теорему.

Теорема Е (Paul Erdos, Acta Arithmetica 6 (1960), 77-81). Пусть e -положительное действительное число. Количество аддитивных цепочек (И), таких, что

Х{п) = т, г<т + {1-е)т/Х{т), (26)

меньше, чем а" для некоторого а < 2 для всех достаточно больших т. (Другими словами, число аддитивных цепочек, столь коротких, что удовлетворяется соотношение (26), существенно меньше количества значений п, таких, что А(п) = т, при больших т.)

Доказательство. Чтобы оценить количество возможных аддитивных цепочек, сначала необходимо улучшить теорему А, и это позволит нам более успешно работать с неудвоениями.

Лемма Р. Пусть д < V2 - I - фиксированное положительное действительное число. Назовем шаг г аддитивной цепочки мини-шагом, если это не удвоение и если Oi < aj{l + дУ~ для некоторого j, где О < j < г. Если аддитивная цепочка содержит S малых шагов и t мпни-шагов, то

t<s/{l-e), где (1 + 5)2 = 2 (27)

Доказательство. Для каждого мини-шага ik, I < к < t, имеем at, < а;(1 -Ь J)*"* для некоторых jk < ik. Пусть h,..., If -интервалы (ji .. ii],... ,{jt.. it], где запись (j - i] означает множество всех целых чисел к, таких, что j < к < i. Можно найти (см. упр. 17) такие неперекрываюшиеся интервалы Ji,..., Л = (jj.. iJ,..., (j .. ], что

/i u---u/t = Ji и--ил,

(28)

< Of (1 + <5)2(ч-Л) для 1 < fc < /I.

Теперь для всех шагов г, находяшихся вне интервалов Ji, ..., Jh, имеем Oj < 2aj-i; следовательно, если положить

можно получить 2(») <п< 2-«(1 -h J)* = 2(»)+»-(i-«)« < 2(")+-(1-«)*.

Возвращаясь к доказательству теоремы Е, выберем S = 2/* - 1 и разделим г шагов каждой аддитивной цепочки на три класса:

t мини-шагов, и удвоений, v прочих шагов, t -I- и -i- v = г. (29)

При другом способе подсчета шагов получим s малых шагов, где s+m = г. Из наших предположений, теоремы А и леммы Р получим соотношения

s<{l-e)m/X{m,), t-h и < 3.271s, t < s/(l - е/2). (30)

Для данных s, t, и и v, удовлетворяющих этим условиям, существует

{t,u,v) ~ {t + v){ V )

способов назначения шагов определенным классам. При заданном распределении шагов рассмотрим, каким образом могут быть выбраны не мини-шаги. Если шаг i является одним из "других" шагов в (29), а» > (1 -Ь d)ai-i, так что = Oj -Ь Ok, где Sui-i < йк < uj < Oi-i. Кроме того, Oj < ai/{l -I-дУ~ < 2ai i/(l -I-Sy~, поэтому д < 2/{1+дУ~. Это дает не более /3 выборов j, где /3 - константа, зависящая только от д. Имеется также не более /3 выборов к, так что количество способов назначения j и к для каждого не мини-шага не превышает

2". (32)

И наконец, как только j и fc выбраны для каждого из не мини-шагов, имеется менее