💻 computer science

On the Computational Content of Moduli of Regularity and their Logical Strength

This paper investigates the computational content and logical strength of moduli of regularity, demonstrating their ability to algorithmically compute zeros of continuous functions and paths in infinite trees while establishing that no tame nonstandard principle can replace compactness with metric boundedness in this context.

Original authors: Ulrich Kohlenbach

Published 2026-03-05

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Ulrich Kohlenbach

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.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 Big Picture: Finding the Needle in the Haystack

Imagine you are looking for a specific spot on a map where a river crosses a road. In math terms, you are looking for a "zero" (a point where a function equals zero).

Sometimes, finding this spot is easy. But often, you can't find the exact spot immediately. Instead, you have a map (an algorithm) that gives you better and better guesses. You get closer and closer to the river, but you never quite know exactly when you've arrived.

This paper is about a special tool called a "Modulus of Regularity." Think of this tool as a guarantee or a speedometer for your search. It tells you: "If your guess is this close to the river (within distance X), then you are guaranteed to be within distance Y of the actual crossing point."

The author, Ulrich Kohlenbach, is asking two big questions:

Can we actually build a machine (algorithm) that uses this guarantee to find the spot?
How much "logical power" (or brainpower) does it take to believe that this guarantee exists in the first place?

1. The Magic of the "Regularity" Guarantee

In the world of continuous optimization (like training AI or designing bridges), we often deal with functions that have many solutions, not just one.

The Problem: You have a function $F$ . You want to find where $F(x) = 0$ . You have a sequence of guesses getting closer and closer.
The Regularity: If the function is "regular," it means the landscape isn't weirdly flat or broken. If you are close to zero, you are physically close to a solution.
The Modulus: This is the specific rule that says, "If your error is less than $1/1000$ , you are within $1/10$ of a solution."

The Analogy: Imagine you are walking in the dark toward a campfire.

Without Regularity: You might feel heat, but it could be a warm rock, a hot stone, or the fire. You can't be sure how close you are.
With a Modulus of Regularity: It's like having a thermometer that says, "If the temperature is above 50°C, you are definitely within 5 meters of the fire." This allows you to stop guessing and start walking confidently toward the fire.

2. The Main Discovery: Turning Guarantees into Algorithms

The paper proves something very cool: If you have this "Regularity Guarantee" (the modulus), you can actually build a computer program to find the solution.

Compact Spaces (The Bounded Room): If you are searching in a finite, bounded area (like a room), and you have this guarantee, you can write a simple, step-by-step recipe (a "primitive recursive functional") that will find the zero. It's not magic; it's just a very efficient search.
The "Leftmost Path" Trick: The author shows this works even for infinite trees (like a family tree that never ends). If you have the guarantee, you can find the "leftmost" infinite path through the tree. This is a classic problem in computer science, and the paper shows the "Regularity Modulus" is the key that unlocks the solution.
The "Best" Solution: If you are in a curved space (like a bowl) and there are many zeros, the paper shows you can use this tool to find the one zero that is closest to the center (the "minimal norm").

The Takeaway: The existence of this "Regularity Modulus" is a superpower. It turns a vague promise ("you'll get close eventually") into a concrete instruction manual ("here is exactly how to get there").

3. The Catch: The Cost of the Guarantee

Here is the twist. While having the guarantee allows you to build an algorithm, proving that the guarantee exists is very expensive in terms of logic.

The Weak Version (Just the Promise): If you just say, "For every distance, there is a closer distance," this is a relatively weak logical statement. It's like saying, "There is a path out of this maze."
The Strong Version (The Modulus): If you demand a specific rule that calculates how close you are (the Modulus), the logical cost skyrockets.

The Analogy:

Weak Version: A tourist says, "I'm sure there's a way out of this forest." (This is easy to believe).
Strong Version: A tourist says, "I have a GPS device that tells me exactly how many steps to the exit." (This requires a lot of complex machinery to build and verify).

