betaFeedback

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 2N2N-port linear microwave network, where the first NN ports are the input ports and the last NN ports are the output ports. The NN input ports are driven by voltage sources u∈CN×1\mathbf{u} \in\mathbb{C}^{N \times1} with series impedance Z0Z_0, e.g., Z0=50 ΩZ_0 = 50~\Omega, while the output voltages v∈CN×1\mathbf{v} \in\mathbb{C}^{N \times1} are read at the NN output ports by probes with input impedance Z0Z_0. The 2N2N-port MiLAC network can be characterized by its scattering matrix S∈C2N×2N\mathbf{S} \in\mathbb{C}^{2N \times2N} [12 Chapter 4], partitioned as

S=[S11S12S21S22],(1)\mathbf{S} = \begin{bmatrix} \mathbf{S}_{11} & \mathbf{S}_{12} \\ \mathbf{S}_{21} & \mathbf{S}_{22} \end{bmatrix}, \tag*{(1)}

where SXY∈CN×NS_{XY} \in\mathbb{C}^{N \times N}, for X,Y∈{1,2}X,Y \in\{1,2\}. Following circuit theory [8 Section II], the output of the MiLAC is v=S21u/2\mathbf{v}=S_{21}\mathbf{u}/2, i.e., it is a linear function of the input depending on the block S21S_{21}. Thus, characterizing the functions computable by a MiLAC built from given components corresponds to characterizing the blocks S21S_{21} 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

S=[0110].(2)S=\begin{bmatrix}0&1\\1&0\end{bmatrix}. \tag*{(2)}

Definition 2. A phase shifter with phase ϕ∈[0,2π)\phi\in[0,2\pi) is a 2-port network with scattering matrix

S=[0ejϕejϕ0].(3)S=\begin{bmatrix}0&e^{j\phi}\\e^{j\phi}&0\end{bmatrix}. \tag*{(3)}

Definition 3. A permutation network reordering the signals at NN ports according to the permutation matrix P∈{0,1}N×NP \in\{0,1\}^{N\times N} is a 2N2N-port network with scattering matrix

S=[0PTP0].(4)S=\begin{bmatrix}0&P^{T}\\P&0\end{bmatrix}. \tag*{(4)}

Definition 4. A hybrid coupler is a 4-port network with scattering matrix

S=12[00j1001jj1001j00].(5)S=\frac{1}{\sqrt{2}} \begin{bmatrix} 0&0&j&1\\ 0&0&1&j\\ j&1&0&0\\ 1&j&0&0 \end{bmatrix}. \tag*{(5)}

All four components are lossless and reciprocal, since their scattering matrices are unitary and symmetric. In addition, all of them are such that S11=0S_{11}=0 and S22=0S_{22}=0, i.e., there is no reflection at their ports. We refer to a 2N2N-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 S21S_{21} block, which we denote as the transmission scattering matrix Sˉ∈CN×N\bar{S} \in\mathbb{C}^{N\times N} [8 Section III]. A hybrid coupler has transmission scattering matrix Sˉ=[[j,1]T,[1,j]T]/2\bar{S}=[[j,1]^{T},[1,j]^{T}]/\sqrt{2}, a phase shifter sˉ=ejϕ\bar{s}=e^{j\phi}, an interconnection sˉ=1\bar{s}=1, and a permutation network Sˉ=P\bar{S}=P. Since v=S21u/2\mathbf{v}=S_{21}\mathbf{u}/2, a MiLAC implemented with a matched network computes v=Sˉu/2\mathbf{v}=\bar{S}\mathbf{u}/2.

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 Qˉ\bar{Q} and Rˉ\bar{R} is a reciprocal matched network with transmission scattering matrix

Sˉ=RˉQˉ.\bar{S}=\bar{R}\bar{Q}.

Definition 6. The parallel of two reciprocal matched networks with transmission scattering matrices Qˉ\bar{Q} and Rˉ\bar{R} is a reciprocal matched network with transmission scattering matrix

Sˉ=diag⁡(Qˉ,Rˉ).\bar{S}=\operatorname{diag}(\bar{Q},\bar{R}).

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

  1. The network is an interconnection,

  2. The network is a phase shifter,

  3. The network is a permutation network,

  4. The network is a hybrid coupler,

  5. The network is a series of two networks, both implementable with hybrid couplers and phase shifters,

  6. 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 Sˉ∈CN×N\bar{S} \in\mathbb{C}^{N\times N} that can be decomposed as

