The Pumping Lemma for EML Trees

How many zeros can a depth-k EML tree have? The theoretical bound is 2^k. The observed bound is roughly O(k). The gap is enormous, and closing it would strengthen the Infinite Zeros Barrier.

The theoretical bound

Theorem (EML Pumping Lemma): Every depth-k real EML tree has at most 2^k real zeros on any bounded interval.

The proof is by induction on depth:

Base case (k = 1). A depth-1 tree is eml(x, c) = exp(x) − c for some constant c. exp is strictly monotone, so this has at most 1 zero. 1 ≤ 2¹. ✓

Inductive step. Suppose every depth-(k−1) tree has at most 2^k−1 zeros. A depth-k tree is T = eml(f, g) = exp(f) − g, where f and g are depth-(k−1) trees. T(x) = 0 iff exp(f(x)) = g(x). Both exp(f) and g are real-analytic. By a Rolle's theorem argument on the difference, the zero count of exp(f) − g is bounded by the sum of zero counts of their derivatives, which satisfies the recurrence zeros(k) ≤ 2 · zeros(k−1), giving zeros(k) ≤ 2^k. ∎

The observed bound

In the exhaustive N=12 search (1,704,034,304 trees), zero counts were recorded for every tree evaluated. The observed distribution:

• ~95% of trees: 0 zeros on [−π, π]
• ~4.9% of trees: 1 zero
• < 0.1% of trees: 2 or more zeros
• Maximum observed: O(k) zeros for depth-k trees

The theoretical bound of 2^k = 4096 for k = 12 is never approached. The actual maximum across 1.7 billion trees is in single digits.

The conjecture

Conjectured tight bound: Every depth-k real EML tree has at most O(k) zeros on any bounded interval — linear in depth, not exponential.

This is currently unproved. It has strong computational support from the N=12 search. If true, it would be a significantly stronger version of the Infinite Zeros Barrier: not just "finitely many zeros" but "at most linearly many."

sin(x) has infinitely many zeros, so it would be excluded not just by the "finite zeros" argument but by the tighter "linear in depth" argument too.

Proof strategy

A natural approach: trace zero-counting through EML composition more carefully. The Rolle's theorem bound in the inductive step counts zeros of the derivative, which is itself a ratio of EML trees (log-differentation). If derivative trees have O(k−1) zeros rather than 2^k−1, the bound tightens to O(k).

The challenge: the derivative of an EML tree is not itself a simple EML tree. It involves quotients and sums that require careful treatment. The conjecture is stated with strong evidence but the proof remains open.

Why it matters

A proved O(k) bound would let us say something more precise about the complexity cost of approximating high-zero-count functions. It would also constrain what kinds of functions can appear at each depth level — making the EML depth hierarchy tighter and more useful as a classification tool.

Cite this work

Monogate Research (2026). "The Pumping Lemma for EML Trees." monogate research blog. https://monogate.org/blog/pumping-lemma

License

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