Applying computer algebra systems to study Chaundy-Bullard identities for the vector partition function with weight

Full Text

1. Введение и постановка задачи

Методы компьютерной алгебры показали свою эффективность в исследовании широкого класса задач из теории многомерных разностных уравнений (см., например, [1]–[7]). В данной работе предложен алгоритм получения тождеств Чаунди–Булларда для функции векторного разбиения с весом с использованием системы компьютерной алгебры Maple.

Для целых неотрицательных чисел m,n обозначим

$P_{m,n}\left(x\right)={(1-x)}^{n+1}\sum _{k=0}^m\left(\begin{array}{c}n+k\\ k\end{array}\right)x^k.$

Элегантное соотношение

$P_{m,n}\left(x\right)+P_{n,m}(1-x)=\mathrm{1,}$ (1.1)

известное как тождество Чаунди–Булларда, было получено в работе [8] в 1960 г.

Подробный обзор тождества Чаунди–Булларда и различных подходов к его доказательству приведен в [9]. В [10] подобные тождества были получены с использованием метода производящих функций и свойств композиции Адамара кратных степенных рядов (подробнее о многомерном аналоге композиции Адамара см. [11]). В [12] отмечалось, что Монмор получил это тождество в 1713 г., затем Муавр обнаружил его в 1738 г. и Геринг применял его в 1868 г. Тождество Чаунди–Булларда появляется в теории рекурсивых цифровых фильтров (см. [13]), в теории вейвлетов (см. [14]), в теории гипергеометрических функций Гаусса (см. [15]). В работе [16] соотношение (1.1) называется тождеством Добеши в случае m = n.

В настоящее время появилось немало исследований по данной тематике. Например, в 2023 г. в работе [17] несколько тождеств с использованием символа Похгаммера были доказаны при помощи тождества Чаунди–Булларда. В 2016 г. в работе [18] были представлены два новых доказательства данного тождества на основе дифференцирования суммы ряда бесконечной геометрической прогрессии в связи с исследованием комбинаторной задачи о справедливом разделе ставки. В 2014 г. в работе [19] были представлены однородная форма тождества Чаунди–Булларда и ее очевидное обобщение на случай n переменных. Некоторые полезные соотношения, связанные с тождеством Чаунди–Булларда, приведены в работе [20].

Обозначим $\mathbb{Z},{\mathbb{Z}}_{⩾},ℂ$ — множества целых, целых неотрицательных и комплексных чисел соответственно, ${\mathbb{Z}}^n=\mathbb{Z}\times \dots \times \mathbb{Z},$ ${\mathbb{Z}}_{⩾}^n={\mathbb{Z}}_{⩾}\times \cdots \times {\mathbb{Z}}_{⩾}.$ Функция векторного разбиения PΔ(λ) является числом представлений вектора λ через набор заданных векторов $\Delta =\{{\alpha }^1,\dots ,{\alpha }^N\}\subset {\mathbb{Z}}^n$ с целыми неотрицательными коэффициентами. Данная функция изучалась в [21] и [22] в связи с исследованиями рациональных многогранников. Функцию векторного разбиения можно также рассматривать как число целых неотрицательных решений диофантова уравнения Ax = λ, где A – матрица, стобцы которой являются векторами из набора Δ (см. [23]):

$P_{\Delta }\left(\lambda \right)=\sum _{Ax=\lambda ,x\in {\mathbb{Z}}_{⩾}^n}1.$

Аналоги функции векторного разбиения в целочисленном конусе исследовались в [24] и [25] в связи с обобщением теоремы Римана–Роха и теории индексов трансверсальных эллиптических операторов. Структурная теорема для функции векторного разбиения и эффективные инстументы для ее вычисления были даны в работе [26].

Пусть $\phi : {\mathbb{Z}}_{⩾}^n\to ℂ$. В работе [27] была определена функция векторного разбиения с весом φ

