Выпуклые и слабо-выпуклые подмножества решетки

[lofar]

Рассмотрим в $n$-мерном пространстве $\mathbb R^n$ решетку $\mathbb Z^n$. Выпуклую оболочку множества $X\subseteq\mathbb R^n$ будем обозначать $Conv(X)$.

Подмножество $M$ решетки $\mathbb Z^n$ назовем:
(i) выпуклым (в $\mathbb Z^n$), если $M=Conv(M)\cap\mathbb Z^n$.
(ii) слабо-выпуклым (в $\mathbb Z^n$), если $M$ вместе с любыми двумя точками $a,b$ содержит и все точки из $[a,b]\cap\mathbb Z^n$ (здесь $[a,b]=\{at+b(1-t)|0\leqslant t\leqslant 1\}$ --- отрезок в $\mathbb R^n$ с концами $a$ и $b$).

В данном определении, выпуклое множество в $\mathbb Z^n$, содержащее более одной точки, не является выпуклым в $\mathbb R^n$ (здесь имеется в виду обычная выпуклость). Допускаю, что терминология не вполне удачная.

Ясно, что всякое выпуклое подмножество решетки является и слабо-выпуклым. Обратное неверно.



Например (см. рис.), множество $A$ (3 черных точки) слабо-вупуклое, но не выпуклое. (Множество $B$ (7 черных точек) является как выпуклым, так и слабо-выпуклым.)

Выпуклые подмножества $\mathbb Z^n$ это в точности пересечения выпуклых подмножеств $\mathbb R^n$ c $\mathbb Z^n$.
Вопрос 1. Можно ли как-то охарактеризовать слабо-выпуклые множества?
Вопрос 2. Можно ли как-то охарактеризовать слабо-выпуклые множества, не являющиеся выпуклыми?

Слабой выпуклой оболочкой множества $M\subseteq\mathbb Z^n$ назовем наименьшее слабо-выпуклое подмножество $\mathbb Z^n$, ссодержащее $M$.
Вопрос 3. Можно ли как-то описать слабую выпуклую оболочку?
Вопрос 4. Можно ли как-то охарактеризовать множества слабая выпуклая оболочка которых является выпуклым множеством?
Вопрос 5. Есть ли какие-нибудь работы посвященные подобным вопросам?

Буду рад любым комментариям. Спасибо.

[lofar]

Говоря менее формально, подмножество решетки (т. е. набор точек с целочисленными координатами) слабо-выпукло если вместе с любыми двумя точками оно содержит все целочисленные точки между ними. Слабая выпуклая оболочка множества $M$, лежащего в решетке, это наименьшее слабо-выпуклое подмножество решетки, содержащее $M$. Ясно, что такая оболочка существует всегда.

Мой интерес к данной тематике начался с задачи построения слабой выпуклой оболочки множества $T=\{(0;0),(0;a),(b;0)\}\subset\mathbb Z^2$ (эта оболочка имеет определенный алгебраический смысл). Слабую оболочку $T$ можно описать явно.

Предложение. Слабая выпуклая оболочка множества $T=\{(0;0),(0;a),(b;0)\}\subset\mathbb Z^2$ состоит из всех целочисленных точек, попавших в треугольник с вершинами $(0;0),(0;a),(b;0)$. Иными словами, слабая выпуклая оболочка $T$ равна выпуклой оболочке $T$ (в $\mathbb Z^2$).

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

Прежде всего, в слабую выпуклую оболочку $C$ попадут все целые точки, лежащие на катетах $(0;0)-(a;0)$ и $(0;0)-(0;b)$. Далее, поделим $a$ на $b$ с остатком: $a=bq+r$. Разобьем катет $a$ в соответствии с этим соотношением. Легко видеть, что $C$ содержит треугольники отвечающие неполному частному $q$ (на рисунке это $F$ и $G$ ($q=2$)). Затем делим $b$ на $r$ с остатком: $b=rq_1+r_1$ и заключаем, что $C$ содержит треугольники, отвечающие неполному частному $q_1$ (пунктирные треугольники на рисунке). Для завершения доказательства остается продолжить этот геометрический вариант алгоритма Евклида до конца.

Полагаю, что подобные вопросы должны быть достаточно хорошо изучены. Вместе с тем, смог найти не так много релевантных работ. Несколько статей об обобщениях формулы Пика. Пара статей ([1],[2]) посвященных обощенным цепным дробям (принадлежащих В. И. Арнольду!). Возникает сомнение: неужели все это (в частности то, о чем пишет Арнольд) ново?

[Руст]

lofar писал(а):

Вопрос 1. Можно ли как-то охарактеризовать слабо-выпуклые множества?
Вопрос 2. Можно ли как-то охарактеризовать слабо-выпуклые множества, не являющиеся выпуклыми?

