🔢 mathematics

On the Algebraic Complexity of Optimal Polynomial Approximation Constants

This paper establishes a sharp phase transition in the algebraic solvability of constants arising from optimal polynomial approximation, demonstrating that while degree-1 minimax constants are solvable by radicals, degree-2 and higher constants generally are not due to a structural coupling of critical points, while also developing a theory of piecewise equiripple approximation that achieves exponential accuracy gains.

Original authors: Filip Filipović, Rémi Géraud-Stewart, David Naccacheand Aleksa Veličković

Published 2026-07-28

📖 6 min read🧠 Deep dive

CC0 1.0

Original authors: Filip Filipović, Rémi Géraud-Stewart, David Naccacheand Aleksa Veličković

Original paper dedicated to the public domain under CC0 1.0 (http://creativecommons.org/publicdomain/zero/1.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Hidden Math Behind "Good Enough" Guesses

Imagine you are trying to draw a perfect circle using only straight lines. You can't do it perfectly, but you can get very close. In the world of computers, this is a daily struggle. Computers are incredibly fast at adding and multiplying numbers, but they are notoriously slow and clumsy when asked to calculate square roots. It's like asking a race car to suddenly stop and tie its shoelaces before it can finish the race. To keep things moving, engineers use a clever trick: instead of calculating the exact square root, they use a simple "best guess" formula made of straight lines and basic math. This is called polynomial approximation.

The big question mathematicians have always asked is: "What are the absolute best numbers to put into this guess formula?" If you pick the wrong numbers, your guess is sloppy. If you pick the perfect ones, your guess is incredibly accurate. For a long time, people knew how to find these numbers for simple, straight-line guesses. But what happens when you try to make the guess slightly more complex? This paper dives into that exact question, exploring the hidden algebraic "DNA" of these perfect numbers. It turns out that while simple guesses are easy to solve, slightly more complex ones hit a wall where the numbers become so mathematically tangled that they cannot be written down using standard formulas, no matter how hard you try.

The Story of the Perfect Guess

The authors of this paper, a team of researchers from Serbia and France, decided to investigate the "perfect numbers" used to approximate the distance formula (the square root of $x^2 + y^2$ ) on a computer. They looked at two ways to measure how good a guess is: how far off the number is in total (absolute error) and how far off it is as a percentage (relative error).

The Simple Case: The Straight Line
First, they looked at the simplest possible guess: a straight line. They found that the perfect numbers for this line are "nice." In the language of math, they are "solvable by radicals." This means you can write down the exact answer using a recipe of square roots, cube roots, and basic arithmetic. It's like solving a puzzle where the pieces fit together neatly. The authors confirmed that for this simple case, the math is manageable and follows a predictable pattern.

The Twist: The Curve That Breaks the Rules
Then, they stepped up the game. They tried to find the perfect numbers for a slightly more complex guess—a curve that bends. They expected this to be just a little harder, maybe requiring a slightly longer recipe. Instead, they found a shocking "phase transition."

The perfect numbers for this curved guess are not solvable by radicals. The authors proved that these numbers are so complex that no formula involving roots and basic operations can ever write them down exactly. It's as if the puzzle pieces have melted together; you can see the shape, but you can't separate them into a clean recipe.

To prove this, the team used a branch of math called Galois theory, which studies the symmetry of equations. They discovered that the equations governing these perfect numbers have a "symmetry group" so wild and chaotic (specifically, groups named $S_{12}$ and $S_{10} \times C_2$ ) that they are mathematically impossible to untangle. The paper explicitly rules out the idea that there is a hidden, simple formula waiting to be found; the authors state with certainty that these constants are inherently unsolvable by standard algebraic methods.

The Numbers Behind the Mystery
The researchers didn't just say "it's impossible"; they did the heavy lifting to show exactly how impossible it is.

For the curved guess, the "first interior point" (a key number in the formula) is a root of a polynomial with 20 terms.
The complexity of this number is so high that its "Galois group" has an order of 7,257,600.
When they looked at a different type of distance measure (called the $L_3$ norm), the complexity exploded even further, jumping to a polynomial of degree 246.

The "Coupling" Problem
Why does this happen? The authors explain it with a concept called "coupling."

In the simple, straight-line case, the different parts of the problem are "decoupled." You can figure out one part (where the line peaks) without needing to know the other parts (how high the line is). It's like solving a crossword puzzle where you can fill in the top row before touching the bottom row.
In the complex, curved case, everything is "irreducibly coupled." You cannot figure out any single part without knowing all the others simultaneously. It's like a knot where pulling one string tightens the whole mess. This structural knotting is what forces the math into the unsolvable zone.

A New Way to Win: The "Piecewise" Trick
If the perfect numbers for a single complex curve are impossible to write down, is the game over? Not quite. The authors found a clever workaround. Instead of trying to fit one complex curve to the whole range, they suggested breaking the range into smaller pieces (subintervals) and using a simple straight line for each piece.

They proved that if you double the number of pieces, you gain a massive amount of accuracy—about $n + 1$ bits of precision (where $n$ is the degree of the polynomial)—without needing any extra complex math.

For example, using a simple straight line ( $n=1$ ) on 4 different subintervals gives you 8.5 bits of accuracy.
This beats using a single, complex curved line ( $n=2$ ) on the whole range, which only gives 7.9 bits of accuracy, even though the curved line requires more calculation steps.

This means that by simply splitting the problem into smaller, easier chunks, you can get better results with less effort, effectively bypassing the "impossible" math of the single complex curve.

The Big Picture
The paper concludes that this isn't just a fluke for this specific formula. The authors used a famous theorem (Hilbert's irreducibility theorem) to show that this "impossibility" is a general rule. For almost any function you try to approximate with a slightly complex curve, the perfect numbers will likely be unsolvable by radicals.

