(*  Title:      HOL/Ln.thy

    Author:     Jeremy Avigad

*)

header {* Properties of ln *}

theory Ln

imports Transcendental

begin

lemma exp_first_two_terms: "exp x = 1 + x + suminf (%n. 

  inverse(fact (n+2)) * (x ^ (n+2)))"

proof -

  have "exp x = suminf (%n. inverse(fact n) * (x ^ n))"

    by (simp add: exp_def)

  also from summable_exp have "... = (SUM n::nat : {0..<2}. 

      inverse(fact n) * (x ^ n)) + suminf (%n.

      inverse(fact(n+2)) * (x ^ (n+2)))" (is "_ = ?a + _")

    by (rule suminf_split_initial_segment)

  also have "?a = 1 + x"

    by (simp add: numerals)

  finally show ?thesis .

qed

lemma exp_tail_after_first_two_terms_summable: 

  "summable (%n. inverse(fact (n+2)) * (x ^ (n+2)))"

proof -

  note summable_exp

  thus ?thesis

    by (frule summable_ignore_initial_segment)

qed

lemma aux1: assumes a: "0 <= x" and b: "x <= 1"

    shows "inverse (fact ((n::nat) + 2)) * x ^ (n + 2) <= (x^2/2) * ((1/2)^n)"

proof (induct n)

  show "inverse (fact ((0::nat) + 2)) * x ^ (0 + 2) <= 

      x ^ 2 / 2 * (1 / 2) ^ 0"

    by (simp add: real_of_nat_Suc power2_eq_square)

next

  fix n :: nat

  assume c: "inverse (fact (n + 2)) * x ^ (n + 2)

       <= x ^ 2 / 2 * (1 / 2) ^ n"

  show "inverse (fact (Suc n + 2)) * x ^ (Suc n + 2)

           <= x ^ 2 / 2 * (1 / 2) ^ Suc n"

  proof -

    have "inverse(fact (Suc n + 2)) <= (1/2) * inverse (fact (n+2))"

    proof -

      have "Suc n + 2 = Suc (n + 2)" by simp

      then have "fact (Suc n + 2) = Suc (n + 2) * fact (n + 2)" 

        by simp

      then have "real(fact (Suc n + 2)) = real(Suc (n + 2) * fact (n + 2))" 

        apply (rule subst)

        apply (rule refl)

        done

      also have "... = real(Suc (n + 2)) * real(fact (n + 2))"

        by (rule real_of_nat_mult)

      finally have "real (fact (Suc n + 2)) = 

         real (Suc (n + 2)) * real (fact (n + 2))" .

      then have "inverse(fact (Suc n + 2)) = 

         inverse(Suc (n + 2)) * inverse(fact (n + 2))"

        apply (rule ssubst)

        apply (rule inverse_mult_distrib)

        done

      also have "... <= (1/2) * inverse(fact (n + 2))"

        apply (rule mult_right_mono)

        apply (subst inverse_eq_divide)

        apply simp

        apply (rule inv_real_of_nat_fact_ge_zero)

        done

      finally show ?thesis .

    qed

    moreover have "x ^ (Suc n + 2) <= x ^ (n + 2)"

      apply (simp add: mult_compare_simps)

      apply (simp add: assms)

      apply (subgoal_tac "0 <= x * (x * x^n)")

      apply force

      apply (rule mult_nonneg_nonneg, rule a)+

      apply (rule zero_le_power, rule a)

      done

    ultimately have "inverse (fact (Suc n + 2)) *  x ^ (Suc n + 2) <=

        (1 / 2 * inverse (fact (n + 2))) * x ^ (n + 2)"

      apply (rule mult_mono)

      apply (rule mult_nonneg_nonneg)

      apply simp

      apply (subst inverse_nonnegative_iff_nonnegative)

      apply (rule real_of_nat_ge_zero)

      apply (rule zero_le_power)

      apply (rule a)

      done

    also have "... = 1 / 2 * (inverse (fact (n + 2)) * x ^ (n + 2))"

      by simp

    also have "... <= 1 / 2 * (x ^ 2 / 2 * (1 / 2) ^ n)"

      apply (rule mult_left_mono)

      apply (rule c)

      apply simp

      done

    also have "... = x ^ 2 / 2 * (1 / 2 * (1 / 2) ^ n)"

      by auto

    also have "(1::real) / 2 * (1 / 2) ^ n = (1 / 2) ^ (Suc n)"

      by (rule power_Suc [THEN sym])

    finally show ?thesis .

  qed

