Московский физико-технический институт

факультет инноваций и высоких технологий

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

Пономаренко Екатерина Игоревна

ПРОБЛЕМЫ БОРСУКА И НЕЛСОНА–ХАДВИГЕРА

В РАЦИОНАЛЬНЫХ ПРОСТРАНСТВАХ

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

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

Научный руководитель — д.ф.-м.н. А.М. Райгородский Москва, 2014 Оглавление Список основных обозначений.................................. 4 Введение........................................................ Глава 1 Верхняя оценка числа независимости графов 1.1 Теорема Франкла–Уилсона.................................. 1.2 Улучшение теоремы Франкла–Уилсона....................... 1.2.1 Формальное доказательство........................... Схема доказательства................................ Первый этап........................................ Второй этап......................................... Третий этап......................................... 1.2.2 Комментарии к доказательству....................... 1.3 Обобщение теоремы Франкла–Уилсона на случай (1, 0, 1)-векторов и ее улучшение............................................ 1.4 Приложения в задаче Нелсона–Эрдеша–Хадвигера............ Глава 2 Хроматическое число рационального пространства 2.1 Определение хроматического числа рационального пространства 2.2 Новая нижняя оценка хроматического числа рационального пространства с одним запрещенным расстоянием................. 2.3 Новая нижняя оценка хроматического числа рационального пространства с двумя запрещенными расстояниями............... 2.4 Хроматическое число аффинно-рационального пространства... Глава 3 Некоторые аналоги задачи Борсука 3.1 Задача Борсука для вещественного и рационального пространства...................................................... 3.2 Правильный аналог задачи Борсука для рационального пространства................................................. 3.3 Размерности контрпримеров................................ 3.3.1 Случай n 903 (n 946)............................ 3.3.2 Случай n [561, 757]................................. 3.4 Обобщение на случай метрики lp............................ Заключение..................................................... Список литературы............................................. Список основных обозначений N — множество натуральных чисел;

Q — множество рациональных чисел;

Q[x1,..., xn ] — пространство многочленов от n переменных с рациональными коэффициентами;

R — множество действительных чисел;

|A| — мощность конечного множества A;

[a] — целая часть числа a;

a|b — свойство “a делит b”, т.е. число a является делителем числа b;

(x, y) — евклидово скалярное произведение векторов x и y;

|x| — норма вектора x в евклидовом пространстве;

V (G) — множество вершин графа G;

E(G) — множество ребер графа G;

f (N ) = o(g(N )) — для любого числа c > 0 существует такое число N0, что для любого N > N0 выполнено неравенство |f (N )| c|g(N )|;

f (x) g(x) — функции асимптотически равны при x, то есть f (x) = g(x) · (1 + o(1));

r(x, y) — расстояние между точками x, y в метрике r;

I(X) — индикатор события X. То есть I(X) = 1 в случае, если X выполняется, и 0 — иначе;

a b( mod k) — a сравнимо с b по модулю k, то есть a и b дают одинаковые остатки при делении на k;

a b — a приближенно равно b с точностью до последнего разряда;

Cn — число сочетаний из n элементов по k.

Введение Данная работа состоит из трех глав. Первая глава посвящена улучшениям верхних оценок чисел независимости дистанционных графов. Во второй и третьей главе речь идет о некоторых рациональных аналогах классических комбинаторно-геометрических задач (о хроматическом числе и о числе Борсука).

Актуальность Диссертация посвящена изучению вопросов, лежащих на стыке нескольких областей. Впервые задачи, рассматриваемые в данной работе, возникли в рамках комбинаторной геометрии. Хотя это достаточно молодая область математики и даже сам термин “комбинаторная геометрия” появился только в середине прошлого века, сейчас это бурно развивающаяся дисциплина, которая своим развитием во многом обязана именно этим задачам. Разумеется, первые задачи комбинаторной геометрии были известны задолго до того, как появилась эта дисциплина: одним из первых задачами комбинаторной геометрии занимался еще И. Кеплер в начале XVII века.

Основными задачами

данной работы являются задача Борсука о разрезании тел в пространстве на части меньшего диаметра и задача Нелсона– Хадвигера о разбиении пространства на части без запрещенного расстояния (см. [1] — [16]). Для комбинаторной геометрии эти задачи действительно являются центральными. Так, гипотеза Борсука тесно связана с задачей об освещении тел (см. [1], [17] — [19]), с классической проблемой дискретной геометрии об упаковке шаров и других тел (см. [20] — [22]), с проблематикой геометрии чисел, с задачей Грюнбаума о покрытии тел шарами (см. [23] — [27]).

Со временем, методы связанные с изучением задач Борсука и Нелсона– Хадвигера, изначально сформулированные в комбинаторно-геометрических терминах, оказались исключительно полезными при решении проблем из других областей математики. Так один из наиболее результативных методов в решении указанных задач заключается в рассмотрении систем (0,1)-векторов.

Тем самым, возникают естественные приложения в теории кодирования — например, в задачах о равновесных кодах с запрещенными Хэмминговыми расстояниями (см. [28], [29]). В то же время (0,1)-векторы можно интерпретировать как ребра гиперграфов, что дает результаты при изучении их экстремальных свойств. Наконец вышеупомянутые задачи тесно связаны и с обычными графами: с проблемой Борсука связано понятие графа диаметров, а с задачей Нелсона–Хадвигера — понятие дистанционного графа. С одной стороны, идеи и термины теории графов помогают решать эти задачи, с другой стороны, получаемые результаты имеют значение для самой теории графов.

В следующих параграфах мы подробно остановимся на истории проблемы Борсука и Нелсона–Хадвигера.

Проблема Борсука В 1933 году К. Борсук (cм. [30]) сформулировал следующий вопрос: верно ли, что всякое ограниченное неодноточечное множество в Rd может быть представлено в виде объединения своих частей меньшего диаметра, причем так, чтобы количество этих частей не превышало d + 1? Предположение о справедливости положительного ответа на этот вопрос получило впоследствии название “гипотеза Борсука”.

К решению этой задачи подходили с разных сторон. В первую очередь справедливость этой гипотезы проверяли в “малых” размерностях. Конечно, для d = 1 утверждение сразу следует из того, что отрезок длины 1 разбивается на два отрезка длины 1. В случае размерности d = 2 сам К. Борсук показал, что любое множество диаметра 1 разбивается на три части меньшего диаметра, и именно этот результат привел его к формулировке общей гипотезы. В доказательстве Борсука использовалась следующая лемма: каждое множество диаметра D может быть покрыто правильным шестиугольником, у которого расстояния между противоположными сторонами также равны D (см. [1], [30] и [31]).

В размерности d = 3 ситуация усложняется. Впервые о доказательстве гипотезы Борсука в этой размерности было заявлено в кратком сообщении Перкала (см. [33]), но полное доказательство так и не было опубликовано.

Чуть позже Эгглстон (см. [32]) предложил неэлементарное доказательство гипотезы. В последствии было предложено несколько элементарных доказательств. В 1957 году Б. Грюнбаум (см. [23]) доказал, что любое трехмерное множество диаметра D можно покрыть некоторым усеченным октаэдром, который допускает разбиение на 4 части диаметра меньше D. В том же году А. Хеппеш (см. [34]) нашел другое элементарное решение трехмерной проблемы.

Начиная с размерности 4 проблема Борсука до сих пор полностью не решена. Однако, хочется отметить, что свой вклад в изучение проблемы Борсука в “малых” размерностях, помимо упомянутых авторов, внесли В.В. Макеев (см. [35] и [36]), А.Л. Евдокимов, Р. Ревес (совместно с А. Хеппешем — [37]), П. Кацарова-Каранова (см. [38]) и др.

Поскольку окончательного результата в проблеме Борсука получить не удавалось, были предприняты попытки решить проблему в каких-нибудь специальных случаях. В 1946 году Г. Хадвигер доказал, что всякое d-мерное множество с гладкой границей может быть разбито на d + 1 часть меньшего диаметра (см. [39]). Доказательство теоремы Хадвигера и её небольшое усиление содержится в [39] и в книге [1]. В 1971 году К.А. Роджерс (см. [40]) предложил принципиально другой класс множеств, для каждого их которых верна гипотеза Борсука. А именно гипотеза Борсука справедлива для множеств, которые инвариантны под действием группы симметрий правильного d-мерного симплекса.

