Computational Essay

Ramsey’s Theorem »

Project: Automated Discovery of Algebraic Structures

Goal of the project:

Algebraic structures are sets equipped with finitary operators satisfying some axiomatic system. These axiomatic systems can be generated by enumerating possible relations involving the operators. This project attempts the computational discovery of interesting structures by searching for slow growth rates for the set of sets that satisfy these relations.

Summary of work:

We automatically generated axioms defined by up to two parameters and equipped with a single binary operator. We tested 611,917 distinct axioms (up to eight instances of a single variable, or up to four instances each of two variables) against operator tables for sets of size 2 (16) and 3 (19,683).

Results and future work:

Fewer than 2% of axioms are “interesting” in the sense of only being satisfied by a relatively small number of operator tables. One can increase the size of sets for the operator tables or the lengths of axioms, including those with more than two variables. Another possible approach is to combine individual axioms and study composite systems.