qed

lemma aux2: "(%n. (x::real) ^ 2 / 2 * (1 / 2) ^ n) sums x^2"

proof -

  have "(%n. (1 / 2::real)^n) sums (1 / (1 - (1/2)))"

    apply (rule geometric_sums)

    by (simp add: abs_less_iff)

  also have "(1::real) / (1 - 1/2) = 2"

    by simp

  finally have "(%n. (1 / 2::real)^n) sums 2" .

  then have "(%n. x ^ 2 / 2 * (1 / 2) ^ n) sums (x^2 / 2 * 2)"

    by (rule sums_mult)

  also have "x^2 / 2 * 2 = x^2"

    by simp

  finally show ?thesis .

qed

lemma exp_bound: "0 <= (x::real) ==> x <= 1 ==> exp x <= 1 + x + x^2"

proof -

  assume a: "0 <= x"

  assume b: "x <= 1"

  have c: "exp x = 1 + x + suminf (%n. inverse(fact (n+2)) * 

      (x ^ (n+2)))"

    by (rule exp_first_two_terms)

  moreover have "suminf (%n. inverse(fact (n+2)) * (x ^ (n+2))) <= x^2"

  proof -

    have "suminf (%n. inverse(fact (n+2)) * (x ^ (n+2))) <=

        suminf (%n. (x^2/2) * ((1/2)^n))"

      apply (rule summable_le)

      apply (auto simp only: aux1 a b)

      apply (rule exp_tail_after_first_two_terms_summable)

      by (rule sums_summable, rule aux2)  

    also have "... = x^2"

      by (rule sums_unique [THEN sym], rule aux2)

    finally show ?thesis .

  qed

  ultimately show ?thesis

    by auto

qed

lemma aux4: "0 <= (x::real) ==> x <= 1 ==> exp (x - x^2) <= 1 + x" 

proof -

  assume a: "0 <= x" and b: "x <= 1"

  have "exp (x - x^2) = exp x / exp (x^2)"

    by (rule exp_diff)

  also have "... <= (1 + x + x^2) / exp (x ^2)"

    apply (rule divide_right_mono) 

    apply (rule exp_bound)

    apply (rule a, rule b)

    apply simp

    done

  also have "... <= (1 + x + x^2) / (1 + x^2)"

    apply (rule divide_left_mono)

    apply (auto simp add: exp_ge_add_one_self_aux)

    apply (rule add_nonneg_nonneg)

    using a apply auto

    apply (rule mult_pos_pos)

    apply auto

    apply (rule add_pos_nonneg)

    apply auto

    done

  also from a have "... <= 1 + x"

    by (simp add: field_simps zero_compare_simps)

  finally show ?thesis .

qed

lemma ln_one_plus_pos_lower_bound: "0 <= x ==> x <= 1 ==> 

    x - x^2 <= ln (1 + x)"

proof -

  assume a: "0 <= x" and b: "x <= 1"

  then have "exp (x - x^2) <= 1 + x"

    by (rule aux4)

  also have "... = exp (ln (1 + x))"

  proof -

    from a have "0 < 1 + x" by auto

    thus ?thesis

      by (auto simp only: exp_ln_iff [THEN sym])

  qed

  finally have "exp (x - x ^ 2) <= exp (ln (1 + x))" .

  thus ?thesis by (auto simp only: exp_le_cancel_iff)

qed

lemma ln_one_minus_pos_upper_bound: "0 <= x ==> x < 1 ==> ln (1 - x) <= - x"

proof -

  assume a: "0 <= (x::real)" and b: "x < 1"

  have "(1 - x) * (1 + x + x^2) = (1 - x^3)"

    by (simp add: algebra_simps power2_eq_square power3_eq_cube)

  also have "... <= 1"

    by (auto simp add: a)

  finally have "(1 - x) * (1 + x + x ^ 2) <= 1" .

  moreover have "0 < 1 + x + x^2"

    apply (rule add_pos_nonneg)

    using a apply auto

    done

  ultimately have "1 - x <= 1 / (1 + x + x^2)"

    by (elim mult_imp_le_div_pos)

  also have "... <= 1 / exp x"

    apply (rule divide_left_mono)

    apply (rule exp_bound, rule a)

    using a b apply auto

    apply (rule mult_pos_pos)

    apply (rule add_pos_nonneg)

    apply auto

    done

  also have "... = exp (-x)"

    by (auto simp add: exp_minus divide_inverse)

  finally have "1 - x <= exp (- x)" .

  also have "1 - x = exp (ln (1 - x))"

  proof -

    have "0 < 1 - x"

      by (insert b, auto)

    thus ?thesis

      by (auto simp only: exp_ln_iff [THEN sym])

  qed

  finally have "exp (ln (1 - x)) <= exp (- x)" .

  thus ?thesis by (auto simp only: exp_le_cancel_iff)