С гипотезой Борсука связано понятие числа Борсука. Пусть f — произвольное натуральное число такое, что всякое ограниченное точечное множество ненулевого диаметра Rd может быть разбито на f частей меньшего диаметра. Определим f (d) как число, минимальное среди всех таких f. В этих терминах гипотеза Борсука равносильна равенству f (d) = d + 1.

Нетрудно видеть, что величина f (d) всегда конечна. В самом деле, произвольное множество диаметра D содержится в d-мерном кубе с ребром D, и нужно лишь разбить этот куб на столь мелкие кубики, что диаметр каждого из них будет меньше D. Этот факт был впервые замечен Х. Ленцем в году (см. [26]). Из него вытекает оценка f (d) < ( d+1)d. Развитие идей относительно числа Борсука вылилось в борьбу за усиление оценок с точки зрения уже не конкретных размерностей, а с точки зрения растущей размерности.

Так, первым эту верхнюю оценку слегка улучшил К. Борсук (см. [41]) в году. А в 1982 году М. Лассак (см. [42]) показал, что f (d) 2d1 + 1. В малых размерностях эта оценка является наилучшей из известных. Например, при d = 4 оценка f (4) 9 по-прежнему является рекордной. При больших d наилучшую известную оценку в 1988 году сформулировал О. Шрамм (см.

[43]):

Аналогичный результат установили в работе [27] Ж. Бургейн и Й. Линденштраусс. Таким образом, для величины f (d) есть только экспоненциальные верхние оценки.

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

Еще К.А. Роджерс в своей статье 1971 года о разбиении симметричных множеств (см. [40]) писал, что получил основной результат этой статьи в попытках опровергнуть гипотезу Борсука. А 10 лет спустя П. Эрдеш предположил, что можно построить контрпример к гипотезе Борсука с помощью некоторых конечных точечных конфигураций в Rd (см. [44]). Аналогичное предположение высказал и Д. Ларман (см. [45] и [46]).

Наконец, в 1993 году гипотеза Борсука была опровергнута. Дж. Кан и Г. Калаи с помощью результатов работы П. Франкла и Р. Уилсона 1981 года (см. [47]) построили контрпримеры к гипотезе во всех размерностях d > (см. [48]). Из их конструкции вытекала оценка f (d) > (1.203... + o(1)) d. Ввиду этой оценки результаты Шрамма и Бургейна–Линденштраусса перестают казаться далекими от истины. В дальнейшем были предприняты достаточно многочисленные попытки понижения размерности контрпримера и, одновременно, усиления нижней оценки величины f (d). Так, в 1994 году А. Нилли предложил некоторую модификацию метода Кана и Калаи и в результате нашел отрицательное решение проблемы К. Борсука при d > 946 (см. [49]).

Кроме того, работа Нилли была краткой и, в отличие от работы Дж. Кана и Г. Калаи, полностью замкнутой в себе. Далее, в 1997 году Й. Грэй и Б. Вайсбах построили, за счет небольшого уточнения метода А. Нилли, контрпримеры для всех d > 903 (см. [50]). В том же году А.М. Райгородский (см. [51]) обнаружил иную модификацию подхода Нилли, которая позволила ему опровергнуть гипотезу Борсука уже при d = 561. В 2000 году Б. Вайсбах слегка видоизменил конструкцию из [51], сумев тем самым уменьшить размерность контрпримера еще на единицу (см. [52]). После этого А. Хинрихс предложил новую конструкцию, с помощью которой удалось еще сильнее уменьшить размерность контрпримера — до d = 323. В 2002 году Пихурко уменьшил эту размерность на 1 (см [54]). В 2003 году Хинрихс вернулся к задаче и доказал результат для d 298 (см [55]). Этот результат держался 10 лет и в году А.В. Бондаренко сумел опровергнуть гипотезу при всех d 65 (см [56]).

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

Авторы публикации Год Ссылка Размерность контрпримера к гипотезе n Помимо попыток понизить размерность контрпримера, предпринимались попытки улучшить асимптотические оценки величины f (d). Однако, известен только один результат, улучшающий оценку Дж. Кана и Г. Калаи, а именно А.М. Райгородский с помощью одного обобщения метода А. Нилли сумел доказать что f (d) > (2/ 3 + o(1)) Как говорилось выше, задачи комбинаторной геометрии часто связаны с теорией графов. Это касается, в частности, проблемы Борсука. В теории графов большое внимание уделяется хроматическому числу (G) — минимальному числу цветов, в которые можно так покрасить некоторый граф G, чтобы концы любого ребра имели разные цвета. Связь проблемы Борсука с хроматическими числами графов реализуется через граф диаметров. Граф диаметров для некоторого тела A — это такой граф G(A), вершинами которого являются все точки, принадлежащие A, а ребрами соединены те из них, которые отстоят друг от друга на расстояние, равное диаметру тела A.

Очевидно, что для того, чтобы разбить A на части меньшего диаметра, понадобится число частей, не меньшее, чем (G(A)) — хроматическое число графа G(A). Таким образом, графы диаметров позволяют строить нижние оценки числа Борсука. Важно отметить, что именно эта идея позволила в свое время Дж. Кану и Г. Калаи опровергнуть гипотезу Борсука.

Хроматическое число пространства Другой классической задачей комбинаторной геометрии является задача о хроматическом числе пространства. В 1944 году Г. Хадвигер опубликовал работу [59], в которой доказал, что если евклидово пространство Rd покрыто d + 1 замкнутым множеством, то хотя бы в одном из этих множеств все неотрицательные вещественные числа реализуются как расстояния между парами точек этого множества. В 1950 году Э. Нелсон поставил очень близкую задачу о том, каково минимальное число цветов, в которые необходимо так раскрасить все евклидово пространство Rd, чтобы точки, расстояние между которыми в точности равно единице, оказались раскрашенными в разные цвета. Это число получило название хроматического числа пространства Rd. Его принято обозначать (Rd ).

Изучение величины (Rd ) в некотором смысле созвучно изучению числа Борсука, которое мы обсуждали выше. Так, для хроматического числа тоже рассматривались малые размерности, верхние и нижние оценки. К сожалению, в отличие от числа Борсука, значения хроматического числа не удалось найти даже для размерности d = 2 (для размерности d = 1 ответ очевиден:

(R1 ) = 2). Известно лишь, что Обе эти оценки были доказаны в 1961 году — нижняя Л. Мозером и В. Мозером, а верхняя Г. Хадвигером (см. [60] и [61]), и никаких принципиальных улучшений с тех пор найдено не было. При d = 3 известно, что Оценки были доказаны в 2002 году — нижняя О. Нечуштаном (см. [62]), а верхняя Д. Кулсоном (см. [63]).

По-видимому, первым, кто получил нетривиальную нижнюю оценку для хроматического числа вещественного пространства в произвольной размерности d, был Д.Е. Райский, доказавший, что (Rd ) d+2 (см. [64]). Результат этот Райский получил путем прямого обобщения идей Л. Мозера и В. Мозера (см. [60]). Далее, в 1972 году Д. Ларман и К.А. Роджерс (см. [65]) установили оценку (Rd ) c1 (log d)3, где c1 > 0 — абсолютная константа. П. Эрдеш и В. Шош заметили, что если сочетать идеи Лармана и Роджерса с техникой из работ Ж. Надя, то получится еще лучшая оценка (Rd ) (1 + o(1)) d6.

В дальнейшем результаты Д. Лармана, К.А. Роджерса, В. Шош и П. Эрдеша неоднократно улучшались. Сперва, в 1978 году сам Д. Ларман показал, что (Rd ) (d1)(d2)(d3)/178200 (см. [66]). Затем, в 1980 году П. Франкл получил неравенство (Rd ) > dt, где t любое, а d d(t) (см. [67]). Прорыв был совершен в 1981 году в замечательной работе П. Франкла и Р. Уилсона, в той самой работе, которая цитировалась в связи с проблемой Борсука и контрпримером Дж. Кана и Г. Калаи (см. [47]). В этой работе авторы доказали гипотезу П. Эрдеша о том, что величина (Rd ) растет экспоненциально.

А именно, они установили неравенство (Rd ) (1.207... + o(1))d. При этом еще в 1972 году Д. Ларман и К.А. Роджерс с помощью Г.Л. Батлера и метода П. Эрдеша и К.А. Роджерса доказали, что (Rd ) (3 + o(1))d (см. [65], [68] и [69]).

