О хроматических числах целочисленных и рациональных решеток

Аннотация

В настоящей работе мы приводим новые верхние оценки для хроматических чисел целочисленных, рациональных и некоторых других решеток. В частности, в работе доказано, что для каждого конкретного целого числа \(d\) хроматическое число для \(Z^{n}\) с критическим расстоянием \(\sqrt{2d}\) имеет полиномиальный рост с ростом \(n,\) причем показатель не превосходит \(d\) (иногда эта оценка является точной). То же самое верно не только для случая евклидовых норм, но также и для любых \(l_{p}\)-норм. Кроме того, мы приводим конкретные оценки для малых размерностей, а также некоторые верхние оценки для хроматических чисел для пространств \(Q_{p}^{n},\) где через \(Q_{p}\) мы обозначаем кольцо всех рациональных чисел, знаменатели которых не делятся на некоторое простое число.

Полный текст

1. ВВЕДЕНИЕ Хроматическим числом метрического пространства M с запрещенным расстоянием (или критическим расстоянием) d мы назовем минимальную мощность множества S, для которого найдется отображение f : M → S, такое что для любых двух точек x, y ∈ M на расстоянии d мы имеем f (x) I= f (y). Обозначим это число χ(M, d). Для краткости мы будем писать χ(M ) вместо χ(M, 1). Хроматические числа евклидовых пространств и линейных пространств над рациональными числами (в случае евклидовой нормы мы будем обозначать последние через Qn) изучались многими авторами, см., например, работы [1, 2, 6-8, 12] и ссылки в них. Хроматические числа целочисленных решеток для норм l2 и l1 изучались, например, в работах З. Фюреди и Дж. Канг, где была получена нижняя экспоненциальная оценка для χ(Zn, √r) для четных r в норме l2 и, аналогично, для χ(Zn, √r) для четных r в норме l1, однако этот результат относился к специальному случаю, когда r зависит от n (например, r = 2q, n = 4q - 1 для некоторого целого q). Некоторые более точные оценки были получены в работе [3]. Оказывается, что самые лучшие известные асимптотические верхние оценки для рациональных пространств - это в точности оценки для евклидовых пространств: хроматическое число для Qn ограничено сверху (3 + o(1))n при n, стремящемся к бесконечности [2, 12]. Настоящая работа является систематическим исследованием целочисленных решеток и некоторых их обобщений: решеток над пополнениями кольца целых чисел, решеток над рациональными числами и решеток над рациональными числами с некоторыми запрещенными знаменателями. Работа организована следующим образом. В следующем разделе мы имеем дело с маломерными целочисленными решетками, в частности, мы находим те случаи, когда хроматическое число равно трем. Эти результаты ранее не появлялись в литературе. Основной результат настоящей работы содержится в третьем разделе: мы доказываем, что для фиксированного m хроматическое число χ(Zn, √2m) оценивается сверху как c nm в любой норме lp, где c не зависит от n. Этот результат контрастирует с оценкой на рациональных решетках, поскольку в рациональном случае доказано, что нижняя оценка является экспоненциальной. Далее мы вспоминаем некоторые известные нижние оценки, происходящие из теоремы Фрэнкла-Уилсона, которые мы трактуем как оценки для целочисленных решеток. Автор частично поддержан грантами правительства РФ 11.G34.31.0053, Президента РФ поддержки ведущих научных школ 1410.2012.1, Минобрнауки РФ 14.740.11.0794. Qc 2013 РУДН 110 О ХРОМАТИЧЕСКИХ ЧИСЛАХ ЦЕЛОЧИСЛЕННЫХ И РАЦИОНАЛЬНЫХ РЕШЕТОК 111 Другим интересным случаем является изучение хроматических чисел рациональных пространств. Мы приводим новые верхние оценки для решеток над кольцами рациональных чисел, знаменатели которых взаимно просты с 5 и 3 соответственно (теоремы 16 и 15 соответственно). В качестве шага в сторону оценок хроматических чисел рациональных решеток мы рассматриваем решетки над рациональными числами с некоторыми запрещенными знаменателями. Статья завершается обсуждением и некоторыми открытыми проблемами. Благодарности. Я благодарен А. М. Райгородскому и А. Б. Купавскому за плодотворные обсуждения настоящей работы, И. Д. Шкредову, который обратил мое внимание на работы [14-16], и Дж.-Х. Канг за обсуждение работы [11]. 2. МАЛОМЕРНЫЕ ЦЕЛОЧИСЛЕННЫЕ РЕШЕТКИ Следующая теорема очевидна (см., например, [6]). Теорема 1. Для любого числа k, представимого в виде суммы двух квадратов целых чисел, имеет место χ(Z2, √k) = 2. В противном случае χ(Z2, √k) = 1. Более того, то же самое утверждение верно для Zn. Для Z3 имеет смысл рассматривать лишь критические расстояния вида √4l + 2,l - нечетное: в случае нечетных критических расстояний хроматическое число не превосходит двух по соображениях четности; случай, когда под квадратным корнем стоит 4l, l ∈ Z, сводится в R3 к случаю √l, так как любое представление числа 4l в виде суммы трех квадратов состоит из трех квадратов четных чисел. Теорема 2 (Верхняя оценка: универсальная раскраска). Для каждого k = 4l + 2,l ∈ Z имеет место χ(Z3, √k) 4. Доказательство. Рассмотрим множество точек на трехмерной решетке, у которых сумма всех трех координат является четной. Раскраска оставшихся точек будет получена из исходной раскраски сдвигом на вектор (1, 0, 0). Рассмотрим следующую «универсальную 4-раскраску» в цвета (0, 0), (0, 1), (1, 0), (1, 1), где тройке целых координат точки из Z3 мы сопоставляем два числа, первое из которых представляет собой четность первой координаты, а второе - четность второй координаты. Ясно, что если две точки на целочисленной трехмерной решетке находятся на расстоянии √4l + 2, то либо они имеют разную четность координаты z, либо они имеют разную четность координаты x. Чтобы получить нижнюю оценку, нам нужно будет использовать веретено Райского-Мозера (см. [5, 13]), и его обобщения. Под двумерным веретеном (для критического расстояния 1) мы понимаем граф с семью вершинами, который выглядит следующим образом: одна вершина A является вершиной двух равносторонних треугольников со стороной один: ABC и AB×C×; также имеются два равносторонних треугольника BCD и B×C×D× со стороной 1, у которых точки D и D× также находятся друг от друга на расстоянии 1 (и соединены ребром). При попытке раскрасить этот граф-веретено в три цвета мы придем к противоречию: A и D должны иметь один и тот же цвет; то же самое верно и для A и D×. С другой стороны, D и D× находятся на расстоянии 1, так что их цвета должны быть различными. Применяя гомотетию с целым коэффициентом к этому веретену, мы можем получить аналогичный граф с произвольным целочисленным запрещенным расстоянием. Этот граф мы также будем называть веретеном. В размерности n вместо треугольников следует рассматривать пары n-мерных симплексов со стороной 1, (A, A1,..., An) и (A, A× ,..., A× ), имеющих общую точку A, а также точки B и B×, 1 n i находящиеся на единичном расстоянии от всех Ai,i = 1,...,n (от всех A× , i = 1,..., n, соответственно). При этом требуется также, чтобы B и B× были на расстоянии 1. В этом случае граф не допускает (n + 1)-раскраски; это приводит к доказательству того, что χ(Rn, 1) n + 2. В случае рациональных пространств или целочисленных решеток для конкретных критических расстояний часто невозможно явно построить такое веретено. Тем не менее рассуждение можно немного поправить, рассматривая обобщенное веретено (или веретено Купавского). Пусть мы 112 В. О. МАНТУРОВ имеем две пары треугольников (A, B, C, D), (A, B×, C×, D×) для некоторого критического расстояния в обозначениях, введенных ранее, причем точки D и D× не находятся на критическом расстоянии. Обозначим расстояние l(D, D×) через d. Предположим, что для любой собственной раскраски найдутся две точки D˜ , D˜ × разных цветов и изометрия пространства, переводящая D 1→ D˜ , D× 1→ D˜ ×. Рассмотрим образы всех точек (A, B, C, D, B×, C×, D×) и увидим, что их невозможно покрасить в три цвета. Это утверждение (в несколько большей общности) для случая евклидовых пространств было доказано А. Б. Купавским [1]. Очевидно, изометрии в случае целочисленных решеток требуют более тонкого подхода, чем изометрии вещественных пространств. Теперь, чтобы доказать нижние оценки для Z3, нам придется часто использовать конструкцию обобщенного веретена (веретена Купавского). Заметим, что в Z3 равенство расстояний l(D, D×) и l(D˜ , D˜ ×) не гарантирует наличия изометрии, переводящей D в D˜ Для целочисленного случая нам понадобится следующая и D× в D˜ ×. Лемма 1 (Целочисленный аналог леммы Купавского). Пусть A = (a1, a2, a3) - точка в Z3, такая что a1 + a2 + a3 является четным и НОД(a1, a2, a3) = 1. Предположим далее, что m = b2 + b2 + b2 является четным для некоторых целых чисел b1, b2, b3, для которых 1 2 3 НОД(b1, b2, b3)= 1. Тогда для любой правильной раскраски пространства Z3 с запрещенным расстоянием √m найдутся точки P, Q ∈ Z3 и изометрия решетки Z3, которая переводит начало координат в точку P, а точку A -в точку Q таким образом, что P и Q имеют разные цвета. Доказательство. Действительно, найдется цепочка X0, X1,..., Xk , состоящая из точек решетки Z3, от точки (0, 0, 0) = X0 к точке (b1, b2, b3) = Xk, у которой все Xi,i = 1,...,k - 1 таковы, что для каждых двух соседних точек Xi, Xi+1 вектор Xi+1 - Xi получается из вектора (a1, a2, a3) в результате изометрии пространства Z3. Теперь, так как X0 и Xk имеют разные цвета, найдутся соседние точки Xi и Xi+1, имеющие разные цвета. Доказательство существования такой цепочки остается читателю в качестве упражнения. Теорема 3. χ(Z3, √2) = 4. В данном случае можно явно построить веретено: мы берем два треугольника (0, 0, 0), (0, 1, 1), (1, 0, 1), (1, 1, 2) и аналогичную пару треугольников, которая получается из первой пары перестановкой второй и третьей координат. Точки (1, 1, 2) и (1, 2, 1) находятся на расстоянии √2. Примеры запрещенного расстояния, для которого хроматическое число в трехмерном пространстве равно четырем, хорошо известны [6]. В работе [6] М. Бенда и М. Перлес поставили вопрос о существовании запрещенного расстояния в Q3, для которого хроматическое число равно 3. Теорема 4. Для k = 10 + 12l, l ∈ Z имеет место χ(Z3, √k)= 3. Доказательство. Легко можно проверить, что любое разложение числа 10 + 12l, l ∈ Z в сумму трех квадратов целых чисел имеет вид a2 + b2 + c2, где приведение по модулю 6 тройки чисел (a, b, c) совпадает с точностью до порядка с одной из троек: (1, 3, 0), (5, 3, 0), (3, 3, 2), (3, 3, 4). Далее мы будем красить точки с четной суммой координат следующим образом: для точки с координатами x, y, z мы берем класс вычетов x + y + z по модулю 6, что приводит нас к раскраске в три цвета. Аналогичным образом мы получаем раскраску в три цвета для тех точек, сумма координат которых нечетна. Перейдем теперь к случаю тех запрещенных расстояний для Z3, для которых хроматическое число равно четырем. Теорема 5. Если m = a2 +ab+b2 для некоторых целых a, b, то χ(Z3, √2m)= 4. В частности, пусть p = 6k +1 - простое число (k - целое). Тогда χ(Z3, √2p)= 4. Доказательство. Действительно, предположим сначала, что m = a2 +ab+b2 для взаимно простых a, b. Мы предположим, что наше пространство имеет хроматическое число 3, и попробуем прийти к противоречию. Предположим сначала, что ровно одно из чисел a и b является нечетным; без ограничения общности будем считать, что a нечетно, b четно. О ХРОМАТИЧЕСКИХ ЧИСЛАХ ЦЕЛОЧИСЛЕННЫХ И РАЦИОНАЛЬНЫХ РЕШЕТОК 113 Мы имеем 2m = a2 + b2 +(a + b)2. Таким образом, расстояние между двумя векторами имеет вид √2m, если разности их координат равны ±a, ±b, ±(a + b) с точностью до порядка. Таким образом, у нас есть возможность выбора различных векторов для построения обобщенного веретена. Рассмотрим сначала два треугольника ABC, BCD со следующими вершинами: A = (0, 0, 0), B = (a, b, a + b), C = (-b, a + b, a), D = (a - b, a + 2b, 2a + b). Мы теперь можем построить другие пары треугольников с начальной вершиной A = (0, 0, 0) посредством перестановки координат и добавления знака «минус» к a и/или к b. Например, имеется пара треугольников с концом D× = (-a - b, -2a + b, -a + 2b), противоположным A. Теперь легко видеть, что наибольший общий делитель НОД(-a - b, -2a + b, -a + 2b) равен 1 или 3. Если он равен 3, то, заменяя b на -b, мы получаем НОД(-a + b, -2a - b, -a - 2b)= 1, что приводит нас к построению веретена. В случае, когда оба числа a, b являются нечетными, мы заметим, что та же самая пара треугольников может быть получена, если мы начнем с пары чисел (a, a + b): число (a + b) является четным. В случае, когда a и b не являются взаимно простыми, мы возьмем c = НОД(a, b),a = a×c, b = b×c и построим аналогичное веретено для подрешеток, состоящих из точек пространства со всеми координатами, делящимися на c. Теперь мы применим лемму 1 и увидим, что после применения изометрии к Z3 образы точек D˜ и D˜ × будут иметь различные цвета. Беря образы всех точек A, B, C, D, B×, C×, D×, мы получим противоречие с тем, что хроматическое число пространства равно 3. Собирая вместе приведенные выше результаты о раскрасках пространства Z3, мы получаем следующую теорему Теорема 6. Имеют место следующие оценки: 1. χ(Z3, √m)= 2, если и только если m нечетно и представимо в виде суммы двух квадратов; 2. для четного m χ(Z3, √m) равно либо 3, либо 4; 3. если m ≡ 10(mod 12), то χ(Z3, √m)= 3; 4. если m =2(a2 + b2 + ab), a, b ∈ Z, то χ(Z3, √m)= 4; 5. χ(Z3, √m)= χ(Z3, 2√m). Единственное из утверждений приведенной выше теоремы, которое мы пока не доказали, - это 2. Мы докажем его в несколько шагов. а) Достаточно доказать его для m = 2p при p. б) Будем считать, что m = 2p = a2 + b2 + c2, где НОД(a, b, c)= 1. в) Из упражнения на с. 112 следует, что существует цепочка в Z3, соединяющая начало координат с точкой (0, 1, 1), у которой любые два соседних узла находятся на расстоянии √m. г) Если найдется цепочка вида в) длины l, то мы можем легко построить «такую же» цепочку из начала координат в (1, 0, 1), а также из (1, 0, 1) в (0, 1, 1). Это приводит к построению замкнутой цепочки длины 3l, что противоречит возможности раскраски пространства в два цвета. д) Предположим, что цепочка из пункта в) имеет четную длину. Тогда мы можем построить цепочку в Z3 четной длины (с длиной звена √m) от начала координат до точки, у которой сумма координат четна. В частности, имеется цепочка четной длины от начала координат до точки (a + 1, b,c + 1). Таким образом, имеется цепочка нечетной длины от начала координат до (1, 0, 1). Из пункта г) следует противоречие с раскраской в 2 цвета. Теорема доказана. Первое критическое расстояние, не охватываемое доказанной теоремой - это √30. Гипотеза 1. В трехмерном пространстве нет других примеров с хроматическим числом 3, иными словами, χ(Z3, √m) = 3 имеет место только для тех m, которые могут быть представлены в виде 22kl, где l ≡ 10 mod 12. Перейдем теперь к случаям размерностей 4 и 5. Теорема 7. Имеют место следующие утверждения: 1. (А. Б. Купавский) Для k = 4l + 2,l ∈ Z, мы имеем χ(Z4, √k) 4, χ(Z5, √k) 8. 114 В. О. МАНТУРОВ 2. χ(Z4, √8k)= χ(Z4, √2k). 3. χ(Z4, √4l) 4 при нечетных l. Доказательство. Для доказательства первого утверждения нам достаточно раскрасить единичный куб {0, 1}4 (соответственно {0, 1}5), который отвечает четностям координат. Действительно, если две точки в Z4 (соответственно в Z5) имеют одну и ту же четность у всех координат, то квадрат расстояния между этими точками делится на четыре. Кроме того, достаточно раскрасить только «половину» куба, состоящую из тех точек, сумма координат которых четна («нечетная» половина куба рассматривается аналогично). Таким образом, в Z4 (на самом деле - в {0, 1}4) мы раскрашиваем 8 точек (a, b, c, d), a, b, c,d ∈ Z2,a + b + c + d ≡ 0 по модулю 2 в четыре цвета таким образом, что каждые две противоположные точки (x, y, z, t) и (1 - x, 1 - y, 1 - z, 1 - t) имеют один цвет. В пятимерном случае достаточно использовать приведенную выше раскраску для четырехмерного подкуба и добавить дополнительные пару цветов, отвечающие за пятую координату: итого мы получим восемь цветов. Второй результат следует из того факта, что сумма квадратов четырех целых чисел, из которых по крайней мере одно является нечетным, не может делиться на восемь, так что проблема сводится к случаю, когда все координаты являются четными. Верхняя оценка в третьем случае получается следующим образом. В качестве цвета мы возьмем пару классов вычетов. Первый класс равен четности первой координаты. Второй класс равен сумме четностей f xi l по всем i = 1, 2, 3, 4. 2 Замечание 1. Заметим сначала, что приведенная выше оценка дает универсальную раскраску для всех запрещенных расстояний тех типов, которые приведены в формулировке теоремы. Приведенное выше доказательство первого утверждения может быть обобщено на высшие размерности. Мы обсудим вопрос о верхних оценках для χ(Zn, 4k + 2) в отдельной статье. 3. ДЛЯ КАЖДОГО m РОСТ ЧИСЛА χ(Zn, √2m) ПОЛИНОМИАЛЕН ПО n И ИМЕЕТ СТЕПЕНЬ НЕ БОЛЬШЕ m Хорошо известно (см., например, [2]), что для рациональных пространств хроматическое число растет экспоненциально с ростом размерности. Ниже мы доказываем, что в случае целочисленных решеток при фиксированном запрещенном расстоянии это никогда не имеет места. Начнем с хорошо известной теоремы о целочисленных решетках (см., например, [6]). Раскраска посредством скалярного произведения будет далее использоваться в доказательстве основной теоремы. Следующая теорема хорошо известна. 2) Теорема 8. Рост хроматического числа χ(Zn, √ линеен при стремлении n к бесконечности. Доказательство. Чтобы получить нижнюю оценку (см. [11]), рассмотрим множество точек в Zn, у которых в точности одна координата равна ±1, а остальные равны нулю. Ясно, что это множество не может быть покрашено менее чем в n цветов при n 2. Верхняя оценка достигается посредством следующей раскраски. В Zn рассмотрим следующий вектор: v = (1, 3, 5, 7,..., 2n - 1). Для каждого u ∈ Zn рассмотрим скалярное произведение (u, v⊗. Ясно, что если два целочисленных вектора u1, u2 находятся на расстоянии √2, то мы имеем (u1, v⊗ I= (u2, v⊗. Более точно, разность значений (·, v⊗ для этих векторов является целым числом, модуль которого расположен между 2 и 4n - 4. Следовательно, если мы возьмем класс вычетов этого скалярного произведения по модулю 4n - 2 в качестве раскраски, мы получим правильную раскраску в (2n - 1) цветов. Идея раскрасок посредством скалярных произведений по модулю некоторых целых чисел будет далее использоваться в более сложных ситуациях. В частности, она будет использована для доказательства нашего главного результата - полиномиальной верхней оценки для хроматического числа целочисленной решетки с фиксированным запрещенным расстоянием. Теорема 9. Для каждого фиксированного m верхняя оценка для χ(Zn, √2m) в любой норме lα полиномиальна по n и имеет степень не больше m. О ХРОМАТИЧЕСКИХ ЧИСЛАХ ЦЕЛОЧИСЛЕННЫХ И РАЦИОНАЛЬНЫХ РЕШЕТОК 115 Перед тем, как доказывать эту теорему в общем случае, который опирается на некие глубокие факты из аддитивной комбинаторики, построим явную раскраску для некоторого частного случая. Утверждение 1. χ(Zn, 2) растет квадратично при n → ∞. Докажем верхнюю оценку. Нижняя оценка на самом деле хорошо известна и будет доказана позже. Пусть n - целое число. Пусть p - простое число, причем p n 2p. Мы докажем квадратичную верхнюю оценку для простого p, которая очевидно влечет квадратичную верхнюю оценку при n → ∞. Рассмотрим множество (k, ak mod p) из p элементов из абелевой группы S = {0,...,p - 1} × {0,...,p - 1}: где k пробегает {1,...,p - 1}, а a является первообразным корнем степени (p - 1) из единицы в Zp. Можно легко заметить, что для любых четырех различных элементов a, b, c, d из описанного выше подмножества мы имеем a - b I= c - d. Действительно, если для некоторых e, f, g, h ∈ Zp имеет место f -e = h-g и h I= f, e I= f, то мы видим, что af -ae отличается от ah -ag умножением на af -h. Мы построили множество (абелеву группу), в которой нет решений уравнения a - b = c - d при различных a, b, c, d. Модифицируем теперь это множество, чтобы избавиться от решения еще некоторых (более простых) уравнений. Возьмем теперь множество S× ⊂ Z × Z целых чисел (4k - 3, ak mod p), где ak mod p рассматривается как целое число между 0 и p - 1 (здесь мы пользуемся включением Zp ⊂ Z). Лемма 2. Для любых четырех различных элементов a, b, c, d ∈ S× мы имеем: 1. никакая из сумм ±a ± b ± c ± d не равна нулю. 2. абсолютное значение первой координаты суммы ±a ± b ± c ± d не превосходит 16p, а абсолютное значение второй координаты суммы не превосходит 4p. Доказательство. Второе утверждение очевидно. Выше мы доказали, что из a - b = c - d для a, b, c, d ∈ S× следует, что a = c или a = b. Уравнение a + b + c + d =0 не имеет решений, поскольку a, b, c, d положительны, а неравенство a + b + c - d I=0 вытекает из рассмотрения соответствующих вычетов по модулю 4. Рассматривая теперь S× как подмножество абелевой группы S×× = Z16p+1 × Z4p+1, мы видим, что для любых четырех различных элементов a, b, c, d ∈ S× ⊂ S×× имеет место ±a ± b ± c ± d I=0 ∈ S××. Мы назовем p элементов, образующих подмножество S× ⊂ S××, отмеченными элементами из S××. Обозначим эти отмеченные элементы из S×× через q1,..., qp. Они образуют вектор, который мы будем использовать для построения раскраски. j Для каждого вектора x = (x1,..., xp) ∈ Zp пусть x× - класс вычетов по модулю p от xj, 0 x× рассмотренный как целое число от до p - 1. Вектору x мы сопоставим элемент (цвет) f (x) = jqj ∈ S×× из группы S ××. Лемма 3. Если расстояние между двумя точками x, x˜ равно двум, то f (x) I= f (x˜) в S××. Доказательство. Действительно, так как все элементы qi ненулевые, две точки, у которых совпадают все координаты, кроме одной, а одна координата отличается на два, имеют разные цвета. Если у двух точек совпадают все координаты, кроме четырех, а каждая из четырех оставшихся координат отличается на ±1, то эти точки имеют разные цвета в силу леммы 2. Принимая теперь во внимание, что |S××| имеет порядок роста n2 при стремлении n к бесконечности, мы получаем утверждение 1. Возвратимся теперь к доказательству теоремы 9. Нам нужно доказать эту теорему в l2-норме. Конструкция, которую мы будем использовать в доказательстве, на самом деле одна и та же для всех норм lα. Начнем с нижней оценки. Пусть M - подмножество множества целых чисел, имеющее мощность N = |M|. Фиксируем целое число m. Следующий вопрос исследовался многими авторами (см., например, работы [14-16] и ссылки в них). 116 В. О. МАНТУРОВ Какова наибольшая мощность подмножества M× ⊂ M, для которого имеются нетривиальные решения уравнения a1 + ··· + am - am+1 - ··· - a2m = 0, (1) где ai,i = 1,..., 2m ∈ M? Что можно сказать в случае, когда N стремится к бесконечности? Ответ зависит, конечно, от того, как мы определим нетривиальное решение. Мы возьмем определение из работы [14] (множества, не имеющие нетривиальных решений аналогичных линейных уравнений, называются множествами Сидона). Решение уравнения (1) назовем тривиальным, если имеется в точности l различных элементов aj, так что если мы зафиксируем одно конкретное aj и положим все ak, не равные aj, равными 0, мы по-прежнему будем иметь решение. Например, при m = 4, решение a1 = a3 = 1, a2 = a4 =2 является тривиальным, в то время как решение a1 = 0, a2 = 2, a3 = a4 =1 нетривиально. В работе [14] доказано следующее утверждение Утверждение 2. Имеется бесконечная последовательность абелевых групп MN и подмно- N жеств в этих группах M× , для которых нет нетривиальных решений уравнения (1), где переменные принадлежат подмножеству, причем n растет как (1 + o(1))N 1/m, где N и n N обозначают мощности множеств MN и M× соответственно. Заметим, что если N достаточно велико, то мы можем считать, что n> N 1/m 1 . Следовательно, 2 если мы берем достаточно большое конкретное n, то N может быть выбрано не больше, чем 2nm = O(nm). Заметим теперь, что нетривиальные решения уравнения (1) могут быть рассмотрены также и как решения многих других уравнений (2), см. ниже. Например, если в некотором множестве M× ⊂ M мы имеем три элемента a, b, c, образующие арифметическую прогрессию c+a = 2b, то это приводит к нетривиальному решению уравнения (1): мы полагаем a1 = a, a2 = c, a3 = b, a4 = b. Более того, имеет место следующая очевидная Лемма 4. Пусть k < m и α1,..., αk - набор целых чисел, таких что |αi| < m и αi = 0. Тогда любое решение системы приводит к решению системы (1). k \ αibi =0 (2) i=1 Доказательство. Действительно, соберем отдельно все положительные αi и отдельно - все отрицательные αj. Пусть (b1,..., bk ) - решение уравнения (2). Для каждого положительного αi выберем αi штук переменных из числа a1,..., am и положим их равными bi, а для каждой переменной αj с отрицательным значением мы положим -αj элементов из числа am+1,..., a2m равными bj. Это возможно, так как |αi| < m. Теперь мы полагаем оставшиеся ak равными 0. Утверждение следует. M× Теперь мы модифицируем множество M× следующим образом. Пусть ˜ = M× + s, где прибавление s означает сдвиг на достаточно большое положительное число. Это число выбирается таким образом, чтобы отношение между минимальным модулем элемента из M× + s и максимальным m - 2 M модулем элемента из M× + s было строго больше, чем . Сначала мы рассматриваем × как m подмножество множества N натуральных чисел. Ясно, что s растет линейно с ростом m. Это делается для того, чтобы избежать решений уравнений (2), где переменные берутся из M×, а сумма M коэффициентов не равна нулю. Далее мы «расширяем» группу M; новая группа ˜ также будет циклической группой Z2f (s), где f (s) - натуральное число, большее, чем модуль максимального элемента из M, умноженного на m + 1. Теорема 10. Пусть βi, i = 1,..., k, - коэффициенты, такие что сумма |bi| четна и M× βi I= 0. Тогда у уравнений (1), (2) нет нетривиальных решений в ˜ ; кроме того, для того О ХРОМАТИЧЕСКИХ ЧИСЛАХ ЦЕЛОЧИСЛЕННЫХ И РАЦИОНАЛЬНЫХ РЕШЕТОК 117 же подмножеств нет нетривиальных решений уравнений k \ βici = 0. (3) i=1 Иными словами, построив абелеву группу и подмножество, для которых нет решений тех уравнений (1) и (2), у которых сумма коэффициентов равна нулю, мы можем легко «запретить» решения всех уравнений, где сумма коэффициентов не равна нулю, «сдвигая» наши множества на некоторое натуральное число μ(m), не зависящее от n. M Теперь мы готовы доказать основную теорему. Заметим сначала, что любое разложение четного n в сумму квадратов - это набор целых чисел, которые могут служить коэффициентами уравнений типа (2) или (3). Более того, подставляя элементы из ˜ ×, рассмотренные как целые числа, в уравнения (1), (2) или (3), мы получаем целое число, абсолютное значение которого меньше, чем λ(m)nm, где λ(m) - это некоторая функция от m, не зависящая от n. Фиксируем четное натуральное число m. i Рассмотрим все возможные представления числа n в виде суммы квадратов n2 целых чисел. Такое представление может содержать не более n слагаемых, более того, сумма этих слагаемых четна. M| Выберем теперь множество M× мощности n и абелеву группу M× ⊃ M мощности | ˜ = O(nm) так, чтобы уравнения (1), (2) не имели решения среди элементов этого множества. Сдвигая на M достаточно большое целое число множество ˜ M и подмножество ˜ × в нем, мы по-прежнему не будем иметь решения уравнения (3) в подмножестве. M Обозначим элементы из ˜ × на x1,..., xn и зафиксируем вектор (x1,..., xn) из Zn. Сопоставим теперь элементам (векторам) y = Zn целые числа (x, y⊗. Если две точки y, y× находятся на расстоянии √2m, то (y - y×, x⊗ I= 0. Действительно, координаты разности y - y× образуют разложение числа n в сумму квадратов, а числа x1,..., xn выбраны так, что для них не выполняется ни одно из уравнений (2), (3). Таким образом, скалярные произведения для таких точек различны. 1 Кроме того, (y× , x⊗ не превосходит числа (max |x|)m, которое растет как O(nm). M x∈ ˜ Таким образом, беря класс вычетов этого скалярного произведения по модулю λ(m)nm + 1, мы получаем раскраску пространства Zn с запрещенным расстоянием √2m в норме l2. Доказательство для любой другой нормы lα с той же самой оценкой полностью аналогично. 1. НИЖНИЕ ОЦЕНКИ ДЛЯ ХРОМАТИЧЕСКИХ ЧИСЕЛ ЦЕЛОЧИСЛЕННЫХ РЕШЕТОК Мы получили верхние полиномиальные оценки для хроматических чисел пространств Zn. Покажем теперь, что для многих фиксированных m показатели степеней в оценках c nm для χ(Zn, √2m) являются оптимальными. Пусть S - метрическое пространство и d - критическое расстояние. Назовем (M, D)-критической конфигурацией подмножество M ⊂ S мощности M, такое что для любого подмножества M× ⊂ M, для которого никакие две точки a, b ∈ M× не находятся на критическом расстоянии d, мощность |M×| не превосходит D. Согласно принципу Дирихле, если существует критическая (M, D)-конфигурация в S, то M χ(S, d) χ(M, d) D . Нижняя оценка для χ(Zn, 2) хорошо известна. Мы приведем ее здесь для целостности картины. Мы построим конкретную критическую конфигурацию. Фиксируем натуральное число n, и пусть S = Zn, M - множество всех точек из Zn, у которых три координаты равны единице, а остальные равны нулю, а M× - подмножество множества M, в котором никакие две точки не n находятся на расстоянии два. Ясно, что |M| = 3 . Любая точка из M× может быть рассмотрена как тройка координат, равных единице (все остальные координаты этой точки равны нулю). Теперь тот факт, что две точки x и y из M× находятся на расстоянии, не равном двум, означает в точности, что соответствующие им тройки либо не пересекаются, либо имеют в точности две общие координаты. Теперь легко видеть, что количество элементов из M×, для которых это условие 118 В. О. МАНТУРОВ выполняется, не превосходит n. Таким образом, M является (M, D)-критической конфигурацией, n(n - 1)(n - 2) где M = |M| = и D = n. 6 Следовательно, хроматическое число для Zn с критическим расстоянием 2 не меньше, чем (n - 1)(n - 2) . 6 Методы нахождения (M, D)-критических конфигураций широко используются для нахождения нижних оценок для хроматических чисел решеток в произвольных размерностях, при этом главным инструментом для нахождения таких конфигураций является теорема Фрэнкла-Уилсона [10]; дальнейшие модификации теоремы Фрэнкла-Уилсона см. в работе [2]. Теорема 11 (Теорема Фрэнкла-Уилсона). Фиксируем n-элементное множество N = {1,..., n}. Пусть p - степень простого числа, и пусть a - натуральное число, такое что a < 2p. Пусть, далее, M - набор a-элементных подмножеств множеств N , таких что мощность пересечения любых двух из них не равна a - p. Тогда |M| n . p - 1 Модификации теоремы Фрэнкла-Уилсона можно прочесть в работе [4]. Мы сейчас покажем, что для многих четных чисел 2m показатель m в верхней оценке nm для хроматического числа χ(Zn, √ m) является оптимальным для m, равного степени простого 2 числа. Действительно, достаточно рассмотреть подмножества множества N как элементы из Zn, координаты которых равны 1 и 0 (i-я координата равна единице, если и только если i ∈ N ). Приводимый ниже факт можно прочесть, например, в работе [2]; однако в точности это же рассуждение ранее использовалось для оценки хроматического числа для Rn, а не для Zn. Теорема 12. Пусть p - степень простого числа. Тогда χ(Zn, √2p) n 2p - 1 n . p - 1 Доказательство. Действительно, достаточно рассмотреть все векторы длины 2p - 1 и запретить векторам иметь «пересечение» длины p - 1, или, эквивалентно, запретить векторам быть на расстоянии √2p. Отсюда получаем требуемое. Таким образом, если p - степень простого числа, то мы доказали, что рост χ(Zn, √2p) является полиномиальным по n степени p. 2. ОЦЕНКИ ДЛЯ РАЦИОНАЛЬНЫХ РЕШЕТОК Qn Теорема 13. Для рационального k, которое может быть представлено в виде суммы двух k квадратов рациональных чисел, мы имеем χ(Q2, √k)= 2. В противном случае χ(Q2, √ )= 1. Пусть m = чисел. Тогда p √ l, где l - нечетное число, представимое в виде суммы двух квадратов целых q χ(Q3, m)= 2; χ(Q4, m) 4. Доказательство. Утверждения, относящиеся к Q2, очевидны. Перейдем теперь к Q3. Без ограничения общности мы можем считать, что m = √l. Раскрасим пространство Q3 в два цвета следующим образом. Пусть (a, b, c) ∈ Q3 и d - минимальный общий знаменатель чисел a, b, c. Запишем a = a× , b = b× , c = c× . В качестве цвета d d d мы возьмем вычет по модулю два числа a× + b× + c×. Очевидно, что если две точки находятся на расстоянии √l, то они имеют разные цвета. Заметим теперь следующее. Если хотя бы одно из чисел a, b, c ∈ Q имеет четный знаменатель в приведенном виде, то сумма квадратов чисел a, b, c не может быть целым числом. Аналогично, если хотя бы один из трех знаменателей содержит в качестве сомножителя 2k, то сумма трех квадратов О ХРОМАТИЧЕСКИХ ЧИСЛАХ ЦЕЛОЧИСЛЕННЫХ И РАЦИОНАЛЬНЫХ РЕШЕТОК 119 не может быть квадратом рационального числа, знаменатель которого содержит степень двойки, меньшую чем k. Теперь мы используем тот факт, что числа, имеющие разные степени двойки в знаменателях, «не взаимодействуют»: сумма квадратов трех целых чисел, по крайней мере одно из которых нечетно, не может быть четной. Теперь мы продолжим эту раскраску на те точки рациональной решетки, у которых координаты имеют четные знаменатели. Мы сначала сдвинем точки исходной решетки (с их цветами) на век- 1 торы , 0, 0 , 2 1 0, , 0 , 2 1 0, 0, 2 ; далее мы сдвинем нашу раскраску на координатные векторы длины 1 4 и т. д. Чтобы получить оценку для хроматического числа пространства Q4, мы сначала раскрасим точки, у которых ни одна из координат не имеет (в приведенной форме) знаменателя, делящегося на четыре. Каждый вектор v такого вида может быть записан как a b c , , , 2s 2s 2s d , где s - некото- 2s рое нечетное число (возможно, некоторые из чисел a, b, c, d четные). Такой точке мы сопоставим цвет α(v), равный классу вычета элемента a по модулю 2. a b c d a× b× c× d× Пусть v1 = , , , 2s 2s 2s 2s и v2 = , , , 2t 2t 2t 2t - два таких вектора; t и s - нечетные числа. Если |v1 - v2| = l, то имеет место одна из возможностей: либо все числа a - a×, b - b×, c - c×, d - d× нечетные (в этом случае α(v) I= α(v×)), либо все эти числа четные. Определим теперь β(v) следующим образом. Сначала мы определим β(v) для точек из Q4, координаты которых имеют нечетные знаменатели: β(v) будет просто равно сумме числителей. Далее мы продолжим определение на те точки, координаты которых имеют знаменатели, не деля- 1 щиеся на 4, посредством параллельных сдвигов на векторы , 0, 0, 0 , 2 1 0, , 0, 0 , 2 1 0, 0, , 0 , 2 1 0, 0, 0, . 2 Теперь мы видим, что если два вектора (v1, v2) со знаменателями координат, не делящимися на четыре, находятся на расстоянии √l, то либо α(v1) I= α(v2), либо β(v1) I= β(v2). Таким образом, мы построили раскраску в четыре цвета α, β для точек, у которых знаменатели координат не делятся на 4. Теперь мы продолжим эту раскраску сдвигами на векторы 1 , где l 2. Здесь мы используем 2l тот факт, что сумма квадратов четырех целых чисел, хотя бы одно из которых нечетно, не может делиться на 16. Теорема 14. Пусть m = √2lp, где l - нечетное число, такое что 2l представимо в виде q суммы квадратов двух целых чисел. Тогда мы имеем: χ(Q4, m) 4, следовательно, χ(Q3, m) 4. Доказательство. Доказательство для точек из Q4, координаты которых имеют нечетные знаменатели, повторяет рассуждение для Z4 из теоремы 7: вместо четностей целых чисел мы берем четности числителей дробей с нечетными знаменателями. Далее это раскрашивание продолжается на Q4 сдвигом на координатные векторы длины 1 , 2k k > 0, как в доказательстве теоремы 13. Здесь нужно принять во внимание, что сумма четырех квадратов целых чисел не может делиться на 8, если хотя бы одно из этих чисел нечетно. 3. РАСКРАСКИ НЕКОТОРЫХ КОНЕЧНЫХ ГРАФОВ Рассмотрим поля Z3 и Z5; мы построим графы Zn и Zm и снабдим их (псевдо)метрикой, которая 3 5 получается взятием обычной l2-метрики по модулю 3 (соответственно по модулю 5). Имеет место следующая 3 Теорема 15. χ(Zn, 1) c(√3 9)n. 120 В. О. МАНТУРОВ 3 Доказательство. Доказательство проводится индукцией по размерности n. Нам достаточно доказать, что для размерности n =2 + 3k мы имеем χ(Zn) 32k+1 для натуральных k. 3 Для Z2 мы будем использовать три цвета для раскраски девяти точек: в качестве цвета мы просто берем класс вычетов суммы трех координат по модулю три. 3 Пусть теперь у нас имеется правильная раскраска для Z2+3k ; построим правильную раскраску для Z5+3k 3 следующим образом. Мы красим первые 2+ 3k координаты в 3 2k+1 цветов и берем девять цветов для Z3. Цвет Z5+3k будет состоять из двух составляющих, одна из которых будет 3 3 представлять собой цвет первых 2+ 3k координат, а вторая - некоторый цвет для последних трех 3 × × × 3 × × × × координат. Вторая составляющая будет представлять собой один из девяти цветов, а именно, для трех последних координат (a, b, c) ∈ Z3 мы в качестве цвета возьмем пару (b - a, c - a) ∈ Z3 ⊕ Z3. Если для двух точек (a, b, c) и (a , b , c ) из Z3 мы имеем b - a ≡ b - a mod 3 и c - a ≡ c - a mod 3, то эти точки будут либо совпадать в случае, если a = a×, либо эти точки (a, b, c) и (a×, b×, c×) будут на расстоянии три, если a I= a×. В любом случае, так как расстояние берется по модулю 3, такая раскраска последних трех координат запрещает расстояния, сравнимые с единицей или двойкой по модулю три. 3 Мы утверждаем, что такая раскраска в для Z5+3k является правильной: никакие две точки на расстоянии, сравнимом с единицей по модулю три, не будут иметь один и тот же цвет. Действи- 3 тельно, если две точки x, y ∈ Z5+3k находятся на расстоянии, сравнимом с единицей по модулю три, то либо расстояние между их проекциями на первые три координаты сравнимо с единицей по модулю три, либо расстояние между их проекциями на последние три координаты не сравнимо с нулем по модулю три. В первом случае у них различается первая компонента цвета, а во втором случае у них различается вторая компонента цвета. Этим завершается шаг индукции. 5 Теорема 16. χ(Zn, 1) c×(√5)n. 3 5 5 Доказательство. Доказательство аналогично приведенному выше доказательству для Zn. Мы устанавливаем базу индукции, раскрашивая Z5 в пять различных цветов; после этого мы раскрашиваем Z2 в пять цветов таким образом, чтобы два точки имели один цвет тогда и только тогда, когда они находятся на расстоянии, сравнимом с нулем по модулю пять. А именно, для (a, b) ∈ Z2 мы в качестве цвета берем a - 2b mod 5. Далее мы осуществляем шаг индукции: для каждых следующих двух координат мы умножаем количество цветов на пять, откуда следует утверждение теоремы. Замечание 1. Приведенные выше оценки остаются верными, если вместо запрещенного расстояния 1 мы запретим все расстояния, сравнимые с единицей по модулю три (соответственно по модулю пять). 4. ОЦЕНКИ ДЛЯ РЕШЕТОК НАД АЛГЕБРАИЧЕСКИМИ РАСШИРЕНИЯМИ КОЛЬЦА Z Пусть p1,..., pk - набор целых чисел. Через Qp1,p2,...,pk мы обозначим кольцо рациональных чисел с знаменателями, взаимно простыми с p1 ... pk. Через Qodd мы обозначим множество рациональных чисел с нечетными знаменателями. odd Теорема 17. χ(Qn , 1) = 2. Более того, для любого расширения K кольца целых чисел, для которого существует гомоморфизм K → Z2 , мы имеем χ(Kn, 1) = 2. Доказательство. Действительно, предположим, что все знаменатели координат точек решетки являются нечетными. Тогда в качестве раскраски в два цвета мы берем вычет по модулю два суммы координат числителей. 3 Теорема 18. χ(Qn, 1) c(√3 9)n, где c - некоторая универсальная константа. Те же рассуждения остаются верными, если мы заменим Q3 на любое подкольцо поля R, допускающее гомоморфизм на Z3. 5 Теорема 19. χ(Qn, 1) c×(√5)n, где c× - некоторая универсальная постоянная. Более того, то же самое остается верным, если мы заменим Q5 на подкольцо поля вещественных чисел, допускающее гомоморфизм на Z5. О ХРОМАТИЧЕСКИХ ЧИСЛАХ ЦЕЛОЧИСЛЕННЫХ И РАЦИОНАЛЬНЫХ РЕШЕТОК 121 Последние две теоремы легко следуют из теорем 15 и 16. Идея состоит в использовании координат (x1,..., xn) по модулю три (соответственно по модулю 5) и применении полученных ранее оценок для χ(Zn) (соответственно для χ(Zn)). Здесь «взятие класса вычетов» понимается в смысле 3 5 соответствующего гомоморфизма колец. 5. НЕКОТОРЫЕ ОТКРЫТЫЕ ПРОБЛЕМЫ Мы выдвинули гипотезу о том, что все возможные запрещенные расстояния, для которых хроматическое число пространства Z3 равно 3, имеют вид 2k √12l + 10; кроме того, мы выдвигаем гипотезу о том, что хроматическое число 3 никогда не встречается в решетках бо´льших размерностей. Наилучшие известные верхние асимптотические оценки для хроматического числа рациональных пространств по-прежнему остаются такими же, как и для евклидовых пространств: (3 + o(1))n (см. [12]); метод получения этих оценок основан на некоторых разбиениях Вороного евклидовых пространств; иными словами, мы делим пространство на ячейки, каждую из которых красим в свой цвет. d Более того, каждая нижняя оценка на χ(Qn, √d) для некоторого конкретного n, √ происходит из конкретного конечного графа Γ из Qn с критическим расстоянием √d. Возможность получения точной оценки из конечного графа утверждает известная теорема Эрдеша-де Брейна [9]. Если мы рассмотрим такой граф для Qn и определим D как общий знаменатель всех координат всех точек графа, то мы можем построить гомотетичный ему граф DΓ в Zn с критическим расстоянием Dα. Таким образом, все нижние оценки для рациональных решеток на самом деле происходят из целочисленных решеток. Было бы интересно применить аргумент, приведенный в настоящей работе, для получения более точных оценок для Qn. Прямой подход не работает в связи с тем, что когда мы выбираем конкретное запрещенное расстояние, нам придется брать все возможные оценки для Dα, число которых стремится к бесконечности при стремлении n к бесконечности. Наши оценки для решеток с рациональными координатами с некоторыми ограничениями на знаменатели несколько лучше оценок для рациональных решеток без ограничений, полученных ранее, но наш подход использует другие идеи: некоторые теоретико-числовые свойства ограничений по модулю p. Было бы интересно получить другие оценки для χ(Qn), комбинируя эти два подхода: подход, предложенный в настоящей работе, и подход, связанный с разбиениями Вороного. Мы нашли верхние оценки для χ(Zn, √d) для любого фиксированного d при n, стремящемся к бесконечности. Если мы фиксируем конкретное значение n, то мы получим: для нечетного d достаточно двух цветов, для d, не делящегося на 3, достаточно c1(√3 9)n цветов, а для d, не делящегося на 5, мы получаем c2(√5)n цветов. Все эти верхние оценки лучше, чем оценки для рациональных решеток, т. е. (3+o(1))n. Таким образом, было бы интересно найти верхнюю оценку d для max(χ(Zn, √ )), где максимум берется по всем d, делящимся на 30. Возможно, аналогичные 30|d методы могут быть разработаны для других простых чисел, однако, такой подход для чисел, знаменатели которых не делятся на 7, аналогичный предыдущим подходам для чисел, знаменатели которых взаимно просты с 2, 3, 5, приводит к оценке, худшей, чем известная оценка для рациональных решеток.