PaperlayerView exact revision on arXiv

Source-linked AI summary

Online Discrepancy of Sparse Random Vectors over Long Horizons

Nicola Wengiel

arXiv:2610.34410v1cs.DScs.DMmath.COmath.PR

TL;DR

The paper asks how prefix discrepancy changes with the horizon and whether terminal discrepancy remains controlled at prescribed times. It develops lower-bound and online-algorithm techniques, showing that at long horizons prefix and terminal discrepancy can diverge.

  • Problem

    The paper addresses how online prefix discrepancy depends on the horizon and whether terminal discrepancy has a matching bound at every prescribed time.

    Source: §1 · pp. 4–5

  • Method

    It realizes finite forcing strategies as rare blocks in random streams and develops online signing rules, with terminal analysis using a recent window and time-uniform moment bounds.

    Source: §1 · p. 5, §1.1 · pp. 7, 9

  • Results

    At T=⌊e^cn⌋, for fixed s≥2, optimal expected terminal discrepancy is of order log log n, while optimal expected prefix discrepancy is at least of order (n/log n)^α_s.

    Source: §1.1 · p. 9

  • Takeaways & Limitations

    For fixed s, prefix discrepancy grows with the horizon beyond a threshold, whereas terminal discrepancy remains the same order at every prescribed time T≥n.

    Source: §1 · p. 5

    For growing s, the joint long-horizon dependence remains open, and Theorem 2 excludes binary inputs with n/2<s<n.

    Source: §1.1 · p. 9, §8.6 · p. 74

Abstract

from arXiv · show

We study online vector balancing for independent sparse random vectors: each arrival is supported on a uniformly random set of $s$ of the $n$ coordinates, with nonzero entries equal to one (binary model) or independent random signs (signed model), and an online algorithm must sign each vector upon arrival. The prefix discrepancy is the largest $\ell_\infty$-norm of the signed sums up to the horizon $T$, the terminal discrepancy that of the sum at time $T$. For binary inputs with $2\le s\le n/2$ and $T=\Theta(n)$, Altschuler and Tikhomirov showed that both are of order $\sqrt{s}+\log\log n$; they asked how the prefix discrepancy depends on the horizon and whether a matching terminal bound holds at every prescribed time. Over long horizons, the two differ. For every fixed $s\ge2$ and $c>0$, every online algorithm, even a randomized one that knows the horizon, incurs with high probability prefix discrepancy $\Omega(\log\log n+(\log T/\log n)^{\alpha_s})$ for $n\le T\le e^{cn}$, where $\alpha_s=(2^{s-1}-1)/(2^s-1)$. For $s=2$, quadratic Greedy matches this bound; for fixed $s\ge3$, we give an online algorithm with prefix discrepancy $O(\log\log n+(\log T/\log n)^{1/2})$. In contrast, a deterministic algorithm that knows neither the horizon nor the failure probability keeps the terminal discrepancy $O_k(\sqrt{s}+\log\log n)$ at each prescribed time, with failure probability $n^{-k}$ for every fixed $k$, for $2\le s\le n/2$ (binary model) and $2\le s\le n$ (signed model); for $s=2$, quadratic Greedy itself does so. This answers their terminal question, and the same order is optimal for prefixes at all polynomial horizons $T\ge n$. The lower bound uses a finite safety game realized within the input law; the upper bounds use moments of elementary symmetric polynomials and, at terminal times, a $\cosh$ potential or a translated gauge with a Foster inequality at every state.

1 Introduction

The introduction studies online discrepancy for independent sparse random arrivals, distinguishing horizon-dependent prefix guarantees from terminal guarantees at prescribed times. It situates these results among related online and offline discrepancy bounds and previews the safety-game and potential-based methods used in the paper.

1 Introduction

  • Rare forcing patterns explain the effective horizon log T / log n: a finite strategy that raises a coordinate’s height can appear in a long random stream, while an algorithm may later recover.The introduction frames the problem around how quickly such strategies raise heights and whether algorithms can defend against them while recovering by a prescribed terminal time.Source: §1 · p. 5

