2025年10月28日¶
\(\newcommand{Cone}{\mathop{\operatorname{cone}}}\) \(\newcommand{Span}{\mathop{\operatorname{span}}}\) \(\newcommand{Supp}{\mathop{\operatorname{supp}}}\) \(\newcommand{BSeq}{\mathop{\operatorname{Seq'}}}\) \(\newcommand{Intr}{\mathop{\operatorname{int}}}\)
Non pumpable implies bounded counter, bounded in terms of geometric dimension¶
Recall from day 2 that bad configurations (i.e. configurations not allowing to kill one space-generator) has bounded number of possibilities, namely \(\binom{d}{g}B^g |Q| =: H\). On a run of length shorter than \(H\) any counter cannot exceed \(H \Vert T\Vert\). Thus if one counter exceed \(VH := H \Vert T\Vert\) then we can do induction by decrease the geometric dimension. We end up with the following lemma:
Lemma
For every number \(U\) and source \(p(\mathbf{s})\) there is a number \(VH_g = \text{poly}(|Q|, \Vert T \Vert, U, d)^{g^g}\) where \(g\) is the geometric dimension, such that if there is a run from \(p(\mathbf{s})\) where for every counter \(i \in [d]\) there is a configuration \(q_i(\mathbf{x}_i)\) on the run with \(\mathbf{x}(i) \ge VH_g\), then there is a pump from \(p(\mathbf{s})\).