on veut seulement être sûr que c’est elle, ne pas se tromper sur l’identité […] cet extrait algébrique... — Albertine disparue
Taking a cue from Marcel Proust, I propose an algebraic approach to partition identities, via regular grammars. Many partition identities take the form ‘A ( n ) = B ( n ) A(n)=B(n) A ( n ) = B ( n ) A ( n ) A(n) A ( n ) B ( n ) B(n) B ( n ) n n n
A teaser: Euler's identity
Here is an illustration of how it works. In Euler’s identity, the archetypal example, A ( n ) A(n) A ( n ) n n n B ( n ) B(n) B ( n ) λ ⊢ n \lambda\vdash n λ ⊢ n λ i \lambda_i λ i i i i R R R U U U R { R , U } ∗ U R\{R,U\}^{*}U R { R , U } ∗ U
L o = R ( U + R R ) ∗ U , L d = R ( R + U R ) ∗ U L_o=R(U+RR)^{*}U,\qquad L_d=R(R+UR)^{*}U L o = R ( U + R R ) ∗ U , L d = R ( R + U R ) ∗ U whose generating functions are the series
H o = R ( 1 − U − R 2 ) − 1 U , H d = R ( 1 − R − U R ) − 1 U H_o=R(1-U-R^2)^{-1}U,\qquad H_d=R(1-R-UR)^{-1}U H o = R ( 1 − U − R 2 ) − 1 U , H d = R ( 1 − R − U R ) − 1 U in the skew field of fractions of the quantum plane A = Q [ q ] ⟨ U , R ⟩ / ( R U − q U R ) \mathbb{A}=\mathbb{Q}[q]\langle U,R\rangle/(RU-qUR) A = Q [ q ] ⟨ U , R ⟩ / ( R U − q U R ) q q q A ^ \widehat{\mathbb{A}} A A \mathbb{A} A R R R U U U λ = ( λ 1 ≥ ⋯ ≥ λ ℓ > 0 ) \lambda=(\lambda_1\geq\cdots\geq\lambda_\ell>0) λ = ( λ 1 ≥ ⋯ ≥ λ ℓ > 0 )
w ( λ ) = R λ ℓ U R λ ℓ − 1 − λ ℓ U ⋯ R λ 1 − λ 2 U = q n U R λ 1 in A . (1) w(\lambda)=R^{\lambda_\ell}UR^{\lambda_{\ell-1}-\lambda_\ell}U\cdots R^{\lambda_1-\lambda_2}U=q^{n}UR^{\lambda_1}
\quad\text{in }\mathbb{A}. \tag*{(1)} w ( λ ) = R λ ℓ U R λ ℓ − 1 − λ ℓ U ⋯ R λ 1 − λ 2 U = q n U R λ 1 in A . (1) every pair formed by a letter R R R U U U q q q U U U j j j j j j
Every s ∈ A ^ s\in\widehat{\mathbb{A}} s ∈ A ∑ i , j s i , j U i R j \sum_{i,j}s_{i,j}U^iR^j ∑ i , j s i , j U i R j s i , j ∈ Q [ [ q ] ] s_{i,j}\in\mathbb{Q}[[q]] s i , j ∈ Q [[ q ]]
ε ( s ) = ∑ i , j s i , j ∈ Q [ [ q ] ] \varepsilon(s)=\sum_{i,j}s_{i,j}\in\mathbb{Q}[[q]] ε ( s ) = i , j ∑ s i , j ∈ Q [[ q ]] is linear but not multiplicative: ε ( R U ) = q ≠ ε ( R ) ε ( U ) \varepsilon(RU)=q\ne\varepsilon(R)\varepsilon(U) ε ( R U ) = q = ε ( R ) ε ( U ) ε ( H o ) \varepsilon(H_o) ε ( H o ) ε ( H d ) \varepsilon(H_d) ε ( H d ) ε ( H o − H d ) = 0 \varepsilon(H_o-H_d)=0 ε ( H o − H d ) = 0 certificate of it is a decomposition
H o − H d = ( 1 − U ) a + b ( 1 − R ) , a , b ∈ A ^ . H_o-H_d=(1-U)a+b(1-R),\qquad a,b\in\widehat{\mathcal A}. H o − H d = ( 1 − U ) a + b ( 1 − R ) , a , b ∈ A . Left multiplication by U U U R R R ε ( ( 1 − U ) a ) = ε ( b ( 1 − R ) ) = 0 \varepsilon((1-U)a)=\varepsilon(b(1-R))=0 ε (( 1 − U ) a ) = ε ( b ( 1 − R )) = 0
The series a , b a,b a , b holonomic , that is, defined by finitely many q q q normal symbol of s s s ∑ i , j s i , j x i R j \sum_{i,j}s_{i,j}x^iR^j ∑ i , j s i , j x i R j marginal is obtained by setting x = 1 x=1 x = 1 U i R j ⋅ U = q j U i + 1 R j U^iR^j\cdot U=q^jU^{i+1}R^j U i R j ⋅ U = q j U i + 1 R j U U U g ↦ x Υ g g\mapsto x\,\Upsilon g g ↦ x Υ g
( Υ g ) ( x , R ) = g ( x , q R ) , (\Upsilon g)(x,R)=g(x,qR), ( Υ g ) ( x , R ) = g ( x , q R ) , and right multiplication by R R R g ↦ R g g\mapsto Rg g ↦ R g U U U Υ \Upsilon Υ Υ R = q R Υ \Upsilon R=qR\Upsilon Υ R = q R Υ U ↦ Υ U\mapsto\Upsilon U ↦ Υ R ↦ R R\mapsto R R ↦ R A \mathcal A A q q q R R R A \mathcal A A H o H_o H o H d H_d H d q q q R R R x x x a a a b b b q q q ν \nu ν q q q q q q q q q b = q Υ b ′ b=q\Upsilon b' b = q Υ b ′ b ′ b' b ′ q q q b ′ ∈ Q [ [ q , R ] ] b'\in\mathbb{Q}[[q,R]] b ′ ∈ Q [[ q , R ]] [ R n ] b = q n + 1 [ R n ] b ′ [R^n]b=q^{n+1}[R^n]b' [ R n ] b = q n + 1 [ R n ] b ′ n + 1 n+1 n + 1 b ∈ A ^ b\in\widehat{\mathcal A} b ∈ A b ′ b' b ′
For Euler’s identity, moving the outer letters inwards gives H o = q U ( 1 − q U − q 2 R 2 ) − 1 R H_o=qU(1-qU-q^2R^2)^{-1}R H o = q U ( 1 − q U − q 2 R 2 ) − 1 R H d = q U ( 1 − q R − q 2 U R ) − 1 R H_d=qU(1-qR-q^2UR)^{-1}R H d = q U ( 1 − q R − q 2 U R ) − 1 R H o − H d H_o-H_d H o − H d
D ( x , R ) = q R ( m o , x − m d , x ) , { ( 1 − q x Υ − q 2 R 2 ) m o , x = x , ( 1 − q R − q 2 x R Υ ) m d , x = x . D(x,R)=qR(m_{o,x}-m_{d,x}),
\qquad
\begin{cases}
(1-qx\Upsilon-q^2R^2)m_{o,x}=x,\\
(1-qR-q^2xR\Upsilon)m_{d,x}=x.
\end{cases} D ( x , R ) = q R ( m o , x − m d , x ) , { ( 1 − q x Υ − q 2 R 2 ) m o , x = x , ( 1 − q R − q 2 x R Υ ) m d , x = x . Both operators are congruent to 1 modulo q q q Q [ x , R ] [ [ q ] ] \mathbb{Q}[x,R][[q]] Q [ x , R ] [[ q ]] a , b a,b a , b
( 1 − x ) a = D ( x , R ) − D ( 1 , R ) , ( 1 − R ) b = D ( 1 , R ) , (1-x)a=D(x,R)-D(1,R),\qquad(1-R)b=D(1,R), ( 1 − x ) a = D ( x , R ) − D ( 1 , R ) , ( 1 − R ) b = D ( 1 , R ) , and are holonomic. It remains to certify their convergence in A ^ \widehat{\mathcal A} A § 3.7 )
u = 1 + R 2 α ( Υ ) u , v = 1 + R 2 β ( Υ ) v , α ( U ) = ( 1 − q U ) − 1 , β ( U ) = ( 1 + q U ) ( 1 + q 2 U ) , u=1+R^2\alpha(\Upsilon)u,\qquad v=1+R^2\beta(\Upsilon)v,\qquad\alpha(U)=(1-qU)^{-1},\qquad\beta(U)=(1+qU)(1+q^2U), u = 1 + R 2 α ( Υ ) u , v = 1 + R 2 β ( Υ ) v , α ( U ) = ( 1 − q U ) − 1 , β ( U ) = ( 1 + q U ) ( 1 + q 2 U ) , select u , v ∈ Q [ [ q , R ] ] u,v\in\mathbb{Q}[[q,R]] u , v ∈ Q [[ q , R ]] χ ( U ) = 1 − q 2 U \chi(U)=1-q^2U χ ( U ) = 1 − q 2 U dilation witness for θ = β / α \theta=\beta/\alpha θ = β / α
θ ( U ) χ ( U ) = ( 1 − q 2 U 2 ) ( 1 − q 4 U 2 ) = χ ( U 2 ) χ ( q 2 U 2 ) . \theta(U)\chi(U)=(1-q^2U^2)(1-q^4U^2)=\chi(U^2)\chi(q^2U^2). θ ( U ) χ ( U ) = ( 1 − q 2 U 2 ) ( 1 − q 4 U 2 ) = χ ( U 2 ) χ ( q 2 U 2 ) . Thus u − v = q 2 Υ w u-v=q^2\Upsilon w u − v = q 2 Υ w w ∈ Q [ [ q , R ] ] w\in\mathbb{Q}[[q,R]] w ∈ Q [[ q , R ]] Proposition 3.7 , and the equations of u u u v v v m o , 1 m_{o,1} m o , 1 m d , 1 m_{d,1} m d , 1
b = ( 1 + R ( 1 − q Υ ) − 1 ) u − ( 1 + R ( 1 + q Υ ) ) v = q Υ b ′ (2) b=(1+R(1-q\Upsilon)^{-1})u-(1+R(1+q\Upsilon))v=q\Upsilon b' \tag*{(2)} b = ( 1 + R ( 1 − q Υ ) − 1 ) u − ( 1 + R ( 1 + q Υ )) v = q Υ b ′ (2) with b ′ = q w + R ( 1 − q Υ ) − 1 ( w + Υ v ) ∈ Q [ [ q , R ] ] b'=qw+R(1-q\Upsilon)^{-1}(w+\Upsilon v)\in\mathbb{Q}[[q,R]] b ′ = q w + R ( 1 − q Υ ) − 1 ( w + Υ v ) ∈ Q [[ q , R ]] b ∈ A ^ b\in\widehat{\mathcal A} b ∈ A a ∈ A ^ a\in\widehat{\mathcal A} a ∈ A λ = 2 \lambda=2 λ = 2
Main results
The scheme of §1 applies to any two partition languages in R ⟨ R , U ⟩ ∗ U \mathcal R\langle R,U\rangle^*U R ⟨ R , U ⟩ ∗ U R R R U U U s 1 s_1 s 1 s 2 s_2 s 2 normalized realization
w Q = r , S = w e , Q ≡ I ( m o d q ) , w\mathbf{Q}=r,\qquad S=we,\qquad\mathbf{Q}\equiv I\pmod q, w Q = r , S = w e , Q ≡ I ( mod q ) , of dimension s = s 1 + s 2 s=s_1+s_2 s = s 1 + s 2 S S S § 3.5 . We write K = Q ( q ) \mathbb{K}=\mathbb{Q}(q) K = Q ( q ) ( a ; q ) n = ∏ j = 0 n − 1 ( 1 − a q j ) (a;q)_n=\prod_{j=0}^{n-1}(1-aq^j) ( a ; q ) n = ∏ j = 0 n − 1 ( 1 − a q j ) ( a 1 , … , a t ; q ) n = ∏ i ( a i ; q ) n (a_1,\ldots,a_t;q)_n=\prod_i(a_i;q)_n ( a 1 , … , a t ; q ) n = ∏ i ( a i ; q ) n n = ∞ n=\infty n = ∞ q q q
Theorem A. Let H 1 , H 2 H_1,H_2 H 1 , H 2 path series (§ 3.1 ) of finite weighted automata with weights in Q ( q ) \mathbb{Q}(q) Q ( q ) q = 0 q=0 q = 0 R { R , U } ∗ U R\{R,U\}^{*}U R { R , U } ∗ U S = H 1 − H 2 S=H_1-H_2 S = H 1 − H 2 normal symbol D ( x , R ) D(x,R) D ( x , R ) s s s
a ( x , R ) = D ( x , R ) − D ( 1 , R ) 1 − x , b ( R ) = D ( 1 , R ) 1 − R = ∑ n ≥ 0 b n R n . a(x,R)=\frac{D(x,R)-D(1,R)}{1-x},\qquad b(R)=\frac{D(1,R)}{1-R}=\sum_{n\geq0}b_nR^n. a ( x , R ) = 1 − x D ( x , R ) − D ( 1 , R ) , b ( R ) = 1 − R D ( 1 , R ) = n ≥ 0 ∑ b n R n . (1) The series a a a b b b q q q 2 s + 1 2s+1 2 s + 1 s + 1 s+1 s + 1 a a a ( x , R ) (x,R) ( x , R ) b b b R R R b n b_n b n K \mathbb{K} K
(2) The coefficients of a a a ν ( a i , j ) ≥ i + j \nu(a_{i,j})\geq i+j ν ( a i , j ) ≥ i + j a ∈ A ^ a\in\widehat{\mathcal{A}} a ∈ A
(3) The following are equivalent:
(a) ε ( H 1 ) = ε ( H 2 ) \varepsilon(H_1)=\varepsilon(H_2) ε ( H 1 ) = ε ( H 2 )
(b) b n → 0 b_n\to0 b n → 0 q q q
(c) ν ( b n ) ≥ n + 1 \nu(b_n)\geq n+1 ν ( b n ) ≥ n + 1 n n n
(d) b = q Υ φ b=q\Upsilon\varphi b = q Υ φ φ ∈ Q [ [ q , R ] ] \varphi\in\mathbb{Q}[[q,R]] φ ∈ Q [[ q , R ]]
(e) b ∈ Q [ R ] [ [ q ] ] b\in\mathbb{Q}[R][[q]] b ∈ Q [ R ] [[ q ]] S = ( 1 − U ) a + b ( 1 − R ) S=(1-U)a+b(1-R) S = ( 1 − U ) a + b ( 1 − R ) A ^ \widehat{\mathcal{A}} A
In (d), φ = q − 1 b ( R / q ) \varphi=q^{-1}b(R/q) φ = q − 1 b ( R / q ) φ \varphi φ ( a , b ) (a,b) ( a , b ) S = ( 1 − U ) a + b ( 1 − R ) S=(1-U)a+b(1-R) S = ( 1 − U ) a + b ( 1 − R ) a ∈ A ^ a\in\widehat{\mathcal{A}} a ∈ A b ∈ Q [ R ] [ [ q ] ] b\in\mathbb{Q}[R][[q]] b ∈ Q [ R ] [[ q ]]
Theorem A is proved in § 3.6 . It reduces a partition identity to the integrality of a single holonomic series φ \varphi φ a , b a,b a , b b n b_n b n ν ( ε ( S ) − b n ) ≥ n + 1 \nu(\varepsilon(S)-b_n)\geq n+1 ν ( ε ( S ) − b n ) ≥ n + 1 Lemma 3.5 ), the identity is false if and only if ν ( b n ) < n + 1 \nu(b_n)<n+1 ν ( b n ) < n + 1 n n n φ \varphi φ direct certificate (§ 3.7 ) does so by finitely many exact checks on holonomic series; alternatively, any independent proof of the identity yields (3d) (Corollary 3.6 ).
This separates discovery from verification, in the spirit of Wilf–Zeilberger certificates [23 , 24 , 25 ] . Certificates are found by finite linear-algebra searches (§ 3.8 and Appendix § 5 ) for integral kernels, dilation witnesses, finite recurrences, telescoping certificates and quadratic invariants, and then checked by exact algebraic manipulations. Since the quantum plane records area, many combinatorial descriptions — allowed residues, controlled differences between coloured parts, forbidden patterns — compile into rational series to which Theorem A applies (§ 3.2 ).
Many partition identities equate restrictions on differences or multiplicities with restrictions on the residue classes of the parts. Classical examples include Euler’s identity between distinct and odd parts (modulo 2) [8 §326] , the Rogers–Ramanujan identities (modulo 5) [19 ] , Schur’s theorem (modulo 6) [21 ] , and the Göllnitz–Gordon identities (modulo 8) [11 , 13 ] . Later examples include Capparelli’s identity (modulo 12), conjectured in his 1988 thesis [6 ] and first proved by Andrews [2 ] , and Nandi’s three identities (modulo 14), conjectured in 2014 [16 §8.1] and proved by Takigiku and Tsuchioka [22 ] . These examples suggest regular languages as a common framework; Nandi’s difference conditions already involve forbidden patterns of unbounded length. Primc’s coloured partition conjectures [18 ] belong to the same tradition; our main application, Theorem B below, is their three-row case at level two, with modulus 8.
Primc's identities at level two
We prove the three-row, level-two case of Primc’s conjecture [18 Conjecture 2.1] . It equates two classes of coloured partitions: one defined by restrictions on neighbouring multiplicities, the other by congruence classes modulo eight.
For the first class, every positive even part has two colours, called top and bottom , and every odd part has one colour, called middle . Write τ n \tau_n τ n β n \beta_n β n 2 n 2n 2 n μ n \mu_n μ n 2 n − 1 2n-1 2 n − 1 k 0 k_0 k 0 k 1 k_1 k 1 k 2 k_2 k 2 level , and set τ 0 = k 2 \tau_0=k_2 τ 0 = k 2 β 0 = k 0 \beta_0=k_0 β 0 = k 0 admissible if
max ( τ n − 1 , τ n ) + μ n + max ( β n − 1 , β n ) ≤ 2 ( n ≥ 1 ) . (3) \max(\tau_{n-1},\tau_n)+\mu_n+\max(\beta_{n-1},\beta_n)\le2 \qquad(n\ge1). \tag*{(3)} max ( τ n − 1 , τ n ) + μ n + max ( β n − 1 , β n ) ≤ 2 ( n ≥ 1 ) . (3) Equivalently, each of the four sums obtained by choosing one of τ n − 1 , τ n \tau_{n-1},\tau_n τ n − 1 , τ n β n − 1 , β n \beta_{n-1},\beta_n β n − 1 , β n μ n \mu_n μ n μ n \mu_n μ n § 3.2 ). The value k 1 = 2 − k 0 − k 2 k_1=2-k_0-k_2 k 1 = 2 − k 0 − k 2 Π k 0 , k 1 , k 2 ( q ) \Pi_{k_0,k_1,k_2}(q) Π k 0 , k 1 , k 2 ( q )
Theorem B. For each N ≥ 0 N\ge0 N ≥ 0 N N N N N N
Each allowed colour has unrestricted multiplicity, and all other residues are forbidden. The cases ( 0 , 0 , 2 ) (0,0,2) ( 0 , 0 , 2 ) ( 0 , 1 , 1 ) (0,1,1) ( 0 , 1 , 1 )
For example, for the boundary ( 2 , 0 , 0 ) (2,0,0) ( 2 , 0 , 0 ) (3) forbids the part 1 and the top-coloured part 2, and the theorem states
Π 2 , 0 , 0 ( q ) = 1 ( q 2 , q 3 , q 4 , q 4 , q 5 , q 6 ; q 8 ) ∞ . \Pi_{2,0,0}(q)=\frac{1}{(q^2,q^3,q^4,q^4,q^5,q^6;q^8)_\infty}. Π 2 , 0 , 0 ( q ) = ( q 2 , q 3 , q 4 , q 4 , q 5 , q 6 ; q 8 ) ∞ 1 . Figure 1 shows the two automata for this boundary; the tags on the letters U U U A A A § 3.2 ).
Figure 1. The two automata for boundary (2, 0, 0). Top: the residue automaton; U 1 , U 2 U_1,U_2 U 1 , U 2 τ β \tau\beta τ β R R R R R R (3) . All tagged U U U U U U A A A
Primc’s Conjecture 2.1 only asserts that these generating functions are periodic products; the four products of Theorem B are those he found numerically [18 p. 53] . Kanade, Russell, Tsuchioka and Warnaar proposed an explicit product for every width and level [15 Conjecture 4.2] , whose case n = k = 2 n=k=2 n = k = 2 [15 Propositions 4.4 and 4.5] and quadruple-sum expressions [15 Theorem 4.10] for the four generating functions, refined by the number of parts, but not their product evaluations. The level-one case, of modulus 6, follows from the coloured partition theorem [14 Theorem 1.2] , and also from a multisum identity of Russell [20 ] together with Bressoud’s identities; see [15 §4] .
Both partition classes are recognized by small automata: the first needs only to remember the preceding even multiplicities, and the second only the part size modulo eight and its colour. The proof in §4.2 reduces the four-state transfer system of the local conditions to two Göllnitz–Gordon systems, by a quadratic invariant and two rational telescoping certificates, all found by the searches of §3.8. The classical Göllnitz–Gordon identities and Jacobi’s triple product then give the products in the theorem. This proves ϵ ( H 1 ) = ϵ ( H 2 ) \epsilon(H_1)=\epsilon(H_2) ϵ ( H 1 ) = ϵ ( H 2 )
In §4 we also treat Glaisher’s identity, the two Rogers–Ramanujan identities, Bessenrodt’s refinement of Euler’s identity by a global partition statistic, Berkovich–Uncu identities involving part sizes and indices, and an identity between two five-state automata, found by computer search, which fits none of the previous patterns.
Holonomic certificates and their discovery
Partition languages
General background on partitions and q q q [1 ] . In the boundary word w ( λ ) w(\lambda) w ( λ ) (1) , R R R height , the number of letters R R R U U U ℓ ( λ ) \ell(\lambda) ℓ ( λ ) λ \lambda λ ∣ λ ∣ |\lambda| ∣ λ ∣
Regular languages are those described by regular expressions, built from letters by concatenation, union and Kleene star; equivalently, those recognized by finite automata, namely finite directed graphs with an initial state, a set of final states and edges labelled R R R U U U T T T r r r e e e path series r ( I − T ) − 1 e = ∑ n ≥ 0 r T n e r(I-T)^{-1}e = \sum_{n\geq0} rT^n e r ( I − T ) − 1 e = ∑ n ≥ 0 r T n e
Compiling constraints into automata
Let f h f_h f h h h h λ \lambda λ w ( λ ) w(\lambda) w ( λ )
w ( λ ) = R U f 1 R U f 2 ⋯ R U f m , m = λ 1 , f m ≥ 1. (4) w(\lambda)=RU^{f_1}RU^{f_2}\cdots RU^{f_m},\qquad m=\lambda_1,\quad f_m\geq1. \tag*{(4)} w ( λ ) = R U f 1 R U f 2 ⋯ R U f m , m = λ 1 , f m ≥ 1. (4) Reading a boundary word from left to right therefore scans the multiplicities in increasing order of the parts, and a constraint is regular as soon as it can be checked during this scan with finite memory. We make this precise for the constraints occurring in Rogers–Ramanujan type identities: congruence conditions on the parts, and difference conditions on the multiplicities, possibly of coloured parts.
Colours and tagged letters. Following Primc [18 ] , let N = N 1 ∪ ⋯ ∪ N r \mathcal{N}=\mathcal{N}_1\cup\cdots\cup\mathcal{N}_r N = N 1 ∪ ⋯ ∪ N r N c \mathcal{N}_c N c c c c N \mathcal{N} N f h , c f_{h,c} f h , c h ∈ N c h\in\mathcal{N}_c h ∈ N c f h = ( f h , 1 , … , f h , r ) f_h=(f_{h,1},\ldots,f_{h,r}) f h = ( f h , 1 , … , f h , r )
w ( λ ) = R U 1 f 1 , 1 ⋯ U r f 1 , r R U 1 f 2 , 1 ⋯ U r f 2 , r ⋯ R U 1 f m , 1 ⋯ U r f m , r w(\lambda)=RU_1^{f_{1,1}}\cdots U_r^{f_{1,r}}\,RU_1^{f_{2,1}}\cdots U_r^{f_{2,r}}\cdots RU_1^{f_{m,1}}\cdots U_r^{f_{m,r}} w ( λ ) = R U 1 f 1 , 1 ⋯ U r f 1 , r R U 1 f 2 , 1 ⋯ U r f 2 , r ⋯ R U 1 f m , 1 ⋯ U r f m , r over the alphabet { R , U 1 , … , U r } \{R,U_1,\ldots,U_r\} { R , U 1 , … , U r } A A A U c U_c U c U U U
Congruence conditions. Suppose that every N c \mathcal{N}_c N c M M M ( ρ , j ) (\rho,j) ( ρ , j ) ρ ∈ Z / M \rho\in\mathbb{Z}/M ρ ∈ Z / M M M M j ∈ { 0 , … , r } j\in\{0,\ldots,r\} j ∈ { 0 , … , r } j = 0 j=0 j = 0 ι \iota ι ( ρ , j ) (\rho,j) ( ρ , j ) j ≥ 1 j\geq1 j ≥ 1
ι → R ( 1 , 0 ) , ( ρ , j ) → R ( ρ + 1 , 0 ) , ( ρ , j ) → U c ( ρ , c ) if j ≤ c and ρ ∈ N c ( m o d M ) . \iota\xrightarrow{R} (1,0),\qquad(\rho,j)\xrightarrow{R}(\rho+1,0),\qquad(\rho,j)\xrightarrow{U_c}(\rho,c)\ \text{if }j\leq c\text{ and }\rho\in\mathcal{N}_c\pmod M. ι R ( 1 , 0 ) , ( ρ , j ) R ( ρ + 1 , 0 ) , ( ρ , j ) U c ( ρ , c ) if j ≤ c and ρ ∈ N c ( mod M ) . It is deterministic and accepts the encodings of all nonempty coloured partitions on N \mathcal{N} N
∏ c = 1 r ∏ h ∈ N c 1 1 − q h − 1 = ∏ t = 1 M 1 ( q t ; q M ) ∞ c t − 1 , \prod_{c=1}^{r}\prod_{h\in\mathcal{N}_c}\frac{1}{1-q^h}-1=\prod_{t=1}^{M}\frac{1}{(q^t;q^M)_\infty^{c_t}}-1, c = 1 ∏ r h ∈ N c ∏ 1 − q h 1 − 1 = t = 1 ∏ M ( q t ; q M ) ∞ c t 1 − 1 , where c t c_t c t t t t Figure 2 (right) shows a variant, with one colour and a separate final state, for M = 5 M=5 M = 5 ( q 3 ; q 6 ) ∞ / ( q , q 2 , q 4 , q 5 ; q 6 ) ∞ (q^3;q^6)_\infty/(q,q^2,q^4,q^5;q^6)_\infty ( q 3 ; q 6 ) ∞ / ( q , q 2 , q 4 , q 5 ; q 6 ) ∞ ( 0 , 1 , 0 ) (0,1,0) ( 0 , 1 , 0 ) ( q 3 ; q 6 ) ∞ − 1 (q^3;q^6)_\infty^{-1} ( q 3 ; q 6 ) ∞ − 1 ≡ 3 ( m o d 6 ) \equiv3 \pmod{6} ≡ 3 ( mod 6 )
Figure 2. Automata for the Rogers–Ramanujan identities: gap conditions (left) and residue conditions (right). Each automaton reads the complete boundary word, from its unique initial state s s s f f f
Difference conditions. Difference conditions constrain the multiplicities in a window of consecutive heights. When the multiplicities they involve are bounded, only finitely many multiplicity vectors occur in a window, and the conditions define a regular language:
Lemma 3.1 (Window conditions). Let r r r M M M W ≥ 1 W \ge1 W ≥ 1 K ≥ 0 K \ge0 K ≥ 0 W ⊆ Z / M × { 0 , … , K } r W \mathcal{W} \subseteq\mathbb{Z}/M \times\{0,\ldots,K\}^{rW} W ⊆ Z / M × { 0 , … , K } r W ( ρ , 0 , … , 0 ) (\rho,0,\ldots,0) ( ρ , 0 , … , 0 ) v 2 − W , … , v 0 ∈ { 0 , … , K } r v_{2-W},\ldots,v_0 \in\{0,\ldots,K\}^r v 2 − W , … , v 0 ∈ { 0 , … , K } r
The coloured partitions such that
( h m o d M , f h − W + 1 , … , f h ) ∈ W for all h ≥ 1 , (5) (h \bmod M, f_{h-W+1},\ldots,f_h) \in\mathcal{W} \qquad\text{for all } h \ge1, \tag*{(5)} ( h mod M , f h − W + 1 , … , f h ) ∈ W for all h ≥ 1 , (5) where f h = v h f_h=v_h f h = v h h ≤ 0 h\le0 h ≤ 0 f h = 0 f_h=0 f h = 0 h > λ 1 h>\lambda_1 h > λ 1 1 + M ( K + 1 ) r W 1+M(K+1)^{rW} 1 + M ( K + 1 ) r W
Proof. After reading a prefix ending at height h h h h h h M M M f h − W + 1 , … , f h − 1 f_{h-W+1},\ldots,f_{h-1} f h − W + 1 , … , f h − 1 f h f_h f h R R R 1 1 1 v 2 − W , … , v 0 v_{2-W},\ldots,v_0 v 2 − W , … , v 0 U c U_c U c c c c K K K R R R W \mathcal{W} W U c U_c U c h + 1 , … , h + W − 1 h+1,\ldots,h+W-1 h + 1 , … , h + W − 1 W \mathcal{W} W
Only the information needed for later checks has to be stored, and the automaton can then be minimized. Colours on which W \mathcal{W} W [12 ] f h + f h + 1 ≤ k f_h+f_{h+1}\le k f h + f h + 1 ≤ k f 1 ≤ a f_1\le a f 1 ≤ a 0 ≤ a ≤ k 0\le a\le k 0 ≤ a ≤ k r = M = 1 r=M=1 r = M = 1 W = 2 W=2 W = 2 K = k K=k K = k v 0 = k − a v_0=k-a v 0 = k − a imaginary multiplicity at height 0. For k = 1 k=1 k = 1 a = 1 , 0 a=1,0 a = 1 , 0 L 1 , L 2 \mathcal{L}_1,\mathcal{L}_2 L 1 , L 2 Figure 2 (left).
Primc’s arrays. Primc’s colours and conditions [18 ] are of this kind. For w = 2 ℓ − 1 w=2\ell-1 w = 2 ℓ − 1 N w o d d \mathcal{N}^{\mathrm{odd}}_w N w odd i = 1 , … , w i=1,\ldots,w i = 1 , … , w i i i i + 1 i+1 i + 1 ℓ \ell ℓ ℓ − 1 \ell-1 ℓ − 1 adjacent if they lie in adjacent rows and their parts differ by one, and a downward path is a sequence of entries, one in each row from top to bottom, any two consecutive ones being adjacent. The level-k k k k k k ( k 0 , … , k ℓ ) (k_0,\ldots,k_\ell) ( k 0 , … , k ℓ ) k 0 + ⋯ + k ℓ = k k_0+\cdots+k_\ell=k k 0 + ⋯ + k ℓ = k ( k 0 , k 1 , 0 , k 2 , 0 , … , 0 , k ℓ − 1 , k ℓ ) (k_0,k_1,0,k_2,0,\ldots,0,k_{\ell-1},k_\ell) ( k 0 , k 1 , 0 , k 2 , 0 , … , 0 , k ℓ − 1 , k ℓ ) 0 0 0 − 1 -1 − 1
The parts along a downward path lie in w w w r = W = w r=W=w r = W = w M = 2 M=2 M = 2 K = k K=k K = k W \mathcal{W} W k k k v 2 − w , … , v 0 v_{2-w},\ldots,v_0 v 2 − w , … , v 0 v − 1 , v 0 v_{-1},v_0 v − 1 , v 0 [15 Conjecture 4.2] , and every product found numerically in [18 ] , once cleared of negative exponents as above, therefore takes the form ε ( H 1 ) = ε ( H 2 ) \varepsilon(H_1)=\varepsilon(H_2) ε ( H 1 ) = ε ( H 2 ) w = 3 w=3 w = 3 k ≤ 2 k\le2 k ≤ 2 w = 5 w=5 w = 5 k = 1 k=1 k = 1 [18 pp. 53–54] .
For w = 3 w=3 w = 3 τ n , μ n , β n \tau_n,\mu_n,\beta_n τ n , μ n , β n Theorem B , the array is
τ 0 τ 1 τ 2 τ 3 ⋯ μ 0 μ 1 μ 2 μ 3 μ 4 ⋯ β 0 β 1 β 2 β 3 ⋯ \begin{aligned}
&\tau_0 && \tau_1 && \tau_2 && \tau_3 && \cdots\\
&&\mu_0 && \mu_1 && \mu_2 && \mu_3 && \mu_4 && \cdots\\
&&&\beta_0 && \beta_1 && \beta_2 && \beta_3 && \cdots
\end{aligned} τ 0 μ 0 τ 1 β 0 μ 1 τ 2 β 1 μ 2 τ 3 β 2 μ 3 ⋯ β 3 μ 4 ⋯ ⋯ with columns indexed by the parts − 1 , 0 , 1 , 2 , … -1,0,1,2,\ldots − 1 , 0 , 1 , 2 , … τ 0 = k 2 \tau_0=k_2 τ 0 = k 2 μ 0 = k 1 \mu_0=k_1 μ 0 = k 1 β 0 = k 0 \beta_0=k_0 β 0 = k 0 μ n \mu_n μ n (3) ; those through μ 0 \mu_0 μ 0 k 0 + k 1 + k 2 = 2 k_0+k_1+k_2=2 k 0 + k 1 + k 2 = 2 k 1 k_1 k 1 ( τ , β ) (\tau,\beta) ( τ , β ) § 4.2 reduces it to four states in this way. Figure 1 shows both automata for the boundary ( 2 , 0 , 0 ) (2,0,0) ( 2 , 0 , 0 )
The completion and the verification theorem
Put
A = Q [ q ] ⟨ U , R ⟩ / ( R U − q U R ) , A ^ = lim N A / q N A = Q [ U , R ] [ [ q ] ] , B ^ = Q [ R ] [ [ q ] ] . A=\mathbb{Q}[q]\langle U,R\rangle/(RU-qUR),\qquad\widehat{A}=\lim_{N}A/q^N A=\mathbb{Q}[U,R][[q]],\qquad\widehat{B}=\mathbb{Q}[R][[q]]. A = Q [ q ] ⟨ U , R ⟩ / ( R U − q U R ) , A = N lim A / q N A = Q [ U , R ] [[ q ]] , B = Q [ R ] [[ q ]] . The notation on the right refers to normal symbols; multiplication in A ^ \widehat{A} A q q q q q q U , R U,R U , R s = ∑ k ≥ 0 q k s k ( U , R ) ∈ A ^ s=\sum_{k\geq0}q^k s_k(U,R)\in\widehat{A} s = ∑ k ≥ 0 q k s k ( U , R ) ∈ A s k s_k s k § 1 are
ρ ( s ) = ∑ k ≥ 0 q k s k ( 1 , R ) , ε ( s ) = ∑ k ≥ 0 q k s k ( 1 , 1 ) . \rho(s)=\sum_{k\geq0}q^k s_k(1,R),\qquad\varepsilon(s)=\sum_{k\geq0}q^k s_k(1,1). ρ ( s ) = k ≥ 0 ∑ q k s k ( 1 , R ) , ε ( s ) = k ≥ 0 ∑ q k s k ( 1 , 1 ) . Both are continuous and linear. A series b = ∑ n ≥ 0 b n R n b=\sum_{n\geq0}b_nR^n b = ∑ n ≥ 0 b n R n Q ( ( q ) ) \mathbb{Q}((q)) Q (( q )) B ^ [ q − 1 ] \widehat{B}[q^{-1}] B [ q − 1 ] ν ( b n ) → + ∞ \nu(b_n)\to+\infty ν ( b n ) → + ∞ B ^ \widehat{B} B b n b_n b n ∑ i , j a i , j U i R j \sum_{i,j}a_{i,j}U^iR^j ∑ i , j a i , j U i R j A ^ [ q − 1 ] \widehat{A}[q^{-1}] A [ q − 1 ] ν ( a i , j ) → + ∞ \nu(a_{i,j})\to+\infty ν ( a i , j ) → + ∞ i + j → ∞ i+j\to\infty i + j → ∞
ν ( a i , j ) ≥ δ ( i + j ) − c , ν ( b n ) ≥ δ n − c ( δ > 0 ) . \nu(a_{i,j})\geq\delta(i+j)-c,\qquad\nu(b_n)\geq\delta n-c\qquad(\delta>0). ν ( a i , j ) ≥ δ ( i + j ) − c , ν ( b n ) ≥ δ n − c ( δ > 0 ) . Theorem 3.2 (Verification). Suppose S ∈ A ^ S\in\widehat{A} S ∈ A
S = ( 1 − U ) a + b ( 1 − R ) (6) S=(1-U)a+b(1-R) \tag*{(6)} S = ( 1 − U ) a + b ( 1 − R ) (6) with a , b ∈ A ^ [ q − 1 ] a,b\in\widehat{A}[q^{-1}] a , b ∈ A [ q − 1 ] ε ( S ) = 0 \varepsilon(S)=0 ε ( S ) = 0 ε ( S ) = 0 \varepsilon(S)=0 ε ( S ) = 0 (6) with a ∈ A ^ a\in\widehat{A} a ∈ A b ∈ B ^ b\in\widehat{B} b ∈ B D ( x , R ) D(x,R) D ( x , R ) S S S
a ( x , R ) = D ( x , R ) − D ( 1 , R ) 1 − x , b ( R ) = D ( 1 , R ) 1 − R . (7) a(x,R)=\frac{D(x,R)-D(1,R)}{1-x},\qquad b(R)=\frac{D(1,R)}{1-R}. \tag*{(7)} a ( x , R ) = 1 − x D ( x , R ) − D ( 1 , R ) , b ( R ) = 1 − R D ( 1 , R ) . (7) Proof. Left multiplication by U U U R R R ε ( ( 1 − U ) a ) = ε ( b ( 1 − R ) ) = 0 \varepsilon((1-U)a)=\varepsilon(b(1-R))=0 ε (( 1 − U ) a ) = ε ( b ( 1 − R )) = 0 C = ρ ( S ) = D ( 1 , R ) C=\rho(S)=D(1,R) C = ρ ( S ) = D ( 1 , R ) q q q D k ( x , R ) − D k ( 1 , R ) D_k(x,R)-D_k(1,R) D k ( x , R ) − D k ( 1 , R ) 1 − x 1-x 1 − x C k ( 1 ) = 0 C_k(1)=0 C k ( 1 ) = 0 C k ( R ) C_k(R) C k ( R ) 1 − R 1-R 1 − R ( 1 − U ) a + b ( 1 − R ) (1-U)a+b(1-R) ( 1 − U ) a + b ( 1 − R ) ( 1 − x ) a + ( 1 − R ) b = D (1-x)a+(1-R)b=D ( 1 − x ) a + ( 1 − R ) b = D b b b U U U ρ \rho ρ C = b ( 1 − R ) C=b(1-R) C = b ( 1 − R ) b b b a a a 1 − U 1-U 1 − U q q q
Certificates
Holonomicity is not needed for the telescoping argument itself, it provides finite descriptions of a a a b b b
O = K ⟨ R , Y ⟩ / ( Y R − q R Y ) , \mathcal{O}=\mathbb{K}\langle R,\mathcal{Y}\rangle/(\mathcal{Y}R-qR\mathcal{Y}), O = K ⟨ R , Y ⟩ / ( Y R − q R Y ) , acting on K [ [ R ] ] \mathbb{K}[[R]] K [[ R ]] Y g ( R ) = g ( q R ) \mathcal{Y}g(R)=g(qR) Y g ( R ) = g ( q R ) P ( R ) P(R) P ( R ) R R R P ∈ O P\in\mathcal{O} P ∈ O K [ [ R ] ] \mathbb{K}[[R]] K [[ R ]] holonomic if it is annihilated by a nonzero element of O \mathcal{O} O q q q K ( R ) \mathbb{K}(R) K ( R ) x , R x,R x , R K ( x , R ) \mathbb{K}(x,R) K ( x , R ) Υ \Upsilon Υ Ξ \Xi Ξ ( Ξ g ) ( x , R ) = g ( q x , R ) (\Xi g)(x,R)=g(qx,R) ( Ξ g ) ( x , R ) = g ( q x , R )
A certificate for a partition identity ε ( S ) = 0 \varepsilon(S)=0 ε ( S ) = 0
(c1) operator kernels defining b b b O \mathcal{O} O a a a x , R x,R x , R
(c2) initial conditions selecting the intended solutions of those kernels;
(c3) exact algebraic identities verifying (6);
(c4) a proof that ν ( b n ) ≥ n + 1 \nu(b_n) \ge n+1 ν ( b n ) ≥ n + 1 Definition 3.9 ) or an independent proof of the identity (Corollary 3.6 ).
No certificate is needed for the convergence of a a a
Constructing the holonomic kernels
Consider a partition automaton. Let T ( U , R ) T(U,R) T ( U , R ) r 0 r_0 r 0 R R R e 0 e_0 e 0 U U U H = R r 0 ( I − T ( U , R ) ) − 1 e 0 U H=Rr_0(\mathbb{I}-T(U,R))^{-1}e_0U H = R r 0 ( I − T ( U , R ) ) − 1 e 0 U
R W ( U , R ) U = q U W ( q U , q R ) R , RW(U,R)U=qUW(qU,qR)R, R W ( U , R ) U = q U W ( q U , q R ) R , valid for every word W W W
w Q = r , H = w e , Q = I − T ( q U , q R ) , r = q U r 0 , e = e 0 R . (8) wQ=r,\qquad H=we,\qquad Q=\mathbb{I}-T(qU,qR),\qquad r=qUr_0,\qquad e=e_0R. \tag*{(8)} w Q = r , H = w e , Q = I − T ( q U , q R ) , r = q U r 0 , e = e 0 R . (8) Every interior letter now carries a factor q q q Q ≡ I ( m o d q ) Q\equiv\mathbb{I}\pmod q Q ≡ I ( mod q ) w = r ∑ k ≥ 0 ( I − Q ) k w=r\sum_{k\geq0}(\mathbb{I}-Q)^k w = r ∑ k ≥ 0 ( I − Q ) k A ^ 1 × s \widehat{A}^{1\times s} A 1 × s S = H 1 − H 2 S=H_1-H_2 S = H 1 − H 2 ( e 1 , − e 2 ) (e_1,-e_2) ( e 1 , − e 2 ) Q , r , e Q,r,e Q , r , e K ⟨ U , R ⟩ / ( R U − q U R ) K\langle U,R\rangle/(RU-qUR) K ⟨ U , R ⟩ / ( R U − q U R ) q = 0 q=0 q = 0 Q ≡ I ( m o d q ) Q\equiv\mathbb{I}\pmod q Q ≡ I ( mod q )
Define the anti-homomorphism Φ : A → O \Phi:A\to O Φ : A → O
Φ ( U i R j ) = R j Υ i . \Phi(U^iR^j)=R^j\Upsilon^i. Φ ( U i R j ) = R j Υ i . It expresses the right action on marginals: ρ ( u v ) = Φ ( v ) ρ ( u ) \rho(uv)=\Phi(v)\rho(u) ρ ( uv ) = Φ ( v ) ρ ( u )
L j i = Φ ( Q i j ) , f = ρ ( r ) T , d i = Φ ( e i ) , L m = f , C = ρ ( S ) = d m , (9) L_{ji}=\Phi(Q_{ij}),\qquad f=\rho(r)^{\mathsf T},\qquad d_i=\Phi(e_i),\qquad Lm=f,\qquad C=\rho(S)=dm, \tag*{(9)} L j i = Φ ( Q ij ) , f = ρ ( r ) T , d i = Φ ( e i ) , L m = f , C = ρ ( S ) = d m , (9) where m = ρ ( w ) T m=\rho(w)^{\mathsf T} m = ρ ( w ) T L ≡ I ( m o d q ) L\equiv\mathbb{I}\pmod q L ≡ I ( mod q ) B ^ s \widehat{B}^s B s m m m C C C K K K L = ∑ j R j L j ( Υ ) L=\sum_jR^jL_j(\Upsilon) L = ∑ j R j L j ( Υ ) R n R^n R n L 0 ( q n ) ≡ I ( m o d q ) L_0(q^n)\equiv\mathbb{I}\pmod q L 0 ( q n ) ≡ I ( mod q ) C C C f f f q q q f = q r 0 T f=qr_0^{\mathsf T} f = q r 0 T d d d
Adjoin an auxiliary coordinate u = 1 u=1 u = 1 ( Υ − 1 ) u = 0 (\Upsilon-1)u=0 ( Υ − 1 ) u = 0 b b b
G b ( m u b ) = 0 , G b = ( L − f 0 0 Υ − 1 0 − d 0 1 − R ) . (10) G_b
\begin{pmatrix}
m\\
u\\
b
\end{pmatrix}
=0,\qquad
G_b=
\begin{pmatrix}
L & -f & 0\\
0 & \Upsilon-1 & 0\\
-d & 0 & 1-R
\end{pmatrix}. \tag*{(10)} G b m u b = 0 , G b = L 0 − d − f Υ − 1 0 0 0 1 − R . (10) The last row means ( 1 − R ) b = C (1-R)b=C ( 1 − R ) b = C K [ [ R ] ] K[[R]] K [[ R ]] C = ∑ c n R n C=\sum c_nR^n C = ∑ c n R n
b = ∑ n ≥ 0 b n R n , b n = ∑ j = 0 n c j . (11) b=\sum_{n\geq0}b_nR^n,\qquad b_n=\sum_{j=0}^{n}c_j. \tag*{(11)} b = n ≥ 0 ∑ b n R n , b n = j = 0 ∑ n c j . (11) For path series as in Theorem A, the boundary word of a partition contains as many letters R R R c j c_j c j j j j b n b_n b n n n n
For a a a Φ x ( U i R j ) = x i R j Υ i \Phi_x(U^iR^j)=x^iR^j\Upsilon^i Φ x ( U i R j ) = x i R j Υ i L x m x = f x L_xm_x=f_x L x m x = f x D = d x m x D=d_xm_x D = d x m x x = 1 x=1 x = 1 a a a
G a ( m x m 1 u a ) = 0 , G a = ( L x 0 − f x 0 0 L 1 − f 1 0 0 0 Υ − 1 0 − d x d 1 0 1 − x ) . (12) G_a
\begin{pmatrix}
m_x\\
m_1\\
u\\
a
\end{pmatrix}
=0,\qquad
G_a=
\begin{pmatrix}
L_x & 0 & -f_x & 0\\
0 & L_1 & -f_1 & 0\\
0 & 0 & \Upsilon-1 & 0\\
-d_x & d_1 & 0 & 1-x
\end{pmatrix}. \tag*{(12)} G a m x m 1 u a = 0 , G a = L x 0 0 − d x 0 L 1 0 d 1 − f x − f 1 Υ − 1 0 0 0 0 1 − x . (12) The last row is the first formula in (7). These homogeneous kernels have sizes s + 2 s+2 s + 2 2 s + 2 2s+2 2 s + 2 ( Υ − 1 ) u = 0 (\Upsilon-1)u=0 ( Υ − 1 ) u = 0 u u u R R R u = 1 u=1 u = 1 s + 1 s+1 s + 1 2 s + 1 2s+1 2 s + 1 f f f f x f_x f x f 1 f_1 f 1 K [ [ R ] ] s + 1 \mathbb{K}[[R]]^{s+1} K [[ R ] ] s + 1 K [ [ x , R ] ] 2 s + 1 \mathbb{K}[[x,R]]^{2s+1} K [[ x , R ] ] 2 s + 1 m m m m 1 m_1 m 1 m x m_x m x x , R x,R x , R x x x R R R I − L x \mathrm{I}-L_x I − L x I − Q \mathrm{I}-Q I − Q q q q 1 − R 1-R 1 − R 1 − x 1-x 1 − x
Lemma 3.3 (Finite elimination). Let G G G n × n n\times n n × n K ( R ) [ Υ ] \mathbb{K}(R)[\Upsilon] K ( R ) [ Υ ] Υ \Upsilon Υ δ \delta δ k k k V V V Ω \Omega Ω V G = Ω e k T VG=\Omega e_k^{\mathsf T} V G = Ω e k T deg V ≤ ( n − 1 ) δ \deg V\le(n-1)\delta deg V ≤ ( n − 1 ) δ
Proof. Put t = ( n − 1 ) δ t=(n-1)\delta t = ( n − 1 ) δ V j = ∑ i = 0 t v j i ( R ) Υ i V_j=\sum_{i=0}^{t}v_{ji}(R)\Upsilon^i V j = ∑ i = 0 t v j i ( R ) Υ i ( n − 1 ) ( t + δ + 1 ) (n-1)(t+\delta+1) ( n − 1 ) ( t + δ + 1 ) K ( R ) \mathbb{K}(R) K ( R ) n ( t + 1 ) n(t+1) n ( t + 1 ) Ω \Omega Ω G G G R R R
The matrices (10) and (12) are nonsingular over the corresponding Ore skew fields: normalization makes each state matrix invertible in its q q q Υ − 1 \Upsilon-1 Υ − 1 1 − R 1-R 1 − R 1 − x 1-x 1 − x Υ − 1 \Upsilon-1 Υ − 1 1 1 1
The symbol a a a x x x Υ i R j ↦ x i R j Ξ j \Upsilon^iR^j\mapsto x^iR^j\Xi^j Υ i R j ↦ x i R j Ξ j Q v = e Qv=e Q v = e S = r v S=rv S = r v Ξ \Xi Ξ D D D Υ \Upsilon Υ p 1 , p 2 p_1,p_2 p 1 , p 2 Ξ i Υ j D \Xi^i\Upsilon^jD Ξ i Υ j D i < p 1 i<p_1 i < p 1 j < p 2 j<p_2 j < p 2 Ξ i − p 1 Υ j \Xi^{i-p_1}\Upsilon^j Ξ i − p 1 Υ j i i i j j j Ξ i Υ j − p 2 \Xi^i\Upsilon^{j-p_2} Ξ i Υ j − p 2 j j j i i i K ( x , R ) \mathbb{K}(x,R) K ( x , R ) C C C R R R x x x a a a
The kernels can also be replaced by scalar operators with finite initial data.
Lemma 3.4 (Exceptional indices). Let Ω = ∑ j ≥ j 0 R ℓ j ω j ( Υ ) ∈ O \Omega=\sum_{j\ge j_0}R^{\ell_j}\omega_j(\Upsilon)\in\mathcal{O} Ω = ∑ j ≥ j 0 R ℓ j ω j ( Υ ) ∈ O ω j 0 ≠ 0 \omega_{j_0}\ne0 ω j 0 = 0 E Ω = { n ≥ 0 : ω j 0 ( q n ) = 0 } E_\Omega=\{n\ge0:\omega_{j_0}(q^n)=0\} E Ω = { n ≥ 0 : ω j 0 ( q n ) = 0 }
(1) If Ω g = 0 \Omega g=0 Ω g = 0 g = ∑ g n R n ∈ K [ [ R ] ] g=\sum g_nR^n\in\mathbb{K}[[R]] g = ∑ g n R n ∈ K [[ R ]]
ω j 0 ( q n ) g n = − ∑ j > j 0 ω j ( q n + j 0 − j ) g n + j 0 − j , (13) \omega_{j_0}(q^n)g_n=-\sum_{j>j_0}\omega_j(q^{n+j_0-j})g_{n+j_0-j}, \tag*{(13)} ω j 0 ( q n ) g n = − j > j 0 ∑ ω j ( q n + j 0 − j ) g n + j 0 − j , (13) where negative subscripts mean zero. Hence g g g E Ω E_\Omega E Ω g = 0 g=0 g = 0
(2) Let ω ( Z ) = ∑ i γ i Z i ∈ K [ Z ] \omega(Z)=\sum_i\gamma_iZ^i\in\mathbb{K}[Z] ω ( Z ) = ∑ i γ i Z i ∈ K [ Z ] i 0 i_0 i 0 γ i 0 ≠ 0 \gamma_{i_0}\ne0 γ i 0 = 0 n 0 n_0 n 0 ( ν ( γ i 0 ) − ν ( γ i ) ) / ( i − i 0 ) (\nu(\gamma_{i_0})-\nu(\gamma_i))/(i-i_0) ( ν ( γ i 0 ) − ν ( γ i )) / ( i − i 0 ) i > i 0 i>i_0 i > i 0 γ i ≠ 0 \gamma_i\ne0 γ i = 0 n 0 = − ∞ n_0=-\infty n 0 = − ∞ ν ( ω ( q n ) ) = ν ( γ i 0 ) + i 0 n \nu(\omega(q^n))=\nu(\gamma_{i_0})+i_0n ν ( ω ( q n )) = ν ( γ i 0 ) + i 0 n n > n 0 n>n_0 n > n 0 ω ( q n ) ≠ 0 \omega(q^n)\ne0 ω ( q n ) = 0 ω = ω j 0 \omega=\omega_{j_0} ω = ω j 0 E Ω E_\Omega E Ω { n ≤ n 0 } \{n\le n_0\} { n ≤ n 0 } E Ω E_\Omega E Ω ω j 0 ( q n ) ∈ K \omega_{j_0}(q^n)\in\mathbb{K} ω j 0 ( q n ) ∈ K n n n
Proof. (1) is the coefficient of R n + j 0 R^{n+j_0} R n + j 0 Ω g = 0 \Omega g=0 Ω g = 0 Z = q n Z=q^n Z = q n γ i Z i \gamma_iZ^i γ i Z i γ i q i n \gamma_iq^{in} γ i q in ν ( γ i ) + i n \nu(\gamma_i)+in ν ( γ i ) + in i > i 0 i>i_0 i > i 0 γ i ≠ 0 \gamma_i\ne0 γ i = 0
ν ( γ i 0 ) + i 0 n < ν ( γ i ) + i n ⟺ n > ν ( γ i 0 ) − ν ( γ i ) i − i 0 . \nu(\gamma_{i_0})+i_0n<\nu(\gamma_i)+in\Longleftrightarrow n>\frac{\nu(\gamma_{i_0})-\nu(\gamma_i)}{i-i_0}. ν ( γ i 0 ) + i 0 n < ν ( γ i ) + in ⟺ n > i − i 0 ν ( γ i 0 ) − ν ( γ i ) . Hence, for n > n 0 n>n_0 n > n 0 γ i 0 q i 0 n \gamma_{i_0}q^{i_0n} γ i 0 q i 0 n ω ( q n ) \omega(q^n) ω ( q n )
Values at E Ω E_\Omega E Ω
Convergence and proof of Theorem A
The kernels produce formal holonomic boundaries whether or not the identity holds: the one-word partition language with series S = R U = q U R S=RU=qUR S = R U = q U R b = q R / ( 1 − R ) b=qR/(1-R) b = q R / ( 1 − R ) b n = q b_n=q b n = q n ≥ 1 n\geq1 n ≥ 1
Lemma 3.5 (Area bound). In the setting of Theorem A , write D ( x , R ) = ∑ i , j d i , j x i R j D(x,R)=\sum_{i,j}d_{i,j}x^iR^j D ( x , R ) = ∑ i , j d i , j x i R j C = D ( 1 , R ) = ∑ j c j R j C=D(1,R)=\sum_j c_jR^j C = D ( 1 , R ) = ∑ j c j R j
ν ( d i , j ) ≥ i + j − 1 , ν ( c j ) ≥ j , ν ( ε ( S ) − b n ) ≥ n + 1 , ν ( a i , j ) ≥ i + j . (14) \nu(d_{i,j})\geq i+j-1,\qquad\nu(c_j)\geq j,\qquad\nu(\varepsilon(S)-b_n)\geq n+1,\qquad\nu(a_{i,j})\geq i+j. \tag*{(14)} ν ( d i , j ) ≥ i + j − 1 , ν ( c j ) ≥ j , ν ( ε ( S ) − b n ) ≥ n + 1 , ν ( a i , j ) ≥ i + j . (14) Proof. A word in R { R , U } ∗ U R\{R,U\}^{*}U R { R , U } ∗ U i i i U U U j j j R R R i + j − 1 i+j-1 i + j − 1 R R R U U U ν ( d i , j ) ≥ i + j − 1 \nu(d_{i,j})\geq i+j-1 ν ( d i , j ) ≥ i + j − 1 ν ( c j ) ≥ j \nu(c_j)\geq j ν ( c j ) ≥ j i ≥ 1 i\geq1 i ≥ 1 ε ( S ) − b n = ∑ j > n c j \varepsilon(S)-b_n=\sum_{j>n}c_j ε ( S ) − b n = ∑ j > n c j ( x t − 1 ) / ( 1 − x ) = − ( 1 + x + ⋯ + x t − 1 ) (x^t-1)/(1-x)=-(1+x+\cdots+x^{t-1}) ( x t − 1 ) / ( 1 − x ) = − ( 1 + x + ⋯ + x t − 1 ) a i , j = − ∑ t > i d t , j a_{i,j}=-\sum_{t>i}d_{t,j} a i , j = − ∑ t > i d t , j min t > i ( t + j − 1 ) = i + j \min_{t>i}(t+j-1)=i+j min t > i ( t + j − 1 ) = i + j
In particular, ( b n ) (b_n) ( b n ) ε ( S ) \varepsilon(S) ε ( S )
ε ( S ) = 0 ⟺ b n ⟶ 0 ⟺ ν ( b n ) ≥ n + 1 for all n ⟺ b = q Υ ϕ , ϕ ∈ Q [ [ q , R ] ] . (15) \begin{aligned}
\varepsilon(S)=0 &\Longleftrightarrow b_n\longrightarrow0\\
&\Longleftrightarrow\nu(b_n)\geq n+1\text{ for all }n\\
&\Longleftrightarrow b=q\Upsilon\phi,\quad\phi\in\mathbb{Q}[[q,R]]. \tag*{(15)}
\end{aligned} ε ( S ) = 0 ⟺ b n ⟶ 0 ⟺ ν ( b n ) ≥ n + 1 for all n ⟺ b = q Υ ϕ , ϕ ∈ Q [[ q , R ]] . (15) Indeed, the last condition says exactly that ν ( q − n − 1 b n ) ≥ 0 \nu(q^{-n-1}b_n)\geq0 ν ( q − n − 1 b n ) ≥ 0 ε ( S ) = 0 \varepsilon(S)=0 ε ( S ) = 0 n + 1 n+1 n + 1 ε ( S ) ≠ 0 \varepsilon(S)\ne0 ε ( S ) = 0 ν ( b n ) = ν ( ε ( S ) ) < n + 1 \nu(b_n)=\nu(\varepsilon(S))<n+1 ν ( b n ) = ν ( ε ( S )) < n + 1 n ≥ ν ( ε ( S ) ) n\geq\nu(\varepsilon(S)) n ≥ ν ( ε ( S ))
Corollary 3.6 (Indirect certificates). If ε ( H 1 ) = ε ( H 2 ) \varepsilon(H_1)=\varepsilon(H_2) ε ( H 1 ) = ε ( H 2 ) ( a , b ) (a,b) ( a , b ) S = ( 1 − U ) a + b ( 1 − R ) S=(1-U)a+b(1-R) S = ( 1 − U ) a + b ( 1 − R ) ν ( a i , j ) ≥ i + j \nu(a_{i,j})\geq i+j ν ( a i , j ) ≥ i + j ν ( b n ) ≥ n + 1 \nu(b_n)\geq n+1 ν ( b n ) ≥ n + 1
Proof. Combine Lemma 3.5, (15) and Theorem 3.2.
Proof of Theorem A. For (1), set u = 1 u=1 u = 1 b n b_n b n K \mathbb{K} K ϕ = q − 1 b ( R / q ) \phi=q^{-1}b(R/q) ϕ = q − 1 b ( R / q ) R R R R / q R/q R / q b b b ⇒ \Rightarrow ⇒
Certifying convergence
Items (c1)–(c3) of a certificate are computed from the automata (§3.5), and by (15) item (c4) is equivalent to the identity itself. We supply (c4) in one of two ways. A direct certificate (Definition 3.9) proves that the preimage ϕ = q − 1 b ( R / q ) \phi=q^{-1}b(R/q) ϕ = q − 1 b ( R / q ) q q q indirect certificate is an independent proof of the identity, which Corollary 3.6 converts into convergence.
Let F ⊂ K ( U ) \mathcal{F}\subset\mathbb{K}(U) F ⊂ K ( U ) Q [ q , U ] \mathbb{Q}[q,U] Q [ q , U ] 1 + q Q [ q , U ] 1+q\mathbb{Q}[q,U] 1 + q Q [ q , U ] g ∈ F g\in\mathcal{F} g ∈ F g ( Υ ) g(\Upsilon) g ( Υ ) R n R^n R n g ( q n ) ∈ Q [ [ q ] ] g(q^n)\in\mathbb{Q}[[q]] g ( q n ) ∈ Q [[ q ]] integral operators ∑ j R j g j ( Υ ) \sum_jR^jg_j(\Upsilon) ∑ j R j g j ( Υ ) g j ∈ F g_j\in\mathcal{F} g j ∈ F Q [ [ q , R ] ] \mathbb{Q}[[q,R]] Q [[ q , R ]] g ( Υ ) R j = R j g ( q j Υ ) g(\Upsilon)R^j=R^jg(q^j\Upsilon) g ( Υ ) R j = R j g ( q j Υ ) L L L integral kernel if the R R R Υ − L \Upsilon-L Υ − L q F q\mathcal{F} q F Υ − L \Upsilon-L Υ − L q q q R R R f ∈ Q [ [ q , R ] ] s f\in\mathbb{Q}[[q,R]]^s f ∈ Q [[ q , R ] ] s m = ∑ k ≥ 0 ( Υ − L ) k f m=\sum_{k\geq0}(\Upsilon-L)^kf m = ∑ k ≥ 0 ( Υ − L ) k f Q [ [ q , R ] ] s \mathbb{Q}[[q,R]]^s Q [[ q , R ] ] s L m = f Lm=f L m = f Q ( ( q ) ) [ [ R ] ] s \mathbb{Q}((q))[[R]]^s Q (( q )) [[ R ] ] s R n R^n R n L m = f Lm=f L m = f m m m Υ \Upsilon Υ q q q f ∈ K [ [ R ] ] s f\in\mathbb{K[[R]]}^s f ∈ K [[ R ]] s m ∈ K [ [ R ] ] s m\in\mathbb{K[[R]]}^s m ∈ K [[ R ]] s
Integral kernels do not always suffice: in (2), the boundary of Euler’s identity combines two series whose coefficients are q q q ℓ ≥ 1 \ell\ge1 ℓ ≥ 1 α ∈ F \alpha\in\mathcal{F} α ∈ F 1 − R ℓ α ( Υ ) 1-R^{\ell}\alpha(\Upsilon) 1 − R ℓ α ( Υ )
u α = ∑ k ≥ 0 ( ∏ j = 0 k − 1 α ( q ℓ j ) ) R ℓ k , ( 1 − R ℓ α ( Υ ) ) u α = 1. u_{\alpha}=\sum_{k\ge0}\left(\prod_{j=0}^{k-1}\alpha\left(q^{\ell^{j}}\right)\right)R^{\ell^{k}},\qquad\left(1-R^{\ell}\alpha(\Upsilon)\right)u_{\alpha}=1. u α = k ≥ 0 ∑ ( j = 0 ∏ k − 1 α ( q ℓ j ) ) R ℓ k , ( 1 − R ℓ α ( Υ ) ) u α = 1. Proposition 3.7 (First-order series). Fix ℓ ≥ 1 \ell\ge1 ℓ ≥ 1 α , β \alpha,\beta α , β 1 + q Q [ q , U ] 1+q\mathbb{Q}[q,U] 1 + q Q [ q , U ] θ = β / α \theta=\beta/\alpha θ = β / α θ − 1 ∈ q c U r F \theta-1\in q^{c}U^{r}\mathcal{F} θ − 1 ∈ q c U r F c ≥ 0 c\ge0 c ≥ 0 r ≥ 1 r\ge1 r ≥ 1
(1) The following are equivalent:
(a) ∏ j ≥ 0 θ ( q ℓ j ) = 1 \prod_{j\ge0}\theta\left(q^{\ell^{j}}\right)=1 ∏ j ≥ 0 θ ( q ℓ j ) = 1
(b) u α − u β = q c Υ r ψ u_{\alpha}-u_{\beta}=q^{c}\Upsilon^{r}\psi u α − u β = q c Υ r ψ ψ ∈ Q [ [ q , R ] ] \psi\in\mathbb{Q}[[q,R]] ψ ∈ Q [[ q , R ]]
(c) the coefficients of u α − u β u_{\alpha}-u_{\beta} u α − u β 0 0 0
(2) Condition (a) holds if there are an integer λ ≥ 2 \lambda\ge2 λ ≥ 2 χ \chi χ 1 + q Q [ q , U ] 1+q\mathbb{Q}[q,U] 1 + q Q [ q , U ] χ ( 0 ) = 1 \chi(0)=1 χ ( 0 ) = 1
θ ( U ) χ ( U ) = ∏ i = 0 λ − 1 χ ( q ℓ i U λ ) . (16) \theta(U)\chi(U)=\prod_{i=0}^{\lambda-1}\chi\left(q^{\ell^{i}}U^{\lambda}\right). \tag*{(16)} θ ( U ) χ ( U ) = i = 0 ∏ λ − 1 χ ( q ℓ i U λ ) . (16) Proof. The coefficient of R ℓ k R^{\ell k} R ℓ k u α u_{\alpha} u α u k = ∏ j < k α ( q ℓ j ) ∈ 1 + q Q [ [ q ] ] u_k=\prod_{j<k}\alpha\left(q^{\ell^{j}}\right)\in1+q\mathbb{Q}[[q]] u k = ∏ j < k α ( q ℓ j ) ∈ 1 + q Q [[ q ]] u β u_{\beta} u β u k π k u_k\pi_k u k π k π k = ∏ j < k θ ( q ℓ j ) \pi_k=\prod_{j<k}\theta\left(q^{\ell^{j}}\right) π k = ∏ j < k θ ( q ℓ j ) ν ( θ ( q ℓ j ) − 1 ) ≥ c + r ℓ j \nu\left(\theta\left(q^{\ell^{j}}\right)-1\right)\ge c+r\ell j ν ( θ ( q ℓ j ) − 1 ) ≥ c + r ℓ j π k \pi_k π k π ∞ = ∏ j ≥ 0 θ ( q ℓ j ) \pi_{\infty}=\prod_{j\ge0}\theta\left(q^{\ell^{j}}\right) π ∞ = ∏ j ≥ 0 θ ( q ℓ j )
(1) If π ∞ = 1 \pi_{\infty}=1 π ∞ = 1 π k = ∏ j ≥ k θ ( q ℓ j ) − 1 ≡ 1 ( m o d q c + r ℓ k ) \pi_k=\prod_{j\ge k}\theta\left(q^{\ell^{j}}\right)^{-1}\equiv1\pmod{q^{c+r\ell k}} π k = ∏ j ≥ k θ ( q ℓ j ) − 1 ≡ 1 ( mod q c + r ℓ k ) u k ( 1 − π k ) u_k(1-\pi_k) u k ( 1 − π k ) R ℓ k R^{\ell k} R ℓ k u α − u β u_{\alpha}-u_{\beta} u α − u β c + r ℓ k c+r\ell k c + r ℓ k [ R n ] q c Υ r ψ = q c + r n [ R n ] ψ [R^n]q^c\Upsilon^r\psi=q^{c+rn}[R^n]\psi [ R n ] q c Υ r ψ = q c + r n [ R n ] ψ r ≥ 1 r\ge1 r ≥ 1 u k ( 1 − π k ) → 0 u_k(1-\pi_k)\to0 u k ( 1 − π k ) → 0 u k u_k u k π k → 1 \pi_k\to1 π k → 1 π ∞ = 1 \pi_{\infty}=1 π ∞ = 1
(2) Since χ ( 0 ) = 1 \chi(0)=1 χ ( 0 ) = 1 χ − 1 ∈ U F \chi-1\in U\mathcal{F} χ − 1 ∈ U F χ ( q ℓ t ) \chi\left(q^{\ell^t}\right) χ ( q ℓ t ) 1 1 1 q ℓ t q^{\ell^t} q ℓ t U = q ℓ j U=q^{\ell^j} U = q ℓ j 0 ≤ j < k 0\le j<k 0 ≤ j < k ( i , j ) (i,j) ( i , j ) { 0 , … , λ − 1 } × { 0 , … , k − 1 } \{0,\ldots,\lambda-1\}\times\{0,\ldots,k-1\} { 0 , … , λ − 1 } × { 0 , … , k − 1 } i + λ j i+\lambda j i + λj { 0 , … , λ k − 1 } \{0,\ldots,\lambda k-1\} { 0 , … , λk − 1 }
π k = ∏ t = 0 λ k − 1 χ ( q ℓ t ) ∏ t = 0 k − 1 χ ( q ℓ t ) = ∏ t = k λ k − 1 χ ( q ℓ t ) ≡ 1 ( m o d q ℓ k ) . \pi_k=\frac{\prod_{t=0}^{\lambda k-1}\chi\left(q^{\ell^t}\right)}{\prod_{t=0}^{k-1}\chi\left(q^{\ell^t}\right)}=\prod_{t=k}^{\lambda k-1}\chi\left(q^{\ell^t}\right)\equiv1\pmod{q^{\ell^k}}. π k = ∏ t = 0 k − 1 χ ( q ℓ t ) ∏ t = 0 λk − 1 χ ( q ℓ t ) = t = k ∏ λk − 1 χ ( q ℓ t ) ≡ 1 ( mod q ℓ k ) . Hence π ∞ = 1 \pi_{\infty}=1 π ∞ = 1
The coefficients of u α u_{\alpha} u α u β u_{\beta} u β q q q R = 1 R=1 R = 1 θ ( q ℓ j ) \theta\left(q^{\ell^j}\right) θ ( q ℓ j ) β ( q ℓ j ) \beta\left(q^{\ell^j}\right) β ( q ℓ j ) α ( q ℓ j ) \alpha\left(q^{\ell^j}\right) α ( q ℓ j ) u β u_{\beta} u β u α u_{\alpha} u α K ( U ) \mathop{\rm K}(U) K ( U ) dilation witness . First-order series arise as bounded counts of languages defined by independent conditions on the multiplicities f h f_h f h
Corollary 3.8 (Periodic product languages). Fix ℓ ≥ 1 \ell\ge1 ℓ ≥ 1 i ∈ Z / ℓ i\in\mathbb{Z}/\ell i ∈ Z / ℓ M i , 1 , M i , 2 ⊆ Z ≥ 0 M_{i,1},M_{i,2}\subseteq\mathbb{Z}_{\ge0} M i , 1 , M i , 2 ⊆ Z ≥ 0 0 0 0 F i ( x ) = ∑ m ∈ M i , 1 x m F_i(x)=\sum_{m\in M_{i,1}}x^m F i ( x ) = ∑ m ∈ M i , 1 x m G i ( x ) = ∑ m ∈ M i , 2 x m G_i(x)=\sum_{m\in M_{i,2}}x^m G i ( x ) = ∑ m ∈ M i , 2 x m H 1 H_1 H 1 h ≥ 1 h\ge1 h ≥ 1 f h f_h f h h h h M h m o d ℓ , 1 M_{h\bmod\ell,1} M h mod ℓ , 1 H 2 H_2 H 2 M i , 2 M_{i,2} M i , 2
α ( U ) = ∏ i = 1 ℓ F i ( q i U ) , β ( U ) = ∏ i = 1 ℓ G i ( q i U ) . \alpha(U)=\prod_{i=1}^{\ell}F_i\left(q^iU\right),\qquad\beta(U)=\prod_{i=1}^{\ell}G_i\left(q^iU\right). α ( U ) = i = 1 ∏ ℓ F i ( q i U ) , β ( U ) = i = 1 ∏ ℓ G i ( q i U ) . If θ = β / α \theta=\beta/\alpha θ = β / α ϵ ( H 1 ) = ϵ ( H 2 ) \epsilon(H_1)=\epsilon(H_2) ϵ ( H 1 ) = ϵ ( H 2 ) H 1 − H 2 H_1-H_2 H 1 − H 2 ν ( a i , j ) ≥ i + j \nu(a_{i,j})\ge i+j ν ( a i , j ) ≥ i + j ν ( b n ) ≥ n + 1 \nu(b_n)\ge n+1 ν ( b n ) ≥ n + 1
Proof. The languages are regular by (4) : an automaton needs to remember only the height modulo ℓ \ell ℓ U U U M i , 1 , M i , 2 M_{i,1}, M_{i,2} M i , 1 , M i , 2 F i ( x ) F_i(x) F i ( x ) 1 + x Q [ x ] 1+x\mathbb{Q}[x] 1 + x Q [ x ] α \alpha α β \beta β θ \theta θ 1 + q Q [ q , U ] 1+q\mathbb{Q}[q,U] 1 + q Q [ q , U ] θ ( 0 ) = 1 \theta(0)=1 θ ( 0 ) = 1 θ − 1 ∈ U F \theta-1\in UF θ − 1 ∈ U F
By Proposition 3.7 , with c = 0 c=0 c = 0 r = 1 r=1 r = 1 u α − u β u_\alpha-u_\beta u α − u β 0 0 0 ℓ j + 1 , … , ℓ j + ℓ \ell j+1,\ldots,\ell j+\ell ℓ j + 1 , … , ℓ j + ℓ 0 ≤ j < k 0\leq j<k 0 ≤ j < k ℓ k \ell k ℓ k ∏ h = 1 ℓ k F h ( q ) = ∏ j < k α ( q ℓ j ) \prod_{h=1}^{\ell k}F_h(q)=\prod_{j<k}\alpha(q^{\ell j}) ∏ h = 1 ℓ k F h ( q ) = ∏ j < k α ( q ℓ j ) (11) , b ℓ k b_{\ell k} b ℓ k R ℓ k R^{\ell k} R ℓ k u α − u β u_\alpha-u_\beta u α − u β b ℓ k → 0 b_{\ell k}\to0 b ℓ k → 0
Since decay along a subsequence suffices in (15) , ε ( H 1 ) = ε ( H 2 ) \varepsilon(H_1)=\varepsilon(H_2) ε ( H 1 ) = ε ( H 2 ) ν ( b n ) ≥ n + 1 \nu(b_n)\geq n+1 ν ( b n ) ≥ n + 1 ν ( a i , j ) ≥ i + j \nu(a_{i,j})\geq i+j ν ( a i , j ) ≥ i + j
Glaisher’s identity (Proposition 4.1) is the basic example.
Definition 3.9. A direct certificate for the convergence of a canonical boundary b b b
finitely many integral inputs : components of solutions of L m = f Lm=f L m = f L L L f ∈ Q [ q ] [ R ] s f\in\mathbb{Q}[q][R]^s f ∈ Q [ q ] [ R ] s ψ \psi ψ Proposition 3.7 (1b), each with a dilation witness;
a series ϕ ′ \phi' ϕ ′ Q [ q ] [ R ] \mathbb{Q}[q][R] Q [ q ] [ R ]
operator identities and selecting values proving b = q Υ ϕ ′ b=q^\Upsilon\phi' b = q Υ ϕ ′
By construction ϕ ′ ∈ Q [ [ q , R ] ] \phi'\in\mathbb{Q}[[q,R]] ϕ ′ ∈ Q [[ q , R ]]
Euler’s identity (Corollary 4.2) and the five-state identity of § 4.7 have direct certificates. The other identities of §4 have indirect ones: Glaisher’s identity by Corollary 3.8, and those of §§§ 4.2 –§ 4.6 by finite telescoping identities, a quadratic invariant (for Primc) and a recurrence with an explicit solution (for Berkovich–Uncu), together with explicit valuation estimates; the proof for Primc also uses the Göllnitz–Gordon identities and Jacobi’s triple product. Appendix A describes further finite tests, not needed for these examples, which bound the valuations of b n b_n b n
Finite searches
The searches were developed to certify the vanishing differences between the 222 354 minimal deterministic interior automata with at most four states, enumerated with one initial state and partial transitions: grouped by their series to order q 50 q^{50} q 50 (16) ; and rational shift quotients for a proposed bounded sum are checked by clearing denominators, as in §4.5. Our JULIA implementation (§4.7) uses such bounded searches, and Appendix A describes further ones.
Telescoping. Let ( f n ) n ≥ 0 (f_n)_{n\geq0} ( f n ) n ≥ 0 f n + 1 = r ( q n ) f n f_{n+1}=r(q^n)f_n f n + 1 = r ( q n ) f n r r r v v v telescoping certificate for a residual ω \omega ω Ψ \Psi Ψ
r ( ζ ) Ψ ( q ζ ) − Ψ ( ζ ) = ω ( ζ ) . (17) r(\zeta)\Psi(q\zeta)-\Psi(\zeta)=\omega(\zeta). \tag*{(17)} r ( ζ ) Ψ ( q ζ ) − Ψ ( ζ ) = ω ( ζ ) . (17) This is an identity between rational functions of an indeterminate ζ \zeta ζ Ψ \Psi Ψ ζ = q n \zeta=q^n ζ = q n f n f_n f n 0 ≤ n ≤ N 0\leq n\leq N 0 ≤ n ≤ N
∑ n = 0 N f n ω ( q n ) = f N + 1 Ψ ( q N + 1 ) − f 0 Ψ ( 1 ) , \sum_{n=0}^{N} f_n\omega(q^n)=f_{N+1}\Psi(q^{N+1})-f_0\Psi(1), n = 0 ∑ N f n ω ( q n ) = f N + 1 Ψ ( q N + 1 ) − f 0 Ψ ( 1 ) , provided that no denominator vanishes at the points q n q^n q n Lemma 3.4 (2), this takes finitely many evaluations. For an infinite sum, the upper flux f N + 1 Ψ ( q N + 1 ) f_{N+1}\Psi(q^{N+1}) f N + 1 Ψ ( q N + 1 ) N N N q N q^N q N Lemma 3.4 (2), applied to numerators and denominators, ν ( r ( q n ) ) \nu(r(q^n)) ν ( r ( q n )) ν ( Ψ ( q n ) ) \nu(\Psi(q^n)) ν ( Ψ ( q n )) n n n n n n ζ \zeta ζ
ν ( f N + 1 Ψ ( q N + 1 ) ) = ν ( f 0 ) + ∑ n = 0 N ν ( r ( q n ) ) + ν ( Ψ ( q N + 1 ) ) \nu\left(f_{N+1}\Psi(q^{N+1})\right)=\nu(f_0)+\sum_{n=0}^{N}\nu(r(q^n))+\nu(\Psi(q^{N+1})) ν ( f N + 1 Ψ ( q N + 1 ) ) = ν ( f 0 ) + n = 0 ∑ N ν ( r ( q n )) + ν ( Ψ ( q N + 1 )) is a quadratic polynomial in N N N N N N + ∞ +\infty + ∞ c ′ N 2 − c c'N^2-c c ′ N 2 − c c ′ > 0 c'>0 c ′ > 0 v v v § 4.2 . All checks are thus manipulations of rational functions in ζ \zeta ζ N N N
Quadratic invariants. For a system F ( z ) = M ( z ) F ( q h z ) F(z)=M(z)F(q^hz) F ( z ) = M ( z ) F ( q h z ) F F F z = 0 z=0 z = 0 J ( z ) J(z) J ( z )
M ( z ) T J ( z ) M ( z ) = λ ( z ) J ( q h z ) M(z)^{\mathsf{T}}J(z)M(z)=\lambda(z)J(q^hz) M ( z ) T J ( z ) M ( z ) = λ ( z ) J ( q h z ) for some polynomial λ ( z ) \lambda(z) λ ( z ) λ \lambda λ J J J λ ( 0 ) = 0 \lambda(0)=0 λ ( 0 ) = 0 F T J F = 0 F^{\mathsf{T}}JF=0 F T J F = 0 g ( z ) g(z) g ( z ) g ( z ) = λ ( z ) g ( q h z ) g(z)=\lambda(z)g(q^hz) g ( z ) = λ ( z ) g ( q h z ) § 4.2 , it is det H = 0 \det H=0 det H = 0 2 × 2 2\times2 2 × 2 H H H H ( v ) = Γ + ( v ) H ( q v ) Γ − T H(v)=\Gamma_+(v)H(qv)\Gamma_-^{\mathsf{T}} H ( v ) = Γ + ( v ) H ( q v ) Γ − T u ( v ) u ( − v ) T u(v)u(-v)^{\mathsf{T}} u ( v ) u ( − v ) T u u u
Partition identities
Glaisher's identity
For an integer λ ≥ 2 \lambda\ge2 λ ≥ 2 H 1 H_1 H 1 H 2 H_2 H 2 λ \lambda λ λ \lambda λ Corollary 3.8 , with ℓ = λ \ell=\lambda ℓ = λ M 0 , 1 = { 0 } M_{0,1}=\{0\} M 0 , 1 = { 0 } M i , 1 = Z ≥ 0 M_{i,1}=\mathbb{Z}_{\ge0} M i , 1 = Z ≥ 0 i ≢ 0 i\not\equiv0 i ≡ 0 M i , 2 = { 0 , … , λ − 1 } M_{i,2}=\{0,\ldots,\lambda-1\} M i , 2 = { 0 , … , λ − 1 }
F i ( x ) = 1 1 − x ( i ≢ 0 ) , F 0 ( x ) = 1 , G i ( x ) = 1 + x + ⋯ + x λ − 1 . F_i(x)=\frac{1}{1-x}\quad(i\not\equiv0),\qquad F_0(x)=1,\qquad G_i(x)=1+x+\cdots+x^{\lambda-1}. F i ( x ) = 1 − x 1 ( i ≡ 0 ) , F 0 ( x ) = 1 , G i ( x ) = 1 + x + ⋯ + x λ − 1 . For λ = 2 \lambda=2 λ = 2 H o H_o H o H d H_d H d
Proposition 4.1 (following Glaisher [10 ] ). Let λ ≥ 2 \lambda\ge2 λ ≥ 2 n n n n n n λ \lambda λ λ \lambda λ λ = 2 \lambda=2 λ = 2 H 1 − H 2 H_1-H_2 H 1 − H 2 ν ( a i , j ) ≥ i + j \nu(a_{i,j})\ge i+j ν ( a i , j ) ≥ i + j ν ( b n ) ≥ n + 1 \nu(b_n)\ge n+1 ν ( b n ) ≥ n + 1
Proof. In the notation of Corollary 3.8 , since G i ( x ) = ( 1 − x λ ) / ( 1 − x ) G_i(x)=(1-x^\lambda)/(1-x) G i ( x ) = ( 1 − x λ ) / ( 1 − x )
α ( U ) = ∏ i = 1 λ − 1 1 1 − q i U , β ( U ) = ∏ i = 1 λ 1 − q λ i U λ 1 − q i U . \alpha(U)=\prod_{i=1}^{\lambda-1}\frac{1}{1-q^iU},\qquad\beta(U)=\prod_{i=1}^{\lambda}\frac{1-q^{\lambda i}U^\lambda}{1-q^{i}U}. α ( U ) = i = 1 ∏ λ − 1 1 − q i U 1 , β ( U ) = i = 1 ∏ λ 1 − q i U 1 − q λi U λ . The factors 1 − q i U 1-q^iU 1 − q i U i < λ i<\lambda i < λ θ = β / α \theta=\beta/\alpha θ = β / α
θ ( U ) = ∏ i = 1 λ − 1 ( 1 − q λ i U λ ) 1 − q λ U . \theta(U)=\frac{\prod_{i=1}^{\lambda-1}(1-q^{\lambda i}U^\lambda)}{1-q^{\lambda}U}. θ ( U ) = 1 − q λ U ∏ i = 1 λ − 1 ( 1 − q λi U λ ) . The polynomial χ ( U ) = 1 − q λ U \chi(U)=1-q^\lambda U χ ( U ) = 1 − q λ U (16) equal the numerator of θ \theta θ Corollary 3.8 concludes.
The dilation witness encodes the classical argument 1 + x + ⋯ + x λ − 1 = ( 1 − x λ ) / ( 1 − x ) 1+x+\cdots+x^{\lambda-1}=(1-x^\lambda)/(1-x) 1 + x + ⋯ + x λ − 1 = ( 1 − x λ ) / ( 1 − x ) b k b_k b k λ = 2 \lambda=2 λ = 2 Definition 3.9 ), whose checks use only the kernels.
Corollary 4.2 (Euler’s certificate). In the notation of §1, the canonical boundary b b b H o − H d H_o-H_d H o − H d b = q Υ b ′ b=q\Upsilon b' b = q Υ b ′ b ′ = q w + R ( 1 − q Υ ) − 1 ( w + Υ v ) ∈ Q [ [ q , R ] ] b'=qw+R(1-q\Upsilon)^{-1}(w+\Upsilon v)\in\mathbb{Q}[[q,R]] b ′ = q w + R ( 1 − q Υ ) − 1 ( w + Υ v ) ∈ Q [[ q , R ]]
Proof. For λ = 2 \lambda=2 λ = 2
α ( U ) = 1 1 − q U , β ( U ) = B ( U ) = ( 1 + q U ) ( 1 + q 2 U ) , χ ( U ) = 1 − q 2 U . \alpha(U)=\frac{1}{1-qU},\qquad\beta(U)=B(U)=(1+qU)(1+q^2U),\qquad\chi(U)=1-q^2U. α ( U ) = 1 − q U 1 , β ( U ) = B ( U ) = ( 1 + q U ) ( 1 + q 2 U ) , χ ( U ) = 1 − q 2 U . and θ ( U ) = ( 1 − q U ) ( 1 + q U ) ( 1 + q 2 U ) \theta(U)=(1-qU)(1+qU)(1+q^2U) θ ( U ) = ( 1 − q U ) ( 1 + q U ) ( 1 + q 2 U ) u = u α u=u_\alpha u = u α v = u β v=u_\beta v = u β ℓ = 2 \ell=2 ℓ = 2 c = 2 c=2 c = 2 r = 1 r=1 r = 1 u − v = q 2 Υ w u-v=q^2\Upsilon w u − v = q 2 Υ w w ∈ Q [ [ q , R ] ] w\in\mathbb{Q}[[q,R]] w ∈ Q [[ q , R ]]
In the computations below, g ( Υ ) R ℓ = R ℓ g ( q ℓ Υ ) g(\Upsilon)R^\ell=R^\ell g(q^\ell\Upsilon) g ( Υ ) R ℓ = R ℓ g ( q ℓ Υ )
Put B o = ( 1 + R ( 1 − q Υ ) − 1 ) u B_o=(1+R(1-q\Upsilon)^{-1})u B o = ( 1 + R ( 1 − q Υ ) − 1 ) u B d = ( 1 + R ( 1 + q Υ ) ) v B_d=(1+R(1+q\Upsilon))v B d = ( 1 + R ( 1 + q Υ )) v u u u v v v
( 1 − q Υ − q 2 R 2 ) Υ ( 1 − q Υ ) − 1 u = Υ ( u − R 2 ( 1 − q Υ ) − 1 u ) = 1 , (1-q\Upsilon-q^2R^2)\Upsilon(1-q\Upsilon)^{-1}u=\Upsilon(u-R^2(1-q\Upsilon)^{-1}u)=1, ( 1 − q Υ − q 2 R 2 ) Υ ( 1 − q Υ ) − 1 u = Υ ( u − R 2 ( 1 − q Υ ) − 1 u ) = 1 , ( 1 − q R − q 2 R Υ ) Υ B d = Υ ( 1 − R ( 1 + q Υ ) ) B d = Υ ( 1 − R 2 B ( Υ ) ) v = 1. (1-qR-q^2R\Upsilon)\Upsilon B_d=\Upsilon(1-R(1+q\Upsilon))B_d=\Upsilon(1-R^2B(\Upsilon))v=1. ( 1 − q R − q 2 R Υ ) Υ B d = Υ ( 1 − R ( 1 + q Υ )) B d = Υ ( 1 − R 2 B ( Υ )) v = 1. By uniqueness of normalized solutions, m o , 1 = Υ ( 1 − q Υ ) − 1 u m_{o,1}=\Upsilon(1-q\Upsilon)^{-1}u m o , 1 = Υ ( 1 − q Υ ) − 1 u m d , 1 = Υ B d m_{d,1}=\Upsilon B_d m d , 1 = Υ B d
( 1 − R ) B o = 1 + R ( ( 1 − q Υ ) − 1 − 1 ) u = 1 + q R m o , 1 , (1-R)B_o=1+R((1-q\Upsilon)^{-1}-1)u=1+qRm_{o,1}, ( 1 − R ) B o = 1 + R (( 1 − q Υ ) − 1 − 1 ) u = 1 + q R m o , 1 , ( 1 − R ) B d = 1 + q R Υ B d = 1 + q R m d , 1 . (1-R)B_d=1+qR\Upsilon B_d=1+qRm_{d,1}. ( 1 − R ) B d = 1 + q R Υ B d = 1 + q R m d , 1 . Hence ( 1 − R ) ( B o − B d ) = D ( 1 , R ) (1-R)(B_o-B_d)=D(1,R) ( 1 − R ) ( B o − B d ) = D ( 1 , R ) b = B o − B d b=B_o-B_d b = B o − B d u = v + q 2 Υ w u=v+q^2\Upsilon w u = v + q 2 Υ w
( 1 − q Υ ) − 1 − ( 1 + q Υ ) = q 2 ( 1 − q Υ ) − 1 (1-q\Upsilon)^{-1}-(1+q\Upsilon)=q^2(1-q\Upsilon)^{-1} ( 1 − q Υ ) − 1 − ( 1 + q Υ ) = q 2 ( 1 − q Υ ) − 1 and q 2 R Υ = q Υ R q^2R\Upsilon=q\Upsilon R q 2 R Υ = q Υ R
B o − B d = q 2 Υ w + q 2 R Υ ( 1 − q Υ ) − 1 ( w + Υ v ) = q Υ b ′ . B_o-B_d=q^2\Upsilon w+q^2R\Upsilon(1-q\Upsilon)^{-1}(w+\Upsilon v)=q\Upsilon b'. B o − B d = q 2 Υ w + q 2 R Υ ( 1 − q Υ ) − 1 ( w + Υ v ) = q Υ b ′ . Primc’s three-row identities at level two
We now prove Theorem B , following the strategy of §§1–3. Both partition classes are recognized by automata (Figure 1 ). In A, left multiplication turns the automaton of the admissible partitions into a linear system of q q q x x x R = 1 R=1 R = 1 x = 1 x=1 x = 1 Theorem B , and Corollary 3.6 converts the resulting equalities into convergent holonomic certificates for the automata.
From automata to four states
The admissible partitions are recognized by the window automaton of Lemma 3.1 , with r = W = 3 r=W=3 r = W = 3 M = 2 M=2 M = 2 K = 2 K=2 K = 2 M = 8 M=8 M = 8 Figure 1 shows both for the boundary ( 2 , 0 , 0 ) (2,0,0) ( 2 , 0 , 0 ) τ n \tau_n τ n β n \beta_n β n μ n \mu_n μ n Theorem B . Once an even height is complete, the window automaton only needs to remember the pair ( τ , β ) (\tau,\beta) ( τ , β ) ( τ 0 , β 0 ) = ( k 2 , k 0 ) (\tau_0,\beta_0)=(k_2,k_0) ( τ 0 , β 0 ) = ( k 2 , k 0 ) ( τ , β ) (\tau,\beta) ( τ , β ) F τ , β ( z ) F_{\tau,\beta}(z) F τ , β ( z ) ( μ n , τ n , β n ) n ≥ 1 (\mu_n,\tau_n,\beta_n)_{n\geq1} ( μ n , τ n , β n ) n ≥ 1 ( τ 0 , β 0 ) = ( τ , β ) (\tau_0,\beta_0)=(\tau,\beta) ( τ 0 , β 0 ) = ( τ , β ) z z z q q q ( τ , β ) (\tau,\beta) ( τ , β ) μ \mu μ τ ′ + β ′ \tau'+\beta' τ ′ + β ′ ( z q ) μ ( z q 2 ) τ ′ + β ′ (zq)^\mu(zq^2)^{\tau'+\beta'} ( z q ) μ ( z q 2 ) τ ′ + β ′ z ↦ q 2 z z\mapsto q^2z z ↦ q 2 z 0 ≤ μ ≤ 2 − max ( τ , τ ′ ) − max ( β , β ′ ) 0\leq\mu\leq2-\max(\tau,\tau')-\max(\beta,\beta') 0 ≤ μ ≤ 2 − max ( τ , τ ′ ) − max ( β , β ′ )
F τ , β ( z ) = ∑ τ ′ , β ′ ≥ 0 ( z q 2 ) τ ′ + β ′ ∑ μ = 0 2 − max ( τ , τ ′ ) − max ( β , β ′ ) ( z q ) μ F τ ′ , β ′ ( q 2 z ) . F_{\tau,\beta}(z)=\sum_{\tau',\beta'\geq0}(zq^2)^{\tau'+\beta'}\sum_{\mu=0}^{2-\max(\tau,\tau')-\max(\beta,\beta')}(zq)^\mu F_{\tau',\beta'}(q^2z). F τ , β ( z ) = τ ′ , β ′ ≥ 0 ∑ ( z q 2 ) τ ′ + β ′ μ = 0 ∑ 2 − m a x ( τ , τ ′ ) − m a x ( β , β ′ ) ( z q ) μ F τ ′ , β ′ ( q 2 z ) . where a negative upper bound contributes zero. This is the opposite realization of §3.5, before normalization, with the letters of two consecutive heights grouped together. Since F τ , β = F β , τ F_{\tau,\beta}=F_{\beta,\tau} F τ , β = F β , τ ( 0 , 0 ) (0,0) ( 0 , 0 ) ( 0 , 0 ) (0,0) ( 0 , 0 ) μ ≤ 2 \mu\leq2 μ ≤ 2 ( 0 , 1 ) (0,1) ( 0 , 1 ) ( 1 , 0 ) (1,0) ( 1 , 0 ) ( 0 , 2 ) (0,2) ( 0 , 2 ) ( 2 , 0 ) (2,0) ( 2 , 0 ) ( 1 , 1 ) (1,1) ( 1 , 1 ) μ = 0 \mu=0 μ = 0 F = ( F 00 , F 01 , F 02 , F 11 ) T F=(F_{00},F_{01},F_{02},F_{11})^{\mathsf T} F = ( F 00 , F 01 , F 02 , F 11 ) T s = q z s=qz s = q z t = q 2 z t=q^2z t = q 2 z
F ( z ) = M ( z ) F ( q 2 z ) , M ( z ) = ( 1 + s + s 2 2 t ( 1 + s ) 2 t 2 t 2 1 + s t ( 2 + s ) t 2 t 2 1 t t 2 0 1 2 t 0 t 2 ) . (18) F(z)=\mathrm{M}(z)F(q^2z),\qquad\mathrm{M}(z)=\begin{pmatrix}1+s+s^2&2t(1+s)&2t^2&t^2\\1+s&t(2+s)&t^2&t^2\\1&t&t^2&0\\1&2t&0&t^2\end{pmatrix}. \tag*{(18)} F ( z ) = M ( z ) F ( q 2 z ) , M ( z ) = 1 + s + s 2 1 + s 1 1 2 t ( 1 + s ) t ( 2 + s ) t 2 t 2 t 2 t 2 t 2 0 t 2 t 2 0 t 2 . (18) The empty tail gives F ( 0 ) = ( 1 , 1 , 1 , 1 ) T F(0)=(1,1,1,1)^{\mathsf T} F ( 0 ) = ( 1 , 1 , 1 , 1 ) T M ( 0 ) \mathrm{M}(0) M ( 0 ) I − q 2 n M ( 0 ) \mathbb{I}-q^{2n}\mathrm{M}(0) I − q 2 n M ( 0 ) n ≥ 1 n\ge1 n ≥ 1 Q ( q ) [ [ z ] ] 4 \mathbb{Q}(q)[[z]]^4 Q ( q ) [[ z ] ] 4
The four generating functions of Theorem B are, in order, Π 2 , 0 , 0 = F 02 ( 1 ) \Pi_{2,0,0}=F_{02}(1) Π 2 , 0 , 0 = F 02 ( 1 ) Π 1 , 1 , 0 = F 01 ( 1 ) \Pi_{1,1,0}=F_{01}(1) Π 1 , 1 , 0 = F 01 ( 1 ) Π 1 , 0 , 1 = F 11 ( 1 ) \Pi_{1,0,1}=F_{11}(1) Π 1 , 0 , 1 = F 11 ( 1 ) Π 0 , 2 , 0 = F 00 ( 1 ) \Pi_{0,2,0}=F_{00}(1) Π 0 , 2 , 0 = F 00 ( 1 ) z z z F 02 F_{02} F 02 F 00 F_{00} F 00 F 01 F_{01} F 01 F 11 F_{11} F 11 D 2 Λ 0 ( 2 ) D^{(2)}_{2\Lambda_0} D 2 Λ 0 ( 2 ) D 2 Λ 0 ( 2 ) D^{(2)}_{2\Lambda_0} D 2 Λ 0 ( 2 ) D Λ 0 + Λ 1 ( 2 ) D^{(2)}_{\Lambda_0+\Lambda_1} D Λ 0 + Λ 1 ( 2 ) D Λ 0 + Λ 2 ( 2 ) D^{(2)}_{\Lambda_0+\Lambda_2} D Λ 0 + Λ 2 ( 2 ) [15 §4] .
Factoring the four-state system
The search for quadratic invariants of §3.8, applied to (18), finds
J ( z ) = ( 0 0 0 1 0 − 2 0 0 0 0 2 q z 0 1 0 0 0 ) , λ ( z ) = − q 5 z 3 ( 1 − q z ) , J(z)=\begin{pmatrix}0&0&0&1\\0&-2&0&0\\0&0&2qz&0\\1&0&0&0\end{pmatrix},\qquad\lambda(z)=-q^5z^3(1-qz), J ( z ) = 0 0 0 1 0 − 2 0 0 0 0 2 q z 0 1 0 0 0 , λ ( z ) = − q 5 z 3 ( 1 − q z ) , and polynomial arithmetic checks that M ( z ) T J ( z ) M ( z ) = λ ( z ) J ( q 2 z ) \mathrm{M}(z)^{\mathsf T}J(z)\mathrm{M}(z)=\lambda(z)J(q^2z) M ( z ) T J ( z ) M ( z ) = λ ( z ) J ( q 2 z ) J J J z z z det M ( z ) = q 11 z 6 ( 1 − q z 2 ) \det\mathrm{M}(z)=q^{11}z^6(1-qz^2) det M ( z ) = q 11 z 6 ( 1 − q z 2 ) λ = ± q 5 z 3 ( 1 − q z ) \lambda=\pm q^5z^3(1-qz) λ = ± q 5 z 3 ( 1 − q z ) M T J M − λ J ( q 2 z ) \mathrm{M}^{\mathsf T}J\mathrm{M}-\lambda J(q^2z) M T J M − λ J ( q 2 z ) z z z 60 × 20 60\times20 60 × 20 Q ( q ) \mathbb{Q}(q) Q ( q ) J J J λ ( 0 ) = 0 \lambda(0)=0 λ ( 0 ) = 0 F T J F = 0 F^{\mathsf T}JF=0 F T J F = 0
F 00 ( z ) F 11 ( z ) = F 01 ( z ) 2 − q z F 02 ( z ) 2 (19) F_{00}(z)F_{11}(z)=F_{01}(z)^2-qzF_{02}(z)^2 \tag*{(19)} F 00 ( z ) F 11 ( z ) = F 01 ( z ) 2 − q z F 02 ( z ) 2 (19) This relation suggests assembling the four series into a matrix of determinant zero. Introduce v v v v 2 = q z v^2=qz v 2 = q z
H ( v ) = ( F 00 ( v 2 / q ) F 01 ( v 2 / q ) + v F 02 ( v 2 / q ) F 01 ( v 2 / q ) − v F 02 ( v 2 / q ) F 11 ( v 2 / q ) ) H(v)=\begin{pmatrix}F_{00}(v^2/q)&F_{01}(v^2/q)+vF_{02}(v^2/q)\\F_{01}(v^2/q)-vF_{02}(v^2/q)&F_{11}(v^2/q)\end{pmatrix} H ( v ) = ( F 00 ( v 2 / q ) F 01 ( v 2 / q ) − v F 02 ( v 2 / q ) F 01 ( v 2 / q ) + v F 02 ( v 2 / q ) F 11 ( v 2 / q ) ) and
Γ ± ( v ) = ( 1 ± v + v 2 q v 2 1 q v 2 ) . \Gamma_{\pm}(v)=\begin{pmatrix}1\pm v+v^2&qv^2\\1&qv^2\end{pmatrix}. Γ ± ( v ) = ( 1 ± v + v 2 1 q v 2 q v 2 ) . By (18), direct multiplication gives the exact identity
H ( v ) = Γ + ( v ) H ( q v ) Γ − ( v ) T ; (20) H(v)=\Gamma_{+}(v)H(qv)\Gamma_{-}(v)^{\mathsf T}; \tag*{(20)} H ( v ) = Γ + ( v ) H ( q v ) Γ − ( v ) T ; (20) thus the transfer acts on H H H det H = 0 \det H=0 det H = 0 Γ 0 = Γ ± ( 0 ) \Gamma_0=\Gamma_{\pm}(0) Γ 0 = Γ ± ( 0 ) P ( Z ) = Γ 0 Z Γ 0 T \mathcal{P}(Z)=\Gamma_0Z\Gamma_0^{\mathsf T} P ( Z ) = Γ 0 Z Γ 0 T 2 × 2 2\times2 2 × 2 Z Z Z H ( v ) = ∑ n H n v n H(v)=\sum_n H_nv^n H ( v ) = ∑ n H n v n v n v^n v n ( I − q n P ) H n (\mathbb{I}-q^n\mathcal{P})H_n ( I − q n P ) H n H 0 , … , H n − 1 H_0,\ldots,H_{n-1} H 0 , … , H n − 1 P 2 = P \mathcal{P}^2=\mathcal{P} P 2 = P I − q n P \mathbb{I}-q^n\mathcal{P} I − q n P n > 0 n>0 n > 0
( I − q n P ) − 1 = I + q n 1 − q n P , (\mathbb{I}-q^n\mathcal{P})^{-1}=\mathbb{I}+\frac{q^n}{1-q^n}\mathcal{P}, ( I − q n P ) − 1 = I + 1 − q n q n P , and for n = 0 n=0 n = 0 P \mathcal{P} P
Let u ( v ) = ( g ( v ) , h ( v ) ) T u(v)=(g(v),h(v))^{\mathsf T} u ( v ) = ( g ( v ) , h ( v ) ) T
u ( v ) = Γ + ( v ) u ( q v ) , u ( 0 ) = ( 1 , 1 ) T . (21) u(v)=\Gamma_{+}(v)u(qv),\qquad u(0)=(1,1)^{\mathsf T}. \tag*{(21)} u ( v ) = Γ + ( v ) u ( q v ) , u ( 0 ) = ( 1 , 1 ) T . (21) The same argument proves uniqueness. Since Γ − ( v ) = Γ + ( − v ) \Gamma_{-}(v)=\Gamma_{+}(-v) Γ − ( v ) = Γ + ( − v ) u ( v ) u ( − v ) T u(v)u(-v)^{\mathsf T} u ( v ) u ( − v ) T
F 00 ( v 2 / q ) = g ( v ) g ( − v ) , F 11 ( v 2 / q ) = h ( v ) h ( − v ) , (22) F_{00}(v^2/q)=g(v)g(-v),\qquad F_{11}(v^2/q)=h(v)h(-v), \tag*{(22)} F 00 ( v 2 / q ) = g ( v ) g ( − v ) , F 11 ( v 2 / q ) = h ( v ) h ( − v ) , (22) F 01 ( v 2 / q ) = g ( v ) h ( − v ) + h ( v ) g ( − v ) 2 , F 02 ( v 2 / q ) = g ( v ) h ( − v ) − h ( v ) g ( − v ) 2 v . (23) F_{01}(v^2/q)=\frac{g(v)h(-v)+h(v)g(-v)}{2},\qquad F_{02}(v^2/q)=\frac{g(v)h(-v)-h(v)g(-v)}{2v}. \tag*{(23)} F 01 ( v 2 / q ) = 2 g ( v ) h ( − v ) + h ( v ) g ( − v ) , F 02 ( v 2 / q ) = 2 v g ( v ) h ( − v ) − h ( v ) g ( − v ) . (23) Two finite telescoping certificates
The solution of (21) is
g ( v ) = ∑ n ≥ 0 q n ( n − 1 ) / 2 v n ( − v ; q ) n ( q ; q ) n , h ( v ) = ∑ n ≥ 0 q n ( n + 1 ) / 2 v n ( − v ; q ) n ( q ; q ) n . (24) g(v)=\sum_{n\ge0}\frac{q^{n(n-1)/2}v^n(-v;q)_n}{(q;q)_n},\qquad h(v)=\sum_{n\ge0}\frac{q^{n(n+1)/2}v^n(-v;q)_n}{(q;q)_n}. \tag*{(24)} g ( v ) = n ≥ 0 ∑ ( q ; q ) n q n ( n − 1 ) /2 v n ( − v ; q ) n , h ( v ) = n ≥ 0 ∑ ( q ; q ) n q n ( n + 1 ) /2 v n ( − v ; q ) n . (24) To verify this, set
f n ( v ) = q n ( n − 1 ) / 2 v n ( − v ; q ) n ( q ; q ) n , ζ = q n , f_n(v)=\frac{q^{n(n-1)/2}v^n(-v;q)_n}{(q;q)_n},\qquad\zeta=q^n, f n ( v ) = ( q ; q ) n q n ( n − 1 ) /2 v n ( − v ; q ) n , ζ = q n , so that h = ∑ n ζ f n h=\sum_n\zeta f_n h = ∑ n ζ f n
f n + 1 ( v ) f n ( v ) = r ( ζ ) : = v ζ ( 1 + v ζ ) 1 − q ζ , f n ( q v ) f n ( v ) = ζ ( 1 + v ζ ) 1 + v . \frac{f_{n+1}(v)}{f_n(v)}=r(\zeta):=\frac{v\zeta(1+v\zeta)}{1-q\zeta},\qquad\frac{f_n(qv)}{f_n(v)}=\frac{\zeta(1+v\zeta)}{1+v}. f n ( v ) f n + 1 ( v ) = r ( ζ ) := 1 − q ζ v ζ ( 1 + v ζ ) , f n ( v ) f n ( q v ) = 1 + v ζ ( 1 + v ζ ) . The two telescoping certificates
Ψ 0 ( ζ ) = ζ − 1 , Ψ 1 ( ζ ) = − v ζ ( 1 − ζ ) 1 + v \Psi_0(\zeta)=\zeta-1,\qquad\Psi_1(\zeta)=-\frac{v\zeta(1-\zeta)}{1+v} Ψ 0 ( ζ ) = ζ − 1 , Ψ 1 ( ζ ) = − 1 + v v ζ ( 1 − ζ ) satisfy (17) with the following residuals:
r ( ζ ) Ψ 0 ( q ζ ) − Ψ 0 ( ζ ) = 1 − ζ − v ζ ( 1 + v ζ ) , (25) r(\zeta)\Psi_0(q\zeta)-\Psi_0(\zeta)=1-\zeta-v\zeta(1+v\zeta), \tag*{(25)} r ( ζ ) Ψ 0 ( q ζ ) − Ψ 0 ( ζ ) = 1 − ζ − v ζ ( 1 + v ζ ) , (25) r ( ζ ) Ψ 1 ( q ζ ) − Ψ 1 ( ζ ) = v ζ ( 1 − ζ ) − q v 2 ζ 2 ( 1 + v ζ ) 1 + v . (26) r(\zeta)\Psi_1(q\zeta)-\Psi_1(\zeta)=\frac{v\zeta(1-\zeta)-qv^2\zeta^2(1+v\zeta)}{1+v}. \tag*{(26)} r ( ζ ) Ψ 1 ( q ζ ) − Ψ 1 ( ζ ) = 1 + v v ζ ( 1 − ζ ) − q v 2 ζ 2 ( 1 + v ζ ) . (26) Multiply by f n ( v ) f_n(v) f n ( v ) N N N Ψ i ( 1 ) = 0 \Psi_i(1)=0 Ψ i ( 1 ) = 0 f N + 1 ( v ) Ψ i ( q N + 1 ) f_{N+1}(v)\Psi_i(q^{N+1}) f N + 1 ( v ) Ψ i ( q N + 1 ) v v v N + 1 N+1 N + 1 Q [ [ v ] ] \mathbb{Q}[[v]] Q [[ v ]]
g ( v ) − h ( v ) = v ( 1 + v ) g ( q v ) , h ( v ) = g ( q v ) + q v 2 h ( q v ) . g(v)-h(v)=v(1+v)g(qv),\qquad h(v)=g(qv)+qv^2h(qv). g ( v ) − h ( v ) = v ( 1 + v ) g ( q v ) , h ( v ) = g ( q v ) + q v 2 h ( q v ) . These are precisely (21), and uniqueness proves (24). Both certificates were found by the search of §3.8: with Ψ \Psi Ψ ζ \zeta ζ 1 − q ζ 1-q\zeta 1 − q ζ r r r Q ( q , v ) \mathbb{Q}(q,v) Q ( q , v ) 4 × 3 4\times3 4 × 3 5 × 4 5\times4 5 × 4
Göllnitz–Gordon specialization
Put q = r 2 q=r^2 q = r 2 v = r v=r v = r
g ( r ; r 2 ) = ∑ n ≥ 0 r n 2 ( − r ; r 2 ) n ( r 2 ; r 2 ) n = 1 ( r , r 4 , r 7 ; r 8 ) ∞ , (27) g(r;r^2)=\sum_{n\ge0}\frac{r^{n^2}(-r;r^2)_n}{(r^2;r^2)_n}=\frac{1}{(r,r^4,r^7;r^8)_\infty}, \tag*{(27)} g ( r ; r 2 ) = n ≥ 0 ∑ ( r 2 ; r 2 ) n r n 2 ( − r ; r 2 ) n = ( r , r 4 , r 7 ; r 8 ) ∞ 1 , (27) h ( r ; r 2 ) = ∑ n ≥ 0 r n 2 + 2 n ( − r ; r 2 ) n ( r 2 ; r 2 ) n = 1 ( r 3 , r 4 , r 5 ; r 8 ) ∞ . (28) h(r;r^2)=\sum_{n\ge0}\frac{r^{n^2+2n}(-r;r^2)_n}{(r^2;r^2)_n}=\frac{1}{(r^3,r^4,r^5;r^8)_\infty}. \tag*{(28)} h ( r ; r 2 ) = n ≥ 0 ∑ ( r 2 ; r 2 ) n r n 2 + 2 n ( − r ; r 2 ) n = ( r 3 , r 4 , r 5 ; r 8 ) ∞ 1 . (28) The final equalities are the Göllnitz–Gordon identities [11 , 13 ] . Since n 2 n^2 n 2 n 2 + 2 n n^2+2n n 2 + 2 n n n n r r r − r -r − r g ( − r ; r 2 ) g(-r;r^2) g ( − r ; r 2 ) h ( − r ; r 2 ) h(-r;r^2) h ( − r ; r 2 )
The series g g g h h h F τ , β ( v 2 / q ) F_{\tau,\beta}(v^2/q) F τ , β ( v 2 / q ) Q [ [ q , v ] ] \mathbb{Q}[[q,v]] Q [[ q , v ]] k k k k k k z k = q − k v 2 k z^k=q^{-k}v^{2k} z k = q − k v 2 k q ↦ r 2 q\mapsto r^2 q ↦ r 2 v ↦ r v\mapsto r v ↦ r Q [ [ q , v ] ] → Q [ [ r ] ] \mathbb{Q}[[q,v]]\to\mathbb{Q}[[r]] Q [[ q , v ]] → Q [[ r ]] z = 1 z=1 z = 1
Pairing the odd factors in the products at r r r − r -r − r
F 00 ( 1 ; q ) = g ( r ; r 2 ) g ( − r ; r 2 ) = 1 ( q , q 7 ; q 8 ) ∞ ( q 2 ; q 4 ) ∞ 2 , F_{00}(1;q)=g(r;r^2)g(-r;r^2)=\frac{1}{(q,q^7;q^8)_\infty(q^2;q^4)_\infty^2}, F 00 ( 1 ; q ) = g ( r ; r 2 ) g ( − r ; r 2 ) = ( q , q 7 ; q 8 ) ∞ ( q 2 ; q 4 ) ∞ 2 1 , F 11 ( 1 ; q ) = h ( r ; r 2 ) h ( − r ; r 2 ) = 1 ( q 3 , q 5 ; q 8 ) ∞ ( q 2 ; q 4 ) ∞ 2 . F_{11}(1;q)=h(r;r^2)h(-r;r^2)=\frac{1}{(q^3,q^5;q^8)_\infty(q^2;q^4)_\infty^2}. F 11 ( 1 ; q ) = h ( r ; r 2 ) h ( − r ; r 2 ) = ( q 3 , q 5 ; q 8 ) ∞ ( q 2 ; q 4 ) ∞ 2 1 . These are the products for the last and third rows of Theorem B: residues 1, 7, respectively 3, 5, have one colour, and residues 2, 6 have two colours.
The two cross-products
Write θ ( y ; p ) = ( y , p / y ; p ) ∞ \theta(y;p)=(y,p/y;p)_\infty θ ( y ; p ) = ( y , p / y ; p ) ∞ [1 Theorem 2.8] gives, in Z [ y 1 ± 1 , y 2 ± 1 ] [ [ p ] ] \mathbb{Z}[y_1^{\pm1},y_2^{\pm1}][[p]] Z [ y 1 ± 1 , y 2 ± 1 ] [[ p ]]
θ ( − y 1 ; p ) θ ( y 2 ; p ) + θ ( y 1 ; p ) θ ( − y 2 ; p ) = 2 ( p 2 ; p 2 ) ∞ 2 ( p ; p ) ∞ 2 θ ( y 1 y 2 ; p 2 ) θ ( p y 1 / y 2 ; p 2 ) . (29) \theta(-y_1;p)\theta(y_2;p)+\theta(y_1;p)\theta(-y_2;p)=2\frac{(p^2;p^2)_\infty^2}{(p;p)_\infty^2}\theta(y_1y_2;p^2)\theta(py_1/y_2;p^2). \tag*{(29)} θ ( − y 1 ; p ) θ ( y 2 ; p ) + θ ( y 1 ; p ) θ ( − y 2 ; p ) = 2 ( p ; p ) ∞ 2 ( p 2 ; p 2 ) ∞ 2 θ ( y 1 y 2 ; p 2 ) θ ( p y 1 / y 2 ; p 2 ) . (29) θ ( − y 1 ; p ) θ ( y 2 ; p ) − θ ( y 1 ; p ) θ ( − y 2 ; p ) = 2 y 1 ( p 2 ; p 2 ) ∞ 2 ( p ; p ) ∞ 2 θ ( y 2 / y 1 ; p 2 ) θ ( p y 1 y 2 ; p 2 ) . (30) \theta(-y_1;p)\theta(y_2;p)-\theta(y_1;p)\theta(-y_2;p)=2y_1\frac{(p^2;p^2)_\infty^2}{(p;p)_\infty^2}\theta(y_2/y_1;p^2)\theta(py_1y_2;p^2). \tag*{(30)} θ ( − y 1 ; p ) θ ( y 2 ; p ) − θ ( y 1 ; p ) θ ( − y 2 ; p ) = 2 y 1 ( p ; p ) ∞ 2 ( p 2 ; p 2 ) ∞ 2 θ ( y 2 / y 1 ; p 2 ) θ ( p y 1 y 2 ; p 2 ) . (30) These two dissections follow by multiplying the left sides by ( p ; p ) ∞ 2 (p;p)_\infty^2 ( p ; p ) ∞ 2 ( − 1 ) n ± ( − 1 ) m (-1)^n\pm(-1)^m ( − 1 ) n ± ( − 1 ) m m = k + l m=k+l m = k + l n = k − l n=k-l n = k − l k 2 + l 2 − k k^2+l^2-k k 2 + l 2 − k ( y 1 y 2 ) k ( y 1 / y 2 ) l (y_1y_2)^k(y_1/y_2)^l ( y 1 y 2 ) k ( y 1 / y 2 ) l m = k + l + 1 m=k+l+1 m = k + l + 1 n = k − l n=k-l n = k − l k 2 + l 2 + l k^2+l^2+l k 2 + l 2 + l y 1 ( y 1 y 2 ) k ( y 1 / y 2 ) l y_1(y_1y_2)^k(y_1/y_2)^l y 1 ( y 1 y 2 ) k ( y 1 / y 2 ) l
The products g ( r ) h ( − r ) g(r)h(-r) g ( r ) h ( − r ) h ( r ) g ( − r ) h(r)g(-r) h ( r ) g ( − r )
D = ( r 4 , r 8 ) ∞ 2 ( r 2 , r 6 , r 10 , r 14 ; r 16 ) ∞ , D=(r^4,r^8)_\infty^2(r^2,r^6,r^{10},r^{14};r^{16})_\infty, D = ( r 4 , r 8 ) ∞ 2 ( r 2 , r 6 , r 10 , r 14 ; r 16 ) ∞ , and their sum and difference have numerators θ ( − r ; r 8 ) θ ( r 3 ; r 8 ) ± θ ( r ; r 8 ) θ ( − r 3 ; r 8 ) \theta(-r;r^8)\theta(r^3;r^8)\pm\theta(r;r^8)\theta(-r^3;r^8) θ ( − r ; r 8 ) θ ( r 3 ; r 8 ) ± θ ( r ; r 8 ) θ ( − r 3 ; r 8 ) y 1 = r y_1=r y 1 = r y 2 = r 3 y_2=r^3 y 2 = r 3 p = r 8 p=r^8 p = r 8 ( r 16 ; r 16 ) ∞ 2 / ( r 8 ; r 8 ) ∞ 2 = ( r 8 ; r 16 ) ∞ − 2 (r^{16};r^{16})_\infty^2/(r^8;r^8)_\infty^2=(r^8;r^{16})_\infty^{-2} ( r 16 ; r 16 ) ∞ 2 / ( r 8 ; r 8 ) ∞ 2 = ( r 8 ; r 16 ) ∞ − 2
2 ( r 4 , r 6 , r 10 , r 12 ; r 16 ) ∞ ( r 8 ; r 16 ) ∞ 2 , 2 r ( r 2 , r 4 , r 12 , r 14 ; r 16 ) ∞ ( r 8 ; r 16 ) ∞ 2 . \frac{2(r^4,r^6,r^{10},r^{12};r^{16})_\infty}{(r^8;r^{16})_\infty^2},
\qquad
\frac{2r(r^2,r^4,r^{12},r^{14};r^{16})_\infty}{(r^8;r^{16})_\infty^2}. ( r 8 ; r 16 ) ∞ 2 2 ( r 4 , r 6 , r 10 , r 12 ; r 16 ) ∞ , ( r 8 ; r 16 ) ∞ 2 2 r ( r 2 , r 4 , r 12 , r 14 ; r 16 ) ∞ . Substituting into (23) and cancelling factors gives
F 01 ( 1 ; r 2 ) = 1 ( r 2 , r 4 , r 8 , r 8 , r 12 , r 14 ; r 16 ) ∞ , F_{01}(1;r^2)=\frac{1}{(r^2,r^4,r^8,r^8,r^{12},r^{14};r^{16})_\infty}, F 01 ( 1 ; r 2 ) = ( r 2 , r 4 , r 8 , r 8 , r 12 , r 14 ; r 16 ) ∞ 1 , F 02 ( 1 ; r 2 ) = 1 ( r 4 , r 6 , r 8 , r 8 , r 10 , r 12 ; r 16 ) ∞ , F_{02}(1;r^2)=\frac{1}{(r^4,r^6,r^8,r^8,r^{10},r^{12};r^{16})_\infty}, F 02 ( 1 ; r 2 ) = ( r 4 , r 6 , r 8 , r 8 , r 10 , r 12 ; r 16 ) ∞ 1 , giving the second and first rows of Theorem B. In both products residue 4 has two colours; the other four listed residues have one colour each. The bilateral series converge r r r
Certificates for the automata
Let S S S Figure 1 . For the boundary ( 2 , 0 , 0 ) (2,0,0) ( 2 , 0 , 0 ) s = 38 s=38 s = 38 G a , G b G_a,G_b G a , G b (12) and (10) have sizes 78 and 40. The proof above establishes ε ( S ) = 0 \varepsilon(S)=0 ε ( S ) = 0 Corollary 3.6 supplies convergent holonomic certificates for the original automata, with ν ( a i , j ) ≥ i + j \nu(a_{i,j})\ge i+j ν ( a i , j ) ≥ i + j ν ( b n ) ≥ n + 1 \nu(b_n)\ge n+1 ν ( b n ) ≥ n + 1 § 4.8 ) lists both automata and computes the sparse operator entries of these kernels.
The Rogers–Ramanujan identities
This classical case shows that the whole proof, product side included, reduces to finite rational identities of the kind found by the searches of § 3.8 . Write ( q ) n = ( q ; q ) n (q)_n=(q;q)_n ( q ) n = ( q ; q ) n i = 1 , 2 i=1,2 i = 1 , 2
L i = R i R ∗ U ( R 2 R ∗ U ) ∗ \mathcal{L}_i=R^iR^*U(R^2R^*U)^* L i = R i R ∗ U ( R 2 R ∗ U ) ∗ encodes nonempty partitions with successive parts differing by at least two and smallest part at least i i i R R R i , i + 2 , … , i + 2 ( n − 1 ) i,i+2,\ldots,i+2(n-1) i , i + 2 , … , i + 2 ( n − 1 )
1 + ε ( H L i ) = ∑ n ≥ 0 q n 2 + ( i − 1 ) n ( q ) n . 1+\varepsilon(H_{\mathcal{L}_i})=\sum_{n\ge0}\frac{q^{n^2+(i-1)n}}{(q)_n}. 1 + ε ( H L i ) = n ≥ 0 ∑ ( q ) n q n 2 + ( i − 1 ) n . Let P 1 , P 2 \mathcal{P}_1,\mathcal{P}_2 P 1 , P 2 Σ 1 = { 1 , 4 } \Sigma_1=\{1,4\} Σ 1 = { 1 , 4 } Σ 2 = { 2 , 3 } \Sigma_2=\{2,3\} Σ 2 = { 2 , 3 } U U U Figure 2 . Both pairs of automata are instances of §3.2. The Rogers–Ramanujan identities [19 ] assert
1 + ε ( H L 1 ) = 1 ( q , q 4 ; q 5 ) ∞ , 1 + ε ( H L 2 ) = 1 ( q 2 , q 3 ; q 5 ) ∞ . (31) 1+\varepsilon(H_{\mathcal{L}_1})=\frac{1}{(q,q^4;q^5)_\infty},\qquad1+\varepsilon(H_{\mathcal{L}_2})=\frac{1}{(q^2,q^3;q^5)_\infty}. \tag*{(31)} 1 + ε ( H L 1 ) = ( q , q 4 ; q 5 ) ∞ 1 , 1 + ε ( H L 2 ) = ( q 2 , q 3 ; q 5 ) ∞ 1 . (31) We derive (31) from finite identities, by two Bailey steps and Jacobi’s triple product.
For a parameter γ \gamma γ ( α , β ) (\alpha,\beta) ( α , β )
β m = ∑ r = 0 m α r ( q ) m − r ( γ q ; q ) m + r . (32) \beta_m=\sum_{r=0}^{m}\frac{\alpha_r}{(q)_{m-r}(\gamma q;q)_{m+r}}. \tag*{(32)} β m = r = 0 ∑ m ( q ) m − r ( γ q ; q ) m + r α r . (32) The unit pairs needed here have β m = δ m , 0 \beta_m=\delta_{m,0} β m = δ m , 0
γ = 1 : α 0 = 1 , α r = ( − 1 ) r q r ( r − 1 ) / 2 ( 1 + q r ) ( r > 0 ) , (33) \gamma=1:\quad\alpha_0=1,\qquad\alpha_r=(-1)^r q^{r(r-1)/2}(1+q^r)\quad(r>0), \tag*{(33)} γ = 1 : α 0 = 1 , α r = ( − 1 ) r q r ( r − 1 ) /2 ( 1 + q r ) ( r > 0 ) , (33) γ = q : α r = ( − 1 ) r q r ( r − 1 ) / 2 ( 1 − q 2 r + 1 ) 1 − q ( r ≥ 0 ) . (34) \gamma=q:\quad\alpha_r=\frac{(-1)^r q^{r(r-1)/2}(1-q^{2r+1})}{1-q}\quad(r\ge0). \tag*{(34)} γ = q : α r = 1 − q ( − 1 ) r q r ( r − 1 ) /2 ( 1 − q 2 r + 1 ) ( r ≥ 0 ) . (34) Both are finite identities. For (33), pairing the indices r , − r r,-r r , − r
∑ r = − m m ( − 1 ) r q r ( r − 1 ) / 2 ( q ) m − r ( q ) m + r = ( − 1 ) m q m ( m + 1 ) / 2 ( q ) 2 m ( q − m ; q ) 2 m . \sum_{r=-m}^{m}\frac{(-1)^r q^{r(r-1)/2}}{(q)_{m-r}(q)_{m+r}}=\frac{(-1)^m q^{m(m+1)/2}}{(q)_{2m}}(q^{-m};q)_{2m}. r = − m ∑ m ( q ) m − r ( q ) m + r ( − 1 ) r q r ( r − 1 ) /2 = ( q ) 2 m ( − 1 ) m q m ( m + 1 ) /2 ( q − m ; q ) 2 m . For (34), pair r , − r − 1 r,-r-1 r , − r − 1
∑ r = − m − 1 m ( − 1 ) r q r ( r − 1 ) / 2 ( q ) m − r ( q ) m + r + 1 = ( − 1 ) m + 1 q ( m + 1 ) ( m + 2 ) / 2 ( q ) 2 m + 1 ( q − m − 1 ; q ) 2 m + 1 . \sum_{r=-m-1}^{m}\frac{(-1)^r q^{r(r-1)/2}}{(q)_{m-r}(q)_{m+r+1}}=\frac{(-1)^{m+1}q^{(m+1)(m+2)/2}}{(q)_{2m+1}}(q^{-m-1};q)_{2m+1}. r = − m − 1 ∑ m ( q ) m − r ( q ) m + r + 1 ( − 1 ) r q r ( r − 1 ) /2 = ( q ) 2 m + 1 ( − 1 ) m + 1 q ( m + 1 ) ( m + 2 ) /2 ( q − m − 1 ; q ) 2 m + 1 . The right-hand sides vanish for m > 0 m > 0 m > 0 m = 0 m = 0 m = 0 q q q
( y ; q ) N = ∑ j = 0 N ( − 1 ) j q j ( j − 1 ) / 2 [ N j ] q y j , [ N j ] q = ( q ) N ( q ) j ( q ) N − j . (y;q)_N=\sum_{j=0}^{N}(-1)^j q^{j(j-1)/2}\begin{bmatrix}N\\j\end{bmatrix}_q y^j,\qquad\begin{bmatrix}N\\j\end{bmatrix}_q=\frac{(q)_N}{(q)_j(q)_{N-j}}. ( y ; q ) N = j = 0 ∑ N ( − 1 ) j q j ( j − 1 ) /2 [ N j ] q y j , [ N j ] q = ( q ) j ( q ) N − j ( q ) N . which follows coefficientwise from ( y ; q ) N + 1 = ( 1 − y q N ) ( y ; q ) N (y;q)_{N+1}=(1-yq^N)(y;q)_N ( y ; q ) N + 1 = ( 1 − y q N ) ( y ; q ) N
The Bailey step has a rational telescoping certificate. Put
h ( m , k ) = κ k q k 2 ( q ) m − k ( q ) k ( κ q ; q ) k , ζ = q m , ξ = q k , h(m,k)=\frac{\kappa^kq^{k^2}}{(q)_{m-k}(q)_k(\kappa q;q)_k},\qquad\zeta=q^m,\qquad\xi=q^k, h ( m , k ) = ( q ) m − k ( q ) k ( κ q ; q ) k κ k q k 2 , ζ = q m , ξ = q k , and
r ( ζ , ξ ) = κ q ξ 2 ( 1 − ζ / ξ ) ( 1 − q ξ ) ( 1 − κ q ξ ) , Ψ ( ζ , ξ ) = − ζ ( 1 − ξ ) ( 1 − κ ξ ) ξ , r(\zeta,\xi)=\frac{\kappa q\xi^2(1-\zeta/\xi)}{(1-q\xi)(1-\kappa q\xi)},\qquad\Psi(\zeta,\xi)=-\frac{\zeta(1-\xi)(1-\kappa\xi)}{\xi}, r ( ζ , ξ ) = ( 1 − q ξ ) ( 1 − κ q ξ ) κ q ξ 2 ( 1 − ζ / ξ ) , Ψ ( ζ , ξ ) = − ξ ζ ( 1 − ξ ) ( 1 − κ ξ ) , so that r ( ζ , ξ ) = h ( m , k + 1 ) / h ( m , k ) r(\zeta,\xi)=h(m,k+1)/h(m,k) r ( ζ , ξ ) = h ( m , k + 1 ) / h ( m , k )
r ( ζ , ξ ) Ψ ( ζ , q ξ ) − Ψ ( ζ , ξ ) = ( 1 − ζ ) ( 1 − κ ζ ) − ( 1 − ζ / ξ ) (35) r(\zeta,\xi)\Psi(\zeta,q\xi)-\Psi(\zeta,\xi)=(1-\zeta)(1-\kappa\zeta)-(1-\zeta/\xi) \tag*{(35)} r ( ζ , ξ ) Ψ ( ζ , q ξ ) − Ψ ( ζ , ξ ) = ( 1 − ζ ) ( 1 − κ ζ ) − ( 1 − ζ / ξ ) (35) is checked by clearing denominators. Extend h ( m , k ) h(m,k) h ( m , k ) 0 ≤ k ≤ m 0\leq k\leq m 0 ≤ k ≤ m h ( m , k ) h(m,k) h ( m , k ) k k k ( 1 − q m ) ( 1 − κ q m ) F m = F m − 1 (1-q^m)(1-\kappa q^m)F_m=F_{m-1} ( 1 − q m ) ( 1 − κ q m ) F m = F m − 1 F m = ∑ k h ( m , k ) F_m=\sum_k h(m,k) F m = ∑ k h ( m , k ) ( 1 − q m − k ) h ( m , k ) = h ( m − 1 , k ) (1-q^{m-k})h(m,k)=h(m-1,k) ( 1 − q m − k ) h ( m , k ) = h ( m − 1 , k ) ξ = 1 \xi=1 ξ = 1 h ( m , m + 1 ) = 0 h(m,m+1)=0 h ( m , m + 1 ) = 0 F 0 = 1 F_0=1 F 0 = 1
∑ k = 0 m h ( m , k ) = 1 ( q ) m ( κ q ; q ) m . (36) \sum_{k=0}^{m}h(m,k)=\frac{1}{(q)_m(\kappa q;q)_m}. \tag*{(36)} k = 0 ∑ m h ( m , k ) = ( q ) m ( κ q ; q ) m 1 . (36) The certificate Ψ \Psi Ψ ξ \xi ξ ξ \xi ξ Q ( q , κ , ζ ) \mathbb{Q}(q,\kappa,\zeta) Q ( q , κ , ζ ) (35) : clearing ξ ( 1 − q ξ ) ( 1 − κ q ξ ) \xi(1-q\xi)(1-\kappa q\xi) ξ ( 1 − q ξ ) ( 1 − κ q ξ ) 5 × 4 5\times4 5 × 4 (32) into
α r ′ = γ r q r 2 α r , β m ′ = ∑ j = 0 m γ j q j 2 β j ( q ) m − j , \alpha'_r=\gamma^r q^{r^2}\alpha_r,\qquad\beta'_m=\sum_{j=0}^{m}\frac{\gamma^j q^{j^2}\beta_j}{(q)_{m-j}}, α r ′ = γ r q r 2 α r , β m ′ = j = 0 ∑ m ( q ) m − j γ j q j 2 β j , and applying (36) with m ↦ m − r m\mapsto m-r m ↦ m − r k = j − r k=j-r k = j − r κ = γ q 2 r \kappa=\gamma q^{2r} κ = γ q 2 r ( α ′ , β ′ ) (\alpha',\beta') ( α ′ , β ′ )
Apply this finite transformation twice to either unit pair, and multiply the relation at index M M M ( q ) M (q)_M ( q ) M
∑ n = 0 M γ n q n 2 ( q ) n ( q ) M ( q ) M − n = ∑ r = 0 M γ 2 r q 2 r 2 α r ( q ) M ( q ) M − r ( γ q ; q ) M + r . (37) \sum_{n=0}^{M}\frac{\gamma^n q^{n^2}}{(q)_n}\frac{(q)_M}{(q)_{M-n}}=\sum_{r=0}^{M}\gamma^{2r}q^{2r^2}\alpha_r\frac{(q)_M}{(q)_{M-r}(\gamma q;q)_{M+r}}. \tag*{(37)} n = 0 ∑ M ( q ) n γ n q n 2 ( q ) M − n ( q ) M = r = 0 ∑ M γ 2 r q 2 r 2 α r ( q ) M − r ( γ q ; q ) M + r ( q ) M . (37) Put γ = q δ \gamma=q^\delta γ = q δ δ ∈ { 0 , 1 } \delta\in\{0,1\} δ ∈ { 0 , 1 } M → ∞ M\to\infty M → ∞ M + 1 + δ M+1+\delta M + 1 + δ M − n + 1 M-n+1 M − n + 1
n 2 + δ n + M − n + 1 ≥ M + 1 + δ ( n ≥ 1 ) . n^2+\delta n+M-n+1\geq M+1+\delta\qquad(n\geq1). n 2 + δ n + M − n + 1 ≥ M + 1 + δ ( n ≥ 1 ) . On the right the numerator has valuation w δ ( r ) = ( 5 r 2 + ( 4 δ − 1 ) r ) / 2 w_\delta(r)=(5r^2+(4\delta-1)r)/2 w δ ( r ) = ( 5 r 2 + ( 4 δ − 1 ) r ) /2 r > 0 r>0 r > 0 w δ ( r ) + M − r + 1 ≥ M + 1 + δ w_\delta(r)+M-r+1\geq M+1+\delta w δ ( r ) + M − r + 1 ≥ M + 1 + δ r = 0 r=0 r = 0 M + 1 + δ M+1+\delta M + 1 + δ (37) gives
∑ n ≥ 0 q n 2 ( q ) n = 1 ( q ) ∞ ∑ r ∈ Z ( − 1 ) r q ( 5 r 2 − r ) / 2 , \sum_{n\geq0}\frac{q^{n^2}}{(q)_n}=\frac{1}{(q)_\infty}\sum_{r\in\mathbb{Z}}(-1)^r q^{(5r^2-r)/2}, n ≥ 0 ∑ ( q ) n q n 2 = ( q ) ∞ 1 r ∈ Z ∑ ( − 1 ) r q ( 5 r 2 − r ) /2 , ∑ n ≥ 0 q n 2 + n ( q ) n = 1 ( q ) ∞ ∑ r ∈ Z ( − 1 ) r q ( 5 r 2 + 3 r ) / 2 . \sum_{n\geq0}\frac{q^{n^2+n}}{(q)_n}=\frac{1}{(q)_\infty}\sum_{r\in\mathbb{Z}}(-1)^r q^{(5r^2+3r)/2}. n ≥ 0 ∑ ( q ) n q n 2 + n = ( q ) ∞ 1 r ∈ Z ∑ ( − 1 ) r q ( 5 r 2 + 3 r ) /2 . The second equality pairs r ≥ 0 r\geq0 r ≥ 0 − r − 1 -r-1 − r − 1 1 − q 1-q 1 − q ( q 2 ; q ) ∞ (q^2;q)_\infty ( q 2 ; q ) ∞
Jacobi’s triple product follows from a finite identity:
( y ; p ) N ( p / y ; p ) N = ∑ k = − N N ( − 1 ) k p k ( k − 1 ) / 2 y k ( 2 N N + k ) p . (y;p)_N(p/y;p)_N=\sum_{k=-N}^{N}(-1)^k p^{k(k-1)/2}y^k\binom{2N}{N+k}_p. ( y ; p ) N ( p / y ; p ) N = k = − N ∑ N ( − 1 ) k p k ( k − 1 ) /2 y k ( N + k 2 N ) p . This is the preceding finite q q q ( p , y ) = ( q 5 , q 2 ) (p,y)=(q^5,q^2) ( p , y ) = ( q 5 , q 2 ) ( q 5 , q 4 ) (q^5,q^4) ( q 5 , q 4 ) 5 N + 2 5N+2 5 N + 2 5 N + 1 5N+1 5 N + 1 1 / ( q 5 ; q 5 ) ∞ 1/(q^5;q^5)_\infty 1/ ( q 5 ; q 5 ) ∞ 5 ( N − ∣ k ∣ + 1 ) 5(N-|k|+1) 5 ( N − ∣ k ∣ + 1 ) ( q 2 , q 3 , q 5 ; q 5 ) ∞ (q^2,q^3,q^5;q^5)_\infty ( q 2 , q 3 , q 5 ; q 5 ) ∞ ( q , q 4 , q 5 ; q 5 ) ∞ (q,q^4,q^5;q^5)_\infty ( q , q 4 , q 5 ; q 5 ) ∞ ( q ) ∞ (q)_\infty ( q ) ∞
To bind this calculation to the quantum-plane certificates, put S i = H L i − H P i S_i=H_{L_i}-H_{P_i} S i = H L i − H P i E E E 5 × 5 5\times5 5 × 5 E j , j − 1 = 1 E_{j,j-1}=1 E j , j − 1 = 1 I Σ I_\Sigma I Σ 1 j ∈ Σ 1_{j\in\Sigma} 1 j ∈ Σ χ Σ \chi_\Sigma χ Σ
L g a p = ( 1 − q R 0 − q R − q Υ 1 0 0 − q R 1 ) , L Σ = I 5 − q R E − q Υ I Σ . L_{\mathrm{gap}}=\begin{pmatrix}1-qR&0&-qR\\-q\Upsilon&1&0\\0&-qR&1\end{pmatrix},\qquad L_\Sigma=I_5-qRE-q\Upsilon I_\Sigma. L gap = 1 − q R − q Υ 0 0 1 − q R − q R 0 1 , L Σ = I 5 − q R E − q Υ I Σ . The data for S i S_i S i
L i = diag ( L g a p , L Σ i ) , f i = ( e 2 i − 1 e 1 ) , d i = q R ( e 1 T − χ Σ i T ) . L_i=\operatorname{diag}(L_{\mathrm{gap}},L_{\Sigma_i}),\qquad f_i=\begin{pmatrix}e_{2i-1}\\e_1\end{pmatrix},\qquad d_i=qR\begin{pmatrix}e_1^{\mathsf T}&-\chi_{\Sigma_i}^{\mathsf T}\end{pmatrix}. L i = diag ( L gap , L Σ i ) , f i = ( e 2 i − 1 e 1 ) , d i = q R ( e 1 T − χ Σ i T ) . where the first basis vector in f i f_i f i Q 3 \mathbb{Q}^3 Q 3 Q 5 \mathbb{Q}^5 Q 5 L i , x = L i ∣ Υ ↦ x Υ L_{i,x}=L_i|_{\Upsilon\mapsto x\Upsilon} L i , x = L i ∣ Υ ↦ x Υ f i , x = x f i f_{i,x}=xf_i f i , x = x f i d i , x = d i d_{i,x}=d_i d i , x = d i G b G_b G b G a G_a G a a , b a,b a , b ε ( S i ) = 0 \varepsilon(S_i)=0 ε ( S i ) = 0 ν ( a i , j ) ≥ i + j \nu(a_{i,j})\ge i+j ν ( a i , j ) ≥ i + j ν ( b n ) ≥ n + 1 \nu(b_n)\ge n+1 ν ( b n ) ≥ n + 1
A global constraint: alternating sums
For a partition λ = ( λ 1 ≥ ⋯ ≥ λ ℓ > 0 ) \lambda=(\lambda_1\ge\cdots\ge\lambda_\ell>0) λ = ( λ 1 ≥ ⋯ ≥ λ ℓ > 0 )
α ( λ ) = λ 1 − λ 2 + λ 3 − ⋯ + ( − 1 ) ℓ − 1 λ ℓ . \alpha(\lambda)=\lambda_1-\lambda_2+\lambda_3-\cdots+(-1)^{\ell-1}\lambda_\ell. α ( λ ) = λ 1 − λ 2 + λ 3 − ⋯ + ( − 1 ) ℓ − 1 λ ℓ . Bessenrodt’s refinement of Euler’s identity, obtained from Sylvester’s bijection [5 , 7 ] , states that for every n , k ≥ 0 n,k\ge0 n , k ≥ 0 n n n α ( λ ) = k \alpha(\lambda)=k α ( λ ) = k n n n k k k
∑ λ d i s t i n c t z α ( λ ) q ∣ λ ∣ = ∑ μ o d d z ℓ ( μ ) q ∣ μ ∣ = 1 ( z q ; q 2 ) ∞ . (38) \sum_{\lambda\ \mathrm{distinct}}z^{\alpha(\lambda)}q^{|\lambda|}
=\sum_{\mu\ \mathrm{odd}}z^{\ell(\mu)}q^{|\mu|}
=\frac{1}{(zq;q^2)_\infty}. \tag*{(38)} λ distinct ∑ z α ( λ ) q ∣ λ ∣ = μ odd ∑ z ℓ ( μ ) q ∣ μ ∣ = ( z q ; q 2 ) ∞ 1 . (38) The refinement is still recognized by a finite weighted automaton. In the boundary word of a distinct partition, give a letter R R R z z z U U U z α ( λ ) z^{\alpha(\lambda)} z α ( λ )
B 0 = R ( 1 − R ) − 1 U , B 1 = z R ( 1 − z R ) − 1 U , B_0=R(1-R)^{-1}U,\qquad B_1=zR(1-zR)^{-1}U, B 0 = R ( 1 − R ) − 1 U , B 1 = z R ( 1 − z R ) − 1 U , the two weighted regular series, including the empty partition, are
H d e = ( 1 + B 1 ) ( 1 − B 0 B 1 ) − 1 , H d o = 1 + R ( 1 − z U − R 2 ) − 1 z U . (39) H_d^{\mathrm{e}}=(1+B_1)(1-B_0B_1)^{-1},\qquad H_d^{\mathrm{o}}=1+R(1-zU-R^2)^{-1}zU. \tag*{(39)} H d e = ( 1 + B 1 ) ( 1 − B 0 B 1 ) − 1 , H d o = 1 + R ( 1 − z U − R 2 ) − 1 z U . (39) Indeed, even-length distinct partitions have block pattern ( B 0 B 1 ) ∗ (B_0B_1)^* ( B 0 B 1 ) ∗ B 1 ( B 0 B 1 ) ∗ B_1(B_0B_1)^* B 1 ( B 0 B 1 ) ∗ U U U z z z [ z k ] [z^k] [ z k ] k k k
We prove (38) by telescoping. For a distinct partition of length m m m δ i = λ i − λ i + 1 ≥ 1 \delta_i=\lambda_i-\lambda_{i+1}\ge1 δ i = λ i − λ i + 1 ≥ 1 λ m + 1 = 0 \lambda_{m+1}=0 λ m + 1 = 0
∣ λ ∣ = ∑ i = 1 m i δ i , α ( λ ) = ∑ 1 ≤ i ≤ m i o d d δ i . |\lambda|=\sum_{i=1}^{m}i\delta_i,\qquad\alpha(\lambda)=\sum_{\substack{1\le i\le m\\i\ \mathrm{odd}}}\delta_i. ∣ λ ∣ = i = 1 ∑ m i δ i , α ( λ ) = 1 ≤ i ≤ m i odd ∑ δ i . Pairing lengths 2 j − 1 2j-1 2 j − 1 2 j 2j 2 j
z j q 2 j 2 − j ( z q ; q 2 ) j ( q 2 ; q 2 ) j − 1 + z j q 2 j 2 + j ( z q ; q 2 ) j ( q 2 ; q 2 ) j = z j q 2 j 2 − j ( z q ; q 2 ) j ( q 2 ; q 2 ) j . \frac{z^{j}q^{2j^{2}-j}}{(zq;q^{2})_{j}(q^{2};q^{2})_{j-1}}+\frac{z^{j}q^{2j^{2}+j}}{(zq;q^{2})_{j}(q^{2};q^{2})_{j}}=\frac{z^{j}q^{2j^{2}-j}}{(zq;q^{2})_{j}(q^{2};q^{2})_{j}}. ( z q ; q 2 ) j ( q 2 ; q 2 ) j − 1 z j q 2 j 2 − j + ( z q ; q 2 ) j ( q 2 ; q 2 ) j z j q 2 j 2 + j = ( z q ; q 2 ) j ( q 2 ; q 2 ) j z j q 2 j 2 − j . Including the empty partition and putting η = z q \eta=zq η = z q Q = q 2 Q=q^{2} Q = q 2 (38) is
V ( η ) = ∑ j ≥ 0 f j ( η ) , f j ( η ) = η j Q j ( j − 1 ) ( Q ; Q ) j ( η ; Q ) j . V(\eta)=\sum_{j\ge0}f_j(\eta),\qquad f_j(\eta)=\frac{\eta^{j}Q^{j(j-1)}}{(Q;Q)_j(\eta;Q)_j}. V ( η ) = j ≥ 0 ∑ f j ( η ) , f j ( η ) = ( Q ; Q ) j ( η ; Q ) j η j Q j ( j − 1 ) . For ξ = Q j \xi=Q^j ξ = Q j
r ( ξ ) = f j + 1 ( η ) f j ( η ) = η ξ 2 ( 1 − Q ξ ) ( 1 − η ξ ) , s ( ξ ) = f j ( Q η ) f j ( η ) = ξ ( 1 − η ) 1 − η ξ . r(\xi)=\frac{f_{j+1}(\eta)}{f_j(\eta)}=\frac{\eta\xi^{2}}{(1-Q\xi)(1-\eta\xi)},\qquad s(\xi)=\frac{f_j(Q\eta)}{f_j(\eta)}=\frac{\xi(1-\eta)}{1-\eta\xi}. r ( ξ ) = f j ( η ) f j + 1 ( η ) = ( 1 − Q ξ ) ( 1 − η ξ ) η ξ 2 , s ( ξ ) = f j ( η ) f j ( Q η ) = 1 − η ξ ξ ( 1 − η ) . The telescoping certificate Ψ ( ξ ) = ( 1 − η ) ( ξ − 1 ) \Psi(\xi)=(1-\eta)(\xi-1) Ψ ( ξ ) = ( 1 − η ) ( ξ − 1 )
r ( ξ ) Ψ ( Q ξ ) − Ψ ( ξ ) = ( 1 − η ) − s ( ξ ) (40) r(\xi)\Psi(Q\xi)-\Psi(\xi)=(1-\eta)-s(\xi) \tag*{(40)} r ( ξ ) Ψ ( Q ξ ) − Ψ ( ξ ) = ( 1 − η ) − s ( ξ ) (40) Its lower boundary is Ψ ( 1 ) = 0 \Psi(1)=0 Ψ ( 1 ) = 0 j = N + 1 j=N+1 j = N + 1 η \eta η N + 1 N+1 N + 1 η = z q \eta=zq η = z q Q = q 2 Q=q^{2} Q = q 2 q q q 2 ( N + 1 ) 2 − ( N + 1 ) 2(N+1)^{2}-(N+1) 2 ( N + 1 ) 2 − ( N + 1 ) (40) therefore gives
V ( Q η ) = ( 1 − η ) V ( η ) , V ( 0 ) = 1. V(Q\eta)=(1-\eta)V(\eta),\qquad V(0)=1. V ( Q η ) = ( 1 − η ) V ( η ) , V ( 0 ) = 1. These equations determine V V V Q ( Q ) [ [ η ] ] \mathbb{Q}(Q)[[\eta]] Q ( Q ) [[ η ]] η j \eta^j η j 1 / ( Q ; Q ) j 1/(Q;Q)_j 1/ ( Q ; Q ) j ( η ; Q ) ∞ − 1 (\eta;Q)_{\infty}^{-1} ( η ; Q ) ∞ − 1 Q Q Q (38) . The proof is uniform in the statistic variable z z z
For the quantum-plane certificate, put S = H d z − H o z S=H^{z}_{d}-H^{z}_{o} S = H d z − H o z D ( x , R ) D(x,R) D ( x , R )
L d = ( 1 0 0 − q Υ 0 1 − q Υ 0 − q R 0 1 − q R 0 0 − z q R 0 1 − z q R ) , L = diag ( L d , 1 − z q Υ − q 2 R 2 ) , L_d=\begin{pmatrix}
1&0&0&-q\Upsilon\\
0&1&-q\Upsilon&0\\
-qR&0&1-qR&0\\
0&-zqR&0&1-zqR
\end{pmatrix},\qquad L=\operatorname{diag}(L_d,1-zq\Upsilon-q^{2}R^{2}), L d = 1 0 − q R 0 0 1 0 − z q R 0 − q Υ 1 − q R 0 − q Υ 0 0 1 − z q R , L = diag ( L d , 1 − z q Υ − q 2 R 2 ) , f = ( 0 , 0 , q , z q , q ) T , d = ( 0 , 0 , 0 , R , − z R ) . f=(0,0,q,zq,q)^{\mathsf T},\qquad d=(0,0,0,R,-zR). f = ( 0 , 0 , q , z q , q ) T , d = ( 0 , 0 , 0 , R , − z R ) . The first four states are: after a U U U B 1 B_1 B 1 U U U B 0 B_0 B 0 B 0 B_0 B 0 B 1 B_1 B 1 L m = f Lm=f L m = f C = d m C=dm C = d m S S S R = 0 R=0 R = 0
m ( 0 ) = ( z q 2 , q 2 , q , z q , q / ( 1 − z q ) ) T , m(0)=(zq^{2},q^{2},q,zq,q/(1-zq))^{\mathsf T}, m ( 0 ) = ( z q 2 , q 2 , q , z q , q / ( 1 − z q ) ) T , and all subsequent coefficients are fixed by L L L R R R Q ( q , z ) \mathbb{Q}(q,z) Q ( q , z ) Υ \Upsilon Υ x Υ x\Upsilon x Υ L L L f f f x f xf x f d d d G b G_b G b G a G_a G a
The constant terms 1 cancel in S S S R { R , U } ∗ U R\{R,U\}^{*}U R { R , U } ∗ U Q [ z ] \mathbb{Q}[z] Q [ z ] Lemma 3.5 and Corollary 3.6 apply unchanged: by (38) , ν ( a i , j ) ≥ i + j \nu(a_{i,j})\ge i+j ν ( a i , j ) ≥ i + j ν ( b n ) ≥ n + 1 \nu(b_n)\ge n+1 ν ( b n ) ≥ n + 1 (38) .
Residues of parts at prescribed indices
For a partition λ 1 > ⋯ > λ ℓ > 0 \lambda_1 > \cdots> \lambda_\ell> 0 λ 1 > ⋯ > λ ℓ > 0 o ( λ ) o(\lambda) o ( λ ) e ( λ ) e(\lambda) e ( λ ) [4 Theorem 1.1] . Thus
∑ λ d i s t i n c t u o ( λ ) v e ( λ ) q ∣ λ ∣ = ( − q 2 ; q 2 ) ∞ ( − u q ; q 4 ) ∞ ( − v q 3 ; q 4 ) ∞ . (41) \sum_{\lambda\ \mathrm{distinct}} u^{o(\lambda)}v^{e(\lambda)}q^{\lvert\lambda\rvert}=(-q^2;q^2)_\infty(-uq;q^4)_\infty(-vq^3;q^4)_\infty. \tag*{(41)} λ distinct ∑ u o ( λ ) v e ( λ ) q ∣ λ ∣ = ( − q 2 ; q 2 ) ∞ ( − u q ; q 4 ) ∞ ( − v q 3 ; q 4 ) ∞ . (41) Both sides count partitions into distinct parts. The empty partition contributes 1 on each side and cancels in their difference. We give the automaton kernels, and certify convergence by a recurrence for the bounded refinement of [4 Theorem 2.1] .
Automata and holonomic kernels. The boundary word reads parts in increasing order. To recover their indices in decreasing order, the first automaton records the parity of the number of U U U ( h , k , r ) ∈ { 0 , 1 } 3 (h,k,r) \in\{0,1\}^3 ( h , k , r ) ∈ { 0 , 1 } 3 h h h k k k r = 1 r=1 r = 1 R R R U U U
Table 1.
w ( h , k ) = { 1 , h = 0 , u , h = 1 , k = 1 , v , h = 1 , k = 0. w(h,k)=
\begin{cases}
1, & h=0,\\
u, & h=1,\ k=1,\\
v, & h=1,\ k=0.
\end{cases} w ( h , k ) = ⎩ ⎨ ⎧ 1 , u , v , h = 0 , h = 1 , k = 1 , h = 1 , k = 0. The initial R R R ( 1 , 0 , 1 ) (1,0,1) ( 1 , 0 , 1 ) ( 1 , 1 , 1 ) (1,1,1) ( 1 , 1 , 1 ) U U U ( h , 1 , 1 ) (h,1,1) ( h , 1 , 1 ) w ( h , 1 ) w(h,1) w ( h , 1 ) r r r U U U
The second automaton has eight states ( h , r ) ∈ Z / 4 Z × { 0 , 1 } (h,r) \in\mathbb{Z}/4\mathbb{Z} \times\{0,1\} ( h , r ) ∈ Z /4 Z × { 0 , 1 }
Table 2.
w ~ ( h ) = { u , h = 1 , v , h = 3 , 1 , h = 0 , 2. \widetilde{w}(h)=
\begin{cases}
u, & h=1,\\
v, & h=3,\\
1, & h=0,2.
\end{cases} w ( h ) = ⎩ ⎨ ⎧ u , v , 1 , h = 1 , h = 3 , h = 0 , 2. Its initial R R R ( 1 , 1 ) (1,1) ( 1 , 1 ) U U U ( h , 1 ) (h,1) ( h , 1 ) w ~ ( h ) \widetilde{w}(h) w ( h )
Let A R , A U A_R,A_U A R , A U j → i j \to i j → i ( i , j ) (i,j) ( i , j ) r 0 r_0 r 0 d d d
( I − q R A R − q x Υ A U ) m x = x r 0 , D ( x , R ) = q R d m x . (42) (\mathbb{I}-qR A_R-qx\Upsilon A_U)m_x=xr_0,\qquad D(x,R)=qRdm_x. \tag*{(42)} ( I − q R A R − q x Υ A U ) m x = x r 0 , D ( x , R ) = q R d m x . (42) The matrix is congruent to I \mathbb{I} I q q q Z [ u , v , x , R ] [ [ q ] ] \mathbb{Z}[u,v,x,R][[q]] Z [ u , v , x , R ] [[ q ]] a , b a,b a , b ϕ \phi ϕ
( I − R A R − q Υ A U ) m ~ = r 0 , ( q − R ) ϕ = R d m ~ , b = q Υ ϕ . (43) \begin{aligned}
(\mathbb{I}-R A_R-q\Upsilon A_U)\widetilde{m}&=r_0,\\
(q-R)\phi&=Rd\widetilde{m},\qquad b=q\Upsilon\phi. \tag*{(43)}
\end{aligned} ( I − R A R − q Υ A U ) m ( q − R ) ϕ = r 0 , = R d m , b = q Υ ϕ . (43) Here m ~ = m 1 ( R / q ) \widetilde{m}=m_1(R/q) m = m 1 ( R / q ) R R R n n n I − q n + 1 A U \mathbb{I}-q^{n+1}A_U I − q n + 1 A U I + q n + 1 A U \mathbb{I}+q^{n+1}A_U I + q n + 1 A U A U 2 = 0 A_U^2=0 A U 2 = 0 ϕ ( 0 ) = 0 \phi(0)=0 ϕ ( 0 ) = 0 ϕ ∈ Z [ u , v ] [ [ q , R ] ] \phi\in\mathbb{Z}[u,v][[q,R]] ϕ ∈ Z [ u , v ] [[ q , R ]]
A recurrence certificate. Write E N ( i , j ) E_N(i,j) E N ( i , j ) u i v j u^iv^j u i v j 2 N 2N 2 N 2 N , 2 N − 1 2N,2N-1 2 N , 2 N − 1
E N ( i , j ) = E N − 1 ( i , j ) + q 2 N E N − 1 ( i , j ) + q 2 N − 1 E N − 1 ( j , i − 1 ) + q 4 N − 1 E N − 1 ( i , j − 1 ) . (44) \begin{aligned}
E_N(i,j)&=E_{N-1}(i,j)+q^{2N}E_{N-1}(i,j)\\
&\quad+q^{2N-1}E_{N-1}(j,i-1)+q^{4N-1}E_{N-1}(i,j-1). \tag*{(44)}
\end{aligned} E N ( i , j ) = E N − 1 ( i , j ) + q 2 N E N − 1 ( i , j ) + q 2 N − 1 E N − 1 ( j , i − 1 ) + q 4 N − 1 E N − 1 ( i , j − 1 ) . (44) The initial data are E 0 ( i , j ) = δ i , 0 δ j , 0 E_0(i,j)=\delta_{i,0}\delta_{j,0} E 0 ( i , j ) = δ i , 0 δ j , 0
T N ( i , j ) = q 2 i 2 − i + 2 j 2 + j ( q 4 ; q 4 ) N ( q 4 ; q 4 ) i ( q 4 ; q 4 ) j ( q 2 ; q 2 ) N − i − j ( i , j ≥ 0 , i + j ≤ N ) . (45) T_N(i,j)=\frac{q^{2i^2-i+2j^2+j}(q^4;q^4)_N}{(q^4;q^4)_i(q^4;q^4)_j(q^2;q^2)_{N-i-j}}\qquad(i,j\ge0,\ i+j\le N). \tag*{(45)} T N ( i , j ) = ( q 4 ; q 4 ) i ( q 4 ; q 4 ) j ( q 2 ; q 2 ) N − i − j q 2 i 2 − i + 2 j 2 + j ( q 4 ; q 4 ) N ( i , j ≥ 0 , i + j ≤ N ) . (45) and zero elsewhere. To verify it, set X = q 2 N X=q^{2N} X = q 2 N Y = q 2 i Y=q^{2i} Y = q 2 i Z = q 2 j Z=q^{2j} Z = q 2 j (44) by T N ( i , j ) T_N(i,j) T N ( i , j )
Table 3.
Their sum is 1 by the polynomial identity
( Y Z − X ) ( Z + X Y ) + X Z ( 1 − Y 2 ) + X 2 Y ( 1 − Z 2 ) = Y Z 2 ( 1 − X 2 ) . (46) (YZ-X)(Z+XY)+XZ(1-Y^2)+X^2Y(1-Z^2)=YZ^2(1-X^2). \tag*{(46)} ( Y Z − X ) ( Z + X Y ) + X Z ( 1 − Y 2 ) + X 2 Y ( 1 − Z 2 ) = Y Z 2 ( 1 − X 2 ) . (46) On the support boundary i + j = N i+j=N i + j = N Y Z − X YZ-X Y Z − X i = 0 i=0 i = 0 j = 0 j=0 j = 0 1 − Y 2 1-Y^2 1 − Y 2 1 − Z 2 1-Z^2 1 − Z 2 T 0 ( 0 , 0 ) = 1 T_0(0,0)=1 T 0 ( 0 , 0 ) = 1 E N = T N E_N=T_N E N = T N
Convergence data. Put σ i , j = 2 i 2 − i + 2 j 2 + j \sigma_{i,j}=2i^2-i+2j^2+j σ i , j = 2 i 2 − i + 2 j 2 + j
G i , j = q σ i , j ( − q 2 ; q 2 ) ∞ ( q 4 ; q 4 ) i ( q 4 ; q 4 ) j . G_{i,j}=\frac{q^{\sigma_{i,j}}(-q^2;q^2)_\infty}{(q^4;q^4)_i(q^4;q^4)_j}. G i , j = ( q 4 ; q 4 ) i ( q 4 ; q 4 ) j q σ i , j ( − q 2 ; q 2 ) ∞ . These are the coefficients of u i v j u^iv^j u i v j (41) : the expansion of ( − z ; q 4 ) ∞ (-z;q^4)_\infty ( − z ; q 4 ) ∞ g ( z ) = ( 1 + z ) g ( q 4 z ) g(z)=(1+z)g(q^4z) g ( z ) = ( 1 + z ) g ( q 4 z ) g ( 0 ) = 1 g(0)=1 g ( 0 ) = 1 i + j ≤ N i+j\leq N i + j ≤ N
T N ( i , j ) G i , j = ( q 2 ( N − i − j + 1 ) ; q 2 ) ∞ ( q 4 N + 4 ; q 4 ) ∞ ≡ 1 ( m o d q 2 ( N − i − j + 1 ) ) . \frac{T_N(i,j)}{G_{i,j}}=\frac{(q^{2(N-i-j+1)};q^2)_\infty}{(q^{4N+4};q^4)_\infty}\equiv1\pmod{q^{2(N-i-j+1)}}. G i , j T N ( i , j ) = ( q 4 N + 4 ; q 4 ) ∞ ( q 2 ( N − i − j + 1 ) ; q 2 ) ∞ ≡ 1 ( mod q 2 ( N − i − j + 1 ) ) . The valuation check is
σ i , j − 2 ( i + j ) + 1 = ( i − 1 ) ( 2 i − 1 ) + j ( 2 j − 1 ) ≥ 0 ( i , j ∈ Z ≥ 0 ) , (47) \sigma_{i,j}-2(i+j)+1=(i-1)(2i-1)+j(2j-1)\geq0\qquad(i,j\in\mathbb{Z}_{\geq0}), \tag*{(47)} σ i , j − 2 ( i + j ) + 1 = ( i − 1 ) ( 2 i − 1 ) + j ( 2 j − 1 ) ≥ 0 ( i , j ∈ Z ≥ 0 ) , (47) each summand being a product of two integers of the same sign. Consequently ν ( T N ( i , j ) − G i , j ) ≥ σ i , j + 2 ( N − i − j + 1 ) ≥ 2 N + 1 \nu(T_N(i,j)-G_{i,j})\geq\sigma_{i,j}+2(N-i-j+1)\geq2N+1 ν ( T N ( i , j ) − G i , j ) ≥ σ i , j + 2 ( N − i − j + 1 ) ≥ 2 N + 1 i + j > N i+j>N i + j > N ν ( G i , j ) = σ i , j ≥ 2 N + 1 \nu(G_{i,j})=\sigma_{i,j}\geq2N+1 ν ( G i , j ) = σ i , j ≥ 2 N + 1
ν ( ∑ i , j u i v j E N ( i , j ) − ∑ i , j u i v j G i , j ) ≥ 2 N + 1. (48) \nu\left(\sum_{i,j}u^iv^jE_N(i,j)-\sum_{i,j}u^iv^jG_{i,j}\right)\geq2N+1. \tag*{(48)} ν ( i , j ∑ u i v j E N ( i , j ) − i , j ∑ u i v j G i , j ) ≥ 2 N + 1. (48) By the remark after (11) , b n b_n b n n n n 2 N 2N 2 N 2 N + 1 2N+1 2 N + 1 Z [ u , v ] \mathbb{Z}[u,v] Z [ u , v ]
ν ( b n ) ≥ n + 1 , b = q Υ ϕ , ϕ ∈ Z [ u , v ] [ [ q , R ] ] . \nu(b_n)\geq n+1,\qquad b=q^\Upsilon\phi,\quad\phi\in\mathbb{Z}[u,v][[q,R]]. ν ( b n ) ≥ n + 1 , b = q Υ ϕ , ϕ ∈ Z [ u , v ] [[ q , R ]] . The same theorem supplies ν ( a i , j ) ≥ i + j \nu(a_{i,j})\geq i+j ν ( a i , j ) ≥ i + j (47) ; its main check is (46) .
Larger moduli. Fu and Zeng extended (41) as follows. Fix L ≥ 2 L\geq2 L ≥ 2
{ L j + 1 , … , L j + L − 1 } , j ≥ 0. \{Lj+1,\ldots,Lj+L-1\},\qquad j\geq0. { L j + 1 , … , L j + L − 1 } , j ≥ 0. Let o r , e r o_r,e_r o r , e r r r r L L L z = ∑ r = 1 L − 1 u r q r z=\sum_{r=1}^{L-1}u_rq^r z = ∑ r = 1 L − 1 u r q r w = ∑ r = 1 L − 1 v r q r w=\sum_{r=1}^{L-1}v_rq^r w = ∑ r = 1 L − 1 v r q r [9 Theorem 2.6] reads
∑ λ q ∣ λ ∣ ∏ r = 1 L − 1 u r o r ( λ ) v r e r ( λ ) = ( − q L ; q L ) ∞ ( − z ; q 2 L ) ∞ ( − q L w ; q 2 L ) ∞ . (49) \sum_{\lambda}q^{|\lambda|}\prod_{r=1}^{L-1}u_r^{o_r(\lambda)}v_r^{e_r(\lambda)}=(-q^L;q^L)_\infty(-z;q^{2L})_\infty(-q^Lw;q^{2L})_\infty. \tag*{(49)} λ ∑ q ∣ λ ∣ r = 1 ∏ L − 1 u r o r ( λ ) v r e r ( λ ) = ( − q L ; q L ) ∞ ( − z ; q 2 L ) ∞ ( − q L w ; q 2 L ) ∞ . (49) For L = 2 L=2 L = 2 (41) .
The certificate extends to all L L L L N LN L N z , w z,w z , w
F N ( z , w ) = ( 1 + q L ( 2 N − 1 ) w ) F N − 1 ( z , w ) + q L ( N − 1 ) ( q L + z ) F N − 1 ( w , z ) , F 0 = 1. (50) F_N(z,w)=(1+q^{L(2N-1)}w)F_{N-1}(z,w)+q^{L(N-1)}(q^L+z)F_{N-1}(w,z),\qquad F_0=1. \tag*{(50)} F N ( z , w ) = ( 1 + q L ( 2 N − 1 ) w ) F N − 1 ( z , w ) + q L ( N − 1 ) ( q L + z ) F N − 1 ( w , z ) , F 0 = 1. (50) There are four possibilities in the last block: neither part, its multiple of L L L z ↔ w z\leftrightarrow w z ↔ w z i w j z^iw^j z i w j
T N ( L ) ( i , j ) = q L i ( i − 1 ) + L j 2 ( q 2 L ; q 2 L ) N ( q 2 L ; q 2 L ) i ( q 2 L ; q 2 L ) j ( q L ; q L ) N − i − j , (51) T_N^{(L)}(i,j)=\frac{q^{Li(i-1)+Lj^2}(q^{2L};q^{2L})_N}{(q^{2L};q^{2L})_i(q^{2L};q^{2L})_j(q^L;q^L)_{N-i-j}}, \tag*{(51)} T N ( L ) ( i , j ) = ( q 2 L ; q 2 L ) i ( q 2 L ; q 2 L ) j ( q L ; q L ) N − i − j q L i ( i − 1 ) + L j 2 ( q 2 L ; q 2 L ) N , (51) on the same support. With X = q L N X=q^{LN} X = q L N Y = q L i Y=q^{Li} Y = q L i Z = q L j Z=q^{Lj} Z = q L j (46) verifies (50) for every L L L (51) , summed against z i w j z^iw^j z i w j (49) , by the same first-order product equations.
Since ν ( z ) , ν ( w ) ≥ 1 \nu(z),\nu(w)\geq1 ν ( z ) , ν ( w ) ≥ 1 σ i , j ( L ) = L i ( i − 1 ) + L j 2 + i + j \sigma_{i,j}^{(L)}=Li(i-1)+Lj^2+i+j σ i , j ( L ) = L i ( i − 1 ) + L j 2 + i + j
σ i , j ( L ) − L ( i + j ) + L = L ( i − 1 ) 2 + L j ( j − 1 ) + i + j ≥ 1. \sigma_{i,j}^{(L)}-L(i+j)+L=L(i-1)^2+Lj(j-1)+i+j\geq1. σ i , j ( L ) − L ( i + j ) + L = L ( i − 1 ) 2 + L j ( j − 1 ) + i + j ≥ 1. With the tail quotient
( q L ( N − i − j + 1 ) ; q L ) ∞ ( q 2 L ( N + 1 ) ; q 2 L ) ∞ , \frac{(q^{L(N-i-j+1)};q^L)_\infty}{(q^{2L(N+1)};q^{2L})_\infty}, ( q 2 L ( N + 1 ) ; q 2 L ) ∞ ( q L ( N − i − j + 1 ) ; q L ) ∞ , this gives the uniform error ν ( F N − F ∞ ) ≥ L N + 1 \nu(F_N-F_\infty)\geq LN+1 ν ( F N − F ∞ ) ≥ L N + 1
Both sides have finite automata: on the index side, the first automaton, with h h h L L L L L L R R R L L L 1 + z q 2 L j 1+zq^{2Lj} 1 + z q 2 L j 1 + w q 2 L j + L 1+wq^{2Lj+L} 1 + w q 2 L j + L
For example, retain only residues 0 , a 0,a 0 , a 0 , c 0,c 0 , c 1 ≤ a , c < L 1\leq a,c<L 1 ≤ a , c < L
0 , a , L , L + c ( m o d 2 L ) . 0,\ a,\ L,\ L+c\pmod{2L}. 0 , a , L , L + c ( mod 2 L ) . Taking L = 4 L=4 L = 4 a = 1 a=1 a = 1 c = 3 c=3 c = 3 0 , 1 , 4 , 7 ( m o d 8 ) 0,1,4,7\pmod8 0 , 1 , 4 , 7 ( mod 8 )
Arbitrary index periods. The automata do not depend on a product formula. For L , M ≥ 1 L,M\geq1 L , M ≥ 1 h h h L L L k k k M M M z k , h z_{k,h} z k , h 0 0 0 1 1 1
( h , k , r ) ∈ Z / L Z × Z / M Z × { 0 , 1 } (h,k,r)\in\mathbb{Z}/L\mathbb{Z}\times\mathbb{Z}/M\mathbb{Z}\times\{0,1\} ( h , k , r ) ∈ Z / L Z × Z / M Z × { 0 , 1 } have transitions
( h , k , r ) → R ( h + 1 , k , 1 ) , ( h , k , 1 ) → z k , h U ( h , k − 1 , 0 ) . (h,k,r)\xrightarrow{R}(h+1,k,1),\qquad(h,k,1)\xrightarrow{z_{k,h}U}(h,k-1,0). ( h , k , r ) R ( h + 1 , k , 1 ) , ( h , k , 1 ) z k , h U ( h , k − 1 , 0 ) . The initial R R R ( 1 , k , 1 ) (1,k,1) ( 1 , k , 1 ) k k k U U U ( h , 1 , 1 ) (h,1,1) ( h , 1 , 1 ) z 1 , h z_{1,h} z 1 , h (42) applies unchanged, with at most 2 L M 2LM 2 L M
Bounded counts also have a small kernel. Let v N ( k ) v_N^{(k)} v N ( k ) N N N k k k M M M N N N
v N ( k ) = v N − 1 ( k ) + q N z k , N m o d L v N − 1 ( k + 1 ) , v 0 ( k ) = 1. (52) v_N^{(k)}=v_{N-1}^{(k)}+q^N z_{k,N\ \mathrm{mod}\ L}v_{N-1}^{(k+1)},\qquad v_0^{(k)}=1. \tag*{(52)} v N ( k ) = v N − 1 ( k ) + q N z k , N mod L v N − 1 ( k + 1 ) , v 0 ( k ) = 1. (52) In vector form put C h = diag ( z k , h ) C_h=\operatorname{diag}(z_{k,h}) C h = diag ( z k , h ) S S S ( S v ) k = v k + 1 (Sv)_k=v_{k+1} ( S v ) k = v k + 1
B ( Z ) = ( I + q L Z C 0 S ) ( I + q L − 1 Z C L − 1 S ) ⋯ ( I + q Z C 1 S ) = ∑ d = 0 L B d Z d , B(Z)=(\mathbb{I}+q^L ZC_0S)(\mathbb{I}+q^{L-1}ZC_{L-1}S)\cdots(\mathbb{I}+qZC_1S)=\sum_{d=0}^{L}B_dZ^d, B ( Z ) = ( I + q L Z C 0 S ) ( I + q L − 1 Z C L − 1 S ) ⋯ ( I + q Z C 1 S ) = d = 0 ∑ L B d Z d , where for L = 1 L=1 L = 1 I + q Z C 0 S \mathbb{I}+qZC_0S I + q Z C 0 S f ( R ) = ∑ N ≥ 0 v L N R N f(R)=\sum_{N\geq0}v_LNR^N f ( R ) = ∑ N ≥ 0 v L N R N
( I − R ∑ d = 0 L B d R L d ) f = 1 , f ( 0 ) = 1 , (53) \left(\mathbb{I}-R\sum_{d=0}^{L}B_dR^{Ld}\right)f=1,\qquad f(0)=1, \tag*{(53)} ( I − R d = 0 ∑ L B d R L d ) f = 1 , f ( 0 ) = 1 , (53) since v L ( N + 1 ) = B ( q L N ) v L N v_{L(N+1)}=B(q^{LN})v_{LN} v L ( N + 1 ) = B ( q L N ) v L N M M M
A matching product, and the convergence of the difference between two proposed classes, remain separate assertions. For L > 2 L>2 L > 2 ≡ 1 ( m o d 4 ) \equiv1\pmod4 ≡ 1 ( mod 4 ) 1 + v 1+v 1 + v q 3 q^3 q 3 (3) and (2,1), whereas marking the parts ≡ 1 ( m o d 8 ) \equiv1\pmod8 ≡ 1 ( mod 8 ) u u u ≡ 5 ( m o d 8 ) \equiv5\pmod8 ≡ 5 ( mod 8 ) v v v 1 + u 1+u 1 + u
An identity between five-state languages
Consider the two partition languages recognized by the automata of Figure 3 . They were found by enumerating the 14 614 080 minimal deterministic interior automata with at most five states (§ 3.8 ) and grouping them by their series to order q 50 q^{50} q 50 M M M W W W W W W n ≥ W n\geq W n ≥ W k ≡ − 2 ( m o d M ) k\equiv-2\pmod M k ≡ − 2 ( mod M ) R R U ( R U ) n U RRU(RU)^nU R R U ( R U ) n U R R U R R U ( R U ) n + k U R R U RRURRU(RU)^{n+k}URRU R R U R R U ( R U ) n + k U R R U L A \mathcal{L}_A L A R R U ( R U ) n U R R U RRU(RU)^nURRU R R U ( R U ) n U R R U M M M R ( R U ) n R U R(RU)^nRU R ( R U ) n R U R R ( R U ) n + M − 1 U RR(RU)^{n+M-1}U R R ( R U ) n + M − 1 U L B \mathcal{L}_B L B R ( R U ) n U R(RU)^nU R ( R U ) n U
Figure 3. The two automata for the identity. Each has one initial state s s s f f f
Write H A , H B H_A,H_B H A , H B R , U R,U R , U H B † H_B^{\dagger} H B †
S = H A − H B † = ( 1 − U ) a + b ( 1 − R ) . S=H_A-H_B^{\dagger}=(1-U)a+b(1-R). S = H A − H B † = ( 1 − U ) a + b ( 1 − R ) . The normal symbol D ( x , R ) D(x,R) D ( x , R ) S S S q q q Q [ x , R ] [ [ q ] ] \mathbb{Q}[x,R][[q]] Q [ x , R ] [[ q ]]
m 1 = x + q x Υ m 3 , c 1 = q x Υ c 2 , m 2 = q R m 1 , c 2 = x + q R c 1 + q x Υ c 3 , m 3 = q x Υ ( m 2 + m 4 ) , c 3 = q R c 2 + q x Υ c 4 , m 4 = q R m 3 + q x Υ m 5 , c 4 = x + q R c 5 , m 5 = q R m 4 , c 5 = q x Υ c 3 . (54) \begin{aligned}
m_1 &= x+qx\Upsilon m_3, & c_1 &= qx\Upsilon c_2,\\
m_2 &= qRm_1, & c_2 &= x+qRc_1+qx\Upsilon c_3,\\
m_3 &= qx\Upsilon(m_2+m_4), & c_3 &= qRc_2+qx\Upsilon c_4,\\
m_4 &= qRm_3+qx\Upsilon m_5, & c_4 &= x+qRc_5,\\
m_5 &= qRm_4, & c_5 &= qx\Upsilon c_3. \tag*{(54)}
\end{aligned} m 1 m 2 m 3 m 4 m 5 = x + q x Υ m 3 , = q R m 1 , = q x Υ ( m 2 + m 4 ) , = q R m 3 + q x Υ m 5 , = q R m 4 , c 1 c 2 c 3 c 4 c 5 = q x Υ c 2 , = x + q R c 1 + q x Υ c 3 , = q R c 2 + q x Υ c 4 , = x + q R c 5 , = q x Υ c 3 . (54) They are read directly from incoming edges: m m m c c c x x x q q q
D ( x , R ) = q R ( m 2 + m 3 + m 4 + m 5 − c 1 ) , a ( x , R ) = D ( x , R ) − D ( 1 , R ) 1 − x . (55) D(x,R)=qR(m_2+m_3+m_4+m_5-c_1),\qquad a(x,R)=\frac{D(x,R)-D(1,R)}{1-x}. \tag*{(55)} D ( x , R ) = q R ( m 2 + m 3 + m 4 + m 5 − c 1 ) , a ( x , R ) = 1 − x D ( x , R ) − D ( 1 , R ) . (55) Equations (54)–(55) give a holonomic definition of a a a
For b b b Υ R = q R Υ \Upsilon R=qR\Upsilon Υ R = q R Υ
P = 1 − q 2 ( 1 + q ) R Υ − q 3 R Υ R 2 + q 8 R 2 Υ 3 , Q = − 1 − ( 1 + q ) R − R 2 + q ( q 2 − 1 ) R Υ + q 5 R 2 Υ 2 . (56) P=1-q^2(1+q)R\Upsilon-q^3R\Upsilon R^2+q^8R^2\Upsilon^3,
\qquad
Q=-1-(1+q)R-R^2+q(q^2-1)R\Upsilon+q^5R^2\Upsilon^2. \tag*{(56)} P = 1 − q 2 ( 1 + q ) R Υ − q 3 R Υ R 2 + q 8 R 2 Υ 3 , Q = − 1 − ( 1 + q ) R − R 2 + q ( q 2 − 1 ) R Υ + q 5 R 2 Υ 2 . (56) Define
P ψ = q 2 R , ψ ( 0 ) = 0 , ϕ = Q ψ − R , b = q Υ ϕ . (57) P\psi=q^2R,\qquad\psi(0)=0,\qquad\phi=Q\psi-R,\qquad b=q\Upsilon\phi. \tag*{(57)} P ψ = q 2 R , ψ ( 0 ) = 0 , ϕ = Q ψ − R , b = q Υ ϕ . (57) Since P ≡ 1 ( m o d R ) P\equiv1\pmod R P ≡ 1 ( mod R ) ψ \psi ψ
We now bind these data to the automata; from now on, put x = 1 x=1 x = 1
q R ( m 2 + m 3 + m 4 + m 5 ) = Θ ψ , q R c 1 = ( Υ − q 5 R Υ 3 ) c 3 − q , Ω c 3 = q + ( q − q 2 ) R . (58) \begin{aligned}
qR(m_2+m_3+m_4+m_5)&=\Theta\psi,\\
qRc_1&=(\Upsilon-q^5R\Upsilon^3)c_3-q,\\
\Omega c_3&=q+(q-q^2)R. \tag*{(58)}
\end{aligned} q R ( m 2 + m 3 + m 4 + m 5 ) q R c 1 Ω c 3 = Θ ψ , = ( Υ − q 5 R Υ 3 ) c 3 − q , = q + ( q − q 2 ) R . (58) where
Θ = R + q R ( 1 − q 2 R + q 2 R 2 ) Υ − q 5 R 2 Υ 2 , Ω = 1 − q ( 1 + q ) R Υ − q 4 R Υ 2 + q 6 R 2 Υ 3 . \Theta=R+qR(1-q^2R+q^2R^2)\Upsilon-q^5R^2\Upsilon^2,
\qquad
\Omega=1-q(1+q)R\Upsilon-q^4R\Upsilon^2+q^6R^2\Upsilon^3. Θ = R + q R ( 1 − q 2 R + q 2 R 2 ) Υ − q 5 R 2 Υ 2 , Ω = 1 − q ( 1 + q ) R Υ − q 4 R Υ 2 + q 6 R 2 Υ 3 . For the first equality, note that the first five equations are satisfied by
q 2 R ( m 1 m 2 m 3 m 4 m 5 ) = ( 1 − q 2 ( 1 + q ) R Υ q R − q 3 ( 1 + q ) R 2 Υ q 2 R Υ − q 6 R 2 Υ 2 q 3 R 2 Υ q 4 R 3 Υ ) ψ . q^2R
\begin{pmatrix}
m_1\\
m_2\\
m_3\\
m_4\\
m_5
\end{pmatrix}
=
\begin{pmatrix}
1-q^2(1+q)R\Upsilon\\
qR-q^3(1+q)R^2\Upsilon\\
q^2R\Upsilon-q^6R^2\Upsilon^2\\
q^3R^2\Upsilon\\
q^4R^3\Upsilon
\end{pmatrix}
\psi. q 2 R m 1 m 2 m 3 m 4 m 5 = 1 − q 2 ( 1 + q ) R Υ q R − q 3 ( 1 + q ) R 2 Υ q 2 R Υ − q 6 R 2 Υ 2 q 3 R 2 Υ q 4 R 3 Υ ψ . substituting, the first equation of (54) becomes P ψ = q 2 R P\psi=q^2R P ψ = q 2 R R R R ψ ( 0 ) = 0 \psi(0)=0 ψ ( 0 ) = 0
Put
N = q + q ( 1 + q ) R + q 2 ( 1 + R ) Υ − q 6 R ( 1 + R ) Υ 2 , J = q + q ( 1 + q ) R + q 2 ( 1 + q 2 R ) Υ − q 3 R ( 1 + q 3 R ) Υ 2 . N=q+q(1+q)R+q^2(1+R)\Upsilon-q^6R(1+R)\Upsilon^2,
\qquad
J=q+q(1+q)R+q^2(1+q^2R)\Upsilon-q^3R(1+q^3R)\Upsilon^2. N = q + q ( 1 + q ) R + q 2 ( 1 + R ) Υ − q 6 R ( 1 + R ) Υ 2 , J = q + q ( 1 + q ) R + q 2 ( 1 + q 2 R ) Υ − q 3 R ( 1 + q 3 R ) Υ 2 . The two operator checks
Ω N = J P , Ω ( q ( 1 + R ) ) + J ( q 2 R ) = q + ( q − q 2 ) R (59) \Omega N=JP,\qquad\Omega\bigl(q(1+R)\bigr)+J(q^2R)=q+(q-q^2)R \tag*{(59)} Ω N = J P , Ω ( q ( 1 + R ) ) + J ( q 2 R ) = q + ( q − q 2 ) R (59) show, by uniqueness for Ω ≡ 1 ( m o d R ) \Omega\equiv1\pmod R Ω ≡ 1 ( mod R ) c 3 = q ( 1 + R ) + N ψ c_3=q(1+R)+N\psi c 3 = q ( 1 + R ) + N ψ
Θ − ( Υ − q 5 R Υ 3 ) N − ( 1 − R ) q Υ Q = ( R − q 2 ( 1 + q 3 R ) R 2 ) P , \Theta-(\Upsilon-q^5R\Upsilon^3)N-(1-R)q\Upsilon Q
=(R-q^2(1+q^3R)R^2)P, Θ − ( Υ − q 5 R Υ 3 ) N − ( 1 − R ) q Υ Q = ( R − q 2 ( 1 + q 3 R ) R 2 ) P , q − ( Υ − q 5 R Υ 3 ) ( q ( 1 + R ) ) + ( 1 − R ) q 2 R + ( R − q 2 ( 1 + q 3 R ) R 2 ) ( q 2 R ) = 0. (60) q-(\Upsilon-q^5R\Upsilon^3)\bigl(q(1+R)\bigr)+(1-R)q^2R+(R-q^2(1+q^3R)R^2)(q^2R)=0. \tag*{(60)} q − ( Υ − q 5 R Υ 3 ) ( q ( 1 + R ) ) + ( 1 − R ) q 2 R + ( R − q 2 ( 1 + q 3 R ) R 2 ) ( q 2 R ) = 0. (60) Applying these identities to ψ \psi ψ
D ( 1 , R ) = ( 1 − R ) q Υ ( Q ψ − R ) = ( 1 − R ) b . D(1,R)=(1-R)q\Upsilon(Q\psi-R)=(1-R)b. D ( 1 , R ) = ( 1 − R ) q Υ ( Q ψ − R ) = ( 1 − R ) b . Together with (55), this verifies the boundary identity. All checks are polynomial calculations using Υ R = q R Υ \Upsilon R=qR\Upsilon Υ R = q R Υ N N N J J J
It remains to certify convergence. Every term of 1 − P 1-P 1 − P R R R Z [ q ] \mathbb{Z}[q] Z [ q ] P P P R R R
ψ ∈ Z [ q ] [ [ R ] ] , ϕ = Q ψ − R ∈ Z [ q ] [ [ R ] ] ⊂ Q [ [ q , R ] ] . \psi\in\mathbb{Z}[q][[R]],\qquad\phi=Q\psi-R\in\mathbb{Z}[q][[R]]\subset\mathbb{Q}[[q,R]]. ψ ∈ Z [ q ] [[ R ]] , ϕ = Q ψ − R ∈ Z [ q ] [[ R ]] ⊂ Q [[ q , R ]] . Together with the checks above, this is a direct certificate: ϕ \phi ϕ b = q Υ ϕ b=q\Upsilon\phi b = q Υ ϕ
ν ( [ R n ] b ) = n + 1 + ν ( [ R n ] ϕ ) ≥ n + 1. \nu([R^n]b)=n+1+\nu([R^n]\phi)\ge n+1. ν ([ R n ] b ) = n + 1 + ν ([ R n ] ϕ ) ≥ n + 1. Theorem A(2) gives ν ( a i , j ) ≥ i + j \nu(a_{i,j})\ge i+j ν ( a i , j ) ≥ i + j a a a q q q
Implementation
The accompanying Julia package [3 ] , built on Oscar [17 ] , enumerates automata, computes their series in A A A x = 1 x=1 x = 1 b n b_n b n
Further convergence tests
The following constructions give further sufficient tests for the convergence of b b b
A degree bound for auxiliary normalized systems
A degree bound for auxiliary normalized systems. For L m = f Lm=f L m = f L ≡ I ( m o d q ) L\equiv I\pmod q L ≡ I ( mod q ) C = d m C=dm C = d m
κ ≥ max ( 1 , deg R L ) , κ 0 ≥ deg R f + deg R d . \kappa\ge\max(1,\deg_R L),\qquad\kappa_0\ge\deg_R f+\deg_R d. κ ≥ max ( 1 , deg R L ) , κ 0 ≥ deg R f + deg R d . Each factor I − L I-L I − L q q q R R R κ \kappa κ
deg R ( [ q t ] C ) ≤ κ 0 + κ t , ν ( [ R n ] C ) ≥ max ( 0 , ⌈ n − κ 0 κ ⌉ ) . \deg_R([q^t]C)\le\kappa_0+\kappa t,\qquad
\nu([R^n]C)\ge\max\left(0,\left\lceil\frac{n-\kappa_0}{\kappa}\right\rceil\right). deg R ([ q t ] C ) ≤ κ 0 + κ t , ν ([ R n ] C ) ≥ max ( 0 , ⌈ κ n − κ 0 ⌉ ) . The same estimate applies to each component of m m m deg R d \deg_R d deg R d ν ( [ R n ] C ) ≥ n \nu([R^n]C)\ge n ν ([ R n ] C ) ≥ n
Polynomial and rational operator witnesses
Polynomial and rational operator witnesses. In (9), seek operator rows Λ 1 , Λ 2 \Lambda_1,\Lambda_2 Λ 1 , Λ 2
d = ( 1 − R ) Λ 1 + Λ 2 L , Λ 2 f = ( 1 − R ) b 0 , b 0 ∈ K [ R ] . d=(1-R)\Lambda_1+\Lambda_2L,\qquad\Lambda_2f=(1-R)b_0,\qquad b_0\in\mathbb{K}[R]. d = ( 1 − R ) Λ 1 + Λ 2 L , Λ 2 f = ( 1 − R ) b 0 , b 0 ∈ K [ R ] . Then C = ( 1 − R ) Λ 1 m + Λ 2 f C=(1-R)\Lambda_1m+\Lambda_2f C = ( 1 − R ) Λ 1 m + Λ 2 f b = Λ 1 m + b 0 b=\Lambda_1m+b_0 b = Λ 1 m + b 0 Λ 1 \Lambda_1 Λ 1 q = 0 q=0 q = 0 m m m T \mathbb{T} T Λ 2 ∈ K [ R ] 1 × s \Lambda_2\in\mathbb{K}[R]^{1\times s} Λ 2 ∈ K [ R ] 1 × s ( 1 − R ) O (1-R)\mathcal{O} ( 1 − R ) O R = 1 R=1 R = 1 ( Λ 2 f ) ( 1 ) = 0 (\Lambda_2f)(1)=0 ( Λ 2 f ) ( 1 ) = 0 T \mathbb{T} T T − k ∑ q n R n = ∑ q − k n q n R n \mathbb{T}^{-k}\sum q_nR^n=\sum q^{-kn}q_nR^n T − k ∑ q n R n = ∑ q − k n q n R n T = q n \mathbb{T}=q^n T = q n
Contracting coefficient recurrences
Coefficient extraction from a holonomic system gives, beyond finitely many singular indices, a finite state recurrence v n + 1 = M ( q n ) v n v_{n+1}=M(q^n)v_n v n + 1 = M ( q n ) v n b n = π ( q n ) v n b_n=\pi(q^n)v_n b n = π ( q n ) v n q n q^n q n ℓ \ell ℓ q n q^n q n Lemma 3.4 (2); consequently the required eventual inequalities reduce to finitely many checks. This sufficient test does not capture cancellation special to one initial vector, such as the one recorded by Proposition 3.7 .
Spans of convergent holonomic series
Call a holonomic series g = ∑ g n R n ∈ K [ [ R ] ] g=\sum g_nR^n\in K[[R]] g = ∑ g n R n ∈ K [[ R ]] certified convergent input when it comes with selecting data and a proved bound ν ( g n ) ≥ δ n − c \nu(g_n)\ge\delta n-c ν ( g n ) ≥ δ n − c δ > 0 \delta>0 δ > 0
∇ λ g ( R ) = g ( R ) − g ( R λ ) 1 − R , λ ≥ 2 , for which [ R n ] ∇ λ g = ∑ j = ⌈ ( n + 1 ) / λ ⌉ n g j . \nabla_\lambda g(R)=\frac{g(R)-g(R^\lambda)}{1-R},\qquad\lambda\ge2,\qquad\text{for which}\qquad[R^n]\nabla_\lambda g=\sum_{j=\lceil(n+1)/\lambda\rceil}^{n}g_j. ∇ λ g ( R ) = 1 − R g ( R ) − g ( R λ ) , λ ≥ 2 , for which [ R n ] ∇ λ g = j = ⌈( n + 1 ) / λ ⌉ ∑ n g j . so that its slope is at least δ / λ \delta/\lambda δ / λ Υ λ \Upsilon^\lambda Υ λ R ↦ R λ R\mapsto R^\lambda R ↦ R λ Υ λ \Upsilon^\lambda Υ λ q q q
For a finite family g 1 , … , g t g_1,\ldots,g_t g 1 , … , g t
C = ∑ i , k , ℓ c i , k , ℓ ( 1 − R ) R ℓ Υ k g i , c i , k , ℓ ∈ K . C=\sum_{i,k,\ell}c_{i,k,\ell}(1-R)R^\ell\Upsilon^k g_i,\qquad c_{i,k,\ell}\in K. C = i , k , ℓ ∑ c i , k , ℓ ( 1 − R ) R ℓ Υ k g i , c i , k , ℓ ∈ K . Take a common scalar annihilator Ω \Omega Ω C C C Lemma 3.4 (1), a linear combination vanishes identically if and only if its coefficients at E Ω E_\Omega E Ω C C C b b b
Enumerating finite expressions in these constructors, with bounds on operator degrees, gives a sound search, which terminates whenever the canonical b b b
Acknowledgments
I am deeply grateful to Jehanne Dousse for stimulating discussions on partition identities, and for pointing me to many examples to which the methods of this article apply.
ChatGPT 6 Astra and Claude Opus 5.5 helped write the code that searches for and checks the certificates, and Claude helped prepare the manuscript. No AI was used to set up the underlying mathematical theory here.
Julien David generously contributed the enumerator of finite automata used in §§§ 3.8 and § 4.7 (exhaustivautomata in [3 ] ).
