The EML Complexity Census

23 functions classified by EML depth. Each row says what its depth rests on: a Lean theorem, a construction, a short argument, or nothing yet.

What "EML depth" means

The EML depth of a function f is the depth of the shallowest EML tree that computes f exactly. For erf, lgamma and Gamma, which have no known exact tree, this table used to record a depth at which an April search found a close approximation. Nothing records that search, and no single tree of that depth comes close (see Reproduce), so those rows are now unverified.

A depth of ∞ means no finite EML tree equals the function exactly. It says nothing about how well finite trees can approximate it.

The census table

Lean-checked: the row names a Lean theorem registered with this site's claims gate, re-proved before every deploy. Construction: an explicit tree reaches that depth, and no shallower tree is possible for an elementary reason. Definition: true by the definition of depth. Argued: a short argument on paper, not checked in Lean. Unverified: a value recorded in April 2026 with no tree, proof or surviving search behind it. Open: unknown.

The open question: EML-4

Whether there are functions that can be approximated to arbitrary precision at depth 4 but not at depth 3 is unknown. In the exact sense the table uses, depth 4 is inhabited: x + 1 has depth exactly 4 on (0, ∞), Lean-checked as x_plus_one_depth_exact_four.

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. (That is about approximation. Exactly, no finite tree equals either one: both are continuous, periodic and not constant.)

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)).

This post said G3 = G1 in closure at depth ≥ 3: that DEML and EXL add efficiency (fewer nodes for specific primitives) but not expressiveness, so the depth classification of every function is the same across G1, G2, and G3. The last part is false. deml(x, 1) = exp(−x) has depth 1 in G2, and no depth-1 EML tree equals exp(−x): each is a constant, eᶜ − ln x, eˣ − ln c or eˣ − ln x. Nothing on record backs the first part.

Reproduce

No public script reproduces the April census. This page pointed to experiments/complexity_census.py, which was never in this repository. The census script on record, eml_complexity_census.py in the private monogate-research repository (2026-04-17), measures something else: how closely a least-squares combination of all trees up to N nodes fits a function. The script below checks the single-tree reading of the erf, lgamma and Gamma rows. It builds every real EML tree of depth at most 3 over {1, x} that is defined on the whole interval, removes duplicates on a 41-point grid, and reports the best maximum error.

import math, numpy as np                                     # pip install numpy
def best_tree(f, a, b, depth=3, n=41):
    x = np.linspace(a, b, n)
    pool = {'1': np.ones(n), 'x': x}                         # expression -> values on the grid
    seen = {tuple(np.round(v, 9)) for v in pool.values()}
    for _ in range(depth):                                   # one more level of eml per pass
        items = list(pool.items())
        for (ea, va), (eb, vb) in ((p, q) for p in items for q in items):
            with np.errstate(all='ignore'):
                v = np.exp(va) - np.log(vb)                  # real eml: undefined where vb <= 0
            k = tuple(np.round(v, 9))
            if np.all(np.isfinite(v)) and k not in seen:
                seen.add(k)
                pool[f'eml({ea},{eb})'] = v
    target = np.array([f(t) for t in x])
    err, expr = min((float(np.max(np.abs(v - target))), e) for e, v in pool.items())
    print(f'{f.__name__} on [{a}, {b}]: {len(pool)} trees of depth <= {depth}; best max error {err:.3g}, by {expr}')
best_tree(math.erf, 0.5, 2.5)
best_tree(math.lgamma, 1.5, 4)
best_tree(math.gamma, 1.5, 4)

Output:

erf on [0.5, 2.5]: 988 trees of depth <= 3; best max error 0.48, by 1
lgamma on [1.5, 4]: 884 trees of depth <= 3; best max error 0.696, by eml(1,eml(eml(1,x),1))
gamma on [1.5, 4]: 884 trees of depth <= 3; best max error 2, by x

Cite 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