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

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

Определение [ править ]

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

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

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

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

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

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

Связанные понятия [ править ]

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

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

Рассмотрим случай частичного порядка ≤ по любому $из n$ набору $S$ элементов . Мы нумеруем $S$ как $s 1, \dots, s n$ , и таким образом, чтобы нумерация была совместима с порядком ≤ на $S$ , то есть $s i \leq s j$ влечет за собой $i \leq j$ , что всегда возможно.

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

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

Специальные элементы [ править ]

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

\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 в базовом кольце.

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

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

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

Квадрат дзета-функции дает количество элементов в интервале:

\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 , упорядоченные по включению: Функция Мёбиуса $\mu (S,T)=(-1)^{\left|T\smallsetminus S\right|}$; всякий раз, когда S и T являются конечными подмножествами E , причем S ⊆ T , и обращение Мёбиуса называется принципом включения-исключения .; Геометрически это гиперкуб : $2^{E}=\{0,1\}^{E}.$
Натуральные числа в их обычном порядке: Функция Мёбиуса $\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-t)^{-1}=1+t+t^{2}+t^{3}+\cdots$ , что является обратным. Дельта-функция в этой алгебре инцидентности аналогично соответствует формальному степенному ряду 1.
Конечные подмультимножества некоторого мультимножества E , упорядоченные по включению: Приведенные выше три примера можно объединить и обобщить, рассмотрев мультимножество E и конечные подмультимножества S и T из E . Функция Мёбиуса $\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 соответствует мультимножеству $\{2,2,3\}.$; Это обобщает натуральные числа их обычного порядка на натуральное число, соответствующее мультимножеству из одного базового элемента и мощности, равной этому числу, например, 3 соответствует мультимножеству $\{1,1,1\}.$
Подгруппы конечной p -группы G , упорядоченные по включению: Функция Мёбиуса $\mu _{G}(H_{1},H_{2})=(-1)^{k}p^{\binom {k}{2}}$ если $H_{1}$ является нормальной подгруппой $H_{2}$ и $H_{2}/H_{1}\cong (\mathbb {Z} /p\mathbb {Z} )^{k}$ и это 0 в противном случае. Это теорема Вейснера (1935).
Разделы набора: Частично упорядочите набор всех разбиений конечного множества, сказав σ ≤ τ, если σ является более тонким разбиением, чем τ . В частности, пусть τ имеет t блоков, которые соответственно распадаются на s ₁ , ..., s _t более мелких блоков σ , что в общей сложности имеет s = s ₁ + ⋅⋅⋅ + s _t блоков. Тогда функция Мёбиуса: $\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]

Натуральные числа и обычные производящие функции [ править ]

Для посета $(\mathbb {N} ,\leq ),$ приведенная алгебра инцидентности состоит из функций $f(a,b)$ инвариант при трансляции, $f(a+k,b+k)=f(a,b)$ для всех $k\geq 0,$ так, чтобы иметь одинаковое значение на изоморфных интервалах [ a + k , b + k ] и [ a , b ]. Пусть t обозначает функцию с t ( a , a +1) = 1 и t ( a , b ) = 0 в противном случае это своего рода инвариантная дельта-функция на классах изоморфизма интервалов. Его степени в алгебре инцидентности — это другие инвариантные дельта-функции t ^н( а , а + п ) знак равно 1 и т ^н( x , y ) = 0 в противном случае. Они составляют основу приведенной алгебры инцидентности, и мы можем записать любую инвариантную функцию как $\textstyle f=\sum _{n\geq 0}f(0,n)t^{n}$ . Эти обозначения проясняют изоморфизм между приведенной алгеброй инцидентности и кольцом формальных степенных рядов. $R[[t]]$ над скалярами R, также известными как кольцо обычных производящих функций . Мы можем записать дзета-функцию как $\zeta =1+t+t^{2}+\cdots ={\tfrac {1}{1-t}},$ обратная функция Мёбиуса $\mu =1-t.$

Подмножество постоянных и экспоненциальных производящих функций [ править ]

Для булева ЧУ множества конечных подмножеств $S\subset \{1,2,3,\ldots \}$ упорядочен по включению $S\subset T$ приведенная алгебра инцидентности состоит из инвариантных функций $f(S,T),$ определено как имеющее одно и то же значение на изоморфных интервалах [ S , T ] и [ S ′, T ′] с | Т \ С | = | Т ′ \ S ′|. Опять же, пусть t обозначает инвариантную дельта-функцию с t ( S , T ) = 1 для | Т \ С | = 1 и t ( S , T ) = 0 в противном случае. Его полномочия:

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.

