О некоторых аналогах проблемы Борсука в пространстве Qn

В 1933 году Борсуком была поставлена задача о разбиении n-мерного множества на части меньшего диаметра (см. [1]). Обозначим через f (n) минимальное число частей меньшего диаметра, на которые разбивается любое ограниченное множество в R n . Назовем f (n) числом Борсука. Классическая гипотеза Борсука состояла в том, что f (n) = n +1. Однако она была опровергнута (см. [2]). Сейчас известно, что гипотеза верна при n ^ 3 и неверна при n ^ 298, а также установлены следующие асимптотические неравенства (см. [3—6]):

(1.225 ... + о(1))^ < f (n) < (1.224 ... + o(1)) n .

В настоящей работе рассматривается аналогичная задача, поставленная относительно пространства Q ⁿ .

Определим сперва величину f Q (n) как минимальное число частей диаметра, меньшего

• 1,    на которые можно разбить любое множество диаметра 1 в Q ⁿ .

Очевидно, что f Q (n) ^ f (n). Однако, как будет доказано ниже, верно и обратное.

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

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

Пусть m = f (n). Предположим, что f Q (n) < m. Рассмотрим множество A, которое в R n не делится на m — 1 часть. Если взять выпуклую оболочку A его замыкания, то она тоже не может делиться на m — 1 часть меньшего диаметра. Возьмем B = A П Q ⁿ . В силу того, что f Q (n) < m, множество B должно делиться на m — 1 часть меньшего диаметра. Воспользуемся тем, что множество рациональных чисел всюду плотно в множестве вещественных чисел. Тогда для любой точки x из A существует некоторая последовательность точек { x k } , x k ∈ Q ⁿ , x k → x . Так как частей конечное число, есть бесконечная подпоследовательность точек, принадлежащих одной части. Отнесем точку x к любой из таких

Настоящая работа выполнена при финансовой поддержке гранта РФФИ № 12-01-00683, гранта Президента РФ № MD-666.2012.1 и гранта НШ-2519.2012.1 поддержки ведущих научных школ.

частей. Мы получили разбиение A на m — 1 часть меньшего диаметра. Противоречие с предположением. Значит, f Q (n) ^ m.

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

2.    Постановка задачи. Формулировки результатов

В Qn возьмем произвольное множество A. Будем красить это множество в несколько цветов так, чтобы не было одноцветных точек на расстоянии 1. Минимальное число таких цветов назовем хроматическим числом множества A и обозначим xq(A). Величину max Xq(A)

AcQn назовем хроматическим числом размерности п и обозначим XQ(n). Наконец, через ХоАп) обозначим величину

X Q ,1M = . m ^max . ₁ X Q ^{( A )} .

A C Q n , diam A=1

Число XqAA послужит правильным аналогом числа f (п). Дабы понять, что из себя представляет величина X Q ,i (n), посмотрим, как она ведет себя в малых размерностях.

Очевидно, что X q , i (1) = 2. Вообще, это число не меньше числа S(п) вершин правильного (рационального) симплекса А С R ⁿ максимальной размерности (с длиной стороны 1) и не больше числа Борсука f (п) и хроматического числа Х о (п}- Но для Q ² и Q 3 хроматическое число равно двум, а для Q ⁴ — четырем (см. [7––9]), причем число вершин рационального симплекса максимальной размерности (в R ² , R ³ и R ⁴ соответственно) равно тому же (см. [10]). Итак,

^X Q ,1 ⁽¹⁾ = ^x Q , 1 ⁽²⁾ = ^X Q ,1 (З) = 2, ^x Q , 1 ⁽⁴⁾ = 4.

Естественно возникает вопрос: может быть, во всех размерностях эта величина равна числу S (п) вершин правильного рационального симплекса А С R ⁿ максимальной размерности? С одной стороны, эта гипотеза созвучна гипотезе Борсука в соответствии с поправкой на выбранное пространство. С другой стороны, величина S (п) подсчитана (см. [10]), и, если бы удалось доказать эту гипотезу, было бы получено и точное значение величины ХоАп)- К сожалению, гипотеза неверна. Удается доказать следующий результат.

