AOP_Tom2 (1021737), страница 144
Текст из файла (страница 144)
*Звездные цепочки. Оптимисты сочтут оправданным предположение а том, что 1(п) = 1" (п); трудно поверить, что по данной алдитивной цепочке минимальной длины 1(и) нельзя найти цепочку той же длины, удовлетворяющую условию звездности (по-видимому, слабому). Однако в 1958 году Вальтер Хансен (уча!гег Напэеп) доказал замечательную теорему о том, что для определенных больших значений п значение 1(и) строго меньше, чем 1'(и), а также ряд связанных с ней теорем, которые мы сейчас и рассмотрим.
Теоремы Хансена начинаются с исследования детальной структуры звездных цепочек. Пусть и = 2" + 2" + + 2", где ео > е~ > > е~ > О, и пусть 1 = ао < аг « . о„= п — звездная цепочка для п. Если в этой цепочке имеется Н удвоений, определим вспомогательную последовательность (35) О=Ив <4 <4 «И, =И, где 4--количество удвоений среди шагов 1, 2, ..., б Также определим последовательность "мультимножеств" 5е, 5м ..., 5„, которая будет отслеживать наличие степеней 2 в цепочке. (Мультомнажесшво (ти(йвег) представляет собой математический объект, подобный множеству, но он может содержать одинаковые элементы. Объект может быть элементом мультимножества несколько раз, причем кратность его появления в множестве имеет важное значение.
Более подробно с мультимножествами вы ознакомитесь в упр. 19.) Мультимножества 5~ определены следующими правилами; а) 5е = (О); Ь) если а, 1 — — 2а,, то 5ьы —— 5, + 1 = (х+ 1 ~ т 6 5„); с) если аьы — — а, + аь, Л < 1, то 5,ч1 — — 5, Ю5ь. (Символ Ы означает, что мультнмножества объединяются со с.южением кратностей.) Из этого определения следует, что а;=" 2*, (36) хез, где члены суммы необязательно различны, в частности и = 2" + 2" + " + 2" = ~ ~2*. ьеэ, (37) Число элементов в последней сумме не превышает 2Х, где Х = г — 4 — количество неудвоений.
Поскольку и имеет два различных бинарных представления в (37),мультимножество 5„можно разбить на мультимножества Ме, ЛХм ..., ЛХм такие, что е, > т > е. — гп для всех х 6 М, (39) Наше исследование структуры звездных цепочек завершается построением мультимножеств Мсь в которгвх записана история ЛХ . Мультимножество 5, разбито на 1+ 1 мультимножеств следующим образом: а) ЛХ„.=М; Ь) если а;+1 — — 2аь то МИ = Мрто, — 1 = (х — 1 ! х 6 ЛХОч.10); с) если аьы = а, + ам й <1, то, поскольку 5,.ы — — 5 Ы5ы полагаем, что М„.
= МО+П минус 5ы т. е. мы удаляем элементы 5ь из ЛХО+П,, Если некоторый элемент 5ь появляется в двух или более различных мультимножествах Мо~о з удаляем его из множества с наибольшим возможным значением Хг Это правило однозначно определяет ЛХ;, для каждого Х, когда 1 фиксировано. Из данного определения следует, что (40) для всех х 6 Мьо ау +Н; — с( > х > е + 4 — а — шу Данную операцию можно выполнить, разместив элементы 5, в порядке неубывания х1 < хз < и взяв ЛХс — — (хыхз,...,ть), где 2*' + ° + 2*' = 2", Это должно быть возможно, поскольку е, — наименьшее из всех е. Аналогично Л4, = (ть+мть+г,,хь ) и т. д. Процесс легко визуализируется в двоичной системе счисления, как показано в следующем примере. Пусть М. содержит ьч элементов (с учетом кратности); тогда гп ~ 2Х вЂ” Г, поскольку 5„имеет не более 2Х элементов и разбито на 1+ 1 непустых мультимножеств.
Из (33) видно, что В качестве примера такой детализированной конструкции рассмотрим звездную цепочку 1, 2, 3, 5, 10, 20. 23, для которой ! = 3, т = 6, д = 3, Х = 3. Получим следующий набор мультимножеств. (~!о, г!г,., Й): (ао, аг,..., ао): (Моз, Мгз,..., Моз): (Мог, Мю,, Мог): (Мою Мм, Мш): (Моо, ЛХго." ., ЛХоо): 50 51 5г 53 54 5з 56 ЛХз ез = Мг ег —— ЛХг ег —— 0.,тз=1 1,тг=1 2, пм — — 1 Мо во=4,то=2 Таким образом, ЛХзо —— (2,2) и т.
д. Из построения можно увидеть, что 4 является наибольшим элементом 5,; следовательно, (41) А Е .Ко. Наиболее важная часть этой структуры следует нз (40) н одним из непосредственных ее следствий является лемма К. Лемма К. Если ЛХ, и М„оба содержат общее число т, то — т„< (е, — е„) — (б„— г),) < т,, ! (42) Теорема Н (%. Напзеп, Сге(!е 202 (1959), 129-136) . Пусть и = 2" + 2" + .. + 2", где ео > е! » . е, > О. Если ео > 2ег+ 2.271(г — 1) и е; г > е;+2т для 1 < г < 1, (43) гДе т = 2~о.ггЦ' ки — г, то ! "(и) = ео + б Доказательство.
Положим, что ! > 2, поскольку результат теоремы прн ! < 2 истинен без наложения ограничений на е. Допустим, что имеется звездная цепочка 1 = ао < аг « . а„= п для п с г < ео + г — 1. Пусть ее структуру отражают целые числа И, Х, о(о, ..., а!„и мультимножества ЛХ,. и 5„как было определено выше. Согласно следствию нз теоремы А известно, что Х < (3.271(г — 1)) . Поэтому значение т является настоящей верхней гранью числа элементов гпу каждого мультимножества М .
В сумме щ=( з 2')+( г 2*)~..~( л 2') Хотя лемма К и не выглядит особо "сильной", она утверждает (когда т. и т„ обоснованно малы и когда ЛХВ содержит общий с М„ элемент), что количество удвоений между шагами и и г примерно равно разности между показателями ег и ез. Это производит впечатление некоторой регулярности в алдитивной цепочке и наводит на мысль о том, что можно доказать результат, аналогичный приведенной выше теореме В, а именно — что !'(п) = ео + г, если показатели степеней ез достаточно различны. Следующая теорема показывает, как это можно сделать. не будет переносов из члена, соответствующего М,;, к члену, соответствующему.
Мцз ор если рассматривать ее как выполняющуюся в двоичной системе счисления, поскольку е достаточна далеко разнесены (см. (40)). В частности, сумма всех членов для у ф 0 не даст переносов к членам для у = О, так что мы должны получить 2я > 2моб (44) О<1<с. хем,о Для доказательства теоремы Н необходимо показать, что в некотором смысле 1 дополнительных степеней и должны размещаться "по одной", чтобы можно было определить, на каком шаге каждый из этих членов, по существу; включается в аддитивную цепочку, Пусть у представляет собой числа между 1 ив. Поскольку Мо, пусто, а М„=ЛХх не пусто, можно найти первый шаг 1, для которога МО не пу.ста. Из способа, которым определяется МО, известна, что шаг 1 не является удвоением; а, = а; 1 + а„для некоторого и < 1 — 1.
Также известно, что все элементы Ми являются элементами 5„. Докажем, что а„должно быть относительно мало по сравнению с а,. Пусть х является элементом МО. Тогда, поскольку ху 6 5„, существует и, для которого х, 6 М „. Отсюда следует, что (45) Х* — д >т т. е. между шагами и и 1 встречается как минимум т+ 1 удвоений: если 4 — Н„< т, лемма К гласит, что ~е — е„~ < 2т; следовательно, и = Х.
Однако это невозможна, потому что ЛХ„пусто в соответствии с нашим выбором шага Г. Все элементы 5„не превышают е, + д, — 4. Действительно, если х 6 5„С 5, и х > е1 + 4 — 4, то х 6 ЛХ„о и х 6 ЛХ,о согласно (40), так чта из леммы К следУет, что ~А — Н„~ < т, а это противоречит (45), Значит, это рассуждение доказывает, что Л4о не имеет общих с 5„элементов и МО Во — — М;о. Из (44) имеем а; 1 > 2~"'~, и поэтому шаг 1 является малым шагом. Теперь вьиедем ключевой факт ва всем этом доказательстве: все элементы 5„ являются элементами М„о.
Действительно, если это не так, пусть х будет элементом 5„, таким, что х К М„о. Поскольку х > О, из (40) следует, что е1 > Ы вЂ” 4„и ео = Х + 4 — в < 2.271в+ 4 < 2.271(1 — 1) + е, + Нл. Из гипотезы (43) получаем, что Н„> ем Однако Н„6 5„в соответствии с (41) и не может находиться в М;о. ГГоэтому Н„< е1+ 4 — 4 < еы что приводит к противоречию. Возвращаясь к элементу ху из Мсм получаем, что ху 6 М„„. К тому же было доказано, чта и = О. Поэтому, используя (40) еще раз,получим (46) ео + А — 4 > х, > ео -ь Х вЂ” 4 — то Теперь для всех Х = 1, 2, 1 определено число ху, удовлетворяющее (46), и малый шаг ~., на котором в аддитивную цепочку вводится член 2' . Если у Ф Х', шаг 1, на котором это происходит, не может быть одним и тем же и для Х, и для у'. Из (46) следует, что ~х, — х, ~ < гп, в то время как элементы МО н Мел должны отличаться более чем на т, поскольку е, и е.
существенно различны. Мы вынуждены заключвтзь что цепочка содержит как минимум ! малых шагов, но это приводит к противоречию. 1 Теорема Е (В. Хансен (уУ. Напзеп)). !(2" + ху) < А+ ы(х) + и(у) — 1, если Л(х) + Л(у) < А. (47) Доказательствоо. Алдитивная цепочка (в общем случае не звездная) может быть построена путем комбинирования бинарвога метода и метода множителя. Пусть х = 2ю +.
+ 2*" и У = 2"' + + 2"', где хг » х„> О и Уг » У„. > О. Первые шаги цепочки представляют собой паследовательнгле степени 2, пока пе достигнуто значенне 2л "'; между этими шагами в соответствующих местах вставляются дополнительные значения 2'"-' + 2", 2'"-' + 2'"- ' + 2"", ... и х.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
