Exact ReLU realization of tensor-product refinement iterates Tsogtgerel Gantumur
arXiv:2605.03917v1 [math.CA] 5 May 2026
McGill University, Montréal, QC, Canada National University of Mongolia, Ulaanbaatar, Mongolia Mongolian Academy of Sciences, Institute of Mathematics and Digital Technology [email protected]
May 6, 2026
Abstract We study scalar dyadic refinement operators on R2 of the form X (V f )(x, y) = cj,k f (2x − j, 2y − k), (j,k)∈Z2
where only finitely many mask coefficients cj,k are nonzero. Under a fixed support-window hypothesis, we prove that for every compactly supported continuous piecewise linear seed g : R2 → R, the iterates V n g admit exact ReLU realizations of fixed width and depth O(n). The proof gives a first genuinely two-dimensional extension of the exact realization theory for refinement cascades. Using the one-dimensional exact loop-controller framework, it transports the tensor-product residual dynamics exactly on the product of two polygonal loops and reduces the remaining seam ambiguity to a final readout and selector step. The matrix cascade is then handled by a fixed-depth recursive block, and general compactly supported CPwL seeds are reduced to a finite decomposition together with exact clamped gluing on the support window. This identifies the tensor-product dyadic case as the natural first multivariate instance of the loop-controller method for refinement iterates.
Contents 1 Introduction 1.1 Background and motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Main theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Proof idea and scope . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4 Organization of the paper . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2 2 3 4 4
2 Preliminaries and notation 2.1 Network classes and CPwL functions . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Dyadic digits and tensor-product residuals . . . . . . . . . . . . . . . . . . . . . . . . 2.3 The refinement operator and the support window . . . . . . . . . . . . . . . . . . . . 2.4 Vectorization on unit squares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5 Block transition matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.6 One-step cascade identity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.7 The product gadget . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.8 Special atoms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4 4 5 6 6 6 7 8 8
1
3 Exact torus controller and scalar readout 8 3.1 A polygonal loop for the one-dimensional residual . . . . . . . . . . . . . . . . . . . . 9 3.2 The torus controller . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.3 One-dimensional terminal readouts . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.4 Four-branch scalar readout for special atoms . . . . . . . . . . . . . . . . . . . . . . 11 4 Recursive realization for special atoms 4.1 Binary loop selectors and terminal boundary localization . . . . . . . . . . . . . . . . 4.2 Modified matrix selectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Recursive realization on the unit square . . . . . . . . . . . . . . . . . . . . . . . . . 4.4 Clamped gluing and the special-atom theorem . . . . . . . . . . . . . . . . . . . . . .
13 13 15 16 17
5 General compactly supported seeds 5.1 Finite special-atom decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Translation covariance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Proof of the main theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19 19 20 20
6 Conclusions and outlook
21
1
Introduction
1.1
Background and motivation
Neural-network approximation theory [1] seeks structural explanations for why deep networks can efficiently represent highly oscillatory, highly recursive, or highly self-similar functions. A particularly clean result in this direction is the scalar binary theorem on refinable functions [2]: if (V g)(x) =
N X
cj g(2x − j),
j=0
and if g is compactly supported and continuous piecewise linear, then the iterates V n g admit exact ReLU realizations of fixed width and depth growing linearly in n. In that setting, the proof is organized around three ingredients: a cascade identity, a controlled treatment of the residual dynamics, and a recursive fixed-depth update block for the finite-dimensional cascade state. The result is one of the clearest examples in neural-network realization theory in which linear growth of depth is explained by an intrinsic recursive analytic mechanism rather than by a generic approximation argument. The purpose of the present paper is to develop the first genuinely multivariate step beyond that theorem. We keep the output scalar and the refinement homogeneous, but replace the onedimensional parameter by a two-dimensional one. Thus we study refinement operators of the form X (V f )(x, y) = cj,k f (2x − j, 2y − k), (1.1) (j,k)∈Z2
where only finitely many coefficients cj,k are nonzero. Our goal is to understand whether, for a compactly supported scalar CPwL seed g : R2 → R, the iterates V n g can still be realized exactly by ReLU networks of fixed width and depth O(n). The tensor-product dyadic case is the natural place to make this first multivariate step. On the conceptual side, it is already a genuinely two-dimensional parameter-domain problem, while still 2
retaining the simplest multivariate residual structure. On the technical side, the one-dimensional scalar binary theory may be organized in two exact ways. In the original surrogate-based formalism [2], the discontinuous residual digits are replaced by continuous piecewise linear surrogate mechanisms, and one keeps track of bad sets created at intermediate stages, showing that their contribution is harmless at the terminal stage. It is conceivable that such a formalism could also be extended to the tensor-product setting, but the bookkeeping would become appreciably more involved. By contrast, the exact loop-controller formulation [3] transports the residual orbit by a forward-exact loop state and confines the remaining seam ambiguity to the terminal readout and selector stage. This is the simpler framework to extend to the present setting: because the tensor-product residual dynamics is still coordinatewise, the controller space becomes simply the product of two polygonal loops. Thus the forward residual transport remains exact, and the genuinely new work is concentrated in the two-dimensional selector and gluing geometry. At the same time, the passage from one parameter variable to two is not merely cosmetic. In one dimension, the discontinuities of the dyadic residual map occur at isolated dyadic points. In two dimensions, the corresponding singular set is a union of dyadic grid lines, and the natural seam region is therefore a union of thin vertical and horizontal strips. Thus the seam bookkeeping becomes geometric rather than purely one-dimensional. Moreover, the naive tensor-product bump h(x)h(y) is not CPwL, so one cannot simply tensorize the one-dimensional special-hat argument. One must instead work with genuine compactly supported CPwL interior atoms. Accordingly, the theorem proved below remains a tensor-product result, but it already exhibits the first genuinely multivariate instance of the loop-controller method.
1.2
Main theorem
We write ΥW,L (ReLU; d, N ) for the set of outputs of fully connected ReLU networks with width W , depth L, input dimension d, and output dimension N . Our main result is the following exact realization theorem. Theorem 1.1. Let V be the scalar dyadic refinement operator on R2 given by X
(V f )(x, y) =
cj,k f (2x − j, 2y − k),
(j,k)∈Z2
where cj,k = 0 for all but finitely many (j, k). Let g : R2 → R be compactly supported and CPwL. Assume that there exists a fixed rectangular support window [0, L1 ] × [0, L2 ] containing supp g and preserved by V , in the sense that supp f ⊂ [0, L1 ] × [0, L2 ]
=⇒
supp(V f ) ⊂ [0, L1 ] × [0, L2 ].
Then there exist constants C0 , C1 > 0, depending only on the mask support, the preserved support window, and the quantitative CPwL complexity of g, such that V n g ∈ ΥC0 ,C1 n (ReLU; 2, 1),
n ≥ 1.
In particular, the width remains bounded independently of n, while the depth grows linearly with the refinement depth. As in the one-dimensional theory, the statement is an exact realization theorem for the finite refinement iterates themselves. We do not formulate a separate approximation theorem for a refinable limit function. Such an approximation statement can be obtained by combining Theorem 1.1 with the corresponding convergence theory for the cascade, as in [2]. 3
1.3
Proof idea and scope
The proof combines the finite-dimensional cascade formalism with an exact controller for the two-dimensional residual dynamics. First, vectorization on the preserved support window reduces the refinement step to a finite-dimensional matrix cascade on [0, 1]2 . Second, the residual pair is transported exactly by a torus controller obtained as the product of two one-dimensional loop controllers. Third, for a compactly supported CPwL profile H supported away from the boundary, the scalar factor H(Rn (·)) is recovered by four terminal readout branches. Fourth, the matrix cascade is propagated by a fixed-depth recursive block using one-dimensional loop-state selectors and the product gadget. Finally, arbitrary compactly supported CPwL seeds are treated by a finite decomposition into such building blocks, together with translation covariance and clamped gluing on the support window. The present paper is intentionally limited to the tensor-product dyadic scalar homogeneous case. This is the cleanest setting in which a genuinely multivariate theorem can be proved, and it already shows that the loop-controller architecture survives passage from one parameter variable to two. At the same time, the argument suggests broader extensions, including diagonal tensor-product dilations in higher dimension, vector-valued outputs, and certain non-diagonal expanding matrices whose suitable iterate becomes diagonal. These directions appear plausible, but would require separate treatment.
1.4
Organization of the paper
Section 2 fixes notation, establishes the dyadic tensor-product cascade identity, and introduces the special atoms used later in the proof. Section 3 develops the exact torus controller obtained as the product of two one-dimensional loop controllers and proves the four-branch scalar readout formula for the special-atom scalar factor. Section 4 constructs the recursive realization of the matrix cascade on the unit square, proves the special-atom theorem, and glues the vectorized realization back to the full support window. Section 5 treats general compactly supported CPwL seeds by finite special-atom decomposition and translation covariance, and deduces Theorem 1.1. Section 6 concludes with a brief discussion of the method and its broader multivariate outlook.
2
Preliminaries and notation
This section fixes notation and records the finite-dimensional cascade formalism underlying the whole paper. The basic mechanism is the same as in the one-dimensional theory, but here it is recast for scalar functions on R2 and for tensor-product dyadic refinement. The main point is that, once the support window is fixed, the refinement step can be encoded by a finite family of transition matrices acting on the vector of unit-square patches of the function.
2.1
Network classes and CPwL functions
For integers W, L, d, N ≥ 1, let ΥW,L (ReLU; d, N ) denote the set of outputs of fully connected feed-forward ReLU networks with width W , depth L, input dimension d, and output dimension N . We write CPwL for continuous piecewise linear. Thus a scalar function f : R2 → R is CPwL if every compact subset of R2 admits a finite polygonal subdivision on whose cells f is affine. In particular, every compactly supported CPwL function is determined by finitely many affine pieces. We shall use repeatedly the following standard closure properties. Remark 2.1. The following facts are standard. 4
(i) Every fixed compactly supported CPwL function on R2 has an exact finite ReLU realization. (ii) Finite sums of fixed-width depth-O(n) networks can be realized by enlarging the width by a constant factor while preserving the depth bound O(n). (iii) Composing a depth-O(n) network with a fixed affine input translation or with a fixed CPwL output map does not change the fact that the depth remains O(n). (iv) If F ∈ ΥW,L (ReLU; 2, N ) and Φ : RN → RM is fixed and CPwL, then Φ ◦ F belongs to ΥW ′ ,L+L′ (ReLU; 2, M ) for some constants W ′ , L′ , depending only on W and on the fixed local complexity of Φ. We shall not track optimal constants in these closure statements. Throughout the paper, the quantity of primary interest is the asymptotic dependence on the refinement depth n, with all other geometric and combinatorial data regarded as fixed.
2.2
Dyadic digits and tensor-product residuals
We begin with the one-dimensional dyadic digit and residual maps. For t ∈ [0, 1), define Q1 (t) := ⌊2t⌋ ∈ {0, 1},
r(t) := 2t − Q1 (t) ∈ [0, 1).
At the endpoint t = 1 we adopt the convention Q1 (1) = 1 and r(1) = 1. Thus r is the usual doubling map on the circle, written on the closed interval [0, 1] with the seam identification 0 ∼ 1. For z = (x, y) ∈ [0, 1]2 , define the dyadic digit map and the tensor-product residual map Q(z) := (Q1 (x), Q1 (y)),
R(z) := (r(x), r(y)).
Thus the residual dynamics is coordinatewise. We define the successive digits and residuals by R0 (z) := z,
Rn := Rn
(n ≥ 1),
Qj (z) := Q(Rj−1 (z))
(j ≥ 1).
Equivalently, we have Rn (z) = rn (x), rn (y) ,
Qj (z) = Q1 (rj−1 (x)), Q1 (rj−1 (y)) .
Remark 2.2. For each n ≥ 1 and each dyadic square Im,n :=
hm
1 m1 + 1 , n 2 2n
×
hm
2 m2 + 1 , n 2 2n
m = (m1 , m2 ) ∈ {0, . . . , 2n − 1}2 ,
,
the residual iterate is affine: Rn (x, y) = 2n x − m1 , 2n y − m2 ,
(x, y) ∈ Im,n .
This is immediate from the one-dimensional identity rn (t) = 2n t − m
on
applied in each coordinate separately.
5
h m m + 1
2n
,
2n
,
2.3
The refinement operator and the support window
Fix finitely many coefficients cj,k ∈ R, not all zero, and define the scalar dyadic refinement operator X
(V f )(x, y) :=
cj,k f (2x − j, 2y − k).
(2.1)
(j,k)∈Z2
Since only finitely many coefficients are nonzero, the sum is finite for every f . Let g : R2 → R be compactly supported and assume supp g ⊂ [0, L1 ] × [0, L2 ] for some integers L1 , L2 ≥ 1. We assume throughout that this rectangular support window is preserved by the operator V , namely, that supp f ⊂ [0, L1 ] × [0, L2 ]
=⇒
supp(V f ) ⊂ [0, L1 ] × [0, L2 ].
(2.2)
This is the natural hypothesis under which the refinement dynamics can be encoded in a fixed finite-dimensional state space.
2.4
Vectorization on unit squares
For 1 ≤ a ≤ L1 and 1 ≤ b ≤ L2 , define the (a, b)-patch of a function f by (u, v) ∈ [0, 1]2 .
fa,b (u, v) := f (u + a − 1, v + b − 1),
Thus fa,b is the restriction of f to the unit square [a − 1, a] × [b − 1, b], reparameterized back to the reference square [0, 1]2 . The vectorization of f is the finite vector-valued function
G(u, v) := Vec(f )(u, v) := fa,b (u, v) 1≤a≤L1 , 1≤b≤L2 . We fix once and for all an ordering of the index pairs (a, b); the precise ordering is irrelevant, provided it is used consistently throughout. Thus G takes values in RL1 L2 and records all unit-square pieces of f simultaneously on the single reference square [0, 1]2 . For the iterates of the seed g, we write Gn := Vec(V n g),
n ≥ 0.
In particular, note that G0 = Vec(g). Remark 2.3. The point of vectorization is that the refinement step no longer acts on a scalar function defined on the whole support window, but on a finite vector of reference-square patches. Once written in this form, the refinement step becomes multiplication by a matrix selected by the current dyadic digit pair. This is the tensor-product analogue of the one-dimensional vectorization used in the scalar dyadic theory.
2.5
Block transition matrices
For each dyadic digit q = (q1 , q2 ) ∈ {0, 1}2 , define the transition matrix Tq ∈ RL1 L2 ×L1 L2 as follows. Its entry from source patch (α, β) to target patch (a, b) is (Tq )(a,b),(α,β) = c q1 +2(a−1)−(α−1), q2 +2(b−1)−(β−1) .
(2.3)
Whenever the corresponding mask index is absent, the coefficient is interpreted as zero. The meaning of (2.3) is simple. On the branch where the current digit pair is q = (q1 , q2 ), the arguments 2x − j and 2y − k can be rewritten in terms of the common residual variables r(x) and r(y), plus integer translations. The matrix Tq records exactly which source patch of the function contributes to which target patch after this rewriting. 6
Remark 2.4. The matrices Tq are the two-dimensional tensor-product analogue of the onedimensional matrices T0 , T1 in the scalar dyadic theory, cf. [2, 3]. Here there are four possibilities, corresponding to the four dyadic quadrants of the unit square.
2.6
One-step cascade identity
We now prove the basic finite-dimensional identity behind the whole construction. Proposition 2.5 (One-step tensor-product cascade identity). For every z ∈ [0, 1]2 , we have G1 (z) = TQ(z) G(R(z)). Proof. Fix z = (x, y) ∈ [0, 1]2 , and write Q(z) = q = (q1 , q2 ). Let (a, b) be a target patch index. By definition of vectorization, we have (G1 )a,b (x, y) = (V g)(x + a − 1, y + b − 1). Using the definition of the refinement operator (2.1), we obtain X
(G1 )a,b (x, y) =
cj,k g(2x + 2(a − 1) − j, 2y + 2(b − 1) − k).
(j,k)∈Z2
Since 2x = r(x) + q1 and 2y = r(y) + q2 , this becomes (G1 )a,b (x, y) =
X
cj,k g(r(x) + q1 + 2(a − 1) − j, r(y) + q2 + 2(b − 1) − k).
(j,k)∈Z2
Now with α := q1 + 2(a − 1) − j + 1 and β := q2 + 2(b − 1) − k + 1, we have r(x) + q1 + 2(a − 1) − j = r(x) + α − 1,
r(y) + q2 + 2(b − 1) − k = r(y) + β − 1.
Whenever 1 ≤ α ≤ L1 and 1 ≤ β ≤ L2 , the corresponding term is exactly gα,β (R(z)). If either index lies outside the support window, then the corresponding physical point lies outside [0, L1 ] × [0, L2 ], and the term vanishes by the support assumption. Therefore we infer (G1 )a,b (z) =
X
c q1 +2(a−1)−(α−1), q2 +2(b−1)−(β−1) Gα,β (R(z)).
α,β
By the definition (2.3) of the transition matrix Tq , this is precisely the (a, b)-component of Tq G(R(z)). Since (a, b) was arbitrary, the proof is complete. Corollary 2.6 (Iterated cascade identity). For every n ≥ 1 and every z ∈ [0, 1]2 , we have Gn (z) = TQ1 (z) TQ2 (z) · · · TQn (z) G(Rn (z)). Proof. We argue by induction on n. The case n = 1 is exactly Proposition 2.5. Assume the formula holds for some n ≥ 1. Then we have Gn+1 (z) = Vec(V n+1 g)(z) = Vec V (V n g) (z).
Applying Proposition 2.5 to the seed V n g, we obtain Gn+1 (z) = TQ(z) Gn (R(z)). 7
Now use the induction hypothesis at the point R(z): Gn (R(z)) = TQ1 (R(z)) · · · TQn (R(z)) G(Rn (R(z))). Taking into account that Qj (R(z)) = Qj+1 (z) and Rn (R(z)) = Rn+1 (z) we have Gn (R(z)) = TQ2 (z) · · · TQn+1 (z) G(Rn+1 (z)). Substituting this into the previous display gives Gn+1 (z) = TQ1 (z) TQ2 (z) · · · TQn+1 (z) G(Rn+1 (z)), which is exactly the required formula with n + 1 in place of n.
2.7
The product gadget
We record here the standard product gadget from [2, Lemma 9] that will be used repeatedly in the recursive block. Its role is not to implement general multiplication of two variable network outputs, but to gate a vector-valued state by a scalar selector and to annihilate states that are already zero. Lemma 2.7 (Product gadget). Let N ∈ N and a > 0. Define Πa (λ, y) := −ReLU(λa1 − y) − ReLU((1 − λ)a1 − ReLU(−y)) + a1, for λ ∈ [0, 1] and y ∈ RN , where 1 ∈ RN is the vector of all ones. Then Πa ∈ Υ2N +1,2 (ReLU; N + 1, N ), and for every y ∈ [−a, a]N and every λ ∈ [0, 1] one has Πa (1, y) = y,
2.8
Πa (0, y) = 0,
Πa (λ, 0) = 0.
Special atoms
Fix once and for all 0 < ϱ < 21 . The specific value of ϱ is not important; its role is simply to keep the support of the distinguished atoms away from the boundary of the reference square. Definition 2.8 (Special atom). A special atom is a compactly supported non-negative CPwL function H : R2 → [0, ∞) such that supp H ⊂ [ϱ, 1 − ϱ]2 ,
and
H has finite polygonal complexity.
The support condition is the two-dimensional replacement for the one-dimensional special-hat condition. It is exactly what allows the terminal seam ambiguity of the loop readout to be absorbed by vanishing near the boundary of the square.
3
Exact torus controller and scalar readout
This section develops the controller and scalar readout used in the rest of the paper. The underlying ingredient is the one-dimensional exact loop controller from [3], which in the present binary scalar setting can be written in a concrete form and then used coordinatewise. In particular, the tensorproduct residual dynamics on [0, 1]2 is transported exactly on the product of two polygonal loops. Thus no forward iteration of scalar residual surrogates is needed; the only remaining seam ambiguity comes from the loop parametrization and is handled at the terminal readout stage. Since the later argument depends directly on this controller, we include a short proof of the binary one-dimensional construction in the concrete form needed here. 8
3.1
A polygonal loop for the one-dimensional residual
Recall from §2.2 the one-dimensional dyadic residual map r(t) = 2t − ⌊2t⌋ for t ∈ [0, 1], together with the endpoint convention r(1) = 1. Thus r is the usual doubling map on the circle, written on the closed interval [0, 1] with the seam identification 0 ∼ 1. We use a concrete polygonal model of this circle dynamics. Let a0 = (0, 0), a1 = (1, 1), and a2 = (1, 0). Let ∆ ⊂ R2 be the closed triangle with vertices a0 , a1 , a2 , and denote its boundary by Γ = ∂∆. We parametrize Γ by the continuous piecewise affine map E : [0, 1] → Γ defined by
E(t) =
(3t, 3t),
0 ≤ t ≤ 13 ,
(1, 2 − 3t),
2 1 3 ≤ t ≤ 3,
(3 − 3t, 0),
2 3 ≤ t ≤ 1.
(3.1)
Then E(0) = E(1) = a0 , and E is injective on [0, 1). Thus Γ is a polygonal realization of the residual circle, with the single seam identification encoded by the equality E(0) = E(1). Proposition 3.1 (Exact loop controller). There exists a fixed CPwL map F : R2 → R2 such that t ∈ [0, 1].
F (E(t)) = E(r(t)),
Moreover, F admits an exact finite ReLU realization, with width and depth depending only on its piecewise-affine complexity. Proof. Define first a boundary map FΓ : Γ → Γ by FΓ (E(t)) := E(r(t)) for t ∈ [0, 1]. This is well defined because the only identification in the parametrization E is E(0) = E(1), and E(r(0)) = E(0) = a0 = E(1) = E(r(1)). More explicitly, FΓ is given on the three sides of Γ by
FΓ (z) =
(2s, 2s), (1, 2 − 2s), (2y − 1, 0),
z = (s, s), 0 ≤ s ≤ 12 , z = (s, s), 21 ≤ s ≤ 1, z = (1, y), 12 ≤ y ≤ 1,
(1 − 2y, 1 − 2y), (1, 2x − 1),
(2x, 0),
z = (1, y), 0 ≤ y ≤ 12 , z = (x, 0), 12 ≤ x ≤ 1, z = (x, 0), 0 ≤ x ≤ 12 .
Thus FΓ is continuous and piecewise affine on Γ. Now choose any continuous piecewise affine extension of FΓ from Γ to the whole plane. For example, one may triangulate ∆ compatibly with the six boundary breakpoints (0, 0), ( 12 , 12 ), (1, 1), (1, 21 ), (1, 0), ( 12 , 0), extend affinely on each subtriangle of ∆, and then extend further outside ∆ by any fixed piecewise affine rule on a finite polygonal subdivision of a surrounding polygonal region. This yields a global CPwL map F : R2 → R2 such that F |Γ = FΓ . Hence F (E(t)) = FΓ (E(t)) = E(r(t)),
t ∈ [0, 1].
Finally, since F : R2 → R2 is a CPwL map, each of its two scalar components admits an exact depth-2 ReLU realization by [4]. Realizing these two components in parallel gives the stated network-realizability property for F . 9
Iterating the controller immediately yields exact transport of the residual orbit. Corollary 3.2 (Exact one-dimensional loop-state transport). For every n ≥ 0 and every t ∈ [0, 1], F n (E(t)) = E(rn (t)). Proof. The case n = 0 is tautological. If the identity holds at level n, then F n+1 (E(t)) = F (F n (E(t))) = F (E(rn (t))) = E(rn+1 (t)) by Proposition 3.1. This proves the claim by induction.
3.2
The torus controller
We now pass from the one-dimensional loop controller to the tensor-product setting relevant for the present paper. Define the controller embedding E : [0, 1]2 → Γ × Γ ⊂ R4 ,
E(x, y) := E(x), E(y) ,
and the controller update map F : R4 → R4 ,
F(z1 , z2 ) := F (z1 ), F (z2 ) .
Thus E embeds the residual point (x, y) into the product loop Γ × Γ, which is a topological torus, and F updates the two loop coordinates independently. Proposition 3.3 (Exact torus controller). For every n ≥ 0 and every (x, y) ∈ [0, 1]2 , we have F n (E(x, y)) = E(Rn (x, y)). Equivalently, if we define the forward controller states by zn (x, y) := F n (E(x, y)), then it holds that zn (x, y) = E(rn (x)), E(rn (y)) ,
n ≥ 0.
Proof. Recall from §2.2 that Rn (x, y) = (rn (x), rn (y)). The case n = 0 is immediate from the definition of E. Suppose the identity holds at stage n. Then we see zn+1 (x, y) = F(zn (x, y)) = F E(rn (x)), E(rn (y)) = F (E(rn (x))), F (E(rn (y))) .
Applying Corollary 3.2 in each coordinate gives zn+1 (x, y) = E(rn+1 (x)), E(rn+1 (y)) = E(Rn+1 (x, y)).
This proves the result by induction. Remark 3.4. The point of Proposition 3.3 is that the forward residual dynamics is now exact. No scalar surrogate residuals are iterated forward. All seam ambiguity is postponed to the terminal readout and selector stage. Because both E and F are fixed CPwL maps, Proposition 3.3 has the following immediate network-theoretic consequence. Corollary 3.5 (Network realization of the forward controller). There exist constants C0 , C1 > 0, depending only on the fixed local complexities of E and F , such that zn ∈ ΥC0 ,C1 n (ReLU; 2, 4),
n ≥ 0.
Proof. The embedding E is a fixed CPwL map, hence it admits an exact finite ReLU realization of constant width and depth. Likewise, F is a fixed CPwL map on R4 , so it also admits an exact finite ReLU realization of constant width and depth. Since zn = F n ◦ E, the map zn is realized by one fixed input block for E, followed by n copies of the fixed update block for F. This gives fixed width and depth O(n). 10
3.3
One-dimensional terminal readouts
To use the exact controller, we must recover the one-dimensional residual coordinate from a point on the loop. Since E(0) = E(1), there is no single globally exact readout on Γ. The corresponding two-readout device from [3], which we simply recall here in the form needed below, is as follows. Lemma 3.6 (One-dimensional terminal readouts). Fix numbers 0 < ε̄ < ϱ < 12 . Then there exist CPwL maps ρ− , ρ+ : R2 → [0, 1] with the following properties. (i) The readouts are exact away from complementary seam neighborhoods: ρ− (E(t)) = t
ρ+ (E(t)) = t
for t ∈ [ε̄, 1],
for t ∈ [0, 1 − ε̄].
(ii) For every one-dimensional special-hat h satisfying supp h ⊂ [ϱ, 1−ϱ], one has the exact identity h(t) = min h(ρ− (E(t))), h(ρ+ (E(t))) ,
t ∈ [0, 1].
(iii) The maps ρ± ◦ E : [0, 1] → [0, 1] admit exact finite ReLU realizations. Figure 1 gives a schematic view of the complementary readouts ρ− and ρ+ from Lemma 3.6.
Figure 1: Complementary scalar readouts ρ− (left) and ρ+ (right). The dashed line is the identity and the solid curve is the corresponding readout. The horizontal shaded strip is the support interval [ρ, 1 − ρ] of the special hat. The vertical shaded strip marks the seam interval modified by the readout: [1 − ε, 1] on the left and [0, ε] on the right.
3.4
Four-branch scalar readout for special atoms
We now combine the exact torus controller with the complementary one-dimensional readouts to recover the scalar factor associated with a special atom. For σ, τ ∈ {−, +}, define the readout ρσ,τ : R4 → R2 ,
ρσ,τ (z1 , z2 ) := ρσ (z1 ), ρτ (z2 ) .
The next theorem is the two-dimensional scalar counterpart of the one-dimensional terminal readout mechanism. It recovers the special-atom factor H(Rn (·)) directly from the exact toruscontroller state by four terminal branches, corresponding to the two complementary seam reads in each coordinate. 11
Theorem 3.7 (Special-atom scalar factor). Let H be a special atom in the sense of Definition 2.8. Then for every n ≥ 1 and every (x, y) ∈ [0, 1]2 , we have H(Rn (x, y)) =
min
σ,τ ∈{−,+}
H(ρσ,τ (zn (x, y))) ,
(3.2)
where zn (x, y) is the exact torus-controller state from Proposition 3.3. Consequently, there exist constants C0 , C1 > 0, depending only on ε̄, ϱ, and the fixed local complexity of H, such that H(Rn (·)) ∈ ΥC0 ,C1 n (ReLU; 2, 1). Proof. Set u = rn (x) and v = rn (y), so that Rn (x, y) = (u, v). By Proposition 3.3, we have zn (x, y) = E(u), E(v) . Hence, for every σ, τ ∈ {−, +}, we infer ρσ,τ (zn (x, y)) = ρσ (E(u)), ρτ (E(v)) .
Therefore (3.2) is equivalent to H(u, v) =
min
σ,τ ∈{−,+}
H ρσ (E(u)), ρτ (E(v)) .
(3.3)
We prove (3.3) by a case split. Case 1: (u, v) ∈ [ε̄, 1 − ε̄]2 . In this case both readouts are exact in each coordinate, so ρ− (E(u)) = u = ρ+ (E(u)),
ρ− (E(v)) = v = ρ+ (E(v)).
Thus all four branches coincide with H(u, v), and therefore min
H ρσ (E(u)), ρτ (E(v)) = H(u, v).
σ,τ ∈{−,+}
Case 2: (u, v) ∈ / [ε̄, 1 − ε̄]2 . Then at least one of the coordinates u, v belongs to [0, ε̄] ∪ [1 − ε̄, 1]. Because ε̄ < ϱ and supp(H) ⊂ [ϱ, 1 − ϱ]2 , we have H(u, v) = 0. Now choose the signs so that the readout is exact in each coordinate: +,
+,
u ∈ [0, ε̄], σ∗ = −, u ∈ [1 − ε̄, 1], arbitrary, u ∈ [ε̄, 1 − ε̄],
v ∈ [0, ε̄], τ∗ = −, v ∈ [1 − ε̄, 1], arbitrary, v ∈ [ε̄, 1 − ε̄].
Then we have ρσ∗ (E(u)) = u,
ρτ∗ (E(v)) = v,
and hence H ρσ∗ (E(u)), ρτ∗ (E(v)) = H(u, v) = 0.
Since H ≥ 0, all four branch values are nonnegative. Therefore min
σ,τ ∈{−,+}
H ρσ (E(u)), ρτ (E(v)) = 0 = H(u, v).
This proves (3.3), and therefore (3.2). For the network-realizability statement, note first that the controller state (x, y) 7→ zn (x, y) belongs to ΥC0′ ,C1′ n (ReLU; 2, 4) by Corollary 3.5. For each σ, τ ∈ {−, +}, the readout ρσ,τ : R4 → R2 12
is fixed and CPwL, and H : R2 → R is a fixed compactly supported CPwL map. Hence each branch (x, y) 7→ H(ρσ,τ (zn (x, y))) belongs to a class ΥCe ,Ce n (ReLU; 2, 1) with constants depending only on 0 1 ε̄, ϱ, and the fixed local complexity of H. Finally, the minimum of two scalar outputs is realized by a fixed-depth ReLU gadget, and hence the minimum of the four branch outputs is obtained by composing this gadget twice. Running the four branches in parallel changes the width only by a constant factor and adds only O(1) extra depth. Therefore there exist constants C0 , C1 > 0, depending only on ε̄, ϱ, and the fixed local complexity of H, such that H(Rn (·)) ∈ ΥC0 ,C1 n (ReLU; 2, 1). The scalar part of the construction is now complete. The exact torus controller transports the residual pair forward without approximation, and Theorem 3.7 shows that the terminal scalar factor associated with a special atom can be recovered exactly from that controller state. It remains to treat the finite-dimensional matrix cascade: the selector matrices, the recursive propagation of the vectorized state, and the reconstruction of the physical function on the support window. This is the content of the next section.
4
Recursive realization for special atoms
In this section we turn from the scalar controller/readout mechanism to the finite-dimensional matrix cascade. By Theorem 3.7, the scalar factor H(Rn (·)) associated with a special atom is already under exact control. What remains is to propagate the vectorized cascade through the dyadic digit pairs and then to glue the resulting squarewise realization back to a scalar function on the support window. For the purposes of the present section, it is enough to treat a special atom H : [0, 1]2 → R supported in the reference square. The translated case will be handled later in Section 5 by translation covariance, so no shifted atoms are needed here. Since H is supported in the first unit square, its vectorization is simply G(u, v) := Vec(H)(u, v) = H(u, v) b11 ,
(u, v) ∈ [0, 1]2 ,
where b11 ∈ RL1 L2 denotes the standard basis vector corresponding to the patch (1, 1). Accordingly, Corollary 2.6 gives Gn (z) = TQ1 (z) TQ2 (z) · · · TQn (z) H(Rn (z)) b11 ,
z ∈ [0, 1]2 .
(4.1)
Thus the scalar factor has already been separated off, and the remaining task is to realize the matrix product by a fixed-depth recursive block.
4.1
Binary loop selectors and terminal boundary localization
Unlike the terminal scalar readout from Section 3, the selector transition width must depend on the final depth n. Indeed, a point that enters the selector transition set at an intermediate stage is not expected to remain near the boundary under further iteration; the dyadic residual map is expanding. What matters is the terminal effect: δn is chosen so that, if one coordinate enters the transition set at some stage j ≤ n, then by time n the terminal residual lies in a boundary layer where the special atom already vanishes. We recall the selector mechanism from [3], specialized to the binary setting. Fix once and for all a parameter 0 < δ̄ < 1, and for each n ≥ 1 define δn := δ̄ ϱ 2−n . We then set Jn := [0, δn ] ∪ [ 12 , 12 + δn ]. This is the one-dimensional transition set used in the selector stage. For each n ≥ 1, we fix CPwL selectors χ0,n , χ1,n : R2 → [0, 1] with the following properties: 13
(i) χ0,n (z) + χ1,n (z) = 1 for z ∈ Γ; (ii) χ0,n (E(t)) = χ[0,1/2) (t) and χ1,n (E(t)) = χ[1/2,1] (t) for every t ∈ [0, 1] \ Jn ; (iii) each χq,n admits an exact finite ReLU realization with width and depth bounded independently of n, while the corresponding weights and biases may be chosen with magnitudes bounded by C 2n , where C depends only on δ̄ and ϱ. The next lemma is the key geometric fact that absorbs selector ambiguity. The one-dimensional transition set Jn gives rise in the square to thin vertical and horizontal transition strips, since ambiguity occurs whenever at least one coordinate is in transition. If a residual orbit enters these strips at any stage, then the terminal residual is already forced outside the support box [ϱ, 1 − ϱ]2 of the special atom. Figure 2 illustrates this geometry and a sample residual orbit.
Figure 2: Transition strips, support box, and a sample residual orbit. Lemma 4.1 (Boundary localization). Assume that for some j ∈ {1, . . . , n} one has rj−1 (x) ∈ Jn
or
rj−1 (y) ∈ Jn .
Then we have H(Rn (x, y)) = 0. Proof. By symmetry, it suffices to treat only the x-coordinate. So assume from now on that rj−1 (x) ∈ Jn = [0, δn ] ∪ [ 21 , 12 + δn ]. If rj−1 (x) ∈ [0, δn ], then the dyadic digit is 0, and therefore rj (x) = 2rj−1 (x) ∈ [0, 2δn ]. If rj−1 (x) ∈ [ 12 , 21 + δn ], then the dyadic digit is 1, and we now have rj (x) = 2rj−1 (x) − 1 ∈ [0, 2δn ]. Thus in all cases, we conclude rj (x) ∈ [0, 2δn ].
14
We now iterate forward. Since the residual map is one-sided from the right at both breakpoints 0 and 12 , each further iterate preserves the left boundary layer and doubles its width. Hence rn (x) ∈ [0, 2 n−j+1 δn ]. Using δn = δ̄ ϱ 2−n , we obtain 2 n−j+1 δn = 2 n−j+1 δ̄ ϱ 2−n = δ̄ ϱ 21−j ≤ δ̄ ϱ < ϱ. Therefore we infer rn (x) ∈ [0, ϱ), and in particular, Rn (x, y) = rn (x), rn (y) ∈ / [ϱ, 1 − ϱ]2 .
Since supp H ⊂ [ϱ, 1 − ϱ]2 , it is immediate that H(Rn (x, y)) = 0.
4.2
Modified matrix selectors
For each stage j = 1, . . . , n, define the modified matrix field cj (x, y) := M
X
(1)
(2)
χq1 ,n zj−1 (x, y) χq2 ,n zj−1 (x, y) T(q1 ,q2 ) ,
q1 ,q2 ∈{0,1}
where (1)
(2)
zj−1 (x, y) = zj−1 (x, y), zj−1 (x, y) = E(rj−1 (x)), E(rj−1 (y))
is the exact torus-controller state from Proposition 3.3. cj (x, y) is a CPwL convex combination of the four digit-pair transition matrices. If neither Thus M coordinate has entered the transition set at the preceding stages, we shall call the orbit good; in cj coincides with the exact transition matrix. If some that case exactly one digit pair is active and M coordinate has entered the transition set earlier, we shall call the orbit bad; in that case the scalar factor has already vanished by Lemma 4.1. cj appears only as a bookkeeping device in the identity below. The actual It is important that M recursive network does not compute the products χq1 ,n χq2 ,n as separate bilinear functions. Instead, the branch states are gated successively by nested applications of the product gadget from §2.7. Lemma 4.2 (Modified cascade identity). For a coordinate index ℓ ∈ {1, . . . , L1 L2 }, define gn,ℓ (x, y) := e⊤ ℓ Gn (x, y),
(x, y) ∈ [0, 1]2 .
Then c c gn,ℓ (x, y) = H(Rn (x, y)) e⊤ ℓ M1 (x, y) · · · Mn (x, y) b11 ,
(x, y) ∈ [0, 1]2 .
Proof. Corollary 2.6 gives Gn (x, y) = TQ1 (x,y) TQ2 (x,y) · · · TQn (x,y) G(Rn (x, y)). Since G = H b11 , this becomes gn,ℓ (x, y) = H(Rn (x, y)) e⊤ ℓ TQ1 (x,y) TQ2 (x,y) · · · TQn (x,y) b11 . We distinguish two cases.
15
(4.2)
Case 1: Good orbit. Assume that rj−1 (x) ∈ / Jn and rj−1 (y) ∈ / Jn for every j = 1, . . . , n. Then, by the defining property of the selectors, we have (1)
(2)
χ0,n zj−1 (x, y) = χ[0,1/2) rj−1 (x) ,
(1)
(2)
χ1,n zj−1 (x, y) = χ[1/2,1] rj−1 (x) ,
χ0,n zj−1 (x, y) = χ[0,1/2) rj−1 (y) ,
χ1,n zj−1 (x, y) = χ[1/2,1] rj−1 (y) .
Since rj−1 (x), rj−1 (y) ∈ / Jn on a good orbit, and Jn contains the overlap point 12 , exactly one selector is active in each coordinate. Hence exactly one pair (q1 , q2 ) is active, namely (q1 , q2 ) = Qj (x, y), and therefore cj (x, y) = T M j = 1, . . . , n. Qj (x,y) , Substituting this into the exact cascade formula gives the claim. Case 2: Bad orbit. Assume that rj−1 (x) ∈ Jn or rj−1 (y) ∈ Jn for some j ∈ {1, . . . , n}. Then Lemma 4.1 gives H(Rn (x, y)) = 0. Therefore the right hand side of (4.2) vanishes, and so does gn,ℓ due to (4.1).
4.3
Recursive realization on the unit square
We now turn the modified cascade identity into an explicit recursive network construction. Fix a coordinate index ℓ ∈ {1, . . . , L1 L2 }. We initialize the backward state by Φ0 (x, y) := H(Rn (x, y)) eℓ . Further, define B := max ∥Tq⊤ ∥∞→∞ , q∈{0,1}2
an := max{1, B n MH }.
MH := ∥H∥L∞ ([0,1]2 ) ,
For j = 1, . . . , n, define recursively b j (x, y) := Φ
(2)
(1)
⊤ b Πan χq2 ,n (zj−1 (x, y)), Πan χq1 ,n (zj−1 (x, y)), T(q Φ (x, y) 1 ,q2 ) j−1
X
,
q1 ,q2 ∈{0,1}
b 0 (x, y) := Φ0 (x, y). with Φ Here Φ0 is obtained by composing the scalar realization of H(Rn (·)) from Theorem 3.7 with the ⊤ fixed linear embedding s 7→ s eℓ , while each map y 7→ T(q y is a fixed affine map on RL1 L2 . Thus 1 ,q2 ) the only nontrivial part of the recursive construction is the exact gating of the branch contributions. The point of the nested definition above is that no exact multiplication of two variable selector outputs is ever required: on a good orbit the selectors are already binary, so exactly one digit pair survives; on a bad orbit the initial state is already zero, and the identity Πan (λ, 0) = 0 annihilates all subsequent branches automatically.
Theorem 4.3 (Recursive realization on the unit square). For every ℓ ∈ {1, . . . , L1 L2 } and every (x, y) ∈ [0, 1]2 , we have n ⊤ b e⊤ ℓ Vec(V H)(x, y) = b11 Φn (x, y). Consequently, there exist constants C0 , C1 > 0, depending only on the support window, the mask support, and the fixed local complexity of H, such that Vec(V n H) ∈ ΥC0 ,C1 n (ReLU; 2, L1 L2 ),
n ≥ 1.
Moreover, the corresponding network weights and biases may be chosen with magnitudes bounded by C2 Λn for suitable constants C2 , Λ > 0 depending only on the support window, the mask support, and H. 16
Proof. We argue by a global good/bad orbit dichotomy. Good orbit. Assume that neither coordinate enters the transition set at any stage, namely rj−1 (x) ∈ / Jn
and
rj−1 (y) ∈ / Jn
for all j = 1, . . . , n.
Then the selectors recover the exact dyadic digits in each coordinate, so at every stage exactly one pair (q1 , q2 ) is active, namely (q1 , q2 ) = Qj (x, y). Hence the recursive block reduces to the exact adjoint update Φj (x, y) := TQ⊤j (x,y) Φj−1 (x, y), j = 1, . . . , n, with Φ0 (x, y) = H(Rn (x, y))eℓ . Now Lemma 4.2 yields n ⊤ e⊤ ℓ Vec(V H)(x, y) = b11 Φn (x, y).
Moreover, we have ∥Φj (x, y)∥∞ ≤ B j MH ≤ an ,
j = 0, . . . , n.
Thus every input to the product gadget lies in the admissible range, and the identities from b j (x, y) = Φj (x, y) for j = 0, . . . , n, and thus Lemma 2.7 apply. Consequently, we have Φ n ⊤ b e⊤ ℓ Vec(V H)(x, y) = b11 Φn (x, y).
Bad orbit. Assume that at least one coordinate enters Jn at some stage. Then Lemma 4.1 gives H(Rn (x, y)) = 0, and so b 0 (x, y) = Φ0 (x, y) = 0. Φ b j (x, y) vanishes whenever Φ b j−1 (x, y) = 0. As Πan (·, 0) = 0, every term in the recursive definition of Φ b By induction, we infer Φj (x, y) = 0 for all j = 0, . . . , n. On the other hand, since
G(Rn (x, y)) = H(Rn (x, y)) b11 = 0, the exact cascade also vanishes: Vec(V n H)(x, y) = 0. Thus we conclude that n ⊤ b e⊤ ℓ Vec(V H)(x, y) = b11 Φn (x, y) = 0
on every bad orbit as well. This proves the scalar identity for each fixed ℓ. Since the number of coordinates is fixed, we may run the finitely many coordinate constructions in parallel. Thus we conclude Vec(V n H) ∈ ΥC0 ,C1 n (ReLU; 2, L1 L2 ). Finally, the only n-dependent affine coefficients in the construction come from the selectors and from the gate scale an . The selector slopes are of order δn−1 ≍ 2n , while an ≤ max{1, B n MH }. Hence all weights and biases may be bounded in magnitude by C2 Λn for suitable constants C2 , Λ > 0.
4.4
Clamped gluing and the special-atom theorem
We now pass from the vectorized realization on the reference square to the physical function on the support window. Theorem 4.3 realizes Vec(V n H) on [0, 1]2 , encoding all unit-square patches of V n H simultaneously. To recover the scalar function V n H on R2 , one must glue these compatible patches across the preserved support window. The next lemma provides this fixed-overhead clamped gluing step, and the resulting theorem yields the exact realization of V n H itself.
17
Lemma 4.4 (Exact clamped gluing on a rectangular window). Let f : R2 → R be supported in [0, L1 ] × [0, L2 ], and for integers 1 ≤ a ≤ L1 , 1 ≤ b ≤ L2 , let (u, v) ∈ [0, 1]2 ,
fa,b (u, v) := f (u + a − 1, v + b − 1),
denote its unit-square pieces. Assume that each fa,b belongs to ΥW,L (ReLU; 2, 1), and that the usual edge compatibilities hold: fa,b (1, v) = fa+1,b (0, v) (1 ≤ a < L1 ), fa,b (u, 1) = fa,b+1 (u, 0)
(1 ≤ b < L2 ).
Then there exist constants C0 , C1 > 0, depending only on L1 , L2 , such that f ∈ ΥC0 W, L+C1 (ReLU; 2, 1). Proof. By [3, Lemma 3.13], if g1 , . . . , gm : [0, 1] → R satisfy g1 (0) = 0,
gm (1) = 0,
gk (1) = gk+1 (0)
then the function G[g1 , . . . , gm ](t) := g1 (σ1 (t)) +
m X
(k = 1, . . . , m − 1),
gk (σk (t)) − gk (0)
k=2
agrees with gk0 (t − k0 + 1) on [k0 − 1, k0 ] and vanishes outside [0, m]. Here σk (t) := ReLU(t − k + 1) − ReLU(t − k) is the standard ramp. We apply this lemma twice. First, fix b ∈ {1, . . . , L2 } and v ∈ [0, 1]. Apply the one-dimensional gluing lemma in the x-variable to the compatible family u 7→ f1,b (u, v), . . . , u 7→ fL1 ,b (u, v). The horizontal edge compatibilities fa,b (1, v) = fa+1,b (0, v) show that the hypotheses are satisfied, and the support condition on f gives the required boundary vanishing at the outer edges. Hence the row-glued function Gb (x, v) := f1,b (σ1 (x), v) +
L1 X
fa,b (σa (x), v) − fa,b (0, v)
a=2
satisfies Gb (x, v) = fa0 ,b (x − a0 + 1, v)
for x ∈ [a0 − 1, a0 ].
Next, fix x ∈ R. Apply the same one-dimensional gluing lemma in the y-variable to the compatible family v 7→ G1 (x, v), . . . , v 7→ GL2 (x, v). The vertical edge compatibilities for the original patches imply Gb (x, 1) = Gb+1 (x, 0) for b = 1, . . . , L2 − 1, and again the support condition gives the outer boundary vanishing. Therefore f ♯ (x, y) := G1 (x, σ1 (y)) +
L2 X
Gb (x, σb (y)) − Gb (x, 0)
b=2
satisfies f ♯ (x, y) = Gb0 (x, y − b0 + 1)
for y ∈ [b0 − 1, b0 ].
Combining the two identities, if x ∈ [a0 − 1, a0 ] and y ∈ [b0 − 1, b0 ], then f ♯ (x, y) = Gb0 (x, y − b0 + 1) = fa0 ,b0 (x − a0 + 1, y − b0 + 1) = f (x, y). Thus f ♯ = f on the support window, and the same gluing lemma shows that f ♯ vanishes outside [0, L1 ] × [0, L2 ]. Hence f ♯ = f on all of R2 . Finally, the construction uses only fixed ramp maps, composition with the already-constructed patch networks, subtraction of fixed edge traces, and finite summation over the fixed index sets 1 ≤ a ≤ L1 , 1 ≤ b ≤ L2 . Since L1 , L2 are fixed, this enlarges the width only by a constant factor and adds only O(1) extra depth. Therefore we have f ∈ ΥC0 W, L+C1 (ReLU; 2, 1). 18
We now pass from the vectorized realization of V n H on the reference square to the physical function V n H on the support window by applying the clamped gluing lemma. Theorem 4.5 (Special-atom theorem). Let H be a special atom. Then there exist constants C0 , C1 > 0, depending only on the support window, the mask support, and the fixed local complexity of H, such that V n H ∈ ΥC0 ,C1 n (ReLU; 2, 1) for n ≥ 1. Proof. Theorem 4.3 gives Vec(V n H) ∈ ΥC0′ ,C1′ n (ReLU; 2, L1 L2 ). The unit-square pieces are compatible by construction, so Lemma 4.4 reconstructs V n H from its vectorization with only O(1) extra overhead. This gives the stated result.
5
General compactly supported seeds
In this section we pass from the special-atom theorem to arbitrary compactly supported CPwL seeds. The argument has three finite steps: decompose the seed into finitely many translated special atoms, move the corresponding realizations to the correct locations by translation covariance, and sum the resulting networks. Since the number of atoms and their local complexities depend only on the fixed geometric and combinatorial complexity of the seed, all of this overhead is independent of the refinement depth n.
5.1
Finite special-atom decomposition
We begin by decomposing an arbitrary compactly supported CPwL seed into finitely many translated special atoms. The only issue is to choose a sufficiently fine local basis so that each basis function fits strictly inside a translate of the reference square with margin ϱ. Proposition 5.1 (Finite special-atom decomposition). Let g : R2 → R be compactly supported and CPwL, and assume supp g ⊂ [0, L1 ] × [0, L2 ]. Then there exist an integer N ≥ 1, coefficients a1 , . . . , aN ∈ R, translation vectors δ1 , . . . , δN ∈ R2 , and special atoms H1 , . . . , HN such that g(z) =
N X
aν Hν (z − δν ),
z ∈ R2 .
(5.1)
ν=1
Moreover, the number N and the local polygonal complexities of the atoms Hν can be bounded in terms of the fixed support window and a chosen quantitative CPwL description of g. Proof. Choose a finite triangulation T of the support window [0, L1 ] × [0, L2 ] such that g is affine on every triangle of T . Since g is compactly supported and CPwL, such a triangulation exists. We now refine T further, if necessary, so that the support of every nodal basis function of the refined triangulation has ℓ∞ -diameter strictly smaller than 1 − 2ϱ. Since the support window is compact and the triangulation is finite, this can be achieved by finitely many barycentric subdivisions or any other standard finite local refinement procedure. Let ϕ1 , . . . , ϕN denote the nodal hat functions of the resulting refined triangulation. Then each ϕν is nonnegative, compactly supported, and CPwL, and the standard nodal expansion gives g(z) =
N X
aν ϕν (z),
ν=1
for suitable coefficients aν ∈ R.
19
Fix ν ∈ {1, . . . , N }. Since the support of ϕν has ℓ∞ -diameter strictly less than 1 − 2ϱ, there exists a translation vector δν ∈ R2 such that supp ϕν ⊂ δν + [ϱ, 1 − ϱ]2 . Define Hν (w) := ϕν (w + δν ),
w ∈ R2 .
Then Hν is nonnegative, compactly supported, and CPwL, and supp Hν ⊂ [ϱ, 1 − ϱ]2 . Hence Hν is a special atom in the sense of Definition 2.8. Moreover, substituting ϕν (z) = Hν (z − δν ) into the nodal expansion of g gives (5.1). Finally, the number N is exactly the number of vertices of the refined triangulation, and the local polygonal complexity of each Hν is controlled by the valence structure of that triangulation. Thus both quantities are bounded in terms of the chosen quantitative CPwL description of g together with the fixed support window. Remark 5.2. The bound on N in Proposition 5.1 depends in general on geometric scale as well as combinatorics: a function may be simple in terms of affine pieces but still require many atoms if its support is large relative to the unit-square atom size.
5.2
Translation covariance
The homogeneous operator enjoys the obvious translation covariance. This is the mechanism that allows us to treat translated special atoms term by term. Lemma 5.3 (Translation covariance). Let δ = (δ1 , δ2 ) ∈ R2 , and define gδ (z) := g(z − δ) for z ∈ R2 . Then for every n ≥ 1, we have V n gδ (z) = V n g (z − 2−n δ),
z ∈ R2 .
(5.2)
Proof. Writing z = (x, y) and δ = (δ1 , δ2 ), we have (V gδ )(x, y) =
X
cj,k gδ (2x − j, 2y − k)
(j,k)∈Z2
=
X
cj,k g(2x − j − δ1 , 2y − k − δ2 )
(j,k)∈Z2
= (V g) x −
δ1 δ2 ,y− . 2 2
Iterating this relation proves the general identity.
5.3
Proof of the main theorem
We can now deduce the full theorem. Proof of Theorem 1.1. Let g : R2 → R be compactly supported and CPwL, with supp g ⊂ [0, L1 ] × [0, L2 ]. By Proposition 5.1, there exist an integer N ≥ 1, coefficients a1 , . . . , aN ∈ R, translation vectors δ1 , . . . , δN ∈ R2 , and special atoms H1 , . . . , HN such that g(z) =
N X
aν Hν (z − δν ).
ν=1
Since V is linear, it follows that n
V g(z) =
N X
aν V n Hν ( · − δν ) (z).
ν=1
20
Fix one term. By Lemma 5.3, we have V n Hν ( · − δν ) (z) = V n Hν (z − 2−n δν ).
On the other hand, Theorem 4.5 gives constants C0,ν , C1,ν > 0 depending only on the fixed support window, the mask support, and the local complexity of Hν , such that V n Hν ∈ ΥC0,ν ,C1,ν n (ReLU; 2, 1),
n ≥ 1.
By the closure property in Remark 2.1(iii), the translated function z 7→ V n Hν (z − 2−n δν ) also belongs to a class ΥCe ,Ce n (ReLU; 2, 1) with constants depending only on the same fixed data. 0,ν 1,ν Since the number of summands N is finite and independent of n, we may run all these networks in parallel and then sum them. By Remark 2.1(ii), this enlarges the width by only a constant factor depending on N and the atom complexities, while preserving the linear depth growth. Therefore there exist constants C0 , C1 > 0, depending only on the mask support, the preserved support window, and the quantitative CPwL complexity of g, such that V n g ∈ ΥC0 ,C1 n (ReLU; 2, 1) for n ≥ 1. This establishes Theorem 1.1.
Remark 5.4. The proof of Theorem 1.1 separates naturally into two layers. Section 4 contains the core multivariate construction, combining the exact torus controller, the four-branch scalar readout, the selector matrices, the recursive block, and the clamped gluing to prove the special-atom theorem. Section 5 then passes to arbitrary compactly supported CPwL seeds by combining that theorem with the finite special-atom decomposition, translation covariance, and finite summation.
6
Conclusions and outlook
We have proved an exact ReLU realization theorem for two-dimensional tensor-product dyadic scalar refinement iterates. Under a fixed support-window hypothesis, every compactly supported CPwL seed g : R2 → R gives rise to iterates V n g that admit exact ReLU realizations of fixed width and depth O(n). This provides a first genuinely two-dimensional extension of the exact realization theory for refinement cascades. The main new ingredient is the exact torus controller for the residual dynamics. In the onedimensional loop-controller framework, the residual orbit is transported by an exact forward state on a polygonal loop. In the present tensor-product setting, the natural controller space is the product of two such loops. Thus the forward residual transport remains exact, while the remaining seam ambiguity is confined to the terminal readout and selector stage. The genuinely new multivariate work then lies in the geometric part of the construction: the digit-pair selectors, the use of compactly supported interior atoms, and the gluing of squarewise realizations on the support window. The tensor-product dyadic case is, in our view, the right first multivariate setting. Its residual dynamics is still coordinatewise, so the controller architecture is a direct product of one-dimensional loop controllers. At the same time, the proof identifies a controller mechanism that should extend more broadly: exact forward transport of the residual state, seam resolution by complementary readouts, selector-driven propagation of the finite-dimensional cascade, and final patch gluing on the support window. Several extensions therefore appear to be natural continuations of the present result. One class consists of tensor-product dilations in higher dimension, with diagonal expansion matrix D = diag(M1 , . . . , Md ),
21
Mi ≥ 2.
There the residual dynamics is again coordinatewise, so one expects the controller space to be a product of one-dimensional loop controllers, with the new work lying mainly in the combinatorics of the selector branches and the higher-dimensional gluing. A second class consists of vector-valued outputs, where the same controller idea should interact with block transition matrices much as in the one-dimensional homogeneous vector-valued theory. A third class consists of certain non-diagonal expanding matrices for which Ap = D for some p ≥ 1 and some diagonal matrix D. In such situations it is natural to expect that the refinement dynamics can be organized in blocks of length p, reducing the residual transport after finitely many steps to a diagonal one. This includes quincunx-type examples among the most natural cases to examine. We do not pursue these broader settings here. Each would require additional notation, charting, and bookkeeping, and in some cases a dedicated exposition would be preferable to a compressed treatment appended to the present paper. Nevertheless, the present theorem should be viewed not only as a complete result in the scalar two-dimensional dyadic case, but also as a foundational multivariate instance of the loop-controller method, with higher-dimensional diagonal, vector-valued, and partially reducible non-diagonal settings as next steps built on the same underlying idea.
References [1] R. DeVore, B. Hanin, and G. Petrova, Neural Network Approximation, Acta Numerica 30 (2021), 327–444. [2] I. Daubechies, R. DeVore, N. Dym, S. Faigenbaum-Golovin, S. Z. Kovalsky, K.-C. Lin, J. Park, G. Petrova, and B. Sober, Neural Network Approximation of Refinable Functions, IEEE Trans. Inform. Theory 69 (2023), no. 1, 482–495. [3] B. Bolorkhuu and T. Gantumur, Exact loop controllers for ReLU realization of homogeneous curve refinements, arXiv:2605.01655, 2026. [4] J. He, L. Li, J. Xu, and C. Zheng, ReLU deep neural networks and linear finite elements, J. Comput. Math. 38 (2020), no. 3, 502–527.
22