Теорема 1. Имеет место неравенство

XqAA >

n

= (1.225 ... + 5 1 (п))Л

5 1 = о(1)

при n → ∞ .

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

Назовем аффинной размерностью множества A минимальную размерность пространства, которое его содержит, и обозначим ее affdimA. Теперь рассмотрим величину xQffi(n) = max,. .   xq(a).

A: affdim A=n, diam A=1

Эта величина послужит другим рациональным аналогом числа Борсука. В данном случае мы обращаем внимание на «реальную» размерность множеств, то есть на размерность подпространств, их содержащих. Смысл этой величины в том, что во внутренних координатах плоскости точки множества уже не будут рациональными, поэтому перейти к «реальной» размерности (как мы бы сделали в вещественном случае) нельзя. В принципе можно ожидать, что Хои(п) ^ X Q ,i (n)- Однако нам лишь удается доказать следующий результат.

Теорема 2. Имеет место неравенство xQffi(n) >

((-з)

+ ^ 2 (n)^

(1.225 ... + d 2 (n)) Vn,

^ 2 = o(1)

при n ^ TO .

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

С точки зрения размерностей контрпримеров различие между аффинным и неаффинным случаями также невелико. Верны следующие теоремы.

Теорема 3. Для величины X Q ,1 (n) гипотеза неверна при всех n ^ 946.

Теорема 4. Для величины Х ои (п) гипотеза неверна при n Е [561, 757] и при всех n ^ 903.

Дальнейшая структура статьи следующая: в разделе 3 мы докажем теоремы 1 и 2, а в разделе 4 — теоремы 3 и 4. В разделе 5 будет рассмотрен аналог рациональной задачи Борсука для метрики l p .

3.    Доказательства теорем 1 и 2

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

Итак, пусть p — простое число, ближайшее к [5n], где 5 = 1 — —з. Рассмотрим множе ство

S = { (x 1 ,..., x n ) | x 1 = 1, x i Е { — 1, 0,1 } , x 1 + ... + х П = p} .

Заметим, что скалярное произведение любых двух векторов из X заключено в границах — p < (х, у) С р. Более того, для любых двух векторов х = у верно (х, у) = 0 mod p О О (х,у) = 0.

Для каждого вектора х = (х1,..., xn) рассмотрим вектор х х х = (х1х2, х1х3,.

.

. , x 1 x _n , x 2 x 3 , . . . , x 2 x _n , . . . , x _{n -} 1 x _n , ₂ x ₁ , .

..

, ₂ x _n , ₂ x ₁ , .

, 2 ^хп) . ⁽¹⁾

Таким образом, множеству X, состоящему из векторов x, ставится во взаимно однознач ное соответствие множество X*, состоящее из векторов х х х. В частности, |X*| = |X| = = Cnp-^p-1, чем мы воспользуемся позднее. В то же время размерность множества X* не

превосходит m = C n2 + 2n =

n ( n + 3) 2

Если же мы будем говорить об его аффинной размер-

ности (что требуется как раз для теоремы 2), то она не превосходит m = С П + n =

n ( n + 1) 2

.

Именно в этих разных оценках размерностей кроется различие полученных оценок чисел

Борсука. Заметим, что доказательства двух теорем отличаются только в этом месте. Далее имеем

nn

5252 x i x j у і У з = i =i j =1

(ft **) 2 =

(x,y) ² .

С другой стороны, nn                                n

52 52 x ' x j y ' y j = 2 52 x ' x j y ' y j + 52 x ' x j y ' y j = 2 52 x ' x j y ' y j + 52 x ² y ² = 2(x х x, y х y).

'=1 j =1                  i=j                 i              '=1

В итоге (x х x, y х y) = 2 (x, y) ² , откуда следует, что

| x х x — y х y | ² = (x х x, x х x) + (y х y, y х y) — 2(x х x, y х y) =

= 2 (x, x) ² + 2 (y, y) ² — (x, y) ² = p ² — (x, y) ² .

Очевидно, что максимальное расстояние достигается тогда и только тогда, когда (x, y) = 0. Более того, это максимальное расстояние равно p, т.е. его можно считать единичным (нам доступна любая рациональная нормировка). Таким образом, построенная конструкция отвечает условиям задачи.

Докажем следующую лемму.

Лемма 1. Пусть Q С X таково, что для любых x, y G Q верно, что (x, y) = 0. Тогда p-1 [(p-1-')/2]

I Q I «X E ¹¹

'=0    j=0

Доказательство. Каждому вектору x G X сопоставим многочлен F _x G Z _p [y ₁ ,..., y _n ], задаваемый следующей формулой:

p - 1 зд) = П^{( і —} (^y)). '=1

Тогда, очевидно, для любых x, y G X верно, что F _x (y) = 0 mod p О (x, y) ^ 0 mod p. Перепишем F¹ _X (y) в виде

F x (y)=Ecy a i ¹

•

^α is . . . • ^y ' s ,

где a ' 1 + ... + a ' s « p — 1. Теперь заметим, что так как мы возводим в степень только ± 1 или 0, то степени выше второй нам не нужны, т.е. можно заменить все степени на 1 или 2 соответственно. Получается новый набор многочленов ^_F _X (y) |, дающий те же результаты на наших векторах.

Докажем, что полиномы из множества ^F _x i (y) j* i линейно независимы над Z _p , коль скоро Q = { x ₁ ,..., X t } . Так как (X i , X i ) = 0 mod p, значит, F x i (X i ) = 0 mod p, в то же время (X i ,X j ) = 0 mod p при i = j, следовательно, F x i (X j ) = 0 mod p. Подставляя X i вместо y, получаем

C i F x 1 (x i ) + ... + C s F x s (x i ) = c i mod p.

Отсюда сразу следует линейная независимость.

Получается, что p-1 [(p-1-i)/2]

| Q | < dim {f,} <52  52 C i, cn - .

i=0    j=0

Лемма доказана.

Заметим, что согласно принципу Дирихле выполнено неравенство l^*l xQ,i(m) ^ |Q ^

2 ^{р -1} С П - 1

p - 1 ^[(p^{-1- i ) / 2]}

Е i=0

E j=0

^C n ^{i C} n ^j - i

= to+o(1)) ■

Последнее равенство получено за диться не будут (см. [12]).

счет

аналитических выкладок, которые здесь приво-

Теперь вспомним об оценках для m, разных для двух теорем. В первой теореме, если учесть, что m = ( ^ ^^ ~ nj- ^ n ~ V 2 V m, получаем итоговую оценку

X Q ,1 ^{( m )} >

+ 5 1 (m)^    =(1.225 ... + 5 i (m)) ^ m .

Аналогично для теоремы 2 m = ( ^ —) ~ n2- ^ n ~ V 2 V m Получаем x Q ^ffi (m) > (1.225 ... + 5 2 (m)) ^m .

Теоремы 1 и 2 доказаны.

4.    Доказательства теорем 3 и 4

Этот раздел мы подразобьем на два параграфа. В первом параграфе мы объясним, почему гипотеза неверна при всех п ^ 903 (п ^ 946). Во втором параграфе мы разберемся с размерностями из промежутка [561, 757] (только для аффинного случая).

• 4.1.    Случай n ^ 903 ( n ^ 946 )

Если при доказательстве теорем 1 и 2 мы следовали логике из работы [11], то здесь мы объединим идеи из работ [13, 14].

Пусть m = 4p ^a , где p простое, а a натуральное. Рассмотрим два множества векторов

S 1 = |(x i ,.

.

m

. ,X _m ) | x₁ = 1,x i G { — 1,1 } ,^^x i = 0 mod 4

,

E = |(X 1 , .

i =1

m

.

.,X m ) | X 1 = X 2 = 1,X i G {- 1, 1 }, ^ X i = 0 i=1

mod 4 ^ .

Ясно, что | S 1 | = 2 ^{m -2} , | S ₂ | = 2 ^{m -3} .

Как и в разделе 3, осуществим переход от множеств S 1 , S ₂ к множествам S i , S 2 по формальному правилу (1). Снова получим биекцию между множествами с одним и тем же „™                m⁽m - ¹

номером. При этом размерность n множеств S1 и S2 не превосходит Cm =---2---• Здесь важно, что всегда х2 = 1, т.е. последние 2m координат каждого вектора xxx фиксированы, а параллельным переносом с точки зрения размерности даже в неаффинном случае можно пренебречь (впрочем, последние 2m координат на расстояния вовсе не влияют, так что их с самого начала можно убрать). Аффинная размерность naff этих же множеств не

₂   m ( m — 1)     ₂

( m — 1)( m — 2)

превосходит соответственно C m = ---2--- и C m - 1

принимает значения из множества

. Подчеркнем, что m

M = {8,12,16,20,28,32,36,44,52,64,... }, стало быть, n пробегает множество

N = { 28,66,120,190,378,496,630,946,1326,2016,... } , а n aff ^—

N aff = { 21, 28, 55, 66,105,120,171,190, 351, 378,465,496, 595, 630, 903, 946,1275,1326,

1953, 2016,... } .

Снова имеем (как для векторов из S1, так и для векторов из S2) |х x х — y x у|2 = m2 — (х, у)2, т.е. максимальное расстояние достигается тогда и только тогда, когда (х, у) = 0, и это расстояние рационально.

Имеют место аналоги леммы 1 из раздела 3.

Лемма 2. Пусть Q С S1 таково, что для любых х, у G Q верно, что (х, у) = 0. Тогда pα-1

iqi « Е C m - 1 .

i=0

Лемма 3. Пусть Q С S2 таково, что для любых х, у G Q верно, что (х, у) = 0. Тогда pα-1

I Q I « Е C m - 2

i=0

Доказательства обеих лемм очень похожи на доказательство леммы 1. Кроме того, их можно найти в обзоре [3] и книге [12]. Поэтому здесь мы их не приводим.

В итоге действуем получаем неравенства

так же, как в конце раздела 3: ссылаясь на принцип Дирихле,

) >    >

₂ m - 2

p ^α - 1

^C m ⁱ - 1 i=0

. x ff n .. ) > -— >