Наконец, в 2000 году А.М. Райгородский доказал теорему, которая приводит к оценке (Rd ) (1.239... + o(1))d (см. [70]).

Как и проблема Борсука, задача об отыскании хроматического числа пространства, называемая также задачей Нелсона–Хадвигера, связана с графами. В некотором смысле, для этой задачи связь даже более очевидна, ведь достаточно заменить пространство Rd бесконечным графом Gd, вершинами которого являются все точки Rd, а ребрами соединены те и только те из них, расстояние между которыми равно 1: очевидно, (Gd ) = (Rd ). С другой стороны, для содержательного применения теории графов к задаче об отыскании хроматического числа пространства важен вопрос о том, достаточно ли рассмотреть только конечные дистанционные графы (то есть конечные подграфы вышеупомянутого графа Gd ). И ответ на этот вопрос неоднозначен: если принимать аксиому выбора, то согласно теореме Эрдеша–де Брейна (см. [71]), max (G) = (Rd ), где максимум берется по всем конечным подграфам графа Gd. Если же не принимать аксиому выбора, то, возможно, этот максимум дает лишь нижнюю оценку хроматического числа пространства.

Теореме Франкла–Уилсона, благодаря которой был совершен прорыв в обеих описанных задачах комбинаторной геометрии, посвящена первая глава настоящей работы. Улучшения этой теоремы, полученные в данной работе, приводят к неожиданным следствиям в задаче о хроматическом числе (см.

раздел 1.4). А именно, новые оценки позволяют в свою очередь улучшить оценки хроматического числа для дистанционных графов определенного вида.

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

Здесь снова проявляется связь этих задач с теорией графов: многие вариации формулируется именно в терминах графов. Так, например, в 1976 году (см.

[72]) М. Бенда и М. Перлес дали общее определение хроматического числа метрического пространства.

Пусть (X, r) — некоторое метрическое пространство, a — произвольное неотрицательное вещественное число. Рассмотрим граф Ga, множество вершин которого совпадает со всем пространством X, а множество ребер состоит из всех возможных пар различных точек x, y X таких, что r(x, y) = a.

Тогда хроматическим числом метрического пространства X с запрещенным (или критическим) расстоянием a называется величина (X, a) = (Ga ).

Иными словами, хроматическое число метрического пространства — это минимальное число цветов, в которые можно так раскрасить точки пространства, что точки, отстоящие друг от друга на расстояние a, окажутся раскрашенными в различные цвета. В случае, когда в роли метрического пространства (X, r) выступает пространство Rd, снабженное стандартной евклидовой метрикой, мы имеем дело с классической задачей о нахождении хроматического числа евклидова пространства. Если же в роли (X, r) взять пространство Qd с евклидовой метрикой, то можно говорить о так называемом хроматическом числе рационального пространства — величине (Qd ).

Изучению вопросов, связанных с хроматическим числом рационального пространства, посвящена вторая глава настоящей работы. Для хроматического числа рационального пространства еще М. Бенда и М. Перлес получили точные значения в малых размерностях. На удивление в рациональном случае посчитать точное значение возможно для гораздо большего числа размерностей (в вещественном случае точное значение хроматического числа известно только для d = 1). Известно, что (Q1 ) = (Q2 ) = (Q3 ) = 2, (Q4 ) = 4 (см. [72], [73]). Оценками для размерностей 5 d 9 занимались К.Б. Чилакамарри, М. Манн, Й. 3акс, А.М. Райгородский, Й. Цибулька.

К сожалению, в общем случае нет никаких верхних оценок, лучших, чем те, что были получены в 1972 году Д. Ларманом и К.А. Роджерсом для случая (Rd ): очевидно, что всегда (Qd ) (Rd ) (3 + o(1))d. Экспоненциальные нижние оценки заведомо следуют из все той же работы П. Франкла и Р. Уилсона,(см. [47] и [13]): (Qd ) (1.139... + o(1))d. Эта оценка была улучшена А.М. Райгородским: в своей работе [4] он доказал, что (Qd ) (1.173... + o(1))d. В настоящей работе получено новое улучшение этой оценки (см. раздел 2.2).

Опишем еще одно обобщение понятия хроматического числа. Пусть (X, r) – некоторое метрическое пространство, а a1,..., ak — произвольный набор из k неотрицательных вещественных чисел. Рассмотрим граф Ga1,...,ak, множество вершин которого совпадает со всем пространством X, а множество ребер состоит из всех возможных пар различных точек x, y X таких, что r(x, y) {a1,..., ak }. Назовем хроматическим числом метрического пространства с запрещенным (или критическим) набором расстояний a1,..., ak величину (X, a1,..., ak ) = (Ga1,...,ak ).

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

Для гипотезы Борсука рациональные аналоги ранее не рассматривались.

Возможно это связано с тем, что прямолинейная замена одного рассматриваемого пространства другим не дает принципиально новой задачи, как это получается в случае с хроматическим числом (подробнее об этом см. в разделе 3.1). Правильные аналоги числа Борсука строятся за счет перехода к терминам графов и хроматических чисел, а также за счет использования понятия аффинной размерности. Для построенных двух аналогов ставятся такие же вопросы как и для классического хроматического числа: в третьей главе настоящей работы изучаются асимптотические нижние оценки и минимальные размерности контрпримеров. Кроме того, для этих аналогов числа Борсука рассматривается задача в пространствах c метриками lp, где p N.

Благодарности. Автор признателен профессору А.М. Райгородскому за постановку задач и неоценимую помощь в работе. Автор также благодарен А.Б. Купавскому за полезные замечания.

Глава Верхняя оценка числа независимости графов В этой главе мы рассмотрим верхнюю оценку числа независимости графов, полученную П. Франклом и Р.М. Уилсоном, и ее улучшение. В разделе 1. мы рассмотрим обобщение результата Франкла–Уилсона на случай (-1,0,1) векторов, а в разделе 1.4 — приложение полученных теорем к задаче Нелсона– Эрдеша–Хадвигера.

1.1 Теорема Франкла–Уилсона В 1981 году в своей работе [47], ставшей классической, П. Франкл и Р.М.

Уилсон доказали следующую теорему.

Теорема 1.1.1. Пусть H = (V, E) — k-однородный гиперграф (т.е. в каждом его ребре ровно k вершин) на n вершинах, причем для любых F1, F2 E выполнено |F1 F2 | = l и k l — степень простого числа, которую мы обозначим q. Тогда имеют место два случая:

1. если 2l < k, то 2. если 2l Теорема 1.1.1 является одним из самых ярких достижений в современной экстремальной комбинаторике. Во-первых, именно с нее, по сути, началось развитие нового на тот момент мощного линейно-алгебраического метода (см.

[5], [13]). Во-вторых, она дает практически неулучшаемую оценку числа ребер гиперграфа с запрещенным пересечением (см. [5]) или, что то же самое, оценку мощности кода с запрещенным расстоянием (см. [28]). В-третьих, из нее вытекают исторически первые экспоненциальные нижние оценки хроматического числа пространства (см. [4], [5], [7], [47]). В-четвертых, на ее основе были построены и первые контрпримеры к известной гипотезе Борсука о разбиении множеств на части меньшего диаметра (см. [4], [5], [8], [9], [48], [51], [58], [74], [75]).

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

1.2 Улучшение теоремы Франкла–Уилсона Прежде всего отметим, что в теореме 1.1.1 неявно предполагается выполn ненным неравенство k 2. Иначе эта теорема допускает чисто технические уточнения, о которых мы не станем здесь говорить. В дальнейшем для пущей строгости изложения мы будем явно упоминать это ограничение. Также подчеркнем, что мы включаем ноль в множество натуральных чисел N. Справедлива следующая теорема, опубликованная автором в статьях [96], [97]:

Теорема 1.2.1. Пусть H = (V, E) — k-однородный гиперграф на n вершидля любых F1, F2 E выполнено |F1 F2 | = l, 2l и q = k l — степень простого числа. Положим d = 2l k + 1. Пусть, далее, d1, d2 N таковы, что d1 + d2 = d. Положим n1 = n d1, k1 = k d1.

