mondrian_ordered_shape_half
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 thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- 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.
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.
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)
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.
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_swaphave 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⟩
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.
uses
Finset.card_le_one.mpr,Finset.mem_inter.mp,mondrian_mem_factor_shapes,Finset.mem_map.mp,congrArg,Prod.fst,Prod.snd,Prod.exthave 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
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.
uses
Finset.card_union_add_card_interhave 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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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