1.1 Main results

  • For fixed s, prefix discrepancy is Ω(log log n + (log T / log n)^α_s); the upper exponent matches for s = 2 and is 1/2 for fixed s ≥ 3.These bounds hold for n ≤ T ≤ e^(cn); the optimal exponent for s ≥ 3 remains open.Source: §1.1 · pp. 6–7
  • At every prescribed T ≥ n, terminal discrepancy is Θ(√s + log log n) in the binary range 2 ≤ s ≤ n/2 and signed range 2 ≤ s ≤ n.One deterministic algorithm, independent of T and the failure probability, achieves the upper bound with failure probability n^-k for every fixed k.Source: §1.1 · pp. 7–8
  • The terminal algorithm uses a translated gauge or a cosh potential, with moment bounds and recovery analysis yielding bounds uniform in time.The gauge builds on Altschuler and Tikhomirov’s inverse-square profile with exponential continuation; the new translation supports a drift inequality at every state.Source: §1.1 · p. 8, §1.2 · p. 10
  • For n ≤ T ≤ n^β, prefix discrepancy has optimal order √s + log log n across the binary range 2 ≤ s ≤ n/2 and signed range 2 ≤ s ≤ n.A single horizon-independent rule attains this order; it follows by applying the terminal guarantee at each time and a union bound.Source: §1.1 · p. 8

1.2 Comparison with previous work

  • Compared with Altschuler and Tikhomirov’s linear-horizon results, the paper adds a horizon term to the lower bound, controls prefixes to exponential horizons for fixed s, and matches the terminal lower bound without restarts.It also shows their prefix order persists at polynomial horizons.Source: §1.2 · p. 10
  • Theorem 2 gives sparse inputs terminal discrepancy O(√s + log log n) at every prescribed T ≥ n without horizon knowledge, extending [BS20] and improving on the known lower-order statement [AT26b].For s = n in the signed model, it recovers the order in [BS20] with failure probability n^-k rather than exponentially small failure; [Wen26] studied independent-coordinate inputs and also found a doubly logarithmic factor for rare activations.Source: §1.2 · pp. 11–12
  • For online edge orientation, prior work established chip-game forcing and Greedy bounds, while this paper adapts forcing across time blocks to obtain lower bounds over exponential horizons.The pair proof uses deterministic chip-game estimates, the cube-root bound, and the spreadness lemma from [BPSS26], while random marks or binary arrivals induce correlated chip moves [AAN+98, Theorem 3.2; BPSS26, Lemmas 3.1 and 3.3].Source: §1.2 · pp. 11–12
  • Offline, worst-case sparse-vector discrepancy can be kept below C√s for any horizon, contrasting with online prefix growth for fixed s.The offline bound follows from the recent resolution of the Komlós conjecture [GFL26b, Theorem 1.1 and Corollary 1.2]; Beck and Fiala’s earlier bound was less than 2s.Source: §1.2 · p. 12
  • For sparse random set systems, offline discrepancy is at most two with high probability once T ≥ Cn^3 log^2 n, whereas online terminal discrepancy is optimally Θ(√s + log log n) at every prescribed T ≥ n.The offline result is due to Franks and Saks; the online lower bound is from [AT26b] and the matching prescribed-time order follows from Theorem 2.Source: §1.2 · p. 12

1.3 Organization

  • The paper develops a finite safety game and width certificate for lower bounds, elementary-symmetric-polynomial moments for prefix bounds, and translated-gauge or cosh potentials for terminal bounds.Later sections prove the main bounds, remove horizon dependence via restarts, extend prefix bounds to growing sparsity, and discuss open questions.Source: §1.3 · pp. 12–13

2 Technical overview

The overview develops a finite-game lower-bound strategy and upper bounds based on population control and energy or state-dependent potentials. Its methods address prefix discrepancy and terminal discrepancy through different mechanisms.

2.1 Lower bounds: a safety game and a width certificate

  • The lower-bound pipeline realizes a finite safety game in the random input law, translating forcing time J ≍ H^β into height H ≍ (log T/log n)^(1/β), with exponent α_s for k = s − 1.The argument applies against every online algorithm, including randomized algorithms that know T.Source: §2.1 · pp. 13–14
  • The safety-game lower-bound certificate has limits: no static coefficient choice improves its bound, and quadratic Greedy survives at least quadratic-many game requests.Thus, for fixed s, this game-based forcing approach cannot yield an exponent larger than 1/2.Source: §2.1 · p. 14

2.2 Population control by elementary symmetric moments

  • Elementary-symmetric-polynomial moments bound the number of coordinates above a height level without assuming coordinate independence, while layer iterations reduce that population over O(log log n) levels.The layer argument uses the rule that a lone high coordinate moves inward.Source: §2.2 · pp. 14–15

2.3 Upper bound for pairs: an energy witness and population control

  • For s = 2, a height reaching b + u requires earlier excess energy F_b ≥ u^3/32, and energy excursions yield u ≍ (L/log n)^(1/3).Population control supplies the level bound needed to control those excursions over the horizon.Source: §2.3 · p. 15

2.4 Upper bound for fixed sparsity: flat weights with a linear tail

  • For s ≥ 3, the upper-bound rule follows the gradient of a potential with exponentially growing weights up to a knee and a linear tail, using population control and two excursion bounds.Quadratic Greedy can reach height Ω_s(log T/log n) with high probability in the signed model over the stated horizon range.Source: §2.4 · pp. 15–16