где сумма по всем цепочкам

S=T_{0}\subset T_{1}\subset \cdots \subset T_{n}=T,

и единственные ненулевые члены встречаются для насыщенных цепей с

|T_{i}\smallsetminus T_{i-1}|=1;

поскольку они соответствуют перестановкам n , мы получаем уникальное ненулевое значение n !. Таким образом, инвариантные дельта-функции представляют собой разделенные степени

{\tfrac {t^{n}}{n!}},

и мы можем записать любую инвариантную функцию как

\textstyle f=\sum _{n\geq 0}f(\emptyset ,[n]){\frac {t^{n}}{n!}},

где [ n ] = {1, . . . , н }. Это дает естественный изоморфизм между приведенной алгеброй инцидентности и кольцом экспоненциальных производящих функций . Дзета-функция

\textstyle \zeta =\sum _{n\geq 0}{\frac {t^{n}}{n!}}=\exp(t),

с функцией Мёбиуса:

\mu ={\frac {1}{\zeta }}=\exp(-t)=\sum _{n\geq 0}(-1)^{n}{\frac {t^{n}}{n!}}.

Действительно, это вычисление с формальным степенным рядом доказывает, что

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

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

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

Рассмотрим частично упорядоченное множество D натуральных чисел, упорядоченное по делимости , обозначаемое $a\,|\,b.$ Приведенная алгебра инцидентности состоит из функций $f(a,b)$ которые инвариантны относительно умножения: $f(ka,kb)=f(a,b)$ для всех $k\geq 1.$ (Эта мультипликативная эквивалентность интервалов является гораздо более сильным отношением, чем изоморфизм ЧУУ-множеств; например, для простых чисел p все двухэлементные интервалы [1, p ] неэквивалентны.) Для инвариантной функции f ( a , b ) зависит только от b / a , поэтому естественный базис состоит из инвариантных дельта-функций $\delta _{n}$ определяется $\delta _{n}(a,b)=1$ если b / a = n и 0 в противном случае; тогда любую инвариантную функцию можно записать $\textstyle f=\sum _{n\geq 0}f(1,n)\,\delta _{n}.$

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

(\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 . Таким образом, мы получаем изоморфизм приведенной алгебры инцидентности кольцу формальных рядов Дирихле , послав $\delta _{n}$ к $n^{-s}\!,$ так что f соответствует ${\textstyle \sum _{n\geq 1}{\frac {f(1,n)}{n^{s}}}.}$

Дзета-функция алгебры инцидентности ζ _D ( a , b ) = 1 соответствует классической дзета-функции Римана $\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}}},}$ где $\mu (n)=\mu _{D}(1,n)$ — классическая функция Мёбиуса теории чисел. Многие другие арифметические функции естественным образом возникают в приведенной алгебре инцидентности и, что эквивалентно, в терминах рядов Дирихле. Например, функция делителя $\sigma _{0}(n)$ - квадрат дзета-функции, $\sigma _{0}(n)=\zeta ^{2}\!(1,n),$ частный случай приведенного выше результата, который $\zeta ^{2}\!(x,y)$ дает количество элементов в интервале [ x , y ]; эквивалентность, ${\textstyle \zeta (s)^{2}=\sum _{n\geq 1}{\frac {\sigma _{0}(n)}{n^{s}}}.}$

Структура произведения частичного набора делителей облегчает вычисление его функции Мёбиуса. Уникальная факторизация на простые числа означает, что D изоморфно бесконечному декартову произведению. $\mathbb {N} \times \mathbb {N} \times \dots$ , с порядком, заданным путем покоординатного сравнения: $n=p_{1}^{e_{1}}p_{2}^{e_{2}}\dots$ , где $p_{k}$ это К ^й простое число, соответствует его последовательности показателей $(e_{1},e_{2},\dots ).$ Теперь функция Мёбиуса D является произведением функций Мёбиуса для фактор-ЧУ, вычисленных выше, что дает классическую формулу:

\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 соответствует декартову произведению дзета-функций факторов, вычисленному выше как ${\textstyle {\frac {1}{1-t}},}$ так что ${\textstyle \zeta _{D}\cong \prod _{k\geq 1}\!{\frac {1}{1-t}},}$ где правая часть является декартовым произведением. Применяя изоморфизм, который переводит t в k ^й фактор для $p_{k}^{-s}$ , мы получаем обычное произведение Эйлера.

См. также [ править ]

Литература [ править ]

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

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

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

Дальнейшее чтение [ править ]

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

[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, доступно онлайн в открытом доступе.

[1]

[2]