Álgebra de incidencia

Álgebra asociativa utilizada en combinatoria, una rama de las matemáticas.

En teoría del orden , un campo de las matemáticas , un álgebra de incidencia es un álgebra asociativa , definida para cada conjunto localmente finito parcialmente ordenado y anillo conmutativo con unidad. Las subálgebras llamadas álgebras de incidencia reducida dan 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 asignando 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 puntualmente, y la "multiplicación" en el álgebra de incidencia es una convolución definida por

${\displaystyle (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 sólo si el poset subyacente es finito.

Conceptos relacionados

Un álgebra de incidencia es análoga a un álgebra de grupos ; de hecho, tanto el álgebra de grupos como el álgebra de incidencia son casos especiales de un álgebra de categorías , definida de manera análoga; Los grupos y posets son tipos especiales de categorías .

Matrices triangulares superiores

Considere el caso de un orden parcial ≤ sobre cualquier conjunto de n elementos S. Enumeramos S como s ₁ , …, s _n , y de tal forma que la enumeración sea compatible con el orden ≤ en S , es decir, s _i ≤ s _j implica i ≤ j , lo cual siempre es posible.

Entonces, las funciones f como arriba, desde intervalos hasta escalares, pueden considerarse como matrices A _ij , donde A _ij = f ( s _i , s _j ) siempre que i ≤ 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 cero 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 (incluido posiblemente cero) en todos los demás lugares, siendo las operaciones suma , escala y multiplicación de matrices ordinarias . ^[1]

Elementos especiales

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

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

La función zeta de un álgebra de incidencia es la función constante ζ ( a , b ) = 1 para cada 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). (Generalmente, un miembro h del álgebra de incidencia es invertible si y sólo si h ( x , x ) es invertible para cada x .) La inversa multiplicativa de la función zeta es la función de Möbius μ ( a, b ); cada valor de μ ( a, b ) es un múltiplo integral de 1 en el anillo base.

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

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

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

El cuadrado de la función zeta da el número de elementos en un intervalo:

$${\displaystyle \zeta ^{2}(x,y)=\sum _{z\in [x,y]}\zeta (x,z)\,\zeta (z,y)=\sum _{z\in [x,y]}1=\#[x,y].}$$

Ejemplos

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 , de ahí que la función de Möbius sea μ ( 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 Moebius es

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

siempre que S y T sean subconjuntos finitos de E con S ⊆ T , y la inversión de Möbius se denomina principio de inclusión-exclusión .

Geométricamente, este es un hipercubo : ${\displaystyle 2^{E}=\{0,1\}^{E}.}$

Números naturales con su orden habitual.

La función de Moebius es

$${\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}}}$$

y la inversión de Möbius se llama 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 : consulte la discusión sobre álgebras de incidencia reducida a continuación. 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 , que es inversa. La función delta en este álgebra de incidencia corresponde de manera similar a la serie de potencias formal 1. ${\displaystyle (1-t)^{-1}=1+t+t^{2}+t^{3}+\cdots }$

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 Moebius es

$${\displaystyle \mu (S,T)={\begin{cases}0&{\text{if }}T\smallsetminus S{\text{ is a proper multiset (has repeated elements)}}\\(-1)^{\left|T\smallsetminus S\right|}&{\text{if }}T\smallsetminus S{\text{ is a set (has no repeated elements)}}.\end{cases}}}$$

Esto generaliza los números enteros positivos ordenados por divisibilidad por un número entero positivo correspondiente a su multiconjunto de factores primos con multiplicidad, por ejemplo, 12 corresponde al multiconjunto ${\displaystyle \{2,2,3\}.}$

Esto generaliza los números naturales con su orden habitual mediante un número natural correspondiente a un multiconjunto de un elemento subyacente y cardinalidad igual a ese número, por ejemplo, 3 corresponde al multiconjunto ${\displaystyle \{1,1,1\}.}$

Subgrupos de un p -grupo G finito , ordenados por inclusión

La función de Moebius es

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

si es un subgrupo normal de y y es 0 en caso contrario. Éste es un teorema de Weisner (1935). ${\displaystyle H_{1}}$ ${\displaystyle H_{2}}$ ${\displaystyle H_{2}/H_{1}\cong (\mathbb {Z} /p\mathbb {Z} )^{k}}$

Particiones de un conjunto

Ordene parcialmente el conjunto de todas las particiones de un conjunto finito diciendo σ ≤ τ si σ es una partición más fina que τ . En particular, supongamos que τ tenga t bloques que se dividen respectivamente en s ₁ , ..., s _t bloques más finos de σ , que tiene un total de s = s ₁ + ⋅⋅⋅ + s _t bloques. Entonces la función de Möbius es:

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

característica de euler

Un poset está acotado si tiene elementos más pequeños y más grandes, a los que llamamos 0 y 1 respectivamente (no confundir con el 0 y 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 utilizando el teorema de Philip Hall, relacionando 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, es decir, generalmente isomórficos como posets. Esta es una subálgebra del álgebra de incidencia y contiene claramente el elemento identidad y la función zeta del álgebra de incidencia. 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 tanto, la función de Möbius también se encuentra en el álgebra de incidencia reducida.

Doubillet, Rota y Stanley introdujeron álgebras de incidencia reducida para dar una construcción natural de varios anillos de funciones generadoras . ^[2]

Números naturales y funciones generadoras ordinarias.

Para el poset, el álgebra de incidencia reducida consta de funciones invariantes bajo traducción, para que todas tengan el mismo valor en intervalos isomórficos [ 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 clases de intervalos de isomorfismo. 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. Estos forman una base para el álgebra de incidencia reducida y podemos escribir cualquier función invariante como . Esta notación deja claro el isomorfismo entre el álgebra de incidencia reducida y el anillo de series de potencias formales sobre los escalares R, también conocido como anillo de funciones generadoras ordinarias . Podemos escribir la función zeta como el recíproco de la función de Möbius. ${\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.}$

Subconjunto poset y funciones generadoras exponenciales

Para el poset booleano de subconjuntos finitos ordenados por inclusión , el álgebra de incidencia reducida consta de funciones invariantes definidas para tener el mismo valor en 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 poderes son: ${\displaystyle S\subset \{1,2,3,\ldots \}}$ ${\displaystyle S\subset T}$ ${\displaystyle f(S,T),}$

$${\displaystyle 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{if}}\,\,|T\smallsetminus S|=n\\0&{\text{otherwise,}}\end{array}}\right.}$$

nnnnortefunciones generadoras exponenciales ${\displaystyle S=T_{0}\subset T_{1}\subset \cdots \subset T_{n}=T,}$ ${\displaystyle |T_{i}\smallsetminus 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 \mu ={\frac {1}{\zeta }}=\exp(-t)=\sum _{n\geq 0}(-1)^{n}{\frac {t^{n}}{n!}}.}$$

calcularse ${\displaystyle \mu (S,T)=(-1)^{|T\smallsetminus S|}.}$

Poset divisor y series de Dirichlet

Considere el poset D de enteros positivos ordenados por divisibilidad , denotado por El álgebra de incidencia reducida consta de funciones que son invariantes bajo multiplicación: para todos (Esta equivalencia multiplicativa de intervalos es una relación mucho más fuerte que el isomorfismo del poset; por ejemplo, para primos p , el intervalos de dos elementos [1, p ] no son equivalentes.) Para una función invariante, f ( a , b ) depende sólo de b / a , por lo que una base natural consta de funciones delta invariantes definidas por si b / a = n y 0 en caso contrario; entonces se puede escribir cualquier función invariante ${\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}.}$

