Лемма Гордана

Лемма Гордана — лемма в выпуклой геометрии и алгебраической геометрии . Она может быть сформулирована несколькими способами.

• Пусть будет матрицей целых чисел. Пусть будет множеством неотрицательных целочисленных решений . Тогда существует конечное подмножество векторов в , такое, что каждый элемент из является линейной комбинацией этих векторов с неотрицательными целочисленными коэффициентами. ^[1] ${\displaystyle A}$ ${\displaystyle M}$ ${\displaystyle A\cdot x=0}$ ${\displaystyle M}$ ${\displaystyle M}$
• Полугруппа целых точек в рациональном выпуклом многогранном конусе конечно порождена. ^[2 ]
• Аффинное торическое многообразие является алгебраическим многообразием (это следует из того факта, что простой спектр полугрупповой алгебры такой полугруппы по определению является аффинным торическим многообразием ).

Лемма названа в честь математика Пола Гордана (1837–1912). Некоторые авторы неправильно пишут ее как «лемма Гордона».

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

Существуют топологические и алгебраические доказательства.

Топологическое доказательство

Пусть будет двойственным конусом данного рационального многогранного конуса. Пусть будут целыми векторами, так что Тогда 's порождают двойственный конус ; действительно, записывая C для конуса, порожденного 's, мы имеем: , что должно быть равенством. Теперь, если x находится в полугруппе ${\displaystyle \sigma }$ ${\displaystyle u_{1},\dots ,u_{r}}$ ${\displaystyle \sigma =\{x\mid \langle u_{i},x\rangle \geq 0,1\leq i\leq r\}.}$ ${\displaystyle u_{i}}$ ${\displaystyle \sigma ^{\vee }}$ ${\displaystyle u_{i}}$ ${\displaystyle \sigma \subset C^{\vee }}$

${\displaystyle S_{\sigma }=\sigma ^{\vee }\cap \mathbb {Z} ^{d},}$

то это можно записать как

${\displaystyle x=\sum _{i}n_{i}u_{i}+\sum _{i}r_{i}u_{i},}$

где — неотрицательные целые числа и . Но поскольку x и первая сумма в правой части являются целыми числами, вторая сумма является точкой решетки в ограниченной области, и поэтому существует только конечное число возможностей для второй суммы (топологическая причина). Следовательно, конечно порождено. ${\displaystyle n_{i}}$ ${\displaystyle 0\leq r_{i}\leq 1}$ ${\displaystyle S_{\sigma }}$

Алгебраическое доказательство

Доказательство ^[3] основано на том факте, что полугруппа S конечно порождена тогда и только тогда, когда ее полугрупповая алгебра является конечно порожденной алгеброй над . Для доказательства леммы Гордана по индукции (ср. доказательство выше) достаточно доказать следующее утверждение: для любой унитальной подполугруппы S из , ${\displaystyle \mathbb {C} [S]}$ ${\displaystyle \mathbb {C} }$ ${\displaystyle \mathbb {Z} ^{d}}$

Если S конечно порождено, то , v — целочисленный вектор, конечно порождено. ${\displaystyle S^{+}=S\cap \{x\mid \langle x,v\rangle \geq 0\}}$

Положим , который имеет базу . Он имеет -градуировку, заданную ${\displaystyle A=\mathbb {C} [S]}$ ${\displaystyle \chi ^{a},\,a\in S}$ ${\displaystyle \mathbb {Z} }$

${\displaystyle A_{n}=\operatorname {span} \{\chi ^{a}\mid a\in S,\langle a,v\rangle =n\}}$.

По предположению, A конечно порождена и, таким образом, является нётеровой. Из алгебраической леммы ниже следует, что является конечно порожденной алгеброй над . Теперь полугруппа является образом S при линейной проекции, таким образом, конечно порождена и, таким образом , конечно порождена. Следовательно, является конечно порожденной тогда. ${\displaystyle \mathbb {C} [S^{+}]=\oplus _{0}^{\infty }A_{n}}$ ${\displaystyle A_{0}}$ ${\displaystyle S_{0}=S\cap \{x\mid \langle x,v\rangle =0\}}$ ${\displaystyle A_{0}=\mathbb {C} [S_{0}]}$ ${\displaystyle S^{+}}$