₂ m - 3

p ^α - 1 ^C m ⁱ - 2 i=0

, X Q ,i ^{( n )} >  p a

₂ m - 2

- 1

^C m ⁱ - 1 i=0

.

А дальше двигаемся вдоль множеств M , N _aff и следим за возникающими оценками:

x Q ^ff1 (903) > -2----= 1063.06 ... > 947, x Q ^ff1 (946) > -2----= 1649.87... > 1276,...

Q,              10                                         Q,

ЕП iЕ

C42

i=0

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

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

XQ ,1 (946) >   ---= 1649.87... > 1327,    x q , 1 (1326) >   ---= 5049.5 ... > 2017,...

Е С4з i=0

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

• 4.2.    Случай n Е [561 , 757]

Тут мы применим в чистом виде конструкцию из работы [15]. Положим m = 36 = 4 • 3 ² (ср. §4.1) и рассмотрим

X =

। ( Х 1 , . . . ,X m ) | Х 1 = Х 2 = X 3 = 1,X i

m

Е{- 1,1 } ,]Txi ^ 0

i=1

mod 4

,

так что | X | = 2 ^{m -4} . Все очень похоже на технологию из раздела 3 и параграфа 4.1. Однако на сей раз мы перейдем к X * по правилу, которое слегка отличается от (1). А именно, мы будем попарно перемножать все x i , Xj , у которых i Е { 2,..., m } , j Е { 4,..., m } . Тогда биекция между X и X * по-прежнему имеет место, причем аффинная размерность X * не превосходит 561 = ⁽ m - 2 2   - ³⁾ .

