Mutation-acyclicity in rank four is decidable but not semialgebraic

Source abstract

We prove that mutation-acyclicity of quivers on four vertices is decidable. If a four-vertex quiver $Q$ is mutation-acyclic, then some sequence of mutations takes it to an acyclic quiver without any arrow multiplicity exceeding $\operatorname{max}\{\operatorname{ht}(Q),m(Q)\}$, where $\operatorname{ht}(Q)$ is the largest arrow multiplicity of $Q$ and $m(Q)$ is the Markov invariant of Fomin and Neville evaluated on the totally proper wiggle class of $Q$. A search within a computable form of this bound decides mutation-acyclicity of four-vertex quivers with $O(h^{24})$ states for input height $h\ge1$. Together with a theorem of Caldero and Keller, it also decides mutation equivalence of two four-vertex quivers up to relabeling whenever one of them is mutation-acyclic. We conjecture that $\operatorname{ht}(Q)$ alone suffices as the bound, which would reduce the search to $O(h^{6})$ states, and we verify this for all four-vertex quivers of height at most three. In the other direction, for every $n\ge4$ we construct an affine family of connected $n$-vertex quivers whose nonnegative even members are mutation-acyclic and whose positive odd members are mutation-cyclic. Consequently, unlike in rank three, no fixed finite Boolean combination of polynomial equations and strict polynomial inequalities in the arrow weights (i.e., a semialgebraic criterion) decides mutation-acyclicity of $n$-vertex quivers, even allowing polynomials that are not mutation-invariant. Finally, we correct the criterion for four-vertex quivers of height at most two stated in our earlier paper, and recover its classification counts with short certificates. The calculations in the proof of the height bound are verified by computer for all values of their parameters.