qed

lemma aux5: "x < 1 ==> ln(1 - x) = - ln(1 + x / (1 - x))"

proof -

  assume a: "x < 1"

  have "ln(1 - x) = - ln(1 / (1 - x))"

  proof -

    have "ln(1 - x) = - (- ln (1 - x))"

      by auto

    also have "- ln(1 - x) = ln 1 - ln(1 - x)"

      by simp

    also have "... = ln(1 / (1 - x))"

      apply (rule ln_div [THEN sym])

      by (insert a, auto)

    finally show ?thesis .

  qed

  also have " 1 / (1 - x) = 1 + x / (1 - x)" using a by(simp add:field_simps)

  finally show ?thesis .

qed

lemma ln_one_minus_pos_lower_bound: "0 <= x ==> x <= (1 / 2) ==> 

    - x - 2 * x^2 <= ln (1 - x)"

proof -

  assume a: "0 <= x" and b: "x <= (1 / 2)"

  from b have c: "x < 1"

    by auto

  then have "ln (1 - x) = - ln (1 + x / (1 - x))"

    by (rule aux5)

  also have "- (x / (1 - x)) <= ..."

  proof - 

    have "ln (1 + x / (1 - x)) <= x / (1 - x)"

      apply (rule ln_add_one_self_le_self)

      apply (rule divide_nonneg_pos)

      by (insert a c, auto) 

    thus ?thesis

      by auto

  qed

  also have "- (x / (1 - x)) = -x / (1 - x)"

    by auto

  finally have d: "- x / (1 - x) <= ln (1 - x)" .

  have "0 < 1 - x" using a b by simp

  hence e: "-x - 2 * x^2 <= - x / (1 - x)"

    using mult_right_le_one_le[of "x*x" "2*x"] a b

    by (simp add:field_simps power2_eq_square)

  from e d show "- x - 2 * x^2 <= ln (1 - x)"

    by (rule order_trans)

qed

lemma exp_ge_add_one_self [simp]: "1 + (x::real) <= exp x"

  apply (case_tac "0 <= x")

  apply (erule exp_ge_add_one_self_aux)

  apply (case_tac "x <= -1")

  apply (subgoal_tac "1 + x <= 0")

  apply (erule order_trans)

  apply simp

  apply simp

  apply (subgoal_tac "1 + x = exp(ln (1 + x))")

  apply (erule ssubst)

  apply (subst exp_le_cancel_iff)

  apply (subgoal_tac "ln (1 - (- x)) <= - (- x)")

  apply simp

  apply (rule ln_one_minus_pos_upper_bound) 

  apply auto

done

lemma ln_add_one_self_le_self2: "-1 < x ==> ln(1 + x) <= x"

  apply (subgoal_tac "x = ln (exp x)")

  apply (erule ssubst)back

  apply (subst ln_le_cancel_iff)

  apply auto

done

lemma abs_ln_one_plus_x_minus_x_bound_nonneg:

    "0 <= x ==> x <= 1 ==> abs(ln (1 + x) - x) <= x^2"

proof -

  assume x: "0 <= x"

  assume x1: "x <= 1"

  from x have "ln (1 + x) <= x"

    by (rule ln_add_one_self_le_self)

  then have "ln (1 + x) - x <= 0" 

    by simp

  then have "abs(ln(1 + x) - x) = - (ln(1 + x) - x)"

    by (rule abs_of_nonpos)

  also have "... = x - ln (1 + x)" 

    by simp

  also have "... <= x^2"

  proof -

    from x x1 have "x - x^2 <= ln (1 + x)"

      by (intro ln_one_plus_pos_lower_bound)

    thus ?thesis

      by simp

  qed

  finally show ?thesis .

qed

lemma abs_ln_one_plus_x_minus_x_bound_nonpos:

    "-(1 / 2) <= x ==> x <= 0 ==> abs(ln (1 + x) - x) <= 2 * x^2"