Далее,

| Х х X — у х у | ² = 2(m — 1)(m — 3) — 2((X, у) — 1)((X, у) — 3).

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

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

Лемма 4. Пусть Q С X таково, что для любых х, у Е Q верно, что (х, у) = 0 и (х, у) = 4. Тогда iqi « Xcm-3- i=0

Доказательство леммы можно найти в [15]. А применение очевидно:

x Q 1 (561) >  ²     > 758.

Е С3з i=0

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

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

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

5.    Обобщение на случай метрики lp

Для пространства Q ⁿ с метрикой l _p можно поставить аналогичные задачи и доказать асимптотические оценки. Число Борсука в этой метрике обозначим X Q ,1 (n,P), а в аффинном случае — x Q ^ff1 (n,P). Предположим, что p G N.

Возьмем множество

X =

| (x 1 , . . . ,X n ) | x i = 1,X i

n

G { — 1,1 } ,]Tx i ^ 0

i=1

mod 4

,

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

x X x = (x 1 x ₂ ,..., x 1 x n , x ₂ x ₃ ,..., x ₂ x n ,.

x n - 1 x n , a 1 x 1 , . . . , a 1 x n , . . . , a s x 1

. , a s x n ) .

Числа a i G Q и s G N будут подобраны позже. Размерность множества X * при этом не ^п (^|^^ 1 )

