2025年10月21日¶

\(\newcommand{Cone}{\mathop{\operatorname{cone}}}\) \(\newcommand{Span}{\mathop{\operatorname{span}}}\) \(\newcommand{Supp}{\mathop{\operatorname{supp}}}\)

A Rackoff Lemma for Geometrical \(g\)-Dimension¶

Consider \(\Span(V) = \Span(\mathbf{v}_1, \ldots, \mathbf{v}_g)\). By multiplying with an invertible matrix \(H\), we can create an identity sub-matrix in \((\mathbf{v}_1 \; \cdots \; \mathbf{v}_g) \cdot H\). Clearly if on some configuration \(\mathbf{c}\) we have \(\mathbf{c}|_{\Supp(\mathbf{v}_i)} \ge B \cdot \vec{1}\) then we can ignore all counters in \(\Supp(\mathbf{v}_i)\), dropping the geometrical dimension by \(1\) and do the induction.

Otherwise (the bad case), if for all ways of creating identity sub-matrix by \(H\), the configuration is not lower-bounded by \(B\) on any of the supports, we show that we can find an invertible matrix \(H'\) such that on the counters corresponding to those identity positions, \(\mathbf{c}\) has value bounded by \(B\).

Indeed, let \(H\) be such that on the identity positions, the number \(k\) of bounded counters is maximal. If \(k = g\) we are done. Otherwise, find a vector \(\mathbf{v}_i\) such that its identity position is unbounded in \(\mathbf{c}\). There must be a counter in \(\Supp(\mathbf{v}_i)\) that is bounded by \(B\) otherwise we fall into the previous case. By Gaussian elimination we can make this counter corresponding to an identity position, without changing other identity positions. This contradicts to the maximality of \(k\).

There are only a bounded number of bad configurations, namely at most \(\binom{d}{g} \cdot B^g \cdot |Q|\) on each fixed run, where we have \(\binom{d}{g}\) choices of identity positions, \(B^g\) of bounded counter values, and \(|Q|\) many shifts caused by simple paths.

Thus, length of the shortest covering run can be bounded by induction on geometrical dimension.