О покрытиях множеств в евклидовых пространствах тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Московский физико-технический институт (Государственный университет)

На правах рукописи

005057923

Филимонов Владислав Павлович

О ПОКРЫТИЯХ МНОЖЕСТВ В ЕВКЛИДОВЫХ ПРОСТРАНСТВАХ

01.01.09 — дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Москва - 2013

005057923

Работа выполнена на кафедре дискретной математики факультета инноваций и высоких технологий Московского физико-технического института (государственного университета).

Научный руководитель: доктор физико-математических наук,

профессор Райгородский Андрей Михайлович.

Официальные оппоненты: доктор физико-математических наук,

профессор Дольников Владимир Леонидович;

доктор физико-математических наук, доцент Карасёв Роман Николаевич.

Ведущая организация: Хабаровское отделение

Института прикладной математики Дальневосточного отделения РАН.

Защита диссертации состоится 17 мая 2013 г. в 11 часов на заседании диссертационного совета Д 501.001.44 при Московском государственном университете имени М.В. Ломоносова по адресу: 119991, Москва, ГСП-1, Ленинские горы, 2-й учебный корпус, факультет ВМК, аудитория 685. Желающие присутствовать на заседании диссертационного совета должны сообщить об этом за два дня по тел. 939-30-10 (для оформления заявки на пропуск).

С диссертацией можно ознакомиться в Фундаментальной библиотеке МГУ имени М. В. Ломоносова. С текстом автореферата можно ознакомиться на официальном сайте факультета ВМК МГУ http://cs.msu.ru/.

Автореферат разослан £6 апреля 2013 г.

Ученый секретарь диссертационного совета

В.А.Костенко

Общая характеристика работы

Актуальность темы диссертации

В работе получены результаты, связанные с классической проблемой Борсука о разбиении множеств в Rm на части меньшего диаметра, с известной задачей Нелсона-Хадвигера о хроматическом числе евклидова пространства, а также с задачей об оптимальных решётчатых покрытиях евклидовых пространств.

Проблема Борсука была сформулирована почти 80 лет назад1, и в последние годы она стала одной из ключевых проблем в области комбинаторной геометрии и явилась источником возникновения множества новых идей и задач в рамках данного раздела науки2,3'4,5. Она заключается в отыскании минимального числа частей меньшего диаметра, на которые может быть разбито произвольное ограниченное множество в пространстве. Из данной формулировки ясно, что проблема Борсука связана с известными задачами оптимальных разбиений, упаковок и покрытий множеств в различных пространствах6. Данная взаимосвязь проясняется в работах таких ученых, как

'К. Borsuk, Drei Sätze über die n-dimensional euklidische Sphäre, Fundamenta Math., 20 (1933), 177 - 190.

2P. Brass, W. Moser, Л. Pach, Research problems in discrete geometry, Springer, 2005.

3A.M. Raigorodskii, Three lectures on the Borsuk partition problem, London Mathematical Society Lecture Note Series, 347 (2007), 202 - 248.

4A.M. Райгородский, Вокруг гипотезы Борсука, Итоги науки и техники, сер. "Современная математика", 23 (2007), 147 - 164.

5А.М. Райгородский, Об одной оценке в проблеме Борсука, Успехи матем. наук, 54 (1999), N2,185 - 186.

бДж. Конвей и Н. Слоэн, Упаковки шаров, решетки и группы, Москва, "Мир", 1990.

К.А. Рождерс7, Р. Ранкин8, Ж. Бургейн и Й. Линденштраусс9 и многих других. Настоящая диссертация также посвящена исследованию задачи об оптимальных покрытиях множеств в евклидовых пространствах множествами меньшего диаметра, являющейся непосредственным обобщением проблемы Ворсука, которое в 50-е годы XX века было предложено X. Ленцем10.

Вторая проблема, непосредственно связанная с результатами нашей работы, принадлежит нескольким авторам, из которых наибольшую роль в ее становлении сыграли Э. Нелсон11, П. Эрдеш12 и Г. Хадвигер13. Проблема заключается в нахождении наименьшего количества цветов, необходимых для такой раскраски метрического пространства, при которой расстояние между произвольными двумя одноцветными точками не может равняться некоторому наперед заданному числу. Данной задаче также более 60 лет, и ее популярность оромна14,15'16. При решении данной задачи была разработана техника, относящаяся к так называемым разбиениям Вороного и имеющая непосредственную взаимосвязь со знаменитыми статьями Г. Батлера17, П. Эрдеша и К.А. Рождерса18, Д. Лармана и К. Рождерса19 и многими другими.

Наконец, задача об оптимальных решетчатых покрытиях также имеет более чем 70-летнюю историю и тесно связана с такими разделами алгебры

7С.А. Rogers, Covering a sphere with spheres, Mathematika, 10 (1963), 157 - 164.

