The information-theoretic complexity of differentiable functions

Technical Summary: The Information-Theoretic Complexity of Differentiable Functions

Problem Statement
The paper addresses the difficulty of defining a rigorous measure for the complexity of differentiable functions $f: [a, b] \to \mathbb{R}$. While complexity is a ubiquitous concept in systems ranging from climate models to cellular automata, it lacks a unified definition. The author posits that complexity should correspond to the amount of information required to describe an object. Since differentiable functions contain infinite information, the paper proposes defining complexity based on finite approximations. The core intuition is that a function is "simple" if a good approximation can be described with few parameters, and "complex" if it requires many. The paper specifically investigates the relationship between visual simplicity (perceived by the human eye as sharp contrasts and outlines) and information-theoretic measures.

Methodology
The paper introduces a measure called V-complexity, derived from approximating a differentiable function $f$ using piecewise constant functions (step functions). The methodology proceeds as follows:

1. Approximation Framework: The function $f$ is approximated by a step function $q$ such that the $L_1$ norm of the difference, $||f - q||_1$, is less than a maximal error $\epsilon$. The $L_1$ norm is chosen over other $L_p$ norms because it aligns with human visual perception, where the precise location of a sharp boundary (contrast) matters less than the existence of the contrast itself.
2. Equidistribution of Error: To minimize the number of intervals $N(\epsilon)$ required for a given $\epsilon$, the paper utilizes the principle of equidistribution of error. This involves constructing a step function where the error on every sub-interval is equal ($||f - q_k||_{I_k} = \epsilon/N(\epsilon)$). The paper cites evidence suggesting this method yields the minimal number of intervals asymptotically.
3. Asymptotic Analysis: By transforming the recursive calculation of interval endpoints into a differential equation as $\epsilon \to 0$, the paper derives the scaling relationship between the number of intervals and the error.
4. Compression Comparison: To validate the V-complexity, the paper compares it against compression-complexity. This involves discretizing $f$ on a grid, converting the values to a string of symbols, and applying lossless compression algorithms (Run Length Encoding [RLE] and Lempel-Ziv 77 [LZ77/GZIP]). The complexity is defined as the product of the compressed string length and the approximation error as the error approaches zero.
5. Application to Complex Systems: The concept is applied to the "cream-in-coffee" diffusion model. The paper compares two approaches:
   • Apparent Complexity: Simulating the system via a lattice gas automaton, coarse-graining the output, and measuring the compressed length.
   • Modified Effective Complexity: Modeling the system via the diffusion equation (a differentiable function) and calculating its V-complexity.

Key Contributions and Results

• Definition of V-Complexity: The paper establishes that for a differentiable function $f$, the number of intervals $N(\epsilon)$ needed for an $\epsilon$-accurate step function approximation scales as $N(\epsilon) \approx V(f)\epsilon^{-1}$ as $\epsilon \to 0$. The pre-factor $V(f)$ is defined as the V-complexity:
  $$V(f) = \frac{1}{4} \left( \int_a^b |f'(x)|^{1/2} dx \right)^2$$
  This formula provides a concrete, analytical measure of complexity based on the function's derivative.

• Behavioral Examples:

  • Step-like functions: Functions that converge to a step function (e.g., sigmoid functions with steep slopes) have V-complexity approaching zero.
  • Oscillating functions: For functions like $\cos(n\pi x)$, V-complexity grows linearly with the number of oscillations $n$, reflecting the increased detail.
  • Flat functions: Functions that are nearly constant (flat) also exhibit low V-complexity.

• Equivalence Hypothesis: The paper hypothesizes that V-complexity is equivalent to RLE-complexity and, by extension, GZIP-complexity (for monotone sequences or in the limit of small grid sizes). Numerical simulations on families of functions (e.g., $x^\alpha$) show qualitative similarity between the analytical V-complexity and the empirical compression complexity.

• Diffusion Model Application: In the cream-in-coffee model, both the cellular automaton approach (Apparent Complexity) and the diffusion equation approach (V-complexity) yield the same qualitative result: complexity starts at zero (separation), rises to a maximum as the interface mixes and creates gradients, and returns to zero as the system reaches a uniform equilibrium.

Significance and Claims
The paper claims that V-complexity formalizes the intuition that visual simplicity corresponds to low information content. It serves as a bridge between static, deterministic function analysis and the study of Complex Systems.

Specifically, the paper proposes a modification to the definition of Effective Complexity (EC). Standard EC is defined as the length of a concise description of a system's regularities. However, if the regularities are described by a differentiable function, the description length is infinite. The paper suggests amending this definition: the EC of a system whose regularities are described by a differentiable function $f$ is simply the V-complexity of $f$.

The author notes that the equivalence between V-complexity and compression complexity remains a hypothesis supported by simulations rather than a rigorous proof. Similarly, the assumption that equidistribution of error yields the absolute minimal number of intervals is treated as a strong practical assumption. The paper concludes that V-complexity offers a promising tool for characterizing complex systems described by differentiable functions, though generalization to multi-variable functions and further theoretical clarification are left for future work.