proof -

  assume a: "-(1 / 2) <= x"

  assume b: "x <= 0"

  have "abs(ln (1 + x) - x) = x - ln(1 - (-x))" 

    apply (subst abs_of_nonpos)

    apply simp

    apply (rule ln_add_one_self_le_self2)

    using a apply auto

    done

  also have "... <= 2 * x^2"

    apply (subgoal_tac "- (-x) - 2 * (-x)^2 <= ln (1 - (-x))")

    apply (simp add: algebra_simps)

    apply (rule ln_one_minus_pos_lower_bound)

    using a b apply auto

    done

  finally show ?thesis .

qed

lemma abs_ln_one_plus_x_minus_x_bound:

    "abs x <= 1 / 2 ==> abs(ln (1 + x) - x) <= 2 * x^2"

  apply (case_tac "0 <= x")

  apply (rule order_trans)

  apply (rule abs_ln_one_plus_x_minus_x_bound_nonneg)

  apply auto

  apply (rule abs_ln_one_plus_x_minus_x_bound_nonpos)

  apply auto

done

lemma ln_x_over_x_mono: "exp 1 <= x ==> x <= y ==> (ln y / y) <= (ln x / x)"  

proof -

  assume x: "exp 1 <= x" "x <= y"

  have a: "0 < x" and b: "0 < y"

    apply (insert x)

    apply (subgoal_tac "0 < exp (1::real)")

    apply arith

    apply auto

    apply (subgoal_tac "0 < exp (1::real)")

    apply arith

    apply auto

    done

  have "x * ln y - x * ln x = x * (ln y - ln x)"

    by (simp add: algebra_simps)

  also have "... = x * ln(y / x)"

    apply (subst ln_div)

    apply (rule b, rule a, rule refl)

    done

  also have "y / x = (x + (y - x)) / x"

    by simp

  also have "... = 1 + (y - x) / x" using x a by (simp add: field_simps)

  also have "x * ln(1 + (y - x) / x) <= x * ((y - x) / x)"

    apply (rule mult_left_mono)

    apply (rule ln_add_one_self_le_self)

    apply (rule divide_nonneg_pos)

    using x a apply simp_all

    done

  also have "... = y - x" using a by simp

  also have "... = (y - x) * ln (exp 1)" by simp

  also have "... <= (y - x) * ln x"

    apply (rule mult_left_mono)

    apply (subst ln_le_cancel_iff)

    apply force

    apply (rule a)

    apply (rule x)

    using x apply simp

    done

  also have "... = y * ln x - x * ln x"

    by (rule left_diff_distrib)

  finally have "x * ln y <= y * ln x"

    by arith

  then have "ln y <= (y * ln x) / x" using a by (simp add: field_simps)

  also have "... = y * (ln x / x)" by simp

  finally show ?thesis using b by (simp add: field_simps)

qed

lemma ln_le_minus_one:

  "0 < x \<Longrightarrow> ln x \<le> x - 1"

  using exp_ge_add_one_self[of "ln x"] by simp

lemma ln_eq_minus_one:

  assumes "0 < x" "ln x = x - 1" shows "x = 1"

proof -

  let "?l y" = "ln y - y + 1"

  have D: "\<And>x. 0 < x \<Longrightarrow> DERIV ?l x :> (1 / x - 1)"

    by (auto intro!: DERIV_intros)

  show ?thesis

  proof (cases rule: linorder_cases)

    assume "x < 1"

    from dense[OF `x < 1`] obtain a where "x < a" "a < 1" by blast

    from `x < a` have "?l x < ?l a"

    proof (rule DERIV_pos_imp_increasing, safe)

      fix y assume "x \<le> y" "y \<le> a"

      with `0 < x` `a < 1` have "0 < 1 / y - 1" "0 < y"

        by (auto simp: field_simps)

      with D show "\<exists>z. DERIV ?l y :> z \<and> 0 < z"

        by auto

    qed

    also have "\<dots> \<le> 0"

      using ln_le_minus_one `0 < x` `x < a` by (auto simp: field_simps)

    finally show "x = 1" using assms by auto

  next

    assume "1 < x"

    from dense[OF `1 < x`] obtain a where "1 < a" "a < x" by blast

    from `a < x` have "?l x < ?l a"

    proof (rule DERIV_neg_imp_decreasing, safe)

      fix y assume "a \<le> y" "y \<le> x"

      with `1 < a` have "1 / y - 1 < 0" "0 < y"

        by (auto simp: field_simps)

      with D show "\<exists>z. DERIV ?l y :> z \<and> z < 0"

        by blast

    qed

    also have "\<dots> \<le> 0"

      using ln_le_minus_one `1 < a` by (auto simp: field_simps)

    finally show "x = 1" using assms by auto

  qed simp

qed

end