CS Paper Radar

Toward a Lean Formalization of Analog Computing with Microwaves

Matteo Nerini, Xuekang Liu, Bruno Clerckx

eess.SP cs.ITphysics.app-ph ·submitted 2026-10-03 21:30 UTC · v1
code/dataunusual

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.

Comment
Submitted to IEEE for publication

Closest papers

Nearest neighbours by meaning across the whole index.

Analog and hybrid computing in the 21st century

cs.AI math.DScs.ETnlin.CD ·2026-10-30 ·Bernd Ulmann, Olivier Bournez, Corey J. Maley, Zhong Sun, Grace Li Zhang +17 more
similarity 0.57
Abstract · 31 pages, 11 figures

Analog computers solve problems through physical representations of mathematical variables and relations, often using the dynamics of electronic circuits and their associated signals. Many analog computers directly represent nonlinear dynamical systems; they encode their solutions in the signals that they generate. Although most modern scientific computing relies on digital architectures with inherently discrete-valued representations and algorithmic approaches, the design constraints of such architectures increasingly limit both performance and energy efficiency. Analog systems can circumvent some of these constraints; they execute specific computations very efficiently by mapping them directly onto physical processes using smaller and simpler computing elements than the ones in digital architectures. In this article, we provide an interdisciplinary perspective on modern analog and hybrid (i.e., analog-digital) computing. We discuss how modern scientific computing workflows can leverage analog approaches in various applications, such as in simulating dynamical systems, performing optimization, and enabling more energy-efficient implementations of artificial intelligence.

0.37

An Algebra of Transformers

cs.LO cs.AI ·2026-10-27 ·Yong Wang, Zhiyan Wang, Hexiao Kang
similarity 0.52
Abstract

On the theoretic analyses on transforms, they mainly focus on the computability analysis, such the Turing-completeness of unbounded precision transformers, the advantage of parallelizability of unbounded precision transformers and the limitations of bounded precision transformers. This paper give transformers an algebra for reasoning, which relies heavily on the functional decomposition results of transformers. This algebra uses functional decompositions as atomic actions, includes sequential composition and parallel composition, recursion for feedback and abstraction for hidden layers. As we know, it is the first attempt to model transformers logically and can be used to verify the correctness of transformer based applications.

0.23

On the monitorability of linear-time timed logics

cs.LO ·2026-11-18 ·Mouloud Amara, Mohammed Aristide Foughali, Giovanni Bernardi, Adrian Francalanza, Nicanora Ordoño Wallig
theory similarity 0.50
Abstract

In [10], we solved the monitorability problem for Tlin , a new expressive (linear-time) timed mu-calculus that we proposed. We showed that Tlin is strictly more expressive than MTL, the de facto timed extension of the well-known LTL. Moreover, we identified MTlin , the largest monitorable fragment of Tlin. The maximality of MTlin was proven modulo an expressive monitoring framework called Mon, yet under the assumption of reactivity. Our work in [10] was the first to solve the monitorability problem for such an expressive timed logic, and its theoretical results were accompanied with compilers (i) from MTL to Tlin and (ii) from Tlin formulae to monitors. This paper is an extension of [10] with the following new contributions. First, we generalise the maximality results to arbitrary monitors, which include both reactive and non-reactive monitors. Second, we extend the expressiveness results of Tlin . We completely revise the embedding of MTL into Tlin : we show that the syntax of MTL given in [10] was incomplete, and provide a new compiler from MTL, under its standard syntax with the strict Until operator and negation over arbitrary formulae, into Tlin . In passing, we demonstrate that Tlin is closed under complement and provide a fully syntactic complementation procedure. Moreover, we prove that Tlin is strictly more expressive than TPTL, a popular timed logic more expressive than MTL, and develop an automatic embedding from TPTL to Tlin . This gives Tlin and the machinery around it the power of a unified framework to reason on the monitorability of linear-time timed logics. Accordingly, we identify important monitorable fragments for both MTL and TPTL.

0.18

AxQM: A Textbook-Scale Benchmark for Formal Proof Synthesis in a Library of Finite-Dimensional Quantum Mechanics

cs.AI quant-phcs.LO ·2026-09-04 ·Weichen Winston Yin, Jacob M. Taylor, Dirk R. Englund, Frank H. L. Koppens
benchmarkcode/data similarity 0.50
Abstract · 15 pages, 3 figures. Benchmark available at https://github.com/Axiomatic-AI/AxQM

Formalizing mathematics in a proof assistant, where a machine checks every definition, statement and proof, has set a new standard of rigor. Large language models are now capable of formalizing autonomously, even at the scale of whole textbooks. We bring this standard of rigor to physics, where theoretical arguments carry idealizations that are rarely stated fully, and any logical gaps could have a cascading effect on interdependent results. Recognizing the need to evaluate autoformalization systems for physics, we release AxQM, 1,019 kernel-checkable proof-synthesis tasks over 479 items drawn from the textbook Quantum Computation and Quantum Information by Nielsen and Chuang. The tasks are stated in a custom Lean library of finite-dimensional quantum mechanics. By task count, it is the largest proof-synthesis benchmark in physics by a factor of four. AxQM is derived from a near-complete formalization of the formal portions of the textbook, so every task is guaranteed a solution, which we keep private. Grading of the benchmark is done deterministically by the Lean kernel, which checks that the proof compiles, that no sorry appears in it or in any declaration it depends on, and that it introduces no new axioms.

0.59

Garlene: Guarded Recursion in Lean

