mnw2_case3_denom_pos
theoremverified
A specific cubic polynomial with positive coefficients (plus the constant 1) in ten nonnegative variables is strictly positive. It is the multiplier of the Positivstellensatz certificate in the hard case of the two-agent price-of-MNW upper bound.
Statement
theorem mnw2_case3_denom_pos (p q r s α β γ δ e3 e4 : ℝ) (hp : 0 ≤ p) (hq : 0 ≤ q) (hr : 0 ≤ r) (hs : 0 ≤ s) (hα : 0 ≤ α) (hβ : 0 ≤ β) (hγ : 0 ≤ γ) (hδ : 0 ≤ δ) (he3 : 0 ≤ e3) (he4 : 0 ≤ e4) : 0 < (4753/10)*p^3 + (2271/2)*p^2*q + (8186/5)*p^2*β + (7861/10)*p^2*γ + (13567/10)*p*q^2 + (1084/5)*p*q*s + (2954/5)*p*q*α + (1949/2)*p*q*β + (613/2)*p*r*s + (4165/2)*p*r*α + (4949/5)*p*r*β + (11757/10)*p*r*δ + (10323/5)*p*s*β + (6808/5)*p*s*γ + (3762/5)*p*s*δ + (2772/5)*p*α*γ + (2841/2)*p*α*δ + (9797/5)*p*α*e4 + (329/2)*p*β^2 + (8561/10)*p*β*δ + (6222/5)*p*γ^2 + (3067/2)*p*γ*δ + (15329/10)*p*δ^2 + (587/2)*p*e3^2 + (79/10)*q^2*r + 373*q^2*β + (10957/10)*q^2*δ + (6059/10)*q^2*e3 + (1131/5)*q^2*e4 + (27383/10)*q*r*α + (7341/10)*q*s*α + (5269/10)*q*s*β + 667*q*s*γ + (15733/10)*q*s*δ + (1819/5)*q*α*δ + (13073/5)*q*α*e4 + (5281/10)*q*β*γ + (15979/10)*q*γ^2 + (14483/10)*q*γ*δ + (349/5)*q*δ^2 + (479/5)*r^3 + (2397/10)*r^2*s + (10807/10)*r^2*α + (3213/10)*r^2*γ + (826/5)*r*s^2 + (4156/5)*r*s*α + 65*r*s*β + (11247/10)*r*s*γ + 40*r*s*δ + (3989/5)*r*α*β + (5922/5)*r*α*δ + (7459/10)*r*β^2 + 1402*r*β*δ + (1388/5)*r*β*e3 + (1199/2)*r*γ^2 + (26/5)*r*γ*e3 + (2839/5)*r*δ^2 + (12097/5)*r*δ*e3 + (1184/5)*r*e3^2 + (317/10)*s^2*α + (1123/10)*s*α*β + (6337/10)*s*α*γ + (2396/5)*s*α*δ + (2723/10)*s*α*e4 + 783*s*β^2 + (3594/5)*s*β*γ + (14077/10)*s*β*e3 + (13107/10)*s*γ*δ + (11147/5)*s*γ*e3 + 2080*s*δ*e3 + (293/10)*α*β^2 + (15803/10)*α*β*δ + (5741/5)*α*β*e4 + (2919/10)*α*γ*e4 + 8*β^3 + 566*β^2*δ + (3933/10)*β^2*e4 + (567/10)*β*e3^2 + (2752/5)*β*e4^2 + (3009/10)*γ^2*δ + (1781/10)*γ^2*e3 + (1607/10)*γ*δ*e3 + (793/5)*γ*e4^2 + (8787/10)*δ^2*e3 + 1- Source
- step towards mnw_two_agents_welfare_le (upper bound 27/23 for the price of MNW with two agents, The Price of Fairness for Indivisible Goods, arXiv:1905.04910, Theorem 5.4; Positivstellensatz certificate found by computer)
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- mnw2_case3Goods are grouped by their owners under an allocation O and an allocation N: A = (O:0, N:0), B = (O:1, N:0), C = (O:0, N:1), D = (O:1,…
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.
/-- Positivity of the multiplier polynomial in the certificate for the hard case of the two-agent price-of-MNW bound. -/theorem mnw2_case3_denom_pos (p q r s α β γ δ e3 e4 : ℝ) (hp : 0 ≤ p) (hq : 0 ≤ q) (hr : 0 ≤ r) (hs : 0 ≤ s) (hα : 0 ≤ α) (hβ : 0 ≤ β) (hγ : 0 ≤ γ) (hδ : 0 ≤ δ) (he3 : 0 ≤ e3) (he4 : 0 ≤ e4) : 0 < (4753/10)*p^3 + (2271/2)*p^2*q + (8186/5)*p^2*β + (7861/10)*p^2*γ + (13567/10)*p*q^2 + (1084/5)*p*q*s + (2954/5)*p*q*α + (1949/2)*p*q*β + (613/2)*p*r*s + (4165/2)*p*r*α + (4949/5)*p*r*β + (11757/10)*p*r*δ + (10323/5)*p*s*β + (6808/5)*p*s*γ + (3762/5)*p*s*δ + (2772/5)*p*α*γ + (2841/2)*p*α*δ + (9797/5)*p*α*e4 + (329/2)*p*β^2 + (8561/10)*p*β*δ + (6222/5)*p*γ^2 + (3067/2)*p*γ*δ + (15329/10)*p*δ^2 + (587/2)*p*e3^2 + (79/10)*q^2*r + 373*q^2*β + (10957/10)*q^2*δ + (6059/10)*q^2*e3 + (1131/5)*q^2*e4 + (27383/10)*q*r*α + (7341/10)*q*s*α + (5269/10)*q*s*β + 667*q*s*γ + (15733/10)*q*s*δ + (1819/5)*q*α*δ + (13073/5)*q*α*e4 + (5281/10)*q*β*γ + (15979/10)*q*γ^2 + (14483/10)*q*γ*δ + (349/5)*q*δ^2 + (479/5)*r^3 + (2397/10)*r^2*s + (10807/10)*r^2*α + (3213/10)*r^2*γ + (826/5)*r*s^2 + (4156/5)*r*s*α + 65*r*s*β + (11247/10)*r*s*γ + 40*r*s*δ + (3989/5)*r*α*β + (5922/5)*r*α*δ + (7459/10)*r*β^2 + 1402*r*β*δ + (1388/5)*r*β*e3 + (1199/2)*r*γ^2 + (26/5)*r*γ*e3 + (2839/5)*r*δ^2 + (12097/5)*r*δ*e3 + (1184/5)*r*e3^2 + (317/10)*s^2*α + (1123/10)*s*α*β + (6337/10)*s*α*γ + (2396/5)*s*α*δ + (2723/10)*s*α*e4 + 783*s*β^2 + (3594/5)*s*β*γ + (14077/10)*s*β*e3 + (13107/10)*s*γ*δ + (11147/5)*s*γ*e3 + 2080*s*δ*e3 + (293/10)*α*β^2 + (15803/10)*α*β*δ + (5741/5)*α*β*e4 + (2919/10)*α*γ*e4 + 8*β^3 + 566*β^2*δ + (3933/10)*β^2*e4 + (567/10)*β*e3^2 + (2752/5)*β*e4^2 + (3009/10)*γ^2*δ + (1781/10)*γ^2*e3 + (1607/10)*γ*δ*e3 + (793/5)*γ*e4^2 + (8787/10)*δ^2*e3 + 1 := by positivity