AFTD Auto-Formalizing Theoretical Domains

mondrian_ordered_shape_half

theoremverified

Twice the number of available unordered dimension pairs is at most one plus the number of ordered dimension pairs fitting in the square.

Statement

theorem mondrian_ordered_shape_half (n A : ℕ) :
    2 * (mondrian_factor_shapes n A).card ≤
      (A.divisorsAntidiagonal.filter (fun d => d.1 ≤ n ∧ d.2 ≤ n)).card + 1
Source
Helper for OP-280 and mondrian_perfect_partition_large_prime_iff. Related work: arXiv:2610.19193, Section 1 (perfect partitions and scaling); arXiv:2007.09639, Theorem 4.1 (available shapes and prime-power exclusions).
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • mondrian_factor_shapesThe available unordered integer dimension pairs of positive area A that fit in an n-square, encoded in increasing order.
  • mondrian_mem_factor_shapesA dimension pair belongs to the available shape set exactly when its product is the nonzero area A, its first dimension is at most its…
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
Used by 1
  • mondrian_prime_shape_boundIf k times A is the area of a c times p to the e square and p exceeds c, at most c * (v_p(k) + 1) unordered shapes of area A fit in the…

The proof, explained

The inequality is proved by a double-counting argument using the principle of inclusion-exclusion. Let S be the set of ordered dimension pairs (a, b) with a ≤ b ≤ n and area A, let T be the set of swapped pairs (b, a), and let U be the set of all ordered pairs with both dimensions at most n. The union S ∪ T equals U because every valid pair satisfies either a ≤ b or b ≤ a, and the intersection S ∩ T has at most one element because any pair in both must be a square (a = b = √A). By inclusion-exclusion, 2 * |S| = |S| + |T| = |S ∪ T| + |S ∩ T| = |U| + |S ∩ T| ≤ |U| + 1.

  1. Let S be the set of ordered factor shapes, T the set of swapped shapes, and U the set of all factor pairs bounded by n.

    We introduce three finite sets: S = mondrian_factor_shapes n A contains pairs (d₁, d₂) of divisors of A such that d₁ ≤ d₂ ≤ n; T is the image of S obtained by swapping dimensions, representing pairs with d₂ ≤ d₁ ≤ n; and U is the set of all divisor pairs of A with both dimensions bounded by n.

    lines 4–6

      let S := mondrian_factor_shapes n A
      let T := S.map (Equiv.prodComm ℕ ℕ).toEmbedding
      let U := A.divisorsAntidiagonal.filter (fun d => d.1 ≤ n ∧ d.2 ≤ n)
  2. The union S ∪ T equals U.

    By set extensionality, an element d belongs to S ∪ T if and only if d ∈ U. In the forward direction, if d ∈ S, then d₁ ≤ d₂ ≤ n, so both dimensions are bounded by n and d ∈ U; if d ∈ T, it is the swap of some s ∈ S with s₁ ≤ s₂ ≤ n, so d₁ = s₂ ≤ n and d₂ = s₁ ≤ s₂ ≤ n, again placing d in U. In the reverse direction, given d ∈ U, both d₁ ≤ n and d₂ ≤ n. We case split on whether d₁ ≤ d₂: if so, d ∈ S; if d₁ > d₂, then d₂ ≤ d₁ ≤ n, so the swapped pair d.swap belongs to S, which means d belongs to T.

    lines 7–21

    uses Finset.mem_union, Finset.mem_map, Equiv.prodComm_apply, Equiv.toEmbedding_apply, mondrian_mem_factor_shapes, Finset.mem_filter, Nat.mem_divisorsAntidiagonal, Nat.mul_comm, Or.inl, Or.inr, Prod.swap_swap

      have hunion : S ∪ T = U := by
        ext d
        simp only [S, T, U, Finset.mem_union, Finset.mem_map,
          Equiv.prodComm_apply, Equiv.toEmbedding_apply,
          mondrian_mem_factor_shapes, Finset.mem_filter, Nat.mem_divisorsAntidiagonal]
        constructor
        · rintro (⟨hprod, hA, hord, hn⟩ | ⟨s, ⟨hprod, hA, hord, hn⟩, rfl⟩)
          · exact ⟨⟨hprod, hA⟩, hord.trans hn, hn⟩
          · exact ⟨⟨by simpa [Nat.mul_comm] using hprod, hA⟩, hn, hord.trans hn⟩
        · rintro ⟨⟨hprod, hA⟩, hx, hy⟩
          by_cases hxy : d.1 ≤ d.2
          · exact Or.inl ⟨hprod, hA, hxy, hy⟩
          · exact Or.inr ⟨d.swap, ⟨by simpa [Nat.mul_comm] using hprod, hA,
              by change d.2 ≤ d.1; omega, hx⟩,
              Prod.swap_swap d⟩
  3. The intersection S ∩ T contains at most one element.

    To prove |S ∩ T| ≤ 1, it suffices to show that any two elements x, y ∈ S ∩ T are equal. If x ∈ S ∩ T, then x ∈ S implies x₁ ≤ x₂, while x ∈ T implies that x is the swap of some s ∈ S (with s₁ ≤ s₂), giving x₁ = s₂ ≥ s₁ = x₂. Thus x₁ = x₂. The same reasoning shows y₁ = y₂. Since both pairs multiply to A, we have x₁² = x₁ x₂ = A = y₁ y₂ = y₁². Because x₁ and y₁ are non-negative integers with equal squares, non-linear arithmetic gives x₁ = y₁ and x₂ = y₂, so x = y.

    lines 22–43

    uses Finset.card_le_one.mpr, Finset.mem_inter.mp, mondrian_mem_factor_shapes, Finset.mem_map.mp, congrArg, Prod.fst, Prod.snd, Prod.ext

      have hint : (S ∩ T).card ≤ 1 := by
        apply Finset.card_le_one.mpr
        intro x hx y hy
        obtain ⟨hxS, hxT⟩ := Finset.mem_inter.mp hx
        obtain ⟨hyS, hyT⟩ := Finset.mem_inter.mp hy
        obtain ⟨hxp, _, hxord, _⟩ := (mondrian_mem_factor_shapes n A x).mp hxS
        obtain ⟨hyp, _, hyord, _⟩ := (mondrian_mem_factor_shapes n A y).mp hyS
        obtain ⟨s, hs, hxs⟩ := Finset.mem_map.mp hxT
        obtain ⟨t, ht, hyt⟩ := Finset.mem_map.mp hyT
        have hsord := ((mondrian_mem_factor_shapes n A s).mp hs).2.2.1
        have htord := ((mondrian_mem_factor_shapes n A t).mp ht).2.2.1
        have hxeq : x.1 = x.2 := by
          have h1 := congrArg Prod.fst hxs
          have h2 := congrArg Prod.snd hxs
          dsimp at h1 h2
          omega
        have hyeq : y.1 = y.2 := by
          have h1 := congrArg Prod.fst hyt
          have h2 := congrArg Prod.snd hyt
          dsimp at h1 h2
          omega
        apply Prod.ext <;> nlinarith
  4. The inequality 2 * |S| ≤ |U| + 1 follows by inclusion-exclusion.

    By the principle of inclusion-exclusion, |S ∪ T| + |S ∩ T| = |S| + |T|. Since T is the image of S under a bijection, |T| = |S|. Substituting S ∪ T = U yields |U| + |S ∩ T| = 2 * |S|. Since |S ∩ T| ≤ 1, linear arithmetic finishes the proof: 2 * |S| ≤ |U| + 1.

    lines 44–48

    uses Finset.card_union_add_card_inter

      have hc := Finset.card_union_add_card_inter S T
      have hT : T.card = S.card := by simp [T]
      rw [hunion, hT] at hc
      dsimp [S, U] at hc hint
      omega
