The Price of Nesting: Deterministic Anytime Line Packings

Many systems hand out signature vectors one at a time and cannot take them back. Examples include pilot sequences assigned to devices as they join a network, codewords burned into deployed sensors, and features added to a dictionary. Each new vector must interfere as little as possible with the ones already issued. In the language of frame theory, the system is building a line packing: a set of directions through the origin whose worst pairwise correlation (the "coherence") should be small. The classical theory asks for the best packing of a known number $N$ of lines in dimension $D$. Its champions are equiangular tight frames (ETFs), configurations in which every pair of lines meets at the same angle and the energy is perfectly balanced, so that they meet the Welch lower bound on coherence exactly. A system that does not know $N$ in advance needs something different. It needs one fixed, deterministic sequence of vectors whose every prefix is nearly optimal for its own size.

This note proposes to measure and bound the price of nesting: how much worse than the size-by-size optimum a single deterministic sequence must be. Our central observation is that exact ETFs are precisely the wrong objects to pass through. Any perfectly energy-balanced prefix is a dead end: every later vector is forced to coherence at least $1/\sqrt{D}$. Near-optimal anytime packings must therefore keep a controlled spectral "reserve" of nearly empty directions. Trading that reserve against current coherence yields both computable lower bounds and a design principle for constructions. The principle draws on the combinatorial gluing ideas used to build ETFs, but uses them for the opposite purpose.

Core Claim

Fix the dimension $D$ and let $\mu^\star(t)$ denote the best coherence achievable by $t$ unit vectors. For $t \le D$ this is $0$; above $D$ it is at least the Welch bound $W(t) = \sqrt{(t-D)/(D(t-1))}$. A deterministic anytime packing is an infinite sequence $\varphi_1, \varphi_2, \dots$, and its quality on a window $[t_0, t_1]$ is

$$ R(t_0,t_1) = \max_{t_0 \le t \le t_1} \frac{\mu(\varphi_1,\dots,\varphi_t)}{\mu^\star(t)} . $$

This is the projective analogue of the all-time-worst-case dispersion objective of Efficient Approximations for the Online Dispersion Problem. That work places points one by one in Euclidean intervals and polytopes, and the adversary chooses when to stop. Their deterministic ratios ($2\ln 2+\epsilon$ in 1D, $1.591$ in the square against a lower bound of $1.183$) are the only competitive-ratio numbers for online packing in the file. Nothing in the file addresses lines through the origin, where tightness and the Welch bound change the geometry.

Two easy facts show where the problem is trivial and where it is not.

The first fact concerns the strict version that starts at $t_0=1$. Here any finite ratio forces the first $D$ vectors to be orthonormal. The first vector after that has coherence at least $1/\sqrt{D}$, because its squared inner products with the basis sum to one. In prime-power dimensions, a chain of mutually unbiased bases attains exactly $1/\sqrt{D}$ up to $t = D(D+1)$. That chain is therefore pointwise optimal among sequences with finite strict ratio, and the strict problem is settled there. The second fact is that for $t \ge 2D$ the Welch bound is within a factor $\sqrt 2$ of $1/\sqrt{D}$. Any sequence holding coherence near $1/\sqrt D$ is therefore near-competitive in that range.

The open regime is low redundancy, $t \in (D, 2D]$, where $W(t)$ climbs from $1/D$ to about $1/\sqrt{2D}$. Here the obstacle is a dead-end inequality. Write $S_s = \sum_{i \le s} \varphi_i\varphi_i^*$ for the frame operator of the first $s$ vectors and $\lambda_{\min}(S_s)$ for its smallest eigenvalue. Then any next vector $v$ satisfies

$$ \max_{i \le s} |\langle v, \varphi_i\rangle|^2 \;\ge\; \frac{v^* S_s v}{s} \;\ge\; \frac{\lambda_{\min}(S_s)}{s}. $$

A tight prefix has $\lambda_{\min} = s/D$, so its successor has coherence at least $1/\sqrt D$. Starting from a simplex, the optimal $D+1$ packing, this already costs a ratio of about $\sqrt{D/2}$ at $t = D+2$.

Pushing $\lambda_{\min}$ down is not free. With the trace fixed at $s$, a small $\lambda_{\min}$ raises the frame potential $\mathrm{tr}(S_s^2)$, and that raises the current coherence through $\mu^2 \ge (\mathrm{tr}(S_s^2) - s)/(s(s-1))$. Rank-one updates also make successive spectra interlace.

