Документ взят из кэша поисковой машины. Адрес оригинального документа : http://halgebra.math.msu.su/staff/arzhan/text2.pdf Дата изменения: Wed Feb 13 11:26:09 2013 Дата индексирования: Sat Apr 9 22:25:41 2016 Кодировка: koi8-r

СВЕРХНАСЫЩЕННЫЕ ПОДМНОЖЕСТВА
ИВАН В. АРЖАНЦЕВ

Эта заметка посвящена комбинаторике наборов векторов с целыми координатами. Рассматриваемая про блема мотивирована задачами алге бры, алгебраической геометрии, теории чисел и теории представлений. Более точно, определяемое ниже свойство насыщенности равносильно нормальности замыкания торической ор биты; оно допускает интересные интерпретации в коммутативной и комбинаторной алге бре, в теории числовых полугрупп и теории представлений колчанов, см., например, [2], [3], [4, Sec. 1.4], [5], [6, Ch. 13], [7]. Здесь мы ограничимся элементарной версией про блемы, которая, со бственно, и составляет наиболее содержательную ее часть. Пусть Zn = {(x1 ; : : : ; xn ) : xi Z} { множество наборов целых чисел, состоящих из n элементов. Множество Zn часто называют целочисленной решеткой или просто решеткой. Также нам понадо бится множество Qn = {(y1 ; : : : ; yn ) : yi Q} наборов рациональных чисел, которое мы будем называть пространством. Наборы (x1 ; : : : ; xn ) и (y1 ; : : : ; yn ) называют точками, или векторами, а элементы этих наборов | их координатами. Элементы решетки Zn можно покоординатно складывать/вычитать и умножать на целые числа: если c = (x1 ; : : : ; xn )
Zn

; c = (x1 ; : : : ; xn ) Zn ; r Z;

то c ± c = (x1 ± x1 ; : : : ; xn ± xn ) и rc = (rx1 ; : : : ; rxn ): Аналогичные формулы определяют сложение/вычитание и умножение на рациональные числа для элементов пространства Qn . С каждым подмножеством A Zn мы свяжем: · подмножество Z+ A = {r1 a1 + · · · + rs as : ai A; ri Z; ri 0} элементов решетки Zn , которые можно получить, складывая (возможно, с повторениями) элементы из A; · подмножество ZA = {r1 a1 + · · · + rs as : ai A; ri Z} элементов решетки Zn , которые можно получить, складывая/вычитая (возможно, с повторениями) элементы из A; · подмножество Q+ A = {q1 a1 + · · · + qs as : ai A; qi Q; qi 0} элементов пространства Qn , которые можно получить из элементов из A посредством сложения и умножения на неотрицательные рациональные числа.

Пример 1. Пусть n = 1 и
d d d d

A

= {2; 3}.
t d t t t t t t t t -

d

-5 -4 -3 -2 -1 Тогда
Z+ A

0

1

2 =

3
Z

4 и

5

6 = {q

7
Q

8 :q

9 .

= {c

Z

:c

2} {0}, ZA A
1

Q+ A

0}

Пример 2. Пусть n = 2 и

= {(3; 0); (0; 2)}.


2

И.В. АРЖАНЦЕВ

` c ` c ` c ` c ` c ` c ` c ` c ` c `

` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` `

` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` `

` c ` c ` c ` c ` c ` c ` c ` c ` c `

` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` `

` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` `

` c ` c ` c ` c ` c ` c ` c ` c ` c `

` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` `

` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` `

` 6 s ` s ` s ` s ` s ` c ` c ` c ` c `

` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` `

` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` `

s ` s ` s ` s ` s ` c ` c ` c ` c `

` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` `

` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` `

` s ` s ` s ` s ` s ` c ` c ` c ` c `

` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` `

` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` `

` s ` s ` s ` s ` s ` c ` c ` c ` c `

Здесь Z+ A = {(x1 ; x2 ) : x1 3Z; x1 0; x2 2Z; x2 0}, ZA = {(x1 ; x2 ) : x1 3Z; x2 2Z} и Q+ A = {(y1 ; y2 ) : yi Q; yi 0}. Ясно, что для любого A Zn имеем Z+ A ZA Q+ A. Определение 3. Подмножество A Zn называется насыщенным (поанглийски saturated), если Z+ A = ZA Q+ A. Пример 4. Подмножество A в примере 2 является насыщенным, а в примере 1 { нет. Задача 5. Приведите как можно больше разнообразных примеров насыщенных и ненасыщенных подмножеств. Задача 6. Докажите, что подмножество A Zn насыщенно тогда и только тогда, когда условие "rc Z+ A для некоторого натурального r и некоторого c ZA" влечет c Z+ A. Сейчас нам будет полезно определить понятие выпуклого полиэдрального конуса, который мы для краткости будем называть просто конусом. Определение 7. Подмножество K Qn называется конусом, если найдется конечное подмножество A Zn такое, что K = Q+ A. Теорема 8. Подмножество K Qn является конусом тогда и только тогда, когда оно совпадает с множеством решений некоторой конечной системы однородных линейных неравенств с рациональными коэффициентами. Доказательство этой теоремы не совсем элементарно, его можно найти, например, в книге [1]. Элементы множества (ZA Q+ A) \ Z+ A удо бно представлять се бе как "дырки" во множестве целых точек конуса Q+ A. Так, в примере 1 "дыркой" является число 1. Задача 9. Докажите, что при n = 1 для любого подмножества A Z, A = {0}, множество ZA совпадает с dZ, где d { наибольшее натуральное число, на которое делятся все элементы подмножества A. Объясните также, почему такое число d существует. Задача 10. Докажите, что если подмножество A Z содержит как положительные, так и отрицательные числа, то A насыщенно.


СВЕРХНАСЫЩЕННЫЕ ПОДМНОЖЕСТВА

3

Задача 11. Докажите, что для любого подмножества
рок" (
ZA ZA Q+ A) \ Z+ A

конечно.

AZ

множество "дыZ; c 8}

Пример 12. Пусть A = {6; 10}. Тогда

Z+ A = {0; 6; 10; 12} {2c : c = 2Z и Q+ A = {q Q : q 0}. Тем самым, "дырками" в этом являются числа 2, 4, 8 и 14. Обоснование этого примера следует из старинной олимпиадной задачи: докажите, что любую сумму денег 7 копеек можно выдать монетами 3 коп. и 5 коп. ZA Q+ A) \ Z+ A

, примере решения большую

Задача 13. Приведите пример конечного подмножества
множество "дырок" ( бесконечно. есть ненасыщенное подмножество.

A Z2

, для которого

Задача 14. Приведите пример конечного насыщенного множества, в котором
Теперь мы готовы определить наш основной персонаж. называется сверхнасыщенным (в [7] использован термин "hereditarily normal"), если любое подмножество B A является насыщенным.

Определение 15. Подмножество

A Zn

Задача 16. Докажите, что подмножество {(1; 0); (-1; 0); (0; 1); (0; -1)}
является сверхнасыщенным.

Z2

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

{ подмножество векторов, у которых ровно одна координата равна 1, ровно одна равна -1, а все остальные координаты равны нулю. Тогда подмножество n является сверхнасыщенным.
Эта теорема допускает элементарное доказательство, и мы настоятельно рекомендуем читателю его найти. Ясно, что подмножество сверхнасыщенного подмножества сверхнасыщенно. Поэтому естественно определить называется максимальным, если A не содержится ни в каком большем сверхнасыщенном подмножестве C Zn .

Теорема 17. [5], [7] Пусть

n nZ

Определение 18. Cверхнасыщенное подмножество

A Zn

Основная про блема. Описать все максимальные сверхнасыщенные подмножества A Zn . Покажем, что для любого n максимальное сверхнасыщенное подмножество в Zn существует. Если подмножество не является сверхнасыщенным, то в нем есть конечное ненасыщенное подмножество (о бъясните!). Рассмотрим о бъединение элементов некоторой цепи сверхнасыщенных подмножеств. Если оно не является сверхнасыщенным, то сожержащееся в нем конечное ненасыщенное подмножество попало бы в о бъединение конечного числа элементов цепи, а значит и в некоторый элемент цепи, что противоречит сверхнасыщенности этого элемента. Теперь существование максимального сверхнасыщенного подмножества следует из леммы Цорна. Задача 19. Докажите, что сыщенное подмножество.
{±2n

:n

0} {0} Z

| максимальное сверхна-

Задача 20. Опишите все максимальные сверхнасыщенные подмножества в Z.


4

И.В. АРЖАНЦЕВ

(Указание. Такие подмножества можно задавать двумя бесконечными последовательностями простых чисел.) Наконец, сформулируем два частных случая основной про блемы, решения которых автору неизвестны. Про блема 1. Описать все максимальные сверхнасыщенные подмножества A Z2 . Про блема 2. Описать, или хотя бы привести примеры конечных максимальных сверхнасыщенных подмножеств A Zn . В частности, является ли сверхнасыщенное подмножество n {0} Zn из теоремы 17 максимальным?

Литература
[1] В.А. Артамонов и В.Н. Латышев, Линейная алге бра и выпуклая геометрия. М.: Факторил Пресс, 2004 [2] J.B. Carrel and A. Kurth, Normality of torus orbit closures in G=P . J. Algebra 233 (2000), 122-134 [3] C. Chindris, Orbit semigroups and representation type of quivers. Preprint arXiv:0708.3413 [4] W. Fulton, Intorduction to Toric Varieties. Annals of Math. Studies 131, Princeton University Press, Princeton, New Jersey, 1993 [5] J. Morand, Closures of torus orbits in adjoint representations of semisimple groups. C. R. Acad. Sci. Paris, S I Math. 328:3 (1999), 197{202 er. [6] B. Sturmfels, Gr obner Bases and Convex Polytopes. Universiy Lecture Series 8, AMS, Providence RI, 1996 [7] B. Sturmfels, Equations de ning toric varieties. Proc. Sympos. Pure Math. 62, Part 2, AMS, Providence RI (1997), 437{449

кафедра высшей алгебры МГУ им. М.В. Ломоносова E-mail address : arjantse@mccme.ru