Equiv.prodComm_apply
Applying the product commutation equivalence to an ordered pair swaps its two components.
Equiv.toEmbedding_apply
Applying an equivalence coerced to an embedding to an argument gives the same result as applying the equivalence directly.
Finset.card_le_one.mpr
A finite set has cardinality at most one if any two elements in it are equal.
Finset.card_union_add_card_inter
For any two finite sets s and t, the sum of the cardinalities of their union and intersection equals the sum of their individual cardinalities: |s ∪ t| + |s ∩ t| = |s| + |t|.
Finset.mem_filter
An element belongs to a filtered finite set if and only if it belongs to the base set and satisfies the filtering predicate.
Finset.mem_inter.mp
If an element belongs to the intersection of two finite sets, then it belongs to both sets.
Finset.mem_map
An element belongs to the image of a finite set under an embedding if and only if it is the image of some element in the domain set.
Finset.mem_map.mp
If an element belongs to the image of a finite set under a map, then there exists a pre-image in the domain set mapping to it.
Finset.mem_union
An element belongs to the union of two finite sets if and only if it belongs to either set.
Nat.mem_divisorsAntidiagonal
A pair of natural numbers belongs to A.divisorsAntidiagonal if and only if their product is A and A is non-zero.
Nat.mul_comm
Multiplication of natural numbers is commutative: n * m = m * n.
Or.inl
Concludes a disjunction a ∨ b from a proof of the left disjunct a.
Or.inr
Concludes a disjunction a ∨ b from a proof of the right disjunct b.
Prod.ext
Two ordered pairs are equal if their first components are equal and their second components are equal.
Prod.fst
The projection function returning the first component of an ordered pair.
Prod.snd
The projection function returning the second component of an ordered pair.
Prod.swap_swap
Swapping the components of an ordered pair twice yields the original pair.
congrArg
Applying a function to equal inputs yields equal outputs: if a₁ = a₂, then f(a₁) = f(a₂).
mondrian_mem_factor_shapes
A pair of integers d belongs to mondrian_factor_shapes n A if and only if d.1 * d.2 = A, A ≠ 0, d.1 ≤ d.2, and d.2 ≤ 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_ordered_shape_half (n A : ℕ) :    2 * (mondrian_factor_shapes n A).card ≤      (A.divisorsAntidiagonal.filter (fun d => d.1 ≤ n ∧ d.2 ≤ n)).card + 1 := by  let S := mondrian_factor_shapes n A  let T := S.map (Equiv.prodComm ℕ ℕ).toEmbedding  let U := A.divisorsAntidiagonal.filter (fun d => d.1 ≤ n ∧ d.2 ≤ n)  have hunion : S ∪ T = U := by    ext d    simp only [S, T, U, Finset.mem_union, Finset.mem_map,      Equiv.prodComm_apply, Equiv.toEmbedding_apply,      mondrian_mem_factor_shapes, Finset.mem_filter, Nat.mem_divisorsAntidiagonal]    constructor    · rintro (⟨hprod, hA, hord, hn⟩ | ⟨s, ⟨hprod, hA, hord, hn⟩, rfl⟩)      · exact ⟨⟨hprod, hA⟩, hord.trans hn, hn⟩      · exact ⟨⟨by simpa [Nat.mul_comm] using hprod, hA⟩, hn, hord.trans hn⟩    · rintro ⟨⟨hprod, hA⟩, hx, hy⟩      by_cases hxy : d.1 ≤ d.2      · exact Or.inl ⟨hprod, hA, hxy, hy⟩      · exact Or.inr ⟨d.swap, ⟨by simpa [Nat.mul_comm] using hprod, hA,          by change d.2 ≤ d.1; omega, hx⟩,          Prod.swap_swap d⟩  have hint : (S ∩ T).card ≤ 1 := by    apply Finset.card_le_one.mpr    intro x hx y hy    obtain ⟨hxS, hxT⟩ := Finset.mem_inter.mp hx    obtain ⟨hyS, hyT⟩ := Finset.mem_inter.mp hy    obtain ⟨hxp, _, hxord, _⟩ := (mondrian_mem_factor_shapes n A x).mp hxS    obtain ⟨hyp, _, hyord, _⟩ := (mondrian_mem_factor_shapes n A y).mp hyS    obtain ⟨s, hs, hxs⟩ := Finset.mem_map.mp hxT    obtain ⟨t, ht, hyt⟩ := Finset.mem_map.mp hyT    have hsord := ((mondrian_mem_factor_shapes n A s).mp hs).2.2.1    have htord := ((mondrian_mem_factor_shapes n A t).mp ht).2.2.1    have hxeq : x.1 = x.2 := by      have h1 := congrArg Prod.fst hxs      have h2 := congrArg Prod.snd hxs      dsimp at h1 h2      omega    have hyeq : y.1 = y.2 := by      have h1 := congrArg Prod.fst hyt      have h2 := congrArg Prod.snd hyt      dsimp at h1 h2      omega    apply Prod.ext <;> nlinarith  have hc := Finset.card_union_add_card_inter S T  have hT : T.card = S.card := by simp [T]  rw [hunion, hT] at hc  dsimp [S, U] at hc hint  omega
See it in the graphDiscuss this resultChallenge it