SMT and Functional Equation Solving over the Reals: Challenges from the IMO
Chad E. Brown, Karel Chvalovský, Mikoláš Janota ✉, Mirek Olšák, Stefan Ratschan · 2025
Read SMT and Functional Equation Solving over the Reals: Challenges from the IMO by Chad E. Brown, Karel Chvalovský, Mikoláš Janota ✉, Mirek Olšák, Stefan Ratschan (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-2504-15645.txt.
Introduction
Some contest problems ask for every function that fits a set of rules over the real numbers, and they appear at events like the International Mathematical Olympiad. Chad Brown and four co-authors test whether automated solvers, known as SMT tools, can crack such problems in this 2025 paper. The math involved is at high school level, yet the solvers often fail.
The trouble lies in mixing unknown functions with nonlinear real arithmetic, a blend that strains current solvers. The authors propose several techniques to help the tools search more wisely in this setting. Their work measures where the solvers break down and which fixes help most. The goal is software that can reliably find all solutions to these function puzzles, a step toward machines that handle contest-style reasoning.
Catalog record
| CREATOR | Chad E. Brown, Karel Chvalovský, Mikoláš Janota ✉, Mirek Olšák, Stefan Ratschan |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 32 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-15645
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
SMT and Functional Equation Solving over the Reals: Challenges from the IMO Chad E. Brown, Karel Chvalovský, Mikoláš Janota ✉, Mirek Olšák, Stefan Ratschan Abstract We use SMT technology to address a class of problems involving uninterpreted functions and nonlinear real arithmetic. In particular, we focus on problems commonly found in mathematical competitions, such as the International Mathematical Olympiad (IMO), where the task is to determine all solutions to constraints on an uninterpreted function. Although these problems require only high-school-level mathematics, state-of-the-art SMT solvers often struggle with them. We propose several techniques to improve SMT performance in this setting. 1 Introduction The AIMO Challenge 1 1 1 https://aimoprize.com/ has garnered significant interest from researchers, particularly within the machine learning community, by focusing on mathematical olympiad problems [ 14 , 29 ] . However, this challenge is also highly relevant to the field of automated reasoning. In a previous study [ 8 ] , the authors formally addressed the problem of functional equations, which involves determining all functions that satisfy a given set of equations. The problem is best illustrated by a simple example where one is to find all f\,:\,\mathbb{R}\rightarrow\mathbb{R} , s.t. \forall xy.f(x+y)=xf(y)+yf(x). (1) Setting y to 0 , yields \forall x.\,f(x)=f(0)x , revealing that f must be linear and is entirely determined by the value of f(0) . Furthermore, substituting x=0 reveals that f must be identically zero, meaning the unique solution is f(x)=0 (formally, f=\lambda x.\,0 ). A solution should provide a clear description of all possible functions f , potentially parameterized by constants. The initial approach of the authors [ 8 ] fixes a template (a polynomial with parameters as coefficients) for the function f and then determines how this template should be parameterized to solve the given problem. The values of the parameters are obtained by real quantifier elimination. Then, it is required to prove that all possible solutions must fit within the template. To illustrate, consider the “linear” template f(x)=ax+b in equation ( 1 ) where applying quantifier elimination on \forall x gives all the possible values of a and b , which is simply a=b=0 . In the second phase, it needs to be proven that all possible f must be linear, which can be stated as follows. (\forall xy.f(x+y)=xf(y)+yf(x))\Rightarrow(\exists a,b\forall x.f(x)=ax+b) (2) It turns out that proving such an implication is the bottleneck of the approach. That is, even if it is easy to find every f within the template that solves the equality, proving that the template is sufficient to cover all the solutions, is hard for state-of-the-art solvers for Satisfiability Modulo Theories (SMT). The problem under investigation presents a dual challenge: function synthesis and comprehensive coverage verification (“there are no more f ’s”). Function synthesis alone represents a significant computational challenge with numerous methodological approaches [ 2 , 18 , 19 , 30 , 7 , 16 ] , which we address through a template-based methodology [ 36 ] coupled with quantifier elimination [ 37 , 13 , 39 ] . The principal contribution of this paper, however, lies in establishing the comprehensive coverage verification. We introduce novel inference techniques that enhance solvers’ performance by generating auxiliary lemmas and strategic quantifier instantiations prior to invoking SMT solvers. These techniques generalize to other challenging problems in real arithmetic that, despite their compact representation, present considerable difficulty in solving. The key contributions of this paper are as follows: • Development of an exploratory procedure that discovers novel lemmas to facilitate proof construction. • Formulation of specialized instantiation-based techniques designed for computationally intensive quantified problems. • Implementation of these advances in a unified framework that leverages state-of-the-art SMT solvers. • Introduction of a benchmark suite to evaluate these techniques, demonstrating meaningful performance improvements over the existing method. 2 Preliminaries Throughout the paper, a basic understanding of first-order logic is expected [ 35 ] . We use SMT solvers [ 5 ] mainly in a black-box fashion, where the primary target is the combination of the theories of nonlinear real arithmetic and uninterpreted functions ( UFNRA ). By a substitution in a formula \phi we mean a mapping from all free variables of \phi to terms and its application is denoted as \phi[x_{1}\mapsto t_{1},\dots,x_{n}\mapsto t_{n}] where all x_{i} are replaced by the corresponding term t_{i} simultaneously. For a vector of variables \vec{x} , a quantified formula \forall\vec{x}.\,\phi , and a substitution s , an instantiation is the formula \forall\vec{x}^{\prime}.\,\phi[s] , where \vec{x^{\prime}} are the free variables introduced by s . SMT solvers attempt to solve quantified problems by adding quantifier instantiations. 2 2 2 If formulas are not prenex, new instantiations are added in the form of the implication (\forall\vec{x}.\,\phi)\rightarrow\phi[s] , but through this paper we assume prenex form. These instantiations only introduce ground terms so that they can be sent to the ground subsolver. There is a large body of research on quantifier instantiation in SMT, with syntactic-driven approaches ( e-matching [ 15 ] or syntax-guided instantiation [ 28 ] ), semantic-driven ( model-based [ 16 , 33 ] ), conflict-based [ 34 ] , and enumerative instantiation [ 21 , 32 ] . Our experiments also use the automated theorem prover Vampire [ 22 ] as an SMT solver. Vampire does not explicitly instantiate but relies on superposition [ 35 ] . Quantifier Elimination (QE). We need to be able to handle nonlinear arithmetic over the real numbers. The corresponding logical theory—the theory of real closed fields—allows QE [ 37 ] . This means, that there is an algorithm that takes any formula with the signature \{0,1,+,\times,=,\leq\} (in practice, further symbols that can be expressed in terms of these) and computes a quantifier-free formula that is equivalent w.r.t. the axioms of the theory of real closed fields. QE in the theory of real-closed fields is highly costly, both in theory [ 39 , 13 ] and in practice. Hence it is usually beneficial, and often indispensable, to exploit the specific structure of the quantifier elimination problems at hand. For QE we use QEPCAD [ 12 , 9 ] via the tool Tarski [ 38 ] . Additional techniques are discussed in Section 3.1 . 3 Problem Statement and Templates Revisited In many cases, the problem is given as an equation, just as in example ( 1 ), but more complicated problem descriptions may appear. For instance, apart from the equation there might also exist the requirement that the function f must be monotone, injective, etc. Similarly, the solution to a problem might be a single function but also more complicated classes of functions often appear, e.g. identity with a positive shift, which can be described as \exists c.\,c>0\land\forall x.\,f(x)=x+c . We formalize this in the following. The input to a problem is a specification of a function f\,:\,\mathbb{R}\rightarrow\mathbb{R} , which is a sentence \Phi_{\textrm{spec}} in the language of first-order real arithmetic augmented with a unary function symbol f . 3 3 3 Competitions may contain problems with multiple functions and with different domains, e.g. \mathbb{Q} . These we currently do not support. We do support certain restrictions on the reals, e.g. \mathbb{R}^{+} but we avoid discussing this here for the purpose of conciseness. A solution to a problem is a specification \Phi_{\textrm{sol}}