Refutations from 3-element magmas

[danielvarga]

I have python repo https://github.com/danielvarga/magmas that refutes 11,814,111 implications by 3-element counterexamples. I'd like to create a PR here, but as a first-time contributor, let me first ask for suggestions. First of all, where to put this code? Second, what's the most useful way to interface with the Lean efforts? For example, with some more effort and compute, I could provide an 4694 x 4694 x 3 x 3 array with all the counterexamples. (With some special value for "no counterexample for that implication".) Would that work?

It first writes up the boolean matrix S indexed by (equation, magma), for each 3-element magma, and works from there. (S stands for satisfied.) https://terrytao.wordpress.com/2024/09/25/a-pilot-project-in-universal-algebra-to-explore-new-ways-to-collaborate-and-use-machine-assistance/comment-page-1/#comment-685911 gives a bit more info.

The code can create Hasse diagrams (https://static.renyi.hu/ai-shared/daniel/tmp/hasse.html) and the pixel art thing (https://static.renyi.hu/ai-shared/daniel/magmas/implications_3.png).

It's a result of a one-day hackathon between me and ChatGPT, so there are lots of low hanging fruits:

• Code needs huge refactor/cleanup. (I'll definitely do this before submitting the PR.)
• Only deals with the 4347 4-variable equations.
• Hasse diagram creation code is half-finished.

Less low-hanging:

• Could use parallelization and batch-processing to make it work for 4-element magmas.
• Could calculate the 4694 x 4694 x 3 x 3 counterexample grid I have mentioned above.
• At the heart of it, there's a huge Einstein summation. For each formula like x+(y+z), it executes one Einstein summation for each binary operation, vectorized over all magmas. In principle, the whole formula could be evaluated with a single crazy big Einstein summation. That's a TODO item, but I don't know how much would that speed things up.

[teorth]

Thanks for the contribution! We just started creating some guidelines for submission at https://github.com/teorth/equational_theories/blob/main/CONTRIBUTING.md which may answer some of your questions. In particular if your code can generate a large file of proof_wanted claims, that can be output as a Lean file in the generated folder, while your code can be placed in the scripts folder, and a description of the code as a blueprint chapter.

[few]

Hi. I have a similar program that searched N=2 and N=3. I Haven't submitted any result yet, because I think there will be considerable overlap with #19 (or it might even be a strict subset). Instead I'm currently playing with ways to extend the program to N=4. What might be of interest to you and what I'd like to have feedback on is the lean proof template that I'm using. Her is an example:

import Mathlib.Tactic
import equational_theories.Magma
import equational_theories.AllEquations
import Mathlib.Data.Fin.Basic

set_option linter.unusedTactic false

theorem Equation52_not_implies_Equation378 : ∃ (G: Type) (_: Magma G), Equation52 G ∧ ¬ Equation378 G := by
  let G := Fin 4
  let hG : Magma G := {
      op := fun x y ↦ match x, y with
        | 0, 0 => 3
        | 0, 1 => 0
        | 0, 2 => 0
        | 0, 3 => 1
        | 1, 0 => 1
        | 1, 1 => 2
        | 1, 2 => 3
        | 1, 3 => 1
        | 2, 0 => 0
        | 2, 1 => 2
        | 2, 2 => 3
        | 2, 3 => 1
        | 3, 0 => 3
        | 3, 1 => 2
        | 3, 2 => 3
        | 3, 3 => 1
  }
  refine ⟨G, hG, ?eq52, ?neq378⟩
  ·
    intro x y
    fin_cases x <;>
    fin_cases y <;>    
    all_goals simp [hG]
  ·
    intro h
    specialize h 2 0
    simp [hG] at h
    try { exact Fin.ne_of_val_ne (by decide) h }

I only switch out the equation numbers, the table and the counter example at the bottom.

[carlini]

I've completely solved N=4 via brute force. This generates just ~500k unique tables that need to be converted into Lean. Almost all of these are already covered by #19, but this gives an extra 0.9% set of refutations that weren't found previously. I can start a PR that has the code to do this and let someone pick up where I left off.

[nomeata]

I believe this is subsumed by existing work now, is it?

[danielvarga]

@nomeata: yes, it is subsumed by existing work.