8R. Rankin, On the closest packing of spheres in n dimensions, Ann. Math., 48 (1947), 1062 - 1081.

3J. Bourgain, J. Lindenstrauss, On covering a set in by balls of the same diameter, Geometric Aspects of Functional Analysis (J. Lindenstrauss and V. Milman, eds.), Lecture Notes in Math., 1469, Springer-Verlag, Berlin, 1991, 138 - 144.

10H. Lenz, Zerlegung ebener Beniche in konvexe Zellen von möglichst kleinem Durchmesser, Jahresbericht d. DMV Bd. 58, (1956), 87 - 97.

UA. Soifer, The Mathematical Coloring Book, Springer, 2009.

"L.A. Szäcely, ErdSs on unit distances and the Szemeridi-Trotter theorems, Paul ErdSs and his Mathematics, Bolyai Series Budapest, J. Bolyai Math. Soc., Springer, 11 (2002), 649 - 666.

13H. Hadwiger, Ein Überdeckungssatz fir den Euklidischen Raum, Portugaliae Math., 4 (1944), 140 - 144.

14A. Сойфер, Хроматическое число плоскости: его прошлое, настоящее и будущее, Матем. просвещение, Вып. 8, 2004.

15А.М. Райгородский, Хроматические числа, Москва, МЦНМО, 2003.

16Р.К. Agarwal, J. Pach, Combinatorial geometry, John Wiley and Sons Inc., New York, 1995.

17G. J. Butler, Simultaneous packing and covering in Euclidean space, Proc. Lon. Math. Soc., Ser. 3, 25 (1972), N4, 721 - 735.

18P. Erd6s, C.A. Rogers, Covering space with convex bodies, Acta Arithmetica, 7 (1962), 281 - 285.

1SD.G. Larinan, C.A. Rogers, The realization of distances within sets in Euclidean space, Mathematika, 19 (1972), 1 - 24.

и дискретной математики, как теория диофантовых приближений и нера-

9П 21

венств и теория кодирования .

Цель и задачи исследования

Целью диссертационной работы является решение следующих задач.

1. Улучшение известных оценок сверху и снизу величин

# = вир<С(Ф),

где супремум берётся по всем множествам Ф диаметра 1 в Кт, а величина й™(Ф) для произвольного ограниченного множества Ф в и натурального числа п определяется следующим образом:

<*£(Ф) = Ы {а; € М+ : Ф С Фх и ... и Фп, V» сМатФ; < о;} .

2. Исследование асимптотического поведения последовательностей <Е£(Ф) для произвольных ограниченных множеств Ф.

Научная новизна полученных результатов

Все результаты диссертации являются новыми.

Практическая значимость полученных результатов

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

20Дж. Касселс, Введение в теорию диофантовых приближений, Москва, ИЛ, 1961.

21Ф.Дж. Мак-Вильямс, Н.Дж.А. Слоэн, Теория кодов, исправляющих ошибки, Москва, "Связь", 1979.

Основные результаты, выносимые на защиту

1. Выполнены следующие неравенства:

4 ^ 0.6020, 4 ^ ^ (2 - л/3) , 4 < 0.4456,

7

,2 ^ /32 — 2л/Ї09 ,2 ^ ' ,2 ^

у/3-1

63

Юл/3'

(Теорема 1)

2. Для каждого натурального п справедливо неравенство

' 9к2 + 9к + 1, п = ЗА; + 1;

