Machine Learning

Using Constraint Programming to Solve Mathematical Equations | by Yan Georget | January, 2025

Case in point: the existence problem of quasigroups

About Data Science

Some mathematical theorems can be solved by combinatorial testing. In this article, we focus on the problem of the existence of some quasigroups. We will show the existence or non-existence of other quasigroups using NuCS. NuCs is a fast obstacle solver written 100% in Python that I'm currently doing as a side project. Released under the MIT license.

Let's start by defining some useful vocabulary.

Groups

Quoting wikipedia:

In mathematics, a the group is a set that has a function that associates the element of the set with every two elements of the set (as do all binary functions) and satisfies the following constraints: the function is additive, has an identity property, and every element of the set has an inverse.

A collection of integers (positive and negative) and addition form a group. There are many types of groups, for example Rubik's Cube manipulation.

Source: Wikipedia

Latin squares

The Latin square is n x n full list 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 author

For example, Sudoku is a 9×9 A Latin square with additional buildings.

Quasigroups

The order m A quasigroup is a Latin square of size m. That is, a mxm a multiplication table (we will note the ∗ multiplication symbol) where each element occurs once in each row and in each column.

The law of multiplication does not have to be interactive. If so, the quasigroup is a group.

In the remainder of this article, we will focus on the problem of the existence of certain quasigroups. The quasigroups we are interested in are nonpotent, viz aa = a in everything a.

In addition, they have additional properties:

  • QG3.m problems are order m quasigroups namely (a∗b)∗(b∗a)=a.
  • QG4.m problems are order m quasigroups namely (b∗a)∗(a∗b)=a.
  • QG5.m problems are order m quasigroups namely ((b∗a)∗b)∗b=a.
  • QG6.m problems are orders of m quasigroups namely (a∗b)∗b=a∗(a∗b).
  • QG7.m problems are ordered m quasigroups namely (b∗a)∗b=a∗(b∗a).

Next, for the quasigroup of order mwe notice 0, …, m-1 quasigroup values ​​(we want the values ​​to correspond to the indices in the multiplication table).

Latin square models

We will model the quasigroup problem using the latin square problem. The first one comes in 2 types:

  • i The LatinSquareProblem,
  • i LatinSquareRCProblem.

The LatinSquareProblem simply says that the values ​​in all 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 describes, in each row i and column jvalue color(i, j) of the cell. We'll call it color model. Symmetrically, we can define:

  • in each row i and color ccolumn column(i, c): we call this column model,
  • per color c again column jline row(c, j): we call this row model.

Note that we have the following properties:

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

To what has been given column j, row (., j) again color(., j) it's the opposite permissions.

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

To what has been given color c, row(c,.) again column(., c) it's the opposite permissions.

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

To what has been given row i, color(i,.) again column(i,.) it's the opposite permissions.

This is exactly what the LatinSquareRCProblem does with the help of the ALG_PERMUTATION_AUX propagator (note that a slightly improved version of this propagator was also used in my previous article about the Traveling Salesman Problem):

def __init__(self, n: int):
super().__init__(list(range(n))) # the color 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 need to use our additional properties for our quasigroups.

Impotence is easily done 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]

Now let's focus on QG5.m. We need to get started ((b∗a)∗b)∗b=a:

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

The last sentence is i color(j,i)th part of etc column is row (i, j). To enforce this, we can use the ALG_ELEMENT_LIV declaration (or the more advanced ALG_ELEMENT_LIV_ALLDIFFERENT to take into account the fact that rows and columns contain different elements).

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 can model problems QG3.m, QG4.m, QG6.m, QG7.m.

Note that this problem is very difficult since the size of the search space is mᵐᵐ. Because m=10this 1e+100.

The following tests were 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 latest versions of NuCS are faster compared to the older ones as Python, Numpy and Numbba have been improved.

The following proof of presence/absence is found in in less than a second:

Testing in small cases

Now let's focus QG5.m only when the first open problem exists QG5.18.

Testing with QG5 (in the second line, we use MultiprocessingSolver)

Moving forward will require renting a powerful machine from a cloud provider within a few days at least!

As we have seen, some mathematical theorems can be solved by integral tests. In this article, we studied the existence/nonexistence problem of quasigroups. Among such problems, some open ones seem accessible, which is very refreshing.

Some ideas for improving our current approach to the existence of quasigroups:

  • refine the already simple model
  • check complex heuristics
  • run code in the cloud (using docker, for example)

Source link

Related Articles

Leave a Reply

Your email address will not be published. Required fields are marked *

Back to top button