AFTD Auto-Formalizing Theoretical Domains

mondrian_partition_width_dvd_of_height_two_chains

theoremverified

If d divides the square side and all width-indivisible tiles have heights in two superincreasing chains C*p^a and C*r*p^a, with p>r+1 and r≥2, then every tile width is divisible by d.

Statement

theorem mondrian_partition_width_dvd_of_height_two_chains (n d p r C : ℕ)
    (P : List (ℕ × ℕ × ℕ × ℕ)) (hP : mondrian_is_partition n P)
    (hz : mondrian_defect P = 0) (hdn : d ∣ n) (hC : 0 < C)
    (hr : 2 ≤ r) (hpr : r + 1 < p)
    (hheight : ∀ u ∈ P, ¬ d ∣ mondrian_rect_width u → ∃ a : ℕ,
      mondrian_rect_height u = C * p ^ a ∨ mondrian_rect_height u = C * r * p ^ a) :
    ∀ u ∈ P, d ∣ mondrian_rect_width u
Source
For the three-prime extension of OP-280, arXiv:2610.19193, Section 1. This develops the proved mondrian_no_perfect_two_prime_area and the width-free signed-height relation from this session.
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7
Used by 2

The proof, explained

The theorem is proved by contradiction: assume some rectangle u in the partition has width not divisible by d. A general relation for Mondrian partitions yields a signed sum of heights of other width-indivisible rectangles that equals the height of u. Prepending the height of u with a negative sign produces a list H of signed heights summing to 0. Since defect is 0, rectangle heights are unique, making all heights in H distinct; and because all width-indivisible rectangles have heights in two superincreasing chains, an arithmetic theorem shows no such non-trivial signed sum can vanish, yielding a contradiction.

  1. Assume for contradiction that some tile in P has width not divisible by d.

    We work classically and introduce an arbitrary tile u ∈ P. We assume for contradiction that d does not divide the width of u.

    lines 8–10

      classical
      intro u hu
      by_contra hfree
  2. There is a duplicate-free list L of signed tiles in P \ {u} with widths not divisible by d whose signed height sum equals the height of u.

    Applying mondrian_partition_width_free_height_signed_relation with d ∣ n and the tile u ∈ P (whose width is not divisible by d) produces a list L of pairs of tiles and boolean signs. The tiles in L are distinct, all belong to P, are distinct from u, have widths not divisible by d, and their signed height sum equals the height of u.

    lines 11–12

    uses mondrian_partition_width_free_height_signed_relation

      obtain ⟨L, hLnd, hLmem, hLsum⟩ :=
        mondrian_partition_width_free_height_signed_relation n d P hP hdn u hu hfree
  3. Define H as the list of signed heights consisting of (height(u), false) followed by the signed heights of L.

    We package the heights into a single list H of pairs of heights and signs by prepending height(u) with sign false (representing a negative sign) to the signed heights from L.

    lines 13–14

      let H := (mondrian_rect_height u, false) ::
        L.map (fun t => (mondrian_rect_height t.1, t.2))
  4. The list of heights of tiles in L contains no duplicates.

    Because the partition has defect 0, height is injective on P by mondrian_perfect_height_injective. Since the tiles in L are distinct and all belong to P, mapping the height function preserves duplicate-freeness via List.Nodup.map_on.

    lines 15–23

    uses List.Nodup.map_on, List.mem_map.mp, mondrian_perfect_height_injective, List.map_map, Function.comp_def

      have hhnd : (L.map (fun t => mondrian_rect_height t.1)).Nodup := by
        have hh : ((L.map Prod.fst).map mondrian_rect_height).Nodup := by
          apply List.Nodup.map_on _ hLnd
          intro v hv w hw he
          obtain ⟨v', hv', rfl⟩ := List.mem_map.mp hv
          obtain ⟨w', hw', rfl⟩ := List.mem_map.mp hw
          exact mondrian_perfect_height_injective n P hP hz v'.1 (hLmem v' hv').1
            w'.1 (hLmem w' hw').1 he
        simpa only [List.map_map, Function.comp_def] using hh
  5. The height of u does not appear among the heights of the tiles in L.

    If height(u) were the height of some tile t in L, then by injectivity of heights (mondrian_perfect_height_injective), t would equal u. However, every tile in L is known to be distinct from u, a contradiction.

    lines 24–28

    uses List.mem_map.mp, mondrian_perfect_height_injective

      have hhead : mondrian_rect_height u ∉ L.map (fun t => mondrian_rect_height t.1) := by
        intro hm
        obtain ⟨t, ht, he⟩ := List.mem_map.mp hm
        exact (hLmem t ht).2.1 (mondrian_perfect_height_injective n P hP hz
          t.1 (hLmem t ht).1 u hu he)
  6. The list of heights in H has no duplicates.

    Since height(u) is not among the heights of L and the heights in L are duplicate-free, prepending height(u) produces a duplicate-free list of heights by List.nodup_cons.mpr.

    lines 29–31

    uses List.map_cons, List.map_map, Function.comp_def, List.nodup_cons.mpr

      have hnd : (H.map Prod.fst).Nodup := by
        simpa only [H, List.map_cons, List.map_map, Function.comp_def] using
          (List.nodup_cons.mpr ⟨hhead, hhnd⟩)
  7. Every height in H has the form C * p^a or C * r * p^a for some natural number a.

    Every element of H is either the head (height(u), false) or comes from L. In both cases, the tile belongs to P and its width is not divisible by d (by the contradiction assumption for u, and by construction for L). Thus the hypothesis hheight applies to every element of H.

    lines 32–38

    uses List.mem_cons.mp, List.mem_map.mp

      have hrep : ∀ t ∈ H, ∃ a : ℕ, t.1 = C * p ^ a ∨ t.1 = C * r * p ^ a := by
        intro t ht
        rcases List.mem_cons.mp ht with he | ht
        · subst t
          exact hheight u hu hfree
        · obtain ⟨v, hv, rfl⟩ := List.mem_map.mp ht
          exact hheight v.1 (hLmem v hv).1 (hLmem v hv).2.2
  8. The signed sum of the heights in H equals zero.

    Expanding the definition of H, the head contributes -height(u) because its sign is false, while the tail contributes the signed sum of heights from L, which equals height(u). The sum evaluates to -height(u) + height(u) = 0.

    lines 39–43

    uses List.map_cons, List.sum_cons, List.map_map, Function.comp_def, Bool.false_eq_true, if_false

      have hzero : (H.map (fun t => if t.2 then (t.1 : ℤ) else -(t.1 : ℤ))).sum = 0 := by
        simp only [H, List.map_cons, List.sum_cons, List.map_map, Function.comp_def,
          Bool.false_eq_true, if_false]
        rw [hLsum]
        ring
  9. A contradiction is reached, proving that d divides the width of every tile in P.

    By mondrian_two_chain_signed_sum_ne_zero, no non-empty list of distinct heights chosen from the two chains C * p^a and C * r * p^a can have a vanishing signed sum when C > 0, r ≥ 2, and p > r + 1. Since H is non-empty, has distinct heights, consists of chain elements, and sums to zero, this produces a contradiction.

    line 44

    uses mondrian_two_chain_signed_sum_ne_zero

      exact mondrian_two_chain_signed_sum_ne_zero p r C hC hr hpr H (by simp [H]) hnd hrep hzero