Определим натуральное число r из соотношения Тогда В свою очередь, улучшение, которое дает теорема 1.2.1, мы иллюстрируем на рисунке 1.1. Здесь изображены четыре пары кривых. Они получены в предположении, что при n выполнено k k n (с k = 0.33, k = 0.45, k = 0.57, k = 0.69 слева направо) и l l n (где l откладывается по оси абсцисс и меняется в пределах от k /2 до k ). Верхняя кривая отражает значения оценки Франкла–Уилсона, нижняя — значения новой оценки. Видно, что разница существенная.

Формальное доказательство теоремы мы изложим в параграфе 1.2.1. Однако из этого доказательства будет не ясно, на чем основан выбор параметров в теореме. Поэтому в параграфе 1.2.2 мы приведем соответствующие комментарии.

1.2.1 Формальное доказательство Схема доказательства Для удобства разобьем рассуждение на три этапа. А именно, пусть дан гиперграф H = (V, E), удовлетворяющий условию теоремы, и n, k, l, q, d, d1, d2, n1, k1, r — те же самые числа, что и в формулировке. На первом этапе мы покажем, что в H есть такой подгиперграф H1 = (V, E1 ) (множество вершин не изменится), что каждые два его ребра пересекаются не менее, чем по d1, вершинам и число его ребер “не сильно” меньше числа ребер исходного гиперграфа H. На втором этапе мы увеличим мощности попарных пересечений, т.е. выделим, в свою очередь, из H1 такой подгиперграф H2 = (V, E2 ) (множество вершин снова не изменится), что каждые два его ребра пересекаются не менее, чем по d = d1 + d2, вершинам и число его ребер “не сильно” меньше числа ребер гиперграфа H1. На третьем этапе мы воспользуемся условием теоремы, в котором говорится об отсутствии пар ребер в E (а стало быть, и пар ребер в E2 E1 E), пересекающихся по l вершинам. В результате мы получим верхнюю оценку мощности множества E2. Но, поскольку E1 не сильно больше E2, а E не сильно больше E1, то в итоге и возникнет верхняя оценка мощности E.

Первый этап Пусть D1 — совокупность всех d1 -элементных подмножеств множества V, так что |D1 | = Cn1. Для любого свойства A обозначим I(A) индикатор этого свойства. Рассмотрим сумму Разумеется, она равна |E| · Ck 1. В то же время Следовательно, существует множество D1 D1, которое содержится в не менее x1 ребрах из E, где Обозначим E1 множество тех ребер из E, которые содержат D1. Таким образом, |E1 | x1, т.е. мощность E1, как и было обещано, не сильно меньше мощности E. При этом в E1 любые два ребра пересекаются по D1, а значит, мощности пересечений действительно не меньше d1.

Первый этап завершен.

Второй этап Рассмотрим все множества вида F \ D1, где F E1. Они содержатся во множестве V1 = V \ D1 мощности n1 = n d1. При этом сами они имеют мощность k1 = k d1. Обозначим совокупность этих множеств E1.

Пусть D2 — совокупность всех (d2 + 2r)-элементных подмножеств множества V1. Их Cn1 +2r штук. Изучим сумму Разумеется, она равна Следовательно, найдется множество D2 D2, с которым по d2 + r элементам пересекается не менее x2 ребер из E1, где Обозначим E2 множество этих ребер. Понятно, что внутри D2 любые два ребра из E2 пересекаются не менее, чем по d2, вершинам.

Пусть E2 E1 — это совокупность множеств вида D1 F, где F E2.

Очевидно, мощности попарных пересечений ребер из E2 не меньше d = d1 +d2.

Кроме того, т.е., как мы и обещали, мощность E2 не сильно меньше мощности E1.

Третий этап Итак, у нас есть совокупность E2 подмножеств n-элементного множества.

Каждое множество в E2 имеет мощность k, и любые два множества из E пересекаются по d и более элементам. При этом никакие два множества из E2 не пересекаются по l элементам.

Предположим, мы доказали, что Тогда и теорема доказана.

Покажем, стало быть, что верно неравенство (1.1). Каждому ребру из E сопоставим двоичный вектор, у которого единицы стоят на позициях, отвечающих вершинам ребра. Первые d1 координат каждого такого вектора по построению равны 1. И только оставшиеся n1 координат являются переменными. При этом скалярное произведение любых двух векторов не меньше d, не больше k и не равно l. Иными словами, скалярное произведение сравнимо с k по модулю q тогда и только тогда, когда оно равно k (перемножаемые векторы совпадают), ведь k q = l, а k 2q = 2l k < d.

Пусть x1,..., xs — все векторы, построенные по ребрам из E2. Поставим каждому из них — вектору xi с i {1,..., s} — в соответствие некоторый многочлен Fxi. А именно, пусть I — множество, полученное из множества {0, 1,..., q 1} удалением вычета числа k по модулю q. Пусть, далее, q = p, а — степень, в которой простое число p входит в каноническое разложение Положим Многочлен рассматривается как элемент пространства Q[yd+1,..., yn ], т.е. это многочлен от n1 переменных, а Рассмотрим невырожденную линейную комбинацию Если она равна нулю в Q[yd+1,..., yn ], то и для любого y вида (1.2) Нетрудно проверить (см. [5] и [4]), что в нашем случае всегда Fxi (y) Z.

Поэтому можно считать, что все коэффициенты в (1.3) целые и что, более того, один из этих коэффициентов не делится на p.

Подставим в (1.3) в качестве аргумента y = xi с произвольным i. С одной стороны, С другой стороны, легко проверить, что поскольку при j = i выполнено (xj, xi ) k (mod q), то Выходит, что ci 0 (mod p) для любого i. Противоречие с невырожденностью, т.е. многочлены линейно независимы над Q.

Преобразуем каждый из многочленов следующим образом. Запишем многочлен в виде линейной комбинации одночленов, и в каждом одночлене заменим сомножители вида y, 1, сомножителями y. Например, одночлен yd+1 yd+5 yn превратится в yd+1 yd+5 yn. Новые многочлены как функции от векторов вида (1.2) тождественно равны исходным многочленам (очевидно, что 0 и 1 не нужно возводить в степени; все равно 0 и 1 останутся неизменными).

Следовательно, новые многочлены также линейно независимы над Q. Это многочлены степени q 1 от n1 переменных, и каждая переменная входит в них в степени 0 или 1. Все такие многочлены заведомо порождаются базисом из Cn1 элементов. Таким образом, и теорема доказана.

1.2.2 Комментарии к доказательству На первых двух этапах доказательства мы нашли гиперграф, у которого мощности попарных пересечений ребер не меньше d. Это было нужно, конечно, для того, чтобы на третьем этапе удалось применить технику полиномов. Однако мы зачем-то действовали в два этапа. Сперва мы просто фиксировали вершины, а потом добились более хитрого зацепления ребер.

Дело в том, что с точки зрения выбора гиперграфа, у которого велики мощности попарных пересечений ребер, второй этап оптимальнее. В его рамках мы фактически опираемся на теорему Алсведе–Хачатряна (см. [76], [77]), в которой найден максимум числа ребер в гиперграфе с данной нижней границей для мощностей пересечения ребер. В частности, величина r — это величина, возникающая именно в той теореме. Почему же тогда сразу не воспользоваться оптимальной конструкцией Алсведе–Хачатряна? А суть в том, что на первом этапе, фиксируя вершины, мы понижаем размерность пространства полиномов, которая служит итоговой оценкой на третьем этапе. И априори не ясно, что выгоднее: взять чуть более мощную совокупность ребер (как на втором этапе) или взять чуть менее мощную совокупность, улучшив при этом финальную оценку с полиномами.

1.3 Обобщение теоремы Франкла–Уилсона на случай (1, 0, 1)-векторов и ее улучшение Задача об отыскании верхних оценок числа ребер в однородном гиперграфе с запрещенными пересечениями исключительно важна не только с точки зрения самой теории гиперграфов, но и с точки зрения комбинаторной геометрии (см. [4], [6], [7], [8], [9], [48], [51], [58], [70], [74], [75]), и с точки зрения теории кодирования (см. [28]). В последних двух случаях говорят обычно о (0,1)-векторах с запрещенными скалярными произведениями или, что то же самое, о равновесных кодах с запрещенными Хэмминговыми расстояниями.

