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

Шаблон:Не путать Лемма Гордана — лемма из области выпуклой геометрии и алгебраической геометрии. У неё есть несколько равносильных формулировок:

• Для выпуклого рационального полиэдрального конуса полугруппа (моноид) точек с целыми координатами, лежащих внутри него, конечно порождена.
• Пусть $A$ — целочисленная матрица. Пусть $M$ — множество неотрицательных целочисленных решений системы $A\cdot x=0$. Тогда существует конечное подмножество $N\subset M$ такое, что каждый элемент $M$ представляется как линейная комбинация векторов из $N$ с целыми неотрицательными коэффициентами.
• Аффинное торическое многообразие является алгебраическим многообразием (см. далее).

Лемма названа в честь математика П. А. Гордана (1837—1912).

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

Геометрическое доказательство

Пример конуса в двумерном пространстве, порождённого векторами $(1,0)$ и $(1,1)$. Эти же векторы порождают моноид целых точек в конусе.

Пример конуса в двумерном пространстве, порождённого векторами $(1,0)$ и $(1,2)$. Вектор $(1,1)$ не выражается, как целочисленная комбинация этих векторов, но конечный набор $(1,0),(1,1),(1,2)$ порождает моноид целых точек в конусе.

Пусть дан выпуклый рациональный полиэдральный конус ${\sigma }^{\vee }$, порождаемый векторами $u_1,\dots ,u_r$ как конус. Пусть $S_{\sigma }$ — полугруппа целых точек в данном конусе, то есть

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

где $d$ — размерность пространства, в котором лежит конус $S_{\sigma }$. Тогда произвольную точку $x\in S_{\sigma }$ можно представить в виде

$x=\sum _i{n}_i{u}_i+\sum _i{r}_i{u}_i,$

где неотрицательные коэффициенты при $u_i$ разложены в сумму неотрицательного целого $n_i$ и дробной части $0⩽r_i<1$. Но так как $x$ и первая сумма целочисленны, вторая сумма тоже обязана быть вектором целочисленной решётки. При этом вторая сумма находится в ограниченной области, зависящей только от векторов $u_i$, но не от вектора $x$, поэтому для неё есть лишь конечное число возможностей. Таким образом, $S_{\sigma }$ конечно порожденаШаблон:Sfn.

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

Доказательство основано на том, что полугруппа $S$ конечно порождена тогда и только тогда, когда её Шаблон:Iw $ℂ[S]$ является конечно порождённой алгеброй над $ℂ$.

Докажем сперва вспомогательную лемму о градуированных алгебрах.

Лемма: Пусть $A$ — нётерово $\mathbb{Z}$-градуированное кольцо. Тогда $A^{+}=\underset{0}{\overset{\mathrm{\infty }}{⨁}}{A}_n$ — конечно-порождённая алгебра над $A_0$.

Доказательство леммы: пусть $I=\underset{i=1}{\overset{\mathrm{\infty }}{⨁}}{A}_i$ — идеал в $A$, порождённый всеми однородными элементами положительной степени. В силу нётеровости $A$ идеал $I$ порождён конечным числом однородных элементов положительной степени $f_i$. Пусть максимальная из степеней элементов $f_i$ равна $d$. Если $f$ — однородный элемент положительной степени, которая больше степеней всех $f_i$, то он представляется в виде $f=\sum _i{g}_i{f}_i$. Можно от каждого $g_i$ рассмотреть только однородную компоненту степени $\mathrm{deg}f-\mathrm{deg}{f}_i$, получив равенство $f=\sum _i{\bar{g}}_i{f}_i$, где ${\bar{g}}_i$ — однородные элементы положительной степени, причём эта степень будет строго меньше $\mathrm{deg}f$. Таким образом, применив индукцию по степени $f$, легко видеть, что $A^{+}$ порождается $\underset{i=0}{\overset{d}{⨁}}{A}_d$ как Шаблон:Nobr. Осталось показать, что $\underset{i=0}{\overset{d}{⨁}}{A}_d$ конечно порождена как $A_0$-алгебра, для чего достаточно показать, что каждый $A_i$ — конечно-порождённый Шаблон:Nobr. Действительно, пусть дана возрастающая цепочка вложенных конечно-порождённых подмодулей $N_j$ в $A_i$, объединение которой равно всему $A_i$. Можно рассмотреть цепочку идеалов $N_{j}A$. По нётеровости $A$ она стабилизируется на некотором шаге, значит стабилизируется и $N_j=N_{j}A\cap A_i$.

