The Operator Zoo: Which exp-ln Gates Are Complete?

Correction (2026-09-13): this post said the EMN question below has a definitive answer. It does not: that EMN is approximately but not exactly complete is a conjecture (T24), and the sketches for both halves stop short. The DEML template has a gap too (T13), so the Incomplete entries are conjectures, except that over ℝ no EAL tree approximates −x.

Second correction (2026-09-13): the Type A paragraph said DEML fails the way EAL does, by slope sign. For DEML that argument has a gap: deml(x, 1) = exp(−x) has negative slope. EDL's "cannot build addition" is conjecture C1 of the preprint, not a result. And the later 16-operator census conjectures the opposite of this table for EXL, EDL and POW (which is EPL), and for EAL over ℂ: exactly complete (T26). Neither classification is proved.

The DEML incompleteness argument gave us a template. Apply it to every operator of the form f(exp(±x), ±ln(y)) and catalog the results. Seven operators. Five sessions. One surprise.

The Operators

Two new operators we explored:

• POW(x,y) = y^x: This equals exp(x·ln(y)). Remarkable fact: pow(1, x) = x — the identity function in a single node. But exp(x) still requires e as a leaf, and e is not constructible from {1} under POW.
• LEX(x,y) = ln(exp(x)−y): At y = 0: lex(x, 0) = x — also the identity in one node. But 0 is not constructible from {1} under LEX.

The DEML Template

The DEML argument proposed: find all “linear mechanisms” — compositions that produce linear functions of x. If all of them have the same sign on their slope, the operator cannot build neg(x) = −x, which blocks all arithmetic.

DEML: deml(1, deml(x,1)) → x + 1/e (slope +1). The argument says all paths give slope +1, but that step has a gap (T13). Conjectured incomplete.

EAL: eal(1, eal(x,1)) = e + x (slope +1). eal(eal(1,x), 1) = e^e · x (slope e^e). All positive. Incomplete.

The EMN Exception

EMN(x,y) = ln(y) − exp(x) = −EML(x,y).

The slope template produces a surprise. emn(emn(1,x), 1):

emn(1,x) = ln(x) − e
emn(ln(x)−e, 1) = ln(1) − exp(ln(x)−e) = −exp(−e)·x = −x/e^e

Slope: −1/e^e ≈ −0.066. Negative! The DEML template cannot prove EMN incomplete.

We ran an exhaustive search over N ≤ 7 trees. The best neg(x) approximation found uses 8 nodes and achieves error ~1.5 × 10⁻⁷ at x = 1.5, growing to ~2.6 × 10⁻⁵ at x = 10. The mechanism: complex intermediate values (via ln(−e) = 1 + iπ) construct an approximate ln(x), then emn(ln(x), 1) = −x exactly.

Is this an exact neg(x)? No — the “approximate ln” introduces exponentially small but nonzero error. Whether EMN is exactly complete remains open.

The Two Incompleteness Mechanisms

The census reveals two distinct reasons a gate can be incomplete:

Type A — Wrong slope sign: All linear mechanisms have the same slope sign, so no finite composition can produce the opposite sign. EAL fails this way over ℝ: every real EAL tree T = exp(A) + ln(B) has T′ = A′e^A + B′/B ≥ 0. DEML was counted here too, but deml(x, 1) = exp(−x) has negative slope, so for DEML the argument has a gap (T13).

Type B — Missing constant: The constant e is not constructible from the gate applied to {1}. EXL and POW both fail here. Without e, you can’t build exp(+x), and without that the operator cannot generate arbitrary elementary functions. (The later census conjectures both complete over ℂ, with e as a constant: T26.)

EMN escapes both: It has negative slopes (Type A doesn’t apply) and it CAN build nonzero constants — emn(1,1) = −e in one node.

The EMN Question — A Conjectured Answer

Is EMN complete? The conjectured answer: approximately complete, not exactly complete. Neither half has a proof (T24).

EMN is not exactly complete (conjectured): No finite EMN tree should compute ln(x) exactly for all x. The suggested obstruction is structural — every EMN output ln(R) − exp(L) has a nonzero exp(L) residual, and driving it to zero requires infinite depth (L → −∞). The growth-rate argument for this (sessions EMN-1 through EMN-3) is on paper, stops at an “infinite regress”, and has no Lean proof.

EMN is approximately complete (conjectured): For any elementary function f and ε > 0, there exists a finite EMN tree T such that |Re(T(x)) − f(x)| < ε on any compact interval. The mechanism: complex intermediate values (via ln(−e) = 1 + iπ) route around the sign barrier. In the searches up to 8 nodes, the error falls doubly-exponentially with tree size.

The three completeness classes would form a clean trichotomy: EML (exactly complete), EMN (approximately complete), all others (incomplete). See the Completeness Trichotomy post for the sketches.

Reproduce: the EDL addition search

Conjecture C1 in the preprint says no finite EDL tree represents addition or subtraction, supported by a search to N ≤ 6. This re-runs it: every EDL tree with at most 6 nodes over {1, x, y}, and with at most 5 over {1, e, x, y}, evaluated at 10 random points in (0.3, 3)². A tree with an undefined part (ln of a non-positive value, or division by ln 1 = 0) is skipped.

import math, numpy as np                                # pip install numpy
np.seterr(all='ignore')
rng = np.random.default_rng(7); X, Y = rng.uniform(0.3, 3.0, size=(2, 10))
for leaves, nmax in (({'1': 1.0, 'x': X, 'y': Y}, 6), ({'1': 1.0, 'e': math.e, 'x': X, 'y': Y}, 5)):
    level = [[(t, np.broadcast_to(np.float64(v), (10,)) * 1.0) for t, v in leaves.items()]]
    seen = {tuple(np.round(v, 9)) for _, v in level[0]}
    best = {'x+y': (math.inf, ''), 'x-y': (math.inf, '')}
    for n in range(1, nmax + 1):                        # edl(a, b) = e^a / ln b; a tree with an undefined part is undefined
        new = []
        for i in range(n):
            for ta, a in level[i]:
                for tb, b in level[n - 1 - i]:
                    v = np.exp(a) / np.log(b)
                    k = tuple(np.round(v, 9))
                    if np.all(np.isfinite(v)) and k not in seen:
                        seen.add(k); new.append((f'edl({ta},{tb})', v))
                        for name, target in (('x+y', X + Y), ('x-y', X - Y)):
                            best[name] = min(best[name], (float(np.max(np.abs(v - target))), f'edl({ta},{tb})'))
        level.append(new)
    total = sum(math.comb(2 * n, n) // (n + 1) * len(leaves) ** (n + 1) for n in range(nmax + 1))
    print(f"leaves {sorted(leaves)}, <= {nmax} nodes: {total:,} trees, {sum(map(len, level)):,} distinct defined at all 10 points; "
          f"best max error to x+y {best['x+y'][0]:.3g}, to x-y {best['x-y'][0]:.3g}")

Output:

leaves ['1', 'x', 'y'], <= 6 nodes: 323,175 trees, 247 distinct defined at all 10 points; best max error to x+y 3.72, to x-y 1.64
leaves ['1', 'e', 'x', 'y'], <= 5 nodes: 187,796 trees, 5,773 distinct defined at all 10 points; best max error to x+y 1.29, to x-y 1.64

A search to a fixed size is evidence, not a proof; C1 stays a conjecture.

Sessions Z1–Z9 · Direction 1 of the Research Roadmap