$P_{\Delta }(\lambda ;\phi )=\sum _{Ax=\lambda ,x\in {\mathbb{Z}}_{⩾}^n}\phi \left(x\right)$

и доказано тождество Чаунди–Булларда для функции векторного разбиения с весом. Отметим, что в данной работе были получены многомерные разностные уравнения, решения которых являются функциями векторного разбиения с весом $P_{\Delta }(\lambda ;\phi ),$ и найдены их производящие функции (подробнее см. [28], [29], [30]).

2. Тождество Чаунди–Булларда

Пусть $\Delta =\{{\alpha }^1,\dots ,{\alpha }^N\}\subset {\mathbb{Z}}^n$ и решеточный конус

$K=\left\{\begin{array}{c}\lambda \in {\mathbb{Z}}^n:\lambda =x_1{\alpha }^1+\cdots +x_N{\alpha }^N,\\ x_1,\dots ,x_N\in {\mathbb{Z}}_{⩾}\end{array}\right\}$

– заостренный, то есть такой, для которого выполняется условие $\lambda \in K$ и $-\lambda \in K$, если и только если λ = 0. Пусть $A=[{\alpha }^1,\dots ,{\alpha }^N]$ — матрица из n строк и N столбцов, составленная из векторов-столбцов $\{{\alpha }^1,\dots ,{\alpha }^N\}$. Для произвольной функции целочисленных аргументов $\phi :{\mathbb{Z}}_{⩾}^N\to ℂ$ определим функцию векторного разбиения с весом φ(x) следующим образом:

$P_A(\lambda ;\phi )=\sum _{\begin{array}{c}x:Ax=\lambda \\ x\in {\mathbb{Z}}_{⩾}^N\end{array}}\phi \left(x\right),\lambda \in {\mathbb{Z}}^n.$

При φ(x) ≡ 1 данная функция совпадает с классической функцией векторного разбиения P_A.

Обозначим наборы вектор-столбцов ${\Delta }_j=\Delta \backslash \left\{{\alpha }^j\right\},$ $j=\mathrm{1,}\dots ,N$ матрицы $A_j,j=\mathrm{1,}\dots ,N,$ составленные из таких наборов соответственно:

$A_j=[{\alpha }^1,\dots ,{\alpha }^{j-1},{\alpha }^{j+1},\dots ,{\alpha }^N]$

и заостренные решеточные конусы

$K_j=\left\{\begin{array}{l}\nu \in {\mathbb{Z}}^n:\nu =y_1{\alpha }^1+\dots \left[j\right]\dots +\\ +y_N{\alpha }^N,y_1,\dots ,\left[j\right],\dots ,y_N\in {\mathbb{Z}}_{⩾}\end{array}\right\}.$

Также обозначим $c^x=c_1^{x_1}\cdots c_N^{x_N}$, $c^{x+e^j}=c_1^{x_1}\cdots c_j^{x_j+1}\cdots c_N^{x_N}$, $\left|x\right|=x_1+\cdots +x_n$.

Тогда справедливо следующее утверждение.

Теорема 1. Если $c_1+c_2+\cdots +c_N=1$ и ${\phi }_j\left(x\right)=\frac{\left|x\right|!}{x!}{c}^{x+e^j}$, тогда для любого $\mu =({\mu }_1,\dots ,{\mu }_N)\in {\mathbb{Z}}^N$ выполняется тождество

$\sum _{j=1}^N\sum _{\begin{array}{c}\nu \in K_j\end{array}}{P}_{A_j}\left(\nu \right)P_A(\mu -\nu ;{\phi }_j)=P_A\left(\mu \right).$ (2.1)

Доказательство данной теоремы приведено в работе [27].

3. Описание алгоритма

Рассмотрим алгоритм получения тождеств Чаунди–Булларда при помощи решения систем линейных диофантовых уравнений вида $Ax=\lambda$ и вычисления функций векторного разбиения с весом $P_A(\lambda ;\phi )$ в системе компьютеной алгебры.