4(»> ^ ^ ' где =

9А;2 + 15& + 7, п = ЗА; + 2; 9 к2 + Зк + 1, п = 3 к.

Более того,

(Теорема 2)

4(9)-3 - ^88 < д^/з '

3. Для всех натуральных п верно неравенство

А2 < 2

°Зп2-Зп+1-3£(т) ^ ЗП — 2 '

-6, а

где то = т(п) = 4п — |^2\/Зп -<5(т) = <

0, т < 0;

/с2, т = 2/с — 1;

*:(£ + !), т = 2к.

Более ТОГО, при 72 = 14

— сіма

Зп2—Зп+1—3(6(т)+1) ~ "526 Зп _ 2

- 0.05.

(Теорема 3)

4. Для любого 0 < х < 1 справедливо неравенство ^ х, где

д(х) = Е

к=О

2тг

агссов 1 —

е(х),

причем е(х) —

2(1 -кху 1, Ц] =2п-1,пеП;

О, иначе. (Теорема 4)

5. Для единичной окружности в К3 и произвольного натурального числа

п справедливо неравенство

4(50 >

2-

(Лемма 2)

б. Для всех достаточно больших натуральных п и произвольного натурального т справедлива оценка

-1

^ < Н шп + 1) у7гт(т + 2)

7. Для произвольной размерности пространства ш справедлива двойная асимптотическая оценка

— < <Г < 1 + °(1) 'ЖГП{Ш + 2) -

ф. V 12(ш + 1) у Г (1 + 1)'

8. Для произвольных ограниченных множеств Ф1 и Фг в К"1, замыкания которых [Ф1] и [Фа] измеримы по Жордану и имеют меры щ и ц2 соответственно, причём Ц2 0, существуют пределы

п->со в™(Ф2) п^оо С^(Ф2) V

(Теорема о площадях)

9. Для произвольного ограниченного множества Ф С Rm, замыкание которого измеримо по Жордану, существует предел

lim е?(Ф) = lim ^п-сС(Ф)-

71—>00 " v ' n-юо п 4

(Теорема о пределе)

Личный вклад соискателя

Все результаты диссертации получены соискателем самостоятельно.

Апробация результатов

Результаты, полученные в диссертации, докладывались и обсуждались на международной конференции «Фестиваль комбинаторики и информатики» (Венгрия, 2008 г.), на международной конференции «Конечные и бесконечные множества» (Венгрия, 2011 г.), на кафедральном семинаре кафедры математической статистики и случайных процессов механико-математического факультета МГУ имени М.В. Ломоносова, на кафедральном семинаре кафедры дискретной математики факультета инноваций и высоких технологий МФТИ, на семинаре профессора A.M. Райгородского в МГУ имени М.В. Ломоносова, на научном семинаре вычислительного центра имени A.A. Дородницына российской академии наук под руководством профессора К.В. Рудакова, а также на научном семинаре «Дискретная математика и математическая кибернетика» кафедры математической кибернетики факультета вычислительной математики и кибернетики МГУ имени М.В. Ломоносова.

Опубликованность результатов

Результаты диссертации опубликованы в работах [1]-[5] списка литературы. Всего по теме диссертации опубликовано 5 работ.

Структура и объем диссертации

В диссертации имеется введение, три главы, список литературы. Полный объем 115 страниц, из них 5 страниц занимает список литературы (66 наименований).

Краткое содержание диссертации

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

Даны определения величин

<С(Ф) = М {а; е : Ф С Ф! и ... и Ф„, Уг сИатФ* ^ х} ,

С = з ирС(Ф),

где супремум берётся по всем множествам Ф диаметра 1 в Кт, а также

е™(ф)= ^п-С(Ф)-

Величина ¿™(Ф) представляет собой точную нижнюю грань положительных чисел х, обладающих тем свойством, что множество Ф может быть полностью покрыто п множествами, диаметры которых не превосходят х.

Последовательности и е™(Ф) называются соответственно кодом де-

ления и нормированным кодом деления множества Ф.

Также приведены определения универсального покрывающего множества и универсальной покрывающей системы множеств в Ет как множества (системы множеств), которым (одним из множеств которой) можно полностью покрыть произвольное множество единичного диаметра в Ет. Приведены примеры наиболее известных универсальных покрывающих множеств в двумерном и трехмерном пространствах. В частности, на двумерной плоско-

сти универсальным покрывающим множеством является правильный шестиугольник с единичным расстоянием между противоположными сторонами.

Универсальные покрывающие множества и системы являются эффективным инструментом получения верхних оценок величин <2^, поскольку если возможно построить покрытие произвольного универсального покрывающего множества в Ет некоторым набором множеств, то очевидным образом аналогичное покрытие найдется и для произвольного множества единичного диаметра в Кт.

Далее во введении приведен полный обзор известных точных и асимптотических оценок сверху и снизу величин и в пространствах различных размерностей. Важнейшей оценкой снизу является

< Ат

" П '

уп

Для пространств размерностей больше трех данная оценка являлась единственной известной оценкой снизу. Кроме того, было доказано существование асимптотических оценок сверху вида

для некоторых констант ф(т), однако явные значения величин ф(т) не были известны.

Улучшению подобных оценок, а также исследованию асимптотических свойств кодов деления посвящена настоящая диссертация.

В первой главе рассматривается случай двумерной плоскости. С использованием техники универсальных покрывающих множеств и систем получены оценки сверху величин £¿5 — ¿\2. Для больших значений п (вплоть до п = 1313) оценки сверху получены при помощи замощения усеченного правильного шестиугольника паркетом из правильных шестиугольников. Всего оценки сверху улучшены для 112 различных значений п.

Также в первой главе описан метод расслоения, позволяющий получать оценки сверху величин <1™ (Ф). Суть метода расслоения заключается в выделении в некотором наиболее удобном множестве Ф единичного диаметра

набора подмножеств, удовлетворяющих свойству, что расстояние между любыми двумя точками различных подмножеств не меньше некоторой наперед заданной константы х. В этом случае для произвольного покрытия Ф множествами, диаметры которых меньше х, никакое множество покрытия не может иметь общие точки более чем с одним множеством расслоения. Поэтому количество множеств с диаметрами меньшими х, необходимых для покрытия Ф, не меньше, чем сумма аналогичных количеств множеств, необходимых для покрытия каждого из подмножеств расслоения по отдельности.

Для случая двумерной плоскости в качестве исходного множества наиболее удобно использовать круг единичного диаметра, а в качестве множеств расслоения — набор концентрических окружностей с радиусами, образующими арифметическую прогрессию с разностью х. Данный метод позволил улучшить известные оценки снизу величин й2п для 55 различных значений п из диапазона 8 ^ п < 69.

Основные результаты главы 1 сформулированы в параграфе 1.1. Это теоремы 1-4, которые приведены в пунктах 1-4 из раздела "Основные результаты, выносимые на защиту" настоящего автореферата. Они доказаны в параграфе 1.2 и прокомментированы в параграфе 1.3. Итоговая таблица с оценками приведена в параграфе 1-4-

Вторая глава посвящена получению оценок величин в пространствах произвольных размерностей. При этом методы, использованные для получения точных оценок, аналогичны методам, использованным в первой главе.

Метод расслоения применяется к единичному шару, а множествами расслоения являются концентрические сферы. В трехмерном пространстве таким образом улучшены оценки снизу величин ¿^ для значений п вплоть до 275 (параграф 2.1).

С ростом размерности пространства т растет количество значений п, для которых метод расслоения позволяет получить улучшения известных ранее оценок. Кроме того, получаемые оценки все более значительно улучшают своих предшественников (параграф 2.2).

Помимо точных оценок сверху (параграф 2.3) и снизу (параграфы 2.1 и 2.2),

во второй главе также получены асимптотические оценки сверху величин с/™ (параграф 2-4)- Как уже упоминалось выше, в пространствах размерностей больше двух ранее было известно лишь о существовании подобных оценок, а в явном виде оценки были получены в настоящей диссертации впервые.

Наконец, с использованием результатов теории решетчатых покрытий во второй главе показано (параграф 24), что в действительности ф(т) 1 при т—> оо.

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

эквивалентная тому, что нормированный код деления произвольного ограниченного множества в Кт ограничен с двух сторон константами:

1 ^ е£(Ф) < ф{т).

Итоговой целью третьей главы является доказательство того, что в действительности для произвольного ограниченного множества, такого, что его замыкание измеримо по Жордану (данному условию удовлетворяют практически все множества, которые могут стать предметом исследования комбинаторной геометрии), существует предел его нормированного кода деления.

Доказательство данного утверждения — теоремы о пределе — значительным образом использует теорему о площадях, доказанную в первом параграфе третьей главы и утверждающую, что для произвольных ограниченных множеств Фх и Фг в Кт, замыкания которых измеримы по Жордану и имеют меры /¿1 и р,2 соответственно, причём /¿2 ф 0, существуют пределы

Ит да) = Ит = ж.