Fresh orientations.

  • Fresh orientations let the proof handle both input models by conditioning on full random marks while revealing only their support restriction; binary inputs use support averaging.For binary inputs, the marks are all one, so the support-averaged anti-concentration bound is needed.Source: Fresh orientations · p. 16

2.5 Terminal discrepancy: a translated gauge

  • For terminal discrepancy, a translated gauge satisfies a Foster inequality at every state, and deterministic-window clearance yields the sharp radius for s ≥ (log(en))^(2/3).For smaller intermediate s, a bootstrap within a controlled height region upgrades the coarse bound; for s ≤ log log(en), the paper uses a hybrid cosh-potential rule.Source: §2.5 · pp. 16–17
  • For s ≤ log log(en), the hybrid rule achieves radius √s log(s + 1) + log log n = O(log log n) with failure probability n^−k; for s = 2, quadratic Greedy has the same guarantee.The bounds hold at every fixed time.Source: §2.5 · pp. 17–18

3 Preliminaries

The preliminaries define the online sparse-vector models, establish a baseline discrepancy lower bound, and collect anti-concentration and moment-based tools for the upper bounds. These tools control high-coordinate populations and energy excursions, with local clearance supporting layer iteration to reduce populations above successive height levels.

3.1 Model and conventions

  • Arrivals independently choose uniform s-subsets; binary entries are ones, while signed entries are independent Rademacher signs, and the online algorithm chooses each arrival’s sign after observing it.Algorithms may be randomized and may depend on n, s, the horizon, and a target failure probability; universal lower bounds include randomized algorithms that know the horizon.Source: §3.1 · p. 18

3.2 Anti-concentration for random supports and signs

  • Clipped anti-concentration estimates for uniform supports and random signs supply the support-randomness input to upper-bound drift estimates.The proof constructs supports using a random matching and applies Paley–Zygmund, yielding clipped forms needed in those estimates.Source: §3.2 · pp. 19–20

3.3 The baseline lower bound

  • At every prescribed T≥n, the baseline terminal lower bound is Ω(√s + log log n) in the binary model for 2≤s≤n/2 and the signed model for 2≤s≤n.The signed-model result extends the binary lower bound of Altschuler and Tikhomirov [AT26b].Source: §3.3 · p. 21

3.4 Moment tools for the upper bounds

  • The upper bounds share triangular moment recursions, moment-weight comparisons, level-clearance estimates, and excursion bounds for energy functionals.The recursions and clearance estimates appear in all three upper bounds; the weight comparisons appear in Sections 6 and 7, and excursion bounds in Sections 5 and 6.Source: §3.4 · pp. 23–24
  • Local clearance applies to rules that move a lone sufficiently high selected coordinate inward, enabling moment bounds on high-coordinate populations.An isolating state requires that a uniquely selected coordinate at height at least b, and at least b + g, moves inward.Source: §3.4 · p. 25
  • The local moment argument contracts old monomials while accounting for additive growth, without assuming independence among coordinates newly reaching the next height.The contraction coefficient is at most −rp/4; additive terms are handled by considering joint selection probabilities.Source: §3.4 · p. 26
  • Layer iteration makes the population above successive height levels drop doubly exponentially, reaching at most 2R within log2 log2 n + 3 levels.For processes started from zero, the iteration can control all levels over the entire horizon; terminal analysis uses general starting times.Source: §3.4 · p. 27
  • The excursions tool bounds the probability that an energy functional reaches a higher level before time T when its exponential transform is a supermartingale above a lower level.It applies a supermartingale bound after each entrance above the lower level, then takes a union bound over at most T entrances.Source: §3.4 · p. 28

4 Universal lower bounds over long horizons

The section proves universal long-horizon lower bounds using finite safety games and forcing constructions realized under random input laws, with repeated attempts in blocks. It extends these bounds to growing sparsity and random-edge orientations, and shows that terminal discrepancy must grow when the allowed failure probability is sufficiently small.

4.1 A finite safety game and a width certificate

  • The safety game admits a finite forcing time exactly when 2R < Δ; its smallest indefinitely maintainable radius is ⌈Δ/2⌉.When 2R ≥ Δ, a parity rule keeps the state in the cube forever.Source: §4.1 · p. 30

4.2 Mixed-radix coefficients

  • Optimized mixed-radix coefficients give 4R ≤ Pk ≤ 8R, Λ ≤ 112R^ηk, J ≤ 481R^βk, and m ≤ 2 + 2k(4R)^γk.A simpler radix choice yields cubic forcing time, J ≍ R^3, in the case s = 2.Source: §4.2 · p. 32