Sˉ=PLDL⋯P2D2P1D1P0,(6)\bar{S}=P_{L}D_{L}\cdots P_{2}D_{2}P_{1}D_{1}P_{0}, \tag*{(6)}

where Pℓ∈CN×NP_{\ell} \in\mathbb{C}^{N\times N} is a permutation matrix, for ℓ=0,…,L\ell=0,\ldots,L, and Dℓ∈CN×ND_{\ell} \in\mathbb{C}^{N\times N} is a block diagonal matrix, for ℓ=1,…,L\ell=1,\ldots,L, partitioned as

Dℓ=diag⁡(Dℓ,1,…,Dℓ,Cℓ,ejϕℓ,1,…,ejϕℓ,Sℓ),(7)D_{\ell}=\operatorname{diag}\left(D_{\ell,1},\ldots,D_{\ell,C_{\ell}},e^{j\phi_{\ell,1}},\ldots,e^{j\phi_{\ell,S_{\ell}}}\right), \tag*{(7)}

where ϕℓ,s∈[0,2π)\phi_{\ell,s} \in[0,2\pi), for s=1,…,Sℓs=1,\ldots,S_{\ell}, and Dℓ,c∈C2×2D_{\ell,c} \in\mathbb{C}^{2\times2} is given by

Dℓ,c=12[ejθℓ,c,11ejθℓ,c,12ejθℓ,c,21ejθℓ,c,22],(8)D_{\ell,c}=\frac{1}{\sqrt{2}} \begin{bmatrix} e^{j\theta_{\ell,c,11}}&e^{j\theta_{\ell,c,12}}\\ e^{j\theta_{\ell,c,21}}&e^{j\theta_{\ell,c,22}} \end{bmatrix}, \tag*{(8)}

with θℓ,c,11,θℓ,c,12,θℓ,c,21∈[0,2π)\theta_{\ell,c,11},\theta_{\ell,c,12},\theta_{\ell,c,21} \in[0,2\pi) and θℓ,c,22=π−θℓ,c,11+θℓ,c,12+θℓ,c,21\theta_{\ell,c,22}=\pi-\theta_{\ell,c,11}+\theta_{\ell,c,12}+\theta_{\ell,c,21}, for c=1,…,Cℓc=1,\ldots,C_{\ell}, where 2Cℓ+Sℓ=N2C_{\ell}+S_{\ell}=N.

Proof. Please, refer to [8 Section IV].

Theorem 1 was used in [8] to show that the N×NN\times N DFT, Hadamard, and Haar matrices are implementable with hybrid couplers and phase shifters for any NN 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 n×nn \times n complex matrix. Physically, this matrix represents the transmission scattering matrix of the microwave network having nn input and nn 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 n×nn \times n complex matrix.

abbrev Network (n : N) :=
  Matrix (Fin n) (Fin n) C

An interconnection is defined as the 1×11 \times1 matrix 11.

def interconnection : Network 1 :=
  1

A phase shifter is defined as the 1×11 \times1 matrix ejϕe^{j\phi}.

noncomputable def phaseShifter (ϕ : R) :
  Network 1 :=
  fun _ _ => Complex.exp (ϕ * Complex.I)

Note that the phase shift ϕ\phi is any real number, rather than being restricted to [0,2π)[0, 2\pi). This is without loss of generality, since ejϕe^{j\phi} is 2π2\pi-periodic. A permutation network is defined as an n×nn \times n permutation matrix, constructed by Mathlib from a permutation σ\sigma 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 2×22 \times2 matrix 12[j11j]\frac{1}{\sqrt{2}} \left[\begin{smallmatrix}j&1\\1&j\end{smallmatrix}\right].

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 nn input and output ports, where A is followed by B, is defined as the matrix product B∗AB * A, following Definition 5.

def series {n : N} (A B : Network n) :
  Network n :=
  B * A

The parallel of a network A with nn input and output ports and a network B with mm 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

diag⁡(ejϕ1,…,ejϕn),(9)\operatorname{diag}(e^{j\phi_1}, \ldots, e^{j\phi_n}), \tag*{(9)}