El producto de dos funciones delta invariantes es:

${\displaystyle (\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 distinto de cero proviene de c = na y b = mc = nma . Por lo tanto, obtenemos un isomorfismo del álgebra de incidencia reducida al anillo de la serie formal de Dirichlet enviando a para que f corresponda a ${\displaystyle \delta _{n}}$ ${\displaystyle n^{-s}\!,}$ ${\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 que tiene recíproco donde 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, de manera equivalente, en términos de series de Dirichlet. Por ejemplo, la función divisora ​​es el cuadrado de la función zeta, un caso especial del resultado anterior que da el número de elementos en el intervalo [ x , y ]; equivalencia, ${\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}}}.}$

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

${\displaystyle \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 clásico de Euler para la función zeta. La función zeta de D corresponde a un producto cartesiano de las funciones zeta de los factores, calculadas anteriormente de modo que el lado derecho sea un producto cartesiano. Aplicando el isomorfismo que envía t en el ^késimo factor a , obtenemos el producto habitual de Euler. ${\textstyle {\frac {1}{1-t}},}$ ${\textstyle \zeta _{D}\cong \prod _{k\geq 1}\!{\frac {1}{1-t}},}$ ${\displaystyle p_{k}^{-s}}$

Ver también

• Álgebra gráfica
• Incidencia coalgebra
• Álgebra de caminos

Literatura

Las álgebras de incidencia de posets 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 Mobius en posets.

1. Kolegov, NA; Markova, OV (agosto de 2019). "Sistemas de generadores de álgebras de incidencia matricial sobre campos finitos". Revista de Ciencias Matemáticas . 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 generar funciones , Simposio de matemáticas de Berkeley. Estadístico. y Prob., Proc. Sexto Simposio de Matemáticas de Berkeley. Estadístico. y Prob., vol. 2 (Univ. of Calif. Press, 1972), 267-318, disponible en línea en acceso abierto

Otras lecturas

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