A Pumping Lemma for EML Trees?
How many zeros can a depth-k EML tree have? The bound claimed here is 2k, and it is unproved. The counts on record stop at 8 internal nodes, where the most found is 3. Closing the gap would strengthen the Infinite Zeros Barrier.
Correction (2026-09-13): this post called the 2k bound a theorem and gave a proof. The proof used the wrong operator (eml(f, g) is exp(f) − ln(g), not exp(f) − g) and asserted zeros(k) ≤ 2 · zeros(k−1) without an argument. As first stated the bound is false: eml(x, eml(eml(x,1),1)) = ex − ln(eex) is zero for every real x, at depth 3. The post also said O(1) in its summary and O(k) in its body, and credited the N=12 search with zero counts it never recorded. The counts below come from a separate search.
The claimed bound
Conjecture (EML Pumping Lemma): Every depth-k real EML tree that is not identically zero has at most 2k real zeros on any bounded interval where every ln argument in it is positive.
The argument offered was an induction on depth. It does not go through:
Base case (k = 1).
A depth-1 tree over {1, x} is eml(1, 1) = e, eml(x, 1) = exp(x),
eml(1, x) = e − ln x or eml(x, x) = exp(x) − ln x.
Each has at most 1 zero. 1 ≤ 21. ✓
Inductive step.
Suppose every depth-(k−1) tree has at most 2k−1 zeros.
A depth-k tree is T = eml(f, g) = exp(f) − ln(g), where f and g are
depth-(k−1) trees.
T(x) = 0 iff exp(f(x)) = ln(g(x)).
Both exp(f) and ln(g) are real-analytic where defined.
The step then asserted that a Rolle's theorem argument on the difference gives the
recurrence zeros(k) ≤ 2 · zeros(k−1), and so zeros(k) ≤ 2k. No such argument is
given, and the zeros of T are not determined by those of f and g:
eml(1, x) = e − ln x vanishes at x = ee, where neither leaf does.
The observed counts
The exhaustive N=12 search (1,704,034,304 trees) measured each tree's error against sin; it recorded no zero counts. The zero counts on record come from a separate exhaustive search of all 862,118 real EML trees over {1, x} with at most 8 internal nodes, counting sign changes on [−2, 2] on a 0.01 grid. The most found:
- 0–2 internal nodes: at most 1 sign change
- 3–6 internal nodes: at most 2
- 7–8 internal nodes: at most 3
These stay far below 2k, but they stop at 8 internal nodes and miss zeros outside [−2, 2], so they do not show how the maximum grows.
The conjecture
Conjectured linear bound: Every depth-k real EML tree that is not identically zero has at most O(k) zeros on any bounded interval where it is defined — linear in depth, not exponential.
This is currently unproved, and so is the 2k bound above. The counts up to 8 internal nodes are consistent with it, but too few sizes to support any growth rate. 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. A Rolle's theorem bound would count zeros of the derivative, which is itself a ratio of EML trees (log-differentation). If derivative trees have O(k−1) zeros, the bound would be 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 rests on counts up to 8 internal nodes, and 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). "A 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