Álgebra de incidencia

En la teoría del orden , un campo de las matemáticas , un álgebra de incidencia es un álgebra asociativa , definida para todo conjunto parcialmente ordenado localmente finito y anillo conmutativo con unidad. Las subálgebras llamadas álgebras de incidencia reducidas proporcionan una construcción natural de varios tipos de funciones generadoras utilizadas en combinatoria y teoría de números .

Definición

Un poset localmente finito es aquel en el que cada intervalo cerrado

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

es finito .

Los miembros del álgebra de incidencia son las funciones f que asignan a cada intervalo no vacío [ a, b ] un escalar f ( a , b ), que se toma del anillo de escalares , un anillo conmutativo con unidad. En este conjunto subyacente se define la suma y la multiplicación escalar punto por punto, y la "multiplicación" en el álgebra de incidencia es una convolución definida por

(f*g)(a,b)=\sum _{a~\leq ~x~\leq ~b}f(a,x)g(x,b).

Un álgebra de incidencia es de dimensión finita si y solo si el conjunto parcialmente ordenado subyacente es finito.

Conceptos relacionados

Un álgebra de incidencia es análoga a un álgebra de grupo ; de hecho, tanto el álgebra de grupo como el álgebra de incidencia son casos especiales de un álgebra de categorías , definidas de forma análoga; los grupos y los conjuntos parcialmente ordenados son tipos especiales de categorías .

Matrices triangulares superiores

Consideremos el caso de un orden parcial ≤ sobre cualquier conjunto $S$ $de n$ elementos . Enumeramos $S$ como $s$ $1$ $, \dots,$ $s$ $n$ , y de tal manera que la enumeración sea compatible con el orden ≤ en $S$ , es decir, $s$ $i$ $\leq$ $s$ $j$ implica $i$ $\leq$ $j$ , lo cual siempre es posible.

Entonces, las funciones $f$ como se describió anteriormente, desde intervalos hasta escalares, pueden pensarse como matrices $A ij$ , donde $A ij = f (s i, s j)$ siempre que $i \leq j$ , y $A ij = 0$ en caso contrario . Dado que organizamos $S$ de una manera consistente con el orden habitual en los índices de las matrices, aparecerán como matrices triangulares superiores con un patrón de ceros prescrito determinado por los elementos incomparables en $S$ bajo ≤.

El álgebra de incidencia de ≤ es entonces isomorfa al álgebra de matrices triangulares superiores con este patrón cero prescrito y entradas escalares arbitrarias (incluyendo posiblemente cero) en todas partes, siendo las operaciones suma , escalado y multiplicación de matrices ordinarias . ^{[ 1 ]}

Elementos especiales

El elemento identidad multiplicativo del álgebra de incidencia es la función delta , definida por

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

La función zeta de un álgebra de incidencia es la función constante ζ ( a , b ) = 1 para todo intervalo no vacío [ a, b ]. Multiplicar por ζ es análogo a la integración .

Se puede demostrar que ζ es invertible en el álgebra de incidencia (con respecto a la convolución definida anteriormente). (En general, un elemento h del álgebra de incidencia es invertible si y solo si h ( x , x ) es invertible para todo x .) El inverso multiplicativo de la función zeta es la función de Möbius μ ( a, b ); cada valor de μ ( a, b ) es un múltiplo entero de 1 en el anillo base.

La función de Möbius también puede definirse inductivamente mediante la siguiente relación:

\mu (x,y)={\begin{cases}{}\qquad 1&{\text{si }}x=y\\[6pt]\displaystyle -\!\!\!\!\sum _{z\,:\,x\,\leq \,z\,<\,y}\mu (x,z)&{\text{para }}x<y\\{}\qquad 0&{\text{en otro caso }}.\end{cases}}

Multiplicar por μ es análogo a la diferenciación y se denomina inversión de Möbius .

El cuadrado de la función zeta da el número de elementos en un intervalo: $\zeta ^{2}(x,y)=\sum _{z\in [x,y]}\zeta (x,z)\,\zeta (z,y)=\sum _{z\in [x,y]}1=\#[x,y].$

