Case research: the quasigroups existence drawback
Some mathematical theorems might be solved by combinatorial exploration. On this article, we concentrate on the issue of the existence of some quasigroups. We’ll reveal 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 creating as a aspect mission. 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 parts of the set (as does each binary operation) and satisfies the next constraints: the operation is associative, it has an identification component, and each component of the set has an inverse component.
The set of integers (constructive and adverse) along with the addition kind a gaggle. There are a lot of of sort of teams, for instance the manipulations of the Rubik’s Dice.
Latin squares
A Latin sq. is an n × n array crammed with n completely 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 further properties.
Quasigroups
An order m quasigroup is a Latin sq. of dimension m. That’s, a m×m multiplication desk (we’ll word ∗ the multiplication image) through which every component happens as soon as in each row and column.
The multiplication legislation doesn’t need to be associative. Whether it is, the quasigroup is a gaggle.
In the remainder of this text, we’ll concentrate on the issue of the existence of some specific quasigroups. The quasigroups we’re fascinated by are idempotent, that’s a∗a=a for each component a.
Furthermore, they’ve further 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 word 0, …, m-1 the values of the quasigroup (we wish the values to match with the indices within the multiplication desk).
Latin sq. fashions
We’ll 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 completely 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 shade(i, j) of the cell. We’ll name it the shade mannequin. Symmetrically, we will outline:
- for every row i and shade c, the column column(i, c): we name this the column mannequin,
- for every shade c and column j, the row row(c, j): we name this the row mannequin.
Notice that we’ve got the next properties:
- row(c, j) = i <=> shade(i, j) = c
For a given column j, row(., j) and shade(., j) are inverse permutations.
- row(c, j) = i <=> column(i, c) = j
For a given shade c, row(c, .) and column(., c) are inverse permutations.
- shade(i, j) = c <=> column(i, c) = j
For a given row i, shade(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 (word {that a} much less optimized model of this propagator was additionally utilized in my earlier article concerning the Travelling Salesman Downside):
def __init__(self, n: int):
tremendous().__init__(checklist(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 <=> shade[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, []))
# shade[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 further 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 concentrate on QG5.m. We have to implement ((b∗a)∗b)∗b=a:
- this interprets into: shade(shade(shade(j, i), j), j) = i,
- or equivalently: row(i, j) = shade(shade(j, i), j).
The final expression states that the shade(j,i)th component of the jth column is row(i, j). To enforces this, we will leverage the ALG_ELEMENT_LIV propagator (or a extra specialised ALG_ELEMENT_LIV_ALLDIFFERENT optimized to take note of the truth that the rows and columns include parts 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 will mannequin the issues QG3.m, QG4.m, QG6.m, QG7.m.
Notice that this drawback could be very laborious for the reason that 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 working Python 3.13, Numpy 2.1.3, Numba 0.61.0rc2 and NuCS 4.6.0. Notice 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 concentrate on 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 just a few days no less than!
As we’ve got seen, some mathematical theorems might 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 method 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)
