Case study: the quasigroups existence problem<\/h4>\nTLDR<\/h3>\n
Some mathematical theorems can be solved by combinatorial exploration. In this article, we focus on the problem of the existence of some quasigroups. We will demonstrate the existence or non existence of some quasigroups using NuCS<\/a>. NuCs is a fast constraint solver written 100% in Python that I am currently developing as a side project. It is released under the MIT\u00a0license<\/a>.<\/p>\n Let’s start by defining some useful vocabulary.<\/p>\n Quoting wikipedia:<\/p>\n In mathematics, a group<\/strong> is a set with an operation that associates an element of the set to every pair of elements of the set (as does every binary operation) and satisfies the following constraints: the operation is associative, it has an identity element, and every element of the set has an inverse\u00a0element.<\/p><\/blockquote>\n The set of integers (positive and negative) together with the addition form a group. There are many of kind of groups, for example the manipulations of the Rubik’s\u00a0Cube<\/a>.<\/p>\n A Latin square is an n<\/em> \u00d7 n<\/em> array filled with n<\/em> different symbols, each occurring exactly once in each row and exactly once in each\u00a0column.<\/p><\/blockquote>\n An example of a 3\u00d73 Latin square\u00a0is:<\/p>\n For example, a Sudoku is a 9×9<\/em> Latin square with additional properties.<\/p><\/blockquote>\n An order m<\/em> quasigroup is a Latin square of size m<\/em>. That is, a m\u00d7m<\/em> multiplication table (we will note \u2217 the multiplication symbol) in which each element occurs once in every row and\u00a0column.<\/p><\/blockquote>\n The multiplication law does not have to be associative. If it is, the quasigroup is a\u00a0group.<\/p>\n In the rest of this article, we will focus on the problem of the existence of some particular quasigroups. The quasigroups we are interested in are idempotent, that is a<\/em>\u2217a=a<\/em><\/strong> for every element\u00a0a<\/em>.<\/p>\n Moreover, they have additional properties:<\/p>\n In the following, for a quasigroup of order m<\/em>, we note 0,\u00a0\u2026, m-1<\/em> the values of the quasigroup (we want the values to match with the indices in the multiplication table).<\/p>\n We will model the quasigroup problem by leveraging the latin square problem. The former comes in 2\u00a0flavors:<\/p>\n The LatinSquareProblem simply states that the values in all the rows and columns of the multiplication table have to be different:<\/p>\n This model defines, for each row i<\/em> and column j<\/em>, the value color(i, j) <\/em>of the cell. We will call it the color<\/strong> model. Symmetrically, we can\u00a0define:<\/p>\n Note that we have the following properties:<\/p>\n For a given <\/em>column j<\/em>, row(., j) <\/em>and color(., j) <\/em>are inverse permutations.<\/p>\n For a given <\/em>color c<\/em>, row(c,\u00a0.) <\/em>and column(., c) <\/em>are inverse permutations.<\/p>\n For a given <\/em>row i<\/em>, color(i,\u00a0.) <\/em>and column(i,\u00a0.) <\/em>are inverse permutations.<\/p>\n This is exactly what is implemented by the LatinSquareRCProblem with the help of the ALG_PERMUTATION_AUX propagator (note that a less optimized version of this propagator was also used in my previous article<\/a> about the Travelling Salesman Problem):<\/p>\n Now we need to implement our additional properties for our quasigroups.<\/p>\n Idempotence is simply implemented by:<\/p>\n Let’s now focus on QG5.m. We need to implement ((b\u2217a)\u2217b)\u2217b=a<\/em>:<\/p>\n The last expression states that the color(j,i)th<\/em> element of the jth<\/em> column is row(i, j)<\/em>. To enforces this, we can leverage the ALG_ELEMENT_LIV propagator (or a more specialized ALG_ELEMENT_LIV_ALLDIFFERENT optimized to take into account the fact that the rows and columns contain elements that are alldifferent).<\/p>\n Similarly, we can model the problems QG3.m, QG4.m, QG6.m,\u00a0QG7.m<\/a>.<\/p>\n Note that this problem is very hard since the size of the search space is m\u1d50\u1d50. For m=10<\/em>, this is\u00a01e+100<\/em>.<\/p>\n The following 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.<\/p>\n The following proofs of existence\/non existence are obtained in less than a\u00a0second<\/strong>:<\/p>\n Let’s now focus on QG5.m<\/strong> only where the first open problem is\u00a0QG5.18<\/strong>.<\/p>\n Going further would require to rent a powerful machine on a cloud provider during a few days at\u00a0least!<\/p>\n As we have seen, some mathematical theorems can be solved by combinatorial exploration. In this article, we studied the problem of the existence\/non existence of quasigroups. Among such problems, some open ones seem to be accessible, which is very stimulating.<\/p>\n Some ideas to improve on our current approach to quasigroups existence:<\/p>\n Some useful links to go further with\u00a0NuCS:<\/p>\n If you enjoyed this article about NuCS, please clap 50<\/strong> times\u00a0!<\/p>\n Using Constraint Programming to Solve Math Theorems<\/a> was originally published in Towards Data Science<\/a> on Medium, where people are continuing the conversation by highlighting and responding to this story.<\/p>\n<\/div>\nSome definitions<\/h3>\n
Groups<\/h4>\n
![\"\"](\"https:\/\/i0.wp.com\/cdn-images-1.medium.com\/max\/440\/1%2AA6HWIqlPHR0Ek6rz1H7mFg.png?ssl=1\")
Latin squares<\/h4>\n
![\"\"](\"https:\/\/i0.wp.com\/cdn-images-1.medium.com\/max\/172\/1%2AwBputE2ca-WpAlVAO0_pzA.png?ssl=1\")
Quasigroups<\/h4>\n
\n
Modelling the quasigroup problem<\/h3>\n
Latin square\u00a0models<\/h4>\n
\n
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)])<\/pre>\n\n
\n
\n
\n
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, []))<\/pre>\nQuasigroup model<\/h4>\n
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]<\/pre>\n\n
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,
[],
)
)<\/pre>\nExperiments<\/h3>\n
![\"\"](\"https:\/\/i0.wp.com\/cdn-images-1.medium.com\/max\/1024\/1%2AznmS07WcsvFkwbWZ15bydw.png?ssl=1\")
![\"\"](\"https:\/\/i0.wp.com\/cdn-images-1.medium.com\/max\/1024\/1%2AJiFv9aJUFFxzvLXGui8Zgg.png?ssl=1\")
Conclusion<\/h3>\n
\n
\n
<\/p>\n
\n