WorksEngineering
Toward a Lean Formalization of Analog Computing with Microwaves
Abstract
Analog computing with microwave signals can perform linear transformations directly in the analog domain, as the signals propagate through a microwave network. A fundamental question is which transformations can be computed with a given set of microwave components. In our previous work, we answered this question for networks of hybrid couplers and phase shifters by deriving a necessary and sufficient condition on the transformations these networks can compute, and we showed that the discrete Fourier transform (DFT) satisfies it. In this paper, we take a first step toward the formalization of analog computing with microwaves in Lean, a programming language and proof assistant that is increasingly adopted in mathematics. We formalize the considered components, their series and parallel connections, and the class of networks they can implement. Then, we formally prove the necessary and sufficient condition characterizing these networks, as well as the implementability of the DFT of any size power of two. All proofs are checked by the Lean kernel, and the code is openly available at: https://github.com/matteonerini/formalizing-analog-computing.
Introduction
A fundamental problem in analog computing is to characterize all the functions that can be computed with a specific physical system. In a seminal work, Claude Shannon addressed this problem for the differential analyzer, the mechanical analog computer built by Vannevar Bush at MIT, and showed which functions it could generate [1]. Characterizations of this kind make it possible to understand what a class of analog computers can and cannot do.
The same problem has recently gained relevance for analog computing with microwaves, which is emerging as a complement to digital computing for latency- and energy-critical applications [2], [3], [4], [5], [6]. In general, linear microwave networks can compute a matrix-vector product as the input signals propagate through them, without any digital operation [7]. These networks, denoted as microwave linear analog computers (MiLACs), can compute specific linear transformations that depend on the components they are built from. In [8], we characterized all the linear transformations computable by MiLACs made of hybrid couplers and phase shifters, through a necessary and sufficient condition, and we showed that they include the DFT, Hadamard, and Haar transforms.
This work has been supported in part by UKRI under Grant EP/Y004086/1, EP/X040569/1, EP/Y037197/1, EP/X04047X/1, EP/Y037243/1.
Results of this kind are valid over all the networks, of any size and topology, that can be made from the given components. Therefore, they cannot be confirmed by simulations or measurements, which can only test individual networks. This makes analog computing a natural target for formalization, i.e., for writing definitions and proofs in a proof assistant, whose kernel checks every logical step. Formalization is gaining momentum in mathematics, where proof assistants such as Lean [9] are being used to verify major results [10], increasingly with the help of artificial intelligence (AI) (see the Navier-Stokes Millennium Prize Problem [11]). Beyond verification, formalization can accelerate research by turning known results into a machine-readable body of knowledge, on which new results can be reliably built.
In this paper, we take a first step toward the formalization of analog computing with microwaves by formalizing in Lean the results of [8]. Our contributions are as follows. First, we formalize the definitions of hybrid couplers, phase shifters, their series and parallel connections, and the class of networks they can implement (§ 3). Second, we formally prove the necessary and sufficient condition characterizing these networks (§ 4). Third, we formally prove that the DFT of any size power of two is implementable with hybrid couplers and phase shifters (§ 5). The complete Lean code is openly available, and all proofs are checked by the Lean kernel. To the best of our knowledge, this is the first formalization of analog computing with microwave networks.
Analog Computing with Hybrid Couplers and Phase Shifters
In this section, we recall the MiLAC model and characterize the networks that can be built with hybrid couplers and phase shifters, as derived in [8].
A MiLAC is a -port linear microwave network, where the first ports are the input ports and the last ports are the output ports. The input ports are driven by voltage sources with series impedance , e.g., , while the output voltages are read at the output ports by probes with input impedance . The -port MiLAC network can be characterized by its scattering matrix [12 Chapter 4], partitioned as
where , for . Following circuit theory [8 Section II], the output of the MiLAC is , i.e., it is a linear function of the input depending on the block . Thus, characterizing the functions computable by a MiLAC built from given components corresponds to characterizing the blocks that these components can realize.
Hybrid Couplers and Phase Shifters
We consider two fundamental microwave components, hybrid couplers and phase shifters, together with two components needed to interconnect them: interconnections and permutation networks.
Definition 1. An interconnection is a 2-port network with scattering matrix
Definition 2. A phase shifter with phase is a 2-port network with scattering matrix
Definition 3. A permutation network reordering the signals at ports according to the permutation matrix is a -port network with scattering matrix
Definition 4. A hybrid coupler is a 4-port network with scattering matrix
All four components are lossless and reciprocal, since their scattering matrices are unitary and symmetric. In addition, all of them are such that and , i.e., there is no reflection at their ports. We refer to a -port network with this property as a matched network. When matched networks are also reciprocal, i.e., their scattering matrix is symmetric, they are fully characterized by their block, which we denote as the transmission scattering matrix [8 Section III]. A hybrid coupler has transmission scattering matrix , a phase shifter , an interconnection , and a permutation network . Since , a MiLAC implemented with a matched network computes .
More complex networks are obtained by connecting networks in series and in parallel. Two networks are connected in series when the output ports of the first are connected to the input ports of the second, and in parallel when their input and output ports become the input and output ports of a larger network, respectively. The series and parallel of matched networks are matched networks whose transmission scattering matrices have a simple expression [8 Corollaries 1, 2], as follows, which we adopt as definitions.
Definition 5. The series of two reciprocal matched networks with transmission scattering matrices and is a reciprocal matched network with transmission scattering matrix
Definition 6. The parallel of two reciprocal matched networks with transmission scattering matrices and is a reciprocal matched network with transmission scattering matrix
The networks that can be built from the four components are then defined inductively, as follows.
Definition 7. A network is implementable with hybrid couplers and phase shifters if any of the following statements are true
The network is an interconnection,
The network is a phase shifter,
The network is a permutation network,
The network is a hybrid coupler,
The network is a series of two networks, both implementable with hybrid couplers and phase shifters,
The network is a parallel of two networks, both implementable with hybrid couplers and phase shifters.
Characterization of Implementable Networks
The following theorem, which is the main result of [8], characterizes all networks implementable with hybrid couplers and phase shifters, and hence all the linear transformations that a MiLAC made of these components can compute.
Theorem 1. A network is implementable with hybrid couplers and phase shifters if and only if it is a reciprocal matched network with transmission scattering matrix that can be decomposed as
where is a permutation matrix, for , and is a block diagonal matrix, for , partitioned as
where , for , and is given by
with and , for , where .
Proof. Please, refer to [8 Section IV].
Theorem 1 was used in [8] to show that the DFT, Hadamard, and Haar matrices are implementable with hybrid couplers and phase shifters for any power of two. In the following, we formalize all the above definitions and Theorem 1 in Lean, together with the implementability of the DFT. The complete code is available in the repository linked in the abstract.
Lean Formalization: Definitions
Lean is a functional programming language and a proof assistant, in which mathematical statements can be written and their proofs verified by a trusted kernel [9]. Our formalization builds on Mathlib [13], the Lean library that provides widely used mathematical concepts such as matrices, permutations, and the complex exponential. To trust that the proofs are correct, a reader does not need to check them, but only that the definitions and the statements of the theorems presented in the following capture the intended concepts. The keyword noncomputable only indicates that a definition involves real numbers or the complex exponential, which Lean cannot evaluate exactly, and has no effect on the proofs.
We define a network as an complex matrix. Physically, this matrix represents the transmission scattering matrix of the microwave network having input and output ports. Since all the considered components are reciprocal matched networks, and reciprocal matched networks are closed under series and parallel connections, the transmission scattering matrix is sufficient to describe all the networks of interest. The following abbreviation is therefore used throughout the whole Lean script, simply meaning that a network is an complex matrix.
abbrev Network (n : N) :=
Matrix (Fin n) (Fin n) C
An interconnection is defined as the matrix .
def interconnection : Network 1 :=
1
A phase shifter is defined as the matrix .
noncomputable def phaseShifter (ϕ : R) :
Network 1 :=
fun _ _ => Complex.exp (ϕ * Complex.I)
Note that the phase shift is any real number, rather than being restricted to . This is without loss of generality, since is -periodic. A permutation network is defined as an permutation matrix, constructed by Mathlib from a permutation of the ports.
def permutationNetwork {n : N}
(σ : Equiv.Perm (Fin n)) : Network n :=
Equiv.Perm.permMatrix (R := C) σ
A hybrid coupler is defined as the matrix .
noncomputable def hybridCoupler : Network 2 :=
(1 / Real.sqrt 2 : C) · !![Complex.I, 1;
1, Complex.I]
The series of two networks A and B with input and output ports, where A is followed by B, is defined as the matrix product , following Definition 5.
def series {n : N} (A B : Network n) :
Network n :=
B * A
The parallel of a network A with input and output ports and a network B with input and output ports is defined as their block diagonal matrix, following Definition 6.
def parallel {n m : N} (A : Network n)
(B : Network m) : Network (n + m) :=
Matrix.reindex finSumFinEquiv finSumFinEquiv
(Matrix.fromBlocks A 0 0 B)
The notion of implementable network in Definition 7 is formalized as an inductive predicate Implementable, with one constructor for each of its six statements. A network is implementable if and only if it can be obtained by applying these six rules a finite number of times.
inductive Implementable : {n : N} → Network n
→ Prop where
| ic : Implementable interconnection
| ps (ϕ : R) : Implementable
(phaseShifter ϕ)
| pn {n : N} (σ : Equiv.Perm (Fin n)) :
Implementable (permutationNetwork σ)
| hc : Implementable hybridCoupler
| series {n : N} {A B : Network n} :
Implementable A → Implementable B →
Implementable (series A B)
| parallel {n m : N}
{A : Network n} {B : Network m} :
Implementable A → Implementable B →
Implementable (parallel A B)
Since this definition is inductive, a property can be proved for all implementable networks by induction, i.e., by proving it for the four components and showing that it is preserved by series and parallel connections. This is the key tool in the proof of Theorem 1.
Lean Formalization: Main Result
We begin by defining as layered a network that satisfies the condition in Theorem 1. This is done by first introducing more basic building blocks. The first building block is the diagonal matrix of phases
representing phase shifters in parallel, which is defined as follows.
noncomputable def phaseDiagonal {n : N}
(ϕ : Fin n → R) : Network n :=
Matrix.diagonal (fun i =>
Complex.exp (ϕ i * Complex.I))
The second building block is the block in (8), i.e.,
which depends on three parameters , , and , and is defined as follows.
noncomputable def block (θ₁₁ θ₁₂ θ₂₁ : R) :
Network 2 :=
(1 / Real.sqrt 2 : C) · !![
Complex.exp (θ₁₁ * Complex.I),
Complex.exp (θ₁₂ * Complex.I);
Complex.exp (θ₂₁ * Complex.I),
Complex.exp ((Real.pi - θ₁₁ + θ₁₂ + θ₂₁)
* Complex.I)]
These two building blocks are combined into the block diagonal matrix in (7), made of blocks (10) and phases, which is a network with input and output ports. The blocks are assembled with Mathlib’s Matrix.blockDiagonal, and placed in parallel with the diagonal matrix of phases.
noncomputable def blockDiagonal {C S : ℕ}
(θ₁₁ θ₁₂ θ₂₁ : Fin C → ℝ) (ϕ : Fin S → ℝ) :
Network (2 * C + S) :=
parallel (Matrix.reindex finProdFinEquiv
finProdFinEquiv (Matrix.blockDiagonal
fun c => block (θ₁₁ c) (θ₁₂ c) (θ₂₁ c)))
(phaseDiagonal ϕ)
Note that, with this indexing, the two ports of the th block are and , rather than two adjacent ports as in (7). The two orderings differ by a permutation, which is absorbed by the adjacent permutation matrices, so the set of matrices of the form (6) is unchanged.
A layer of the decomposition (6) is described by the structure Layer, which collects the number of blocks , the number of phases , the parameters of the blocks and the phases, the constraint , and the permutation defining .
structure Layer (n : ℕ) where
C : ℕ
S : ℕ
θ₁₁ : Fin C → ℝ
θ₁₂ : Fin C → ℝ
θ₂₁ : Fin C → ℝ
ϕ : Fin S → ℝ
size : 2 * C + S = n
σ : Equiv.Perm (Fin n)
Finally, the product in (6) is defined recursively from the initial permutation , defining , and a list of layers, ordered from down to 1. An empty list gives , while a list with head gives multiplied by the product of the remaining layers. The number of layers is the length of the list.
noncomputable def layered {n : ℕ}
(σ₀ : Equiv.Perm (Fin n)) :
List (Layer n) → Network n
| [] => permutationNetwork σ₀
| layer :: layers =>
permutationNetwork layer.σ *
Matrix.reindex (finCongr layer.size)
(finCongr layer.size)
(blockDiagonal layer.θ₁₁ layer.θ₁₂
layer.θ₂₁ layer.ϕ) * layered σ₀ layers
The sufficient condition of Theorem 1 states that any layered network is implementable.
theorem implementable_if_layered {n : ℕ}
(σ₀ : Equiv.Perm (Fin n))
(layers : List (Layer n)) :
Implementable (layered σ₀ layers) := by
...
The statement of this sufficient condition is followed by the keyword := by, after which Lean expects the proof. This proof is omitted here for brevity, but it can be found in the GitHub repository, where it has been checked by Lean. As in [8 Section IV-A], the key step is that each block (10) is a series of three implementable networks, i.e., the parallel of a phase shifter and an interconnection, a hybrid coupler, and the parallel of two phase shifters. Then, the diagonal matrix of phases (9) is shown to be implementable by induction on , and consequently also the block diagonal matrix is implementable. Finally, a layered network is shown to be implementable, using the fact that the series of implementable networks is implementable, and that permutation networks are implementable.
The necessary condition of Theorem 1 states that any implementable network is layered.
theorem implementable_only_if_layered {n : ℕ}
{S : Network n} (hS : Implementable S) :
∃ σ₀ : Equiv.Perm (Fin n),
∃ layers : List (Layer n),
S = layered σ₀ layers := by
...
Also for this theorem we omit the proof after the keyword := by, but it can be found in the GitHub repository, where it has been checked by Lean. In [8 Section IV-B], this is proved by dividing a generic network into subnetworks, each containing hybrid couplers and phase shifters in parallel between two permutation networks. This argument is intuitive, but it is not directly expressed in terms of Definition 7. The Lean proof is instead by induction on Definition 7, and considers the six cases separately.
A phase shifter is a layered network with a single layer containing one phase and no blocks.
An interconnection is a layered network since it is a phase shifter with zero phase.
A permutation network is a layered network with only and no layers.
A hybrid coupler is a layered network with a single layer containing the block (10) with and .
The series of two layered networks is layered, since their layers can be concatenated, merging the last permutation matrix of the first network with the first permutation matrix of the second into a single permutation matrix.
The parallel of two layered networks A and B is layered, since it can be written as the series of the parallel of A with an identity and the parallel of an identity with B. The parallel of a layered network with an identity is layered, since each of its layers can be extended with zero phases, i.e., interconnections.
By combining the sufficient and necessary conditions, we obtain Theorem 1 in Lean, which states that a network is implementable if and only if it is layered.
theorem implementable_iff_layered {n : N}
{S : Network n} :
Implementable S ↔
∃ σ0 : Equiv.Perm (Fin n),
∃ layers : List (Layer n),
S = layered σ0 layers := by
constructor
· exact implementable_only_if_layered
· rintro ⟨ σ0 , layers, rfl⟩
exact implementable_if_layered σ0 layers
The theorem holds for any number of ports and any number of layers , and its proof is certified by the Lean kernel.
Lean Formalization: Implementing the DFT
We now formalize the proof that the DFT can be computed by a MiLAC made of hybrid couplers and phase shifters, i.e., that the DFT matrix is implementable for any power of two [8 Corollary 3]. The DFT matrix is defined as
for , where . Note that the indices start from 0 here, in agreement with Lean.
noncomputable def dft (N : N) : Network N :=
fun i k => (1 / Real.sqrt N : C) *
Complex.exp (-2 * Real.pi * Complex.I *
(i : N) * (k : N) / N)
The following theorem states that the DFT matrix is implementable, for any .
theorem implementable_dft (L : N) :
Implementable (dft (2 ^ L)) := by
...
In [8 Section V], this result is obtained by deriving a decomposition of of the form (6). The Lean proof instead proceeds by induction on , following the radix-2 structure of the fast Fourier transform (FFT). For , is an interconnection. For the inductive step, the DFT matrix is shown to be, up to a permutation of its input ports and a permutation of its output ports, the series of two DFT matrices in parallel, followed by butterfly matrices in parallel, for , where . Each butterfly matrix is a block (10) with suitable phases, and is therefore implementable. The two smaller DFT matrices are implementable by the induction hypothesis, and the permutations of the input and output ports are implemented by two permutation networks, which concludes the proof. By Theorem 1, implementable_dft also guarantees that admits a decomposition of the form (6), although it does not identify the specific matrices and given in [8 Proposition 3].
Acknowledgment
The authors used Claude (Anthropic) to assist in developing the Lean code, whose proofs are all checked by the Lean kernel. The authors also thank the Mathlib community for developing and maintaining the Mathlib library [13], on which this formalization builds.
Conclusion
We have presented a first formalization of analog computing with microwaves in Lean. We have formalized hybrid couplers, phase shifters, interconnections, and permutation networks, together with their series and parallel connections, and the class of linear transforms they can compute. Specifically, we have formally proved the necessary and sufficient condition characterizing these transforms, derived in [8], and the implementability of the DFT of any size power of two.
This work opens several directions for future research. First, the implementability of the Hadamard and Haar transforms [8], and maybe other transforms, can be formalized. Second, the scattering matrices of generic networks (not necessarily matched) and their series and parallel connections can be formalized. Third, other microwave components can be included to characterize the functions they can compute. Fourth, the formalized results can be used to automatically generate verified designs of microwave networks computing a desired transformation.
References
- [1]C. E. Shannon, “Mathematical theory of the differential analyzer,” Journal of Mathematics and Physics, vol. 20, no. 1-4, pp. 337–354, 1941.
- [2]C. Caloz, S. Gupta, Q. Zhang, and B. Nikfal, “Analog signal processing: A possible alternative or complement to dominantly digital radio schemes,” IEEE Microw. Mag., vol. 14, no. 6, pp. 87–103, 2013.arxiv.org/abs/1307.2618
- [3]A. Silva, F. Monticone, G. Castaldi, V. Galdi, A. Alù, and N. Engheta, “Performing mathematical operations with metamaterials,” Science, vol. 343, no. 6167, pp. 160–163, 2014.DOI
- [4]F. Zangeneh-Nejad, D. L. Sounas, A. Alù, and R. Fleury, “Analogue computing with metamaterials,” Nature Reviews Materials, vol. 6, no. 3, pp. 207–225, 2021.
- [5]D. Dardari, G. Torcolacci, G. Pasolini, and N. Decarli, “Over-the-air electromagnetic signal processing: From fundamentals to emerging paradigms,” IEEE Signal Process. Mag., vol. 43, no. 1, pp. 6–28, 2026.DOI
- [6]P. de Hougne, M. D. Renzo, A. Alù, T. Jun Cui, Y. Eldar, N. Engheta, W. Hu, and A. Ozcan, “Programmable wave-domain computing in wireless communications,” Feb. 2026, working paper or preprint. [Online]. Available: https://hal.science/hal-05487878
- [7]M. Nerini and B. Clerckx, “Analog computing for signal processing and communications – Part I: Computing with microwave networks,” IEEE Trans. Signal Process., vol. 73, pp. 5183–5197, 2025.arxiv.org/abs/2504.06790
- [8]M. Nerini, X. Liu, and B. Clerckx, “Analog computing with hybrid couplers and phase shifters,” IEEE Trans. Microw. Theory Tech., vol. 74, no. 9, pp. 8039–8061, 2026.arxiv.org/abs/2603.24604
- [9]L. de Moura and S. Ullrich, “The Lean 4 theorem prover and programming language,” in Automated Deduction – CADE 28: 28th International Conference on Automated Deduction, Virtual Event, July 12–15, 2021, Proceedings. Berlin, Heidelberg: Springer-Verlag, 2021, p. 625–635.DOI
- [10]K. Buzzard and R. Taylor, “Towards a lean proof of fermat’s last theorem,” URL https://imperialcollegelondon.github.io/FLT/blueprint.pdf, 2025.
- [11]OpenAI, “Finite time blowup for navier-stokes,” 2026. [Online]. Available: https://openai.com/index/navier-stokes-solution
- [12]D. M. Pozar, Microwave engineering, 4th ed. John wiley & sons, 2012.
- [13]The mathlib Community, “The Lean Mathematical Library,” in Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs, ser. CPP 2020. New Orleans, LA, USA: ACM, Jan. 2020.DOI