п-юо е™(Ф2) V А«2

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

В силу теоремы о площадях утверждение теоремы о пределе достаточно доказать для некоторого фиксированного, наиболее удобного жорданова множества.

Параграфы 2-4 третьей главы посвящены отысканию интересных свойств кодов деления жордановых множеств. Все результаты данных параграфов являются прямыми следствиями теоремы о пределе, однако методы, использованные при доказательстве данных результатов (комбинаторный и интегрально-геометрический), отличаются от метода, использованного при доказательстве теоремы о пределе и представляют самостоятельный интерес.

В пятом параграфе доказана теорема о пределе. В качестве наиболее удобного множества для доказательства использован единичный квадрат. Теорема о пределе означает, что код деления произвольного жорданова множества асимптотически эквивалентен величине -щ, а его нормированный код деления эквивалентен константе.

Благодарности

Автор выражает искреннюю благодарность своему научному руководителю A.M. Райгородскому за всестороннюю помощь при написании настоящей работы. Автор также сердечно благодарит своих родителей за их понимание и поддержку.

Работы автора по теме диссертации

[1] В.П. Филимонов, О покрытии плоских множеств, Математический Сборник. 2010. Т. 201. N8. С. 127- 160.

[2] В.П. Филимонов, Коды деления и теорема о площадях, Доклады Академии Наук. 2009. Т. 426. N2. С. 173 - 176.

[3] В.П. Филимонов, Теорема о малых отклонениях для кодов деления, Доклады Академии Наук. 2010. Т. 431. N5. С. 593 - 597.

[4] В.П. Филимонов, Теорема о рациональной периодичности для кодов деления, Доклады Академии Наук. 2010. Т. 434. N2. С. 168 - 172.

[5] В.П. Филимонов, Теорема о вещественной периодичости для кодов деления, Доклады Академии Наук. 2011. Т. 436. N4. С. 452 - 457.

Напечатано с готового оригинал-макета

