CS Paper Radar

Geometric Function Atlas: certified computing for geometric function theory in Python

Kishan Gurumurthy, Pushparaj Devadiga, Prasanna Devadiga, Arya Suneesh, Asha Sebastian

cs.MS ·submitted 2026-09-07 20:46 UTC · v1
code/data

Abstract

We describe geometric-function-atlas, our open-source Python package for the sharp extremal problems of geometric function theory. We organise it around a catalogue of thirty-nine Ma--Minda starlike generators. From this catalogue we compute exact Taylor coefficients, closed-form Fekete--Szegő constants, exact coefficients of the Ma--Minda extremal function, and admissibility screens. Our verifier answers membership questions for normalised polynomials at three levels of evidence: a floating-point grid screen, an exact sufficient condition decided in rational arithmetic, and a certified interval enclosure at the worst screened point. Every answer names the level at which we obtained it. We ship a checksummed artifact snapshot with three hundred and six coefficient certificates and seven hundred and two directed inclusion radii. Eight reviewed radius lanes carry certificates whose proof chains we replay symbolically, and we re-execute every coefficient certificate through our exact Schur-parameter machinery on request. We emit all results through one versioned envelope that records the method, the evidence status, the assumptions, and the artifact identifiers. Two optional laboratories apply the same discipline to cryptographic S-box metrics and to image-quality metrics. We present our design, state as propositions what each tier establishes, follow one radius lane from screen to replayed certificate, report measured timings, and place our package among symbolic-algebra, rigorous-numerics, and mathematical-database software. We release geometric-function-atlas under the MIT licence on the Python Package Index and at https://github.com/Prasanna28Devadiga/geometric-function-atlas.

Closest papers

Nearest neighbours by meaning across the whole index.

Approximate Polynomial Satisfiability and Integral Closure Membership in the Counting Hierarchy

cs.CC ·2026-10-30 ·Sanyam Agarwal, Archit Hari, Anurag Pandey, Himanshu Shukla
theory similarity 0.61
Abstract · Made some minor changes

Andrews, Garg, and Schost (FOCS~2026) recently, in a breakthrough result, placed Hilbert's Nullstellensatz (HN) in the Counting Hierarchy ($\CH$) using constant-depth circuits for multivariate resultants. While HN deals with exact polynomial satisfiability, Guo, Saxena, and Sinhababu (CCC~2018; Theory of Computing~2019) introduced approximate polynomial satisfiability (APS) as a natural approximative analogue of polynomial system satisfiability. They proved its $\mathsf{NP}$-hardness and a $\PSPACE$ upper bound, and used APS to construct hitting sets for $\overline{\mathsf{VP}}$ in polynomial space, substantially narrowing the GCT chasm in geometric complexity theory. We place APS in the Counting Hierarchy for rational polynomials given by arithmetic circuits. Our proof combines Noether normalization with a geometric restriction on how points in the image of a polynomial map approach the origin, reducing APS to a test on multivariate resultants which allows solvability in $\CH$. It complements the independent and concurrent proofs of Balaji, Shirmohammadi, Tavenas, and Worrell, and Andrews, Garg, Oliveira, and Schost. Moreover, we also place integral closure membership testing in the Counting Hierarchy. Here, the question is whether a given polynomial $f$ is integral over $\C[f_1,\ldots,f_m]$. Our approach uses a global annihilator criterion and an effective degree bound to reduce non-integrality to APS in polynomial time. In fact, we show that the reduction holds both ways, and Integral Closure Membership Testing is equivalent to APS under polynomial-time reductions.

0.17

Exact rational certificates and a Lean formalization of the eleven-variable Vasc inequality

cs.SC ·2026-10-09 ·Dakai Guo, Ruichen Qiu, Yichuan Cao, Ruyong Feng, Xiao-Shan Gao
theorycode/data similarity 0.57
Abstract

