Алгебра инцидентности

В теории порядка , области математики , алгебра инцидентности — это ассоциативная алгебра , определенная для каждого локально конечного частично упорядоченного множества и коммутативного кольца с единицей. Подалгебры , называемые редуцированными алгебрами инцидентности, дают естественную конструкцию различных типов производящих функций, используемых в комбинаторике и теории чисел .

Локально конечный посет — это такой посет, в котором каждый замкнутый интервал

[ а, б ] = { х  : а ≤ х ≤ б }

является конечным .

Членами алгебры инцидентности являются функции f, назначающие каждому непустому интервалу [ a, b ] скаляр f ( a , b ), который берется из кольца скаляров , коммутативного кольца с единицей. На этом базовом множестве определяются сложение и скалярное умножение поточечно, а «умножение» в алгебре инцидентности является сверткой, определяемой как

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

Алгебра инцидентности конечномерна тогда и только тогда, когда базовый посет конечен.

Алгебра инцидентности аналогична групповой алгебре ; действительно, как групповая алгебра, так и алгебра инцидентности являются частными случаями алгебры категорий , определяемыми аналогично; группы и частично упорядоченные множества являются частными видами категорий .

Рассмотрим случай частичного порядка ≤ над любым n -элементным множеством S. Перечислим S как s1 , …, sn , _причем таким образом, чтобы перечисление было совместимо с порядком ≤ на _S , то есть s _i ≤ sj влечет i ≤ _j , что всегда возможно.

Тогда функции f, как указано выше, от интервалов до скаляров, можно рассматривать как матрицы A _ij , где A _ij = f ( s _i , s _j ) всякий раз, когда i ≤ j , и A _ij = 0 в противном случае . Поскольку мы расположили S в соответствии с обычным порядком индексов матриц, они будут выглядеть как верхнетреугольные матрицы с заданным нулевым шаблоном, определяемым несравнимыми элементами в S при ≤.

Тогда алгебра инцидентности ≤ изоморфна алгебре верхнетреугольных матриц с этим предписанным нулевым шаблоном и произвольными (включая, возможно, нулевые) скалярными элементами во всех остальных местах, причем операциями являются обычное сложение матриц , масштабирование и умножение . ^[1]

Мультипликативный элемент тождества алгебры инцидентности — это дельта-функция , определяемая как

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

Дзета -функция алгебры инцидентности — это постоянная функция ζ ( a , b ) = 1 для каждого непустого интервала [ a, b ]. Умножение на ζ аналогично интегрированию .

Можно показать, что ζ обратим в алгебре инцидентности (относительно свертки, определенной выше). (В общем случае, элемент h алгебры инцидентности обратим тогда и только тогда, когда h ( x , x ) обратим для каждого x .) Мультипликативной обратной функцией дзета-функции является функция Мёбиуса μ ( a, b ); каждое значение μ ( a, b ) является целым кратным 1 в базовом кольце.

Функцию Мёбиуса можно также определить индуктивно с помощью следующего соотношения:

${\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{internally }}.\end{cases}}}$

Умножение на μ аналогично дифференцированию и называется обращением Мёбиуса .

Квадрат дзета-функции дает количество элементов в интервале:$${\displaystyle \zeta ^{2}(x,y)=\sum _{z\in [x,y]}\zeta (x,z)\,\zeta (z,y)=\sum _{z \in [x,y]}1=\#[x,y].}$$

Положительные целые числа, упорядоченные по делимости

Свертка, связанная с алгеброй инцидентности для интервалов [1, n ], становится сверткой Дирихле , следовательно, функция Мёбиуса равна μ ( a, b ) = μ ( b/a ), где второе « μ » — классическая функция Мёбиуса , введенная в теорию чисел в 19 веке.

Конечные подмножества некоторого множества E , упорядоченные по включению

Функция Мёбиуса — это$${\displaystyle \mu (S,T)=(-1)^{\left|T\smallsetминус S\right|}}$$

всякий раз, когда S и T являются конечными подмножествами E с S ⊆ T , а обращение Мёбиуса называется принципом включения-исключения .

Геометрически это гиперкуб :${\displaystyle 2^{E}=\{0,1\}^{E}.}$

Натуральные числа в их обычном порядке

Функция Мёбиуса называется , а обращение Мёбиуса называется (обратным) оператором разности .$${\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}}}$$

Геометрически это соответствует дискретной числовой оси .

