Álgebra de incidencia

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

En la teoría del orden , un campo de las matemáticas , un álgebra de incidencia es un álgebra asociativa , definida para cada conjunto parcialmente ordenado localmente finito 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 conjunto parcial 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. Sobre este conjunto subyacente se define la adición 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 conjunto posesivo 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 , definidas de manera análoga; los grupos y los conjuntos parciales son tipos especiales de categorías .

Matrices triangulares superiores

Consideremos el caso de un orden parcial ≤ sobre cualquier conjunto de n elementos S . Enumeramos S como s ₁ , …, s _n , y de tal manera 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 las anteriores, 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 (incluyendo posiblemente cero) en todos los demás lugares, siendo las operaciones la suma , el escalamiento y la multiplicación de matrices ordinarias . ^[1]

Elementos especiales

El elemento 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 solo 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 entero 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 la 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

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 el segundo " μ " es la función clásica de Möbius 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 $${\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, esto es un hipercubo : ${\displaystyle 2^{E}=\{0,1\}^{E}.}$

Números naturales con su orden habitual

La función de Möbius es y la inversión de Möbius se llama operador de diferencia (hacia atrás) . $${\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}}}$$

Geométricamente, esto corresponde a la línea 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 las álgebras de incidencia reducidas 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 formales 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 esta álgebra de incidencia corresponde de manera similar a la serie de potencias formales 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 se pueden unificar y generalizar considerando un multiconjunto E y submulticonjuntos finitos S y T de E. La función de Möbius 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 finito G , ordenados por inclusión

La función de Möbius es si es un subgrupo normal de y y es 0 en caso contrario. Este es un teorema de Weisner (1935). $${\displaystyle \mu _{G}(H_{1},H_{2})=(-1)^{k}p^{\binom {k}{2}}}$$ ${\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, sea τ con 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 conjunto parcial está acotado si tiene elementos más pequeños y más grandes, que llamamos 0 y 1 respectivamente (no confundir con el 0 y el 1 del anillo de escalares). La característica de Euler de un conjunto parcial 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, 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 consiste en funciones que asignan el mismo valor a dos intervalos cualesquiera que sean equivalentes en un sentido apropiado, es decir, que normalmente sean isomorfos , como los conjuntos parciales. Esta es una subálgebra del álgebra de incidencia y claramente contiene 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 más grande tiene su inverso en el álgebra de incidencia reducida. Por lo tanto, la función de Möbius también está en el á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 generatrices ordinarias

Para el conjunto parcial, el álgebra de incidencia reducida consiste en funciones invariantes bajo traslación, para todas de modo que tengan el mismo valor en 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 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 . 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 el 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.}$

Funciones de generación de subconjuntos poset y exponenciales

Para el conjunto booleano de subconjuntos finitos ordenados por inclusión , el álgebra de incidencia reducida consiste en 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 potencias son: donde la suma es sobre todas las cadenas y los únicos términos distintos de cero ocurren para cadenas saturadas con dado que estos corresponden a permutaciones de n , obtenemos el único valor distinto de cero n !. Por lo tanto, las funciones delta invariantes son las potencias divididas y podemos escribir cualquier función invariante como 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 con la función de Möbius: De hecho, este cálculo con series de potencias formales demuestra que 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. ${\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.}$$ ${\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!}}.}$$ ${\displaystyle \mu (S,T)=(-1)^{|T\smallsetminus S|}.}$

Serie divisora ​​poset y serie de Dirichlet

Considere el conjunto poset D de números enteros positivos ordenados por divisibilidad , denotado por El álgebra de incidencia reducida consiste en funciones que son invariantes bajo la multiplicación: para todos (Esta equivalencia multiplicativa de intervalos es una relación mucho más fuerte que el isomorfismo de conjuntos poset; por ejemplo, para primos p , los intervalos de dos elementos [1, p ] son ​​todos inequivalentes). Para una función invariante, f ( a , b ) depende solo de b / a , por lo que una base natural consiste en funciones delta invariantes definidas por si b / a = n y 0 en caso contrario; entonces cualquier función invariante puede escribirse ${\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 series formales de Dirichlet enviando a de modo que f corresponde 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 clásica de Riemann que tiene recíproco donde es la función clásica de Möbius 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 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 ]; equivalentemente, ${\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 conjunto de divisores 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 , con el orden dado por comparación de 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 conjuntos 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 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, calculado anteriormente como tal que donde el lado ^derecho es un producto cartesiano. Aplicando el isomorfismo que envía t en el factor k a , obtenemos el producto de Euler habitual. ${\textstyle {\frac {1}{1-t}},}$ ${\textstyle \zeta _{D}\cong \prod _{k\geq 1}\!{\frac {1}{1-t}},}$ ${\displaystyle p_{k}^{-s}}$

Véase también

• Álgebra gráfica
• Coalgebra de incidencia
• Álgebra de caminos

Literatura

Las álgebras de incidencia de conjuntos parciales localmente finitos fueron tratadas en una serie de artículos de Gian-Carlo Rota a partir de 1964, y por muchos combinatorios 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 , Basic Algebra . I, WH Freeman and Co., 1974. Véase la sección 8.6 para un tratamiento de las funciones de Möbius en conjuntos parciales.

1. Kolegov, NA; Markova, OV (agosto de 2019). "Sistemas de generadores de álgebras de incidencia de matrices sobre cuerpos 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 la función generadora , Berkeley Symposium on Math. Statist. and Prob., Proc. Sexto Berkeley Symposium on Math. Statist. and Prob., vol. 2 (Univ. of Calif. Press, 1972), 267-318, disponible en línea en acceso abierto

Lectura adicional

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