Мы же поставим аналогичную задачу для (1, 0, 1)-векторов и сформулируем аналоги теорем 1.1.1 и 1.2.1.

Пусть n — натуральное число и k1, k0, k1 — натуральные числа, в сумме дающие n. Пусть Разумеется, |Vn (k1, k0, k1 )| = k1 !k0 !k1 !. И, в частности, при k1 = 0, k1 = k имеем совокупность (0,1)-векторов веса k или, что то же самое, совокупность ребер полного k-однородного гиперграфа на n вершинах. В общем случае работаем с (1, 0, 1)-векторами, т.е. с троичными кодами в терминах теории кодирования.

Пусть теперь t — произвольное натуральное число. Нас будет интересовать величина т.е. максимальное количество векторов, которым запрещено иметь скалярные произведения, равные t. В такой постановке задача является обобщением именно комбинаторно-геометрической, а не теоретико-кодовой проблемы, т.к. скалярное произведение отвечает за евклидово, а не Хэммингово расстояние, которые для (0,1)-векторов по сути не различались. О приложениях в комбинаторной геометрии мы поговорим в четвертом разделе.

Очень много работ посвящено нижним оценкам величины m(n, k1, k0, k1, t) (см. [78]–[82]), и их результатами мы еще воспользуемся, несмотря на то, что нынешняя наша цель — верхние оценки. Верхние же оценки изучены довольно плохо, и есть лишь одна теорема, служащая обобщением пункта 1 теоремы 1.1.1 и приведенная явно в книге [5]. Мы выпишем ее ниже для наиболее показательного случая (см. [5]), когда k1 + k1 n и k1 k1.

Теорема 1.3.1. Пусть n, k1, k0, k1, t таковы, что k1 + k1 2, k1 k1, разность k1 + k1 t является степенью простого числа (обозначим ее q = pa ) и k1 + k1 2q < 2k1. Тогда где Теорема 1.3.1 ничего не говорит о ситуации, когда k1 + k1 2q 2k1.

Именно поэтому мы и говорим о том, что теорема 1.3.1 служит обобщением пункта 1 теоремы 1.1.1. Новая теорема 1.3.2 закрывает этот пробел.

