🏛️ Atlas✒️Isabelle.MemoryAccessFloors.Memory_Cycle_No_Reset view on GitHub ↗13 theorems
(*  Title:      Memory_Cycle_No_Reset.thy    Author:     Carles Marin    Copyright:  Carles Marin    License:    BSD-3-Clause     The mathematical core of Proposition prop:noreset of paper A (memory floors): the memory cycle without reset, to    first order.  Two pieces:      (a) a change-of-variables inequality: f continuous, f >= 0 on the path, |theta'| <= G give          (1/G) |int_{theta a}^{theta b} f| <= int_a^b f (theta s) ds;      (b) with rho(P) = [gq P + fq P (2-P) + gm (1-P) + fm (1-P^2)]/3 and          F_t(th) = (2/G) int_0^th rho(cos^2 u) du + t rho(cos^2 th):  F_t'(pi/2) = (2/(3G)) (gm + fm), so if          gm + fm > 0 every minimiser of F_t on [0,pi/2] lies below pi/2 and F_t (pi/2) is not the minimum.    The physical reduction r_1 = int rho(P(s)) ds along the lossless path is a HYPOTHESIS of the model and is not    formalised; the asymptotics t -> infinity (delta_* and the gain) is not formalised.*) theory Memory_Cycle_No_Reset  imports "HOL-Analysis.Analysis"begin section \<open>Piece (a): change of variables\<close> text \<open>The primitive of a continuous function on a compact interval, composed with a path.\<close> lemma primitive_difference:  fixes f :: "real \<Rightarrow> real" and R x y :: real  assumes fc: "continuous_on UNIV f" and x: "-R \<le> x" and xy: "x \<le> y" and y: "y \<le> R"  shows "integral {-R..y} f - integral {-R..x} f = integral {x..y} f"proof -  have "f integrable_on {-R..y}" using fc by (intro integrable_continuous_real continuous_on_subset[OF fc]) auto  then have "integral {-R..x} f + integral {x..y} f = integral {-R..y} f"    by (rule Henstock_Kurzweil_Integration.integral_combine[OF x xy])  then show ?thesis by simpqed theorem change_of_variables_ineq:  fixes f theta theta' :: "real \<Rightarrow> real" and a b G :: real  assumes ab: "a \<le> b" and G: "0 < G" and fc: "continuous_on UNIV f"    and f0: "\<forall>s\<in>{a..b}. 0 \<le> f (theta s)"    and der: "\<forall>s\<in>{a..b}. (theta has_vector_derivative theta' s) (at s within {a..b})"    and bd: "\<forall>s\<in>{a..b}. \<bar>theta' s\<bar> \<le> G"  shows "(1 / G) * \<bar>integral {min (theta a) (theta b)..max (theta a) (theta b)} f\<bar>           \<le> integral {a..b} (\<lambda>s. f (theta s))"proof -  have thc: "continuous_on {a..b} theta"    unfolding continuous_on_eq_continuous_within    using der by (auto intro: has_vector_derivative_continuous)  have "bounded (theta ` {a..b})" by (intro compact_imp_bounded compact_continuous_image thc compact_Icc)  then obtain R where Rb: "\<forall>y\<in>theta ` {a..b}. norm y \<le> R" unfolding bounded_iff by blast  have inK: "\<And>s. s \<in> {a..b} \<Longrightarrow> theta s \<in> {-R..R}"  proof -    fix s assume s: "s \<in> {a..b}"    then have "norm (theta s) \<le> R" using Rb by blast    then show "theta s \<in> {-R..R}" by (simp add: abs_le_iff)  qed  define Phi where "Phi = (\<lambda>x. integral {-R..x} f)"  have Phid: "\<And>x. x \<in> {-R..R} \<Longrightarrow> (Phi has_vector_derivative f x) (at x within {-R..R})"    unfolding Phi_def by (rule integral_has_vector_derivative[OF continuous_on_subset[OF fc] ]) auto  have chain: "\<And>s. s \<in> {a..b} \<Longrightarrow>      ((Phi \<circ> theta) has_vector_derivative theta' s * f (theta s)) (at s within {a..b})"  proof -    fix s assume s: "s \<in> {a..b}"    have 1: "(Phi has_vector_derivative f (theta s)) (at (theta s) within theta ` {a..b})"      by (rule has_vector_derivative_within_subset[OF Phid[OF inK[OF s]]]) (use inK in auto)    have "((Phi \<circ> theta) has_vector_derivative theta' s *\<^sub>R f (theta s)) (at s within {a..b})"      by (rule vector_diff_chain_within[OF der[rule_format, OF s] 1])    then show "((Phi \<circ> theta) has_vector_derivative theta' s * f (theta s)) (at s within {a..b})" by simp  qed  have ftc: "((\<lambda>s. theta' s * f (theta s)) has_integral (Phi (theta b) - Phi (theta a))) {a..b}"    by (rule fundamental_theorem_of_calculus[OF ab, where f = "\<lambda>x. Phi (theta x)"]) (use chain in \<open>simp add: o_def\<close>)  define D where "D = Phi (theta b) - Phi (theta a)"  have fthc: "continuous_on {a..b} (\<lambda>s. f (theta s))"    by (rule continuous_on_compose2[OF fc thc]) simp  have hi: "((\<lambda>s. f (theta s)) has_integral integral {a..b} (\<lambda>s. f (theta s))) {a..b}"    using fthc by (intro integrable_integral integrable_continuous_real)  have key: "\<And>c. \<forall>s\<in>{a..b}. c * (theta' s * f (theta s)) \<le> f (theta s) \<Longrightarrow>      c * D \<le> integral {a..b} (\<lambda>s. f (theta s))"  proof -    fix c assume pw: "\<forall>s\<in>{a..b}. c * (theta' s * f (theta s)) \<le> f (theta s)"    have h1: "((\<lambda>s. c *\<^sub>R (theta' s * f (theta s))) has_integral c *\<^sub>R D) {a..b}"      by (rule has_integral_cmul[OF ftc[folded D_def]])    have "c *\<^sub>R D \<le> integral {a..b} (\<lambda>s. f (theta s))"      by (rule has_integral_le[OF h1 hi]) (use pw in simp)    then show "c * D \<le> integral {a..b} (\<lambda>s. f (theta s))" by simp  qed  have up: "(1 / G) * D \<le> integral {a..b} (\<lambda>s. f (theta s))"  proof (rule key, rule ballI)    fix s assume s: "s \<in> {a..b}"    have f0s: "0 \<le> f (theta s)" using f0 s by blast    have h: "theta' s \<le> G" using bd s by (auto simp: abs_le_iff)    have h1: "f (theta s) * theta' s \<le> f (theta s) * G" by (rule mult_left_mono[OF h f0s])    have h2: "(1 / G) * (f (theta s) * theta' s) \<le> (1 / G) * (f (theta s) * G)"      by (rule mult_left_mono[OF h1]) (use G in simp)    show "1 / G * (theta' s * f (theta s)) \<le> f (theta s)" using h2 G by (simp add: ac_simps)  qed  have lo: "- (1 / G) * D \<le> integral {a..b} (\<lambda>s. f (theta s))"  proof (rule key, rule ballI)    fix s assume s: "s \<in> {a..b}"    have f0s: "0 \<le> f (theta s)" using f0 s by blast    have h: "- theta' s \<le> G" using bd s by (auto simp: abs_le_iff)    have h1: "f (theta s) * (- theta' s) \<le> f (theta s) * G" by (rule mult_left_mono[OF h f0s])    have h2: "(1 / G) * (f (theta s) * (- theta' s)) \<le> (1 / G) * (f (theta s) * G)"      by (rule mult_left_mono[OF h1]) (use G in simp)    show "- (1 / G) * (theta' s * f (theta s)) \<le> f (theta s)" using h2 G by (simp add: ac_simps)  qed  have absD: "(1 / G) * \<bar>D\<bar> \<le> integral {a..b} (\<lambda>s. f (theta s))"    using up lo by (cases "0 \<le> D") (simp_all add: abs_of_nonneg abs_of_neg)  have ta: "theta a \<in> {-R..R}" and tb: "theta b \<in> {-R..R}" using inK ab by auto  have "\<bar>D\<bar> = \<bar>integral {min (theta a) (theta b)..max (theta a) (theta b)} f\<bar>"  proof (cases "theta a \<le> theta b")    case True    have "D = integral {theta a..theta b} f"      unfolding D_def Phi_def using primitive_difference[OF fc _ True] ta tb by simp    with True show ?thesis by simp  next    case False    then have le: "theta b \<le> theta a" by simp    have pd: "integral {-R..theta a} f - integral {-R..theta b} f = integral {theta b..theta a} f"      by (rule primitive_difference[OF fc _ le _]) (use ta tb in auto)    have "D = - integral {theta b..theta a} f"      unfolding D_def Phi_def using pd by simp    with le show ?thesis by simp  qed  with absD show ?thesis by simpqed section \<open>Piece (b): the first-order minimisation\<close> locale cycle =  fixes gq fq gm fm G t :: real  assumes gq0: "0 \<le> gq" and fq0: "0 \<le> fq" and gm0: "0 \<le> gm" and fm0: "0 \<le> fm"    and G0: "0 < G" and t0: "0 \<le> t"begin definition rho :: "real \<Rightarrow> real" where  "rho P = (gq * P + fq * P * (2 - P) + gm * (1 - P) + fm * (1 - P^2)) / 3" definition F :: "real \<Rightarrow> real" where  "F th = (2 / G) * integral {0..th} (\<lambda>u. rho (cos u ^ 2)) + t * rho (cos th ^ 2)" lemma rho_nonneg: assumes "0 \<le> P" "P \<le> 1" shows "0 \<le> rho P"proof -  have "0 \<le> 2 - P" using assms by simp  have "P^2 \<le> 1" using assms by (simp add: power_le_one)  have "0 \<le> gq * P" using gq0 assms by simp  moreover have "0 \<le> fq * P * (2 - P)" using fq0 assms \<open>0 \<le> 2 - P\<close> by (intro mult_nonneg_nonneg) auto  moreover have "0 \<le> gm * (1 - P)" using gm0 assms by simp  moreover have "0 \<le> fm * (1 - P^2)" using fm0 \<open>P^2 \<le> 1\<close> by simp  ultimately show ?thesis unfolding rho_def by simpqed lemma rho_zero: "rho 0 = (gm + fm) / 3" by (simp add: rho_def) lemma rho_cos_continuous: "continuous_on UNIV (\<lambda>u. rho (cos u ^ 2))"  unfolding rho_def by (intro continuous_intros) simp lemma rho_cos_nonneg: "0 \<le> rho (cos u ^ 2)"proof (rule rho_nonneg)  show "0 \<le> cos u ^ 2" by simp  show "cos u ^ 2 \<le> 1" using cos_squared_eq[of u] zero_le_power2[of "sin u"] by linarithqed text \<open>Application of piece (a) to the density rho along a path with speed at most G.\<close> theorem noreset_lower_bound:  fixes theta theta' :: "real \<Rightarrow> real" and a b :: real  assumes ab: "a \<le> b"    and der: "\<forall>s\<in>{a..b}. (theta has_vector_derivative theta' s) (at s within {a..b})"    and bd: "\<forall>s\<in>{a..b}. \<bar>theta' s\<bar> \<le> G"  shows "(1 / G) * \<bar>integral {min (theta a) (theta b)..max (theta a) (theta b)} (\<lambda>u. rho (cos u ^ 2))\<bar>           \<le> integral {a..b} (\<lambda>s. rho (cos (theta s) ^ 2))"  using change_of_variables_ineq[where f = "\<lambda>u. rho (cos u ^ 2)", OF ab G0 rho_cos_continuous _ der bd]    rho_cos_nonneg by blast text \<open>The derivative of F at pi/2.\<close> lemma rho_cos_deriv_zero:  "((\<lambda>th. rho (cos th ^ 2)) has_real_derivative 0) (at (pi / 2))"proof -  have m: "((\<lambda>th. cos th * cos th) has_real_derivative      (- sin (pi / 2)) * cos (pi / 2) + cos (pi / 2) * (- sin (pi / 2))) (at (pi / 2))"    by (auto intro!: derivative_eq_intros)  have c2: "((\<lambda>th. cos th ^ 2) has_real_derivative 0) (at (pi / 2))"    using m by (simp add: power2_eq_square)  have "((\<lambda>P. (gq * P + fq * P * (2 - P) + gm * (1 - P) + fm * (1 - P^2)) / 3) has_real_derivative          (gq + fq * (2 - 2 * (cos (pi / 2) ^ 2)) - gm - 2 * fm * cos (pi / 2) ^ 2) / 3) (at (cos (pi / 2) ^ 2))"    by (auto intro!: derivative_eq_intros)  from DERIV_chain[OF this c2] show ?thesis unfolding rho_def comp_def by simpqed theorem F_derivative_pi_half:  "(F has_real_derivative (2 / (3 * G)) * (gm + fm)) (at (pi / 2))"proof -  define g where "g = (\<lambda>u. rho (cos u ^ 2))"  have gc: "continuous_on {0..pi} g" unfolding g_def using rho_cos_continuous continuous_on_subset by blast  have pm: "pi / 2 \<in> {0..pi}" using pi_gt_zero by auto  have w: "((\<lambda>x. integral {0..x} g) has_vector_derivative g (pi / 2)) (at (pi / 2) within {0..pi})"    by (rule integral_has_vector_derivative[OF gc pm])  have "((\<lambda>x. integral {0..x} g) has_vector_derivative g (pi / 2)) (at (pi / 2) within {0<..<pi})"    by (rule has_vector_derivative_within_subset[OF w]) auto  then have "((\<lambda>x. integral {0..x} g) has_vector_derivative g (pi / 2)) (at (pi / 2))"    using at_within_open[where S = "{0<..<pi}" and a = "pi / 2"] pi_gt_zero by simp  then have i: "((\<lambda>x. integral {0..x} g) has_real_derivative g (pi / 2)) (at (pi / 2))"  proof -    have e: "(\<lambda>x::real. x * g (pi / 2)) = (*) (g (pi / 2))" by (rule ext) simp    show ?thesis using \<open>(_ has_vector_derivative _) (at (pi / 2))\<close>      by (simp add: has_vector_derivative_def has_field_derivative_def e)  qed  have "((\<lambda>th. (2 / G) * integral {0..th} g + t * rho (cos th ^ 2)) has_real_derivative          (2 / G) * g (pi / 2) + t * 0) (at (pi / 2))"    by (rule DERIV_add[OF DERIV_cmult[OF i] DERIV_cmult[OF rho_cos_deriv_zero]])  moreover have "g (pi / 2) = (gm + fm) / 3" unfolding g_def by (simp add: rho_def)  ultimately show ?thesis unfolding F_def g_def[symmetric] using G0 by (simp add: field_simps)qed theorem F_below_pi_half:  assumes pos: "0 < gm + fm"  shows "\<exists>th. 0 \<le> th \<and> th < pi / 2 \<and> F th < F (pi / 2)"proof -  have d: "0 < (2 / (3 * G)) * (gm + fm)" using G0 pos by simp  obtain d0 where d0: "0 < d0" and h: "\<forall>h. 0 < h \<longrightarrow> h < d0 \<longrightarrow> F (pi / 2 - h) < F (pi / 2)"    using DERIV_pos_inc_left[OF F_derivative_pi_half d] by blast  define h0 where "h0 = min (d0 / 2) (pi / 4)"  have h0: "0 < h0" "h0 < d0" "h0 \<le> pi / 4" unfolding h0_def using d0 pi_gt_zero by auto  have "0 \<le> pi / 2 - h0" "pi / 2 - h0 < pi / 2" using h0 pi_gt_zero by linarith+  moreover have "F (pi / 2 - h0) < F (pi / 2)" using h h0 by blast  ultimately show ?thesis by blastqed lemma F_continuous: "continuous_on {0..pi / 2} F"proof -  define g where "g = (\<lambda>u. rho (cos u ^ 2))"  have gc: "continuous_on {0..pi} g" unfolding g_def using rho_cos_continuous continuous_on_subset by blast  have "continuous_on {0..pi} (\<lambda>x. integral {0..x} g)"    unfolding continuous_on_eq_continuous_within    using integral_has_vector_derivative[OF gc] has_vector_derivative_continuous by blast  then have i1: "continuous_on {0..pi / 2} (\<lambda>x. integral {0..x} g)"    by (rule continuous_on_subset) (use pi_gt_zero in auto)  have i2: "continuous_on {0..pi / 2} (\<lambda>th. rho (cos th ^ 2))"    by (rule continuous_on_subset[OF rho_cos_continuous]) simp  have "continuous_on {0..pi / 2} (\<lambda>th. (2 / G) * integral {0..th} g + t * rho (cos th ^ 2))"    by (rule continuous_on_add[OF continuous_on_mult_left[OF i1] continuous_on_mult_left[OF i2]])  then show ?thesis unfolding F_def g_def .qed theorem minimiser_not_pi_half:  assumes pos: "0 < gm + fm"  shows "\<exists>th0\<in>{0..pi / 2}. (\<forall>th\<in>{0..pi / 2}. F th0 \<le> F th) \<and> th0 < pi / 2 \<and> F th0 < F (pi / 2)"proof -  have "\<exists>th0\<in>{0..pi / 2}. \<forall>th\<in>{0..pi / 2}. F th0 \<le> F th"    by (rule continuous_attains_inf[OF compact_Icc _ F_continuous]) (use pi_gt_zero in auto)  then obtain th0 where th0: "th0 \<in> {0..pi / 2}" "\<forall>th\<in>{0..pi / 2}. F th0 \<le> F th" by blast  obtain th where th: "0 \<le> th" "th < pi / 2" "F th < F (pi / 2)" using F_below_pi_half[OF pos] by blast  have "F th0 \<le> F th" using th0(2) th by auto  then have lt: "F th0 < F (pi / 2)" using th(3) by simp  then have "th0 \<noteq> pi / 2" by blast  then have "th0 < pi / 2" using th0(1) by auto  then show ?thesis using th0 lt by blastqed corollary every_minimiser_below_pi_half:  assumes pos: "0 < gm + fm" and th0: "th0 \<in> {0..pi / 2}" and min: "\<forall>th\<in>{0..pi / 2}. F th0 \<le> F th"  shows "th0 < pi / 2" and "F th0 < F (pi / 2)"proof -  obtain th where th: "0 \<le> th" "th < pi / 2" "F th < F (pi / 2)" using F_below_pi_half[OF pos] by blast  have "F th0 \<le> F th" using min th by auto  then show lt: "F th0 < F (pi / 2)" using th(3) by simp  then have "th0 \<noteq> pi / 2" by blast  then show "th0 < pi / 2" using th0 by autoqed end end