955 by (cases "z = 0") (simp_all add: rcis_def cis_arg sgn_div_norm of_real_def) |
955 by (cases "z = 0") (simp_all add: rcis_def cis_arg sgn_div_norm of_real_def) |
956 |
956 |
957 lemma cos_arg_i_mult_zero [simp]: "y \<noteq> 0 \<Longrightarrow> Re y = 0 \<Longrightarrow> cos (arg y) = 0" |
957 lemma cos_arg_i_mult_zero [simp]: "y \<noteq> 0 \<Longrightarrow> Re y = 0 \<Longrightarrow> cos (arg y) = 0" |
958 using cis_arg [of y] by (simp add: complex_eq_iff) |
958 using cis_arg [of y] by (simp add: complex_eq_iff) |
959 |
959 |
|
960 subsection \<open>Complex n-th roots\<close> |
|
961 |
|
962 lemma bij_betw_roots_unity: |
|
963 assumes "n > 0" |
|
964 shows "bij_betw (\<lambda>k. cis (2 * pi * real k / real n)) {..<n} {z. z ^ n = 1}" |
|
965 (is "bij_betw ?f _ _") |
|
966 unfolding bij_betw_def |
|
967 proof (intro conjI) |
|
968 show inj: "inj_on ?f {..<n}" unfolding inj_on_def |
|
969 proof (safe, goal_cases) |
|
970 case (1 k l) |
|
971 hence kl: "k < n" "l < n" by simp_all |
|
972 from 1 have "1 = ?f k / ?f l" by simp |
|
973 also have "\<dots> = cis (2*pi*(real k - real l)/n)" |
|
974 using assms by (simp add: field_simps cis_divide) |
|
975 finally have "cos (2*pi*(real k - real l) / n) = 1" |
|
976 by (simp add: complex_eq_iff) |
|
977 then obtain m :: int where "2 * pi * (real k - real l) / real n = real_of_int m * 2 * pi" |
|
978 by (subst (asm) cos_one_2pi_int) blast |
|
979 hence "real_of_int (int k - int l) = real_of_int (m * int n)" |
|
980 unfolding of_int_diff of_int_mult using assms by (simp add: divide_simps) |
|
981 also note of_int_eq_iff |
|
982 finally have *: "abs m * n = abs (int k - int l)" by (simp add: abs_mult) |
|
983 also have "\<dots> < int n" using kl by linarith |
|
984 finally have "m = 0" using assms by simp |
|
985 with * show "k = l" by simp |
|
986 qed |
|
987 |
|
988 have subset: "?f ` {..<n} \<subseteq> {z. z ^ n = 1}" |
|
989 proof safe |
|
990 fix k :: nat |
|
991 have "cis (2 * pi * real k / real n) ^ n = cis (2 * pi) ^ k" |
|
992 using assms by (simp add: DeMoivre mult_ac) |
|
993 also have "cis (2 * pi) = 1" by (simp add: complex_eq_iff) |
|
994 finally show "?f k ^ n = 1" by simp |
|
995 qed |
|
996 |
|
997 have "n = card {..<n}" by simp |
|
998 also from assms and subset have "\<dots> \<le> card {z::complex. z ^ n = 1}" |
|
999 by (intro card_inj_on_le[OF inj]) (auto simp: finite_roots_unity) |
|
1000 finally have card: "card {z::complex. z ^ n = 1} = n" |
|
1001 using assms by (intro antisym card_roots_unity) auto |
|
1002 |
|
1003 have "card (?f ` {..<n}) = card {z::complex. z ^ n = 1}" |
|
1004 using card inj by (subst card_image) auto |
|
1005 with subset and assms show "?f ` {..<n} = {z::complex. z ^ n = 1}" |
|
1006 by (intro card_subset_eq finite_roots_unity) auto |
|
1007 qed |
|
1008 |
|
1009 lemma card_roots_unity_eq: |
|
1010 assumes "n > 0" |
|
1011 shows "card {z::complex. z ^ n = 1} = n" |
|
1012 using bij_betw_same_card [OF bij_betw_roots_unity [OF assms]] by simp |
|
1013 |
|
1014 lemma bij_betw_nth_root_unity: |
|
1015 fixes c :: complex and n :: nat |
|
1016 assumes c: "c \<noteq> 0" and n: "n > 0" |
|
1017 defines "c' \<equiv> root n (norm c) * cis (arg c / n)" |
|
1018 shows "bij_betw (\<lambda>z. c' * z) {z. z ^ n = 1} {z. z ^ n = c}" |
|
1019 proof - |
|
1020 have "c' ^ n = of_real (root n (norm c) ^ n) * cis (arg c)" |
|
1021 unfolding of_real_power using n by (simp add: c'_def power_mult_distrib DeMoivre) |
|
1022 also from n have "root n (norm c) ^ n = norm c" by simp |
|
1023 also from c have "of_real \<dots> * cis (arg c) = c" by (simp add: cis_arg Complex.sgn_eq) |
|
1024 finally have [simp]: "c' ^ n = c" . |
|
1025 |
|
1026 show ?thesis unfolding bij_betw_def inj_on_def |
|
1027 proof safe |
|
1028 fix z :: complex assume "z ^ n = 1" |
|
1029 hence "(c' * z) ^ n = c' ^ n" by (simp add: power_mult_distrib) |
|
1030 also have "c' ^ n = of_real (root n (norm c) ^ n) * cis (arg c)" |
|
1031 unfolding of_real_power using n by (simp add: c'_def power_mult_distrib DeMoivre) |
|
1032 also from n have "root n (norm c) ^ n = norm c" by simp |
|
1033 also from c have "\<dots> * cis (arg c) = c" by (simp add: cis_arg Complex.sgn_eq) |
|
1034 finally show "(c' * z) ^ n = c" . |
|
1035 next |
|
1036 fix z assume z: "c = z ^ n" |
|
1037 define z' where "z' = z / c'" |
|
1038 from c and n have "c' \<noteq> 0" by (auto simp: c'_def) |
|
1039 with n c have "z = c' * z'" and "z' ^ n = 1" |
|
1040 by (auto simp: z'_def power_divide z) |
|
1041 thus "z \<in> (\<lambda>z. c' * z) ` {z. z ^ n = 1}" by blast |
|
1042 qed (insert c n, auto simp: c'_def) |
|
1043 qed |
|
1044 |
|
1045 lemma finite_nth_roots [intro]: |
|
1046 assumes "n > 0" |
|
1047 shows "finite {z::complex. z ^ n = c}" |
|
1048 proof (cases "c = 0") |
|
1049 case True |
|
1050 with assms have "{z::complex. z ^ n = c} = {0}" by auto |
|
1051 thus ?thesis by simp |
|
1052 next |
|
1053 case False |
|
1054 from assms have "finite {z::complex. z ^ n = 1}" by (intro finite_roots_unity) simp_all |
|
1055 also have "?this \<longleftrightarrow> ?thesis" |
|
1056 by (rule bij_betw_finite, rule bij_betw_nth_root_unity) fact+ |
|
1057 finally show ?thesis . |
|
1058 qed |
|
1059 |
|
1060 lemma card_nth_roots: |
|
1061 assumes "c \<noteq> 0" "n > 0" |
|
1062 shows "card {z::complex. z ^ n = c} = n" |
|
1063 proof - |
|
1064 have "card {z. z ^ n = c} = card {z::complex. z ^ n = 1}" |
|
1065 by (rule sym, rule bij_betw_same_card, rule bij_betw_nth_root_unity) fact+ |
|
1066 also have "\<dots> = n" by (rule card_roots_unity_eq) fact+ |
|
1067 finally show ?thesis . |
|
1068 qed |
|
1069 |
|
1070 lemma sum_roots_unity: |
|
1071 assumes "n > 1" |
|
1072 shows "\<Sum>{z::complex. z ^ n = 1} = 0" |
|
1073 proof - |
|
1074 define \<omega> where "\<omega> = cis (2 * pi / real n)" |
|
1075 have [simp]: "\<omega> \<noteq> 1" |
|
1076 proof |
|
1077 assume "\<omega> = 1" |
|
1078 with assms obtain k :: int where "2 * pi / real n = 2 * pi * of_int k" |
|
1079 by (auto simp: \<omega>_def complex_eq_iff cos_one_2pi_int) |
|
1080 with assms have "real n * of_int k = 1" by (simp add: field_simps) |
|
1081 also have "real n * of_int k = of_int (int n * k)" by simp |
|
1082 also have "1 = (of_int 1 :: real)" by simp |
|
1083 also note of_int_eq_iff |
|
1084 finally show False using assms by (auto simp: zmult_eq_1_iff) |
|
1085 qed |
|
1086 |
|
1087 have "(\<Sum>z | z ^ n = 1. z :: complex) = (\<Sum>k<n. cis (2 * pi * real k / real n))" |
|
1088 using assms by (intro sum.reindex_bij_betw [symmetric] bij_betw_roots_unity) auto |
|
1089 also have "\<dots> = (\<Sum>k<n. \<omega> ^ k)" |
|
1090 by (intro sum.cong refl) (auto simp: \<omega>_def DeMoivre mult_ac) |
|
1091 also have "\<dots> = (\<omega> ^ n - 1) / (\<omega> - 1)" |
|
1092 by (subst geometric_sum) auto |
|
1093 also have "\<omega> ^ n - 1 = cis (2 * pi) - 1" using assms by (auto simp: \<omega>_def DeMoivre) |
|
1094 also have "\<dots> = 0" by (simp add: complex_eq_iff) |
|
1095 finally show ?thesis by simp |
|
1096 qed |
|
1097 |
|
1098 lemma sum_nth_roots: |
|
1099 assumes "n > 1" |
|
1100 shows "\<Sum>{z::complex. z ^ n = c} = 0" |
|
1101 proof (cases "c = 0") |
|
1102 case True |
|
1103 with assms have "{z::complex. z ^ n = c} = {0}" by auto |
|
1104 also have "\<Sum>\<dots> = 0" by simp |
|
1105 finally show ?thesis . |
|
1106 next |
|
1107 case False |
|
1108 define c' where "c' = root n (norm c) * cis (arg c / n)" |
|
1109 from False and assms have "(\<Sum>{z. z ^ n = c}) = (\<Sum>z | z ^ n = 1. c' * z)" |
|
1110 by (subst sum.reindex_bij_betw [OF bij_betw_nth_root_unity, symmetric]) |
|
1111 (auto simp: sum_distrib_left finite_roots_unity c'_def) |
|
1112 also from assms have "\<dots> = 0" |
|
1113 by (simp add: sum_distrib_left [symmetric] sum_roots_unity) |
|
1114 finally show ?thesis . |
|
1115 qed |
960 |
1116 |
961 subsection \<open>Square root of complex numbers\<close> |
1117 subsection \<open>Square root of complex numbers\<close> |
962 |
1118 |
963 primcorec csqrt :: "complex \<Rightarrow> complex" |
1119 primcorec csqrt :: "complex \<Rightarrow> complex" |
964 where |
1120 where |