Подписано в печать 20.03.2013 г. Формат 60x90 1/16. Усл.печл. 1,0. Тираж 100 экз. Заказ 075.

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от01.12.99 г. 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 527 к. Тел. 8(495)939-3890/91. Тел./факс 8(495)939-3891.

Московский Физико-Технический Институт Факультет Инноваций и Высоких Технологий

На правах рукописи

04201356315

Филимонов Владислав Павлович О ПОКРЫТИЯХ МНОЖЕСТВ В ЕВКЛИДОВЫХ ПРОСТРАНСТВАХ 01.01.09 — дискретная математика и математическая кибернетика

Диссертация на соискание ученой степени кандидата физико-математических наук

Научный руководитель — д.ф.-м.н. А.М. Райгородский

Москва, 2013

Оглавление

Введение 4

1 Оценки в М2 10

1.1 Формулировки результатов.....................10

1.2 Доказательства............................11

1.3 Комментарии.............................28

1.4 Таблица результатов..........................37

2 Оценки в Мт 39

2.1 Оценки снизу в М3...........................40

2.1.1 Метод расслоения ......................40

2.1.2 Получение оценок ......................42

2.1.3 Таблица результатов.....................45

2.2 Оценки снизу вГ..........................53

2.2.1 Оценки Хеппеша.......................54

2.2.2 Обобщение оценок Хеппеша.................56

2.2.3 Применение метода расслоения...............58

2.3 Точные оценки сверху в Мт.....................62

2.3.1 Перестановочный многогранник ..............62

2.3.2 Получение оценок ......................63

2.4 Асимптотические оценки сверху в К771................66

2.4.1 Получение оценок.......................66

2.4.2 Асимптотика при ш —> оо...................67

2.4.3 Гипотеза об асимптотике (I™ при 1 ^ т ^ 5........68

2.4.4 Связь с теорией решетчатых покрытий...........69

2.5 Вспомогательные утверждения...................72

3 Асимптотические свойства кодов деления 78

3.1 Теорема о площадях..........................78

3.2 Теорема о малых отклонениях....................84

3.3 Теорема о рациональной периодичности..............90

3.4 Теорема о вещественной периодичности...............93

Теорема о пределе

Введение

Вступление

В данной работе будут изложены результаты, связанные с классической проблемой Борсука (см. [1], [2], [3], [4], [5], [6]) о разбиении множеств в Ет на части меньшего диаметра, с известной задачей Нелсона-Хадвигера (см. [2], [7], [8], [9], [10]) о хроматическом числе евклидова пространства, а также с задачей об оптимальных решётчатых покрытиях евклидовых пространств (см., например, [11] и [12]).

Проблема Борсука была сформулирована почти 80 лет назад, и в последние годы она стала одной из ключевых проблем в области комбинаторной геометрии и явилась источником возникновения множества новых идей и задач в рамках данного раздела науки. Она заключается в отыскании минимального числа частей меньшего диаметра, на которое может быть разбито произвольное ограниченное множество в пространстве. Из данной формулировки ясно, что проблема Борсука связана с известными задачами оптимальных разбиений, упаковок и покрытий множеств в различных пространствах. Данная взаимосвязь проясняется в работах таких ученых, как К.А. Рождерс (см. [13]), Р. Ранкин (см. [14]), Ж. Бургейн и Й. Линденштраусс (см. [15]) и многих других. Настоящая диссертация также посвящена исследованию задачи об оптимальных покрытиях множеств в евклидовых пространствах множествами меньшего диаметра, являющейся непосредственным обобщением проблемы Борсука,

Вторая проблема, непосредственно связанная с результатами нашей работы, принадлежит нескольким авторам, из которых наибольшую роль в ее становлении сыграли Э. Нелсон, П. Эрдеш и Г. Хадвигер. Проблема заключается в нахождении наименьшего количества цветов, необходимых для такой раскраски метрического пространства, при которой расстояние между произвольными двумя одноцветными точками не может равняться некоторому наперед заданному числу. Данной задаче также более 60 лет, и ее популярность огромна. При решении данной задачи была разработана техника, относящаяся к так называемым разбиениям Вороного и имеющая непосредственную

взаимосвязь со знаменитыми статьями Г. Батлера (см. [16]), П. Эрдеша и К.А. Рождерса (см. [17]), Д. Лармана и К.А. Рождерса (см. [18]) и многими другими.

Наконец, задача об оптимальных решетчатых покрытиях также имеет более чем 70-летнюю историю и тесно связана с таким разделом алгебры, как теория Диофантовых приближений и неравенств (см. [12], [19]).

Основные определения

Пусть Ф — произвольное ограниченное множество в Мт, п — натуральное число. Обозначим через точную нижнюю грань положительных вещественных чисел х, обладающих тем свойством, что Ф может быть полностью покрыто п множествами ФЬФ2,...,ФП, диаметры которых не превосходят х\

¿С(ф) =^{2;е1+:ФСФ1и...и Фп, Уг сНатФ; ^ х} .

Можно показать (см. [1]), что эта точная нижняя грань достижима, то есть что Ф может быть полностью покрыто п множествами, диаметры которых не превосходят а^(Ф).

Последовательности ¿/™(Ф) и е™(Ф) = ^/п • (элементы последова-

тельностей всюду будут нумероваться индексом п) называются соответственно кодом деления и нормированным кодом деления множества Ф.

Заметим, что для произвольного Ф С Кта последовательность с1™(Ф) является невозрастающей, поскольку в классе всех покрытий п+ 1 множеством существует подкласс, для которого Фп+1 = 0, совпадающий с классом всех покрытий п множествами.

Кроме того, легко убедиться, что для произвольного Ф С Мт существуют такие неотрицательные (а в случае, когда Ф содержит подмножество ненулевой жордановой меры, — положительные) константы С\ = С^Ф) и Сг = СгСФ), что для всех натуральных п справедливо неравенство С\ ^ е™(Ф) ^ С2, которое равносильно оценке ^ ^(Ф) ^ (см., например, [20]).