Лемма : Пусть A — -градуированное кольцо. Если A — нётерово кольцо, то — конечно порождённая -алгебра. ${\displaystyle \mathbb {Z} }$ ${\displaystyle A^{+}=\oplus _{0}^{\infty }A_{n}}$ ${\displaystyle A_{0}}$

Доказательство: Пусть I — идеал A, порождённый всеми однородными элементами A положительной степени. Так как A — нётерово, I на самом деле порождается конечным числом , однородных положительной степени. Если f однороден положительной степени, то мы можем записать с однородным. Если f имеет достаточно большую степень, то каждый имеет степень положительную и строго меньшую, чем у f . Кроме того, каждая часть степени является конечно порождённым -модулем. (Доказательство: Пусть — возрастающая цепочка конечно порождённых подмодулей с объединением . Тогда цепочка идеалов стабилизируется за конечные шаги; то же самое делает и цепочка ) Таким образом, индукцией по степени мы видим, что — конечно порождённая -алгебра. ${\displaystyle f_{i}'s}$ ${\textstyle f=\sum _{i}g_{i}f_{i}}$ ${\displaystyle g_{i}}$ ${\displaystyle g_{i}}$ ${\displaystyle A_{n}}$ ${\displaystyle A_{0}}$ ${\displaystyle N_{i}}$ ${\displaystyle A_{n}}$ ${\displaystyle A_{n}}$ ${\displaystyle N_{i}A}$ ${\displaystyle N_{i}=N_{i}A\cap A_{n}.}$ ${\displaystyle A^{+}}$ ${\displaystyle A_{0}}$

Приложения

Мультигиперграф над некоторым множеством — это мультимножество подмножеств (оно называется «мультигиперграфом», поскольку каждое гиперребро может встречаться более одного раза). Мультигиперграф называется регулярным , если все вершины имеют одинаковую степень . Он называется разложимым, если у него есть собственное непустое подмножество, которое также является регулярным. Для любого целого числа n пусть — максимальная степень неразложимого мультигиперграфа на n вершинах. Из леммы Гордана следует, что является конечным. ^[1] Доказательство : для каждого подмножества S вершин определим переменную x _S (неотрицательное целое число). Определим другую переменную d (неотрицательное целое число). Рассмотрим следующий набор из n уравнений (одно уравнение на вершину): Каждое решение ( x , d ) обозначает регулярный мультигиперграф на , где x определяет гиперребра, а d — степень. По лемме Гордана множество решений порождается конечным множеством решений, т. е. существует конечное множество мультигиперграфов, такое, что каждый регулярный мультигиперграф является линейной комбинацией некоторых элементов из . Каждый неразложимый мультигиперграф должен быть в (так как по определению он не может быть порожден другим мультигиперграфом). Следовательно, множество неразложимых мультигиперграфов конечно. ${\displaystyle V}$ ${\displaystyle V}$ ${\displaystyle D(n)}$ ${\displaystyle D(n)}$ $${\displaystyle \sum _{S\ni v}x_{S}-d=0{\text{ for all }}v\in V}$$ ${\displaystyle V}$ ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle M}$

Смотрите также

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

Ссылки

1. Alon, N; Berman, KA (1986-09-01). «Регулярные гиперграфы, лемма Гордона, лемма Стейница и теория инвариантов». Журнал комбинаторной теории, Серия A. 43 ( 1): 91–97. doi : 10.1016/0097-3165(86)90026-9 . ISSN  0097-3165.
2. Дэвид А. Кокс, Лекции по торическим многообразиям. Лекция 1. Предложение 1.11.
3. Брунс, Винфрид; Губеладзе, Джозеф (2009). Многогранники, кольца и K-теория . Springer Monographs in Mathematics. Springer. doi :10.1007/b105283. ISBN  978-0-387-76355-2., Лемма 4.12.

Смотрите также

• Лемма Диксона