CS Paper Radar

Certified pandigital approximations of $π$, $γ$, $δ$ and $e$

Daniel Bendjema Garcia

cs.MS math.NT ·submitted 2026-11-19 01:56 UTC · v1
theory

Abstract

In 2004 Erich Friedman asked for the best approximations of $π$, $e$, the Euler-Mascheroni constant $γ$ and Feigenbaum's constant $δ$ that use each of the digits $1,\dots,n$ exactly once, with addition, subtraction, multiplication, division, exponentiation, parentheses and the decimal point. We determine the optimal expressions for $π$, $γ$ and $δ$ for every $n \le 9$, with the digits in any order and in increasing order, and for $e$ when $n \le 6$. The optima are found by exhaustive search and certified by an independent algorithm that encloses every expression rigorously and decides each candidate with Arb and exact arithmetic; a second certified computation covers intermediate values of any size. Twenty-one entries improve the published records; for $π$ with the digits 1-9 the optimal error is $2.81\cdot 10^{-14}$. For $e$, whose records come from identities between power towers, we prove that Bamberger's formula is optimal within the natural family of such identities. All code and certificates are public.

Comment
50 pages, 1 figure. Code, data and certificates: https://doi.org/10.5281/zenodo.24356239

Closest papers

Nearest neighbours by meaning across the whole index.

An $n^{8/5+o(1)}$-Time $Ω(λ^3)$-Approximation for Longest Common Subsequence

cs.DS ·2026-09-25 ·Zhao Song
similarity 0.58
Abstract

Let $λ$ denote the ratio of the length of a longest common subsequence of two length-$n$ strings to $n$. Rubinstein, Seddighin, Song and Sun [RSSS19] gave an $Ω(λ^3)$-approximation for LCS running in $\widetilde O(n^{39/20})$ time, where $39/20=1.95$. Song [Son19] mentioned that improving the $n^{1.95}$ running time is an interesting open question. We give an algorithm that computes an $Ω(λ^3)$-approximation of the longest common subsequence in $n^{8/5+o(1)}$ time. This improves the exponent $1.95$ to $1.6+o(1)$.

0.15

New Lower and Upper Bounds for the Grothendieck Constant

cs.CC cs.DS ·2026-08-11 ·Rahul Saha, Alan Li, Anton Xue, Swarat Chaudhuri, Adam Klivans +2 more
theoryhighly cited similarity 0.56
Abstract

We establish new bounds on the Grothendieck constant $K_G$: \[ \frac{6π}{11} \le K_G \le \fracπ{2\log(1+\sqrt2)} - 10^{-4}. \] Methodologically, our lower bound approach differs from previous works by establishing limitations on the asymptotically optimal Krivine schemes, rather than giving explicit constructions of gap instances. Our upper bound is obtained by proposing and analyzing the first asymptotic construction of rounding schemes, whereas previous works only consider low-dimensional schemes. Together, these bounds determine the previously unknown tenths digit of $K_G$ to be $7$. The bounds were discovered by a long-running collaborative effort of humans and a long-horizon AI research system that we engineered.

0.43

Limits and Constants of OpenAI's Claimed ETH Refutation

cs.CC cs.DSmath.CO ·2026-10-31 ·Fabio Dias, Yvens Lima
theory similarity 0.53
Abstract

A recent OpenAI preprint claims a deterministic algorithm that counts the satisfying assignments of a $k$-CNF formula in time $2^{O_k(n\log\log n/\sqrt{\log n})}$, and $2^{O(n/\sqrt{\log n})}$ at bounded clause density, which would refute the Exponential Time Hypothesis. The headline bound is proved by tensor contraction; the body develops an interpolation algorithm with the weaker exponent $n(\log\log n)^2/\sqrt{\log n}$. This note does four things. First, it explains the interpolation algorithm in plain terms. Second, it asks how large $n$ must be for the bounds to bite. The preprint states no constants, so we treat the hidden constant $C$ as a parameter: the general bound beats the $2^n$ of brute force only beyond $n\approx 10^{32}$ for $C=2$, $10^{126}$ for $C=3$ and $10^{3517}$ for $C=10$. We then extract the constants from the tensor-contraction proof: for every input with $m$ clauses at bounded density, the running time it certifies stays above $2^n$ unless $\log_2(n+m)>10^9$, and on random 3-CNF at the satisfiability threshold unless $\log_2 n>5\times10^{11}$. So the bounds are subexponential as $n\to\infty$, but the proof certifies no speed-up over brute force for any input of bounded density that could ever be written down. Third, for the clause-product form of the interpolation algorithm we prove limits in a cost model matching the preprint's evaluation. By a short algebraic lemma, polynomial cost needs components of $O(\log^3 n)$ variables with per-point evaluation, or primal treewidth $O(\log^2 n)$ with dynamic programming over the groups. So the scheme costs $2^{Ω(\sqrt{\mathrm{tw}})}$ at treewidth $\mathrm{tw}$, $2^{Ω(\sqrt n)}$ with high probability on random 3-CNF above clause density 3, and $2^{Ω(n^{1/3})}$ even on trivially countable path formulas. We explain why the preprint's sharper routes escape these limits. Fourth, we report experiments.

0.35

Primal/Dual Method for the Grothendieck Constant

cs.CC math.FA ·2026-10-07 ·Steven Heilman, Chris Jones, Giulio Malavolta
similarity 0.53
Abstract

We determine the hundredths digit of the real Grothendieck constant by proving $1.773 \leq K_G \leq 1.7799$. Furthermore, numerical heuristics suggest the estimate $K_G \approx 1.779$. We start by simplifying the Gaussian duality theory of $K_G$, based on Hermite projection games and Krivine rounding schemes. The bounds are obtained by a heuristic primal/dual search for these objects, followed by rigorous {\em certification} of their values. The search and certification are performed using AI tools, and in particular the rigorous certificates are very large (analytical reductions to thousands of numerical inequalities).

