🏛️ Atlas✒️Isabelle.MemoryAccessFloors.Planar_Exposure_Bound view on GitHub ↗23 theorems
(*  Title:      Planar_Exposure_Bound.thy    Author:     Carles Marin    Copyright:  Carles Marin    License:    BSD-3-Clause     The planar exposure bound (Lemma "planar exposure bound" of the memory-floor note B, sec_robust.tex),    from the step that is elementary onwards.     What is formalised.  With z in [0,1), d = arccos z, a_z(phi) = phi - (1+z) tan(phi/2),    b_z(phi) = phi + (1-z) cot(phi/2) and, for the normalised exposures a, b of a pulse and    theta = (a+b)/2, the arc of type (1,0,-1)        x_3 = -2 sin(phi) - 2 (theta-phi) cos(phi),   y_3 = 2 cos(phi) - 2 (theta-phi) sin(phi):    - the exposures along the arc: a = phi - sin(phi) + (theta-phi)(1-cos phi), b = phi + sin(phi) + (theta-phi)(1+cos phi);    - steps (3) and (4) of the proof: from y_3 <= 2z get theta >= theta_z(phi) = phi + (cos phi - z)/sin phi, hence      a >= a_z(phi); a_z is strictly increasing, theta_z is non-increasing on (0,d]; so for beta = a_z^{-1}(a)      one has b >= b_z(beta)   (theorems planar_exposure_bound_inner and planar_exposure_bound);    - the statement about the range: a_z maps (0,d] into (0,d - sin d] (and onto it: Memory_Floors_Pieces.a_z_range);    - equality is attained by the arc with the non-negative wait (arc_attains);    - step (1): odd turns k >= 1 give exposures k*pi, larger than the bang-bang values d -+ sin d      (multi_turn_dominated; the integral inequality itself is Memory_Floors_Pieces.odd_turns_integral).     What is NOT formalised, and enters as a hypothesis (named in the theorem statements).  Step (2) of the proof is the    classification of the section of the reachable set of a planar Dubins car at heading pi by Patsko and Fedotov    (Lemma 3.1 and Theorem 11.1 of their paper), which is dynamics (extremal controls, Cases 1-3) and is an    external result.  Its consequence enters as the hypothesis "on the arc": every pulse in the strict sector    a < d - sin d lies above the point of the arc x_3, y_3 at the same x, with 0 < phi < d, i.e. a - b = x_3 and    y_3 <= 2z.  The case a = d - sin d needs only theta >= d, which is part (b) of the robust theorem of B    and is also a hypothesis.  The reduction of the pulse to a Dubins car (the Bloch direction on a meridian) is not    formalised either.  The symmetric statement (a and b exchanged) is the same theorem applied to the time-reversed    pulse and is not repeated.*)theory Planar_Exposure_Bound  imports Memory_Floors_Piecesbegin section \<open>The arc and the closed forms\<close> definition x3 :: "real \<Rightarrow> real \<Rightarrow> real" where  "x3 theta phi = - 2 * sin phi - 2 * (theta - phi) * cos phi" definition y3 :: "real \<Rightarrow> real \<Rightarrow> real" where  "y3 theta phi = 2 * cos phi - 2 * (theta - phi) * sin phi" definition theta_z :: "real \<Rightarrow> real \<Rightarrow> real" where  "theta_z z phi = phi + (cos phi - z) / sin phi" text \<open>Exposures along the arc: the points a = theta + x_3/2 and b = theta - x_3/2 (since a + b = 2 thetaand a - b = x_3) are the closed forms of the remark of B, with G w = theta - phi.\<close> theorem arc_exposures:  fixes theta phi :: real  shows "theta + x3 theta phi / 2 = phi - sin phi + (theta - phi) * (1 - cos phi)"    and "theta - x3 theta phi / 2 = phi + sin phi + (theta - phi) * (1 + cos phi)"  unfolding x3_def by (simp_all add: field_simps) lemma alg_a:  fixes s c z :: real  assumes s: "0 < s" and c: "0 < c" and e: "s\<^sup>2 + c\<^sup>2 = 1"  shows "- ((1 + z) * (s / c)) = - (2 * s * c) + ((c\<^sup>2 - s\<^sup>2 - z) / (2 * s * c)) * (1 - (c\<^sup>2 - s\<^sup>2))"proof -  have o: "1 - (c\<^sup>2 - s\<^sup>2) = 2 * s\<^sup>2" using e by linarith  have n: "(- (2 * s * c) * c + (c\<^sup>2 - s\<^sup>2 - z) * s) = - s * (c\<^sup>2 + s\<^sup>2) - z * s"    by (simp add: algebra_simps power2_eq_square)  have "- (2 * s * c) + ((c\<^sup>2 - s\<^sup>2 - z) / (2 * s * c)) * (2 * s\<^sup>2)        = (- (2 * s * c) * c + (c\<^sup>2 - s\<^sup>2 - z) * s) / c"    using s c by (simp add: field_simps power2_eq_square)  also have "\<dots> = (- s * (c\<^sup>2 + s\<^sup>2) - z * s) / c" using n by simp  also have "\<dots> = (- s - z * s) / c" using e by (simp add: add.commute)  also have "\<dots> = - ((1 + z) * (s / c))" using c by (simp add: field_simps)  finally show ?thesis unfolding o by simpqed lemma alg_b:  fixes s c z :: real  assumes s: "0 < s" and c: "0 < c" and e: "s\<^sup>2 + c\<^sup>2 = 1"  shows "(1 - z) * (c / s) = 2 * s * c + ((c\<^sup>2 - s\<^sup>2 - z) / (2 * s * c)) * (1 + (c\<^sup>2 - s\<^sup>2))"proof -  have o: "1 + (c\<^sup>2 - s\<^sup>2) = 2 * c\<^sup>2" using e by linarith  have n: "(2 * s * c * s + (c\<^sup>2 - s\<^sup>2 - z) * c) = c * (c\<^sup>2 + s\<^sup>2) - z * c"    by (simp add: algebra_simps power2_eq_square)  have "2 * s * c + ((c\<^sup>2 - s\<^sup>2 - z) / (2 * s * c)) * (2 * c\<^sup>2)        = (2 * s * c * s + (c\<^sup>2 - s\<^sup>2 - z) * c) / s"    using s c by (simp add: field_simps power2_eq_square)  also have "\<dots> = (c * (c\<^sup>2 + s\<^sup>2) - z * c) / s" using n by simp  also have "\<dots> = (c - z * c) / s" using e by (simp add: add.commute)  also have "\<dots> = (1 - z) * (c / s)" using s by (simp add: field_simps)  finally show ?thesis unfolding o by simpqed lemma half_angle_data:  fixes phi :: real  assumes "0 < phi" and "phi < pi"  shows "0 < sin (phi / 2)" and "0 < cos (phi / 2)"    and "sin phi = 2 * sin (phi / 2) * cos (phi / 2)"    and "cos phi = (cos (phi / 2))\<^sup>2 - (sin (phi / 2))\<^sup>2"    and "(sin (phi / 2))\<^sup>2 + (cos (phi / 2))\<^sup>2 = 1"proof -  show "0 < sin (phi / 2)" using assms by (intro sin_gt_zero) simp_all  show "0 < cos (phi / 2)" using assms by (intro cos_gt_zero_pi) simp_all  have "sin phi = sin (2 * (phi / 2))" by simp  then show "sin phi = 2 * sin (phi / 2) * cos (phi / 2)" by (simp only: sin_double)  have "cos phi = cos (2 * (phi / 2))" by simp  then show "cos phi = (cos (phi / 2))\<^sup>2 - (sin (phi / 2))\<^sup>2"    by (simp only: cos_double power2_eq_square)  show "(sin (phi / 2))\<^sup>2 + (cos (phi / 2))\<^sup>2 = 1" by simpqed theorem a_z_arc:  fixes z phi :: real  assumes "0 < phi" and "phi < pi"  shows "a_z z phi = phi - sin phi + (theta_z z phi - phi) * (1 - cos phi)"proof -  define s where "s = sin (phi / 2)"  define c where "c = cos (phi / 2)"  have sp: "0 < s" and cp: "0 < c" and sn: "sin phi = 2 * s * c"    and cs: "cos phi = c\<^sup>2 - s\<^sup>2" and e: "s\<^sup>2 + c\<^sup>2 = 1"    unfolding s_def c_def using half_angle_data[OF assms] by simp_all  have "tan (phi / 2) = s / c" unfolding s_def c_def tan_def by simp  then have "a_z z phi = phi - (1 + z) * (s / c)" unfolding a_z_def by simp  moreover have "phi - sin phi + (theta_z z phi - phi) * (1 - cos phi)                 = phi - (2 * s * c) + ((c\<^sup>2 - s\<^sup>2 - z) / (2 * s * c)) * (1 - (c\<^sup>2 - s\<^sup>2))"    unfolding theta_z_def sn cs by simp  ultimately show ?thesis using alg_a[OF sp cp e, of z] by simpqed theorem b_z_arc:  fixes z phi :: real  assumes "0 < phi" and "phi < pi"  shows "b_z z phi = phi + sin phi + (theta_z z phi - phi) * (1 + cos phi)"proof -  define s where "s = sin (phi / 2)"  define c where "c = cos (phi / 2)"  have sp: "0 < s" and cp: "0 < c" and sn: "sin phi = 2 * s * c"    and cs: "cos phi = c\<^sup>2 - s\<^sup>2" and e: "s\<^sup>2 + c\<^sup>2 = 1"    unfolding s_def c_def using half_angle_data[OF assms] by simp_all  have "cot (phi / 2) = c / s" unfolding s_def c_def cot_def by simp  then have "b_z z phi = phi + (1 - z) * (c / s)" unfolding b_z_def by simp  moreover have "phi + sin phi + (theta_z z phi - phi) * (1 + cos phi)                 = phi + (2 * s * c) + ((c\<^sup>2 - s\<^sup>2 - z) / (2 * s * c)) * (1 + (c\<^sup>2 - s\<^sup>2))"    unfolding theta_z_def sn cs by simp  ultimately show ?thesis using alg_b[OF sp cp e, of z] by simpqed theorem theta_z_avg:  fixes z phi :: real  assumes "0 < phi" and "phi < pi"  shows "theta_z z phi = (a_z z phi + b_z z phi) / 2"  using a_z_arc[OF assms, of z] b_z_arc[OF assms, of z] by (simp add: algebra_simps) theorem b_z_from_theta:  fixes z phi :: real  assumes "0 < phi" and "phi < pi"  shows "b_z z phi = 2 * theta_z z phi - a_z z phi"  using theta_z_avg[OF assms, of z] by simp section \<open>Monotonicity: a_z strictly increasing, theta_z non-increasing\<close> lemma cos_gt_z:  fixes z phi :: real  assumes "0 \<le> z" and "z < 1" and "0 < phi" and "phi < arccos z"  shows "z < cos phi"proof -  have d2: "arccos z \<le> pi / 2" by (rule arccos_facts(2)[OF assms(1,2)])  have "cos (arccos z) < cos phi"    using assms(3,4) d2 pi_gt_zero by (intro cos_monotone_0_pi) linarith+  then show ?thesis using arccos_facts(3)[OF assms(1,2)] by simpqed lemma cos_ge_z:  fixes z phi :: real  assumes "0 \<le> z" and "z < 1" and "0 < phi" and "phi \<le> arccos z"  shows "z \<le> cos phi"proof (cases "phi = arccos z")  case True  then show ?thesis using arccos_facts(3)[OF assms(1,2)] by simpnext  case False  then show ?thesis using cos_gt_z[OF assms(1,2,3)] assms(4) by simpqed theorem a_z_strict_mono:  fixes z p1 p2 :: real  assumes "0 \<le> z" and "z < 1" and "0 < p1" and "p1 < p2" and "p2 \<le> arccos z"  shows "a_z z p1 < a_z z p2"proof -  have d2: "arccos z \<le> pi / 2" by (rule arccos_facts(2)[OF assms(1,2)])  have dr: "(a_z z has_real_derivative (cos x - z) / (1 + cos x)) (at x)" if "p1 \<le> x" "x \<le> p2" for x  proof -    have "- pi < x" "x < pi" using that assms(3,5) d2 pi_gt_zero by linarith+    then show ?thesis by (rule a_z_deriv)  qed  have D: "\<exists>y. DERIV (a_z z) x :> y \<and> 0 < y" if x1: "p1 < x" and x2: "x < p2" for x  proof -    have cz: "z < cos x" using cos_gt_z[OF assms(1,2)] x1 x2 assms(3,5) by simp    have "0 < (cos x - z) / (1 + cos x)" using cz assms(1) by (intro divide_pos_pos) linarith+    then show ?thesis using dr[of x] x1 x2 by auto  qed  have C: "continuous_on {p1..p2} (a_z z)"    by (intro continuous_at_imp_continuous_on ballI DERIV_isCont) (use dr in auto)  show ?thesis by (rule DERIV_pos_imp_increasing_open[OF assms(4) D C]) (use D in blast)qed theorem a_z_inj:  fixes z p1 p2 :: real  assumes "0 \<le> z" and "z < 1" and "0 < p1" and "p1 \<le> arccos z" and "0 < p2" and "p2 \<le> arccos z"    and "a_z z p1 = a_z z p2"  shows "p1 = p2"proof (rule ccontr)  assume ne: "p1 \<noteq> p2"  then consider "p1 < p2" | "p2 < p1" by linarith  then show False  proof cases    case 1 then show ?thesis using a_z_strict_mono[OF assms(1,2,3) 1 assms(6)] assms(7) by simp  next    case 2 then show ?thesis using a_z_strict_mono[OF assms(1,2,5) 2 assms(4)] assms(7) by simp  qedqed theorem theta_z_antimono:  fixes z p1 p2 :: real  assumes "0 \<le> z" and "z < 1" and "0 < p1" and "p1 \<le> p2" and "p2 \<le> arccos z"  shows "theta_z z p2 \<le> theta_z z p1"proof -  have d2: "arccos z \<le> pi / 2" by (rule arccos_facts(2)[OF assms(1,2)])  define f where "f = (\<lambda>x. (a_z z x + b_z z x) / 2)"  have fe: "f x = theta_z z x" if "0 < x" "x \<le> p2" for x    unfolding f_def using theta_z_avg[of x z] that assms(5) d2 pi_gt_zero by simp  have D: "\<exists>y. DERIV f x :> y \<and> y \<le> 0" if x1: "p1 \<le> x" and x2: "x \<le> p2" for x  proof -    have x0: "0 < x" and xp: "x < pi" using x1 x2 assms(3,5) d2 pi_gt_zero by linarith+    have da: "(a_z z has_real_derivative (cos x - z) / (1 + cos x)) (at x)"      using x0 xp by (intro a_z_deriv) linarith+    have db: "(b_z z has_real_derivative (z - cos x) / (1 - cos x)) (at x)"      using x0 xp by (intro b_z_deriv)    have dd: "(f has_real_derivative ((cos x - z) / (1 + cos x) + (z - cos x) / (1 - cos x)) / 2) (at x)"      unfolding f_def by (rule DERIV_cdivide[OF DERIV_add[OF da db]])    have cge: "z \<le> cos x" using cos_ge_z[OF assms(1,2)] x1 x2 assms(3,5) by simp    have c0: "0 \<le> cos x" using cge assms(1) by linarith    have c1: "cos x < 1"    proof -      have "1 - cos x = 2 * (sin (x / 2))\<^sup>2" by (rule one_minus_cos)      moreover have "0 < (sin (x / 2))\<^sup>2"        using x0 xp by (intro zero_less_power sin_gt_zero) simp_all      ultimately show ?thesis by linarith    qed    have n1: "1 + cos x \<noteq> 0" using c0 by linarith    have n2: "1 - cos x \<noteq> 0" using c1 by linarith    have n3: "1 - cos x * cos x \<noteq> 0"    proof -      have "1 - cos x * cos x = (1 + cos x) * (1 - cos x)" by (simp add: algebra_simps)      then show ?thesis using n1 n2 by simp    qed    have n4: "2 - cos x * (cos x * 2) \<noteq> 0" using n3 by (simp add: algebra_simps)    have "((cos x - z) / (1 + cos x) + (z - cos x) / (1 - cos x)) / 2          = - (cos x * (cos x - z)) / ((1 + cos x) * (1 - cos x))"      using n1 n2 n3 n4 by (simp add: field_simps)    moreover have "- (cos x * (cos x - z)) / ((1 + cos x) * (1 - cos x)) \<le> 0"    proof -      have "0 \<le> cos x * (cos x - z)" using c0 cge by (intro mult_nonneg_nonneg) linarith+      moreover have "0 < (1 + cos x) * (1 - cos x)" using c0 c1 by (intro mult_pos_pos) linarith+      ultimately show ?thesis by (simp add: divide_nonpos_pos)    qed    ultimately show ?thesis using dd by auto  qed  have "f p2 \<le> f p1" by (rule DERIV_nonpos_imp_nonincreasing[OF assms(4)]) (blast intro: D)  then show ?thesis using fe assms(3,4,5) by simpqed theorem theta_z_ge_phi:  fixes z phi :: real  assumes "0 \<le> z" and "z < 1" and "0 < phi" and "phi \<le> arccos z"  shows "phi \<le> theta_z z phi"proof -  have d2: "arccos z \<le> pi / 2" by (rule arccos_facts(2)[OF assms(1,2)])  have "0 < sin phi" using assms(3,4) d2 pi_gt_zero by (intro sin_gt_zero) linarith+  moreover have "0 \<le> cos phi - z" using cos_ge_z[OF assms] by simp  ultimately show ?thesis unfolding theta_z_def by simpqed section \<open>The range of a_z and the wait of the arc\<close> lemma sin_lt_self:  fixes x :: real  assumes "0 < x" and "x < pi"  shows "sin x < x"proof -  define f where "f = (\<lambda>t::real. t - sin t)"  have D: "\<exists>y. DERIV f t :> y \<and> 0 < y" if t0: "0 < t" and t1: "t < x" for t  proof -    have "(f has_real_derivative 1 - cos t) (at t)" unfolding f_def      by (auto intro!: derivative_eq_intros)    moreover have "0 < 1 - cos t"    proof -      have "1 - cos t = 2 * (sin (t / 2))\<^sup>2" by (rule one_minus_cos)      moreover have "0 < (sin (t / 2))\<^sup>2"        using t0 t1 assms(2) by (intro zero_less_power sin_gt_zero) simp_all      ultimately show ?thesis by linarith    qed    ultimately show ?thesis by blast  qed  have C: "continuous_on {0..x} f" unfolding f_def by (intro continuous_intros)  have "f 0 < f x" by (rule DERIV_pos_imp_increasing_open[OF assms(1) D C]) (use D in blast)  then show ?thesis unfolding f_def by simpqed theorem a_z_image:  fixes z phi :: real  assumes "0 \<le> z" and "z < 1" and "0 < phi" and "phi \<le> arccos z"  shows "0 < a_z z phi" and "a_z z phi \<le> arccos z - sin (arccos z)"proof -  have d2: "arccos z \<le> pi / 2" by (rule arccos_facts(2)[OF assms(1,2)])  have pp: "phi < pi" using assms(4) d2 pi_gt_zero by linarith  have "0 < sin phi" using assms(3) pp by (intro sin_gt_zero)  have "phi - sin phi < a_z z phi \<or> phi - sin phi = a_z z phi"  proof -    have w: "0 \<le> theta_z z phi - phi" using theta_z_ge_phi[OF assms] by simp    have "0 \<le> 1 - cos phi" by simp    then have "0 \<le> (theta_z z phi - phi) * (1 - cos phi)" using w by (intro mult_nonneg_nonneg)    then show ?thesis using a_z_arc[OF assms(3) pp, of z] by linarith  qed  moreover have "sin phi < phi" using assms(3) pp by (rule sin_lt_self)  ultimately show "0 < a_z z phi" by linarith  show "a_z z phi \<le> arccos z - sin (arccos z)"  proof -    have "a_z z phi \<le> a_z z (arccos z)"    proof (cases "phi = arccos z")      case True then show ?thesis by simp    next      case False then show ?thesis using a_z_strict_mono[OF assms(1,2,3) _ order_refl] assms(4) by simp    qed    then show ?thesis using a_z_at_d[OF assms(1,2)] by simp  qedqed theorem arc_attains:  fixes z phi :: real  assumes "0 \<le> z" and "z < 1" and "0 < phi" and "phi \<le> arccos z"  defines "th \<equiv> theta_z z phi"  shows "th + x3 th phi / 2 = a_z z phi" and "th - x3 th phi / 2 = b_z z phi"    and "y3 th phi = 2 * z" and "0 \<le> th - phi"proof -  have d2: "arccos z \<le> pi / 2" by (rule arccos_facts(2)[OF assms(1,2)])  have pp: "phi < pi" using assms(4) d2 pi_gt_zero by linarith  have sp: "0 < sin phi" using assms(3) pp by (intro sin_gt_zero)  show "th + x3 th phi / 2 = a_z z phi"    unfolding th_def using arc_exposures(1)[of "theta_z z phi" phi] a_z_arc[OF assms(3) pp, of z] by simp  show "th - x3 th phi / 2 = b_z z phi"    unfolding th_def using arc_exposures(2)[of "theta_z z phi" phi] b_z_arc[OF assms(3) pp, of z] by simp  show "y3 th phi = 2 * z" unfolding th_def y3_def theta_z_def using sp by (simp add: field_simps)  show "0 \<le> th - phi" unfolding th_def using theta_z_ge_phi[OF assms(1-4)] by simpqed section \<open>The bound\<close> text \<open>Step (3): on the arc, the lateral constraint $y_3 \le 2z$ gives $\theta \ge \theta_z(\varphi)$, and thenthe exposure $a \ge a_z(\varphi)$.\<close> theorem arc_bounds:  fixes z phi theta :: real  assumes "0 < phi" and "phi < pi" and "y3 theta phi \<le> 2 * z"  shows "theta_z z phi \<le> theta" and "a_z z phi \<le> theta + x3 theta phi / 2"proof -  have sp: "0 < sin phi" using assms(1,2) by (intro sin_gt_zero)  have "(cos phi - z) \<le> (theta - phi) * sin phi" using assms(3) unfolding y3_def by linarith  then have "(cos phi - z) / sin phi \<le> theta - phi" using sp by (simp add: pos_divide_le_eq)  then show th: "theta_z z phi \<le> theta" unfolding theta_z_def by linarith  have "0 \<le> 1 - cos phi" by simp  then have "(theta_z z phi - phi) * (1 - cos phi) \<le> (theta - phi) * (1 - cos phi)"    using th by (intro mult_right_mono) linarith+  then show "a_z z phi \<le> theta + x3 theta phi / 2"    using a_z_arc[OF assms(1,2), of z] arc_exposures(1)[of theta phi] by linarithqed lemma lin_mid:  fixes th a b :: real  assumes "th = (a + b) / 2"  shows "2 * th - a = b"  using assms by (simp add: field_simps) lemma lin_end:  fixes a b d s bz :: real  assumes "a = d - s" and "d \<le> (a + b) / 2" and "bz = d + s"  shows "bz \<le> b"proof -  have h: "2 * d \<le> a + b" using assms(2) by (simp add: field_simps)  have e: "bz = b - (a + b - 2 * d)" using assms(1,3) by (simp add: algebra_simps)  have "0 \<le> a + b - 2 * d" using h by simp  then show ?thesis using e by simpqed theorem planar_exposure_bound_inner:  fixes z a b :: real  assumes z: "0 \<le> z" "z < 1" and a: "0 < a" "a < arccos z - sin (arccos z)"    and arc: "\<exists>phi. 0 < phi \<and> phi < arccos z \<and> a - b = x3 ((a + b) / 2) phi                      \<and> y3 ((a + b) / 2) phi \<le> 2 * z"  shows "\<exists>beta. 0 < beta \<and> beta \<le> arccos z \<and> a_z z beta = a                \<and> (\<forall>beta'. 0 < beta' \<longrightarrow> beta' \<le> arccos z \<longrightarrow> a_z z beta' = a \<longrightarrow> beta' = beta)                \<and> b_z z beta \<le> b"proof -  obtain beta where be: "0 < beta" "beta \<le> arccos z" "a_z z beta = a"    using a_z_range[OF z a(1) less_imp_le[OF a(2)]] by blast  obtain phi where ph: "0 < phi" "phi < arccos z" and xe: "a - b = x3 ((a + b) / 2) phi"    and ye: "y3 ((a + b) / 2) phi \<le> 2 * z" using arc by blast  define th where "th = (a + b) / 2"  have d2: "arccos z \<le> pi / 2" by (rule arccos_facts(2)[OF z])  have pp: "phi < pi" using ph(2) d2 pi_gt_zero by linarith  have bd: "theta_z z phi \<le> th" and ad: "a_z z phi \<le> th + x3 th phi / 2"    using arc_bounds[OF ph(1) pp ye[folded th_def]] by simp_all  have xe': "a - b = x3 th phi" unfolding th_def by (rule xe)  have h: "x3 th phi = a - b" using xe' by simp  have aeq: "th + x3 th phi / 2 = a"    by (subst h, subst th_def) (simp add: field_simps)  have pb: "phi \<le> beta"  proof (rule ccontr)    assume "\<not> phi \<le> beta"    then have "beta < phi" by simp    then have "a_z z beta < a_z z phi" using a_z_strict_mono[OF z be(1) _ _] ph(2) by simp    then show False using ad aeq be(3) by linarith  qed  have "theta_z z beta \<le> theta_z z phi"    using theta_z_antimono[OF z ph(1) pb be(2)] .  then have "theta_z z beta \<le> th" using bd by linarith  moreover have bpp: "beta < pi" using be(2) d2 pi_gt_zero by linarith  ultimately have "b_z z beta \<le> 2 * th - a"    using b_z_from_theta[OF be(1) bpp, of z] be(3) by linarith  moreover have "2 * th - a = b" by (rule lin_mid[OF th_def])  ultimately have "b_z z beta \<le> b" by simp  moreover have "\<forall>beta'. 0 < beta' \<longrightarrow> beta' \<le> arccos z \<longrightarrow> a_z z beta' = a \<longrightarrow> beta' = beta"    using a_z_inj[OF z be(1,2)] be(3) by auto  ultimately show ?thesis using be by blastqed theorem planar_exposure_bound:  fixes z a b :: real  assumes z: "0 \<le> z" "z < 1" and a: "0 < a" "a \<le> arccos z - sin (arccos z)"    and th: "arccos z \<le> (a + b) / 2"    and arc: "a < arccos z - sin (arccos z) \<Longrightarrow>              \<exists>phi. 0 < phi \<and> phi < arccos z \<and> a - b = x3 ((a + b) / 2) phi                      \<and> y3 ((a + b) / 2) phi \<le> 2 * z"  shows "\<exists>beta. 0 < beta \<and> beta \<le> arccos z \<and> a_z z beta = a                \<and> (\<forall>beta'. 0 < beta' \<longrightarrow> beta' \<le> arccos z \<longrightarrow> a_z z beta' = a \<longrightarrow> beta' = beta)                \<and> b_z z beta \<le> b"proof (cases "a < arccos z - sin (arccos z)")  case True  from planar_exposure_bound_inner[OF z a(1) True arc[OF True]] show ?thesis .next  case False  then have ae: "a = arccos z - sin (arccos z)" using a(2) by simp  have d0: "0 < arccos z" by (rule arccos_facts(1)[OF z])  have ad: "a_z z (arccos z) = a" using a_z_at_d[OF z] ae by simp  have bd: "b_z z (arccos z) \<le> b" by (rule lin_end[OF ae th b_z_at_d[OF z]])  have uq: "\<forall>beta'. 0 < beta' \<longrightarrow> beta' \<le> arccos z \<longrightarrow> a_z z beta' = a \<longrightarrow> beta' = arccos z"  proof (intro allI impI)    fix beta' assume h1: "0 < beta'" and h2: "beta' \<le> arccos z" and h3: "a_z z beta' = a"    have "a_z z beta' = a_z z (arccos z)" using h3 ad by simp    then show "beta' = arccos z" by (rule a_z_inj[OF z(1) z(2) h1 h2 d0 order_refl])  qed  show ?thesis using d0 ad bd uq by (intro exI[of _ "arccos z"]) simpqed section \<open>Step (1): odd turns beyond the first are dominated\<close> theorem multi_turn_dominated:  fixes z :: real and k :: nat  assumes "0 \<le> z" and "z < 1" and "1 \<le> k"  shows "arccos z - sin (arccos z) < real k * pi" and "arccos z + sin (arccos z) < real k * pi"proof -  have d2: "arccos z \<le> pi / 2" by (rule arccos_facts(2)[OF assms(1,2)])  have d0: "0 < arccos z" by (rule arccos_facts(1)[OF assms(1,2)])  have s1: "sin (arccos z) \<le> 1" by simp  have s0: "- 1 \<le> sin (arccos z)" by simp  have k1: "(1::real) \<le> real k" using assms(3) by simp  have "pi \<le> real k * pi" using k1 pi_gt_zero by (simp add: mult_le_cancel_right1)  moreover have "2 < pi" using pi_gt3 by simp  ultimately show "arccos z - sin (arccos z) < real k * pi" and "arccos z + sin (arccos z) < real k * pi"    using d2 s1 s0 by linarith+qed end