# Quivers of finite mutation type

Quiver mutation is described in arXiv:0807.1960.

Question: describe all finite mutation classes of quivers.

A quiver has finite mutation class if and only if it is one of the following:

1.      A quiver with two vertices.

2.      A quiver associated with a triangulation of a two-dimensional bordered surface (see  arXiv:math/0608367 ).

3.      A quiver mutation equivalent to one of the list of 11 quivers (see arXiv.math/0811.1703).

To prove the result we used the following two C++ programs "quiver.cpp" and "min_inf.cpp" and
various input files.

The programs can be compiled with g++ compiler.

You can download the programs and required input files by clicking on the links in the description below.

1. quiver.cpp
The input data for program "quiver.cpp" is a file consisting of skew-symmetric matrices, where each matrix
is preceded by the number of its rows ("SizeOfMatrix").
The output file consists of the following data: for each input matrix A the output file contains:
-- size of A
-- serial number of matrix A in the input file
-- matrix A
-- all the lines of length (size of A) of integers from -2 to 2, such that a skew-symmetric
matrix A' of size (size of A)+1 composed of A, this line, and corresponding column
(to keep skew-symmetry)
is finite-mutational
-- possibly some additional lines of length (size of A) of integers from -2 to 2.

In other words, the program gives all matrices of size (size of A)+1 which contain A and could be
mutation-finite. The further work in detecting different mutation-finite classes of matrices is done
by using Java applet by B.Keller: for any line from the answer we check if the corresponding matrix
is really mutation-finite, and check if it is mutation-equivalent to any of matrices obtained before.

The program proceeds as follows. For each matrix (=quiver) from the input file it adds one new vertex and
joins this new vertex with the old ones by edges of multiplicity at most 2 in all possible ways. For each
matrix obtained the program checks if this matrix is finite-mutational. This check involves random mutations:
the program makes several random mutations (more precisely, the number is equal to “NumberOfRandomMutations"
defined in the main body, NumberOfRandomMutations =3000, by default),
and for any intermediate result verifies that the matrix does not contain entries exceeding 2.
If there are such entries, the matrix is mutation-infinite. If none of the, say,
3000 mutation-equivalent matrices have such entries, the corresponding matrix appears in the answer as a
matrix which is suspected to be mutation-finite.

Notice that the results of the program on the same file may differ since random mutations are involved.
However, if the value of NumberOfRandomMutations is relatively high (e.g. 3000 is enough) then no
mutation-infinite answers have been seen yet.

The following input files are contained in the directory:
-- input3.txt: all the mutation-finite matrices of size 3 (representing distinct mutation classes);
-- input4.txt: the same of size 4, obtained as the result of the program applied to input3.txt and
then shortened by using B.Keller’s applet;
-- input5.txt, input6.txt : the same of sizes 5 and 6, respectively;
-- E6.txt, E7.txt, E8.txt, E6_affine.txt, E7_affine.txt, E8_affine.txtE6_1_1.txt, E7_1_1.txt, E8_1_1.txt, X6.txt, X7.txt:
totally 11 files containing one non-decomposable mutation-finite matrix each.
-- 11nondec.txt: all eleven exceptional matrices in one file.

2. min_inf.cpp
The input data for program “min_inf.cpp” is a qmu-file  produced by B.Keller’s applet containing
complete mutation class of some indecomposable matrix A (i.e., corresponding to connected quiver).
The size of A should exceed 3.

The output data is a file containing all the indecomposable matrices A’ of size (size of A)+1

satisfying the following conditions:

-- A' contains a submatrix  that is mutation-equivalent to A;

-- Any principal submatrix of A' of size (size of A) could be mutation-finite
(i.e., large number of random mutations did not produce entries exceeding 2).

The data is presented in the following way:

-- serial number of matrix A in the input file;

-- lines with answers (as in "quiver.cpp").

The algorithm is similar to the program “quiver.cpp”. However, there is one refinement to make the algorithm faster.

According to the list of connected mutation-finite quivers of order 4, none of them has a vertex

incident to two double edges or more. Therefore, we do not need to check matrices A' where the new vertex

is incident to two or more double edges: any indecomposable submatrix of order 4 containing the corresponding

submatrix of size 3 with two double edges will be mutation-infinite.

There is an input file E8_11.qmu in the directory, it contains the mutation class of “E_8^(1,1)”. The program

applied to this file gives an empty result (theoretically, due to randomness, it may produce some nonempty lines,
but, practically, it never happened for parameter value NumberOfRandomMutations=3000).

Warning: the running time of “min_inf.cpp” is pretty long:
depending on compiler version and processor speed, it may take from several hours
to several days to run.

