Skip to main content

logicaffeine_proof/
arith.rs

1//! Proof-PRODUCING arithmetic oracle (untrusted search, kernel-checked proof).
2//!
3//! Given an `Int` equality goal `Eq Int lhs rhs`, [`prove_int_eq`] searches for a
4//! genuine kernel proof term and returns it — or `None`. Nothing here is trusted:
5//! whatever it returns is re-checked by the kernel's `infer_type`, so a wrong
6//! proof is rejected, never believed. This is the Coq-`lia`/`nia` model — the fast
7//! search lives outside the trusted base; a bug here can only cause a *failed*
8//! proof, never a false one.
9//!
10//! Trust boundary: closed/literal goals use exact kernel computation and
11//! reflexivity. Symbolic ring proofs apply the registered law names. The standard
12//! prelude now gives checked proof bodies to add_comm, add_zero, mul_comm,
13//! mul_one, mul_zero, mul_assoc, add_assoc, mul_distrib_add and sub_elim.
14//! These ring proofs now have empty transitive axiom dependencies.
15//! sub_elim states a - b = a + (-1)*b, exposing subtraction to this vocabulary.
16//! The oracle itself remains an untrusted proof producer.
17
18use logicaffeine_kernel::{
19    int_lit, lit_bigint, normalize, normalize_at, normalize_checked, BigInt, Context, Literal,
20    Term, Transparency,
21};
22
23fn global(name: &str) -> Term {
24    Term::Global(name.to_string())
25}
26fn app(f: Term, x: Term) -> Term {
27    Term::App(Box::new(f), Box::new(x))
28}
29fn app2(f: Term, x: Term, y: Term) -> Term {
30    app(app(f, x), y)
31}
32fn app3(f: Term, x: Term, y: Term, z: Term) -> Term {
33    app(app2(f, x, y), z)
34}
35fn int() -> Term {
36    global("Int")
37}
38
39/// `refl Int t`
40fn refl(t: Term) -> Term {
41    app2(global("refl"), int(), t)
42}
43
44/// `Eq_sym Int x y proof` : turns a proof of `Eq Int x y` into `Eq Int y x`.
45fn eq_sym(x: Term, y: Term, proof: Term) -> Term {
46    app(app(app(app(global("Eq_sym"), int()), x), y), proof)
47}
48
49/// Match `op a b` (i.e. `App(App(Global op, a), b)`), returning `(a, b)`.
50fn match_bin(t: &Term, op: &str) -> Option<(Term, Term)> {
51    if let Term::App(f, b) = t {
52        if let Term::App(g, a) = f.as_ref() {
53            if let Term::Global(name) = g.as_ref() {
54                if name == op {
55                    return Some(((**a).clone(), (**b).clone()));
56                }
57            }
58        }
59    }
60    None
61}
62
63/// Definitional equality check: do `a` and `b` share a normal form?
64fn conv(ctx: &Context, a: &Term, b: &Term) -> bool {
65    normalize(ctx, a) == normalize(ctx, b)
66}
67
68/// Prove an `Int` equality `Eq Int lhs rhs`, or return `None`.
69///
70/// The returned term, when it exists, has type `Eq Int lhs rhs` (the kernel will
71/// confirm). `None` means "this oracle found no proof" — never "it is false."
72pub fn prove_int_eq(ctx: &Context, lhs: &Term, rhs: &Term) -> Option<Term> {
73    if !logicaffeine_kernel::int_inductive::supports_integer_polynomial_operations(ctx) {
74        return None;
75    }
76    // Expose ordinary wrappers without erasing the polynomial vocabulary into
77    // constructor matches. These are definitionally equal views of the original
78    // goals; the eventual proof is still checked against the original goal.
79    let lhs = polynomial_view(ctx, lhs);
80    let rhs = polynomial_view(ctx, rhs);
81    let (lhs, rhs) = (&lhs, &rhs);
82
83    // Closed arithmetic is a computation problem, regardless of literal width.
84    // Reuse checked normalization before invoking symbolic proof search;
85    // exhaustion declines rather than treating a partial result as a value.
86    if ground_integer_expression(lhs) && ground_integer_expression(rhs) {
87        let left_value = normalize_checked(ctx, lhs).ok()?;
88        let right_value = normalize_checked(ctx, rhs).ok()?;
89        return match (&left_value, &right_value) {
90            (
91                Term::Lit(Literal::Int(_) | Literal::BigInt(_)),
92                Term::Lit(Literal::Int(_) | Literal::BigInt(_)),
93            ) if left_value == right_value => Some(refl(left_value)),
94            _ => None,
95        };
96    }
97
98    // Complete negative decision: two terms are a *formal* ring identity iff they
99    // have the same canonical polynomial. If they differ, no proof exists — bail
100    // fast (and never waste the search on a non-identity).
101    let mut polys = Polynomials { atoms: Vec::new() };
102    let pl = to_poly(&mut polys, ctx, lhs);
103    let pr = to_poly(&mut polys, ctx, rhs);
104    if pl != pr {
105        return None;
106    }
107
108    // Positive proof: bounded rewrite search first…
109    if let Some(p) = prove_eq(ctx, lhs, rhs, MAX_REWRITE_DEPTH) {
110        return Some(p);
111    }
112    // …then the proof-producing normalizer (handles coefficient collection / FOIL
113    // that the bounded search can't reach). Additive & sound: returns None if it
114    // can't build a proof, and every proof it returns is kernel-checked.
115    prove_by_normalization(ctx, lhs, rhs)
116}
117
118// =============================================================================
119// Polynomial decision layer — canonical multivariate polynomials over opaque
120// atoms (any non-add/mul/sub/literal subterm). Used for the fast, complete
121// negative decision and as the target of the proof-producing normalizer.
122// =============================================================================
123
124/// Atom interner: distinct non-arithmetic subterms get stable ids.
125struct Polynomials {
126    atoms: Vec<Term>,
127}
128impl Polynomials {
129    fn atom_id(&mut self, t: &Term) -> usize {
130        if let Some(i) = self.atoms.iter().position(|a| a == t) {
131            i
132        } else {
133            self.atoms.push(t.clone());
134            self.atoms.len() - 1
135        }
136    }
137}
138
139/// A monomial: a sorted multiset of atom ids (`[]` = the constant monomial).
140type Mono = Vec<usize>;
141/// A polynomial: monomials with nonzero coefficients, sorted, like terms combined.
142type Poly = Vec<(Mono, BigInt)>;
143
144fn poly_canon(mut terms: Poly) -> Poly {
145    for (m, _) in terms.iter_mut() {
146        m.sort_unstable();
147    }
148    terms.sort_by(|a, b| a.0.cmp(&b.0));
149    let mut out: Poly = Vec::new();
150    for (m, c) in terms {
151        if c.is_zero() {
152            continue;
153        }
154        if let Some(last) = out.last_mut() {
155            if last.0 == m {
156                last.1 = last.1.add(&c);
157                if last.1.is_zero() {
158                    out.pop();
159                }
160                continue;
161            }
162        }
163        out.push((m, c));
164    }
165    out
166}
167
168fn poly_add(a: &Poly, b: &Poly) -> Poly {
169    let mut t = a.clone();
170    t.extend(b.iter().cloned());
171    poly_canon(t)
172}
173fn poly_mul(a: &Poly, b: &Poly) -> Poly {
174    let mut t = Vec::new();
175    for (m1, c1) in a {
176        for (m2, c2) in b {
177            let mut m = m1.clone();
178            m.extend(m2.iter().cloned());
179            t.push((m, c1.mul(c2)));
180        }
181    }
182    poly_canon(t)
183}
184fn poly_scale(k: i64, a: &Poly) -> Poly {
185    let k = BigInt::from_i64(k);
186    poly_canon(a.iter().map(|(m, c)| (m.clone(), c.mul(&k))).collect())
187}
188
189/// Recognize the closed literal fragment without unfolding symbolic operations.
190/// An explicit work stack keeps this grammar check independent of native depth.
191fn ground_integer_expression(term: &Term) -> bool {
192    let mut pending = vec![term];
193    while let Some(term) = pending.pop() {
194        match term {
195            Term::Lit(Literal::Int(_) | Literal::BigInt(_)) => {}
196            Term::App(function, right) => {
197                let Term::App(head, left) = function.as_ref() else {
198                    return false;
199                };
200                let Term::Global(name) = head.as_ref() else {
201                    return false;
202                };
203                if !matches!(name.as_str(), "add" | "mul" | "sub") {
204                    return false;
205                }
206                pending.push(left);
207                pending.push(right);
208            }
209            _ => return false,
210        }
211    }
212    true
213}
214
215/// The ring oracle owns this local transparency choice. The trusted kernel
216/// retains full unfolding when checking the resulting proof.
217fn polynomial_view(ctx: &Context, term: &Term) -> Term {
218    normalize_at(
219        ctx,
220        term,
221        Transparency::Excluding(&|name| matches!(name, "add" | "mul" | "sub")),
222    )
223}
224
225/// Compute the canonical polynomial of an arithmetic term.
226fn to_poly(p: &mut Polynomials, ctx: &Context, t: &Term) -> Poly {
227    let t = polynomial_view(ctx, t);
228    if let Term::Lit(literal) = &t {
229        if let Some(n) = lit_bigint(literal) {
230            return if n.is_zero() {
231                vec![]
232            } else {
233                vec![(vec![], n)]
234            };
235        }
236    }
237    if let Some((a, b)) = match_bin(&t, "add") {
238        return poly_add(&to_poly(p, ctx, &a), &to_poly(p, ctx, &b));
239    }
240    if let Some((a, b)) = match_bin(&t, "mul") {
241        return poly_mul(&to_poly(p, ctx, &a), &to_poly(p, ctx, &b));
242    }
243    if let Some((a, b)) = match_bin(&t, "sub") {
244        return poly_add(&to_poly(p, ctx, &a), &poly_scale(-1, &to_poly(p, ctx, &b)));
245    }
246    let id = p.atom_id(&t);
247    vec![(vec![id], BigInt::from_i64(1))]
248}
249
250// =============================================================================
251// Proof-producing canonical normalizer.
252//
253// `norm(t)` returns `(c, proof : Eq Int t c)` where `c = reify(to_poly t)` is the
254// deterministic canonical term. Because the negative guard already established
255// `to_poly(lhs) == to_poly(rhs)`, the two canonical terms are identical, so the
256// goal follows by transitivity. Every proof is built from the ring axioms and is
257// re-checked by the kernel — the normalizer is untrusted.
258// =============================================================================
259
260fn lit_t(n: i64) -> Term {
261    Term::Lit(Literal::Int(n))
262}
263
264/// Emit one canonical literal for an exact coefficient, demoting small results.
265fn coefficient_term(n: &BigInt) -> Term {
266    Term::Lit(int_lit(n.clone()))
267}
268fn ax1(name: &str, a: Term) -> Term {
269    app(global(name), a)
270}
271fn ax2(name: &str, a: Term, b: Term) -> Term {
272    app2(global(name), a, b)
273}
274fn ax3(name: &str, a: Term, b: Term, c: Term) -> Term {
275    app3(global(name), a, b, c)
276}
277
278/// The product term for a monomial (left-assoc), or `None` for the empty monomial.
279fn mono_to_term(mono: &[usize], atoms: &[Term]) -> Option<Term> {
280    let mut iter = mono.iter();
281    let first = *iter.next()?;
282    let mut t = atoms[first].clone();
283    for &id in iter {
284        t = ax2("mul", t, atoms[id].clone());
285    }
286    Some(t)
287}
288/// The canonical term for one `(monomial, coeff)`.
289fn scaled_term(mono: &[usize], coeff: &BigInt, atoms: &[Term]) -> Term {
290    match mono_to_term(mono, atoms) {
291        None => coefficient_term(coeff),
292        Some(m) if coeff.to_i64() == Some(1) => m,
293        Some(m) => ax2("mul", coefficient_term(coeff), m),
294    }
295}
296/// The canonical term for a whole polynomial (left-assoc sum, sorted).
297fn reify(poly: &[(Mono, BigInt)], atoms: &[Term]) -> Term {
298    // Drop zero-coefficient monomials so the canonical form is unique (a cancelled
299    // term must not linger as `add 0 …` / `mul 0 …`, which would make two equal
300    // polynomials reify to syntactically different terms).
301    let mut iter = poly.iter().filter(|(_, c)| !c.is_zero());
302    let Some((m0, c0)) = iter.next() else {
303        return lit_t(0);
304    };
305    let mut t = scaled_term(m0, c0, atoms);
306    for (m, c) in iter {
307        t = ax2("add", t, scaled_term(m, c, atoms));
308    }
309    t
310}
311
312/// Proof `term = mul (lit c) M`, where `term = scaled_term(m, c)` and `M = mono_to_term(m)`.
313/// For `c == 1` the term is the bare monomial `M`, coerced via `mul_one`/`mul_comm`.
314fn as_scaled_mul(c: &BigInt, m_term: &Term) -> Term {
315    if c.to_i64() == Some(1) {
316        // M = mul 1 M  via  sym (mul 1 M = mul M 1 = M)
317        let mul1m = ax2("mul", lit_t(1), m_term.clone());
318        let chain = eq_trans(
319            mul1m.clone(),
320            ax2("mul", m_term.clone(), lit_t(1)),
321            m_term.clone(),
322            ax2("mul_comm", lit_t(1), m_term.clone()),
323            ax1("mul_one", m_term.clone()),
324        );
325        eq_sym(mul1m, m_term.clone(), chain)
326    } else {
327        refl(ax2("mul", coefficient_term(c), m_term.clone()))
328    }
329}
330
331/// Proof `add (mul c1 M) (mul c2 M) = mul (add c1 c2) M`  (right reverse-distribution).
332fn rev_distrib(c1: &BigInt, c2: &BigInt, m_term: &Term) -> Term {
333    let big_c = ax2("add", coefficient_term(c1), coefficient_term(c2));
334    let mul_c1 = ax2("mul", coefficient_term(c1), m_term.clone());
335    let mul_c2 = ax2("mul", coefficient_term(c2), m_term.clone());
336    // mul C M = mul M C
337    let s1 = ax2("mul_comm", big_c.clone(), m_term.clone());
338    // mul M C = add (mul M c1) (mul M c2)
339    let s2 = ax3(
340        "mul_distrib_add",
341        m_term.clone(),
342        coefficient_term(c1),
343        coefficient_term(c2),
344    );
345    // add (mul M c1)(mul M c2) = add (mul c1 M)(mul c2 M)
346    let s3 = cong2(
347        "add",
348        &ax2("mul", m_term.clone(), coefficient_term(c1)),
349        &mul_c1,
350        &ax2("mul", m_term.clone(), coefficient_term(c2)),
351        &mul_c2,
352        ax2("mul_comm", m_term.clone(), coefficient_term(c1)),
353        ax2("mul_comm", m_term.clone(), coefficient_term(c2)),
354    );
355    // mul C M = add (mul c1 M)(mul c2 M)
356    let forward = eq_trans(
357        ax2("mul", big_c.clone(), m_term.clone()),
358        ax2("mul", m_term.clone(), big_c.clone()),
359        ax2("add", mul_c1.clone(), mul_c2.clone()),
360        s1,
361        eq_trans(
362            ax2("mul", m_term.clone(), big_c.clone()),
363            ax2(
364                "add",
365                ax2("mul", m_term.clone(), coefficient_term(c1)),
366                ax2("mul", m_term.clone(), coefficient_term(c2)),
367            ),
368            ax2("add", mul_c1.clone(), mul_c2.clone()),
369            s2,
370            s3,
371        ),
372    );
373    eq_sym(
374        ax2("mul", big_c, m_term.clone()),
375        ax2("add", mul_c1, mul_c2),
376        forward,
377    )
378}
379
380/// Proof `add (scaled m c1) (scaled m c2) = scaled m (c1+c2)` for the SAME monomial `m`.
381fn combine_coeff(m: &[usize], c1: &BigInt, c2: &BigInt, atoms: &[Term]) -> Option<Term> {
382    let t1 = scaled_term(m, c1, atoms);
383    let t2 = scaled_term(m, c2, atoms);
384    let sum = c1.add(c2);
385    let result = scaled_term(m, &sum, atoms);
386    let _ = (&t1, &t2, &result);
387    match mono_to_term(m, atoms) {
388        // constant terms: `add (lit c1)(lit c2)` ≡ `lit (c1+c2)` by computation.
389        None => Some(refl(coefficient_term(&sum))),
390        Some(m_term) => {
391            // add t1 t2 = add (mul c1 M)(mul c2 M)  [coerce]  = mul (c1+c2) M  [rev_distrib]
392            let coerce = cong2(
393                "add",
394                &t1,
395                &ax2("mul", coefficient_term(c1), m_term.clone()),
396                &t2,
397                &ax2("mul", coefficient_term(c2), m_term.clone()),
398                as_scaled_mul(c1, &m_term),
399                as_scaled_mul(c2, &m_term),
400            );
401            let rd = rev_distrib(c1, c2, &m_term);
402            let coerced = ax2(
403                "add",
404                ax2("mul", coefficient_term(c1), m_term.clone()),
405                ax2("mul", coefficient_term(c2), m_term.clone()),
406            );
407            if sum.to_i64() != Some(1) {
408                Some(eq_trans(ax2("add", t1, t2), coerced, result, coerce, rd))
409            } else {
410                // c1+c2 == 1: the result is the bare monomial, so extend the chain
411                // past `mul 1 M` (what rev_distrib's RHS reduces to) with
412                // `mul 1 M = mul M 1 = M`.
413                let mul1m = ax2("mul", lit_t(1), m_term.clone());
414                let to_bare = eq_trans(
415                    mul1m.clone(),
416                    ax2("mul", m_term.clone(), lit_t(1)),
417                    m_term.clone(),
418                    ax2("mul_comm", lit_t(1), m_term.clone()),
419                    ax1("mul_one", m_term.clone()),
420                );
421                let inner = eq_trans(coerced.clone(), mul1m, result.clone(), rd, to_bare);
422                Some(eq_trans(ax2("add", t1, t2), coerced, result, coerce, inner))
423            }
424        }
425    }
426}
427
428/// Proof `add (add X Y) Z = add (add X Z) Y` (move `Z` past `Y`).
429fn swap_top(x: Term, y: Term, z: Term) -> Term {
430    // add(add X Y)Z = add X (add Y Z) = add X (add Z Y) = add(add X Z)Y
431    let s1 = ax3("add_assoc", x.clone(), y.clone(), z.clone());
432    let s2 = cong2(
433        "add",
434        &x,
435        &x,
436        &ax2("add", y.clone(), z.clone()),
437        &ax2("add", z.clone(), y.clone()),
438        refl(x.clone()),
439        ax2("add_comm", y.clone(), z.clone()),
440    );
441    let s3 = eq_sym(
442        ax2("add", ax2("add", x.clone(), z.clone()), y.clone()),
443        ax2("add", x.clone(), ax2("add", z.clone(), y.clone())),
444        ax3("add_assoc", x.clone(), z.clone(), y.clone()),
445    );
446    eq_trans(
447        ax2("add", ax2("add", x.clone(), y.clone()), z.clone()),
448        ax2("add", x.clone(), ax2("add", y.clone(), z.clone())),
449        ax2("add", ax2("add", x.clone(), z.clone()), y.clone()),
450        s1,
451        eq_trans(
452            ax2("add", x.clone(), ax2("add", y.clone(), z.clone())),
453            ax2("add", x.clone(), ax2("add", z.clone(), y.clone())),
454            ax2("add", ax2("add", x.clone(), z.clone()), y),
455            s2,
456            s3,
457        ),
458    )
459}
460
461/// Insert one `(mono, coeff)` term into a canonical poly `p`, returning
462/// `(result_poly, proof : add (reify p) (scaled term) = reify(result))`.
463fn merge_term(
464    atoms: &[Term],
465    p: &[(Mono, BigInt)],
466    m: &[usize],
467    c: &BigInt,
468) -> Option<(Poly, Term)> {
469    let st = scaled_term(m, c, atoms);
470    if p.is_empty() {
471        // add (lit 0) st = add st 0 = st
472        let proof = eq_trans(
473            ax2("add", lit_t(0), st.clone()),
474            ax2("add", st.clone(), lit_t(0)),
475            st.clone(),
476            ax2("add_comm", lit_t(0), st.clone()),
477            ax1("add_zero", st.clone()),
478        );
479        return Some((vec![(m.to_vec(), c.clone())], proof));
480    }
481    let (ml, cl) = p.last().unwrap().clone();
482    let init = &p[..p.len() - 1];
483    let last_t = scaled_term(&ml, &cl, atoms);
484    let reify_p = reify(p, atoms);
485
486    use std::cmp::Ordering;
487    match m.to_vec().cmp(&ml) {
488        Ordering::Greater => {
489            // already sorted: structurally reify(p ++ [term])
490            let mut res = p.to_vec();
491            res.push((m.to_vec(), c.clone()));
492            Some((res, refl(ax2("add", reify_p, st))))
493        }
494        Ordering::Equal => {
495            if cl.add(c).is_zero() {
496                // The monomial cancels (`cl·M + c·M = 0`), so it drops from the
497                // canonical form. `combine_coeff` gives `add last_t st = mul 0 M`;
498                // chain `mul 0 M = mul M 0 (mul_comm) = 0 (mul_zero)`.
499                let cc = combine_coeff(&ml, &cl, c, atoms)?;
500                let cancel = match mono_to_term(&ml, atoms) {
501                    None => cc, // constant monomial: `scaled(ml, 0)` is already `lit 0`
502                    Some(m_term) => eq_trans(
503                        ax2("add", last_t.clone(), st.clone()),
504                        ax2("mul", lit_t(0), m_term.clone()),
505                        lit_t(0),
506                        cc,
507                        eq_trans(
508                            ax2("mul", lit_t(0), m_term.clone()),
509                            ax2("mul", m_term.clone(), lit_t(0)),
510                            lit_t(0),
511                            ax2("mul_comm", lit_t(0), m_term.clone()),
512                            ax1("mul_zero", m_term),
513                        ),
514                    ),
515                };
516                // cancel : add last_t st = 0
517                if init.is_empty() {
518                    return Some((vec![], cancel));
519                }
520                let ri = reify(init, atoms);
521                let assoc = ax3("add_assoc", ri.clone(), last_t.clone(), st.clone());
522                let cong = cong2(
523                    "add",
524                    &ri,
525                    &ri,
526                    &ax2("add", last_t.clone(), st.clone()),
527                    &lit_t(0),
528                    refl(ri.clone()),
529                    cancel,
530                );
531                let azero = ax1("add_zero", ri.clone());
532                let proof = eq_trans(
533                    ax2("add", ax2("add", ri.clone(), last_t.clone()), st.clone()),
534                    ax2("add", ri.clone(), ax2("add", last_t.clone(), st.clone())),
535                    ri.clone(),
536                    assoc,
537                    eq_trans(
538                        ax2("add", ri.clone(), ax2("add", last_t.clone(), st.clone())),
539                        ax2("add", ri.clone(), lit_t(0)),
540                        ri.clone(),
541                        cong,
542                        azero,
543                    ),
544                );
545                return Some((init.to_vec(), proof));
546            }
547            let cc = combine_coeff(&ml, &cl, c, atoms)?; // add last_t st = scaled(ml, cl+c)
548            let combined = scaled_term(&ml, &cl.add(c), atoms);
549            if init.is_empty() {
550                Some((vec![(ml, cl.add(c))], cc))
551            } else {
552                let ri = reify(init, atoms);
553                let assoc = ax3("add_assoc", ri.clone(), last_t.clone(), st.clone());
554                let cong = cong2(
555                    "add",
556                    &ri,
557                    &ri,
558                    &ax2("add", last_t.clone(), st.clone()),
559                    &combined,
560                    refl(ri.clone()),
561                    cc,
562                );
563                let proof = eq_trans(
564                    ax2("add", ax2("add", ri.clone(), last_t), st),
565                    ax2(
566                        "add",
567                        ri.clone(),
568                        ax2(
569                            "add",
570                            scaled_term(&ml, &cl, atoms),
571                            scaled_term(m, c, atoms),
572                        ),
573                    ),
574                    ax2("add", ri.clone(), combined),
575                    assoc,
576                    cong,
577                );
578                let mut res = init.to_vec();
579                res.push((ml, cl.add(c)));
580                Some((res, proof))
581            }
582        }
583        Ordering::Less => {
584            if init.is_empty() {
585                // add last_t st = add st last_t
586                let mut res = vec![(m.to_vec(), c.clone())];
587                res.push((ml, cl));
588                Some((res, ax2("add_comm", last_t, st)))
589            } else {
590                let ri = reify(init, atoms);
591                let swap = swap_top(ri.clone(), last_t.clone(), st.clone());
592                let (init2, inner) = merge_term(atoms, init, m, c)?; // add ri st = reify(init2)
593                let ri2 = reify(&init2, atoms);
594                let cong = cong2(
595                    "add",
596                    &ax2("add", ri.clone(), st.clone()),
597                    &ri2,
598                    &last_t,
599                    &last_t,
600                    inner,
601                    refl(last_t.clone()),
602                );
603                let proof = eq_trans(
604                    ax2("add", ax2("add", ri.clone(), last_t.clone()), st.clone()),
605                    ax2("add", ax2("add", ri, st.clone()), last_t.clone()),
606                    ax2("add", ri2.clone(), last_t.clone()),
607                    swap,
608                    cong,
609                );
610                // If the merge cancelled all of `init`, the result reifies to the
611                // bare `last_t` — eliminate the `add 0 last_t` residue so the
612                // proof's conclusion IS the canonical form.
613                let proof = if init2.is_empty() {
614                    let zfix = eq_trans(
615                        ax2("add", lit_t(0), last_t.clone()),
616                        ax2("add", last_t.clone(), lit_t(0)),
617                        last_t.clone(),
618                        ax2("add_comm", lit_t(0), last_t.clone()),
619                        ax1("add_zero", last_t.clone()),
620                    );
621                    eq_trans(
622                        ax2(
623                            "add",
624                            ax2("add", reify(init, atoms), last_t.clone()),
625                            st.clone(),
626                        ),
627                        ax2("add", ri2, last_t.clone()),
628                        last_t.clone(),
629                        proof,
630                        zfix,
631                    )
632                } else {
633                    proof
634                };
635                let mut res = init2;
636                res.push((ml, cl));
637                Some((res, proof))
638            }
639        }
640    }
641}
642
643/// Merge two canonical polynomials, returning
644/// `(merged, proof : add (reify pa)(reify pb) = reify(merged))`.
645fn merge_canonical(
646    atoms: &[Term],
647    pa: &[(Mono, BigInt)],
648    pb: &[(Mono, BigInt)],
649) -> Option<(Poly, Term)> {
650    let ra = reify(pa, atoms);
651    if pb.is_empty() {
652        // add (reify pa) 0 = reify pa
653        return Some((pa.to_vec(), ax1("add_zero", ra)));
654    }
655    if pb.len() == 1 {
656        let (m, c) = &pb[0];
657        return merge_term(atoms, pa, m, c);
658    }
659    let (ml, cl) = pb.last().unwrap().clone();
660    let pb_init = &pb[..pb.len() - 1];
661    let rbi = reify(pb_init, atoms);
662    let slast = scaled_term(&ml, &cl, atoms);
663    // add ra (add rbi slast) = add (add ra rbi) slast
664    let assoc_sym = eq_sym(
665        ax2("add", ax2("add", ra.clone(), rbi.clone()), slast.clone()),
666        ax2("add", ra.clone(), ax2("add", rbi.clone(), slast.clone())),
667        ax3("add_assoc", ra.clone(), rbi.clone(), slast.clone()),
668    );
669    let (m1, p1) = merge_canonical(atoms, pa, pb_init)?; // add ra rbi = reify(m1)
670    let rm1 = reify(&m1, atoms);
671    let cong = cong2(
672        "add",
673        &ax2("add", ra.clone(), rbi.clone()),
674        &rm1,
675        &slast,
676        &slast,
677        p1,
678        refl(slast.clone()),
679    );
680    let (m2, p2) = merge_term(atoms, &m1, &ml, &cl)?; // add rm1 slast = reify(m2)
681    let rm2 = reify(&m2, atoms);
682    let proof = eq_trans(
683        ax2("add", ra.clone(), ax2("add", rbi.clone(), slast.clone())),
684        ax2("add", ax2("add", ra, rbi), slast.clone()),
685        rm2,
686        assoc_sym,
687        eq_trans(
688            ax2(
689                "add",
690                ax2("add", reify(pa, atoms), reify(pb_init, atoms)),
691                slast.clone(),
692            ),
693            ax2("add", rm1, slast),
694            reify(&m2, atoms),
695            cong,
696            p2,
697        ),
698    );
699    Some((m2, proof))
700}
701
702/// The id of an ALREADY-interned atom (non-inserting); `None` for a literal / non-atom, which the
703/// constructive monomial sort declines (the caller falls back to the bounded search).
704fn atom_index(polys: &Polynomials, t: &Term) -> Option<usize> {
705    polys.atoms.iter().position(|a| a == t)
706}
707
708/// Swap the last two factors of a left-assoc product: proof of `mul(mul(A,b),x) = mul(mul(A,x),b)`,
709/// built from `mul_assoc` (twice) and one `mul_comm` under a congruence.
710fn swap_last(a: &Term, b: &Term, x: &Term) -> Term {
711    let m_ab_x = ax2("mul", ax2("mul", a.clone(), b.clone()), x.clone());
712    let m_a_bx = ax2("mul", a.clone(), ax2("mul", b.clone(), x.clone()));
713    let m_a_xb = ax2("mul", a.clone(), ax2("mul", x.clone(), b.clone()));
714    let m_ax_b = ax2("mul", ax2("mul", a.clone(), x.clone()), b.clone());
715    // mul(mul(A,b),x) = mul(A, mul(b,x))
716    let s1 = ax3("mul_assoc", a.clone(), b.clone(), x.clone());
717    // mul(A, mul(b,x)) = mul(A, mul(x,b))    (mul_comm under A)
718    let s2 = cong2(
719        "mul",
720        a,
721        a,
722        &ax2("mul", b.clone(), x.clone()),
723        &ax2("mul", x.clone(), b.clone()),
724        refl(a.clone()),
725        ax2("mul_comm", b.clone(), x.clone()),
726    );
727    // mul(A, mul(x,b)) = mul(mul(A,x), b)
728    let s3 = eq_sym(
729        m_ax_b.clone(),
730        m_a_xb.clone(),
731        ax3("mul_assoc", a.clone(), x.clone(), b.clone()),
732    );
733    let inner = eq_trans(m_a_bx.clone(), m_a_xb, m_ax_b.clone(), s2, s3); // mul(A,mul(b,x)) = mul(mul(A,x),b)
734    eq_trans(m_ab_x, m_a_bx, m_ax_b, s1, inner)
735}
736
737/// Insert atom `x` into the sorted product `p`. Returns `(result, proof : mul(p,x) = result)` where
738/// `result` is `p` with `x` in its sorted position. `None` if a factor is not an interned atom.
739fn insert_atom(polys: &Polynomials, p: &Term, x: &Term) -> Option<(Term, Term)> {
740    let xid = atom_index(polys, x)?;
741    let prod = ax2("mul", p.clone(), x.clone());
742    match match_bin(p, "mul") {
743        None => {
744            let pid = atom_index(polys, p)?;
745            if pid <= xid {
746                Some((prod.clone(), refl(prod)))
747            } else {
748                Some((
749                    ax2("mul", x.clone(), p.clone()),
750                    ax2("mul_comm", p.clone(), x.clone()),
751                ))
752            }
753        }
754        Some((pinit, plast)) => {
755            let lastid = atom_index(polys, &plast)?;
756            if lastid <= xid {
757                Some((prod.clone(), refl(prod)))
758            } else {
759                // swap x past plast, then insert into pinit
760                let swap = swap_last(&pinit, &plast, x); // mul(mul(pinit,plast),x) = mul(mul(pinit,x),plast)
761                let (inner, pin) = insert_atom(polys, &pinit, x)?; // mul(pinit,x) = inner
762                let cong = cong2(
763                    "mul",
764                    &ax2("mul", pinit.clone(), x.clone()),
765                    &inner,
766                    &plast,
767                    &plast,
768                    pin,
769                    refl(plast.clone()),
770                );
771                let result = ax2("mul", inner, plast.clone());
772                let proof = eq_trans(
773                    prod,
774                    ax2("mul", ax2("mul", pinit.clone(), x.clone()), plast.clone()),
775                    result.clone(),
776                    swap,
777                    cong,
778                );
779                Some((result, proof))
780            }
781        }
782    }
783}
784
785/// Merge two sorted atom-products `ca`, `cb` into one sorted product.
786/// Returns `(result, proof : mul(ca,cb) = result)`, or `None` (any non-atom factor).
787fn merge_sorted(polys: &Polynomials, ca: &Term, cb: &Term) -> Option<(Term, Term)> {
788    match match_bin(cb, "mul") {
789        None => insert_atom(polys, ca, cb),
790        Some((cbinit, cblast)) => {
791            // mul(ca, mul(cbinit,cblast)) = mul(mul(ca,cbinit), cblast)   (eq_sym mul_assoc)
792            let assoc_rev = eq_sym(
793                ax2(
794                    "mul",
795                    ax2("mul", ca.clone(), cbinit.clone()),
796                    cblast.clone(),
797                ),
798                ax2(
799                    "mul",
800                    ca.clone(),
801                    ax2("mul", cbinit.clone(), cblast.clone()),
802                ),
803                ax3("mul_assoc", ca.clone(), cbinit.clone(), cblast.clone()),
804            );
805            let (merged1, p1) = merge_sorted(polys, ca, &cbinit)?; // mul(ca,cbinit) = merged1
806            let cong = cong2(
807                "mul",
808                &ax2("mul", ca.clone(), cbinit.clone()),
809                &merged1,
810                &cblast,
811                &cblast,
812                p1,
813                refl(cblast.clone()),
814            );
815            let (merged2, p2) = insert_atom(polys, &merged1, &cblast)?; // mul(merged1,cblast) = merged2
816            let start = ax2("mul", ca.clone(), cb.clone());
817            let mid = ax2(
818                "mul",
819                ax2("mul", ca.clone(), cbinit.clone()),
820                cblast.clone(),
821            );
822            let proof = eq_trans(
823                start,
824                mid.clone(),
825                merged2.clone(),
826                assoc_rev,
827                eq_trans(
828                    mid,
829                    ax2("mul", merged1.clone(), cblast.clone()),
830                    merged2.clone(),
831                    cong,
832                    p2,
833                ),
834            );
835            Some((merged2, proof))
836        }
837    }
838}
839
840/// Split a canonical monomial into `(coeff, atom_product)`: `lit(n)` → `(n, None)`;
841/// `mul(lit n, M)` → `(n, Some(M))`; a bare atom product → `(1, Some(t))`. The coefficient of a
842/// `scaled_term` always sits at the outermost-left, so this is exact.
843fn split_coeff(t: &Term) -> (BigInt, Option<Term>) {
844    if let Term::Lit(literal) = t {
845        if let Some(n) = lit_bigint(literal) {
846            return (n, None);
847        }
848    }
849    if let Some((a, b)) = match_bin(t, "mul") {
850        if let Term::Lit(literal) = a {
851            if let Some(n) = lit_bigint(&literal) {
852                return (n, Some(b));
853            }
854        }
855    }
856    (BigInt::from_i64(1), Some(t.clone()))
857}
858
859/// Swap the two middle factors of a product-of-products: proof of
860/// `mul(mul(P,Q), mul(R,S)) = mul(mul(P,R), mul(Q,S))`, a fixed 5-step assoc/comm chain
861/// (independent of the degree of P,Q,R,S). Used to hoist coefficients out of a monomial product.
862fn swap_middle(p: &Term, q: &Term, r: &Term, s: &Term) -> Term {
863    let rs = ax2("mul", r.clone(), s.clone());
864    let qs = ax2("mul", q.clone(), s.clone());
865    let qr = ax2("mul", q.clone(), r.clone());
866    let rq = ax2("mul", r.clone(), q.clone());
867    let w0 = ax2("mul", ax2("mul", p.clone(), q.clone()), rs.clone());
868    let w1 = ax2("mul", p.clone(), ax2("mul", q.clone(), rs.clone()));
869    let w2 = ax2("mul", p.clone(), ax2("mul", qr.clone(), s.clone()));
870    let w3 = ax2("mul", p.clone(), ax2("mul", rq.clone(), s.clone()));
871    let w4 = ax2("mul", p.clone(), ax2("mul", r.clone(), qs.clone()));
872    let w5 = ax2("mul", ax2("mul", p.clone(), r.clone()), qs.clone());
873    // w0 = w1 : mul_assoc P Q (mul R S)
874    let p01 = ax3("mul_assoc", p.clone(), q.clone(), rs.clone());
875    // w1 = w2 : under P, sym(mul_assoc Q R S) turns mul(Q, mul(R,S)) into mul(mul(Q,R), S)
876    let p12 = cong2(
877        "mul",
878        p,
879        p,
880        &ax2("mul", q.clone(), rs.clone()),
881        &ax2("mul", qr.clone(), s.clone()),
882        refl(p.clone()),
883        eq_sym(
884            ax2("mul", qr.clone(), s.clone()),
885            ax2("mul", q.clone(), rs.clone()),
886            ax3("mul_assoc", q.clone(), r.clone(), s.clone()),
887        ),
888    );
889    // w2 = w3 : under P·(_·S), mul_comm Q R
890    let p23 = cong2(
891        "mul",
892        p,
893        p,
894        &ax2("mul", qr.clone(), s.clone()),
895        &ax2("mul", rq.clone(), s.clone()),
896        refl(p.clone()),
897        cong2(
898            "mul",
899            &qr,
900            &rq,
901            s,
902            s,
903            ax2("mul_comm", q.clone(), r.clone()),
904            refl(s.clone()),
905        ),
906    );
907    // w3 = w4 : under P, mul_assoc R Q S
908    let p34 = cong2(
909        "mul",
910        p,
911        p,
912        &ax2("mul", rq.clone(), s.clone()),
913        &ax2("mul", r.clone(), qs.clone()),
914        refl(p.clone()),
915        ax3("mul_assoc", r.clone(), q.clone(), s.clone()),
916    );
917    // w4 = w5 : sym(mul_assoc P R (mul Q S))
918    let p45 = eq_sym(
919        w5.clone(),
920        w4.clone(),
921        ax3("mul_assoc", p.clone(), r.clone(), qs.clone()),
922    );
923    eq_trans(
924        w0,
925        w1.clone(),
926        w5.clone(),
927        p01,
928        eq_trans(
929            w1,
930            w2.clone(),
931            w5.clone(),
932            p12,
933            eq_trans(
934                w2,
935                w3.clone(),
936                w5.clone(),
937                p23,
938                eq_trans(w3, w4, w5, p34, p45),
939            ),
940        ),
941    )
942}
943
944/// Constructive coefficient-aware monomial product: `mul(ca,cb) = scaled_term(sort(atoms), c1·c2)`.
945/// Handles two signed monomials (`±·atoms`) — the case `merge_sorted` declines because of the literal
946/// coefficient. Hoists both coefficients out with one `swap_middle`, folds them by computation, sorts
947/// the atom parts with the (fast, any-degree) `merge_sorted`, and drops a `·1` coefficient. Returns
948/// `None` unless BOTH factors carry an atom product (the pure-literal / already-sorted cases the caller
949/// discharges by `refl`). No search: the proof is built directly, so it is fast at any degree.
950fn merge_scaled(polys: &Polynomials, ca: &Term, cb: &Term) -> Option<(Term, Term)> {
951    let (c1, oa) = split_coeff(ca);
952    let (c2, ob) = split_coeff(cb);
953    let a = oa?;
954    let b = ob?;
955    let coeff = c1.mul(&c2);
956    let (merged, p_atoms) = merge_sorted(polys, &a, &b)?; // mul(a,b) = merged   (pure atoms, fast)
957    let (lc1, lc2, lcoeff) = (
958        coefficient_term(&c1),
959        coefficient_term(&c2),
960        coefficient_term(&coeff),
961    );
962    let ca_u = ax2("mul", lc1.clone(), a.clone());
963    let cb_u = ax2("mul", lc2.clone(), b.clone());
964    let cvt_a = if c1.to_i64() == Some(1) {
965        as_scaled_mul(&c1, &a)
966    } else {
967        refl(ca_u.clone())
968    };
969    let cvt_b = if c2.to_i64() == Some(1) {
970        as_scaled_mul(&c2, &b)
971    } else {
972        refl(cb_u.clone())
973    };
974    let step_cvt = cong2("mul", ca, &ca_u, cb, &cb_u, cvt_a, cvt_b); // mul(ca,cb) = mul(ca_u,cb_u)
975    let step_swap = swap_middle(&lc1, &a, &lc2, &b); // = mul(mul(lc1,lc2), mul(a,b))
976    let ab = ax2("mul", a.clone(), b.clone());
977    let coeff_redex = ax2("mul", lc1.clone(), lc2.clone());
978    // fold coefficient (mul(lc1,lc2) = lcoeff by computation) and atoms (p_atoms) together
979    let step_fold = cong2(
980        "mul",
981        &coeff_redex,
982        &lcoeff,
983        &ab,
984        &merged,
985        refl(lcoeff.clone()),
986        p_atoms,
987    ); // mul(mul(lc1,lc2), mul(a,b)) = mul(lcoeff, merged)
988    let prod = ax2("mul", ca.clone(), cb.clone());
989    let mid1 = ax2("mul", ca_u, cb_u);
990    let mid2 = ax2("mul", coeff_redex, ab);
991    let scaled_lit = ax2("mul", lcoeff, merged.clone());
992    let up_to_lit = eq_trans(
993        prod.clone(),
994        mid1.clone(),
995        scaled_lit.clone(),
996        step_cvt,
997        eq_trans(mid1, mid2, scaled_lit.clone(), step_swap, step_fold),
998    ); // mul(ca,cb) = mul(lcoeff, merged)
999    if coeff.to_i64() == Some(1) {
1000        // canonical form of a coeff-1 monomial is the bare product: strip the `·1`.
1001        let elim = eq_sym(
1002            merged.clone(),
1003            scaled_lit.clone(),
1004            as_scaled_mul(&coeff, &merged),
1005        );
1006        Some((
1007            merged.clone(),
1008            eq_trans(prod, scaled_lit, merged, up_to_lit, elim),
1009        ))
1010    } else {
1011        Some((scaled_lit, up_to_lit))
1012    }
1013}
1014
1015/// Is `t` the literal integer `v`?
1016fn is_lit(t: &Term, v: i64) -> bool {
1017    matches!(t, Term::Lit(logicaffeine_kernel::Literal::Int(n)) if *n == v)
1018}
1019
1020/// Distribute `mul ca cb` (canonical terms), returning
1021/// `(product_poly, proof : mul ca cb = reify(product))`.
1022fn dist_mul(ctx: &Context, polys: &mut Polynomials, ca: &Term, cb: &Term) -> Option<(Poly, Term)> {
1023    // Literal annihilator / identity factors (e.g. an identity matrix's 0/1 entries in `det·I`):
1024    // collapse them directly. Distributing a literal 0 or 1 across a sum instead would strand a
1025    // `mul(0, monomial)` / `mul(1, monomial)` that the bounded search can't close (`mul_zero`/`mul_one`
1026    // are right-sided, so the left forms need a `mul_comm` flip the search doesn't chain to).
1027    if is_lit(cb, 0) {
1028        return Some((vec![], ax1("mul_zero", ca.clone()))); // mul(ca, 0) = 0
1029    }
1030    if is_lit(ca, 0) {
1031        let prod = ax2("mul", ca.clone(), cb.clone());
1032        let flip = ax2("mul_comm", ca.clone(), cb.clone()); // mul(0, cb) = mul(cb, 0)
1033        let zero = ax1("mul_zero", cb.clone()); //             mul(cb, 0) = 0
1034        return Some((
1035            vec![],
1036            eq_trans(
1037                prod,
1038                ax2("mul", cb.clone(), ca.clone()),
1039                lit_t(0),
1040                flip,
1041                zero,
1042            ),
1043        ));
1044    }
1045    if is_lit(cb, 1) {
1046        let pca = to_poly(polys, ctx, ca); // ca is canonical, so reify(pca) == ca
1047        return Some((pca, ax1("mul_one", ca.clone()))); // mul(ca, 1) = ca
1048    }
1049    if is_lit(ca, 1) {
1050        let pcb = to_poly(polys, ctx, cb);
1051        let prod = ax2("mul", ca.clone(), cb.clone());
1052        let flip = ax2("mul_comm", ca.clone(), cb.clone()); // mul(1, cb) = mul(cb, 1)
1053        let one = ax1("mul_one", cb.clone()); //               mul(cb, 1) = cb
1054        return Some((
1055            pcb,
1056            eq_trans(
1057                prod,
1058                ax2("mul", cb.clone(), ca.clone()),
1059                cb.clone(),
1060                flip,
1061                one,
1062            ),
1063        ));
1064    }
1065    if let Some((cb1, cb2)) = match_bin(cb, "add") {
1066        // mul ca (add cb1 cb2) = add (mul ca cb1)(mul ca cb2)
1067        let distrib = ax3("mul_distrib_add", ca.clone(), cb1.clone(), cb2.clone());
1068        let (pp1, d1) = dist_mul(ctx, polys, ca, &cb1)?;
1069        let (pp2, d2) = dist_mul(ctx, polys, ca, &cb2)?;
1070        let rp1 = reify(&pp1, &polys.atoms);
1071        let rp2 = reify(&pp2, &polys.atoms);
1072        let cong = cong2(
1073            "add",
1074            &ax2("mul", ca.clone(), cb1.clone()),
1075            &rp1,
1076            &ax2("mul", ca.clone(), cb2.clone()),
1077            &rp2,
1078            d1,
1079            d2,
1080        );
1081        let (pm, mproof) = merge_canonical(&polys.atoms, &pp1, &pp2)?;
1082        let rpm = reify(&pm, &polys.atoms);
1083        let proof = eq_trans(
1084            ax2("mul", ca.clone(), cb.clone()),
1085            ax2(
1086                "add",
1087                ax2("mul", ca.clone(), cb1.clone()),
1088                ax2("mul", ca.clone(), cb2.clone()),
1089            ),
1090            rpm,
1091            distrib,
1092            eq_trans(
1093                ax2(
1094                    "add",
1095                    ax2("mul", ca.clone(), cb1),
1096                    ax2("mul", ca.clone(), cb2),
1097                ),
1098                ax2("add", rp1, rp2),
1099                reify(&pm, &polys.atoms),
1100                cong,
1101                mproof,
1102            ),
1103        );
1104        return Some((pm, proof));
1105    }
1106    if let Some((_ca1, _ca2)) = match_bin(ca, "add") {
1107        // mul (sum) cb = mul cb (sum) then distribute
1108        let comm = ax2("mul_comm", ca.clone(), cb.clone());
1109        let (pm, inner) = dist_mul(ctx, polys, cb, ca)?; // mul cb ca = reify(pm)
1110        let rpm = reify(&pm, &polys.atoms);
1111        return Some((
1112            pm,
1113            eq_trans(
1114                ax2("mul", ca.clone(), cb.clone()),
1115                ax2("mul", cb.clone(), ca.clone()),
1116                rpm,
1117                comm,
1118                inner,
1119            ),
1120        ));
1121    }
1122    // both monomials: canonicalize the product. The constructive merge sorts the atom factors by
1123    // comm/assoc swaps for ANY degree (no bounded search), so degree-4+ monomial reorderings like
1124    // (df·dg)·(f·g) = (df·f)·(dg·g) go through; it falls back to the bounded search when a factor is
1125    // not an interned atom (e.g. a literal coefficient).
1126    let prod = ax2("mul", ca.clone(), cb.clone());
1127    let pp = to_poly(polys, ctx, &prod);
1128    let c = reify(&pp, &polys.atoms);
1129    // Two constructive sorts build the proof directly (no search, fast at any degree): `merge_sorted`
1130    // for pure atom-products, and `merge_scaled` for signed/coefficient-carrying monomials (a factor
1131    // like `mul(-1, …)` from a subtraction — the det case). The bounded search is only a last-resort
1132    // net for whatever neither constructs (already-sorted / pure-literal cases, which it closes by refl).
1133    let proof = merge_sorted(polys, ca, cb)
1134        .filter(|(result, _)| *result == c)
1135        .or_else(|| merge_scaled(polys, ca, cb).filter(|(result, _)| *result == c))
1136        .map(|(_, pf)| pf)
1137        .or_else(|| prove_eq(ctx, &prod, &c, MONO_FALLBACK_DEPTH))?;
1138    Some((pp, proof))
1139}
1140
1141/// `norm(t)` → `(canonical_term, proof : Eq Int t canonical_term)`, or `None`.
1142fn norm(ctx: &Context, polys: &mut Polynomials, t: &Term) -> Option<(Term, Term)> {
1143    if let Some((a, b)) = match_bin(t, "add") {
1144        let (ca, pa) = norm(ctx, polys, &a)?;
1145        let (cb, pb) = norm(ctx, polys, &b)?;
1146        let pa_poly = to_poly(polys, ctx, &a);
1147        let pb_poly = to_poly(polys, ctx, &b);
1148        let cong = cong2("add", &a, &ca, &b, &cb, pa, pb); // add a b = add ca cb
1149        let (merged, merge) = merge_canonical(&polys.atoms, &pa_poly, &pb_poly)?;
1150        let c = reify(&merged, &polys.atoms);
1151        return Some((
1152            c.clone(),
1153            eq_trans(t.clone(), ax2("add", ca, cb), c, cong, merge),
1154        ));
1155    }
1156    if let Some((a, b)) = match_bin(t, "mul") {
1157        let (ca, pa) = norm(ctx, polys, &a)?;
1158        let (cb, pb) = norm(ctx, polys, &b)?;
1159        let cong = cong2("mul", &a, &ca, &b, &cb, pa, pb); // mul a b = mul ca cb
1160        let (pm, dproof) = dist_mul(ctx, polys, &ca, &cb)?;
1161        let c = reify(&pm, &polys.atoms);
1162        return Some((
1163            c.clone(),
1164            eq_trans(t.clone(), ax2("mul", ca, cb), c, cong, dproof),
1165        ));
1166    }
1167    if let Some((a, b)) = match_bin(t, "sub") {
1168        // sub a b = add a (mul (-1) b)  [sub_elim], then normalize the add/mul form. Without this the
1169        // proof path leaves a symbolic `sub` stuck (only `to_poly` decides it), so a `sub` identity
1170        // would be decided-true yet unprovable.
1171        let elimmed = ax2("add", a.clone(), ax2("mul", lit_t(-1), b.clone()));
1172        let elim = ax2("sub_elim", a, b);
1173        let (c, p) = norm(ctx, polys, &elimmed)?;
1174        return Some((c.clone(), eq_trans(t.clone(), elimmed, c, elim, p)));
1175    }
1176    // atoms, literals: canonical form via the bounded search (handles nothing
1177    // for a bare atom — refl — and is here for robustness).
1178    let c = reify(&to_poly(polys, ctx, t), &polys.atoms);
1179    let proof = prove_eq(ctx, t, &c, MAX_REWRITE_DEPTH)?;
1180    Some((c, proof))
1181}
1182
1183/// Prove `Eq Int lhs rhs` by normalizing both sides to the shared canonical form.
1184fn prove_by_normalization(ctx: &Context, lhs: &Term, rhs: &Term) -> Option<Term> {
1185    let mut polys = Polynomials { atoms: Vec::new() };
1186    let (cl, pl) = norm(ctx, &mut polys, lhs)?; // lhs = cl
1187    let (cr, pr) = norm(ctx, &mut polys, rhs)?; // rhs = cr
1188                                                // The guard guarantees the polynomials match; their canonical terms are equal.
1189    if cl != cr {
1190        return None;
1191    }
1192    // lhs = cl = cr = rhs  ⇒  lhs = rhs
1193    Some(eq_trans(
1194        lhs.clone(),
1195        cl,
1196        rhs.clone(),
1197        pl,
1198        eq_sym(rhs.clone(), cr, pr),
1199    ))
1200}
1201
1202/// Bound on the multi-step (Eq_trans) rewrite search. Congruence does not consume
1203/// it (it recurses on strictly-smaller subterms), so this only limits same-size
1204/// axiom-chaining — enough for the ring identities that arise, and total.
1205const MAX_REWRITE_DEPTH: u32 = 6;
1206
1207/// Last-resort bound for the monomial-product fallback. Both the pure-atom (`merge_sorted`) and the
1208/// coefficient-aware (`merge_scaled`) sorts build their proofs constructively, so this search is only
1209/// a net for the residual already-sorted / pure-literal cases it closes by `refl` — a shallow bound
1210/// suffices, and nothing high-degree reaches it (that was the source of the exponential blow-up).
1211const MONO_FALLBACK_DEPTH: u32 = 6;
1212
1213fn prove_eq(ctx: &Context, lhs: &Term, rhs: &Term, depth: u32) -> Option<Term> {
1214    // 1. Computation: if both sides reduce to the same term, `refl` closes it.
1215    //    Covers all closed/literal arithmetic — zero axioms.
1216    let nlhs = normalize(ctx, lhs);
1217    let nrhs = normalize(ctx, rhs);
1218    if nlhs == nrhs {
1219        return Some(refl(nlhs));
1220    }
1221
1222    // 2. A single oriented ring-axiom step (try both orientations).
1223    if let Some(p) = match_axiom(ctx, lhs, rhs) {
1224        return Some(p);
1225    }
1226    if let Some(p) = match_axiom(ctx, rhs, lhs) {
1227        // proof : Eq Int rhs lhs  ⇒  Eq_sym … : Eq Int lhs rhs
1228        return Some(eq_sym(rhs.clone(), lhs.clone(), p));
1229    }
1230
1231    // 3. Congruence: `op a b = op a' b'` when `a=a'` and `b=b'` are each provable.
1232    //    Recurses on strictly-smaller subterms, so it terminates.
1233    for op in ["add", "mul", "sub"] {
1234        if let (Some((la, lb)), Some((ra, rb))) = (match_bin(lhs, op), match_bin(rhs, op)) {
1235            if let (Some(pa), Some(pb)) = (
1236                prove_eq(ctx, &la, &ra, depth),
1237                prove_eq(ctx, &lb, &rb, depth),
1238            ) {
1239                return Some(cong2(op, &la, &ra, &lb, &rb, pa, pb));
1240            }
1241        }
1242    }
1243
1244    // 4. Multi-step: rewrite lhs → mid by one forward axiom, prove `mid = rhs`,
1245    //    and compose with `Eq_trans`. Handles identities needing a rewrite plus a
1246    //    congruence (e.g. (x+y)+z = z+(y+x)). Depth-bounded ⇒ total.
1247    if depth > 0 {
1248        for (mid, p_lhs_mid) in forward_rewrites(lhs) {
1249            if let Some(p_mid_rhs) = prove_eq(ctx, &mid, rhs, depth - 1) {
1250                return Some(eq_trans(
1251                    lhs.clone(),
1252                    mid,
1253                    rhs.clone(),
1254                    p_lhs_mid,
1255                    p_mid_rhs,
1256                ));
1257            }
1258        }
1259    }
1260
1261    None
1262}
1263
1264/// `Eq_trans Int x y z p1 p2` : from `p1 : x=y` and `p2 : y=z`, prove `x=z`.
1265fn eq_trans(x: Term, y: Term, z: Term, p1: Term, p2: Term) -> Term {
1266    app(
1267        app(app(app(app(app(global("Eq_trans"), int()), x), y), z), p1),
1268        p2,
1269    )
1270}
1271
1272/// Single-step forward ring rewrites of `l`: each `(l', proof : Eq Int l l')`.
1273/// Only top-level rewrites; sub-term rewriting is covered by congruence.
1274fn forward_rewrites(l: &Term) -> Vec<(Term, Term)> {
1275    let g = global;
1276    let mut out = Vec::new();
1277    // add_comm : add a b → add b a
1278    if let Some((a, b)) = match_bin(l, "add") {
1279        out.push((
1280            app2(g("add"), b.clone(), a.clone()),
1281            app2(g("add_comm"), a.clone(), b.clone()),
1282        ));
1283        // add_assoc fwd : add (add a b) c → add a (add b c)
1284        if let Some((a2, b2)) = match_bin(&a, "add") {
1285            let c = b.clone();
1286            out.push((
1287                app2(g("add"), a2.clone(), app2(g("add"), b2.clone(), c.clone())),
1288                app3(g("add_assoc"), a2.clone(), b2.clone(), c.clone()),
1289            ));
1290        }
1291        // add_assoc rev : add a (add b c) → add (add a b) c
1292        if let Some((b2, c2)) = match_bin(&b, "add") {
1293            let lhs_a = app2(g("add"), app2(g("add"), a.clone(), b2.clone()), c2.clone());
1294            let rhs_a = app2(g("add"), a.clone(), app2(g("add"), b2.clone(), c2.clone()));
1295            out.push((
1296                lhs_a.clone(),
1297                eq_sym(
1298                    lhs_a,
1299                    rhs_a,
1300                    app3(g("add_assoc"), a.clone(), b2.clone(), c2.clone()),
1301                ),
1302            ));
1303        }
1304    }
1305    // mul_comm : mul a b → mul b a
1306    if let Some((a, b)) = match_bin(l, "mul") {
1307        out.push((
1308            app2(g("mul"), b.clone(), a.clone()),
1309            app2(g("mul_comm"), a.clone(), b.clone()),
1310        ));
1311        // mul_assoc fwd : mul (mul a b) c → mul a (mul b c)
1312        if let Some((a2, b2)) = match_bin(&a, "mul") {
1313            let c = b.clone();
1314            out.push((
1315                app2(g("mul"), a2.clone(), app2(g("mul"), b2.clone(), c.clone())),
1316                app3(g("mul_assoc"), a2.clone(), b2.clone(), c.clone()),
1317            ));
1318        }
1319        // mul_distrib_add fwd : mul a (add b c) → add (mul a b) (mul a c)
1320        if let Some((b2, c2)) = match_bin(&b, "add") {
1321            out.push((
1322                app2(
1323                    g("add"),
1324                    app2(g("mul"), a.clone(), b2.clone()),
1325                    app2(g("mul"), a.clone(), c2.clone()),
1326                ),
1327                app3(g("mul_distrib_add"), a.clone(), b2.clone(), c2.clone()),
1328            ));
1329        }
1330    }
1331    out
1332}
1333
1334/// `Eq Int l r` as a term.
1335fn eq_int_term(l: Term, r: Term) -> Term {
1336    app(app(app(global("Eq"), int()), l), r)
1337}
1338
1339/// `Eq_rec Int x P base y eqp` : rewrites `x` to `y` in `P` using `eqp : Eq Int x y`.
1340fn eq_rec(x: Term, motive: Term, base: Term, y: Term, eqp: Term) -> Term {
1341    app(
1342        app(
1343            app(app(app(app(global("Eq_rec"), int()), x), motive), base),
1344            y,
1345        ),
1346        eqp,
1347    )
1348}
1349
1350/// `λ(__w : Int). body`
1351fn lam_int(body: Term) -> Term {
1352    Term::Lambda {
1353        param: "__w".to_string(),
1354        param_type: Box::new(int()),
1355        body: Box::new(body),
1356    }
1357}
1358
1359/// Congruence for a binary op: from `pa : a = a'` and `pb : b = b'`, build a
1360/// proof of `Eq Int (op a b) (op a' b')` by two `Eq_rec` rewrites.
1361fn cong2(op: &str, a: &Term, a2: &Term, b: &Term, b2: &Term, pa: Term, pb: Term) -> Term {
1362    let opab = app2(global(op), a.clone(), b.clone());
1363    let w = Term::Var("__w".to_string());
1364
1365    // step1 : Eq Int (op a b) (op a' b)   — rewrite a → a'
1366    //   motive P1 = λw. Eq Int (op a b) (op w b)
1367    let p1 = lam_int(eq_int_term(
1368        opab.clone(),
1369        app2(global(op), w.clone(), b.clone()),
1370    ));
1371    let step1 = eq_rec(a.clone(), p1, refl(opab.clone()), a2.clone(), pa);
1372
1373    // step2 : Eq Int (op a b) (op a' b')  — rewrite b → b'
1374    //   motive P2 = λw. Eq Int (op a b) (op a' w)
1375    let p2 = lam_int(eq_int_term(opab.clone(), app2(global(op), a2.clone(), w)));
1376    eq_rec(b.clone(), p2, step1, b2.clone(), pb)
1377}
1378
1379/// One oriented ring-axiom application proving `Eq Int l r`, if `(l, r)` matches.
1380fn match_axiom(ctx: &Context, l: &Term, r: &Term) -> Option<Term> {
1381    // add_comm : l = add a b,  r = add b a
1382    if let (Some((la, lb)), Some((ra, rb))) = (match_bin(l, "add"), match_bin(r, "add")) {
1383        if conv(ctx, &la, &rb) && conv(ctx, &lb, &ra) {
1384            return Some(app2(global("add_comm"), la, lb));
1385        }
1386    }
1387    // mul_comm : l = mul a b,  r = mul b a
1388    if let (Some((la, lb)), Some((ra, rb))) = (match_bin(l, "mul"), match_bin(r, "mul")) {
1389        if conv(ctx, &la, &rb) && conv(ctx, &lb, &ra) {
1390            return Some(app2(global("mul_comm"), la, lb));
1391        }
1392    }
1393    // add_assoc : l = add (add a b) c,  r = add a (add b c)
1394    if let Some((lab, lc)) = match_bin(l, "add") {
1395        if let Some((la, lb)) = match_bin(&lab, "add") {
1396            if let Some((ra, rbc)) = match_bin(r, "add") {
1397                if let Some((rb, rc)) = match_bin(&rbc, "add") {
1398                    if conv(ctx, &la, &ra) && conv(ctx, &lb, &rb) && conv(ctx, &lc, &rc) {
1399                        return Some(app3(global("add_assoc"), la, lb, lc));
1400                    }
1401                }
1402            }
1403        }
1404    }
1405    // mul_assoc : l = mul (mul a b) c,  r = mul a (mul b c)
1406    if let Some((lab, lc)) = match_bin(l, "mul") {
1407        if let Some((la, lb)) = match_bin(&lab, "mul") {
1408            if let Some((ra, rbc)) = match_bin(r, "mul") {
1409                if let Some((rb, rc)) = match_bin(&rbc, "mul") {
1410                    if conv(ctx, &la, &ra) && conv(ctx, &lb, &rb) && conv(ctx, &lc, &rc) {
1411                        return Some(app3(global("mul_assoc"), la, lb, lc));
1412                    }
1413                }
1414            }
1415        }
1416    }
1417    // add_zero : l = add a 0,  r = a
1418    if let Some((la, lb)) = match_bin(l, "add") {
1419        if conv(ctx, &lb, &Term::Lit(logicaffeine_kernel::Literal::Int(0))) && conv(ctx, &la, r) {
1420            return Some(app(global("add_zero"), la));
1421        }
1422    }
1423    // mul_one : l = mul a 1,  r = a
1424    if let Some((la, lb)) = match_bin(l, "mul") {
1425        if conv(ctx, &lb, &Term::Lit(logicaffeine_kernel::Literal::Int(1))) && conv(ctx, &la, r) {
1426            return Some(app(global("mul_one"), la));
1427        }
1428    }
1429    // mul_distrib_add : l = mul a (add b c),  r = add (mul a b) (mul a c)
1430    if let Some((a, bc)) = match_bin(l, "mul") {
1431        if let Some((b, c)) = match_bin(&bc, "add") {
1432            if let Some((rab, rac)) = match_bin(r, "add") {
1433                if let (Some((ra1, rb1)), Some((ra2, rc1))) =
1434                    (match_bin(&rab, "mul"), match_bin(&rac, "mul"))
1435                {
1436                    if conv(ctx, &a, &ra1)
1437                        && conv(ctx, &a, &ra2)
1438                        && conv(ctx, &b, &rb1)
1439                        && conv(ctx, &c, &rc1)
1440                    {
1441                        return Some(app3(global("mul_distrib_add"), a, b, c));
1442                    }
1443                }
1444            }
1445        }
1446    }
1447    None
1448}
1449
1450#[cfg(test)]
1451#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/arith/tests.rs"]
1452mod tests;