Interval-tree certificates and connected higher-dimensional families

Proof

Suppose the gate is \(s\to t\) with \(s<t\). Let \(v_0\) be the lowest node of \(T\) whose two children separate \(s\) and \(t\). The order of the leaves forces \(s\in L_{v_0}\) and \(t\in R_{v_0}\). At this one node, a single row of the cross block \(X[R_{v_0},L_{v_0}]\) changes, so its rank changes by at most one.

At every ancestor of \(v_0\), the two rows lie in the same child. If that child is the right child, the gate is an internal row operation on the relevant cross block and preserves rank; if it is the left child, the cross block is unchanged. At a descendant containing \(t\) but not \(s\), every column of the descendant interval lies strictly to the right of \(s\). Since \(X\) remains lower triangular, row \(s\) vanishes on those columns, so the descendant block is unchanged. All other descendants are also unchanged. Hence only the term at \(v_0\) can vary.

Back to statement · Permalink · Source line 1962

Proof

The identity has potential zero. Apply Lemma 9.32 along any lower-directed word from the identity to \(A\).

Back to statement · Permalink · Source line 1975

Proof of Theorem 9.5

For the ambient construction, first apply

Sweep through the updates

Whenever phase \(s_j\) is reached, apply

Finally apply \(q\to p\) with coefficient \(-1\). At phase \(s\), the carrier is \(e_q+w_s\), so every output has the required value, and the final gate removes \(e_q\) from row \(p\). The word has length

Thus

For a lower word, perform the same \(u\) updates without opening the catalyst. At each selected phase, use the two gates

This gives length \(u+2v\).

It remains to prove optimality in the lower model. At the root, split

The nonzero rows of the root cross block are \(w_{s_1},\ldots,w_{s_v}\). Distinct prefix vectors are linearly independent: in a linear relation, inspect successively a coordinate occurring in \(w_{s_j}\) but in none of the earlier prefixes, starting from the largest phase. Hence the root contributes \(v\).

Inside the left child, use the comb that splits off \(x_1\), then \(x_2\), and so on while retaining \(p\) in the remaining interval. Every one of the \(u\) cuts has rank one because the final row \(p\) contains every \(x_i\). Inside the right child, repeatedly split off the last output while retaining \(q\) in the left interval. Each of the \(v\) cuts has rank one because every output contains \(q\). Therefore

The interval-tree lower bound matches the displayed lower circuit.

Back to statement · Permalink · Source line 2027

Proof

The restricted values follow from Theorem 9.5. The ambient words have lengths \(7\), \(8\), and \(9\). To exclude shorter words, the supplement computes exact ambient balls and checks that the two relevant balls do not intersect. The certificate sizes are

Every intersection is empty. Since the generating sets are symmetric, an empty radius-\(r\) versus radius-\(s\) intersection rules out every word of length at most \(r+s\).

Back to statement · Permalink · Source line 2110

Proof of Corollary 9.6

For \(n\ge7\), put

and take the phases

The inequality \(v_n\le u_n+1\) holds, so the snapshot target is defined. By Theorem 9.5,

while

Hence

Connectivity follows from the preceding remark.

Back to statement · Permalink · Source line 2130

Proof

Along the optimized connected family,

which tends to \(3/2\).

Back to statement · Permalink · Source line 2201