Слабой выпуклой оболочкой множества $M\subseteq\mathbb Z^n$ назовем наименьшее слабо-выпуклое подмножество $\mathbb Z^n$, ссодержащее $M$.
Вопрос 3. Можно ли как-то описать слабую выпуклую оболочку?
Вопрос 4. Можно ли как-то охарактеризовать множества слабая выпуклая оболочка которых является выпуклым множеством?
Вопрос 5. Есть ли какие-нибудь работы посвященные подобным вопросам?

Буду рад любым комментариям. Спасибо.

Мне кажется на все эти вопросы можно ответить утвердительно.
Для этого предлагаю следующий план действий.
1. Охарактеризовать слабо выпуклые оболочки n+1 точек. Так как это не зависит от смещения (точнее инвариантна относительно смещения) всегда можно считать, что одна точка в начале координат. Тогда выпуклая оболочка будет характеризоваться матрицей, составленной векторами концов остальных точек. В частности, если определитель равен 1, то имеется выпуклость всегда. Иначе может теряться выпуклость, но не обязательно слабая выпуклость. Слабая выпуклость не теряется, если вектора линейно независимы и координаты всех векторов и координаты парных разниц взаимно просты. Т.е. в этом случае слабое замыкание n+1 точек совпадает с самим собой.
2. Для большего количества точек, можно выпуклую оболочку разделить на выпуклые симплексы и доказать, что если при любом разбиении на симплексы, каждый симплекс слабо выпуклый, то множество точек слабо выпукло.

[Macavity]

lofar писал(а):

Вопрос 5. Есть ли какие-нибудь работы посвященные подобным вопросам

Ваши вопросы напомнили о гипотезе Минковского. Но вроде прямого отношения к ней не имеют. Недавно попалась статья о ней http://www.poiskknig.ru/cgi-bin/poisk.c ... &network=1

[lofar]

Руст писал(а):

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

Тут есть одна проблема. Слабая выпуклая оболочка множества может не совпадать с объединением слабых выпуклых оболочек $(n+1)$-точечных подмножеств. Например,

Слабая выпуклая оболочка множества $N=\{A,B,C,D\}$ равна $C=\{A,B,C,D,E,F,G\}$, а объединение слабых выпуклых оболочек 3-точечных подмножеств $N$ равно $\{A,B,C,D,F,G\}$ (не содержит $E$).

Очевидный способ построения слабой выпуклой оболочки состоит в следующем. Возьмем множество точек решетки $M$. Добавим к $M$ все целочисленные точки, находящиеся на отрезках, соединяющих точки из $M$. Полученное множество обозначим $M_1$. Применим аналогичную процедуру к $M_1$, получим множество $M_2$. Продолжая подобным образом, построим цепочку подмножеств

$$M=M_0\subseteq M_1\subseteq M_2\subseteq\ldots \qquad(*)$$

Множество

$$C=\bigcup_{i=0}^{\infty}M_i $$

есть слабая выпуклая оболочка $M$.

Если $M$ конечно, то цепочка (*) стабилизируется и следовательно слабая выпуклая оболочка будет построена за конечное число шагов. Например, для множества $N=\{A,B,C,D\}$ стабилизация происходит на 3-м шаге:

$$N=\{A,B,C,D\}\subsetneq N_1=\{A,B,C,D,G\}\subsetneq N_2=\{A,B,C,D,G,F\}\subsetneq N_3=\{A,B,C,D,G,F,E\}=N_4=N_5=\ldots$$

Вопрос 6. Существует ли бесконечное множество $M\subseteq\mathbb Z^n$ такое, что в (*) все включения строгие?
Вопрос 7. Существует ли $c=c(n)$, такое, что для всякого (конечного) множества $M\subseteq\mathbb Z^n$ цепочка (*) стабилизируется до $c$-го шага. Если "да", то чему равно наименьшее такое $c$?

Macavity писал(а):

Ваши вопросы напомнили о гипотезе Минковского... Недавно попалась статья о ней ...

Благодарю Вас, непременно посмотрю эту статью.

[lofar]

Обнаружился интересный факт. Сформулированное в моем втором посте Предложение не может быть обобщено на случай трех и более измерений.

Рассмотрим множество $K=\{(0,0,0);(7,0,0);(0,6,0);(0,0,5)\}\subset\mathbb Z^3$. Точка $C=(3,1,2)$ находится в выпуклой оболочке $K$ (тетраэдре с вершинами из $K$). Вместе с тем, $C$ не лежит в слабой выпуклой оболочке $K$ ($C$ нельзя получить с помощью описанной в предыдущих постах процедуры, состоящей в проведении отрезков и добавлении лежащих на них целочисленных точек).

Точнее: тетраэдр натянутый на точки из $K$ содержит $70$ целочисленных точек, слабая выпуклая оболочка $K$ состоит из $69$ точек (те $70$ точек, исключая $C$).