Теорема 1.3.2 Пусть n, k1, k0, k1, t таковы, что k1 + k1 2, k1 k1, разность k1 + k1 t является степенью простого числа (обозначим ее причем все элементы вектора и матрицы — натуральные числа, m1 + m2 + m3 = n, m1,1 + m0,1 + m1,1 = m1, m1,2 + m0,2 + m1,2 = m2, и выполнено еще одно условие, для формулировки которого нам потребуются дополнительные обозначения и термины. А именно, пусть множество {1,..., n} представлено в виде объединения трех непересекающихся частей M1, M2, M3, мощности которых равны m1, m2, m3 соответственно.

Скажем, что вектор x = (x1,..., xn ) Vn (k1, k0, k1 ) удовлетворяет разбиению T (M1, M2, M3 ), если Еще одно условие, которому подчиняются параметры m, M, состоит в том, что у любых двух векторов x, y, удовлетворяющих одному и тому же разбиению, скалярное произведение не меньше d. Тогда m1,1 !m1,2 !m1,3 ! m0,1 !m0,2 !m0,3 ! m1,1 !m1,2 !m1,3 ! i j где Доказательство.

Пусть фиксированы числа n, k1, k0, k1, t, q, p, a, d, удовлетворяющие условию теоремы, а также вектор m и матрица M. Пусть T — множество всех разбиений T (M1, M2, M3 ). Разумеется, |T | = m1 !m2 !m3 !. Обозначим I(A) инn!

дикатор того или иного свойства A. Пусть, наконец, W Vn (k1, k0, k1 ) — произвольное множество без скалярного произведения t. Рассмотрим величину При текущем порядке суммирования видно, что Значит, если переставить суммы местами, то получится, что существует разбиение T (M1, M2, M3 ) T, которому удовлетворяет не менее векторов из W. Обозначим W множество всех таких векторов. В нем скалярные произведения любых двух векторов больше либо равны d и не равны t. При этом максимальное скалярное произведение векторов из W — это скалярный квадрат любого из них, т.е. k1 + k1. Таким образом, скалярное произведение любых двух различных векторов из W не сравнимо с k1 + k по модулю q. Воспользуемся этим для получения верхней оценки мощности Пусть W = {x1,..., xs }. Поставим каждому вектору xi с i {1,..., s} в соответствие некоторый многочлен Fxi. А именно, пусть I — множество, полученное из множества {0, 1,..., q 1} удалением вычета числа k1 + k по модулю q. Пусть, далее, b — степень, в которой простое число p входит в каноническое разложение числа Положим Многочлен рассматривается как элемент пространства Q[y1,..., yn ], т.е. это многочлен от n переменных, а Рассмотрим невырожденную линейную комбинацию Если она равна нулю в Q[y1,..., yn ], то и для любого y Vn (k1, k0, k1 ) Нетрудно проверить (см. [4] и [5]), что в нашем случае всегда Fxi (y) Z.

Поэтому можно считать, что все коэффициенты в (1.4) целые и что, более того, один из этих коэффициентов не делится на p.

Подставим в (1.4) в качестве аргумента y = xi с произвольным i. С одной стороны, Fxi (y) = Fxi (xi ) = b С другой стороны, легко проверить, что поскольку при j = i выполнено (xj, xi ) (k1 + k1 ) (mod q), то Выходит, что ci 0 (mod p) для любого i. Противоречие с невырожденностью, т.е. многочлены линейно независимы над Q.

Преобразуем каждый из многочленов следующим образом. Запишем многочлен в виде линейной комбинации одночленов, и в каждом одночлене заменим сомножители вида y, 1, сомножителями y, где = 1, если нечетно, и = 2, если четно. Например, одночлен y1 y5 yn превратится в y1 y5 yn. Новые многочлены как функции от векторов из Vn (k1, k0, k1 ) тождественно равны исходным многочленам (очевидно, что y = y, коль скоро y {1, 0, 1}). Следовательно, новые многочлены также линейно независимы над Q. Это многочлены степени q 1 от n переменных, и каждая переменная входит в них в степени 0, 1 или 2. Все такие многочлены заведомо порождаются базисом из Cn Cni элементов. Таким образом, откуда и теорема доказана.

Замечание. Структура разбиений из формулировки теоремы 1.3.2 и множества T обусловлена тем, что именно на таких разбиениях достигается, по-видимому, асимптотический максимум логарифма мощности совокупности (1, 0, 1)-векторов с запрещенным скалярным произведением (см. [5], [78]–[82], а также [83]–[87]).

1.4 Приложения в задаче Нелсона–Эрдеша–Хадвигера Задача Нелсона–Эрдеша–Хадвигера, появившаяся в середине ХХ века, состоит в отыскании хроматического числа (Rn ) евклидова пространства:

В работе [47] было показано, что где максимум в знаменателе берется по всем гиперграфам, удовлетворяющим условиям теоремы 1.1.1. И из теоремы 1.1.1 получилось, что асимптотически максимум по k и l достигается при k 2 n, l k, n. В итоге возникла оценка Теорема 1.2.1 приводит к следствию, опубликованному автором в[96], [97].

n. Тогда существует l (0, k ), при котором запрет l l n дает Иными словами, оценка Франкла–Уилсона может быть получена не только при k 2 n, но и при всех k, описанных в следствии.

Доказательство следствия — это стандартная аналитическая выкладка, которую мы в настоящей работе не приводим.

Оценка Франкла–Уилсона улучшена (см. [70]) до (Rn ) (1.239... + o(1)), но не за счет уточнения теоремы 1.1.1, а за счет ее обобщения с гиперграфов на более сложные объекты.

С понятием хроматического числа пространства тесно связано понятие дистанционного графа. Граф G = (V, E) называется дистанционным, если V Rn, а E — это множество пар точек, отстоящих друг от друга на одно и то же расстояние a > 0. Ясно, что (Rn ) (G) для любого дистанционного графа G в Rn ((G) — это обычное хроматическое число графа). Более того, по теореме Эрдеша–де Брёйна (см. [71]) существует конечный дистанционный граф, на котором достигается значение (Rn ).

Дистанционный граф, на котором достигается оценка (Rn ) (1.239... + o(1))n, (вернее, последовательность графов Gn ) строится следующим образом. В качестве множества вершин берется Vn = Vn (k1, k0, k1 ), а ребра проводятся тогда и только тогда, когда скалярное произведение вершин равно t. Таким образом, число независимости (Gn ) этого графа (максимальная мощность множества попарно не смежных вершин) в точности равно величине m(n, k1, k0, k1, t). При этом ясно, что Теорема 1.3.1 (известная ранее) позволяет дать верхнюю оценку знаменателя в некоторых специальных допущениях. С учетом этих допущений берется максимум дроби по всем k1, k0, k1 и t, и он оказывается равным (1 + o(1))n, где 1 = 1.239... (см. [5]). Более того, он соответствует параметрам k В итоге мотивирована следующая постановка задачи. Пусть даны числа k1, k0, k1 (0, 1), в сумме дающие единицу. Пусть Чему равна величина Разумеется, его известные нижние оценки по-прежнему имеют вид Например, при k1 0.06, k1 0.3 выполнено (k1, k0, k1 ) 1.239. Однако до сих пор в нашем распоряжении была только теорема 1.3.1, а теперь есть еще и дополняющая ее теорема 1.3.2. Замечательно то, что теорема 1.3.2 действительно дает значимое улучшение теоремы 1.3.1 с точки зрения описанной постановки. Ниже мы приводим таблицу значений величины (k1, k0, k1 ). В каждой клетке, отвечающей паре чисел (k1, k1 ), по которой k0 находится однозначно, мы пишем оценку, полученную за счет теоремы 1.3.1, (ниже) и оценку, полученную за счет теоремы 1.3.2, (выше). Если новая оценка лучше, мы выделяем обе оценки жирным шрифтом. Кроме того, мы приводим в каждой клетке то значение t, на котором получена лучшая из двух оценок.

В случае, когда сильнее теорема 1.3.1, величина t всегда равна 1 2 1, т.е.

середине между минимальным и максимальным скалярным произведением (при k1 k1 и k1 + k1 2 минимальное скалярное произведение векторов из Vn (k1, k0, k1 ) равно 2k1, а максимальное скалярное произведение — это всегда скалярный квадрат, т.е. k1 + k1 ). Удивительно именно то, что зачастую сильнее теорема 1.3.2, в которой t просто по условию правее середины указанного отрезка. К сожалению, глобальный максимум по всей таблице дает все же теорема 1.3.1, т.е. оценку хроматического числа пространства улучшить не удается.

Глава Хроматическое число рационального пространства 2.1 Определение хроматического числа рационального пространства В 1976 году М. Бенда и М. Перлес (см. [72]) предложили обобщение задачи Нелсона–Хадвигера на случай рационального пространства Qn с той же евклидовой метрикой, что и в исходной постановке. Зазор между известными оценками соответствующей величины (Qn ) еще больше:

Нижняя оценка получена в работе [4] А.М. Райгородского в 2001 году, а верхняя оценка является следствием тривиального неравенства (Qn ) (Rn ).

В работах [88]–[92] изучаются хроматические числа пространств с несколькими запрещенными расстояниями. В частности, в статье [89] получены наилучшие известные оценки в случае двух запретов. А именно, пусть X, Y {R, Q}, k N. Положим где (Y n ; a1,..., ak ) — хроматическое число пространства Y n с запрещенными расстояниями a1,..., ak (точкам одного цвета запрещено отстоять друг от друга на расстояние, равное любому из данных k чисел). Положим также В работе [89] установлено неравенство приведена очевидная оценка Q (Qn ; 2) 2 + o(1) и доказано неожиданное неравенство lim sup R (Rn ; 2) + lim sup Q (Qn ; 2) 2.2 Новая нижняя оценка хроматического числа рационального пространства с одним запрещенным расстоянием Справедлива новая теорема, опубликованная в работе [98].

Теорема 2.2.1 Имеет место оценка где 3 = 1.199...

Возьмем произвольное число x 0, 8. Для каждого n (величины размерности) положим Ясно, что q [x, 4x] и правый конец этого отрезка не превосходит 1.

Рассмотрим любые положительные числа k1, k1, удовлетворяющие ограничениям k1 < k1 1 и k1 +3k1 = 2q. Положим k1 = [k1 n], k1 = [k1 n]1.

Имеем k1 < k1 и k1 + k1 2q < 2k1.

Пусть Gn = (Vn, En ) — граф, у которого Понятно, что хроматическое число (Gn ) этого графа служит нижней оценкой для (Qn ), ведь все координаты точек из Vn рациональны. В свою очередь где (Gn ) — число независимости графа, т.е. максимальная мощность такого подмножества множества его вершин, в котором нет ребер.

Лемма 2.2.1. Выполнена оценка где Доказательство леммы 2.2.1.

множество вершин, в котором нет ребер, т.е. для любых различных i, j имеем |xi xj | = 1. Пусть W = {x1,..., xs }, где xi = 2q · xi {1, 0, 1}n для каждого i {1,..., s}. Тогда для любых различных i, j имеем |xi xj |2 = 2q, откуда с учетом равенств получаем (xi, xj ) = k1 + k1 q ((x, y) — евклидово скалярное произведение).

Пусть I — множество, полученное из {0, 1,..., q 1} удалением вычета числа k1 + k1 по модулю q. Пусть a — степень, в которой двойка входит в каноническое разложение числа ( (k1 +k1 )). Каждому вектору xi W сопоставим многочлен рассматриваемый как элемент пространства Q[y1,..., yn ].

Изучим невырожденную линейную комбинацию Если она равна нулю в Q[y1,..., yn ], то и для любого xi W Нетрудно проверить (ср. [4] и [5]), что в нашем случае всегда Fxj (xi ) Z.

Поэтому можно считать, что все коэффициенты в (2.1) целые и что, более того, один из этих коэффициентов не делится на 2.

Далее, с одной стороны, С другой стороны, для j = i выполнено: 1) (xj, xi ) 2k1 (это верно, поскольку у нас k1 < k1 и k k1 + k1, — откуда ввиду известного нам неравенства k1 + k1 2q < 2k следует, что (xj, xi ) (k1 +k1 ) (mod q), и это в свою очередь, как несложно проверить, влечет Выходит, что ci 0 (mod 2) для любого i. Противоречие с невырожденностью, т.е. многочлены линейно независимы над Q.

Преобразуем каждый из многочленов следующим образом. Запишем многочлен в виде линейной комбинации одночленов, и в каждом одночлене заменим сомножители вида y, 1, сомножителями y, где = 1, если нечетно, и = 2, если четно. Например, одночлен y1 y5 yn превратится в y1 y5 yn. Новые многочлены как функции от векторов из W тождественно равны исходным многочленам (очевидно, что y = y, коль скоро y {1, 0, 1}).

Следовательно, новые многочлены также линейно независимы над Q. Это многочлены степени q 1 от n переменных, и каждая переменная входит в них в степени 0, 1 или 2. Все такие многочлены заведомо порождаются базисом из Cn Cni элементов. Таким образом, и лемма доказана.

Из леммы получаем, что (мы вынуждены брать минимум по q, т.к. при разных n величина q непредсказуемо меняет свои значения в известных пределах).

Стандартная выкладка с привлечением формулы Стирлинга показывает, что при x 0.1089, q 0.4356, k1 0.3437, k1 0.1758 получается как раз (Qn ) (1.199... + o(1))n. Теорема доказана.

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

Теорема 2.3.1. Имеет место оценка lim sup R (Rn ; 2) + lim sup Q (Qn ; 2) В работе [89] показано, что Доказательство. Как и оценка из предыдущего раздела, этот результат опирается на некоторую последовательность графов Gn = (Vn, En ). Напомним вкратце ту конструкцию. Пусть v0, v1, v2, v3, v4 — положительные числа, в сумме дающие n. Положим Пусть s — максимальное скалярное произведение векторов из Vn (т.е. скалярный квадрат любого из них), а s — минимальное скалярное произведение.

Пусть = ss. Зафиксируем произвольную “не слишком маленькую” функцию f аргумента n, которая равна o(n) при n (например, f (n) = ln n ), и рассмотрим такую последовательность {ni } размерностей, что для люi= бого n {ni } на интервале (, + f (n)) есть хотя бы одно число q вида (берем для определенности наименьшее) с некоторым натуральq= ным j (функция f влияет только на частоту, с которой числа ni встречаются в натуральном ряде). Именно с этими размерностями мы станем работать в дальнейшем, и именно они неявно присутствуют в верхних пределах, которые фигурируют в формулировке теоремы 2.3.1.

Положим Нетрудно видеть, что Более того, s 5q < s. Поэтому применима техника с полиномами, подробно описанная при доказательстве теоремы 2.2.1 (выкладки можно найти в оригинальной статье [89]), которая приводит к оценке где С помощью численных методов в статье [89] показано, что для оптимизации оценки нужно брать при n причем, если то имеем в аккурат Итак, пусть {ni } — та самая последовательность размерностей и графы Gni отвечают оптимальным параметрам, описанным выше. Тогда по формуле Стирлинга имеем Зафиксируем один из графов и для краткости обозначим его просто Gn.

Рассмотрим новый граф G1 = (Vn, En ), у которого К сожалению, мы не знаем его числа независимости. Но мы можем предположить, что с некоторым (мы позже выберем это число оптимально) выполнено (G1 ) < n. Если предположение верно, то, разумеется, откуда При этом, безусловно, так что в текущих предположениях В противном случае (G1 ) n, т.е. существует подмножество Wn в мноn жестве Vn, у которого |Wn | n и в котором нет пар векторов на расстоянии a2 и a3 друг от друга. Рассмотрим граф G2 = (Wn, En ), где Поскольку a1, a4 Q, имеем Однако (G2 ) — это размер самого большого подмножества в Wn, свободного от расстояний a1, a4, причем в самом Wn, как мы помним, нет расстояний a2, a3. Таким образом, (G2 ) (Gn ). Но из работы [89] мы знаем, что так что В то же время заведомо и, значит, Подберем так, чтобы было выполнено равенство Решая квадратное уравнение и подставляя найденное в обе части равенства, получаем 2.693..., что и требовалось доказать.

2.4 Хроматическое число аффинно-рационального пространства Подробнее проанализируем определение величины (Rn ) в терминах теории графов. А именно, назовем вещественным дистанционным графом (или вещественным графом расстояний) любой граф G = (V, E), у которого Таким образом, оценка (Rn ) (1 + o(1))n, которую мы упоминали в разделе 1.4, равносильна утверждению о том, что существует такая последовательность конечных вещественных графов расстояний Gn Rn и такая последовательность чисел n 0, n, что (Gn ) (1 + n )n.

Для обобщения понятия хроматического числа на рациональное пространство тоже полезна теоретико-графовая терминология. Назовем вполне рациональным дистанционным графом (или вполне рациональным графом расстояний) любой граф G = (V, E), у которого С учетом результата [71] вновь имеем (Qn ) = max{(G) : G конечный вполне рациональный Оценка (Qn ) (3 + o(1))n, доказанная в разделе 2.2, равносильна утверждению о том, что существует такая последовательность конечных вполне рациональных графов расстояний Gn Qn и такая последовательность чисел n 0, n, что (Gn ) (2 + n )n.

Видно, что разница между результатами (Rn ) (1 + o(1))n и (Qn ) (3 + o(1))n связана с различием между последовательностями вещественных и вполне рациональных графов. Оказывается, в большей степени здесь играет роль не то, что у вполне рациональных графов вершины рациональны, но то, что у них рациональны длины ребер. А именно, можно показать (см. [4]), что для величины R (Qn ) = max{(G) : G конечный частично рациональный выполнена оценка R (Qn ) (1 + o(1))n. Здесь частично рациональный дистанционный граф — это граф, который отличается от вполне рационального заменой условия a Q условием a R. Заметим, что величина уже возникала в разделе 2.1, когда мы говорили о хроматическом числе рационального пространства с несколькими запрещенными расстояниями.

В свете введенного в разделе 2.1 обозначения можно говорить и о величине Q (Qn ) = (Qn ). Отметим, что для пространства Rn между величинами R (Rn ) и Q (Rn ) никакой разницы нет.

Итак, мы знаем, что R (Qn ) (1 + o(1))n, а Q (Qn ) (2 + o(1))n. На самом деле, можно даже показать, что lim sup Q (Qn ) (1 +o(1))n, т.е. сущеn ствует такая последовательность размерностей ni, такая последовательность конечных вполне рациональных графов расстояний Gni Qni и такая последовательность чисел ni 0, i, что (Gni ) (1 +ni )ni. Спрашивается, можно ли что-то подобное сказать про все размерности? Разумеется, самым прямым ответом на вопрос была бы оценка Q (Qn ) (1 + o(1))n. Однако ее установить не удается. Удается сделать нечто иное.

Зачастую вполне рациональный граф с вершинами в Qn Rn лежит в некотором аффинном подпространстве Rn размерности m < n. Вообще говоря, его нельзя считать в этом случае вполне рациональным графом в Qm, ведь во внутренних координатах пространства рациональные (и даже целые) точки могут стать иррациональными (такие пространства мы будем называть аффинно-рациональными). Назовем аффинной размерностью множества A минимальную размерность пространства, которое его содержит, и обозначим ее adim A. Тогда мы можем говорить о том, что аффинная размерность adim G вполне рационального графа G не превосходит m. Положим a (Qn ) = max{(G) : G конечный вполне рациональный Справедлива Теорема 2.4.1. Имеет место оценка А именно, существует такая последовательность конечных вполне рациональных графов расстояний Gn Q4n с adim Gn n и такая последовательность чисел n 0, n, что (Gn ) R (Q ) (1 + n )n.

Теорема опубликована в работе [99].

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

Пусть Gn = (Vn, En ) — последовательность таких частично рациональных графов, что (Gn ) = R (Qn ). Пусть, далее, длина ребра каждого из графов Gn равна t. Ясно, что t = s, где s Q. Выберем такие рациональные числа a, b, c, d, что a2 +b2 +c2 +d2 = s. Это можно сделать за счет классической теоремы Лагранжа о представлении произвольного целого числа в виде суммы не более четырех квадратов целых чисел.

Рассмотрим произвольную вершину x = (x1,..., xn ) Vn. Поставим ей в соответствие вектор Обозначим через Vn множество всех таких x. Разумеется, мы, тем самым, получим биекцию между Vn и Vn. Посмотрим, во что при этой биекции перейдут ребра. Пусть {x, y} En. Тогда Таким образом, граф G = (Vn, En ) вполне рационален. Однако он изоморn фен исходному графу, и, стало быть, (G ) = (Gn ) = R (Qn ). Теорема доказана.

Теорема 2.4.1 дает некоторый ответ на поставленный нами вопрос о хроматических числах вполне рациональных графов во всех размерностях. Минус ее в том, что эти размерности аффинные, а плюс в том, что “настоящие” размерности не сильно от аффинных отличаются — не более, чем в 4 раза.

Заметим, что неверно равенство a (Qn ) = R (Qn ). Например, в Q4 есть равносторонние треугольники с длинами сторон 1. Иными словами, a (Q2 ) 3. Однако еще в работе [72] показано, что R (Q2 ) = 2. Таким образом, вообще говоря, a (Qn ) > R (Qn ).

В то же время очевидно, что a (Qn ) (Rn ). С одной стороны, это означает, что у нас нет шансов сколь-нибудь принципиально улучшить оценку (2.2). С другой стороны, мы имеем новую величину, которая почти наверняка не совпадает ни с одной из ранее изучавшихся. Иными словами, мы предполагаем, что каждое из строгих неравенств в следующей цепочке выполнено хотя бы в некоторых размерностях:

Второе из неравенств, как мы знаем, имеет место хотя бы для n = 2. Первое неравенство справедливо при n = 3. В самом деле, Q (Q3 ) = 2 (см. [72]).

Однако точки (1, 0, 0), (0, 1, 0), (0, 0, 1) образуют частично рациональный треугольник в Q3, и, стало быть, R (Q3 ) 3. Любопытно, что a (Q3 ) 4, т.к.

вполне рациональные симплексы на четырех вершинах (правильные тетраэдры со стороной 1) существуют во всех достаточно больших размерностях (см.

[93]). И более того, (R3 ) 6 (см. [62]). Кажется довольно правдоподобным, что уже для n = 3 все три величины различны.

Глава Некоторые аналоги задачи Борсука В этой главе мы сформулируем и изучим несколько аналогов классической задачи Борсука.

3.1 Задача Борсука для вещественного и рационального пространства В 1933 году Борсуком была поставлена задача о разбиении n-мерного множества на части меньшего диаметра (см. [30]). Обозначим через f (n) минимальное число частей меньшего диаметра, на которые разбивается любое ограниченное множество в Rn. Назовем f (n) числом Борсука. Классическая гипотеза Борсука состояла в том, что f (n) = n + 1. Однако она была опровергнута (см. [48]). Сейчас известно, что гипотеза верна при n 3 и неверна при n 65, а также установлены следующие асимптотические неравенства (см. [5], [8], [17], [51] ):

В этом разделе рассматривается аналогичная задача, поставленная относительно пространства Qn.

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

Утверждение. Выполнена оценка fQ (n) f (n) для любого n N.

Доказательство. Докажем методом от противного.

Пусть m = f (n). Предположим, что fQ (n) < m. Рассмотрим множество A, которое в Rn не делится на m1 часть. Если взять выпуклую оболочку A его замыкания, то она тоже не может делиться на m 1 часть меньшего диаметра. Возьмем B = A Qn. В силу того, что fQ (n) < m, множество B должно делиться на m 1 часть меньшего диаметра. Воспользуемся тем, что множество рациональных чисел всюду плотно в множестве вещественных чисел.

Тогда для любой точки x из A существует некоторая последовательность точек {xk }, xk Qn, xk x. Так как частей конечное число, есть бесконечная подпоследовательность точек, принадлежащих одной части. Отнесем точку x к любой из таких частей. Мы получили разбиение A на m 1 часть меньшего диаметра. Противоречие с предположением. Значит, fQ (n) m.

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

3.2 Правильный аналог задачи Борсука для рационального пространства Для построения правильного аналога воспользуемся понятием хроматического числа множества, которое аналогично обсуждавшимся понятиям хроматического числа графа и хроматического числа пространства. А именно хроматическим числом множества A, обозначаемое Q (A) — минимальное число цветов необходимое для такой раскраски множества A, чтобы не было одноцветных точек на расстоянии 1. Через Q,1 (n) обозначим величину Именно эта величина Q,1 (n) послужит правильным аналогом числа f (n).

Чтобы понять, что из себя представляет величина Q,1 (n), посмотрим, как она ведет себя в малых размерностях.

Очевидно, что Q,1 (1) = 2. Вообще, это число не меньше числа S(n) вершин правильного (рационального) симплекса Rn максимальной размерности (с длиной стороны 1) и не больше числа Борсука f (n) и хроматического числа Q (n). Но для Q2 и Q3 хроматическое число равно двум, а для Q4 — четырем (см. [72], [73], [94]), причем число вершин рационального симплекса максимальной размерности (в R2, R3 и R4 соответственно) равно тому же (см. [93]). Итак, Естественно возникает вопрос: может быть, во всех размерностях эта величина равна числу S(n) вершин правильного рационального симплекса Rn максимальной размерности? С одной стороны, эта гипотеза созвучна гипотезе Борсука в соответствии с поправкой на выбранное пространство. С другой стороны, величина S(n) подсчитана (см. [93]) и, если бы удалось доказать эту гипотезу, было бы получено и точное значение величины Q,1 (n). К сожалению, гипотеза неверна. Удается доказать следующий результат (см. [100], [101]).

Теорема 3.2.1. Имеет место неравенство при n.

Как видно, гипотеза неверна, а рассматриваемая величина имеет такой же экспоненциальный рост, как и обычное число Борсука. Забегая вперед, скажем, что отличие между оценками для величин f (n) и Q,1 (n) все же есть, но оно лишь на уровне o(1).

Напомним, что аффинной размерностью множества A мы называем минимальную размерность пространства, которое его содержит, и обозначим ее adim A. Теперь рассмотрим величину Эта величина послужит другим рациональным аналогом числа Борсука. В данном случае мы обращаем внимание на “реальную” размерность множеств — то есть на размерность подпространств, их содержащих. Смысл этой величины в том, что во внутренних координатах плоскости точки множества уже не будут рациональными, поэтому перейти к “реальной” размерности (как мы бы сделали в вещественном случае) нельзя. В принципе, можно ожидать, что a (n) Q,1 (n). Однако нам лишь удается доказать следующий результат (см. [101]).

Теорема 3.2.2. Имеет место неравенство при n.

Здесь величина 2 значительно больше величины 1 (как и ожидалось), и она практически неотличима от величины o(1) в оценке для f (n). Впрочем, ясно, что любое дальнейшее продвижение в этом месте почти автоматически бы означало продвижение и в классической задаче, а с этим пока довольно плохо.

Доказательства этих теорем почти полностью совпадают, поэтому здесь будет приведено только доказательство теоремы 3.2.1, с указанием тех отличий, которые появятся при доказательстве теоремы 3.2.2. Вообще, это доказательство во многом параллельно доказательству основного результата из работы [58]. Однако имеется ряд тонкостей, которые необходимо будет преодолеть.

Итак, пусть p — простое число, ближайшее к [n], где = 1 3. Рассмот- рим множество Заметим, что скалярное произведение любых двух векторов из заключено в границах p < (, y ) p. Более того, для любых двух векторов x = y Для каждого вектора x = (x1,..., xn ) рассмотрим вектор Таким образом, множеству, состоящему из векторов x, ставится во взаимно однозначное соответствие множество, состоящее из векторов x x. В частности, | | = || = Cn1 2, чем мы воспользуемся позднее. В то же время, размерность множества не превосходит m = Cn + 2n = n(n+3). Если же мы будем говорить об его аффинной размерности (что требуется как раз для теоремы 3.2.2), то она не превосходит m = Cn + n = n(n+1). Именно в этих разных оценках размерностей кроется различие полученных оценок чисел Борсука. Заметим, что доказательства двух теорем отличаются только в этом месте. Далее, имеем С другой стороны, и так далее.

Можно убедиться в том, что подобные оценки верны для всех n Na, 903, а это и значит, что при любом n 903 гипотеза неверна. При n < 903 такой номер не проходит.

Для неаффинного случая получаем чуть иную последовательность:

и так далее.

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

3.3. Тут в чистом виде применяется конструкция из работы [51]. Положим m = 36 = 4 · 32 (ср. §4.1) и рассмотрим так что || = 2m4. Все очень похоже на технологию из доказательств теорем 3.2.1, 3.2.2 и параграфа 3.3.1. Однако на сей раз мы перейдем к по правилу, которое слегка отличается от (3.1). А именно, мы будем попарно перемножать все xi, xj, у которых i {2,..., m}, j {4,..., m}. Тогда биекция между и по-прежнему имеет место, причем аффинная размерность не превосходит 561 = (m2)(m3).

Далее, Максимум расстояния достигается тогда только тогда, когда либо (, y ) = 0, либо (, y ) = 4. Этот максимум равен 2304 = 48 Q.

Теперь остается выписать и применить стандартную лемму.

Лемма. Пусть Q таково, что для любых x, y Q верно, что (, y ) = 0 и (, y ) = 4. Тогда Доказательство леммы можно найти в [51]. А применение очевидно:

Теорема доказана.

Существуют способы “поднятия” контрпримеров в бльшие размерности (см. [58]). Однако при этом диаметры перестают быть рациональными. Именно поэтому сохраняется зазор между размерностями 758 и 902.

Заметим также, что подход, осуществленный нами в этом параграфе, можно было бы попытаться перенести на случай бльших размерностей. Ясно, что для этого нам нужно, чтобы для данного числа m вида 4p (иначе не удается доказывать леммы, см. [5]) число 2(m 1)(m 3) 6 (или похожее число) было полным квадратом. К сожалению, результатов о частоте возникновения подобных чисел в натуральном ряде автору найти не удалось.

3.4 Обобщение на случай метрики lp Для пространства Qn с метрикой lp можно поставить аналогичные задачи и доказать асимптотические оценки. Число Борсука в этой метрике обозначим Q,1 (n, p), а в аффинном случае — a (n, p). Предположим, что p N.

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

Числа ai Q и s N будут подобраны позже. Размерность множества при этом не превосходит Cn = n(n1) в аффинном случае и Cn + sn — в неаффинном.

Рассмотрим расстояние между векторами в новообразованном множестве.

Согласно выбранной метрике получаем