4.3 Realization and the block bound

  • Requests can be realized by random arrivals with probability bounded below uniformly over the past, tracking coordinates directly in the signed model and differences of disjoint pairs in the binary model.The binary model uses twice the cube radius, while unused support positions are filled outside the tracked pool.Source: §4.3 · pp. 33–35
  • Repeated blocks of J arrivals force some height to reach H with conditional probability at least 1 − (1 − p*^J)^⌊T/J⌋, uniformly over histories and algorithm choices.The construction does not reset the tracked state at block boundaries or require independence between blocks.Source: §4 · p. 28, §4.3 · pp. 34–35

4.4 Proof of the lower bound

  • The text next inserts the optimized radices, setting Cχ = 481χ3, Ak,χ = 2 + 8χk, and λk = (k + 1) log 2en for 1 ≤ k ≤ s − 1 and χ ∈ {1, 2}.Source: §4.4 · p. 35
  • For fixed s≥2 and c>0, every online algorithm has prefix discrepancy Ω(log log n + (log T/log n)^α_s) for n≤T≤e^{cn}.The failure probability is at most C_bl n^-0.8 + exp(-√n/log n) for large n; α_s=1/β_{s−1}.Source: §4.4 · p. 35
  • For s=2, every T≥n has prefix discrepancy at least c min{(log T/log n)^(1/3), n} with probability 1−o(1).This matches quadratic Greedy’s deterministic bound of at most 2n once log T≥Cn^3 log n.Source: §4.4 · p. 36
  • For growing sparsity, the construction yields prefix discrepancy of order log T/(log(4en/s) log log U) under its touch and pool constraints, where U=log T/log(4en/s).For T=⌈en⌉ and s=⌈2 log n⌉, this gives order n/(log n log log n); the fixed-s theorem cannot simply be applied with growing s.Source: §4.4 · p. 36
  • For random edge orientations, every online algorithm has prefix discrepancy Ω((log T/log n)^(1/3)) with probability 1−o(1), uniformly for n≤T≤e^{cn}.The forcing strategy applies when each requested arrival is realized with probability uniformly bounded below over the past.Source: §4.4 · p. 36
  • For fixed s≥2, terminal discrepancy radius at failure probability δ must grow with log(1/δ)/log n for all large n, T≥n, and e^-n≤δ≤n^-C_s.The lower-bound argument maintains a coordinate at height at least H through the end of a block; the stated range leaves the fixed-polynomial failure levels covered by Theorem 2 outside this conclusion.Source: §4.4 · p. 37

5 Upper bounds for pairs

For pairs, quadratic Greedy is a single deterministic rule that does not depend on the horizon or failure probability. Its analysis combines a chip-game energy witness, height-population bounds, and a global quadratic moment to control prefix discrepancy.

5.1 Chip games and a cubic energy witness

  • DT ≤ min{2n, 4(2T)^1/3} for every arrival sequence with two nonzero entries in {±1}.The chip-game representation also yields a cubic excess-energy witness before a height can reach b + u.Source: §5.1 · pp. 38–39

5.2 Cubic excursions

  • Except with probability T exp{−u^3 log z/128}, excess energy does not reach u^3/32 while the stated population and height conditions hold.This bound applies in both models for the parameters specified in Lemma 12.Source: §5.2 · p. 39

5.3 Moments of the heights

  • At each fixed time, at most q coordinates exceed log2(32en/q) + O(L/q), except with probability e^−L.Layer iteration reduces the population to O(L) within O(log log n) further levels.Source: §5.3 · p. 41

5.4 A global quadratic moment

  • For L > √n, a global quadratic moment controls populations above a level b* ≍ log n uniformly in time, so no layer iteration is needed.In this range, log n is at most of order (L/log n)^1/3.Source: §5.4 · p. 41

5.5 Proof of Theorem 1(b)

  • The proof treats L ≤ √n with height-population bounds and layer iteration, and L > √n with the global quadratic moment.Both ranges use the same rule for every admissible (T, δ).Source: §5.5 · pp. 42–43
  • O(log log n + (L/log n)^1/3) bounds quadratic Greedy’s prefix discrepancy for T ≥ n when n ≥ e^256 and L = log(16n(T + 1)/δ) ≤ n^2.The same rule is used throughout, and the bound holds with probability at least 1 − δ/4.Source: §5.5 · pp. 42–43

6 Upper bounds for fixed sparsity

For fixed s ≥3, this section constructs one deterministic rule for both input models and proves a long-horizon prefix-discrepancy bound. The proof controls high-coordinate populations and potential excursions, using different excursion arguments in two ranges of L.

6 Upper bounds for fixed sparsity

  • The deterministic rule uses weights that grow exponentially below a knee and linearly above it, with the knee chosen from n, s, and L before the run.The rule chooses the update sign from the weighted projection of the arriving vector; its parameters do not change during the run.Source: §6 · p. 44

