LemmaStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedjudge pass (gpt-6-luna)

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

DPLR SSM filter values reduce to Cauchy products

Statement

Let $N, r \geq 1$ , $M = 2^{q} \geq 1$ , $1 \leq L \leq M$ , $A = Λ - P Q^{*}$ with diagonal $Λ \in C^{N \times N}$ and $P, Q \in C^{N \times r}$ , where $^{*}$ denotes conjugate transpose, $B, C \in C^{N}$ , and $Δ > 0$ . Assume $G = I - Δ A / 2$ is invertible, define $\overset{ˉ}{A} = G^{- 1} (I + Δ A / 2)$ , $\overset{ˉ}{B} = G^{- 1} Δ B$ , and put ${\tilde{C}}_{M} = (I - {\overset{ˉ}{A}}^{M})^{*} C$ . For each $M$ th root of unity $z \neq - 1$ , let $s (z) = (2 / Δ) (1 - z) / (1 + z)$ , $R (z) = (s (z) I - Λ)^{- 1}$ , and $W (z) = I_{r} + Q^{*} R (z) P$ . Assume all these $R (z)$ and $W (z)$ are invertible. The length- $M$ truncated generating value $H_{M} (z) = \sum_{j = 0}^{M - 1} C^{*} {\overset{ˉ}{A}}^{j} \overset{ˉ}{B} z^{j}$ then satisfies

H_{M} (z) = \frac{2}{1 + z} ({\tilde{C}}_{M}^{*} R (z) B - {\tilde{C}}_{M}^{*} R (z) P W (z)^{- 1} Q^{*} R (z) B) (z \neq - 1) .

If $M$ is even, the root $z = - 1$ has the finite value $H_{M} (- 1) = (Δ / 2) {\tilde{C}}_{M}^{*} B$ . For $a = 2 / Δ$ and each diagonal entry $λ_{j} \neq - a$ , put $μ_{j} = (a - λ_{j}) / (a + λ_{j})$ . For any $u, v \in C^{N}$ and root $z \neq - 1$ ,

\frac{2}{1 + z} u^{*} R (z) v = \frac{Δ}{2} \sum_{λ_{j} = - a} \overline{u_{j}} v_{j} - 2 \sum_{λ_{j} \neq - a} \frac{\overline{u_{j}} v_{j}}{a + λ_{j}} \frac{1}{z - μ_{j}} .

Thus the four families of scalar products ${\tilde{C}}_{M}^{*} R B$ , ${\tilde{C}}_{M}^{*} R P$ , $Q^{*} R B$ , and $Q^{*} R P$ reduce to $1 + 2 r + r^{2} = (r + 1)^{2}$ roots-of-unity Cauchy products; when $r = 1$ there are four.

Statement references

Gu, Goel, and Ré, “Efficiently Modeling Long Sequences with Structured State Spaces,” Appendix C.3

Exact Cauchy matrix-vector product on a radix-two root grid

DPLR structured state-space parameterization

Facts & Assumptions

Given: The finite DPLR matrices, $1 \leq L \leq M = 2^{q}$ , $Δ > 0$ , the bilinear inverse, and all root-grid diagonal resolvents and low-rank corrections required in the Statement.

[A1]

For every root $z \neq - 1$ , both $R (z)$ and $W (z)$ in the Statement are invertible; the bilinear matrix $G$ is invertible.

[F1]

DPLR structured state-space parameterization: $\overset{ˉ}{A} = (I - Δ A / 2)^{- 1} (I + Δ A / 2)$ , $\overset{ˉ}{B} = (I - Δ A / 2)^{- 1} Δ B$ , and the kernel coefficients are $C^{*} {\overset{ˉ}{A}}^{j} \overset{ˉ}{B}$ .

[F2]

Woodbury inverse for a diagonal-plus-low-rank update: for invertible $D$ , $(D + P Q^{*})^{- 1} = D^{- 1} - D^{- 1} P (I + Q^{*} D^{- 1} P)^{- 1} Q^{*} D^{- 1}$ whenever the displayed correction is invertible.

[F3]

Exact Cauchy matrix-vector product on a radix-two root grid: on a primitive $M$ th-root grid, the procedure returns $\sum_{j} a_{j} / (z_{k} - μ_{j})$ at each root, and reports a collision if a pole equals a root.

Proof

1.1A1F1F2algebra

