Аннотация:
Каждому частично упорядоченному множеству $(X, \preccurlyeq)$ мы сопоставляем квадратную матрицу $M^{X}$, матричные элементы которой индексируются парой полных порядков на $X$, совместимых с $\preccurlyeq$. Каждый матричный элемент $(M^{X})_{PQ}$ – это формальная переменная, определяемая пьедесталом полного порядка $Q$ относительно полного порядка $P$. Мы доказываем, что все собственные значения матрицы $M^{X}$ являются $\mathbb{Z}$-линейными комбинациями этих переменных.
Ключевые слова:
частично упорядоченное множество (посет), пьедестал, фильтр, диаграмма Юнга.
Работа Р. Кеньона выполнена при финансовой поддержке NSF, грант № DMS-1940932, и Simons Foundation, грант № 327929. Работа В. Савина выполнена при поддержке NSF, грант № DMS-2101491, и Sloan Research Fellowship. Работа С. Шлосмана выполнена при поддержке Российского научного фонда, грант № 23-10-00150.
Поступило в редакцию: 15.12.2023 Исправленный вариант: 20.02.2024 Принята в печать: 14.03.2024
Пусть $X=\{ \alpha_{1},\dots ,\alpha_{n}\} $ – это посет, т. е. частично упорядоченное множество, с частичным порядком $\preccurlyeq$. Линейным расширением $P$ частичного порядка $\preccurlyeq$ называется биекция $P\colon X\to[1,\dots,n]$ такая, что для любой пары элементов $\alpha_{i},\alpha_{j}$ такой, что $\alpha_{i}\preccurlyeq\alpha_{j}$, выполняется соотношение $P(\alpha_{i}) \leqslant P(\alpha_{j})$.
Пусть $P,Q$ – два линейных расширения $\preccurlyeq$. Скажем, что на месте $Q^{-1}(k) \in X$ имеет место $(P,Q)$-конфликт (или, в терминологии Стенли, $(P,Q)$-спуск, [9]), если
По определению на позиции $Q^{-1}(1) $ конфликта (т. е. $(P,Q)$-конфликта) не имеется. Сопоставим каждой паре $P,Q$ функцию $\varepsilon_{PQ}\colon \{ 1,\dots,n-1\} \to\{ 0,1\}$:
Отметим, что для некоторых пар $(P,Q) \neq(P,Q') $ функции $\varepsilon_{PQ}$, $\varepsilon_{PQ'}$ могут совпадать (см. п. 4.3).
Рассмотрим множество $\mathcal{E}=\{\varepsilon\colon \{ 1,\dots,n-1\} \to\{ 0,1\}\} $ из $2^{n-1}$ всевозможных функций $\varepsilon$ и сопоставим каждой из них соответствующую формальную переменную $a_{\varepsilon}$. Сопоставим каждому посету $X$ матрицу $M^{X}$, матричные элементы которой занумерованы парами $(P,Q) $ и задаются соотношением $(M^{X})_{PQ}=a_{\varepsilon_{PQ}}$.
К примеру, возьмем посет $(X,\preccurlyeq) $ с тремя элементами и одним соотношением $X=\{\{u,v,w\},\,u<v\}$. Частичный порядок $\preccurlyeq$ допускает три линейных расширения: $u<v<w$, $u<w<v$ и $ w<u<v$. Пусть $P$ – это порядок $u<v<w$, а $Q$ – порядок $u<w<v$. Тогда $\varepsilon _{PQ}=(0,1)$, так как $2$ не является спуском (ибо $u<v$ и по упорядочению $Q$, и по упорядочению $P$), а $3$ – это спуск (так как $w<v$ по $Q$, но не по $P$). Соответствующая матрица $M^{X}$ такова:
Ее собственные значения $a_{00}-a_{01}$, $a_{00}-a_{10}$ и $a_{00}+a_{01}+a_{10}$ являются целочисленными линейными комбинациями ее матричных элементов. Один из нас (О. В. Огиевецкий) на основе компьютерных экспериментов высказал гипотезу, что такое явление имеет место для любого посета $X$. Эту гипотезу мы и доказываем в настоящей работе.
Теорема 1. Для произвольного посета $X$ его матрица $M^{X}$ невырождена, а ее собственные значения суть целочисленные линейные комбинации переменных $a_{\varepsilon}$.
Здесь имеется в виду невырожденность над полем рациональных функций от матричных элементов.
Матрицы $M^{X}$ были введены в работе [5]. Там доказано, что сумма матричных элементов в каждой строке $\sum_{Q}(M^{X})_{PQ}$ одна и та же, т. е. не зависит от $P$. Другими словами, матрица $M^{X}$ является стохастической (с точностью до нормировки), а ее главное собственное значение равно
Эти суммы названы в [5] “пьедестальными полиномами”. Они входят в выражения для производящих функций числа монотонных функций $f\colon X\to\{0,1, 2,\dots \} $ (например, для производящих функций числа плоских разбиений, числа пространственных разбиений и т. п.):
Необходимые факты о пьедесталах и пьедестальных полиномах помещены в § 4.
Основной инструмент нашего доказательства – это полугруппы фильтров $M_{F}^{X}$, которые мы рассмотрим в § 2. Они появились в работах [1], [3], где изучались их спектральные свойства. Часть доказательства теоремы 1 может быть получена с помощью доказательств теорем 1, 2 из статьи [1]. Однако наше доказательство короче и проще.
В § 2 содержатся общие сведения о посетах, а в § 3 приводится доказательство.
§ 2. Полугруппа фильтров
Полугруппа фильтров будет введена в конце этого параграфа. Ее проще определить геометрически как полугруппу граней расположения гиперплоскостей, с которой мы и начнем.
Пусть $f'$, $f''$ – две грани конуса $A(X)=A(X,\preccurlyeq)$. (Это могут быть и камеры конуса, т. е. грани максимальной размерности). Определим грань $f=f''(f') \in A(X) $ – или произведение граней $f''f'$ – следующим образом: выберем пару точек $x'\in f'$, $x''\in f''$ в общем положении, и пусть $s_{x'x''}\colon [ 0,1] \to\mathbb{R}^{n}$ – отрезок, их соединяющий, $s_{x'x''}(0)=x'$, $s_{x'x''}(1)=x''$. Рассмотрим грань $f\in A(X)$, в которой лежат все точки $s_{x'x''}(1-\varepsilon) $ нашего отрезка при достаточно малых значениях $\varepsilon>0$. Такая грань существует в силу выпуклости $A(X)$. По определению $f''(f')=f$. Отметим, что если $f''$ – камера, то $f''f'=f''$.
Определенное таким образом произведение граней ассоциативно. Отметим для полноты, что полугруппы $A(X,\preccurlyeq) $ являются “лево-регулярными полосками” (left-regular bands); см. [6].
Утверждение 3. Для любых граней $f,g,h\in A(X,\preccurlyeq) $ имеем
(Мы записываем по уравнению для каждого этажа $F$, содержащего по крайней мере два элемента $X$.) Таким образом, возникает взаимно однозначное соответствие между фильтрами и гранями. Фильтры максимального ранга $n$, т. е. линейные расширения частичного порядка $\preccurlyeq$, отвечают камерам.
Соответствующее произведение фильтров выглядит так: если $F'$, $F''$ – пара фильтров на $X$, то фильтр $F=F''F'$ на $X$ – это единственный фильтр, удовлетворяющий соотношениям:
В самом деле, пусть $f',f''$ – две грани, соответствующие фильтрам $F',F''$, и в них выбраны точки $x',x''$ общего положения.
То обстоятельство, что $F''(u) <F''(v)$, означает, что $x_{u}''<x_{v}''$. Но точка $s_{x'x''}(1-\varepsilon) $ близка к $x''$ и, стало быть, $[ s_{x'x''}(1-\varepsilon) ]_{u}<[s_{x'x''}(1-\varepsilon) ]_{v}$ при достаточно малом $\varepsilon$.
Если же $F''(u)=F''(v)$, а $F'(u) <F'(v) $, то $x_{u}''=x_{v}''$, а $x'_{u}<x_{v}'$. А так как отображение $s_{x'x''}\colon [0,1] \to\mathbb{R}^{n}$ линейно, то для всех $t<1$ мы имеем $[ s_{x'x''}(t) ]_{u}<[s_{x'x''}(t) ]_{v}$.
Пусть $F$ – фильтр на $X$, а $P$ – фильтр ранга $n$, т. е. линейный порядок на $X$. Тогда фильтр $FP$ – тоже фильтр ранга $n$. Рассмотрим квадратную матрицу $M_{F}^{X}=\|(M_{F}^{X})_{P,Q}\|$, где $P,Q$ – линейные порядки на $X$:
где матричные элементы матриц $B_{X,\varepsilon}$ – это $0$ или $1$.
Для каждой функции $\varepsilon$ определим число $r(\varepsilon)=1+\sum_{j=1}^{n-1}\varepsilon(j)$ и разобьем отрезок $\{ 1,\dots,n\} $ на $r(\varepsilon) $ последовательных отрезков:
где значения $c_{1}+1$, $c_{1}+c_{2}+1$, $\dots$, $c_{1}+\dots +c_{r(\varepsilon) }+1$ – это все те точки, в которых функция $\varepsilon$ равна $1$.
Для набора $c_{1},\dots,c_{r}$ натуральных чисел, дающих в сумме $n$, oбозначим через $\mathcal{F}_{c_{1},\dots,c_{r}}$ множество всех фильтров $F\colon X\to[ 1,2,\dots,r] $ таких, что $|F^{-1}(i)|=c_{i}$ для всех $i=1,\dots,r$.
Лемма 4. Предположим, что матрица $B_{X,\varepsilon}$ не равна нулю, а функция $\varepsilon$ имеет параметры $r$ и $c_{1},\dots,c_{r}$. Тогда справедлива следующая формула включения-исключения:
где суммы берутся по всевозможным склейкам соседних сегментов индексов $c_{i}$, а знаки есть $(-1)^{\#\text{склейки}}$.
Доказательство. В самом деле, рассмотрим порядок $Q$ из строки $P$, который наличествует в левой части. Он согласован с порядком $P$ на первых $c_{1}-1$ позициях, противоречит порядку $P$ на следующей позиции, опять согласован с $P$ на следующих $c_{2}-1$ позициях, снова противоречит $P$ на одной позиции и т. д. В то же время порядок $Q$ из строки $P$ из первого слагаемого правой части (5) согласован с $P$ на первых $c_{1}-1$ позициях, противоречит или не противоречит ему на следующей позиции, опять согласован с $P$ на следующих $c_{2}-1$ позициях, снова противоречит или не противоречит $P$ на одной позиции и т. д. Стало быть, следует удалить все те порядки $Q$, которые согласованы с порядком $P$ на первых $c_{1}-1$ позициях, потом согласованы на следующей позиции и на следующих $c_{2}-1$ позициях и т. д.
Примеры операторов $M_{F}^{X}$ приведены в п. 4.3. $\square$
3.2. Одновременное приведение матриц $M_{F}^{X}$ к верхнетреугольному виду
Пусть $X=\{ \alpha_{1},\dots,\alpha_{n}\} $ – посет с частичным порядком $\preccurlyeq$. Обозначим через $\mathrm{Tot}_{X}$ множество всех линейных расширений порядка $\preccurlyeq$. Размер наших матриц $M_{F}^{X}$ – это $|\mathrm{Tot}_{X}| \times| \mathrm{Tot}_{X}| $. Если забыть о частичном порядке на $X$, то возникнет посет $\overline{X}$ с $|\mathrm{Tot}_{\overline{X}}|=n!$. Очевидно, что матрица $M_{F}^{X}$ – подматрица $M_{F}^{\overline{X}}$. Предположим, что эта подматрица занимает (после перенумерации) левый верхний угол. Мы утверждаем, что справа от нее все матричные элементы матрицы $M_{F}^{\overline{X}}$ равны нулю, т. е. $M_{F}^{X}$ – это блок матрицы $M_{F}^{\overline{X}}$. В самом деле, каждая строка матрицы $M_{F}^{\overline{X}}$ содержит ровно одну единицу, а остальные элементы – нули. Но каждая строка $M_{F}^{X}$ уже имеет одну единицу, и, стало быть, достаточно установить целочисленность спектра матрицы $M_{F}^{\overline{X}}$.
Исходный посет $X$ больше не появится до конца доказательства; мы будем работать только с “тотально неупорядоченным” посетом $\overline{X}$. Одновременная приводимость матриц $M_{F}^{\overline{X}}$ к верхнетреугольному виду может быть извлечена из работ [1], [3]. Наше доказательство заметно короче.
А именно, рассмотрим матрицы $N_{F}^{\overline{X}}$ большего размера $2^{n(n-1) /2}$. Здесь $F$ – по-прежнему фильтр на $\overline{X}$, а строки и столбцы $N_{F}^{\overline{X}}$ занумерованы турнирами между элементами множества $\overline{X}$. Турнир – это произвольный выбор порядка $\preccurlyeq$ на каждой паре $i\neq j$ элементов из $\overline{X}$.
По турниру $\preccurlyeq$ и фильтру $F$ на $\overline{X}$ определим турнир $\preccurlyeq_{F}$ так:
1) если $F(i)=F(j)$, то $i\preccurlyeq_{F}j$ тогда и только тогда, когда $i\preccurlyeq j$;
Очевидно, что всякий линейный порядок является турниром, и поэтому наши матрицы $M_{F}^{\overline{X}}$ являются блоками матриц $N_{F}^{\overline{X}}$, а стало быть, достаточно изучать только их.
Заметим теперь, что матрицы $N_{F}^{\overline{X}}$ представляют собой тензорные произведения $n(n-1) /2$ матриц размера $2\times 2$, соответствующих всем парам $(i,j)$, так как турнирный порядок $\preccurlyeq$ назначается каждому ребру независимо. А так как тензорное произведение верхнетреугольных матриц есть снова верхнетреугольная матрица, то наше утверждение достаточно проверить для фильтров и турниров в случае $n=| \overline{X}|=2$.
Неупорядоченное множество $\overline{X}$, состоящее из двух различных элементов, $\overline{X}=\{ 1,2\}$, допускает три фильтра и два турнира. Три соответствующих матрицы $N_{F}^{\overline{X}}$ – это
Это сопряжение продолжается естественным образом на тензорные произведения. $\square$
Замечание 5. Вернемся к определению (4) матриц $B_{X,\varepsilon}$: для посета $X$ матрицы $\{B_{X,\varepsilon}\}$, где $\varepsilon\in\{0,1\}^{\{1,\dots,n-1\}}$, определяются с помощью равенства $M^{X}=\sum_{\varepsilon }a_{\varepsilon}B_{X,\varepsilon}$. Пусть $\mathcal{L}(X)$ – алгебра Ли, порожденная матрицами $\{B_{X,\varepsilon}\}$. Наше доказательство показывает, что алгебра $\mathcal{L}(X)$ разрешима.
Замечание 6. Пусть $\Phi_{T}$ – алгебра функций на множестве $\mathrm{Tour}_{\overline{X}}$ турниров, рассматриваемом как множество вершин $n(n-1)/2$-мерного куба в $\mathbb{R}^{n(n-1)/2}$. На ней имеется возрастающая фильтрация
состоящая из ограничений полиномов степени $\leqslant0$, степени $\leqslant1$, $\dots$ на вершины куба. Эта фильтрация строго мультипликативна в том смысле, что
Из сказанного выше следует, что все операторы $N_{F}^{\overline{X}}$ сохраняют эту фильтрацию и коммутируют на ассоциированном градуированном пространстве $\bigoplus_{k}\Phi_{T}^{\leqslant k}/\Phi_{T}^{\leqslant k-1}$.
Ограничивая функции с $\Phi_{T}$ на подмножество $\mathrm{Tot}_{X} \subset\mathrm{Tour}_{\overline{X}}$, мы снова получаем строго мультипликативную фильтрацию на алгебре $\Phi_{X}:=\mathbb{R}^{\mathrm{Tot}_{X}}$ функций $\mathrm{Tot}_{X}$, сохраняемую всеми операторами $M_{F}^{X}$, где индекс $F$ пробегает множество фильтров на $X$.
§ 4. Дополнения
4.1. Пьедесталы
Как и ранее, пусть $X$ – посет с частичным порядком $\preccurlyeq$, а $P,Q$ – пара полных порядков на $X$, совместимых с $\preccurlyeq$. Рассмотрим функцию $q_{PQ}$ на $X$, задаваемую соотношением
– это взаимно однозначное соответствие, что мы установим ниже.
Имеется естественное отображение $\mathcal{E}_{P}\to\mathcal{E}$, сопоставляющее каждому пьедесталу $q_{PQ}$ его “дискретную производную” $\varepsilon_{PQ}$.
Пьедесталы были введены в работе [7] в следующем контексте. Рассмотрим множество $\mathcal{P}=\mathcal{P}_{X}$ всех неотрицательных целочисленных неубывающих функций $p$ на $X$. Пусть $v(p) $ – это “объем” функции $p$:
т. е. $g_{k}$ – это количество неубывающих функций $p$ объема $v(p)=k$. Например, если $X$ – это множество $X_{n}=[1,2,\dots,n] $ с линейным порядком, то
где $\pi(i)\geqslant0$, $\pi(i) \leqslant\pi(i+1)$. Пусть $\mathcal{Y}_{n}$ – множество всех таких разбиений $\pi$ (т. е. диаграмм Юнга).
Чтобы записать формулу для функции $G_{X}$ для произвольного посета $X$, нужны пьедесталы. А именно, выберем какое-то упорядочение $P$ на $X$, рассмотрим все пьедесталы $q_{PQ}$, и пусть
(ср. с (3)). Из соотношения (8), в частности, следует, что полином $\Pi_{P}(t) $ не зависит от $P$ и может быть обозначен $\Pi_{X}(t)$. Равенство (8) вытекает из существования биекции $b\colon \mathcal{P}_{X}\to \mathcal{E}_{P}\times\mathcal{Y}_{n}$ между множеством $\mathcal{P}_{X}$ неубывающих функций и прямым произведением $\mathcal{E}_{P}\times\mathcal{Y}_{n}$, сохраняющим объем. А именно, пьедесталу $q_{PQ}$ и разбиению $\pi$ она сопоставляет функцию $p$ на $X$ по формуле
Ясно, что это – неубывающая функция на $X$. Проверка того, что $b$ – биекция, содержится в [7], см. соотношение (46) и следующее за ним определение обратного отображения $b^{-1}$. Из биективности отображения $b$ следует, в частности, что для любого фиксированного $P$ все пьедесталы $q_{PQ}$ различны.
Когда $X$ – это (двумерная) диаграмма Юнга, функции $p\in\mathcal{P}_{X}$ называются обратными плоскими разбиениями. Для их производящей функции $G_{X}$ известна другая формула – знаменитая формула Стенли [9]
где $h(\alpha) $ – это длина крюка клетки $\alpha\in X$. Когда $X$ – прямоугольник, это формула МакМагона. Мы видим, тем самым, что в случае, когда $X$ – это диаграмма Юнга, в правой части соотношения (8) имеют место многочисленные сокращения. Прямая проверка показывает, что если $X$ – трехмерная диаграмма Юнга, аналогичных сокращений в формуле (8) не происходит, и, стало быть, аналога формулы Стенли в размерности 3 не существует.
4.2. Пьедестальные полиномы
Тот факт, что функция $\Pi_{P}(t) $ (см. (7)) зависит только от посета $X$, а не от порядка $P$ на $X$, имеет следующее обобщение. Вместо того чтобы сопоставить пьедесталу его объем, сопоставим пьедесталу $q_{PQ}$ моном
тоже не зависит от порядка $P$, поэтому его корректно обозначить как $\mathfrak{h}_{X}(x_{1}, x_{2},x_{3},\dots)$. Иными словами, матрица $\widetilde{M}^{X}$ (размера $| \mathrm{Tot}_{X}|\times| \mathrm{Tot}_{X}| $) с матричными элементами
является стохастической: вектор $(1,1,\dots,1) $ – ее правый собственный вектор с собственным значением $\mathfrak{h}_{X}(x_{1},x_{2},x_{3},\dots)$.
Заменяя мономы $m_{PQ}(x_{1},x_{2},x_{3},\dots) $ переменными $a_{\varepsilon_{PQ}}$, мы получаем из $\widetilde{M}^{X}$ нашу матрицу $M^{X}$.
Замечание 7. Как мы только что отметили, строки матрицы $M^{X}$ отличаются друг от друга перестановкой матричных элементов. Заманчиво поэтому расмотреть множество перестановок $\pi_{PP'}\in S_{|\mathrm{Tot}_{X}|}$, превращающих строку $P$ в $P'$. К сожалению, строки матрицы $M^{X}$ могут содержать повторяющиеся элементы, поэтому пeрестановки $\pi_{PP'}$ определены неоднозначно.
4.3. Примеры
В этом пункте мы рассмотрим несколько примеров, где посеты $X$ соответствуют разбиениям, т. е. диаграммам Юнга. Сначала мы перечисляем полные порядки на них, т. е. стандартные таблицы Юнга, а потом выписываем соответствующую пьедестальную матрицу, строки и столбцы которой занумерованы стандартными таблицами Юнга в перечисленном порядке.
Во всех рассмотренных нами случаях пьедестальные матрицы оказываются диагонализуемыми в общей точке. Однако для специальных значений переменных пьедестальная матрица может иметь нетривиальные жордановы блоки. Минимальный пример такого явления возникает в случае разбиения $(3,1)$. По существу это тот же пример, что и перед основной теоремой, с пьедестальной матрицей (2), так как клетка $(1,1)$ является первой в любом полном порядке и может быть опущена.
Достаточно рассмотреть частичную спецификацию $a_{10}\mapsto -2a_{01}$. Жорданова форма имеет вид
где символ $(y)_{k}$ означает, что кратность собственного значения $y$ равна $k$.
В случае посета $(3,1,1)$ имеется вырождение: символ $a_{3}$ появляется в каждой строке матрицы $A_{(3,1,1)}^{\phi}$ дважды. Соответствующий моном равен $x_{1}^{3}x_{2}^{2}$, поэтому в разложение матрицы $B_{a_{3}}$ входят фильтры из семейства $\mathcal{F}_{3,2}$, каковых имеется три (мы используем стандартные матричные обозначения, элемент $(i,j)$ находится на пересечении строки $i$ и столбца $j$):
Часть настоящей работы была выполнена в Институте высших исследований (IHES) во время программы, посвященной столетию модели Изинга в мае–июне 2022 г. Р. Кеньон, М. Концевич и С. Шлосман благодарны организаторам программы за создание прекрасной рабочей атмосферы.
Мы благодарим профессора П. Дьякониса и профессора Р. Стенли за ценные комментарии.
Литература
1.
P. Bidigare, P. Hanlon, D. Rockmore, “A combinatorial description of the spectrum for the Tsetlin library and its generalization to hyperplane arrangements”, Duke Math. J., 99:1 (1999), 135–174
2.
K. S. Brown, “Semigroups, rings, and Markov chains”, J. Theoret. Probab., 13:3 (2000), 871–938
3.
K. S. Brown, P. Diaconis, “Random walks and hyperplane arrangements”, Ann. Probab., 26:4 (1998), 1813–1854
4.
G. A. Dorpalen-Barry, Cones of hyperplane arrangements, Thesis (Ph.D.), Univ. of Minnesota, 2021, 123 pp.
5.
О. В. Огиевецкий, С. Б. Шлосман, “Плоские разбиения и их пьедестальные многочлены”, Матем. заметки, 103:5 (2018), 745–749; англ. пер.: O. V. Ogievetsky, S. B. Shlosman, “Plane partitions and their pedestal polynomials”, Math. Notes, 103:5 (2018), 793–796
6.
F. V. Saliola, “The face semigroup algebra of a hyperplane arrangement”, Canad. J. Math., 61:4 (2009), 904–929
7.
С. Б. Шлосман, “Конструкция Вульфа в статистической механике и комбинаторике”, УМН, 56:4(340) (2001), 97–128; англ. пер.: S. Shlosman, “The Wulff construction in statistical mechanics and combinatorics”, Russian Math. Surveys, 56:4 (2001), 709–738
8.
N. J. A. Sloane, The on-line encyclopedia of integer sequenceshttp://www.oeis.org/
9.
Р. Стенли, Перечислительная комбинаторика, Мир, М., 1990, 440 с. ; пер. с англ.: R. P. Stanley, Enumerative combinatorics, т. 1, Cambridge Stud. Adv. Math., 49, 2nd ed., Cambridge Univ. Press, Cambridge, 2012, xiv+626 с.
Образец цитирования:
Ричард Кеньон, Максим Концевич, Олег Огиевецкий, Космин Похоата, Вилл Савин, Семен Шлосман, “Удивительная целочисленность собственных значений”, Функц. анализ и его прил., 58:2 (2024), 100–114; Funct. Anal. Appl., 58:2 (2024), 182–194