Входными данными для алгоритма являются:

1. Матрица A, составленая из вектор-столбцов из набора $\Delta =\{{\alpha }^1,\dots ,{\alpha }^N\}$.
2. Некоторая точка λ ∈ K, где $K=⟨{\alpha }^1,\dots ,{\alpha }^N⟩$ — конус, образованный векторами из Δ.

Выходными данными алгоритма является тождество Чаунди–Булларда для функции векторного разбиения с весом.

Описание входных и выходных данных и работы алгоритма:

1. Строим набор векторов $\Delta =\{{\alpha }^1,\dots ,{\alpha }^N\}$ из столбцов заданной матрицы A.
2. Строим конус $\lambda -K$, где K – конус, натянутый на вектора из набора Δ (строим достаточное количество точек конуса, что обеспечивается выбором достаточно большого значения параметра interval).
3. Строим множества точек L_j, образованные пересечением конуса с конусами K_j, натянутыми на вектора из набора $\Delta \backslash \left\{{\alpha }^j\right\}$.
4. Для каждого множества $L_j,j=\mathrm{1,}\dots ,N$ строим соответствующие группы cлагаемых, домноженных на c_j, для их вычисления используется функция $VPF(A,\lambda ,j,\mathrm{int}erval,\phi )$ – сокращение от Vector Partition Function. Для каждой точки Δ ∈ L_j функция действует следующим образом: если j > 0, то функция возвращает многочлен $P_{A_j}(\lambda ,\phi );$ если j = 0, то функция возвращает $P_A(\lambda ;\phi )$ – значение функции векторного разбиения с весом φ(x).
5. Объединяем полученные группы слагаемых в общую сумму CBI – сокращение от Chaundy and Bullard Indentity, которая и будет левой частью тождества Чаунди–Булларда для функции векторного разбиения с весом; если φ(x) = 1, то функция возвращает значение «класссической» функции векторного разбиения.
6. Вычисляем правую часть тожества, используя $VPF(A,\lambda \mathrm{,0,}\mathrm{int}erval\mathrm{,1})$.

Алгоритм был реализован в среде Maple 18. Полный код программы доступен по ссылке https://github.com/lyapinap/ALeinartene2023. Вычисления производились на машине Intel(R) Core(TM) i5-1135G7 CPU 2.40 GHz, 64bit, ОЗУ 16.00 Гб под управлением Windows 11.

4. Пример

Пусть n = 2 и N = 3. Рассмотрим набор векторов

${\alpha }^1=\left(\begin{array}{c}1\\ 0\end{array}\right),{\alpha }^2=\left(\begin{array}{c}1\\ 1\end{array}\right),{\alpha }^3=\left(\begin{array}{c}0\\ 1\end{array}\right)è\lambda =\left(\begin{array}{c}3\\ 1\end{array}\right),$

тогда $\Delta =\{{\alpha }^1,{\alpha }^2,{\alpha }^3\}$, ${\Delta }_1{\alpha }^2\mathrm{,}{\alpha }^3$, ${\Delta }_2=\{{\alpha }^1,{\alpha }^3\}$, ${\Delta }_3=\{{\alpha }^1,{\alpha }^2\}$, A, A₁, A₂, A₃ — матрицы, составленные из данных векторов соответственно, и K, K₁, K₂, K₃ — целочисленные конусы, натянутые на вектора из данных наборов соответственно.

Тогда тождество Чаунди–Булларда имеет вид:

$\begin{array}{c}\sum _{\nu \in K_1}{P}_{A_1}\left(\nu \right)P_A(\lambda -\nu ;{\phi }_1)+\\ +\sum _{\nu \in K_2}{P}_{A_2}\left(\nu \right)P_A(\lambda -\nu ;{\phi }_2)+\\ +\sum _{\nu \in K_3}{P}_{A_3}\left(\nu \right)P_A(\lambda -\nu ;{\phi }_3)=P_A\left(\lambda \right).\end{array}$