Ejemplos

Números enteros positivos ordenados por divisibilidad: La convolución asociada al álgebra de incidencia para intervalos [1, n ] se convierte en la convolución de Dirichlet , por lo tanto la función de Möbius es μ ( a, b ) = μ ( b/a ), donde la segunda " μ " es la función de Möbius clásica introducida en la teoría de números en el siglo XIX.
Subconjuntos finitos de algún conjunto E , ordenados por inclusión.: La función de Möbius es $\mu (S,T)=(-1)^{\left|T\smallsetminus S\right|}$; siempre que S y T sean subconjuntos finitos de E con S ⊆ T , la inversión de Möbius se denomina principio de inclusión-exclusión .; Geométricamente, esto es un hipercubo : $2^{E}=\{0,1\}^{E}.$
Números naturales con su orden habitual: La función de Möbius es $\mu (x,y)={\begin{cases}1&{\text{si }}y=x,\\-1&{\text{si }}y=x+1,\\0&{\text{si }}y>x+1,\end{cases}}$ y la inversión de Möbius se denomina operador de diferencia (hacia atrás) .; Geométricamente, esto corresponde a la recta numérica discreta .; La convolución de funciones en el álgebra de incidencia corresponde a la multiplicación de series de potencias formales : véase la discusión de álgebras de incidencia reducidas más adelante. La función de Möbius corresponde a la secuencia (1, −1, 0, 0, 0, ...) de coeficientes de la serie de potencias formal 1 − t , y la función zeta corresponde a la secuencia de coeficientes (1, 1, 1, 1, ...) de la serie de potencias formales $(1-t)^{-1}=1+t+t^{2}+t^{3}+\cdots$ , que es inversa. La función delta en esta álgebra de incidencia corresponde de manera similar a la serie de potencias formal 1.
Submulticonjuntos finitos de algún multiconjunto E , ordenados por inclusión.: Los tres ejemplos anteriores pueden unificarse y generalizarse considerando un multiconjunto E y submulticonjuntos finitos S y T de E. La función de Möbius es $\mu (S,T)={\begin{cases}0&{\text{si }}T\smallsetminus S{\text{ es un multiconjunto propio (tiene elementos repetidos)}}\\(-1)^{\left|T\smallsetminus S\right|}&{\text{si }}T\smallsetminus S{\text{ es un conjunto (no tiene elementos repetidos)}}.\end{cases}}$; Esto generaliza los enteros positivos ordenados por divisibilidad por un entero positivo correspondiente a su multiconjunto de factores primos con multiplicidad, por ejemplo, 12 corresponde al multiconjunto $\{2,2,3\}.$; Esto generaliza los números naturales con su orden usual por un número natural que corresponde a un multiconjunto de un elemento subyacente y cardinalidad igual a ese número, por ejemplo, 3 corresponde al multiconjunto $\{1,1,1\}.$
Subgrupos de un p -grupo finito G , ordenados por inclusión.: La función de Möbius es $\mu _{G}(H_{1},H_{2})=(-1)^{k}p^{\binom {k}{2}}$ si $H_{1}$ es un subgrupo normal de $H_{2}$ y $H_{2}/H_{1}\cong (\mathbb {Z} /p\mathbb {Z} )^{k}$ y es 0 en caso contrario. Este es un teorema de Weisner (1935).
Particiones de un conjunto: Ordenamos parcialmente el conjunto de todas las particiones de un conjunto finito diciendo σ ≤ τ si σ es una partición más fina que τ . En particular, sea τ con t bloques que se dividen respectivamente en s ₁ , ..., s _t bloques más finos de σ , lo que tiene un total de s = s ₁ + ⋅ ⋅ ⋅ + s _t bloques. Entonces la función de Möbius es: $\mu (\sigma ,\tau )=(-1)^{st}(s_{1}{-}1)!\dots (s_{t}{-}1)!$

Característica de Euler

