페트코브셰크의 알고리즘

페트코브셰크의 알고리즘(역시 하이퍼)은 다항계수를 갖는 입력 선형재발 방정식의 초지하학적 용어 해법의 기초를 계산하는 컴퓨터 대수 알고리즘이다.동등하게 다항식 계수를 갖는 선형 차이 연산자의 첫 번째 순서 오른쪽 인자를 계산한다.이 알고리즘은 마르코 페트코브셰크가 1992년 박사과정 때 개발한 것이다.^[1]알고리즘은 모든 주요 컴퓨터 대수 시스템에서 구현된다.

고스퍼-페트코프셰크 대표

$K\mathbb{}$ ${\$를) 특성 0의 필드가 되도록$$ 한다.0이 아닌 $시퀀스$ y$(n$) ${\textstyle$ y$(n)}$의 비율이 합리적이라면, 즉, $y(n$+ $1)$/ y$(n)$ $\in$ $K\mathbb{}(n)$ ${\textstyle y(n+1)/y(n)\in \mathb {K}(n$ .페트코브셰크 알고리즘은 이 이성적 함수가 특정한 표현, 즉 고스퍼-페트코브셰크 정상 형태를 갖는 핵심 개념으로 사용한다.$r$( $n$) $\in$ $K\mathbb{}$[ $n$ $]$ ${\textstyle r(n)\in \mathb {K}[n]}$을(를) 0이 아닌 이성 함수가 되도록$$ 한다.그 다음, 단일 다항식 $a\mathbb{},$ $b,$ $c$ $\in$ K$$[$n$ $]$ ${\textstyle a,b,c\in \mathb {K}[n]$ 및$$ $0\mathrm{}$ $\ne$ $z$ $\in$ $k\mathbb{}$ ${\$이$($가) 있다.

${\displaystyle r(n)=z{\frac {a(n)}{b(n)}}{\frac {c(n+1)}{c(n)}}}}$

그리고

1. $gcd$($a$) $,$ b$$($n$+ $k$)$$= $\mathrm{모든}$음이 아닌 정수 k$k$ N ${\$ \$mathb {N$에 대해 1 {\$textstyle \a(n),b(n+k)=1},$
2. $\gcd$( $a$ ($$n$$) , $c$($n$)$$= 1 ${\textstyle \gcd(a(n),c(n)=1$}$$및
3. $gcd$( $b$( n$$)$$, $c$($$n +$1$) = $1$ ${\textstyle \gcd(b)(n),c(n+1)=1$

$r$($n$) ${\textstyle r(n)}$의 이러한 표현을 Gosper-Petkovseck 정상형이라고 한다$$.이러한 다항식들은 명시적으로 계산할 수 있다.이러한 대표성의 구성은 고스퍼의 알고리즘에서 필수적인 부분이다.^[2]Petkovseck는 이 표현의 조건 2와 3을 더하여 이 정상적인 형태를 독특하게 만들었다.^[1]

알고리즘.

Gosper-Petkovseck 표현을 사용하면 원래의 반복 방정식을 $다항식$ c$$($){\textstyle c(n)}$에 대한 반복 방정식으로 변환할 수 있다$.$다른 다항식 $a$( $n$)$$, b $(n$ $)$ ${\textstyle a(n),b(n)}$은(는) 첫 번째 $다항식{}_{}$ p $($ {\$textstyle p_{0$}(n$)$ resp의$$ 단일 계수로 취할 수 있다$$.마지막 계수 다항식 이동 $p{}_{}$ $r_{}$($\mathrm{n}$- r$$+ 1$$) ${\textstyle p_{r}(n-r+1)}$.그러면 $z$ ${\textstyle$ z$}$은(는) 특정한 대수 방정식을 충족시켜야$$ 한다.가능한 모든 세 곱$(a$($n$)$$, $b$( $n$)$$, $z$) ${\textstyle (a(n),b(n),z)}$을(를) 취하고 변환된 재발방정식 $c(n$ )$${\$textstyle$ c$(n)}$의 해당 다항식 솔루션을 계산하면 초지하학적 해법이 존재하는 경우 이를$$ 제공한다.^[1][3][4]

In the following pseudocode the degree of a polynomial ${\textstyle p(n)\in \mathbb {K} [n]}$ is denoted by ${\textstyle \deg(p(n))}$ and the coefficient of ${\textstyle n^{d}}$ is denoted by ${\textstyle {\text{coeff}}(p(n),n^{d})}$.

algorithm petkovsek is input: Linear recurrence equation ${\textstyle \sum _{k=0}^{r}p_{k}(n)\,y(n+k)=0,p_{k}\in \mathbb {K} [n],p_{0},p_{r}\neq 0}$.     output:초기하 용액이 있는$$ 경우 초기하 $용액$y {\$textstyle$y}for each monic divisor ${\textstyle a(n)}$ of ${\textstyle p_{0}(n)}$ do for each monic divisor ${\textstyle b(n)}$ of ${\textstyle p_{r}(n-r+1)}$ do for each ${\textstyle k=0,\dots ,r}$ do ${\tilde{p}}_k(n)=p_k(n)\prod _{j=0}^{k-}$${\textstyle {\tilde {p}}_{k}(n)=p_{k}(n)\prod _{j=0}^{k-1}a(n+j)\prod _{i=k}^{r-1}b(n+i)}$ ${\textstyle d=\max _{k=0,\dots ,r}\deg({\tilde {p}}_{k}(n))}$ for each root ${\textstyle z}$ of $\sum _{k=0}^r\text{coeff}({\tilde{p}}_{}$${\textstyle \sum _{k=0}^{r}{\text{coeff}}({\tilde {p}}_{k}(n),n^{d})z^{k}}$ do             Find non-zero polynomial solution ${\textstyle c(n)}$ of ${\textstyle \sum _{k=0}^{r}z^{k}\,{\tilde {p}}_{k}(n)\,c(n+k)=0}$ if such a non-zero solution ${\textstyle c(n)}$ exists then ${\textstyle r(n)=z\,a(n)/b(n)\,c(n+1)/c(n)}$ return a non-zero solution ${\textstyle y(n)}$ of ${\textstyle y(n+1)=r(n)\,y(n)}$

만약 해결책이 발견되면 모든 초기하 솔루션을 결합하여 재발 방정식의 일반적인 초기하 용액, 즉 초기하 시퀀스의 선형 범위에서 재발 방정식의 커널에 대한 생성 세트를 얻을 수 있다.^[1]

페트코브셰크는 또한 어떻게 이 비균형 문제를 해결할 수 있는지를 보여주었다.그는 재발방정식의 오른쪽이 초기하 시퀀스의 합인 경우를 고려했다.우측의 특정 초기하 시퀀스를 그룹화한 후, 각 그룹에 대해 합리적인 해결책을 위해 특정 재발 방정식을 해결한다.이러한 이성적인 해결책들은 비균형 방정식의 특정한 해결책을 얻기 위해 결합될 수 있다.이것은 동종 문제의 일반적 해결책과 함께 비균형 문제의 일반적 해결책을 제공한다.^[1]

예

서명 순열 매트릭스

$sizen$ $×$ n {\$textstyle$ n$\times$ n$}$의 서명된 순열 행렬 수는 반복 방정식에 의해 결정되는$$ $y(n$) ${\textstyle y(n)}$ 시퀀스로 설명될$$ 수 있다.

over ${\textstyle \mathbb {Q} }$. Taking ${\textstyle a(n)=n+1,b(n)=1}$ as monic divisors of ${\textstyle p_{0}(n)=4(n+1)^{2},p_{2}(n)=-1}$ respectively, one gets ${\textstyle z=\pm 2}$. For ${\textstyle z=2}$ the co페트코브셰크의 알고리즘에서 해결되는 반응재발 방정식은This recurrence equation has the polynomial solution ${\textstyle c(n)=c_{0}}$ for an arbitrary ${\textstyle c_{0}\in \mathbb {Q} }$. Hence ${\textstyle r(n)=2(n+1)}$ and ${\textstyle y(n)=2^{n}\,n!}$ is a hypergeometric solution.사실 그것은 (상수까지) 유일한 초지압 솔루션이며 서명된 순열 매트릭스의 수를 설명한다.^[5]

$\zeta {\displaystyle }$( ${\displaystyle 3}$) ${\displaystyle \zeta (3)}$의 비합리성

합계를 보면

${\displaystyle a(n)=\sum _{k=0}^{n}{\binom {n}{k}^{2}{\binom {n+k}{k}}}^{2}},}$

$\zeta {\displaystyle }$( $){\displaystyle \zeta (3)}$의 불합리성에 대한 아페리의 증명에서 나온 제일버거의 알고리즘은 선형 재발을 계산한다$.$

${\displaystyle (n+2)^{3}\,a(n+2)-(17n^{2}+51n+39)(2n+3)\,a(n+1)+(n+1)^{3}\,a(n)=0.}$

이러한 반복을 고려할 때 알고리즘은 초기하 용액을 반환하지 않으며${\displaystyle ,}$ $이$는 (${\displaystyle n}$) ${\displaystyle a(n)}$이(가) 초기하 용어로 단순화되지 않음을 증명한다.^[3]

참조