Introduction
In formal verification, verifying "straightforward" real-number inequalities remains a persistent challenge. While specialized tools exist for linear arithmetic or polynomial systems, interactive theorem prover (ITP) users frequently encounter routine problems that mix these domains with non-linear functions like $\exp$ and $\log$. For instance, an inference such as $0 < x < y, u < v \implies 2u + \exp(1 + x + x^4) < 2v + \exp(1 + y + y^4)$ is intuitively obvious due to monotonicity, yet often stumps state-of-the-art SMT solvers that lack a unified heuristic for heterogeneous mathematical expressions.
This paper introduces Polya, a modular framework designed to bridge this gap. Rather than aiming for completeness in a narrow domain, Polya employs a heuristic, extensible approach to verify complex inferences by coordinating specialized reasoning engines through a shared central database.
Architecture and Methodology
Polya's design is inspired by the Nelson-Oppen architecture but centers on a "Blackboard" system that facilitates communication between independent modules.
The Blackboard and Canonical Forms
At the heart of Polya is the Blackboard, a central repository for known comparisons (e.g., $t_i < c \cdot t_j$). Modules do not interact directly; instead, they read existing information from the blackboard, derive new inequalities, and post their findings back. To ensure consistency across modules, Polya reduces all expressions to a canonical normal form. It distinguishes between "terms" and "scaled terms" (s-terms), which allows the system to automatically recognize equivalent expressions like $4y + 2x$ and $2 \cdot (x + 2y)$.
Specialized Reasoning Modules
Polya utilizes several specialized modules to handle different mathematical domains:
- Arithmetic Modules: Variable elimination is handled via a standard Fourier-Motzkin algorithm or a more advanced Geometric Module. The latter treats inequalities as polyhedral cones and uses vertex enumeration to find tight bounds, often proving more robust for medium-sized problems.
- Axiom Instantiation: This module identifies functional terms (e.g., $f(x)$) and applies relevant properties such as monotonicity or convexity.
- Function-Specific Handlers: Dedicated modules manage $\min/\max$, absolute values, $\exp/\log$, and $n$-th roots, as illustrated in the architecture diagram.
Evaluation and Results
The authors evaluated Polya against two primary datasets to test its heuristic effectiveness and real-world utility.
- Custom Benchmark Suite: A set of 81 problems focusing on mixed-function inequalities that are typically "easy for humans but hard for machines." Polya solved the entire suite in approximately 8.5 seconds.
- KeYmaera Problems: Polya was tested on 4,442 problems generated by KeYmaera, a tool for verifying hybrid systems. Polya successfully verified 96% (4,252) of these problems in roughly six minutes, demonstrating significant scalability.
In comparative tests, Polya successfully solved problems involving transcendental functions that caused solvers like Z3 to fail or required extensive manual intervention in Isabelle/HOL.
Discussion and Limitations
Polya's strength lies in its modularity and speed, prioritizing being "mostly right and very fast" over theoretical completeness. By restricting its search to "terms of interest" already present in the problem, it avoids the combinatorial explosion typical of more exhaustive solvers.
However, the system has notable limitations. It currently lacks a robust handling of the distributive law (e.g., recognizing $x^2 + 2x + 1 = (x+1)^2$), which can lead to non-termination in specific polynomial contexts. Additionally, its multiplicative reasoning is highly sensitive to the signs of terms, and its current case-splitting mechanism is relatively naive. Future work aims to integrate CDCL-style case splitting and extend support to second-order operators like integrals and sums.
Summary updated