Primality of Polyominoes
In the paper C. Mascia, G. Rinaldo, and F. Romeo, Primality of multiply connected polyominoes, we used symbolic computation to obtain the following (see Theorem 3.9 in the paper)
Theorem
Let P be a polyomino with rank \(\leq 14\). The following conditions are equivalent:
- \(I_P\) is prime;
- P contains no zig-zag walk.
In short the algorithm is defined by the following 3 Steps :
- Step 1
- Compute all multiply connected polyominoes with rank \(\leq 14\);
- Step 2
- Compute the set NonPrime whose elements are the ones whose associated ideals are not prime;
- Step 3
- Check if all the elements of NonPrime have a zig-zag walk.
In this page we describe the algorithm (Step 1, Step 2 and Step 3) and we give the results of our computation together with the source code. We refer to the article for an in-depth description of the notation and results.
Step 1. Compute all multiply connected polyominoes with rank \(\leq 14\).
To compute all multiply connected polyominoes with a given rank \(n\) we use the following algorithm:
- Compute all polyominoes with rank \(n-1\);
- Attach a cell to each polyomino generated in the previous step;
- Remove the ones that are congruent by isometries (e.g. translations, rotations, reflections and glide reflections);
- Discard the simple ones due to the connectedness property of the non-cells of the polyomino.
To this purpose we used Java that permits a good definitions of combinatorial structures, and a very nice portability on different platforms.
Step 2. Compute the set NonPrime whose elements are the ones whose associated ideals are not prime.
To obtain this set we used the package Binomials.m2, developed by Thomas Kahle, that implements in efficient way, primality tests and other routines in Macaulay2, when we have to work with binomials.
Step 3. Check if all the elements of NonPrime have a zig-zag walk.
In this last step we check if in the set of non-prime ideals, resulted by the previous step, there exists a polyomino that does not contain a zig-zag walk.
If such element does not occur, then our condition on the existence of zig-zag walk is not only necessary but also sufficient for the primality, proving the Theorem.
We implemented this algorithm, as in the first step, in Java.
Implementation of the algorithm and results.
In this section we give the results of our computation by the routines that we implemented in Java and Macaulay2 whose sources are downloadable from here.
The program uses only standard library and with some effort can work on any platforms. To use it you have to download, and extract by
tar -xzvf polyominoesPrimality.tgz
move to the folder
cd polyominoesPrimality
and then compile the Java bytecode by
javac Main.java
Now we are ready to compute the multiply connected polyominoes with a given rank. We show the input and the output in the console. As an example we calculate the case with rank 9. We run the program
java Main --findMaximalInnerIntervalsNotSimple --rank 9 --outputfile MaximalInnerIntervalNotSimple.m2
This program generates the maximal inner intervals of not simple polyominoes, namely multiply connected ones, with rank 9, and writes the output on the file MaximalInnerIntervalNotSimple.m2.
Now we can filter this file by Macaulay2 according to Step 2, that is we want to compute the polyomino ideals that are not prime by the following command
M2 NonPrime.m2
The result is the file input.txt containing:
{0, 7}
That are the non-prime polyominoes within the rank 9 multiply connected ones. Now we end with the last step. We execute the command:
java Main --testConjecture --rank 9 --inputfile input.txt
whose result is:
Conjecture true for all the polyominoes with rank 9
To show the polyominoes with rank 9 we use the following command:
java Main --generateNotSimple --rank 9
whose result is (observe that in position 0 and 7 we have the polyominoes with zig-zag walks within this set):
(0, 1)(0, 2)(1, 0)(1, 1)(1, 3)(2, 1)(2, 2)(2, 3)(3, 2)
+---+---+
|/// ///|
+---+---+ +---+
|///| |/// ///|
+ +---+ +---+
|/// /// ///|
+---+ +---+
|///|
+---+
(0, 0)(0, 1)(0, 2)(1, 0)(1, 2)(1, 3)(2, 1)(2, 2)(3, 1)
+---+
|///|
+---+ +---+
|/// /// ///|
+ +---+ +---+
|///| |/// ///|
+ +---+---+---+
|/// ///|
+---+---+
(0, 0)(0, 1)(0, 2)(1, 1)(1, 3)(2, 1)(2, 2)(2, 3)(3, 2)
+---+---+
|/// ///|
+---+---+ +---+
|///| |/// ///|
+ +---+ +---+
|/// /// ///|
+ +---+---+
|///|
+---+
(0, 0)(0, 1)(0, 2)(0, 3)(1, 1)(1, 3)(1, 4)(2, 2)(2, 3)
+---+
|///|
+---+ +---+
|/// /// ///|
+ +---+ +
|///| |///|
+ +---+---+
|/// ///|
+ +---+
|///|
+---+
(0, 1)(0, 2)(1, 0)(1, 1)(1, 3)(2, 1)(2, 2)(2, 3)(3, 1)
+---+---+
|/// ///|
+---+---+ +
|///| |///|
+ +---+ +---+
|/// /// /// ///|
+---+ +---+---+
|///|
+---+
(0, 0)(0, 1)(0, 2)(0, 3)(1, 0)(1, 1)(1, 3)(2, 1)(2, 2)
+---+---+
|/// ///|
+ +---+---+
|///| |///|
+ +---+ +
|/// /// ///|
+ +---+
|/// ///|
+---+---+
(0, 0)(0, 1)(0, 2)(1, 0)(1, 2)(1, 3)(2, 0)(2, 1)(2, 2)
+---+
|///|
+---+ +---+
|/// /// ///|
+ +---+ +
|///| |///|
+ +---+ +
|/// /// ///|
+---+---+---+
(0, 1)(0, 2)(0, 3)(1, 0)(1, 1)(1, 3)(1, 4)(2, 1)(2, 2)
+---+
|///|
+---+ +
|/// ///|
+ +---+---+
|///| |///|
+ +---+ +
|/// /// ///|
+---+ +---+
|///|
+---+
(0, 0)(0, 1)(0, 2)(1, 0)(1, 1)(1, 3)(2, 1)(2, 2)(2, 3)
+---+---+
|/// ///|
+---+---+ +
|///| |///|
+ +---+ +
|/// /// ///|
+ +---+
|/// ///|
+---+---+
(0, 0)(0, 1)(0, 2)(1, 0)(1, 2)(1, 3)(1, 4)(2, 1)(2, 2)
+---+
|///|
+ +
|///|
+---+ +---+
|/// /// ///|
+ +---+ +
|///| |///|
+ +---+---+
|/// ///|
+---+---+
(0, 0)(0, 1)(0, 2)(1, 0)(1, 2)(1, 3)(2, 1)(2, 2)(3, 2)
+---+
|///|
+---+ +---+---+
|/// /// /// ///|
+ +---+ +---+
|///| |///|
+ +---+---+
|/// ///|
+---+---+
(0, 0)(0, 1)(0, 2)(1, 0)(1, 2)(2, 1)(2, 2)(2, 3)(3, 1)
+---+
|///|
+---+---+ +
|/// /// ///|
+ +---+ +---+
|///| |/// ///|
+ +---+---+---+
|/// ///|
+---+---+
(0, 0)(0, 1)(1, 1)(1, 2)(1, 3)(2, 1)(2, 3)(3, 1)(3, 2)
+---+---+
|/// ///|
+ +---+---+
|///| |///|
+---+ +---+ +
|/// /// /// ///|
+ +---+---+---+
|///|
+---+
(0, 0)(0, 1)(0, 2)(1, 0)(1, 2)(2, 1)(2, 2)(2, 3)(3, 3)
+---+---+
|/// ///|
+---+---+ +---+
|/// /// ///|
+ +---+ +
|///| |///|
+ +---+---+
|/// ///|
+---+---+
(0, 0)(0, 1)(0, 2)(1, 0)(1, 2)(2, 1)(2, 2)(3, 2)(3, 3)
+---+
|///|
+---+---+---+ +
|/// /// /// ///|
+ +---+ +---+
|///| |///|
+ +---+---+
|/// ///|
+---+---+
(0, 0)(0, 1)(0, 2)(0, 3)(1, 0)(1, 1)(1, 3)(2, 2)(2, 3)
+---+---+---+
|/// /// ///|
+ +---+ +
|///| |///|
+ +---+---+
|/// ///|
+ +
|/// ///|
+---+---+
(0, 0)(0, 1)(0, 2)(0, 3)(0, 4)(1, 0)(1, 2)(2, 0)(2, 1)
+---+
|///|
+ +
|///|
+ +---+
|/// ///|
+ +---+---+
|///| |///|
+ +---+ +
|/// /// ///|
+---+---+---+
(0, 0)(0, 1)(0, 2)(0, 3)(0, 4)(1, 0)(1, 2)(2, 1)(2, 2)
+---+
|///|
+ +
|///|
+ +---+---+
|/// /// ///|
+ +---+ +
|///| |///|
+ +---+---+
|/// ///|
+---+---+
(0, 1)(0, 2)(1, 0)(1, 2)(2, 0)(2, 1)(2, 2)(2, 3)(3, 2)
+---+
|///|
+---+---+ +---+
|/// /// /// ///|
+ +---+ +---+
|///| |///|
+---+---+ +
|/// ///|
+---+---+
(0, 0)(0, 1)(0, 2)(1, 0)(1, 2)(2, 1)(2, 2)(2, 3)(3, 2)
+---+
|///|
+---+---+ +---+
|/// /// /// ///|
+ +---+ +---+
|///| |///|
+ +---+---+
|/// ///|
+---+---+
(0, 0)(0, 1)(0, 2)(0, 3)(1, 0)(1, 2)(2, 1)(2, 2)(3, 2)
+---+
|///|
+ +---+---+---+
|/// /// /// ///|
+ +---+ +---+
|///| |///|
+ +---+---+
|/// ///|
+---+---+
(0, 0)(0, 1)(0, 2)(1, 1)(1, 3)(2, 1)(2, 2)(2, 3)(3, 1)
+---+---+
|/// ///|
+---+---+ +
|///| |///|
+ +---+ +---+
|/// /// /// ///|
+ +---+---+---+
|///|
+---+
(0, 0)(0, 1)(0, 2)(0, 3)(0, 4)(1, 1)(1, 3)(2, 1)(2, 2)
+---+
|///|
+ +---+
|/// ///|
+ +---+---+
|///| |///|
+ +---+ +
|/// /// ///|
+ +---+---+
|///|
+---+
(0, 0)(0, 1)(0, 2)(0, 3)(1, 0)(1, 2)(2, 0)(2, 1)(2, 2)
+---+
|///|
+ +---+---+
|/// /// ///|
+ +---+ +
|///| |///|
+ +---+ +
|/// /// ///|
+---+---+---+
(0, 0)(0, 1)(0, 2)(0, 3)(1, 0)(1, 2)(2, 0)(2, 1)(3, 0)
+---+
|///|
+ +---+
|/// ///|
+ +---+---+
|///| |///|
+ +---+ +---+
|/// /// /// ///|
+---+---+---+---+
(0, 0)(0, 1)(0, 2)(0, 3)(1, 1)(1, 3)(2, 2)(2, 3)(2, 4)
+---+
|///|
+---+---+ +
|/// /// ///|
+ +---+ +
|///| |///|
+ +---+---+
|/// ///|
+ +---+
|///|
+---+
(0, 0)(0, 1)(0, 2)(0, 3)(1, 0)(1, 2)(2, 0)(2, 1)(3, 1)
+---+
|///|
+ +---+
|/// ///|
+ +---+---+---+
|///| |/// ///|
+ +---+ +---+
|/// /// ///|
+---+---+---+
(0, 0)(0, 1)(0, 2)(0, 3)(1, 1)(1, 3)(1, 4)(2, 1)(2, 2)
+---+
|///|
+---+ +
|/// ///|
+ +---+---+
|///| |///|
+ +---+ +
|/// /// ///|
+ +---+---+
|///|
+---+
(0, 0)(0, 1)(0, 2)(0, 3)(1, 0)(1, 2)(2, 1)(2, 2)(3, 1)
+---+
|///|
+ +---+---+
|/// /// ///|
+ +---+ +---+
|///| |/// ///|
+ +---+---+---+
|/// ///|
+---+---+
(0, 0)(0, 1)(0, 2)(0, 3)(1, 0)(1, 2)(2, 1)(2, 2)(2, 3)
+---+ +---+
|///| |///|
+ +---+ +
|/// /// ///|
+ +---+ +
|///| |///|
+ +---+---+
|/// ///|
+---+---+
(0, 0)(0, 1)(0, 2)(0, 3)(1, 2)(1, 4)(2, 2)(2, 3)(2, 4)
+---+---+
|/// ///|
+---+---+ +
|///| |///|
+ +---+ +
|/// /// ///|
+ +---+---+
|///|
+ +
|///|
+---+
(0, 0)(0, 1)(0, 2)(1, 1)(1, 3)(2, 1)(2, 2)(2, 3)(3, 3)
+---+---+---+
|/// /// ///|
+---+---+ +---+
|///| |///|
+ +---+ +
|/// /// ///|
+ +---+---+
|///|
+---+
(0, 0)(0, 1)(0, 2)(1, 1)(1, 3)(1, 4)(2, 1)(2, 2)(2, 3)
+---+
|///|
+ +---+
|/// ///|
+---+---+ +
|///| |///|
+ +---+ +
|/// /// ///|
+ +---+---+
|///|
+---+
(0, 0)(0, 1)(0, 2)(1, 0)(1, 2)(1, 3)(2, 0)(2, 1)(2, 3)
+---+---+
|/// ///|
+---+ +---+
|/// ///|
+ +---+---+
|///| |///|
+ +---+ +
|/// /// ///|
+---+---+---+
(0, 0)(0, 1)(0, 2)(1, 0)(1, 2)(1, 3)(1, 4)(2, 0)(2, 1)
+---+
|///|
+ +
|///|
+---+ +
|/// ///|
+ +---+---+
|///| |///|
+ +---+ +
|/// /// ///|
+---+---+---+
(0, 0)(0, 1)(0, 2)(1, 0)(1, 2)(1, 3)(2, 0)(2, 1)(3, 1)
+---+
|///|
+---+ +
|/// ///|
+ +---+---+---+
|///| |/// ///|
+ +---+ +---+
|/// /// ///|
+---+---+---+
(0, 0)(0, 1)(0, 2)(0, 3)(1, 0)(1, 3)(2, 0)(2, 1)(2, 2)
+---+---+
|/// ///|
+ +---+---+
|///| |///|
+ + + +
|///| |///|
+ +---+ +
|/// /// ///|
+---+---+---+
Number of polyominoes 37
Time 0 seconds
The authors are grateful to Dr. Federico Della Bona for his help in the development of the Java part.