6.1 Fresh orientations

  • A support-averaging lemma transfers bounds valid for every fixed mark orientation to conditional expectation in both binary and signed models.The binary model uses the all-ones orientation; the signed model averages over independent Rademacher orientations.Source: §6.1 · p. 44

6.2 Stopped geometric moments

  • Stopped geometric moments control how many coordinates exceed a level throughout the horizon, up to a stopping time defined by that population crossing a cutoff.The moments are elementary symmetric polynomials of exponentiated coordinate heights, and the drift argument applies across degrees up to the stated maximum.Source: §6.2 · p. 45

6.3 The potential of the rule and a tilted supermartingale

  • The rule is the exact gradient rule for a potential whose exponential tilt has controlled drift when few coordinates carry substantial weight.The potential's increments split into linear and curvature terms; the drift estimate accounts for pairs of weighted coordinates and selected zero-height coordinates.Source: §6.3 · pp. 46–47

6.4 Layers and squared-hinge excursions

  • Above the knee, the squared-hinge potential can increase only when at least two selected coordinates are high; below it, an isolation gap makes a lone high coordinate move inward.For L < √n, these properties support the layer iteration and squared-hinge excursion bound.Source: §6.4 · pp. 48–49

6.5 Proof of Theorem 1(c)

  • O_s(log log n + sqrt(L/log n)) bounds the discrepancy radius in both ranges of L, completing the proof of Theorem 1(c).For L ≥ √n, the proof uses a tilted supermartingale; for L < √n, it uses layer iteration and squared-hinge excursions.Source: §6.5 · pp. 49–50

7 Terminal discrepancy at every prescribed time

The section gives a deterministic rule that needs neither the horizon nor the failure probability and bounds terminal discrepancy at each prescribed time. Its gauge is built from a normalized profile and has deterministic geometric and one-step properties.

7 Terminal discrepancy at every prescribed time

  • The theorem selects between two deterministic rules using n and s alone; neither rule uses the horizon or failure probability, and neither is restarted.For s ≤ log ℓ under the stated condition, it uses the hybrid rule; otherwise it uses the gauge rule.Source: §7 · p. 51
  • For every fixed k, terminal discrepancy at each prescribed time is at most C_k times the stated radius, with failure probability at most n^-k across the theorem's four sparsity ranges.The theorem covers 2 ≤ s ≤ n/2 for binary inputs and 2 ≤ s ≤ n for signed inputs.Source: §7 · p. 51

7.1 The translated gauge and the rule

  • The gauge normalizes a profile sum at level B(S), and coordinates above a profile threshold are designated exceptional for the rule's priority update.The profile threshold defines the exceptional set through the excess over the gauge.Source: §7.1 · pp. 52–53

7.2 Deterministic estimates

  • The gauge is convex and 1-Lipschitz in the infinity norm, and when B(S) is bounded, a lone sufficiently high selected coordinate is moved inward.The section also bounds the number of coordinates above the specified level by K0n/Y*.Source: §7.2 · p. 54

7.3 Reduction to binary inputs

The section reduces signed-input estimates to binary estimates by conjugating the state with fresh random marks. It then establishes service and curvature bounds for the gauge rule and uses them to obtain an all-state Foster inequality.

7.3 Reduction to binary inputs

  • Fresh-mark conjugation transfers binary one-step inequalities to the signed rule at every state when the state set is sign-invariant and the quantities depend on magnitudes as specified.The proof fixes a full fresh Rademacher vector, conjugates the state, and identifies the signed update with a binary update at that conjugate state.Source: §7.3 · pp. 55–56

7.4 Service and curvature in the binary model

  • For binary inputs, the gauge rule's service and curvature estimates hold at every state with B(S) > 1.The estimates split contributions from supports avoiding exceptional coordinates and supports that meet them.Source: §7.4 · pp. 56–57

7.5 Drift and a Foster inequality at every state

  • The gauge rule satisfies a Foster inequality for its exponential gauge at every state, for binary 2 ≤ s ≤ n/2 and signed 2 ≤ s ≤ n.The proof combines the gauge drift bounds with the binary-to-signed reduction.Source: §7.5 · pp. 57–58
  • From the zero initial state, the Foster inequality yields global exponential moments and deterministic-window bounds for the gauge.The window bound uses the moment at its deterministic starting time, without imposing control over the entire elapsed history.Source: §7.5 · pp. 58–59

7.6 Moderate exponents

This section strengthens the gauge rule's exponential-moment control with a moderate exponent. The resulting bounds apply at every state and yield global moments and deterministic-window estimates.

