Inzidenzalgebra - Incidence algebra

In der Ordnungstheorie , einem Gebiet der Mathematik , ist eine Inzidenzalgebra eine assoziative Algebra , die für jede lokal endliche teilgeordnete Menge und jeden kommutativen Ring mit Eins definiert ist. Subalgebren, die als Algebren mit reduzierter Inzidenz bezeichnet werden, geben eine natürliche Konstruktion verschiedener Arten von erzeugenden Funktionen, die in der Kombinatorik und der Zahlentheorie verwendet werden.

Definition

Ein lokal endliches Poset ist eines, in dem jedes abgeschlossene Intervall

[ a, b ] = { x  : a ≤ x ≤ b }

ist endlich .

Die Glieder der Inzidenzalgebra sind die Funktionen f , die jedem nichtleeren Intervall [ a, b ] einen Skalar f ( a , b ) zuordnen , der dem Ring der Skalare entnommen ist , einem kommutativen Ring mit Eins. Auf dieser zugrunde liegenden Menge definiert man punktweise Addition und Skalarmultiplikation, und "Multiplikation" in der Inzidenzalgebra ist eine Faltung definiert durch

${\displaystyle (f*g)(a,b)=\sum_{a\leq x\leq b}f(a,x)g(x,b).}$

Eine Inzidenzalgebra ist genau dann endlichdimensional, wenn das zugrundeliegende Poset endlich ist.

Verwandte konzepte

Eine Inzidenzalgebra ist einer Gruppenalgebra analog ; tatsächlich sind sowohl die Gruppenalgebra als auch die Inzidenzalgebra Spezialfälle einer analog definierten Kategoriealgebra ; Gruppen und Posen sind spezielle Arten von Kategorien .

Obere Dreiecksmatrizen

Betrachten wir den Fall einer partiellen Ordnung ≤ über einer beliebigen n- elementigen Menge S . Wir aufzählen S als s ₁ , ..., s _n , und in einer solchen Art und Weise , dass die Aufzählung mit der Ordnung ≤ auf kompatibel ist S , das heißt, s _i ≤ s _j impliziert i ≤ j , was immer möglich ist.

Dann können die Funktionen f wie oben, von Intervallen bis zu Skalaren, als Matrizen A _{ij betrachtet werden} , wobei A _ij = f ( s _i , s _j ) wann immer i ≤ j ist , und A _ij = 0 andernfalls . Da wir S entsprechend der üblichen Ordnung auf den Indizes der Matrizen angeordnet haben, erscheinen sie als obere Dreiecksmatrizen mit einem vorgegebenen Nullmuster, das durch die unvergleichbaren Elemente in S unter ≤ bestimmt wird.

Die Inzidenzalgebra von ist dann isomorph zur Algebra der oberen Dreiecksmatrizen mit diesem vorgeschriebenen Nullmuster und beliebigen (einschließlich möglicherweise Null) Skalareinträgen überall sonst, wobei die Operationen gewöhnliche Matrixaddition, Skalierung und Multiplikation sind.

Sonderelemente

Das multiplikative Identitätselement der Inzidenzalgebra ist die Deltafunktion , definiert durch

${\displaystyle \delta (a,b)={\begin{cases}1&{\text{if }}a=b,\\0&{\text{if }}a\neq b.\end{cases}} }$

Die Zetafunktion einer Inzidenzalgebra ist die konstante Funktion ζ ( a , b ) = 1 für jedes nichtleere Intervall [ a, b ]. Die Multiplikation mit ζ ist analog zur Integration.

Man kann zeigen, dass ζ in der Inzidenzalgebra (bezüglich der oben definierten Faltung) invertierbar ist. (Im Allgemeinen ist ein Mitglied h der Inzidenzalgebra genau dann invertierbar, wenn h ( x , x ) für jedes x invertierbar ist .) Die multiplikative Inverse der Zeta-Funktion ist die Möbius-Funktion μ ( a, b ); jeder Wert von μ ( a, b ) ist ein ganzzahliges Vielfaches von 1 im Basisring.

Die Möbius-Funktion lässt sich auch induktiv durch folgende Beziehung definieren:

${\displaystyle \mu (x,y)={\begin{cases}{}\qquad 1&{\text{if }}x=y\\[6pt]\displaystyle -\!\!\!\!\sum _{z\,:\,x\,\leq\,z\,<\,y}\mu (x,z)&{\text{für }}x<y\\{}\qquad 0&{\ text{sonst }}.\end{cases}}}$

Die Multiplikation mit μ ist analog zur Differentiation und wird als Möbius-Inversion bezeichnet .

Das Quadrat der Zeta-Funktion zählt die Anzahl der Elemente in einem Intervall:

Beispiele

Positive ganze Zahlen geordnet nach Teilbarkeit

Die Faltung für Intervalle zur Einfall Algebra assoziiert [1, n ] wird die Dirichlet Faltung , also die Möbius Funktion μ ( a, b ) = μ ( b / a ), wobei der zweiten " μ " die klassische Möbius - Funktion eingeführt in die Zahlentheorie im 19.

Endliche Teilmengen einer Menge E , geordnet nach Inklusion

Die Möbius-Funktion ist

$${\displaystyle \mu(S,T)=(-1)^{\left|T\setminus S\right|}}$$

wenn S und T endliche Teilmengen von E mit S ⊆ T sind und die Möbius-Inversion als Inklusions-Ausschluss-Prinzip bezeichnet wird .

Geometrisch ist dies ein Hyperwürfel :${\displaystyle 2^{E}=\{0,1\}^{E}.}$

Natürliche Zahlen in ihrer üblichen Reihenfolge

Die Möbius-Funktion ist

$${\displaystyle \mu (x,y)={\begin{cases}1&{\text{if }}y=x,\\-1&{\text{if}}y=x+1,\\0&{ \text{if }}y>x+1,\end{cases}}}$$

und die Möbius-Inversion wird der (Rückwärts-) Differenzoperator genannt .

Geometrisch entspricht dies dem diskreten Zahlenstrahl .

Die Faltung von Funktionen in der Inzidenzalgebra entspricht der Multiplikation formaler Potenzreihen : siehe die Diskussion über Algebren mit reduzierter Inzidenz weiter unten. Die Möbius-Funktion entspricht der Folge (1, −1, 0, 0, 0, ... ) der Koeffizienten der formalen Potenzreihe 1 − t und die Zeta-Funktion der Koeffizientenfolge (1, 1, 1 , 1, ...) der formalen Potenzreihe , die invers ist. Die Deltafunktion in dieser Inzidenzalgebra entspricht ebenfalls der formalen Potenzreihe 1.${\displaystyle (1-t)^{-1}=1+t+t^{2}+t^{3}+\cdots}$

Endliche Teilmengen einer Mehrfachmenge E , geordnet nach Inklusion

Die obigen drei Beispiele können vereinheitlicht und verallgemeinert werden, indem man eine Mehrfachmenge E und endliche Untermengen S und T von E betrachtet . Die Möbius-Funktion ist

$${\displaystyle \mu(S,T)={\begin{cases}0&{\text{if}}T\setminus S{\text{ ist eine echte Multimenge (hat sich wiederholende Elemente)}}\\(-1) ^{\left|T\setminus S\right|}&{\text{if }}T\setminus S{\text{ ist eine Menge (hat keine wiederholten Elemente)}}.\end{cases}}}$$

Dies verallgemeinert die nach Teilbarkeit geordneten positiven ganzen Zahlen durch eine positive ganze Zahl, die ihrer Vielfachmenge von Primteilern mit Vielfachheit entspricht, z. B. entspricht 12 der Vielfachmenge ${\displaystyle \{2,2,3\}.}$

Dies verallgemeinert die natürlichen Zahlen in ihrer üblichen Reihenfolge durch eine natürliche Zahl, die einer Vielfachmenge eines zugrunde liegenden Elements und einer Kardinalität gleich dieser Zahl entspricht, zB 3 entspricht der Vielfachmenge ${\displaystyle \{1,1,1\}.}$

Untergruppen einer endlichen p -Gruppe G , geordnet nach Inklusion

Die Möbius-Funktion ist

$${\displaystyle \mu_{G}(H_{1},H_{2})=(-1)^{k}p^{\binom {k}{2}}}$$

