tile_complement_card_cases
Let d ≥ 3. If two natural numbers e_card and t_card satisfy e_card * t_card = 2^d and 2^(d - 3) ≤ e_card, then t_card equals 1, 2, 4, or 8.
Statement
theorem tile_complement_card_cases (d : ℕ) (hd : 3 ≤ d)
(e_card t_card : ℕ) (hprod : e_card * t_card = 2 ^ d) (hbound : 2 ^ (d - 3) ≤ e_card) :
t_card = 1 ∨ t_card = 2 ∨ t_card = 4 ∨ t_card = 8- Source
- arXiv:2610.24022
- Verified
- 22 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext
Read back from the Lean
For every natural number $d$ with $3 \le d$, and all natural numbers $e\_card$ and $t\_card$, if $e\_card \cdot t\_card = 2^d$ and $2^{d - 3} \le e\_card$, then $t\_card = 1$ or $t\_card = 2$ or $t\_card = 4$ or $t\_card = 8$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
Because the product of e_card and t_card is 2^d, t_card must be a divisor of 2^d, hence of the form 2^k. Multiplying the lower bound 2^(d - 3) ≤ e_card by 2^k yields 2^(d - 3) * 2^k ≤ 2^d = 2^(d - 3) * 8, which simplifies to 2^k ≤ 8 and thus k ≤ 3. Testing the four possible values k ∈ {0, 1, 2, 3} shows that t_card can only be 1, 2, 4, or 8.
t_card is a power of 2: t_card = 2^k for some k ≤ d
Since e_card * t_card = 2^d, t_card divides 2^d (by Dvd.intro_left). Because 2 is prime (Nat.prime_two), the only divisors of 2^d are powers of 2 with exponent at most d (Nat.dvd_prime_pow), so t_card = 2^k with k ≤ d.
uses
Dvd.intro_left,Nat.dvd_prime_pow,Nat.prime_twohave hdvd : t_card ∣ 2 ^ d := Dvd.intro_left e_card hprod obtain ⟨k, hk, rfl⟩ := (Nat.dvd_prime_pow Nat.prime_two).mp hdvd
2^(d - 3) * 2^k ≤ 2^d
Multiplying the assumed bound 2^(d - 3) ≤ e_card on the right by 2^k preserves the inequality (Nat.mul_le_mul_right), giving 2^(d - 3) * 2^k ≤ e_card * 2^k = 2^d.
uses
Nat.mul_le_mul_righthave h1 : 2 ^ (d - 3) * 2 ^ k ≤ 2 ^ d := by calc 2 ^ (d - 3) * 2 ^ k ≤ e_card * 2 ^ k := Nat.mul_le_mul_right (2 ^ k) hbound _ = 2 ^ d := hprod
2^d = 2^(d - 3) * 8
Since d ≥ 3, we have d = (d - 3) + 3 (Nat.sub_add_cancel). Splitting the exponent using pow_add gives 2^d = 2^(d - 3) * 2^3 = 2^(d - 3) * 8.
uses
Nat.sub_add_cancel,pow_addhave h2 : 2 ^ d = 2 ^ (d - 3) * 8 := by have hd3 : d = (d - 3) + 3 := (Nat.sub_add_cancel hd).symm rw [hd3, pow_add] rfl
2^k ≤ 8
Rewriting 2^d as 2^(d - 3) * 8 in the previous inequality yields 2^(d - 3) * 2^k ≤ 2^(d - 3) * 8. Since 2^(d - 3) is strictly positive (Nat.two_pow_pos), cancelling it from both sides gives 2^k ≤ 8 (Nat.le_of_mul_le_mul_left).
uses
Nat.two_pow_pos,Nat.le_of_mul_le_mul_leftrw [h2] at h1 have hpos : 0 < 2 ^ (d - 3) := Nat.two_pow_pos (d - 3) have hle : 2 ^ k ≤ 8 := Nat.le_of_mul_le_mul_left h1 hpos
k ≤ 3
Because the base 2 is strictly greater than 1, 2^k ≤ 8 = 2^3 is equivalent to k ≤ 3 (Nat.pow_le_pow_iff_right).
uses
Nat.pow_le_pow_iff_righthave hk3 : k ≤ 3 := (Nat.pow_le_pow_iff_right (by decide : 1 < 2)).mp hle
t_card = 1 ∨ t_card = 2 ∨ t_card = 4 ∨ t_card = 8
Since k is a natural number and k ≤ 3, k must be 0, 1, 2, or 3. Exhausting these four possibilities with interval_cases, evaluating 2^k in each case produces 1, 2, 4, or 8 respectively.
interval_cases k <;> decide
Dvd.intro_left- If c * a = b, then a divides b.
Nat.dvd_prime_pow- A natural number divides a prime power p^m if and only if it equals p^k for some k ≤ m.
Nat.prime_two- 2 is a prime number.
Nat.mul_le_mul_right- Multiplying both sides of an inequality by a natural number on the right preserves the inequality.
Nat.sub_add_cancel- For natural numbers with m ≤ n, (n - m) + m = n.
pow_add- For any element in a monoid, a^(m + n) = a^m * a^n.
Nat.two_pow_pos- Any power of 2 is strictly positive.
Nat.le_of_mul_le_mul_left- If c * a ≤ c * b and c is strictly positive, then a ≤ b.
Nat.pow_le_pow_iff_right- For a base a > 1, a^n ≤ a^m if and only if n ≤ m.
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.
/-- Cardinality cases for the complement of a translational tile of size at least 2^(d-3). -/theorem tile_complement_card_cases (d : ℕ) (hd : 3 ≤ d) (e_card t_card : ℕ) (hprod : e_card * t_card = 2 ^ d) (hbound : 2 ^ (d - 3) ≤ e_card) : t_card = 1 ∨ t_card = 2 ∨ t_card = 4 ∨ t_card = 8 := by have hdvd : t_card ∣ 2 ^ d := Dvd.intro_left e_card hprod obtain ⟨k, hk, rfl⟩ := (Nat.dvd_prime_pow Nat.prime_two).mp hdvd have h1 : 2 ^ (d - 3) * 2 ^ k ≤ 2 ^ d := by calc 2 ^ (d - 3) * 2 ^ k ≤ e_card * 2 ^ k := Nat.mul_le_mul_right (2 ^ k) hbound _ = 2 ^ d := hprod have h2 : 2 ^ d = 2 ^ (d - 3) * 8 := by have hd3 : d = (d - 3) + 3 := (Nat.sub_add_cancel hd).symm rw [hd3, pow_add] rfl rw [h2] at h1 have hpos : 0 < 2 ^ (d - 3) := Nat.two_pow_pos (d - 3) have hle : 2 ^ k ≤ 8 := Nat.le_of_mul_le_mul_left h1 hpos have hk3 : k ≤ 3 := (Nat.pow_le_pow_iff_right (by decide : 1 < 2)).mp hle interval_cases k <;> decide