2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Задача о целой точке в выпуклом многограннике
Сообщение08.08.2021, 05:05 


12/05/07
509
г. Уфа
В пространстве $\mathbb R^n$ имеется целочисленная решётка (множество точек с целочисленными координатами). Элементарная ячейка такой решётки имеет объём $V=1$. Существуют ли такие два числа $V(n)$ и $D(n)$, что всякий выпуклый многогранник в $\mathbb R^n$ объёма $V\geqslant V(n)$ и диаметра $ d\leqslant D(n)$ содержит как минимум одну точку целочисленной решётки? Если да, известно ли данное утверждение и где можно посмотреть его доказательство?

 Профиль  
                  
 
 Re: Задача о целой точке в выпуклом многограннике
Сообщение08.08.2021, 08:56 
Заслуженный участник


25/02/11
1745
Имеется теорема Минковского. Там не многогранник, а выпуклое тело, но есть требование симметричности относительно нуля. Для плоскости можно попробовать вывести из теоремы Пика.

 Профиль  
                  
 
 Re: Задача о целой точке в выпуклом многограннике
Сообщение08.08.2021, 12:08 
Заслуженный участник


18/01/15
2590
Ruslan_Sharipov в сообщении #1528296 писал(а):
Существуют ли такие два числа $V(n)$ и $D(n)$, что всякий выпуклый многогранник в $\mathbb R^n$ объёма $V\geqslant V(n)$ и диаметра $ d\leqslant D(n)$ содержит как минимум одну точку целочисленной решётки?
Да, конечно. Это следует из того, что при некоторых $V'$ и $D'$ множество выпуклых многогранников диаметра $\leq D'$ и объема $\geq V'$ пусто.

 Профиль  
                  
 
 Re: Задача о целой точке в выпуклом многограннике
Сообщение09.08.2021, 03:35 


12/05/07
509
г. Уфа
vpb в сообщении #1528310 писал(а):
Да, конечно. Это следует из того, что при некоторых $V'$ и $D'$ множество выпуклых многогранников диаметра $\leq D'$ и объема $\geq V'$ пусто.

Ну это софизм. Может ли многогранник из пустого множества многогранников считаться содержащим как минимум одну точку целочисленной решётки? Если хотите избежать подобного толкования задачи, добавьте требование непустоты множества многогранников с заданными ограничениями на объём и диаметр. Хотя мне думается такое требование понимается имеющимся по умолчанию.

 Профиль  
                  
 
 Re: Задача о целой точке в выпуклом многограннике
Сообщение10.08.2021, 03:34 
Заслуженный участник
Аватара пользователя


08/11/11
5936
1) $n-1$-мерная площадь поверхности выпуклого многогранника в $\mathbb R^n$ диаметра $d$ не превышает $C_1(n) d^{n-1}$.

Доказательство: многогранник диаметра $d$ содержится в шаре радиуса $d$. Построим внешние цилиндры около каждой грани и посмотрим на их пересечения со сферой (границей шара). Поскольку каждое из этих пересечений проецируется в соответствующую грань, его площадь может быть только больше (и ясно, что они не пересекаются друг с другом). Другими словами, в качестве $C_1(n)$ можно взять площадь единичной сферы в $\mathbb R^n$.

2) Предположим, что многогранник диаметра $d$ в $\mathbb R^n$ не содержит шара радиуса $\varepsilon$. Тогда любая внутренняя точка многогранника содержится в $\varepsilon$-окрестности одной из граней, причём грань можно выбрать так, что проекция точки на гиперплоскость, содержащую эту грань, принадлежит этой грани (достаточно взять шар минимального радиуса, пересекающийся с границей многогранника, он будет касаться одной из граней, её и выбрать).

3) В предположениях пункта 2, суммируя по всем граням получаем, что объём многогранника не превосходит $C_1(n)d^{n-1}\varepsilon$. Следовательно, если назначить объём многогранника больше $C_1(n)d^{n-1}$ и диаметр меньше $d$, он будет содержать шар радиуса $1$. Само $d$ должно быть не очень маленьким, чтобы многогранник существовал. Например, куб диаметра $d$ имеет объём $(d/\sqrt{n})^n$, поэтому очень грубо достаточно удовлетворить $C_1(n)d^{n-1}\le (d/\sqrt{n})^n$. Обозначим через $V_0(n)$ и $D_0(n)$ какую-нибудь пару объём-диаметр с данным свойством. Тогда, из масштабирования, если взять $V(n)=R^n V_0(n)$, $D(n)=R^{n-1}D_0(n)$, то многогранник с $V\ge V(n)$ и $D\le D(n)$ будет существовать и любой такой многогранник будет содержать шар радиуса $R$. При $R>2\sqrt{n}$ этого достаточно, чтобы он содержал точку решётки (по крайней мере, если её интерпретировать как написано в исходном посте).

Где это написано -- не знаю, но мне кажется, что это простое упражнение, которое очевидно из общих соображений: многогранник большого диаметра и маленького объёма должен быть очень сплюснут, поэтому если объём не очень маленький, у него должна быть нетривиальная внутренность. На самом деле, я подозреваю, что если взять $V(n)$ равное объёму единичного шара, а $D(n)$ чуть меньше диаметра этого шара, то любой многогранник с такими данными должен быть очень близок к единичному шару и поэтому содержать шар радиуса чуть меньше единицы. Но это довольно муторно с точки зрения строгости.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 5 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group