wenn ist eine normale Untergruppe von und, andernfalls ist sie 0. Dies ist ein Satz von Weisner (1935).${\displaystyle H_{1}}$${\displaystyle H_{2}}$${\displaystyle H_{2}/H_{1}\cong (\mathbb{Z} /p\mathbb{Z})^{k}}$

Partitionen einer Menge

Ordne die Menge aller Partitionen einer endlichen Menge teilweise, indem du σ ≤ τ sagst, falls σ eine feinere Partition als τ ist. Insbesondere lassen τ haben t - Blöcke , die jeweils aufgeteilt in s ₁ , ..., s _t feinere Blöcke von σ, die insgesamt hat s = s ₁ + ··· + s _t Blöcke. Dann lautet die Möbius-Funktion:

$${\displaystyle \mu(\sigma,\tau)=(-1)^{st}(s_{1}{-}1)!\cdots (s_{t}{-}1)!}$$

Euler-Charakteristik

Ein Poset ist beschränkt, wenn es kleinste und größte Elemente hat, die wir 0 bzw. 1 nennen (nicht zu verwechseln mit 0 und 1 des Skalarrings). Die Euler-Charakteristik eines beschränkten endlichen Poset ist μ (0,1). Der Grund für diese Terminologie ist folgender: Wenn P eine 0 und 1 hat, dann ist μ (0,1) die reduzierte Euler-Charakteristik des simplizialen Komplexes, dessen Seiten Ketten in P  \ {0, 1} sind. Dies kann mit dem Satz von Philip Hall gezeigt werden, der den Wert von μ (0,1) auf die Anzahl der Ketten der Länge i bezieht .

Algebren mit reduzierter Inzidenz

Die Algebra mit reduzierter Inzidenz besteht aus Funktionen, die zwei beliebigen Intervallen, die in einem angemessenen Sinne äquivalent sind, denselben Wert zuweisen, was normalerweise als Posets isomorph bedeutet. Dies ist eine Subalgebra der Inzidenzalgebra und enthält eindeutig das Identitätselement und die Zetafunktion der Inzidenzalgebra. Jedes Element der Algebra mit reduzierter Inzidenz, das in der Algebra mit größerer Inzidenz invertierbar ist, hat seine Umkehrung in der Algebra mit reduzierter Inzidenz. Somit ist die Möbius-Funktion auch in der Algebra mit reduzierter Inzidenz enthalten.

Algebren mit reduzierter Inzidenz wurden von Doubillet, Rota und Stanley eingeführt, um eine natürliche Konstruktion verschiedener Ringe von erzeugenden Funktionen zu erhalten .

Natürliche Zahlen und gewöhnliche erzeugende Funktionen

Für den Poset besteht die Algebra mit reduzierter Inzidenz aus Funktionen, die unter Translation invariant sind, für alle , um den gleichen Wert auf isomorphen Intervallen [a+k, b+k] und [a,b] zu haben. Lassen t bezeichnet die Funktion mit t (a, a + 1) = 1 und t (a, b) = 0 sonst, einer Art invariant Deltafunktion auf Isomorphieklassen Intervalle. Seine Potenzen in der Inzidenzalgebra sind die anderen invarianten Deltafunktionen t ⁿ (a, a+n) = 1 und sonst t ⁿ (x,y) = 0. Diese bilden eine Basis für die Algebra mit reduzierter Inzidenz, und wir können jede invariante Funktion als schreiben . Diese Notation verdeutlicht den Isomorphismus zwischen der Algebra mit reduzierter Inzidenz und dem Ring der formalen Potenzreihen über den Skalaren R, auch bekannt als Ring der gewöhnlichen erzeugenden Funktionen . Wir können die Zeta-Funktion als Kehrwert der Möbius-Funktion schreiben${\displaystyle (\mathbb{N},\leq),}$${\displaystyle f(a,b)}$${\displaystyle f(a+k,b+k)=f(a,b)}$${\displaystyle k\geq 0,}$${\displaystyle \textstyle f=\sum _{n\geq 0}f(0,n)t^{n}}$${\displaystyle R[[t]]}$${\displaystyle \zeta=1+t+t^{2}+\cdots ={\tfrac{1}{1-t}},}$${\displaystyle \mu=1-t.}$

Teilmenge Poset und Exponential erzeugende Funktionen

