The EML Complexity Census
23 functions classified by their minimum EML approximation depth. Three categories: proved, computational observation, and still open.
What "EML depth" means
The EML depth of a function f is the minimum number of EML nodes in any tree that computes f exactly (or, for transcendental functions with no exact representation, the minimum depth of trees that approximate f to arbitrary precision in the sense of the EML Weierstrass theorem).
A depth of ∞ means no finite EML tree can equal the function even in the limit — equivalently, the function requires an infinite sequence of increasingly deep trees. This is the case for non-analytic functions like |sin(x)| and for functions with non-analytic kinks.
The census table
| Function | EML depth | Status |
|---|---|---|
| integers, rationals | 0 | proved |
| exp(x) | 1 | proved |
| eˣ (constant e) | 1 | proved |
| ln(x) | 2 | proved |
| √x | 2 | proved |
| xⁿ (integer n) | 2 | proved |
| sinh(x) | 3 | proved |
| cosh(x) | 3 | proved |
| tanh(x) | 3 | proved |
| sin(x) over ℂ | 1 | proved |
| sin(x) over ℝ | ∞ | proved |
| cos(x) over ℝ | ∞ | proved |
| erf(x) | 3 | computational |
| lgamma(x) | 3 | computational |
| Gamma(x) | 3 | computational |
| Fourier series (finite) | 3 | proved |
| wave equation ψ = Ae^(ikx) | 3 | proved |
| |sin(x)| | ∞ | proved |
| |x| | ∞ | proved |
| sawtooth wave | ∞ | proved |
| Heaviside H(x) | ∞ | proved |
| floor ⌊x⌋ | ∞ | proved |
| sin(sin(x)) | ? | open |
Proved: formal proof exists. Computational: exhaustive or deep search confirms depth, no formal proof. Open: depth unknown, active question.
The open question: EML-4
The EML depth hierarchy so far has strata at 0, 1, 2, 3, and ∞. Whether there exist functions requiring exactly depth 4 — that is, functions approximable to arbitrary precision at depth 4 but not depth 3 — is currently unknown.
Candidates include sin(sin(x)), exp(sin(x)), and related
compositions of EML-3 functions. Current dictionary search (depth ≤ 4) has not confirmed
whether these require depth 4 or whether depth 3 is sufficient with the right tree structure.
Grammar comparison: G1, G2, G3
The EML complexity census applies to grammar G1 (EML only). Grammar G2 adds DEML
(deml(x,y) = exp(−x) − ln(y)). Grammar G3 adds EXL
(exl(x,y) = exp(x) · ln(y)).
Key result: G3 = G1 in closure at depth ≥ 3. DEML and EXL add efficiency (fewer nodes for specific primitives) but not expressiveness. The depth classification of every function is the same across G1, G2, and G3.
Reproduce
python experiments/complexity_census.py
# Prints depth classifications for all 23 functions
# Flags proved vs. computational vs. openCite this work
Monogate Research (2026). "The EML Complexity Census: 23 Functions Classified by Depth." monogate research blog. https://monogate.org/blog/complexity-census
License
CC BY 4.0 — free to share and adapt with attribution. ·
Code: pip install monogate ·
Paper: arXiv:2603.21852