Теперь докажем, что для любого подмоноида $S\subset {\mathbb{Z}}^d$ выполнено следующее утверждение:

Если $S$ конечно порождён (как моноид), то и для произвольного целочисленного вектора $v$, лежащего в двойственной решётке к решётке, в которой лежит моноид, подмоноид $S^{+}=S\cap \{x\mid ⟨x,v⟩⩾0\}$ также конечно порождён.

Действительно, рассмотрим алгебру $A=ℂ[S]$, пусть её базис есть ${\chi }^a,a\in S$. На ней можно ввести $\mathbb{Z}$-градуировку:

$A_n=\mathrm{span}\{{\chi }^a\mid a\in S,⟨a,v⟩=n\}$.

По предположению $A$ конечно порождена, а значит нётерова. Тогда из доказанной леммы следует, что $ℂ[S^{+}]=\underset{0}{\overset{\mathrm{\infty }}{⨁}}{A}_n$ — конечно порождённая алгебра над $A_0$. Полугруппа $S_0=S\cap \{x\mid ⟨x,v⟩=0\}$ лежит в подпространстве меньшей размерности, поэтому можно считать при помощи индукции по размерности, что она тоже конечно порождена, а значит и алгебра $A_0=ℂ[S_0]$ конечно порождена. Таким образом, $S^{+}$ конечно порождён.

Наконец, из доказанного утверждения следует лемма Гордана. Действительно, можно рассмотреть в качестве $S$ всю целочисленную решётку и применять лемму к каждой гиперплоскости, задающей грань максимальной размерности полиэдрального конуса, пока не останется моноид целочисленных точек внутри конуса.

Применения

Аффинные торические многообразия

В стандартном определении аффинного торического многообразия по решётке $M$ и выпуклому рациональному полиэдральному конусу ${\sigma }^{\vee }$ в пространстве, соответствующем решётке, строится полугруппа ${\sigma }^{\vee }\cap M$, по ней алгебра $ℂ[{\sigma }^{\vee }\cap M]$ и рассматривается её спектр. Из леммы Гордана следует корректность этого определения: полученная алгебра конечно порождена, то есть действительно задаёт аффинное многообразие как свой спектрШаблон:Sfn.

Максимальная степень неразложимого мультигиперграфа

Мультигиперграф с множеством вершин $V$ — это мультимножество подмножеств $V$. Мультигиперграф называется регулярным, если у всех вершин одинаковая степень. Мультигиперграф $(V,E)$ называется разложимым, если у него можно выбрать собственное непустое подмультимножество рёбер $F\subset E$ так, что мультигиперграф $(V,F)$ тоже регулярен для некоторой степени $k<n$. Для натурального $n$ обозначим через $D(n)$ максимальную степень неразложимого мультигиперграфа на $n$ вершинах. Из леммы Гордана следует, что $D(n)$ конечно.

Доказательство: для каждого подмножества вершин $S$ определим переменную $x_S$ (принимающую неотрицательные целые значения). Добавим также ещё одну переменную $d$ (тоже принимающую неотрицательные целые значения). Рассмотрим набор из $n$ уравнений (по одному уравнению на каждую вершину):

$\mathrm{\forall }v\in V:\sum _{S\ni v}{x}_S-d=0$

Каждое решение $(𝐱,d)$ задаёт регулярный мультигиперграф с множеством вершин $V$: $𝐱$ задаёт кратности соответствующих гиперрёбер, а $d$ задаёт степень вершин. По лемме Гордана множество решений порождается конечным набором решений, то есть существует конечный набор $M$ мультигиперграфов таких, что каждый регулярный мультигиперграф — это линейная комбинация некоторых элементов $M$. Все неразложимые мультигиперграфы должны лежать в $M$, то есть их множество конечно.

Литература

• Шаблон:Книга
• Шаблон:Книга