Zulip Chat Archive

Stream: mathlib4

Topic: Can `nlinarith` prove the Motzkin polynomial positive?


Bolton Bailey (Mar 03 2025 at 02:36):

I was telling a cryptographer at a conference about Lean and showing him some goals that can be proved by linarith. he asked if it could prove the "Motzkin polynomial" positive 0 < 1 - 3 * x^2 * y^2 + x^2 * y^4 + x^4 * y^2, which I guess has the distinction of not being a sum of squares of polynomials. I figured I would ask here if there is something special I can do to get nlinarith to prove this positive.

Kim Morrison (Mar 03 2025 at 03:22):

Seems pretty unlikely!

Jeremy Tan (Mar 03 2025 at 03:25):

Well, this is the textbook way of proving it:

import Mathlib.Analysis.MeanInequalities

open Real

theorem motzkin_polynomial_nonneg {x y : } :
    0  1 - 3 * x ^ 2 * y ^ 2 + x ^ 2 * y ^ 4 + x ^ 4 * y ^ 2 := by
  have nn₁ : 0  x ^ 2 * y ^ 4 := by positivity
  have nn₂ : 0  x ^ 4 * y ^ 2 := by positivity
  have key := geom_mean_le_arith_mean3_weighted (by norm_num) (by norm_num) (by norm_num)
    nn₁ nn₂ zero_le_one (add_thirds 1)
  rw [one_rpow, mul_one,  Real.mul_rpow nn₁ nn₂,  mul_add,  mul_add,
    show x ^ 2 * y ^ 4 * (x ^ 4 * y ^ 2) = (x ^ 2) ^ 3 * (y ^ 2) ^ 3 by ring,
    Real.mul_rpow (by positivity) (by positivity),
     Real.rpow_natCast _ 3,  Real.rpow_mul (sq_nonneg x),
     Real.rpow_natCast _ 3,  Real.rpow_mul (sq_nonneg y),
    show ((3 : ) * ((1 : ) / 3)) = 1 by norm_num, rpow_one, rpow_one] at key
  linarith

Kim Morrison (Mar 20 2025 at 23:14):

@Jeremy Tan, you should PR this somewhere! If someone also wanted to prove that it is not a sum of squares then it would be a great candidate for Counterexamples/.

Jeremy Tan (Mar 21 2025 at 06:47):

#23170


Last updated: May 02 2025 at 03:31 UTC