Свертка функций в алгебре инцидентности соответствует умножению формальных степенных рядов : см. обсуждение приведенных алгебр инцидентности ниже. Функция Мёбиуса соответствует последовательности (1, −1, 0, 0, 0, ... ) коэффициентов формального степенного ряда 1 −  t , а дзета-функция соответствует последовательности коэффициентов (1, 1, 1, 1, ...) формального степенного ряда , который является обратным. Дельта-функция в этой алгебре инцидентности аналогично соответствует формальному степенному ряду 1.${\displaystyle (1-t)^{-1}=1+t+t^{2}+t^{3}+\cdots }$

Конечные подмножества некоторого мультимножества E , упорядоченные по включению

Приведенные выше три примера можно объединить и обобщить, рассмотрев мультимножество E и конечные подмножества S и T множества E. Функция Мёбиуса имеет вид$${\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}}}$$

Это обобщает положительные целые числа, упорядоченные по делимости на положительное целое число, соответствующее его мультимножеству простых множителей с кратностью, например, 12 соответствует мультимножеству${\displaystyle \{2,2,3\}.}$

Это обобщает натуральные числа с их обычным порядком с помощью натурального числа, соответствующего мультимножеству из одного базового элемента и мощности, равной этому числу, например, 3 соответствует мультимножеству${\displaystyle \{1,1,1\}.}$

Подгруппы конечной p -группы G , упорядоченные по включению

Функция Мёбиуса равна , если является нормальной подгруппой группы и , в противном случае она равна 0. Это теорема Вейснера (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}}$

Разделы множества

Частично упорядочим множество всех разбиений конечного множества, сказав σ ≤ τ, если σ является более мелким разбиением, чем τ . В частности, пусть τ имеет t блоков, которые соответственно делятся на s ₁ , ..., s _t более мелких блоков σ , что в сумме дает s = s ₁ + ⋅⋅⋅ + s _t блоков. Тогда функция Мёбиуса имеет вид:$${\displaystyle \mu (\sigma ,\tau )=(-1)^{s-t}(s_{1}{-}1)!\dots (s_{t}{-}1)!}$$

ЧУМ ограничен , если он имеет наименьший и наибольший элементы, которые мы называем 0 и 1 соответственно (не путать с 0 и 1 кольца скаляров). Эйлерова характеристика ограниченного конечного ЧУМ равна μ (0,1). Причина такой терминологии следующая: если P имеет 0 и 1, то μ (0,1) является приведенной эйлеровой характеристикой симплициального комплекса , грани которого являются цепями в P  \ {0, 1}. Это можно показать с помощью теоремы Филипа Холла, связывающей значение μ (0,1) с числом цепей длины i .

Редуцированная алгебра инцидентности состоит из функций, которые присваивают одно и то же значение любым двум интервалам, которые эквивалентны в соответствующем смысле, обычно имея в виду изоморфные как частично упорядоченные множества. Это подалгебра алгебры инцидентности, и она, очевидно, содержит элемент тождества алгебры инцидентности и дзета-функцию. Любой элемент редуцированной алгебры инцидентности, который обратим в большей алгебре инцидентности, имеет свой обратный в редуцированной алгебре инцидентности. Таким образом, функция Мёбиуса также находится в редуцированной алгебре инцидентности.

Редуцированные алгебры инцидентности были введены Дубийе, Ротой и Стэнли, чтобы дать естественную конструкцию различных колец производящих функций . ^[2]

Для частично упорядоченного множества приведенная алгебра инцидентности состоит из функций, инвариантных относительно сдвига, для всех так, чтобы иметь одно и то же значение на изоморфных интервалах [ a + k , b + k ] и [ a , b ]. Пусть t обозначает функцию с t ( a , a +1) = 1 и t ( a , b ) = 0 в противном случае, своего рода инвариантную дельта-функцию на классах изоморфизма интервалов. Ее степенями в алгебре инцидентности являются другие инвариантные дельта-функции t ⁿ ( a , a + n ) = 1 и t ⁿ ( x , y ) = 0 в противном случае. Они образуют основу для приведенной алгебры инцидентности, и мы можем записать любую инвариантную функцию как . Эта запись проясняет изоморфизм между приведенной алгеброй инцидентности и кольцом формальных степенных рядов над скалярами R, также известным как кольцо обычных производящих функций . Мы можем записать дзета-функцию как обратную величину функции Мёбиуса${\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.}$

