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.txt,
E6_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.cpp
These 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, the
number 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 subdiagram
of order 10 of the resulting matrix must be s-decomposable. This gives clear bounds on the number
of 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.