Some mathematical theorems might be solved by combinatorial search. This text focuses on the problem of the existence of a number of quasi-groups. Use to show the existence or non-existence of some subgroup. NuCS. NuCs is a quick constraint solver written 100% in Python and at present being developed as a aspect challenge. It’s launched beneath MIT license.
Let’s begin by defining some helpful vocabulary.
group
Quoting Wikipedia:
in arithmetic, group is a set containing an operation (like all binary operations) that associates a component of the set with each pair of components of the set, satisfying the next constraints: The operation is associative and has identification components. , set has an inverse factor.
A set of integers (constructive and adverse) and addition kind a gaggle. Many forms of teams exist. rubik’s cube.
latin sq.
Latin Sq. is n × n array crammed with n Every image seems as soon as in every row and as soon as in every column.
An instance of a 3×3 Latin sq. is:
For instance, Sudoku 9×9 Latin Sq. with extra properties.
quasi-group
order meter quasigroup is a Latin sq. of measurement meter. In different phrases, m×m A multiplication desk the place every factor seems as soon as in every row and column (be aware the * multiplication signal).
Multiplication legal guidelines would not have to be associative. If that’s the case, the quasi-group is a gaggle.
Within the the rest of this text, we are going to deal with the problem of the existence of some particular subgroups. The subgroup we’re enthusiastic about is idempotent. be*a=a for each factor be.
Moreover, there are extra properties as effectively.
- QG3.m The issue is the next m subgroup. (a*b)*(b*a)=a.
- QG4.m The issue is the next m subgroup. (b∗a)∗(a∗b)=a.
- QG5.m The issue is the next m subgroup. ((b∗a)∗b)∗b=a.
- QG6.m The issue is the next m subgroup. (a*b)*b=a*(a*b).
- QG7.m The issue is the next m subgroup. (b*a)*b=a*(b*a).
Beneath, for the quasigroup of the order, meterwe be aware 0,…, m-1 Quasi-group worth (worth should match index in multiplication desk).
latin sq. mannequin
Mannequin the subgroup drawback utilizing the Latin sq. drawback. The previous is available in two flavors.
- of latin equation issues,
- of latin sq. rc drawback.
The LatinSquare drawback merely states that every one rows and columns of the multiplication desk will need to have totally different values.
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)])
For every row, this mannequin defines: I and column j,worth colour(i, j) of cells. that colour mannequin. Symmetrically, it may be outlined as:
- for every row I and colour c,column column(i, c): this column mannequin,
- for every colour c and column j,line row(c, j): this line mannequin.
Notice that it has the next properties:
- row(c, j) = i <=> colour(i, j) = c
given column j, row(., j) and colour(., j) It is a reverse permutation.
- row(c, j) = i <=> column(i, c) = j
given colour c, line(c, .) and column(.,c) It is a reverse permutation.
- colour(i, j) = c <=> column(i, c) = j
given line I, colour(i, .) and column(i, .) It is a reverse permutation.
That is precisely what was carried out by LatinSquareRCProblem with the assistance of the ALG_PERMUTATION_AUX propagator (be aware {that a} much less optimized model of this propagator can be utilized in my challenge) Previous article Concerning the touring salesman drawback):
def __init__(self, n: int):
tremendous().__init__(listing(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 <=> colour[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, []))
# colour[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 extra properties for quasi-groups.
Idempotency might be simply carried out as follows.
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 deal with QG5.m right here. should be carried out ((b∗a)∗b)∗b=a:
- This interprets to: colour(colour(colour(j, i), j), j) = i,
- or equivalently: row(i, j) = colour(colour(j, i), j).
The ultimate system is colour(j,i)th components of jth The column is row(i, j). To implement this, you’ll be able to make the most of the ALG_ELEMENT_LIV propagator (or the extra specialised ALG_ELEMENT_LIV_ALLDIFFERENT, which is optimized to take note of the truth that rows and columns include utterly totally different components).
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, you’ll be able to mannequin your drawback. QG3.m, QG4.m, QG6.m, QG7.m.
Notice that this drawback may be very tough as a result of the dimensions 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. Notice that the most recent model of NuCS is comparatively sooner than older variations as a result of upgrades to Python, Numpy, and Numba.
The next proof of existence/nonexistence is obtained. lower than 1 second:
Let’s focus right here QG5.m Provided that there’s an preliminary unresolved concern QG5.18.
To go additional, you will have to lease a strong machine at a cloud supplier for a minimum of a couple of days.
As we’ve got seen, some mathematical theorems might be solved by combinatorial search. On this article, we studied the issue of existence/nonexistence of quasigroups. A few of these issues are open and accessible, which may be very thrilling.
Some concepts to enhance the present method to the existence of quasi-groups:
- Bettering a nonetheless pretty easy mannequin
- Discover extra refined heuristics
- Run your code on the cloud (e.g. utilizing Docker)