Beyond Affine Loops: A Geometric Approach to Program Synthesis

Erdenebayar Bayarmagnai, Fatemeh Mohammadi, Rémi Prébet · 2025

Read Beyond Affine Loops: A Geometric Approach to Program Synthesis by Erdenebayar Bayarmagnai, Fatemeh Mohammadi, Rémi Prébet (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-00620.txt.

Introduction

Erdenebayar Bayarmagnai and co-authors tackle a hard task in program checking, in work from 2025. Rather than test a loop against a fixed trait, they build loops that are sure to hold the trait. Past tools could only build plain loops with no guard terms and with traits of a fixed shape.

Their method uses tools from algebraic geometry to turn the task into a set of equations. The answers to those equations match exactly the loops that keep the stated traits. A solver then finds those answers in set regions of the number plane. The team built the method into working software.

Catalog record

CREATORErdenebayar Bayarmagnai, Fatemeh Mohammadi, Rémi Prébet
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE35 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-00620

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Beyond Affine Loops: A Geometric Approach to Program Synthesis Erdenebayar Bayarmagnai, Fatemeh Mohammadi, Rémi Prébet Abstract Ensuring software correctness remains a fundamental challenge in formal program verification. One promising approach relies on finding polynomial invariants for loops. Polynomial invariants are properties of a program loop that hold before and after each iteration. Generating polynomial invariants is a crucial task for loops, but it is an undecidable problem in the general case. Recently, an alternative approach to this problem has emerged, focusing on synthesizing loops from invariants. However, existing methods only synthesize affine loops without guard conditions from polynomial invariants. In this paper, we address a more general problem, allowing loops to have polynomial update maps with a given structure, inequations in the guard condition, and polynomial invariants of arbitrary form. In this paper, we use algebraic geometry tools to design and implement an algorithm that computes a finite set of polynomial equations whose solutions correspond to all loops satisfying the given polynomial invariants. In other words, we reduce the problem of synthesizing loops to finding solutions of polynomial systems within a specified subset of the complex numbers. The latter is handled in our software using an SMT solver. 1 Introduction Loop invariants are properties that hold before and after each iteration of a loop. They are key to automating program verification, which ensures that programs produce correct results before execution. Various well-established methods use loop invariants for safety verification, such as the Floyd-Hoare inductive assertion technique [ 11 ] and termination verification via standard ranking functions [ 26 ] . When a loop invariant is a polynomial equation or inequality, it is called a polynomial invariant. In this work, instead of generating polynomial invariants for a given loop, we address the reverse problem, that is synthesizing a loop that satisfies given polynomial invariants. We consider polynomial loops \mathcal{L}(\mathbf{a},h,F) of the form \mathbf{x}:=(x_{1},\ldots,x_{n})\leftarrow\mathbf{a}:=(a_{1},\ldots,a_{n}) while h(\mathbf{x})\neq 0 do \begin{pmatrix}x_{1}\\ x_{2}\\ \vdots\\ x_{n}\end{pmatrix}\xleftarrow{F}\begin{pmatrix}F_{1}\\ F_{2}\\ \vdots\\ F_{n}\end{pmatrix} end while where x_{i} are the program variables with initial values a_{i} , h\in\mathbb{C}[\mathbf{x}] , and F=(F_{1},\ldots,F_{n}) is a sequence of polynomials in \mathbb{C}[\mathbf{x}] . The inequation h(\mathbf{x})\neq 0 , called the guard , is assumed to be a single inequality for simplicity (we can replace h_{1}\neq 0,\ldots,h_{k}\neq 0 with their product h_{1}\cdot\ldots\cdot h_{k}\neq 0 without loss of generality). Where there is no h we simply write \mathcal{L}(\mathbf{a},1,F) , which corresponds to an infinite loop. Previous work [ 22 , 16 , 19 ] has focused on update maps that are restricted to be linear. In this paper, we go beyond this limitation by allowing update maps to be arbitrary polynomial functions. We present a method for computing a system of equations whose common solutions characterize all coefficient assignments for update maps of loops that satisfy a given set of polynomial invariants. To illustrate our main objective, we now present a motivating example. Example 1 . Consider the following polynomial loop: (x_{1},x_{2},x_{3})\leftarrow(1,1,-1) while true do \begin{pmatrix}x_{1}\\ x_{2}\\ x_{3}\end{pmatrix}\xleftarrow{F}\begin{pmatrix}\lambda_{1}x_{1}^{3}+\lambda_{2}x_{2}^{2}\\ \lambda_{3}x_{1}+\lambda_{4}x_{2}^{2}\\ \lambda_{5}x_{1}\end{pmatrix} end while By applying Algorithm 2 , we construct polynomials P_{1},\ldots,P_{4} , such that (\lambda_{1},\ldots,\lambda_{5}) is a common root of these polynomials if and only if the loop satisfies the polynomial invariants g_{1}=x_{2}^{2}-x_{1} and g_{2}=x_{3}^{3}+2x_{2}^{2}-x_{1} . For instance, (-3,3,1,-1,0) is a common root of \{P_{1},\ldots,P_{4}\} . Thus, if the update map is F(x_{1},x_{2},x_{3})=(-3x_{1}^{3}+3x_{2}^{2},x_{1}-x_{2}^{2},0) , the loop satisfies the invariants g_{1} and g_{2} . See Example 3 for further details. Related works. The computation of polynomial invariants for loops has been a prominent area of research over the past two decades [ 3 , 9 , 17 , 20 , 23 , 24 , 27 , 28 , 29 ] . However, computing invariant ideals is undecidable for general loops [ 18 ] . As a result, efficient methods have been developed for restricted classes of loops, particularly those where the assertions are linear or can be transformed into linear assertions. The converse problem of synthesizing loops from given invariants has received less attention, primarily focusing on linear and affine loops. These studies vary in the types of invariants considered: linear invariants in [ 34 ] , a single quadratic polynomial in [ 16 ] , and pure difference binomials in [ 22 ] . In contrast, [ 19 ] explores general polynomial invariants but lacks the completeness properties of earlier work and does not address guard conditions. Higher degree loops have been studied in a more general framework in [ 13 , 12 ] , which also takes polynomial inequalities as input. However, the loops synthesized by this algorithm are restricted to those where the input invariants are inductive, meaning that if the invariant holds after one iteration, it holds for all subsequent iterations. Our contributions. We consider the problem of generating polynomial loops with guards from arbitrary polynomial invariants. As a first step, we construct a polynomial system whose solutions correspond precisely to loops with a given structure that satisfy the specified invariants. We then discuss strategies for solving this system. In practice, in most cases a satisfying solution is found using an SMT solver. Section 2 recalls the definition of invariant sets and key results from [ 2 ] . Section 3 introduces a method for identifying multiple polynomial invariants (Proposition 3.5 ) and proves that the set \mathscr{C}(\mathbf{a},h,\mathbf{f};\bm{g}) of coefficients of polynomial maps of loops satisfying the invariants \bm{g} forms an algebraic variety. We also present Algorithm 2 , which computes the polynomials defining \mathscr{C}(\mathbf{a},h,\mathbf{f};\bm{g}) . Section 4 discusses strategies for solving polynomial systems and their limitations, while Section 5 presents our algorithm’s implementation and experimental results. 2 Preliminaries In the following, we present some terminology from algebraic geometry. For further details, we refer the reader to [ 7 , 21 , 32 ] . We denote the field of complex numbers by \mathbb{C} . Throughout the paper, \mathbf{x} denotes indeterminates x_{1},\dots,x_{n} , and \mathbb{C}[\mathbf{x}] the multivariate polynomial ring in these variables. Ideals. A polynomial ideal I is a subset of \mathbb{C}[\mathbf{x}] that is closed under addition, 0\in I and for any f\in\mathbb{C}[\mathbf{x}] and g\in I , fg\in I . Given a subset S of \mathbb{C}[\mathbf{x}] , the ideal generated by S is \langle S\rangle=\{a_{1}f_{1}+\ldots+a_{m}f_{m}\mid a_{i}\in\mathbb{C}[\mathbf{x}],f_{i}\in S,m\in\mathbb{N}\}. By Hilbert Basis Theorem [ 7 , Theorem 4, Chap. 2] , every ideal is finitely generated. For a subset X\subset\mathbb{C}^{n} , the defining ideal I(X) consists of all polynomials vanishing on X . The radical of an ideal I\subset\mathbb{C}[\mathbf{x}] is defined as \sqrt{I}=\{f\in\mathbb{C}[\mathbf{x}]|\,f^{m}\in I\text{ for some }m\in\mathbb{N}\}. Varieties. For S\subset\mathbb{C}[x] , the algebraic variety \bm{V}(S) is the common zero set of all polynomials in S . Moreover, \bm{V}(S)=\bm{V}(\langle S\rangle) and so every algebraic variety is the vanishing locus of finitely many polynomials. Polynomial maps. A map F:\mathbb{C}^{n}\longrightarrow\mathbb{C}^{m} is a polynomial map if there exist f_{1},\ldots,f_{m}\in\mathbb{C}[x_{1},\ldots,x_{m}] such that F(x)=(f_{1}(x),\ldots,f_{m}(x)) for all x\in\mathbb{C}^{n} . For simplicity, we will identify polynomial maps and their corresponding polynomials. Here, we introduce the main object of this paper and build upon key results from [ 2 ] by recalling and extending them. Definition 2.1 . Let F:\mathbb{C}^{n}\longrightarrow\mathbb{C}^{n} be a map and X be a subset of \mathbb{C}^{n} . The invariant set of (F,X) is defined as: S_{(F,X)}=\{x\in X\mid\forall m\in\mathbb{N},F^{(m)}(x)\in X\}, where F^{(0)}(x)=x and F^{(m)}(x)=F(F^{(m-1)}(x)) for m>1 . The following proposition enables the

Read the complete text