Für das Boolesche Poset endlicher Teilmengen, geordnet nach Inklusion , besteht die Algebra mit reduzierter Inzidenz aus invarianten Funktionen, die so definiert sind, dass sie den gleichen Wert auf isomorphen Intervallen [S,T] und [S',T'] mit |T\S| haben = |T'\S'|. Sei wieder t die invariante Deltafunktion mit t (S,T) = 1 für |T\S| = 1 und t (S,T) = 0 sonst. Seine Befugnisse sind:${\displaystyle S\subset \{1,2,3,\ldots\}}$${\displaystyle S\Teilmenge T}$${\displaystyle f(S,T),}$

wobei die Summe über alle Ketten ist und die einzigen Nicht-Null-Terme für gesättigte Ketten mit auftreten, da diese Permutationen von n entsprechen, erhalten wir den eindeutigen Nicht-Null-Wert n!. Somit sind die invarianten Deltafunktionen die geteilten Potenzen und wir können jede invariante Funktion schreiben als wobei [n] = {1, . . . , n}. Dies ergibt einen natürlichen Isomorphismus zwischen der Algebra mit reduzierter Inzidenz und dem Ring exponentiell erzeugender Funktionen . Die Zeta-Funktion ist mit der Möbius-Funktion:${\displaystyle S=T_{0}\subset T_{1}\subset \cdots \subset T_{n}=T,}$${\displaystyle |T_{i}{\setminus}T_{i-1}|=1;}$${\displaystyle {\tfrac {t^{n}}{n!}},}$${\displaystyle \textstyle f=\sum _{n\geq 0}f(\emptyset ,[n]){\frac {t^{n}}{n!}},}$${\displaystyle \textstyle \zeta =\sum _{n\geq 0}{\frac {t^{n}}{n!}}=\exp(t),}$

$${\displaystyle \textstyle \mu\ =\ {\frac {1}{\zeta}}\ =\ \exp(-t)\ =\ \sum _{n\geq 0}(-1)^{n} {\frac {t^{n}}{n!}}.}$$

Tatsächlich beweist diese Berechnung mit formalen Potenzreihen, dass viele kombinatorische Zählsequenzen, die Teilmengen oder markierte Objekte beinhalten, im Hinblick auf die Algebra mit reduzierter Inzidenz interpretiert und mit exponentiellen Erzeugungsfunktionen berechnet werden können. ${\displaystyle \mu(S,T)=(-1)^{|T{\setminus}S|}.}$

Divisor Poset und Dirichlet-Serie

Betrachten Sie das Poset D von positiven ganzen Zahlen, geordnet nach der Teilbarkeit , bezeichnet Die Algebra mit reduzierter Inzidenz besteht aus Funktionen, die unter Multiplikation invariant sind, für alle (Diese Multiplikationsäquivalenz von Intervallen ist eine viel stärkere Beziehung als der Poset-Isomorphismus: für Primzahl p sind die Zweielementintervalle 1,p] sind alle inäquivalent.) Für eine invariante Funktion hängt

f (a,b) nur von b/a ab, also besteht eine natürliche Basis aus invarianten Deltafunktionen definiert durch wenn b/a = n und 0 sonst: jede Invariante Funktion kann geschrieben werden${\displaystyle a|b.}$${\displaystyle f(a,b)}$${\displaystyle f(ka,kb)=f(a,b)}$${\displaystyle k\geq 1.}$${\displaystyle \delta_{n}}$${\displaystyle \delta_{n}(a,b)=1}$${\displaystyle \textstyle f\ =\ \sum _{n\geq 0}f(1,n)\,\delta_{n}.}$

Das Produkt zweier invarianten Deltafunktionen ist:

${\displaystyle (\delta_{n}\delta_{m})(a,b)\ =\ \sum_{a|c|b}\delta_{n}(a,c)\,\delta _{m}(c,b)=\delta_{nm}(a,b),}$

da der einzige von Null verschiedene Term von c = na und b = mc = nma stammt. Somit erhalten wir einen Isomorphismus von der Algebra mit reduzierter Inzidenz zum Ring der formalen Dirichlet-Reihe, indem wir an senden , so dass

f entspricht${\displaystyle \delta_{n}}$${\displaystyle n^{-s}\!,}$${\textstyle \sum _{n\geq 1}{\frac {f(1,n)}{n^{s}}}.}$