They also looked at the "breakpoints"—the exact spots where you switch from one straight line to the next in the piecewise method. Even these switching points are mathematically wild, with degrees as high as 16 and Galois groups that are also unsolvable.

In short, the paper reveals a hidden boundary in mathematics: simple approximations are easy to solve, but the moment you try to make them slightly more accurate by adding a curve, the math snaps into a chaotic, unsolvable state. The only way to win is to stop trying to solve the whole puzzle at once and instead solve many small, simple puzzles side-by-side.

Technical Summary: On the Algebraic Complexity of Optimal Polynomial Approximation Constants

1. Problem Statement

The paper investigates the algebraic nature of the constants arising from Chebyshev equiripple (minimax) polynomial approximation of the function $f(t) = \sqrt{1+t^2}$ on the interval $[0, 1]$ . This function is central to computing the Euclidean norm $\sqrt{x^2+y^2}$ , a common operation in digital signal processing where square roots are computationally expensive.

The core problem is to find the optimal coefficients for polynomials $h(t)$ of degree $n$ that minimize the maximum error (either absolute or relative) between $h(t)$ and $\sqrt{1+t^2}$ . While the existence and uniqueness of such polynomials are guaranteed by Chebyshev's theorem, the specific algebraic properties of the resulting optimal coefficients (specifically, whether they can be expressed in closed form using radicals) had not been previously analyzed.

The authors focus on the transition from degree $n=1$ (linear approximation, known as the $\alpha$ -max+ $\beta$ -min algorithm) to degree $n=2$ (quadratic approximation with a rational correction term).

2. Methodology

The authors employ a combination of algebraic geometry, Galois theory, and computational algebra to analyze the equiripple conditions.

Algebraization of the Equiripple System: The optimal approximation is characterized by the error function $d(t) = h(t) - f(t)$ attaining its maximum magnitude with alternating signs at $n+2$ points. The authors translate these conditions (error values and derivative zeros) into a system of polynomial equations by introducing auxiliary variables to eliminate square roots (e.g., $w^2 = 1+t^2$ ).
Resultant Elimination: To find the minimal polynomial for the critical points (specifically the first interior alternation point $k$ ), the authors use classical resultant elimination to reduce the multivariate system to a single univariate polynomial.
Galois Group Analysis: The solvability of the resulting polynomials is determined by computing their Galois groups. The authors utilize Jordan's Theorem (1870), which states that a transitive subgroup of $S_n$ containing a transposition and a $p$ -cycle (for a prime $p$ in a specific range) is the full symmetric group $S_n$ . They verify these conditions by factoring the polynomials modulo specific primes (e.g., $p=17, 257$ ) to identify the cycle types of Frobenius elements.
Hilbert's Irreducibility Theorem: To generalize findings beyond specific norms, the authors apply Hilbert's irreducibility theorem to show that non-solvability is a generic property for families of algebraic target functions.
Piecewise Approximation Analysis: The paper extends the analysis to piecewise polynomials with jointly optimized breakpoints, analyzing the algebraic degree of these breakpoints and the arithmetic efficiency gains.

