«Карас в Роман Николаевич е О ПОКРЫТИЯХ ВЫПУКЛЫМИ МНОЖЕСТВАМИ 01.01.09 — дискретная математика и математическая кибернетика Диссертация на соискание ученой степени кандидата физико-математических наук Научные ...»

МОСКОВСКИЙ ФИЗИКО-ТЕХНИЧЕСКИЙ ИНСТИТУТ

(ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ)

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

Карас в Роман Николаевич

е

О ПОКРЫТИЯХ

ВЫПУКЛЫМИ МНОЖЕСТВАМИ

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

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

Научные руководители:

член-корреспондент РАО, доктор физико-математических наук, профессор Г.Н. Яковлев;

доктор физико-математических наук, профессор В.Л. Дольников.

Долгопрудный Оглавление Введение Некоторые обозначения 1 О трансверсалях семейства транслятов двумерного выпуклого компакта 1.1 Формулировка результата........................... 1.2 Вспомогательные факты............................ 1.3 Доказательство основной теоремы...................... 2 M -сильная выпуклость и порождающие множества 2.1 Введение.................................... 2.2 Вспомогательные факты............................ 2.3 Доказательство теоремы 2.3......................... 2.4 Применение теоремы 2.3........................... 2.5 Эквивалентность M -сильной выпуклости и M -выпуклости........ 2.6 Доказательство аналога теоремы Каратеодори............... 2.6.1 Сведение доказательства к лемме 2.23............... 2.6.2 Доказательство леммы 2.23..................... 2.7 Тела постоянной ширины........................... 2.7.1 Основные понятия и результаты................... 2.7.2 Доказательства............................ 3 О назначении точек гиперграням многогранника 3.1 Введение.................................... 3.2 Формулировка основных результатов.................... 3.3 Вспомогательные утверждения........................ 3.4 Доказательства основных результатов.................... 3.5 Следствия доказанных теорем........................ Литература i Введение Интерес к исследованиям в области дискретной геометрии и выпуклого анализа в последние десятилетия вызван значительным прогрессом в развитии вычислительной техники, который сделал возможным решение разнообразных задач геометрической оптимизации и управления и привел к постановке многих новых задач в этой области.

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

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

Одним из фундаментальных результатов выпуклого анализа является теорема Хелли (см. [2]). Она утверждает, что конечное семейство выпуклых множеств в Rn имеет непустое пересечение тогда и только тогда, когда любое подсемейство из не более чем n + 1 множества имеет непустое пересечение. В книге Л. Данцера, Б. Грюнбаума и В.

Кли [2] содержатся разные приложения теоремы Хелли и ее обобщения, в частности, топологическая теорема Хелли, которая утверждает, что в теореме Хелли достаточно вместо выпуклости требовать гомологической тривиальности всех множеств семейства и всех их непустых пересечений.

Один из путей обобщения теоремы Хелли связан с понятием k-трансверсали семейства множеств — такого множества из k точек, которое пересекается с любым множеством семейства. Теорема Хелли утверждает, что конечное семейство выпуклых множеств имеет 1-трансверсаль тогда и только тогда, когда 1-трансверсаль имеет любое подсемейство из не более чем n + 1 элемента.

Однако, для k-трансверсалей при k 2 аналог теоремы Хелли не верен ни при какой константе вместо n + 1. Тем не менее (см. обзор [4]) при рассмотрении других классов семейств аналогичные результаты могут быть установлены. Кроме того, в аналогах теоремы Хелли можно требовать выполнение более сильных условий, чем существование k-трансверсали достаточно малых подсемейств. В частности, Б. Грюнбаумом была сформулирована гипотеза о том, что семейство транслятов выпуклого компакта на плоскости имеет 3-трансверсаль, если любые два множества из этого семейства пересекаются.

Ранее в литературе приводились частичные доказательства этой гипотезы в случае евклидовых кругов [5, 6], треугольников [7], центрально симметричных множеств [8] или множеств постоянной ширины [9].

Глава 1 посвящена полному доказательству гипотезы Грюнбаума. В процессе доказательства установлено, что эта гипотеза допускает переформулировку в терминах покрытий одного выпуклого множества транслятами другого, поэтому она аналогична вопросу о количестве частей меньшего диаметра, на которые можно разрезать выпуклое множество в Rn (задача Борсука), а также вопросу о количестве гомотетически уменьшенных копий, необходимых для покрытия фигуры заданного выпуклого множества (задача Хадвигера).

В главе 2 излагается ряд результатов, связанных с понятием M -сильной выпуклости и порождающего множества.

Понятия сильной выпуклости возникло как некоторое усиление понятия строгой выпуклости. Сильно выпуклые множества с радиусом R, то есть множества, образованные пересечением шаров радиуса R, использовались в работах Б.Т. Поляка, A.

