AFTD Auto-Formalizing Theoretical Domains

complex_cycle_four_laplacian_sector_cost_nonneg

theoremverified

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
Used by 1

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

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

    line 3

      dsimp [complex_laplacian_sector_cost]
  2. 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.

    lines 4–8

    uses sq_nonneg

      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)]
sq_nonneg
The square of any real number (or element of an ordered semiring) is nonnegative: 0 ≤ x^2.

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