AFTD Auto-Formalizing Theoretical Domains

tile_complement_card_cases

theoremverified

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.

  1. 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.

    lines 5–6

    uses Dvd.intro_left, Nat.dvd_prime_pow, Nat.prime_two

      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
  2. 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.

    lines 7–9

    uses Nat.mul_le_mul_right

      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
  3. 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.

    lines 10–13

    uses Nat.sub_add_cancel, pow_add

      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
  4. 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).

    lines 14–16

    uses Nat.two_pow_pos, Nat.le_of_mul_le_mul_left

      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
  5. 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).

    line 17

    uses Nat.pow_le_pow_iff_right

      have hk3 : k ≤ 3 := (Nat.pow_le_pow_iff_right (by decide : 1 < 2)).mp hle
  6. 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.

    line 18

      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

/-- 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
See it in the graphDiscuss this resultChallenge it