3. Key Contributions and Results

3.1 The Solvability Phase Transition

The paper establishes a sharp phase transition in algebraic complexity between degree 1 and degree 2 approximations:

Degree 1 (Solvable): For both absolute and relative error formulations, the optimal constants satisfy polynomials of degree 4.
- Relative Error: The optimal coefficient $\alpha$ satisfies an irreducible polynomial of degree 4 with Galois group $C_4$ (cyclic). The constants are expressible by nested radicals.
- Absolute Error: The constants satisfy a polynomial with Galois group $D_4$ (dihedral).
- Mechanism: The system decouples. The location of the critical point is determined independently of the error level, allowing for sequential solution.
Degree 2 (Non-Solvable): The optimal constants for degree 2 are provably not expressible by radicals.
- Absolute Error: The first interior alternation point $k$ is a root of an irreducible polynomial of degree 20. Its Galois group is $S_{10} \times C_2$ (order 7,257,600). Since $S_{10}$ contains the non-abelian simple group $A_5$ , the group is not solvable.
- Relative Error: The corresponding constant satisfies an irreducible polynomial of degree 12 with Galois group $S_{12}$ (order 479,001,600).
- Mechanism: The system is irreducibly coupled. The critical points and the error level depend on each other simultaneously; no variable can be isolated without solving the full system.

3.2 Extension to $L_p$ Norms

The authors extend the analysis to $L_p$ norms, approximating $(1+t^p)^{1/p}$ .

For $p=3$ (the $L_3$ norm), the degree of the minimal polynomial for the degree-2 equiripple constant jumps to 246.
The algebraic complexity grows rapidly with $p$ . The authors conjecture that the degree of the irreducible factor follows a pattern related to $p$ and that the Galois groups are generally full symmetric groups (or wreath products thereof).

3.3 General Impossibility Theorem

Using Hilbert's irreducibility theorem, the authors prove that for the family of functions $f_\lambda(t) = \sqrt{1+\lambda t^2}$ , the degree-2 equiripple constant is generically not expressible by radicals. Specifically, for all rational $\lambda$ outside a "thin set" (a set of density zero), the Galois group remains $S_{10} \times C_2$ .

3.4 Piecewise Approximation and Breakpoints

The paper analyzes piecewise equiripple approximation where the interval $[0, 1]$ is subdivided into $k$ subintervals with jointly optimized breakpoints.

Accuracy Gain: Each doubling of the number of subintervals gains approximately $n+1$ bits of accuracy at zero additional arithmetic cost (since comparisons are considered free in hardware).
Algebraic Complexity of Breakpoints: Even the optimal breakpoints are algebraic numbers of high complexity. For degree-1 approximation with $k=2$ subintervals, the optimal breakpoint is a root of an irreducible polynomial of degree 16 with Galois group $S_8 \times C_2$ , which is also non-solvable.

3.5 Numerical Data

The authors provide numerical equiripple solutions for degrees 1 through 8, analyzing the convergence rate governed by the Bernstein ellipse parameter $\rho \approx 4.612$ . They also provide parallel execution schedules for evaluating these approximations on x86-64 hardware, demonstrating how higher-degree approximations can be computed efficiently despite the complexity of their coefficients.

4. Significance and Claims

The paper claims to establish a previously unobserved connection between Chebyshev approximation theory and the non-solvability of algebraic equations.

Structural Insight: The authors explain that the transition from solvable to non-solvable is driven by a structural dichotomy: the decoupling of critical points in linear approximation versus the coupling in higher-degree approximations.
Generic Non-Solvability: The results suggest that for almost all target functions in algebraic families, the constants required for optimal minimax approximation are not expressible by radicals. This implies that "closed-form" solutions for optimal approximation constants are the exception (degree 1) rather than the rule.
Methodological Contribution: The paper demonstrates the utility of applying Jordan's theorem via modular reduction (Frobenius elements) to determine Galois groups of high-degree polynomials (degree 20 and 246) where direct computation is infeasible.

The authors do not claim to provide new algorithms for computing these constants in practice (as they are non-solvable), but rather to characterize the fundamental algebraic limits of such approximations. The work highlights that while optimal coefficients exist and can be computed numerically to high precision, they lack the algebraic simplicity (radical expressibility) often found in classical engineering approximations.