The paper shows that to prove this "GPS device" (the modulus) exists for general continuous functions, you need a very strong logical system called Arithmetical Comprehension (ACA₀). This is a level of mathematical logic that is much stronger than what is needed for simple geometry.

4. Why Can't We Just Relax the Rules?

In math, we often try to make things easier by removing strict rules. For example, instead of requiring the search area to be a "compact" (finite/bounded) room, can we just say it's "bounded" (has a limit but might be infinite)?

The author tries to see if we can replace the strict "Compactness" rule with a weaker "Boundedness" rule using some fancy non-standard logic tricks.

The Result: No.
The Analogy: You can't replace a solid, finite room with an infinite hallway and expect the same search algorithm to work without breaking. The paper proves that if you try to weaken the rules too much, the "Regularity Modulus" disappears, and you lose your ability to compute the solution.

5. The Logical "Price Tag"

The paper concludes by analyzing the "logical price tag" of these concepts:

The Existence of the Modulus is equivalent to a powerful logical principle called $\Sigma^0_1$ -LEM (a version of the Law of Excluded Middle).
In simple terms: To believe that a "Regularity Modulus" exists, you must accept a specific type of logical certainty that says, "Either a solution exists within this range, or it doesn't, and we can decide which."
Without this strong logical assumption, you cannot guarantee that the "Modulus" exists, even if the function looks nice and continuous.

Summary for the General Audience

This paper is about trust and efficiency in mathematics and computing.

Trust: It asks, "If we trust that a function behaves nicely (Regularity), can we trust that we can find the answer?"
Efficiency: The answer is Yes, but only if we have a specific "rulebook" (the Modulus) that tells us how fast we are converging.
The Cost: The paper reveals that creating this "rulebook" is logically very heavy. It requires a high level of mathematical certainty. If you try to cut corners and use weaker logic, the rulebook vanishes, and you are left with a search that might never finish.

In a nutshell: The "Modulus of Regularity" is a magical compass. If you have it, you can find your way out of any mathematical maze. But the paper proves that making that compass is a very difficult logical task, and you can't make a cheaper version of it without losing its power.

1. Problem Statement

The paper investigates the computational and logical strength of the existence of moduli of regularity for solution sets of equations, specifically in the context of continuous optimization and fixed-point theory.

Regularity: A solution set $zer F = \{x \mid F(x)=0\}$ is "regular" if sufficiently good approximate solutions are guaranteed to be close to an actual solution.
The Gap: While the existence of a modulus of regularity is a classical fact for continuous functions on compact metric spaces (proven in prior work [21]), it is generally not computable in a constructive sense.
The Core Question: What is the precise logical strength required to prove the existence of such a modulus? How does this strength compare to the weaker $\forall\exists$ -form of regularity (without a modulus)? Furthermore, can one compute actual zeros or specific solutions (like the minimal norm zero) given a modulus of regularity?

2. Methodology

The author employs a combination of Constructive Analysis, Proof Mining, and Reverse Mathematics:

Constructive/Computational Analysis: The paper uses Kleene's $S1-S8$ functionals and primitive recursive functionals to explicitly construct algorithms that compute zeros of functions given a modulus of regularity.
Reverse Mathematics: The logical strength of the existence of moduli is analyzed within subsystems of second-order arithmetic (e.g., $WKL_0$ , $ACA_0$ ) and intuitionistic systems ($EL$).
Weihrauch Degrees & Logical Principles: The paper relates the existence of moduli to principles like the $\Sigma^0_1$ -Law of Excluded Middle ( $\Sigma^0_1$ -LEM) and Arithmetical Comprehension ( $ACA_0$ ).
Nonstandard Analysis: It investigates whether "tame" nonstandard principles (like the Uniform Boundedness Principle $\exists$ -UBX) can replace compactness assumptions to guarantee regularity, a common technique in proof mining.

3. Key Contributions and Results

