🏛️ Atlas✒️Isabelle.MemoryAccessFloors.Robust_Cost view on GitHub ↗25 theorems
(*  Title:      Robust_Cost.thy    Author:     Carles Marín    Copyright (c) 2026 Carles Marín. All rights reserved.    License:    BSD     From "Exact limits for writing a quantum memory" (C. Marín, draft, November 2026): the exact cost of cancelling the first-order leakage    with a pulse of fixed phase, (gq + gm)/(2G) arccos(|gq - gm|/(gq + gm)), as the minimum over the axial    displacement of the shortest U-turn length L(s). L is taken as a definition: that it is the shortest    length is Dubins' theorem.*) theory Robust_Cost  imports "HOL-Analysis.Analysis"begin text \<open>The minimal duration @{text "L(u)"} of a U-turn with zero leakage is taken as a definition (that it is  the minimum is Dubins' theorem and is not formalised here).  With rates @{text "a \<ge> b \<ge> 0"} the cost in the  favourable direction is @{text "f(u) = ((a+b) L(u) - (a-b) u)/2 - (a+b) \<pi>/2"}.\<close> section \<open>A. Definitions\<close> definition Lccc :: "real \<Rightarrow> real" where  "Lccc u = 3 * pi - 4 * arcsin (sqrt (4 + u\<^sup>2) / 4)" definition Lcsc :: "real \<Rightarrow> real" where  "Lcsc u = pi + 2 * arctan (2 / sqrt (u\<^sup>2 - 4)) + sqrt (u\<^sup>2 - 4)" definition Lmin :: "real \<Rightarrow> real" where  "Lmin u = (if u \<le> 2 then Lccc u else Lcsc u)" definition cost :: "real \<Rightarrow> real \<Rightarrow> real \<Rightarrow> real" where  "cost a b u = ((a + b) * Lmin u - (a - b) * u) / 2 - (a + b) * pi / 2" text \<open>An auxiliary form of the CSC branch which is continuous at @{text "u = 2"}.\<close> definition Hh :: "real \<Rightarrow> real" where  "Hh u = 2 * pi - 2 * arctan (sqrt (u\<^sup>2 - 4) / 2) + sqrt (u\<^sup>2 - 4)" lemma unfavourable_ge:  fixes a b u :: real  assumes "b \<le> a" and "0 \<le> u"  shows "cost a b u \<le> cost a b u + (a - b) * u"  using assms by (simp add: mult_nonneg_nonneg) section \<open>B. The CSC branch\<close> lemma sq_minus4_pos:  fixes u :: real  assumes "2 < u"  shows "0 < u\<^sup>2 - 4"proof -  have "u\<^sup>2 - 4 = (u - 2) * (u + 2)" by (simp add: power2_eq_square algebra_simps)  moreover have "0 < (u - 2) * (u + 2)" using assms by (intro mult_pos_pos) auto  ultimately show ?thesis by simpqed lemma sqrt_deriv:  fixes u :: real  assumes "2 < u"  shows "((\<lambda>x. sqrt (x\<^sup>2 - 4)) has_real_derivative u / sqrt (u\<^sup>2 - 4)) (at u)"proof -  have pos: "0 < u\<^sup>2 - 4" by (rule sq_minus4_pos[OF assms])  have h1: "((\<lambda>x::real. x\<^sup>2 - 4) has_real_derivative 2 * u) (at u)"    by (rule derivative_eq_intros | simp)+  have h2: "(sqrt has_real_derivative inverse (sqrt (u\<^sup>2 - 4)) / 2) (at (u\<^sup>2 - 4))"    by (rule DERIV_real_sqrt[OF pos])  have h3: "((\<lambda>x. sqrt (x\<^sup>2 - 4)) has_real_derivative inverse (sqrt (u\<^sup>2 - 4)) / 2 * (2 * u)) (at u)"    by (rule DERIV_chain2[where f=sqrt and g="\<lambda>x::real. x\<^sup>2 - 4", OF h2 h1])  have "inverse (sqrt (u\<^sup>2 - 4)) / 2 * (2 * u) = u / sqrt (u\<^sup>2 - 4)"    by (simp add: field_simps)  with h3 show ?thesis by simpqed lemma Hh_derivative:  fixes u :: real  assumes "2 < u"  shows "(Hh has_real_derivative sqrt (u\<^sup>2 - 4) / u) (at u)"proof -  define r where "r = sqrt (u\<^sup>2 - 4)"  have pos: "0 < u\<^sup>2 - 4" by (rule sq_minus4_pos[OF assms])  have r0: "0 < r" using pos by (simp add: r_def)  have r2: "r\<^sup>2 = u\<^sup>2 - 4" unfolding r_def by (rule real_sqrt_pow2) (use pos in simp)  have u0: "0 < u" using assms by simp  have hr: "((\<lambda>x. sqrt (x\<^sup>2 - 4)) has_real_derivative u / r) (at u)"    using sqrt_deriv[OF assms] by (simp add: r_def)  have hr2: "((\<lambda>x. sqrt (x\<^sup>2 - 4) / 2) has_real_derivative u / r / 2) (at u)"    by (rule DERIV_cdivide[OF hr])  have ha: "(arctan has_real_derivative inverse (1 + (sqrt (u\<^sup>2 - 4) / 2)\<^sup>2)) (at (sqrt (u\<^sup>2 - 4) / 2))"    by (rule DERIV_arctan)  have hb: "((\<lambda>x. arctan (sqrt (x\<^sup>2 - 4) / 2)) has_real_derivative      inverse (1 + (sqrt (u\<^sup>2 - 4) / 2)\<^sup>2) * (u / r / 2)) (at u)"    by (rule DERIV_chain2[where f=arctan and g="\<lambda>x. sqrt (x\<^sup>2 - 4) / 2", OF ha hr2])  have hc: "(Hh has_real_derivative      0 - 2 * (inverse (1 + (sqrt (u\<^sup>2 - 4) / 2)\<^sup>2) * (u / r / 2)) + u / r) (at u)"    unfolding Hh_def    by (rule DERIV_add[OF DERIV_diff[OF DERIV_const DERIV_cmult[OF hb]] hr])  have hc2: "(Hh has_real_derivative      0 - 2 * (inverse (1 + (r / 2)\<^sup>2) * (u / r / 2)) + u / r) (at u)"    using hc by (simp add: r_def)  have e: "1 + (r / 2)\<^sup>2 = u\<^sup>2 / 4"  proof -    have "(r / 2)\<^sup>2 = r\<^sup>2 / 4" by (simp add: power_divide)    then show ?thesis using r2 by linarith  qed  have nu: "u \<noteq> 0" using u0 by simp  have nr: "r \<noteq> 0" using r0 by simp  have s1: "0 - 2 * (inverse (1 + (r / 2)\<^sup>2) * (u / r / 2)) + u / r = (u\<^sup>2 - 4) / (u * r)"    unfolding e    by ((simp add: inverse_divide field_simps nu nr; fail)      | (simp add: inverse_divide divide_simps nu nr power2_eq_square algebra_simps; fail)      | (simp add: inverse_divide divide_simps nu nr; algebra))  have s2: "(u\<^sup>2 - 4) / (u * r) = r / u"    unfolding r2[symmetric]    by ((simp add: power2_eq_square nu nr; fail)      | (simp add: power2_eq_square divide_simps nu nr; fail)      | (simp add: power2_eq_square divide_simps nu nr algebra_simps; fail))  have "0 - 2 * (inverse (1 + (r / 2)\<^sup>2) * (u / r / 2)) + u / r = r / u" using s1 s2 by simp  with hc2 show ?thesis by (simp add: r_def)qed lemma Lcsc_eq_Hh:  fixes u :: real  assumes "2 < u"  shows "Lcsc u = Hh u"proof -  have pos: "0 < u\<^sup>2 - 4" by (rule sq_minus4_pos[OF assms])  define r where "r = sqrt (u\<^sup>2 - 4)"  have r0: "0 < r" using pos by (simp add: r_def)  have "arctan (2 / r) = pi / 2 - arctan (r / 2)"  proof -    have "arctan (inverse (r / 2)) = pi / 2 - arctan (r / 2)"      using r0 by (intro arctan_inverse) auto    moreover have "inverse (r / 2) = 2 / r" by (simp add: inverse_eq_divide)    ultimately show ?thesis by simp  qed  then show ?thesis by (simp add: Lcsc_def Hh_def r_def)qed theorem csc_derivative:  fixes u :: real  assumes "2 < u"  shows "(Lcsc has_real_derivative sqrt (u\<^sup>2 - 4) / u) (at u)"proof -  have ev: "eventually (\<lambda>x. Hh x = Lcsc x) (nhds u)"    unfolding eventually_nhds    by (rule exI[of _ "{2<..}"]) (use assms Lcsc_eq_Hh in auto)  show ?thesis    by (rule iffD1[OF DERIV_cong_ev[OF refl ev refl] Hh_derivative[OF assms]])qed section \<open>C. The closed form at the optimum\<close> lemma arctan_arccos:  fixes k :: real  assumes "0 < k" and "k < 1"  shows "arctan (sqrt (1 - k\<^sup>2) / k) = arccos k"proof -  define x where "x = arccos k"  have c: "cos x = k" using assms by (simp add: x_def cos_arccos)  have s: "sin x = sqrt (1 - k\<^sup>2)" using assms by (simp add: x_def sin_arccos)  have x0: "0 \<le> x" unfolding x_def by (rule arccos_lbound) (use assms in auto)  have x1: "x < pi / 2"  proof (rule ccontr)    assume "\<not> x < pi / 2"    then have hx: "pi / 2 \<le> x" by simp    have hp: "x \<le> pi" unfolding x_def by (rule arccos_ubound) (use assms in auto)    define y where "y = x - pi / 2"    have y0: "0 \<le> y" using hx unfolding y_def by linarith    have y1: "y \<le> pi" using hp pi_gt_zero unfolding y_def by linarith    have e1: "cos x = cos (y + pi / 2)" by (simp add: y_def)    have e2: "cos (y + pi / 2) = - sin y" by (simp add: cos_add)    have sy: "0 \<le> sin y" by (rule sin_ge_zero[OF y0]) (use y1 pi_gt_zero in linarith)    have "cos x \<le> 0" using e1 e2 sy by simp    with c assms show False by simp  qed  have "tan x = sqrt (1 - k\<^sup>2) / k" by (simp add: tan_def c s)  moreover have "arctan (tan x) = x"    using x0 x1 pi_gt_zero by (intro arctan_tan) auto  ultimately show ?thesis by (simp add: x_def)qed lemma ustar_facts:  fixes a b :: real  assumes "b < a" and "0 < b"  shows "2 < (a + b) / sqrt (a * b)"    and "sqrt (((a + b) / sqrt (a * b))\<^sup>2 - 4) = (a - b) / sqrt (a * b)"proof -  define s where "s = sqrt (a * b)"  have a0: "0 < a" using assms by simp  have ab: "0 < a * b" using a0 assms by simp  have s0: "0 < s" using ab by (simp add: s_def)  have s2: "s\<^sup>2 = a * b" unfolding s_def by (rule real_sqrt_pow2) (use ab in simp)  have sne: "s\<^sup>2 \<noteq> 0" using s0 by simp  have e1: "(a + b)\<^sup>2 = (a - b)\<^sup>2 + 4 * s\<^sup>2"  proof -    have "(a + b)\<^sup>2 = (a - b)\<^sup>2 + 4 * (a * b)" by (simp add: power2_eq_square algebra_simps)    then show ?thesis using s2 by simp  qed  have e4: "4 * s\<^sup>2 / s\<^sup>2 = 4" using sne by (rule nonzero_mult_div_cancel_right)  have key: "((a + b) / s)\<^sup>2 - 4 = ((a - b) / s)\<^sup>2"  proof -    have "((a + b) / s)\<^sup>2 = ((a - b)\<^sup>2 + 4 * s\<^sup>2) / s\<^sup>2" by (simp add: power_divide e1)    also have "\<dots> = ((a - b) / s)\<^sup>2 + 4" by (simp only: add_divide_distrib e4 power_divide)    finally show ?thesis by simp  qed  have pos: "0 < ((a - b) / s)\<^sup>2"  proof -    have "0 < (a - b) / s" using assms s0 by (intro divide_pos_pos) auto    then show ?thesis by (rule zero_less_power)  qed  show "sqrt (((a + b) / sqrt (a * b))\<^sup>2 - 4) = (a - b) / sqrt (a * b)"    unfolding s_def[symmetric] using key assms s0 by (simp add: real_sqrt_unique)  have "2 < (a + b) / s"  proof (rule ccontr)    assume "\<not> 2 < (a + b) / s"    then have "(a + b) / s \<le> 2" by simp    moreover have "0 \<le> (a + b) / s" using a0 assms s0 by simp    ultimately have "((a + b) / s)\<^sup>2 \<le> 2\<^sup>2" by (intro power_mono) auto    then have "((a + b) / s)\<^sup>2 \<le> 4" by simp    with key pos show False by linarith  qed  then show "2 < (a + b) / sqrt (a * b)" by (simp add: s_def)qed theorem closed_form_value:  fixes a b :: real  assumes "b < a" and "0 < b"  shows "sqrt (((a + b) / sqrt (a * b))\<^sup>2 - 4) = (a - b) / sqrt (a * b)"    and "cost a b ((a + b) / sqrt (a * b)) = (a + b) * arccos ((a - b) / (a + b))"proof -  show "sqrt (((a + b) / sqrt (a * b))\<^sup>2 - 4) = (a - b) / sqrt (a * b)"    by (rule ustar_facts(2)[OF assms])  define s where "s = sqrt (a * b)"  define r where "r = (a - b) / s"  define us where "us = (a + b) / s"  define k where "k = (a - b) / (a + b)"  have a0: "0 < a" using assms by simp  have ab: "0 < a * b" using a0 assms by simp  have s0: "0 < s" using ab by (simp add: s_def)  have s2: "s\<^sup>2 = a * b" unfolding s_def by (rule real_sqrt_pow2) (use ab in simp)  have us2: "2 < us" using ustar_facts(1)[OF assms] by (simp add: us_def s_def)  have rr: "sqrt (us\<^sup>2 - 4) = r" using ustar_facts(2)[OF assms] by (simp add: us_def r_def s_def)  have k0: "0 < k" using assms by (simp add: k_def)  have k1: "k < 1" using assms by (simp add: k_def divide_less_eq)  have r0: "0 < r" using assms s0 by (simp add: r_def)  have ne: "a + b \<noteq> 0" using a0 assms by simp  have ne2: "(a + b)\<^sup>2 \<noteq> 0" using ne by simp  have sq1: "(2 * s / (a + b))\<^sup>2 = 4 * (a * b) / (a + b)\<^sup>2"    by (simp add: power_divide power_mult_distrib s2)  have sq3: "(a + b)\<^sup>2 - (a - b)\<^sup>2 = 4 * (a * b)"    by (simp add: power2_eq_square algebra_simps)  have sq2: "1 - k\<^sup>2 = 4 * (a * b) / (a + b)\<^sup>2"  proof -    have "1 - k\<^sup>2 = ((a + b)\<^sup>2 - (a - b)\<^sup>2) / (a + b)\<^sup>2"      by (simp only: k_def power_divide) (simp add: diff_divide_distrib ne ne2)    then show ?thesis using sq3 by simp  qed  have sq: "sqrt (1 - k\<^sup>2) = 2 * s / (a + b)"  proof (rule real_sqrt_unique)    show "(2 * s / (a + b))\<^sup>2 = 1 - k\<^sup>2" using sq1 sq2 by simp    show "0 \<le> 2 * s / (a + b)" using a0 assms s0 by simp  qed  have nab: "a - b \<noteq> 0" using assms by simp  have ratio: "2 / r = sqrt (1 - k\<^sup>2) / k"  proof -    have "sqrt (1 - k\<^sup>2) / k = (2 * s / (a + b)) / k" by (simp only: sq)    also have "\<dots> = 2 * s / (a - b)" unfolding k_def      by ((simp add: field_simps ne nab; fail)        | (simp add: divide_simps ne nab; fail)        | (simp add: divide_simps ne nab algebra_simps; fail))    also have "\<dots> = 2 / r" unfolding r_def      by ((simp add: field_simps nab s0; fail)        | (simp add: divide_simps nab; fail))    finally show ?thesis by simp  qed  have "cost a b us = ((a + b) * Lcsc us - (a - b) * us) / 2 - (a + b) * pi / 2"    using us2 by (simp add: cost_def Lmin_def)  also have "\<dots> = (a + b) * arctan (2 / r) + ((a + b) * r - (a - b) * us) / 2"    by ((simp add: Lcsc_def rr algebra_simps field_simps; fail) | (simp add: Lcsc_def rr; algebra))  also have "(a + b) * r - (a - b) * us = 0"    using s0 by (simp add: r_def us_def field_simps)  also have "arctan (2 / r) = arccos k"    using ratio arctan_arccos[OF k0 k1] by simp  finally show "cost a b ((a + b) / sqrt (a * b)) = (a + b) * arccos ((a - b) / (a + b))"    by (simp add: us_def s_def k_def)qed section \<open>D. The minimum on the CSC side\<close> lemma Lmin_two: "Lmin 2 = 2 * pi"proof -  define y where "y = sin (pi / 4)"  have y0: "0 < y" unfolding y_def by (rule sin_gt_zero) (use pi_gt_zero in auto)  have e: "sin (pi / 4) = cos (pi / 4)"  proof -    have "pi / 2 - pi / 4 = pi / 4" by simp    then show ?thesis using sin_cos_eq[of "pi / 4"] by simp  qed  have "y\<^sup>2 + y\<^sup>2 = 1"    using sin_cos_squared_add[of "pi / 4"] e by (simp add: y_def)  then have y2: "y\<^sup>2 = 1 / 2" by simp  have "sqrt (4 + 2\<^sup>2) = 4 * y"  proof (rule real_sqrt_unique)    show "(4 * y)\<^sup>2 = 4 + 2\<^sup>2" using y2 by (simp add: power_mult_distrib)    show "0 \<le> 4 * y" using y0 by simp  qed  then have "arcsin (sqrt (4 + 2\<^sup>2) / 4) = pi / 4"    using y_def pi_gt_zero by (simp add: arcsin_sin)  then show ?thesis by (simp add: Lmin_def Lccc_def)qed lemma Lmin_Hh:  fixes u :: real  assumes "2 \<le> u"  shows "Lmin u = Hh u"proof (cases "u = 2")  case True  then show ?thesis by (simp add: Lmin_two Hh_def)next  case False  with assms have "2 < u" by simp  then show ?thesis by (simp add: Lmin_def Lcsc_eq_Hh)qed definition gcost :: "real \<Rightarrow> real \<Rightarrow> real \<Rightarrow> real" where  "gcost a b u = ((a + b) * Hh u - (a - b) * u) / 2 - (a + b) * pi / 2" lemma cost_gcost:  fixes u :: real  assumes "2 \<le> u"  shows "cost a b u = gcost a b u"  using assms by (simp add: cost_def gcost_def Lmin_Hh) lemma isCont_Hh: "isCont Hh (x::real)"  unfolding Hh_def by (intro continuous_intros; simp) lemma gcost_derivative:  fixes a b u :: real  assumes "2 < u"  shows "(gcost a b has_real_derivative ((a + b) * (sqrt (u\<^sup>2 - 4) / u) - (a - b)) / 2) (at u)"proof -  have "(gcost a b has_real_derivative      ((a + b) * (sqrt (u\<^sup>2 - 4) / u) - (a - b) * 1) / 2 - 0) (at u)"    unfolding gcost_def    by (rule DERIV_diff[OF DERIV_cdivide[OF DERIV_diff[OF DERIV_cmult[OF Hh_derivative[OF assms]]        DERIV_cmult[OF DERIV_ident]]] DERIV_const])  then show ?thesis by simpqed text \<open>Mean value theorem on @{text "[c, d]"} with @{text "2 \<le> c < d"}.\<close> lemma gcost_mvt:  fixes a b c d :: real  assumes "2 \<le> c" and "c < d"  shows "\<exists>z. c < z \<and> z < d \<and>    gcost a b d - gcost a b c = (d - c) * (((a + b) * (sqrt (z\<^sup>2 - 4) / z) - (a - b)) / 2)"proof -  have cont: "\<forall>x. c \<le> x \<and> x \<le> d \<longrightarrow> isCont (gcost a b) x"    unfolding gcost_def by (auto intro!: continuous_intros isCont_Hh)  have cont2: "continuous_on {c..d} (gcost a b)"    by (rule continuous_at_imp_continuous_on) (use cont in auto)  have dif: "\<And>x. c < x \<Longrightarrow> x < d \<Longrightarrow> gcost a b differentiable (at x)"  proof -    fix x assume "c < x" "x < d"    then have "2 < x" using assms by simp    from gcost_derivative[OF this] show "gcost a b differentiable (at x)"      by (auto simp: real_differentiable_def)  qed  from MVT[OF assms(2) cont2 dif]  obtain l z where z: "c < z" "z < d" and dz: "DERIV (gcost a b) z :> l"      and eq: "gcost a b d - gcost a b c = (d - c) * l" by blast  have "2 < z" using z assms by simp  from DERIV_unique[OF dz gcost_derivative[OF this]] eq z  show ?thesis by autoqed lemma slope_sign:  fixes a b z :: real  assumes "b < a" and "0 < b" and "2 < z"  shows "z \<le> (a + b) / sqrt (a * b) \<Longrightarrow> (a + b) * (sqrt (z\<^sup>2 - 4) / z) - (a - b) \<le> 0"    and "(a + b) / sqrt (a * b) \<le> z \<Longrightarrow> 0 \<le> (a + b) * (sqrt (z\<^sup>2 - 4) / z) - (a - b)"proof -  define s where "s = sqrt (a * b)"  define r where "r = sqrt (z\<^sup>2 - 4)"  have a0: "0 < a" using assms by simp  have ab: "0 < a * b" using a0 assms by simp  have s0: "0 < s" using ab by (simp add: s_def)  have s2: "s\<^sup>2 = a * b" unfolding s_def by (rule real_sqrt_pow2) (use ab in simp)  have pos: "0 < z\<^sup>2 - 4" by (rule sq_minus4_pos[OF assms(3)])  have r0: "0 < r" using pos by (simp add: r_def)  have r2: "r\<^sup>2 = z\<^sup>2 - 4" unfolding r_def by (rule real_sqrt_pow2) (use pos in simp)  have z0: "0 < z" using assms by simp  have diff: "((a - b) * z)\<^sup>2 - ((a + b) * r)\<^sup>2 = 4 * (a + b)\<^sup>2 - 4 * (a * b) * z\<^sup>2"  proof -    have "((a - b) * z)\<^sup>2 - ((a + b) * r)\<^sup>2 = (a - b)\<^sup>2 * z\<^sup>2 - (a + b)\<^sup>2 * r\<^sup>2"      by (simp add: power_mult_distrib)    also have "\<dots> = (a - b)\<^sup>2 * z\<^sup>2 - (a + b)\<^sup>2 * (z\<^sup>2 - 4)" by (simp add: r2)    also have "\<dots> = 4 * (a + b)\<^sup>2 - 4 * (a * b) * z\<^sup>2" by (simp add: power2_eq_square algebra_simps)    finally show ?thesis .  qed  have eqn: "(a + b) * (r / z) - (a - b) = ((a + b) * r - (a - b) * z) / z"    using z0 by (simp add: field_simps)  have ab1: "0 < a + b" using a0 assms by simp  have ab2: "0 < a - b" using assms by simp  show "z \<le> (a + b) / s \<Longrightarrow> (a + b) * (r / z) - (a - b) \<le> 0"  proof -    assume h: "z \<le> (a + b) / s"    then have "z * s \<le> a + b" using s0 by (simp add: pos_le_divide_eq)    then have "(z * s)\<^sup>2 \<le> (a + b)\<^sup>2" using z0 s0 by (intro power_mono) auto    then have "(a * b) * z\<^sup>2 \<le> (a + b)\<^sup>2" by (simp add: power_mult_distrib s2 algebra_simps)    with diff have "((a + b) * r)\<^sup>2 \<le> ((a - b) * z)\<^sup>2" by simp    then have "(a + b) * r \<le> (a - b) * z"    proof (rule power2_le_imp_le)      show "0 \<le> (a - b) * z" using ab2 z0 by (rule mult_nonneg_nonneg[OF less_imp_le less_imp_le])    qed    then have "(a + b) * r - (a - b) * z \<le> 0" by simp    then show ?thesis unfolding eqn by (rule divide_nonpos_pos[OF _ z0])  qed  show "(a + b) / s \<le> z \<Longrightarrow> 0 \<le> (a + b) * (r / z) - (a - b)"  proof -    assume h: "(a + b) / s \<le> z"    then have "a + b \<le> z * s" using s0 by (simp add: divide_le_eq)    then have "(a + b)\<^sup>2 \<le> (z * s)\<^sup>2" using ab1 by (intro power_mono) auto    then have "(a + b)\<^sup>2 \<le> (a * b) * z\<^sup>2" by (simp add: power_mult_distrib s2 algebra_simps)    with diff have "((a - b) * z)\<^sup>2 \<le> ((a + b) * r)\<^sup>2" by simp    then have "(a - b) * z \<le> (a + b) * r"    proof (rule power2_le_imp_le)      show "0 \<le> (a + b) * r" using ab1 r0 by (rule mult_nonneg_nonneg[OF less_imp_le less_imp_le])    qed    then have "0 \<le> (a + b) * r - (a - b) * z" by simp    then show ?thesis unfolding eqn by (rule divide_nonneg_pos[OF _ z0])  qedqed theorem csc_minimum:  fixes a b u :: real  assumes "b < a" and "0 < b" and "2 \<le> u"  shows "(a + b) * arccos ((a - b) / (a + b)) \<le> cost a b u"proof -  define us where "us = (a + b) / sqrt (a * b)"  have us2: "2 < us" using ustar_facts(1)[OF assms(1,2)] by (simp add: us_def)  have val: "gcost a b us = (a + b) * arccos ((a - b) / (a + b))"    using closed_form_value(2)[OF assms(1,2)] cost_gcost[where a=a and b=b and u=us, OF less_imp_le[OF us2]]    by (simp add: us_def)  have "(a + b) * arccos ((a - b) / (a + b)) \<le> gcost a b u"  proof (cases "u \<le> us")    case True    show ?thesis    proof (cases "u = us")      case True      then show ?thesis using val by simp    next      case False      with \<open>u \<le> us\<close> have lt: "u < us" by simp      obtain z where z: "u < z" "z < us"          and eq: "gcost a b us - gcost a b u = (us - u) * (((a + b) * (sqrt (z\<^sup>2 - 4) / z) - (a - b)) / 2)"        using gcost_mvt[OF assms(3) lt] by blast      have z2: "2 < z" using z assms(3) by simp      have "(a + b) * (sqrt (z\<^sup>2 - 4) / z) - (a - b) \<le> 0"        using slope_sign(1)[OF assms(1,2) z2] z us_def by simp      then have "(us - u) * (((a + b) * (sqrt (z\<^sup>2 - 4) / z) - (a - b)) / 2) \<le> 0"        using lt by (intro mult_nonneg_nonpos) auto      with eq val show ?thesis by simp    qed  next    case False    then have lt: "us < u" by simp    obtain z where z: "us < z" "z < u"        and eq: "gcost a b u - gcost a b us = (u - us) * (((a + b) * (sqrt (z\<^sup>2 - 4) / z) - (a - b)) / 2)"      using gcost_mvt[where a=a and b=b and c=us and d=u, OF less_imp_le[OF us2] lt] by auto    have z2: "2 < z" using z us2 by simp    have "0 \<le> (a + b) * (sqrt (z\<^sup>2 - 4) / z) - (a - b)"      using slope_sign(2)[OF assms(1,2) z2] z us_def by simp    then have "0 \<le> (u - us) * (((a + b) * (sqrt (z\<^sup>2 - 4) / z) - (a - b)) / 2)"      using lt by (intro mult_nonneg_nonneg) auto    with eq val show ?thesis by simp  qed  then show ?thesis using cost_gcost[OF assms(3)] by simpqed section \<open>E. The CCC branch\<close> lemma ccc_alg:  fixes u :: real  assumes "0 \<le> u" and "u \<le> 2"  shows "16 * u\<^sup>2 \<le> (12 - u\<^sup>2) * (4 + u\<^sup>2)"proof -  have u4: "u\<^sup>2 \<le> 2\<^sup>2" using assms by (intro power_mono) auto  have "(12 - u\<^sup>2) * (4 + u\<^sup>2) - 16 * u\<^sup>2 = (12 + u\<^sup>2) * (4 - u\<^sup>2)"    by (simp add: power2_eq_square algebra_simps)  moreover have "0 \<le> (12 + u\<^sup>2) * (4 - u\<^sup>2)" using u4 by (intro mult_nonneg_nonneg) auto  ultimately show ?thesis by simpqed theorem ccc_slope:  fixes u :: real  assumes "0 \<le> u" and "u \<le> 2"  shows "(Lccc has_real_derivative - 4 * u / sqrt ((12 - u\<^sup>2) * (4 + u\<^sup>2))) (at u)"    and "\<bar>- 4 * u / sqrt ((12 - u\<^sup>2) * (4 + u\<^sup>2))\<bar> \<le> 1"    and "- 4 * u / sqrt ((12 - u\<^sup>2) * (4 + u\<^sup>2)) \<le> 0"proof -  define s where "s = sqrt (4 + u\<^sup>2)"  define t where "t = sqrt (1 - (s / 4)\<^sup>2)"  define q where "q = sqrt ((12 - u\<^sup>2) * (4 + u\<^sup>2))"  have u4: "u\<^sup>2 \<le> 2\<^sup>2" using assms by (intro power_mono) auto  have p4: "0 < 4 + u\<^sup>2" by (rule add_pos_nonneg) simp_all  have s0: "0 < s" using p4 by (simp add: s_def)  have s2: "s\<^sup>2 = 4 + u\<^sup>2" unfolding s_def by (rule real_sqrt_pow2) (use p4 in simp)  have s4: "s < 4"  proof (rule ccontr)    assume "\<not> s < 4"    then have "4\<^sup>2 \<le> s\<^sup>2" by (intro power_mono) auto    with s2 u4 show False by simp  qed  have t2a: "1 - (s / 4)\<^sup>2 = (12 - u\<^sup>2) / 16" by (simp add: power_divide s2 field_simps)  have t0: "0 < 1 - (s / 4)\<^sup>2" using t2a u4 by simp  have tt: "0 < t" using t0 by (simp add: t_def)  have t2: "t\<^sup>2 = (12 - u\<^sup>2) / 16"  proof -    have "t\<^sup>2 = 1 - (s / 4)\<^sup>2" unfolding t_def by (rule real_sqrt_pow2) (use t0 in simp)    then show ?thesis using t2a by simp  qed  have q4: "q = 4 * s * t"    unfolding q_def  proof (rule real_sqrt_unique)    show "(4 * s * t)\<^sup>2 = (12 - u\<^sup>2) * (4 + u\<^sup>2)"      by (simp add: power_mult_distrib s2 t2)    show "0 \<le> 4 * s * t" using s0 tt by simp  qed  have q0: "0 < q" using q4 s0 tt by simp  have h2: "(sqrt has_real_derivative inverse (sqrt (4 + u\<^sup>2)) / 2) (at (4 + u\<^sup>2))"    by (rule DERIV_real_sqrt[OF p4])  have h1: "((\<lambda>x::real. 4 + x\<^sup>2) has_real_derivative 2 * u) (at u)"    by (rule derivative_eq_intros | simp)+  have h3: "((\<lambda>x. sqrt (4 + x\<^sup>2)) has_real_derivative inverse (sqrt (4 + u\<^sup>2)) / 2 * (2 * u)) (at u)"    by (rule DERIV_chain2[where f=sqrt and g="\<lambda>x::real. 4 + x\<^sup>2", OF h2 h1])  have h4: "((\<lambda>x. sqrt (4 + x\<^sup>2) / 4) has_real_derivative inverse (sqrt (4 + u\<^sup>2)) / 2 * (2 * u) / 4) (at u)"    by (rule DERIV_cdivide[OF h3])  have h5: "(arcsin has_real_derivative inverse (sqrt (1 - (sqrt (4 + u\<^sup>2) / 4)\<^sup>2))) (at (sqrt (4 + u\<^sup>2) / 4))"    by (rule DERIV_arcsin) (use s0 s4 s_def in linarith)+  have h6: "((\<lambda>x. arcsin (sqrt (4 + x\<^sup>2) / 4)) has_real_derivative      inverse (sqrt (1 - (sqrt (4 + u\<^sup>2) / 4)\<^sup>2)) * (inverse (sqrt (4 + u\<^sup>2)) / 2 * (2 * u) / 4)) (at u)"    by (rule DERIV_chain2[where f=arcsin and g="\<lambda>x. sqrt (4 + x\<^sup>2) / 4", OF h5 h4])  have h7: "(Lccc has_real_derivative 0 - 4 * (inverse (sqrt (1 - (sqrt (4 + u\<^sup>2) / 4)\<^sup>2)) *      (inverse (sqrt (4 + u\<^sup>2)) / 2 * (2 * u) / 4))) (at u)"    unfolding Lccc_def by (rule DERIV_diff[OF DERIV_const DERIV_cmult[OF h6]])  have val: "0 - 4 * (inverse (sqrt (1 - (sqrt (4 + u\<^sup>2) / 4)\<^sup>2)) *      (inverse (sqrt (4 + u\<^sup>2)) / 2 * (2 * u) / 4)) = - 4 * u / q"  proof -    have f: "0 - 4 * (inverse (sqrt (1 - (sqrt (4 + u\<^sup>2) / 4)\<^sup>2)) *        (inverse (sqrt (4 + u\<^sup>2)) / 2 * (2 * u) / 4)) = 0 - 4 * (inverse t * (inverse s / 2 * (2 * u) / 4))"      by (simp only: s_def[symmetric] t_def[symmetric])    have ns: "s \<noteq> 0" using s0 by simp    have nt: "t \<noteq> 0" using tt by simp    have g: "0 - 4 * (inverse t * (inverse s / 2 * (2 * u) / 4)) = - 4 * u / (4 * s * t)"      by ((simp add: field_simps ns nt; fail)        | (simp add: divide_simps ns nt algebra_simps; fail)        | (simp add: divide_simps ns nt; algebra))    have h: "- 4 * u / (4 * s * t) = - 4 * u / q" by (simp only: q4)    show ?thesis by (rule trans[OF f trans[OF g h]])  qed  show "(Lccc has_real_derivative - 4 * u / q) (at u)"    using h7 val by (simp add: q_def)  have u0: "0 \<le> 4 * u / q" using assms q0 by simp  show "- 4 * u / q \<le> 0" using u0 by (simp add: divide_nonpos_pos assms q0)  have "4 * u \<le> q"  proof (rule power2_le_imp_le)    show "(4 * u)\<^sup>2 \<le> q\<^sup>2" using ccc_alg[OF assms] q0      by (simp add: q_def power_mult_distrib power2_eq_square)    show "0 \<le> q" using q0 by simp  qed  then have "4 * u / q \<le> 1" using q0 by (simp add: divide_le_eq)  then show "\<bar>- 4 * u / q\<bar> \<le> 1" using u0 by (simp add: abs_of_nonpos divide_nonneg_pos)qed lemma Lccc_two: "Lccc 2 = 2 * pi"  using Lmin_two by (simp add: Lmin_def) lemma Lccc_antitone:  fixes u :: real  assumes "0 \<le> u" and "u \<le> 2"  shows "Lccc 2 \<le> Lccc u"proof (rule DERIV_nonpos_imp_nonincreasing[OF assms(2)])  fix x :: real assume x: "u \<le> x" "x \<le> 2"  then have "0 \<le> x" using assms by simp  from ccc_slope[OF this x(2)] show "\<exists>y. DERIV Lccc x :> y \<and> y \<le> 0" by blastqed lemma cost_two:  fixes a b :: real  shows "cost a b 2 = (a + b) * pi / 2 - (a - b)"  unfolding cost_def Lmin_two  by ((simp add: algebra_simps field_simps; fail) | algebra) theorem ccc_branch:  fixes a b u :: real  assumes "0 \<le> b" and "b \<le> a" and "0 \<le> u" and "u \<le> 2"  shows "cost a b 2 \<le> cost a b u" and "cost a b 2 = (a + b) * pi / 2 - (a - b)"proof -  show "cost a b 2 = (a + b) * pi / 2 - (a - b)" by (rule cost_two)  have ab: "0 \<le> a + b" using assms by simp  have l: "Lccc 2 \<le> Lccc u" by (rule Lccc_antitone[OF assms(3,4)])  have m1: "0 \<le> (a + b) * (Lccc u - Lccc 2)" using ab l by (intro mult_nonneg_nonneg) auto  have m2: "0 \<le> (a - b) * (2 - u)" using assms by (intro mult_nonneg_nonneg) auto  have c1: "cost a b u = ((a + b) * Lccc u - (a - b) * u) / 2 - (a + b) * pi / 2"    using assms by (simp add: cost_def Lmin_def)  have c2: "cost a b 2 = ((a + b) * Lccc 2 - (a - b) * 2) / 2 - (a + b) * pi / 2"    by (simp add: cost_def Lmin_def)  have "cost a b u - cost a b 2 = ((a + b) * (Lccc u - Lccc 2) + (a - b) * (2 - u)) / 2"    unfolding c1 c2 by ((simp add: algebra_simps field_simps; fail) | algebra)  moreover have "0 \<le> ((a + b) * (Lccc u - Lccc 2) + (a - b) * (2 - u)) / 2"    using m1 m2 by simp  ultimately show "cost a b 2 \<le> cost a b u" by linarithqed section \<open>F. Equal rates and the total minimum\<close> theorem equal_rates:  fixes a u :: real  assumes "0 < a" and "0 \<le> u"  shows "pi * a \<le> cost a a u"    and "cost a a 2 = pi * a"    and "(a + a) * arccos ((a - a) / (a + a)) = pi * a"proof -  have c2: "cost a a 2 = pi * a" using cost_two[where a=a and b=a] by (simp add: algebra_simps)  show "cost a a 2 = pi * a" by (rule c2)  show "(a + a) * arccos ((a - a) / (a + a)) = pi * a" by (simp add: arccos_0)  show "pi * a \<le> cost a a u"  proof (cases "u \<le> 2")    case True    have "cost a a 2 \<le> cost a a u" by (rule ccc_branch(1)) (use assms True in auto)    then show ?thesis using c2 by simp  next    case False    then have u2: "2 < u" by simp    obtain z where z: "2 < z" "z < u"        and eq: "gcost a a u - gcost a a 2 = (u - 2) * (((a + a) * (sqrt (z\<^sup>2 - 4) / z) - (a - a)) / 2)"      using gcost_mvt[where a=a and b=a and c=2 and d=u, OF order_refl u2] by auto    have pz: "0 < z\<^sup>2 - 4" by (rule sq_minus4_pos[OF z(1)])    have q0: "0 \<le> sqrt (z\<^sup>2 - 4) / z"      by (rule divide_nonneg_pos[OF real_sqrt_ge_zero[OF less_imp_le[OF pz]]]) (use z in linarith)    have "0 \<le> (a + a) * (sqrt (z\<^sup>2 - 4) / z)" using assms q0 by (intro mult_nonneg_nonneg) auto    then have "0 \<le> (u - 2) * (((a + a) * (sqrt (z\<^sup>2 - 4) / z) - (a - a)) / 2)"      using z by (intro mult_nonneg_nonneg) auto    with eq have g1: "gcost a a 2 \<le> gcost a a u" by simp    have g2: "gcost a a 2 = pi * a" using cost_gcost[where a=a and b=a and u=2] c2 by simp    have g3: "cost a a u = gcost a a u" by (rule cost_gcost[OF less_imp_le[OF u2]])    show ?thesis using g1 g2 g3 by simp  qedqed theorem total_minimum:  fixes a b u :: real  assumes "b < a" and "0 < b" and "0 \<le> u"  shows "(a + b) * arccos ((a - b) / (a + b)) \<le> cost a b u"    and "cost a b ((a + b) / sqrt (a * b)) = (a + b) * arccos ((a - b) / (a + b))"proof -  show "cost a b ((a + b) / sqrt (a * b)) = (a + b) * arccos ((a - b) / (a + b))"    by (rule closed_form_value(2)[OF assms(1,2)])  show "(a + b) * arccos ((a - b) / (a + b)) \<le> cost a b u"  proof (cases "2 \<le> u")    case True    then show ?thesis by (rule csc_minimum[OF assms(1,2)])  next    case False    then have u2: "u \<le> 2" by simp    have "(a + b) * arccos ((a - b) / (a + b)) \<le> cost a b 2"      by (rule csc_minimum[OF assms(1,2)]) simp    also have "\<dots> \<le> cost a b u" by (rule ccc_branch(1)) (use assms u2 in auto)    finally show ?thesis .  qedqed end