💻 computer science

Rigorous High-Order Hausdorff Dimension Estimation of Limit Sets of Continued Fraction Iterated Function Systems via B-Splines

This paper presents a rigorous, high-order method for estimating the Hausdorff dimensions of continued fraction limit sets by approximating the Perron-Frobenius operator with B-splines and proving an analogue of Falk and Nussbaum's "hidden positivity" result to establish certified upper and lower bounds.

Original authors: Jacob Brown

Published 2026-04-23

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jacob Brown

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

Imagine you are an architect trying to measure the "roughness" or "complexity" of a never-ending, infinitely detailed shape. In math, this shape is called a limit set, and its complexity is measured by something called the Hausdorff dimension.

Think of the Hausdorff dimension like a "fractal ruler." A straight line has a dimension of 1. A flat square has a dimension of 2. But a fractal? It's somewhere in between. It's so crinkly and detailed that it's more than a line but not quite a full surface. For example, the famous "Cantor Set" (a line with infinite holes punched in it) has a dimension of about 0.63.

The paper you're asking about is about a new, super-precise way to measure these dimensions for a specific type of fractal generated by continued fractions (a way of writing numbers like $1/(1 + 1/(2 + 1/(3...)))$ ).

Here is the breakdown of their method using simple analogies:

1. The Problem: The "Infinite Maze"

The authors are studying systems where you have an infinite number of rules (maps) that shrink and shift a shape over and over again.

The Analogy: Imagine a magical mirror that reflects a room, but inside that reflection, there are smaller mirrors, and inside those, even smaller ones, forever. The "limit set" is the tiny, intricate pattern you see if you look deep enough into the infinite mirrors.
The Challenge: To measure the complexity of this pattern, mathematicians use a tool called the Perron-Frobenius operator. Think of this as a giant, complex machine that takes a guess at the shape's complexity and refines it. However, this machine is hard to run on a computer because it deals with infinite possibilities.

2. The Old Way: The "Low-Res Pixel" Approach

Previous methods tried to approximate this machine by breaking the shape into tiny, simple pieces (like pixels on a low-resolution screen).