Put $α = Δ / 2$ . For every root $z \neq - 1$ , substitution of $\overset{ˉ}{A} = G^{- 1} (I + α A)$ gives $I - z \overset{ˉ}{A} = G^{- 1} ((1 - z) I - α (1 + z) A) = G^{- 1} α (1 + z) (s (z) I - A)$ . By [A1] and [F2], $s (z) I - A = (s (z) I - Λ) + P Q^{*}$ is invertible; inversion and multiplication by $\overset{ˉ}{B} = G^{- 1} Δ B$ give $(I - z \overset{ˉ}{A})^{- 1} \overset{ˉ}{B} = \frac{2}{1 + z} (s (z) I - A)^{- 1} B$ . At $z = - 1$ , $I + \overset{ˉ}{A} = G^{- 1} (G + I + α A) = 2 G^{- 1}$ is invertible.

1.2A1algebra

For any root $z \neq - 1$ , put $a = 1 / α = 2 / Δ$ . For $λ_{j} \neq - a$ , direct algebra gives $s (z) - λ_{j} = \frac{(a - λ_{j}) - (a + λ_{j}) z}{1 + z} = \frac{(a + λ_{j}) (μ_{j} - z)}{1 + z}$ , hence $\frac{2}{1 + z} (s (z) - λ_{j})^{- 1} = - \frac{2}{a + λ_{j}} (z - μ_{j})^{- 1}$ . For $λ_{j} = - a$ , $s (z) - λ_{j} = 2 a / (1 + z)$ and the scaled reciprocal is $1 / a = Δ / 2$ . No nonexceptional pole equals $- 1$ , since $μ_{j} = - 1$ would imply $2 a = 0$ although $a > 0$ .

2.1F1step 1.1algebra

At each root, $z^{M} = 1$ and step 1.1 makes $I - z \overset{ˉ}{A}$ invertible. The finite geometric identity gives $(I - {\overset{ˉ}{A}}^{M}) (I - z \overset{ˉ}{A})^{- 1} = \sum_{j = 0}^{M - 1} z^{j} {\overset{ˉ}{A}}^{j}$ . Multiplying by $C^{*}$ and $\overset{ˉ}{B}$ , and using ${\tilde{C}}_{M}^{*} = C^{*} (I - {\overset{ˉ}{A}}^{M})$ , gives $H_{M} (z) = {\tilde{C}}_{M}^{*} (I - z \overset{ˉ}{A})^{- 1} \overset{ˉ}{B}$ ; for $z \neq - 1$ , step 1.1 supplies its bilinear resolvent expression.

3.1A1F2step 2.1algebra

Since $A = Λ - P Q^{*}$ , $s I - A = (s I - Λ) + P Q^{*}$ . Applying [F2] with $D = s I - Λ$ and multiplying by ${\tilde{C}}_{M}^{*}$ and $B$ gives the displayed Woodbury expression for $H_{M} (z)$ from step 2.1, with $R = (s I - Λ)^{- 1}$ and $W = I + Q^{*} R P$ .

3.2A1F1step 1.1step 2.1algebra

If $M$ is even, $- 1$ is a root. Step 1.1 gives $(I + \overset{ˉ}{A})^{- 1} \overset{ˉ}{B} = (1 / 2) G (G^{- 1} Δ B) = (Δ / 2) B$ ; applying the finite geometric identity from step 2.1 yields $H_{M} (- 1) = {\tilde{C}}_{M}^{*} (I + \overset{ˉ}{A})^{- 1} \overset{ˉ}{B} = (Δ / 2) {\tilde{C}}_{M}^{*} B$ .

4.1A1F3step 1.2step 3.1algebra∎

By step 1.2, each scaled diagonal-resolvent entry in step 3.1 is one scalar roots-of-unity Cauchy sum, with the $λ_{j} = - a$ entries supplied by their explicit constants. The four vector-pair families ${\tilde{C}}_{M}^{*} R B$ , ${\tilde{C}}_{M}^{*} R P$ , $Q^{*} R B$ , and $Q^{*} R P$ have sizes $1, r, r, r^{2}$ , so [F3] evaluates at most $(r + 1)^{2}$ products; at $r = 1$ this is four.

Depends on

Used by

S4 convolution-filter arithmetic and numerical cost Theorem

Dependency tree · two levels

6 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Gu, Goel, and Ré, Efficiently Modeling Long Sequences with Structured State Spaces, Appendix C.3 (standard reference, not scraped)