Полином ожерелья

В комбинаторной математике полином ожерелья , или функция подсчета ожерелья Моро, введенная К. Моро ( 1872 ), подсчитывает количество различных ожерелий из n цветных бусинок, выбранных из α доступных цветов, расположенных в цикле. В отличие от обычной задачи раскраски графов , ожерелья предполагаются апериодическими (не состоящими из повторяющихся подпоследовательностей), и считаются с точностью до вращения (вращение бусинок вокруг ожерелья считается за одно и то же ожерелье), но без переворачивания (обратного порядка бус считается другим ожерельем). Эта считающая функция также описывает размерности свободной алгебры Ли и количество неприводимых многочленов над конечным полем.

Определение

Полиномы ожерелья представляют собой семейство полиномов. $M(\alpha ,n)$ в переменной $\alpha$ такой, что

\alpha ^{n}\ =\ \sum _{d\,|\,n}d\,M(\alpha ,d).

С помощью обращения Мёбиуса они имеют вид

M(\alpha ,n)\ =\ {1 \over n}\sum _{d\,|\,n}\mu \!\left({n \over d}\right)\alpha ^{d},

где $\mu$ — классическая функция Мёбиуса .

Близкородственное семейство, называемое общим полиномом ожерелья или общей функцией подсчета ожерелья , это:

N(\alpha ,n)\ =\ \sum _{d\,|\,n}M(\alpha ,d)\ =\ {\frac {1}{n}}\sum _{d\,|\,n}\varphi \!\left({n \over d}\right)\alpha ^{d},

где $\varphi$ — это полная функция Эйлера .

Приложения

Полиномы ожерелья $M(\alpha ,n)$ и $N(\alpha ,n)$ выглядеть как:

Количество апериодических ожерелий (или, что то же самое, слов Линдона ), которые представляют собой циклические расположения n цветных бусинок, имеющих α доступных цветов. Два таких ожерелья считаются равными, если они связаны вращением (без учета отражений). Апериодическое относится к ожерельям без вращательной симметрии, имеющим n различных вращений. Соответственно, $N(\alpha ,n)$ дает количество ожерелий, включая периодические: это легко вычисляется с помощью теории Полиа .
Размерность степени n компоненты свободной алгебры Ли на α образующих («формула Витта» ^[1]), или, что то же самое, количество слов Холла длины n . Соответственно, $N(\alpha ,n)$ должна быть размерностью компоненты степени n свободной йордановой алгебры .
Число унитарных неприводимых полиномов степени n над конечным полем с α элементами (при $\alpha =p^{d}$ это высшая степень). Соответственно, $N(\alpha ,n)$ - количество примарных полиномов ( степень неприводимого).
Показатель степени в круговом тождестве : $\textstyle {1 \over 1-\alpha z}\ =\ \prod _{j=1}^{\infty }\left({1 \over 1-z^{j}}\right)^{\!M(\alpha ,j)}$ .

Хотя все эти различные типы объектов учитываются одним и тем же полиномом, их точные взаимоотношения остаются неясными. Например, не существует канонической биекции между неприводимыми полиномами и словами Линдона. ^[2] Однако существует следующая неканоническая биекция. Для любого монического неприводимого многочлена степени n над полем F с α элементами расширения Галуа его корни лежат в поле L с $\alpha ^{n}$ элементы. Можно выбрать элемент $x\in L$ такой, что $\{x,\sigma x,...,\sigma ^{n-1}x\}$ является F -базисом для L ( нормальный базис ), где σ — автоморфизм Фробениуса $\sigma y=y^{\alpha }$ . Тогда биекцию можно определить, взяв ожерелье, рассматриваемое как класс эквивалентности функций $f:\{1,...,n\}\rightarrow F$ , к неприводимому многочлену

$\phi (T)=(T-y)(T-\sigma y)\cdots (T-\sigma ^{n-1}y)\in F[T]$ для $y=f(1)x+f(2)\sigma x+\cdots +f(n)\sigma ^{n-1}x$ .

Различные циклические перестановки f , т.е. разные представители одного и того же класса эквивалентности ожерелья, приводят к циклическим перестановкам факторов $\phi (T)$ , поэтому это соответствие четко определено. ^[3]

Отношения между М и N

Полиномы для M и N легко связываются с помощью свертки Дирихле арифметических функций. $f(n)*g(n)$ , касательно $\alpha$ как константа.

Формула для М дает $n\,M(n)\,=\,\mu (n)*\alpha ^{n}$ ,
Формула для N дает $n\,N(n)\,=\,\varphi (n)*\alpha ^{n}\,=\,n*\mu (n)*\alpha ^{n}$ .
Их отношение дает $N(n)\,=\,1*M(n)$ или эквивалентно $n\,N(n)\,=\,n*(n\,M(n))$ , поскольку функция $f(n)=n$ полностью мультипликативна .

Любые два из них подразумевают третий, например:

n*\mu (n)*\alpha ^{n}\,=\,n\,N(n)\,=\,n*(n\,M(n))\quad \Longrightarrow \quad \mu (n)*\alpha ^{n}=n\,M(n)

сокращением в алгебре Дирихле.

Примеры

{\begin{aligned}M(1,n)&=0{\text{ if }}n>1\\[6pt]M(\alpha ,1)&=\alpha \\[6pt]M(\alpha ,2)&={\tfrac {1}{2}}(\alpha ^{2}-\alpha )\\[6pt]M(\alpha ,3)&={\tfrac {1}{3}}(\alpha ^{3}-\alpha )\\[6pt]M(\alpha ,4)&={\tfrac {1}{4}}(\alpha ^{4}-\alpha ^{2})\\[6pt]M(\alpha ,5)&={\tfrac {1}{5}}(\alpha ^{5}-\alpha )\\[6pt]M(\alpha ,6)&={\tfrac {1}{6}}(\alpha ^{6}-\alpha ^{3}-\alpha ^{2}+\alpha )\\[6pt]M(\alpha ,p)&={\tfrac {1}{p}}(\alpha ^{p}-\alpha )&{\text{ if }}p{\text{ is prime}}\\[6pt]M(\alpha ,p^{N})&={\tfrac {1}{p^{N}}}(\alpha ^{p^{N}}-\alpha ^{p^{N-1}})&{\text{ if }}p{\text{ is prime}}\end{aligned}}

Для $\alpha =2$ , начиная с нулевой длины, они образуют целочисленную последовательность

1, 2, 1, 2, 3, 6, 9, 18, 30, 56, 99, 186, 335, ... (последовательность A001037 в OEIS )

Личности

Полиномы подчиняются различным комбинаторным тождествам, данным Метрополисом и Ротой:

M(\alpha \beta ,n)=\sum _{\operatorname {lcm} (i,j)=n}\gcd(i,j)M(\alpha ,i)M(\beta ,j),

где НОД — наибольший общий делитель , а НОД — наименьшее общее кратное . В более общем смысле,

M(\alpha \beta \cdots \gamma ,n)=\sum _{\operatorname {lcm} (i,j,\ldots ,k)=n}\gcd(i,j,\cdots ,k)M(\alpha ,i)M(\beta ,j)\cdots M(\gamma ,k),

что также подразумевает:

M(\beta ^{m},n)=\sum _{\operatorname {lcm} (j,m)=nm}{\frac {j}{n}}M(\beta ,j).

Ссылки

^ Лотер, М. (1997). Комбинаторика слов . Энциклопедия математики и ее приложений. Том. 17. Перрен, Д.; Ройтенауэр, К.; Берстель, Дж.; Пин, Дж. Э.; Пирилло, Г.; Фоата, Д.; Сакарович Дж.; Саймон, И.; Шютценбергер, член парламента; Шоффрут, К.; Кори, Р.; Линдон, Роджер; Рота, Джан-Карло. Предисловие Роджера Линдона (2-е изд.). Издательство Кембриджского университета . стр. 79, 84. ISBN. 978-0-521-59924-5 . МР 1475463 . Збл 0874.20040 .
^ Эми Глен, (2012) Комбинаторика слов Линдона , Мельбурнский разговор
^ Адальберт Кербер, (1991) Алгебраическая комбинаторика через действия конечных групп , [1]

Моро, К. (1872), «О различных круговых перестановках» , Nouvelles Annales de Mathématiques , Série 2 (на французском языке), 11 : 309–31, JFM 04.0086.01
Метрополис, Северная Каролина ; Рота, Джан-Карло (1983), «Векторы Витта и алгебра ожерелья», Успехи в математике , 50 (2): 95–125, doi : 10.1016/0001-8708(83)90035-X , ISSN 0001-8708 , МР 0723197 , Збл 0545.05009
Ройтенауэр, Кристоф (1988). «Круговые слова и неприводимые полиномии». Энн. наук. Квебек . 12 (2): 275–285.

[L7984-1] Лотер, М. (1997). Комбинаторика слов . Энциклопедия математики и ее приложений. Том. 17. Перрен, Д.; Ройтенауэр, К.; Берстель, Дж.; Пин, Дж. Э.; Пирилло, Г.; Фоата, Д.; Сакарович Дж.; Саймон, И.; Шютценбергер, член парламента; Шоффрут, К.; Кори, Р.; Линдон, Роджер; Рота, Джан-Карло. Предисловие Роджера Линдона (2-е изд.). Издательство Кембриджского университета . стр. 79, 84. ISBN. 978-0-521-59924-5 . МР 1475463 . Збл 0874.20040 .

[2] Эми Глен, (2012) Комбинаторика слов Линдона , Мельбурнский разговор

[3] Адальберт Кербер, (1991) Алгебраическая комбинаторика через действия конечных групп , [1]

[1]

[2]

[3]