7.6 Moderate exponents

  • The gauge rule has a moderate-exponent Foster inequality at every state with B(S) > 1, in both input models.The resulting drift rate is proportional to min{θ√s, s}/n for the exponential gauge potential.Source: §7.6 · p. 59
  • Starting from zero, the moderate-exponent inequality gives global moments and deterministic-window bounds in both models over the stated range.The window estimate follows by stopping a nonnegative supermartingale at the first gauge crossing or at the window's end.Source: §7.6 · p. 61
  • The moderate exponent is restricted to O(s) by the all-state certificate, not by a discrepancy lower bound.A larger exponent is used later, but only inside a region of bounded heights.Source: §7.6 · p. 61

7.7 Composition at a prescribed time

This section composes bounds over a finite window before each prescribed time, rather than controlling the entire history. The resulting gauge-rule bounds give the sharp terminal radius in the stated sparsity ranges, with polynomially small failure probability.

7.7 Composition at a prescribed time

  • A good event must persist through a final window of length at most w̄, and its failure probability is controlled separately from the terminal-height tail.The three failure sources include loss of a good event in the window, a population failing to drop at a level, or a coordinate remaining above the final level at T.Source: §7.7 · p. 61
  • For s ≥ ℓ^(2/3), the gauge rule achieves terminal radius O_k(√s + log log n) with polynomially small failure probability.The composition argument combines bounded populations, bounded heights, and an isolating property over a window whose length does not depend on T.Source: §7.7 · pp. 61–62
  • For s ≥ ℓ^(2/3), ℓ/s ≤ √s, so the coarse terminal bound already has the sharp O_k(√s + log log n) radius.The stated guarantee is for either input model.Source: §7.7 · p. 62
  • For s ≤ ℓ^2, the composition bound gives the sharp radius with failure probability (log n)^−k; for log ℓ < s < ℓ^(2/3), a later argument improves this to n^−k.The coarse bound includes an ℓ/s term, which the next section removes in the intermediate sparsity range.Source: §7.7 · p. 62

7.8 Polynomially small failure probability at the sharp radius: a bootstrap

This section removes the ℓ/s term in the intermediate sparsity range by bootstrapping from a coarse terminal bound. It controls a large-exponent gauge locally, while a separate local moment bound handles exits from the height region.

7.8 Polynomially small failure probability at the sharp radius: a bootstrap

  • A large gauge exponent is used only when heights are at most H = O(ℓ/log ℓ), where each step changes the gauge by at most n^−3/4.A local moment of degree one controls exit from this height region; the coarse bound supplies the starting state.Source: §7.8 · pp. 63–64
  • The coupled barriers stop the process if either the gauge exceeds H0 + 2 or any height exceeds H.Before the stopping time, the state satisfies the conditions for both the gauge drift bound and the local clearance argument.Source: §7.8 · p. 64
  • The gauge rule achieves terminal radius at most C_k(√s + log ℓ) with failure probability at most n^−k in the stated range.The proof combines a coarse bound for the starting state with a coupled gauge and height barrier over a window before T.Source: §7.8 · pp. 63, 65
  • The range's lower endpoint keeps H at order at most ℓ/log ℓ, while its upper endpoint is where the coarse bound becomes sharp.These conditions support the local large-exponent argument and mark the range where bootstrapping is needed.Source: §7.8 · pp. 63, 65

7.9 A hybrid rule for small sparsity

For small sparsity, the paper uses a hybrid rule that prioritizes high coordinates and otherwise follows a hyperbolic-cosine potential. Its terminal guarantee combines with the gauge bounds to prove the terminal theorem, while quadratic Greedy provides the corresponding pair result.

7.9 A hybrid rule for small sparsity

  • When the set of high coordinates is small and the arrival hits it, the hybrid rule moves the highest selected coordinate inward; otherwise it uses the cosh choice.The rule combines high-coordinate priority with the gradient of the hyperbolic cosine potential; elementary symmetric polynomials of cosh(ωS_i) are used to control populations.Source: §7.9 · p. 65
  • The hybrid rule's moment bound extends to signed inputs because the rule and the bound depend on selected-coordinate magnitudes.The proof transfers the binary-input estimate to signed inputs.Source: §7.9 · p. 66
  • For 2 ≤ s ≤ √n, the hybrid rule gives terminal radius O_k(√s log(s + 1) + log ℓ) with failure probability n^−k in both models.Its terminal analysis composes population and height bounds over a finite window.Source: §7.9 · p. 67

7.10 Proof of the terminal theorem

  • Combining the hybrid and gauge bounds gives terminal discrepancy O_k(√s + log log n) with failure probability n^−k across the theorem's stated model ranges.For s ≤ log ℓ, the hybrid radius simplifies because √s log(s + 1) ≤ log ℓ; the other sparsity ranges use Propositions 11 and 10.Source: §7.10 · p. 67, §7.9 · p. 67

