AFTD Auto-Formalizing Theoretical Domains

mondrian_mem_factor_shapes

theoremverified

A dimension pair belongs to the available shape set exactly when its product is the nonzero area A, its first dimension is at most its second, and its second is at most n.

Statement

theorem mondrian_mem_factor_shapes (n A : ℕ) (d : ℕ × ℕ) :
    d ∈ mondrian_factor_shapes n A ↔
      d.1 * d.2 = A ∧ A ≠ 0 ∧ d.1 ≤ d.2 ∧ d.2 ≤ n
Source
arXiv:2610.19193, Section 1, and arXiv:2311.02385, Section 3 (available integer dimension pairs); helper for OP-280 and mondrian_no_perfect_partition.
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • mondrian_factor_shapesThe available unordered integer dimension pairs of positive area A that fit in an n-square, encoded in increasing order.
Used by 10

The proof, explained

The equivalence follows directly by unfolding definitions and simplifying propositional logic. The set mondrian_factor_shapes n A is defined as the pairs in the divisors antidiagonal of A satisfying d.1 ≤ d.2 and d.2 ≤ n. Rewriting with the membership lemmas for filtered finsets and the divisors antidiagonal yields the four conjuncts, which are re-associated by propositional logic.

  1. d ∈ mondrian_factor_shapes n A is equivalent to (d.1 * d.2 = A ∧ A ≠ 0) ∧ d.1 ≤ d.2 ∧ d.2 ≤ n

    Unfold the definition of mondrian_factor_shapes, which filters the divisors antidiagonal of A by the condition d.1 ≤ d.2 ∧ d.2 ≤ n. Applying Finset.mem_filter turns membership in the filtered set into membership in the antidiagonal along with the filter condition. Then Nat.mem_divisorsAntidiagonal rewrites antidiagonal membership into d.1 * d.2 = A ∧ A ≠ 0.

    line 4

    uses mondrian_factor_shapes, Finset.mem_filter, Nat.mem_divisorsAntidiagonal

      simp only [mondrian_factor_shapes, Finset.mem_filter, Nat.mem_divisorsAntidiagonal]
  2. The equivalence d ∈ mondrian_factor_shapes n A ↔ d.1 * d.2 = A ∧ A ≠ 0 ∧ d.1 ≤ d.2 ∧ d.2 ≤ n holds

    The left-hand side and right-hand side are identical up to the associativity of conjunction, ((P ∧ Q) ∧ R ∧ S) ↔ (P ∧ Q ∧ R ∧ S), which is solved by propositional tautology reasoning (tauto).

    line 5

      tauto
Finset.mem_filter
an element a belongs to Finset.filter p s if and only if a ∈ s and p a holds
Nat.mem_divisorsAntidiagonal
a pair x of natural numbers belongs to n.divisorsAntidiagonal if and only if x.1 * x.2 = n and n ≠ 0
mondrian_factor_shapes
the finset of dimension pairs (d₁, d₂) for bounding box n and area A, defined by filtering A.divisorsAntidiagonal for pairs satisfying d₁ ≤ d₂ and d₂ ≤ 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

theorem mondrian_mem_factor_shapes (n A : ℕ) (d : ℕ × ℕ) :    d ∈ mondrian_factor_shapes n A ↔      d.1 * d.2 = A ∧ A ≠ 0 ∧ d.1 ≤ d.2 ∧ d.2 ≤ n := by  simp only [mondrian_factor_shapes, Finset.mem_filter, Nat.mem_divisorsAntidiagonal]  tauto
See it in the graphDiscuss this resultChallenge it