Concavity of the binary perspective of a concave test
ProvedKSATSingleFlip.Connect.concave_test_perspectiveFor a concave test ψ on [0,1], the binary perspective (v₀+v₁)ψ(v₁/(v₀+v₁)) is jointly concave on pairs of nonnegative coordinates with positive total. This is the perspective inequality used in the single-clause comparison in Lemma 4.5.
Preamble
import Mathlib set_option autoImplicit false open Set
Formal statement
theorem KSATSingleFlip.Connect.concave_test_perspective (ψ : ℝ → ℝ) (hψ : ConcaveOn ℝ (Icc 0 1) ψ)
(x0 x1 y0 y1 a b : ℝ)
(hx0 : 0 ≤ x0) (hx1 : 0 ≤ x1) (hy0 : 0 ≤ y0) (hy1 : 0 ≤ y1)
(hxs : 0 < x0+x1) (hys : 0 < y0+y1)
(ha : 0 ≤ a) (hb : 0 ≤ b) (hab : a+b=1) :
a*(x0+x1)*ψ (x1/(x0+x1)) + b*(y0+y1)*ψ (y1/(y0+y1)) ≤
(a*(x0+x1)+b*(y0+y1))*ψ ((a*x1+b*y1)/(a*(x0+x1)+b*(y0+y1))) := by sorrySource
Wang–Yin–Yu–Zhang, Single-Variable Connectivity in Random k-SAT, proof of Lemma 4.5, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/737.pdf