превосходит С П = --2-- в аффинном случае и С П + sn — в неаффинном.

Рассмотрим расстояние между векторами в новообразованном множестве. Согласно выбранной метрике получаем

|х X x _ у X yip = ^2 ixixj — УіУз Ip + i

sn X ap • X i=1       j=1

|xj

— yj Ip.

В силу того, что x_i,y_iG { — 1,1}, каждый модуль в правой части равен двум или нулю.

Вынося двойку, можем изменить степень:

|x X x — у X y|p = 2p 2 I ^ ixixj — УiУj I2 + i

(Xap)-Xixj — j) .

n

Введем форму (x, у) = ^xiyi. Это по сути скалярное произведение в метрике l2. Полагая i=1 s r = ^ ap и не забывая, что (x, x) = n, без труда получаем i=1

|x X x — у X y|^p= 2^p-2(n²+ 2rn — (x,у)²— 2r(x,у)).

Подберем r так, что 2r|(x, у)| < 1. В этом случае максимальное расстояние будет достигнуто тогда, когда (x, у) = 0. Если же выбор r сделает это расстояние, равное p/2^p-2n(n + 2r),

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

Очевидно, что сколь угодно близко к числу 2^Р

щееся p-й степенью рационального числа. Взяв r =

2_n2 ^q

находится число q > 2^{p 2}n², являю

2^p-1n

n

2, мы получим рациональность

максимального расстояния. Покажем, что r можно представить в виде суммы a_i^p, a_iG Q. В самом деле, поскольку p G N, имеем r G Q, а значит,

и = uvp¹

v      v^p

Далее, uvp¹G N. Но хорошо известно, что существует такое A(p) 6 N, при котором любое ^А(р)

натуральное число представимо в виде суммы   bip с подходящими натуральными bi (см., i=1

^x(p)

например, [16]). Следовательно, uvp-1 = 22 bp. В итоге i=1

₌uvp ¹ r     _vp

A(p)

= Е (v У i=1

Взяв s = A(p), а ai = v, мы получим нужное нам r.

Мы знаем, что |Е| = 2n^-2, мощность же максимального подмножества M, не содержащего векторов X, у, таких, что (X, у) = 0, уже посчитана в лемме 2. Итоговые оценки имеют вид

|Σ|                                                                             |Σ|

XQ,1(n,p) > |M = (1.203 ... + 51 (n))^, Xq>,P) > M = (1.203 ... + §2(n)), 5i = o(1).

Суть в том, что даже СП + sn ~ — (s зависит только от p).

Мы разобрались лишь со случаем p ∈ N. По-видимому, с другими p все значительно сложнее.