We prove that the cyclic sum $\sum_{i=0}^{10}(x_i-x_{i+1})/(x_{i+1}+x_{i+2})$ is nonnegative for every strictly positive real eleven-tuple, with indices taken modulo eleven. Clearing denominators reduces the problem to a homogeneous polynomial. Subtracting the smallest coordinate then separates the proof into nonnegativity of a common-translation derivative and nonnegativity on a full boundary face. We supply exact rational polynomial certificates in Gram-matrix form for both statements. The derivative certificate uses a linear multiplier, centered monomials and cyclic averaging; the boundary certificate uses a strictly positive quadratic multiplier and uncentered monomials. Their verification requires 6,069 cyclic coefficient comparisons and 34,304 literal coefficient comparisons. All 606 certificate matrices are certified by integer congruences with strictly diagonally dominant images. A Lean 4 development formally verifies the certificate checks and their connection to the original inequality. The exact certificate data, replay programs, and formal sources are publicly available.

0.20

Formally Certifying the Vertex Set of a Polyhedron Faster than Informal Enumeration

cs.LO math.COmath.OC ·2026-10-08 ·Xavier Allamigeon, Yazid Id-Sahra, Pierre-Yves Strub
similarity 0.57
Abstract · 20 pages, 3 figures, 2 tables

The computation of the vertices of a polyhedron described by a system of linear inequalities is a central problem in polyhedral computation. It is a fundamental step in the conversion between H-representations, by linear inequalities, and V-representations, by vertices and extreme rays. This operation plays an important role both in the study of polyhedra and their combinatorics in mathematics and in applications to software and system verification. We present a certificate-based approach for formally verifying the computation of the vertices of a polyhedron. Given an informally computed list of vertices, our method allows to certify in the proof assistant Rocq that the list is complete, or even exact. The cornerstone of the method is a new completeness criterion based on an abstract simplicial complex that generalizes a triangulation of the normal fan of the polyhedron. A significant advantage over previous approaches is that the usually expensive numerical computations are essentially reduced to membership tests to the polyhedron, while the other steps are cheap combinatorial tests. We implement the certification method and prove its correctness in the proof assistant Rocq. We experiment with it on a variety of polyhedra, including Birkhoff polytopes, cross-polytopes, cubes, permutahedra, hypersimplices, and high-dimensional polytopes involved in the disproof of the Hirsch conjecture. Our experiments show that certification with the Rocq-to-OCaml extracted checker is typically 1.5x to over 5x faster than vertex enumeration by the state-of-the-art informal C implementation lrslib of the reverse search method.

0.28

The Geometric Function Atlas: Using What We Know About Radius Problems to Solve New Ones

cs.DL math.CV ·2026-08-16 ·Prasanna Devadiga, Kishan Gurumurthy, Arya Suneesh, Pushparaj Devadiga, Asha Sebastian
similarity 0.57
Abstract

Usually, radius problems between Ma--Minda classes are solved one pair at a time, by fitting a disk inside the target region, providing a sufficient but not always the sharp radius. The same class appearing under different names makes comparison of results harder, with mistakes and duplication eluding detection. The Geometric Function Atlas catalogs radius problems using exact generators and a direction (source $\to$ target), ensuring unique identification. For each problem, we then compute the radius numerically, together with the point where the image first meets the target boundary. This helps us identify the sharp estimate which guides the proof we write. With this system, we were able to refine two earlier stated estimates, the disk radius for the sine $\to$ modified sigmoid and sine $\to$ rational cases from $\operatorname{arsinh} c$ to $\arcsin c$, and correct earlier stated values for the crescent and exponential classes: the sharp radius is $\sin 1$ from crescent to exponential, and $\log(1+\sqrt2)$ from exponential to crescent. All four proofs follow a common strategy: an estimate that is exact at the contact point, followed by the standard extremal function. Applying the method, we derive fifteen further sharp radii, four of them known.

0.43

A Degree--Size Relation for Resolution over Polynomials

cs.CC cs.LO ·2026-09-30 ·Shuo Pang
similarity 0.56
Abstract · Parameters in Section 8 (Conclusions) made explicit

For every constant-width CNF, we show that linear degree in polynomial calculus (PC) implies exponential size in resolution over constant-degree polynomials, over the same prime field. Applications include exponential lower bounds for CNFs in $\operatorname{Res}(\operatorname{PC}_r/\mathbb{F}_p)$ and hence in $\operatorname{Res}(\oplus_p)$, separations between different moduli, improved lower bounds for $\operatorname{Res}(k)$ up to $k=\varepsilon\log n$, proof-search consequences, and an implication of super-polynomial $AC^0[p]$-Frege bounds from very strong PC degree lower bounds. The proof uses the common-multiplier idea isolated from Braun [arXiv:2609.23015] to construct a Razborov--Smolensky approximation that preserves inferences, without introducing extension variables. The approximation errors are measured by ranks of the multiplication maps induced by the error-witness polynomials, modulo bounded-degree PC consequences.

