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

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

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 (861,952 trees) found no tree computing neg(x) = −x:

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

python python/results/s_r1_deml_incompleteness.json  # results
# Search script:
# python -c "import math; d=lambda x,y:math.exp(-x)-math.log(y); print(d(1,d(2,1)), 1/math.e+2)"

Cite this work

Monogate Research (2026). "DEML Is Incomplete: A Structural Proof." 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