Die Inzidenzalgebra-Zetafunktion ζ _D (a,b) = 1 entspricht der klassischen Riemannschen Zetafunktion mit Kehrwert wobei die klassische

Möbius-Funktion der Zahlentheorie ist. Viele andere arithmetische Funktionen entstehen natürlicherweise innerhalb der Algebra mit reduzierter Inzidenz und entsprechend in Bezug auf die Dirichlet-Reihen. Zum Beispiel ist die Divisorfunktion das Quadrat der Zetafunktion, ein Sonderfall des obigen Ergebnisses, das die Anzahl der Elemente im Intervall [x,y] zählt; Äquivalent,${\displaystyle \zeta(s)=\textstyle\sum _{n\geq 1}{\frac {1}{n^{s}}},}$${\textstyle {\frac {1}{\zeta (s)}}=\sum _{n\geq 1}{\frac {\mu(n)}{n^{s}}},}$${\displaystyle \mu(n)=\mu_{D}(1,n)}$ ${\displaystyle \sigma_{0}(n)}$${\displaystyle \sigma_{0}(n)=\zeta^{2}\!(1,n),}$${\displaystyle \zeta^{2}\!(x,y)}$${\textstyle \zeta(s)^{2}=\sum _{n\geq 1}{\frac {\sigma_{0}(n)}{n^{s}}}.}$

Die Produktstruktur des Divisors Poset erleichtert die Berechnung seiner Möbius-Funktion. Einzigartige Faktorisierung in Primzahlen impliziert D sind isomorph zu einem unendlichen cartesianischen Produkt , mit dem Auftrag von koordinaten Vergleich gegeben: wo ist die

k - ^te Primzahl ist , entspricht seine Folge von Exponenten Nun ist die Möbius - Funktion von D ist das Produkt der Möbius - Funktionen für der oben berechnete Faktor Posets ergibt die klassische Formel: ${\displaystyle \mathbb{N}\times\mathbb{N}\times\cdots}$${\displaystyle n=p_{1}^{e_{1}}p_{2}^{e_{2}}\cdots}$${\displaystyle p_{k}}$${\displaystyle (e_{1},e_{2},\ldots).}$

${\displaystyle \mu(n)=\mu_{D}(1,n)=\prod_{k\geq 1}\mu_{\mathbb{N}}(0,e_{k})\, =\,\left\{{\begin{array}{cl}(-1)^{d}&{\text{ für }}n{\text{ quadratfrei mit }}d{\text{ Primfaktoren}} \\0&{\text{sonst.}}\end{array}}\right.}$

Die Produktstruktur erklärt auch das klassische Euler-Produkt für die Zetafunktion. Die Zetafunktion von D entspricht einem kartesischen Produkt von Zetafunktionen der Faktoren, die oben so berechnet wurde , dass die rechte Seite ein kartesisches Produkt ist. Wendet man den Isomorphismus an, der

t im k- ^ten Faktor an schickt , erhält man das übliche Euler-Produkt. ${\textstyle {\frac {1}{1-t}},}$${\textstyle \zeta_{D}\cong\prod_{k\geq 1}\!{\frac {1}{1-t}},}$${\displaystyle p_{k}^{-s}}$

Siehe auch

• Graphische Algebra
• Inzidenz-Koalgebra
• Pfadalgebra

Literatur

Inzidenzalgebren von lokal endlichen Posets wurden in einer Reihe von Arbeiten von Gian-Carlo Rota ab 1964 und von vielen späteren Kombinatorikern behandelt . Rotas Aufsatz aus dem Jahr 1964 lautete:

• Rota, Gian-Carlo (1964), "On the Foundations of Combinatorial Theory I: Theory of Möbius Functions", Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete , 2 (4): 340–368, doi : 10.1007/BF00531932 , S2CID  121334025
• N. Jacobson , Grundlegende Algebra . I, WH Freeman and Co., 1974. Siehe Abschnitt 8.6 für eine Behandlung von Mobius-Funktionen auf Posets

Weiterlesen

• Spiegel, Eugen; O'Donnell, Christopher J. (1997), Inzidenzalgebren , Reine und Angewandte Mathematik, 206 , Marcel Dekker, ISBN 0-8247-0036-8