Description Complexity Bounds for Analytic Approximations of Lipschitz Functions

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 ,÷,\exp \}$ with the variables and rational constants, and their size is $\text{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 $\mathrm{\Delta }$ with $\text{dc}(f)\le C(L\mathrm{/}\mathrm{\Delta }+\lg (1\mathrm{/}\mathrm{\Delta }+2))$ for all $L,\mathrm{\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 $\mathrm{\Delta }\le 1\mathrm{/}36$ and every $L>0$ some $L$-Lipschitz function needs at least $\frac{1}{16}(L\mathrm{/}\mathrm{\Delta }+\lg (1\mathrm{/}\mathrm{\Delta }+2))$ bits. Hence the worst-case description complexity is $\mathrm{\Theta }(L\mathrm{/}\mathrm{\Delta }+\lg (1\mathrm{/}\mathrm{\Delta }+2))$. For functions on $[0,1{]}^d$ the same method gives ${\mathrm{\Theta }}_d((L\mathrm{/}\mathrm{\Delta }{)}^d+\lg (1\mathrm{/}\mathrm{\Delta }+2))$, 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.