GWリレー記事:有限和とZeilberger's Algorithm
こんにちは,itouです.
この記事はオープンチャット 積分,級数の部屋 のGW mathlogリレーの4日目の記事です.
有限和とZeilberger's Algorithm
有限和をやります.積分,級数はどこいったねんという感じですが, 世の中はまさに離散化の時代なのです .特に多重ゼータ値の分野における各種関係式がどこまで離散化できるか,そして有限和等式が何に活用できるか,まさに研究が始まったところであるようです.私は皆がどうやって離散化の関係式を導いているのか全く知らないのですが,今回はZeilberger's Algorithmで有限和等式を見つける方法を紹介します.
Zeilberger's Algorithmとは?
説明するよりpythonコードを見た方が早い!!
# -*- coding: # -*- coding: cp932 -*-
import sympy
from math import *
from fractions import Fraction
import sys
#(dep+2)項間wt次多項式漸化式は、(wt+1)(dep+2)個の係数変数をもつ
wt=1
dep=0
# 変数の数を指定
num_vars = (wt+1)*(dep+2)
# sympy.Symbolを使用して変数を生成
x = [sympy.Symbol(f'x_{i}') for i in range(num_vars)]
def binom(n,k):# binomial coefficient
if k > n or k < 0 :
return 0
else:
return Fraction(factorial(n), factorial(k)*factorial(n-k))
def beta(n):
s=Fraction(binom(2*n,n),4**n)
return s
def seque(N):#一般項による計算
s=0
for n_1 in range(0,N):
s+=beta(n_1)
return s
def calculate_sequence(n):
sequence = [seque(n) for n in range(0, n+1)]
return sequence
def coefficient(i):
s=0
for l in range(0,wt+1):
s+=x[i*(wt+1)+l]*n**(wt-l)
return s
def coefficient_str(i):
s=0
for l in range(0,wt+1):
s+=x[i*(wt+1)+l]*n**(wt-l)
return s
def divide_dict_to_lists(my_dict, k, n):
total_elements = (k + 1) * (n + 2)
# 辞書を (k+1) 個ずつの要素を持つリスト (n+2) 個に分ける
chunks = [dict(list(my_dict.items())[i:i + k + 1]) for i in range(0, total_elements, k + 1)]
# 分けた結果を (n+2) 個のリストに格納
result_lists = [list(chunk.values()) for chunk in chunks]
return result_lists
def divide_dict_to_lists1(x):
expression = "+".join([f"{coeff}*n^{len(x)-exp}" for exp, coeff in enumerate(x, start=1)])
result_string = f"{expression}"
print(result_string)
MAX=(wt+1)*(dep+2)+3+dep#nの値は
a=calculate_sequence(MAX)
equations = [x[0]-1]
for n in range(1,(wt+1)*(dep+2)+4):#不定方程式を解き係数決定
equations.append(sum(coefficient(i)*a[n+dep-i] for i in range(0, dep+2)))
solution = sympy.solve(equations, x)
if solution==[]:
print("解なし.wtまたはdepの値を大きくして下さい.")
sys.exit()
# キーを引用符で囲んで新しい辞書を作成
converted_data = {str(key): value for key, value in solution.items()}
# x_i_valueに値を文字列として代入（分数形式で表示）
x_i_values = {}
for key, value in converted_data.items():
index = int(key.split('_')[1]) # キーからインデックスを取得
x_i_values[f'x_{index}_value'] = str(value)
# 結果の表示
print("深さ"+f"{dep}"+"重さ"+f"{wt}")
for key, value in x_i_values.items():
print(f"{key}: {value}")
result = divide_dict_to_lists(x_i_values, wt, dep)
for x in result:
divide_dict_to_lists1(x)
冗談です.解説すると,与えられた関数$a_N$が満たすような斉次多項式係数漸化式を発見する漸化式です.$\rm{wt}$は多項式の次数で,$\rm{dep}+2$項漸化式を探索します.見つからなかったら「"解なし.wtまたはdepの値を大きくして下さい."」と表示されます.
多項式係数漸化式に関する理論については
子葉さんの記事:
超幾何数列の基礎シリーズ
にまとめられています.
等式たち
発見した漸化式を直接解く,あるいは別の式が同一の漸化式(と初期条件)満たすことを直接確認することで,以下のような等式が得られます.
以下,$(a)_n$をポッホハマー記号$(a)_n=a(a+1)…(a+n-1)$,$[a]_n=\frac{(a)_n}{n!}$とします.
0
以下は定義からすぐにわかる.
\begin{align}
{n \choose k}=(-1)^k[-n]_k
\end{align}
\begin{align}
{-n-a\choose k}=(-1)^k\frac{[n+a]_k}{[a]_k}
\end{align}
1
\begin{align} &\sum_{k=0}^{N}[-N]_k[a]_k=[1-a]_N \end{align}
2
\begin{align} &\sum_{k=0}^{2N}\frac{[-2N]_k}{[a]_N[a]_{2N-k}}=\frac{[\frac{1}{2}]_N}{[\frac{a}{2}]_N[\frac{1+a}{2}]_N}\frac{a-1}{N+a-1}\ \end{align}
3
\begin{align}
&\sum_{0\leq n_2 \leq n_1 \leq N }[a]_{n_1}[1-a]_{N-n_2}\\
&=1+a(1-a)N+4A\sum_{k=1}^{N-1}\sum_{i=0}^{k-1}
\frac{[a]_i[1-a]_i}{(i+1)^2(i+2)^2}\frac{(i+a)(i+1-a)}{a(1-a)}
\end{align}
ただし
\begin{align}
A=\frac{a(a+1)}{2}+a(1-a)+\frac{3}{4}a(a+1)(1-a)(2-a)-2a(1-a)-1
\end{align}
とする.
4
\begin{align}
&\sum_{k=0}^{N}(-1)^k {N \choose k}[a]_{k}[1-a]_{k}
=\sum_{k=0}^{N}[a]_k^2[1-a]_{N-k}\\
&\sum_{k=0}^{N}(-1)^k {N \choose k}{N+k \choose k}[a]_{k}[1-a]_{k}
=\sum_{k=0}^{N}[a]_k^2[1-a]_{N-k}^2\\
\end{align}
1の式は二項変換による対称性を示しています.(積分でいうと$t$を$1-t$に置換したようなものでしょうか?二項変換はかなり重要な性質をもっているように思います.)
離散化の観点からいうと,3の式は反復積分の等式の離散化かもしれません.
4の式はゼータ関数と深く関わっているようです(「光とゼータ関数の特殊値」というpdfに出てくるアペリ類似数を一般化したもの).
感想
今回はZeilberger's Algorithmの利用方法を紹介しました.まあお気づきの通り,式自体を自分で持ってくる必要があること,漸化式は一般には解けないこともあって,このアルゴリズムで等式を得るのは非常に効率が悪いです.
とはいえ,有限和が複数の非自明な表示をもつことを踏まえると,漸化式で特徴づけるというアイデアは重要だと思っています.大体遊びつくしたと思うので,別の有限和等式を求める方法を探したいところです.
さて,GWリレー記事は明日で最終日です.最後の方がきっちり締めてくれるでしょう！
おまけ データ
私が集めたデータです.
上の式が下の漸化式を満たすという意味です.
$\beta_n=[\frac{1}{2}]_n$とします.
\begin{multline} \begin{split} a_N&=\sum_{0 \leq n_2 \leq n_1 \leq N}\beta_{n_{1}}\beta_{N-n_2} \\ 0&=(n^2 + 4n + 4)a_{n+2} +(-3n^2 - 9n - \frac{33}{4} )a_{n+1} +(3n^2 + 6n + \frac{9}{2} )a_{n} +(-n^2 - n - \frac{1}{4} )a_{n-1} \end{split} \end{multline}
\begin{multline} \begin{split} a_N&=\sum_{0 \leq n_2 \leq n_1 \leq N}\beta_{n_{2}}\beta_{N-n_1} \\ 0&=(n )a_{n} +(-n-1 )a_{n-1} \end{split} \end{multline}
\begin{multline} \begin{split} a_N&=\sum_{0 \leq n_3\leq n_2 \leq n_1 \leq N}\beta_{n_{3}}\beta_{n_{2}}\beta_{N-n_1} \\ 0&= (n^2 + 2n + 1 )a_{n+1} +(-2n^2 - 5n - \frac{9}{4} )a_{n} +(n^2 + 3n + 2 )a_{n-1} \end{split} \end{multline}
\begin{multline} \begin{split} a_N&=\sum_{0 \leq n_2 \leq n_1 \leq N}N\beta_{n_{2}}\beta_{N-n_1} \\ 0&=(n-1 )a_{n} +(-n-1 )a_{n-1} \end{split} \end{multline}
\begin{multline} \begin{split} a_N&=\sum_{0 \leq n_2 \leq n_1 \leq N}N^2\beta_{n_{2}}\beta_{N-n_1} \\ 0&= (n^2-2n+1 )a_{n} +(-n^2-n )a_{n-1} \end{split} \end{multline}
\begin{multline} \begin{split} a_N&=\sum_{0 \leq n_2 \leq n_1 \leq N}\frac{\beta_{n_{2}}}{N-n_2+1} \beta_{N-n_1} \\ 0&= (n+2 )a_{n+1} +(-2n-\frac{5}{2}n )a_{n} +(n+\frac{1}{2} )a_{n-1} \end{split} \end{multline}
\begin{multline} \begin{split} a_N&=\sum_{0 \leq n_2 \leq n_1 \leq N}\frac{\beta_{N-n_1}}{n_1+1} \beta_{n_2} \\ 0&= (n+2 )a_{n+1} +(-2n-\frac{5}{2}n )a_{n} +(n+\frac{1}{2} )a_{n-1} \end{split} \end{multline}
\begin{multline} \begin{split} a_N&=\sum_{0 \leq n_2 \leq n_1 \leq N}\frac{\beta_{N-n_1}}{n_1+1} \frac{\beta_{n_2}}{n_2+1} \\ 0&= (n^2 + 4n + 4 )a_{n+1} +(-2n^2 - 6n - \frac{9}{2} )a_{n} +(n^2 + 2n + \frac{3}{4} )a_{n-1} \end{split} \end{multline}
\begin{multline} \begin{split} a_N&=\sum_{0 \leq n_3 \leq n_2 \leq n_1 \leq N}\beta_{N-n_1}\beta_{n_2}\beta_{n_3}\\ 0&= (n^2 + 2n + 1 )a_{n+1} +(-2n^2 - 5n - \frac{9}{4} )a_{n} +(n^2 + 3n + 2 )a_{n-1} \end{split} \end{multline}
\begin{multline} \begin{split} a_N&=\sum_{0 \leq n_3 \leq n_2 \leq n_1 \leq N}\beta_{N-n_1}\beta_{N-n_2}\beta_{n_3}\\ 0&= (n^2 + 2n + 1 )a_{n+1} +(-2n^2 - 5n - \frac{9}{4} )a_{n} +(n^2 + 3n + 2 )a_{n-1} \end{split} \end{multline}
\begin{multline} \begin{split} a_N&=\sum_{0 \leq n_2 \leq n_1 \leq N}\beta_{N-n_1}\beta_{N-n_2}\\ 0&= (n^2 + 2n + 1 )a_{n+1} +(-2n^2 - 4n - \frac{7}{4} )a_{n} +(n^2 + 2n + \frac{3}{4} )a_{n-1} \end{split} \end{multline}
\begin{multline}
\begin{split}
a_N&=\sum_{1 \leq n_2 \leq n_1 \leq N}\beta_{N-n_1}\beta_{N-n_2}\\
0&=
(n^2
)a_{n+1}
+(-2n^2 + \frac{1}{4}
)a_{n}
+(n^2 -\frac{1}{4}
)a_{n-1}
\end{split}
\end{multline}
\begin{multline}
\begin{split}
a_N&=\sum_{1 \leq n_3 \leq n_2 \leq n_1 \leq N}\beta_{N-n_1}\beta_{N-n_2}\beta_{N-n_3}\\
0&=
(n^4 + 3n^3 + 3n^2 + n
)a_{n+1}
+(-3n^4 - 8n^3 - \frac{27}{4}n^2 - \frac{15}{8}n
)a_{n+1}
+(3n^4 + 7n^3 + \frac{17}{4}n^2 + \frac{3}{8}n - \frac{3}{16}
)a_{n}
+(-n^4 - 2n^3 - \frac{1}{2}n^2 + \frac{1}{2}n + \frac{3}{16}
)a_{n-1}
\end{split}
\end{multline}
\begin{multline} \begin{split} a_N&=\sum_{0 \leq n_2 \leq n_1 \leq N}\beta_{n_{2}}\beta_{N-n_1}\frac{1}{(N-n_1+1)(N-n_1+2)}\frac{1}{(n_2+1)(n_2+2)}\\ 0&= (n^2+14n+45 )a_{n+1} +(-2n^2-\frac{51}{2}n-60 )a_{n} +(n^2+\frac{23}{2}n+15 )a_{n-1} \end{split} \end{multline}
\begin{multline} \begin{split} a_N&=\sum_{0 \leq n_2 \leq n_1 \leq N}\beta_{n_{1}}\beta_{N-n_{2}}\frac{1}{n_1+1}\\ 0&= (n^2 + 3n + 2 )a_{n+1} +(-2n^2 - 4n - \frac{9}{4} )a_{n} +(n^2 + n + \frac{1}{4} )a_{n-1} \end{split} \end{multline}
\begin{multline} \begin{split} a_N&=\sum_{0 \leq n_2 \leq n_1 \leq N}\beta_{N-n_{1}}\beta_{N-n_{2}}(N-n_1)(N-n_2)\\ 0&= (n^2 )a_{n+1} +(-2n^2 - 2n - \frac{3}{4} )a_{n} +(n^2 + 2n + \frac{3}{4} )a_{n-1} \end{split} \end{multline}
\begin{align} a_N&=\sum_{k=0}^N\frac{1}{k^4\beta_k^4}\\ 0&= (n^4+2n^3+\frac{3}{2}n^2+\frac{1}{2}n+\frac{1}{16} )a_{n+1} +(-2n^4-2n^3-\frac{3}{2}n^2-\frac{1}{2}n-\frac{1}{16})a_{n} +(n^4 )a_{n-1} \end{align}
\begin{multline} \begin{split} a_N&=\sum_{0 < n_2 \leq n_1 < N} \frac{1}{N-n_1}\frac{1}{N-n_2}\\ 0&=(n^2 + 2n + 1 )a_{n+2} +(-3n^2 - 3n - 1 )a_{n+1} +(3n^2 )a_{n} +(-n^2 + n )a_{n-1} \end{split} \end{multline}
\begin{multline} \begin{split} a_N&=\sum_{0 < n_2 \leq n_1 < N} \frac{1}{n_1^2}\frac{1}{N-n_2}\\ 0&=(n^3 + 6n^2 + 12n + 8 )a_{n+3} +(-5n^3 - 17n^2 - 22n - 11 )a_{n+2} +(9n^3 + 10n^2 + 10n + 3 )a_{n+1} +(-7n^3 + 7n^2 - 6n + 2 )a_{n} +(2n^3 - 6n^2 + 6n - 2 )a_{n-1} \end{split} \end{multline}
\begin{multline} \begin{split} a_N&=\sum_{0 < n_2 \leq n_1 < N} \frac{1}{n_1^2}\frac{1}{(N-n_2)^2}\\ 0&=(n^4 + 8n^3 + 24n^2 + 32n + 16 )a_{n+3} +(-8n^4 - 32n^3 - 54n^2 - 48n - 19 )a_{n+2} +(18n^4 + 20n^3 + 30n^2 + 16n + 3 )a_{n+1} +(-16n^4 + 24n^3 - 30n^2 + 20n - 5 )a_{n} +(5n^4 - 20n^3 + 30n^2 - 20n + 5 )a_{n-1} \end{split} \end{multline}
\begin{multline} \begin{split} a_N&=\sum_{0 < n_2 \leq n_1 < N} \frac{N^2}{n_1(n_1+1)(n_1+2)}\frac{1}{N-n_2}\\ 0&=(n^4 + 2n^3 )a_{n+1} +(-2n^4 - 4n^3 - n^2 + 2n + 1 )a_{n} +(n^4 + 2n^3 + n^2 )a_{n-1} \end{split} \end{multline}
\begin{multline} \begin{split} a_N&=\sum_{0 \leq n_1 \leq N} \frac{1}{((N-n_1)!)^2n_1!}\\ 0&=(n^2+2n+1 )a_{n+1} +(-2n-2 )a_{n} +(1 )a_{n-1}\\ \end{split} \end{multline}
この記事を高評価した人
この記事に送られたバッジ
投稿者