Un poset es acotado si tiene elementos mínimo y máximo, que llamamos 0 y 1 respectivamente (que no deben confundirse con el 0 y el 1 del anillo de escalares). La característica de Euler de un poset finito acotado es μ (0,1). La razón de esta terminología es la siguiente: si P tiene un 0 y un 1, entonces μ (0,1) es la característica de Euler reducida del complejo simplicial cuyas caras son cadenas en P \ {0, 1}. Esto se puede demostrar usando el teorema de Philip Hall, que relaciona el valor de μ (0,1) con el número de cadenas de longitud i .

Álgebras de incidencia reducida

El álgebra de incidencia reducida consta de funciones que asignan el mismo valor a dos intervalos cualesquiera que sean equivalentes en un sentido apropiado, generalmente isomorfos como conjuntos parcialmente ordenados. Esta es una subálgebra del álgebra de incidencia y, claramente, contiene el elemento identidad y la función zeta de esta última. Cualquier elemento del álgebra de incidencia reducida que sea invertible en el álgebra de incidencia mayor tiene su inverso en el álgebra de incidencia reducida. Por lo tanto, la función de Möbius también pertenece al álgebra de incidencia reducida.

Las álgebras de incidencia reducida fueron introducidas por Doubillet, Rota y Stanley para dar una construcción natural de varios anillos de funciones generadoras . ^{[ 2 ]}

Números naturales y funciones generadoras ordinarias

Para el poset $(\mathbb {N} ,\leq ),$ El álgebra de incidencia reducida consta de funciones $f(a,b)$ invariante bajo traslación, $f(a+k,b+k)=f(a,b)$ a pesar de $k\geq 0,$ para que tenga el mismo valor en los intervalos isomorfos [ a + k , b + k ] y [ a , b ]. Sea t la función con t ( a , a +1) = 1 y t ( a , b ) = 0 en caso contrario, una especie de función delta invariante en las clases de isomorfismo de intervalos. Sus potencias en el álgebra de incidencia son las otras funciones delta invariantes t ⁿ ( a , a + n ) = 1 y t ⁿ ( x , y ) = 0 en caso contrario. Estas forman una base para el álgebra de incidencia reducida, y podemos escribir cualquier función invariante como $\textstyle f=\sum _ {n\geq 0}f(0,n)t^{n}$ Esta notación deja claro el isomorfismo entre el álgebra de incidencia reducida y el anillo de series de potencias formales. $R[[t]]$ sobre los escalares R, también conocido como el anillo de funciones generadoras ordinarias . Podemos escribir la función zeta como $\zeta =1+t+t^{2}+\cdots ={\tfrac {1}{1-t}},$ el recíproco de la función de Möbius $\mu =1-t.$

Conjunto parcialmente ordenado de subconjuntos y funciones generadoras exponenciales

