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

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

Определение

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

[ a, b ] = { x  : a ≤ x ≤ b }

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

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

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

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

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

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

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

Рассмотрим случай частичного порядка ≤ над любым п - элементного множества S . Мы занумеруем 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 при ≤.

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

Специальные элементы

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

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

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

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

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

${\ displaystyle \ mu (x, y) = {\ begin {case} {} \ qquad 1 & {\ text {if}} x = y \\ [6pt] \ displaystyle - \! \! \! \! \ sum _ {z \,: \, x \, \ leq \, z \, <\, y} \ mu (x, z) & {\ text {for}} x <y \\ {} \ qquad 0 & {\ текст {иначе}}. \ end {case}}}$

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

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

Примеры

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

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

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

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

$${\ Displaystyle \ му (S, T) = (- 1) ^ {\ left | T \ setminus S \ right |}}$$

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

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

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

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

$${\ displaystyle \ mu (x, y) = {\ begin {case} 1 & {\ text {if}} y = x, \\ - 1 & {\ text {if}} y = x + 1, \\ 0 & { \ text {if}} y> x + 1, \ end {case}}}$$

а обращение Мёбиуса называется (обратным) разностным оператором .

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

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

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

Выше трех примеров могут быть объединены и обобщены с учетом мультимножеством Е, и конечные суб-мультимножествами S и Т из Е . Функция Мёбиуса есть

$${\ displaystyle \ mu (S, T) = {\ begin {cases} 0 & {\ text {if}} T \ setminus S {\ text {- правильный мультимножество (имеет повторяющиеся элементы)}} \\ (- 1) ^ {\ left | T \ setminus S \ right |} & {\ text {if}} T \ setminus S {\ text {- это набор (не имеет повторяющихся элементов)}}. \ end {case}}}$$

Это обобщает положительные целые числа, упорядоченные по делимости на положительное целое число, соответствующее его мультимножеству простых делителей с кратностью, например, 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 Н_ {2} / Н_ {1} \ cong (\ mathbb {Z} / p \ mathbb {Z}) ^ {k}}$

Перегородки набора

Частично упорядочите множество всех разбиений конечного множества, сказав, что σ ≤ τ, если σ более тонкое разбиение, чем τ. В частности, пусть τ имеет t блоков, которые соответственно разбиваются на s ₁ , ..., s _t более мелких блоков σ, что в сумме имеет s = s ₁ + ··· + s _t блоков. Тогда функция Мёбиуса:

$${\ displaystyle \ mu (\ sigma, \ tau) = (- 1) ^ {st} (s_ {1} {-} 1)! \ cdots (s_ {t} {-} 1)!}$$

Эйлерова характеристика

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

Приведенные алгебры инцидентности

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

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

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

Для ч.у.м. редуцированная алгебра инцидентности состоит из функций, инвариантных относительно сдвига для всех, чтобы иметь одно и то же значение на изоморфных интервалах [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 (а, б)}$${\ Displaystyle е (а + к, Ь + к) = е (а, Ь)}$${\ displaystyle k \ geq 0,}$${\ displaystyle \ textstyle f = \ sum _ {n \ geq 0} f (0, n) t ^ {n}}$${\ Displaystyle Р [[т]]}$${\ displaystyle \ zeta = 1 + t + t ^ {2} + \ cdots = {\ tfrac {1} {1-t}},}$${\ displaystyle \ mu = 1-t.}$

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

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

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

Действительно, это вычисление с формальными степенными рядами доказывает, что многие комбинаторные счетные последовательности, включающие подмножества или помеченные объекты, могут быть интерпретированы в терминах приведенной алгебры инцидентности и вычислены с использованием экспоненциальных производящих функций. ${\ Displaystyle \ му (S, T) = (- 1) ^ {| T {\ setminus} S |}.}$

Делитель позета и ряд Дирихле

Рассмотрю ч.у.м. D натуральных чисел упорядочены по делимости , обозначается Пониженная частота алгебра состоит из функций , инвариантные относительно умножения, для всех (Это умножение эквивалентности интервалов является гораздо более сильным отношением , чем посет изоморфизм: для простого числа р, интервалы двухэлементных [ 1, p] неэквивалентны.) Для инвариантной функции

f (a, b) зависит только от b / a, поэтому естественный базис состоит из инвариантных дельта-функций, определенных, если b / a = n, и 0 в противном случае: любой инвариант функция может быть написана${\ displaystyle a | b.}$${\ Displaystyle f (а, б)}$${\ displaystyle f (ka, kb) = f (a, b)}$${\ Displaystyle к \ geq 1.}$${\ displaystyle \ delta _ {n}}$${\ Displaystyle \ дельта _ {п} (а, б) = 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 п ^ {- 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 \ му (п) = \ му _ {D} (1, п)}$ ${\ displaystyle \ sigma _ {0} (п)}$${\ Displaystyle \ sigma _ {0} (п) = \ дзета ^ {2} \! (1, п),}$${\ Displaystyle \ zeta ^ {2} \! (х, у)}$${\ textstyle \ zeta (s) ^ {2} = \ sum _ {n \ geq 1} {\ frac {\ sigma _ {0} (n)} {n ^ {s}}}.}$

Структура произведения дивизора poset облегчает вычисление его функции Мёбиуса. Уникальное разложение на простые множители следует , D изоморфна бесконечному декартову произведение , с порядком , заданным покоординатным сравнением: , где есть

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

${\ 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 {без квадрата с}} d {\ text {простые множители}} \\ 0 & {\ text {в противном случае.}} \ 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 унд 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