В теории порядка , области математики , алгебра инцидентности - это ассоциативная алгебра , определенная для каждого локально конечного частично упорядоченного множества и коммутативного кольца с единицей. Подалгебры, называемые приведенными алгебрами инцидентности, дают естественную конструкцию различных типов производящих функций, используемых в комбинаторике и теории чисел.
Определение
Локально конечное упорядоченное множество является один , в котором каждый замкнутый интервал
- [ a, b ] = { x : a ≤ x ≤ b }
является конечным .
Члены алгебры инцидентности - это функции f, назначающие каждому непустому интервалу [ a, b ] скаляр f ( a , b ), взятый из кольца скаляров , коммутативного кольца с единицей. На этом базовом множестве определяется точечное сложение и скалярное умножение, а «умножение» в алгебре инцидентности - это свертка, определяемая формулой
Алгебра инцидентности конечномерна тогда и только тогда, когда лежащий в основе ч.у. конечен.
Связанные понятия
Алгебра инцидентности аналогична групповой алгебре ; действительно, и групповая алгебра, и алгебра инцидентности являются частными случаями категориальной алгебры , определяемой аналогичным образом; группы и позы являются особыми видами категорий .
Верхнетреугольные матрицы
Рассмотрим случай частичного порядка ≤ над любым п - элементного множества S . Мы занумеруем S как s 1 ,…, 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]
Специальные элементы
Мультипликативным тождественным элементом алгебры инцидентности является дельта-функция , определяемая формулой
Дзета - функция из алгебры инцидентности является функция постоянной ζ ( , б ) = 1 для любого непустого интервала [ а, Ь ]. Умножение на ζ аналогично интегрированию.
Можно показать, что ζ обратима в алгебре инцидентности (относительно определенной выше свертки). (Как правило, элемент h алгебры инцидентности обратим тогда и только тогда, когда h ( x , x ) обратим для любого x .) Мультипликативная обратная дзета-функция - это функция Мёбиуса μ ( a, b ); каждое значение μ ( a, b ) является целым кратным 1 в базовом кольце.
Функцию Мёбиуса также можно определить индуктивно с помощью следующего соотношения:
Умножение на μ аналогично дифференцированию и называется инверсией Мёбиуса .
Квадрат дзета-функции подсчитывает количество элементов в интервале:
Примеры
- Положительные целые числа, упорядоченные по делимости
- Свертка, связанная с алгеброй инцидентности для интервалов [1, n ], становится сверткой Дирихле , следовательно, функция Мёбиуса равна μ ( a, b ) = μ ( b / a ), где вторая « μ » - это классическая функция Мёбиуса, введенная в теорию чисел в 19 веке.
- Конечные подмножества некоторого множества E , упорядоченные по включению
- Функция Мёбиуса есть
- всякий раз, когда S и T конечные подмножества E с S ⊆ T , и обращение Мёбиуса называется принципом включения-исключения .
- Геометрически это гиперкуб :
- Натуральные числа в обычном порядке
- Функция Мёбиуса есть
- а обращение Мёбиуса называется (обратным) разностным оператором .
- Геометрически это соответствует дискретной числовой прямой .
- Свертка функций в алгебре инцидентности соответствует умножению формальных степенных рядов : см. Обсуждение приведенных алгебр инцидентности ниже. Функция Мёбиуса соответствует последовательности (1, −1, 0, 0, 0, ...) коэффициентов формального степенного ряда 1 - t , а дзета-функция соответствует последовательности коэффициентов (1, 1, 1 , 1, ...) формального степенного ряда , что обратное. Дельта-функция в этой алгебре инцидентности аналогично соответствует формальному степенному ряду 1.
- Конечные подмножества некоторого мультимножества E , упорядоченные по включению
- Выше трех примеров могут быть объединены и обобщены с учетом мультимножеством Е, и конечные суб-мультимножествами S и Т из Е . Функция Мёбиуса есть
- Это обобщает положительные целые числа, упорядоченные по делимости на положительное целое число, соответствующее его мультимножеству простых делителей с кратностью, например, 12 соответствует мультимножеству
- Это обобщает натуральные числа с их обычным порядком с помощью натурального числа, соответствующего мультимножеству одного базового элемента, и мощности, равной этому числу, например, 3 соответствует мультимножеству
- Подгруппы конечной p -группы G , упорядоченные по включению
- Функция Мёбиуса есть
- если нормальная подгруппа а также
- в противном случае - 0. Это теорема Вейснера (1935).
- Перегородки набора
- Частично упорядочите множество всех разбиений конечного множества, сказав, что σ ≤ τ, если σ более тонкое разбиение, чем τ. В частности, пусть τ имеет t блоков, которые соответственно разбиваются на s 1 ,. . . , s t более мелких блоков σ, в котором всего s = s 1 + ··· + s t блоков. Тогда функция Мёбиуса:
Эйлерова характеристика
ЧУМ ограничен, если он имеет наименьший и наибольший элементы, которые мы называем 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 n (a, a + n) = 1 и t n (x, y) = 0 в противном случае. Они составляют основу приведенной алгебры инцидентности, и мы можем записать любую инвариантную функцию в виде. Эти обозначения проясняют изоморфизм между приведенной алгеброй инцидентности и кольцом формальных степенных рядовнад скалярами R, также известными как кольцо обычных производящих функций . Мы можем записать дзета-функцию как обратная функция Мёбиуса
Подмножество poset и экспоненциальные производящие функции
Для булевого ч.у.м. конечных подмножеств заказано включением , приведенная алгебра инцидентности состоит из инвариантных функций определены как имеющие одинаковое значение на изоморфных интервалах [S, T] и [S ', T'] с | T \ S | = | Т '\ S' |. Снова, пусть t обозначает инвариантную дельта-функцию с t (S, T) = 1 для | T \ S | = 1 и t (S, T) = 0 в противном случае. Его возможности:
где сумма по всем цепочкам и единственные ненулевые члены встречаются для насыщенных цепей с поскольку они соответствуют перестановкам n, мы получаем уникальное ненулевое значение n !. Таким образом, инвариантные дельта-функции представляют собой разделенные степени и мы можем записать любую инвариантную функцию как где [n] = {1,. . . , n}. Это дает естественный изоморфизм между приведенной алгеброй инцидентности и кольцом экспоненциальных производящих функций . Дзета-функция с функцией Мёбиуса:
Действительно, это вычисление с формальным степенным рядом доказывает, что Многие комбинаторные счетные последовательности, включающие подмножества или помеченные объекты, можно интерпретировать в терминах уменьшенной алгебры инцидентности и вычислять с использованием экспоненциальных производящих функций.
Делитель позета и ряд Дирихле
Рассмотрим ч.у.м. D натуральных чисел, упорядоченных по делимости , обозначенное как Приведенная алгебра инцидентности состоит из функций инвариантен относительно умножения, для всех (Эта эквивалентность интервалов умножением является гораздо более сильным отношением, чем изоморфизм чугуна: для простого p все двухэлементные интервалы [1, p] неэквивалентны.) Для инвариантной функции f (a, b) зависит только от b / a, поэтому естественный базис состоит из инвариантных дельта-функций определяется если b / a = n и 0 в противном случае: любая инвариантная функция может быть записана
Произведение двух инвариантных дельта-функций:
поскольку единственный ненулевой член происходит от c = na и b = mc = nma. Таким образом, мы получаем изоморфизм приведенной алгебры инцидентности к кольцу формальных рядов Дирихле , посылая к так что f соответствует
Дзета-функция алгебры инцидентности ζ D (a, b) = 1 соответствует классической дзета-функции Римана имея взаимный где - классическая функция Мёбиуса теории чисел. Многие другие арифметические функции естественным образом возникают в рамках приведенной алгебры инцидентности и, что эквивалентно, в терминах рядов Дирихле. Например, функция делителя квадрат дзета-функции, частный случай приведенного выше результата, что подсчитывает количество элементов в интервале [x, y]; эквивалентно,
Структура произведения дивизора poset облегчает вычисление его функции Мёбиуса. Уникальная факторизация на простые числа подразумевает, что D изоморфно бесконечному декартову произведению., в порядке, заданном покоординатным сравнением: , где является к - е простого числа, соответствует его последовательности показателейТеперь функция Мёбиуса D является произведением функций Мёбиуса для факторных множеств, вычисленных выше, что дает классическую формулу:
Структура произведения также объясняет классическое произведение Эйлера для дзета-функции. Дзета-функция D соответствует декартовому произведению дзета-функций факторов, вычисленных выше как чтобы где правая часть - декартово произведение. Применяя изоморфизм, который переводит t в k- м множителе в, получаем обычное произведение Эйлера.
Смотрите также
Литература
Алгебры инцидентности локально конечных множеств рассматривались в ряде работ Джан-Карло Рота, начиная с 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 для обработки функций Мебиуса в позах.
- ^ Колегов Н.А. Маркова, О.В. (август 2019). "Системы генераторов матричных алгебр инцидентности над конечными полями" . Журнал математических наук . 240 (6): 783–798. DOI : 10.1007 / s10958-019-04396-6 . ISSN 1072-3374 .
- ^ Питер Дубилет, Джан-Карло Рота и Ричард Стэнли: Об основах комбинаторики (IV): Идея производящей функции , Симптом Беркли. по математике. Статист. и вероятность. Proc. Шестой симпозиум Беркли. по математике. Статист. and Prob., Vol. 2 (Univ. Of Calif. Press, 1972), 267-318, доступно онлайн в открытом доступе
дальнейшее чтение
- Шпигель, Юджин; О'Доннелл, Кристофер Дж. (1997), Алгебры инцидентности , Чистая и прикладная математика, 206 , Марсель Деккер, ISBN 0-8247-0036-8