7.11 Quadratic Greedy for pairs

  • For s = 2, quadratic Greedy has expected terminal discrepancy Θ(log log n) uniformly for T ≥ n.It also has polynomially small failure probability at every prescribed time, and thus attains the optimal order of both objectives for pairs.Source: §7.11 · pp. 67–68

8 Corollaries, benchmarks, and complements

The corollaries sharpen the horizon-dependent prefix bounds, give a horizon-independent restart rule, and establish terminal and prefix guarantees across specified sparsity ranges. They also describe the much-later infinite-horizon limit and identify scope boundaries for binary inputs.

8.1 Expected prefix discrepancy

  • For s = 2, the expected prefix discrepancy is determined throughout n ≤ T ≤ e^cn; for fixed s ≥ 3, its bounds have horizon exponents α_s and 1/2.The two exponents coincide for s = 2, while the transition for fixed s ≥ 3 is not identified exactly.Source: §8.1 · pp. 68–69

8.2 A rule independent of the horizon

  • The restart rule is deterministic, uses neither T nor δ, and attains the stated upper bound with one sequence of signs across horizons.Its guarantee applies in both models for s ≥ 3 under the conditions of Proposition 13.Source: §8.2 · pp. 69–70

8.3 Beyond exponential horizons

  • As T tends to infinity, the prefix discrepancy limit is of order n^(s−1) for fixed s in both models.The limit is approached only far beyond the exponential horizons covered by Corollary 1; for fixed s ≥ 3, when it is reached remains open.Source: §8.3 · pp. 70–71

8.4 Consequences of the terminal bound

  • At every prescribed T ≥ n, the optimal expected terminal discrepancy is of order √s + log log n, and the rule of Theorem 2 attains this order.The same rule controls prefix discrepancy at every polynomial horizon T ≤ n^β with radius O_{β,k}(√s + log log n) and failure probability n^(−k).Source: §8.4 · pp. 71–72

8.5 Prefix bounds for growing sparsity

  • For 2 ≤ s ≤ (log(en))^2, the gauge rule gives optimal prefix order √s + log log n when log T ≤ √s min{s, log(en)}.This range extends beyond every polynomial horizon when s/(log(en))^(2/3) tends to infinity.Source: §8.5 · pp. 72–73

8.6 Benchmarks and complements

  • Known fixed-sequence benchmarks can match O(√s) in the stated sparsity regime, while the paper notes limits on its own binary-input coverage.Theorems 1 and 2 do not determine the long-horizon order for binary s = n−2, and Theorem 2 does not cover n/2 < s < n.Source: §8.6 · pp. 73–74

9 Open questions and a conjecture

The open questions focus on whether the prefix exponent for fixed s ≥ 3 reaches the square-root law, how sparsity and horizon jointly affect discrepancy, and what bounds hold for terminal tails and random edge orientations. The paper also identifies a quadratic-forcing question that could close the exponent gap.

9 Open questions and a conjecture

  • For fixed s ≥ 3, the paper conjectures prefix discrepancy of order log log n + (log T / log n)^(1/2) throughout n ≤ T ≤ e^cn.The proved exponent lies between α_s and 1/2, and the paper says the gap may reflect the lower-bound method rather than the game.Source: §9 · p. 74
  • It remains open whether a three-touch safety game can force exit from radius R within O(R^2) requests using O(R^2) coordinates.The known forcing time lies between order R^2 and O(R^(7/3)); the analogous four-touch question is also posed.Source: §9 · p. 74
  • The proposed joint sparsity-horizon order remains unresolved beyond established regimes, including for dense Rademacher inputs up to T = e^cn.The passage lists polynomial horizons, a large-sparsity regime, and a growing-sparsity regime as ranges where the proposed order holds.Source: §9 · p. 75
  • For fixed s, the paper asks whether the terminal radius is O(log log n + (log(1/δ) / log n)^α_s) across e^(−n) ≤ δ ≤ n^(−C_s).For s = 2, the cited expected-prefix result gives the exponent 1/3; for s ≥ 3, Conjecture 1 predicts exponent 1/2.Source: §9 · p. 75
  • For uniformly random complete-graph edges, it remains open whether optimal prefix discrepancy is of order log log n + (log T / log n)^(1/3).The paper notes that its proof for pairs does not apply directly to the edge model.Source: §9 · p. 75

A Limits of the lower-bound method

The appendix analyzes how the finite safety game and its forcing arguments constrain the lower-bound exponents.

A Limits of the lower-bound method

A.1 Quadratic survival

The quadratic-survival analysis bounds how long Greedy can remain inside a cube and compares that bound with forcing times in the safety game.