0.33

Long-Horizon AI Research for Grothendieck Constant: A Case Study in Human-AI Mathematical Collaboration

cs.AI cs.CCcs.HCmath.FA ·2026-08-11 ·Alan Li, Rahul Saha, Anton Xue, Swarat Chaudhuri, Adam Klivans +2 more
similarity 0.52
Abstract

AI agents are increasingly used in mathematics research, but it is often unclear how to use them effectively. Towards this, we present an extensive case study of how AI was used to improve bounds on the Grothendieck constant $K_G$, which captures the hardness between combinatorial problems and their continuous relaxations. Specifically, while the precise value of $K_G$ is not known, we recently tightened the best known bounds to \[ \frac{6π}{11} \;\le\; K_G \;\le\; \fracπ{2\log(1+\sqrt2)} - 10^{-4}. \] Crucially, these improvements were achieved using an AI research system that could arrive at insights deemed novel by domain experts. We give a detailed discussion of our experience using AI for mathematics research, particularly touching upon its strengths and weaknesses, as well as our experience with creating ideal conditions for AI to arrive at breakthrough insights.

0.34

Performance Evaluation of an Adaptive Quadrature and a Double Exponential Formula Using Arbitrary-Precision Floating-Point Arithmetic

cs.PF math.NA ·2026-08-13 ·Tomonori Kouya
similarity 0.52
Abstract

Using arbitrary-precision arithmetic provided by the GNU Multiple Precision Floating-Point Reliable Library, we implement AQE11D---that is, Ninomiya's adaptive 9-point Newton--Cotes rule extended with a sequence of higher-order rules---and Takahasi and Moris' double exponential (DE) formula. We evaluate them for Kahaner's 21 test problems. For both absolute tolerances $10^{-50}$ and $10^{-100}$, AQE11D attains target accuracy on all 21 problems; however, for strong endpoint singularity such as $1/\sqrt{x}$, it requires about $5.4\times10^{7}$ function evaluations at $10^{-100}$, roughly $7\times10^{4}$ times as many as the DE formula. The formula converges on 18 problems at both tolerances, demonstrating its strength against endpoint singularities but also its failure, as it stands, on problems with a singularity inside the integration interval.

0.04

A Numerical Refinement of an Exact Discrete Fourier Transform Bound

cs.CC cs.DS ·2026-10-31 ·Zhihao Yao, Sichao Liu
theory similarity 0.52
Abstract

We refine the numerical bounds in Kartal's instantiation of Sussman's exact discrete Fourier transform construction. For every integer n >= 1, the resulting algorithm computes the length-n transform with work O(n (log n)^(1 - delta)), where delta = 0.0030201659. The bound holds in an exact complex-arithmetic RAM model with a supplied canonical root of unity. This final exponent saving exceeds the earlier certified parameter C_0 = 0.00302016 by 5.9 x 10^(-9). We retain the underlying circuit, tighten rational bounds for sums of powers of its block and target ranks, and increase the fixed tensor power from 7760 to 11640. These bounds establish the inequalities for Sussman's recursion at the intermediate certificate parameter C = 0.00302016595. The gap C - delta absorbs the overhead of recursion and Fourier reduction. The resulting transform theorem is proved in Lean and checked against the reference problem statement.

0.25

High Precision Multiplicative-Error Approximation of $\#$SAC$^1$ Functions in Logspace Uniform AC$^1$

cs.CC ·2026-10-19 ·Kuan Cheng, Shengtang Huang, Ruiyang Wu
similarity 0.51
Abstract

We show that approximations of $\#\mathsf{SAC}^1$ functions (i.e. functions computed by logspace-uniform polynomial-size positive semi-unbounded arithmetic circuits of depth $O(\log n)$) can be computed in logspace uniform $\mathsf{AC}^1$ (denoted as $\mathsf{L}\text{-}\mathsf{AC}^1$) with multiplicative error $2^{-\operatorname{poly}\log n}$.Previously, approximations of $\#\mathsf{SAC}^1$ functions were known to be in logspace-uniform $\mathsf{TC}^1$ via exact computation given by Allender, Jiao, Mahajan, and Vinay (TCS'98). A main corollary of our result is that the following models beyond $\mathsf{BPL}$ are computable by $\mathsf{L}\text{-}\mathsf{AC}^1$ with multiplicative error $2^{-\operatorname{poly}\log n}$: - Probabilistic Auxiliary Push-down Machines (Probabilistic $\mathsf{AuxPDM}$s), which are polynomial time logspace Turing Machines (TMs) with an auxiliary stack having unbounded size and a read-once random tape; - Read-$k$ Probabilistic TMs with polynomial time and logarithmic space, where $k$ is a constant and Read-$k$ means the random tape is two-way accessible and each cell can be visited for at most $k$ times. Notice that this is a direct generalization and improvement for $\mathsf{BPL}\subseteq\mathsf{L}\text{-}\mathsf{AC}^1$ of Cheng and Wang (CCC'24), and the approximation error is improved from additive reverse polynomial to multiplicative reverse quasi-polynomial. $\mathsf{AuxPDM}$ was introduced by Cook (JACM'71) and its probabilistic version was first studied by Macarie and Ogihara (TCS'98). Read-$k$ Probabilistic logspace TMs was studied by Impagliazzo, Nisan, Wigderson (STOC'94) where a pseudorandom generator for this model was given. We mention that multiplicative error approximations are stronger than additive error approximations in the sense that they can even be used to decide non-deterministic computations.

0.31