Some mathematical theorems will be solved by combinatorial exploration. On this article, we deal with the issue of the existence of some quasigroups. We are going to exhibit the existence or non existence of some quasigroups utilizing NuCS. NuCs is a quick constraint solver written 100% in Python that I’m at the moment growing as a facet undertaking. It’s launched beneath the MIT license.
Let’s begin by defining some helpful vocabulary.
Teams
Quoting wikipedia:
In arithmetic, a group is a set with an operation that associates a component of the set to each pair of components of the set (as does each binary operation) and satisfies the next constraints: the operation is associative, it has an id factor, and each factor of the set has an inverse factor.
The set of integers (optimistic and destructive) along with the addition kind a bunch. There are a lot of of form of teams, for instance the manipulations of the Rubik’s Dice.
Latin squares
A Latin sq. is an n × n array stuffed with n totally different symbols, every occurring precisely as soon as in every row and precisely as soon as in every column.
An instance of a 3×3 Latin sq. is:
For instance, a Sudoku is a 9×9 Latin sq. with extra properties.
Quasigroups
An order m quasigroup is a Latin sq. of dimension m. That’s, a m×m multiplication desk (we’ll observe ∗ the multiplication image) wherein every factor happens as soon as in each row and column.
The multiplication regulation doesn’t need to be associative. Whether it is, the quasigroup is a bunch.
In the remainder of this text, we’ll deal with the issue of the existence of some explicit quasigroups. The quasigroups we’re fascinated about are idempotent, that’s a∗a=a for each factor a.
Furthermore, they’ve extra properties:
- QG3.m issues are order m quasigroups for which (a∗b)∗(b∗a)=a.
- QG4.m issues are order m quasigroups for which (b∗a)∗(a∗b)=a.
- QG5.m issues are order m quasigroups for which ((b∗a)∗b)∗b=a.
- QG6.m issues are order m quasigroups for which (a∗b)∗b=a∗(a∗b).
- QG7.m issues are order m quasigroups for which (b∗a)∗b=a∗(b∗a).
Within the following, for a quasigroup of order m, we observe 0, …, m-1 the values of the quasigroup (we would like the values to match with the indices within the multiplication desk).
Latin sq. fashions
We are going to mannequin the quasigroup drawback by leveraging the latin sq. drawback. The previous is available in 2 flavors:
- the LatinSquareProblem,
- the LatinSquareRCProblem.
The LatinSquareProblem merely states that the values in all of the rows and columns of the multiplication desk need to be totally different:
self.add_propagators([(self.row(i), ALG_ALLDIFFERENT, []) for i in vary(self.n)])
self.add_propagators([(self.column(j), ALG_ALLDIFFERENT, []) for j in vary(self.n)])
This mannequin defines, for every row i and column j, the worth coloration(i, j) of the cell. We are going to name it the coloration mannequin. Symmetrically, we are able to outline:
- for every row i and coloration c, the column column(i, c): we name this the column mannequin,
- for every coloration c and column j, the row row(c, j): we name this the row mannequin.
Be aware that now we have the next properties:
- row(c, j) = i <=> coloration(i, j) = c
For a given column j, row(., j) and coloration(., j) are inverse permutations.
- row(c, j) = i <=> column(i, c) = j
For a given coloration c, row(c, .) and column(., c) are inverse permutations.
- coloration(i, j) = c <=> column(i, c) = j
For a given row i, coloration(i, .) and column(i, .) are inverse permutations.
That is precisely what’s applied by the LatinSquareRCProblem with the assistance of the ALG_PERMUTATION_AUX propagator (observe {that a} much less optimized model of this propagator was additionally utilized in my earlier article concerning the Travelling Salesman Drawback):
def __init__(self, n: int):
tremendous().__init__(record(vary(n))) # the colour mannequin
self.add_variables([(0, n - 1)] * n**2) # the row mannequin
self.add_variables([(0, n - 1)] * n**2) # the column mannequin
self.add_propagators([(self.row(i, M_ROW), ALG_ALLDIFFERENT, []) for i in vary(self.n)])
self.add_propagators([(self.column(j, M_ROW), ALG_ALLDIFFERENT, []) for j in vary(self.n)])
self.add_propagators([(self.row(i, M_COLUMN), ALG_ALLDIFFERENT, []) for i in vary(self.n)])
self.add_propagators([(self.column(j, M_COLUMN), ALG_ALLDIFFERENT, []) for j in vary(self.n)])
# row[c,j]=i <=> coloration[i,j]=c
for j in vary(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 vary(n):
self.add_propagator(([*self.row(c, M_ROW), *self.column(c, M_COLUMN)], ALG_PERMUTATION_AUX, []))
# coloration[i,j]=c <=> column[i,c]=j
for i in vary(n):
self.add_propagator(([*self.row(i, M_COLOR), *self.row(i, M_COLUMN)], ALG_PERMUTATION_AUX, []))
Quasigroup mannequin
Now we have to implement our extra properties for our quasigroups.
Idempotence is solely applied by:
for mannequin in [M_COLOR, M_ROW, M_COLUMN]:
for i in vary(n):
self.shr_domains_lst[self.cell(i, i, model)] = [i, i]
Let’s now deal with QG5.m. We have to implement ((b∗a)∗b)∗b=a:
- this interprets into: coloration(coloration(coloration(j, i), j), j) = i,
- or equivalently: row(i, j) = coloration(coloration(j, i), j).
The final expression states that the coloration(j,i)th factor of the jth column is row(i, j). To enforces this, we are able to leverage the ALG_ELEMENT_LIV propagator (or a extra specialised ALG_ELEMENT_LIV_ALLDIFFERENT optimized to have in mind the truth that the rows and columns include components which are alldifferent).
for i in vary(n):
for j in vary(n):
if j != i:
self.add_propagator(
(
[*self.column(j), self.cell(j, i), self.cell(i, j, M_ROW)],
ALG_ELEMENT_LIV_ALLDIFFERENT,
[],
)
)
Equally, we are able to mannequin the issues QG3.m, QG4.m, QG6.m, QG7.m.
Be aware that this drawback could be very laborious because the dimension of the search house is mᵐᵐ. For m=10, that is 1e+100.
The next experiments are carried out on a MacBook Professional M2 operating Python 3.13, Numpy 2.1.3, Numba 0.61.0rc2 and NuCS 4.6.0. Be aware that the current variations of NuCS are comparatively sooner than older ones since Python, Numpy and Numba have been upgraded.
The next proofs of existence/non existence are obtained in lower than a second:
Let’s now deal with QG5.m solely the place the primary open drawback is QG5.18.
Going additional would require to lease a strong machine on a cloud supplier throughout a number of days a minimum of!
As now we have seen, some mathematical theorems will be solved by combinatorial exploration. On this article, we studied the issue of the existence/non existence of quasigroups. Amongst such issues, some open ones appear to be accessible, which could be very stimulating.
Some concepts to enhance on our present strategy to quasigroups existence:
- refine the mannequin which continues to be pretty easy
- discover extra refined heuristics
- run the code on the cloud (utilizing docker, for instance)