Решая соответствующие системы линейных диофантовых уравнений, получим множества точек, связанные с каждым слагаемым (см. рис. 1–3): 

Рис. 1. Пересечение решеточных конусов

Рис. 2. Пересечение решеточных конусов

Рис. 3. Пересечение решеточных конусов

$K\cap K_1=\left\{\left(\begin{array}{c}0\\ 0\end{array}\right),\left(\begin{array}{c}0\\ 1\end{array}\right),\left(\begin{array}{c}1\\ 1\end{array}\right)\right\},$

$K\cap K_2=\left\{\begin{array}{c}\left(\begin{array}{c}0\\ 0\end{array}\right),\left(\begin{array}{c}0\\ 1\end{array}\right),\left(\begin{array}{c}1\\ 0\end{array}\right),\left(\begin{array}{c}1\\ 1\end{array}\right),\left(\begin{array}{c}2\\ 0\end{array}\right),\\ \left(\begin{array}{c}2\\ 1\end{array}\right),\left(\begin{array}{c}3\\ 0\end{array}\right),\left(\begin{array}{c}3\\ 1\end{array}\right)\end{array}\right\},$

$K\cap K_3=\left\{\begin{array}{c}\left(\begin{array}{c}0\\ 0\end{array}\right),\left(\begin{array}{c}1\\ 0\end{array}\right),\left(\begin{array}{c}1\\ 1\end{array}\right),\left(\begin{array}{c}2\\ 0\end{array}\right),\left(\begin{array}{c}2\\ 1\end{array}\right),\\ \left(\begin{array}{c}3\\ 0\end{array}\right),\left(\begin{array}{c}3\\ 1\end{array}\right)\end{array}\right\}.$

Так как P_A(λ) = 2, находим тождество Чаунди–Булларда: 

$\begin{array}{c}{c}_1\left(4c_1^3{c}_3+c_1^3+3c_1^2{c}_2+c_1^2\right)+\\ +c_2\left(\begin{array}{c}4c_1^3{c}_3+c_1^3+3c_1^2{c}_2+3c_1^2{c}_3+\\ +c_1^2+2c_1{c}_2+2c_1{c}_3+c_1+c_2+c_3+1\end{array}\right)+\\ +c_3\left(\begin{array}{l}4c_1^3{c}_3+3c_1^2{c}_2+3c_1^2{c}_3+c_1^2+\\ +2c_1{c}_2+2c_1{c}_3+c_1+c_2+c_3+1\end{array}\right)=\mathrm{2,}\end{array}$

которое выполняется при условии, что c₁ + c₂ + + c₃ = 1.

Для получения данного тождества с использованием разработанного алгоритма надо задать матрицу

$A=\left(\begin{array}{ccc}1& 1& 0\\ 0& 1& 1\end{array}\right),$

точку $\lambda =\left(\mathrm{3,1}\right)$ и, например, interval = 5. Выполнение команды

ChaundyBullard(A, lambda, interval)

и дает указанный результат.

Благодарности

Работа поддержана Красноярским математическим центром, финансируемым Минобрнауки РФ в рамках мероприятий по созданию и развитию региональных НОМЦ (соглашение 075-02-2024-1429).

About the authors

A. B. Leinartene

Author for correspondence.
Email: aleina@mail.ru
Russian Federation, pr. Svobodny 79, Krasnoyarsk, 660041

A. P. Lyapin

Email: aplyapin@sfu-kras.ru
Russian Federation, pr. Svobodny 79, Krasnoyarsk, 660041

References

Supplementary files

Supplementary Files

Action

1. JATS XML

Download

2. Fig. 1. Intersection of lattice cones

Download (47KB)

Indexing metadata

3. Fig. 2. Intersection of lattice cones

Download (43KB)

Indexing metadata

4. Fig. 3. Intersection of lattice cones

Download (48KB)

Indexing metadata