cs.LO cs.PL ·2026-09-21 ·Sergei Stepanenko, Patrick Bahr, Rasmus Ejlers Møgelberg
theoryhot direction similarity 0.50
Abstract

Extending the recursion principles of a formal system is an enticing but dangerous endeavour with a well-documented history of leading to consistency bugs. Nakano's guarded recursion is an elegant, type-based approach to soundly extend type theory with a powerful recursion principle. This makes guarded recursion useful for many applications, from programming with infinite structures such as streams to reasoning about advanced programming language features using synthetic guarded domain theory. Sadly, guarded recursion is not directly supported by any major interactive theorem prover, which leaves users of guarded recursion with unmechanised pen-and-paper proofs or mechanisations that depend on unmaintained theorem provers. In this paper, we present an implementation of guarded recursion as an embedded language in Lean consisting of a simply-typed lambda calculus for definitions and a higher-order logic for reasoning. Using Lean's excellent support for metaprogramming, our language allows users to write guarded recursive definitions in an intuitive syntax and to prove properties about them using a dedicated proof mode. We give our language a presheaf model, which we use to prove the soundness of our language and to allow users to export guarded recursive definitions and their theorems into standard Lean developments. To demonstrate the usefulness of our language, we present several case studies for programming and reasoning with guarded recursion.

0.24

Fixing the Fixpoint: A Formal Theory of Convergence Detection for Incremental Recursive Computation

cs.PL cs.DB ·2026-09-30 ·Chengxi Yang, Tej Chajed, Thomas Reps
code/data similarity 0.50
Abstract

Modern incremental computation theories like DBSP have enabled efficient incrementalization of general recursive computations. To do so, they require a runtime Fixpoint Detection (FPD) mechanism to detect whether an iterative computation has reached the fixpoint and thus should terminate. However, we show that the commonly suggested "FirstZero" strategy is unsound even in naturally arising cases, and that exact FPD is impossible for arbitrary DBSP circuits with expressive primitive nodes. This issue reveals a fundamental gap between the mathematical specification and implementations of such theories. To fill this gap, using DBSP as a core calculus, we develop a formal theory of convergence detection. Within this theory, we define internal convergence (IntConv) as a declarative criterion corresponding to the internal-state-stability strategy used by practical implementations, and prove that IntConv is a sufficient condition for external convergence. We then define the state fixpoint (StFP) predicate and a sound and complete StFP detector. Combining the StFP detector with fixed-input and zero-output checks yields a sound and complete IntConv detector. Moreover, for a large class of useful circuits (programs) including Datalog queries, nested while queries, and their incrementally optimized versions, we show that IntConv is not only sound but also complete (meaning any convergence in the theory implies the convergence in our criterion). As a result, our theory provides semantic guarantees for convergence detection on all these circuits. Our results are formally verified in Lean, with the formalization available at https://github.com/Arcadia-Y/fixing-the-fixpoint/.

0.46

A Pragmatic Guide to Building Conservative Discrete Abstractions of Cyber-Physical Systems

eess.SY cs.LO ·2026-08-10 ·Jordan Peper, Krish Kapadia, James Gast, Ethan Howes, Ivan Ruchkin
similarity 0.49
Abstract

Symbolic model checking is an effective approach for verifying semantically rich temporal-logic properties of cyber-physical systems, but it hinges on discretizing continuous-state dynamics into a finite-state abstraction. To transfer verification guarantees from the abstract model to the concrete CPS, the abstraction must conservatively approximate the concrete state space and behaviors. Hence, model-builders must maintain this soundness while balancing pessimism with tractability. However, they face several common pitfalls such as under-approximating the state space, under-approximating transitions, unsound pruning of "degenerate" behaviors, and improper specification lifting. This tutorial presents a pragmatic, conservative-by-construction workflow for building discrete abstractions of closed-loop dynamical systems. The workflow consists of four modular steps with interchangeable subroutines: (i) state-space partition and abstraction-function design, (ii) conservative transition construction via axis-aligned bounding boxes, polytopes, or sampling with PAC coverage certificates, (iii) mitigation of spurious transitions and self-loops using certified erasure and counterexample-guided abstraction refinement, and (iv) sound lifting of LTL specifications using may-must semantics. We demonstrate the end-to-end pipeline on three case studies and report how these design choices affect abstraction structure, runtime, and verification outcomes.

0.04

Long-horizon autoformalization of a core theorem underlying MIP* = RE

cs.AI quant-phcs.LO ·2026-09-17 ·Sirui Lu, Ruixuan Deng, Yanqiao Zhu, Zhengfeng Ji
theorycode/data similarity 0.49
Abstract · 74 pages. Main text 13 pages with 4 figures and 1 table, followed by supplementary appendices (59 pages, 9 figures, 17 tables) and reference…

Landmark mathematical formalizations have taken specialist teams years to complete. We present FormalFlow, a system that coordinates AI proving agents under human supervision to address statement drift and proof composition in long-horizon formalization. Drawing on software-engineering principles and practices, it uses a shared blueprint to guide nested planning, proving, and review loops. Using FormalFlow, we completed a machine-checked Lean 4 proof of the quantum soundness of the classical low individual-degree test, a core theorem underlying MIP* = RE, in 63 days. The final library contains 126,367 lines of Lean code, all generated by agents. Beyond providing a verified foundation for quantum complexity, the formalization corrects side conditions and intermediate error bounds in the published proof and improves the error exponent of the main theorem. The development record shows what it takes to trust proofs written by AI agents and provides reusable tools for verifying research mathematics at scale.

0.56