Introduction
Quivers are finite directed multigraphs without loops or directed 2-cycles. Fomin and Zelevinsky introduced quiver mutation in their theory of cluster algebras [35 , 36 ] . A quiver is mutation-acyclic if some sequence of mutations takes it to a quiver without directed cycles, and mutation-cyclic otherwise. Mutation-acyclic quivers are the quivers of acyclic cluster algebras, which have been studied through cluster categories and quiver representations [BMR08, BMRT07, CK06, CK08], through c c c -vectors [46 , 44 ] , and through reflection groups [9 , 30 , 31 ] . This paper concerns the following decision problem.
Problem 1. Given a quiver Q Q Q , decide whether Q Q Q is mutation-acyclic.
Neville records that no algorithm for Problem 1 is known [41 Chapter I] , and in our earlier paper we noted that no algorithm or mutation invariant was known to decide mutation-acyclicity in rank four or higher [3 ] . The problem is closely related to deciding mutation equivalence, for which Fomin, Williams and Zelevinsky ask for an algorithm [34 Problem 2.6.12] , and for which no algorithm is known [26 FI21, Remark 2.3] , [27 slide 7] .
For quivers with at most three vertices, Problem 1 is solved. Quivers with one or two vertices are acyclic. For three vertices, Assem, Blais, Brüstle and Samson gave a descent algorithm [1 Section 2.5] , and Beineke, Brüstle and Hille proved that an oriented triangle is mutation-cyclic exactly when its multiplicities are at least two and its Markov constant is at most four [4 Theorem 1.2] .
2020 Mathematics Subject Classification. 13F60, 05E10, 05C20, 68V05.
Key words and phrases. quiver mutation, mutation-acyclicity, decidability, Markov invariant, proper cyclic orderings, polynomial invariants, computer-assisted proof.
K.T.K.A.W. was supported by a Royal Society Career Development Fellowship. E.H. was supported by a São Paulo Research Foundation (FAPESP) grant 2024/18994-7. B.J. was supported by ICARM through NSF grant DMS-2425401. K.-H.L. was supported by NSF grant DMS-2617278. Seven extended the description of rank-three mutation classes to skew-symmetrizable matrices [43 ] , Akagi gave the skew-symmetrizable form of the Markov-constant criterion [2 ] , and Felikson and Tumarkin and Casals and Ke studied rank-three quivers with real weights [32 , 17 ] . Quivers of finite mutation type, classified by Felikson, Shapiro and Tumarkin [29 ] (see also [20 ] and, for acyclic quivers, [12 ] ), have finite mutation classes, so for them the problem reduces to a finite enumeration.
For quivers with four or more vertices, only partial results are known. Felikson and Tumarkin showed that a quiver mutation-equivalent to an acyclic quiver with at least two arrows between every pair of vertices reaches such a quiver by a descent that never increases an arrow multiplicity [31 Corollary 3.5 and Remark 3.6] , and they note that Corollary 3.5 is also proved in Warkentin’s thesis [War14]. Lawson and Mills determined which minimal mutation-infinite quivers are mutation-acyclic [38 Section 4] . In an earlier paper, we classified the four-vertex quivers with at most two arrows between any two vertices [3 ] , in the course of a machine-learning study; see [6 HJC+25, 19 ] for other applications of machine learning to quiver mutation. The criterion stated in [3 Theorem 2.9] is wrong, and we correct it in Section 6.
There is also a long list of necessary conditions for mutation-acyclicity. Buan, Marsh and Reiten proved that every full subquiver of a mutation-acyclic quiver is mutation-acyclic [BMR08, Corollary 5.3], a consequence of their Theorem 2.13 that was pointed out to them by A. Seven, and Warkentin gave a more explicit proof [48 ] . Both proofs are representation-theoretic, and an elementary proof is still wanted [FWZ17, Example 4.1.5], [27 slides 11–12] . Every mutation-acyclic quiver admits an admissible quasi-Cartan companion [44 Theorem 1.2] , a notion going back to Barot, Geiss and Zelevinsky [8 ] . Every mutation-acyclic quiver also has a reddening sequence, since acyclic quivers have maximal green sequences [5 Lemma 2.20] and the existence of a reddening sequence is mutation invariant [40 Corollary 19] . Neville proved that every mutation-acyclic quiver is totally proper [42 Theorem 1.1] , as conjectured by Fomin and Neville [26 Conjecture 15.9] . Warkentin’s forks give further mutation-invariant tools [War14], developed by Ervin [23 ] . In rank four there are mutation-cyclic quivers without mutation-cyclic full subquivers on three vertices, such as the dreaded torus [39 Section 7.2] , whose cluster algebra comes from a torus with one boundary component and one marked point [28 ] , and Warkentin’s oriented four-cycles with multiplicities a , b , c , d ≥ 2 a,b,c,d \ge2 a , b , c , d ≥ 2 [War14, Example 6.11]. Mutation invariants beyond the determinant are studied in [14 , 13 , 47 , 23 , 25 , 26 ] , and Ervin and Jackson ask for a description of mutation-acyclicity as an intersection of hereditary mutation-invariant properties [21 ] .
The starting point for our main result is a finiteness theorem of Neville. Fomin and Neville attach to a quiver with a cyclic ordering of its vertices a Markov invariant [26 ] . For a mutation-acyclic quiver Q Q Q , write m ( Q ) m(Q) m ( Q ) for its value on the totally proper wiggle class of Q Q Q (§ 2 ), and ht ( Q ) \operatorname{ht}(Q) ht ( Q ) for the largest arrow multiplicity of Q Q Q . Neville proved that the arrow multiplicities of every acyclic quiver in the mutation class of Q Q Q are bounded in terms of m ( Q ) m(Q) m ( Q ) , so that only finitely many acyclic quivers share a given Markov invariant [42 Proposition 3.21] . Our main result extends this bound from the acyclic quivers of a mutation class to a mutation sequence leading to one of them.
Theorem 1.1. Let Q Q Q be a mutation-acyclic quiver on four vertices. Then some sequence of mutations takes Q Q Q to an acyclic quiver, with every quiver along the sequence of height at most max { ht ( Q ) , m ( Q ) } \max\{\operatorname{ht}(Q),m(Q)\} max { ht ( Q ) , m ( Q )} . Consequently, mutation-acyclicity of four-vertex quivers is decidable. For input height h ≥ 1 h \ge1 h ≥ 1 , the decision procedure searches O ( h 24 ) O(h^{24}) O ( h 24 ) quivers.
The height statement is Theorem 5.1 , and the decision procedure and the state count are Corollaries 5.2 and 5.3. Since the totally proper class of Q Q Q is not known in advance, the procedure uses the largest Markov value over all proper wiggle classes of Q Q Q in place of m ( Q ) m(Q) m ( Q ) , and a four-vertex quiver without proper wiggle classes is a vortex and hence mutation-cyclic. The bound concerns the existence of one suitable mutation sequence, and other routes to an acyclic quiver may climb arbitrarily high. The running time is pseudo-polynomial in the arrow multiplicities, rather than polynomial in their binary encoding length.
The proof chooses a route to an acyclic quiver that minimizes its maximum height, then the number of quivers at that height, then its length, and shows that a stretch of such a route above max { ht ( Q ) , m ( Q ) } \max\{\operatorname{ht}(Q),m(Q)\} max { ht ( Q ) , m ( Q )} could be replaced by a lower one. The replacements are found by a case analysis on how the first two mutation vertices of such a stretch are joined. Every calculation in this case analysis is verified by a computer program, exactly and for all values of the parameters (Appendices § 7 and § 8 ). Descent methods face an obstacle in rank four. Fomin and Neville constructed arbitrarily long primitive mutation cycles of four-vertex quivers, and observed that any descent algorithm would have to be confluent over arbitrarily large diamonds [25 ] ; see also [22 ] and [41 Chapter I] . Soukup observes that if mutation equivalence were undecidable, some equivalent quivers would be joined only by extremely long mutation sequences, going far “into the sky”, and suggests that a bound like that of Coward and Lackenby for Reidemeister moves may exist for quiver mutation [45 Sections 4.1–4.2] , [18 ] . Theorem 1.1 gives such a bound for mutation-acyclicity in rank four, since a bound on height also bounds the length of a shortest route.
We do not know whether the term m ( Q ) m(Q) m ( Q ) is needed. We conjecture that ht ( Q ) \operatorname{ht}(Q) ht ( Q ) alone suffices, which would reduce the search to O ( h 6 ) O(h^6) O ( h 6 ) quivers, and we verify this for all four-vertex quivers of height at most three (Conjecture 5.5 ). The height bound also certifies mutation-cyclicity in an example where none of the other obstructions of this paper applies to any quiver within the search range (Example 5.4). Combined with the description of acyclic seeds by Caldero and Keller [CK06, Corollary 4 and its proof], Theorem 1.1 also decides mutation equivalence of two four-vertex quivers up to relabeling whenever at least one of them is mutation-acyclic (Corollary 5.7 ).
Our second main result shows that no criterion of the kind that works in rank three can exist in higher rank. The rank-three criterion of Beineke, Brüstle and Hille is a finite Boolean combination of polynomial sign conditions on the arrow weights.
Theorem 1.2. Let n ≥ 4 n \ge4 n ≥ 4 . No fixed, finite Boolean combination of polynomial equations and strict polynomial inequalities in the ( n 2 ) \binom{n}{2} ( 2 n ) arrow weights, with real coefficients and not necessarily mutation-invariant, decides mutation-acyclicity for all integral quivers on n n n vertices. This remains true when the quivers are required to be connected.
For n = 4 n=4 n = 4 the proof uses the affine family Q ( t ) Q(t) Q ( t ) , t ∈ Z t \in\mathbb{Z} t ∈ Z , of § 3 , with arrow weights ( − 2 , t + 2 , t , − t , 2 − t , 0 ) (-2,t+2,t,-t,2-t,0) ( − 2 , t + 2 , t , − t , 2 − t , 0 ) in the coordinates of § 2 . The family is mutation-acyclic exactly when t < 0 t<0 t < 0 or t t t is even, so for large positive t t t its mutation-acyclicity changes at every successive integer. In contrast, substituting the six affine arrow weights into any fixed polynomial gives a one-variable polynomial, whose sign is eventually constant unless it vanishes identically. For n > 4 n>4 n > 4 we attach a path to Q ( t ) Q(t) Q ( t ) .
Chelnokov proved that a mutation invariant of four-vertex quivers that is polynomial on each sign pattern of the arrow weights is a polynomial in the determinant [14 Theorem 1] . The family Q ( t ) Q(t) Q ( t ) has determinant 16 16 16 for every t t t , so criteria built from such invariants cannot decide mutation-acyclicity, and Theorem 1.2 complements this by removing the invariance hypothesis. The family is also invisible to the Markov invariant and to properness, since every Q ( t ) Q(t) Q ( t ) with t ≥ 0 t \ge0 t ≥ 0 has a single proper wiggle class, with the same Markov value as the acyclic quiver Q ( 0 ) Q(0) Q ( 0 ) (Remark 3.3). Theorem 1.2 does not rule out arithmetic tests, mutation invariants in general, or algorithms whose number of steps depends on the input, and Theorem 1.1 is an algorithm of the last kind.
Finally, § 6 corrects the criterion of [AWHL25, Theorem 2.9] for four-vertex quivers of height at most two and recovers the classification counts with short certificates. All computations in this paper are carried out by a supplementary Python package, and checking them needs only the Python standard library. The program check_proofs.py verifies every calculation delegated from the appendices, check_census.py verifies the certificates of § 6 with an independent implementation of mutation, and examples.py checks the examples. The main results are also formalized in Lean 4 with mathlib, and the Lean sources are available with the supplement at https://github.com/KTKAW/rank4-paper . The formalization proves decidability of mutation-acyclicity in rank four with a coarser computable height bound than that of Theorem 1.1 , the case n = 4 n=4 n = 4 of Theorem 1.2 for rational coefficients, Theorems 3.2 and 6.2 , and Proposition 6.1 , the last for every oriented four-cycle with multiplicities a , b , a , b ≥ 2 a,b,a,b \ge2 a , b , a , b ≥ 2 .
Quivers and mutation
A quiver of rank n n n is a quiver on the vertices 1 , … , n 1,\ldots,n 1 , … , n . Unless we explicitly take a smaller subquiver or say otherwise, our quivers have rank four. Every rank-n n n quiver Q Q Q has a skew-symmetric integral exchange matrix B Q = ( b i j ( Q ) ) B_Q=(b_{ij}(Q)) B Q = ( b ij ( Q )) , where b i j ( Q ) > 0 b_{ij}(Q)>0 b ij ( Q ) > 0 means that there are b i j ( Q ) b_{ij}(Q) b ij ( Q ) arrows i → j i \to j i → j . For rank four, we encode Q Q Q by the tuple
b ( Q ) = ( b 12 ( Q ) , b 13 ( Q ) , b 14 ( Q ) , b 23 ( Q ) , b 24 ( Q ) , b 34 ( Q ) ) = ( a , b , c , d , e , f ) , (1) \mathbf{b}(Q)=(b_{12}(Q),b_{13}(Q),b_{14}(Q),b_{23}(Q),b_{24}(Q),b_{34}(Q))=(a,b,c,d,e,f), \tag*{(1)} b ( Q ) = ( b 12 ( Q ) , b 13 ( Q ) , b 14 ( Q ) , b 23 ( Q ) , b 24 ( Q ) , b 34 ( Q )) = ( a , b , c , d , e , f ) , (1)
so that
B Q = ( 0 a b c − a 0 d e − b − d 0 f − c − e − f 0 ) . B_Q=\begin{pmatrix}
0 & a & b & c \\
-a & 0 & d & e \\
-b & -d & 0 & f \\
-c & -e & -f & 0
\end{pmatrix}. B Q = 0 − a − b − c a 0 − d − e b d 0 − f c e f 0 .
The coordinates of every six-tuple in this paper are in the fixed order 12 , 13 , 14 , 23 , 24 , 34 12,13,14,23,24,34 12 , 13 , 14 , 23 , 24 , 34 , unless a cyclic ordering is explicitly attached as a subscript. When a quiver is fixed in a calculation, we may suppress its argument and write b i j b_{ij} b ij . Six-entry parenthesized lists denote coordinate tuples; mutation words and cyclic orderings use different brackets, as specified below. We say a quiver is acyclic if it contains no directed cycles of any length.
The operation of interest is mutation at a vertex k k k . To mutate at vertex k k k , first add an arrow i → j i \to j i → j for every two-path i → k → j i \to k \to j i → k → j , counting multiplicities. Next, reverse all arrows touching k k k , and cancel pairs of arrows pointing in opposite directions. The resulting quiver is denoted μ k Q \mu_k Q μ k Q . In matrix form [35 ] , abbreviate b i j = b i j ( Q ) b_{ij}=b_{ij}(Q) b ij = b ij ( Q ) and b i j ′ = b i j ( μ k Q ) b'_{ij}=b_{ij}(\mu_k Q) b ij ′ = b ij ( μ k Q ) . Then
b i j ′ = { − b i j , i = k or j = k , b i j + [ b i k ] + [ b k j ] + − [ − b i k ] + [ − b k j ] + , i , j ≠ k , [ x ] + = max ( x , 0 ) . (2) b'_{ij}=
\begin{cases}
-b_{ij}, & i=k\text{ or }j=k,\\
b_{ij}+[b_{ik}]_+[b_{kj}]_+-[-b_{ik}]_+[-b_{kj}]_+, & i,j\ne k,
\end{cases}
\qquad[x]_+=\max(x,0). \tag*{(2)} b ij ′ = { − b ij , b ij + [ b ik ] + [ b k j ] + − [ − b ik ] + [ − b k j ] + , i = k or j = k , i , j = k , [ x ] + = max ( x , 0 ) . (2)
Mutation is an involution, and preserves the vertex sets of the connected components. A quiver is mutation-acyclic if a finite sequence of mutations takes it to an acyclic quiver; otherwise it is mutation-cyclic . If a quiver is acyclic, a topological ordering is a total order on its vertices such that every directed path of the quiver points from an earlier vertex to a later vertex. In other words, if there is a directed path i → j i \to j i → j in the quiver, then i < j i<j i < j in the topological ordering.
We write a mutation word as a bold letter w = [ k 1 , … , k r ] \mathbf{w}=[k_1,\ldots,k_r] w = [ k 1 , … , k r ] . The square brackets list the vertices in the order of mutation, from left to right:
μ w Q = μ k r ( ⋯ μ k 2 ( μ k 1 Q ) ⋯ ) . \mu_{\mathbf{w}}Q=\mu_{k_r}(\cdots\mu_{k_2}(\mu_{k_1}Q)\cdots). μ w Q = μ k r ( ⋯ μ k 2 ( μ k 1 Q ) ⋯ ) .
For example, μ [ 1 , 2 , 3 ] Q = μ 3 ( μ 2 ( μ 1 Q ) ) \mu_{[1,2,3]}Q=\mu_3(\mu_2(\mu_1Q)) μ [ 1 , 2 , 3 ] Q = μ 3 ( μ 2 ( μ 1 Q )) . The empty word is [ ] [\,] [ ] , and juxtaposition of words means concatenation in the order performed. A mutation sequence is reduced if consecutive mutation vertices differ; since mutation is an involution, mutations at the same vertex back-to-back cancel each other out.
The height of a quiver Q Q Q is
ht ( Q ) = max i < j ∣ b i j ( Q ) ∣ . \operatorname{ht}(Q)=\max_{i<j}|b_{ij}(Q)|. ht ( Q ) = i < j max ∣ b ij ( Q ) ∣.
A full subquiver of a quiver Q Q Q consists of a subset of vertices and all arrows between them. On the level of the exchange matrix, the full subquiver on a subset of vertices is obtained by taking the full submatrix on the rows and columns corresponding to the subset of vertices.
For a permutation π ∈ S n \pi\in S_n π ∈ S n , write Q π Q^\pi Q π for the relabeling defined by
b i j ( Q π ) = b π ( i ) π ( j ) ( Q ) . b_{ij}(Q^\pi)=b_{\pi(i)\pi(j)}(Q). b ij ( Q π ) = b π ( i ) π ( j ) ( Q ) .
Thus old vertex π ( i ) \pi(i) π ( i ) receives new label i i i . We write permutations in cycle notation, with spaces between successive vertices and no commas. The two relabelings used repeatedly in rank four are
π 12 = ( 1 2 ) , π 123 = ( 1 2 3 ) , \pi_{12}=(1\ 2), \qquad\pi_{123}=(1\ 2\ 3), π 12 = ( 1 2 ) , π 123 = ( 1 2 3 ) ,
with all unlisted vertices fixed. In particular, π 123 ( 1 ) = 2 \pi_{123}(1)=2 π 123 ( 1 ) = 2 , π 123 ( 2 ) = 3 \pi_{123}(2)=3 π 123 ( 2 ) = 3 , and π 123 ( 3 ) = 1 \pi_{123}(3)=1 π 123 ( 3 ) = 1 . Write Q o p Q^{\mathrm{op}} Q op for the quiver obtained by reversing all arrows, so that B Q o p = − B Q B_{Q^{\mathrm{op}}}=-B_Q B Q op = − B Q . Relabeling and reversal of all arrows preserve height and acyclicity. Both commute with mutation, in the following sense. For reversal, (2) gives μ k ( Q o p ) = ( μ k Q ) o p \mu_k(Q^{\mathrm{op}})=(\mu_kQ)^{\mathrm{op}} μ k ( Q op ) = ( μ k Q ) op directly. To transport a mutation through a relabeling, use
μ π − 1 ( k ) ( Q π ) = ( μ k Q ) π . (3) \mu_{\pi^{-1}(k)}(Q^\pi)=(\mu_kQ)^\pi. \tag*{(3)} μ π − 1 ( k ) ( Q π ) = ( μ k Q ) π . (3)
For a word w = [ k 1 , … , k r ] \mathbf{w}=[k_1,\ldots,k_r] w = [ k 1 , … , k r ] , let π − 1 w = [ π − 1 ( k 1 ) , … , π − 1 ( k r ) ] \pi^{-1}\mathbf{w}=[\pi^{-1}(k_1),\ldots,\pi^{-1}(k_r)] π − 1 w = [ π − 1 ( k 1 ) , … , π − 1 ( k r )] . Then μ π − 1 w ( Q π ) = ( μ w Q ) π \mu_{\pi^{-1}\mathbf{w}}(Q^\pi)=(\mu_{\mathbf{w}}Q)^\pi μ π − 1 w ( Q π ) = ( μ w Q ) π . Thus replacing an endpoint Q Q Q by Q π Q^\pi Q π requires replacing each later mutation vertex k k k by π − 1 ( k ) \pi^{-1}(k) π − 1 ( k ) ; all later heights and the acyclicity of the final quiver are preserved.
We now state some classical results of [4 Theorem 1.2] and [BMR08, Corollary 5.3], which we will use frequently enough to warrant restating here.
Proposition 2.1 ([4 Theorem 1.2] , [BMR08, Corollary 5.3]). A three-vertex quiver is mutation-cyclic if and only if it is an oriented triangle whose arrow multiplicities x , y , z x,y,z x , y , z satisfy
x , y , z ≥ 2 , x 2 + y 2 + z 2 − x y z ≤ 4. x,y,z \ge2,\qquad x^2+y^2+z^2-xyz\le4. x , y , z ≥ 2 , x 2 + y 2 + z 2 − x y z ≤ 4. The value x 2 + y 2 + z 2 − x y z x^2+y^2+z^2-xyz x 2 + y 2 + z 2 − x y z is called the Markov constant , and the expression defining it is the Markov polynomial . Also, every full subquiver of a mutation-acyclic quiver is mutation-acyclic. This implies that a quiver is mutation-cyclic if it contains a mutation-cyclic full subquiver.
We call a full subquiver on three vertices a full triangle , even when some of its three pairs of vertices are not joined. Finding a mutation-cyclic full triangle is a practical way to prove mutation-cyclicity for quivers of larger rank.
Cyclic orderings
We use the cyclic ordering framework of [26 ] throughout this paper. A cyclic ordering puts the vertices of a quiver around a circle. We write ω = ⟨ v 1 , … , v n ⟩ \omega=\langle v_1,\ldots,v_n\rangle ω = ⟨ v 1 , … , v n ⟩ , with angle brackets identifying lists that differ by cyclic rotation, but not by reversal. A linear ordering is written v 1 < ⋯ < v n v_1<\cdots<v_n v 1 < ⋯ < v n ; wrapping it around the circle gives ⟨ v 1 , … , v n ⟩ \langle v_1,\ldots,v_n\rangle ⟨ v 1 , … , v n ⟩ . A vertex k k k is proper if every directed path i → k → j i\to k\to j i → k → j encounters i , k , j i,k,j i , k , j in clockwise order according to the cyclic ordering. In other words, every two-path through k k k follows the circle clockwise. A wiggle swaps two neighboring vertices on the circle that are not joined by an arrow. Cyclic orderings related by wiggles are wiggle equivalent ; we denote the class of ω \omega ω by [ ω ] w i g [\omega]_{\mathrm{wig}} [ ω ] wig . A wiggle-equivalence class is itself proper if each vertex is proper in some ordering in the class.
To perform a proper mutation at k k k , first choose an ordering in which k k k is proper. Mutate the quiver and move k k k clockwise past its incoming neighbors in μ k Q \mu_kQ μ k Q (its outgoing neighbors in Q Q Q ), without passing its outgoing neighbors in μ k Q \mu_kQ μ k Q . The result is well defined up to wiggles. A class is totally proper if it remains proper after every sequence of proper mutations [26 Definition 14.1] .
Theorem 2.2 ([26 Observation 11.6, Theorem 14.3, and Conjecture 15.9] , [42 Theorem 1.1] ). A quiver of any rank has at most one totally proper wiggle-equivalence class. Every mutation-acyclic quiver has such a class. For an acyclic quiver, it is the class obtained by wrapping a topological ordering around the circle.
Remark 2.3. A practical consequence used throughout this paper is that if a quiver is known to be mutation-acyclic and has only one proper wiggle class, then that class is the totally proper one.
The Markov invariant
For a cyclic ordering ω = ⟨ v 1 , v 2 , v 3 , v 4 ⟩ \omega= \langle v_1, v_2, v_3, v_4\rangle ω = ⟨ v 1 , v 2 , v 3 , v 4 ⟩ , choose the displayed linear representative and read the exchange matrix in that order:
B ω ( Q ) = ( b v i v j ( Q ) ) i , j = 1 4 , b ω ( Q ) = ( b v 1 v 2 ( Q ) , b v 1 v 3 ( Q ) , b v 1 v 4 ( Q ) , b v 2 v 3 ( Q ) , b v 2 v 4 ( Q ) , b v 3 v 4 ( Q ) ) . B_\omega(Q) = \left(b_{v_i v_j}(Q)\right)_{i,j=1}^{4}, \qquad\mathbf{b}_\omega(Q) = \left(b_{v_1v_2}(Q), b_{v_1v_3}(Q), b_{v_1v_4}(Q), b_{v_2v_3}(Q), b_{v_2v_4}(Q), b_{v_3v_4}(Q)\right). B ω ( Q ) = ( b v i v j ( Q ) ) i , j = 1 4 , b ω ( Q ) = ( b v 1 v 2 ( Q ) , b v 1 v 3 ( Q ) , b v 1 v 4 ( Q ) , b v 2 v 3 ( Q ) , b v 2 v 4 ( Q ) , b v 3 v 4 ( Q ) ) .
The ordered matrix and tuple depend on the chosen linear representative; the Markov value below does not. Writing b ω ( Q ) = ( a , b , c , d , e , f ) \mathbf{b}_\omega(Q) = (a,b,c,d,e,f) b ω ( Q ) = ( a , b , c , d , e , f ) , define the Markov invariant by
M ω ( Q ) = a 2 + b 2 + c 2 + d 2 + e 2 + f 2 + a b d + a c e + b c f + d e f + a c d f . (4) M_\omega(Q) = a^2 + b^2 + c^2 + d^2 + e^2 + f^2 + abd + ace + bcf + def + acdf. \tag*{(4)} M ω ( Q ) = a 2 + b 2 + c 2 + d 2 + e 2 + f 2 + ab d + a ce + b c f + d e f + a c df . (4)
This is the Markov invariant M Q M_Q M Q of [26 Equation (8.2)] , computed for the linear ordering v 1 < v 2 < v 3 < v 4 v_1 < v_2 < v_3 < v_4 v 1 < v 2 < v 3 < v 4 , and its explicit form for four vertices is [26 Equation (9.6)] . To match the two notations, note that the unipotent companion of [26 Definition 4.2] has entries − b v i v j ( Q ) -b_{v_i v_j}(Q) − b v i v j ( Q ) above the diagonal, so the letters x , z , w , y , v , u x,z,w,y,v,u x , z , w , y , v , u of [26 Examples 4.15 and 9.3] are our ordered coordinates a , b , c , d , e , f a,b,c,d,e,f a , b , c , d , e , f , respectively. The invariant is unchanged by cyclic rotation of the ordering, by wiggles, and by proper mutations, by the invariance of the Alexander polynomial [26 Corollary 8.5] read through [26 Equation (8.2)] . For a mutation-acyclic quiver Q Q Q , the value of M M M on the totally proper class of Q Q Q is therefore an invariant of the mutation class of Q Q Q , and we denote it by m ( Q ) m(Q) m ( Q ) . Returning to the fixed-label tuple b ( Q ) = ( a , b , c , d , e , f ) \mathbf{b}(Q) = (a,b,c,d,e,f) b ( Q ) = ( a , b , c , d , e , f ) , the Pfaffian is
p ( Q ) = a f − b e + c d , det B Q = p ( Q ) 2 . (5) p(Q) = af - be + cd, \qquad\det B_Q = p(Q)^2. \tag*{(5)} p ( Q ) = a f − b e + c d , det B Q = p ( Q ) 2 . (5)
The factorization of matrix mutation in the proof of [7 Lemma 3.2] shows that mutation changes the sign of p ( Q ) p(Q) p ( Q ) , so ∣ p ( Q ) ∣ \lvert p(Q)\rvert ∣ p ( Q )∣ is mutation invariant, and hence so is det B Q \det B_Q det B Q [34 Theorem 2.8.4] . Relabeling gives p ( Q π ) = sgn ( π ) p ( Q ) p(Q^\pi) = \operatorname{sgn}(\pi)p(Q) p ( Q π ) = sgn ( π ) p ( Q ) and hence preserves p ( Q ) 2 p(Q)^2 p ( Q ) 2 , and reversing all arrows together with the cyclic ordering, which is passing to the opposite COQ of [26 Definition 12.1] , preserves M ω ( Q ) M_\omega(Q) M ω ( Q ) [26 Lemma 12.4 and (8.2)] .
An acyclic quiver has a cyclic ordering, induced by a topological ordering, in which all its entries are nonnegative. In that ordering the terms of the Markov invariant cannot cancel, so the Markov invariant bounds every arrow multiplicity of the acyclic quiver. Since m ( Q ) m(Q) m ( Q ) is a mutation invariant, it bounds the multiplicities of every acyclic quiver in the mutation class of Q Q Q , though not those of Q Q Q itself. The next lemma makes this precise.
Lemma 2.4. Suppose a four-vertex quiver Q Q Q is mutation-acyclic, and let m = m ( Q ) m = m(Q) m = m ( Q ) . If A A A is an acyclic quiver mutation equivalent to Q Q Q , then, for a topological ordering v 1 < ⋯ < v 4 v_1 < \cdots< v_4 v 1 < ⋯ < v 4 of A A A and ω A = ⟨ v 1 , … , v 4 ⟩ \omega_A = \langle v_1,\ldots,v_4\rangle ω A = ⟨ v 1 , … , v 4 ⟩ , the coordinates b ω A ( A ) = ( a , b , c , d , e , f ) \mathbf{b}_{\omega_A}(A) = (a,b,c,d,e,f) b ω A ( A ) = ( a , b , c , d , e , f ) satisfy
a , b , c , d , e , f ≥ 0 , a 2 + b 2 + c 2 + d 2 + e 2 + f 2 ≤ m , 2 ∣ p ( A ) ∣ ≤ m . (6) a,b,c,d,e,f \ge0,\qquad a^2+b^2+c^2+d^2+e^2+f^2 \le m,\qquad2\lvert p(A)\rvert\le m. \tag*{(6)} a , b , c , d , e , f ≥ 0 , a 2 + b 2 + c 2 + d 2 + e 2 + f 2 ≤ m , 2 ∣ p ( A )∣ ≤ m . (6) In particular, ht ( A ) ≤ ⌊ m ⌋ \operatorname{ht}(A) \le\lfloor\sqrt{m}\rfloor ht ( A ) ≤ ⌊ m ⌋ . If Q Q Q is connected, then m ≥ 3 m \ge3 m ≥ 3 and 2 ∣ p ( Q ) ∣ < m 2\lvert p(Q)\rvert< m 2 ∣ p ( Q )∣ < m .
The sum-of-squares bound in (6) is [42 Proposition 3.21] , and the bound m ≥ 3 m \ge3 m ≥ 3 is the case n = 4 n = 4 n = 4 of [42 Corollary 6.6] . The Pfaffian bounds are new. For four vertices, [42 Corollary 6.7] gives p ( Q ) 2 = det B Q ≤ ( 2 m ) 2 p(Q)^2 = \det B_Q \le(2m)^2 p ( Q ) 2 = det B Q ≤ ( 2 m ) 2 , which is ∣ p ( Q ) ∣ ≤ 2 m \lvert p(Q)\rvert\le2m ∣ p ( Q )∣ ≤ 2 m , so (6) improves it by a factor of four. We include the full proof because the strict inequality for connected quivers is used often in the appendices.
Proof. Transport the totally proper class along a mutation sequence from Q Q Q to A A A . By Theorem 2.2 , it becomes the class of a topological ordering of A A A with the same Markov invariant m m m , and all six upper-triangular entries in that ordering are nonnegative. Every term on the right of (4) is then nonnegative, which gives the sum-of-squares bound, and since each entry squared is at most this sum, ht ( A ) ≤ ⌊ m ⌋ \operatorname{ht}(A) \le\lfloor\sqrt{m}\rfloor ht ( A ) ≤ ⌊ m ⌋ . Moreover,
2 ∣ a f − b e + c d ∣ ≤ 2 ( a f + b e + c d ) ≤ a 2 + f 2 + b 2 + e 2 + c 2 + d 2 ≤ m , 2\lvert af - be + cd\rvert\le2(af + be + cd) \le a^2 + f^2 + b^2 + e^2 + c^2 + d^2 \le m, 2 ∣ a f − b e + c d ∣ ≤ 2 ( a f + b e + c d ) ≤ a 2 + f 2 + b 2 + e 2 + c 2 + d 2 ≤ m ,
where the second inequality follows from repeatedly applying 2 x y ≤ x 2 + y 2 2xy \le x^2 + y^2 2 x y ≤ x 2 + y 2 , which is true because ( x − y ) 2 ≥ 0 (x-y)^2 \ge0 ( x − y ) 2 ≥ 0 . Now suppose Q Q Q is connected. Mutation preserves connectedness, so A A A is connected, and in a connected quiver on four vertices at least three of the six pairs of vertices are joined. Hence at least three entries are positive integers and m ≥ 3 m \ge3 m ≥ 3 . Since ∣ p ( ⋅ ) ∣ |p(\cdot)| ∣ p ( ⋅ ) ∣ is invariant under mutation, ∣ p ( Q ) ∣ = ∣ p ( A ) ∣ |p(Q)| = |p(A)| ∣ p ( Q ) ∣ = ∣ p ( A ) ∣ , so it remains to show 2 ∣ p ( A ) ∣ < m 2|p(A)| < m 2∣ p ( A ) ∣ < m .
Suppose, for contradiction, that 2 ∣ p ( A ) ∣ = m 2|p(A)| = m 2∣ p ( A ) ∣ = m . Then every inequality above becomes an equality. Equality in the second step forces ( a − f ) 2 + ( b − e ) 2 + ( c − d ) 2 = 0 (a-f)^2+(b-e)^2+(c-d)^2=0 ( a − f ) 2 + ( b − e ) 2 + ( c − d ) 2 = 0 , so a = f a=f a = f , b = e b=e b = e , c = d c=d c = d . Equality in the triangle inequality gives b e = 0 be=0 b e = 0 or a f = c d = 0 af=cd=0 a f = c d = 0 . In the last step, this forces every cubic and quartic term of (4) to vanish; in particular the quartic term containing a c d f acdf a c df vanishes, so a a a , f f f , c c c , d d d cannot all be positive. This implies that at most one of the pairs ( a , f ) (a,f) ( a , f ) , ( b , e ) (b,e) ( b , e ) , ( c , d ) (c,d) ( c , d ) is nonzero. The underlying graph of A A A then has at most two edges, so A A A is disconnected, a contradiction. □ \square □
Remark 2.5. For each integer k ≥ 1 k \ge1 k ≥ 1 , let L k L_k L k be defined by b ( L k ) = ( k , 0 , 0 , 1 , 0 , k ) \mathbf{b}(L_k)=(k,0,0,1,0,k) b ( L k ) = ( k , 0 , 0 , 1 , 0 , k ) . This is the connected acyclic quiver 1 ⟶ 2 ⟶ 3 ⟶ 4 1 \mathbin{\longrightarrow} 2 \mathbin{\longrightarrow} 3 \mathbin{\longrightarrow} 4 1 ⟶ 2 ⟶ 3 ⟶ 4 , with topological ordering 1 < 2 < 3 < 4 1<2<3<4 1 < 2 < 3 < 4 and induced cyclic ordering ω = ⟨ 1 , 2 , 3 , 4 ⟩ \omega=\langle1,2,3,4\rangle ω = ⟨ 1 , 2 , 3 , 4 ⟩ . Direct substitution gives [S2.Lk-markov, S2.Lk-pf]
M ω ( L k ) = 2 k 2 + 1 , p ( L k ) = k 2 . M_{\omega}(L_k)=2k^2+1,\qquad p(L_k)=k^2. M ω ( L k ) = 2 k 2 + 1 , p ( L k ) = k 2 .
Consequently, M ω ( L k ) − 2 ∣ p ( L k ) ∣ = 1 M_{\omega}(L_k)-2|p(L_k)|=1 M ω ( L k ) − 2∣ p ( L k ) ∣ = 1 , the smallest possible positive integer gap in the strict inequality of Lemma 2.4 . Moreover,
M ω ( L k ) ∣ p ( L k ) ∣ = 2 + 1 k 2 ⟶ 2. \frac{M_{\omega}(L_k)}{|p(L_k)|}=2+\frac{1}{k^2}\longrightarrow2. ∣ p ( L k ) ∣ M ω ( L k ) = 2 + k 2 1 ⟶ 2.
Thus, for every constant c > 2 c>2 c > 2 , sufficiently large k k k satisfies M ω ( L k ) < c ∣ p ( L k ) ∣ M_{\omega}(L_k)<c|p(L_k)| M ω ( L k ) < c ∣ p ( L k ) ∣ . The coefficient 2 therefore cannot be increased uniformly, even when restricted to connected acyclic four-vertex quivers.
Lemma 2.4 gives a finite obstruction test, which we name for later use. We say that a connected four-vertex quiver Q Q Q is Markov-excluded if it has at least one proper wiggle class, and for every proper wiggle class [ ω ] w i g [\omega]_{\mathrm{wig}} [ ω ] wig no connected acyclic four-vertex quiver A A A , with cyclic ordering ω A \omega_A ω A induced by a topological ordering, has both M ω A ( A ) = M ω ( Q ) M_{\omega_A}(A)=M_{\omega}(Q) M ω A ( A ) = M ω ( Q ) and p ( A ) 2 = p ( Q ) 2 p(A)^2=p(Q)^2 p ( A ) 2 = p ( Q ) 2 .
Lemma 2.6. Let Q Q Q be a connected four-vertex quiver. If Q Q Q has no proper wiggle class, or if Q Q Q is Markov-excluded, then Q Q Q is mutation-cyclic. Whether Q Q Q is Markov-excluded can be decided by a finite computation. For four-vertex quivers, having no proper wiggle class is equivalent to being a vortex, by [26 Proposition 13.2] . The resulting obstruction to mutation-acyclicity is stated separately in Lemma 2.7 below.
Proof. If Q Q Q were mutation-acyclic, Theorem 2.2 would give a totally proper class [ ω ] w i g [\omega]_{\mathrm{wig}} [ ω ] wig , and Lemma 2.4 would give an acyclic quiver A A A in the class of Q Q Q with M ω A ( A ) = M ω ( Q ) M_{\omega_A}(A)=M_{\omega}(Q) M ω A ( A ) = M ω ( Q ) , where ω A \omega_A ω A is induced by a topological ordering. Also, p ( A ) 2 = p ( Q ) 2 p(A)^2=p(Q)^2 p ( A ) 2 = p ( Q ) 2 by (5) , and A A A is connected because mutation preserves components. Both hypotheses rule this possibility out. For the finiteness, put m = M ω ( Q ) m=M_{\omega}(Q) m = M ω ( Q ) for a proper class [ ω ] w i g [\omega]_{\mathrm{wig}} [ ω ] wig . By (6) every candidate tuple b ω A ( A ) \mathbf{b}_{\omega_A}(A) b ω A ( A ) is nonnegative with sum of squares at most m m m , so there are finitely many to check, and none if m < 3 m<3 m < 3 . □ \square □
A match in the exclusion test does not prove mutation-acyclicity. Neville uses the same exclusion idea in [42 Section 6] . A vortex is a complete four-vertex quiver consisting of an oriented triangle and a fourth vertex that is a source or a sink [26 Definition 13.1] . Fomin and Neville show that a four-vertex quiver has a proper cyclic ordering if and only if it is not a vortex [26 Proposition 13.2] . A vortex is complete, so each of its wiggle classes consists of a single cyclic ordering, and having no proper cyclic ordering is the same as having no proper wiggle class. A quiver that is not a vortex has a proper cyclic ordering, whose wiggle class is proper. This proves the equivalence stated in Lemma 2.6.
Lemma 2.7 ([26 Proposition 13.2] ). A vortex has no proper wiggle class. Hence, by Theorem 2.2, every vortex is mutation-cyclic.
The following fact holds in every rank and is used twice below.
Lemma 2.8 ([CK06, Corollary 4 and its proof]). Let A A A and B B B be mutation-equivalent acyclic quivers of the same rank. Then B B B can be reached from A A A , up to relabeling of vertices, by a sequence of mutations at sources and sinks. Consequently A A A and B B B have the same underlying weighted graph up to relabeling, and a mutation class contains only finitely many acyclic quivers.
Caldero and Keller show that the seeds with acyclic exchange matrix form a connected subgraph of the exchange graph [CK06, Corollary 4], and the statement about sources and sinks is in its proof; for acyclic seeds see also [11 ] . A mutation between two acyclic quivers is necessarily at a source or a sink. Indeed, if a vertex k k k of an acyclic quiver is neither a source nor a sink, there is a path i → k → j i \to k \to j i → k → j . There can be no arrow j → i j \to i j → i , since that would already give a directed cycle. Mutation at k k k therefore leaves a positive number of arrows i → j i \to j i → j , together with the reversed arrows j → k → i j \to k \to i j → k → i , producing a directed triangle.
An alternating family
For t ∈ Z t \in\mathbb{Z} t ∈ Z , let
b ( Q ( t ) ) = ( − 2 , t + 2 , t , − t , 2 − t , 0 ) = ( − 2 , 2 , 0 , 0 , 2 , 0 ) + t ( 0 , 1 , 1 , − 1 , − 1 , 0 ) , (7) \mathbf{b}(Q(t)) = (-2,t+2,t,-t,2-t,0) = (-2,2,0,0,2,0) + t(0,1,1,-1,-1,0), \tag*{(7)} b ( Q ( t )) = ( − 2 , t + 2 , t , − t , 2 − t , 0 ) = ( − 2 , 2 , 0 , 0 , 2 , 0 ) + t ( 0 , 1 , 1 , − 1 , − 1 , 0 ) , (7)
where negative labels in the following diagram mean reversed arrows and zero labels mean omitted arrows:
Figure 1.
Each Q ( t ) Q(t) Q ( t ) is connected, since the edge between vertex 1 and 2 is always present, vertex 3 is joined to 1 unless t = − 2 t=-2 t = − 2 and to 2 unless t = 0 t=0 t = 0 , and vertex 4 is joined to 1 unless t = 0 t=0 t = 0 and to 2 unless t = 2 t=2 t = 2 .
Lemma 3.1. For t ≥ 2 t \ge2 t ≥ 2 , mutating Q ( t ) Q(t) Q ( t ) at vertex 2 gives Q ( t − 2 ) π 12 Q(t-2)^{\pi_{12}} Q ( t − 2 ) π 12 .
Proof. Mutation at 2 gives [S3.recurrence]
b ( μ 2 Q ( t ) ) = ( 2 , 2 − t , 4 − t , t , t − 2 , 0 ) . \mathbf{b}(\mu_2Q(t)) = (2,2-t,4-t,t,t-2,0). b ( μ 2 Q ( t )) = ( 2 , 2 − t , 4 − t , t , t − 2 , 0 ) .
Swapping the first two labels gives
b ( ( μ 2 Q ( t ) ) π 12 ) = ( − 2 , t , t − 2 , 2 − t , 4 − t , 0 ) = b ( Q ( t − 2 ) ) . \mathbf{b}\left((\mu_2Q(t))^{\pi_{12}}\right) = (-2,t,t-2,2-t,4-t,0) = \mathbf{b}(Q(t-2)). b ( ( μ 2 Q ( t ) ) π 12 ) = ( − 2 , t , t − 2 , 2 − t , 4 − t , 0 ) = b ( Q ( t − 2 )) .
Theorem 3.2. The four-vertex quiver Q ( t ) Q(t) Q ( t ) is mutation-acyclic if and only if t < 0 t < 0 t < 0 or t t t is even.
Proof. For t < 0 t < 0 t < 0 , vertex 2 is a source and there is no arrow between vertices 3 and 4. Hence Q ( t ) Q(t) Q ( t ) is acyclic; for t ≤ − 3 t \le-3 t ≤ − 3 this is [S3.Qneg], and examples.py checks t = − 2 , − 1 t=-2,-1 t = − 2 , − 1 .
For t ≥ 0 t \ge0 t ≥ 0 , repeatedly apply Lemma 3.1. Each step subtracts two from t t t after relabeling, which preserves mutation-acyclicity. So we only need to understand Q ( 0 ) Q(0) Q ( 0 ) and Q ( 1 ) Q(1) Q ( 1 ) .
The even endpoint Q ( 0 ) Q(0) Q ( 0 ) , with b ( Q ( 0 ) ) = ( − 2 , 2 , 0 , 0 , 2 , 0 ) \mathbf{b}(Q(0))=(-2,2,0,0,2,0) b ( Q ( 0 )) = ( − 2 , 2 , 0 , 0 , 2 , 0 ) , is acyclic. For the odd endpoint, one mutation gives
b ( μ 2 Q ( 1 ) ) = ( 2 , 1 , 1 , 1 , − 1 , 1 ) . \mathbf{b}(\mu_2Q(1)) = (2,1,1,1,-1,1). b ( μ 2 Q ( 1 )) = ( 2 , 1 , 1 , 1 , − 1 , 1 ) . Here vertex 1 is a source, while 2 → 3 → 4 → 2 2 \to3 \to4 \to2 2 → 3 → 4 → 2 is a directed triangle. Every pair of vertices is joined, so this is a vortex. Lemma 2.7 proves that Q ( 1 ) Q(1) Q ( 1 ) is therefore mutation-cyclic.
Remark 3.3. For every t ≥ 0 t \ge0 t ≥ 0 , the quiver Q ( t ) Q(t) Q ( t ) has exactly one proper wiggle class, and its Markov value is 12. For t ≥ 3 t \ge3 t ≥ 3 this class contains ⟨ 1 , 3 , 4 , 2 ⟩ \langle1,3,4,2\rangle ⟨ 1 , 3 , 4 , 2 ⟩ [S3.Qt-class, S3.Qt-markov], and for t ≤ 2 t \le2 t ≤ 2 it is a direct check. Also p ( Q ( t ) ) = − 4 p(Q(t))=-4 p ( Q ( t )) = − 4 for every t t t [S3.Qt-pf]. The connected acyclic quiver Q ( 0 ) Q(0) Q ( 0 ) has the same pair ( M , p 2 ) = ( 12 , 16 ) (M,p^2)=(12,16) ( M , p 2 ) = ( 12 , 16 ) in its topological ordering. Hence no Q ( t ) Q(t) Q ( t ) is Markov-excluded, and the even and odd members of the family are not distinguished by the Markov invariant, by the determinant, or by properness. The odd members become detectable after mutation. By Lemma 3.1 , s s s mutations take Q ( 2 s + 1 ) Q(2s+1) Q ( 2 s + 1 ) to a relabeling of Q ( 1 ) Q(1) Q ( 1 ) , and one more mutation gives a vortex.
Remark 3.4. For n > 4 n>4 n > 4 , build Q n ( t ) Q_n(t) Q n ( t ) from Q ( t ) Q(t) Q ( t ) by adding the vertices 5 , … , n 5,\ldots,n 5 , … , n and the arrows
n ⟶ n − 1 ⟶ ⋯ ⟶ 5 ⟶ 3 n \longrightarrow n-1 \longrightarrow\cdots\longrightarrow5 \longrightarrow3 n ⟶ n − 1 ⟶ ⋯ ⟶ 5 ⟶ 3
with the convention that for n = 5 n=5 n = 5 the only added arrow is 5 → 3 5\to3 5 → 3 . In particular, no arrow 4 → 3 4\to3 4 → 3 is added, and the full subquiver on { 1 , 2 , 3 , 4 } \{1,2,3,4\} { 1 , 2 , 3 , 4 } is Q ( t ) Q(t) Q ( t ) . The resulting quiver is connected. None of the added vertices is adjacent to vertex 2, so mutation at 2 leaves all the added arrows unchanged, as does the swap of labels 1, 2. Consequently, the recurrence of Lemma 3.1 sends Q n ( t ) Q_n(t) Q n ( t ) to Q n ( t − 2 ) Q_n(t-2) Q n ( t − 2 ) for t ≥ 2 t\ge2 t ≥ 2 .
For t < 0 t<0 t < 0 , the original quiver is acyclic, and attaching a chain at a single vertex creates no directed cycle. The same argument applies to the even endpoint Q n ( 0 ) Q_n(0) Q n ( 0 ) . For the odd endpoint, the full subquiver on { 1 , 2 , 3 , 4 } \{1,2,3,4\} { 1 , 2 , 3 , 4 } is the mutation-cyclic quiver Q ( 1 ) Q(1) Q ( 1 ) , so Proposition 2.1 rules out mutation-acyclicity of Q n ( 1 ) Q_n(1) Q n ( 1 ) . It follows that Q n ( t ) Q_n(t) Q n ( t ) is mutation-acyclic exactly when t < 0 t<0 t < 0 or t t t is even. We also write Q 4 ( t ) = Q ( t ) Q_4(t)=Q(t) Q 4 ( t ) = Q ( t ) .
Polynomial sign tests
We now prove Theorem 1.2 . The point is that finitely many polynomial tests eventually see no change along the family, whereas mutation-acyclicity continues to alternate.
Proof of Theorem 1.2. Fix n ≥ 4 n\ge4 n ≥ 4 , and suppose for contradiction that such a rule exists for quivers on n n n vertices. Move all terms of each polynomial equation/inequality to one side, so that it has the form P = 0 P=0 P = 0 , P > 0 P>0 P > 0 , or P < 0 P<0 P < 0 for some polynomial P P P . Because the rule is fixed and finite, there are finitely many polynomials
P 1 , … , P r ∈ R [ b i j : 1 ≤ i < j ≤ n ] P_1,\ldots,P_r\in\mathbb{R}[b_{ij}:1\le i<j\le n] P 1 , … , P r ∈ R [ b ij : 1 ≤ i < j ≤ n ]
whose zero values and signs determine its answer. Combining these tests with the Boolean operations and, or, and not uses no information beyond this finite list of signs. If there are no tests, the rule is constant and already cannot distinguish the even and odd members of the family.
Now apply the rule only to the connected integral quivers Q n ( t ) Q_n(t) Q n ( t ) of Remark 3.4, for t = 0 , 1 , 2 , … t=0,1,2,\ldots t = 0 , 1 , 2 , … . For each ℓ \ell ℓ , the value tested by the rule is
q ℓ ( t ) : = P ℓ ( B Q n ( t ) ) . q_\ell(t):=P_\ell(B_{Q_n(t)}). q ℓ ( t ) := P ℓ ( B Q n ( t ) ) .
Every entry of B Q n ( t ) B_{Q_n(t)} B Q n ( t ) is an affine function of t t t , since the entries of Q ( t ) Q(t) Q ( t ) are affine in t t t by (7) and the added entries are constant. So q ℓ q_\ell q ℓ is an ordinary one-variable real polynomial. There are exactly two possibilities:
If q ℓ q_\ell q ℓ is the zero polynomial, then q ℓ ( t ) = 0 q_\ell(t)=0 q ℓ ( t ) = 0 for every t t t . Its sign is always zero, so all tests involving P ℓ P_\ell P ℓ have constant answers on the family.
If q ℓ q_\ell q ℓ is not the zero polynomial, it has only finitely many real roots. Choose a real number R ℓ R_\ell R ℓ larger than all of them, taking R ℓ = 0 R_\ell=0 R ℓ = 0 if there are none. The polynomial never vanishes on the interval ( R ℓ , ∞ ) (R_\ell,\infty) ( R ℓ , ∞ ) . It is either positive everywhere on that interval or negative everywhere there. Otherwise continuity and the intermediate value theorem would give another root between two points of opposite signs. Thus its sign, and every test involving P ℓ P_\ell P ℓ , is constant for t > R ℓ t>R_\ell t > R ℓ .
Since there are only finitely many ℓ \ell ℓ , we can choose a single integer N ≥ 2 N\ge2 N ≥ 2 larger than every R ℓ R_\ell R ℓ needed in case (ii). For all integers t ≥ N t\ge N t ≥ N , the entire sign vector
( sgn q 1 ( t ) , … , sgn q r ( t ) ) (\operatorname{sgn} q_1(t),\ldots,\operatorname{sgn} q_r(t)) ( sgn q 1 ( t ) , … , sgn q r ( t ))
is constant. In particular, every individual test has the same truth value on every such Q n ( t ) Q_n(t) Q n ( t ) with t ≥ N t \ge N t ≥ N . Applying the same fixed Boolean combination to the same truth values must give the same final answer.
Choose an even integer 2 s > N 2s > N 2 s > N . The proposed rule therefore gives the same answer on Q n ( 2 s ) Q_n(2s) Q n ( 2 s ) and Q n ( 2 s + 1 ) Q_n(2s+1) Q n ( 2 s + 1 ) . But Theorem 3.2 and Remark 3.4 say that Q n ( 2 s ) Q_n(2s) Q n ( 2 s ) is mutation-acyclic and Q n ( 2 s + 1 ) Q_n(2s+1) Q n ( 2 s + 1 ) is mutation-cyclic. The rule must be wrong on at least one of these two connected integral quivers. This contradicts its assumed correctness on every input, proving the theorem. □ \square □
Remark 3.5. Equivalently, for each n ≥ 4 n \ge4 n ≥ 4 , no semialgebraic subset of R ( n 2 ) \mathbb{R}^{\binom{n}{2}} R ( 2 n ) agrees with mutation-acyclicity on all integral n n n -vertex quivers. This assertion concerns the integral points; no notion of mutation-acyclicity for real weights is needed. It also rules out fixed finite piecewise-polynomial rules with semialgebraic branches, and rational sign tests after denominator signs and zero denominators are accounted for.
Arithmetic tests are a different story. For example, the greatest common divisor of the entries of the exchange matrix is a mutation invariant [34 Section 2.8] , and more generally, for skew-symmetric matrices mutation is an integral congruence, so the whole Smith normal form is invariant [13 Section 1] . For the family Q ( t ) Q(t) Q ( t ) the greatest common divisor equals gcd ( 2 , t ) \operatorname{gcd}(2,t) gcd ( 2 , t ) , which distinguishes positive even and positive odd parameters. Finer arithmetic invariants include the binary invariant of Casals [13 ] and the congruence invariants of Seven and Ünal [47 ] . The theorem does not exclude such tests, or the finite decision algorithm proved below.
Corollary 3.6. There is no uniform bound on the length of a shortest mutation sequence from a mutation-acyclic four-vertex quiver to an acyclic quiver.
Proof. By Lemma 3.1 , the distinct quivers Q ( 2 s ) Q(2s) Q ( 2 s ) , s ≥ 0 s \ge0 s ≥ 0 , lie in the mutation class of Q ( 0 ) Q(0) Q ( 0 ) up to relabeling. By Lemma 2.8 , that class contains only finitely many acyclic quivers, and there are finitely many relabelings. From finitely many endpoints, at most L L L mutations can reach only finitely many quivers, because at each step there are only four mutation vertices to choose from. Reversing these paths shows that a fixed length bound L L L cannot cover the infinitely many distinct quivers Q ( 2 s ) Q(2s) Q ( 2 s ) . □ \square □
Remark 3.7. Corollary 3.6 holds for connected integral quivers of every rank n ≥ 4 n \ge4 n ≥ 4 , with the same proof applied to the family Q n ( t ) Q_n(t) Q n ( t ) of Remark 3.4, since Lemma 2.8 supplies the finiteness of acyclic representatives in every rank. The results that follow, by contrast, use the four-vertex Markov invariant (4) in an essential way, and therefore apply to rank four only.
Local replacements along mutation sequences
This section sets up the technical input for the height bound of Theorem 5.1 . The guiding idea is that whenever a mutation sequence climbs above a certain height level and later comes back down, the stretch spent above that level (a “high segment,” defined below) can be rerouted below it. The three lemmas here justify this locally by following how the first two mutation vertices of the high segment are joined. With no edge between them the two mutations commute; with one arrow the pentagon relation supplies detours; with at least two arrows an attempted detour is forced to keep growing. These three regimes mirror the behavior of ice quivers with exactly two mutable vertices. Soukup shows that the mutation class of such an ice quiver has at most four quivers when the two mutable vertices are not joined and at most ten when they are joined by a single arrow, while in any nontrivial case the arrow multiplicities grow without bound when they are joined by two or more arrows [45 Theorem 1.3] . Here the additional task is to control the height along a mutation sequence (what we will call a route ) and the possibility of mutating at a third vertex. The proofs are case analyses, given in Appendices § 7 and § 8 , and every calculation in them is verified by the program check_proofs.py.
The setup and supporting lemmas
Throughout this section and Appendices A and B, fix a connected mutation-acyclic four-vertex quiver Q ∗ Q_* Q ∗ , let m = m ( Q ∗ ) m=m(Q_*) m = m ( Q ∗ ) , fix an integer T ≥ m T\ge m T ≥ m , and put F = T + 1 F=T+1 F = T + 1 . All quivers considered below are mutation-equivalent to Q ∗ Q_* Q ∗ . Call a quiver low if its height is at most T T T and high if its height is exactly F F F . The routes we choose stay within height F F F , so each quiver on them is low or high; quivers of larger height appear only as intermediate quivers of alternative routes that we compare. A high segment is a maximal run of consecutive high quivers on a route. If it is preceded and followed by low quivers, its associated excursion word starts with the mutation from the low predecessor to the first high quiver and ends with the mutation from the last high quiver to the low successor. Thus a segment containing r r r high quivers has an excursion word of length r + 1 r+1 r + 1 . When we describe the mutation vertices or replace the word of a high segment, we always mean this excursion word.
Lemma 4.1. Let R R R be mutation-equivalent to Q ∗ Q_* Q ∗ , and let p = p ( R ) p=p(R) p = p ( R ) . Then
3 ≤ m ≤ T , 2 ∣ p ∣ < m . (8) 3\le m\le T,\qquad2\lvert p\rvert<m. \tag*{(8)} 3 ≤ m ≤ T , 2 ∣ p ∣ < m . (8) In particular T ≥ 3 T\ge3 T ≥ 3 and F ≥ 4 F\ge4 F ≥ 4 . These bounds are unchanged by relabeling R R R and by reversing all arrows of R R R (together with its cyclic ordering).
Proof. By Theorem 2.2, the totally proper class of R R R is obtained by transporting that of Q ∗ Q_* Q ∗ along a mutation sequence, so its Markov invariant is m ( R ) = m ( Q ∗ ) = m m(R)=m(Q_*)=m m ( R ) = m ( Q ∗ ) = m . Lemma 2.4 applied to the connected quiver Q ∗ Q_* Q ∗ gives m ≥ 3 m\ge3 m ≥ 3 and 2 ∣ p ( Q ∗ ) ∣ < m 2\lvert p(Q_*)\rvert<m 2 ∣ p ( Q ∗ )∣ < m , and ∣ p ( R ) ∣ = ∣ p ( Q ∗ ) ∣ \lvert p(R)\rvert=\lvert p(Q_*)\rvert ∣ p ( R )∣ = ∣ p ( Q ∗ )∣ because ∣ p ∣ \lvert p\rvert ∣ p ∣ is mutation invariant. The bound m ≤ T m\le T m ≤ T holds by the choice of T T T . The invariance statements were noted after equation (5) . □
These bounds always refer to the totally proper class, and a different proper cyclic ordering need not give the same value. Much of the work in the appendices consists of identifying that class.
We also record two elementary tools. First, for integers 1 ≤ r , s ≤ F − 1 1\le r,s\le F-1 1 ≤ r , s ≤ F − 1 ,
r 2 + s 2 − F r s ≤ 2 − F . (9) r^2+s^2-Frs\le2-F. \tag*{(9)} r 2 + s 2 − F r s ≤ 2 − F . (9)
Indeed, the left side is convex in each variable, so its maximum on the rectangle occurs at a corner. The corners ( 1 , 1 ) (1,1) ( 1 , 1 ) , ( 1 , F − 1 ) (1,F-1) ( 1 , F − 1 ) and ( F − 1 , 1 ) (F-1,1) ( F − 1 , 1 ) give 2 − F 2-F 2 − F ; the corner ( F − 1 , F − 1 ) (F-1,F-1) ( F − 1 , F − 1 ) gives ( 2 − F ) ( F − 1 ) 2 ≤ 2 − F (2-F)(F-1)^2\le2-F ( 2 − F ) ( F − 1 ) 2 ≤ 2 − F [A0.rect].
Second, if the edge between vertices 1 and 2 of a quiver has multiplicity one, the type-A 2 A_2 A 2 pentagon relation [35 ] , in the form for extended exchange matrices with arbitrary additional rows [[FWZ24, Example 3.2.4], gives
μ [ 1 , 2 , 1 , 2 , 1 ] Q = Q π 12 . (10) \mu_{[1,2,1,2,1]}Q=Q^{\pi_{12}}. \tag*{(10)} μ [ 1 , 2 , 1 , 2 , 1 ] Q = Q π 12 . (10)
It holds regardless of the signs of the other entries. To compute the intermediate quivers, apply the mutation formula (2) to columns 3 and 4; the b 34 b_{34} b 34 entry then follows from p ( μ k Q ) = − p ( Q ) p(\mu_kQ)=-p(Q) p ( μ k Q ) = − p ( Q ) and the b 12 b_{12} b 12 entry, which is 1 or − 1 -1 − 1 .
The three local lemmas
In Lemmas 4.2 and 4.5, P P P is a high quiver mutation-equivalent to Q ∗ Q_* Q ∗ , and i ≠ j i\ne j i = j are vertices with
ht ( μ i P ) ≤ T , ht ( μ j P ) ≤ F . \operatorname{ht}(\mu_iP)\le T,\qquad\operatorname{ht}(\mu_jP)\le F. ht ( μ i P ) ≤ T , ht ( μ j P ) ≤ F .
This is the situation at the start of a high segment, where μ i P \mu_iP μ i P is the low quiver the route came from and j j j is the next mutation vertex.
Lemma 4.2 (No arrow). Suppose there is no edge between i i i and j j j in P P P . Then a reduced sequence starting at P P P with j j j , staying within height F F F , and stopping at its first low quiver is either w = [ j ] \mathbf{w}=[j] w = [ j ] or w = [ j , i ] \mathbf{w}=[j,i] w = [ j , i ] . Moreover, if R R R is a low quiver with no edge between i , j i,j i , j , then every low quiver obtained from R R R using only mutations at i i i and j j j can be reached from R R R by at most two such mutations with every intermediate quiver low.
Since i , j i,j i , j are not joined, mutations at i i i and j j j commute, and the only entry either of these can push above T T T is the one between the other two vertices. The lemma implies that the commuting square never needs to pass through a high corner. The two routes in this square have the same labeled endpoint:
R → μ i μ i R μ j R → μ i μ [ i , j ] R R ↓ μ j μ i R ↓ μ j \begin{aligned}
R &\xrightarrow{\mu_i} \mu_iR \\
\mu_jR &\xrightarrow{\mu_i} \mu_{[i,j]}R
\end{aligned}
\qquad
\begin{aligned}
R &\downarrow{\mu_j} \\
\mu_iR &\downarrow{\mu_j}
\end{aligned} R μ j R μ i μ i R μ i μ [ i , j ] R R μ i R ↓ μ j ↓ μ j
Remark 4.3. The first assertion of Lemma 4.2 does not extend verbatim to five-vertex quivers. For a five-vertex quiver Q Q Q write
b ( Q ) = ( b 12 , b 13 , b 14 , b 15 , b 23 , b 24 , b 25 , b 34 , b 35 , b 45 ) , \mathbf{b}(Q)=(b_{12},b_{13},b_{14},b_{15},b_{23},b_{24},b_{25},b_{34},b_{35},b_{45}), b ( Q ) = ( b 12 , b 13 , b 14 , b 15 , b 23 , b 24 , b 25 , b 34 , b 35 , b 45 ) ,
and let m ( Q ) m(Q) m ( Q ) be the value on the totally proper class of the Fomin–Neville invariant M = 5 − tr ( U − T U ) M=5-\operatorname{tr}(U^{-T}U) M = 5 − tr ( U − T U ) [26 Equation (8.2)] , where U U U is the unipotent upper triangular matrix with U i j = − b i j U_{ij}=-b_{ij} U ij = − b ij for i < j i<j i < j . On four vertices, 4 − tr ( U − T U ) 4-\operatorname{tr}(U^{-T}U) 4 − tr ( U − T U ) is the invariant (4) .
Consider the connected quiver C C C with b ( C ) = ( 1 , − 3 , 0 , 3 , 0 , 0 , 2 , 0 , − 15 , 2 ) \mathbf{b}(C)=(1,-3,0,3,0,0,2,0,-15,2) b ( C ) = ( 1 , − 3 , 0 , 3 , 0 , 0 , 2 , 0 , − 15 , 2 ) . Then b ( μ [ 1 , 4 , 2 ] C ) = ( 1 , 0 , 0 , − 3 , 3 , 0 , − 2 , 0 , 0 , − 2 ) \mathbf{b}(\mu_{[1,4,2]}C)=(1,0,0,-3,3,0,-2,0,0,-2) b ( μ [ 1 , 4 , 2 ] C ) = ( 1 , 0 , 0 , − 3 , 3 , 0 , − 2 , 0 , 0 , − 2 ) , which is acyclic with topological ordering 5 < 1 < 2 < 3 < 4 5<1<2<3<4 5 < 1 < 2 < 3 < 4 and Markov value 33 33 33 . So C C C is mutation-acyclic and m ( C ) = 33 m(C)=33 m ( C ) = 33 . Take T = 41 T=41 T = 41 , F = 42 F=42 F = 42 , and P = μ 3 C P=\mu_3C P = μ 3 C . The heights of C C C and of the quivers along [ 3 , 4 , 2 ] [3,4,2] [ 3 , 4 , 2 ] are 15 , 42 , 42 , 40 15,42,42,40 15 , 42 , 42 , 40 . Moreover b 34 ( P ) = 0 b_{34}(P)=0 b 34 ( P ) = 0 , ht ( μ 3 P ) = 15 ≤ T \operatorname{ht}(\mu_3P)=15\le T ht ( μ 3 P ) = 15 ≤ T and ht ( μ 4 P ) = F \operatorname{ht}(\mu_4P)=F ht ( μ 4 P ) = F . The reduced continuation [ 4 , 2 ] [4,2] [ 4 , 2 ] from P P P therefore reaches its first low quiver within height F F F , although it is neither [ 4 ] [4] [ 4 ] nor [ 4 , 3 ] [4,3] [ 4 , 3 ] .
The excursion still has a low replacement. The vertices 2 , 3 , 4 2,3,4 2 , 3 , 4 are pairwise nonadjacent in C C C , so their mutations commute, and μ [ 3 , 4 , 2 ] C = μ [ 2 , 3 , 4 ] C \mu_{[3,4,2]}C=\mu_{[2,3,4]}C μ [ 3 , 4 , 2 ] C = μ [ 2 , 3 , 4 ] C . The heights along the replacement are 15 , 15 , 40 , 40 15,15,40,40 15 , 15 , 40 , 40 .
Lemma 4.4 (A single arrow). Let K ≥ 0 K\ge0 K ≥ 0 be an integer, and let C C C be a quiver mutation-equivalent to Q ∗ Q_\ast Q ∗ with exactly one arrow between i i i and j j j . Suppose that C C C and a quiver R R R obtained from C C C by mutations at i i i and j j j both have height at most K K K . Then a sequence of at most three mutations at i , j i,j i , j reaches R R R , possibly with i , j i,j i , j swapped, and every quiver along it has height at most K K K .
Here the pentagon relation (10) gives a ten-quiver picture, and any endpoint can be reached by two routes. This lemma says at least one of them stays within height K K K . For example, if R = μ [ 1 , 2 ] C R=\mu_{[1,2]}C R = μ [ 1 , 2 ] C , the two routes to the same endpoint up to π 12 \pi_{12} π 12 are
C → μ 1 μ 1 C → μ 2 R ↓ μ 2 μ 2 C → μ 1 μ [ 2 , 1 ] C → μ 2 R π 12 . \begin{aligned}
C &\xrightarrow{\mu_1} \mu_1C \xrightarrow{\mu_2} R \\
\downarrow{\mu_2} && \\
\mu_2C &\xrightarrow{\mu_1} \mu_{[2,1]}C \xrightarrow{\mu_2} R^{\pi_{12}}.
\end{aligned} C ↓ μ 2 μ 2 C μ 1 μ 1 C μ 2 R μ 1 μ [ 2 , 1 ] C μ 2 R π 12 .
The direct route has length two and the detour has length three, and the lemma controls their intermediate heights.
Lemma 4.5 (Multiplicity at least two). Suppose the edge between i i i and j j j in P P P has multiplicity at least two. Then no reduced sequence starting at P P P with j j j can reach a low quiver while staying within height F F F .
Here a double arrow makes the entries grow. After the mutation at j j j , every mutation other than at i i i exceeds height F F F , and alternating at i , j i,j i , j never lowers the entry that is already F F F .
Remark 4.6. Lemma 4.5 also fails for five-vertex quivers. With the conventions of Remark 4.3, consider the connected quiver C C C with b ( C ) = ( 1 , − 2 , 0 , 0 , 2 , − 1 , 0 , 0 , 6 , − 4 ) \mathbf{b}(C)=(1,-2,0,0,2,-1,0,0,6,-4) b ( C ) = ( 1 , − 2 , 0 , 0 , 2 , − 1 , 0 , 0 , 6 , − 4 ) . Then b ( μ [ 2 , 4 , 3 ] C ) = \mathbf{b}(\mu_{[2,4,3]}C)= b ( μ [ 2 , 4 , 3 ] C ) = ( − 1 , 0 , 0 , 0 , 0 , − 1 , 0 , − 2 , 2 , 0 ) (-1, 0, 0, 0, 0, -1, 0, -2, 2, 0) ( − 1 , 0 , 0 , 0 , 0 , − 1 , 0 , − 2 , 2 , 0 ) , which is acyclic with topological ordering 4 < 2 < 1 < 3 < 5 4 < 2 < 1 < 3 < 5 4 < 2 < 1 < 3 < 5 and Markov value 10 10 10 . So C C C is mutation-acyclic and m ( C ) = 10 m(C) = 10 m ( C ) = 10 . Take T = 11 T = 11 T = 11 , F = 12 F = 12 F = 12 , and P = μ 3 C P = \mu_3 C P = μ 3 C . Then
b ( P ) = ( − 3 , 2 , 0 , 0 , − 2 , − 1 , 12 , 0 , − 6 , − 4 ) , \mathbf{b}(P) = (-3, 2, 0, 0, -2, -1, 12, 0, -6, -4), b ( P ) = ( − 3 , 2 , 0 , 0 , − 2 , − 1 , 12 , 0 , − 6 , − 4 ) ,
b ( μ 1 P ) = ( 3 , − 2 , 0 , 0 , 4 , − 1 , 12 , 0 , − 6 , − 4 ) , \mathbf{b}(\mu_1P) = (3, -2, 0, 0, 4, -1, 12, 0, -6, -4), b ( μ 1 P ) = ( 3 , − 2 , 0 , 0 , 4 , − 1 , 12 , 0 , − 6 , − 4 ) ,
b ( μ [ 1 , 4 ] P ) = ( 3 , − 2 , 0 , 0 , 4 , 1 , 8 , 0 , − 6 , 4 ) . \mathbf{b}(\mu_{[1,4]}P) = (3, -2, 0, 0, 4, 1, 8, 0, -6, 4). b ( μ [ 1 , 4 ] P ) = ( 3 , − 2 , 0 , 0 , 4 , 1 , 8 , 0 , − 6 , 4 ) .
Thus ∣ b 13 ( P ) ∣ = 2 |b_{13}(P)| = 2 ∣ b 13 ( P ) ∣ = 2 , ht ( μ 3 P ) = ht ( C ) = 6 ≤ T \operatorname{ht}(\mu_3P) = \operatorname{ht}(C) = 6 \le T ht ( μ 3 P ) = ht ( C ) = 6 ≤ T and ht ( μ 1 P ) = F \operatorname{ht}(\mu_1P) = F ht ( μ 1 P ) = F , but the reduced continuation [ 1 , 4 ] [1,4] [ 1 , 4 ] reaches a quiver of height 8 ≤ T 8 \le T 8 ≤ T within height F F F .
Again the excursion has a low replacement. Vertex 4 4 4 is joined to neither 1 1 1 nor 3 3 3 in C C C , so its mutation commutes with both, and μ [ 3 , 1 , 4 ] C = μ [ 4 , 3 , 1 ] C \mu_{[3,1,4]}C = \mu_{[4,3,1]}C μ [ 3 , 1 , 4 ] C = μ [ 4 , 3 , 1 ] C . The heights along the two words are 6 , 12 , 12 , 8 6, 12, 12, 8 6 , 12 , 12 , 8 and 6 , 6 , 8 , 8 6, 6, 8, 8 6 , 6 , 8 , 8 . So the arguments behind Lemmas 4.2 and 4.5 would need further normalization in rank five, although in both examples the excursion can still be lowered.
High segments across a single arrow
When the first two mutation vertices of a high segment are joined by a single arrow, Lemma 4.4 alone does not suffice, because the segment may use a third vertex. The following proposition classifies the remaining cases for a minimizing route, defined next. The restriction to minimizing routes is essential, as Remark 4.8 shows.
For a finite route R = ( R 0 , … , R L ) \mathcal{R} = (R_0, \ldots, R_L) R = ( R 0 , … , R L ) , let
F ( R ) = max 0 ≤ j ≤ L ht ( R j ) , N ( R ) = # { j : ht ( R j ) = F ( R ) } . F(\mathcal{R}) = \max_{0 \le j \le L} \operatorname{ht}(R_j), \qquad N(\mathcal{R}) = \#\{j : \operatorname{ht}(R_j) = F(\mathcal{R})\}. F ( R ) = 0 ≤ j ≤ L max ht ( R j ) , N ( R ) = # { j : ht ( R j ) = F ( R )} .
We call R \mathcal{R} R minimizing if, among all mutation routes from its fixed starting quiver to any acyclic quiver, it minimizes lexicographically
( F ( R ) , N ( R ) , L ) . (11) \bigl(F(\mathcal{R}), N(\mathcal{R}), L\bigr). \tag*{(11)} ( F ( R ) , N ( R ) , L ) . (11)
In other words, first minimize the maximum height, then the number of visits at that height, and finally the length. Such a route exists whenever the starting quiver is mutation-acyclic, since each quantity is a nonnegative integer. The last minimum makes the route reduced. Relabeling the entire route or reversing every arrow preserves these three quantities and gives a bijection with routes from the transformed starting quiver, so it also preserves minimality.
The quivers defined by
b ( A c ) = ( 1 , − 2 , c , 1 , 0 , F − 2 c ) , b ( I t , u ) = ( 1 , − 1 , − t , 2 , t − F , F − u ) , 1 ≤ c , t , u ≤ T , (12) \mathbf{b}(A_c) = (1, -2, c, 1, 0, F - 2c), \qquad\mathbf{b}(I_{t,u}) = (1, -1, -t, 2, t - F, F - u), \qquad1 \le c,t,u \le T, \tag*{(12)} b ( A c ) = ( 1 , − 2 , c , 1 , 0 , F − 2 c ) , b ( I t , u ) = ( 1 , − 1 , − t , 2 , t − F , F − u ) , 1 ≤ c , t , u ≤ T , (12)
are the only possible low predecessors when a high segment of a minimizing route uses a third mutation vertex, and each admits an explicit low detour.
Proposition 4.7. Let R \mathcal{R} R be a minimizing mutation route from Q ∗ Q_* Q ∗ to an acyclic quiver in the sense of (11), and suppose its maximum height is F F F . Consider a high segment of R \mathcal{R} R , preceded by a low quiver C C C and followed by a low quiver. Suppose exactly one arrow joins the first two mutation vertices of the segment. Relabel so that these vertices are 1 1 1 and 2 2 2 , in that order, and reverse all arrows if necessary so that b 12 ( C ) = 1 b_{12}(C) = 1 b 12 ( C ) = 1 . Then one of the following holds.
(a) The segment mutates only at 1 1 1 and 2 2 2 . Then a sequence of at most three mutations at 1 , 2 1,2 1 , 2 , all of whose quivers are low, reaches the same low endpoint, possibly relabeled by the swap of 1 , 2 1,2 1 , 2 .
(b) The segment mutates at a third vertex, which we relabel $3$. Then the segment begins with exactly w = [ 1 , 2 ] \mathbf{w} = [1,2] w = [ 1 , 2 ] before its first mutation at 3 3 3 , the quiver C C C is A c A_c A c for some 1 ≤ c ≤ T 1 \le c \le T 1 ≤ c ≤ T or I t , u I_{t,u} I t , u for some $1 \le t \ne u \le T$, and the segment is replaced as follows:
Table 3.
In each row the segment column is the excursion word from C C C through the entire high segment to its first low successor, and every quiver on the replacement is low.
Part (a) is Lemma 4.4 with K = T K = T K = T . The rest is proved in Appendix B. Appendix B.1 shows that the alternating prefix at 1, 2 is exactly w = [ 1 , 2 ] \mathbf{w} = [1,2] w = [ 1 , 2 ] , Appendices B.2.1–B.2.3 run through the signs of the entries of C C C to isolate A c A_c A c and I t , u I_{t,u} I t , u , and Appendix B.3 verifies the replacements and excludes t = u t = u t = u .
Remark 4.8. The minimizing-route hypothesis in Proposition 4.7 cannot be replaced by reducedness alone. Take the connected acyclic quiver
b ( Q ∗ ) = ( 1 , 1 , − 1 , 1 , 0 , 0 ) , m ( Q ∗ ) = T = 5 , F = 6. \mathbf{b}(Q_*) = (1,1,-1,1,0,0), \qquad m(Q_*) = T = 5, \qquad F = 6. b ( Q ∗ ) = ( 1 , 1 , − 1 , 1 , 0 , 0 ) , m ( Q ∗ ) = T = 5 , F = 6.
The word w = [ 2 , 3 , 1 , 3 , 1 , 3 , 1 , 3 ] \mathbf{w} = [2,3,1,3,1,3,1,3] w = [ 2 , 3 , 1 , 3 , 1 , 3 , 1 , 3 ] reaches the quiver C C C with b ( C ) = ( 1 , − 2 , 5 , 1 , − 1 , − 4 ) \mathbf{b}(C) = (1,-2,5,1,-1,-4) b ( C ) = ( 1 , − 2 , 5 , 1 , − 1 , − 4 ) , with successive heights 2, 2, 2, 2, 2, 3, 4, 5. Starting at this low quiver C C C , the following reduced excursion remains within height six. In the row for v \mathbf{v} v , each entry column gives b i j ( μ v C ) b_{ij}(\mu_{\mathbf{v}}C) b ij ( μ v C ) :
Table 1.
After the return to height five, the word [ 1 , 2 , 1 , 2 , 3 ] [1,2,1,2,3] [ 1 , 2 , 1 , 2 , 3 ] reaches the acyclic quiver ( 1 , 1 , 0 , − 1 , 1 , 0 ) (1,1,0,-1,1,0) ( 1 , 1 , 0 , − 1 , 1 , 0 ) , with successive heights 4, 3, 2, 2, 1. Thus the full word
w = [ 2 , 3 , 1 , 3 , 1 , 3 , 1 , 3 ] [ 1 , 2 , 1 , 3 , 2 ] [ 1 , 2 , 1 , 2 , 3 ] \mathbf{w} = [2,3,1,3,1,3,1,3]\ [1,2,1,3,2]\ [1,2,1,2,3] w = [ 2 , 3 , 1 , 3 , 1 , 3 , 1 , 3 ] [ 1 , 2 , 1 , 3 , 2 ] [ 1 , 2 , 1 , 2 , 3 ]
is reduced, starts at Q ∗ Q_* Q ∗ , ends at an acyclic quiver, and has maximum height six. The first two excursion vertices are 1, 2, with b 12 ( C ) = 1 b_{12}(C) = 1 b 12 ( C ) = 1 , but the first mutation at a third vertex occurs after the prefix [ 1 , 2 , 1 ] [1,2,1] [ 1 , 2 , 1 ] rather than [ 1 , 2 ] [1,2] [ 1 , 2 ] . Moreover, C C C is neither A c A_c A c nor I t , u I_{t,u} I t , u in this labeling. This contradicts the conclusion of Proposition 4.7 if its minimality hypothesis is omitted. The route here is not minimizing since its starting quiver is already acyclic. In Appendix B.1, minimality is exactly what allows longer alternating prefixes to be replaced before the sign cases are classified. These claims are checked by examples.py.
A height bound and decision algorithms
A height bound on mutation sequences
Theorem 5.1. Let Q Q Q be a mutation-acyclic four-vertex quiver. Then some mutation sequence takes Q Q Q to an acyclic quiver with every intermediate arrow multiplicity at most max { ht ( Q ) , m ( Q ) } \max\{\operatorname{ht}(Q),m(Q)\} max { ht ( Q ) , m ( Q )} .
Proof. If Q Q Q is disconnected, every component has at most three vertices, and components with at most two vertices are acyclic. A non-acyclic three-vertex component is an oriented triangle, and the descent of [1 Section 2.5] mutates it at the vertex opposite a largest multiplicity until it becomes acyclic. If the multiplicities are x ≤ y ≤ z x \le y \le z x ≤ y ≤ z , such a mutation keeps x , y x,y x , y and replaces z z z by ∣ x y − z ∣ |xy-z| ∣ x y − z ∣ , and the result is acyclic if x y ≤ z xy \le z x y ≤ z . We claim that x y < 2 z xy < 2z x y < 2 z whenever x ≥ 2 x \ge2 x ≥ 2 . Otherwise y ≤ z ≤ x y / 2 y \le z \le xy/2 y ≤ z ≤ x y /2 , and since z 2 − x y z z^2 - xyz z 2 − x y z decreases for z ≤ x y / 2 z \le xy/2 z ≤ x y /2 , the Markov constant satisfies
x 2 + y 2 + z 2 − x y z ≤ x 2 + 2 y 2 − x y 2 = x 2 + ( 2 − x ) y 2 ≤ 4. x^2 + y^2 + z^2 - xyz \le x^2 + 2y^2 - xy^2 = x^2 + (2-x)y^2 \le4. x 2 + y 2 + z 2 − x y z ≤ x 2 + 2 y 2 − x y 2 = x 2 + ( 2 − x ) y 2 ≤ 4.
using y ≥ x ≥ 2 y \ge x \ge2 y ≥ x ≥ 2 ; by Proposition 2.1 the component would be mutation-cyclic. If x ≤ 1 x \le1 x ≤ 1 , then x y ≤ z xy \le z x y ≤ z . So the replaced multiplicity never increases, and while the component remains an oriented triangle the sum of its multiplicities strictly decreases, so the descent terminates. Apply these componentwise sequences independently, obtaining a route of height at most ht ( Q ) \operatorname{ht}(Q) ht ( Q ) . We can therefore assume Q Q Q is connected.
Choose a minimizing route R \mathcal{R} R in the sense of (11) , and let F F F be its maximum height. Suppose, for a contradiction, that F > max { ht ( Q ) , m ( Q ) } F > \max\{\operatorname{ht}(Q),m(Q)\} F > max { ht ( Q ) , m ( Q )} , and put T = F − 1 T=F-1 T = F − 1 . Then T ≥ m ( Q ) T \ge m(Q) T ≥ m ( Q ) , so we are in the setup of § 4 with Q ∗ = Q Q^{*}=Q Q ∗ = Q . We will replace one high excursion by a low route. If this lowers the maximum height, it contradicts the first minimum in (11) , and if the maximum remains F F F , the replacement decreases the number of visits at height F F F and contradicts the second minimum.
The starting quiver is low, since ht ( Q ) ≤ T \operatorname{ht}(Q) \le T ht ( Q ) ≤ T . The ending quiver is also low, since Lemma 2.4 bounds its height by ⌊ m ( Q ) ⌋ ≤ m ( Q ) ≤ T \lfloor\sqrt{m(Q)}\rfloor\le m(Q) \le T ⌊ m ( Q ) ⌋ ≤ m ( Q ) ≤ T . So the route contains a high segment, preceded by a low quiver C C C and followed by a low quiver. Let i i i be the mutation producing the first high quiver P = μ i C P=\mu_i C P = μ i C , and j ≠ i j\ne i j = i the next mutation vertex. Then ht ( μ i P ) = ht ( C ) ≤ T \operatorname{ht}(\mu_iP)=\operatorname{ht}(C)\le T ht ( μ i P ) = ht ( C ) ≤ T and ht ( μ j P ) ≤ F \operatorname{ht}(\mu_jP)\le F ht ( μ j P ) ≤ F , so the lemmas of § 4 apply to P P P , i i i , j j j . We distinguish by the edge between i i i and j j j in P P P (its multiplicity is the same in C C C ).
Multiplicity at least two. Lemma 4.5 says the route cannot return to a low quiver within height F F F . But it does return. This case cannot occur.
No edge. By the first part of Lemma 4.2 , the whole segment together with its return is i j ij ij or i j i iji ij i , so the low endpoint is reached from C C C using only i , j i,j i , j . By the second part, the same labeled endpoint is reached from C C C by at most two mutations with every quiver low. Replacing the segment removes its high quivers without changing anything later.
Multiplicity one. Relabel i , j i,j i , j as 1 , 2 1,2 1 , 2 and reverse all arrows if necessary, so that b 12 ( C ) = 1 b_{12}(C)=1 b 12 ( C ) = 1 ; by Lemma 4.1 and the remarks before it, this changes neither the heights along the route nor the bounds (8). The route remains minimizing after these transformations, so Proposition 4.7, including its minimality hypothesis, gives a replacement for the segment in every case. In case (a) it is a low route of at most three mutations, and in case (b) it is one of the three listed detours, all of whose quivers are low. Each replacement ends at the old endpoint up to a stated relabeling π \pi π . Relabel every later mutation vertex k k k as π − 1 ( k ) \pi^{-1}(k) π − 1 ( k ) ; by (3) every later quiver is relabeled by π \pi π , so all later heights and the acyclicity of the final quiver are preserved.
In the second and third cases the modified route either has maximum height less than F F F , or still has maximum F F F and has strictly fewer visits at that height. This contradicts the first or second minimum in (11) , respectively. Hence F ≤ max { ht ( Q ) , m ( Q ) } F\le\max\{\operatorname{ht}(Q),m(Q)\} F ≤ max { ht ( Q ) , m ( Q )} .
The proof uses the bound T ≥ m ( Q ) T\ge m(Q) T ≥ m ( Q ) only through Lemma 4.1 and to make the last quiver of the route low, and the bound T ≥ ht ( Q ) T\ge\operatorname{ht}(Q) T ≥ ht ( Q ) only to make the first quiver low.
A finite decision algorithm
For a four-vertex quiver Q Q Q with at least one proper wiggle class, put
H ( Q ) = max { ht ( Q ) ∪ { M ω ( Q ) : [ ω ] w i g a proper wiggle class of Q } } . (13) H(Q)=\max\left\{\operatorname{ht}(Q)\cup\{M_{\omega}(Q): [\omega]_{\mathrm{wig}}\text{ a proper wiggle class of }Q\}\right\}. \tag*{(13)} H ( Q ) = max { ht ( Q ) ∪ { M ω ( Q ) : [ ω ] wig a proper wiggle class of Q } } . (13)
There are six cyclic orderings to examine, written as ⟨ 1 , v 2 , v 3 , v 4 ⟩ \langle1,v_2,v_3,v_4\rangle ⟨ 1 , v 2 , v 3 , v 4 ⟩ , where ( v 2 , v 3 , v 4 ) (v_2,v_3,v_4) ( v 2 , v 3 , v 4 ) ranges over the permutations of ( 2 , 3 , 4 ) (2,3,4) ( 2 , 3 , 4 ) .
Corollary 5.2. Let Q Q Q be a four-vertex quiver. If Q Q Q has no proper wiggle class, it is mutation-cyclic. Otherwise, Q Q Q is mutation-acyclic if and only if a sequence of mutations through quivers of height at most H ( Q ) H(Q) H ( Q ) takes Q Q Q to an acyclic quiver, and such a sequence can be chosen of length at most ( 2 H ( Q ) + 1 ) 6 − 1 (2H(Q)+1)^6-1 ( 2 H ( Q ) + 1 ) 6 − 1 . In particular, mutation-acyclicity of four-vertex quivers is decidable by a finite search.
Proof. If Q Q Q has no proper wiggle class, it is mutation-cyclic by Theorem 2.2 , since a totally proper class is proper. If Q Q Q is mutation-acyclic, its totally proper class is one of its proper classes, so m ( Q ) ≤ H ( Q ) m(Q)\le H(Q) m ( Q ) ≤ H ( Q ) , and Theorem 5.1 gives a sequence to an acyclic quiver within height H ( Q ) H(Q) H ( Q ) . There are ( 2 H ( Q ) + 1 ) 6 (2H(Q)+1)^6 ( 2 H ( Q ) + 1 ) 6 labeled integer quivers of height at most H ( Q ) H(Q) H ( Q ) . Starting at Q Q Q , search its connected component in the mutation graph restricted to these quivers. Record each quiver once and test it for acyclicity. If an acyclic quiver is found, the recorded mutation sequence proves mutation-acyclicity. If the component is exhausted, Theorem 5.1 proves that Q Q Q is mutation-cyclic. The search examines at most four mutations at each recorded quiver. A shortest path cannot repeat a quiver, giving the length bound. □
The search can be implemented as follows, storing a predecessor and a mutation vertex for each newly found quiver.
If Q Q Q has no proper wiggle class, return mutation-cyclic . Otherwise compute H = H ( Q ) H = H(Q) H = H ( Q ) , initialize a queue with Q Q Q , and mark Q Q Q as visited.
If the queue is empty, return mutation-cyclic . Otherwise remove its next quiver R R R .
If R R R is acyclic, return mutation-acyclic together with the path reconstructed from the predecessor records.
For each vertex v ∈ { 1 , 2 , 3 , 4 } v \in\{1,2,3,4\} v ∈ { 1 , 2 , 3 , 4 } , compute S = μ v R S = \mu_v R S = μ v R . If ht ( S ) ≤ H \operatorname{ht}(S) \le H ht ( S ) ≤ H and S S S has not been visited, mark it, store its predecessor R R R and mutation vertex v v v , and add it to the queue. Return to step 2.
The negative answer in step 2 is returned only after the entire reachable component within the fixed height bound has been exhausted. Theorem 5.1 is what makes a negative answer conclusive. In practice, one can first test acyclicity, mutation-cyclic full triangles, vortices, and the exclusions of Lemma 2.6 , and can process disconnected components separately. Caching acyclic endpoint signatures ( M , p 2 ) (M,p^2) ( M , p 2 ) and quotienting states by relabeling can further reduce repeated work; to recover a labeled mutation word, book-keep the relabeling used at each step. The function decide in quiver4.py implements this procedure.
The size of the search space
Corollary 5.3. If a four-vertex quiver Q Q Q with a proper wiggle class has height h h h , then
H ( Q ) ≤ h 4 + 4 h 3 + 6 h 2 . H(Q) \le h^4 + 4h^3 + 6h^2. H ( Q ) ≤ h 4 + 4 h 3 + 6 h 2 . For h ≥ 1 h \ge1 h ≥ 1 , the decision search of Corollary 5.2 has O ( h 24 ) O(h^{24}) O ( h 24 ) states and can be implemented in a time polynomial in h h h . This is a pseudo-polynomial bound, since it is polynomial in the numerical arrow multiplicities, but may be exponential in the number of bits used to write them. When h = 0 h = 0 h = 0 , the quiver is already acyclic.
Proof. In every cyclic ordering, the six entries have absolute value at most h h h . Formula (4) has six quadratic terms, four cubic terms and one quartic term. The triangle inequality therefore gives
∣ M ω ( Q ) ∣ ≤ 6 h 2 + 4 h 3 + h 4 . \lvert M_\omega(Q)\rvert\le6h^2 + 4h^3 + h^4. ∣ M ω ( Q )∣ ≤ 6 h 2 + 4 h 3 + h 4 .
For integer h ≥ 1 h \ge1 h ≥ 1 , the right side also bounds h h h , so it bounds H ( Q ) H(Q) H ( Q ) . Corollary 5.2 now gives at most
( 2 ( h 4 + 4 h 3 + 6 h 2 ) + 1 ) 6 = O ( h 24 ) (2(h^4 + 4h^3 + 6h^2) + 1)^6 = O(h^{24}) ( 2 ( h 4 + 4 h 3 + 6 h 2 ) + 1 ) 6 = O ( h 24 )
states. If h = 0 h = 0 h = 0 , all entries and all Markov values vanish, so H ( Q ) = 0 H(Q) = 0 H ( Q ) = 0 and there is just one state. For the running time, each state requires at most four mutations and an acyclicity test. A tested mutation has entries of magnitude at most H ( Q ) + H ( Q ) 2 H(Q) + H(Q)^2 H ( Q ) + H ( Q ) 2 , even if it is discarded for exceeding the bound. Thus all arithmetic uses integers with O ( log ( h + 1 ) ) O(\log(h+1)) O ( log ( h + 1 )) bits when h ≥ 1 h \ge1 h ≥ 1 . Store the visited six-tuples in a balanced search tree. A lookup then takes O ( log N ) O(\log N) O ( log N ) comparisons for N N N states, and each comparison takes O ( log ( h + 1 ) ) O(\log(h+1)) O ( log ( h + 1 )) bit operations. Since N = O ( h 24 ) N = O(h^{24}) N = O ( h 24 ) , lookup and exact arithmetic take time polynomial in log ( h + 1 ) \log(h+1) log ( h + 1 ) per state. Thus, with basic integer arithmetic and balanced-tree storage, one obtains O ( h 24 log 2 ( h + 1 ) ) O(h^{24}\log^2(h+1)) O ( h 24 log 2 ( h + 1 )) bit operations and O ( h 24 log ( h + 1 ) ) O(h^{24}\log(h+1)) O ( h 24 log ( h + 1 )) bits of storage, including the queue and predecessor records. In particular, the running time is polynomial in h h h , as claimed. □
An example and a conjecture
The search of Corollary 5.2 can also prove mutation-cyclicity when the obstructions of § 2 do not apply within the search range.
Example 5.4. Let b ( Q ) = ( − 3 , − 2 , 2 , 0 , 3 , − 3 ) \mathbf{b}(Q)=(-3,-2,2,0,3,-3) b ( Q ) = ( − 3 , − 2 , 2 , 0 , 3 , − 3 ) , a connected quiver of height three. It has a single proper wiggle class, with Markov value 41, and p ( Q ) 2 = 225 p(Q)^2=225 p ( Q ) 2 = 225 , so H ( Q ) = 41 H(Q)=41 H ( Q ) = 41 . The pair ( 41 , 225 ) (41,225) ( 41 , 225 ) is realized by the connected acyclic quiver ( 0 , 0 , 3 , 5 , 1 , 1 ) (0,0,3,5,1,1) ( 0 , 0 , 3 , 5 , 1 , 1 ) in its topological ordering 1 < 2 < 3 < 4 1<2<3<4 1 < 2 < 3 < 4 , so Q Q Q is not Markov-excluded. The component of Q Q Q in the mutation graph restricted to quivers of height at most 41 consists of 238 quivers, none of which is acyclic, so Q Q Q is mutation-cyclic by Corollary 5.2 . None of these 238 quivers contains a mutation-cyclic full triangle, is a vortex, or is Markov-excluded, so within this range the obstructions of § 2 do not detect Q Q Q . The mutation class of Q Q Q contains oriented four-cycles such as ( 3 , − 2 , 0 , 0 , 9 , − 1 ) (3,-2,0,0,9,-1) ( 3 , − 2 , 0 , 0 , 9 , − 1 ) , with multiplicities 3, 9, 1, 2 around the cycle. These claims are checked by examples.py.
We do not know whether the term m ( Q ) m(Q) m ( Q ) in Theorem 5.1 is needed.
Conjecture 5.5. Every mutation-acyclic four-vertex quiver Q Q Q admits a mutation sequence to an acyclic quiver along which every arrow multiplicity is at most ht ( Q ) \operatorname{ht}(Q) ht ( Q ) .
If Conjecture 5.5 holds, the search of Corollary 5.2 can be run with the bound ht ( Q ) \operatorname{ht}(Q) ht ( Q ) in place of H ( Q ) H(Q) H ( Q ) , and it has at most ( 2 h + 1 ) 6 = O ( h 6 ) (2h+1)^6=O(h^6) ( 2 h + 1 ) 6 = O ( h 6 ) states for input height h ≥ 1 h\ge1 h ≥ 1 . The program conjecture_evidence.py gives the following evidence.
For every connected four-vertex quiver Q Q Q of height at most three, either a search within height ht ( Q ) \operatorname{ht}(Q) ht ( Q ) reaches an acyclic quiver, or Q Q Q is mutation-cyclic. There are 34, 633 and 4276 such quivers of heights one, two and three up to relabeling. The mutation-cyclic ones are certified by a mutation-cyclic full triangle, a vortex or a Markov exclusion within three mutations, except for the dreaded torus at height two and four quivers at height three, which are certified by Corollary 5.2 . Up to relabeling and reversal of all arrows, these four quivers are mutation-equivalent to the quiver of Example 5.4.
Starting from each connected acyclic quiver with entries in { 0 , 1 , 2 } \{0,1,2\} { 0 , 1 , 2 } , we computed every quiver reachable through quivers of height at most 10, a total of 94,344 quivers in 320 regions, and checked that each of them reaches an acyclic quiver inside its region without exceeding its own height.
The same holds for 2000 random mutation-acyclic quivers of heights between 6 and 60, obtained by random mutation sequences from acyclic quivers.
Conjecture 5.5 holds for every mutation class that contains an acyclic quiver with at least two arrows between every pair of vertices. Following [31 Definition 3.4] , call a mutation decreasing if it lowers the multiplicity of some arrow and raises none. By [31 Corollary 3.5 and Remark 3.6] , every quiver in such a class reaches an acyclic quiver by finitely many decreasing mutations. No multiplicity increases along this sequence, so it never exceeds ht ( Q ) \operatorname{ht}(Q) ht ( Q ) .
Remark 5.6. The method of Theorem 5.1 does not prove Conjecture 5.5, because the local analysis of § 4 uses m ≤ T m\le T m ≤ T , and m ( Q ) m(Q) m ( Q ) can be much larger than ht ( Q ) \operatorname{ht}(Q) ht ( Q ) . For x ≥ 1 x\ge1 x ≥ 1 , the quiver G x G_x G x with b ( G x ) = ( x , x , 0 , x + 1 , − x , 1 ) \mathbf{b}(G_x)=(x,x,0,x+1,-x,1) b ( G x ) = ( x , x , 0 , x + 1 , − x , 1 ) is acyclic with topological ordering 1 < 2 < 4 < 3 1<2<4<3 1 < 2 < 4 < 3 and m ( G x ) = x 3 + 4 x 2 + x + 2 m(G_x)=x^3+4x^2+x+2 m ( G x ) = x 3 + 4 x 2 + x + 2 [S5.Gx–acyclic, S5.Gx–markov], while b ( μ 4 G x ) = ( x , x , 0 , x + 1 , − x , 1 ) \mathbf{b}(\mu_4G_x)=(x,x,0,x+1,-x,1) b ( μ 4 G x ) = ( x , x , 0 , x + 1 , − x , 1 ) has height x + 1 x+1 x + 1 [S5.Gx–mu4]. Thus the height grows linearly along this family of mutation-acyclic quivers, while m m m grows cubically. For acyclic quivers m m m can even be of order ht ( Q ) 4 \operatorname{ht}(Q)^4 ht ( Q ) 4 , since the acyclic quiver with all six entries equal to h h h in a topological ordering has m = h 4 + 4 h 3 + 6 h 2 m=h^4+4h^3+6h^2 m = h 4 + 4 h 3 + 6 h 2 .
Comparing mutation classes
Corollary 5.7. Mutation equivalence up to vertex relabeling is decidable for pairs of integral four-vertex quivers of which at least one is mutation-acyclic. More precisely, there is an algorithm that, given two four-vertex quivers, either decides whether they are mutation equivalent up to relabeling, or reports that both are mutation-cyclic.
Proof. Apply Corollary 5.2 to both inputs. If both are mutation-cyclic, report this. If exactly one is mutation-acyclic, they cannot be mutation equivalent. Otherwise both are mutation-acyclic, and the searches give acyclic representatives A A A , B B B . The original inputs are mutation equivalent up to relabeling exactly when A A A , B B B are.
By Lemma 2.8 , if A A A and B B B are mutation equivalent up to relabeling, then B B B is reached from A A A , up to relabeling, by mutations at sources and sinks, which only reorient the underlying weighted graph of A A A . That graph has at most six edges, hence at most 2 6 = 64 2^6 = 64 2 6 = 64 orientations. Starting at A A A , search all orientations reachable by source or sink mutations. At each one, compare with the 24 relabelings of B B B . Finding a match proves equivalence; exhausting this finite search without a match disproves it. □
If both inputs are mutation-cyclic, this argument provides no decision method for their mutation equivalence. The reduction to acyclic representatives in the second paragraph works in every rank, so only the decision procedure of the first paragraph is specific to rank four.
The bounded classification
Theorem 2.9 of [3 ] claims that a four-vertex quiver with arrow multiplicities at most two is mutation-cyclic exactly when its mutation class contains a mutation-cyclic full triangle, or the quiver is the dreaded torus Q T Q_{\mathrm{T}} Q T with b ( Q T ) = ( − 2 , 1 , 1 , − 1 , − 1 , − 1 ) \mathbf{b}(Q_{\mathrm{T}}) = (-2,1,1,-1,-1,-1) b ( Q T ) = ( − 2 , 1 , 1 , − 1 , − 1 , − 1 ) . The double-arrow box disproves this criterion. The computation in that paper already included the box as a mutation-cyclic seed. Indeed, the proof of [3 Theorem 2.9] lists the box and the dreaded torus as special cases, and arrives at the same counts 534 and 133 for connected quivers as Theorem 6.2 below. So the issue is the stated criterion rather than the reported class counts. Disconnected quivers were not considered in [3 ] , so the second row of the table in Theorem 6.2 is new. We give a corrected criterion with short certificates and recover those counts.
Proposition 6.1. The double-arrow box
b ( Q □ ) = ( − 2 , 0 , 2 , − 2 , 0 , − 2 ) \mathbf{b}(Q_{\square}) = (-2,0,2,-2,0,-2) b ( Q □ ) = ( − 2 , 0 , 2 , − 2 , 0 , − 2 ) is mutation-cyclic. It is not isomorphic to the dreaded torus, and every full triangle in every quiver in its mutation class is mutation-acyclic.
Proof. The quiver μ 1 Q □ \mu_1 Q_{\square} μ 1 Q □ , with b ( μ 1 Q □ ) = ( 2 , 0 , − 2 , − 2 , 4 , − 2 ) \mathbf{b}(\mu_1 Q_{\square}) = (2,0,-2,-2,4,-2) b ( μ 1 Q □ ) = ( 2 , 0 , − 2 , − 2 , 4 , − 2 ) , is connected and has a single proper wiggle class, in which M = 0 < 3 M = 0 < 3 M = 0 < 3 . By Lemma 2.4 , no connected acyclic quiver has Markov value 0 in a topological ordering, so μ 1 Q □ \mu_1 Q_{\square} μ 1 Q □ is Markov-excluded, and Q □ Q_{\square} Q □ is mutation-cyclic by Lemma 2.6 . The box is the oriented four-cycle 1 → 4 → 3 → 2 → 1 1 \to4 \to3 \to2 \to1 1 → 4 → 3 → 2 → 1 with all multiplicities two, the case a = b = 2 a = b = 2 a = b = 2 of the four-cycles with multiplicities a , b , a , b a,b,a,b a , b , a , b shown to be mutation-cyclic in [War14, Example 6.11]; see also [42 Example 6.10] . The name is from [3 ] . The assertion about all full triangles is [Frv24, discussion after Corollary 5.5]. The box has four underlying edges and the dreaded torus has six, so they are not isomorphic. □
Theorem 6.2 (Correction of [3 Theorem 2.9] ). Let Q Q Q be a four-vertex quiver of height at most two.
(i) Q Q Q is mutation-acyclic if and only if a mutation sequence of length at most three takes it to an acyclic quiver. Such a sequence can be chosen so that every intermediate quiver has height at most two.
(ii) Q Q Q is mutation-cyclic if and only if either Q Q Q is isomorphic to the dreaded torus, or a sequence of at most two mutations takes Q Q Q to a quiver that
(a) contains a mutation-cyclic full triangle, or
(b) is a vortex, or
(c) is connected and Markov-excluded.
The sufficiency of the conditions in (ii) holds for every four-vertex quiver, and the height restriction is needed only for necessity. Up to vertex relabeling, with reversal of all arrows not quotiented out, the counts are
Table 1 (PDF p. 19).
Proof. The “if” direction of (i) is by definition. The “if” direction of (ii) holds for any four-vertex quiver. Mutation-cyclicity is a property of the mutation class, the dreaded torus is mutation-cyclic because each of its four mutations is a relabeling of Q T Q_T Q T , which contains the directed cycle 1 → 3 → 2 → 1 1 \to3 \to2 \to1 1 → 3 → 2 → 1 , and conditions (a), (b), (c) each force mutation-cyclicity by Proposition 2.1 , Lemma 2.7 and Lemma 2.6 respectively.
The “only if” directions are a finite enumeration. For each representative we record either a short path to an acyclic quiver, or a short path to a quiver with one of the obstructions in (ii). The supplementary program census.py performs both searches and writes the certificates to census_certificates.json, which contains no interpreter versions or timestamps, so that its checksum is reproducible. The program check_census.py checks the representative coverage and every certificate using only the independent implementation of mutation, relabeling, acyclicity, full triangles, vortices, proper wiggle classes and Markov values in reference_q4.py, which shares no code with the generator. For a Markov-exclusion certificate it recomputes every proper wiggle class and its pair ( M , p 2 ) (M,p^2) ( M , p 2 ) , together with the finite table of endpoint pairs used to rule out a match. Both programs use exact integer arithmetic. The census proof uses these certificates and the obstructions above, independently of Theorem 5.1 .
Enumerate the 5 6 = 15,625 5^6 = 15{,}625 5 6 = 15 , 625 tuples with entries in { − 2 , − 1 , 0 , 1 , 2 } \{-2,-1,0,1,2\} { − 2 , − 1 , 0 , 1 , 2 } . Replace each by the lexicographically least of its 24 vertex relabelings. This leaves 695 representatives.
For each representative, examine all 1 + 4 + 4 2 + 4 3 = 85 1+4+4^2+4^3=85 1 + 4 + 4 2 + 4 3 = 85 mutation sequences of length at most three. Discard a sequence if it leaves height two. There are 561 representatives for which a remaining sequence ends at an acyclic quiver. Their shortest lengths are
Table 2.
Of the 134 remaining representatives, one is disconnected. It is ( − 2 , 0 , 2 , 0 , − 2 , 0 ) (-2,0,2,0,-2,0) ( − 2 , 0 , 2 , 0 , − 2 , 0 ) , an oriented triangle of multiplicities ( 2 , 2 , 2 ) (2,2,2) ( 2 , 2 , 2 ) and an isolated vertex. It satisfies (a) with no mutation. One connected representative is the dreaded torus. For each of the other 132, a sequence of at most two mutations reaches a connected quiver satisfying (a), (b) or (c). The first two conditions are checked directly; for (c), use the finite computation of Lemma 2.6 for each proper class. For each representative we take a shortest certificate, and among certificates of the same length we prefer (a), then (b), then (c). With this rule, (a), (b) and (c) are used for 45, 40, and 47 representatives, respectively. For 127 representatives no mutation is needed; four require one mutation and one requires two. Thus every representative not found by the acyclic search satisfies one of the conditions in (ii), which proves both “only if” directions. Separating the representatives by connectedness gives the stated counts.
Remark 6.3. The bound three in Theorem 6.2 (i) is attained by
( − 2 , − 1 , 2 , − 1 , − 1 , − 1 ) → [ 4 , 1 , 3 ] acyclic , ( − 2 , 1 , 1 , − 2 , 1 , − 1 ) → [ 3 , 2 , 4 ] acyclic . (-2,-1,2,-1,-1,-1) \xrightarrow{[4,1,3]} \text{acyclic}, \qquad(-2,1,1,-2,1,-1) \xrightarrow{[3,2,4]} \text{acyclic}. ( − 2 , − 1 , 2 , − 1 , − 1 , − 1 ) [ 4 , 1 , 3 ] acyclic , ( − 2 , 1 , 1 , − 2 , 1 , − 1 ) [ 3 , 2 , 4 ] acyclic .
Neither quiver has an acyclic endpoint after at most two mutations, even if the intermediate height is unrestricted; this is checked by the finite list of words of length at most two. For the negative certificate system in part (ii), the representative
b ( R ) = ( − 2 , − 1 , 2 , − 1 , − 1 , − 2 ) b(R)=(-2,-1,2,-1,-1,-2) b ( R ) = ( − 2 , − 1 , 2 , − 1 , − 1 , − 2 )
requires two mutations. Indeed, μ [ 1 , 3 ] R \mu_{[1,3]}R μ [ 1 , 3 ] R , whose tuple is ( 3 , − 1 , − 2 , 1 , 3 , 0 ) (3,-1,-2,1,3,0) ( 3 , − 1 , − 2 , 1 , 3 , 0 ) , contains the cyclic triangle on { 1 , 2 , 4 } \{1,2,4\} { 1 , 2 , 4 } with multiplicities ( 3 , 3 , 2 ) (3,3,2) ( 3 , 3 , 2 ) and Markov constant 4. Neither R R R nor any of its four one-mutation neighbors is a vortex or contains a mutation-cyclic full triangle. Each has a single proper wiggle class with ( M , p 2 ) = ( 3 , 1 ) (M,p^2)=(3,1) ( M , p 2 ) = ( 3 , 1 ) , a pair realized by the connected acyclic tuple ( 1 , 0 , 0 , 1 , 0 , 1 ) (1,0,0,1,0,1) ( 1 , 0 , 0 , 1 , 0 , 1 ) , so none is Markov-excluded. These examples, including the absence of shorter certificates, are checked by check_census.py.
Proofs of the local lemmas
Throughout the appendices, retain the setup of § 4 , so that Q ∗ Q_\ast Q ∗ is connected and mutation-acyclic, m = m ( Q ∗ ) m=m(Q_\ast) m = m ( Q ∗ ) , T ≥ m T\ge m T ≥ m , and F = T + 1 F=T+1 F = T + 1 . Every quiver considered belongs to the mutation class of Q ∗ Q_\ast Q ∗ , so
3 ≤ m ≤ T , 2 ∣ p ∣ < m 3\le m\le T,\qquad2|p|<m 3 ≤ m ≤ T , 2∣ p ∣ < m
by (8) , where m m m is the Markov invariant of the totally proper class. For each local lemma, relabel the specified vertices as 1, 2.
Every calculation in these appendices is stated as a claim in the file proof_claims.py of the supplement, and is cited here by its label in typewriter font. The program check_proofs.py verifies each claim exactly and for all integer values of its parameters. Polynomial identities are checked by expansion. Inequalities and contradictions are checked with explicit certificates, which write the goal as a nonnegative combination of products of the hypotheses and of squares, modulo the stated equations, sometimes after splitting on whether an integer quantity is at least 1 or at most 0. Mutation formulas are checked by symbolic mutation, after certifying the sign of every entry that the mutation formula (2) needs. Statements about proper wiggle classes, acyclicity, vortices and oriented triangles depend only on the signs of the entries, and are checked by enumerating all sign patterns allowed by the hypotheses. Each claim lists the hypotheses it uses, including the standing bounds F ≥ 4 F\ge4 F ≥ 4 , 3 ≤ m ≤ F − 1 3\le m\le F-1 3 ≤ m ≤ F − 1 and 2 ∣ p ∣ < m 2|p|<m 2∣ p ∣ < m where needed. The case analysis itself, that is, the choice of cases and the argument that they cover all possibilities, is written out below and is not checked by machine. The program bruteforce_local.py tests it independently, by enumerating all excursions for T ≤ 6 T\le6 T ≤ 6 using only the constraints that the proofs use. The verification relies on the exact arithmetic of polynomial.py, the certificate checker in certificates.py, the symbolic mutation in symbolic.py, and the functions of quiver4.py that compute proper wiggle classes, acyclicity and vortices. The hand calculations behind the claims, in the form of an earlier version of these appendices, are reproduced with the same labels in the file APPENDIX_CALCULATIONS.md of the supplement.
We first collect two observations used in several proofs.
Lemma A.1. Let P P P be mutation-acyclic, with b ( P ) = ( a , b , − c , d , E , f ) \mathbf{b}(P)=(a,b,-c,d,E,f) b ( P ) = ( a , b , − c , d , E , f ) . Assume b , c , f > 0 b,c,f>0 b , c , f > 0 and a ≥ 0 a\ge0 a ≥ 0 , and assume moreover that one of the following holds.
(i) d ≥ 0 d\ge0 d ≥ 0 ; the entry E E E may have any sign.
(ii) d < 0 d<0 d < 0 , a = 0 a=0 a = 0 , and $E\le0.
Then P P P has exactly one proper wiggle class, and this class contains ω 0 = ⟨ 1 , 2 , 3 , 4 ⟩ \omega_0=\langle1,2,3,4\rangle ω 0 = ⟨ 1 , 2 , 3 , 4 ⟩ . In particular, m = M ω 0 ( P ) m=M_{\omega_0}(P) m = M ω 0 ( P ) .
Proof. The complete directed triangle on { 1 , 3 , 4 } \{1,3,4\} { 1 , 3 , 4 } restricts every proper class to ⟨ 1 , 2 , 3 , 4 ⟩ \langle1,2,3,4\rangle ⟨ 1 , 2 , 3 , 4 ⟩ , ⟨ 1 , 3 , 2 , 4 ⟩ \langle1,3,2,4\rangle ⟨ 1 , 3 , 2 , 4 ⟩ , and ⟨ 1 , 3 , 4 , 2 ⟩ \langle1,3,4,2\rangle ⟨ 1 , 3 , 4 , 2 ⟩ , and in each sign case the remaining entries either exclude the last two orders or join them to ω 0 \omega_0 ω 0 by wiggles. The proper wiggle classes depend only on the signs of the entries, and for every sign pattern allowed by (i) or (ii) there is at most one proper wiggle class, which contains ω 0 \omega_0 ω 0 [A0.ord1, A0.ord2]. Theorem 2.2 supplies a totally proper class, so it is that class.
Lemma A.2. Let F , r , s F,r,s F , r , s be positive integers satisfying 1 ≤ r , s ≤ F − 1 1\le r,s\le F-1 1 ≤ r , s ≤ F − 1 and r s = 2 F rs=2F r s = 2 F . Then r , s ≥ 3 r,s\ge3 r , s ≥ 3 and
3 ( r 2 + s 2 ) ≤ 2 F 2 − 5 F + 36. (14) 3(r^2+s^2)\le2F^2-5F+36. \tag*{(14)} 3 ( r 2 + s 2 ) ≤ 2 F 2 − 5 F + 36. (14)
Proof. If r ≤ 2 r \le2 r ≤ 2 , then s = 2 F / r ≥ F s = 2F/r \ge F s = 2 F / r ≥ F , contradicting s ≤ F − 1 s \le F - 1 s ≤ F − 1 , and symmetrically for s s s [A0.pb1]. The inequality follows from ( r − 3 ) ( F − 1 − r ) ≥ 0 (r - 3)(F - 1 - r) \ge0 ( r − 3 ) ( F − 1 − r ) ≥ 0 , ( s − 3 ) ( F − 1 − s ) ≥ 0 (s - 3)(F - 1 - s) \ge0 ( s − 3 ) ( F − 1 − s ) ≥ 0 and ( r − 3 ) ( s − 3 ) ≥ 0 (r - 3)(s - 3) \ge0 ( r − 3 ) ( s − 3 ) ≥ 0 [A0.pb2]. □ \square □
Proof of Lemma 4.2
Because vertices 1, 2 are not joined, mutation at either one leaves all entries incident to the other unchanged. The low neighbor μ 1 P \mu_1P μ 1 P therefore bounds every entry except b 34 b_{34} b 34 by T T T . Exchange 3, 4 and reverse arrows as needed to write
b ( P ) = ( 0 , b , − c , d , E , F ) , b , c ≥ 1 , b , c , ∣ d ∣ , ∣ E ∣ ≤ T . \mathbf{b}(P) = (0,b,-c,d,E,F), \qquad b,c \ge1, \qquad b,c,|d|,|E| \le T. b ( P ) = ( 0 , b , − c , d , E , F ) , b , c ≥ 1 , b , c , ∣ d ∣ , ∣ E ∣ ≤ T .
(The signs of b , c b,c b , c are forced, because mutation at 1 lowers the b 34 b_{34} b 34 entry only if its arrows point 4 → 1 → 3 4 \to1 \to3 4 → 1 → 3 , in which case it becomes F − b c F-bc F − b c [A1.mu1P].) The case d < 0 < E d < 0 < E d < 0 < E is impossible, because mutation at 2 would increase b 34 b_{34} b 34 to F + ( − d ) E > F F+(-d)E>F F + ( − d ) E > F [A1.mu2-dneg-Epos, A1.dneg-Epos]. Lemma A.1 gives [A1.markov]
m = b 2 + c 2 + d 2 + E 2 + F 2 − b c F + d E F . (15) m=b^2+c^2+d^2+E^2+F^2-bcF+dEF. \tag*{(15)} m = b 2 + c 2 + d 2 + E 2 + F 2 − b c F + d E F . (15)
We first show that from P P P , and from every quiver of the same form, the mutations at 3 and 4 leave height F F F . This is applied to the second high quiver below. Mutation at 3 would create the entries b F − c bF-c b F − c and E + F [ d ] + E+F[d]_+ E + F [ d ] + [A1.mu3-dpos, A1.mu3-dneg]. If its height were at most F F F , then b = 1 b=1 b = 1 and d ≤ 1 d\le1 d ≤ 1 , with E ≤ 0 E\le0 E ≤ 0 when d = 1 d=1 d = 1 [A1.mu3-b1, A1.mu3-d1, A1.mu3-E]. With b = 1 b=1 b = 1 , each of the cases d = 0 d=0 d = 0 , d < 0 d<0 d < 0 (where E ≤ 0 E\le0 E ≤ 0 , since d < 0 < E d<0<E d < 0 < E is excluded) and d = 1 d=1 d = 1 gives m > F m>F m > F [A1.id-dnonpos, A1.dzero, A1.dneg-Enonpos, A1.id-d1, A1.d1], contradicting m ≤ T m\le T m ≤ T . Mutation at 4 is ruled out by the same argument after reversing arrows and exchanging 3, 4, which sends ( b , c , d , E ) (b,c,d,E) ( b , c , d , E ) to ( c , b , − E , − d ) (c,b,-E,-d) ( c , b , − E , − d ) and preserves the form of the calculation [A1.sym34].
If μ 2 P \mu_2P μ 2 P is high, only its b 34 b_{34} b 34 entry can have magnitude F F F . That entry stays F F F unless d > 0 > E d>0>E d > 0 > E , in which case it becomes F + d E F+dE F + d E [A1.mu2-dpos-Eneg, A1.mu2-dpos-Epos, A1.mu2-dneg-Eneg]. So it either stays F F F or becomes − F -F − F , and the latter requires d > 0 d>0 d > 0 , E = − e < 0 E=-e<0 E = − e < 0 and d e = 2 F de=2F d e = 2 F , where d , e ≤ F − 1 d,e\le F-1 d , e ≤ F − 1 . Then d , e ≥ 3 d,e\ge3 d , e ≥ 3 [A1.minusF-d3, A1.minusF-e3], and the rectangle bound (9) and Lemma A.2 give 3 m ≤ 42 − 8 F − F 2 < 0 3m\le42-8F-F^2<0 3 m ≤ 42 − 8 F − F 2 < 0 , a contradiction [A1.minusF]. Thus a second high quiver has the form ( 0 , b , − c , − d , − E , F ) (0,b,-c,-d,-E,F) ( 0 , b , − c , − d , − E , F ) . It satisfies the same sign restriction and the same Markov bound, so the preceding argument again forbids 3, 4. The next reduced mutation must be at 1. It gives the entry F − b c F-bc F − b c at b 34 b_{34} b 34 , exactly as in the low quiver μ 1 P \mu_1P μ 1 P , and all its other entries are low [A1.second-dneg-Eneg, A1.second-dpos-Epos]. This proves the first assertion.
For the second assertion, the two mutations commute and are involutions, so there are at most four labeled quivers to consider. Only a low endpoint requiring both mutations needs attention. If a one-mutation intermediate quiver P P P has height greater than T T T , its two neighbors are the low start and low endpoint. Such a temporary corner need not have height at most F F F ; the bound m ≤ T m\le T m ≤ T still holds throughout the mutation class. The two low neighbors force every incident entry to be low, and both lower the remaining entry. Thus normalize
b ( P ) = ( 0 , b , − c , d , − e , f ) , 1 ≤ b , c , d , e ≤ T , f > T . \mathbf{b}(P)=(0,b,-c,d,-e,f), \qquad1\le b,c,d,e\le T, \qquad f>T. b ( P ) = ( 0 , b , − c , d , − e , f ) , 1 ≤ b , c , d , e ≤ T , f > T .
The two low neighbors have b 34 b_{34} b 34 entries f − b c f-bc f − b c and f − d e f-de f − d e , and the other corner of the commuting square has entry f − b c − d e f-bc-de f − b c − d e [A1.sq-paths, A1.sq-paths2]. Its upper bound follows from f − b c ≤ T f-bc\le T f − b c ≤ T ; we must prove
f − b c − d e ≥ − T . (16) f-bc-de\ge-T. \tag*{(16)} f − b c − d e ≥ − T . (16)
Lemma A.1 also gives [A1.sq-markov, A1.sq-pf]
m = b 2 + c 2 + d 2 + e 2 + f 2 − f ( b c + d e ) , p = b e − c d . m=b^2+c^2+d^2+e^2+f^2-f(bc+de), \qquad p=be-cd. m = b 2 + c 2 + d 2 + e 2 + f 2 − f ( b c + d e ) , p = b e − c d .
Assume for a contradiction that b c + d e > f + T bc+de>f+T b c + d e > f + T .
If all four of b , c , d , e b,c,d,e b , c , d , e are at least two, then 4 m ≤ 9 4m\le9 4 m ≤ 9 , contradicting m ≥ 3 m\ge3 m ≥ 3 ; the two claims [A1.sq-all2-rs, A1.sq-all2-sr] treat d e ≤ b c de\le bc d e ≤ b c and b c ≤ d e bc\le de b c ≤ d e . Otherwise some entry is 1. The transformations
( b , c , d , e ) ⟼ ( c , b , e , d ) , ( b , c , d , e ) ⟼ ( d , e , b , c ) (b,c,d,e) \longmapsto(c,b,e,d), \qquad(b,c,d,e) \longmapsto(d,e,b,c) ( b , c , d , e ) ⟼ ( c , b , e , d ) , ( b , c , d , e ) ⟼ ( d , e , b , c )
are realized by reversing all arrows and exchanging 3, 4, and by exchanging 1, 2 [A1.sq-sym1-relabel, A1.sq-sym2-relabel]. They preserve all the hypotheses and m m m , and change only the sign of p p p [A1.sq-sym1, A1.sq-sym2]. They can put a unit entry at b = 1 b=1 b = 1 . Then neither d d d nor e e e can be 1 [A1.u-d1, A1.u-e1]. If also c = 1 c=1 c = 1 , then f = F f=F f = F and d e = 2 F − 1 de=2F-1 d e = 2 F − 1 [A1.u-c1-f, A1.u-c1-dehi, A1.u-c1-delo], so d , e d,e d , e are odd and at least three [A1.u-c1-d2, A1.u-c1-e2], and then m < 3 m<3 m < 3 [A1.u-c1-main]. Assume from now on that c ≥ 2 c\ge2 c ≥ 2 , so that c , d , e ≥ 2 c,d,e\ge2 c , d , e ≥ 2 . We use one common estimate [A1.u-common]:
m ≤ ( d − e ) 2 + 4. (17) m \le(d-e)^2+4. \tag*{(17)} m ≤ ( d − e ) 2 + 4. (17)
It remains to compare c c c with d , e d,e d , e .
If c < max ( d , e ) c<\max(d,e) c < max ( d , e ) , then m ≤ 2 m\le2 m ≤ 2 [A1.u-case1-d, A1.u-case1-e].
If e ≤ d ≤ c e\le d\le c e ≤ d ≤ c , then 2 ∣ p ∣ = 2 ( c d − e ) ≥ ( d − e ) 2 + 4 ≥ m 2|p|=2(cd-e)\ge(d-e)^2+4\ge m 2∣ p ∣ = 2 ( c d − e ) ≥ ( d − e ) 2 + 4 ≥ m by (17) , contradicting 2 ∣ p ∣ < m 2|p|<m 2∣ p ∣ < m [A1.u-case2].
If d < e = c d<e=c d < e = c , then m ≤ 2 ∣ p ∣ m\le2|p| m ≤ 2∣ p ∣ , contradicting 2 ∣ p ∣ < m 2|p|<m 2∣ p ∣ < m [A1.u-case3-d2, A1.u-case3-d3].
If d < e < c d<e<c d < e < c , then f < d e < 2 ( c d − e ) < m ≤ T < f f<de<2(cd-e)<m\le T<f f < d e < 2 ( c d − e ) < m ≤ T < f [A1.u-case4].
This proves (16) . Thus whenever one intermediate corner has height greater than T T T , the other is low. The alternative two-mutation path has exactly the same labeled endpoint and stays low, proving the second assertion. □
Proof of Lemma 4.4
Put N 0 = C N_0=C N 0 = C , N 1 = μ 1 C N_1=\mu_1C N 1 = μ 1 C , N 2 = μ [ 1 , 2 ] C N_2=\mu_{[1,2]}C N 2 = μ [ 1 , 2 ] C , N 3 = μ [ 1 , 2 , 1 ] C N_3=\mu_{[1,2,1]}C N 3 = μ [ 1 , 2 , 1 ] C , N 4 = μ [ 1 , 2 , 1 , 2 ] C N_4=\mu_{[1,2,1,2]}C N 4 = μ [ 1 , 2 , 1 , 2 ] C . By the pentagon relation (10) , there are at most ten labeled quivers reachable using only 1, 2, namely N r N_r N r , N r π 12 N_r^{\pi_{12}} N r π 12 . Mutation at 1 or 2 gives the following transitions:
Table 4.
The transitions from N r π 12 N_r^{\pi_{12}} N r π 12 follow by swapping the mutation vertices. It is enough to reach the endpoint up to π 12 \pi_{12} π 12 . The endpoints N 0 N_0 N 0 , N 1 N_1 N 1 , N 4 N_4 N 4 require at most one mutation. For N 2 N_2 N 2 , use [ 1 , 2 ] [1,2] [ 1 , 2 ] if ht ( N 1 ) ≤ K \operatorname{ht}(N_1)\le K ht ( N 1 ) ≤ K , and [ 2 , 1 , 2 ] [2,1,2] [ 2 , 1 , 2 ] otherwise. For N 3 N_3 N 3 , use [ 2 , 1 ] [2,1] [ 2 , 1 ] if ht ( N 4 ) ≤ K \operatorname{ht}(N_4)\le K ht ( N 4 ) ≤ K , and [ 1 , 2 , 1 ] [1,2,1] [ 1 , 2 , 1 ] otherwise. The next calculation proves that each detour stays within height K K K .
It remains to justify the detour when a direct intermediate quiver P P P exceeds height K K K , but both neighbors μ 1 P , μ 2 P \mu_1P,\mu_2P μ 1 P , μ 2 P have height at most K K K . Every entry touching vertex 1 or 2 is bounded by K K K , because one of these mutations simply reverses that entry. Thus only the b 34 b_{34} b 34 entry can exceed K K K . Reverse arrows and exchange 3, 4 if necessary to make b 12 ( P ) = 1 b_{12}(P)=1 b 12 ( P ) = 1 and b 34 ( P ) = f > K b_{34}(P)=f>K b 34 ( P ) = f > K . For mutation at 1 to reduce f f f , its incident arrows must be 4 → 1 → 3 4\to1\to3 4 → 1 → 3 , and for mutation at 2 to reduce f f f , they must be 4 → 2 → 3 4\to2\to3 4 → 2 → 3 . Therefore
b ( P ) = ( 1 , b , − c , d , − e , f ) , b , c , d , e ≥ 1. \mathbf{b}(P)=(1,b,-c,d,-e,f), \qquad b,c,d,e\ge1. b ( P ) = ( 1 , b , − c , d , − e , f ) , b , c , d , e ≥ 1.
The tuples of the two low neighbors are [A2.neighbours1, A2.neighbours2]
( − 1 , − b , c , d , − c − e , f − b c ) , ( − 1 , b + d , − c , − d , e , f − d e ) . (-1,-b,c,d,-c-e,f-bc), \qquad(-1,b+d,-c,-d,e,f-de). ( − 1 , − b , c , d , − c − e , f − b c ) , ( − 1 , b + d , − c , − d , e , f − d e ) .
They give b + d ≤ K b+d\le K b + d ≤ K , c + e ≤ K c+e\le K c + e ≤ K , and ∣ f − b c ∣ , ∣ f − d e ∣ ≤ K |f-bc|,|f-de|\le K ∣ f − b c ∣ , ∣ f − d e ∣ ≤ K . Lemma A.1 identifies the totally proper class, so [A2.markov, A2.pf]
D = b c + d e + c d , m = 1 + b 2 + c 2 + d 2 + e 2 + b d + c e + f 2 − f D , p = f + b e − c d . D=bc+de+cd,\qquad m=1+b^2+c^2+d^2+e^2+bd+ce+f^2-fD,\qquad p=f+be-cd. D = b c + d e + c d , m = 1 + b 2 + c 2 + d 2 + e 2 + b d + ce + f 2 − f D , p = f + b e − c d .
Starting at μ 1 P \mu_1P μ 1 P , the alternative path [2, 1, 2] ends at ( μ 2 P ) τ 12 (\mu_2P)^{\tau_{12}} ( μ 2 P ) τ 12 , and its two intermediate tuples are [A2.detour]
( 1 , − b , − e , − d , c + e , f − D ) , ( − 1 , b , e , − b − d , c , f − D ) (1,-b,-e,-d,c+e,f-D),\qquad(-1,b,e,-b-d,c,f-D) ( 1 , − b , − e , − d , c + e , f − D ) , ( − 1 , b , e , − b − d , c , f − D ) .
All their entries are bounded by K K K except possibly f − D f-D f − D . Its upper bound follows from f − D ≤ f − b c ≤ K f-D\le f-bc\le K f − D ≤ f − b c ≤ K . We must prove f − D ≥ − K f-D\ge-K f − D ≥ − K . Suppose instead f + K < D f+K<D f + K < D . If c , d ≥ 2 c,d\ge2 c , d ≥ 2 , then m ≤ − 1 m\le-1 m ≤ − 1 , contradicting m ≥ 3 m\ge3 m ≥ 3 ; the two claims [A2.cd2-SU, A2.cd2-US] treat b + d ≥ c + e b+d\ge c+e b + d ≥ c + e and c + e ≥ b + d c+e\ge b+d c + e ≥ b + d . If d = 1 d=1 d = 1 , then b , c ≥ 2 b,c\ge2 b , c ≥ 2 [A2.d1-b1, A2.d1-c1], and m − 2 p ≤ − 5 m-2p\le-5 m − 2 p ≤ − 5 , contradicting 2 ∣ p ∣ < m 2|p|<m 2∣ p ∣ < m ; with S = b + 1 S=b+1 S = b + 1 and U = c + e U=c+e U = c + e , the three claims [A2.d1-SU, A2.d1-US-i, A2.d1-US-ii] treat S ≥ U S\ge U S ≥ U , and U ≥ S U\ge S U ≥ S with c ≤ S − 1 c\le S-1 c ≤ S − 1 or c ≥ S − 1 c\ge S-1 c ≥ S − 1 . The case c = 1 c=1 c = 1 follows by the symmetry ( b , c , d , e ) ↦ ( e , d , c , b ) (b,c,d,e)\mapsto(e,d,c,b) ( b , c , d , e ) ↦ ( e , d , c , b ) , which is realized by reversing all arrows and relabeling by ( 1 2 ) ( 3 4 ) (1\,2)(3\,4) ( 1 2 ) ( 3 4 ) , and which preserves the hypotheses [A2.sym-relabel, A2.sym]. Thus f − D ≥ − K f-D\ge-K f − D ≥ − K , proving the height bound. □
Proof of Lemma 4.5
Reverse all arrows if necessary so that a = b 12 ( P ) ≥ 2 a=b_{12}(P)\ge2 a = b 12 ( P ) ≥ 2 . All entries incident to 1 have magnitude less than F F F , because mutation at 1 only reverses them. The entries incident to 2 also have magnitude less than F F F . Indeed, for k = 3 , 4 k=3,4 k = 3 , 4 , mutation at 1 replaces b 2 k ( P ) b_{2k}(P) b 2 k ( P ) by b 2 k ( P ) − a [ − b 1 k ( P ) ] + b_{2k}(P)-a[-b_{1k}(P)]_+ b 2 k ( P ) − a [ − b 1 k ( P ) ] + . Thus b 2 k ( P ) = − F b_{2k}(P)=-F b 2 k ( P ) = − F could not become low. If b 2 k ( P ) = F b_{2k}(P)=F b 2 k ( P ) = F becomes low, then b 1 k ( P ) < 0 b_{1k}(P)<0 b 1 k ( P ) < 0 , and mutation at 2 would create the entry b 1 k ( P ) + a F > F b_{1k}(P)+aF>F b 1 k ( P ) + a F > F , contrary to its height bound [A3.b23-mu1-ypos, A3.b23-mu1-yneg, A3.b23m-mu1, A3.b23m-mu1-ypos, A3.b23-mu2, A3.b23-big]; these claims treat k = 3 k=3 k = 3 , and k = 4 k=4 k = 4 follows by exchanging 3, 4. Only the entry b 34 ( P ) b_{34}(P) b 34 ( P ) can therefore have magnitude F F F . Exchange 3, 4 if necessary to make that entry positive. For mutation at 1 to lower it, its two arrows must point 4 → 1 → 3 4\to1\to3 4 → 1 → 3 . Consequently
b ( P ) = ( a , b , − c , d , E , F ) , a ≥ 2 , b , c ≥ 1 , a , b , c , ∣ d ∣ , ∣ E ∣ ≤ F − 1. \mathbf{b}(P)=(a,b,-c,d,E,F),\qquad a\ge2,\quad b,c\ge1,\quad a,b,c,|d|,|E|\le F-1. b ( P ) = ( a , b , − c , d , E , F ) , a ≥ 2 , b , c ≥ 1 , a , b , c , ∣ d ∣ , ∣ E ∣ ≤ F − 1.
The two neighbor bounds also give
∣ E − a c ∣ ≤ F − 1 , b + a d ≤ F if d ≥ 0. |E-ac|\le F-1,\qquad b+ad\le F\quad\text{if }d\ge0. ∣ E − a c ∣ ≤ F − 1 , b + a d ≤ F if d ≥ 0.
[A3.nb1, A3.nb2]. Its Pfaffian is p = a F − b E − c d p=aF-bE-cd p = a F − b E − c d [A3.pf].
We first show d ≥ 0 d\ge0 d ≥ 0 and E ≥ c E\ge c E ≥ c . If d < 0 < E d<0<E d < 0 < E , mutation at 2 creates the entry F + ( − d ) E > F F+(-d)E>F F + ( − d ) E > F [A3.mu2-dneg-Epos, A3.dneg-Epos]. If d < 0 d<0 d < 0 and E ≤ 0 E\le0 E ≤ 0 , then p ≥ a F ≥ 2 F p\ge aF\ge2F p ≥ a F ≥ 2 F , contradicting (8) [A3.dneg-Enonpos]. The same contradiction excludes d = 0 d=0 d = 0 , E < 0 E<0 E < 0 [A3.d0-Eneg]. In all remaining cases, Lemma A.1 gives m = M ω 0 ( P ) m=M_{\omega_0}(P) m = M ω 0 ( P ) . If d ≥ 0 d\ge0 d ≥ 0 and 0 ≤ E < c 0\le E<c 0 ≤ E < c , put x = b + ( a − 1 ) d x=b+(a-1)d x = b + ( a − 1 ) d and y = c − E y=c-E y = c − E , so that 1 ≤ x , y ≤ F − 1 1\le x,y\le F-1 1 ≤ x , y ≤ F − 1 . The identity
m = a 2 + x 2 + y 2 − F x y − ( a − 1 ) F 2 + F p − ( a − 2 ) { d ( b + a d ) + c E + F d E } m=a^2+x^2+y^2-Fxy-(a-1)F^2+Fp-(a-2)\{d(b+ad)+cE+FdE\} m = a 2 + x 2 + y 2 − F x y − ( a − 1 ) F 2 + F p − ( a − 2 ) { d ( b + a d ) + c E + F d E }
[A3.identity1], the rectangle bound (9) and 2 p < m ≤ F − 1 2p<m\le F-1 2 p < m ≤ F − 1 give 2 m < 6 2m<6 2 m < 6 , contradicting m ≥ 3 m\ge3 m ≥ 3 [A3.case-Esmall-d1, A3.case-Esmall-d0]. If d > 0 d>0 d > 0 and E = − e < 0 E=-e<0 E = − e < 0 , then a c + e ≤ F − 1 ac+e\le F-1 a c + e ≤ F − 1 and b + ( a − 1 ) d ≤ F − 1 b+(a-1)d\le F-1 b + ( a − 1 ) d ≤ F − 1 , and a similar estimate [A3.identity2, A3.case-Eneg] again gives 2 m < 6 2m<6 2 m < 6 . Thus d ≥ 0 d\ge0 d ≥ 0 and E ≥ c E\ge c E ≥ c as claimed.
Write β = b + a d \beta=b+ad β = b + a d and γ = a E − c \gamma=aE-c γ = a E − c . Mutation at 2 gives [A3.mu2-rest, A3.gamma-ge-E]
b ( μ 2 P ) = ( − a , β , γ , − d , − E , F ) , β ≥ 1 , γ ≥ E ≥ 1. (18) \mathbf{b}(\mu_2P)=(-a,\beta,\gamma,-d,-E,F),\qquad\beta\ge1,\quad\gamma\ge E\ge1. \tag*{(18)} b ( μ 2 P ) = ( − a , β , γ , − d , − E , F ) , β ≥ 1 , γ ≥ E ≥ 1. (18)
Mutation at 3 would create the entry γ + β F > F \gamma+\beta F>F γ + β F > F [A3.mu2-then3, A3.mu2-then3-big]. Mutation at 4 would create an entry of magnitude d + E F > F d+EF>F d + E F > F , unless d = 0 d=0 d = 0 , E = c = 1 E=c=1 E = c = 1 [A3.mu2-then4, A3.mu2-then4-d, A3.mu2-then4-E]. In this exception the unique proper class identified above gives m = a 2 + b 2 + F 2 − a − b F + 2 > F m=a^2+b^2+F^2-a-bF+2>F m = a 2 + b 2 + F 2 − a − b F + 2 > F , contradicting m ≤ T m\le T m ≤ T [A3.exception-m, A3.exception]. A reduced continuation must therefore mutate at 1.
After this mutation, b 12 b_{12} b 12 is positive, b 34 = F b_{34}=F b 34 = F , and the two columns joining 1, 2 to 3, 4 are ( − β , a β − d ) (-\beta,a\beta-d) ( − β , a β − d ) and ( − γ , a γ − E ) (-\gamma,a\gamma-E) ( − γ , aγ − E ) [A3.mu1-after]. Each has the form ( − X , Y ) (-X,Y) ( − X , Y ) with 1 ≤ X ≤ Y 1\le X\le Y 1 ≤ X ≤ Y [A3.form-beta, A3.form-gamma]. From any quiver of this form, mutation at 3 creates the b 24 b_{24} b 24 entry Y 4 + Y 3 F > F Y_4+Y_3F>F Y 4 + Y 3 F > F , and mutation at 4 creates the b 13 b_{13} b 13 entry − X 3 − X 4 F < − F -X_3-X_4F<-F − X 3 − X 4 F < − F [A3.W-mu3, A3.W-mu3-big, A3.W-mu4, A3.W-mu4-big]. Only 1, 2 can be used. To see that the same argument keeps applying, mutate at 2 and exchange labels 1, 2. A column ( − X , Y ) (-X,Y) ( − X , Y ) becomes ( − Y , a Y − X ) (-Y,aY-X) ( − Y , aY − X ) with a Y − X ≥ Y ≥ 1 aY-X \ge Y \ge1 aY − X ≥ Y ≥ 1 [A3.W-mu2, A3.W-form3, A3.W-form4]. The entry b 12 b_{12} b 12 is again positive, and b 34 b_{34} b 34 remains F F F . Thus every reduced continuation is forced to alternate at 1, 2, and a forbidden choice at 3 or 4 exceeds height F F F . The unchanged entry b 34 = F b_{34}=F b 34 = F prevents any return to a low quiver. □
Proof of Proposition 4.7
We keep the setup of § 4 and of Proposition 4.7. In particular, the route minimizes (11) , its maximum height is F F F , and C C C is the low quiver preceding a high segment of this route; the first two mutation vertices are 1, 2, and b 12 ( C ) = 1 b_{12}(C)=1 b 12 ( C ) = 1 . Part (a) is Lemma 4.4 with K = T K=T K = T . From now on the segment uses a third vertex. No quiver before the endpoint of a minimizing route is acyclic. Otherwise, truncating there would decrease its maximum height, its number of visits at that height, or its length, in that order. In particular, the low predecessor C C C is not acyclic. We use this observation to discard acyclic sign cases immediately.
The prefix before the third vertex is [1,2]
Before the first mutation at a third vertex, the route alternates at 1, 2 and reaches a quiver of height at most F F F from the low quiver C C C . By Lemma 4.4 with K = F K=F K = F , that quiver is reached, up to the swap of 1, 2, by at most three mutations within height F F F . If the alternating prefix had length four or more, replacing it by this shorter route and transporting the tail by (3) would remove at least one high quiver (the prefix consists of high quivers, and the shorter route contains fewer of them), contradicting the minimizing-route hypothesis in Proposition 4.7. Hence the prefix is [ 1 , 2 ] [1,2] [ 1 , 2 ] or [ 1 , 2 , 1 ] [1,2,1] [ 1 , 2 , 1 ] . We now exclude [ 1 , 2 , 1 ] [1,2,1] [ 1 , 2 , 1 ] . The pentagon relation gives μ [ 2 , 1 ] C = ( μ [ 1 , 2 , 1 ] C ) π 12 \mu_{[2,1]}C=(\mu_{[1,2,1]}C)^{\pi_{12}} μ [ 2 , 1 ] C = ( μ [ 1 , 2 , 1 ] C ) π 12 . If μ 2 C \mu_2C μ 2 C had height at most F F F , replacing [ 1 , 2 , 1 ] [1,2,1] [ 1 , 2 , 1 ] by [ 2 , 1 ] [2,1] [ 2 , 1 ] would remove a high quiver. In each replacement, the old prefix has three high quivers, while the new prefix has at most two, and transporting the tail preserves all its heights. Thus minimality forces ht ( μ 2 C ) > F \operatorname{ht}(\mu_2C)>F ht ( μ 2 C ) > F . The next calculation shows that this is impossible.
Write the tuple of the low starting quiver as b ( C ) = ( 1 , x , c , d , e , f ) \mathbf{b}(C)=(1,x,c,d,e,f) b ( C ) = ( 1 , x , c , d , e , f ) . Because μ [ 2 , 1 ] C \mu_{[2,1]}C μ [ 2 , 1 ] C is a relabeling of the third high quiver, it has height at most F F F . Its last mutation reverses every entry touching 1, and the entries touching 2 of μ 2 C \mu_2C μ 2 C are reversals of entries of C C C . Hence only the b 34 b_{34} b 34 entry of μ 2 C \mu_2C μ 2 C can exceed F F F . Exchange 3, 4 to make it less than − F -F − F . To decrease f f f at vertex 2, we must have d > 0 d>0 d > 0 and e = − E < 0 e=-E<0 e = − E < 0 , and then b 34 ( μ 2 C ) = f − d E < − F b_{34}(\mu_2C)=f-dE<-F b 34 ( μ 2 C ) = f − d E < − F , while the b 13 , b 14 b_{13},b_{14} b 13 , b 14 entries of μ 2 C \mu_2C μ 2 C are x + d , c x+d,c x + d , c [B1.mu2C]. For mutation at 1 to raise its b 34 b_{34} b 34 entry back into [ − F , F ] [-F,F] [ − F , F ] , we therefore need x + d < k x+d<k x + d < k , so write x = − b x=-b x = − b , thus b > d > 1 b>d>1 b > d > 1 and c , E > 1 c,E>1 c , E > 1 . The first high quiver μ 1 C \mu_1C μ 1 C can now reach height F F F only in its b 34 b_{34} b 34 entry, which is f + b c f+bc f + b c [B1.mu1C]. Since f ≥ − ( F − 1 ) f\ge-(F-1) f ≥ − ( F − 1 ) and b c > 0 bc>0 b c > 0 , this entry cannot be − F -F − F . Consequently
b ( C ) = ( 1 , − b , c , d , − E , F − b c ) , b , c , d , E ≥ 1 , d < b . \mathbf{b}(C)=(1,-b,c,d,-E,F-bc),\qquad b,c,d,E\ge1,\qquad d<b. b ( C ) = ( 1 , − b , c , d , − E , F − b c ) , b , c , d , E ≥ 1 , d < b .
The height bounds on C C C , on μ 2 C \mu_2C μ 2 C , and on the quivers after [ 1 ] [1] [ 1 ] , [ 1 , 2 ] [1,2] [ 1 , 2 ] , [ 1 , 2 , 1 ] [1,2,1] [ 1 , 2 , 1 ] [B1.prefix] give
b c ≤ 2 F − 1 , 2 F < b c + d E , c + E ≤ F , bc\le2F-1,\qquad2F<bc+dE,\qquad c+E\le F, b c ≤ 2 F − 1 , 2 F < b c + d E , c + E ≤ F ,
and either
or
d ( c + E ) = 2 F . d(c+E)=2F. d ( c + E ) = 2 F .
The directed triangle 1 → 2 → 3 → 1 1\to2\to3\to1 1 → 2 → 3 → 1 fixes the cyclic order ⟨ 1 , 2 , 3 ⟩ \langle1,2,3\rangle ⟨ 1 , 2 , 3 ⟩ , and the path 1 → 4 → 2 1\to4\to2 1 → 4 → 2 in the complete triple { 1 , 2 , 4 } \{1,2,4\} { 1 , 2 , 4 } places 4 between 1, 2. Thus C C C has the unique proper wiggle class represented by ⟨ 1 , 4 , 2 , 3 ⟩ \langle1,4,2,3\rangle ⟨ 1 , 4 , 2 , 3 ⟩ [B1.order], and [B1.markov, B1.pf]
m = 1 + b 2 + c 2 + d 2 + E 2 + c E − b d + F 2 − F ( b c + d E ) , p = F − b ( c + E ) + c d . m=1+b^2+c^2+d^2+E^2+cE-bd+F^2-F(bc+dE),\qquad p=F-b(c+E)+cd. m = 1 + b 2 + c 2 + d 2 + E 2 + c E − b d + F 2 − F ( b c + d E ) , p = F − b ( c + E ) + c d .
If c + E = F c+E=F c + E = F , then b ≥ 3 b\ge3 b ≥ 3 [B1.ce-b2], and the identity b ( − 2 p − F ) = F ( 2 b 2 − 3 b − 4 d ) + 2 d ( 2 F − b c ) b(-2p-F)=F(2b^2-3b-4d)+2d(2F-bc) b ( − 2 p − F ) = F ( 2 b 2 − 3 b − 4 d ) + 2 d ( 2 F − b c ) [B1.ce-identity] shows − 2 p > F -2p>F − 2 p > F , contradicting 2 ∣ p ∣ < m ≤ F − 1 2|p|<m\le F-1 2∣ p ∣ < m ≤ F − 1 [B1.ce]. Otherwise d ( c + E ) = 2 F d(c+E)=2F d ( c + E ) = 2 F , so that d , c + E ≥ 3 d,c+E\ge3 d , c + E ≥ 3 and F ≥ 5 F\ge5 F ≥ 5 [B1.d1-d3, B1.d1-L3, B1.d1-F5], and Lemma A.2 gives 3 m ≤ − F 2 − 5 F + 36 − 3 c E < 9 3m\le-F^2-5F+36-3cE<9 3 m ≤ − F 2 − 5 F + 36 − 3 c E < 9 , contradicting m ≥ 3 m\ge3 m ≥ 3 [B1.d1]. Hence the first mutation at a third vertex follows the sequence [ 1 , 2 ] [1,2] [ 1 , 2 ] .
The sign cases
Write the tuple of the low starting quiver as b ( C ) = ( 1 , x , c , d , e , f ) \mathbf{b}(C)=(1,x,c,d,e,f) b ( C ) = ( 1 , x , c , d , e , f ) , and relabel the third vertex as 3. The quivers after [1] and [1, 2] have height F F F , and the quiver after [1, 2, 3] has height at most F F F . We write P P P and Q Q Q for the quivers after [1] and [1, 2], so that Q = μ 2 P Q=\mu_2P Q = μ 2 P is a local name in this appendix, and we refer to the height bounds on P P P , Q Q Q and μ 3 Q \mu_3Q μ 3 Q as the first, second and third height bounds. There are three cases, according to the signs of x x x and d d d . The outcome is that only the quivers A c A_c A c and I t , u I_{t,u} I t , u of (12) survive.
Case x = − b < 0 < d x=-b<0<d x = − b < 0 < d
Here 1 ≤ b , d ≤ F − 1 1\leq b,d\leq F-1 1 ≤ b , d ≤ F − 1 , and all entries of C C C have absolute value at most F − 1 F-1 F − 1 .
First suppose c > 0 c>0 c > 0 . Mutation at 1 gives ( − 1 , b , − c , d − b , e , f + b c ) (-1,b,-c,d-b,e,f+bc) ( − 1 , b , − c , d − b , e , f + b c ) [B21.P-cpos], so the first high quiver can reach height F F F only through its b 34 b_{34} b 34 entry, and f + b c = F f+bc=F f + b c = F . We consider the three possible comparisons between b b b and d d d .
If d < b d<b d < b , put r = b − d ≥ 1 r=b-d\geq1 r = b − d ≥ 1 . For e ≥ 0 e\geq0 e ≥ 0 , the b 34 b_{34} b 34 entry of Q Q Q is F + r e F+re F + r e , and for e ≤ 0 e\leq0 e ≤ 0 , the b 24 b_{24} b 24 entry of μ 3 Q \mu_3Q μ 3 Q is r F − e rF-e r F − e [B21.a-Q-epos, B21.a-Q-eneg]. The second and third height bounds therefore give e = 0 e=0 e = 0 [B21.a-epos, B21.a-eneg], then r = 1 r=1 r = 1 [B21.a-r] and d = 1 d=1 d = 1 [B21.a-d]. Thus b = 2 b=2 b = 2 and
b ( C ) = ( 1 , − 2 , c , 1 , 0 , F − 2 c ) = b ( A c ) . \mathbf{b}(C)=(1,-2,c,1,0,F-2c)=\mathbf{b}(A_c). b ( C ) = ( 1 , − 2 , c , 1 , 0 , F − 2 c ) = b ( A c ) .
If b < d b<d b < d , put r = d − b ≥ 1 r=d-b\geq1 r = d − b ≥ 1 . When e ≥ 0 e\geq0 e ≥ 0 , the Pfaffian is p = F + r c + b e ≥ F p=F+rc+be\geq F p = F + r c + b e ≥ F , contrary to (8) [B21.b-pf, B21.b-epos]. Hence e = − E < 0 e=-E<0 e = − E < 0 . Now b ( Q ) = ( 1 , b , − c − E , − r , E , F − r E ) \mathbf{b}(Q)=(1,b,-c-E,-r,E,F-rE) b ( Q ) = ( 1 , b , − c − E , − r , E , F − r E ) [B21.b-Q], and μ 3 Q \mu_3Q μ 3 Q has b 12 = 1 + b r b_{12}=1+br b 12 = 1 + b r and b 24 = E − r [ r E − F ] + b_{24}=E-r[rE-F]_+ b 24 = E − r [ r E − F ] + [B21.b-mu3Q-a, B21.b-mu3Q-b]. Because Q Q Q has height F F F , either c + E = F c+E=F c + E = F or r E = 2 F rE=2F r E = 2 F . The latter forces r ≥ 3 r\geq3 r ≥ 3 , and then b 24 ( μ 3 Q ) < − F b_{24}(\mu_3Q)<-F b 24 ( μ 3 Q ) < − F [B21.b-rE2, B21.b-rE3]. Consequently c + E = F c+E=F c + E = F . The directed triangle 1 → 2 → 3 → 1 1\to2\to3\to1 1 → 2 → 3 → 1 and the path 1 → 4 → 2 1\to4\to2 1 → 4 → 2 again leave the single proper wiggle class of ⟨ 1 , 4 , 2 , 3 ⟩ \langle1,4,2,3\rangle ⟨ 1 , 4 , 2 , 3 ⟩ [B1.order], and evaluation in this ordering gives [B21.markov-1423]
m = 1 + b 2 + c 2 + d 2 + E 2 + f 2 + c E + b c f − b d − d E f − b c d E . (19) m=1+b^2+c^2+d^2+E^2+f^2+cE+bcf-bd-dEf-bcdE. \tag*{(19)} m = 1 + b 2 + c 2 + d 2 + E 2 + f 2 + c E + b c f − b d − d E f − b c d E . (19)
Using d = b + r d=b+r d = b + r , c + E = F c+E=F c + E = F , and f = F − b c f=F-bc f = F − b c , this becomes [B21.b-reduced, B21.b-reduced-p]
m = 1 + b 2 + b r + r 2 − ( b − 2 ) F 2 − r F E − c E , p = ( r + 1 ) c − ( b − 1 ) E . m=1+b^2+br+r^2-(b-2)F^2-rFE-cE,\qquad p=(r+1)c-(b-1)E. m = 1 + b 2 + b r + r 2 − ( b − 2 ) F 2 − r F E − c E , p = ( r + 1 ) c − ( b − 1 ) E .
If b ≥ 3 b\geq3 b ≥ 3 , then m < 3 m<3 m < 3 [B21.b-b3], and if b = 2 b=2 b = 2 , then m ≤ 1 m\leq1 m ≤ 1 [B21.b-b2-identity, B21.b-b2]. We must therefore have b = 1 b=1 b = 1 . Now p = ( r + 1 ) c > 0 p=(r+1)c>0 p = ( r + 1 ) c > 0 , and 2 p < m ≤ F − 1 = c + E − 1 2p<m\leq F-1=c+E-1 2 p < m ≤ F − 1 = c + E − 1 gives E ≥ ( 2 r + 1 ) c + 2 E\geq(2r+1)c+2 E ≥ ( 2 r + 1 ) c + 2 [B21.b-b1-E]. But f = E f=E f = E , so the full triangle on { 2 , 3 , 4 } \{2,3,4\} { 2 , 3 , 4 } is an oriented cycle with multiplicities ( r + 1 , E , E ) (r+1,E,E) ( r + 1 , E , E ) [B21.b-b1-triangle], all at least two, and its Markov constant ( r + 1 ) 2 − ( r − 1 ) E 2 (r+1)^2-(r-1)E^2 ( r + 1 ) 2 − ( r − 1 ) E 2 is at most 4 [B21.b-b1-markov3]. Proposition 2.1 excludes this triangle. Thus b < d b<d b < d is impossible when c > 0 c>0 c > 0 .
If b = d b=d b = d , the Pfaffian is p = F + b e p=F+be p = F + b e , so again e = − E < 0 e=-E<0 e = − E < 0 [B21.c-pf, B21.c-epos]. Here b ( Q ) = ( 1 , b , − c − E , 0 , E , F ) \mathbf{b}(Q)=(1,b,-c-E,0,E,F) b ( Q ) = ( 1 , b , − c − E , 0 , E , F ) and b 14 ( μ 3 Q ) = b F − c − E b_{14}(\mu_3Q)=bF-c-E b 14 ( μ 3 Q ) = b F − c − E [B21.c-Q], which forces b ≤ 2 b\leq2 b ≤ 2 [B21.c-b3]. The same ordering argument identifies the transported Markov value with (19). At b = 1 b=1 b = 1 , we get m > F m>F m > F [B21.c-b1-m, B21.c-b1]. At b = 2 b=2 b = 2 , the height bound on Q Q Q gives c + E ≤ F c+E\leq F c + E ≤ F , while the b 14 b_{14} b 14 entry of μ 3 Q \mu_3Q μ 3 Q gives c + E ≥ F c+E\geq F c + E ≥ F . Thus c + E = F c+E=F c + E = F , and then m = 5 − c F m=5-cF m = 5 − c F forces c + E ≤ 3 < F c+E\leq3<F c + E ≤ 3 < F [B21.c-b2-m, B21.c-b2].
Now suppose c ≤ 0 c\leq0 c ≤ 0 . Mutation at 1 gives ( − 1 , b , − c , d − b , e + c , f ) (-1,b,-c,d-b,e+c,f) ( − 1 , b , − c , d − b , e + c , f ) [B21.n-P], whose only entry that can have magnitude F F F is e + c e+c e + c . Hence c = − t < 0 c=-t<0 c = − t < 0 , e = − v < 0 e=-v<0 e = − v < 0 , and t + v = F t+v=F t + v = F , with t , v ≥ 1 t,v\geq1 t , v ≥ 1 . If f < 0 f<0 f < 0 , vertex 4 is a source and C C C is a vortex [B21.n-vortex], which Lemma 2.7 excludes. We may assume 0 ≤ f ≤ F − 1 0\leq f\leq F-1 0 ≤ f ≤ F − 1 .
If d < b d<b d < b , put r = b − d ≥ 1 r=b-d\geq1 r = b − d ≥ 1 . Then b ( Q ) = ( 1 , d , − v , r , F , f ) \mathbf{b}(Q)=(1,d,-v,r,F,f) b ( Q ) = ( 1 , d , − v , r , F , f ) and b 24 ( μ 3 Q ) = F + r f b_{24}(\mu_3Q)=F+rf b 24 ( μ 3 Q ) = F + r f [B21.n-dlt]. The third height bound gives f = 0 f=0 f = 0 [B21.n-dlt-f], but then ∣ p ∣ = b v + t d ≥ F |p|=bv+td\geq F ∣ p ∣ = b v + t d ≥ F , contradicting (8) [B21.n-dlt-p].
If d = b d=b d = b , then p = f − b F p=f-bF p = f − b F [B21.n-deq-p], so b = 1 b=1 b = 1 [B21.n-deq-b2]. The unique proper wiggle class contains ⟨ 1 , 2 , 3 , 4 ⟩ \langle1,2,3,4\rangle ⟨ 1 , 2 , 3 , 4 ⟩ [B21.n-deq-order0, B21.n-deq-order1], and evaluation in this class gives m = 2 + t 2 + v 2 + f 2 + t v − v f > F m=2+t^2+v^2+f^2+tv-vf>F m = 2 + t 2 + v 2 + f 2 + t v − v f > F , again impossible [B21.n-deq-m, B21.n-deq-b1].
Finally, if d > b d>b d > b , put r = d − b ≥ 1 r=d-b\ge1 r = d − b ≥ 1 . Then b ( Q ) = ( 1 , b , − v , − r , F , f − r F ) \mathbf{b}(Q)=(1,b,-v,-r,F,f-rF) b ( Q ) = ( 1 , b , − v , − r , F , f − r F ) and b 34 ( μ 3 Q ) = r F − f b_{34}(\mu_3Q)=rF-f b 34 ( μ 3 Q ) = r F − f [B21.n-dgt]. Since f ≤ F − 1 f\le F-1 f ≤ F − 1 , the third height bound forces r = 1 r=1 r = 1 [B21.n-dgt-r]. Put u = F − f ≥ 1 u=F-f\ge1 u = F − f ≥ 1 . Then ∣ p ∣ = ( b − 1 ) F + t + u |p|=(b-1)F+t+u ∣ p ∣ = ( b − 1 ) F + t + u [B21.n-dgt-p], so b = 1 b=1 b = 1 [B21.n-dgt-b2], d = 2 d=2 d = 2 , and 2 ( t + u ) < m ≤ F − 1 2(t+u)<m\le F-1 2 ( t + u ) < m ≤ F − 1 [B21.n-dgt-b1]. The starting quiver therefore has tuple
b ( C ) = ( 1 , − 1 , − t , 2 , t − F , F − u ) = b ( I t , u ) , 1 ≤ t , u ≤ F − 1. \mathbf{b}(C)=(1,-1,-t,2,t-F,F-u)=\mathbf{b}(I_{t,u}),\qquad1\le t,u\le F-1. b ( C ) = ( 1 , − 1 , − t , 2 , t − F , F − u ) = b ( I t , u ) , 1 ≤ t , u ≤ F − 1.
These cases leave only A c A_c A c and I t , u I_{t,u} I t , u .
Case x = − b < 0 x=-b<0 x = − b < 0 , d = − D ≤ 0 d=-D\le0 d = − D ≤ 0
Here 1 ≤ b ≤ T 1\le b\le T 1 ≤ b ≤ T and 0 ≤ D ≤ T 0\le D\le T 0 ≤ D ≤ T . Put
h = e − [ − c ] + , g = f + b [ c ] + , z = g + ( b + D ) [ h ] + . h=e-[-c]_{+},\qquad g=f+b[c]_{+},\qquad z=g+(b+D)[h]_{+}. h = e − [ − c ] + , g = f + b [ c ] + , z = g + ( b + D ) [ h ] + .
In each of the eight sign cases of c c c , h h h and z z z , which are the claims [B22.paths-+++] through [B22.paths--],
b ( P ) = ( − 1 , b , − c , − D − b , h , g ) , b ( Q ) = ( 1 , − D , − c − [ − h ] + , D + b , − h , z ) , \mathbf{b}(P)=(-1,b,-c,-D-b,h,g),\qquad\mathbf{b}(Q)=(1,-D,-c-[-h]_{+},D+b,-h,z), b ( P ) = ( − 1 , b , − c , − D − b , h , g ) , b ( Q ) = ( 1 , − D , − c − [ − h ] + , D + b , − h , z ) ,
and two entries after the third mutation are
b 12 ( μ 3 Q ) = 1 − D ( D + b ) , b 24 ( μ 3 Q ) = − h + ( D + b ) [ z ] + . b_{12}(\mu_3Q)=1-D(D+b),\qquad b_{24}(\mu_3Q)=-h+(D+b)[z]_{+}. b 12 ( μ 3 Q ) = 1 − D ( D + b ) , b 24 ( μ 3 Q ) = − h + ( D + b ) [ z ] + .
All entries of C C C have absolute value at most T T T . Consequently P P P can reach height F F F only through
h = − F , g = F , or b + D = F . h=-F,\qquad g=F,\qquad\text{or}\qquad b+D=F. h = − F , g = F , or b + D = F .
We exclude these possibilities in that order, since they need not be disjoint.
If h = − F h=-F h = − F , then c , e < 0 c,e<0 c , e < 0 and g = z = f g=z=f g = z = f . The third height bound forces f ≤ 0 f\le0 f ≤ 0 [B22.hF-f], and then C C C is acyclic [B22.hF-acyclic], contrary to its nonacyclicity.
If g = F g=F g = F , then c > 0 c>0 c > 0 , and z ≤ F z\le F z ≤ F forces e ≤ 0 e\le0 e ≤ 0 [B22.gF-e]. The third height bound forces b = 1 b=1 b = 1 and D = 0 D=0 D = 0 [B22.gF-bD], and then e = 0 e=0 e = 0 [B22.gF-e0]. Hence C = ( 1 , − 1 , c , 0 , 0 , F − c ) C=(1,-1,c,0,0,F-c) C = ( 1 , − 1 , c , 0 , 0 , F − c ) with 0 < c < F 0<c<F 0 < c < F , which is acyclic [B22.gF-acyclic].
It remains to consider b + D = F b+D=F b + D = F . Since b ≤ T b\le T b ≤ T , we have D ≥ 1 D\ge1 D ≥ 1 . The third b 12 b_{12} b 12 bound forces D = 1 D=1 D = 1 and b = T b=T b = T [B22.bD-D], and the third b 24 b_{24} b 24 bound forces z ≤ 1 z\le1 z ≤ 1 [B22.bD-z]. The Pfaffian is now p = f + T e − c p=f+Te-c p = f + T e − c [B22.bD-pf]. If c > 0 c>0 c > 0 , then z ≤ 1 z\le1 z ≤ 1 forces e ≤ 0 e\le0 e ≤ 0 [B22.bD-cpos-e], and then p ≤ − T p\le-T p ≤ − T , contrary to (8) [B22.bD-cpos-p].
We may therefore put c = − t c=-t c = − t , where t ≥ 0 t\ge0 t ≥ 0 , so that z = f + F [ e − t ] + ≥ f z=f+F[e-t]_{+}\ge f z = f + F [ e − t ] + ≥ f . If f > 0 f>0 f > 0 , the inequality z ≤ 1 z\le1 z ≤ 1 forces f = 1 f=1 f = 1 and e ≤ t e\le t e ≤ t [B22.bD-cneg-f2, B22.bD-cneg-et]. The third b 24 b_{24} b 24 entry is then F + t − e F+t-e F + t − e , so e ≥ t e\ge t e ≥ t as well [B22.bD-cneg-b24, B22.bD-cneg-ete]. Thus e = t e=t e = t . If t > 0 t>0 t > 0 , the complete quiver is a vortex, with source 3 and directed triangle 1 → 2 → 4 → 1 1\to2\to4\to1 1 → 2 → 4 → 1 [B22.bD-vortex], and if t = 0 t=0 t = 0 , C C C is acyclic [B22.bD-t0]. Both are impossible.
Finally suppose f ≤ 0 f\le0 f ≤ 0 . Now p = f + T e + t p=f+Te+t p = f + T e + t [B22.bD-fneg-pf], so an integer e ≥ 2 e\ge2 e ≥ 2 would give p ≥ T p\ge T p ≥ T [B22.bD-fneg-e2], and e ≤ 1 e\le1 e ≤ 1 . If e ≤ 0 e\le0 e ≤ 0 , or if e = 1 e=1 e = 1 and t = f = 0 t=f=0 t = f = 0 , then C C C is acyclic [B22.bD-fneg-e0, B22.bD-fneg-e1-00]. Otherwise e = 1 e=1 e = 1 , and C C C has a single proper wiggle class, containing ⟨ 1 , 2 , 4 , 3 ⟩ \langle1,2,4,3\rangle ⟨ 1 , 2 , 4 , 3 ⟩ [B22.bD-order-tf, B22.bD-order-t0, B22.bD-order-f0]. Evaluation gives
m = T 2 + T + 3 + t ( t − 1 ) + f 2 + f ( T + 1 − T t ) > T m=T^2+T+3+t(t-1)+f^2+f(T+1-Tt)>T m = T 2 + T + 3 + t ( t − 1 ) + f 2 + f ( T + 1 − T t ) > T
[B22.bD-m, B22.bD-mbig]. This excludes the whole case x < 0 x<0 x < 0 , d ≤ 0 d\le0 d ≤ 0 .
Case x ≥ 0 x\ge0 x ≥ 0
The first mutation can reach height F F F only if c = − t < 0 c=-t<0 c = − t < 0 , where 1 ≤ t ≤ T 1\le t\le T 1 ≤ t ≤ T . Write w = f − x t w=f-xt w = f − x t and
z = w + [ − d ] + [ e − t ] + − [ d ] + [ t − e ] + . z=w+[-d]_{+}[e-t]_{+}-[d]_{+}[t-e]_{+}. z = w + [ − d ] + [ e − t ] + − [ d ] + [ t − e ] + .
In each of the eight sign cases of d d d , e − t e-t e − t and z z z , which are the claims [B23.paths-+++] through [B23.paths--],
b ( P ) = ( − 1 , − x , t , d , e − t , w ) , b ( Q ) = ( 1 , − x − [ − d ] + , min ( t , e ) , − d , t − e , z ) , \mathbf{b}(P)=(-1,-x,t,d,e-t,w),\qquad\mathbf{b}(Q)=(1,-x-[-d]_{+},\min(t,e),-d,t-e,z), b ( P ) = ( − 1 , − x , t , d , e − t , w ) , b ( Q ) = ( 1 , − x − [ − d ] + , min ( t , e ) , − d , t − e , z ) ,
and the entries we need after the third mutation are
b 12 ( μ 3 Q ) = 1 − ( x + [ − d ] + ) [ − d ] + , b_{12}(\mu_3 Q) = 1 - (x + [-d]_+)[-d]_+, b 12 ( μ 3 Q ) = 1 − ( x + [ − d ] + ) [ − d ] + ,
b 14 ( μ 3 Q ) = min ( t , e ) − ( x + [ − d ] + ) [ − z ] + , b_{14}(\mu_3 Q) = \min(t,e) - (x + [-d]_+)[-z]_+, b 14 ( μ 3 Q ) = min ( t , e ) − ( x + [ − d ] + ) [ − z ] + ,
b 24 ( μ 3 Q ) = t − e + [ − d ] + [ z ] + − [ d ] + [ − z ] + . b_{24}(\mu_3 Q) = t - e + [-d]_+[z]_+ - [d]_+[-z]_+. b 24 ( μ 3 Q ) = t − e + [ − d ] + [ z ] + − [ d ] + [ − z ] + .
The Pfaffian is p = f − x e − t d p = f - xe - td p = f − x e − t d [B23.pf]. Since every starting entry has absolute value at most T T T , the first high quiver must satisfy e − t = − F e - t = -F e − t = − F or w = − F w = -F w = − F .
First suppose e − t = − F e - t = -F e − t = − F . Put u = F − t ≥ 1 u = F - t \ge1 u = F − t ≥ 1 , so e = − u e = -u e = − u . Then z = w − [ d ] + F z = w - [d]_+F z = w − [ d ] + F , and the third b 14 b_{14} b 14 bound reads
( x + [ − d ] + ) [ − z ] + ≤ t . (20) (x + [-d]_+)[-z]_+ \le t. \tag*{(20)} ( x + [ − d ] + ) [ − z ] + ≤ t . (20)
If d = − D < 0 d = -D < 0 d = − D < 0 , the third b 24 b_{24} b 24 entry is F + D [ w ] + F + D[w]_+ F + D [ w ] + , so w ≤ 0 w \le0 w ≤ 0 [B23.eF-dneg-w]. Set v = − w ≥ 0 v = -w \ge0 v = − w ≥ 0 . Equation (20) gives ( x + D ) v ≤ t (x+D)v \le t ( x + D ) v ≤ t , and then x ≥ 1 x \ge1 x ≥ 1 would give p = x F + t D − v ≥ F p = xF +tD-v \ge F p = x F + t D − v ≥ F [B23.eF-dneg-pf, B23.eF-dneg-x]. Thus x = 0 x = 0 x = 0 and f = w ≤ 0 f = w \le0 f = w ≤ 0 , and C C C is acyclic [B23.eF-acyc1].
If d ≥ 0 d \ge0 d ≥ 0 , the second height bound gives w − d F ≥ − F w - dF \ge-F w − d F ≥ − F , which forces d ≤ 1 d \le1 d ≤ 1 since w ≤ T w \le T w ≤ T [B23.eF-dpos-d]. For d = 0 d = 0 d = 0 , equation (20) is x [ − w ] + ≤ t x[-w]_+ \le t x [ − w ] + ≤ t , and p = w + x F p = w + xF p = w + x F [B23.eF-d0-pf]. An x ≥ 2 x \ge2 x ≥ 2 is impossible, since p ≥ 2 F p \ge2F p ≥ 2 F if w ≥ 0 w \ge0 w ≥ 0 , and p ≥ 2 F − t > F p \ge2F-t > F p ≥ 2 F − t > F if w < 0 w < 0 w < 0 [B23.eF-d0-x2a, B23.eF-d0-x2b]. When x = 1 x = 1 x = 1 , the same inequality gives f = t + w ≥ 0 f = t+w \ge0 f = t + w ≥ 0 [B23.eF-d0-x1]. For d = 1 d = 1 d = 1 , the second height bound gives w ≥ 0 w \ge0 w ≥ 0 , and x ≥ 1 x \ge1 x ≥ 1 is impossible [B23.eF-d1-x]. Hence x = 0 x = 0 x = 0 and f = w ≥ 0 f = w \ge0 f = w ≥ 0 . The case x = d = 0 x = d = 0 x = d = 0 makes C C C acyclic [B23.eF-acyc2]. Thus only ( x , d ) = ( 0 , 1 ) (x,d) = (0,1) ( x , d ) = ( 0 , 1 ) or ( 1 , 0 ) (1,0) ( 1 , 0 ) remains, with f > 0 f > 0 f > 0 , because f = 0 f = 0 f = 0 is again acyclic [B23.eF-acyc3, B23.eF-acyc4]. In both cases C C C has a single proper wiggle class, containing ω 0 = ⟨ 1 , 2 , 3 , 4 ⟩ \omega_0 = \langle1,2,3,4\rangle ω 0 = ⟨ 1 , 2 , 3 , 4 ⟩ [B23.eF-ord01, B23.eF-ord10], and
m = 2 + t 2 + u 2 + t u + f 2 − λ f , λ = { F , ( x , d ) = ( 0 , 1 ) , t , ( x , d ) = ( 1 , 0 ) , m = 2 + t^2 + u^2 + tu + f^2 - \lambda f,\qquad
\lambda=
\begin{cases}
F, & (x,d) = (0,1),\\
t, & (x,d) = (1,0),
\end{cases} m = 2 + t 2 + u 2 + t u + f 2 − λ f , λ = { F , t , ( x , d ) = ( 0 , 1 ) , ( x , d ) = ( 1 , 0 ) ,
which is at least F F F in both cases, contradicting m ≤ T m \le T m ≤ T , by [B23.eF-m01, B23.eF-m01-big] and [B23.eF-m10, B23.eF-m10-big]. This excludes e − t = − F e - t = -F e − t = − F .
We may now suppose w = − F w = -F w = − F and e − t > − F e - t > -F e − t > − F . Since f = x t − F > − F f = xt - F > -F f = x t − F > − F , we have x ≥ 1 x \ge1 x ≥ 1 [B23.wF-x]. Also ∣ e − t ∣ < F |e-t| < F ∣ e − t ∣ < F and ∣ min ( t , e ) ∣ < F |\min(t,e)| < F ∣ min ( t , e ) ∣ < F . For d = − D < 0 d = -D < 0 d = − D < 0 ,
z = − F + D [ e − t ] + , z = -F + D[e-t]_+, z = − F + D [ e − t ] + ,
and the second quiver can be high only if x + D = F x + D = F x + D = F or z = ± F z = \pm F z = ± F . If x + D = F x + D = F x + D = F , the third b 12 b_{12} b 12 bound gives D = 1 D = 1 D = 1 [B23.wF-dneg-D], the third b 14 b_{14} b 14 bound then gives z ≥ − 1 z \ge-1 z ≥ − 1 [B23.wF-dneg-z], and z = − F + [ e − t ] + ≥ − 1 z = -F + [e-t]_+ \ge-1 z = − F + [ e − t ] + ≥ − 1 is impossible because e − t ≤ F − 2 e-t \le F-2 e − t ≤ F − 2 [B23.wF-dneg-et]. If z = − F z = -F z = − F , the third b 14 b_{14} b 14 entry is less than − F -F − F [B23.wF-dneg-zmF]. If z = F z = F z = F , then e − t > 0 e-t > 0 e − t > 0 , the third b 24 b_{24} b 24 bound gives D = 1 D = 1 D = 1 [B23.wF-dneg-zF-D], and z = − F + ( e − t ) = F z = -F + (e-t) = F z = − F + ( e − t ) = F is impossible [B23.wF-dneg-zF]. All possibilities with d < 0 d < 0 d < 0 are excluded.
For d ≥ 0 d \ge0 d ≥ 0 , we have z = − F − d [ t − e ] + ≤ − F z = -F - d[t-e]_+ \le-F z = − F − d [ t − e ] + ≤ − F . The second height bound therefore gives z = − F z = -F z = − F and d [ t − e ] + = 0 d[t-e]_+ = 0 d [ t − e ] + = 0 [B23.wF-dpos-z]. The third b 14 b_{14} b 14 bound min ( t , e ) − x F ≥ − F \min(t,e)-xF \ge-F min ( t , e ) − x F ≥ − F forces x = 1 x = 1 x = 1 and e ≥ 0 e \ge0 e ≥ 0 [B23.wF-dpos-x, B23.wF-dpos-e]. If d > 0 d > 0 d > 0 , then e ≥ t e \ge t e ≥ t , and the third b 24 b_{24} b 24 bound forces d = 1 d = 1 d = 1 and e = t e = t e = t [B23.wF-dpos-d, B23.wF-dpos-e2]. But then p = − F − t p = -F-t p = − F − t , contrary to (8) [B23.wF-d1-pf, B23.wF-d1-p].
Only d = 0 d = 0 d = 0 remains. Put u = F − t u = F-t u = F − t , so bc ( C ) = ( 1 , 1 , − t , 0 , e , − u ) \operatorname{bc}(C) = (1,1,-t,0,e,-u) bc ( C ) = ( 1 , 1 , − t , 0 , e , − u ) with t , u ≥ 1 t,u \ge1 t , u ≥ 1 and e ≥ 0 e \ge0 e ≥ 0 . If e = 0 e = 0 e = 0 , C C C is acyclic [B23.wF-d0-acyc]. For e > 0 e > 0 e > 0 , the unique proper wiggle class contains ⟨ 1 , 2 , 3 , 4 ⟩ \langle1,2,3,4\rangle ⟨ 1 , 2 , 3 , 4 ⟩ [B23.wF-d0-order], and evaluation gives m = 2 + t 2 + u 2 + e 2 + t u − t e > F m = 2 + t^2 + u^2 + e^2 + tu - te > F m = 2 + t 2 + u 2 + e 2 + t u − t e > F [B23.wF-d0-m, B23.wF-d0-big]. This final contradiction excludes every case with x ≥ 0 x \ge0 x ≥ 0 , including zero entries. Together with Appendices § 8 .§ 2.1 and § 8 .§ 2.2 , this shows that C C C is A c A_c A c or I t , u I_{t,u} I t , u .
The two remaining cases
For A c A_c A c , with b ( A c ) = ( 1 , − 2 , c , 1 , 0 , F − 2 c ) \mathbf{b}(A_c)=(1,-2,c,1,0,F-2c) b ( A c ) = ( 1 , − 2 , c , 1 , 0 , F − 2 c ) and 1 ≤ c ≤ T 1\le c\le T 1 ≤ c ≤ T , the quivers after [ 1 ] [1] [ 1 ] , [ 1 , 2 ] [1,2] [ 1 , 2 ] , [ 1 , 2 , 3 ] [1,2,3] [ 1 , 2 , 3 ] and [ 1 , 2 , 3 , 1 ] [1,2,3,1] [ 1 , 2 , 3 , 1 ] are high, and the quiver after [ 1 , 2 , 3 , 1 , 3 ] [1,2,3,1,3] [ 1 , 2 , 3 , 1 , 3 ] is low [B3.A-segment, B3.A-low-lo0, B3.A-low-hi0, B3.A-low-lo1, B3.A-low-hi1]. After [ 1 , 2 , 3 ] [1,2,3] [ 1 , 2 , 3 ] , mutations at 2 , 4 2,4 2 , 4 create entries 2 F − c > F 2F-c>F 2 F − c > F and F 2 − 1 > F F^2-1>F F 2 − 1 > F , respectively [B3.A-forced1, B3.A-forced1b, B3.A-forced-2Fc, B3.A-forced-F2]. Repeating the last mutation would cancel, so the next vertex must be 1 1 1 . After [ 1 , 2 , 3 , 1 ] [1,2,3,1] [ 1 , 2 , 3 , 1 ] , mutations at 2 , 4 2,4 2 , 4 create entries 2 F − c > F 2F-c>F 2 F − c > F and − 1 − F ( F − c ) < − F -1-F(F-c)<-F − 1 − F ( F − c ) < − F , so the next vertex must be 3 3 3 [B3.A-forced2, B3.A-forced2b, B3.A-forced-FFc]. Thus the first return is exactly [ 1 , 2 , 3 , 1 , 3 ] [1,2,3,1,3] [ 1 , 2 , 3 , 1 , 3 ] . All three quivers along [ 2 , 1 , 3 ] [2,1,3] [ 2 , 1 , 3 ] are low by the same claims [B3.A-replacement]. For the relabeling π 123 \pi_{123} π 123 [B3.A-relabel],
μ [ 2 , 1 , 3 ] A c = ( μ [ 1 , 2 , 3 , 1 , 3 ] A c ) π 123 . \mu_{[2,1,3]}A_c=(\mu_{[1,2,3,1,3]}A_c)^{\pi_{123}}. μ [ 2 , 1 , 3 ] A c = ( μ [ 1 , 2 , 3 , 1 , 3 ] A c ) π 123 .
This replacement removes four high quivers, and the tail is transported by (3) .
For I t , u I_{t,u} I t , u , with b ( I t , u ) = ( 1 , − 1 , − t , 2 , t − F , F − u ) \mathbf{b}(I_{t,u})=(1,-1,-t,2,t-F,F-u) b ( I t , u ) = ( 1 , − 1 , − t , 2 , t − F , F − u ) , exactly the quivers after [ 1 ] [1] [ 1 ] and [ 1 , 2 ] [1,2] [ 1 , 2 ] are high, and the quiver after [ 1 , 2 , 3 ] [1,2,3] [ 1 , 2 , 3 ] is low [B3.I-segment], so the first return is [ 1 , 2 , 3 ] [1,2,3] [ 1 , 2 , 3 ] . Both replacement mutation sequences terminate at the quiver J J J with b ( J ) = ( 1 , − 2 , F − u , 1 , u , t − F ) = b ( ( μ [ 1 , 2 , 3 ] I t , u ) π 123 ) \mathbf{b}(J)=(1,-2,F-u,1,u,t-F)=\mathbf{b}((\mu_{[1,2,3]}I_{t,u})^{\pi_{123}}) b ( J ) = ( 1 , − 2 , F − u , 1 , u , t − F ) = b (( μ [ 1 , 2 , 3 ] I t , u ) π 123 ) [B3.I-endpoint, B3.I-tgu, B3.I-ugt]. Every quiver along them is low, using T ≥ 3 T\ge3 T ≥ 3 [B3.I-low-tgu-lo0, ..., B3.I-low-ugt-hi5]. Thus both replacement paths, including their common endpoint J J J , are entirely low and each removes two high quivers.
Finally, suppose t = u t=u t = u . The Pfaffian of I t , t I_{t,t} I t , t is p = − 2 t p=-2t p = − 2 t [B3.I-tt-pf]. Thus (8) gives 4 t < m ≤ F − 1 4t<m\le F-1 4 t < m ≤ F − 1 , and in particular k = F − t ≥ 2 k=F-t\ge2 k = F − t ≥ 2 [B3.I-tt-k]. The full triangle on { 2 , 3 , 4 } \{2,3,4\} { 2 , 3 , 4 } is an oriented cycle with multiplicities ( 2 , k , k ) (2,k,k) ( 2 , k , k ) [B3.I-tt-triangle], whose Markov constant is 2 2 + k 2 + k 2 − 2 k 2 = 4 2^2+k^2+k^2-2k^2=4 2 2 + k 2 + k 2 − 2 k 2 = 4 [B3.I-tt-markov]. By Proposition 2.1 , this triangle is mutation-cyclic, contradicting mutation-acyclicity of the whole quiver. So t ≠ u t\ne u t = u , and Proposition 4.7 is proved. □
Use of AI
After being prompted at length by the authors, the main results were discovered by GPT-Astra (OpenAI) and the original statements were formalized in Lean (https://github.com/KTKAW/rank4-paper ). The results follow from many well-known results in the literature, along with the AI-discovery of the family Q ( t ) Q(t) Q ( t ) and many case checks carried out by AI systems. The exact checks in all of the appendix calculations are also verified by Python scripts. The text in this article was entirely organized and reviewed by humans. Significant portions of the text were generated, reviewed, or edited by AI. There was significant effort put in by the human team to generalize the results as far as possible, to simplify the proofs, to give appropriate credit to the human results that came before, and to bring the exposition up to standard. Centre for Theoretical Physics and Astronomy, Queen Mary University of London, London E1 4NS, United Kingdom Email address: k.t.k.armstrong-williams@qmul.ac.uk
Institute of Mathematics, Statistics and Scientific Computing, University of Campinas (Unicamp), Campinas 13083-859, Brazil Email address: ehirst@unicamp.br
Institute for Computer-Aided Reasoning in Mathematics, Carnegie Mellon University, 4720 Forbes Avenue, Pittsburgh, PA 15213, USA Email address: jackson@icarm.io
Department of Mathematics, University of Connecticut, Storrs, CT 06269, USA; Korea Institute for Advanced Study, Seoul 02455, Republic of Korea Email address: khlee@math.uconn.edu