Цикл работ [60]—[63], а также третья глава диссертации посвящены доказательству теоремы о существовании предела нормированного кода деления произвольного ограниченного множества, замыкание которого измеримо по Жордану. Иными словами, для произвольного такого множества Ф С К771 в действительности существует единственая константа С = С(Ф), с которой

ип •

При этом, в силу теоремы о площадях, доказанной в работе [60], для произвольных ограниченных множеств Фх и Ф2 в Мт, замыкания которых из-

меримы по Жордану и имеют меры дх и /12 соответственно, причём ¡12 ф О, справедливо соотношение

С(ф2) V №'

Для произвольных натуральных пит рассмотрим величину

С = 8Щ>С(Ф)>

где супремум берётся по всем множествам Ф диаметра 1 в Мто. Заметим, что из невозрастания последовательности Ф) для произвольного Ф С Ет следует, что последовательности (1™ также не возрастают для всех т.

Получению точных значений и оценок сверху и снизу величин (I™ для различных пит посвящены первые две главы диссертации.

Очевидно, что для каждого п £ N произвольное множество единичного диаметра в Мт может быть покрыто п множествами, диаметры которых не превосходят с1™.

Значения с1™ не изменятся, если взять супремумы только по всем выпуклым и замкнутым множествам Ф диаметра 1. Действительно, если обозначить через [Ф] замыкание, а через сопу Ф выпуклую оболочку множества Ф, то сИат [сопуФ] = сНатФ и Ф С [сопуФ], поэтому с1™(Ф) ^ «¿™([сопуФ]).

Заметим также, что чуть более тонкие рассуждения показывают, что всякое множество диаметра 1 содержится в некотором множестве постоянной ширины I1 (см. [21]), и поэтому достаточно взять супремум лишь по выпуклым замкнутым множествам постоянной ширины 1 без изменения значений

Напомним, что универсальным покрывающим множеством (или универсальной покрышкой) называется такое множество Пто С Кт, что любое множество Ф С диаметра 1 может быть полностью накрыто 0,т (то есть в Мт существует такое множество О™, конгруэнтное что Ф С Од1). Аналогично, универсальной покрывающей системой называется такая система множеств Г2т = что произвольное множество Ф С Мто диаметра 1

может быть полностью накрыто одним из множеств П™. Здесь I — некоторый (возможно, бесконечный) набор индексов. Универсальное покрывающее множество является частным случаем универсальной покрывающей системы, когда I состоит из одного элемента. Подробнее об универсальных покрывающих множествах и системах см. в [22], [23].

Легко видеть, что, если Г2ТО = } 7 — универсальная покрывающая система, то для произвольного п £ N справедливо неравенство с1™ ^ эир

ае1

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

В частности, если — универсальное покрывающее множество, то сЩ ^ с/™(ГГг) для всех натуральных п.

Простейшим примером универсальной покрышки в Мт является т-мер-ный гиперкуб с единичной длиной стороны.

Кроме того, в 1901 году Юнг показал (см. [24]), что в Ш™ универсальной покрышкой является шар радиуса у/2т+2-

На плоскости и в трёхмерном пространстве известны также и другие универсальные покрышки.

В 1920 году Пал в своей работе [25] (см. также [5]) доказал, что правильный шестиугольник с длиной стороны является универсальной покрышкой на плоскости. Более того, можно убедиться, что от такого шестиугольника можно "отрезать" два треугольника с тем, чтобы полученный усеченный шестиугольник по-прежнему оставался универсальной покрышкой (см., например,

И).

Для трёхмерного пространства Хеппеш и Грюнбаум в 1957 году показали (см. [26], [27]), что правильный октаэдр с единичным расстоянием между противоположными гранями является универсальной покрышкой. Кроме того, усечённый окраэдр, от которого плоскостями, отстоящими от трёх плоскостей симметрии октаэдра на расстояние "отрезаны" три четырёхугольные пирамиды, также является универсальной покрышкой.

Наконец, в 1997 году Макеев (см. [23], [28]) построил ещё две универсальные покрышки — ромбододекаэдр, у которого расстояние между параллельными гранями равно 1, а также усечённый ромбододекаэдр, от которого отсечены три четырёхугольных пирамиды по такому же принципу, как и от октаэдра. Изображения и более подробные описания универсальных покрышек в трёхмерном пространстве можно найти в [3].

Универсальные покрышки и покрывающие системы являются весьма эффективным инструментом для получения верхних оценок величин (I™. Для получения нижних оценок автором в статье [64] был разработан также показавший себя эффективным метод расслоения, который мы более подробно опишем во второй главе диссертации.

Обзор известных результатов

Заметим, прежде всего, что на одномерной прямой задача об отыскании величин (¿п является тривиальной, поскольку универсальное покрывающее множество — единичный отрезок имеет единичных диаметр, откуда очевидным образом следует, что для произвольного натурального п справедливо

равенство

п

Получением асимптотических и точных оценок на двумерной плоскости занимался Ленд, отыскавший в работах [20], [29] точные значения

(]2 _ 1 И2 _ , 12 _ И2 _ ,2 _ 1 а1 — 1) "2 — 15 аз — 2 ' 4 ~~ ' 2 '

а также получивший оценки

2 7Г О 1

^ эт — , ^

5 ' ь " л/3 '

1 . ,о . 1 /2 /4 2тг

и асимптотические оценки

/ ' * +0(1)

12

Также в книге [30] упоминается оценка 4 ^ Наконец, в работе [31] доказаны оценки

п

2С05§

,2 1 ,2 у/2657 - 896л/3

-—-— « 0.3324.

Кроме того, что в работе [32] также были получены точные значения и оценки величин 4(Ф) при небольших значениях п для трёх различных множеств Ф — круга, квадрата и правильного треугольника.

Для случая трехмерного пространства в книге [5] и статье [33] получены оценки

4 > 4 ^ 0.9425.

Кроме того, в работе [34] найдены точные значения и получены оценки величин ^(б1) для малых п для единичной сферы 5, из которых очевидным образом получаются следующие оценки:

4 > уЦ-

Заметим, что в доказательстве теоремы ¿д в статье [34] мы обнаружили существенную ошибку, исправление которой как автору настоящей работы,

так и автору [34] не представляется возможным; таким образом, утверждение

теоремы <?9, а также следующее из него неравенство (і\ ^ нельзя считать справедливыми.

Для случая пространств большей размерности, в статье [35] показано, что для произвольного натурального т справедливо неравенство

^ < /4т2 + У8ш2 + 1-1

Наконец, заметим, что для произвольных натуральных пит справедлива оценка

С > (2)

В работе [20] данное утверждение доказано для случая т = 2 следующим образом. Среди всех измеримых множеств диаметра 1 на плоскости максимальную площадь имеет круг (см. [36]). Поэтому для произвольного натурального п суммарная площадь п множеств диаметра с^(-О) на плоскости (где В — круг единичного диаметра), с одной стороны, не меньше его площади а с другой — не превосходит ^ • (о^)2, откуда имеем с/2 ^ ^п(^) ^ Заметим, что при т > 1 неравенство (2) является строгим, поскольку очевидно, что единичный шар не может быть замощен непересекающимися шарами меньшего диаметра.

Приведенное выше рассуждение может быть проведено в пространстве произвольной размерности, поскольку, как показано, например, в [37], среди всех множеств диаметра 1 в 1КТО максимальный объём имеет т-мерный шар.

Заметим, однако, что можно было и вовсе обойтись без этого факта, поскольку очевидно, что множество максимального объема при заданном диаметре в существует, а потому рассуждение, аналогичное описанному выше, можно провести для этого множества максимального объёма безотносительно его формы и получить необходимую оценку (2).

Благодарности

Автор выражает искреннюю благодарность своему научному руководителю A.M. Райгородскому за всестороннюю помощь при написании настоящей работы. Автор также сердечно благодарит своих родителей за их понимание и поддержку.

Глава 1 Оценки в М2

В данной главе мы будем для простоты опускать верхний индекс, отвечающий за размерность пространства, при обозначении элементов последовательности <Й.

"п•

1.1 Формулировки результатов

Теорема 1. Выполнены следующие неравенства:

йпт ^ ¿п^т, Уп,т Є N (3)

(¿5 ^ 0.6020 ... (4)

(¿6 ^ у^ (2 - л/з) = 0.5577... (5)

бі8 К 0.4456 ... (6)

4^/32^ = 0.4201... (7)

7

¿10 ^ -7= = °-4041 • • • (8)

Юл/3 /3 — 1

¿12 ^ ^— = 0.3660 ... (9)

Теорема 2. Для каждого натурального п справедливо неравенство

2

9/с2 + 9/с + 1. п = 3/с + 1;

(1Пп) ^ —-= , где /(п) = < 9/с2 + 15А; + 7, п = 3/с + 2; (10)

п

л/з

9/с2 + 3/с + 1. п = 3/с.

Более того.

й

/(9)—3 — «88

— ^

9л/3

(11)

Теорема 3. Для всех натуральных п верно неравенство

2

¿3 п2 —Зп+1—3<5(т)

£

Зп - 2 '

(12)

где т - т(п) = 4п — Более того, при п = 14

О,

т ^ 0;

— 6, а ¿>(т) = ^ /с2, т = 2к — 1;

&0 + 1), т = 2/с.

^3п2-3п+1-3(£(то)+1) — <^526 ^

Зп - 2

0.05.

(13)

Теорема 4. Дал любого 0 < х ^ 1 справедливо неравенство ^ х, где

И

00е) = XI

/с=0

2тг

агссоэ 1 —

-ф),

причем, є{х)

2(\-кх) )

_ І 1, Ц] = 2п - 1,п Є М;

