Constraint Classes for the Doubling Map
We classify trajectories of the map \(N_{n+1}=2N_n – \varepsilon(N_n)\) where \(0 \le \varepsilon(N_n) \le N_n\). The constraint \(\varepsilon\) determines whether \(N_n = \Theta(2^n)\), \(N_n = \Theta(c^n)\) for \(1 < c < 2\), or \(N_n = \Theta(n^k)\). We define seven syntactic classes via the form of \(\varepsilon\) and prove a Master Lemma linking \(\varepsilon(N_n)/N_n\) to asymptotic growth.
1. Framework
Consider the recurrence
with constraint function \(\varepsilon: \mathbb{N} \to \mathbb{N}\) satisfying \(0 \le \varepsilon(N_n) \le N_n\). Define the retention ratio
If \(\varepsilon(N_n)/N_n \to 0\) then \(R_n \to 2\) and \(N_n = \Theta(2^n)\). If \(\varepsilon(N_n)/N_n \to 1\), growth collapses to polynomial. Intermediate limits produce \(\Theta(c^n)\) with \(1 < c < 2\).
2. Syntactic Classes I–III
\(\varepsilon(N_n)=0\). Then \(N_{n+1}=2N_n\) and \(N_n = N_0 \cdot 2^n\). So \(N_n = \Theta(2^n)\).
\(\varepsilon(N_n)=k\) for constant \(k\). Then \(N_n = (N_0-k)2^n + k\). Still \(\Theta(2^n)\) for \(N_0 > k\). Ratio: \(R_n = 2 – k/N_n \to 2\).
\(\varepsilon(N_n)= \alpha N_n\) with \(0 < \alpha < 1\). Then \(N_{n+1}=(2-\alpha)N_n\). So \(N_n = \Theta((2-\alpha)^n)\). Example: \(\alpha=0.3\) gives \(\Theta(1.7^n)\).
2. Syntactic Classes IV–VII (cont.)
\(\varepsilon(N_n)=O(N_n^{\beta})\), \(0 < \beta < 1\). Example \(\varepsilon=\sqrt{N_n}\). Then \(\varepsilon(N_n)/N_n \to 0\), so \(R_n \to 2\) and \(N_n = \Theta(2^n)\). Loss is negligible.
\(\varepsilon(N_n)=N_n – f(N_n)\) where \(f(N_n)=o(N_n)\) but \(f(N_n)=\omega(1)\). Then \(N_{n+1}=N_n+f(N_n)\). This yields polynomial growth: if \(f(N_n)=c\), \(N_n=\Theta(n)\); if \(f(N_n)=\sqrt{N_n}\), \(N_n=\Theta(n^2)\).
\(\varepsilon(N_n)=N_n – k\) constant \(k\). Then \(N_{n+1}=N_n+k\), so \(N_n = \Theta(n)\). Ratio \(R_n = 1 + k/N_n \to 1\).
\(\varepsilon(N_n)=N_n\). Then \(N_{n+1}=N_n\), constant trajectory. \(N_n = \Theta(1)\).
3. Master Lemma
Let \(r_n = \varepsilon(N_n)/N_n\). Then:
- If \(\limsup r_n < 1\), then \(N_n = \Omega((2-\limsup r_n)^n)\).
- If \(r_n \to 0\), then \(N_n = \Theta(2^n)\).
- If \(r_n \to 1 – c\cdot N_n^{-1}\cdot g(N_n)\) with \(g(N_n)=o(N_n)\), then \(N_{n+1}=N_n+g(N_n)\).
- Hence \(\prod_{i=0}^{n-1} R_i = N_n/N_0\) determines exponent.
Proof sketch. Write \(N_n = N_0 \prod_{i=0}^{n-1}(2-r_i)\). Log: \(\log N_n = \log N_0 + \sum \log(2-r_i)\). If \(r_i \to 0\), \(\log(2-r_i)=\log 2 + O(r_i)\), so \(\log N_n = n\log 2 + O(\sum r_i)\). Bound \(\sum r_i\) by class.
4. Mapping Table
Syntactic form of \(\varepsilon\) → asymptotic growth.
| Class | \(\varepsilon(N_n)\) | \(R_n\) | Growth |
|---|---|---|---|
| I | \(0\) | \(2\) | \(\Theta(2^n)\) |
| II | \(k\) | \(2 – k/N_n \to 2\) | \(\Theta(2^n)\) |
| III | \(\alpha N_n\) | \(2-\alpha\) | \(\Theta(1.7^n)\) type |
| IV | \(N_n^{\beta}\) | \(2 – o(1)\) | \(\Theta(2^n)\) |
| V | \(N_n – \sqrt{N_n}\) | \(1 + 1/\sqrt{N_n}\) | \(\Theta(n^2)\) |
| VI | \(N_n – k\) | \(1 + k/N_n \to 1\) | \(\Theta(n)\) |
| VII | \(N_n\) | \(1\) | \(\Theta(1)\) |
5. Canonical Examples
Note for Gutenberg: these are static divs with inline styles — no canvas/JS — so they survive Custom HTML blocks.
6. Relation to Frameworks
The map \(N_{n+1}=2N_n-\varepsilon(N_n)\) appears as:
- Population with culling: \(\varepsilon(N_n)\) = harvested individuals. Class III = proportional harvest, Class VI = constant quota leading to \(\Theta(n)\).
- Complexity blow-up: \(N_n\) = state space, \(\varepsilon\) = merging. If merging is \(\Theta(N_n)\) then growth drops from \(\Theta(2^n)\) to \(\Theta(1.7^n)\) or polynomial.
- Proof search: \(2N_n\) = naive expansion, \(\varepsilon\) = subsumption. Sublinear \(\varepsilon=N_n^{\beta}\) preserves \(\Theta(2^n)\) lower bound.
7. Extensions — Threshold, Delayed, Stochastic
Intro: The seven syntactic classes above are complete for \(\varepsilon(N_n)\) depending only on current \(N_n\) and monotone. Three extensions that arose in Paper I reviews — threshold, delayed feedback, and stochastic — require history or randomness. They do not add new \(R_\infty\) limits, but they realize the same limits via different mechanisms relevant to distributed systems.
A. Threshold / Saturation (Phase Change)
Define \(\varepsilon(N_n)=0\) if \(N_n < N_c\) else \(\alpha N_n\) with \(\alpha=0.85, N_c=10^6\). So \(N_{n+1}=2N_n\) for \(N_n<N_c\) else \(1.15 N_n\). Then \(R_n: 2 \to 1.15\). Growth: \(2^n \to 1.15^n\). Piecewise. Interpretation: shard saturation.
B. Delayed Feedback (Memory)
Define \(\varepsilon(N_n)=0.95 N_{n-2}\). Then \(N_{n+1}=2N_n -0.95 N_{n-2}\). Characteristic \(\lambda^3 =2\lambda^2-0.95\). Dominant root \(\rho \approx 1.68\) with complex pair causing oscillations in \(R_n\). Still \(R_n \to \approx1.68 \in(1,2)\). So \(\Theta(\rho^n)\). Interpretation: autoscaling lag.
C. Stochastic Perturbation (Mean-Preserving Noise)
Define \(N_{n+1}=2N_n\cdot \xi_n\), \(E[\xi_n]=1\), \(\text{Var}(\log \xi_n)=\sigma^2\). Then \(E[N_n]=2^n N_0\), but sample paths: \(\log N_n = n\log2 + \sum \log \xi_i\), so \(\text{Var}(\log N_n)=\sigma^2 n\). Log-normal band around \(2^n\), \(R_n =2\xi_n\) noisy around 2. Preserves doubling in expectation but not pathwise.
Note: These three map into existing \(R_\infty\) trichotomy (Threshold → Class III, Delayed → Class III with oscillation, Stochastic → Class I/II in mean) — they provide operational pointers for the eight AI partners: each partner can take one syntactic class plus one extension.
8. Open Problems
If \(\varepsilon(N_n)\) is random with \(\mathbb{E}[\varepsilon/N_n]=\mu\), does \(N_n\) concentrate around \(\Theta((2-\mu)^n)\)? What about variance \(\Theta(2^n)\) vs \(\Theta(c^n)\) phase transition?
Classify when \(\varepsilon(N_n)\) oscillates between Classes II and VI. Does \(\liminf R_n =1\), \(\limsup R_n =2\) imply \(N_n\) is neither \(\Theta(2^n)\) nor \(\Theta(n^k)\)?
Given \(\varepsilon\) as a program, is it decidable whether \(N_n = \Theta(2^n)\)? Likely undecidable in general; find syntactic fragment where it is decidable.
9. Conclusion
We gave a complete syntactic checklist: inspect \(\varepsilon(N_n)\) and read off growth. If \(\varepsilon/N_n \to 0\) — including constants and \(N_n^{\beta}\) — you keep \(\Theta(2^n)\). If \(\varepsilon=\alpha N_n\), you get \(\Theta((2-\alpha)^n)\), e.g. \(\Theta(1.7^n)\) for \(\alpha=0.3\). If \(\varepsilon=N_n-f(N_n)\), you collapse to \(\Theta(n^k)\) or \(\Theta(n)\) or \(\Theta(1)\).
Thus the single parameter \(R_n = 2 – \varepsilon(N_n)/N_n\) and its limit govern the transition from exponential \(2^n\) to linear.