Lemma 4.1, p. 9 — f_a(x) = x(1 − ax) is concave, unimodal with maximum 1/(4a), has no nonzero fixed point and f_a(x) < x
ProvedRecMarkovGraph.IndepLB.lemma_4_1concave-functionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1recursion
Let and . Then is concave on and:
- is strictly increasing on and strictly decreasing on ;
- for all , with equality at ;
- only for ;
- for ;
- for ;
- for all ;
- for every and every real .
These elementary facts drive the analysis of the recursion , which governs the edge probabilities of (with ).
Differences from the source:
- reading: "is increasing on (−∞, 1/(2a)] and decreasing on (1/(2a), ∞)" → StrictMonoOn on Iic (1/(2a)) and StrictAntiOn on Ioi (1/(2a)); reason: the stronger of the two readings, true for a > 0
- encoding: "has a maximum value of 1/(4a)" → f_a(x) ≤ 1/(4a) for all x and f_a(1/(2a)) = 1/(4a); reason: the definition of a maximum value
- generalization: item 7 for a > b, with b a parameter of (3), i.e. b ∈ (0, 1] → every real b < a; reason: the inequality −a x² < −b x² holds for every real b < a; it specializes to b ∈ (0, 1]
Preamble
import Mathlib import Definitions.Def_RecMarkovGraph_IndepLB_Model
Formal statement
namespace RecMarkovGraph.IndepLB
open Set
theorem lemma_4_1 (a : ℝ) (ha : 0 < a) (ha1 : a ≤ 1) :
ConcaveOn ℝ univ (fa a) ∧
(StrictMonoOn (fa a) (Iic (1 / (2 * a))) ∧ StrictAntiOn (fa a) (Ioi (1 / (2 * a)))) ∧
((∀ x, fa a x ≤ 1 / (4 * a)) ∧ fa a (1 / (2 * a)) = 1 / (4 * a)) ∧
(∀ x, fa a x = x → x = 0) ∧
(∀ x ∈ Ioo (0 : ℝ) 1, fa a x ∈ Ioo (0 : ℝ) 1) ∧
(∀ x, x ≠ 0 → fa a x < x) ∧
(∀ x, a * fa a x = fa 1 (a * x)) ∧
(∀ b x : ℝ, b < a → 0 < x → fa a x < fa b x) := by sorry
end RecMarkovGraph.IndepLB
Source
Gupte, Zhu, Large independent sets in recursive Markov random graphs, arXiv:2207.04514v4, p. 9, Lemma 4.1 (proof in §9, p. 22); context (3), p. 9
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.