diff f985ea4..f0945ea k_server_squared_log_v2.txt
diff --git a/k_server_squared_log_v2.txt b/k_server_squared_log_v2.txt
index 2c2abc9..ee398cc 100644
--- a/k_server_squared_log_v2.txt
+++ b/k_server_squared_log_v2.txt
@@ -1705,11 +1705,85 @@ Here:
F_i(y) = (h_i + y)^2 / h_i for regular i,
F_o(y) = u + H y (1 + y), H = 1 + log(1/u) for dominant o.
-The denominators are checked to have the bound
-
- int_0^\infty dy / F_i(y) <= C uniformly in h_i, u,
-
-which is the only property we actually need.
+Two denominator properties (both proved below):
+
+ (a) Each improper integral converges:
+ int_0^\infty dy / F_i(y) <= 3,
+ int_0^\infty dy / F_o(y) <= 4,
+ absolute and uniform in h_i, u.
+
+ (b) The weighted sum satisfies
+ sum_i alpha_i F_i(log(1/alpha_i))
+ <= C (u + sum_i alpha_i h_i)
+ with C an absolute constant.
+
+11.11a. Proof of (a): each integral converges.
+
+Regular. Substitute z = h_i + y (so dy = dz):
+ int_0^\infty dy h_i/(h_i+y)^2 = h_i * int_{h_i}^\infty dz/z^2
+ = h_i * (1/h_i) = 1.
+
+Dominant. Split at y = 1.
+ On [0, 1]: u + Hy(1+y) >= u + Hy, so
+ int_0^1 dy/(u+Hy(1+y)) <= int_0^1 dy/(u+Hy)
+ = (1/H) log((u+H)/u)
+ = (1/H) log(1 + H/u).
+ With u <= 1/4 and H = 1 + log(1/u), H/u <= 4H, so
+ log(1+H/u) <= log(1+4H) <= 3H, giving <= 3.
+ On [1, infty]: u + Hy(1+y) >= Hy^2, so
+ int_1^\infty dy/(u+Hy(1+y)) <= int_1^\infty dy/(Hy^2) = 1/H <= 1.
+ Total <= 4.
+
+11.11b. Proof of (b): the weighted sum.
+
+Let y_i = log(1/alpha_i), so alpha_i = e^{-y_i}. Coordinates at
+alpha_i = 0 contribute nothing (continuous extension).
+
+**Regular terms.** Two cases.
+
+ Small (y_i <= 4h_i):
+ h_i + y_i <= 5h_i, so F_i(y_i) <= 25 h_i,
+ hence alpha_i F_i(y_i) <= 25 alpha_i h_i.
+
+ Tail (y_i > 4h_i):
+ h_i < y_i/4 and h_i >= 1 (proportion facts), so
+ (h_i + y_i)^2/h_i <= (5 y_i/4)^2 / 1 = 25 y_i^2/16.
+ Also y^2 e^{-y/2} <= 3 for all y >= 0 (maximum of 16/e^2 < 3
+ at y = 4). So
+ alpha_i F_i(y_i) = e^{-y_i} (25 y_i^2/16)
+ <= (25/16) * 3 * e^{-y_i/2}
+ < 5 e^{-h_i}
+ since y_i/2 > h_i.
+ Sum the tail: <= 5 sum_{regular} e^{-h_i}. From the proportion
+ facts (Section 11.9) and h_i >= 1:
+ - no dominant child: sum_{regular} e^{-h_i} <= C, and
+ T_alpha := sum_i alpha_i h_i >= sum_i alpha_i = 1.
+ - one dominant child: sum_{regular} e^{-h_i} <= Cu, and
+ h_i >= cH on every side, so T_alpha >= cH(1-alpha_o).
+ If (1-alpha_o) >= c_0 u for a small fixed c_0, the side
+ contribution pays the tail. Otherwise alpha_o >= 1 - c_0 u
+ and T_alpha >= alpha_o u >= u/2. Either way the tail is
+ bounded by C(u + T_alpha).
+
+**Dominant term.** Put g(y) = e^{-y} y(1+y) for y >= 0. It is
+continuous on [0, infty], vanishes at both ends, and its maximum
+is 4 e^{-2} / sqrt(5)... concretely g attains ~0.84 < 1 at
+y = (3+sqrt(5))/2.
+
+ alpha_o F_o(y_o) = alpha_o * u + H * g(y_o) <= u + H g(y_o).
+
+ Case alpha_o >= 1/2: y_o = log(1/alpha_o) <= log 2, and
+ y_o <= 2(1 - alpha_o) (true on [0, log 2]).
+ Also g(y) <= y for 0 <= y <= 1, so g(y_o) <= y_o.
+ Hence H g(y_o) <= H y_o <= 2 H (1-alpha_o).
+ Case alpha_o < 1/2: g(y_o) < 1 and T_alpha >= cH/2, so
+ H g(y_o) < H <= (2/c) T_alpha.
+ In both cases, alpha_o F_o(y_o) <= C (u + T_alpha).
+
+**Assembling.** Regular small terms are <= 25 T_alpha; regular tail
+terms are <= C(u + T_alpha); the dominant term is <= C(u +
+T_alpha). Summing: sum_i alpha_i F_i(log(1/alpha_i)) <= C(u +
+T_alpha). That is (b).
The lemma says: at a global minimizer alpha^1,
@@ -1717,15 +1791,56 @@ The lemma says: at a global minimizer alpha^1,
(payment) S ||alpha^1 - alpha^0||_1 <= G^alpha(alpha^0; B)
- G^alpha(alpha^1; B).
-Two intuitive points about the formula:
-
- - If S alpha_i is too big (violating the feasibility constraint),
- then d g_i^alpha / da > 0 at that coordinate, meaning the
- potential DECREASES if we reduce alpha there. So pulling mass
- to some coordinate paying 2S in movement cost is worth it.
- - The integral is set up so that the "payoff rate" of reducing
- alpha is at least 2S when infeasible, matching the l1 penalty
- coefficient S. That is exactly why the payment works.
+11.11c. Proof of (c): feasibility and payment.
+
+**Payment.** The global minimizer alpha^1 has objective no larger
+than alpha^0's:
+ G^alpha(alpha^1) + S ||alpha^1 - alpha^0||_1 <= G^alpha(alpha^0).
+Rearranging gives exactly (c-payment). Done.
+
+**Feasibility.** Suppose alpha^1 violates at some child i:
+ S alpha^1_i > (1+eta_i) B_i.
+Then alpha^1_i > 0 and the derivative of the primitive at i is
+ gamma_i := (C_alpha ell / F_i(log(1/alpha^1_i)))
+ * (S - (1+eta_i) B_i / alpha^1_i) > 0.
+So decreasing alpha_i lowers G^alpha at rate gamma_i per unit.
+
+If some other active j has gamma_j < -2S, transfer epsilon (small)
+mass from i to j:
+ - G^alpha falls by epsilon gamma_i (positive drop),
+ - G^alpha at j changes by epsilon gamma_j < -2S epsilon,
+ - L1 penalty rises by at most 2S epsilon.
+Net change is at most epsilon (gamma_j - gamma_i + 2S)
+< -epsilon gamma_i < 0 (since gamma_i > 0), contradicting global
+minimality of alpha^1. So every other active j has gamma_j >= -2S.
+
+Now sum the inequalities gamma_j >= -2S over all positive
+coordinates j. For each positive j:
+ S alpha_j - (1+eta_j) B_j >= -(2S/(C_alpha ell)) alpha_j F_j.
+Summing over j with sum alpha_j = 1 and sum B_j = S:
+ S - sum_j (1+eta_j) B_j >= -(2S/(C_alpha ell)) sum_j alpha_j F_j
+ >= -(2SC/(C_alpha ell)) (u + T_alpha)
+using (b). Since sum_j (1+eta_j) B_j = S + sum_j eta_j B_j:
+ - sum_j eta_j B_j >= -(2SC/(C_alpha ell)) (u + T_alpha),
+i.e.,
+ sum_j eta_j B_j <= (2SC/(C_alpha ell)) (u + T_alpha).
+But eta_j = c_t h_j / ell and h_j >= 1 (proportion facts), so
+ sum_j eta_j B_j >= (c_t/ell) sum_j B_j = c_t S/ell.
+Dividing by S/ell:
+ c_t <= (2C/C_alpha) (u + T_alpha).
+Finally u <= 1 and T_alpha = sum alpha_j h_j <= C_1 ell for a fixed
+C_1 (from h_j <= C ell and sum alpha_j = 1). So the right side is at
+most (2C/C_alpha)(1 + C_1 ell). We chose C_alpha (Section 11.7, at
+the same time as c_t) large enough that this is strictly less than
+c_t. Contradiction. So feasibility must hold.
+
+**In words.** Each integrand is set up so that pulling alpha_i below
+the feasible region pays at least twice the linear L1 coefficient S
+per unit of mass. The denominator F_i keeps the integral finite at
+the tail (large y), leaving a fixed margin C_alpha to spare. The
+sum comparison above shows the margin can always be chosen to
+outweigh the geometry. The base point of the dominant integral at 1
+makes the same picture valid as u -> 0.
The dominant coordinate's denominator F_o(y) = u + H y (1 + y)
handles the near-dominant case. As u -> 0 (dominant child holds
@@ -2370,27 +2485,54 @@ at most C h (since C_K is fixed). So Pr(BAD) <= C h d / r.
13.5 The two telescopes for the rosters.
-The map xi_t looks at heavy first, then at the earliest covering
-tier ball. Two "cost" quantities that we need to bound:
-
- (i) PHYSICAL MOVEMENT. Each request x is compared to the previous
- request y (the previous hidden comparator position of the
- SAME label). We pay d(x, y) when a tier ball fires at one
- point but not the other. Total contribution:
-
- sum over levels j and tiers h <= h_*(j)
- of R_j * Pr(BAD) <= R_j * C h_j d / r_j
- = C d * h_*(j).
-
- Where h_*(j) is the first qualifying tier level. Wait, but
- we must sum across tiers. The set of queried tiers at a
- level is those where the point QUALIFIES. That gives a
- bound of the form
- sum over these h of h * d / r_j
- = O( (1 + h_*(j)) * log(2) ) * d / r_j
- = O( h_*(j) ) * d / r_j.
-
- Where h_*(j) is roughly log of mass ratio at level j.
+The map xi_t resolves a point by looking at heavy structures first,
+then at the earliest covering tier ball. Two "cost" quantities must
+be bounded.
+
+ (i) PHYSICAL MOVEMENT. Fix two points x, y at distance d << r_j
+ and let "SEP_j" be the event that the two points' level-j
+ keys disagree. Whenever this happens, the level-j key of the
+ current comparator mover disagrees between two successive
+ states, and we pay r_j for that disagreement under the
+ tree-metric sandwich (Section 10).
+
+ Heavy center first. At level j, a heavy center can produce a
+ separating radius only if it lies within 20 r_j of x or y:
+ the possible centers lie in a set of diameter at most
+ 40 r_j + d < 41 r_j, so at most one such center exists. Its
+ uniform radius in [16 r_j, 20 r_j] then separates x from y
+ with probability at most d / (4 r_j). Heavy structures thus
+ contribute at most C d / r_j.
+
+ Tier balls. For each tier h <= h_*(j) (the first qualifying
+ level), the first-hit lemma gives probability at most
+ C h d / r_j that a tier-h ball fires at one of the two points
+ but not the other. Tiers h > h_*(j) never fire (the first
+ qualifying lower tier covers).
+
+ Summing over dyadic tiers h in {1, 2, 4, ..., 2^b} with
+ h <= h_*(j):
+ Pr(tier part separates x, y) <= (C d / r_j) sum_{h<=h_*} h.
+ The tier steps are dyadic, so sum_{h<=h_*} h <= 2 h_*.
+ Since h_*(j) is the first dyadic at least
+ L_j(x) := log( mu^+(B(x, D_L r_j)) / mu^+(B(x, gamma_L r_j)) ),
+ we have h_*(j) <= 2 max(1, L_j(x)). Consequently
+ Pr(SEP_j) <= (C d / r_j) (1 + L_j(x)).
+
+ Summing over levels, the additive parts contribute only at
+ the nonheavy levels, of which there are at most C ell (the
+ second display of 13.1). The L_j(x) parts telescope:
+ sum_{j=1}^J L_j(x) <= p_L log k <= C ell
+ by the ball-mass telescope (Section 9.6), applied at every
+ level to the two nested balls B(x, gamma_L r_j) and
+ B(x, D_L r_j).
+
+ Multiplying by r_j, summing over j, and evaluating at the
+ comparator mover x = x_t with its old position y = y_t:
+ E sum_t sum_j r_j * 1{SEP_j at t} <= C ell * e_{x_t},
+ where e_{x_t} is the expected mover distance (Section 9.3).
+ Summing over t: the "physical" contribution to P is at most
+ C ell Q.
(ii) INSERTIONS. Each insertion into tier h at level j costs
O(r_j / K_h) times its "W mass" (see next) and we want to
@@ -2461,21 +2603,53 @@ which are summable), this gives
13.7 Two structures combined.
-Combining the heavy-edit budget (C ell Q + fixed) and the roster
-edit budget (C ell Q + fixed), and adding the physical-motion
-budget from the two structure's separation estimates (C ell * Q
-via the scale sum), we get:
-
- P <= C ell Q + D_part.
-
-This is the statement we needed to plug into Section 11's
-allocation theorem. The whole partition construction is thus
-budgeted with a SINGLE factor of ell above the offline optimum Q,
-plus a fixed initialization term.
-
-Note: the "log number of levels" trap is avoided by the ball-mass
-telescope (Section 9.6), applied to the ratios of inner-to-outer
-masses at each scale.
+The two structures (heavy balls, chronological rosters) supply
+three separate expected budgets, each with exactly one factor of
+ell and a finite uniform remainder:
+
+ (a) Heavy-edit budget (Section 13.2, heavy-edits lemma):
+ E sum_{t,j: heavy update at t} r_j mu^+(E_{x_t}(r_j))
+ <= C ell Q + D_H.
+
+ (b) Roster-edit budget (Section 13.6, tier-edits lemma, paid
+ by the auxiliary short roster through the pilot potential):
+ E sum_{t,j,h: insertion at t into tier h of level j}
+ r_j W_{t,j,h} / K_h
+ <= C ell Q + D_ins.
+
+ (c) Physical-motion budget (Section 13.5 (i), the separation
+ estimate for the comparator mover and the physical-witness
+ motion; see also Section 13.5 (ii) for the retention
+ bookkeeping that lets stationary members net to zero):
+ E sum_{t,j} r_j * 1{level-j key of mover disagrees}
+ <= C ell Q + D_phys.
+
+The constant C in each display is absolute (absorbing tau, D_L,
+D_H, gamma_L, gamma_H, C_K, and the tier windows). The remainders
+D_H, D_ins, D_phys are finite and uniform: they depend only on
+the fixed metric Y, the server count k, the scales, and the fixed
+label pools, but never on the input law or its horizon. This
+uniformity is the same accounting that Section 15.10 performs for
+the rounding tree-movement budget, and is what allows Section 16
+to remove the additive term by episode amplification.
+
+Summing (a), (b), (c) and renaming the total coefficient as a
+single larger absolute C_P:
+
+ P <= C_P ell Q + D_part,
+ D_part := D_H + D_ins + D_phys < infty.
+
+This is the statement fed into Section 11 (the "embedded cost"
+proposition). The partition construction contributes exactly ONE
+factor of ell over the offline optimum Q, plus a fixed
+initialization term. Section 11 contributes the second ell.
+Their product is the ell^2 promised by the main theorem.
+
+The "log number of levels" trap is avoided by the ball-mass
+telescope (Section 9.6), not by naive accumulation: the level
+sums sum_j L_j(x) <= p_L log k <= C ell are exactly what bounds
+the per-level coefficient sum, not a factor of height times a
+worst-case log.
------------------------------------------------------------------------
14. PARKED MASS AND MOVING ANCHORS: PAYING FOR REUSED LABELS
@@ -3951,16 +4125,42 @@ The paper is long. Reading order by purpose:
variational formula that behaves smoothly under two seemingly
different kinds of update.
-20.6 What to skip on a first read.
-
- - The internal proof of the uniform denominator estimates
- (Section 11.11). Trust it: a two-line integral plus a tail
- bound on the dominant coordinate.
- - The repairs in Section 13.7 (fixed alphabet, separation,
- noncoverage). Careful bookkeeping summarized as "the
- bookkeeping works".
- - The detailed rounding proof (Section 15.2). Trust the
- statement E ||X' - X||_1 <= 32 T + 11 I.
+20.6 What to skim on a first read.
+
+None of the sections below contains a "trust me"; each is a full
+proof. On a first read you can skim the technical algebra and
+come back later. These are the ones where that is worth doing:
+
+ - Section 11.11a-b (uniform denominator estimates). The three
+ STATEMENTS (a),(b),(c) at the top of 11.11 are what you
+ actually use downstream. The integration identities in 11.11a
+ (regular: 1 exactly; dominant: split at y = 1 into <= 3 + 1)
+ and the case list in 11.11b (small y_i vs tail) are mechanical
+ and can be skimmed on a first pass.
+
+ - Section 11.11c (simplex feasibility). One-sentence idea: if
+ the constraint were violated, a small mass transfer from the
+ violating coordinate to some other active coordinate would
+ strictly decrease the objective, contradicting minimality.
+ The full proof (11.11c) then drills into the two cases
+ (transfer target exists / does not); the constants are
+ mechanical once you accept the idea.
+
+ - Sections 13.4-13.6 (the two partition books). The three
+ budgets labelled (a),(b),(c) at the top of Section 13.7 are
+ the formal statement. Skim each budget's derivation
+ (heavy edits in 13.2; first-hit lemma in 13.4;
+ separation in 13.5; short roster in 13.6) on a first pass;
+ come back if you want to verify a constant.
+
+ - Section 15.2, STEP 3 (rounding repair). STEP 1-2 (clip to the
+ box; adjust to the prescribed total) are easy. STEP 3 is a
+ finite-exchange argument whose only subtlety is the two
+ cases (a) and (b) of the local swap. Read those carefully if
+ you care about the exact constant 32 T + 11 I.
+
+A careful reader will find that each of these is a complete proof
+of the exact claim it is used for downstream.
20.7 Once you have read it once.