```Diagrams of finite mutation type

The directory consists of four C++ codes "diagram-l.cpp", "diagram-s.cpp", "min_inf_d.cpp",
and "check_unfolding.cpp", and various input files.
The source codes can be compiled with g++ compiler.

1. diagram-l.cpp and diagram-s.cppThese two programs are almost identical. The program "diagram-l.cpp" is a
version of "diagram-s.cpp" adopted to work faster on matrices of size 5x5 or more.

The input data for both programs is a file consisting of skew-symmetric matrices,
where each matrix
is preceeded by the number of its rows ("SizeOfMatrix"),
and followed by a skew-symmetrizing vector (array "e[]").

The output file consists of the following data: for each input matrix A the output file contains:
-- size of A
-- serial number of matrix A in the input file
-- matrix A
-- all the pairs of line and column of length (size of A) of integers from -4 to 4, such that a skew-symmetrizable
matrix A' of size (size of A)+1 composed of A, this line and this column, is mutation-finite, together with corresponding skew-symmetrizing vectors
-- possibly some additional pairs of line and column of length (size of A) of integers from -4 to 4.

In other words, the program produces all matrices of size (size of A)+1 which contain A and could be
mutation-finite. The further work in detecting different mutation-finite classes of matrices is done
by using Java applet by B.Keller: for any line+column from the answer we check whether the corresponding matrix
is really mutation-finite, and check if it is mutation-equivalent to any of matrices obtained before.
The program proceeds as follows. For each matrix from the input file it adds one new vertex and
joins this new vertex with the old ones by edges of weight at most 4 in all possible ways. For each
matrix obtained the program checks whether this matrix is skew-symmetrizable and finite-mutational. This check involves random mutations: the program makes several random mutations (more precisely, thenumber is equal to "NumberOfRandomMutations" defined in the main body, 3000 by defaut), and for any intermediate result verifies that a product of any two entries symmetric with respect to main diagonal is not less than negative 4. If there are such entries, the matrix is mutation-infinite. If none of the, say,
3000 mutation-equivalent matrices have such entries, the corresponding matrix appears in the answer as a
matrix which is suspected to be mutation-finite.

Notice that the results of the program on the same file may differ since random mutations are involved.
However, if the value of NumberOfRandomMutations is relatively high (e.g. 3000 is enough) then no
mutation-infinite answers have been seen yet.To reduce the number of answers belonging to the same mutation class (or differing by permutation of rows and columns),we add some partial check: we compare every new matrix mutation-finite with some number (NumberOfRandomMutationsN, defined in the main body) of mutations of all the previously found matrices (including those obtained by renumbering of rows and columns).This hugely reduces the number of repetitions, but not completely. Some work involving Java applet by B.Keller is needed anyway. The program produces another one output file, "input_next.txt" -- this is the same as the standard output, but in the format of input file for the program. The following input files are contained in the directory:
--  input2.txt: all the mutation-finite matrices of size 2 (representing distinct mutation classes) with determinant between 2 and 4, up to symmetry;
--  input3.txt: the same of size 3, obtained as the result of the program applied to input2.txt;
--  input4.txt, input5.txt: the same of size 4,5 respectively;
--  input6.txt: the same of size 6, and then shortened by using B.Keller's applet;
2.  check_unfolding.cpp The input data is a file containg pairs of matrices in the following format:number of pair, size of skew-symmetrizable matrix, skew-symmetrizable matrix, depth of the mutation class, skew-symmetrizing vector, size of skew-symmetric matrix, skew-symmetric matrix. The first matrix must be mutation-finite.For every such pair from the input file the program verifies whether the second matrix is the unfolding for the first.The method is straightforward: we mutate the first matrix to cover the mutation class, perform the induced composite mutations of the second one, and then check whether corresponding pairs of matrices satisfy the assertions of the definition of unfolding. The output file contains the initial matrices and either FAIL or OK for each of the pairs depending whether the pair provides an unfolding or not.  There is an input file  unfoldings.txt in the directory, the file contains all mutation-finite non-skew-symmetric matrices with non-decomposable diagrams and their unfoldings.
3. min_inf_d.cpp

The input data for program "min_inf_d.cpp" is a .qmu file produced by B.Keller's applet containing
complete mutation class of some matrix A. The size of matrix must exceed 6 (see details below).

The output data is a file containing all the indecomposable matrices A' of size (size of A)+1
satisfying the following conditions:
-- A' contains one of the matrix mutation-equivalent to A as a submatrix;
-- any principal submatrix of A' of size (size of A) could be mutation-finite (i.e., many random mutations
did not found out pairs of symmetric entries with product less than negative 4).
The data is presented in the following way:
-- serial number of matrix A in the input file;
-- pairs line+column with answers (as in "diagram-l.cpp");
The algorithm is similar to the preceeding program. However, there is one refinement to speed up.
According to Theorem 5.13, every non-skew-symmetric subdiagramof order 10 of the resulting matrix must be s-decomposable. This gives clear bounds on the numberof edges in the diagram with weights 2,3, and 4 (as well as combinations of them). More precisely, the additional vertex is not incident to any edge of weight 3, the number of edges of weight two does not exceed 4, etc.
There is an input file E8_11.qmu in the directory, it contains the mutation class of E_8^(1,1). The program
applied to this file gives an empty result (it may produce some lines due to use of random procedure, but
for NumberOfRandomMutations=3000 it has not done that yet). However, the program takes time: depending on
compiler and machine, it may take from several hours to several days to run.
```