representing nn 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 2×22 \times2 block in (8), i.e.,

12[ejθ11ejθ12ejθ21ej(π−θ11+θ12+θ21)],(10)\frac{1}{\sqrt{2}} \begin{bmatrix} e^{j\theta_{11}} & e^{j\theta_{12}} \\ e^{j\theta_{21}} & e^{j(\pi-\theta_{11}+\theta_{12}+\theta_{21})} \end{bmatrix}, \tag*{(10)}

which depends on three parameters θ11\theta_{11}, θ12\theta_{12}, and θ21\theta_{21}, 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 DℓD_\ell in (7), made of CC blocks (10) and SS phases, which is a network with 2C+S2C + S input and output ports. The CC 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 ccth block are cc and C+cC + c, 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 PℓDℓP_\ell D_\ell of the decomposition (6) is described by the structure Layer, which collects the number of blocks CℓC_\ell, the number of phases SℓS_\ell, the parameters of the CℓC_\ell blocks and the SℓS_\ell phases, the constraint 2Cℓ+Sℓ=n2C_\ell+ S_\ell= n, and the permutation σ\sigma defining PℓP_\ell.

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 PLDL⋯P1D1P0P_LD_L \cdots P_1D_1P_0 in (6) is defined recursively from the initial permutation σ0\sigma_0, defining P0P_0, and a list of layers, ordered from LL down to 1. An empty list gives P0P_0, while a list with head PℓDℓP_\ell D_\ell gives PℓDℓP_\ell D_\ell multiplied by the product of the remaining layers. The number of layers LL 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 nn, and consequently also the block diagonal matrix DℓD_\ell 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 LL 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.

  1. A phase shifter is a layered network with a single layer containing one phase and no blocks.

  2. An interconnection is a layered network since it is a phase shifter with zero phase.

  3. A permutation network is a layered network with only P0P_0 and no layers.

  4. A hybrid coupler is a layered network with a single layer containing the block (10) with θ11=π/2\theta_{11} = \pi/2 and θ12=θ21=0\theta_{12} = \theta_{21} = 0.

  5. 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.

  6. 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 nn and any number of layers LL, 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 N×NN \times N DFT matrix is implementable for any NN power of two [8 Corollary 3]. The N×NN \times N DFT matrix is defined as

[FN]i,k=1Nωik,(11)[F_N]_{i,k} = \frac{1}{\sqrt{N}}\omega^{ik}, \tag*{(11)}

for i,k=0,…,N−1i,k = 0,\ldots,N-1, where ω=e−j2π/N\omega= e^{-j2\pi/N}. 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 2L×2L2^L \times2^L DFT matrix is implementable, for any L∈NL \in\mathbb{N}.

theorem implementable_dft (L : N) :
    Implementable (dft (2 ^ L)) := by
  ...

In [8 Section V], this result is obtained by deriving a decomposition of FN\mathbf{F}_N of the form (6). The Lean proof instead proceeds by induction on LL, following the radix-2 structure of the fast Fourier transform (FFT). For L=0L = 0, F1=1\mathbf{F}_1 = 1 is an interconnection. For the inductive step, the 2L+1×2L+12^{L+1} \times2^{L+1} 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 2L×2L2^L \times2^L DFT matrices in parallel, followed by 2L2^L butterfly matrices [[1,1]T,[ωi,−ωi]T]/2[[1,1]^{T},[\omega^i,-\omega^i]^{T}]/\sqrt{2} in parallel, for i=0,…,2L−1i = 0,\ldots,2^L-1, where ω=e−j2π/2L+1\omega= e^{-j2\pi/2^{L+1}}. 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 F2L\mathbf{F}_{2^L} admits a decomposition of the form (6), although it does not identify the specific matrices Pℓ\mathbf{P}_{\ell} and Dℓ\mathbf{D}_{\ell} 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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [11]OpenAI, “Finite time blowup for navier-stokes,” 2026. [Online]. Available: https://openai.com/index/navier-stokes-solution
  12. [12]D. M. Pozar, Microwave engineering, 4th ed. John wiley & sons, 2012.
  13. [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

Paper details

vlnc:W_gjcaxeu9
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 3

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Engineering

Claude (Anthropic)

View statement
Looking for related papers…
Contents