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{Packet systems and refinement towers}\label{sec:refinement}
2 
3 Packet coordinates split a module into pieces that can be recovered separately and then added back together. The construction uses idempotents and does not need an inner product.
4 
5 \begin{definition}[Packet system]\label{def:packet_system}
6 Let $X$ be a module over a unital ring.  A finite packet system on $X$ is a family
7 \[
8 \Pcal=(P_\alpha)_{\alpha\in I}
9 \subseteq\End(X)
10 \]
11 of nonzero idempotents such that
12 \[
13 P_\alpha P_\beta=0
14 \quad\text{when }\alpha\ne\beta,
15 \qquad
16 \sum_{\alpha\in I}P_\alpha=I_X.
17 \]
18 Write
19 \[
20 X_\alpha=P_\alpha X,
21 \qquad
22 X^{\Pcal}=\bigoplus_{\alpha\in I}X_\alpha.
23 \]
24 The analysis and synthesis maps are
25 \[
26 \Acal_{\Pcal}x=(P_\alpha x)_\alpha,
27 \qquad
28 \Scal_{\Pcal}(x_\alpha)_\alpha=\sum_\alpha x_\alpha.
29 \]
30 They are inverse isomorphisms.
31 \end{definition}
32 
33 \begin{definition}[Refinement]\label{def:refinement}\label{def:refinement-map}
34 Let $\Pcal=(P_\alpha)_{\alpha\in I}$ and $\Qcal=(Q_\beta)_{\beta\in J}$ be packet systems on the same module.  We say that $\Qcal$ refines $\Pcal$ when there is a surjection
35 \[
36 \rho:J\longrightarrow I
37 \]
38 such that
39 \[
40 P_\alpha=\sum_{\rho(\beta)=\alpha}Q_\beta
41 \]
42 for every $\alpha\in I$.  The index $\beta$ is then called a child of $\rho(\beta)$.
43 \end{definition}
44 
45 \begin{theorem}[Children, parents, and transitivity]\label{thm:children_transitivity}\label{thm:nested-refinement}
46 Suppose that $\Qcal$ refines $\Pcal$ through $\rho$.  Then
47 \[
48 P_\alpha Q_\beta
49 =
50 Q_\beta P_\alpha
51 =
52 \begin{cases}
53 Q_\beta & \rho(\beta)=\alpha,\\
54 0 & \rho(\beta)\ne\alpha.
55 \end{cases}
56 \]
57 Hence $Q_\beta X\subseteq P_{\rho(\beta)}X$.  If a third packet system $\Rcal$ refines $\Qcal$, then $\Rcal$ refines $\Pcal$ through the composite parent map.
58 \end{theorem}
59 
60 \begin{proof}
61 Multiply the identity
62 \[
63 P_\alpha=\sum_{\rho(\gamma)=\alpha}Q_\gamma
64 \]
65 by $Q_\beta$ on either side.  Pairwise annihilation in the fine family leaves $Q_\beta$ when $\rho(\beta)=\alpha$ and leaves zero otherwise.  For transitivity, substitute the child expansion of each $Q_\beta$ into the expansion of $P_\alpha$ and group the resulting terms by the composite parent.
66 \end{proof}
67 
68 A refinement tower is a sequence $(\Pcal_\ell)_{\ell\geq0}$ with parent maps
69 \[
70 \rho_{m,\ell}:I_m\longrightarrow I_\ell
71 \qquad(m\geq\ell)
72 \]
73 such that $\Pcal_m$ refines $\Pcal_\ell$ through $\rho_{m,\ell}$ for every $m\geq\ell$, and
74 \[
75 \rho_{\ell,\ell}=\id_{I_\ell},
76 \qquad
77 \rho_{n,\ell}=\rho_{m,\ell}\circ\rho_{n,m}
78 \qquad(n\geq m\geq\ell).
79 \]
80 Thus every parent map witnesses the stated refinement and the maps compose coherently. The next result shows that the coordinate changes form a coherent system.
81 
82 \begin{definition}[Coordinate change across levels]\label{def:coordinate_change}\label{def:coordinate-refinement}
83 For two packet systems $\Pcal$ and $\Qcal$ on $X$, define
84 \[
85 J_{\Qcal\leftarrow\Pcal}
86 =
87 \Acal_{\Qcal}\Scal_{\Pcal}:X^{\Pcal}\longrightarrow X^{\Qcal}
88 \]
89 and
90 \[
91 C_{\Pcal\leftarrow\Qcal}
92 =
93 \Acal_{\Pcal}\Scal_{\Qcal}:X^{\Qcal}\longrightarrow X^{\Pcal}.
94 \]
95 When $\Qcal$ refines $\Pcal$, the first map resolves each coarse coordinate into its children and the second adds the children back to their parent.
96 \end{definition}
97 
98 \begin{keyidea}
99 A coarse coordinate retains a whole vector in its coarse packet. Adding its children keeps the whole vector inside that packet. Fine analysis recovers each child by applying its projector. This explains why the two coordinate maps can be inverse even when the fine system has more packet labels.
100 \end{keyidea}
101 
102 \begin{theorem}[Exact coordinate change and coherence]\label{thm:coordinate_coherence}\label{prop:perfect-reconstruction}
103 For any two packet systems on $X$,
104 \[
105 C_{\Pcal\leftarrow\Qcal}J_{\Qcal\leftarrow\Pcal}=I_{X^{\Pcal}},
106 \qquad
107 J_{\Qcal\leftarrow\Pcal}C_{\Pcal\leftarrow\Qcal}=I_{X^{\Qcal}}.
108 \]
109 For three packet systems $\Pcal$, $\Qcal$, and $\Rcal$ on $X$,
110 \[
111 J_{\Rcal\leftarrow\Qcal}J_{\Qcal\leftarrow\Pcal}
112 =
113 J_{\Rcal\leftarrow\Pcal},
114 \]
115 \[
116 C_{\Pcal\leftarrow\Qcal}C_{\Qcal\leftarrow\Rcal}
117 =
118 C_{\Pcal\leftarrow\Rcal}.
119 \]
120 If $\Qcal$ refines $\Pcal$ through $\rho$, then
121 \[
122 \bigl(J_{\Qcal\leftarrow\Pcal}x\bigr)_\beta
123 =
124 Q_\beta x_{\rho(\beta)},
125 \qquad
126 \bigl(C_{\Pcal\leftarrow\Qcal}y\bigr)_\alpha
127 =
128 \sum_{\rho(\beta)=\alpha}y_\beta.
129 \]
130 \end{theorem}
131 
132 \begin{proof}
133 The packet analysis and synthesis maps are inverse.  Therefore
134 \[
135 C_{\Pcal\leftarrow\Qcal}J_{\Qcal\leftarrow\Pcal}
136 =
137 \Acal_{\Pcal}\Scal_{\Qcal}\Acal_{\Qcal}\Scal_{\Pcal}
138 =
139 \Acal_{\Pcal}\Scal_{\Pcal}
140 =
141 I.
142 \]
143 The other inverse identity is the same calculation with the two systems exchanged.  The coherence identities follow by inserting
144 \[
145 \Scal_{\Qcal}\Acal_{\Qcal}=I_X.
146 \]
147 Now assume that $\Qcal$ refines $\Pcal$.  If $x=(x_\alpha)_\alpha$ with $x_\alpha\in P_\alpha X$, then
148 \[
149 Q_\beta\sum_\alpha x_\alpha
150 =
151 Q_\beta x_{\rho(\beta)}
152 \]
153 by \cref{thm:children_transitivity}.  The formula for $C$ follows by synthesis followed by projection onto the parent packet.
154 \end{proof}
155 
156 \begin{remark}[Refinement and reduction]\label{rem:refinement_reduction}
157 The maps in \cref{thm:coordinate_coherence} are isomorphisms because both coordinate spaces represent all of $X$.  They do not reduce dimension and they do not discard packets.  Approximation begins only after one chooses a truncation or compression rule.
158 \end{remark}
159 
160 \begin{corollary}[Orthogonal Hilbert packets]\label{cor:orthogonal_isometry}
161 If $X$ is a real or complex Hilbert space and every packet system in the tower consists of orthogonal projections, equip each finite packet direct sum with the Hilbert inner product $\langle(x_\alpha),(y_\alpha)\rangle=\sum_\alpha\langle x_\alpha,y_\alpha\rangle$. Then analysis and synthesis are unitary. Every coordinate change in \cref{thm:coordinate_coherence} is unitary.
162 \end{corollary}
163 
164 \begin{proof}
165 For an orthogonal packet system,
166 \[
167 \|x\|^2=\sum_\alpha\|P_\alpha x\|^2.
168 \]
169 Thus analysis is an isometry onto the full packet direct sum.  Synthesis is its inverse.  A coordinate change is a composition of two unitary maps.
170 \end{proof}
171 
172 Every coarse packet is also uniquely reconstructed from its fine children.  If vectors $x_\beta\in Q_\beta X$ sum to a coarse packet $x$, applying $Q_\gamma$ recovers $x_\gamma=Q_\gamma x$.  This is the uniqueness clause of the canonical nested-refinement statement.
173 
174 \subsection{Typed coordinate naturality}
175 These coordinate changes are coherent through every finite tower. If three
176 complete packet systems are denoted by $a,b,c$, then
177 \[
178 J_{c,b}J_{b,a}=J_{c,a},
179 \qquad J_{a,a}=I,
180 \qquad J_{b,a}^{-1}=J_{a,b}.
181 \]
182 These laws hold for arbitrary exact packet systems representing the same
183 ambient module. The parent maps supply the component formulas linking
184 children to their parents. Coordinate coherence itself does not require them.
185 
186 The same coherence applies to operators. Let $P_a,P_b$ be packet systems on $X$, let $Q_a,Q_b$ be packet
187 systems on $Y$, where $X$ and $Y$ are modules over the same scalar ring, and let $T:X\to Y$ be a linear map over that ring. Its exact coordinate
188 representation
189 \[
190 \widehat T_{Q,P}=\cA_QT\cS_P
191 \]
192 preserves identities and typed composition, and the naturality square is
193 \[
194 \boxed{
195 J^Y_{Q_b,Q_a}\,\widehat T_{Q_a,P_a}
196 =
197 \widehat T_{Q_b,P_b}\,J^X_{P_b,P_a}.
198 }
199 \]
200 The identity, cocycle, composition, inverse, and naturality laws are all proved
201 in Lean. The separate refinement hypotheses supply the local component
202 formulas linking each child to its parent.
203 
204 \begin{interpretation}
205 These identities concern complete coordinates of the same module. A quotient is a different operation: it identifies vectors that differ by an element of a chosen submodule. Later, finite precision will be expressed by a quotient that removes terms beyond the chosen filtration depth. This distinction explains why refinement is exactly reversible while precision truncation has a prescribed residual.
206 \end{interpretation}
207 
208 
209 \begin{figure}[htbp]
210 \centering
211 \includegraphics[width=0.96\textwidth]{01_nested_dyadic_refinement.pdf}
212 \caption{A nested residue hierarchy. Each residue modulo $2$ is the union of two residues modulo $4$, and each residue modulo $4$ is the union of two residues modulo $8$.}
213 \label{fig:refinement-tree}
214 \end{figure}
215 \subsection{Operator blocks across refinement}
216 
217 For $T\in\End(X)$ and a packet system $\Pcal$, write
218 \[
219 T^{\Pcal}_{\beta\alpha}=P_\beta T P_\alpha.
220 \]
221 
222 \begin{theorem}[Refinement of operator blocks]\label{thm:block_refinement}\label{thm:transfer-block-refinement}
223 Suppose that $\Qcal$ refines $\Pcal$ through $\rho$.  Then
224 \[
225 T^{\Pcal}_{ba}
226 =
227 \sum_{\substack{\rho(\beta)=b\\\rho(\alpha)=a}}
228 T^{\Qcal}_{\beta\alpha}.
229 \]
230 The matrix of $T$ in fine coordinates is related to the matrix in coarse coordinates by
231 \[
232 [T]_{\Pcal}
233 =
234 C_{\Pcal\leftarrow\Qcal}[T]_{\Qcal}J_{\Qcal\leftarrow\Pcal}.
235 \]
236 \end{theorem}
237 
238 \begin{proof}
239 Expand the two coarse projectors into their children:
240 \[
241 P_bTP_a
242 =
243 \left(\sum_{\rho(\beta)=b}Q_\beta\right)
244 T
245 \left(\sum_{\rho(\alpha)=a}Q_\alpha\right).
246 \]
247 Distributing the finite sums gives the first identity.  For the coordinate identity, use
248 \[
249 [T]_{\Pcal}=\Acal_{\Pcal}T\Scal_{\Pcal}
250 \]
251 and insert
252 \[
253 I_X=\Scal_{\Qcal}\Acal_{\Qcal}.
254 \]
255 \end{proof}
256 
257 \begin{corollary}[Support under refinement]\label{cor:block_support_refinement}
258 Under the hypotheses of \cref{thm:block_refinement}, a coarse block $T^{\Pcal}_{ba}$ is zero if and only if every fine descendant block
259 \[
260 T^{\Qcal}_{\beta\alpha}
261 \qquad
262 \bigl(\rho(\beta)=b,\ \rho(\alpha)=a\bigr)
263 \]
264 is zero.
265 \end{corollary}
266 
267 \begin{proof}
268 If every fine block is zero, the coarse block is zero by \cref{thm:block_refinement}.  Conversely, suppose $P_bTP_a=0$.  Multiply on the left by $Q_\beta$ and on the right by $Q_\alpha$.  The child identities in \cref{thm:children_transitivity} give
269 \[
270 Q_\beta TQ_\alpha=0.
271 \]
272 \end{proof}
273 
274 Thus refinement cannot hide an active transfer inside a zero coarse block.  It can only reveal where the active transfer sits among the descendants.
275 
276 \begin{figure}[htbp]
277 \centering
278 \includegraphics[width=0.96\textwidth]{03_refinement_incidence.pdf}
279 \caption{The incidence matrix $M_{r,s}=1$ when the fine residue $s$ belongs to the coarse residue $r$. Its rows implement exact aggregation from fine packets to coarse packets.}
280 \label{fig:incidence}
281 \end{figure}
282 \subsection{Common refinements}
283 
284 Two packet systems need not be comparable.  When their idempotents commute, their products give a common refinement.
285 
286 \begin{theorem}[Common refinement of commuting packet systems]\label{thm:common_refinement}
287 Let $\Pcal=(P_\alpha)_{\alpha\in I}$ and $\Qcal=(Q_\beta)_{\beta\in J}$ be packet systems on $X$.  Assume
288 \[
289 P_\alpha Q_\beta=Q_\beta P_\alpha
290 \]
291 for all $\alpha$ and $\beta$.  Remove the zero operators from the family
292 \[
293 R_{\alpha\beta}=P_\alpha Q_\beta.
294 \]
295 The remaining operators form a packet system that refines both $\Pcal$ and $\Qcal$.  The same statement holds for any finite collection of pairwise commuting packet systems.
296 \end{theorem}
297 
298 \begin{proof}
299 Commutativity gives
300 \[
301 R_{\alpha\beta}^2=P_\alpha^2Q_\beta^2=R_{\alpha\beta}.
302 \]
303 If $(\alpha,\beta)\ne(\alpha',\beta')$, then either $P_\alpha P_{\alpha'}=0$ or $Q_\beta Q_{\beta'}=0$, so the corresponding products annihilate one another.  Finally,
304 \[
305 \sum_{\alpha,\beta}R_{\alpha\beta}
306 =
307 \left(\sum_\alpha P_\alpha\right)
308 \left(\sum_\beta Q_\beta\right)
309 =I_X.
310 \]
311 For a fixed $\alpha$,
312 \[
313 P_\alpha
314 =P_\alpha\sum_\beta Q_\beta
315 =
316 \sum_\beta R_{\alpha\beta},
317 \]
318 and the same argument works for a fixed $\beta$. Since each $P_\alpha$ and $Q_\beta$ is nonzero, these identities ensure that every parent has a nonzero product child. The two parent maps on the supported product family are therefore surjective. Iteration proves the finite family statement. For the empty collection, use the supported identity family: $(I_X)$ when $X\ne0$ and the empty family when $X=0$.
319 \end{proof}
320 
321 \begin{proposition}[Coarsest common refinement]\label{prop:coarsest_common_refinement}
322 Under the hypotheses of \cref{thm:common_refinement}, let $\Rcal$ be a packet system that refines both $\Pcal$ and $\Qcal$.  Then $\Rcal$ refines the nonzero product family $(P_\alpha Q_\beta)$.  Hence that product family is the coarsest packet system that refines both $\Pcal$ and $\Qcal$.
323 \end{proposition}
324 
325 \begin{proof}
326 Let $R_\gamma$ be a packet in $\Rcal$.  Because $\Rcal$ refines $\Pcal$, there is a unique $\alpha$ with
327 \[
328 P_\alpha R_\gamma=R_\gamma.
329 \]
330 Likewise there is a unique $\beta$ with
331 \[
332 Q_\beta R_\gamma=R_\gamma.
333 \]
334 Therefore
335 \[
336 P_\alpha Q_\beta R_\gamma=R_\gamma.
337 \]
338 Every packet of $\Rcal$ lies in one product packet. Multiplying $\sum_\gamma R_\gamma=I_X$ by $P_\alpha Q_\beta$ and using the parent identities gives
339 \[
340 P_\alpha Q_\beta
341 =\sum_{\substack{\gamma:\ P_\alpha R_\gamma=R_\gamma\\Q_\beta R_\gamma=R_\gamma}}R_\gamma.
342 \]
343 Thus the packets with the same pair of parents reconstruct the product packet. If that product packet is nonzero, the sum has a child, so the parent map onto the supported product family is surjective.
344 \end{proof}
345 
346 \begin{example}[A two level split]\label{ex:two_level_split}
347 Let
348 \[
349 X=X_{00}\oplus X_{01}\oplus X_{10}\oplus X_{11}.
350 \]
351 Assume that all four summands are nonzero. The four coordinate projections form a fine packet system.  The two sums
352 \[
353 P_0=Q_{00}+Q_{01},
354 \qquad
355 P_1=Q_{10}+Q_{11}
356 \]
357 form a coarse packet system.  If $x=(x_{00},x_{01},x_{10},x_{11})$, the coarse coordinates are
358 \[
359 (x_{00}+x_{01},x_{10}+x_{11})
360 \]
361 when the sums are interpreted inside the two coarse direct summands.  Fine analysis recovers the four entries exactly.  Nothing has been approximated.
362 \end{example}
363 
364 \section{Residue coordinates and coprime factorization}\label{sec:residue}
365 
366 Residue packets sort a formal series by the congruence classes of its exponents. This construction works over every coefficient ring. The character formula describes the same selectors through an operator average and needs stronger hypotheses.
367 
368 \begin{definition}[Residue selector]\label{def:residue_selector}
369 Let $R$ be a commutative ring and let
370 \[
371 F(z)=\sum_{n\geq0}a_nz^n\in R[[z]].
372 \]
373 For $N\geq1$ and $0\leq j<N$, define
374 \[
375 (P_{N,j}F)(z)
376 =
377 \sum_{n\equiv j\pmod N}a_nz^n.
378 \]
379 \end{definition}
380 
381 \begin{proposition}[Residue packet algebra]\label{prop:residue_algebra}\label{prop:residue-algebra}
382 For every commutative ring $R$, the operators $(P_{N,j})_{0\leq j<N}$ satisfy the identities below.  If $R$ is nonzero, they form a packet system on $R[[z]]$:
383 \[
384 P_{N,i}P_{N,j}=\delta_{ij}P_{N,j},
385 \qquad
386 \sum_{j=0}^{N-1}P_{N,j}=I.
387 \]
388 \end{proposition}
389 
390 \begin{proof}
391 Every nonnegative integer belongs to one residue class modulo $N$.  A coefficient survives both $P_{N,i}$ and $P_{N,j}$ exactly when the two labels are equal to its residue.  Summing all selectors preserves every coefficient once.
392 \end{proof}
393 
394 \subsection{Finite orthogonality certificates}
395 
396 The coefficient-mask definition of $P_{N,j}$ also makes sense over a commutative semiring: it only retains or sets coefficients to zero. We use that same definition in the following semiring statement.
397 
398 Let $U$ act on coefficient sequences by
399 \[
400 (UF)(z)=F(\omega z).
401 \]
402 If $\omega^N=1$, then $U^N=I$.
403 
404 \begin{theorem}[Root-of-unity realization]\label{thm:root-of-unity}
405 Let $R$ be a commutative semiring, let $N>0$, and suppose
406 $\omega,\omega^\vee,\eta\in R$ satisfy $\omega^N=1$ and the finite
407 $N\times N$ Fourier orthogonality table
408 \[
409 \eta\sum_{k=0}^{N-1}(\omega^\vee)^{jk}\omega^{rk}
410 =
411 \begin{cases}
412 1,&r=j,\\
413 0,&r\ne j,
414 \end{cases}
415 \qquad 0\le j,r<N.
416 \]
417 Then
418 \[
419 \boxed{
420 P_{N,j}
421 =
422 \eta\sum_{k=0}^{N-1}(\omega^\vee)^{jk}U^k.
423 }
424 \]
425 In particular, if $R$ is a field, $N>0$, and $\omega$ is a primitive
426 $N$th root of unity, the certificate holds with
427 $\omega^\vee=\omega^{-1}$ and $\eta=N^{-1}$.
428 \end{theorem}
429 
430 \begin{proof}
431 On the monomial $z^n$, the right-hand side acts by
432 \[
433 \eta\sum_{k=0}^{N-1}(\omega^\vee)^{jk}\omega^{nk}.
434 \]
435 The identity $\omega^N=1$ reduces this expression to the table entry indexed
436 by $r=n\bmod N$. The finite certificate therefore gives exactly the
437 coefficient mask defining $P_{N,j}$.
438 Over a field, the primitive-root geometric sum supplies the certificate.
439 \end{proof}
440 
441 The field or orthogonality condition is essential. A primitive element of
442 order $N$ in a ring with zero divisors does not by itself force the geometric
443 sums away from the diagonal to vanish. For example, in $\mathbb F_3\times\mathbb F_3$ the
444 element $(-1,1)$ has order two, but the second component of its nontrivial
445 character sum is nonzero. The coefficient selector uses no division and remains valid
446 without any Fourier certificate. This distinction becomes decisive at the
447 dyadic prime.
448 
449 
450 \subsection{The field specialization}
451 \begin{theorem}[Character realization]\label{thm:character_realization}
452 Let $\bbk$ be a field, assume that $N$ is nonzero in $\bbk$, and suppose that $\bbk$ contains a primitive $N$th root of unity $\omega$.  Define
453 \[
454 (UF)(z)=F(\omega z).
455 \]
456 Then
457 \[
458 P_{N,j}
459 =
460 \frac1N\sum_{k=0}^{N-1}\omega^{-jk}U^k.
461 \]
462 \end{theorem}
463 
464 \begin{proof}
465 On $z^n$, the right side acts by the scalar
466 \[
467 \frac1N\sum_{k=0}^{N-1}\omega^{k(n-j)}.
468 \]
469 This is one when $n\equiv j\pmod N$ and zero otherwise by the geometric sum identity in the field $\bbk$.
470 \end{proof}
471 
472 \begin{remark}[Two distinct constructions]\label{rem:selector_character}
473 The coefficient selector of \cref{def:residue_selector} uses no division.  The character formula in \cref{thm:character_realization} divides by $N$.  At a prime that divides $N$, the coefficient selector may remain integral even when the character average does not.
474 \end{remark}
475 
476 \begin{theorem}[Nested residue refinement]\label{thm:residue_refinement}\label{thm:polyphase-refinement}
477 Let $N,M$ be positive integers with $N$ dividing $M$, and let $0\leq j<N$.  Then
478 \[
479 P_{N,j}
480 =
481 \sum_{\substack{0\leq s<M\\s\equiv j\pmod N}}P_{M,s}.
482 \]
483 When $R$ is nonzero, the packet system modulo $M$ refines the packet system modulo $N$.
484 \end{theorem}
485 
486 \begin{proof}
487 An exponent $n$ satisfies $n\equiv j\pmod N$ exactly when its unique residue $s$ modulo $M$ satisfies $s\equiv j\pmod N$.
488 \end{proof}
489 
490 \begin{example}[The shift graph of residue packets]\label{ex:residue_shift}
491 Assume that $R$ is nonzero and $N>0$. Multiplication by $z$ sends the residue packet $P_{N,j}R[[z]]$ into $P_{N,j+1}R[[z]]$, where the index is read modulo $N$.  Its packet graph is the directed cycle
492 \[
493 0\longrightarrow1\longrightarrow\cdots\longrightarrow N-1\longrightarrow0.
494 \]
495 Multiplication by a polynomial supported on a set of residues gives the corresponding finite set of phase shifts.  This is the simplest transfer graph behind a polyphase representation.
496 \end{example}
497 
498 \begin{theorem}[Coprime factorization]\label{thm:crt_factorization}
499 Let $A$ and $B$ be coprime positive integers.  For each $j$ modulo $AB$, write
500 \[
501 j_A=j\pmod A,
502 \qquad
503 j_B=j\pmod B.
504 \]
505 Then
506 \[
507 P_{AB,j}=P_{A,j_A}P_{B,j_B}.
508 \]
509 Every pair $(j_A,j_B)$ occurs for one residue $j$ modulo $AB$.
510 \end{theorem}
511 
512 \begin{proof}
513 A coefficient survives the product on the right exactly when its exponent satisfies both congruences.  The Chinese remainder theorem gives one residue class modulo $AB$ with those two coordinates.  The needed form of the theorem is standard and may be found in \cite{Lang2002}.
514 \end{proof}
515 
516 \begin{corollary}[Dyadic and odd coordinates]\label{cor:dyadic_odd_coordinates}\label{thm:dyadic-odd}
517 Write $N=2^aM$ with $M$ odd.  Every residue packet modulo $N$ is the product of one packet modulo $2^a$ and one packet modulo $M$.
518 \end{corollary}
519 
520 \begin{proof}
521 Apply \cref{thm:crt_factorization} to the coprime moduli $2^a$ and $M$.
522 \end{proof}
523 
524 \begin{example}[Residues modulo twelve]\label{ex:mod_twelve}
525 The pair
526 \[
527 (j\pmod4,j\pmod3)=(3,1)
528 \]
529 corresponds to $j=7$ modulo $12$.  Hence
530 \[
531 P_{12,7}=P_{4,3}P_{3,1}.
532 \]
533 This factorization concerns addresses.  It does not say that the two factors have the same integral spectral behavior.
534 \end{example}
535 
536 \begin{figure}[htbp]
537 \centering
538 \includegraphics[width=0.96\textwidth]{02_crt_dyadic_odd_grid.pdf}
539 \caption{A composite residue packet is addressed by its dyadic and odd coordinates. The displayed mod-$24$ system is the product of mod $8$ and mod $3$.}
540 \label{fig:crt-grid}
541 \end{figure}

Back to source controls

Back to Realization Calculus