Gordans lemma

Gordans lemma är ett lemma i konvex geometri och algebraisk geometri . Det kan sägas på flera sätt.

• Låt $A$ vara en matris av heltal. Låt $M$ vara mängden icke-negativa heltalslösningar av $A\cdot x=0$ . Sedan finns det en ändlig delmängd av vektorer i $M$ , så att varje element i $M$ är en linjär kombination av dessa vektorer med icke-negativa heltalskoefficienter.
• Halvgruppen av integralpunkter i en rationell konvex polyedrisk kon genereras ändligt .
• En affin torisk varietet är en algebraisk variant (detta följer av det faktum att det primära spektrumet för halvgruppsalgebra i en sådan halvgrupp, per definition, är en affin torisk sort ).

Lemmat är uppkallat efter matematikern Paul Gordan (1837–1912). Vissa författare har felstavat det som "Gordons lemma".

Bevis

Det finns topologiska och algebraiska bevis.

Topologiska bevis

Låt $\sigma$ vara den dubbla konen för den givna rationella polyedriska konen. Låt $\displaystyle u_{1},\dots ,u_{r}}$${\displaystyle \sigma =\{x\mid \langle u_{i},x\rangle \geq 0,1\leq i\leq r\}.} Sedan u i {\displaystyle u_$ vara integralvektorer så att { $}$ s generera den dubbla konen $\sigma ^{\vee }$ ; Om vi ​​skriver C för konen som genereras av $u_{i}$ s, har vi: ${\displaystyle \sigma \subset C^{\vee }} ,$ som måste vara likheten. Nu, om x är i semigruppen

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

då kan det skrivas som

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

där $n_{i}$ är icke-negativa heltal och $0\leq r_{i}\leq 1$ . Men eftersom x och den första summan på höger sida är integral, är den andra summan en gitterpunkt i ett avgränsat område, och det finns alltså bara ändligt många möjligheter för den andra summan (det topologiska skälet). Därför genereras ${\displaystyle S_{\sigma }} ändligt.$

Algebraiskt bevis

Beviset är baserat på ett faktum att en semigrupp S genereras ändligt om och endast om dess semigruppalgebra $\mathbb {C} [S]$ är en ändligt genererad algebra över $\mathbb { C}$ . För att bevisa Gordans lemma, genom induktion (jfr beviset ovan), räcker det att bevisa följande påstående: för varje enhetlig undersemigrupp S av $\mathbb {Z} ^{d}$ ,

Om S genereras ändligt, då $S^{+}=S\cap \{x\mid \langle x,v\rangle \geq 0\ }$ , v en integralvektor, genereras ändligt.

Sätt $A=\mathbb {C} [S]$ , som har en bas $\chi ^{a},\,a\in S$ . Den har $\mathbb {Z}$ -gradering given av

$A_{n}=\operatörsnamn {span} \{\chi ^{a}\mid a\in S,\ langle a,v\rangle =n\}$ .

Enligt antagandet genereras A ändligt och är således Noetherian. Det följer av det algebraiska lemmat nedan att $\mathbb {C} [S^{+}]=\oplus _{0}^{\infty }A_{n}$ är en ändligt genererad algebra över $A_{0}$ . Nu är halvgruppen $S_{0}=S\cap \{x\mid \langle x,v\rangle =0\}$ bilden av S under en linjär projektion, alltså ändligt genererad och så $A_{0}=\mathbb {C} [S_{0}]$ genereras ändligt. Därför genereras ${\displaystyle S^{+}} ändligt då.$

Lemma : Låt A vara en $\mathbb {Z}$ -graderad ring. Om A är en Noetherian ring, så är $A^{+}=\oplus _{0}^{\infty }A_{n}$ en ändligt genererad $A_{ 0}$ -algebra.

Bevis: Låt mig vara idealet för A som genereras av alla homogena element i A med positiv grad. Eftersom A är Noetherian, genereras I faktiskt av ändligt många ${\displaystyle f_{i}'s} ,$ homogena av positiv grad. Om f är homogen av positiv grad, så kan vi skriva ${\textstyle f=\sum _{i}g_{i}f_{i}}$ med $g_{i}$ homogen. Om f har tillräckligt stor grad, så har varje $g_{i}$ grad positiv och strikt mindre än den för f Dessutom är varje gradbit $A_{n}$ en ändligt genererad $A_{0}$ -modul. (Bevis: Låt $N_{i}$ vara en ökande kedja av ändligt genererade submoduler av $A_{n}$ med union $A_{n}$ . Sedan kedjan av idealen $N_{i}A$ stabiliseras i ändliga steg, så även kedjan $N_{i}=N_{i}A\cap A_{ n}.$ ) Sålunda, genom induktion på grad, ser vi $A^{+}$ är en ändligt genererad $A_{0}$ -algebra.

Ansökningar

En multi- hypergraf över en viss uppsättning $V$ är en multiset av delmängder av $V$ (det kallas "multi-hypergraph" eftersom varje hyperedge kan förekomma mer än en gång). En multi-hypergraf kallas regelbunden om alla hörn har samma grad . Det kallas nedbrytbart om det har en korrekt icke-tom delmängd som också är regelbunden. För vilket heltal n som helst , låt $D(n)$ vara den maximala graden av en oupplöslig multihypergraf på n hörn. Gordans lemma antyder att $D(n)$ är ändlig. Bevis : för varje delmängd S av hörn, definiera en variabel x _S (ett icke-negativt heltal). Definiera en annan variabel d (ett icke-negativt heltal). Betrakta följande uppsättning av n ekvationer (en ekvation per vertex):

$$\sum _{S\ni v}x_{S}-d=0{\text{ för alla }}v\in V$$

Varje lösning ( x , d ) betecknar en vanlig multihypergraf på $V$ , där x definierar hyperkanterna och d är graden. Enligt Gordans lemma genereras uppsättningen lösningar av en ändlig uppsättning lösningar, dvs det finns en finit uppsättning $M$ av multihypergrafer, så att varje vanlig multihypergraf är en linjär kombination av vissa element av $M$ . Varje icke-nedbrytbar multihypergraf måste vara i $M$ (eftersom den per definition inte kan genereras av andra multihypergrafer). Följaktligen är uppsättningen av icke-nedbrytbara multihypergrafer ändlig.

Se även

• Birkhoff-algoritmen är en algoritm som, givet en bistokastisk matris (en matris som löser en viss uppsättning ekvationer), hittar en nedbrytning av den till integralmatriser. Det är relaterat till Gordans lemma genom att det visar att mängden av dessa matriser genereras av en ändlig uppsättning integralmatriser.

Se även

• Dicksons lemma