Some mathematical theorems can be solved by combinatorial exploration. In this article we focus on the problem of the existence of some quasigroups. We will prove the existence or non-existence of some quasigroups using nucs. NuCs is a fast constraint solver written 100% in Python that I'm currently developing as a side project. It is published under the MY license.
Let's start by defining some useful vocabulary.
Groups
Quoting wikipedia:
In mathematics, a cluster is a set with an operation that associates an element of the set to each pair of elements in the set (as every binary operation does) and satisfies the following restrictions: the operation is associative, it has an identity element, and each element of the set The set has an inverse element.
The set of integers (positive and negative) together with the sum form a group. There are many types of groups, for example manipulations of the rubik's cube.
latin squares
A Latin square is a north × north matrix full of north different symbols, each of which appears exactly once in each row and exactly once in each column.
An example of a 3×3 Latin square is:
For example, a Sudoku is a 9×9 Latin square with additional properties.
Quasigroups
an order metro quasigroup is a Latin square of size metro. That is, a m×m multiplication table (we will note ∗ the multiplication symbol) in which each element appears once in each row and column.
The law of multiplication does not have to be associative. If so, the quasigroup is a group.
In the rest of this article we will focus on the problem of the existence of some particular quasigroups. The quasigroups that interest us are idempotent, that is to∗a=a for each element to.
In addition, they have additional properties:
- The QG3.m problems are quasigroups of order m for which (a∗b)∗(b∗a)=a.
- The QG4.m problems are quasigroups of order m for which (b∗a)∗(a∗b)=a.
- The QG5.m problems are quasigroups of order m for which ((b∗a)∗b)∗b=a.
- The QG6.m problems are quasigroups of order m for which (a∗b)∗b=a∗(a∗b).
- The QG7.m problems are quasigroups of order m for which (b∗a)∗b=a∗(b∗a).
Then for a quasigroup of order metrowe notice 0,…, m-1 the values of the quasigroup (we want the values to match the indices of the multiplication table).
Latin square models
We will model the quasigroup problem taking advantage of the Latin square problem. The first one comes in 2 flavors:
- he ProblemSquareLatin,
- he LatinSquareRCProblem.
The LatinSquareProblem simply states that the values in all rows and columns of the multiplication table have to be different:
self.add_propagators(((self.row(i), ALG_ALLDIFFERENT, ()) for i in range(self.n)))
self.add_propagators(((self.column(j), ALG_ALLDIFFERENT, ()) for j in range(self.n)))
This model defines, for each row Yo and column jthe value color(i,j) of the cell. We will call him the color model. Symmetrically we can define:
- for each row Yo and color dothe column column(i,c): we call this the column model,
- for each color do and column jthe row row(c,j): we call this the row model.
Note that we have the following properties:
- row(c, j) = i color(i, j) = c
for a certain column j, row(., j) and color(., j) They are inverse permutations.
- row(c, j) = i column(i, c) = j
for a certain color do, row(c,.) and column(.,c) They are inverse permutations.
- color(i, j) = c column(i, c) = j
for a certain row Yo, color(i, .) and column(i, .) They are inverse permutations.
This is exactly what LatinSquareRCProblem implements with the help of the ALG_PERMUTATION_AUX propagator (note that a less optimized version of this propagator was also used in my previous article on the problem of the salesman):
def __init__(self, n: int):
super().__init__(list(range(n))) # the color model
self.add_variables(((0, n - 1)) * n**2) # the row model
self.add_variables(((0, n - 1)) * n**2) # the column model
self.add_propagators(((self.row(i, M_ROW), ALG_ALLDIFFERENT, ()) for i in range(self.n)))
self.add_propagators(((self.column(j, M_ROW), ALG_ALLDIFFERENT, ()) for j in range(self.n)))
self.add_propagators(((self.row(i, M_COLUMN), ALG_ALLDIFFERENT, ()) for i in range(self.n)))
self.add_propagators(((self.column(j, M_COLUMN), ALG_ALLDIFFERENT, ()) for j in range(self.n)))
# row(c,j)=i <=> color(i,j)=c
for j in range(n):
self.add_propagator(((*self.column(j, M_COLOR), *self.column(j, M_ROW)), ALG_PERMUTATION_AUX, ()))
# row(c,j)=i <=> column(i,c)=j
for c in range(n):
self.add_propagator(((*self.row(c, M_ROW), *self.column(c, M_COLUMN)), ALG_PERMUTATION_AUX, ()))
# color(i,j)=c <=> column(i,c)=j
for i in range(n):
self.add_propagator(((*self.row(i, M_COLOR), *self.row(i, M_COLUMN)), ALG_PERMUTATION_AUX, ()))
Quasigroup model
Now we need to implement our additional properties for our quasigroups.
Idempotence is simply implemented by:
for model in (M_COLOR, M_ROW, M_COLUMN):
for i in range(n):
self.shr_domains_lst(self.cell(i, i, model)) = (i, i)
Let's now focus on QG5.m. We need to implement ((b∗a)∗b)∗b=a:
- this translates to: color(color(color(j, i), j), j) = i,
- or equivalent: row(i, j) = color(color(j, i), j).
The last expression states that the color(j,i)th element of the jth the column is row(i,j). To enforce this, we can take advantage of the ALG_ELEMENT_LIV propagator (or a more specialized ALG_ELEMENT_LIV_ALLDIFFERENT optimized to take into account the fact that rows and columns contain elements that are all different).
for i in range(n):
for j in range(n):
if j != i:
self.add_propagator(
(
(*self.column(j), self.cell(j, i), self.cell(i, j, M_ROW)),
ALG_ELEMENT_LIV_ALLDIFFERENT,
(),
)
)
Similarly, we can model the problems. QG3.m, QG4.m, QG6.m, QG7.m.
Note that this problem is very difficult since the size of the search space is mᵐᵐ. For meter=10this is 1e+100.
The following experiments are performed on an M2 MacBook Pro with Python 3.13, Numpy 2.1.3, Numba 0.61.0rc2, and NuCS 4.6.0. Note that recent versions of NuCS are relatively faster than previous ones since Python, Numpy and Numba were updated.
The following existence/non-existence tests are obtained in less than a second:
Let us now focus on QG5.m only where is the first open problem QG5.18.
Going further would require renting a powerful machine from a cloud provider for at least a few days!
As we have seen, some mathematical theorems can be solved by combinatorial exploration. In this article we study the problem of the existence/non-existence of quasigroups. Among these problems, some open ones seem accessible, which is very stimulating.
Some ideas to improve our current approach to the existence of quasigroups:
- refine the model which is still quite simple
- explore more sophisticated heuristics
- run the code in the cloud (using Docker for example)