0.49

Rózsa: Certified Equational Reasoning

cs.LO ·2026-10-19 ·Georgios Kissas
similarity 0.54
Abstract

When does one equation imply another? Stage 2 of the SAIR Mathematics Distillation Challenge required teams to submit solvers to answer this question for sets equipped with a binary operation. For these sets, associativity, commutativity, or any other algebraic property was not assumed. Each answer required a proof or counterexample that could be verified by Lean. Programs also had to respect fixed resource limits. We present Rózsa, a Python solver that searches for both kinds of evidence. It begins with simple tests and considers more extensive searches when those fail. To find a proof, it applies a given equation and derives any further equations as needed, keeping a record of each step. To find a counterexample, it searches for operations on finite sets. It also tests one fixed infinite model. The given equation must hold for every assignment, while the target equation must fail for at least one. In either case, Rózsa turns the evidence into a Lean certificate. The submitted solver solved 199/200 problems (99.5%) in the official main evaluation getting the 6th overall position. Additional tests show that the solver can prove many implications linked by long chains of known results, but has limited success with infinite counterexamples. We explain the search methods, how they fit together, and what the unsolved cases reveal about their limits.

0.16

Sensitivity of Rotation Symmetric Boolean Functions via Binary Necklaces

cs.CC math.COcs.DM ·2026-10-12 ·Yuan Li, Jing Zhang
theory similarity 0.54
Abstract · Version 2 29 pages

Rotation symmetric Boolean functions are important structured families in the theory of Boolean functions, where cyclic invariance permits compact algebraic descriptions while retaining nontrivial local behavior. We investigate their sensitivity through binary necklaces and monomial orbit sums. In the necklace quotient of the Boolean cube, ordinary adjacency does not record the number of coordinate flips: we give a directed flip-multiplicity formula involving stabilizers and distance-two near-periods, and derive exact local sensitivity formulas when the number of variables is an odd prime. For monomial rotation symmetric functions we determine sensitivity for all odd degrees and for quadratic orbit sums. For the consecutive-monomial family of every even degree $d\ge4$, we prove a run-cluster inequality and obtain the eventual exact formula $s(F_{d,n})=n-\min\{r,d+2-r\}$, where $n\equiv r\pmod{d+2}$, under the stated length hypothesis. The consecutive quartic case follows explicitly. We also evaluate sensitivity for cyclic run-threshold functions. Our results provide exact combinatorial and complexity-theoretic information about cyclic Boolean functions and clarify how cyclic symmetry governs local sensitivity.

0.48

A Simple Algebraic Proof of the PCP Theorem

cs.CC ·2026-08-18 ·Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan, Madhu Sudan, Sophus Valentin Willumsgaard
publishedtheory similarity 0.54
Abstract · Fixed an error in Lemma 3.3 and modified the tests accordingly

We give the simplest known algebraic proof of the PCP theorem, involving only ingredients like code concatenation, polynomial interpolation, and polynomial multiplication. Specifically, we prove that graph 3-coloring has a polynomial-sized proof that can be verified by a verifier tossing logarithmically many coins and querying a constant number of bits in the proof. In particular, our proof does not involve any PCP compositions; notably, it does not invoke the NP-completeness of any fixed problem, such as SAT or 3-coloring, in the construction of the verifier. The main innovation in our work is a clean, coding theoretic, way to encode univariate polynomials that allows us to implement ``low-degree testing'' using just a constant number of bits of queries. Insights from recent attempts to simplify the PCP proof by the authors (STOC 2026) and Goldreich (ECCC 2025) allow us to observe that low-degree was the key bottleneck in converting previous algebraic constructions of the PCP verifier into a constant query PCP. Thus, by overcoming this bottleneck, we get the full PCP verifier using elementary and self-contained steps. As concrete support for the claimed simplicity, we include the full pseudocode of the PCP verifier, assuming finite field arithmetic, and a full description of the completeness (aka ``honest'') prover, assuming multivariate polynomial arithmetic including interpolation and evaluation, that fit in about a page each.

0.32