Para el conjunto parcialmente ordenado booleano de subconjuntos finitos $S\subset \{1,2,3,\ldots \}$ ordenado por inclusión $S\subset T$ , el álgebra de incidencia reducida consta de funciones invariantes $f(S,T),$ Definida para tener el mismo valor en los intervalos isomorfos [ S , T ] y [ S ′ , T ′ ] con | T \ S | = | T ′ \ S ′ |. Nuevamente, sea t la función delta invariante con t ( S , T ) = 1 para | T \ S | = 1 y t ( S , T ) = 0 en caso contrario. Sus potencias son: $t^{n}(S,T)=\,\sum t(T_{0},T_{1})\,t(T_{1},T_{2})\dots t(T_{n-1},T_{n})=\left\{{\begin{array}{cl}n!&{\text{si}}\,\,|T\smallsetminus S|=n\\0&{\text{en otro caso,}}\end{array}}\right.$ donde la suma se realiza sobre todas las cadenas $S=T_{0}\subset T_{1}\subset \cdots \subset T_{n}=T,$ y los únicos términos distintos de cero aparecen para cadenas saturadas con $|T_{i}\smallsetminus T_{i-1}|=1;$ Dado que estas corresponden a permutaciones de n , obtenemos el único valor distinto de cero n !. Por lo tanto, las funciones delta invariantes son las potencias divididas. ${\tfrac {t^{n}}{n!}},$ y podemos escribir cualquier función invariante como $\textstyle f=\sum _{n\geq 0}f(\emptyset ,[n]){\frac {t^{n}}{n!}},$ donde [ n ] = {1, . . . , n }. Esto da un isomorfismo natural entre el álgebra de incidencia reducida y el anillo de funciones generadoras exponenciales . La función zeta es $\textstyle \zeta =\sum _{n\geq 0}{\frac {t^{n}}{n!}}=\exp(t),$ con función Möbius: $\mu ={\frac {1}{\zeta }}=\exp(-t)=\sum _{n\geq 0}(-1)^{n}{\frac {t^{n}}{n!}}.$ En efecto, este cálculo con series de potencias formales demuestra que $\mu (S,T)=(-1)^{|T\smallsetminus S|}.$ Muchas secuencias de conteo combinatorias que involucran subconjuntos u objetos etiquetados pueden interpretarse en términos del álgebra de incidencia reducida y calcularse utilizando funciones generadoras exponenciales.

Conjunto parcialmente ordenado divisor y series de Dirichlet

Consideremos el conjunto parcialmente ordenado D de enteros positivos ordenados por divisibilidad , denotado por $a\,|\,b.$ El álgebra de incidencia reducida consta de funciones $f(a,b)$ que son invariantes bajo la multiplicación: $f(ka,kb)=f(a,b)$ a pesar de $k\geq 1.$ (Esta equivalencia multiplicativa de intervalos es una relación mucho más fuerte que el isomorfismo de conjuntos parcialmente ordenados; por ejemplo, para los números primos p , los intervalos de dos elementos [1, p ] son todos no equivalentes). Para una función invariante, f ( a , b ) depende solo de b / a , por lo que una base natural consiste en funciones delta invariantes. $\delta _{n}$ definido por $\delta _{n}(a,b)=1$ si b / a = n y 0 en caso contrario; entonces se puede escribir cualquier función invariante. $\textstyle f=\sum _{n\geq 0}f(1,n)\,\delta _{n}.$

El producto de dos funciones delta invariantes es:

(\delta _{n}\delta _{m})(a,b)=\sum _{a|c|b}\delta _{n}(a,c)\,\delta _{m}(c,b)=\delta _{nm}(a,b),

ya que el único término no nulo proviene de c = na y b = mc = nma . Por lo tanto, obtenemos un isomorfismo del álgebra de incidencia reducida al anillo de series de Dirichlet formales enviando $\delta _{n}$ a $n^{-s}\!,$ de modo que f corresponde a ${\textstyle \sum _{n\geq 1}{\frac {f(1,n)}{n^{s}}}.}$

La función zeta del álgebra de incidencia ζ _D ( a , b ) = 1 corresponde a la función zeta de Riemann clásica. $\zeta (s)=\textstyle \sum _{n\geq 1}{\frac {1}{n^{s}}},$ tener recíproco ${\textstyle {\frac {1}{\zeta (s)}}=\sum _{n\geq 1}{\frac {\mu (n)}{n^{s}}},}$ dónde $\mu (n)=\mu _{D}(1,n)$ es la función de Möbius clásica de la teoría de números. Muchas otras funciones aritméticas surgen naturalmente dentro del álgebra de incidencia reducida, y equivalentemente en términos de series de Dirichlet. Por ejemplo, la función divisor $\sigma _{0}(n)$ es el cuadrado de la función zeta, $\sigma _{0}(n)=\zeta ^{2}\!(1,n),$ un caso especial del resultado anterior que $\zeta ^{2}\!(x,y)$ da el número de elementos en el intervalo [ x , y ]; equivalentes, ${\textstyle \zeta (s)^{2}=\sum _{n\geq 1}{\frac {\sigma _{0}(n)}{n^{s}}}.}$

La estructura de producto del poset divisor facilita el cálculo de su función de Möbius. La factorización única en primos implica que D es isomorfo a un producto cartesiano infinito. $\mathbb {N} \times \mathbb {N} \times \dots$ , con el orden dado por la comparación de coordenadas: $n=p_{1}^{e_{1}}p_{2}^{e_{2}}\dots$ , dónde $p_{k}$ es el k ^-ésimo número primo, corresponde a su secuencia de exponentes $(e_{1},e_{2},\dots ).$ Ahora, la función de Möbius de D es el producto de las funciones de Möbius para los conjuntos parcialmente ordenados de factores, calculados anteriormente, lo que da como resultado la fórmula clásica:

\mu (n)=\mu _{D}(1,n)=\prod _{k\geq 1}\mu _{\mathbb {N} }(0,e_{k})\,=\,\left\{{\begin{array}{cl}(-1)^{d}&{\text{for }}n{\text{ squarefree with }}d{\text{ prime factors}}\\0&{\text{otherwise.}}\end{array}}\right.

La estructura del producto también explica el producto de Euler clásico para la función zeta. La función zeta de D corresponde a un producto cartesiano de funciones zeta de los factores, calculados anteriormente como ${\textstyle {\frac {1}{1-t}},}$ de modo que ${\textstyle \zeta _{D}\cong \prod _{k\geq 1}\!{\frac {1}{1-t}},}$ donde el lado derecho es un producto cartesiano. Aplicando el isomorfismo que envía t en el k ^-ésimo factor a $p_{k}^{-s}$ , obtenemos el producto de Euler habitual.

Véase también

Literatura

Las álgebras de incidencia de conjuntos parcialmente ordenados localmente finitos fueron tratadas en varios artículos de Gian-Carlo Rota a partir de 1964, y por muchos combinatorialistas posteriores . El artículo de Rota de 1964 fue:

Rota, Gian-Carlo (1964), "Sobre los fundamentos de la teoría combinatoria I: teoría de las funciones de Möbius", Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete , 2 (4): 340– 368, doi : 10.1007/BF00531932 , S2CID 121334025
N. Jacobson , Álgebra básica . I, WH Freeman and Co., 1974. Véase la sección 8.6 para un tratamiento de las funciones de Möbius en conjuntos parcialmente ordenados.

↑ Kolegov, NA; Markova, OV (agosto de 2019). "Sistemas de generadores de álgebras de incidencia de matrices sobre cuerpos finitos" . Journal of Mathematical Sciences . 240 (6): 783– 798. doi : 10.1007/s10958-019-04396-6 . ISSN 1072-3374 . S2CID 198443199 .
↑ Peter Doubilet, Gian-Carlo Rota y Richard Stanley: Sobre los fundamentos de la combinatoria (VI): La idea de la función generadora , Simposio de Berkeley sobre estadística matemática y probabilidad, Actas del sexto Simposio de Berkeley sobre estadística matemática y probabilidad, vol. 2 (Univ. de Calif. Press, 1972), 267-318, disponible en línea en acceso abierto.

Lecturas adicionales

Spiegel, Eugene; O'Donnell, Christopher J. (1997), Álgebras de incidencia , Matemáticas puras y aplicadas, vol. 206, Marcel Dekker, ISBN 0-8247-0036-8

[1] Kolegov, NA; Markova, OV (agosto de 2019). "Sistemas de generadores de álgebras de incidencia de matrices sobre cuerpos finitos" . Journal of Mathematical Sciences . 240 (6): 783– 798. doi : 10.1007/s10958-019-04396-6 . ISSN 1072-3374 . S2CID 198443199 .

[2] Peter Doubilet, Gian-Carlo Rota y Richard Stanley: Sobre los fundamentos de la combinatoria (VI): La idea de la función generadora , Simposio de Berkeley sobre estadística matemática y probabilidad, Actas del sexto Simposio de Berkeley sobre estadística matemática y probabilidad, vol. 2 (Univ. de Calif. Press, 1972), 267-318, disponible en línea en acceso abierto.

[ 1 ]

[ 2 ]