Bool.false_eq_true
The boolean false is not equal to true.
Function.comp_def
Definition of function composition: (f ∘ g)(x) = f(g(x)).
List.map_cons
Mapping a function over a non-empty list applies the function to the head and maps over the tail.
List.map_map
Mapping g over map f l equals mapping the composite g ∘ f over l.
List.mem_cons.mp
An element of a list a :: l is either equal to a or belongs to l.
List.mem_map.mp
If an element belongs to map f l, it is the image under f of some element of l.
List.Nodup.map_on
A mapped list map f l has no duplicates if l has no duplicates and f is injective on l.
List.nodup_cons.mpr
Prepending an element a to a duplicate-free list l preserves duplicate-freeness if a is not in l.
List.sum_cons
The sum of elements in a :: l equals the head a plus the sum of the tail l.
if_false
An if-then-else expression with a false condition evaluates to the else branch.
mondrian_partition_width_free_height_signed_relation
In a partition of an n × n square with d ∣ n, if a tile r has width not divisible by d, there exists a duplicate-free list of other tiles with widths not divisible by d whose signed height sum equals the height of r.
mondrian_perfect_height_injective
In a Mondrian partition with defect 0, rectangle height is injective: no two distinct rectangles have the same height.
mondrian_two_chain_signed_sum_ne_zero
A non-empty list of signed, distinct integers from two geometric chains C * p^a and C * r * p^a (with C > 0, r ≥ 2, and p > r + 1) cannot have a signed sum of zero.

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_partition_width_dvd_of_height_two_chains (n d p r C : ℕ)    (P : List (ℕ × ℕ × ℕ × ℕ)) (hP : mondrian_is_partition n P)    (hz : mondrian_defect P = 0) (hdn : d ∣ n) (hC : 0 < C)    (hr : 2 ≤ r) (hpr : r + 1 < p)    (hheight : ∀ u ∈ P, ¬ d ∣ mondrian_rect_width u → ∃ a : ℕ,      mondrian_rect_height u = C * p ^ a ∨ mondrian_rect_height u = C * r * p ^ a) :    ∀ u ∈ P, d ∣ mondrian_rect_width u := by  classical  intro u hu  by_contra hfree  obtain ⟨L, hLnd, hLmem, hLsum⟩ :=    mondrian_partition_width_free_height_signed_relation n d P hP hdn u hu hfree  let H := (mondrian_rect_height u, false) ::    L.map (fun t => (mondrian_rect_height t.1, t.2))  have hhnd : (L.map (fun t => mondrian_rect_height t.1)).Nodup := by    have hh : ((L.map Prod.fst).map mondrian_rect_height).Nodup := by      apply List.Nodup.map_on _ hLnd      intro v hv w hw he      obtain ⟨v', hv', rfl⟩ := List.mem_map.mp hv      obtain ⟨w', hw', rfl⟩ := List.mem_map.mp hw      exact mondrian_perfect_height_injective n P hP hz v'.1 (hLmem v' hv').1        w'.1 (hLmem w' hw').1 he    simpa only [List.map_map, Function.comp_def] using hh  have hhead : mondrian_rect_height u ∉ L.map (fun t => mondrian_rect_height t.1) := by    intro hm    obtain ⟨t, ht, he⟩ := List.mem_map.mp hm    exact (hLmem t ht).2.1 (mondrian_perfect_height_injective n P hP hz      t.1 (hLmem t ht).1 u hu he)  have hnd : (H.map Prod.fst).Nodup := by    simpa only [H, List.map_cons, List.map_map, Function.comp_def] using      (List.nodup_cons.mpr ⟨hhead, hhnd⟩)  have hrep : ∀ t ∈ H, ∃ a : ℕ, t.1 = C * p ^ a ∨ t.1 = C * r * p ^ a := by    intro t ht    rcases List.mem_cons.mp ht with he | ht    · subst t      exact hheight u hu hfree    · obtain ⟨v, hv, rfl⟩ := List.mem_map.mp ht      exact hheight v.1 (hLmem v hv).1 (hLmem v hv).2.2  have hzero : (H.map (fun t => if t.2 then (t.1 : ℤ) else -(t.1 : ℤ))).sum = 0 := by    simp only [H, List.map_cons, List.sum_cons, List.map_map, Function.comp_def,      Bool.false_eq_true, if_false]    rw [hLsum]    ring  exact mondrian_two_chain_signed_sum_ne_zero p r C hC hr hpr H (by simp [H]) hnd hrep hzero
See it in the graphDiscuss this resultChallenge it