DEML Is Incomplete

DEML: deml(x,y) = exp(−x) − ln(y). It gives exp(−x) in one node — an improvement over EML for decay functions. But it cannot build exp(+x) or neg(x). Here is the argument, and where it falls short.

The key identity

Start with what DEML can do. The most useful univariate identity is:

deml(1, deml(x, 1)) = 1/e + x

Algebraic proof:

deml(1, deml(x, 1))
  = exp(−1) − ln(deml(x, 1))
  = exp(−1) − ln(exp(−x) − ln(1))
  = exp(−1) − ln(exp(−x))
  = exp(−1) − (−x)
  = 1/e + x  ✓

This is a 3-node DEML tree that extracts x, shifted by the constant 1/e ≈ 0.368. More generally, for any constant c (DEML-constructible or not):

deml(c, deml(x, 1)) = exp(−c) + x

The slope is always +1. The offset exp(−c) is always positive. This is DEML's only mechanism for producing functions linear in x.

The incompleteness theorem

Theorem (DEML Incompleteness): The operator deml(x,y) = exp(−x) − ln(y) with terminal 1 cannot construct neg(x) = −x or exp(+x) as finite binary trees. Therefore DEML is incomplete: it does not generate all elementary functions.

Proof

Correction (2026-09-12): this argument has a gap. Case 1 assumes every subtree f(x) either grows with x or is bounded, but f(x) = deml(x, 1) = exp(−x) does neither, and then exp(−f(x)) rises toward 1 instead of decaying. The theorem has no Lean proof, and the search further down is evidence, not proof.

Every DEML tree T over {1, x} falls into one of two structural cases:

Case 1: x appears in a left branch. Any path from the root where x enters through a left child eventually contributes through exp(−f(x)). Since f(x) grows with x (or is bounded), exp(−f(x)) decays toward 0. The slope contribution from this case is ≤ 0 and approaches 0.

Case 2: x enters through a right branch via deml(x, 1). The only DEML tree that introduces x through a right branch in a non-decaying way is deml(x, 1) = exp(−x). When this appears as the right child of another DEML node:

deml(c, deml(x, 1)) = exp(−c) + x

Slope = +1. The positive constant exp(−c) > 0 cannot be cancelled by any further DEML composition without introducing neg(x) itself.

The trap: Feeding the output back into the left branch:

deml(1/e + x, 1) = exp(−(1/e + x)) = exp(−1/e) · exp(−x)

This is exponential decay, not growth. Every attempt to use the +x output to produce exp(+x) results in exp(−x) decay.

Consequence for neg(x): neg(x) = −x requires slope −1. But every DEML tree over {1, x} has slope ∈ {0, +1} in its x-linear component. Slope −1 is unreachable. □

Consequence for exp(+x): exp(+x) = deml(neg(x), 1). Since neg(x) is not DEML-constructible, neither is exp(+x). □

Exhaustive search confirmation

An exhaustive search over all DEML trees up to N = 17 nodes, 862,118 trees in all, found no tree computing neg(x) = −x. A tree with k internal nodes has N = 2k + 1 nodes, and there are Catalan(k)·2^k+1 of them over the leaves {1, x}, so each row's count is exact. The error column is the smallest max |T(x) + x| over x in [0.5, 3.14] among all trees with at most N nodes; a tree undefined anywhere on that interval is skipped.

Correction (2026-09-13): this page, its search record and the /theorems card gave the total as 861,952, which is not the sum of the rows below. The rows are right. Re-running the search (the script under Reproduce) gives every count and every error in the table, and a total of 862,118. No script or run in either research repository produces 861,952.

The error is not converging to 0. It stalls at ~0.84. This is consistent with neg(x) being outside the DEML closure entirely, not just requiring a larger tree.

What DEML can and cannot construct

Implication for the BEST router

DEML is not complete, but it is useful. For any expression matching the pattern exp(−f(x)) where f is an EML-constructible subexpression, DEML provides a 1-node primitive that replaces a deep EML tower. The BEST router treats DEML as a special-case gate for negative-exponent patterns: Boltzmann factors, Gaussian decay, Arrhenius equations.

The incompleteness result constrains what DEML can do as a standalone system. As a routing target within BEST, it remains the optimal gate for its native pattern.

Reproduce

Every count and error in the search table, from scratch (Python 3 with NumPy). It prints N, the number of N-node trees, and the best error over all trees with at most N nodes:

import math
import numpy as np
np.seterr(all="ignore")
X = np.linspace(0.5, 3.14, 50)                   # probe grid
trees = [None, np.stack([np.ones_like(X), X])]   # trees[n]: values of every n-node tree
total, best = 0, math.inf
for n in range(1, 18, 2):
    if n > 1:
        trees += [None, np.concatenate([
            (np.exp(-trees[a])[:, None, :]
             - np.log(np.where(trees[n - 1 - a] > 0, trees[n - 1 - a], np.nan))[None, :, :]
            ).reshape(-1, X.size)
            for a in range(1, n - 1, 2)])]
    err = np.nan_to_num(np.abs(trees[n] + X).max(axis=1), nan=math.inf)
    total += len(trees[n])
    best = min(best, err.min())
    print(n, len(trees[n]), round(best, 2))
print("total", total)                            # 862118

The original session summary is python/results/s_r1_deml_incompleteness.json. Its trees_checked is the misstated 861,952, and no search script was kept with it.

Cite this work

Monogate Research (2026). "DEML Is Incomplete: A Structural Argument." (Originally titled "…: A Structural Proof"; corrected 2026-09-12.) monogate research blog. https://monogate.org/blog/deml-is-incomplete

License

CC BY 4.0 — free to share and adapt with attribution. · Code: pip install monogate · Paper: arXiv:2603.21852