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,÷,\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.

Classical Analysis and ODEs (math.CA); Computation and Language (cs.CL)

arXiv:2610.14893 [math.CA]

(or arXiv:2610.14893v1 [math.CA] for this version)

https://doi.org/10.48550/arXiv.2610.14893 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.