src/HOL/Algebra/Exponent.thy
author wenzelm
Sun Mar 21 15:57:40 2010 +0100 (2010-03-21)
changeset 35847 19f1f7066917
parent 32946 22664da2923b
child 35848 5443079512ea
permissions -rw-r--r--
eliminated old constdefs;
     1 (*  Title:      HOL/Algebra/Exponent.thy
     2     Author:     Florian Kammueller, with new proofs by L C Paulson
     3 
     4     exponent p s   yields the greatest power of p that divides s.
     5 *)
     6 
     7 theory Exponent
     8 imports Main "~~/src/HOL/Old_Number_Theory/Primes" Binomial
     9 begin
    10 
    11 section {*Sylow's Theorem*}
    12 
    13 subsection {*The Combinatorial Argument Underlying the First Sylow Theorem*}
    14 
    15 definition exponent :: "nat => nat => nat" where
    16 "exponent p s == if prime p then (GREATEST r. p^r dvd s) else 0"
    17 
    18 
    19 text{*Prime Theorems*}
    20 
    21 lemma prime_imp_one_less: "prime p ==> Suc 0 < p"
    22 by (unfold prime_def, force)
    23 
    24 lemma prime_iff:
    25   "(prime p) = (Suc 0 < p & (\<forall>a b. p dvd a*b --> (p dvd a) | (p dvd b)))"
    26 apply (auto simp add: prime_imp_one_less)
    27 apply (blast dest!: prime_dvd_mult)
    28 apply (auto simp add: prime_def)
    29 apply (erule dvdE)
    30 apply (case_tac "k=0", simp)
    31 apply (drule_tac x = m in spec)
    32 apply (drule_tac x = k in spec)
    33 apply (simp add: dvd_mult_cancel1 dvd_mult_cancel2)
    34 done
    35 
    36 lemma zero_less_prime_power: "prime p ==> 0 < p^a"
    37 by (force simp add: prime_iff)
    38 
    39 
    40 lemma zero_less_card_empty: "[| finite S; S \<noteq> {} |] ==> 0 < card(S)"
    41 by (rule ccontr, simp)
    42 
    43 
    44 lemma prime_dvd_cases:
    45   "[| p*k dvd m*n;  prime p |]  
    46    ==> (\<exists>x. k dvd x*n & m = p*x) | (\<exists>y. k dvd m*y & n = p*y)"
    47 apply (simp add: prime_iff)
    48 apply (frule dvd_mult_left)
    49 apply (subgoal_tac "p dvd m | p dvd n")
    50  prefer 2 apply blast
    51 apply (erule disjE)
    52 apply (rule disjI1)
    53 apply (rule_tac [2] disjI2)
    54 apply (auto elim!: dvdE)
    55 done
    56 
    57 
    58 lemma prime_power_dvd_cases [rule_format (no_asm)]: "prime p
    59   ==> \<forall>m n. p^c dvd m*n -->  
    60         (\<forall>a b. a+b = Suc c --> p^a dvd m | p^b dvd n)"
    61 apply (induct c)
    62  apply clarify
    63  apply (case_tac "a")
    64   apply simp
    65  apply simp
    66 (*inductive step*)
    67 apply simp
    68 apply clarify
    69 apply (erule prime_dvd_cases [THEN disjE], assumption, auto)
    70 (*case 1: p dvd m*)
    71  apply (case_tac "a")
    72   apply simp
    73  apply clarify
    74  apply (drule spec, drule spec, erule (1) notE impE)
    75  apply (drule_tac x = nat in spec)
    76  apply (drule_tac x = b in spec)
    77  apply simp
    78 (*case 2: p dvd n*)
    79 apply (case_tac "b")
    80  apply simp
    81 apply clarify
    82 apply (drule spec, drule spec, erule (1) notE impE)
    83 apply (drule_tac x = a in spec)
    84 apply (drule_tac x = nat in spec, simp)
    85 done
    86 
    87 (*needed in this form in Sylow.ML*)
    88 lemma div_combine:
    89   "[| prime p; ~ (p ^ (Suc r) dvd n);  p^(a+r) dvd n*k |]  
    90    ==> p ^ a dvd k"
    91 by (drule_tac a = "Suc r" and b = a in prime_power_dvd_cases, assumption, auto)
    92 
    93 (*Lemma for power_dvd_bound*)
    94 lemma Suc_le_power: "Suc 0 < p ==> Suc n <= p^n"
    95 apply (induct n)
    96 apply (simp (no_asm_simp))
    97 apply simp
    98 apply (subgoal_tac "2 * n + 2 <= p * p^n", simp)
    99 apply (subgoal_tac "2 * p^n <= p * p^n")
   100 apply arith
   101 apply (drule_tac k = 2 in mult_le_mono2, simp)
   102 done
   103 
   104 (*An upper bound for the n such that p^n dvd a: needed for GREATEST to exist*)
   105 lemma power_dvd_bound: "[|p^n dvd a;  Suc 0 < p;  a > 0|] ==> n < a"
   106 apply (drule dvd_imp_le)
   107 apply (drule_tac [2] n = n in Suc_le_power, auto)
   108 done
   109 
   110 
   111 text{*Exponent Theorems*}
   112 
   113 lemma exponent_ge [rule_format]:
   114   "[|p^k dvd n;  prime p;  0<n|] ==> k <= exponent p n"
   115 apply (simp add: exponent_def)
   116 apply (erule Greatest_le)
   117 apply (blast dest: prime_imp_one_less power_dvd_bound)
   118 done
   119 
   120 lemma power_exponent_dvd: "s>0 ==> (p ^ exponent p s) dvd s"
   121 apply (simp add: exponent_def)
   122 apply clarify
   123 apply (rule_tac k = 0 in GreatestI)
   124 prefer 2 apply (blast dest: prime_imp_one_less power_dvd_bound, simp)
   125 done
   126 
   127 lemma power_Suc_exponent_Not_dvd:
   128   "[|(p * p ^ exponent p s) dvd s;  prime p |] ==> s=0"
   129 apply (subgoal_tac "p ^ Suc (exponent p s) dvd s")
   130  prefer 2 apply simp 
   131 apply (rule ccontr)
   132 apply (drule exponent_ge, auto)
   133 done
   134 
   135 lemma exponent_power_eq [simp]: "prime p ==> exponent p (p^a) = a"
   136 apply (simp (no_asm_simp) add: exponent_def)
   137 apply (rule Greatest_equality, simp)
   138 apply (simp (no_asm_simp) add: prime_imp_one_less power_dvd_imp_le)
   139 done
   140 
   141 lemma exponent_equalityI:
   142   "!r::nat. (p^r dvd a) = (p^r dvd b) ==> exponent p a = exponent p b"
   143 by (simp (no_asm_simp) add: exponent_def)
   144 
   145 lemma exponent_eq_0 [simp]: "\<not> prime p ==> exponent p s = 0"
   146 by (simp (no_asm_simp) add: exponent_def)
   147 
   148 
   149 (* exponent_mult_add, easy inclusion.  Could weaken p \<in> prime to Suc 0 < p *)
   150 lemma exponent_mult_add1: "[| a > 0; b > 0 |]
   151   ==> (exponent p a) + (exponent p b) <= exponent p (a * b)"
   152 apply (case_tac "prime p")
   153 apply (rule exponent_ge)
   154 apply (auto simp add: power_add)
   155 apply (blast intro: prime_imp_one_less power_exponent_dvd mult_dvd_mono)
   156 done
   157 
   158 (* exponent_mult_add, opposite inclusion *)
   159 lemma exponent_mult_add2: "[| a > 0; b > 0 |]  
   160   ==> exponent p (a * b) <= (exponent p a) + (exponent p b)"
   161 apply (case_tac "prime p")
   162 apply (rule leI, clarify)
   163 apply (cut_tac p = p and s = "a*b" in power_exponent_dvd, auto)
   164 apply (subgoal_tac "p ^ (Suc (exponent p a + exponent p b)) dvd a * b")
   165 apply (rule_tac [2] le_imp_power_dvd [THEN dvd_trans])
   166   prefer 3 apply assumption
   167  prefer 2 apply simp 
   168 apply (frule_tac a = "Suc (exponent p a) " and b = "Suc (exponent p b) " in prime_power_dvd_cases)
   169  apply (assumption, force, simp)
   170 apply (blast dest: power_Suc_exponent_Not_dvd)
   171 done
   172 
   173 lemma exponent_mult_add: "[| a > 0; b > 0 |]
   174    ==> exponent p (a * b) = (exponent p a) + (exponent p b)"
   175 by (blast intro: exponent_mult_add1 exponent_mult_add2 order_antisym)
   176 
   177 
   178 lemma not_divides_exponent_0: "~ (p dvd n) ==> exponent p n = 0"
   179 apply (case_tac "exponent p n", simp)
   180 apply (case_tac "n", simp)
   181 apply (cut_tac s = n and p = p in power_exponent_dvd)
   182 apply (auto dest: dvd_mult_left)
   183 done
   184 
   185 lemma exponent_1_eq_0 [simp]: "exponent p (Suc 0) = 0"
   186 apply (case_tac "prime p")
   187 apply (auto simp add: prime_iff not_divides_exponent_0)
   188 done
   189 
   190 
   191 text{*Main Combinatorial Argument*}
   192 
   193 lemma le_extend_mult: "[| c > 0; a <= b |] ==> a <= b * (c::nat)"
   194 apply (rule_tac P = "%x. x <= b * c" in subst)
   195 apply (rule mult_1_right)
   196 apply (rule mult_le_mono, auto)
   197 done
   198 
   199 lemma p_fac_forw_lemma:
   200   "[| (m::nat) > 0; k > 0; k < p^a; (p^r) dvd (p^a)* m - k |] ==> r <= a"
   201 apply (rule notnotD)
   202 apply (rule notI)
   203 apply (drule contrapos_nn [OF _ leI, THEN notnotD], assumption)
   204 apply (drule less_imp_le [of a])
   205 apply (drule le_imp_power_dvd)
   206 apply (drule_tac b = "p ^ r" in dvd_trans, assumption)
   207 apply (metis diff_is_0_eq dvd_diffD1 gcd_dvd2 gcd_mult' gr0I le_extend_mult less_diff_conv nat_dvd_not_less nat_mult_commute not_add_less2 xt1(10))
   208 done
   209 
   210 lemma p_fac_forw: "[| (m::nat) > 0; k>0; k < p^a; (p^r) dvd (p^a)* m - k |]  
   211   ==> (p^r) dvd (p^a) - k"
   212 apply (frule p_fac_forw_lemma [THEN le_imp_power_dvd, of _ k p], auto)
   213 apply (subgoal_tac "p^r dvd p^a*m")
   214  prefer 2 apply (blast intro: dvd_mult2)
   215 apply (drule dvd_diffD1)
   216   apply assumption
   217  prefer 2 apply (blast intro: dvd_diff_nat)
   218 apply (drule gr0_implies_Suc, auto)
   219 done
   220 
   221 
   222 lemma r_le_a_forw:
   223   "[| (k::nat) > 0; k < p^a; p>0; (p^r) dvd (p^a) - k |] ==> r <= a"
   224 by (rule_tac m = "Suc 0" in p_fac_forw_lemma, auto)
   225 
   226 lemma p_fac_backw: "[| m>0; k>0; (p::nat)\<noteq>0;  k < p^a;  (p^r) dvd p^a - k |]  
   227   ==> (p^r) dvd (p^a)*m - k"
   228 apply (frule_tac k1 = k and p1 = p in r_le_a_forw [THEN le_imp_power_dvd], auto)
   229 apply (subgoal_tac "p^r dvd p^a*m")
   230  prefer 2 apply (blast intro: dvd_mult2)
   231 apply (drule dvd_diffD1)
   232   apply assumption
   233  prefer 2 apply (blast intro: dvd_diff_nat)
   234 apply (drule less_imp_Suc_add, auto)
   235 done
   236 
   237 lemma exponent_p_a_m_k_equation: "[| m>0; k>0; (p::nat)\<noteq>0;  k < p^a |]  
   238   ==> exponent p (p^a * m - k) = exponent p (p^a - k)"
   239 apply (blast intro: exponent_equalityI p_fac_forw p_fac_backw)
   240 done
   241 
   242 text{*Suc rules that we have to delete from the simpset*}
   243 lemmas bad_Sucs = binomial_Suc_Suc mult_Suc mult_Suc_right
   244 
   245 (*The bound K is needed; otherwise it's too weak to be used.*)
   246 lemma p_not_div_choose_lemma [rule_format]:
   247   "[| \<forall>i. Suc i < K --> exponent p (Suc i) = exponent p (Suc(j+i))|]  
   248    ==> k<K --> exponent p ((j+k) choose k) = 0"
   249 apply (cases "prime p")
   250  prefer 2 apply simp 
   251 apply (induct k)
   252 apply (simp (no_asm))
   253 (*induction step*)
   254 apply (subgoal_tac "(Suc (j+k) choose Suc k) > 0")
   255  prefer 2 apply (simp add: zero_less_binomial_iff, clarify)
   256 apply (subgoal_tac "exponent p ((Suc (j+k) choose Suc k) * Suc k) = 
   257                     exponent p (Suc k)")
   258  txt{*First, use the assumed equation.  We simplify the LHS to
   259   @{term "exponent p (Suc (j + k) choose Suc k) + exponent p (Suc k)"}
   260   the common terms cancel, proving the conclusion.*}
   261  apply (simp del: bad_Sucs add: exponent_mult_add)
   262 txt{*Establishing the equation requires first applying 
   263    @{text Suc_times_binomial_eq} ...*}
   264 apply (simp del: bad_Sucs add: Suc_times_binomial_eq [symmetric])
   265 txt{*...then @{text exponent_mult_add} and the quantified premise.*}
   266 apply (simp del: bad_Sucs add: zero_less_binomial_iff exponent_mult_add)
   267 done
   268 
   269 (*The lemma above, with two changes of variables*)
   270 lemma p_not_div_choose:
   271   "[| k<K;  k<=n;
   272       \<forall>j. 0<j & j<K --> exponent p (n - k + (K - j)) = exponent p (K - j)|]
   273    ==> exponent p (n choose k) = 0"
   274 apply (cut_tac j = "n-k" and k = k and p = p in p_not_div_choose_lemma)
   275   prefer 3 apply simp
   276  prefer 2 apply assumption
   277 apply (drule_tac x = "K - Suc i" in spec)
   278 apply (simp add: Suc_diff_le)
   279 done
   280 
   281 
   282 lemma const_p_fac_right:
   283   "m>0 ==> exponent p ((p^a * m - Suc 0) choose (p^a - Suc 0)) = 0"
   284 apply (case_tac "prime p")
   285  prefer 2 apply simp 
   286 apply (frule_tac a = a in zero_less_prime_power)
   287 apply (rule_tac K = "p^a" in p_not_div_choose)
   288    apply simp
   289   apply simp
   290  apply (case_tac "m")
   291   apply (case_tac [2] "p^a")
   292    apply auto
   293 (*now the hard case, simplified to
   294     exponent p (Suc (p ^ a * m + i - p ^ a)) = exponent p (Suc i) *)
   295 apply (subgoal_tac "0<p")
   296  prefer 2 apply (force dest!: prime_imp_one_less)
   297 apply (subst exponent_p_a_m_k_equation, auto)
   298 done
   299 
   300 lemma const_p_fac:
   301   "m>0 ==> exponent p (((p^a) * m) choose p^a) = exponent p m"
   302 apply (case_tac "prime p")
   303  prefer 2 apply simp 
   304 apply (subgoal_tac "0 < p^a * m & p^a <= p^a * m")
   305  prefer 2 apply (force simp add: prime_iff)
   306 txt{*A similar trick to the one used in @{text p_not_div_choose_lemma}:
   307   insert an equation; use @{text exponent_mult_add} on the LHS; on the RHS,
   308   first
   309   transform the binomial coefficient, then use @{text exponent_mult_add}.*}
   310 apply (subgoal_tac "exponent p ((( (p^a) * m) choose p^a) * p^a) = 
   311                     a + exponent p m")
   312  apply (simp del: bad_Sucs add: zero_less_binomial_iff exponent_mult_add prime_iff)
   313 txt{*one subgoal left!*}
   314 apply (subst times_binomial_minus1_eq, simp, simp)
   315 apply (subst exponent_mult_add, simp)
   316 apply (simp (no_asm_simp) add: zero_less_binomial_iff)
   317 apply arith
   318 apply (simp del: bad_Sucs add: exponent_mult_add const_p_fac_right)
   319 done
   320 
   321 
   322 end