MathDB

Direct recurrence conjecture for the coefficients of Hermite subdivision schemes

About 8 years old · traced to

Let αk,ℓ1\alpha^{1}_{k,\ell}, for k∈Nk\in\mathbb{N} and ℓ=1,…,k\ell=1,\dots,k, be the coefficients defined recursively in Definition 3.1 of the paper. The convention is that

∑i=ℓk−2αi+1,ℓ−11=0\sum_{i=\ell}^{k-2}\alpha^{1}_{i+1,\ell-1}=0

when ℓ=k−1\ell=k-1.

Direct recurrence conjecture. The coefficients can be computed directly by

αk,11:=2k,\alpha^{1}_{k,1}:=2k, αk,ℓ1:=2(ℓ+1)(ℓ−1)!+(ℓ−1)∑i=ℓk−2αi+1,ℓ−11,ℓ=2,…,k−1,\alpha^{1}_{k,\ell}:=2(\ell+1)(\ell-1)!+(\ell-1)\sum_{i=\ell}^{k-2}\alpha^{1}_{i+1,\ell-1},\qquad \ell=2,\dots,k-1,

and

αk,k1:=2(k−1)!.\alpha^{1}_{k,k}:=2(k-1)!.

In particular, αk,k−11=2k(k−2)!\alpha^{1}_{k,k-1}=2k(k-2)!.

The claim is motivated by numerical computations and the displayed values for k≤7k\leq 7; no proof or resolution is supplied in the source.

References

Primary source

Costanza Conti and Svenja Hüning, “An algebraic approach to polynomial reproduction of Hermite subdivision schemes”, arXiv:1803.11007 (2018).

polynomial-reproductionrecurrence-relationssubdivision-schemes
Posted

Progress summary

Refreshed
Claimed solved

A posted argument claims to prove the conjecture through a stronger formula, but that proof has not been independently verified.

The conjecture was posed by Costanza Conti and Svenja Hüning in 2018 and asserts a direct computation rule for the recursively defined coefficients αk,ℓ1\alpha^{1}_{k,\ell}; the paper supplies numerical evidence but no proof.

Known results

  • Numerical values through k≤7k \le 7 support the formulas, including αk,k−11=2k(k−2)!\alpha^{1}_{k,k-1}=2k(k-2)!; no proof is given in the source (Conti–Hüning, 2018).

Posted attempt

A posted argument claims a complete proof of the stronger identity αk,ℓ1=2(ℓ−1)!(kℓ)\alpha^{1}_{k,\ell}=2(\ell-1)!\binom{k}{\ell}, using Stirling-number identities, and derives the conjectured recurrence. The attempt has not been independently verified.

Current status (as of August 2026): The original conjecture has only numerical support, while a complete proof has been claimed in an unverified posted argument; no published or independently checked resolution was found.

Sources

Solutions 1

ProofThis solution needs a summarySee full solutionHide full solution

We prove the stronger closed formula

αk,ℓ1=2(ℓ−1)!(kℓ)(k≥1, 1≤ℓ≤k).(1)\boxed{ \alpha^1_{k,\ell} = 2(\ell-1)!\binom{k}{\ell} } \qquad(k\ge1,\ 1\le\ell\le k). \tag{1}

Let c(k,n)c(k,n) denote the unsigned Stirling number of the first kind. The auxiliary polynomials in the defining recurrence satisfy

qk(−x)=∏r=0k−1(−2x−r)=(−1)k(2x)k‾,q_k(-x) = \prod_{r=0}^{k-1}(-2x-r) = (-1)^k(2x)^{\overline{k}},

so their coefficients are

γnk=(−1)k2nc(k,n).(2)\gamma_n^k=(-1)^k2^n c(k,n). \tag{2}

Substituting (2) into the original recursion gives

αk,k−n+11=(−1)k21−n(nγnk−∑j=1k−n(−1)jαk,j1γn−1k−j)=2nc(k,n)−∑j=1k−nαk,j1c(k−j,n−1).(3)\begin{aligned} \alpha^1_{k,k-n+1} &= (-1)^k2^{1-n} \left( n\gamma_n^k- \sum_{j=1}^{k-n} (-1)^j\alpha^1_{k,j}\gamma_{n-1}^{k-j} \right)\\ &= 2n c(k,n) - \sum_{j=1}^{k-n} \alpha^1_{k,j}c(k-j,n-1). \tag{3} \end{aligned}

Count permutations of [k][k] with nn cycles and one distinguished cycle. There are nc(k,n)n c(k,n) such permutations. If the distinguished cycle has length jj, its elements and cyclic order can be chosen in

(kj)(j−1)!\binom{k}{j}(j-1)!

ways, and the remaining elements can be arranged in c(k−j,n−1)c(k-j,n-1) ways. Therefore

nc(k,n)=∑j=1k−n+1(kj)(j−1)!c(k−j,n−1).(4)n c(k,n) = \sum_{j=1}^{k-n+1} \binom{k}{j}(j-1)!c(k-j,n-1). \tag{4}

The initial condition

αk,11=2k\alpha^1_{k,1}=2k

agrees with (1). Assume (1) holds for all earlier indices

j<ℓ=k−n+1.j<\ell=k-n+1.

Substituting these values into (3) and applying (4), all but the last marked-cycle term cancel:

αk,ℓ1=2(kℓ)(ℓ−1)!c(k−ℓ,n−1)=2(kℓ)(ℓ−1)!,\alpha^1_{k,\ell} = 2\binom{k}{\ell}(\ell-1)! c(k-\ell,n-1) = 2\binom{k}{\ell}(\ell-1)!,

because k−ℓ=n−1k-\ell=n-1. This proves (1) for all k,ℓk,\ell.

Finally, for 2≤ℓ≤k−12\le\ell\le k-1, the proposed direct recurrence follows from the hockey-stick identity:

2(ℓ+1)(ℓ−1)!+(ℓ−1)∑i=ℓk−2αi+1,ℓ−11=2(ℓ−1)!(ℓ+1+∑t=ℓ+1k−1(tℓ−1))=2(ℓ−1)!(kℓ)=αk,ℓ1.\begin{aligned} 2(\ell+1)(\ell-1)! + (\ell-1) \sum_{i=\ell}^{k-2} \alpha^1_{i+1,\ell-1} &= 2(\ell-1)! \left( \ell+1+ \sum_{t=\ell+1}^{k-1} \binom{t}{\ell-1} \right)\\ &= 2(\ell-1)!\binom{k}{\ell}\\ &= \alpha^1_{k,\ell}. \end{aligned}

The boundary values are likewise

αk,11=2k,αk,k1=2(k−1)!,\alpha^1_{k,1}=2k,\qquad \alpha^1_{k,k}=2(k-1)!,

and in particular

αk,k−11=2k(k−2)!.\alpha^1_{k,k-1}=2k(k-2)!.

Thus the complete direct-recurrence conjecture holds, together with the stronger explicit closed formula.

0
Shivam Patel Posted