The purpose of this project, launched on Sep 25, 2024, is to explore the space of equational theories of magmas, ordered by implication. To begin with we shall focus only on theories of a single equation, and specifically on this list of 4694 equations (all laws involving at most four magma operations, up to symmetry and relabeling). This creates 4694*(4694-1) = 22,028,942 implications that need to be proven or disproven.

Some selected equations of interest are listed here (in Lean form) and here (in a human readable blueprint).

Some automatically generated progress:

• Sep 28, 2024: 85 laws have been shown to be equivalent to the constant law Equation46, and 815 laws have been shown to be equivalent to the singleton law Equation2. Discussed in the blueprint here.
• Sep 28, 2024: 18972 implications were established by simple rewrite laws. Discussed in the blueprint here.
• Sep 28, 2024: 4.2m implications proven by a transitive reduction of 15k theorems were proven using simple rewrite proof scripts. Discussed in the blueprint here.
• Sep 29, 2024: 13.7m implications were conjectured to be refused by a collection of 515 magmas, collected by enumerating all 4^(4*4) operators and reducing to a covering set. Discussed in the blueprint here.
• Oct 1, 2024: Another ~250k transitive implications were proven by simple proof generation. Discussed in the blueprint here.
• Oct 1, 2024: ~500k transitive implications were proven by a custom tool that chooses hypotheses and leveraged previously found implications to search by using the implied equations as substitutions. Discussed in the blueprint here.
• Oct 2, 2024: 86 (potentially) new implications in Subgraph.lean conclusively (i.e. in Lean) resolved using the lean-egg tactic. Some of these were simply missed by the transitive closure computation and technically already implied, but some were genuinely new.

Some statistics and data files from a given point in time:

• Oct 2, 2024: A list of unknown implications whose converse is proven, i.e. implications that would reduce the number of equivalence classes of equations. At the time of creation we had 2969 equivalence classes. This file contains 4526 unknown implications, if all hold then it will reduce the number of equivalence classes to 1300.
• Sep 28, 2024: A repository of unknown implications, including all unknown implications, known equivalence classes, unknown implications modulo known equivalence, and only the strongest unknown implications.
• Sep 29, 2024: Here is a text file of the (21K or so) direct implications proven to date, and here is the transitive closure of these implications (about 4.5m). More precisely, we have 21791 implications explicitly proven true, 4494090 additional relations implicitly proven true, 739207 explicitly proven false, 12764328 implicitly proven false, one additional relations explicitly conjectured true (and 64 more implicitly conjectured true), and 4014155 remaining implications which remain completely open. Quotienting out by known equivalences, there are 3182453 open implications remaining.
• Oct 2, 2024: 23019 implications explicitly proven true (and an additional 5925922 implicitly proven); 829607 explicitly proven false (and an additional 12994633 implicitly disproven); 38489 explicitly conjectured true (and an additional 1223057 implicitly conjectured), and 79635 explicitly conjectured false (and an additional 1540725 implicitly conjectured false). This only leads 7999 open implications!

Some visualizations from a given point in time:

• Sep 28, 2024: A (manually created) Hasse diagram of the dependencies obtained up to this date for the selected equations of interest can be found here. Note: the orientation in these legacy images is reversed from that in current guidance.
• Sep 28, 2024: A directed acyclic graph of automatically generated implications is here: circular vertices are for nodes representing multiple equivalent equations and equations in green are from Subgraph.lean. Note: the orientation in these legacy images is reversed from that in current guidance.
• Oct 1, 2024: An image visualizing the graph of proved results can be found here. This was generated by outcomes_to_image.py.

Current statistics and data files, updated automatically:

• dashboard

Current visualizations, updated automatically:

• coming soon!

For guidelines on how to contribute, see the CONTRIBUTING.md file.

To build this project after installing Lean and cloning this repository, follow these steps:

% cd equational_theories/
% lake exe cache get
% lake build

• Main web page
  • Blueprint
  • Documentation
  • The Lean Zulip stream for the project
  • Instructions on how to contribute
• A blog post describing the project., Sep 25, 2024.
• Initial discussion on Zulip, Sep 26, 2024.
• Initial discussion on Mastodon, Jul 18, 2023.
  • Followup discussion on Mastodon, Sep 25, 2024.
• The MathOverflow post that inspired the project, Jul 17, 2023.
  • A related MathOverflow post, Jul 16, 2023.
• Scripts
  • Lean
    • extract_implications - extracts implications from one or more Lean files
  • Python
    • find_dual - finds the dual of an equation
    • find_equation_id - finds the equation number of an equation string
    • generate_eqs_list - generates a list of equations
    • generate_graphviz_graph - generates a graphviz dot file, that can be used to create an implication graph
    • generate_image - generates an image of implications
    • generate_most_wanted_list - generates the "most wanted" implications
    • generate_z3_counterexample - given an implication statement between two equations, calls Z3 to try to generate a counterexample
    • process_implications - processes implications from one or more Lean files
  • Ruby
    • generate_graphviz_graph - creates a graphviz graph
    • graph - graph condensation tools
    • transitive_closure - computes the transitive closure of a set of implications
    • transitive_reduction - finds a transitive reduction of a set of implications
• Automated provers for equational theories
  • Prover9 and Mace4
    • aa - a project to use Prover9/Mace4 to brute force axioms for finite mathematical domains
  • Vampire
  • eprover
  • twee
  • zipperposition
  • Z3
  • Knuckledragger
  • A blog post by Philip Zucker testing many of the above provers on a sample implication of this project.
  • "Guided Equality Saturation", Thomas Kœhler, Andrés Goens, Siddharth Bhat, Tobias Grosser, Phil Trinder, Michel Steuwer, Jan 5, 2024.
  • "Rewrite Rule Inference Using Equality Saturation", Chandrakana Nandi, Max Willsey, Amy Zhu, Yisu Remy Wang, Brett Saiki, Adam Anderson, Adriana Schulz, Dan Grossman, Zachary Tatlock, 23 Aug, 2021.
• Other tools
  • egg - e-graphs good