mondrian_mem_factor_shapes
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
- mondrian_shape_exponent_interval_boundA family of distinct sorted factor pairs that can be encoded by a chosen side C times p to an exponent in [lo,hi] has at most hi plus one…
- mondrian_prime_area_shape_boundFor distinct primes p and q, if t+r=2e, at most r plus floor(log_p(q)) plus one shapes of area q times p^t fit in the q times p^e square.
- mondrian_ordered_shape_halfTwice the number of available unordered dimension pairs is at most one plus the number of ordered dimension pairs fitting in the square.
- mondrian_prime_free_area_shape_boundFor distinct primes p and q, if t+r=2e, at most r plus floor(log_p(q)) plus one shapes of pure p-power area p^t fit in the q times p^e…
- mondrian_partition_prime_free_shape_count_boundIn an admissible equal-area partition, any selected collection of tiles each having a side indivisible by q has cardinality at most the…
- mondrian_shape_boundA partition of the n-square whose rectangles all have area A has at most as many members as available unordered dimension pairs.
- mondrian_prime_power_shape_boundFor k at least two and positive A with k times A equal to the area of a p-power square, the number of available shapes is at most the…
- mondrian_prime_square_area_middle_shape_boundFor distinct primes p and q and t+r=2e with positive r, at most r unordered shapes of area q^2 times p^t fitting in a q times p^e square…
- mondrian_prime_square_area_free_shape_boundFor distinct primes p and q and t+r=2e, at most r unordered shapes of area q^2 times p^t fitting in a q times p^e square have a side…
- mondrian_prime_first_exponent_shape_boundWhen the p-adic exponent of k is exactly one, at most c unordered shapes of area A fit in a c times p to the e square with area k times A…
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.
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.
uses
mondrian_factor_shapes,Finset.mem_filter,Nat.mem_divisorsAntidiagonalsimp only [mondrian_factor_shapes, Finset.mem_filter, Nat.mem_divisorsAntidiagonal]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).
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
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_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