AFTD Auto-Formalizing Theoretical Domains

partition_lift_57_intersection_card

theoremverified

For t ≥ 1, the multiset intersection size of two lifted partitions exceeds the multiset intersection size of the original partitions of 57 by exactly t - 1.

Statement

theorem partition_lift_57_intersection_card (t : ℕ) (ht : 1 ≤ t)
    (p q : Nat.Partition 57) :
    ((partition_lift_57 t ht p).parts ∩ (partition_lift_57 t ht q).parts).card =
      (p.parts ∩ q.parts).card + (t - 1)
Source
arXiv:2610.01747, Eq. (25)
Verified
28 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • partition_lift_57For t ≥ 1, the lifting map sends a partition p of 57 to a partition of t + 56 by adding t - 1 ones to its multiset of parts.

Read back from the Lean

For every natural number $t$ satisfying $1 \le t$, and for all partitions $p$ and $q$ of the natural number 57, the cardinality (with multiplicity) of the multiset intersection of the parts of the lifted partition of $p$ (partition_lift_57 t ht p) and the parts of the lifted partition of $q$ (partition_lift_57 t ht q) is equal to the cardinality of the multiset intersection of the parts of $p$ and $q$ plus $t - 1$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The proof expands the definition of `partition_lift_57`, which adds t - 1 copies of 1 to the parts of a partition of 57. By the distributivity of multiset intersection over multiset addition, the intersection of the two lifted partitions factors into the intersection of the original parts plus the t - 1 shared copies of 1. Taking the multiset cardinality splits across this sum and immediately yields the original intersection cardinality plus t - 1.

  1. The parts of the lifted partitions are expanded as the original parts plus t - 1 copies of 1.

    Unfolding the definition of `partition_lift_57` replaces the parts of each lifted partition with `p.parts + Multiset.replicate (t - 1) 1` and `q.parts + Multiset.replicate (t - 1) 1`.

    line 6

    uses partition_lift_57

      simp only [partition_lift_57]
  2. The multiset cardinality of the intersection of the lifted partitions equals the cardinality of the original intersection plus t - 1.

    Applying the distributivity of multiset intersection over multiset addition (`Multiset.inter_add_distrib`) in reverse factors out the common summand `Multiset.replicate (t - 1) 1`, transforming (p.parts + u) ∩ (q.parts + u) into (p.parts ∩ q.parts) + u. Then, multiset cardinality distributes over addition (`Multiset.card_add`), and the cardinality of the replicated ones evaluates to t - 1 (`Multiset.card_replicate`), completing the proof.

    line 7

    uses Multiset.inter_add_distrib, Multiset.card_add, Multiset.card_replicate

      rw [← Multiset.inter_add_distrib, Multiset.card_add, Multiset.card_replicate]
partition_lift_57
Constructs a partition of t + 56 from a partition of 57 by appending t - 1 copies of 1 to its parts.
Multiset.inter_add_distrib
Multiset intersection distributes over multiset addition: (s ∩ t) + u = (s + u) ∩ (t + u).
Multiset.card_add
The cardinality of the sum of two multisets is the sum of their cardinalities: |s + t| = |s| + |t|.
Multiset.card_replicate
The cardinality of a multiset consisting of n copies of an element is n.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- Common parts count of two lifted partitions increases by exactly t - 1. -/theorem partition_lift_57_intersection_card (t : ℕ) (ht : 1 ≤ t)    (p q : Nat.Partition 57) :    ((partition_lift_57 t ht p).parts ∩ (partition_lift_57 t ht q).parts).card =      (p.parts ∩ q.parts).card + (t - 1) := by  simp only [partition_lift_57]  rw [← Multiset.inter_add_distrib, Multiset.card_add, Multiset.card_replicate]
See it in the graphDiscuss this resultChallenge it