Utilizing Constraint Programming to Clear up Math Theorems | by Yan Georget | Jan, 2025

Some mathematical theorems will be solved by combinatorial exploration. On this article, we give attention to 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 creating as a aspect venture. 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 components of the set (as does each binary operation) and satisfies the next constraints: the operation is associative, it has an identification ingredient, and each ingredient of the set has an inverse ingredient.

The set of integers (optimistic and adverse) along with the addition kind a gaggle. There are numerous of type 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 measurement m. That’s, a m×m multiplication desk (we are going to observe ∗ the multiplication image) by which every ingredient 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 gaggle.

In the remainder of this text, we are going to give attention to the issue of the existence of some explicit quasigroups. The quasigroups we’re all in favour of are idempotent, that’s a∗a=a for each ingredient 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 wish the values to match with the indices within the multiplication desk).

Latin sq. fashions

We’ll 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 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.

Notice 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 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 extra properties for our quasigroups.

Idempotence is just 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 give attention to 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 ingredient 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 bear 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 are able to mannequin the issues QG3.m, QG4.m, QG6.m, QG7.m.

Notice that this downside may be very exhausting for the reason that 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. 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 give attention to 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 just a few 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 may 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 subtle heuristics
• run the code on the cloud (utilizing docker, for instance)