Спросить
Войти
^Г, СибАК
www.sibac.m1o
Естественные и математические науки в современном мире _№ 6 (41), 2016 г.
НОРМЕННЫЙ МИНИМУМ РЕШЕТКИ
И ОПРЕДЕЛИТЕЛИ ГРАНЕЙ ВНУТРЕННЕГО ПОЛИЭДРА КЛЕЙНА
Макаров Илья Андреевич
заместитель руководителя департамента анализа данных и искусственного интеллекта факультета компьютерных наук, старший преподаватель Национального Исследовательского Университета «Высшая Школа Экономики»,
РФ, г. Москва E-mail: revan1986@mail. ru
LATTICE NORM MINIMA AND FACETS DETERMINANTS OF INTERIOR KLEIN POLYHEDRA
Ilya Makarov
deputy head of Data Analysis and Artificial Intelligence school at faculty of Computer Science, senior lecturer, National Research University Higher School of Economics,
Russia, Moscow
АННОТАЦИЯ
В работе доказывается многомерное обобщение утверждения о том, что действительно число плохо приближаемо тогда и только тогда, когда его неполные частные равномерно ограничены. Мы рассматриваем многомерный аналог цепных дробей - внутренний полиэдр Клейна - целочисленные характеристики границы которого выбираются в качестве неполных частных многомерной цепной дроби. Мы доказали равносильность равенства нулю норменного минимума решетки, порождающего внутренний полиэдр Клейна, и условия, что определители всех граней всех 2n внутренних полиэдров Клейна, соответствующих данной решетке и координатным ортантам, равномерно ограничены сверху.
ABSTRACT
We proved a multidimensional generalization of a statement that real number is badly approximated if and only if its partial quotients are uniformly bounded. We considered multidimensional analog of continued fractions, such as interior Klein polyhedron, and integral characteristics of its border. We use them as multidimensional partial quotients of the
Естественные и математические науки в современном мире № 6 (41), 2016 г_
continued fraction. We proved the equivalence zero norm minimum of a lattice generating an interior Klein polyhedron, and uniform boundness from above of the determinants of all faces for all 2n interior Klein polyhedra corresponding to a lattice and coordinate orthants.
Действительное число а называется плохо приближаемым, если существует константа c > 0, такая что для любого целого числа p и любого натурального числа q выполняется условие
|qa-p| >-.
Известно следующее утверждение:
Утверждение 1. Иррациональное число плохо приближаемо тогда и только тогда, когда если его неполные частные равномерно ограничены.
Определение плохой приближаемости может быть сведено к исследованию линейных форм, а именно: два числа а ив плохо приближаемы тогда и только тогда, когда inf |(qa — p)(qP — p)| > 0 , где наименьшее значение ищется по всем целым p и q, не равным одновременно 0.
Целочисленной длиной отрезка с концами в Z2 называется количество точек решетки Z2, содержащихся во внутренности этого отрезка, плюс 1. Целочисленным углом между двумя такими отрезками с общей вершиной называется площадь параллелограмма, натянутого на них, деленная на произведение их целочисленных длин.
Рассмотрим два иррациональных числа а и р. Их цепные дроби допускают следующее геометрическое представление: рассмотрим две прямые в R2, порожденные векторами (1, а) и (1, р). Внутренний полигон Клейна определяется как выпуклая оболочка целых точек строго внутри каждого конуса, порождаемого линейными оболочками этих векторов. При условии а>0>р>—1 имеет место соответствие [1; 4] между вершинами полигонов Клейна и подходящими дробями чисел а и р.
^ СибАК
www.sibac.info
СибАК
Естественные и математические науки в современном мире пщ&М&.яЬааМо_№6(41). 2016г.
Таким образом, свойства чисел, выраженные цепными дробями, могут быть интерпретированы как свойства границ полигонов Клейна или границ внутренних полигонов Клейна. Если теперь определить форму
ф<х,р(Х1,Х2) = (Х1а - Х2ХХ1Р - Х2),
то утверждение 1 можно переформулировать следующим образом:
Утверждение 2. Для любых иррациональных чисел а и в целочисленные длины ребер полигонов Клейна равномерно ограничены если, и только если
|П£ ,|фа,р(х)1 > 0.
Ж.-О. Муссафир в работе [6] доказал, что выпуклая оболочка всех целых точек в полиэдре является замкнутым множеством и обобщенным полиэдром только для случая, когда все грани симплициального конуса одновременно либо содержат решетку полной размерности, либо не содержат ни одной точки решетки. Автор в работе [5] показал, то выпуклая оболочка точек строго внутри открытого полиэдра, не содержащего прямой линии, является замкнутым множеством и обобщенным полиэдром.
В случае, когда С — симплициальный конус с началом в 0, то есть, число порождающих полиэдр С гиперплоскостей gi равно d, gi -линейно независимы, множество К(С) = ш^((С \\ дС) П 2й) называется внутренним полиэдром Клейна и является обобщением понятия цепной дроби на многомерный случай.
Пусть дана произвольная ^мерная решетка Лс 1° и произвольный невырожденный симплициальный конус СсК° с ребрами, порожденными векторами е1ш1, ...,епшп для 2° комбинаций £; = ±1,1 = 1, ...,п: С = {Я1е1ш1 + —+ Япепш° > 0}. Рассматривается множество К = coпv ((С \\дС)ПЛ), которое оказывается аналогом полиэдра Клейна. Парусом называется граница П = дК так выбранного аналога полиэдра Клейна К.
Опорной к K гиперплоскостью называется такая гиперплоскость
Н = {Х|М = Ц}, что Н П К^(С) Ф 0 и (h, Kint(C)) > ho.
.(с СибАК
Естественные и матемапш ческие науки в современном мире
№ 6 (41). 2016г._www.sibac.info
Пересечение опорной гиперплоскости с K называется гранью F для K. Размерностью грани называется размерность l линейной гиперплоскости, проходящей через 0 параллельно Aff(F). В зависимости от размерности грань F называется: вершиной, при l = 0, ребром, при l = 1, гипергранью (или просто гранью), при l = n — 1.
Обозначим через C0 конус, ребра которого порождены векторами ex, ...,en. Ему соответствует форма ф0(х) = xx • ... • xn. Форма ф(х) соответствует конусу C, если ф(х) = ф0^-1 •x) • det(W), где W -матрица координат векторов ш1, ..., шп, записанных по столбцам.
Норменным минимумом решетки Л (относительно конуса C0) называется величина N(A) = inf |ф0(х)|. Норменным минимумом
решетки Zn относительно конуса C называется величина N(Zn, C) = inf | ф (x) |.
Пусть Fe Rn - произвольный (n — 1) —мерный многогранник. Тогда определителем F называется величина det(F) = voln(conv(FU {0})) • n! .
Вершина v 6 П, взятая вместе с ребрами K, ей инцидентными, называется реберной звездой паруса П. Определителем реберной звезды v паруса П, у которой на каждом ребре выбран минимальный вектор Г; с началом и концом в точке решетки, количеством ребер равном m, называется:
det(Stv) = ^ |det(r;i.....rin)| .
Под сечением конуса C по F понимается S(F) = Aff(F)HC.
Теорема 1. Следующие условия эквивалентны:
Оказывается, что доказательства из работ [3; 2] целиком переносятся на рассматриваемый нами случай. Поскольку полиэдр Клейна хорошо определялся только для иррационального относительно решетки симплициального конуса, то все утверждения
^Г, СибАК
www.sibac.m1o
Естественные и математические науки в современном мире _№ 6 (41). 2016 г.
о гранях делались в предположении, что все точки находятся строго внутри конуса. Таким образом, теоремы, утверждающие свойства граней полиэдра Клейна, на самом деле утверждают свойства границы выпуклой оболочки целых точек внутри конуса. Из [5] следует, что теорема 1 верна для внутреннего полиэдра Клейна.
Следствие 1. Если на границах конуса C лежат точки решетки Zn, то определители граней одного из парусов, порожденных конусом C и решеткой Zn, не ограничены.
Следствие 2. Если K имеет неограниченную грань, то норменный минимум решетки равен 0.
Доказательство следствия 2. Если у какого-то из парусов, порождаемых конусом C и решеткой Zn, есть неограниченная грань, то существует параллельное ей ребро l конуса C. Отсюда следует, что через l проходит вполне рациональная гиперплоскость п, такая что в плоскости одной из граней двойственного конуса C* лежит ее нормаль пп. Получаем, что ЗЯ > 0: Япп 6 Zn, откуда следует, что C* не иррационален. Значит C* и содержит целую точку на грани. Отсюда следует, что норменный минимум двойственного конуса N(C*) равен
В работе [3; 2] рассматривался случай иррационального конуса, порождающего полиэдр Клейна. Переходя к внутреннему полиэдру Клейна для более широкого класса конусов, мы сохранили результаты на связь норменного минимума соответствующей решетки и ограниченностью характеристик внутреннего полиэдра Клейна, обобщая теорему о плохой приближаемости числа, представленного цепной дробью, на многомерный случай.
Список литературы:
