Using Constraint Programming to Solve Math Theorems

-

Case study: the quasigroups existence problem

Some mathematical theorems may be solved by combinatorial exploration. In this text, we give attention to the issue of the existence of some quasigroups. We are going to display the existence or non existence of some quasigroups using NuCS. NuCs is a quick constraint solver written 100% in Python that I’m currently developing as a side project. It’s released under the MIT license.

Let’s start by defining some useful vocabulary.

Groups

Quoting wikipedia:

In mathematics, a group is a set with an operation that associates a component of the set to each pair of elements of the set (as does every binary operation) and satisfies the next constraints: the operation is associative, it has an identity element, and each element of the set has an inverse element.

The set of integers (positive and negative) along with the addition form a bunch. There are various of type of groups, for instance the manipulations of the Rubik’s Cube.

Source: Wikipedia

Latin squares

A Latin square is an n × n array stuffed with n different symbols, each occurring exactly once in each row and exactly once in each column.

An example of a 3×3 Latin square is:

Designed by the creator

For instance, a Sudoku is a 9×9 Latin square with additional properties.

Quasigroups

An order m quasigroup is a Latin square of size m. That’s, a m×m multiplication table (we are going to note ∗ the multiplication symbol) wherein each element occurs once in every row and column.

The multiplication law doesn’t must be associative. Whether it is, the quasigroup is a bunch.

In the remainder of this text, we are going to give attention to the issue of the existence of some particular quasigroups. The quasigroups we’re all in favour of are idempotent, that’s aa=a for each element a.

Furthermore, they’ve additional properties:

  • QG3.m problems are order m quasigroups for which (a∗b)∗(b∗a)=a.
  • QG4.m problems are order m quasigroups for which (b∗a)∗(a∗b)=a.
  • QG5.m problems are order m quasigroups for which ((b∗a)∗b)∗b=a.
  • QG6.m problems are order m quasigroups for which (a∗b)∗b=a∗(a∗b).
  • QG7.m problems are order m quasigroups for which (b∗a)∗b=a∗(b∗a).

In the next, for a quasigroup of order m, we note 0, …, m-1 the values of the quasigroup (we would like the values to match with the indices within the multiplication table).

Latin square models

We are going to model the quasigroup problem by leveraging the latin square problem. The previous is available in 2 flavors:

  • the LatinSquareProblem,
  • the LatinSquareRCProblem.

The LatinSquareProblem simply states that the values in all of the rows and columns of the multiplication table must be different:

self.add_propagators([(self.row(i), ALG_ALLDIFFERENT, []) for i in range(self.n)])
self.add_propagators([(self.column(j), ALG_ALLDIFFERENT, []) for j in range(self.n)])

This model defines, for every row i and column j, the worth color(i, j) of the cell. We are going to call it the color model. Symmetrically, we are able to define:

  • for every row i and color c, the column column(i, c): we call this the column model,
  • for every color c and column j, the row row(c, j): we call this the row model.

Note that we’ve the next properties:

  • row(c, j) = i <=> color(i, j) = c

For a given column j, row(., j) and color(., j) are inverse permutations.

  • row(c, j) = i <=> column(i, c) = j

For a given color c, row(c, .) and column(., c) are inverse permutations.

  • color(i, j) = c <=> column(i, c) = j

For a given row i, color(i, .) and column(i, .) are inverse permutations.

This is strictly what’s implemented by the LatinSquareRCProblem with the assistance of the ALG_PERMUTATION_AUX propagator (note that a less optimized version of this propagator was also utilized in my previous article concerning the Travelling Salesman Problem):

def __init__(self, n: int):
super().__init__(list(range(n))) # the colour model
self.add_variables([(0, n - 1)] * n**2) # the row model
self.add_variables([(0, n - 1)] * n**2) # the column model
self.add_propagators([(self.row(i, M_ROW), ALG_ALLDIFFERENT, []) for i in range(self.n)])
self.add_propagators([(self.column(j, M_ROW), ALG_ALLDIFFERENT, []) for j in range(self.n)])
self.add_propagators([(self.row(i, M_COLUMN), ALG_ALLDIFFERENT, []) for i in range(self.n)])
self.add_propagators([(self.column(j, M_COLUMN), ALG_ALLDIFFERENT, []) for j in range(self.n)])
# row[c,j]=i <=> color[i,j]=c
for j in range(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 range(n):
self.add_propagator(([*self.row(c, M_ROW), *self.column(c, M_COLUMN)], ALG_PERMUTATION_AUX, []))
# color[i,j]=c <=> column[i,c]=j
for i in range(n):
self.add_propagator(([*self.row(i, M_COLOR), *self.row(i, M_COLUMN)], ALG_PERMUTATION_AUX, []))

Quasigroup model

Now we’d like to implement our additional properties for our quasigroups.

Idempotence is just implemented by:

for model in [M_COLOR, M_ROW, M_COLUMN]:
for i in range(n):
self.shr_domains_lst[self.cell(i, i, model)] = [i, i]

Let’s now give attention to QG5.m. We’d like to implement ((b∗a)∗b)∗b=a:

  • this translates into: color(color(color(j, i), j), j) = i,
  • or equivalently: row(i, j) = color(color(j, i), j).

The last expression states that the color(j,i)th element of the jth column is row(i, j). To enforces this, we are able to leverage the ALG_ELEMENT_LIV propagator (or a more specialized ALG_ELEMENT_LIV_ALLDIFFERENT optimized to take note of the proven fact that the rows and columns contain elements which might be alldifferent).

for i in range(n):
for j in range(n):
if j != i:
self.add_propagator(
(
[*self.column(j), self.cell(j, i), self.cell(i, j, M_ROW)],
ALG_ELEMENT_LIV_ALLDIFFERENT,
[],
)
)

Similarly, we are able to model the issues QG3.m, QG4.m, QG6.m, QG7.m.

Note that this problem could be very hard for the reason that size of the search space is mᵐᵐ. For m=10, that is 1e+100.

The next experiments are performed on a MacBook Pro M2 running Python 3.13, Numpy 2.1.3, Numba 0.61.0rc2 and NuCS 4.6.0. Note that the recent versions of NuCS are relatively faster 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:

Experiments with small instances

Let’s now give attention to QG5.m only where the primary open problem is QG5.18.

Experiments with QG5 (within the second line, we use a MultiprocessingSolver)

Going further would require to rent a strong machine on a cloud provider during a number of days at the least!

As we’ve seen, some mathematical theorems may be solved by combinatorial exploration. In this text, we studied the issue of the existence/non existence of quasigroups. Amongst such problems, some open ones appear to be accessible, which could be very stimulating.

Some ideas to enhance on our current approach to quasigroups existence:

  • refine the model which continues to be fairly easy
  • explore more sophisticated heuristics
  • run the code on the cloud (using docker, for instance)
ASK ANA

What are your thoughts on this topic?
Let us know in the comments below.

0 0 votes
Article Rating
guest
0 Comments
Oldest
Newest Most Voted
Inline Feedbacks
View all comments

Share this article

Recent posts

0
Would love your thoughts, please comment.x
()
x