complex_cycle_four_laplacian_sector_cost_nonneg
The sum of the Laplacian sector costs around any closed four-step complex cycle is nonnegative, including repeated vertices.
Statement
theorem complex_cycle_four_laplacian_sector_cost_nonneg (a b c d : ℂ) :
0 ≤ complex_laplacian_sector_cost a b + complex_laplacian_sector_cost b c + complex_laplacian_sector_cost c d + complex_laplacian_sector_cost d a- Source
- Sector-bound formalization for IN-166; arXiv:math/0508176, Theorem 5.
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- complex_laplacian_sector_costThe sum of the real and imaginary parts of the complex Laplacian edge form.
- Used by 1
- laplacian_order_four_stationary_eigenvalue_one_sideFor a real order-four matrix with zero row sums, nonpositive off-diagonal entries, and a strictly positive left null vector, every complex…
The proof, explained
The proof shows that the four-cycle Laplacian sector cost is nonnegative by establishing that it is a sum of squares. Expanding the definition reveals an algebraic identity expressing twice the cycle cost as the sum of four squared real expressions involving the real and imaginary parts of the four complex vertices. The nonlinear arithmetic tactic `nlinarith` then finishes the proof using the nonnegativity of squares (`sq_nonneg`).
The sector costs are expressed in terms of the real and imaginary components of the vertices.
Unfolding the definition of `complex_laplacian_sector_cost` rewrites the cyclic sum into a polynomial in the real and imaginary parts of a, b, c, and d.
dsimp [complex_laplacian_sector_cost]The sum of the four Laplacian sector costs is nonnegative. automation
The expanded cyclic sum is identically equal to 1/2 times the sum of four squares: (a.re - c.re - (b.im - d.im))^2 + (a.im - c.im + (b.re - d.re))^2 + (a.re - b.re + c.re - d.re)^2 + (a.im - b.im + c.im - d.im)^2. By `sq_nonneg`, each square is nonnegative, and `nlinarith` uses these four inequalities to conclude that the overall sum is at least 0.
uses
sq_nonnegnlinarith only [ sq_nonneg (a.re - c.re - (b.im - d.im)), sq_nonneg (a.im - c.im + (b.re - d.re)), sq_nonneg (a.re - b.re + c.re - d.re), sq_nonneg (a.im - b.im + c.im - d.im)]
sq_nonneg- The square of any real number (or element of an ordered semiring) is nonnegative: 0 ≤ x^2.
- The proof relies on an algebraic sum-of-squares identity: twice the cyclic sum of the four sector costs is identically equal to the sum of the four squares supplied to `nlinarith`. This identity is verified automatically by nonlinear arithmetic without writing out the intermediate algebraic equality.
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 complex_cycle_four_laplacian_sector_cost_nonneg (a b c d : ℂ) : 0 ≤ complex_laplacian_sector_cost a b + complex_laplacian_sector_cost b c + complex_laplacian_sector_cost c d + complex_laplacian_sector_cost d a := by dsimp [complex_laplacian_sector_cost] nlinarith only [ sq_nonneg (a.re - c.re - (b.im - d.im)), sq_nonneg (a.im - c.im + (b.re - d.re)), sq_nonneg (a.re - b.re + c.re - d.re), sq_nonneg (a.im - b.im + c.im - d.im)]