AFTD Auto-Formalizing Theoretical Domains

edge_list_cubic_encoding_time_exponent

theoremverified

For every natural number n, the integer square root of ⌊2·⌊(3n²+3n)/2⌋/3⌋ equals n. (A cubic edge list on n vertices has unary encoding length N = (3n²+3n)/2, so the exponent ⌊√⌊2N/3⌋⌋ in the time bound of the O*(2^n) question is exactly n.)

Statement

theorem edge_list_cubic_encoding_time_exponent (n : ℕ) :
    Nat.sqrt (2 * ((3 * n ^ 2 + 3 * n) / 2) / 3) = n
Source
arXiv:2610.35794, Conjecture 5 (calibrating the time bound to n)
Verified
30 Oct 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

The proof evaluates the expression by simplifying the integer divisions from the inside out and then computing the integer square root. First, since n(n + 1) is even, 3n² + 3n = 3n(n + 1) is divisible by 2, so multiplying by 2 after integer division by 2 is exact. Next, dividing 3(n² + n) by 3 cancels the factor of 3 to leave n² + n. Finally, since the remainder n satisfies n ≤ 2n, the integer square root of n² + n is identically n.

  1. 2 * ⌊(3n² + 3n) / 2⌋ = 3n² + 3n

    We show that integer division by 2 causes no truncation. The product of consecutive integers n(n + 1) is even by Nat.even_mul_succ_self, so 2 divides n(n + 1) by even_iff_two_dvd.mp. Rewriting 3n² + 3n as 3(n(n + 1)) by polynomial identity, Dvd.dvd.mul_left shows that 2 also divides 3n² + 3n. Therefore, by Nat.mul_div_cancel', multiplying by 2 exactly inverts division by 2.

    lines 3–8

    uses Nat.even_mul_succ_self, even_iff_two_dvd.mp, Dvd.dvd.mul_left, Nat.mul_div_cancel'

      have h : 2 * ((3 * n ^ 2 + 3 * n) / 2) = 3 * n ^ 2 + 3 * n := by
        have : 2 ∣ 3 * n ^ 2 + 3 * n := by
          have := Nat.even_mul_succ_self n
          rw [show 3 * n ^ 2 + 3 * n = 3 * (n * (n + 1)) by ring]
          exact Dvd.dvd.mul_left (even_iff_two_dvd.mp this) 3
        exact Nat.mul_div_cancel' this
  2. The goal reduces to ⌊√(n² + n)⌋ = n.

    Rewriting with the identity h replaces 2 * ⌊(3n² + 3n) / 2⌋ with 3n² + 3n. Factoring out 3 gives 3 * (n * n + n) by ring arithmetic. Because 0 < 3 (verified by norm_num), dividing by 3 cancels the factor of 3 via Nat.mul_div_cancel_left, leaving ⌊√(n² + n)⌋ = n.

    line 9

    uses Nat.mul_div_cancel_left

      rw [h, show 3 * n ^ 2 + 3 * n = 3 * (n * n + n) by ring, Nat.mul_div_cancel_left _ (by norm_num)]
  3. ⌊√(n² + n)⌋ = n, completing the proof.

    By Nat.sqrt_add_eq, the integer square root ⌊√(n² + a)⌋ is n whenever a ≤ 2n. Setting a = n, the required inequality n ≤ n + n is verified by linear integer arithmetic (omega).

    line 10

    uses Nat.sqrt_add_eq

      exact Nat.sqrt_add_eq n (by omega)
Nat.even_mul_succ_self
The product of any natural number and its successor, n(n + 1), is even.
even_iff_two_dvd.mp
If a number is even, then 2 divides it.
Dvd.dvd.mul_left
If a divides b, then a divides any multiple c * b.
Nat.mul_div_cancel'
If n divides m, then n * (m / n) = m.
Nat.mul_div_cancel_left
For any positive natural number n, (n * m) / n = m.
Nat.sqrt_add_eq
If a ≤ 2n, then the integer square root of n² + a equals 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

theorem edge_list_cubic_encoding_time_exponent (n : ℕ) :    Nat.sqrt (2 * ((3 * n ^ 2 + 3 * n) / 2) / 3) = n := by  have h : 2 * ((3 * n ^ 2 + 3 * n) / 2) = 3 * n ^ 2 + 3 * n := by    have : 2 ∣ 3 * n ^ 2 + 3 * n := by      have := Nat.even_mul_succ_self n      rw [show 3 * n ^ 2 + 3 * n = 3 * (n * (n + 1)) by ring]      exact Dvd.dvd.mul_left (even_iff_two_dvd.mp this) 3    exact Nat.mul_div_cancel' this  rw [h, show 3 * n ^ 2 + 3 * n = 3 * (n * n + n) by ring, Nat.mul_div_cancel_left _ (by norm_num)]  exact Nat.sqrt_add_eq n (by omega)
See it in the graphDiscuss this resultChallenge it