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

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

Определение

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

[ а, б ] знак равно { Икс  : а ≤ Икс ≤ б }

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

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

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

Алгебра инцидентности конечномерна тогда и только тогда, когда лежащее в ее основе ЧУ-множество конечно.

Связанные понятия

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

Верхнетреугольные матрицы

Рассмотрим случай частичного порядка ≤ по любому набору S из n элементов . Мы нумеруем S как s ₁ , …, s _n , и таким образом, чтобы нумерация была совместима с порядком ≤ на S , то есть s _i ≤ s _j влечет за собой 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{otherwise }}.\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 ), где второй « µ » — это введенная классическая функция Мёбиуса в теорию чисел в XIX веке.

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

Функция Мёбиуса

$${\displaystyle \mu (S,T)=(-1)^{\left|T\setminus 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\setminus S{\text{ is a proper multiset (has repeated elements)}}\\(-1)^{\left|T\setminus S\right|}&{\text{if }}T\setminus S{\text{ is a set (has no repeated elements)}}.\end{cases}}}$$

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

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

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

Функция Мёбиуса

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

if — нормальная подгруппа группы и , в противном случае — 0. Это теорема Вейснера (1935). ${\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 обозначает инвариантную дельта-функцию с t ( S , T ) = 1 для | Т \ С | = 1 и t ( S , T ) = 0 в противном случае. Его полномочия: ${\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{\setminus }S|=n\\0&{\text{otherwise,}}\end{array}}\right.}$$

nnnнэкспоненциальных производящих функций ${\displaystyle S=T_{0}\subset T_{1}\subset \cdots \subset T_{n}=T,}$ ${\displaystyle |T_{i}{\setminus }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{\setminus }S|}.}$

Частный делитель и ряд Дирихле

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

1. Колегов, Н.А.; Маркова О.В. (август 2019). «Системы генераторов матричных алгебр инцидентности над конечными полями». Журнал математических наук . 240 (6): 783–798. дои : 10.1007/s10958-019-04396-6. ISSN  1072-3374. S2CID  198443199.
2. Питер Дубилет, Джан-Карло Рота и Ричард Стэнли: Об основах комбинаторики (VI): идея порождающей функции , Симпозиум Беркли по математике. Статист. и проб., Учеб. Шестой симпозиум по математике в Беркли. Статист. и Проб., Том. 2 (Univ. of Calif. Press, 1972), 267–318, доступно онлайн в открытом доступе.

дальнейшее чтение

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