The Flaw: To get a good picture, you needed millions of tiny pixels. If you tried to use bigger, smoother shapes to get a better picture faster, the math would break. Specifically, the computer would start producing "negative probabilities" (which don't make sense in this context), causing the rigorous proof to fail.
The Rule: There was a mathematical law saying, "If you want to keep the math honest (positive), you can only use simple, low-order shapes." This meant slow, tedious calculations.

3. The New Solution: The "B-Spline" Magic

The authors, led by Jacob Brown, introduced a new tool called B-splines.

The Analogy: Instead of using jagged, blocky pixels (like Lego bricks), imagine using smooth, flexible clay. B-splines are mathematical curves that can bend smoothly to fit the shape perfectly.
The Advantage: Because these "clay curves" are so smooth and flexible, the computer can get a highly accurate picture using far fewer pieces. It's like drawing a circle with a few smooth strokes of a pen instead of thousands of tiny straight lines. This allows the method to converge (get the right answer) much faster—specifically, three times faster than the old methods.

4. The "Hidden Positivity" Trick

This is the most clever part of the paper.

The Problem: Even with smooth clay, if you aren't careful, the math might still dip below zero (negative numbers), which breaks the proof.
The Discovery: The authors proved a concept they call "Hidden Positivity."
- The Metaphor: Imagine you are balancing a stack of plates. Some plates are heavy (positive numbers) and some are light (negative numbers). If you just look at the plates individually, the stack might look like it's going to fall (negative result).
- However, the authors showed that if you look at the entire stack as a whole system, the "heaviness" of the positive plates is so dominant that the whole structure remains stable and upright, even if a few light plates are technically negative.
- They proved that their smooth B-spline method keeps the "stack" stable. This allows them to use the high-speed, high-accuracy smooth curves without breaking the mathematical rules.

5. The Result: A Super-Precise Ruler

By combining these smooth curves (B-splines) with the "hidden stability" trick, the authors created a method that:

Is Rigorous: It doesn't just guess; it mathematically proves the answer is within a specific tiny range (Upper and Lower bounds).
Is Fast: It gets to the answer much quicker than previous methods because it doesn't need millions of tiny steps.
Works in 2D: They showed this works not just for 1D lines, but for 2D shapes (like complex patterns on a flat surface).

Summary

Think of this paper as upgrading from a pixelated, blocky map to a high-definition, smooth satellite image for measuring the complexity of infinite fractal patterns. They found a way to use the smooth, high-definition tools without the map falling apart, allowing them to measure these infinite shapes with incredible speed and mathematical certainty.

In short: They found a way to measure the "roughness" of infinite, crinkly shapes using smooth, flexible math tools, proving that you can be both fast and mathematically perfect at the same time.

1. Problem Statement

The paper addresses the challenge of rigorously estimating the Hausdorff dimension of limit sets associated with Conformal Iterated Function Systems (CIFSs), specifically those arising from continued fractions.

Context: While Hutchinson's formula allows for exact dimension calculation for finite systems of similarities, it fails for systems with infinitely many maps or non-similar maps (common in continued fractions).
Theoretical Framework: Mauldin and Urbański established that the Hausdorff dimension $s$ of a CIFS limit set corresponds to the unique parameter where the Perron-Frobenius operator ( $L_s$ ) has a leading eigenvalue of 1 with a strictly positive eigenfunction.
The Obstacle: Numerical methods for approximating $L_s$ require positivity preservation to derive rigorous bounds (upper and lower) on the dimension. However, Korovkin's Theorem dictates that any linear approximation scheme preserving positivity is limited to second-order accuracy. To achieve higher-order convergence (essential for high-precision estimates), one must typically sacrifice strict positivity, which breaks standard rigorous bounding techniques.
Previous Work: Falk and Nussbaum introduced the concept of "hidden positivity," showing that operators could map a specific cone of functions into itself, allowing for higher-order polynomial interpolants. However, their method required iterating the operator on the alphabet (increasing computational cost) and was primarily developed for piecewise polynomials.

2. Methodology

The author proposes a Finite Element Method (FEM) approach using B-splines as basis functions to approximate the Perron-Frobenius operator.

A. B-Spline Quasi-Interpolation

Instead of standard interpolation, the method employs quasi-interpolation.

Basis: Degree $n$ B-splines defined on a uniform knot sequence.
Operator: The function $f$ is approximated by $Qf = \sum (Q_k f) b_k$ , where $Q_k$ are linear functionals acting on function values at midpoints of knot intervals.
Advantage: This approach avoids solving large linear systems for coefficients and allows for explicit error bounds.

B. Rigorous Error Bounds

The paper derives explicit error estimates for the quasi-interpolant and its derivatives:

Approximation Error: $|f(x) - Qf(x)| \leq C h^{n+1} \|f^{(n+1)}\|_\infty$ .
Derivative Error: Bounds are established for partial derivatives using a computable version of the Bramble-Hilbert Lemma.
Eigenfunction Bounds: The method utilizes known bounds on the derivatives of the eigenfunction $f_s$ (from Falk and Nussbaum) to quantify the error term ( $\epsilon$ ) in the approximation. This allows the construction of two matrices, $A_h$ and $B_h$ , such that $(1-\epsilon)Qf_s \leq f_s \leq (1+\epsilon)Qf_s$ .

C. Hidden Positivity for B-Splines

The core theoretical contribution is proving that B-spline quasi-interpolants satisfy the "hidden positivity" condition required for rigorous bounding.

The Cone: The method defines a cone $K_M$ of functions where the logarithm of the function is Lipschitz continuous with constant $M$ (i.e., $|\log f(x) - \log f(y)| \leq M|x-y|$ ).
Theorem: The author proves that if a positive function $f$ belongs to $K_M$ , and the mesh size $h$ is sufficiently small, the B-spline quasi-interpolant $Qf$ is strictly positive and belongs to a cone $K_{M'}$ with $M' < M$ .
Significance: This allows the application of the Perron-Frobenius theorem for cones (Lemma 2.12), enabling the calculation of rigorous spectral radius bounds (and thus dimension bounds) even though the B-spline approximation matrix may contain negative entries.

D. Dimensionality

The method is generalized from 1D to $d$ -dimensions ( $d \geq 2$ ) using tensor products of B-splines, maintaining the same convergence properties and hidden positivity results.

3. Key Contributions

Higher-Order Convergence: The method achieves order $n+1$ convergence (e.g., order 3 for quadratic B-splines), overcoming the second-order limit of traditional positivity-preserving schemes.
Resolution of Falk-Nussbaum Conjecture: The paper proves that operator iteration (iterating the alphabet) is not necessary for the method to work. This significantly reduces computational complexity compared to previous approaches.
Extension to Higher Dimensions: The "hidden positivity" result is rigorously extended to multi-dimensional B-spline interpolants, enabling the study of higher-dimensional continued fraction systems (e.g., Apollonian gaskets).
Explicit Rigorous Bounds: The paper provides a complete framework for calculating rigorous upper and lower bounds, including explicit formulas for all constants involved in the error estimates.

4. Numerical Results

The author validates the method using quadratic B-splines ( $n=2$ ) in both 1D and 2D.

1D Examples:
- Alphabet $E=\{1, 2\}$ : Achieved an estimate of $0.531280506277205$ with an error bound of $10^{-15}$ , matching known high-precision results.
- Convergence: Tables 4.2–4.4 demonstrate order 3 convergence (error $\propto h^3$ ) for various alphabets, including large sets like $\{1, \dots, 100\}$ .
- Constraint: The mesh size $h$ must satisfy $h < 1/\max(E)$ to resolve large elements in the alphabet.
2D Examples:
- Applied to systems in $\mathbb{R}^2$ (e.g., $E = \{(1,0), (1,1), (1,-1), (2,0)\}$ ).
- Convergence: Tables 4.6–4.8 confirm order 3 convergence in 2D as well.
- Results: Provided rigorous bounds for complex 2D limit sets, such as those related to the Apollonian gasket and specific continued fraction subsystems.

5. Significance

This paper represents a significant advancement in the computational theory of fractal geometry:

Efficiency: By eliminating the need for operator iteration and utilizing high-order B-splines, the method is computationally more efficient than previous high-accuracy techniques.
Rigor: It provides a mathematically rigorous path to high-precision dimension estimates, avoiding the heuristic nature of many numerical approximations.
Generality: The extension to arbitrary dimensions opens the door to rigorous analysis of complex, high-dimensional dynamical systems and fractals that were previously difficult to quantify with guaranteed error bounds.
Practicality: The use of explicit constants and the resolution of the "iteration" conjecture make the method immediately applicable to a wide range of problems in dynamical systems and number theory.