Some mathematical theorems could be solved by combinatorial exploration. On this article, we concentrate on the issue of the existence of some quasigroups. We’ll display the existence or non existence of some quasigroups utilizing NuCS. NuCs is a quick constraint solver written 100% in Python that I’m at present growing as a aspect mission. It’s launched below 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 unfavourable) along with the addition kind a bunch. There are numerous of form of teams, for instance the manipulations of the Rubik’s Dice.
Latin squares
A Latin sq. is an n × n array full of 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 further properties.
Quasigroups
An order m quasigroup is a Latin sq. of measurement m. That’s, a m×m multiplication desk (we are going to be aware ∗ the multiplication image) wherein 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 bunch.
In the remainder of this text, we are going to concentrate on the issue of the existence of some explicit quasigroups. The quasigroups we’re eager about 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 be aware 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’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 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’ll 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.
Word that we now 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 (be aware {that a} much less optimized model of this propagator was additionally utilized in my earlier article in regards to the Travelling Salesman Downside):
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 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: 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 component 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 take into consideration the truth that the rows and columns include parts which can be 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.
Word that this drawback could be very exhausting because the measurement 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. Word that the latest variations of NuCS are comparatively quicker 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 robust machine on a cloud supplier throughout a couple of days no less than!
As we now have seen, some mathematical theorems could 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 remains to be pretty easy
- discover extra refined heuristics
- run the code on the cloud (utilizing docker, for instance)