Pli`, М.А. Красносельского и А.В. Покровского в приложении к задачам оптимизации.

В работе H. Frankowska и Ch. Olech [16] подробно изучались свойства сильно выпуклых множеств радиуса R, были установлены критерии сильной выпуклости в терминах опорной функции и доказано утверждение, что множество является сильно выпуклом радиуса R тогда и только тогда, когда вместе с любыми двумя точками оно содержит любую дугу радиуса R и длины не более R с концами в этих точках.

В работах Е.С. Половинкина (см. [13]) были установлены новые свойства сильной выпуклости, были доказаны аналоги теорем Крейна-Мильмана и Каратеодори в конечномерных пространствах и исследованы сильно выпуклые аппроксимации множеств и функций. Эти результаты позволили Г.Е. Иванову и Е.С. Половинкину в [12] получить новые алгоритмы второго порядка в теории дифференциальных игр.

Е.С. Половинкин ввел понятие M -сильно выпуклого множества, где M — любое замкнутое выпуклое множество: M -сильно выпуклым множеством называется любое пересечение транслятов M. При этом оказалось, что результаты о сильной выпуклости радиуса R можно перенести на M -сильную выпуклость только тогда, когда множество M удовлетворяет одному дополнительному условию: для любого M -сильно выпуклого множества A найдется множество B такое, что A + B = M в смысле суммы Минковского. Такие множества M были названы порождающими. Сильная выпуклость и порождающие множества изучались в работах Е.С. Половинкина и М.В. Балашова [15, 14]. Был доказан аналог теоремы Каратеодори для M -сильной выпуклости в случае строго выпуклого M и в общем случае с большей константой n2 +1. Кроме того, понятие M -сильной выпуклости было исследовано и в бесконечномерных банаховых пространствах. Также были найдены приложения M -сильно выпуклых множеств к задачам оптимизации.

В книге Л. Данцера, Б. Грюнбаума и В. Кли [2] приведено еще одно усиление ками оно содержит и пересечение всех транслятов M, содержащих эти две точки, или в нашей терминологии: вместе с любыми двумя точками содержит их M -сильно выпуклую оболочку. Авторы указывают, что эквивалентность понятий M -выпуклости и M -сильной выпуклости (которая там так не называется, но фактически эквивалентна ей) в двумерном случае была известна.

Одним из результатов главы 2 является доказательство теоремы 2.3, которая позволяет несколько упростить проверку того, что множество M порождающее, сводя проверку по определению порождающего множества к проверке пересечений пар его транслятов.

В главе 2 также доказывается аналог теоремы Каратеодори для M -сильной выпуклости при условии, что M — порождающее множество без ограничений на его строгую выпуклость и с константой n + 1. Доказательство использует топологическую теорему Хелли и одно топологическое свойство разности выпуклых множеств (лемма 2.23). Кроме того, приводится контрпример, показывающий, что без условия, что M порождающее, аналог теоремы Каратеодори не верен.

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

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

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

Многие результаты, относящиеся к этому понятию, содержатся в книге Т. Боннесена и В. Фенхеля [23]. Там же были приведено доказательство следующего утверждения:

любое множество диаметра 1 может быть вложено в множество постоянной ширины Вложения в множество постоянной ширины изучались и для случая пространств с произвольной (не евклидовой) нормой. E. Meissner в [25] доказал, что в двумерном случае это утверждение остается верным, H. G. Eggleston в [24] показал, что оно верно не для всех норм начиная с размерности 3, однако оно верно не только для евклидовой нормы, но и для нормы l. Вопрос же о характеризации норм, в которых это вложение всегда возможно, оставался открытым.

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

В главе 3 изучается серия задач, связанных с назначением точек гиперграням многогранника. В.В. Произволов на конференции по комбинаторной геометрии в Батуми в 1985 году (см. [30]) сформулировал следующую гипотезу: если дан выпуклый многоугольник P на плоскости со сторонами S1,..., Sn и точки a1,..., an, то точки ai можно перенумеровать так, что n треугольников, образованные вершинами pi и основаниями Si соответственно покроют P.

Эта гипотеза была доказана А.В. Богомольной, Ф.Л. Назаровым и С.Е. Рукшиным (см. [28]), кроме того, было доказано, что при некоторой перенумерации соответствующие треугольники будут попарно неперекрывающимися.

А. Бездек в [27] исследовал случай гипотезы Произволова, когда точки не обязательно лежат внутри многоугольника и доказал этот гипотезу в этом случае. Кроме того, был исследован случай утверждения о неперекрывающихся треугольниках, когда точки не обязательно лежат внутри многоугольника, в результате была доказан вариант, в котором число точек было меньше числа сторон и равно p = m. Также была сформулирована гипотеза о том, что константа p может быть сделана равной Независимо и одновременно с автором гипотеза Бездека для многогранника и некоторые обобщения результатов [28] на многогранники в Rn были доказаны С.Е.

Рукшиным и Ф.В. Петровым в [29] с использованием методов, существенно отличных от методов данной работы. В главе 3 приведены доказательства этих результатов:

гипотеза Бездека (теорема 3.1) и два следствия 3.4 и 3.5.

В главе 3 усилены результаты работ [28, 29] (теоремы 3.2 и 3.3) и из них выведено следствие 3.15, которое устанавливает одно замечательное свойство некоторого класса разбиений Rn. Основным методом доказательства является топологическая лемма 3. о покрытии одного множества некоторым семейством множеств.

Автор признателен Е.С. Половинкину и М.В. Балашову за обсуждение результатов главы 2, которое позволило сделать изложение более кратким и ясным, и кроме того, М.В. Балашову за внимательное редактирование текста главы 2 и полезные замечания.

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

Г.Н. Яковлева за всестороннюю поддержку и полезные советы при подготовке текста.

Некоторые обозначения 1. |X| — мощность множества X, для всех бесконечных множеств будем писать 2. Im = {1, 2,... m} — множество индексов и S m — группа перестановок на Im.

4. cl X, int X, bd X — замыкание, внутренность и граница множества X, которое является подмножеством некоторого топологического пространства.

5. conv V, lin V, a V — выпуклая, линейная, аффинная оболочка множества V, являющегося подмножеством некоторого линейного пространства.

6. rint V — относительная внутренность множества V, являющегося подмножеством некоторого конечномерного линейного пространства, то есть его внутренность в топологии пространства a V.

7. [a b], (a b) — для точек a и b в некотором линейном пространстве отрезок с концами в a и b и rint [a b].

8. Сумма Минковского непустых множеств A и B, которые являются подмножествами некоторого линейного пространства:

Если множество B состоит из одной точки b, то будем для краткости обозначать 9. Геометрическая разность двух непустых множеств A и B, которые являются подмножествами некоторого линейного пространства:

или, эквивалентно, 10. conv F — выпуклую оболочку множества функций F на некотором топологическом линейном пространстве L. Это функция, надграфик которой совпадает с замыканием выпуклой оболочки надграфиков всех функций из F.

11. diml V, dima V, codim V — линейная и аффинная размерность, коразмерность подмножества V некоторого линейного пространства. Если V — линейное подпространство, то будем просто писать dim V вместо diml V, если V — аффинное подпространство, то будем просто писать dim V вместо dima V 12. dist(a, b), dist(A, B), diam A в некотором метрическом пространстве — расстояние между точками a и b, расстояние между подмножествами A и B, диаметр подмножества A.

13. l, x — значение на векторе x L линейного функционала l L. Здесь L — некоторое линейное пространство. Для L = Rn пространство L также отождествляется с Rn.

14. (x, y) — скалярное произведение векторов в пространстве со скалярным произведением. Будем считать, что в Rn задано скалярное произведение (x, y) = 15. Пусть Ln — пространство линейных функций на Rn. Для f Ln обозначим (a) H(f ) = {x Rn : f (x) = 0} — гиперплоскость;

(b) H (f ) = {x Rn : f (x) < 0} — открытое полупространство;

(c) H + (f ) = {x Rn : f (x) 0} — замкнутое полупространство.

Глава О трансверсалях семейства транслятов двумерного выпуклого компакта 1.1 Формулировка результата В известном обзоре [1] (см. [2, 3], а также [4] гл. 2.1 стр. 407 гипотеза 6.2), Грюнбаумом была поставлена следующая задача: для семейства транслятов выпуклого компакта на двумерной плоскости, в котором любые два множества пересекаются, существует 3-трансверсаль, то есть такие три точки, что каждое множество семейства содержит хотя бы одну из них. В литературе приведены частичные решения в случае евклидовых кругов [5, 6], треугольников [7], центрально-симметричных множеств [8] или множеств постоянной ширины [9]. В настоящей работе дается решение этой задачи:

Теорема 1.1. Для семейства F = {K + x : x X} транслятов выпуклого компакта K в R2, в котором любые два множества пересекаются, существует 3трансверсаль.

В [4] содержится также информация по поводу аналогичных утверждений в Rn, n 3, а именно: об оценке порядка трансверсали семейства транслятов выпуклого компакта, в котором любые два множества семейства пересекаются. Далее из формулировки теоремы 1.2 будет видно, что эта задача аналогична вопросу о разрезании фигур на меньшие части (задача Борсука), а также задаче о покрытии фигуры ее уменьшенными копиями (задача Хадвигера).

1.2 Вспомогательные факты В этой части будут приведены доказательства необходимых вспомогательных результатов. Сначала переформулируем утверждение теоремы 1.1.

Теорема 1.2. Если X X K K для множества X R2 и выпуклого компакта K, то X можно покрыть тремя транслятами K.

Замечание. Так как множество K K центрально-симметрично, то условие X X K K не меняется при замене K на K, так что далее, при доказательстве теоремы 2, мы будем писать просто K.

Лемма 1.3. Теоремы 1.1 и 1.2 эквивалентны.

Доказательство. Покажем, что теорема 1.1 следует из теоремы 1.2. Так как (K + x1 ) (K + x2 ) =, то для любых x1, x2 X найдется такая точка p, что p = x1 + y1 и По теореме 1.2 существуют такие точки x1, x2, x3, что для любой x X найдется такое i = 1, 2, 3 и y K, что x = xi y или, иначе говоря, для xi x + K всех x X и для некоторого i, что и требуется в теореме 1.1.

В обратную сторону утверждение доказывается теми же самыми рассуждениями в обратном порядке.

Замечание. Далее будем считать, что int K =, так как иначе K одномерно, и тогда, очевидно, в теореме 1.1 найдется 1-трансверсаль.

Определение. Для ограниченных множеств X, K Rn (int K = ) отношение длин проекций X и K на вектор a S n1 (S n1 — единичная сфера) будем называть шириной X в направлении a относительно K и обозначать w(X, K, a).

Очевидно, что и что w(X, K, a) равно расстоянию между параллельными опорными гиперплоскостями к X с направляющим вектором a в банаховой метрике dB (x, y), задаваемой единичным шаром B1 = K K.

Следующая простая лемма проясняет геометрический смысл включения X X Лемма 1.4. Данные утверждения равносильны:

ii) X имеет диаметр diam X 1, в метрике dB (x, y), B1 = K K.

iii) w(X, K, a) 1 для любого a.

Доказательство. (ii) (iii) Очевидно.

(iii) (i) Множества K K и X X центрально симметричны с центром в 0, а K K — выпукло и поэтому является пересечением центрально симметричных полос с центром в 0. Так как w(X, K, a) = w(X X, K K, a) 1, то выпуклая оболочка Из леммы 1.4 следует, что множество X в теореме 1.2 можно считать выпуклым, так как условие (iii) леммы не меняется при замене X на conv X.

Лемма 1.5. Если B — двумерное банахово пространство с единичным шаром B1, а X B и diamB X 1, то существует такой выпуклый компакт F, что X F и w(F, B1, a) = 1/2 для всех a B.

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

Доказательство. По теореме 2.4 множество B1 — порождающее (см. главу 2), а по теореме 2.5 множество X можно вложить в множество F постоянной ширины относительно данной нормы, что и означает, что w(F, B1, a) = 1/2 для всех a B.

Таким образом, теперь теорема 1.2 с помощью леммы 1.5 может быть выведена из своего частного случая:

Теорема 1.6. Если X, K R2 — выпуклые компакты и X X = K K, то X можно покрыть тремя транслятами K.

Замечание. Условие X X = K K равносильно тому, что X и K имеют одинаковую ширину в любом направлении (см. лемму 1.4).

Теперь сформулируем лемму, которая будет играть основную роль в доказательстве теоремы 1.6:

Лемма 1.7. Пусть A1 B1 C1 составлен из середин сторон ABC. Если прямая l не пересекает A1 B1 C1 и не параллельна ни одной из его сторон, то l образует с некоторыми двумя сторонами ABC треугольник площади, большей чем S ABC.

Доказательство. Достаточно рассмотреть два существенно различных случая:

1) Прямая l не пересекает ABC и точка A наиболее удалена от l. Тогда, очевидно, l образует с прямыми AB и AC треугольник большей площади, чем S ABC.

2) Прямая l пересекает стороны AB и AC и луч BC в точках F, E и D соответственно. Тогда из условия леммы следует, что AE < EC. Легко видеть, что симметричный DEC относительно точки E треугольник содержит AF E, а следовательно, S AF E < S DEC. Значит, S BF D > S ABC.

Остальные случаи сводятся к этим переобозначением сторон треугольника.

1.3 Доказательство основной теоремы Введем обозначения. Пусть a S 1, а X — выпуклый компакт. Обозначим за l+ (a, X) и l (a, X) опорные прямые к X, перпендикулярные a такие, что если 1 a l( a, X), 2 a l+ (a, X), то 2 1 > 0, иначе говоря (a, x) > 0 для всех x l+ (a, X) l (a, X).

Можно заметить, что l+ (a, X) = l (a, X). Заметим также, что сумма или разность двух параллельных прямых — прямая, параллельная им обоим. Тогда можно обозначить m(a, X) = 1/2(l+ (a, X) + l (a, X)), то есть прямая m(a, X) равноудалена от l+ (a, X) и l (a, X)) и параллельна им обоим.

Доказательство теоремы 1.6. Сначала построим явную конструкцию трех транслятов K, а потом докажем, что они покрывают X.

Для любого вектора a S 1 рассмотрим прямую l(a) = l+ (a, X) l+ (a, K). Очевидно, что l(a) = l (a, X) l (a, K) = m(a, X K), так как w(X, K, a) = 1. Следовательно, l(a) = l(a). Очевидно, что l(a) — непрерывная функция от a S 1. Для попарно неколлинеарных векторов a1, a2, a3 через S(a1, a2, a3 ) обозначим площадь треугольника, образованного прямыми l(a1 ), l(a2 ), l(a3 ). Так как m(a1, X K) и m(a2, X K) пересекаются внутри X K, то, очевидно, S(a1, a2, a3 ) 1/2(diam(X K))2 sin, где — угол между прямыми l(a1 ) и l(a2 ). Следовательно S(a1, a2, a3 ) стремится к нулю, когда какие-то из направлений l(ai ) стремятся друг к другу, поэтому ее можно считать непрерывной функцией набора a1, a2 и a3, в котором могут быть и равные вектора. Поэтому S является непрерывной функцией на компакте S 1 S 1 S 1 и при некоторых a1, a2 и a3 достигает максимума.

Если максимум равен нулю, то это означает, что любые три, а, значит, и все l(a) пересекаются в одной точке t. Тогда X = K + t, так как опорные прямые к ним в любом направлении совпадают. В самом деле, t l+ (a, X)l+ (a, K), а, следовательно, 0 l+ (a, X) l+ (a, K) t, то есть 0 l+ (a, X) l+ (a, K + t) и l+ (a, K + t) = l+ (a, X).

Иначе, пусть t1, t2 и t3 — середины соответствующих сторон треугольника, образованного прямыми l(a1 ), l(a2 ) и l(a3 ). Рассмотрим трансляты Ki = K + ti. Будем считать, что (ai, ti tj ) > 0 (i = j), меняя в случае необходимости знаки у ai (см.

рис. 1.1).

Возьмем на границе K точки yi, принадлежащие l (ai, K). Докажем, что yi + ti tj K, то есть yi + ti Kj, i, j = 1, 2, 3, см. рис. 1.2. Достаточно доказать это, например, для y1 +t1 t2 и y1 +t1 t3, так как для других i доказательство аналогично.

Это будет следовать из того, что выпуклая оболочка точек касания l+ (a2, K) и l+ (a3, K) с K и точки y1 содержит y1, y1 + t1 t2 и y1 + t1 t3 и содержится в K, это же следует из того, что l+ (a2, K) или l+ (a3, K) не может пересекать K внутри полосы, образованной l (a1, K) и l (a1, K) + t1 t2 = l (a1, K) + t1 t3 (последняя прямая содержит точки y1 + t1 t2 и y1 + t1 t3 — см. рис. 1.2).

Без ограничения общности докажем последнее утверждение для одной прямой, то есть докажем, что точки касания l+ (a3, K) и K не лежат все внутри полосы, образованной l (a1, K) и l (a1, K) + t1 t2. Сдвинем все рассматриваемые прямые и точки на вектор t2. Тогда K перейдет в K2.

Следовательно нам нужно доказать, что точки касания l+ (a3, K2 ) и K2 не лежат все внутри полосы, образованной l (a1, K2 ) и l (a1, K2 )+t1 t2 = l (a1, K)+t1 = l (a1, X) (последнее равенство следует из того, что t1 l(a1 ) = l (a1, X) l (a1, K)).

Предположим противное и возьмем a S 1, немного отличающийся от a3 и в направлении вращения к a1. Тогда при достаточно малом отличии от a3 прямые l+ (a3, K2 ) и l+ (a, K2 ) будут пересекаться между l (a1, K2 ) и l (a1, X) (см. рис. 1.3).

Рассмотрим теперь прямые l+ (a3, X) и l+ (a, X). Прямая l+ (a3, X) получается из l+ (a3, K2 ) сдвигом на вектор t3 t2, так как t3 l+ (a3, X) l+ (a3, K), то есть t3 t l+ (a3, X) l+ (a3, k2 ).

По лемме 1.7 l(a) пересекает t1 t2 t3, а, в данном случае, обязана пересекать сторону t2 t3. Так как l(a) = l+ (a, X) l+ (a, K) = l+ (a, X) l+ (a, K2 ) + t2, то прямая l+ (a, X) получается из прямой l+ (a, K2 ) сдвигом на вектор, сонаправленный с t3 t и меньшей длины. Это означает, что точка пересечения l+ (a3, X) и l+ (a, X) лежит по другую сторону от прямой l (a1, X) по сравнению с X, как и точка пересечения прямых l+ (a3, K2 ) и l+ (a, K2 ) (см. рис. 1.3, эти сдвиги прямых l+ (a3, K2 ) и l+ (a, K2 ) только удаляют точку их пересечения от l (a1, X)). Из рисунка 1.3 также видно, что при таком расположении все три прямые l+ (a, X), l+ (a3, X) и l (a1, X) не могут быть опорными для X. Получили противоречие.

Итак, по доказанному, точки yi + ti j Kj. Предположим что X i Ki. Пусть C = conv i Ki. Докажем, что X C.

Предположим противное и возьмем прямую, отделяющую какие-то точки X от C.

Пусть a ее направляющий вектор, тогда прямые l+ (a, X) l+ (a, Ki ) лежат по одну сторону от начала координат, то есть все три точки ti лежат по одну сторону от l(a) — противоречие с леммой 1.7.

Так как yi + ti i Ki, то C отличается от i Ki на объединение множеств, лежащих внутри треугольников Ti, с вершинами yi + tj (j = 1, 2, 3, см. рис. 1.4).

Но Ti лежит с X по разные стороны от l (ai, X) и, поэтому, Ti (C \ i Ki ) не пересекает X. Поэтому C \ i Ki тоже не пересекает X.

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

О трансверсалях семейства транслятов... О трансверсалях семейства транслятов... Глава M -сильная выпуклость и порождающие множества 2.1 Введение В этой главе излагается ряд результатов, связанных с понятием сильной выпуклости и порождающего множества.

Рассматривается вопрос о характеризации выпуклых множеств, которые обладают некоторым свойством и фигурировали в работах [15, 13, 19, 18]. Следуя работам [15, 13], такие множества будут называться порождающими.

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

Во всех дальнейших теоремах E — рефлексивное банахово пространство, в частности это может быть конечномерное или гильбертово пространство.

Введем несколько определений, следуя работе [15].

Определение. Пусть M E — выпуклое множество. Множество A E называется M -сильно выпуклым, если оно является пересечением некоторого множества транслятов M, то есть A = tT (M + t), где T E.

Определение. Выпуклое множество M E называется порождающим, если для любого множества T E, для которого Y = tT (M + t) не пусто, найдется такое выпуклое множество Y, что Y + Y = M.

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

Такое понятие выпуклости естественно приводит к определению выпуклой оболочки (см. [15]):

Определение. Пусть множество S E таково, что M S =. Тогда M -выпуклой оболочкой множества S называется множество Мы будем обозначать его convM S.

Замечание. Иначе говоря, convM S — это пересечение всех транслятов M, содержащих S. Также имеет место формула Можно заметить, что M -выпуклая оболочка является наименьшим по включению M -сильно выпуклым множеством, содержащим S.

В [2] приведено еще одно определение аналога понятия выпуклости:

Определение. Пусть M E — выпуклое множество. Множество A E называется M -выпуклым, если для любых двух точек a, b A множество convM {a, b} определено и convM {a, b} A.

В этой главе будет доказаны следующие теоремы:

Теорема 2.1. Пусть дано множество M E, не обязательно порождающее. Тогда любое M -сильно выпуклое множество является M -выпуклым.

Теорема 2.2. Пусть множество M E является порождающим, а множество A — M -выпуклым. Если int b(A) =, то A M -сильно выпукло. Если M ограничено, то условие int b(A) = выполняется для любого M -выпуклого A.

Эти теоремы позволяют, при условии, что множество M порождающее и ограниченное, распространить определение M -сильно выпуклого множества на незамкнутые выпуклые множества, так как, очевидно, в определении M -выпуклого множества можно вообще избавиться от требования замкнутости.

Также в разделе 2.5 будет дан пример 2.2 M -выпуклого множества, которое не является M -сильно выпуклым. Множество M при этом ограничено, но не является порождающим.

Еще одним результатом этой главы является доказательство следующей теоремы:

Теорема 2.3. Пусть M — выпуклое множество, у которого int M = и int b(M ) =. Множество M является порождающим множеством тогда и только тогда, когда для любых t1, t2 E таких, что Y = (M + t1 ) (M + t2 ) = и int Y = найдется такое Y, что Y + Y = M.

Замечание. Множество b(X) — барьерный конус X — определено далее.

В конечномерном случае условие int b(M ) = не нужно, так как если это множество пусто, то найдется линейное подпространство L E такое, что b(M ) L. Тогда множества M и Y факторизуются по линейному подпространству L, что сводит теорему к случаю int b(M ) =.

Также в конечномерном случае не нужно условие int M =, так как перейдя в пространство a M всегда можно добиться того, что оно будет выполняться.

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

Таким образом, проверка может быть упрощена.

В работе [15] было показано, что в конечномерном случае (с размерностью n) теорема Каратеодори позволяет ограничить проверку определения порождающего множества множествами T с количеством элементов не более n. Таким образом, в данной работе получено значительное усиление этого результата.

О похожей задаче про сведение проверки того, что множество Y является слагаемым M (см. определение ниже), к проверке некоторого утверждения для конечных подмножеств M можно прочитать в [17].

Следующее утверждение было доказано в [18] в другой формулировке, мы сформулируем его с использованием определения порождающего множества:

Теорема 2.4. Любое выпуклое множество M R2 является порождающим.

Кроме того, в этой главе будет изучаться вопрос о характеризации таких банаховых пространств (см. обзор [22], а также [23, 24], где разбирается случай евклидовой нормы и ставятся вопросы о других нормах, в этих работах обсуждается случай конечномерных банаховых пространств), что любое множество диаметра 1 может быть вложено в множество постоянной ширины 1 (относительно этой нормы). Как оказалось, этот вопрос имеет прямое отношение к понятию порождающего множества.

Введем свойство нормы в банаховом пространстве:

Свойство 2.1. Любое множество Y диаметра 1 может быть вложено в множество постоянной ширины 1.

Имеет место следующее утверждение:

Теорема 2.5. Если единичный шар B1 нормы пространства E является порождающим множеством, то норма пространства E обладает свойством 2.1.

Это утверждение будет доказано в следующем усиленном варианте с помощью аналога теоремы 2.3:

Теорема 2.6. Пусть для единичного шара B1 нормы в пространстве E выполняется следующее свойство: множество Y = B1 (B1 + u) при любом u таком, что u 1, является слагаемым B1. Тогда норма · обладает свойством 2.1.

В конечномерном случае для строго выпуклых B1 теорема 2.6 является не только достаточным, но и необходимым условием:

Теорема 2.7. Пусть dim E <, норма в пространстве E обладает свойством 2. и ее единичный шар B1 является строго выпуклым. Тогда множество Y = B (B1 + u) при любом u таком, что u 1, является слагаемым B1.

В данной главе также приводится доказательство аналога теоремы Каратеодори для M -сильной выпуклости при условии, что M — порождающее множество.

Для случая строго выпуклого M это утверждение было доказано в диссертации Балашова [14]. Для случая не строго выпуклого M в [14] доказан аналог теоремы Каратеодори с заменой константы n + 1 на n2 + 1.

Теорема 2.8 (Аналог теоремы Каратеодори). Пусть M — порождающее выпуклое множество. Для множеств S Rn таких, что M S =, имеет место формула Если S конечно, то имеет место В разделе 2.6 будет также приведен пример 2.3, показывающий, что если не накладывать условия, что M — порождающее, то аналог теоремы Каратеодори не будет верен ни с какой константой N.

2.2 Вспомогательные факты.

Сформулируем некоторые вспомогательные факты и определения, необходимые при доказательстве теорем этой главы.

Определение. Выпуклое множество Y называется слагаемым множества X, если найдется такое выпуклое Y, что Y + Y = X.

Если Y + Y = X, то X = y Y (Y + y ), то есть X является объединением транслятов Y. Верно и обратное: если множество X выпукло и X = zZ (Y + z), то взяв Y = conv Z, получим X = Y + Y. Следовательно, чтобы установить, что Y — слагаемое X, достаточно проверить, покрывают ли те трансляты Y, которые содержатся в X, все множество X.

Определение. Опорной функцией множества X называется функция вектора p E, определяемая как Определение. Пусть X — выпуклое множество и x bd X. Конусом нормалей Nx (X) E в точке x называется Лемма 2.9. Если выпуклое множество Y представлено в виде пересечения некоторого конечного семейства выпуклых множеств Y = iI Xi и y bd Y и int Y =, Доказательство. Пусть p Ny (Y ), это означает, что Опорная функция Y выражается через опорные функции Xi следующим образом:

Докажем включение Значит, все выписанные неравенства были равенствами, следовательно p, y = s(p, Y ), то есть p Ny (Y ).

Теперь докажем включение При этом без ограничения общности можно считать, что 0 int Y, следовательно 0 int Xi для всех i I. Отсюда следует, что существует > 0 такое, что Рассмотрим теперь надграфики функций s(p, Xi ) в пространстве E R, обозначим их Si. Надграфик функции s(p, Y ) обозначим S.

Тогда S = conv{Si }iI. Покажем, что на самом деле имеет место S = conv{Si }iI.

Для этого достаточно показать, что множество S0 = conv{Si }iI замкнуто.

Пусть Аналогично определяется S0. Для любой пары (p, s) Sih имеем это значит, что |p | h, кроме того 0 s h. Это значит, что множества Sih ограничены.

Докажем, что S0 = conv{Sih }iI.

Пусть (p, s) S0. Это значит, что для некоторых наборов (pi, si ) Si и 0 < wi Если какое-то si 0, то соответствующее pi = 0, так как si |pi |, при этом обязательно si = 0. Исключим из наборов пары (pi, si ), равные нулю. При этом сумма iI wi = w может стать меньше 1. Если w стала равна нулю, то (p, s) = (0, 0) conv{Sih }iI и доказывать нечего, иначе умножим все wi на w, а все пары (pi, si ) умножим на w. После этого можно считать, что si > 0 для всех i I.

Тогда можно записать Заметим, что s h и значит, (p, s) conv{Sih }iI.

Мы доказали, что S0 = conv{Sih }iI. А так как множества Sih ограничены и выh пуклы, а пространство E рефлексивно, то по теореме Банаха-Алаоглу они компактны в слабой топологии. Значит, их выпуклая оболочка тоже компактна. Следовательно, S0 замкнуто для любого h, значит S0 замкнуто.

Теперь мы доказали, что S = conv{Si }iI. Для точки (p, s(p, Y )) это означает, что найдутся такие наборы (pi, si ) Si и 0 wi 1 (i I I, iI wi = 1), что Так как s(p, Y ) = Это значит, что все выписанные неравенства были равенствами, а это значит, что для любого i I s(pi, Xi ) = pi, y, то есть pi Ny (Xi ), следовательно, wi pi Ny (Xi ) и Что и требовалось доказать.

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

Определение. Барьерным конусом множества X называется Лемма 2.10. Пусть X — выпуклое множество и p int b(X). Тогда множество ограничено.

Доказательство. По условию, найдется некоторое открытое множество U E такое, что p U и U b(X). Так как при этом очевидно p b(Xp,a ), то U p b(Xp,a ) и при этом U p — окрестность нуля. Это означает, что p, x ограничено на Xpa при любом p. По известной теореме (теорема 3.18 из [20]) отсюда следует ограниченность Xp,a.

Приведем еще три известных леммы, которые также можно найти в [15].

Лемма 2.11. Если int b(X) =, то для любой точки y X найдется p int b(X) такое, что p, y > s(p, X).

Лемма 2.12. Если X = A + B, то s(p, X) = s(p, A) + s(p, B).

Лемма 2.13. Если p int b(X), то найдется точка x X такая, что p, x = s(p, X).

Cформулируем еще несколько определений и лемм.

Определение. Пусть X и Y — строго выпуклые множества, для которых int b(X) =, int X =. Тогда Y называется локально вложимым в X, если выполняется следующее: для любой точки x bd X найдется такая точка y bd Y и такая окрестность U точки y, что Поясним последнюю формулу: если сделать трансляцию, переводящую точку y в точку x, то образ множества Y U окажется в X. Точка y определена однозначно точкой x, так как можно взять внешнюю нормаль n к X в точке x, и заметить, что в точке y внешняя нормаль должна быть та же, а у строго выпуклых множеств точка на границе однозначно определяется внешней нормалью.

Определение. Пусть X — строго выпуклое множество. Тогда для любого p int b(X), p = 0 можно определить точку x = DX (p) X как единственную точку X, для которой По лемме 2.13 такая точка найдется, а так как X строго выпукло, то эта точка единственная. На самом деле DX (p) — это дифференциал функции s(p, X), но мы это замечание не будем использовать.

Лемма 2.14. Пусть X и Y — строго выпуклые тела в E (dim E 2), Y локально вложимо в X и отображение DY (p) непрерывно на int b(Y ) \ {0}. Тогда Y — слагаемое X.

Для ее доказательства понадобится следующая лемма:

Лемма 2.15. Пусть f — непрерывная функция на открытом выпуклом подмножестве D линейного топологического пространства L и для любых l0 D и l L найдется такое число R и такое > 0, что Тогда f выпукла.

Доказательство. Ясно, что достаточно доказать выпуклость f (l) на каждой прямой.

Далее считаем f (x) функцией на прямой.

Тогда условие леммы принимает вид:

Покажем, что для любых x1, x2 D и t [0, 1] Вычтем из f линейную функцию так, чтобы стало При этом функция f все еще будет удовлетворять условию. Тогда остается доказать, что для всех x (x1, x2 ) f (x) 0.

Предположим противное. Функция f непрерывна. Тогда f в каких-то точках отрезка [x1, x2 ] достигает своего максимума m > 0. Множество таких x, что f (x) = m замкнуто, поэтому из него можно взять минимальный элемент x0. Тогда Пусть для x0 найдутся такие и > 0, что Подставим любое < 0, получим, что > 0. Подставим любое > 0, получим, что 0. Получено противоречие.

Доказательство леммы 2.14. Для любого p int b(X), подставив x = DX (p) в определение локальной вложимости, получим, что y = DY (p), так как на точке y функционал p, · принимает свое максимальное на Y значение. Следовательно p b(Y ).

Отсюда следует, что int b(X) int b(Y ).

Для доказательства того, что найдется Y такое, что Y + Y = X достаточно доказать выпуклость функции f (p) = s(p, X) s(p, Y ) на множестве int b(X).

Пусть есть какое-то p0 int b(X). Возьмем x = DX (p0 ) и найдем для него точку y Y и окрестность U точки y, для которых Ясно, что при этом y = DY (p0 ), так как именно на точке y p0, · принимает максимальное значение на Y. Из включения множеств также следует, что для всех p E Так как DY (p) непрерывно, то для некоторой окрестности V p0 для всех p V выполняется DY (p) U. Тогда имеем:

Так как кроме того s(p0, X) = p0, x и s(p0, Y ) = p0, y, то можно записать Ясно, что f удовлетворяет всем условиям леммы 2.15 во всех точках p0 int b(X), кроме, возможно, точки 0. Однако можно применить лемму 2.15 к функции f на любом множестве int b(X) Hv, где для любого v E \ {0} На каждом таком множестве f будет выпукла. Чтобы доказать, что f (p) выпукла на всем int b(X) достаточно доказать, что если 0 = tp1 + (1 t)p2, то Найдем такой v E \ {0}, что p1, v = p2, v = 0, это можно сделать, так как dim E > 2. Найдем какой-то p E такой, что p, v > 0. Тогда для любого s > sp, p1 + sp, p2 + sp Hv, а так как int b(X) — открытое множество, то для достаточно маленьких s sp, p1 + sp, p2 + sp int b(X). Для таких s по доказанной выпуклости f на int b(X) Hv можно записать Так как f непрерывна, то, переходя к пределу s 0, получаем Значит f (p) = s(p, X) s(p, Y ) выпукла на int b(X) и доказательство завершено.

Приведем еще две леммы (см. [21]):

Лемма 2.16. Если X — строго выпуклое множество в конечномерном пространстве E, то отображение DX (p) непрерывно на int b(X) B1 (0).

Определение. Пусть X — гладкое выпуклое множество. Тогда для любой точки x bd X можно определить p = DX (x) b(X) B1 (0) как единственный элемент b(X) B1 (0), для которого Лемма 2.17. Если X — гладкое выпуклое множество в конечномерном пространстве E, то отображение DX (x) непрерывно на bd X.

Приведем также полезную лемму из [15]:

Лемма 2.18. Пусть X E — выпуклое множество, int X = и int b(X) =. Пусть для любого множества T такого, что для Y = tT (X + t) int Y = найдется такое Y, что Y + Y = X. Тогда X является порождающим множеством.

2.3 Доказательство теоремы 2. Докажем, что M — порождающее множество по определению. Пусть Y = M (T ) = tT M + t.

Также, как в работе [15], заметим, что int b(M ) = int b(Y ).

доказать, что на самом деле Y + Y = M.

Обозначим Z = Y +Y. Множество Y очевидно замкнуто, замкнутость множества Z следует из леммы 1.1 работы [15]. Так как int b(M ) int b(Z) int b(M ), то на самом деле int b(M ) = int b(Z) = int b(M ).

Далее доказательство разбивается на следующие случаи:

Доказательство для конечных T при int Y =. Проведем доказательство индукцией по |T |. Случай |T | = 2 верен по условию.

Пусть Z = M. Тогда по лемме 2.11 найдется p int b(M ) = int b(Z) такое, что s(p, M ) > s(p, Z). Также по лемме 2.13 можно найти такую точку z Z, что p, z = s(p, Z). Так как Z = Y + Y, то найдется y Y такое, что z Y + y. Так как то по лемме 2. то есть Рассмотрим два случая:

1. Если только один из pt не равен нулю (при t = ), то заметим, что Y + y По выбору p s(p, Z) < s(p, M ), значит p, + p, y < 0.

приходим к противоречию.

2. Если как минимум два вектора p и p не равны нулю, то можно считать, что их сумма p2 тоже не равна нулю. Пусть T = T \ {, }, Положим Тогда Y + y = Y2 Y2+. По условию теоремы есть множество Y2 такое, что Y2 + Y2 = M. По лемме 2.12 s(p2, M ) = s(p2, Y2 ) + s(p2, Y2 ), то есть для любого положительного можно найти такой t2 Y2, что и Y2 + t2 M. При этом p2 Nz (Y2 ), следовательно s(p2, Y2 ) = p2, z.

Ясно, что либо p p2 = 0, либо p p2 Nz (Y2+ ). В первом случае:

Во втором случае:

то есть то же самое. Значит, мы можем выбрать таким, что Заметим, что Y3 — пересечение |T | 1 транслятов M, int Y3 =, значит по предположению индукции Y3 является слагаемым M. Тогда, по лемме 2.12, для Так как s(p, M ) > s(p, Y3 ), то при достаточно малом будем иметь:

и тогда мы получим что приводит к противоречию.

Доказательство для произвольных T и int Y =. Предположим Z = M. Как в предыдущем случае, возьмем некоторый p int b(M ) такой, что s(p, M ) > s(p, Z) и такую точку z Y + y Z, что p, z = s(p, Z).

Заметим следующее: если удастся найти такое пересечение конечного числа транслятов YF = tF (M + t + y ) (F T, |F | < ), что s(p, YF ) < s(p, M ), то мы сразу придем к противоречию. Действительно, при этом int YF = и по доказанному выше найдется y YF такой, что s(p, M ) s(p, YF ) + p, y + и при достаточно малом получаем, что p, y > 0. При этом Y + y + y YF + y M, следовательно что приводит к противоречию.

Итак, предположим противное — для всех конечных F T оказалось s(p, YF ) s(p, M ). Положим таким, что s(p, Z) < s(p, M ) и обозначим Тогда все YF пересекают H, но Y + y не пересекает H, так как на Y + y функция p, · меньше, чем s(p, M ).

По лемме 2.10 все множества (M + t + y ) H ограничены. Кроме того их пересечение (Y + y ) H пусто.

По теореме Банаха-Алаоглу в рефлексивном банаховом пространстве все ограниченные замкнутые (в слабой топологии) множества компактны в слабой топологии.

Множества (M + t + y ) H замкнуты и ограничены в слабой топологии, так как они выпуклы, замкнуты и ограничены в обычной топологии. Пересечение семейства компактных множеств пусто тогда, когда пусто пересечение некоторого конечного подсемейства F. Это означает, что YF H =, что приводит к противоречию.

Доказательство при int Y =. Так как для любого Y = tT (M + t), такого, что int Y = найдется Y такое, что Y + Y = M, то по лемме 2.18 множество M — порождающее.

2.4 Применение теоремы 2. Покажем, как с помощью теоремы 2.3 можно доказать некоторые известные утверждения (см. [15]).

Теорема 2.19. Шары в гильбертовых пространствах являются порождающими множествами.

Доказательство. Пусть X — единичный шар в некотором гильбертовом пространстве. По теореме 2.3 достаточно проверить определение порождающего множества для множеств Y, являющихся пересечениями двух шаров. По лемме 2.18 можно считать, что int Y =.

Возьмем произвольную точку x bd X и явно найдем транслят Y, содержащий x и содержащийся в X. Пусть единичный вектор внешней нормали в x равен n и найдем точку y Y, у которой такой же вектор нормали.

Теперь сдвинем Y так, чтобы точка y совпала с x. При этом по лемме 2.9, которая утверждает, что вектор n представляется в виде n = n1 + n2.

Если при этом один из векторов n1 и n2 равен нулю, то получим, что n = n или n = n2. Это означает, что X совпадает с соответствующим X + ti. В этом случае Y лежит в X.

Рассмотрим случай, когда и не равны нулю. Заметим, что из выпуклости единичного шара следует, что + 1.

Тогда множество X задается неравенством так как это единичный шар, нормаль которого известна. Аналогично, множество точек x Y задано системой Теперь, если какая-то точка x находится в Y, то сложив оба неравенства системы, определяющей Y, предварительно умножив их на и найдем, что Так как (x x, x x) ( + )(x x, x x), то выполняется то есть x X, это означает, что Y X.

порождающее.

Теорема 2.20. Параболоиды являются порождающими множествами.

Доказательство. Можно считать, что параболоид X — это множество точек (y, x) в пространстве R1 H, где H — некоторое гильбертово пространство, задаваемое неравенством Для любого вектора v будем обозначать vy и vx проекции вектора на R1 и H соответственно.

По лемме 2.18 можно считать, что int Y =.

Совершенно аналогично предыдущей теореме возьмем соответствующие точки в X и Y с одинаковой внешней нормалью n и сдвинем Y так, чтобы они совпали. Также по лемме 2.9 можно заключить, что либо n = n1 или n = n2, либо n = n1 + n2. Здесь векторы нормали лучше считать нормированными условием ny = n1y = n2y = 1, поэтому + = 1. В первом случае, так как множество точек (y, x ) X задается неравенством и так как неравенство транслята параболоида X определяется его нормалью, то X +t или X + t2 совпадает с X. В этом случае Y X.

Во втором случае выпишем неравенства, определяющие точки множества Y с координатами (y, x ):

Теперь сложив эти неравенства с коэффициентами и, получим неравенство, определяющее X, что доказывает, что Y X.

Аналогично предыдущей теореме заключаем, что Y — слагаемое X и X — порождающее.

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

Пример 2.1.

Взяв в качестве точки x, определяемой также, как в предыдущих доказательствах точку (1, 0, 0)t, и перенеся параллельно Y так, чтобы его соответствующая точка y перешла в x, мы получим, что сечение Y плоскостью x3 = 0 не будет содержаться в X, так как это сечение будет гиперболой с меньшей кривизной, чем соответствующее сечение X.

Также с помощью теоремы 2.3 можно было бы доказать и теорему 2.4, но доказательство нет смысла приводить, так как известные доказательства этого факта по сути были такие же.

2.5 Эквивалентность M -сильной выпуклости и M -выпуклости Доказательство теоремы 2.1. Если A — M -сильно выпуклое множество, то для любых a, b A имеем:

Это значит, что A — M -выпукло.

Доказательство теоремы 2.2. Докажем сначала включение int b(A) int b(M ). Возьмем некоторый p int b(A). Возьмем некоторые a, b A. Множество C = convM {a, b} содержится в A, значит, p int b(C). А так как C — пересечение транслятов M, то int b(C) = int b(M ).

Теперь докажем, что int b(M ) b(A). Предположим противное: найдется p int b(M ) такой, что p b(A). Кроме того, по уже доказанному существует p int b(M ) int b(A). По лемме 2.13 найдутся такие x0 M и a0 A, что Так как p b(A), то найдется такая последовательность точек bn A, что p, bn + при n. Обозначим Cn = convM {a0, bn }.

Теперь, так как M порождающее, то для каждого Cn найдется Cn такое, что Cn + Cn = M. Зафиксируем некоторое > 0. По лемме 2.12, примененной к p0, найдется такой вектор c Cn, что s(p0, Cn ) + p0, c > s(p0, M ). При этом Cn + c M, следовательно a0 + c M, а так как p0, a0 = s(p0, A) s(p0, Cn ) и s(p0, M ) = p0, x0 = mM, то Если определить По лемме 2.10 множество Mp0,mM ограничено, значит последовательность p, a0 + c ограничена. Значит, последовательность p, c тоже ограничена.

Так как Cn + c M, bn + c M. Следовательно, последовательность p, bn + c ограничена сверху, что влечет ограниченность сверху p, bn. Однако p, bn +, что приводит к противоречию.

Так как int b(A) int b(M ) и int b(M ) b(A), то int b(A) = int b(M ).

Так как M — порождающее множество, то A M -сильно выпукло тогда и только тогда, когда существует A такое, что A + A = M. Это, в свою очередь, равносильно тому, что разность опорных функций s(p, M ) s(p, A) выпукла на int b(M ) = int b(A).

Докажем выпуклость разности s(p, M ) s(p, A). Возьмем p1, p2 int b(A). По лемме 2.13 найдутся a1, a2 A такие, что Обозначим B = convM {a1, a2 }. Так как A M -выпукло, то B A. Следовательно но a1 B, значит s(p1, B) = s(p1, A). Аналогично s(p2, B) = s(p2, A).

Так как B A, то для любого p int b(A) Так как B M -выпукло, то для любого t [0, 1] Следовательно, для любого t [0, 1] То есть s(p, M ) s(p, A) выпукла.

Осталось доказать, что если M ограничено, то int b(A) =. Докажем более сильное утверждение: A ограничено. Зафиксируем точку a0 A. Для любой b A по определению M -выпуклого множества convM {a0, b} A. Это означает в частности, что найдется такое t E, что Значит, a0 t M и где M M — сумма Минковского множеств M и M. Отсюда следует, что A a0 + M M. При этом ограниченность M влечет ограниченность M M, значит A тоже ограничено.

На этом теорема полностью доказана.

Приведем пример M -выпуклого множества, которое не является M -сильно выпуклым. При этом множество M будет ограниченным, но не порождающим.

Пример 2.2. Пусть E = R3, S0 — правильный тетраэдр. Рассмотрим четыре плоскости, каждая из которых параллельна одной из граней S0 и делит соответствующую высоту S0 пополам. Эти плоскости разбивают S0 на октаэдр M и четыре меньших тетраэдра, один из которых обозначим A.

Ясно, что A не может быть M -сильно выпуклым, так как никакая трансляция M не покрывает A. Однако A является M -выпуклым. Докажем это.

Возьмем любые точки a, b A. Чтобы доказать, что convM {a, b} A, достаточно для любой грани F симплекса A найти такой транслят M + t, что M + t a, b и M + t лежит по ту же сторону от F, что и A. Рассмотрим гомотетичный A симплекс A минимального размера, содержащий a и b. Если обозначить грань A, параллельную F за ABC, а оставшуюся вершину за S, то с точностью до симметрий остается разобрать три случая:

В каждом из этих случаев явно строится транслят M +t, содержащий a и b и лежащий по ту же сторону от ABC, что и A.

2.6 Доказательство аналога теоремы Каратеодори 2.6.1 Сведение доказательства к лемме 2. Аналог теоремы Каратеодори будет выведен из следующего утверждения:

Лемма 2.21. Пусть множество M — порождающее. Пусть для некоторого конечного множества S Rn имеет место:

Тогда для некоторого U S такого, что |U | n + 1, имеет место Приведем пример, показывающий невозможность доказать аналог теоремы Каратеодори с некоторой константой N, если M не является порождающим:

Пример 2.3. Пусть M — правильная пирамида в R3, в основании которой лежит правильный N + 1-угольник. Пусть ее вершина — точка 0. Пусть точки m1,..., mN + — центры ее боковых граней. Положим Тогда M S — подобная M пирамида с вершиной 0 и меньшего размера, чем M.

Очевидно M S M.

При этом если взять U S и рассмотреть M U, то это будет пирамида c вершиной в 0, строго включающая M S (у нее меньше боковых граней и каждая боковая грань M U содержит некоторую боковую грань M S). Поэтому включение M U M не может выполняться.

Это значит, что, с одной стороны С другой стороны Для таких M и S аналог теоремы Каратеодори с константой N не может быть верен.

Докажем аналог теоремы Каратеодори предполагая, что лемма 2.21 верна.

Доказательство аналога теоремы Каратеодори. Докажем для конечных S равенство Ясно, что всегда имеет место включение Предположим, что равенство не выполняется, то есть существует точка x convM S, не принадлежащая правой части. Без ограничения общности будем считать, что x = (для этого можно совершить трансляцию).

Тогда условие 0 M (M S) означает, что иначе Тогда по лемме 2.21 существует такое множество U S, что |U | n + 1 и M U M. Проводя вышеуказанные выкладки в обратном порядке, получим, что 0 convM U. Противоречие.

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

Теорема 2.22 (Топологическая теорема Хелли). Если конечное семейство F подмножеств Rn обладает следующими свойствами:

1. Для любого G F множество либо пусто, либо гомологически тривиально, 2. Для любого H F такого, что |H| n + 1, множество то пересечение не пусто.

Сформулируем теперь основную лемму:

Лемма 2.23. Пусть A и B — выпуклые множества в Rn. Тогда множество A \ cl(A + B) либо пусто, либо гомологически тривиально.

Примем эту лемму на веру и докажем лемму 2.21:

Доказательство леммы 2.21. Определим семейство множеств следующим образом:

По условию теоремы имеем Покажем, что для любого V S множество либо пусто, либо гомологически тривиально. Обозначим A = M V. По условию, A является M -сильно выпуклым, значит M = A + B для некоторого выпуклого B, кроме того M замкнуто, то есть M = cl M. Значит лемме 2.23 A \ M либо пусто, либо гомологически тривиально.

Семейство {M (s)}sS имеет пустое пересечение, тогда по топологической теореме Хелли получаем, что некоторое семейство {M (s)}sU (|U | n+1) также имеет пустое пересечение. Тогда то есть M 2.6.2 Доказательство леммы 2. Сначала напомним определения некоторых топологических понятий, которые мы будем использовать в доказательстве. Также напомним несколько утверждений из топологии, которые мы будем использовать.

Определение. Два непрерывных отображения где X и Y — некоторые топологические пространства, называются гомотопными, если найдется непрерывное отображение такое, что Определение. Непрерывное отображение f : X Y, где X и Y — некоторые топологические пространства, называется гомотопической эквивалентностью, если существует непрерывное отображение g : Y X такое, что отображения f g и g f гомотопны тождественным отображениям пространств Y и X соответственно.

Лемма 2.24. Любая гомотопическая эквивалентность является гомологической эквивалентностью.

Определение. Топологическое пространство X называется гомотопически тривиальным, если оно гомотопически эквивалентно точке.

Для краткости, если речь идет о подмножестве X некоторого топологического пространства T, которое является гомотопически тривиальным топологическим пространством в индуцированной топологии, будем просто говорить, что X — гомотопически тривиальное множество.

Лемма 2.25. Если семейство F подмножеств топологического пространства X таково, что все Y F гомологически тривиальны и любое компактное подмножество K X принадлежит некоторому Y F, то X тоже гомологически тривиально.

Из этой леммы следует еще одна лемма:

Лемма 2.26. Если топологическое пространство X представлено в виде объединения упорядоченной по включению последовательности открытых подмножеств Ui X (i N), каждое из которых гомологически тривиально, то X тоже гомологически тривиально.

Доказательство лемм 2.24, 2.25 и 2.26 можно найти, например, в [26].

Сформулируем еще несколько лемм.

Лемма 2.27. Пусть выпуклые множества A, C Rn таковы, что функция s(p, A) определена на rint b(C) и функция s(p, C) s(p, A) выпукла на rint b(C). Тогда существует выпуклое множество B такое, что C = cl(A + B).

Доказательство. Сначала рассмотрим случай a b(C) = Rn. В этом случае int b(C) = rint b(C) =.

Функции s(p, C) и s(p, A) определены и выпуклы на int b(C), следовательно они непрерывны на int b(C). Так как их разность выпукла и непрерывна на int b(C), то можно определить непустое выпуклое множество для которого будет выполняться s(p, C) = s(p, A) + s(p, B) для любого p int b(C) и int b(B) = int b(C). Кроме того, по лемме 2.11 для множества C можно записать:

Для множества C = cl(A + B) по лемме 2.13 выполняется s(p, C ) = s(p, A) + s(p, B) = s(p, C) для любого p int b(C). Отсюда следует, что int b(C ) int b(C). Кроме того, так как C = cl(A + B), то b(C ) b(B) cl b(C). Значит int b(C ) = int b(C), следовательно C = C. В этом случае лемма доказана.

Рассмотрим случай a b(C) = Rn. Пусть L — линейное подпространство в Rn, перпендикулярное a b(C). Возьмем проекцию вдоль L на некоторое пространство L. Тогда будем иметь:

и у множества (C) L будет int b(C ) =. По доказанному выше, найдется такое B, что (C) = cl(cl (A) + B ). Заметим, что cl(A + 1 (B )) = 1 (cl(cl (A) + B )).

Отсюда сразу получаем, что C = cl(A + 1 (B )).

Лемма 2.28. Пусть A — выпуклый компакт в Rn. Тогда существует такая последовательность Ai, что для всех i Ai Ai+1, множество Ai строго выпукло и гладко, A = i Ai, и Ai A в метрике Хаусдорфа.

Доказательство. Пусть diam A = D. Положим convR S = convBR (0) S для S Rn.

Теперь определим Множества Ai гладкие, так как являются суммами Минковского, в которых одно из слагаемых гладко, кроме того, они строго выпуклы, так как convR X BR (0)-сильно выпукла, а значит и строго выпукла.

Кроме того, а так как последовательность A + B2i (0) монотонна по включению и сходится к A, то Ai тоже монотонна по включению и сходится к A.

Лемма 2.29. Пусть A — выпуклый компакт в Rn и int A =. Тогда существует такая последовательность Ai, что для всех i Ai Ai+1, множество Ai строго выпукло и гладко, A = i Ai, и Ai A в метрике Хаусдорфа.

Доказательство. Пусть diam A = D. Тогда определим Множества Ai гладкие, так как являются суммами Минковского, в которых одно из слагаемых гладко, кроме того, они строго выпуклы, так как convR X BR (0)-сильно выпукла, а значит и строго выпукла.

Кроме того, а так как последовательность A B4i (0) монотонна по включению и сходится к A, то Ai тоже монотонна по включению и сходится к A.

Теперь перейдем к леммам, из которых мы выведем основную лемму.

Лемма 2.30. Достаточно доказать лемму 2.23 для случая Доказательство. Если int A =, то можно просто перейти в несущее аффинное подпространство L для A и обозначить Можно также считать, что L содержит начало координат, иначе можно просто сменить координаты для множества A. Покажем, что в пространстве L найдется некоторое B такое, что C = cl(A + B ). По лемме 2.27 для этого достаточно показать, что разность опорных функций C и A определена и выпукла на rint b(C ), что мы и сделаем.

Пусть C = cl(A + B), L — пространство линейных функционалов на L, L — пространство линейных функционалов на Rn, обращающихся в нуль на L. Тогда, так как C rint L = C L =, для опорных функций можно записать (см. [21]):

Отсюда следует, что если p b(C ) L, то для любого > 0 найдется такой p L, что s(p + p, C) s(p, C ) + <. Тогда, так как C = cl(A + B), то s(p, A) = s(p + p, A) <, то есть s(p, A) определена на b(C ).

Далее, При этом s(p, A) = s(p+p, A), а значит, в правой части под знаком inf стоит выпуклая функция аргумента p + p, равная s(p + p, B)).

Мы должны доказать, что функция выпукла на rint b(C ).

Докажем это по определению: пусть p1, p2 rint b(C ) и t [0, 1]. Тогда для любого > 0 можно найти p, p L так, что Функция f выпукла, следовательно и значит, В силу того, что > 0 произвольно, выполняется то есть f выпукла и C = cl(A + B ).

Мы получили, что A и A + B лежат в L, и int A в пространстве L непусто. Так что лемму 2.23 достаточно доказать для A и Итак, далее предполагаем, что int A =.

Сформулируем одно полезное утверждение:

Лемма 2.31. Для выпуклых множеств A и B множества гомотопически эквивалентны при условии int A =.

Доказательство. Возьмем точку p в множестве если такой нет, то (int A) \ cl(A + B) — это int A, а A \ cl(A + B) отличается от него добавлением некоторых точек bd A и, очевидно, оба они гомотопически тривиальны.

Если же точка p нашлась, то можно заметить следующее: для любого луча r, выходящего из p, пересечение r A \ cl(A + B) — это некоторый полуинтервал (x y], а r (int A) \ cl(A + B) — это интервал (x y) (при этом возможно y = на луче r). Точка x непрерывно зависит от луча r на множестве тех лучей, для которых r A \ cl(A + B) =, точка y непрерывно зависят от луча r, если считать луч пополненным бесконечно удаленной точкой. Введем на луче r координату l(z) так, что точка p является нулем и l(z) 0 для z r. Тогда определим отображение r отрезка (x y] в точку на r с координатами и отображение r, являющееся ограничением r на (x y). Будучи примененными для всех лучей r, таких, что r A \ cl(A + B) = (равносильно r (int A) \ cl(A + B) = ) отображения r и r задают непрерывные отображения которые дают гомотопическую эквивалентность между A\cl(A+B) и (int A)\cl(A+B).

Действительно, отображение ((z)) гомотопически эквивалентно тождественному с помощью гомотопии и аналогично для ((z)).

Следующая лемма позволит нам рассматривать только случай ограниченных множеств A и B:

Лемма 2.32. Лемма 2.23 следует из утверждения леммы 2.23 для ограниченных A Перед ее доказательством введем некоторое обозначение: для линейной функции (x) обозначим Доказательство. Выведем лемму 2.23 из ее случая для ограниченных A и B.

По леммам 2.31 и 2.30 достаточно доказать гомологическую тривиальность множества (int A) \ cl(A + B), где int A =.

Вначале предположим, что множество cl(A+B) не содержит ни одной прямой. Это означает, что найдется такая линейная функция на Rn, что множества Ht cl(A+B) ограниченны при любом t. Тогда множества Ht A и Ha B тоже ограниченны при любом t.

После прибавления к функции некоторой константы можно считать, что l(a) для всех a A и l(b) 0 для всех b B.

Множество (int A) \ cl(A + B) является объединением возрастающей по включению последовательности открытых множеств поэтому по лемме 2.26 достаточно доказать гомологическую тривиальность каждого из (int An ) \ cl(A + B).

Так как l(a) 0 для всех a A и l(b) 0 для всех b B, то нетрудно заметить, что и, значит, Но по лемме 2.31 и лемме 2.23 для ограниченных множеств, множество в правой части гомологически тривиально, либо пусто.

Значит, остается рассмотреть случай, когда cl(A + B) содержит некоторую прямую l. Пусть — проекция вдоль прямой l, а (x) — некоторая линейная функция, не постоянная на прямой l.

В этом случае множества ((int A) \ cl(A + B)) и (int A) \ cl(A + B) гомотопически эквивалентны с помощью отображения. Действительно, для точки x ((int A) \ cl(A + B)) При этом множество 1 (x) int A является некоторым открытым интервалом (x1 x2 ) (возможно, что точки некоторые из точек x1, x2 лежат в бесконечности на прямой 1 (x)). Для x (int A) положим при этом может быть a1 (x) = и a2 (x) = +.

Если для каждого x (int A) взять точку (x) 1 (x) так, что (считая, что arctan(+) = и arctan() = ) то будет непрерывным. Отображения и зададут гомотопическую эквивалентность множеств ((int A) \ cl(A + B)) и (int A) \ cl(A + B).

Если заметить, что и предположить, что для множеств (A) и (B) все уже доказано, то доказательство можно считать законченным с помощью индукции по размерности.

Теперь сведем лемму 2.23 к ее очень удобному частному случаю:

Лемма 2.33. Если утверждение леммы 2.23 верно для строго выпуклых, гладких и ограниченных A и B, то лемма 2.23 верна.

С ограниченностью мы уже разобрались, так что дальше предполагается, что A и B ограниченны. Это также означает, что Доказательство. Сначала докажем, что из утверждения леммы 2.23 для гладких и строго выпуклых B следует лемма 2.23.

Пусть лемма 2.23 верна для гладких и строго выпуклых B, а нам нужно доказать ее для множества B, которое не является гладким, либо строго выпуклым. Тогда по лемме 2.28 найдется последовательность гладких и строго выпуклых множеств {Bi }i1 такая, что Bi+1 Bi для всех i 1 и B = i1 Bi. При замене B на Bi лемма 2.23 верна, значит множества A \ (A + Bi ) либо пусты, либо гомологически тривиальны. Так как A \ (A + B) является объединением упорядоченного по включению семейства своих относительно открытых подмножеств A \ (A + Bi ), каждое из которых гомологически тривиально, либо пусто, то само это множество гомологически тривиально, либо пусто.

Предположим теперь, что лемма 2.23 верна для гладких и строго выпуклых A и B и покажем, что она верна для случая, когда A либо не гладко, либо не строго выпукло. При этом B уже можно считать гладким и строго выпуклым.

По леммам 2.31 и 2.30 достаточно показать, что множество (int A) \ (A + B) гомологически тривиально или пусто.

Рассмотрим последовательность гладких и строго выпуклых множеств {Ai }i1 таких, что Ai+1 Ai для всех i 1, A = i1 Ai и A является пределом последовательности {Ai }i1 в хаусдорфовой метрике для выпуклых компактов. Такая последовательность найдется по лемме 2.29, так как int A =, что подразумевается в силу леммы 2.30.

Сходимость к A в метрике Хаусдорфа означает, что найдется последовательность i 0 такая, что A Ai + B(i ), где B() — шар с центром в нуле и радиусом.

Обозначим теперь Bi = B + B(i ). Тогда множества Ai и Bi гладки и строго выпуклы и:

причем Это значит, что множество (int A) \ (A + B) является объединением последовательности множеств (int Ai ) \ (Ai + Bi ), каждое из которых является гомологически тривиальным, либо пустым. Каждое компактное подмножество K (int A) \ (A + B) содержится в (int Ai ) \ (Ai + Bi ) при некотором i; достаточно взять i таким, что По лемме 2.25 (int A) \ (A + B) гомотопически тривиально, либо пусто.

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

Заметим, что если множество B содержит начало координат O, то и в этом случае лемма 2.23 очевидно верна. Поэтому можно предполагать O B.

Обозначим за X выпуклый конус с вершиной O, состоящий из всех лучей r таких, что rB = (иначе говоря, это коническая оболочка B). Обозначим также следующий конус:

Ясно, что X и X — гладкие острые выпуклые конусы.

Для любой прямой l и вектора x l и двух точек a1, a2 l будем говорить, что a больше (дальше) a1 относительно вектора x, если a2 = a1 + x, где > 0. Понятие меньше (ближе) определяется аналогично.

Теперь нам понадобится еще несколько лемм, в которых фигурируют рассматриваемые множества A, B и X:

Лемма 2.34. Для любого ненулевого вектора x X, где X определено выше, и любой прямой l x пересечение либо пусто, либо состоит из одного полуинтервала.

Доказательство. Ясно, что пересечения S1 = l A и S2 = l (A + B) являются отрезками, как пересечения прямой и выпуклого множества. Так что нам нужно показать, что множество S1 \ S2 либо пусто, либо состоит из одного полуинтервала.

Докажем от противного. Утверждение этой леммы может быть неверным только в одном случае, когда отрезок S2 содержится внутри S1. Но x X, значит найдется b = x B ( > 0), значит множество A + B содержит отрезок S1 + b на прямой l, то есть что является явным противоречием.

Лемма 2.35. Для ограниченных, гладких и строго выпуклых A и B таких, что O B, найдется отображение обладающее следующими свойствами:

2. для любого a A f (f (a)) = f (a);

Обозначим за nC внешнюю нормаль к гладкому выпуклому множеству C в точке p bd C.

Доказательство. Обозначим A = A + X и докажем, что существует отображение такое, что 2. для любого a A f (f (a)) = f (a);

Тогда для доказательства леммы достаточно будет взять ограничение f на A. Сначала определим f на границе A. Множество A является выпуклым объединением семейства транслятов гладкого выпуклого множества A, поэтому оно гладко.

Для любой a bd A в качестве f (a) возьмем точку bd A, так, что Так как A гладко, то по лемме 2.17 отображения точки его границы в нормаль непрерывно, а так как A строго выпукло, то по лемме 2.16 отображение нормали в точки на ее границе непрерывно. Это доказывает непрерывность отображения f на bd A.

Свойство 2 для этого отображения выполнено очевидно. Свойство 1 выполнено, так как каждая точка a bd A принадлежит bd(A + x) для некоторого x X. Ясно, что тогда и f (a) = a x, то есть f (a) a X. Свойство 3 также выполняется. Докажем это.

Образ f — это те точки p bd A, для которых nA b(X).

Покажем, что такие точки p A не могут принадлежать A + B. На самом деле nA b(X) означает, что B полностью лежит в полупространстве, определяемом неравенством Так как nA — внешняя нормаль к A, то Значит а это означает, что точка p может лежать в A + B только в том случае, если p = a + b Но при этом p, a A и A строго выпукло, следовательно p = a и b = O, но в самом начале мы предположили, что O B.

Теперь распространим отображение f на все A. Выберем некоторый вектор x int X. Определим отображение следующим образом: для любого a A определим g(a) так, чтобы выполнялось следующее:

Легко видеть, что таким образом это отображение определено и непрерывно.

Теперь определим f на A так:

Для такого отображения свойства 2 и 3 очевидно продолжают выполняться, а свойство 1 выполняется потому, что Тем самым лемма доказана.

Теперь все готово для доказательства леммы 2.23:

Доказательство леммы 2.23. По лемме 2.33 для доказательства достаточно рассматривать ограниченные, строго выпуклые и гладкие A и B.

Также можно считать, что O B.

Рассмотрим отображение f из леммы 2.35. Покажем, что оно задает гомотопическую эквивалентность A и f (A).

Рассмотрим естественное отображение вложения Отображение if гомотопно тождественному отображению A, так как для любой точки a A отрезок [a i(f (a))] содержится в A. Отображение f i равно тождественному отображению f (A). Значит, это действительно гомотопическая эквивалентность.

Покажем теперь, что f задает гомотопическую эквивалентность A \ (A + B) и f (A) = f (A \ (A + B)).

В этом случае отображение f i равно тождественному отображению f (A).

Отображение i f гомотопно тождественному отображению множества A \ (A + B).

В самом деле, покажем, что для любой точки a A \ (A + B) отрезок [a i(f (a))] лежит в A \ (A + B). По лемме 2.34 этот отрезок параллелен некоторому x X, и по свойству 1 отображения f прямая, содержащая этот отрезок, пересекает A \ (A + B) по некоторому полуинтервалу, это значит, что отрезок [a i(f (a))] содержится в этом полуинтервале, так как его концы содержатся в нем.

Таким образом доказано, что A \ (A + B) гомотопически эквивалентно A. Доказательство завершено, так как выпуклое множество A, очевидно, гомологически тривиально.

2.7 Тела постоянной ширины 2.7.1 Основные понятия и результаты Сначала поясним свойство 2.1 нормы в банаховом пространстве E. Диаметр в этом свойстве рассматривается в смысле данной нормы.

Определение. Тело постоянной ширины — это замкнутое выпуклое множество, для которого расстояние между любой парой параллельных опорных гиперплоскостей с противоположными нормалями равно 1 в смысле данной нормы.

Телам постоянной ширины посвящен обзор [22]. Свойство 2.1 было уже давно установлено для евклидовых норм в Rn, см. [23]. В обзоре [22] ставится вопрос о характеризации норм со свойством 2.1 в Rn, так как в [24] были приведены примеры норм, для которых это свойство не выполняется. По информации обзора [22] на данный момент свойство 2.1 установлено только для норм в двумерном пространстве, евклидовых норм и норм с параллелотопом в качестве единичного шара.

Следуя [22], введем понятие экстремального множества диаметра 1:

Определение. Экстремальным множеством диаметра 1 называется множество диаметра 1, которое не является собственным подмножеством какого-либо множества диаметра 1.

Верно следующее утверждение:

Теорема 2.36. Любое множество диаметра не более 1 является подмножеством некоторого экстремального множества диаметра 1.

Доказательство. Рассмотрим семейство упорядоченное по включению. Очевидно, что любой максимальный элемент этого семейства является экстремальным множеством диаметра 1, содержащим X. Покажем, что для доказательства его существования можно применить лемму Цорна.

Рассмотрим некоторое линейно упорядоченное подсемейство Покажем, что C = C F. Ясно, что C X, остается доказать, что diam C 1.

Пусть x1, x2 C. Тогда x1 X1 C и x2 X2 C. Без ограничения общности X1 X2.

Тогда x1, x2 X2, а так как diam X2 1, то |x1 x2 | 1. Следовательно, diam C и C F. Значит, лемма Цорна действительно применима.

Это утверждение позволяет свести проверку свойства 2.1 к доказательству того, что любое экстремальное множество диаметра 1 является телом постоянной ширины В данной работе вопрос о полной характеризации норм, обладающих свойством 2. не решается, однако теоремы 2.6 и 2.7 являются сравнительно обозримым критерием того, что норма в конечномерном пространстве со строго выпуклым единичным шаром обладает свойством 2.1. Теорема 2.6 является достаточным условием для выполнения свойства 2.1.

Перейдем к теоремам 2.6 и 2.7.

Теорема 2.6 позволяет доказать классические факты (см. [25]) о том, что свойством 2.1 обладает любая норма в двумерном пространстве и что им обладает евклидова норма (см. [23]). Они сразу следуют из теоремы 2.19 и того факта, что в двумерном случае любое выпуклое множество является порождающим.

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

Для норм, единичные шары которых не являются строго выпуклыми, теорема 2. не всегда верна в обратную сторону.

Пример 2.4. Контрпримером является следующая конструкция единичного шара:

возьмем трехмерный куб со стороной 2 и центром в начале координат, и отрежем около его противоположных вершин по пирамидке с боковыми ребрами 1/2 (как показано на рисунке 2.1). Множество Y = B1 (B1 + (1/2, 1/2, 0)t ) не является слагаемым B1, так как это будет параллелепипед без отрезанных уголков и с высотой, равной высоте B1. Достаточно ясно, что трансляты Y не смогут достать до точек на тех ребрах B1, которые параллельны оси Oz и выходят из отрезанных пирамидок.

С другой стороны, экстремальные множества диаметра 1 — это кубы с ребром 1, у которых отрезаны в соответствующих углах две пирамидки, сумма боковых ребер которых (то есть сумма ребра первой и ребра второй) равна 1/2. Нетрудно проверить, что такие экстремальные множества имеют постоянную ширину 1.

2.7.2 Доказательства Перед доказательством теоремы 2.6 сформулируем еще одно свойство нормы:

Свойство 2.2. Для любого множества T такого, что diam T 1 пересечение Y = tT (B1 + t) является слагаемым B1.

Для проверки этого свойства подойдет аналог теоремы 2.3:

Лемма 2.37. Свойство 2.2 достаточно проверить для множеств T, состоящих из двух элементов.

Замечание. Для множеств T, состоящих из двух элементов t1 и t2 таких, что t t2 1 множество Y = (B1 + t1 ) (B1 + t2 ) будет иметь непустую внутренность. Кроме того, b(B1 ) = E. Поэтому лемма 2.37 отличается от теоремы 2.3 только тем, что вместо M стоит единичный шар B1 и рассматриваются только такие T, что diam T 1.

Доказательство. По сути доказательство то же самое, что и у теоремы 2.3.

В доказательстве для конечных T и int Y = нужно проверить, что в индукционном переходе от множества T к множеству T {t2 } диаметр множества не может стать больше 1.

Покажем это. Так как диаметр множества T не превосходит 1, то множество T содержится в Y. А так как B1 t2 (B1 + ) (B1 + ) Y T, то расстояние от t2 до любой точки из T не превосходит 1.

Доказательство для бесконечных T и int Y = остается таким же.

При разборе случая int Y = можно заметить, что лемма 2.18 также применима, так как она доказывается рассмотрением последовательности Tn = (1 n )T и последовательности соответствующих Yn = tTn B1 + t. Так как diam Tn 1 и int Yn =, то для Tn и Yn все уже доказано, и, аналогично доказательству леммы 2.18, для Y тоже найдется Y такое, что Y + Y = B1.

Теперь можно перейти к доказательству теоремы 2.6.

Доказательство теоремы 2.6. По лемме 2.37 можно считать свойство 2.2 выполненным для нормы в пространстве E.

По теореме 2.36 нужно доказать, что всякое экстремальное множество Y диаметра 1 имеет постоянную ширину. Тогда для любой точки x Y найдется точка y Y такая, что x y > 1, так как иначе множество Y {x} будет иметь диаметр 1 и содержать Y. Это означает, что Y = yY (B1 + y) и, по свойству 2.2, Y является слагаемым B1.

Пусть теперь ширина Y в каком-то направлении равна 1 ( > 0). Проведем в соответствующем направлении опорную гиперплоскость h и гиперплоскость h на расстоянии 1 от нее так, что Y лежит между ними и не пересекает h. По лемме 2. существует такой транслят B1 + y, что B1 + y Y и (B1 + y) h =. Так как Y экстремально, то y Y, но в таком случае y лежит между двумя гиперплоскостями, расстояние между которыми равно 1 и при этом находится на расстоянии больше от одной из них, так как (B1 + y) h =. Противоречие.

Значит, ширина Y во всех направлениях равна 1.

Доказательство теоремы 2.7. Предположим противное, то есть что существуют такой вектор u ( u 1), что множество не является слагаемым B1 и норма · обладает свойством 2.1.

По леммам 2.16 и 2.14 в этом случае найдутся такие точка y bd Y и внешняя нормаль n в этой точке, что для точки x B1 с такой же внешней нормалью n ни для какой окрестности U y Выберем такую окрестность U точки y в множестве Y, что диаметр U не превосходит 1. Тогда рассмотрим множество F = {0} {u} U. По теореме 2.36 найдется экстремальное множество G F.

Ясно, что diam G 1, значит G B1 (B1 + u) и n является внешней нормалью к G в точке y. Пусть h — перпендикулярная n опорная гиперплоскость к G в точке y. Норма пространства E обладает свойством 2.1, поэтому ширина множества G в направлении n равна 1. Значит, G пересекает гиперплоскость h, находящуюся на расстоянии 1 от h в некоторой точке y. Тогда очевидно y y = 1 и G B1 + y.

При этом n будет нормалью к B1 +y в точке y (B1 +y не выходит за гиперплоскость h в противоположную h сторону, так как расстояние между h и h равно 1). Получаем, что множество G и, следовательно, множество Y U попало в транслят B1 так, что n является внешней нормалью к B1 + y в точке y (при этом требуемая точка x B определится как x = y y ). Это противоречит выбору точки y.

Глава О назначении точек гиперграням многогранника 3.1 Введение Данная глава продолжает исследования, начавшиеся с гипотезы, сформулированной Произволовым на конференции по комбинаторной геометрии в Батуми в 1985 году (см. [30]): если дан выпуклый многоугольник P на плоскости со сторонами S1,..., Sn и точки a1,..., an, то точки ai можно перенумеровать так, что n треугольников, образованные вершинами pi и основаниями Si соответственно покроют P.

Эта гипотеза была доказана Богомольной, Назаровым и Рукшиным (см. [28]).

Фактически, в [28] доказаны теоремы 3.4 и 3.5 данной главы для случая R2 и намечено доказательство в общем случае Rn (n > 2), при этом предполагалось, что точки лежат внутри многоугольника.

Бездек в [27] исследовал случай теоремы 3.4 в R2, когда точки не обязательно лежат внутри многоугольника и доказал этот случай. Кроме того, был исследован случай теоремы 3.5 в R2, когда точки не обязательно лежат внутри многоугольника, в результате была доказан вариант теоремы 3.1 в R2 с заменой числа p на меньшее p = m. Также была сформулирована гипотеза о том, что константа p может быть сделана равной m, которая доказана здесь в более общем случае в Rn (теорема 3.1).

Независимо и одновременно с автором теорема 3.1 и следствия 3.4 и 3.5 были доказаны Рукшиным и Петровым в [29] с использованием существенно отличных методов.

Автором были обобщены теоремы 3.4 и 3.5 на случай, когда количество точек превосходит количество граней (теоремы 3.2 и 3.3) и выведено следствие 3.15.

3.2 Формулировка основных результатов Напомним некоторые определения:

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

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

Далее для каждого многогранного множества X будем считать, что int X =, если не оговорено противное, и при этом множество функций {fi }iIm таково, что codim H(fi ) X = 1 для всех i Im. Последнего всегда можно добиться путем выбрасывания из {fi }iIm лишних элементов.

Определение. Множества Fi = H(fi ) Для многогранного множества X обозначим Hi = H (fi ), i Im.

Теорема 3.1. Пусть X — многогранное множество в Rn, с семейством всех гиперграней {Fi }iIm и {xi }iIp Rn, где p = m/2. Тогда существует такая инъекция Оценку p в теореме 3.1 нельзя увеличить. Для p > m/2 в [27] построен контрпример при n = 2. В дальнейшем будет показано, что, если теорема 3.1 верна при некотором n и данных p и m, то она должна быть верна и при n n и тех же p и m.

Следовательно, теорема 3.1 не верна для p > m/2 при всех n 2.

Теорема 3.2. Пусть X — многогранник в Rn с семейством всех гиперграней {Fi }iIm, A Rn, |A| = l и {li }iIm — такой набор натуральных чисел, что iIm li = l. Тогда существует разбиение множества A на множества Ai (i Im ), удовлетворяющее следующим условиям:

2) множества Ci = {a}Ai conv(a Fi ) (i Im ) покрывают X, то есть Теорема 3.3. Пусть X — многогранное множество в Rn с семейством всех гиперграней {Fi }iIm, A X, |A| = l и {li }iIm — такой набор натуральных чисел, что iIm li = l. Тогда существует разбиение множества A на множества Ai (i Im ), удовлетворяющее следующим условиям:

2) множества Ci = conv(Ai Fi ) (i Im ) попарно не пересекаются по внутренним точкам, то есть для любых i = j Im Следующие теоремы являются частными случаями теорем 3.2 и 3.3, получающимися, если |A| = m и li = 1 для всех i. Мы формулируем их отдельно, так как именно они дают положительный ответ на вопрос работы [30].

Следствие 3.4. Пусть {xi }iIm Rn и X — многогранник в Rn с семейством всех гиперграней {Fi }iIm. Тогда существует S m такая, что Следствие 3.5. Пусть X — многогранное множество в Rn с семейством всех гиперграней {Fi }iIm и {xi }iIm X. Тогда существует S m такая, что Кроме того, несколько следствий и гипотез сформулированы в разделе 3.5. Следующая теорема возникла при доказательстве теоремы 3.1.

Теорема 3.6. Пусть X — многогранное множество в Rn с семейством всех гиперграней {Fi }iIm, A Rn \ X, |A| = l и {li }iIm — такой набор натуральных чисел, что iIm li = l. Пусть также |A iI Hi | iI li для всех I Im. Тогда существует разбиение множества A на множества Ai (i Im ), удовлетворяющее следующим условиям:

2) множества Ci = conv(Ai Fi ) (i Im ) не перекрываются с X и попарно не пересекаются по внутренним точкам, то есть для любого i Im и для любых i = j Im Метод доказательства всех этих результатов является, по существу, одним и тем же и отличным от методов работ [27] и [28].

3.3 Вспомогательные утверждения Дадим сначала несколько определений.

Определение. Будем говорить, что множество V в линейном (аффинном) пространстве L (A) находится в общем положении или V LGP (V AGP ), если для всех конечных U V.

Нам понадобится обобщение этого стандартного определения.

Определение. Пусть F – семейство отображений конечного множества I в L (A), тогда отображение F находится в общем положении или LGP (F) ( AGP (F)), если Если семейство отображений F — неприводимое алгебраическое подмногообразие в LI (AI ), то легко видеть, что LGP (F) (AGP (F)) — открыто и всюду плотно в F.

Определение. Многогранное множество S Rn назовем простым, если или S — симплекс, или S = iIm H + (fi ) и {fi }iIm LGP, m n.

Для двух точек a = b Rn обозначим:

1. a b, [a b — прямую, проходящую через a и b и луч на этой прямой с началом a, содержащий b;

2. a b = [a b \ {a} \ (a b) — луч на прямой a b с началом в b, не содержащий a.

Определение. Множество U V называется V -звездным, если для всех u U и v V отрезок [u v] U. Очевидно, что если:

1. V =, то V -звездное множество U — звездно;

3. U — V -звездно и W V, то U — W -звездно.

Следующее утверждение можно найти, например, в [31].

Лемма 3.7. Пусть X — многогранное множество с семейством всех гиперграней {Fi }iIm в пространстве L. Тогда пространство L можно вложить в пространство большей размерности L и найти такое простое многогранное множество S в L, что X = S L, int X = (int S) L и для любого i Im Fi = Gi L, где {Gi }iIm — множество гиперграней S. При этом, если X — многогранник, то S — симплекс.

Лемма 3.8. Пусть G — конечный неориентированный граф на множестве вершин V Ln, причем V LGP, с множеством ребер E = {ei }iIl, l |V | и F — семейство всех отображений g : Il Ln таких, что если f1, f2 V — концы e E, то H(f1 ) H(f2 ) H(g(e)). Тогда существует непустое W V, такое, что Доказательство. Так как |E| |V |, то в G есть цикл. Пусть ei1,... eim — последовательные ребра цикла, а fi1, fi2,... fim — его последовательные вершины. По условию леммы, имеем, Следовательно, если g LGP (F). Но тогда Лемма доказана.

Лемма 3.9. Если семейство замкнутых подмножеств {Vi }d симплекса S в Rd1 с гипергранями {Fi }d таково, что каждое множество Vi Fi -звездно и S d Vi, то d Vi =.

Докажем несколько более общее утверждение, которое является обобщением теорем Кли и Леви (см. [2]).

Лемма 3.10. Пусть S Rd1 — гомотопически тривиальное множество и {Fi }d — такое семейство подмножеств S, что FJ = iJ Fi = и гомотопически тривиально для всех J Id, J = Id. Если {Vi }d — такое семейство замкнутых подмножеств S, что Vi — Fi -звездно и S d Vi, то d Vi =.

Доказательство. Пусть J Id и VJ = iJ Vi. Так как множества Vi — FJ -звездны, то VJ также FJ -звездно. Поэтому множество VJ гомотопически тривиально, а значит когомологические группы H m (VJ ) = 0 при m > 0.

Предположим, d Vi =. По теореме Лере (см. [32]), для когомологий Чеха покрытия V = {Vi } пространства S, имеем, H i (S, Z) = H i (V, Z). В частности, Полученное противоречие доказывает лемму.

Лемма 3.11. Пусть {Ui }d — такое семейство открытых подмножеств симплекса S в Rd1 с гипергранями {Fi }d, что: i) Ui rint Fi — rint Fi -звездно; ii) int S Ui ; iii) у всех p bd S существует такая окрестность N (p), что N (p)int S i, pFi Ui. Тогда Доказательство. Можно считать S правильным симплексом. Пусть где Ak — сжатие относительно гиперплоскости, проходящей через грань {Fi } с коэфi фициентом (1 1/k), k N. Очевидно, что Uik Uik и Vik Vik при k k и так как Fi cl Ui, то Fi Vik для всех i Id и k N. Также ясно, что Пусть G = iJG Fi — грань симплекса, где JG = {i Id : G Fi }. Докажем, индукцией по codim G, что у rint G есть такая окрестность WG, что при некотором k Если codim G = 1, то G = Fi для некоторого i. Тогда Uik rint Fi — открытое множество в топологии пространства S и rint Fi Uik rint Fi.

Индукционный переход. Пусть p rint G, тогда по условию леммы существует такая окрестность N (p), что Возьмем в L сферу с центром в p такую, что N (p).

Очевидно, если грань G такая, что G =, то G G и dima G > dima G.

Поэтому, по предположению индукции, для некоторого k найдется такая окрестность WG множества rint G, что при некотором k. Поэтому множество замкнуто, а значит и компактно. Так как Y — компактно и то имеем, Y iJG Если G Fi, то Uik rint G — rint G-звездны и поэтому Множество int conv(int G ) — окрестность rint G и индукционный переход доказан.

Таким образом, для некоторой окрестности W bd S и некоторого k, имеем, А так как int S \ W — компактное множество, то, для некоторого k, имеем, при некотором k. Но тогда, по лемме 3 и при этом k, имеем, 3.4 Доказательства основных результатов Заметим, что теоремы 3.2, 3.3 и 3.6 достаточно доказать в случае, когда X — простое многогранное множество.

Действительно, по лемме 3.7, X = S L, где S — простое многогранное множество, L — n-мерное подпространство RN и Fi = FiS L, где {FiS }iIm — гиперграни В самом деле, теоремы 3.2, 3.3 и 3.6 для X следуют из таких же утверждений для S, так как Далее S — простое многогранное множество, и {Fi }iIm — его гиперграни.

Далее, можно считать, что A AGP и a a Fi для всех a A, j Im. Очевидно, что множество наборов A таких, что A AGP и A a Fi = для всех i, открыто и всюду плотно в множестве AN = RN l всех наборов A.

Теоремы 3.2, 3.3 и 3.6 достаточно доказать для любого всюду плотного B AN. l В самом деле, пусть A AN, элементы a A как то пронумерованы от a1 до al. и последовательность {Ak } B такова, что и для Ak утверждение какой-либо из теорем верно. Для каждого k получим некоторое разбиение Ak на Ak. Очевидно, что существует бесконечное N N такое, что соответствующие разбиения индексов Il элементов множеств Ak совпадают. Тогда то, при достаточно больших k, так как множества conv(a Fi ) — замкнуты. Этим случай теоремы 3.2 разобран.

В случае теорем 3.3 и 3.6, если то, при достаточно больших k, В случае теоремы 3.6, если для некоторого i то, при достаточно больших k, Кроме того можно потребовать выполнение еще одного условия. Для того, чтобы его сформулировать, потребуется несколько обозначений.

Пусть S — простое многогранное множество, {Fi }iIm — его гиперграни и множество A занумеровано: A = {ai }iIl. Тогда положим тогда обозначим через F(S, A) семейство отображений g : I LN таких, что а через G(S) — семейство отображений : I LN таких, что Очевидно, F(S, A) G(S) и для любого g G(S) найдется такое A, что g F(S, A).

Значит, множество таких A, что F(S, A) LGP (G(S)), плотно в множестве всех возможных A.

Теперь мы можем доказывать теоремы 3.2, 3.3 и 3.6 при выполнении следующих условий:

(1) S — простое многогранное множество с гипергранями {Fi }iIm ;

(3) F(S, A) содержит некоторое g LGP (G(S)).

Для данного g LGP (G(S)) будем для краткости писать gajk вместо gijk, если номер a A равен i. Заметим, что при выполнении этих условий H(gajk ) = a(a, Fj Fk ), так как При доказательстве теоремы 3.1 эти условия не нужны, так как она следует из теорем 3.3 и 3.6, и поэтому она будет доказана последней.

Доказательство теоремы 3.2. Можно считать, что S — симплекс, так как X — многогранник. Доказательство будем проводить индукцией по dima S. Если dima S = — все очевидно.

Обозначим для всех I Im Разобъем доказательство на два случая в зависимости от выполнения следующего условия:

Случай 1. Условие (*) не выполняется. Тогда существуют I Im и A A такие, что Обозначим I = Im \ I. Уменьшая множество A при необходимости, можно считать, что |A | = l lI = lI. Пусть Докажем, что Пусть p — ортогональная проекция на L (всюду далее L — подпространство Rn такое, что L L и codim L = dima L), тогда p(S) — симплекс с вершиной p(L) = p(M ) и противоположной ей гипергранью p(N ). Имеем, так как fi (a) < 0, fi (M ) = 0, i I, a A и для некоторой окрестности U точки p(M ), имеем, Поэтому [p(a) p(M ) p(N ) =. Тогда, имеем, Положим тогда Ai = A, тогда Ci уже покрывает S, а для остальных i I определим Ai произвольно, чтобы их мощности были заданными числами. В этом случае разбиение {Ai } построено и теорема доказана.

Если dima M > 0, то для всех a A возьмем любую a L conv({a} N ), они образуют множество A. Так как dima M = m |I| 1 < m 1, то, по предположению индукции, для симплекса M, множества A и чисел li (i I ) существует разбиение A = iI Ai такое, что и |Ai | = li, где FjM — гиперграни M. Соответствующие Ai подмножества A обозначим Ai (i I ).

Для i I выберем множества Ai из A \ iI Ai произвольно, чтобы их мощности были заданными li. Тогда для всех a Ai и соответствующих им a Ai поэтому Следовательно, для всех a из некоторого Ai, имеем Тогда В этом случае теорема доказана.