En la 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 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, uno define la suma y la multiplicación escalar puntualmente, y "multiplicación" en el álgebra de incidencia es una convolución definida por
Un álgebra de incidencia es de dimensión finita si y solo si el conjunto 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 , definida de manera análoga; grupos y posets son tipos especiales de categorías .
Matrices triangulares superiores
Considere el caso de un orden parcial ≤ sobre cualquier n conjunto -elemento S . Enumeramos S como s 1 ,…, 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 arriba, desde intervalos a escalares, se pueden considerar 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 isomórfica al álgebra de matrices triangulares superiores con este patrón cero prescrito y entradas escalares arbitrarias (incluyendo posiblemente cero) en cualquier otro lugar, siendo las operaciones sumas, escalas y multiplicaciones de matrices ordinarias. [1]
Elementos especiales
El elemento de identidad multiplicativo del álgebra de incidencia es la función delta , definida por
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 .) 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 integral de 1 en el anillo base.
La función de Möbius también se puede definir inductivamente por la siguiente relación:
Multiplicar por μ es análogo a la diferenciación y se denomina inversión de Möbius .
El cuadrado de la función zeta cuenta el número de elementos en un intervalo:
Ejemplos de
- 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 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
- siempre que S y T son 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 :
- Números naturales con su orden habitual
- La función de Möbius es
- 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 : ver la discusión de álgebras de incidencia reducida más abajo. La función de Möbius corresponde a la secuencia (1, −1, 0, 0, 0, ...) de coeficientes de la serie de potencia 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 inverso. La función delta en este álgebra de incidencia corresponde de manera similar a la serie formal de potencias 1.
- Sub-conjuntos múltiples finitos de algunos conjuntos múltiples E , ordenados por inclusión
- Lo anterior tres ejemplos se pueden unificar y generalizada considerando un conjunto múltiple E, y finitos sub-conjuntos múltiples S y T de E . La función de Möbius es
- Esto generaliza los enteros positivos ordenados por divisibilidad por un entero positivo correspondiente a su multiset de divisores primos con multiplicidad, por ejemplo, 12 corresponde al multiset
- Esto generaliza los números naturales con su orden habitual por un número natural correspondiente a un multiset de un elemento subyacente y la cardinalidad igual a ese número, por ejemplo, 3 corresponde al multiset
- Subgrupos de un p -grupo G finito , 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).
- 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, dejar que tienen τ t bloques que respectivamente divididos en s 1 ,. . . , s t bloques más finos de σ, que tiene un total de s = s 1 + ··· + s t bloques. Entonces la función de Möbius es:
Característica de Euler
Un poset 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 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, relacionando 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 son equivalentes en un sentido apropiado, generalmente significando isomorfos como posets. 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 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 invariante en traducción, para todos para tener 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 intervalos de isomorfismo. Sus potencias en el álgebra de incidencia son las otras funciones delta invariantes t n (a, a + n) = 1 y t n (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 aclara el isomorfismo entre el álgebra de incidencia reducida y el anillo de series formales de potencias.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
Poset de subconjunto y funciones generadoras exponenciales
Para el conjunto booleano de subconjuntos finitos ordenado por inclusión , el álgebra de incidencia reducida consta de funciones invariantes definido para tener el mismo valor en intervalos isomorfos [S, T] y [S ', T'] con | T \ S | = | T '\ S' |. Nuevamente, denote 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:
donde la suma está 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 valor único distinto de cero n !. Por 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 formales de potencia demuestra que Muchas secuencias de conteo combinatorio que involucran subconjuntos u objetos etiquetados pueden interpretarse en términos del álgebra de incidencia reducida y calcularse usando funciones generadoras exponenciales.
Serie Divisor Poset y Dirichlet
Considere el posconjunto D de enteros positivos ordenados por divisibilidad , denotados El álgebra de incidencia reducida consta de funciones invariante bajo multiplicación, para todos (Esta equivalencia de multiplicación de intervalos es una relación mucho más fuerte que el isomorfismo poset: para el primo p, los intervalos de dos elementos [1, p] son todos desiguales.) Para una función invariante, f (a, b) depende solo de b / a, por lo que una base natural consta de funciones delta invariantes definido por si b / a = ny 0 en caso contrario: se puede escribir cualquier función invariante
El producto de dos funciones delta invariantes es:
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 de modo que f corresponde a
La función zeta del álgebra de incidencia ζ D (a, b) = 1 corresponde a la función zeta clásica de Riemann tener reciprocidad dónde 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, de manera equivalente, 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 cuenta el número de elementos en el intervalo [x, y]; equivalentemente,
La estructura del producto del divisor poset 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 de coordenadas: , dónde es el k- ésimo primo, corresponde a su secuencia de exponentesAhora, 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:
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, calculado anteriormente como así que eso donde el lado derecho es un producto cartesiano. Aplicando el isomorfismo que envía t en el k- ésimo factor a, obtenemos el producto Euler habitual.
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 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 , S225CID 1213340CID
- 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.
- ^ Kolegov, NA; Markova, VO (agosto de 2019). "Sistemas de Generadores de Álgebras Matriciales de Incidencia sobre Campos Finitos" . Revista de Ciencias Matemáticas . 240 (6): 783–798. doi : 10.1007 / s10958-019-04396-6 . ISSN 1072-3374 .
- ^ Peter Doubilet, Gian-Carlo Rota y Richard Stanley: sobre los fundamentos de la combinatoria (IV): la idea de la función generadora , Berkeley Symp. en matemáticas. Estadístico. y Prob. Proc. Sexto Berkeley Symp. en matemáticas. Estadístico. y Prob., vol. 2 (Univ. Of Calif. Press, 1972), 267-318, disponible en línea en acceso abierto
Otras lecturas
- Spiegel, Eugene; O'Donnell, Christopher J. (1997), Álgebras de incidencia , Matemáticas puras y aplicadas, 206 , Marcel Dekker, ISBN 0-8247-0036-8