Realization Calculus

Download original file

This is the original TeX manuscript source. Use the paper’s PDF for typeset equations.

Read the typeset paper

1 \section{Complete filtered transfer algebras}\label{sec:filtered}
2 
3 A filtration records how deeply a term lies in the chosen notion of precision. The weights record guaranteed filtration gains that add under multiplication. A discrete valuation ring provides the main example.
4 
5 \begin{definition}[Complete multiplicative filtration]\label{def:filtered_algebra}
6 A complete filtered algebra is a unital algebra $\Bcal$ with a decreasing sequence of two-sided ideals
7 \[
8 \Bcal=F^0\Bcal\supseteq F^1\Bcal\supseteq F^2\Bcal\supseteq\cdots
9 \]
10 such that
11 \[
12 F^r\Bcal\,F^s\Bcal\subseteq F^{r+s}\Bcal,
13 \qquad
14 \bigcap_{L\geq0}F^L\Bcal=0,
15 \]
16 and the natural map
17 \[
18 \Bcal\longrightarrow\varprojlim_L\Bcal/F^L\Bcal
19 \]
20 is an isomorphism.  A transfer term $N_e$ has a declared positive integer weight $w(e)\in\mathbb Z_{>0}$ when
21 \[
22 N_e\in F^{w(e)}\Bcal.
23 \]
24 \end{definition}
25 
26 In the filtration topology, reduction to $\Bcal/F^L\Bcal$ is continuous when the quotient has the discrete topology. Its kernel $F^L\Bcal$ is therefore closed. In particular, a convergent sum of terms in $F^L\Bcal$ remains in that ideal.
27 
28 If $\OO$ is a complete discrete valuation ring with uniformizer $\pi$ and $\Bcal$ is a separated and complete $\OO$ algebra for the filtration
29 \[
30 F^L\Bcal=\pi^L\Bcal,
31 \]
32 then this is a standard example. Finite matrix algebras over $\OO$ satisfy these conditions. Completeness of $\OO$ alone does not imply completeness of every $\OO$ algebra. Basic facts about completeness in this setting are reviewed in \cite{Serre1979}.
33 
34 \begin{theorem}[Weighted inverse]\label{thm:weighted_inverse}
35 Let $\Bcal$ be a complete filtered algebra.  Let $D\in\Bcal$ be invertible with
36 \[
37 D,D^{-1}\in F^0\Bcal.
38 \]
39 Let $E$ be a finite set and suppose
40 \[
41 T=D+\sum_{e\in E}N_e,
42 \qquad
43 N_e\in F^{w(e)}\Bcal,
44 \qquad
45 w(e)\geq1.
46 \]
47 Set
48 \[
49 A_e=D^{-1}N_e.
50 \]
51 For a word $\gamma=(e_1,\ldots,e_r)$, write
52 \[
53 A_\gamma=A_{e_r}\cdots A_{e_1},
54 \qquad
55 W(\gamma)=\sum_{j=1}^rw(e_j).
56 \]
57 The empty word has weight zero and contributes the identity.  Then $T$ is invertible and
58 \[
59 T^{-1}
60 =
61 \sum_\gamma(-1)^{|\gamma|}A_\gamma D^{-1}.
62 \]
63 The series converges in the filtration, and the term indexed by $\gamma$ belongs to $F^{W(\gamma)}\Bcal$.
64 \end{theorem}
65 
66 \begin{proof}
67 Put
68 \[
69 A=\sum_{e\in E}A_e.
70 \]
71 Since left multiplication by $D^{-1}$ preserves the filtration, $A\in F^1\Bcal$.  Completeness gives the convergent Neumann series
72 \[
73 (I+A)^{-1}=\sum_{r\geq0}(-A)^r.
74 \]
75 Because $T=D(I+A)$,
76 \[
77 T^{-1}=(I+A)^{-1}D^{-1}.
78 \]
79 Expanding each power of $A$ gives the sum over words, with the rightmost edge acting first.  Multiplicativity of the filtration gives
80 \[
81 A_\gamma\in F^{W(\gamma)}\Bcal.
82 \]
83 For each $L$, only finitely many words have weight below $L$ because $E$ is finite and every edge has positive weight.  Thus the word expansion converges to the same inverse.
84 \end{proof}
85 
86 The preceding formula does not yet use packet blocks. When $D$ is packet diagonal and the terms $N_e$ are individual transfers, only words with compatible packet endpoints can contribute. These words become directed paths.
87 
88 \begin{theorem}[Block path formula]\label{thm:block_path_formula}
89 Let $\Pcal=(P_\alpha)_{\alpha\in I}$ be a finite packet system in a complete filtered algebra of operators.  Suppose
90 \[
91 D=\sum_\alpha P_\alpha D P_\alpha
92 \]
93 belongs to $\Bcal$ and is invertible on every packet.  Assume that the assembled inverse
94 \[
95 D^{-1}=\sum_\alpha D_\alpha^{-1}P_\alpha\in\Bcal=F^0\Bcal,
96 \qquad D_\alpha=P_\alpha DP_\alpha,
97 \]
98 where each packet inverse is extended by zero to the other packets.  Let the edge set be finite, assume $w(e)\geq1$ for every edge, and write
99 \[
100 N=\sum_{e:\alpha\to\beta}N_e,
101 \qquad
102 N_e=P_\beta N_eP_\alpha,
103 \qquad
104 N_e\in F^{w(e)}\Bcal.
105 \]
106 For an edge $e:\alpha\to\beta$, put
107 \[
108 A_e=(P_\beta DP_\beta)^{-1}N_e.
109 \]
110 Then the block from $P_\alpha X$ to $P_\beta X$ of $(D+N)^{-1}$ is
111 \[
112 P_\beta(D+N)^{-1}P_\alpha
113 =
114 \sum_{\gamma:\alpha\leadsto\beta}
115 (-1)^{|\gamma|}A_\gamma D_\alpha^{-1},
116 \]
117 where $D_\alpha=P_\alpha DP_\alpha$ and the sum runs over directed paths from $\alpha$ to $\beta$, including the empty path when $\alpha=\beta$.
118 \end{theorem}
119 
120 \begin{proof}
121 The diagonal inverse is
122 \[
123 D^{-1}=\sum_\alpha D_\alpha^{-1}P_\alpha.
124 \]
125 The block $P_\beta D^{-1}NP_\alpha$ is nonzero only when there is a declared edge from $\alpha$ to $\beta$.  Repeated block multiplication shows that the $r$th power of $D^{-1}N$ is the sum over all directed paths of length $r$, with the operator factors ordered along the path.  Apply \cref{thm:weighted_inverse} and multiply on the right by the packet diagonal inverse.
126 \end{proof}
127 
128 \begin{corollary}[Minimum path weight]\label{cor:minimum_path_weight}
129 For packets $\alpha$ and $\beta$, let $d(\alpha,\beta)$ be the least total weight of a directed path from $\alpha$ to $\beta$, with $d=\infty$ when no path exists.  Use the convention $F^\infty\Bcal=\bigcap_{L\geq0}F^L\Bcal=0$.  If $\alpha\ne\beta$, then
130 \[
131 P_\beta(D+N)^{-1}P_\alpha
132 \in
133 F^{d(\alpha,\beta)}\Bcal.
134 \]
135 If there is no path from $\alpha$ to $\beta$, the block is zero.
136 \end{corollary}
137 
138 \begin{proof}
139 Every term in the block path formula is indexed by a path from $\alpha$ to $\beta$ and lies in the filtration level given by its total weight.  If no such path exists, the sum is empty.
140 \end{proof}
141 
142 \begin{example}[A longer path that appears earlier]\label{ex:weighted_route}
143 Consider three packets $\alpha$, $\beta$, and $\gamma$.  Suppose there is a direct edge from $\alpha$ to $\gamma$ of weight three, together with edges
144 \[
145 \alpha\longrightarrow\beta,
146 \qquad
147 \beta\longrightarrow\gamma
148 \]
149 of weight one each.  The two edge route has total weight two, so it contributes to the inverse before the direct edge does.  This is why the truncation rule uses total weight rather than path length. The lower bound in \cref{cor:minimum_path_weight} need not be an equality because several paths of the same weight may cancel.
150 \end{example}
151 
152 \begin{keyidea}
153 Word length counts how many transfers are composed. Weight counts how much filtration gain those transfers guarantee. The sign in the inverse expansion depends on length, while the precision cutoff depends on weight. A short word can therefore disappear at a chosen precision while a longer word still contributes.
154 \end{keyidea}
155 
156 \begin{corollary}[Acyclic transfer graph]\label{cor:acyclic_inverse}
157 If the packet transfer graph is acyclic, then $D^{-1}N$ is nilpotent.  The inverse in \cref{thm:block_path_formula} is a finite sum and does not require completeness of the filtration.
158 \end{corollary}
159 
160 \begin{proof}
161 A finite acyclic directed graph has a bound on path length.  Every sufficiently long product of transfer blocks is therefore zero.  The Neumann series terminates.
162 \end{proof}
163 
164 \begin{corollary}[Stability of inversion at finite precision]\label{cor:inverse_stability}
165 Let $T$ and $\widetilde T$ be invertible elements of $F^0\Bcal$.  If
166 \[
167 T-\widetilde T\in F^L\Bcal,
168 \]
169 then
170 \[
171 T^{-1}-\widetilde T^{-1}\in F^L\Bcal.
172 \]
173 \end{corollary}
174 
175 \begin{proof}
176 Use the resolvent identity at zero in the form
177 \[
178 T^{-1}-\widetilde T^{-1}
179 =
180 T^{-1}(\widetilde T-T)\widetilde T^{-1}.
181 \]
182 Both inverse factors belong to $F^0\Bcal$, so the product lies in $F^L\Bcal$.
183 \end{proof}
184 
185 \begin{corollary}[Exact finite precision truncation]\label{cor:finite_precision}
186 Under the hypotheses of \cref{thm:weighted_inverse}, define
187 \[
188 R_L
189 =
190 \sum_{W(\gamma)<L}(-1)^{|\gamma|}A_\gamma D^{-1}.
191 \]
192 Then
193 \[
194 T^{-1}-R_L\in F^L\Bcal,
195 \]
196 \[
197 TR_L-I\in F^L\Bcal,
198 \qquad
199 R_LT-I\in F^L\Bcal.
200 \]
201 Thus $R_L$ is the exact inverse in $\Bcal/F^L\Bcal$.
202 \end{corollary}
203 
204 \begin{proof}
205 Every omitted word has weight at least $L$, so the difference from the full inverse lies in $F^L\Bcal$.  Multiplication by $T$ or by its inverse preserves membership in $F^L\Bcal$ under the stated filtration assumptions.  The two residual statements follow.
206 \end{proof}
207 
208 \Needspace{4\baselineskip}
209 \begin{example}[A triangular transfer]\label{ex:triangular_transfer}
210 Let $\OO$ be complete with uniformizer $\pi$, and consider
211 \[
212 T=
213 \begin{pmatrix}
214 1&\pi^a\\
215 0&1
216 \end{pmatrix}
217 \]
218 with $a\geq1$.  The only nontrivial transfer has weight $a$, and its square is zero.  Hence
219 \[
220 T^{-1}
221 =
222 \begin{pmatrix}
223 1&-\pi^a\\
224 0&1
225 \end{pmatrix}.
226 \]
227 At precision $L\leq a$, the transfer vanishes and the inverse is the identity modulo $\pi^L$.  At depth $a+1$, the transfer between the two packets first becomes visible.
228 \end{example}
229 
230 \paragraph{Two compatible word conventions.} The path expansion above labels a word in chronological order and writes its operator product in reverse order, so the first edge acts first.  The following finite-word contract uses written multiplication order.  Reversing all word labels identifies the sums over all words. Individual path labels must retain their stated convention.  The two conventions do not change a weight or an inverse.
231 
232 \subsection{Finite quotient and normed-ring realizations}
233 
234 \subsubsection{Normalized edges and written-word convention}
235 
236 Let $\OO$ be a complete discrete valuation ring with uniformizer $\pi$, fraction field $K$, and filtration
237 \[
238 F^m\cB=\pi^m\cB
239 \]
240 on an $\OO$-algebra $\cB$. The finite quotient statements below do not require $\cB$ itself to be complete. Suppose
241 \[
242 T=D+H,
243 \]
244 where $D$ is invertible and the perturbation $H$ raises filtration. The symbol
245 $K$ is reserved for the fraction field.
246 
247 A packet decomposition resolves $H=\sum_{e\in E}H_e$ and assigns a
248 certified filtration gain
249 \[
250 D^{-1}H_e\in F^{w(e)}\cB,
251 \qquad w(e)\in\Z_{>0}.
252 \]
253 Each $e$ is a directed transfer edge. For an ordered transfer word
254 \[
255 \gamma=(e_1,\ldots,e_r),
256 \]
257 define
258 \[
259 W(\gamma)=\sum_{j=1}^rw(e_j),
260 \qquad
261 A_\gamma=A_{e_1}\cdots A_{e_r},
262 \qquad A_e=D^{-1}H_e.
263 \]
264 
265 \begin{figure}[htbp]
266 \centering
267 \includegraphics[width=0.96\textwidth]{04_weighted_transfer_graph.pdf}
268 \caption{A finite packet-transfer graph. Edge weights record filtration gain rather than merely the number of operator compositions.}
269 \label{fig:weighted-graph}
270 \end{figure}
271 
272 \Needspace{8\baselineskip}
273 \begin{theorem}[Certified weighted inverse]\label{thm:weighted-inverse}
274 Let $R$ be a possibly noncommutative ring, let $D^{-1}$ be a supplied
275 two-sided inverse of $D$, and put $A=D^{-1}H$.
276 \begin{enumerate}[label=(\alph*)]
277 \item If $A^r=0$, then $D+H$ has the two-sided inverse
278 \[
279 \boxed{(D+H)^{-1}=\left(\sum_{k=0}^{r-1}(-A)^k\right)D^{-1}.}
280 \]
281 \item If $R$ is a complete normed ring and $\lVert A\rVert<1$, then
282 $\sum_{k\ge0}(-A)^k$ converges and
283 \[
284 \boxed{(D+H)^{-1}=\left(\sum_{k\ge0}(-A)^k\right)D^{-1}.}
285 \]
286 \end{enumerate}
287 \end{theorem}
288 
289 \begin{proof}
290 Factor
291 \[
292 T=D(I+A),
293 \qquad A=D^{-1}H.
294 \]
295 For a finite cutoff $r$, multiplication on either side gives the
296 noncommutative telescoping identity
297 \[
298 (I+A)\sum_{k=0}^{r-1}(-A)^k
299 =
300 \left(\sum_{k=0}^{r-1}(-A)^k\right)(I+A)
301 =1-(-A)^r.
302 \]
303 This proves (a). In (b), the strict norm bound makes the geometric series
304 summable. Continuity of multiplication passes the same identities to the
305 limit. Multiplication by $D^{-1}$ gives the displayed inverse in both orders.
306 \end{proof}
307 
308 \Needspace{4\baselineskip}
309 \begin{corollary}[Finite precision]\label{cor:finite-precision}
310 Let $F^\bullet R$ be a multiplicative decreasing filtration and let
311 $q_L:R\to R_L$ be a ring homomorphism that kills $F^L R$. Suppose
312 \[
313 H=\sum_{e\in E}H_e,
314 \qquad D^{-1}H_e\in F^{w(e)}R,
315 \qquad w(e)\ge1,
316 \]
317 with $E$ finite. Then $q_L(D^{-1}H)^L=0$, the finite sum in
318 \cref{thm:weighted-inverse}(a) is a two-sided inverse after applying $q_L$,
319 and its word expansion may discard every word of weight at least $L$.
320 More explicitly, for a length cutoff $N$, define
321 \[
322 S^{\mathrm{pr}}_{L,N}
323 =
324 \sum_{n=0}^{N-1}(-1)^n
325 \sum_{\substack{\gamma\in E^n\\W(\gamma)<L}}A_\gamma.
326 \]
327 Lean proves directly that $q_L(S^{\mathrm{pr}}_{L,N})$ equals the mapped
328 geometric inverse whenever $q_L(A^N)=0$, and hence is a two-sided inverse of
329 $q_L(I+A)$, where $A=\sum_eA_e=D^{-1}H$. With the supplied two-sided
330 inverse $D^{-1}$ of $D$, this gives the explicit two-sided inverse
331 \[
332 \boxed{q_L\!\left(S^{\mathrm{pr}}_{L,N}D^{-1}\right)}
333 \quad\text{of}\quad q_L(D+H).
334 \]
335 If every edge weight is at least $m$ and $L\le mN$, then the nilpotence
336 condition follows from the filtration data because
337 $m|\gamma|\le W(\gamma)$. For $m>0$, the executable choice
338 $N=\lceil L/m\rceil$ satisfies $L\le mN$. This elementary ceiling inequality
339 is also proved in Lean. The choice $m=1,N=L$ gives the standard cutoff.
340 In the DVR example $q_L:R\to R/\pi^L R$, this reads
341 \[
342 q_L(T)^{-1}
343 =
344 q_L\!\left(\sum_{W(\gamma)<L}
345 (-1)^{|\gamma|}A_\gamma D^{-1}\right).
346 \]
347 \end{corollary}
348 
349 Here $A_\gamma=(D^{-1}H_{e_1})\cdots(D^{-1}H_{e_r})$ in the written
350 order. Multiplicativity places it in $F^{W(\gamma)}R$, so the quotient kills
351 it when $W(\gamma)\ge L$. Positive weights also imply
352 $|\gamma|\le W(\gamma)$, making the retained search finite.
353 
354 \begin{interpretation}
355 Using the standard length cutoff, every discarded word has weight at least the chosen depth and vanishes in the quotient. The retained sum therefore satisfies both inverse identities exactly at that precision. The earlier truncation theorem states the corresponding residual bounds in the complete filtered algebra itself.
356 \end{interpretation}
357 
358 The inherited finite-word contract proves the result in the finite quotients above and in the contraction specialization for complete normed rings. The complete filtered statement has its own separation and inverse-limit completeness hypotheses. Its Lean coverage is recorded separately in the correspondence.
359 
360 \begin{figure}[htbp]
361 \centering
362 \includegraphics[width=0.96\textwidth]{06_filtered_inverse_depth.pdf}
363 \caption{At precision $L$, weighted inversion requires only transfer words whose cumulative weight is below $L$.}
364 \label{fig:inverse-depth}
365 \end{figure}
366 
367 
368 \section{Rational weighted transfer series}\label{sec:path_series}
369 
370 A finite weighted graph records which path terms can occur in the inverse. Collecting paths by total weight turns this support information into a generating function. The finite adjacency matrix makes that function rational.
371 
372 \begin{definition}[Weighted transfer series]\label{def:transfer_series}
373 Let $G$ be a finite directed multigraph.  Give every edge $e$ a positive integer weight $w(e)$ and a scalar multiplicity $m(e)$ in a field $\bbk$.  Define the polynomial adjacency matrix
374 \[
375 A(t)_{ij}
376 =
377 \sum_{e:i\to j}m(e)t^{w(e)}.
378 \]
379 For column vectors $u$ and $v$, define
380 \[
381 Z_{u,v}(t)
382 =
383 \sum_{n\geq0}a_nt^n,
384 \]
385 where
386 \[
387 a_n=\sum_{i,j}\ \sum_{\substack{\gamma:i\leadsto j\\W(\gamma)=n}}
388  u_i v_j\prod_{\nu=1}^{|\gamma|}m(e_\nu).
389 \]
390 Here $\gamma=(e_1,\ldots,e_{|\gamma|})$ is a directed walk. Vertices and edges may repeat, and the empty walk has weight zero and multiplicity one. Thus the endpoint vectors weight the start and end of each walk, rather than only selecting subsets of vertices.
391 \end{definition}
392 
393 \begin{theorem}[Rationality of the transfer series]\label{thm:transfer_rationality}
394 The weighted transfer series satisfies
395 \[
396 Z_{u,v}(t)
397 =
398 u^{\mathsf T}(I-A(t))^{-1}v.
399 \]
400 It is a rational function whose denominator divides
401 \[
402 \det(I-A(t)).
403 \]
404 \end{theorem}
405 
406 \begin{proof}
407 Since every entry of $A(t)$ has zero constant term, the inverse exists in the formal power series ring and
408 \[
409 (I-A(t))^{-1}=\sum_{r\geq0}A(t)^r.
410 \]
411 The $(i,j)$ entry of $A(t)^r$ is the sum of the monomials attached to all paths of length $r$ from $i$ to $j$.  Summing over $r$ records paths of every length.  Multiplication by the endpoint vectors gives the stated series.  The adjugate formula gives
412 \[
413 (I-A(t))^{-1}
414 =
415 \frac{\operatorname{adj}(I-A(t))}{\det(I-A(t))},
416 \]
417 so every entry is rational.
418 \end{proof}
419 
420 \begin{corollary}[Recurrence for path counts]\label{cor:path_recurrence}
421 Write
422 \[
423 Z_{u,v}(t)=\frac{P(t)}{Q(t)},
424 \qquad
425 Q(t)=1+q_1t+\cdots+q_dt^d.
426 \]
427 Use the convention $\deg 0=-\infty$. Then, for every nonnegative integer $n>\deg P$,
428 \[
429 a_n+q_1a_{n-1}+\cdots+q_da_{n-d}=0.
430 \]
431 \end{corollary}
432 
433 \begin{proof}
434 Compare coefficients in the identity
435 \[
436 Q(t)Z_{u,v}(t)=P(t).
437 \]
438 Beyond the degree of $P$, the coefficient on the right is zero.
439 \end{proof}
440 
441 In the recurrence, set $a_k=0$ when $k<0$. This is the coefficient convention for the formal power series $Z_{u,v}(t)$ and makes the first recurrence equations meaningful even when $n<d$.
442 
443 \begin{corollary}[Several independent weights]\label{cor:multigraded_series}
444 Suppose every edge has a weight vector
445 \[
446 w(e)=(w_1(e),\ldots,w_r(e))\in\mathbb N^r\setminus\{0\}.
447 \]
448 Replace $t^{w(e)}$ by
449 \[
450 t_1^{w_1(e)}\cdots t_r^{w_r(e)}.
451 \]
452 The resulting multigraded transfer series is rational in $t_1,\ldots,t_r$.
453 \end{corollary}
454 
455 \begin{proof}
456 The same matrix inverse proof works over the formal power series ring in several variables.  The adjugate formula gives rationality.
457 \end{proof}
458 
459 The multigraded form is useful when dyadic depth, odd depth, and another filtration are tracked separately rather than collapsed into one number.
460 
461 \begin{example}[A transfer series with one loop]\label{ex:simple_transfer_series}
462 Take vertices $0$, $1$, and $2$.  Give the edge $0\to1$ weight one, the loop $1\to1$ weight two, and the edge $1\to2$ weight one.  Every path from $0$ to $2$ uses the first and last edges and may traverse the loop any number of times.  Hence
463 \[
464 Z_{0,2}(t)
465 =
466 t^2(1+t^2+t^4+\cdots)
467 =
468 \frac{t^2}{1-t^2}.
469 \]
470 There is one path at every positive even weight and no path at an odd weight.  The denominator records the increase of two units produced by the loop.
471 \end{example}
472 
473 \subsection{Automatic finite-graph construction}
474 
475 Let $G$ be a finite directed graph with positive integer edge weights. Define the polynomial adjacency matrix
476 \[
477 A(t)_{ij}
478 =
479 \sum_{e:i\to j}t^{w(e)},
480 \]
481 where parallel edges are distinct elements of the finite edge type and are
482 therefore counted with their full multiplicity.
483 
484 For fixed start and target vertices $s,t$, define
485 \[
486 Z_{s,t}(t)
487 =
488 \sum_{n\ge0}a_n(s,t)t^n,
489 \]
490 where $a_n(s,t)$ counts directed walks from $s$ to $t$ with total weight $n$.
491 Vertices and edges may repeat. Thus ``path zeta'' is retained as the name of
492 the series and Lean API, but the walks are not required to visit each vertex only once.
493 
494 \begin{theorem}[Automatic finite-graph transfer-zeta rationality]\label{thm:transfer-zeta}
495 Assume the vertex and edge sets are finite and every edge has positive integer
496 weight. For every $n$, exact enumeration of edge tuples of lengths at most
497 $n$, followed by endpoint and total-weight filtering, returns $a_n(s,t)$.
498 These coefficients obey the recurrence obtained by removing the first edge
499 \[
500 a_n(s,t)
501 =
502 \mathbf 1_{s=t,\,n=0}
503 +\sum_{\substack{e:\,\operatorname{source}(e)=s\\w(e)\le n}}
504 a_{n-w(e)}(\operatorname{target}(e),t).
505 \]
506 Let
507 \[
508 T(t)=I-A(t),\qquad
509 Q(t)=\det T(t),\qquad
510 P_{s,t}(t)=\operatorname{adj}(T(t))_{s,t}.
511 \]
512 Then $Q(0)=1$, hence $Q\ne0$ and $Q$ is a unit in $\Z[[t]]$, and the
513 independently enumerated walk series satisfies
514 \[
515 \boxed{
516 Z_{s,t}(t)=Q(t)^{-1}P_{s,t}(t),
517 \qquad
518 Q(t)Z_{s,t}(t)=P_{s,t}(t)
519 }
520 \quad\text{in }\Z[[t]].
521 \]
522 \end{theorem}
523 
524 \begin{proof}
525 Every edge has weight at least one, so a word of weight $n$ has length at
526 most $n$. The enumerator therefore searches a finite set containing every
527 contributing walk, and its filters are exactly the defining predicates for
528 $a_n$. Removing the first edge gives the displayed disjoint decomposition
529 into the empty diagonal walk and the first-edge tails. In matrix form this is
530 \[
531 Z=I+AZ,
532 \qquad (I-A)Z=I.
533 \]
534 Positive weights give $A(0)=0$, so $T(0)=I$ and
535 $Q(0)=\det(I)=1$. The two adjugate identities
536 \[
537 T\operatorname{adj}(T)=Q I,
538 \qquad
539 \operatorname{adj}(T)T=Q I
540 \]
541 remain valid after inclusion into $\Z[[t]]$. Multiplying the adjugate by the
542 formal-series inverse of $Q$ constructs a two-sided inverse of $T$.
543 Uniqueness of the inverse identifies that construction with the independently
544 enumerated matrix $Z$, yielding the entrywise formulas.
545 \end{proof}
546 
547 This is the finite transfer-matrix method of \cite{Stanley2012}, but here its
548 determinant, adjugate, normalization, recurrence from the first edge, and identification
549 with the enumerated series are all formalized. The older API accepting an
550 independently supplied normalized coefficient identity $QZ=P$ is retained for
551 external certificates. It is no longer needed to obtain rationality for the
552 finite graph defined above. The Python companion performs an exact symbolic
553 construction as an independent executable check.
554 
555 \begin{corollary}[Linear recurrence]\label{cor:zeta-recurrence}
556 With the canonical polynomials from \cref{thm:transfer-zeta}, write
557 \[
558 Q(t)=\sum_kq_kt^k,
559 \qquad
560 Z_{s,t}(t)=\sum_{n\ge0}a_n(s,t)t^n.
561 \]
562 Then the walk counts satisfy the recurrence with constant coefficients determined by
563 $Q$ after the finite initial range contributed by $P_{s,t}$, with $\deg 0=-\infty$:
564 \[
565 \boxed{
566 \sum_{k=0}^{n}q_k a_{n-k}(s,t)=0
567 \qquad\bigl(n>\deg P_{s,t}\bigr).
568 }
569 \]
570 \end{corollary}
571 
572 \begin{figure}[htbp]
573 \centering
574 \includegraphics[width=0.96\textwidth]{05_path_zeta_coefficients.pdf}
575 \caption{The walk counts for one weighted graph. The exact generating function is rational, so these counts satisfy a finite linear recurrence.}
576 \label{fig:zeta-counts}
577 \end{figure}
578 
579 \begin{example}[A computed transfer zeta]
580 For the graph used in the numerical companion, the walk series from packet $0$ to packet $2$ is
581 \[
582 Z_{0,2}(t)
583 =
584 \frac{t^3}{1-t^2-t^3-2t^4+t^5+t^6+t^7-t^9}.
585 \]
586 The first nonzero coefficients are
587 \[
588 1,1,1,3,1,5,4,10,7,19,17,37,\ldots
589 \]
590 at their corresponding weights. Direct enumeration through weight $30$ agrees coefficient by coefficient with the rational expansion.
591 \end{example}
592 
593 

Back to source controls

Back to Realization Calculus