A.1 Quadratic survival

  • Greedy starting at zero survives at least (R^2 + F_(r−1)(R))/r requests before leaving the radius-R cube.For r ≥ 2, this is at least R^2/(r−1) requests, regardless of the adversary.Source: §A.1 · p. 76
  • Even with unlimited coordinates, the forcing-time bound limits the heights obtainable from Proposition 5 to order (log T / log n)^(1/2) for fixed s.Source: §A.1 · p. 76
  • For r ≥ 3, the quadratic-survival bound is sharp up to a constant for quadratic Greedy with ties broken toward +1.That rule can be forced to every height H within O(H^2) requests.Source: §A.1 · p. 76
  • With two touches, the cubic forcing time is the true order: the safety set remains nonempty through J = R^3/128 requests.The stated bound holds for every m and R ≥ 1.Source: §A.1 · p. 76

A.2 A barrier for static width certificates

This section bounds the strength of Lemma 8’s width certificate when it uses static coefficients: its exponent is limited by how many distinct roots the chosen directions can produce. The bound also persists under nonnegative weighted scores, but does not rule out stronger certificates using other approaches.

A.2 A barrier for static width certificates

  • With alphabet V_{m,k+1}, directions with v_1=1 have at most K_kΛ^(1−2^−k) distinct roots −⟨a,v⟩.Here a_1=0 and Λ=∥a∥_1≥1; K_0=1 and K_k=2^k+1+2K_{k−1}.Source: §A.2 · p. 77
  • When Lemma 8 has N>2R distinct roots, its static-certificate forcing-time bound implies Λ>(2R/K_k)^η_k.The exponents α_s=1/β_s−1 are exactly the limit of this certificate evaluation with its budget and guaranteed unit decrease at all but 2R roots.Source: §A.2 · p. 77
  • The same forcing-time barrier applies to nonnegative weighted scores evaluated by this method, provided their guaranteed decrease d_ω is positive.Positive d_ω requires more than 2R positively weighted roots, so the same root-counting argument applies.Source: §A.2 · p. 77
  • The proposition does not exclude stronger certificates using larger actual score decreases, smaller actual ranges, adaptive coefficients, or different adversaries.Symmetry of the safety sets only makes the scores nonnegative, which halves the range.Source: §A.2 · p. 77

B Forcing quadratic Greedy

For signed inputs with fixed s≥3, an adaptive forcing strategy can drive quadratic Greedy to height H within O(H^2) arrivals. Realizing the prescribed arrivals in the random input law yields a high-probability lower bound of order (log T/log n)^(1/2) over long horizons.

B Forcing quadratic Greedy

  • This forcing construction is specific to quadratic Greedy with ties toward +1 and does not show a lower bound against every controller.The parity rule keeps main-coordinate heights at most five against these directions, regardless of their order.Source: B Forcing quadratic Greedy · pp. 77, 80
  • From every state whose m(H) main heights are below H, an adaptive sequence of at most R_H=48H^2+1 arrivals forces a main coordinate to height H, if m(H)+s−3≤n.The construction needs m(H)≤2⌈log_2(2H)⌉+2 main coordinates and s−3 auxiliary coordinates.Source: B Forcing quadratic Greedy · p. 78
  • For fixed s≥3, quadratic Greedy has D_T≥c_s(log T/log n)^(1/2) with probability at least 1−n^(−k) when C_{s,k}log n≤log T≤n^2.At T=⌊e^(cn)⌋ for fixed c>0, the bound is of order √(n/log n).Source: B Forcing quadratic Greedy · pp. 78–79
  • The forcing argument uses Fibonacci-recursive weights w_j, with W=w_m chosen so 4H≤W<8H, to certify that a suitable direction exists below height H.The bounded certificate satisfies ∥w∥_1≤3W, while the proof bounds the number of consecutive steps before a main height reaches H by 6(H−1)W+1≤48H^2+1.Source: B Forcing quadratic Greedy · pp. 78–79
  • The strategy presents a direction u_j with ⟨S,u_j⟩≤0, which Greedy adds; a certificate y makes ⟨y,S⟩ increase by one on each such step.The directions have three nonzero entries in {±1}; for s>3, auxiliary marks ensure their contribution to ⟨S,V⟩ is nonpositive.Source: B Forcing quadratic Greedy · pp. 78–79
  • In a block of R_H random arrivals, the prescribed direction-and-marks event has conditional probability at least p_s^R_H, yielding the stated high-probability bound across complete blocks.The strategy is state-measurable and each required arrival is independent of the past; because the tie rule is asymmetric, only the prescribed orientation is counted.Source: B Forcing quadratic Greedy · p. 79
Loading 2610.34410v1…