We claim three things. First, the price of nesting on $(D,2D]$ is bounded by a constant independent of $D$. A crude direct-sum construction suggests this: a simplex on half the space plus an orthonormal basis on the other half has coherence $2/D$ at $t = D+1$. Second, the constant is strictly greater than one, and the interlacing spectral program certifies a value for it. Third, the best sequences are built by gluing small simplices along combinatorial skeletons while deliberately leaving the result non-tight.

How the Four Directions Fit

The four directions play different roles. Optimal line packing supplies the objective and the Welch reference point. The difficulty of constructing ETFs is the mechanism. Minimization of the probabilistic p-frame potential shows that for $N = D+1$ the minimizer jumps discontinuously from "orthonormal basis plus a duplicate" to the simplex as the exponent crosses a threshold. This is proven only for $D=2$, with $D>2$ left as Conjecture 3.8. We read that jump as evidence that optimal packings at neighboring sizes are far apart, which is exactly why nesting has a price.

Prime tight frames shows that tight frames resist continuous deformation. That result constrains our designs: one cannot pass through a tight configuration and then smoothly keep going.

Synergistic construction supplies the method. The Tremain ETFs in Tremain equiangular tight frames embed small Hadamard-derived simplices into coordinate subspaces indexed by the points of a Steiner triple system. Because each pair of points lies in exactly one block, cross-talk between pieces stays controlled. Equiangular Tight Frames From Hyperovals does the analogous gluing with hyperovals in projective planes. Both papers aim for a finished tight object. We reuse the gluing language but order the pieces so that every intermediate union keeps a spectral reserve, and we stop short of the tight endpoint.

The deterministic-algorithm direction supplies the evaluation discipline. The algorithm is a fixed sequence, so an adversary knowing the code picks the worst stopping time, as in the dispersion work. The deterministic channel-access results of Broadcasting on Adversarial Multiple Access Channels motivate why guarantees for every prefix matter in practice.

Research Program

The theoretical arm formalizes the reserve trade-off as a finite program over spectra. The variables are the spectrum of $S_t$ for each $t$ in the window, constrained to have trace $t$ and to interlace between consecutive steps. Two bounds tie the spectra to coherence: the frame-potential bound gives the current coherence, and the $\lambda_{\min}/s$ bound gives the next step's coherence. Minimizing the worst ratio over this relaxation gives a certified lower bound $L(D)$ on $R(D+1, 2D)$.

The relaxation ignores how vectors actually overlap, so it may be loose. We will tighten it with the stronger known bounds for small $t-D$, using the Naimark-complement relationship: an ETF of $N$ vectors in dimension $D$ corresponds to one in dimension $N-D$. We will also try to prove that $L(D)$ tends to a constant above one. In the smallest case, $D=2$ or $3$, we will attempt exact verification with the algebraic decomposition approach of Packings in Real Projective Spaces. That paper notes the method's doubly exponential cost, so we expect it to work only for the first few sizes.

The constructive arm builds three families of sequences. The first is recursive direct sums of simplices, with explicit ratios. The second is block-ordered gluings in the Tremain and Steiner style, where small simplices are added one design point at a time across dimensions supplied by resolvable designs. For these we will compute prefix spectra exactly. The third is harmonic sequences that add rows of discrete Fourier matrices in a deterministic order chosen to keep $\lambda_{\min}$ low. Here we draw on the group-Fourier constructions of Low-Coherence Frames From Group Fourier Matrices.

We will also cover the two regimes our core claim calls easy but not finished. The first is dimensions without complete sets of mutually unbiased bases, for example $D=6$, and the real case. The second is the range beyond the Gerzon bound, where Welch is no longer the right reference.

Baselines

The naive reference point is a sequence of independent uniformly random unit vectors, with the ratio averaged over many draws and also taken in the worst case over draws. It costs nothing, and its coherence at the start of the window is far above $1/D$. This sets the floor any structured method must clear by a wide margin.

The strongest practical competitor is greedy online coherence minimization. Each new vector minimizes the maximum correlation to the vectors already placed, found by Riemannian gradient descent on the sphere with many restarts. The restart seeds are fixed so the procedure is deterministic. It is strong because it directly optimizes the quantity being measured at every step. For fairness, all methods get the same dimensions, the same windows, and the same total wall-clock optimization budget. Beating it means a strictly smaller worst-window ratio $R(D+1,2D)$ for the majority of $D$ in our sweep, with the gap growing in $D$.

The strongest offline competitor is joint optimization of the entire nested sequence. All $2D$ vectors are optimized together against the smoothed all-time ratio, starting from many initializations, including our constructions. This is not an online algorithm. It is our best numerical estimate of the true price of nesting, and the distance between it and the lower bound $L(D)$ is the quantity the theory must explain.