A. Computational Extraction of Zeros (Theorems 2.3 & 2.4)

The paper demonstrates that a modulus of regularity is sufficient to constructively compute zeros, even though the modulus itself is not computable from the function alone.

Compact Metric Spaces: For a continuous function $F: X \to \mathbb{R}$ on a compact metric space $X$ , if a modulus of regularity $\rho$ is provided, there exists a primitive recursive functional $\Phi$ that computes a zero of $F$ (provided $zer F \neq \emptyset$ ). The convergence rate is explicitly determined by $\rho$ .
Uniformly Convex Banach Spaces: If $K$ is a compact subset of a uniformly convex Banach space and the zero set is convex, the functional can compute the zero of minimal norm (the metric projection of 0 onto the zero set). This is significant for convex optimization problems.

B. Application to Infinite Trees (Theorem 2.8)

The concept of regularity is applied to the problem of finding infinite paths in binary trees (König's Lemma).

The existence of a modulus of regularity for an infinite binary tree allows for the computation of the leftmost infinite path.
This is achieved via a Kalmar elementary functional (a specific type of primitive recursive functional), transforming the modulus of regularity directly into the path.

C. Logical Strength and Equivalences (Theorem 2.11)

The paper establishes precise logical equivalences regarding the strength of regularity:

$\forall\exists$ -Regularity vs. Modulus:
- The $\forall\exists$ -form of regularity (without a modulus) is equivalent to Weak König's Lemma ( $WKL_0$ ) in classical reverse mathematics.
- However, the existence of a modulus of regularity is much stronger. It implies the $\Sigma^0_1$ -Law of Excluded Middle ( $\Sigma^0_1$ -LEM).
- Consequently, the existence of a modulus is equivalent to Arithmetical Comprehension ( $ACA_0$ ).
Intuitionistic Implication: Even in intuitionistic logic (system $EL$), the $\varepsilon$ - $\delta$ form of regularity implies $\Sigma^0_1$ -LEM. This explains why the modulus is not computable in a purely constructive setting without additional strong axioms.

D. Failure of "Tame" Nonstandard Principles (Proposition 2.5)

The paper addresses a question in proof mining: Can one replace the compactness assumption with metric boundedness using "tame" nonstandard principles (like $\exists$ -UBX) to still guarantee regularity?

Result: The answer is no. The paper proves that adding the principle "Every nonexpansive function with a zero has a modulus of regularity" (NE-Reg) to a formal system of analysis leads to the provability of sentences that are false in standard bounded hyperbolic spaces (specifically, it implies the strong convergence of Krasnoselski iterations, which is known to fail in $l^2$ ).
This shows that regularity is intrinsically tied to compactness and cannot be derived from boundedness alone, even with strong nonstandard axioms, without losing classical correctness.

4. Significance

Clarification of Computational Content: The paper resolves the apparent paradox that while regularity is a classical fact on compact spaces, it is not constructively valid. It shows that the modulus acts as a "black box" oracle: if one has the modulus, one can compute the solution effectively (primitive recursively), but obtaining the modulus itself requires non-constructive logical strength ( $ACA_0$ ).
Unification of Concepts: It unifies the study of regularity in optimization with classical logical principles (like $\Sigma^0_1$ -LEM) and combinatorial problems (finding paths in trees).
Limits of Proof Mining: By disproving the possibility of replacing compactness with boundedness via tame nonstandard principles for regularity, the paper sets clear boundaries for the applicability of proof mining techniques in non-compact settings.
Algorithmic Construction: It provides explicit algorithms (functionals) for computing zeros and minimal norm solutions, which is valuable for the theoretical analysis of iterative algorithms in optimization.

In summary, Kohlenbach demonstrates that the modulus of regularity is a powerful computational tool that bridges the gap between approximate and exact solutions, but its existence carries a high logical cost ( $ACA_0$ ), distinguishing it sharply from the weaker, purely existential regularity conditions.