Some mathematical theorems could be solved by combinatorial exploration. On this article, we concentrate on the issue of the existence of some quasigroups. We are going to reveal the existence or non existence of some quasigroups utilizing NuCS. NuCs is a quick constraint solver written 100% in Python that I’m presently growing 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 components of the set (as does each binary operation) and satisfies the next constraints: the operation is associative, it has an id component, and each component of the set has an inverse component.
The set of integers (optimistic and destructive) along with the addition type a gaggle. There are numerous of sort of teams, for instance the manipulations of the Rubik’s Cube.
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 further properties.
Quasigroups
An order m quasigroup is a Latin sq. of dimension m. That’s, a m×m multiplication desk (we are going to be aware ∗ the multiplication image) through which every component happens as soon as in each row and column.
The multiplication legislation doesn’t must be associative. Whether it is, the quasigroup is a gaggle.
In the remainder of this text, we are going to concentrate on the issue of the existence of some specific quasigroups. The quasigroups we’re fascinated with 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 wish the values to match with the indices within the multiplication desk).
Latin sq. fashions
We are going to mannequin the quasigroup downside by leveraging the latin sq. downside. 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 must 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 shade(i, j) of the cell. We are going to 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.
Observe that we’ve 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 carried out 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 previous 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 just carried out 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 have in mind the truth that the rows and columns comprise components 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 will mannequin the issues QG3.m, QG4.m, QG6.m, QG7.m.
Observe that this downside could be very arduous 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 working Python 3.13, Numpy 2.1.3, Numba 0.61.0rc2 and NuCS 4.6.0. Observe 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 downside 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’ve 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 continues to be pretty easy
- discover extra subtle heuristics
- run the code on the cloud (utilizing docker, for instance)
