Kauers–Koutschan recurrence conjecture

What Lean checks

Written proof and exact symbolic verification of both recurrences for all lengths.

Write ana_n for the number of permutations π\pi of [n][n] satisfying π(i+2)−π(i)≠2\pi(i+2)-\pi(i)\ne2 for every 1≤i≤n−21\le i\le n-2, including a0=1a_0=1. We prove that ∑i=08Pi(n)an+i=0\sum_{i=0}^8 P_i(n)a_{n+i}=0 for every n≥0n\ge0, with exactly the polynomials listed in A189281. Row ii of the accompanying coefficient table gives PiP_i in ascending degree, starting at row zero. We also verify the published order-thirteen operator. Conjecture 10 · OEIS operators · Coefficient table

1. Inclusion–exclusion on two chains

Put p=⌈n/2⌉p=\lceil n/2\rceil and q=⌊n/2⌋q=\lfloor n/2\rfloor. The odd and even positions, in their natural orders, form two chains of lengths p,qp,q. The values form two chains with the same lengths. An offending pair is an oriented adjacency of a value chain that maps to an oriented adjacency of a position chain under π−1\pi^{-1}.

Use inclusion–exclusion on these value-chain adjacencies. A selected subset groups each value chain into an ordered list of blocks of consecutive values of the same parity. A block of length ℓ\ell has sign (−1)ℓ−1(-1)^{\ell-1}. Assign each block to one of the position chains. Within that chain its entries must be consecutive, in the specified order. If kik_i blocks go to position chain ii, there are ki!k_i! orders for them, provided they fill that chain. Blocks are distinguishable by their original value intervals. This counts every permutation satisfying the selected adjacencies exactly once.

Let uiu_i mark the length of position chain ii, and vjv_j the length of value chain jj. Let x1,x2x_1,x_2 be independent unit exponential random variables, so 𝔼xik=k!\mathbb E x_i^k=k!. Summing a nonempty signed block gives z/(1+z)z/(1+z). Summing the ordered list of such blocks in each value chain gives the generating function

F(u,v)=𝔼∏j=12(1−∑i=12xiuivj1+uivj)−1. F(u,v)=\mathbb E\prod_{j=1}^{2} \left(1-\sum_{i=1}^{2}x_i\frac{u_i v_j}{1+u_i v_j}\right)^{-1}.

Then ana_n is the coefficient of u1pu2qv1pv2qu_1^p u_2^q v_1^p v_2^q in FF. All series and expectations here are coefficientwise, so each uses only finitely many moments.

2. A Schur moment

Realize xi=|gi|2x_i=|g_i|^2 for independent complex Gaussian coordinates with density π−1e−|z|2\pi^{-1}e^{-|z|^2}. Write D=diag(u1,u2)D=\mathrm{diag}(u_1,u_2) and T=gg*−IT=gg^*-I. The matrix determinant lemma gives

det(I−vDT)=∏i(1+uiv)(1−∑ixiuiv1+uiv). \det(I-vDT)= \prod_i(1+u_i v)\left(1-\sum_i x_i\frac{u_i v}{1+u_i v}\right).

For a two-part partition λ=(r,j)\lambda=(r,j) with r≥j≥0r\ge j\ge0, write sλs_\lambda for its Schur character. The two-variable Cauchy identity gives

F(u,v)=∏i,j(1+uivj)∑λsλ(v1,v2)𝔼sλ(DT). F(u,v)=\prod_{i,j}(1+u_i v_j) \sum_{\lambda} s_\lambda(v_1,v_2)\,\mathbb E\,s_\lambda(DT). \tag{1}

Indeed, for eigenvalues z1,z2z_1,z_2 of DTDT, the Cauchy kernel is ∏i,j(1−zivj)−1\prod_{i,j}(1-z_i v_j)^{-1}. This identity also follows directly by summing the two-variable alternant formula for s(r,j)s_{(r,j)}. It extends to all matrices by polynomial identity in each homogeneous degree.

The random matrix TT is invariant in law under unitary conjugation. For ρλ=detj⊗Symr−j\rho_\lambda=\det^j\otimes\mathrm{Sym}^{r-j} on ℂ2\mathbb C^2, the expectation 𝔼ρλ(T)\mathbb E\rho_\lambda(T) commutes with every ρλ(U)\rho_\lambda(U), U∈U(2)U\in U(2). This representation is irreducible. On homogeneous polynomials, the diagonal torus separates the monomials and the two off-diagonal infinitesimal operators connect adjacent monomials, proving irreducibility of the symmetric power. The determinant twist preserves it. Schur’s lemma and the trace therefore give

𝔼sλ(DT)=sλ(u1,u2)𝔼sλ(T)r−j+1. \mathbb E\,s_\lambda(DT)=s_\lambda(u_1,u_2)\, \frac{\mathbb E\,s_\lambda(T)}{r-j+1}. \tag{2}

Let t=|g1|2+|g2|2t=|g_1|^2+|g_2|^2. It has density te−tte^{-t} on the positive half-line. The eigenvalues of TT are t−1,−1t-1,-1. Put k=r+1k=r+1, so the dimension in (2) is k−jk-j. The alternant formula has denominator (t−1)−(−1)=t(t-1)-(-1)=t, which cancels the factor tt in the density. Define Dℓ=∫0∞e−t(t−1)ℓdtD_\ell=\int_0^\infty e^{-t}(t-1)^\ell\,dt. Integration by parts gives D0=1D_0=1 and Dℓ+1=(ℓ+1)Dℓ+(−1)ℓ+1D_{\ell+1}=(\ell+1)D_\ell+(-1)^{\ell+1}, the derangement numbers. The scalar in (2) is exactly

