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 +,-,×,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]→[0,1] has an everywhere-defined approximant of accuracy Delta with dc(f)≤ 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 every description language: for Delta≤ 1/36 and every L>0 some L-Lipschitz function needs at least tfrac116(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 Thetadbigl((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.