🏛️ Atlas✒️Isabelle.MemoryAccessFloors.Symmetric_Branch view on GitHub ↗3 theorems
(*  Title:      Symmetric_Branch.thy    Author:     Carles Marin    Copyright:  Carles Marin    License:    BSD-3-Clause     The symmetric branch of the turn-wait-turn family never beats the square pulse (memory-floor notes, slow noise    with memory loss above the threshold, case 3 of the argument): in units z0 = 1, 2 A0 = pi, for a turn of phi in    (0, pi/2] and a wait w >= 0, with s = sin phi, c = cos phi, z = c - w s / 2 and y = phi + s + w (1 + c) / 2,        Q_m = 2 (z^2 - 1) + y (pi + y) >= pi phi + s (pi - 2 s) > 0.    Only the inequality is formalised; the reduction of the cost to Q_m is a written argument.*) theory Symmetric_Branch  imports "HOL-Analysis.Analysis"begin lemma one_minus_z_sq:  fixes p w :: real  assumes "0 \<le> w" "0 \<le> sin p" "cos p \<le> 1"  shows "1 - (cos p - w * sin p / 2)\<^sup>2 \<le> (sin p)\<^sup>2 + (1 + cos p) * w * sin p / 2"proof -  define s c z where "s = sin p" and "c = cos p" and "z = c - w * s / 2"  have ws: "0 \<le> w * s" using assms(1,2) by (simp add: s_def)  have zc: "z \<le> c" using ws by (simp add: z_def)  have c1: "c \<le> 1" using assms(3) by (simp add: c_def)  have omz: "0 \<le> 1 - z" using zc c1 by linarith  have "(1 - z) * (1 + z) \<le> (1 - z) * (1 + c)" by (rule mult_left_mono) (use zc omz in auto)  moreover have "(1 - z) * (1 + c) = s\<^sup>2 + (1 + c) * w * s / 2"  proof -    have "s\<^sup>2 = 1 - c\<^sup>2" by (simp add: s_def c_def sin_squared_eq)    then show ?thesis by (simp add: z_def algebra_simps power2_eq_square)  qed  moreover have "1 - z\<^sup>2 = (1 - z) * (1 + z)" by (simp add: power2_eq_square algebra_simps)  ultimately have "1 - z\<^sup>2 \<le> s\<^sup>2 + (1 + c) * w * s / 2" by linarith  then show ?thesis by (simp add: s_def c_def z_def)qed theorem symmetric_branch_bound:  fixes p w :: real  assumes p0: "0 < p" and p1: "p \<le> pi / 2" and w0: "0 \<le> w"  shows "pi * p + sin p * (pi - 2 * sin p)           \<le> 2 * ((cos p - w * sin p / 2)\<^sup>2 - 1)              + (p + sin p + w * (1 + cos p) / 2) * (pi + (p + sin p + w * (1 + cos p) / 2))"proof -  define s c y where "s = sin p" and "c = cos p" and "y = p + sin p + w * (1 + cos p) / 2"  have s0: "0 \<le> s" unfolding s_def using p0 p1 by (intro sin_ge_zero) auto  have s1: "s \<le> 1" by (simp add: s_def)  have c0: "0 \<le> c" unfolding c_def using p0 p1 by (intro cos_ge_zero) auto  have c1: "c \<le> 1" by (simp add: c_def)  have y0: "0 \<le> y" using p0 s0 c0 w0 by (simp add: y_def s_def c_def)  have sp: "0 \<le> sin p" using s0 by (simp add: s_def)  have h1: "1 - (cos p - w * sin p / 2)\<^sup>2 \<le> (sin p)\<^sup>2 + (1 + cos p) * w * sin p / 2"    by (rule one_minus_z_sq[OF w0 sp cos_le_one])  have h2: "2 * (1 - (cos p - w * sin p / 2)\<^sup>2) \<le> 2 * ((sin p)\<^sup>2 + (1 + cos p) * w * sin p / 2)"    by (rule mult_left_mono[OF h1]) simp  have h3: "2 * ((sin p)\<^sup>2 + (1 + cos p) * w * sin p / 2) = 2 * s\<^sup>2 + (1 + c) * w * s"    by (simp add: s_def c_def algebra_simps)  have step1: "2 * (1 - (cos p - w * sin p / 2)\<^sup>2) \<le> 2 * s\<^sup>2 + (1 + c) * w * s"    using h2 h3 by linarith  have half: "s \<le> pi / 2" using s1 pi_gt3 by linarith  have wterm: "0 \<le> w * (1 + c) * (pi / 2 - s)"    using w0 c0 half by (intro mult_nonneg_nonneg) auto  have a1: "y * (pi + y) \<ge> pi * y" using y0 by (simp add: algebra_simps)  have a2: "pi * y = pi * (p + s) + w * (1 + c) * (pi / 2)"    by (simp add: y_def s_def c_def algebra_simps)  have a3: "w * (1 + c) * (pi / 2 - s) = w * (1 + c) * (pi / 2) - (1 + c) * w * s"    by (simp add: algebra_simps)  have a4: "pi * (p + s) - 2 * s\<^sup>2 = pi * p + s * (pi - 2 * s)"    by (simp add: algebra_simps power2_eq_square)  have main: "y * (pi + y) - 2 * (1 - (cos p - w * sin p / 2)\<^sup>2) \<ge> pi * p + s * (pi - 2 * s)"    using a1 a2 a3 a4 step1 wterm by linarith  have rhs: "2 * ((cos p - w * sin p / 2)\<^sup>2 - 1) + y * (pi + y)             = y * (pi + y) - 2 * (1 - (cos p - w * sin p / 2)\<^sup>2)"    by (simp add: algebra_simps)  show ?thesis using main rhs by (simp add: y_def s_def)qed corollary symmetric_branch_positive:  fixes p w :: real  assumes "0 < p" "p \<le> pi / 2" "0 \<le> w"  shows "0 < 2 * ((cos p - w * sin p / 2)\<^sup>2 - 1)              + (p + sin p + w * (1 + cos p) / 2) * (pi + (p + sin p + w * (1 + cos p) / 2))"proof -  have s0: "0 \<le> sin p" using assms by (intro sin_ge_zero) auto  have s1: "sin p \<le> 1" by simp  have "0 \<le> pi - 2 * sin p" using s1 pi_gt3 by linarith  then have "0 \<le> sin p * (pi - 2 * sin p)" using s0 by (rule mult_nonneg_nonneg[rotated])  moreover have "0 < pi * p" using assms(1) by simp  ultimately show ?thesis using symmetric_branch_bound[OF assms] by linarithqed end