weighted_max_cut_linear_combination
For all real numbers W and M, the convex combination of (3/4)W + (3/16)M and W - M with weights 16/19 and 3/19 equals (15/19)W.
Statement
theorem weighted_max_cut_linear_combination (W M : ℝ) :
(16 / 19 : ℝ) * ((3 / 4 : ℝ) * W + (3 / 16 : ℝ) * M) + (3 / 19 : ℝ) * (W - M) =
(15 / 19 : ℝ) * W- Source
- arXiv:2611.05178 Section 3
- Verified
- 09 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 3
- bpe_deviation_prob_nonnegFor any source bias p ∈ (0, 1), step count k, input length N, target constant c, and tolerance ε, the deviation probability…
- triangle_homothet_mem_leftFor points $p, q \in \mathbb{R}^2$, the point $p$ belongs to $\text{triangle\_homothet}(p, q)$.
- cubic_edge_entropy_zeroThe edge entropy production phi(0) is equal to 0.
Read back from the Lean
For all real numbers $W$ and $M$, \[ \frac{16}{19} \left( \frac{3}{4} W + \frac{3}{16} M \right) + \frac{3}{19} (W - M) = \frac{15}{19} W. \]
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
The claim is an algebraic identity over the real numbers. Expanding the left-hand side and grouping terms shows that the coefficients of $M$ cancel out to 0, while the coefficients of $W$ combine to $15/19$; the automated `ring` tactic performs this polynomial simplification directly.
The identity $\frac{16}{19}\left(\frac{3}{4}W + \frac{3}{16}M\right) + \frac{3}{19}(W - M) = \frac{15}{19}W$ holds for all real numbers $W$ and $M$. automation
Expanding both products yields $\left(\frac{16}{19} \cdot \frac{3}{4}\right) W + \left(\frac{16}{19} \cdot \frac{3}{16}\right) M + \frac{3}{19} W - \frac{3}{19} M = \frac{12}{19} W + \frac{3}{19} M + \frac{3}{19} W - \frac{3}{19} M$. The coefficients of $M$ cancel out ($\frac{3}{19} - \frac{3}{19} = 0$), while the coefficients of $W$ sum to $\frac{12}{19} + \frac{3}{19} = \frac{15}{19}$. The `ring` tactic carries out this standard ring normalization and rational arithmetic automatically.
ring
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.
/-- Linear combination identity combining the structural cut bound and the max-cut partition bound. -/theorem weighted_max_cut_linear_combination (W M : ℝ) : (16 / 19 : ℝ) * ((3 / 4 : ℝ) * W + (3 / 16 : ℝ) * M) + (3 / 19 : ℝ) * (W - M) = (15 / 19 : ℝ) * W := by ring