0, иначе.

(14)

Отметим, что асимптотически оценки теорем 2, 3 и 4 слабее (1). Однако для конечного числа небольших значений п, /(п) и д(а;) они оказываются лучше. В этом улучшении известной оценки (1) и заключается главный результат данной главы.

1.2 Доказательства

Доказательство теоремы 1.

Сначала докажем (3). С этой целью заметим, что для всех натуральных п и т и произвольного ограниченного множества Ф справедливо неравенство ¿пт{Ф) ^ апс1т(Ф).

Действительно, для любого £ > 0 существует такое покрытие

ФСФхи.-.иФш,

что сИатФг ^ <1т{Ф) + £ при каждом г ^ т. Поэтому

4т(Ф) < 4т(Ф1 и . . . и Фто) = 4+...+п(Ф1 и . . . и Фт) < ^ тахс?п(Фг) ^ (1п тахЛатФг ^ йп(^то(Ф) + е).

г г

Устремив £ к нулю, получаем требуемое неравенство. Для доказательства (3) осталось взять инфимумы обеих его частей по всем множествам диаметра 1.

Для доказательства (4), (5) и (6) нам потребуется новое универсальное покрывающее множество — усечённый шестиугольник а также универсальная покрывающая система из двух усечённых шестиугольников Оед и ^6,2-

Рис. 1.1: Универсальная покрышка и покрывающая система

Рассмотрим произвольное множество Ф единичного диаметра. Накроем его множеством Пб и проведём шесть прямых, которые перпендикулярны отрезкам, соединяющим центр шестиугольника со всеми его вершинами, и отстоят от центра на расстояние Эти прямые отсекают от Пе шесть треугольников. Очевидно, для каждой пары треугольников, содержащих противоположные вершины, хотя бы один из них не содержит внутренних точек Ф (поскольку расстояние между этими треугольниками равно 1). Назовём такой треугольник отсечённым.

Поскольку отсечённые треугольники всегда существуют (их по крайней мере три), очевидно, что Ф покрывается множеством Г^, изображённым на рисунке 1.1 слева. Также несложным перебором вариантов взаимного расположения отсечённых треугольников можно убедиться, что Ф покрывается одним из множеств, изображённых на рисунке 1.1 в центре и справа (отсечённые треугольники им не принадлежат). Обозначим их через Пбд и Г^.г-В силу произвольности Ф, множество Од — универсальное покрывающее, а {Пбд,Пб,2} ~~ универсальная покрывающая система.

Заметим, что каждый из отсечённых треугольников является равнобедренным с длиной боковой стороны 2(4= — |). Отношение последней величины к

длине стороны шестиугольника равно 2 — у/3 = ^ё ^ = 0.2679 .... Обозначим это число через Л.

Докажем (5). Для этого введём обозначение а = (2 — \/3) и убедимся,

что

тах{сг6(П6д),сг6(^6)2)} < о.

Сначала проверим, что ¿¿б(^бд) ^ Для этого построим покрытие Г2бд шестью множествами, диаметры которых не превосходят а.

В В, М,

F F2 МЬ

Рис. 1.2: Покрытие шестью множествами

Пусть Пед получается из правильного шестиугольника АВСБЕЕ с серединами сторон М\, . . . , Мб и центром О отсечением треугольников ВВ1В2, и Fi7\i72 (см. рис. 1.2). Отложим на лучах АО, СО, ЕО отрезки АХ, СУ, Е2 длины \ и проведём отрезки ОХ, ОУ, OZ. Далее, соединим каждую из точек X, У, X с двумя серединами сторон шестиугольника, как на рисунке. Тем самым, задано покрыт