Для булевого частично упорядоченного множества конечных подмножеств, упорядоченных по включению , приведенная алгебра инцидентности состоит из инвариантных функций, определенных как имеющие одно и то же значение на изоморфных интервалах [ S , T ] и [ S ′, T  ′] с | T  \  S | = | T  ′ \  S ′|. Снова пусть t обозначает инвариантную дельта-функцию с t ( S , T ) = 1 для | T  \  S | = 1 и t ( S , T ) = 0 в противном случае. Ее мощности: где сумма берется по всем цепям , и единственные ненулевые члены встречаются для насыщенных цепей с поскольку они соответствуют перестановкам n , мы получаем уникальное ненулевое значение n !. Таким образом, инвариантные дельта-функции являются разделенными мощностями , и мы можем записать любую инвариантную функцию как где [ n ] = {1, . . . , n }. Это дает естественный изоморфизм между приведенной алгеброй инцидентности и кольцом экспоненциальных производящих функций . Дзета-функция связана с функцией Мёбиуса: Действительно, это вычисление с формальными степенными рядами доказывает, что Многие комбинаторные счетные последовательности, включающие подмножества или помеченные объекты, могут быть интерпретированы в терминах приведенной алгебры инцидентности и вычислены с использованием экспоненциальных производящих функций.${\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|}.}$

Рассмотрим частично упорядоченный набор D положительных целых чисел, упорядоченных по делимости , обозначаемый как Приведенная алгебра инцидентности состоит из функций , которые инвариантны относительно умножения: для всех (Эта мультипликативная эквивалентность интервалов является гораздо более сильным отношением, чем изоморфизм частично упорядоченных множеств; например, для простых чисел p двухэлементные интервалы [1, p ] неэквивалентны.) Для инвариантной функции f ( a , b ) зависит только от b / a , поэтому естественный базис состоит из инвариантных дельта-функций, определяемых следующим образом: если b / a = n и 0 в противном случае; тогда любую инвариантную функцию можно записать${\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}.}$

Произведение двух инвариантных дельта-функций равно:

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

поскольку единственный ненулевой член происходит от c = na и b = mc = nma . Таким образом, мы получаем изоморфизм из редуцированной алгебры инцидентности в кольцо формальных рядов Дирихле , отправляя в так, что f соответствует${\displaystyle \delta _{n}}$${\displaystyle n^{-s}\!,}$${\textstyle \sum _{n\geq 1}{\frac {f(1,n)}{n^{s}}}.}$

Дзета-функция алгебры инцидентности ζ _D ( a , b ) = 1 соответствует классической дзета-функции Римана, имеющей обратную величину , где — классическая функция Мёбиуса теории чисел. Многие другие арифметические функции возникают естественным образом в рамках редуцированной алгебры инцидентности и, что эквивалентно, в терминах рядов Дирихле. Например, функция делителя — это квадрат дзета-функции, частный случай приведенного выше результата, который дает число элементов в интервале [ x , y ]; эквивалентно,${\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}}}.}$

Структура произведения делителя частично упорядоченного множества облегчает вычисление его функции Мёбиуса. Уникальное разложение на простые числа подразумевает, что D изоморфно бесконечному декартову произведению , с порядком, заданным покоординатным сравнением: , где k - ^й простой элемент, соответствует его последовательности показателей Теперь функция Мёбиуса D является произведением функций Мёбиуса для частично упорядоченных множеств-множителей, вычисленных выше, что дает классическую формулу: ${\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.}$

Структура произведения также объясняет классическое произведение Эйлера для дзета-функции. Дзета-функция D соответствует декартову произведению дзета-функций факторов, вычисленных выше как так, что где правая сторона является декартовым произведением. Применяя изоморфизм, который переводит t в k ^-м факторе в , мы получаем обычное произведение Эйлера.${\textstyle {\frac {1}{1-t}},}$${\textstyle \zeta _{D}\cong \prod _{k\geq 1}\!{\frac {1}{1-t}},}$${\displaystyle p_{k}^{-s}}$

• Графовая алгебра
• Инцидентность коалгебра
• Алгебра путей

Алгебры инцидентности локально конечных частично упорядоченных множеств рассматривались в ряде статей Джан-Карло Роты, начиная с 1964 года, и многими более поздними комбинаториистами . Статья Роты 1964 года была следующей:

• Рота, Джан-Карло (1964), «Об основах комбинаторной теории I: теория функций Мёбиуса», Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete , 2 (4): 340–368, doi : 10.1007/BF00531932 , S2CID  121334025
• Н. Якобсон , Базовая алгебра . I, WH Freeman and Co., 1974. См. раздел 8.6 для рассмотрения функций Мёбиуса на частично упорядоченных множествах.

• Шпигель, Юджин; О'Доннелл, Кристофер Дж. (1997), Алгебры инцидентности , Чистая и прикладная математика, т. 206, Марсель Деккер, ISBN 0-8247-0036-8