Description Complexity Bounds for Analytic Approximations of Lipschitz Functions
Abstract
We study how many bits are needed to write down an elementary analytic expression that uniformly approximates a Lipschitz function. Expressions are finite trees over the basis $\{+,-,\times,\div,\exp\}$ with the variables and rational constants, and their size is $\dc(f)$, the length of the shortest description of $f$ in a fixed binary description language. For functions of one variable we prove that every $L$-Lipschitz $F:[0,1]\to[0,1]$ has an everywhere-defined approximant of accuracy $\Delta$ with $\dc(f)\le C\,(L/\Delta+\lg(1/\Delta+2))$ for all $L,\Delta>0$, by a linear spline smoothed with logistic ramps in a description language with one repetition construct. We prove a matching lower bound valid for \emph{every} description language: for $\Delta\le 1/36$ and every $L>0$ some $L$-Lipschitz function needs at least $\tfrac1{16}(L/\Delta+\lg(1/\Delta+2))$ bits. Hence the worst-case description complexity is $\Theta(L/\Delta+\lg(1/\Delta+2))$. For functions on $[0,1]^d$ the same method gives $\Theta_d\bigl((L/\Delta)^d+\lg(1/\Delta+2)\bigr)$, using a tensor-product spline whose coefficients are mixed second differences and cost $O(d)$ bits each. Without the repetition construct the upper bounds carry an additional logarithmic factor, whose necessity for plain expression trees is left open. A reference encoder, decoder and evaluator confirm the constructions numerically, and figures and tables report the checks.