The denominators are the Welch bound and the best non-nested packing found by independent optimization at each size $t$. We report both to separate the real price of nesting from slack in the Welch bound.

There is no reported result on Lacuna for online or anytime line packing. The closest reported numbers are the deterministic all-time-worst-case dispersion ratios of Efficient Approximations for the Online Dispersion Problem: $1.591$ upper and $1.183$ lower in the square, and $2/(1-\epsilon)$ upper against $7/6$ lower for polytopes. Another is the offline approximation factor of about 49 within the Gerzon range from Packings in Real Projective Spaces. Neither is directly comparable, and we cite them only as scale.

Two ablations isolate the key ingredient. The first adds a reserve term $-\eta\,\lambda_{\min}(S_t)$ to the greedy objective, with $\eta$ tuned on a held-out set of dimensions, and compares it with plain greedy. If the reserve principle is correct, this term alone should account for most of the improvement. The second takes the block-ordered gluing constructions and shuffles the order of their blocks while keeping the same vectors. This tests whether ordering, rather than the vectors themselves, drives the result.

Why not just…?

Why not just use random vectors? Random vectors in dimension $D$ have coherence on the order of $\sqrt{\log t / D}$. This is fine for large redundancy but loses by roughly a $\sqrt{D}$ factor against $W(D+1) = 1/D$ at the start of the low-redundancy window, which is the regime we target. In the overloaded pilot setting of Grant-Free Access via Bilinear Inference for Cell-Free MIMO With Low-Coherence Pilots, unoptimized pilots combined with a standard receiver hit error floors that low-coherence pilots avoided. The random baseline will quantify the gap directly.

Why not just run greedy coherence minimization online? This is the real threat. Greedy may already find reserve-keeping configurations implicitly, because spreading vectors out early is myopically cheap. It is also possible that greedy instead walks into near-tight prefixes and then pays the dead-end penalty. The paper on online dispersion warns that greedy placement is exploitable in the Euclidean case, but that does not settle the projective case. If plain greedy matches joint optimization within a few percent, the practical contribution shrinks to the lower bound and an explanation of why greedy works. We will say so.

Why not just recompute the optimal packing whenever a vector is added? This is correct whenever reassignment is free. In that case the problem disappears and one simply uses the best packing for the current size, ETFs included. Our setting assumes issued vectors are irrevocable: deployed devices or pilots fixed at association time. The non-nested optimum enters our study as the denominator. For readers who can afford some reassignment, we will also report how many reassignments per step bring greedy down to that optimum.

Why not just chain mutually unbiased bases or other nested ETF families? These are exactly optimal for the strict problem, as shown above, and near-competitive for $t \ge 2D$. They cannot help on $(D,2D]$. Every prefix that contains a full orthonormal basis or ETF is tight, so the dead-end inequality applies. We include them in the sweep to confirm this.

Proposed Experiments

The main sweep covers real and complex dimensions $D$ from 3 to 64. For each method we compute the exact prefix coherence and the full prefix spectrum for $t$ from $D+1$ to $2D$. We then report the worst-window ratio, the location of the worst stopping time, and $\lambda_{\min}$ along the path. Separate shorter sweeps cover non-prime-power dimensions over $(D, D^2]$ and the real range up to $D(D+1)/2$.

The first decisive check is whether the certified lower bound $L(D)$ stays meaningfully above one, say above 1.1, for $D \ge 8$. If it collapses to one, the claimed price of nesting is an artifact.

The second decisive check is the reserve ablation. The test is whether adding $-\eta\lambda_{\min}$ to greedy closes most of the gap to joint optimization, and whether shuffling the block order of the glued constructions destroys their advantage.

The third check is downstream. We build a scaled-down admission scenario with 14-symbol pilots in which users arrive and receive the next vector in the sequence. We compare channel-estimation normalized mean squared error (NMSE) under a simple linear minimum-mean-square-error (MMSE) estimator across methods, as a function of how many users have arrived. Grant-Free Access via Bilinear Inference for Cell-Free MIMO With Low-Coherence Pilots reports NMSE between $10^{-3}$ and $10^{-4}$ at high signal-to-noise ratio with offline-optimized pilots and its message-passing receiver. We use this as the target for the full-population endpoint, while our question is how much is lost at intermediate populations. If the prefix-ratio ranking does not carry over to NMSE ranking, the coherence objective is the wrong proxy for this application, and we will report that.