edge_list_cubic_encoding_time_exponent
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.
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.
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
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.
uses
Nat.mul_div_cancel_leftrw [h, show 3 * n ^ 2 + 3 * n = 3 * (n * n + n) by ring, Nat.mul_div_cancel_left _ (by norm_num)]
⌊√(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).
uses
Nat.sqrt_add_eqexact 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
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 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)