2025年10月20日¶

Wideness of Strongly Connected Geometrical VASS¶

\(\newcommand{Cone}{\mathop{\operatorname{Cone}}}\) \(\newcommand{Span}{\mathop{\operatorname{Span}}}\)

Let \(V\) be a strongly connected \(d\)-VASS with geometrical \(g\). We say \(V\) is wide if its forward (open) cone \(\Cone(V)\) and backward cone \(\Cone(V^{\text{rev}}) = - \Cone(V)\) has non-empty intersection. We have the following observations:

Proof. The "if" direction is obvious as \(\Cone(V) = \Span(V)\) implies \(-\Cone(V) = -\Span(V) = \Span(V)\) as well. For the "only if" part, assume \(\mathbf{w} \in \Cone(V) \cap -\Cone(V)\). Let \(\mathbf{x} \in \Span(V)\) be arbitrary, we need to show that \(\mathbf{x} \in \Cone(V)\).

Let \(\mathbf{x} = \sum_{i = 1}^r \lambda_i \mathbf{v}_i\) for \(\lambda_i \in \mathbb{Q}\). Also let \(\mathbf{w} = \sum_{i = 1}^r \mu_i \mathbf{v}_i\) for \(\mu_i > 0\) (we are talking about open cones). Then \(\mathbf{x} + h \mathbf{w} \in \Cone(V)\) for sufficiently large \(h\). Notice that \(-h\mathbf{w} \in \Cone(V)\) as we assumed. We conclude that \(\mathbf{x} = \mathbf{x} + h\mathbf{w} - h\mathbf{w} \in \Cone(V)\).