C(k,j)=(−1)jDk−(−1)kDjk−j. C(k,j)=\frac{(-1)^jD_k-(-1)^kD_j}{k-j}. \tag{3}

3. Extracting the count

For each subset SS of the four cells of a 22-by-22 square, write d=|S|d=|S| and let ri,cir_i,c_i be its row and column sums. Selecting these numerator factors in (1) leaves total degree n−dn-d on each side. Put

m=n−d+1,J=min(p−r1,q−r2,p−c1,q−c2). m=n-d+1,\qquad J=\min(p-r_1,q-r_2,p-c_1,q-c_2).

The weights of s(k−1,j)(u1,u2)s_{(k-1,j)}(u_1,u_2) are the monomials of total degree k+j−1k+j-1 with each exponent at least jj, each with coefficient one. The same applies to vv. Thus

an=∑S⊆[2]×[2]∑j=0JC(m−j,j). a_n=\sum_{S\subseteq[2]\times[2]}\ \sum_{j=0}^{J} C(m-j,j). \tag{4}

A negative upper limit gives zero. For every nonempty inner sum 2J≤m−12J\le m-1, so its denominators are nonzero. This proves the formula including n=0n=0.

4. A two-step recurrence for the full sum

For m≥0m\ge0 define

Tm=∑0≤j<m−jC(m−j,j)=∑0≤k≤m2k≠m(−1)m−kDk2k−m,Um=∑k=0m(−1)m−kDk. T_m=\sum_{0\le j<m-j}C(m-j,j) =\sum_{\substack{0\le k\le m\\2k\ne m}} \frac{(-1)^{m-k}D_k}{2k-m},\qquad U_m=\sum_{k=0}^{m}(-1)^{m-k}D_k .

The second expression for TmT_m pairs kk with m−km-k. In Tm+2T_{m+2} separate the endpoints 0,m+20,m+2. Together they contribute Dm+1D_{m+1} by the derangement recurrence. At each interior index k+1k+1, substitute Dk+1=(k+1)Dk+(−1)k+1D_{k+1}=(k+1)D_k+(-1)^{k+1}. The constant terms sum to zero by k↔m−kk\leftrightarrow m-k. Writing k+1=(2k−m)/2+(m+2)/2k+1=(2k-m)/2+(m+2)/2 in the remaining terms yields

Tm+2=Dm+1−m+22Tm−12Um+12𝟏2∣m(−1)m/2Dm/2. T_{m+2}=D_{m+1}-\frac{m+2}{2}T_m-\frac12 U_m +\frac12\,\mathbf{1}_{2\mid m}(-1)^{m/2}D_{m/2}. \tag{5}

Also Um+1=Dm+1−UmU_{m+1}=D_{m+1}-U_m. The half-index terms Ej=(−1)jDjE_j=(-1)^jD_j satisfy Ej+1=−(j+1)Ej+1E_{j+1}=-(j+1)E_j+1.

5. Exact substitution into the conjectured operators

Here are the finite polynomial identities completing the proof. The included checker expands them over ℚ\mathbb Q, using the coefficients in A189281. We describe the arithmetic explicitly so that the identity can be replayed in another algebra system. Checker · Original operator · Published factorization of the order-thirteen operator

For t=4,…,18t=4,\ldots,18 write At=a2h+tA_t=a_{2h+t}, where h≥0h\ge0 is arbitrary. Treat T2h,T2h+1,D2h,U2h,Eh,1T_{2h},T_{2h+1},D_{2h},U_{2h},E_h,1 as six independent indeterminates over ℚ[h]\mathbb Q[h], with BB representing 11 in the inhomogeneous recurrences. Generate the required positive shifts by (5) and the three first-order recurrences above. For each numerator subset take s=t+1−ds=t+1-d and let J0J_0 be the cutoff in (4) calculated at n=tn=t. The contribution to AtA_t is

T2h+s−∑i=J0+1⌊(s−1)/2⌋(−1)s(Eh+s−i−Eh+i)s−2i. T_{2h+s}- \sum_{i=J_0+1}^{\lfloor(s-1)/2\rfloor} \frac{(-1)^s(E_{h+s-i}-E_{h+i})}{s-2i}. \tag{6}

Indeed the full sum includes exactly those omitted pairs with j=h+ij=h+i. Formula (3) gives the displayed summand. All denominator factors are nonzero rational constants. Each computed AtA_t is thus a linear form in the six indeterminates with polynomial coefficients in hh.

Applying the original order-eight operator gives the following six coefficients in the indicated order.

Base index T2hT_{2h} T2h+1T_{2h+1} D2hD_{2h} U2hU_{2h} EhE_h BB
2h+42h+4 0 0 0 0 0 0
2h+52h+5 0 0 0 0 0 0

The checker verifies the same two polynomial identities for the equivalent order-thirteen operator using van Hoeij’s factorization. For n=0,1,2,3n=0,1,2,3 direct substitution of (4) gives residual zero for both operators. Every n≥0n\ge0 occurs in these four initial indices or one of the two polynomial identities, proving the conjecture.