1 header {* GCD for polynomials, implemented using the function package (_FP) *}
3 imports "~~/src/HOL/Algebra/poly/Polynomial" (*imports ~~/src/HOL/Library/Polynomial ...2012*)
4 "~~/src/HOL/Number_Theory/Primes"
5 (* WN130304.TODO see Algebra/poly/LongDiv.thy: lcoeff_def*)
9 This code has been translated from GCD_Poly.thy by Diana Meindl,
10 who follows Franz Winkler, Polynomial algorithyms in computer algebra, Springer 1996.
11 Winkler's original identifiers are in test/./gcd_poly_winkler.sml;
12 test/../gcd_poly.sml documents the changes towards GCD_Poly.thy;
13 the style of GCD_Poly.thy has been adapted to the function package.
16 section {* gcd for univariate polynomials *}
18 type_synonym unipoly = "int list" (*TODO: compare Polynomial.thy*)
19 value "[0, 1, 2, 3, 4, 5] :: unipoly"
21 subsection {* auxiliary functions *}
23 5 div 2 = 2; ~5 div 2 = ~3; BUT WEE NEED ~5 div2 2 = ~2; *)
24 definition div2 :: "int \<Rightarrow> int \<Rightarrow> int" (infixl "div2" 70) where
25 "a div2 b = (if a div b < 0 then (\<bar>a\<bar> div \<bar>b\<bar>) * -1 else a div b)"
28 value "-5 div2 2 = -2"
29 value "-5 div2 -2 = 2"
30 value " 5 div2 -2 = -2"
32 value "gcd (15::int) (6::int) = 3"
33 value "gcd (10::int) (3::int) = 1"
34 value "gcd (6::int) (24::int) = 6"
36 (* drop tail elements equal 0 *)
37 primrec drop_hd_zeros :: "int list \<Rightarrow> int list" where
38 "drop_hd_zeros (p # ps) = (if p = 0 then drop_hd_zeros ps else (p # ps))"
39 definition drop_tl_zeros :: "int list \<Rightarrow> int list" where
40 "drop_tl_zeros p = (rev o drop_hd_zeros o rev) p"
42 subsection {* modulo calculations for integers *}
43 (* modi is just local for mod_inv *)
44 function modi :: "int \<Rightarrow> int \<Rightarrow> nat \<Rightarrow> nat \<Rightarrow> nat" where
50 else modi (rold * ((int rinv) + 1)) rold m (rinv + 1))"
52 termination by (relation "measure (\<lambda>(r, rold, m, rinv). m - rinv)") auto
54 (* mod_inv :: int \<Rightarrow> nat \<Rightarrow> nat
57 yields r * s mod m = 1 *)
58 definition mod_inv :: "int \<Rightarrow> nat \<Rightarrow> nat" where "mod_inv r m = modi r r m 1"
60 value "modi 5 5 7 1 = 3"
61 value "modi 3 3 7 1 = 5"
62 value "modi 4 4 339 1 = 85"
64 value "mod_inv 5 7 = 3"
65 value "mod_inv 3 7 = 5"
66 value "mod_inv 4 339 = 85"
68 value "mod_inv -5 7 = 4"
69 value "mod_inv -3 7 = 2"
70 value "mod_inv -4 339 = 254"
72 (* mod_div :: int \<Rightarrow> int \<Rightarrow> nat \<Rightarrow> natO
75 yields a * b ^(-1) mod m = c <\<Longrightarrow> a mod m = (b * c) mod m*)
76 definition mod_div :: "int \<Rightarrow> int \<Rightarrow> nat \<Rightarrow> nat" where
77 "mod_div a b m = (nat a) * (mod_inv b m) mod m"
79 (*if mod_div 21 4 5 = 4 then () else error "mod_div 21 4 5 = 4 changed";
80 if mod_div 1 4 5 = 4 then () else error "mod_div 1 4 5 = 4 changed";
81 if mod_div 0 4 5 = 0 then () else error "mod_div 0 4 5 = 0 changed";
83 value "mod_div 21 3 5 = 2" value "(21::int) mod 5 = (3 * 2) mod 5"
84 (* 21/3 = 7 mod 5 21 mod 5 = 6 mod 5
86 value "mod_div 22 3 5 = 4" value "(22::int) mod 5 = (3 * 4) mod 5"
87 (* 22/3 = ------- 22 mod 5 = 12 mod 5
89 value "mod_div 23 3 5 = 1" value "(23::int) mod 5 = (3 * 1) mod 5"
90 (* 23/3 = ------- 23 mod 5 = 3 mod 5
92 value "mod_div 24 3 5 = 3" value "(24::int) mod 5 = (3 * 3) mod 5"
93 (* 24/3 = ------- 24 mod 5 = 9 mod 5
95 value "mod_div 25 3 5 = 0" value "(25::int) mod 5 = (3 * 0) mod 5"
96 (* 25/3 = ------- 25 mod 5 = 0 mod 5
98 value "mod_div 21 4 5 = 4" value "(21::int) mod 5 = (4 * 4) mod 5"
99 value "mod_div 1 4 5 = 4" value "( 1::int) mod 5 = (4 * 4) mod 5"
100 value "mod_div 0 4 5 = 0" value "( 0::int) mod 5 = (0 * 4) mod 5"
102 (* root1 is just local to approx_root *)
103 function root1 :: "int \<Rightarrow> nat \<Rightarrow> nat" where
104 "root1 a n = (if (int (n * n)) < a then root1 a (n + 1) else n)"
106 termination by (relation "measure (\<lambda>(a, n). nat (a - (int (n * n))))") auto
108 (* required just for one approximation:
109 approx_root :: nat \<Rightarrow> nat
112 yields r * r \<ge> a *)
113 definition approx_root :: "int \<Rightarrow> nat" where "approx_root a = root1 a 1"
115 (* chinese_remainder :: int \<Rightarrow> int \<Rightarrow> int \<Rightarrow> int \<Rightarrow> int
116 chinese_remainder (r1, m1) (r2, m2) = r
118 yields r = r1 mod m1 \<and> r = r2 mod m2 *)
119 definition chinese_remainder :: "int \<Rightarrow> nat \<Rightarrow> int \<Rightarrow> nat \<Rightarrow> nat" where
120 "chinese_remainder r1 m1 r2 m2 =
121 ((nat (r1 mod (int m1))) +
122 (nat (((r2 - (r1 mod (int m1))) * (int (mod_inv (int m1) m2))) mod (int m2))) * m1)"
124 value "chinese_remainder 17 9 3 4 = 35"
125 value "chinese_remainder 7 2 6 11 = 17"
127 subsection {* creation of lists of primes for efficiency *}
129 (* is_prime :: int list \<Rightarrow> int \<Rightarrow> bool
131 assumes max ps < n \<and> n \<le> (max ps)^2 \<and>
132 (* FIXME: really ^^^^^^^^^^^^^^^? *)
133 (\<forall>p. List.member ps p \<longrightarrow> Primes.prime p) \<and> (\<forall>p. p < n \<and> Primes.prime p \<longrightarrow> List.member ps p)
134 yields Primes.prime n *)
135 fun is_prime :: "nat list \<Rightarrow> nat \<Rightarrow> bool" where
137 (if List.length ps > 0
139 if (n mod (List.hd ps)) = 0
141 else is_prime (List.tl ps) n
143 declare is_prime.simps [simp del] -- "make_primes, next_prime_not_dvd"
145 value "is_prime [2, 3] 2 = False" --"... precondition!"
146 value "is_prime [2, 3] 3 = False" --"... precondition!"
147 value "is_prime [2, 3] 4 = False"
148 value "is_prime [2, 3] 5 = True"
149 value "is_prime [2, 3, 5] 5 = False" --"... precondition!"
150 value "is_prime [2, 3] 6 = False"
151 value "is_prime [2, 3] 7 = True"
152 value "is_prime [2, 3] 25 = True" -- "... because 5 not in list"
154 (* make_primes is just local to primes_upto only:
155 make_primes :: int list \<Rightarrow> int \<Rightarrow> int \<Rightarrow> int list
156 make_primes ps last_p n = pps
157 assumes last_p = maxs ps \<and> (\<forall>p. List.member ps p \<longrightarrow> Primes.prime p) \<and>
158 (\<forall>p. p < last_p \<and> Primes.prime p \<longrightarrow> List.member ps p)
159 yields n \<le> maxs pps \<and> (\<forall>p. List.member pps p \<longrightarrow> Primes.prime p) \<and>
160 (\<forall>p. (p < maxs pps \<and> Primes.prime p) \<longrightarrow> List.member pps p)*)
161 function make_primes :: "nat list \<Rightarrow> nat \<Rightarrow> nat \<Rightarrow> nat list" where
162 "make_primes ps last_p n =
163 (if n <= last ps then ps else
164 if is_prime ps (last_p + 2)
165 then make_primes (ps @ [(last_p + 2)]) (last_p + 2) n
166 else make_primes ps (last_p + 2) n)"
167 by pat_completeness auto --"simp del: is_prime.simps <-- declare"
169 a) (ps, last_p, n) ~> (ps @ [last_p + 2], last_p + 2, n)
170 b) (ps, last_p, n) ~> (ps, last_p + 2, n)
172 1) \<lambda>p. size (snd (snd p)) --"n"
173 2) \<lambda>p. size (fst (snd p)) --"last_p"
174 3) \<lambda>p. size (snd p) --"(last_p, n)"
175 4) \<lambda>p. list_size size (fst p) --"ps"
176 5) \<lambda>p. length (fst p) --"ps"
181 b: <= ? <= <= <= <= *)
183 find_theorems "_ - _ < _ = _"
184 find_theorems "?n < ?n + _"
185 thm Rings.linordered_semidom_class.less_add_one --"?a < ?a + 1"
186 find_theorems "_ + ?a < _ + ?a = _"
187 thm Groups.ordered_ab_semigroup_add_imp_le_class.add_less_cancel_right
188 find_theorems "_ - ?a < _ - ?a = _"
189 thm Nat.less_diff_iff
191 lemma termin_1: "n - Suc (length ps) < n - length ps" (*? \<not> True ?*) sorry
193 termination make_primes (*by lexicographic_order +PROOF:2 GOLAS / size_change LOOPS*)
194 apply (relation "measures [\<lambda>(ps, last_p, n). n - (length ps),
195 \<lambda>(ps, last_p, n). n + 2 - last_p]")
197 (*\<lambda>(ps, last_p, n). last_p - (length ps):
199 1. \<And>ps last_p n. \<not> n \<le> last ps \<Longrightarrow> is_prime ps (Suc (Suc last_p)) \<Longrightarrow> \<not> Suc last_p - length ps < last_p - length ps \<Longrightarrow> Suc last_p - length ps = last_p - length ps
200 2. \<And>ps last_p n. \<not> n \<le> last ps \<Longrightarrow> is_prime ps (Suc (Suc last_p)) \<Longrightarrow> \<not> Suc last_p - length ps < last_p - length ps \<Longrightarrow> n - last_p < Suc (Suc n) - last_p
201 3. \<And>ps last_p n. \<not> n \<le> last ps \<Longrightarrow> \<not> is_prime ps (Suc (Suc last_p)) \<Longrightarrow> \<not> Suc (Suc last_p) - length ps < last_p - length ps \<Longrightarrow> Suc (Suc last_p) - length ps = last_p - length ps
202 4. \<And>ps last_p n. \<not> n \<le> last ps \<Longrightarrow> \<not> is_prime ps (Suc (Suc last_p)) \<Longrightarrow> \<not> Suc (Suc last_p) - length ps < last_p - length ps \<Longrightarrow> n - last_p < Suc (Suc n) - last_p
203 \<lambda>(ps, last_p, n). n - (length ps):
205 1. \<And>ps last_p n. \<not> n \<le> last ps \<Longrightarrow> is_prime ps (Suc (Suc last_p)) \<Longrightarrow> \<not> n - Suc (length ps) < n - length ps \<Longrightarrow> n - last_p < Suc (Suc n) - last_p
206 2. \<And>ps last_p n. \<not> n \<le> last ps \<Longrightarrow> \<not> is_prime ps (Suc (Suc last_p)) \<Longrightarrow> n - last_p < Suc (Suc n) - last_p*)
208 declare make_primes.simps [simp del] -- "next_prime_not_dvd"
210 value "make_primes [2, 3] 3 3 = [2, 3]"
211 value "make_primes [2, 3] 3 4 = [2, 3, 5]"
212 value "make_primes [2, 3] 3 5 = [2, 3, 5]"
213 value "make_primes [2, 3] 3 6 = [2, 3, 5, 7]"
214 value "make_primes [2, 3] 3 7 = [2, 3, 5, 7]"
215 value "make_primes [2, 3] 3 8 = [2, 3, 5, 7, 11]"
216 value "make_primes [2, 3] 3 9 = [2, 3, 5, 7, 11]"
217 value "make_primes [2, 3] 3 10 = [2, 3, 5, 7, 11]"
218 value "make_primes [2, 3] 3 11 = [2, 3, 5, 7, 11]"
219 value "make_primes [2, 3] 3 12 = [2, 3, 5, 7, 11, 13]"
220 value "make_primes [2, 3] 3 13 = [2, 3, 5, 7, 11, 13]"
221 value "make_primes [2, 3] 3 14 = [2, 3, 5, 7, 11, 13, 17]"
222 value "make_primes [2, 3] 3 15 = [2, 3, 5, 7, 11, 13, 17]"
223 value "make_primes [2, 3] 3 16 = [2, 3, 5, 7, 11, 13, 17]"
224 value "make_primes [2, 3] 3 17 = [2, 3, 5, 7, 11, 13, 17]"
225 value "make_primes [2, 3] 3 18 = [2, 3, 5, 7, 11, 13, 17, 19]"
226 value "make_primes [2, 3] 3 19 = [2, 3, 5, 7, 11, 13, 17, 19]"
227 value "make_primes [2, 3, 5, 7] 7 4 = [2, 3, 5, 7]"
229 (* primes_upto :: nat \<Rightarrow> nat list
232 yields (\<forall>p. List.member ps p \<longrightarrow> Primes.prime p) \<and>
233 n \<le> maxs ps \<and> maxs ps \<le> Fact.fact n + 1 \<and>
234 (\<forall>p. p \<le> maxs ps \<and> Primes.prime p \<longrightarrow> List.member ps p) *)
235 definition primes_upto :: "nat \<Rightarrow> nat list" where
236 "primes_upto n = (if n < 3 then [2] else make_primes [2, 3] 3 n)"
238 value "primes_upto 0 = [2]"
239 value "primes_upto 1 = [2]"
240 value "primes_upto 2 = [2]"
241 value "primes_upto 3 = [2, 3]"
242 value "primes_upto 4 = [2, 3, 5]"
243 value "primes_upto 5 = [2, 3, 5]"
244 value "primes_upto 6 = [2, 3, 5, 7]"
245 value "primes_upto 7 = [2, 3, 5, 7]"
246 value "primes_upto 8 = [2, 3, 5, 7, 11]"
247 value "primes_upto 9 = [2, 3, 5, 7, 11]"
248 value "primes_upto 10 = [2, 3, 5, 7, 11]"
249 value "primes_upto 11 = [2, 3, 5, 7, 11]"
251 lemma primes_upto_0: "last (primes_upto n) > 0" (*see above*) sorry
252 lemma primes_upto_1: "last (primes_upto (Suc n)) > n" (*see above*) sorry
253 lemma primes_upto_2: "last (primes_upto n) >= n" (*see above*) sorry
255 lemma termin_next_prime_not_dvd:
256 shows "last (primes_upto (Suc n1)) * q - last (primes_upto (Suc n1))
257 < last (primes_upto (Suc n1)) * q - n1"
259 from primes_upto_1 have "n1 < last (primes_upto (Suc n1))" by auto
260 from this have "(int n1) - (int (last (primes_upto (Suc n1)) * q))
261 < (int (last (primes_upto (Suc n1)))) - (int (last (primes_upto (Suc n1)) * q))" by auto
262 from this show ?thesis sorry
263 qed (*?FLORIAN : lifting nat -> int ?*)
266 find_theorems "_ - _ < _ - _ = _" thm Nat.less_diff_iff
267 find_theorems "_ * _ < _ * _ = _" thm Nat.Suc_mult_less_cancel1
268 find_theorems "-_ < -_ = _" thm Groups.ordered_ab_group_add_class.neg_less_iff_less
270 (* max's' is analogous to Integer.gcds *)
271 definition maxs :: "nat list \<Rightarrow> nat" where "maxs ns = List.fold max ns (List.hd ns)"
273 value "maxs [5, 3, 7, 1, 2, 4] = 7"
275 (* find the next prime greater p not dividing the number n:
276 next_prime_not_dvd :: int \<Rightarrow> int \<Rightarrow> int (infix)
277 n1 next_prime_not_dvd n2 = p
278 assumes True assumes "0 < q"
280 yields p is_prime \<and> n1 < p \<and> \<not> p dvd n2 \<and> (* smallest with these properties... *)
281 (\<forall> p'. (p' is_prime \<and> n1 < p' \<and> \<not> p' dvd n2) \<longrightarrow> p \<le> p') *)
282 function next_prime_not_dvd :: "nat \<Rightarrow> nat \<Rightarrow> nat" (infixl "next'_prime'_not'_dvd" 70) where
283 "n1 next_prime_not_dvd n2 =
285 ps = primes_upto (n1 + 1);
288 if n2 mod nxt \<noteq> 0
290 else nxt next_prime_not_dvd n2)"
291 by auto --"simp del: is_prime.simps, make_primes.simps, primes_upto.simps <-- declare"
292 termination (*next_prime_not_dvd: lexicographic_order +PROOF:?lifting nat-int? / size_change: Failed to apply initial proof method*)
293 apply (relation "measure (\<lambda>(n1, n2). n2 - n1)")
295 apply (rule termin_next_prime_not_dvd) (*?FLORIAN: IN Try_GCD... this is not necessary!?!+*)
298 value "1 next_prime_not_dvd 15 = 2"
299 value "2 next_prime_not_dvd 15 = 7"
300 value "3 next_prime_not_dvd 15 = 7"
301 value "4 next_prime_not_dvd 15 = 7"
302 value "5 next_prime_not_dvd 15 = 7"
303 value "6 next_prime_not_dvd 15 = 7"
304 value "7 next_prime_not_dvd 15 =11"
306 subsection {* basic notions for univariate polynomials *}
308 (* not in List.thy, copy from library.ML *)
309 fun nth_drop :: "nat \<Rightarrow> 'a list \<Rightarrow> 'a list" where
310 "nth_drop n xs = List.take n xs @ List.drop (n + 1) xs"
311 value "nth_drop 0 [] = []"
312 value "nth_drop 0 [1, 2, 3::int] = [2, 3]"
313 value "nth_drop 2 [1, 2, 3::int] = [1, 2]"
314 value "nth_drop 77 [1, 2, 3::int] = [1, 2, 3]"
316 (* leading coefficient *)
317 definition lcoeff_up :: "unipoly \<Rightarrow> int" where "lcoeff_up p = (last o drop_tl_zeros) p"
319 value "lcoeff_up [3, 4, 5, 6] = 6"
320 value "lcoeff_up [3, 4, 5, 6, 0] = 6"
322 (* drop leading coefficients equal 0 *)
323 (* THESE MAKE value "gcd_up [-1, 0 ,1] [0, 1, 1] = [1, 1]" LOOP
324 WHILE SML-VERSION WORKS: (*?FLORIAN*)
325 (**)definition drop_lc0_up :: "unipoly \<Rightarrow> unipoly" where
326 "drop_lc0_up p = drop_tl_zeros p"
327 (**)fun drop_lc0_up :: "unipoly \<Rightarrow> unipoly" where
328 "drop_lc0_up p = drop_tl_zeros p"
330 fun drop_lc0_up :: "unipoly \<Rightarrow> unipoly" where
331 "drop_lc0_up [] = []" |
333 (let l = List.length p - 1
336 then drop_lc0_up (nth_drop l p)
339 value "drop_lc0_up [0, 1, 2, 3, 4, 5, 0, 0] = [0, 1, 2, 3, 4, 5]"
340 value "drop_lc0_up [0, 1, 2, 3, 4, 5] = [0, 1, 2, 3, 4, 5]"
343 (* THE VERSIONS BELOW CREATE THE RESULT value "[-18,.." --> value "[-1,.." = [1]
344 ALTHOUGH THE TESTS BELOW SEEM TO WORK AND THE SAME CODE WORKS IN ML ?FLORIAN*)
346 (*function deg_up :: "unipoly \<Rightarrow> nat" where
347 "deg_up p = ((op - 1) o length o drop_lc0_up) p"
348 by auto termination sorry*)
350 (*fun deg_up :: "unipoly \<Rightarrow> nat" where
351 "deg_up p = ((op - 1) o length o drop_lc0_up) p"*)
353 (*definition deg_up :: "unipoly \<Rightarrow> nat" where
354 "deg_up p = ((op - 1) o length o drop_lc0_up) p"*)
356 function deg_up :: "unipoly \<Rightarrow> nat" where
358 (let len = List.length p - 1
360 if p ! len \<noteq> 0 then len else deg_up (nth_drop len p))"
361 by (*pat_completeness*) auto
366 shows "min a (a - Suc 0) < a"
368 from min_def have 1: "min a (a - Suc 0) = a - Suc 0" by auto
369 from `0 < a` have 2: "a - Suc 0 < a" by auto
370 from 1 2 show ?thesis by auto
373 find_theorems "min _ _ = (_::nat)"
374 find_theorems "min _ _ "
375 thm Orderings.ord_class.min_def --"min ?a ?b = (if ?a \<le> ?b then ?a else ?b)"
377 termination deg_up (*by lexicographic_order +PROOF:STRANGE GOAL+definition / by size_change: Failed to apply initial proof method*)
378 apply (relation "measure (\<lambda>(p). length p)")
380 (*..RELATED?: https://lists.cam.ac.uk/mailman/htdig/cl-isabelle-users/2013-May/msg00075.html*)
381 apply (rule min_Suc) (* 1. \<And>p. p ! (length p - Suc 0) = 0 \<Longrightarrow> 0 < length p*)
382 apply auto (*?????: 1. [] ! 0 = 0 \<Longrightarrow> False *)
385 find_theorems "nth _ _"
386 thm List.nth_mem (*?n < length ?xs \<Longrightarrow> ?xs ! ?n \<in> set ?xs*)
387 (*(length p - Suc 0) < length ?xs *)
388 thm List.set_conv_nth (*set ?xs = {?xs ! i |i. i < length ?xs}*)
389 find_theorems "set _" (*found 378 theorem(s)*)
390 find_theorems "length _" (*found 241 theorem(s)*)
392 value "[1,2,3,4,5::int] ! 2"
393 value "[1,2,3,4,5::int] ! 4"
395 value "([]::int list) ! 0"
400 1) list_size (nat \<circ> abs)
405 value "deg_up [3, 4, 5, 6] = 3"
406 value "deg_up [3, 4, 5, 6, 0] = 3"
407 value "deg_up [1, 0, 3, 0, 0] = 2"
409 (* norm is just local to normalise *)
410 fun norm :: "unipoly \<Rightarrow> unipoly \<Rightarrow> nat \<Rightarrow> int \<Rightarrow> nat \<Rightarrow> unipoly" where
411 "norm p nrm m lcp i =
413 then [int (mod_div (p ! i) lcp m)] @ nrm
414 else norm p ([int (mod_div (p ! i) lcp m)] @ nrm) m lcp (i - 1))"
415 (* normalise a unipoly such that lcoeff_up mod m = 1.
416 normalise :: unipoly \<Rightarrow> nat \<Rightarrow> unipoly
417 normalise [p_0, .., p_k] m = [q_0, .., q_k]
419 yields \<exists> t. 0 \<le> i \<le> k \<Rightarrow> (p_i * t) mod m = q_i \<and> (p_k * t) mod m = 1 *)
420 fun normalise :: "unipoly \<Rightarrow> nat \<Rightarrow> unipoly" where
426 if List.length p = 0 then [] else norm p [] m lcp (List.length p - 1))"
427 declare normalise.simps [simp del] --"HENSEL_lifting_up"
429 value "normalise [-18, -15, -20, 12, 20, -13, 2] 5 = [1, 0, 0, 1, 0, 1, 1]"
430 value "normalise [9, 6, 3] 10 = [3, 2, 1]"
432 subsection {* addition, multiplication, division *}
434 (* scalar multiplication *)
435 definition mult_ups :: "unipoly \<Rightarrow> int \<Rightarrow> unipoly" (infixl "%*" 70) where
436 "p %* m = List.map (op * m) p"
438 value "[5, 4, 7, 8, 1] %* 5 = [25, 20, 35, 40, 5]"
439 value "[5, 4, -7, 8, -1] %* 5 = [25, 20, -35, 40, -5]"
442 definition swapf :: "('a \<Rightarrow> 'b \<Rightarrow> 'c) \<Rightarrow> 'b \<Rightarrow> 'a \<Rightarrow> 'c" where "swapf f a b = f b a"
443 definition div_ups :: "unipoly \<Rightarrow> int \<Rightarrow> unipoly" (infixl "div'_ups" (* %/ error FLORIAN*) 70) where
444 "p div_ups m = map (swapf op div2 m) p"
446 value "[4, 3, 2, 5, 6] div_ups 3 = [1, 1, 0, 1, 2]"
447 value "[4, 3, 2, 0] div_ups 3 = [1, 1, 0, 0]"
449 (* not in List.thy, copy from library.ML *)
450 fun map2 :: "('a \<Rightarrow> 'b \<Rightarrow> 'c) \<Rightarrow> 'a list \<Rightarrow> 'b list \<Rightarrow> 'c list" where
451 "map2 _ [] [] = []" |
452 "map2 f (x # xs) (y # ys) = f x y # map2 f xs ys" |
453 "map2 _ _ _ = []" (*raise ListPair.UnequalLengths*)
456 definition minus_up :: "unipoly \<Rightarrow> unipoly \<Rightarrow> unipoly" (infixl "%-%" 70) where
457 "p1 %-% p2 = map2 (op -) p1 p2"
459 value "[8, -7, 0, 1] %-% [-2, 2, 3, 0] = [10, -9, -3, 1]"
460 value "[8, 7, 6, 5, 4] %-% [2, 2, 3, 1, 1] = [6, 5, 3, 4, 3]"
462 (* lemmata for pattern compatibility in dvd_up *)
463 lemma ex_falso_1: "([d], [p]) = (v # vb # vc, ps) \<Longrightarrow> QUODLIBET" by simp
464 lemma ex_falso_2: "([], ps) = (v # vb # vc, psa) \<Longrightarrow> QUODLIBET" by simp
465 lemma ex_falso_3: "(ds, []) = (dsa, v # vb # vc) \<Longrightarrow> QUODLIBET" by simp
467 function (sequential) dvd_up :: "unipoly \<Rightarrow> unipoly \<Rightarrow> bool" (infixl "%|%" 70) where
468 "[d] %|% [p] = ((\<bar>d\<bar> \<le> \<bar>p\<bar>) \<and> (p mod d = 0))" |
471 ds = drop_lc0_up ds; ps = drop_lc0_up ps;
472 d000 = (List.replicate (List.length ps - List.length ds) 0) @ ds;
473 quot = (lcoeff_up ps) div2 (lcoeff_up d000);
474 rest = drop_lc0_up (ps %-% (d000 %* quot))
476 if rest = [] then True else
477 if quot \<noteq> 0 \<and> List.length ds \<le> List.length rest then ds %|% rest else False)"
478 apply pat_completeness
481 defer (*a "mixed" obligation*)
483 defer (*a "mixed" obligation*)
485 defer (*a "mixed" obligation*)
488 apply simp (* > 1 sec IMPROVED BY declare simp del:
489 centr_up_def normalise.simps mod_up_gcd.simps lcoeff_up.simps*)
491 apply simp (* > 1 sec IMPROVED BY declare simp del:
492 centr_up_def normalise.simps mod_up_gcd.simps lcoeff_up.simps*)
494 defer (*a "mixed" obligation*)
495 apply simp (* > 1 sec IMPROVED BY declare simp del:
496 centr_up_def normalise.simps mod_up_gcd.simps lcoeff_up.simps*)
497 defer (*a "mixed" obligation*)
498 apply (rule ex_falso_1)
500 apply (rule ex_falso_2)
502 apply (rule ex_falso_3)
504 apply (rule ex_falso_1)
506 done (* > 1 sec IMPROVED BY declare simp del:
507 centr_up_def normalise.simps mod_up_gcd.simps lcoeff_up.simps*)
508 termination (*dvd_up: by lexicographic_order LOOPS +PROOF:5 HUGE GOALS/ size_change LOOPS*)
509 using [[linarith_split_limit = 999]]
510 apply (relation "measure (\<lambda>(ds, ps). length (let
511 ds = drop_lc0_up ds; ps = drop_lc0_up ps;
512 d000 = (List.replicate (List.length ps - List.length ds) 0) @ ds;
513 quot = (lcoeff_up ps) div2 (lcoeff_up d000);
514 rest = drop_lc0_up (ps %-% (d000 %* quot))
518 (*apply (relation "measure (\<lambda>(ds, ps). length ps - length ds)"):
519 1. wf (measure (\<lambda>(ds, ps). length ps - length ds))
520 2. \<And>ps x xa xb xc xd. x = drop_lc0_up [] \<Longrightarrow> xa = drop_lc0_up ps \<Longrightarrow> xb = replicate (length xa - length x) 0 @ x \<Longrightarrow> xc = lcoeff_up xa div2 lcoeff_up xb \<Longrightarrow> xd = drop_lc0_up (xa %-% (xb %* xc)) \<Longrightarrow> xd \<noteq> [] \<Longrightarrow> xc \<noteq> 0 \<and> length x \<le> length xd \<Longrightarrow> ((x, xd), [], ps) \<in> measure (\<lambda>(ds, ps). length ps - length ds)
521 3. \<And>v vb vc ps x xa xb xc xd. x = drop_lc0_up (v # vb # vc) \<Longrightarrow> xa = drop_lc0_up ps \<Longrightarrow> xb = replicate (length xa - length x) 0 @ x \<Longrightarrow> xc = lcoeff_up xa div2 lcoeff_up xb \<Longrightarrow> xd = drop_lc0_up (xa %-% (xb %* xc)) \<Longrightarrow> xd \<noteq> [] \<Longrightarrow> xc \<noteq> 0 \<and> length x \<le> length xd \<Longrightarrow> ((x, xd), v # vb # vc, ps) \<in> measure (\<lambda>(ds, ps). length ps - length ds)
522 4. \<And>ds x xa xb xc xd. x = drop_lc0_up ds \<Longrightarrow> xa = drop_lc0_up [] \<Longrightarrow> xb = replicate (length xa - length x) 0 @ x \<Longrightarrow> xc = lcoeff_up xa div2 lcoeff_up xb \<Longrightarrow> xd = drop_lc0_up (xa %-% (xb %* xc)) \<Longrightarrow> xd \<noteq> [] \<Longrightarrow> xc \<noteq> 0 \<and> length x \<le> length xd \<Longrightarrow> ((x, xd), ds, []) \<in> measure (\<lambda>(ds, ps). length ps - length ds)
523 5. \<And>ds v vb vc x xa xb xc xd. x = drop_lc0_up ds \<Longrightarrow> xa = drop_lc0_up (v # vb # vc) \<Longrightarrow> xb = replicate (length xa - length x) 0 @ x \<Longrightarrow> xc = lcoeff_up xa div2 lcoeff_up xb \<Longrightarrow> xd = drop_lc0_up (xa %-% (xb %* xc)) \<Longrightarrow> xd \<noteq> [] \<Longrightarrow> xc \<noteq> 0 \<and> length x \<le> length xd \<Longrightarrow> ((x, xd), ds, v # vb # vc) \<in> measure (\<lambda>(ds, ps). length ps - length ds)
525 6 subgoals, even longer
529 value "[4] %|% [6] = False"
530 value "[8] %|% [16, 0] = True"
531 value "[3, 2] %|% [0, 0, 9, 12, 4] = True"
532 value "[8, 0] %|% [16] = True"
534 subsection {* normalisation and Landau-Mignotte bound *}
536 (* centr is just local to centr_up *)
537 definition centr :: "nat \<Rightarrow> int \<Rightarrow> int \<Rightarrow> int" where
538 "centr m mid p_i = (if mid < p_i then p_i - (int m) else p_i)"
540 (* normalise :: centr_up \<Rightarrow> unipoly => int \<Rightarrow> unipoly
541 normalise [p_0, .., p_k] m = [q_0, .., q_k]
543 yields 0 \<le> i \<le> k \<Rightarrow> |^ ~m/2 ^| <= q_i <=|^ m/2 ^|
544 (where |^ x ^| means round x up to the next greater integer) *)
545 definition centr_up :: "unipoly \<Rightarrow> nat \<Rightarrow> unipoly" where
549 mid = if (int m) mod mi = 0 then mi else mi + 1
550 in map (centr m mid) p)"
552 value "centr_up [7, 3, 5, 8, 1, 3] 10 = [-3, 3, 5, -2, 1, 3]"
553 value "centr_up [1, 2, 3, 4, 5] 2 = [1, 0, 1, 2, 3]"
554 value "centr_up [1, 2, 3, 4, 5] 3 = [1, -1, 0, 1, 2]"
555 value "centr_up [1, 2, 3, 4, 5] 4 = [1, 2, -1, 0, 1]"
556 value "centr_up [1, 2, 3, 4, 5] 5 = [1, 2, 3, -1, 0]"
557 value "centr_up [1, 2, 3, 4, 5] 6 = [1, 2, 3, -2, -1]"
558 value "centr_up [1, 2, 3, 4, 5] 7 = [1, 2, 3, 4, -2]"
559 value "centr_up [1, 2, 3, 4, 5] 8 = [1, 2, 3, 4, -3]"
560 value "centr_up [1, 2, 3, 4, 5] 9 = [1, 2, 3, 4, 5]"
561 value "centr_up [1, 2, 3, 4, 5] 10 = [1, 2, 3, 4, 5]"
562 value "centr_up [1, 2, 3, 4, 5] 11 = [1, 2, 3, 4, 5]"
564 (* sum_lmb :: centr_up \<Rightarrow> unipoly \<Rightarrow> int \<Rightarrow> int
565 sum_lmb [p_0, .., p_k] e = s
567 yields. p_0^e + p_1^e + ... + p_k^e *)
568 definition sum_lmb :: "unipoly \<Rightarrow> nat \<Rightarrow> int" where
569 "sum_lmb p exp = List.fold ((op +) o (swapf power exp)) p 0"
571 value "sum_lmb [-1, 2, -3, 4, -5] 1 = -3"
572 value "sum_lmb [-1, 2, -3, 4, -5] 2 = 55"
573 value "sum_lmb [-1, 2, -3, 4, -5] 3 = -81"
574 value "sum_lmb [-1, 2, -3, 4, -5] 4 = 979"
575 value "sum_lmb [-1, 2, -3, 4, -5] 5 = -2313"
576 value "sum_lmb [-1, 2, -3, 4, -5] 6 = 20515"
578 (* LANDAU_MIGNOTTE_bound :: centr_up \<Rightarrow> unipoly => unipoly \<Rightarrow> int
579 LANDAU_MIGNOTTE_bound [a_0, ..., a_m] [b_0, .., b_n] = lmb
581 yields lmb = 2^min(m,n) * gcd(a_m,b_n) *
582 min( 1/|a_m| * root(sum_lmb [a_0,...a_m] 2 , 1/|b_n| * root(sum_lmb [b_0,...b_n] 2)*)
583 definition LANDAU_MIGNOTTE_bound :: "unipoly \<Rightarrow> unipoly \<Rightarrow> nat" where
584 "LANDAU_MIGNOTTE_bound p1 p2 =
585 ((power 2 (min (deg_up p1) (deg_up p2))) * (nat (gcd (lcoeff_up p1) (lcoeff_up p2))) *
586 (nat (min (abs ((int (approx_root (sum_lmb p1 2))) div2 -(lcoeff_up p1)))
587 (abs ((int (approx_root (sum_lmb p2 2))) div2 -(lcoeff_up p2))))))"
589 value "LANDAU_MIGNOTTE_bound [1] [4, 5] = 1"
590 value "LANDAU_MIGNOTTE_bound [1, 2] [4, 5] = 2"
591 value "LANDAU_MIGNOTTE_bound [1, 2, 3] [4, 5] = 2"
592 value "LANDAU_MIGNOTTE_bound [1, 2, 3] [4] = 1"
593 value "LANDAU_MIGNOTTE_bound [1, 2, 3] [4, 5] = 2"
594 value "LANDAU_MIGNOTTE_bound [1, 2, 3] [4, 5, 6] = 12"
596 value "LANDAU_MIGNOTTE_bound [-1] [4, 5] = 1"
597 value "LANDAU_MIGNOTTE_bound [-1, 2] [4, 5] = 2"
598 value "LANDAU_MIGNOTTE_bound [-1, 2, -3] [4, -5] = 2"
599 value "LANDAU_MIGNOTTE_bound [-1, 2, -3] [4] = 1"
600 value "LANDAU_MIGNOTTE_bound [-1, 2, -3] [4, -5] = 2"
601 value "LANDAU_MIGNOTTE_bound [-1, 2, -3] [4, -5, 6] = 12"
603 subsection {* modulo calculations for polynomials *}
605 (* pair is just local to chinese_remainder_up, is "op ~~" in library.ML *)
606 fun pair :: "unipoly \<Rightarrow> unipoly \<Rightarrow> ((int \<times> int) list)" (infix "pair" 4) where
607 "([] pair []) = []" |
608 "([] pair ys) = []" | (*raise ListPair.UnequalLengths*)
609 "(xs pair []) = []" | (*raise ListPair.UnequalLengths*)
610 "((x#xs) pair (y#ys)) = (x, y) # (xs pair ys)"
611 fun chinese_rem :: "nat \<times> nat \<Rightarrow> int \<times> int \<Rightarrow> int" where
612 "chinese_rem (m1, m2) (p1, p2) = (int (chinese_remainder p1 m1 p2 m2))"
614 (* chinese_remainder_up :: int * int \<Rightarrow> unipoly * unipoly \<Rightarrow> unipoly
615 chinese_remainder_up (m1, m2) (p1, p2) = p
616 assume m1, m2 relatively prime
617 yields p1 = p mod m1 \<and> p2 = p mod m2 *)
618 fun chinese_remainder_up :: "nat \<times> nat \<Rightarrow> unipoly \<times> unipoly \<Rightarrow> unipoly" where
619 "chinese_remainder_up (m1, m2) (p1, p2) = map (chinese_rem (m1, m2)) (p1 pair p2)"
621 value "chinese_remainder_up (5, 7) ([2, 2, 4, 3], [3, 2, 3, 5]) = [17, 2, 24, 33]"
623 (* mod_up :: unipoly \<Rightarrow> int \<Rightarrow> unipoly
624 mod_up [p1, p2, ..., pk] m = up
626 yields up = [p1 mod m, p2 mod m, ..., pk mod m]*)
627 definition mod' :: "nat \<Rightarrow> int \<Rightarrow> int" where "mod' m i = i mod (int m)"
628 definition mod_up :: "unipoly \<Rightarrow> nat \<Rightarrow> unipoly" (infixl "mod'_up" 70) where
629 "p mod_up m = map (mod' m) p"
631 value "[5, 4, 7, 8, 1] mod_up 5 = [0, 4, 2, 3, 1]"
632 value "[5, 4,-7, 8,-1] mod_up 5 = [0, 4, 3, 3, 4]"
634 (* euclidean algoritm in Z_p[x/m].
635 mod_up_gcd :: unipoly \<Rightarrow> unipoly \<Rightarrow> nat \<Rightarrow> unipoly
636 mod_up_gcd p1 p2 m = g
638 yields gcd (p1 mod m) (p2 mod m) = g *)
639 function mod_up_gcd :: "unipoly \<Rightarrow> unipoly \<Rightarrow> nat \<Rightarrow> unipoly" where
640 "mod_up_gcd p1 p2 m =
643 p2m = drop_lc0_up (p2 mod_up m);
644 p2n = (replicate (List.length p1 - List.length p2m) 0) @ p2m;
645 quot = mod_div (lcoeff_up p1m) (lcoeff_up p2n) m;
646 rest = drop_lc0_up ((p1m %-% (p2n %* (int quot))) mod_up m)
648 if rest = [] then p2 else
649 if List.length rest < List.length p2
650 then mod_up_gcd p2 rest m
651 else mod_up_gcd rest p2 m)"
653 termination mod_up_gcd (*by lexicographic_order +PROOF:3 HUGE SUGOALS / size_change LOOPS*)
654 apply (relation "measures [\<lambda>(p1, p2, m). length p2 - length (let
656 p2m = drop_lc0_up (p2 mod_up m);
657 p2n = (replicate (List.length p1 - List.length p2m) 0) @ p2m;
658 quot = mod_div (lcoeff_up p1m) (lcoeff_up p2n) m;
659 rest = drop_lc0_up ((p1m %-% (p2n %* (int quot))) mod_up m)
661 \<lambda>(p1, p2, m). length p1 - length (let
663 p2m = drop_lc0_up (p2 mod_up m);
664 p2n = (replicate (List.length p1 - List.length p2m) 0) @ p2m;
665 quot = mod_div (lcoeff_up p1m) (lcoeff_up p2n) m;
666 rest = drop_lc0_up ((p1m %-% (p2n %* (int quot))) mod_up m)
668 (*apply auto ..LOOPS*)
671 a) (p1, p2, m) ~> (p2, xab, m)
672 b) (p1, p2, m) ~> (xab, p2, m)
674 1) \<lambda>p. size (snd (snd p)) m
675 2) \<lambda>p. list_size (nat \<circ> abs) (fst (snd p)) p2 ?(nat \<circ> abs) ...coeff?!?
676 3) \<lambda>p. length (fst (snd p)) p2
677 4) \<lambda>p. size (snd p) (p2, m)
678 5) \<lambda>p. list_size (nat \<circ> abs) (fst p) p1 ?(nat \<circ> abs) ...coeff?!?
679 6) \<lambda>p. length (fst p) p1
684 b: <= <= <= <= ? ? <= *)
685 declare mod_up_gcd.simps [simp del] --"HENSEL_lifting_up"
687 value "mod_up_gcd [-18, -15, -20, 12, 20, -13, 2] [8, 28, 22, -11, -14, 1, 2] 7 = [2, 6, 0, 2, 6]"
688 value "mod_up_gcd [8, 28, 22, -11, -14, 1, 2] [2, 6, 0, 2, 6] 7 = [2, 6, 0, 2, 6]"
689 value "mod_up_gcd [20, 15, 8, 6] [8, -2, -2, 3] 2 = [0, 1]"
690 value "[20, 15, 8, 6] %|% [0, 1] = False"
691 value "[8, -2, -2, 3] %|% [0, 1] = False"
693 (* analogous to Integer.gcds
694 gcds :: int list \<Rightarrow> int
697 yields THE d. ((\<forall>n. List.member ns n \<longrightarrow> d dvd n) \<and>
698 (\<forall>d'. (\<forall>n. List.member ns n \<and> d' dvd n) \<longrightarrow> d'modp \<le> d)) *)
699 fun gcds :: "int list \<Rightarrow> int" where "gcds ns = List.fold gcd ns (List.hd ns)"
701 value "gcds [6, 9, 12] = 3"
702 value "gcds [6, -9, 12] = 3"
703 value "gcds [8, 12, 16] = 4"
704 value "gcds [-8, 12, -16] = 4"
706 (* prim_poly :: unipoly \<Rightarrow> unipoly
709 yields \<forall>p1, p2. (List.member pp p1 \<and> List.member pp p2 \<and> p1 \<noteq> p2) \<longrightarrow> gcd p1 p2 = 1 *)
710 fun primitive_up :: "unipoly \<Rightarrow> unipoly" where
711 "primitive_up [c] = (if c = 0 then [0] else [1])" |
715 if d = 1 then p else p div_ups d)"
717 value "primitive_up [12, 16, 32, 44] = [3, 4, 8, 11]"
718 value "primitive_up [4, 5, 12] = [4, 5, 12]"
719 value "primitive_up [0] = [0]"
720 value "primitive_up [6] = [1]"
722 subsection {* gcd_up, code from [1] p.93 *}
723 (* try_new_prime_up :: unipoly \<Rightarrow> unipoly \<Rightarrow> int \<Rightarrow> int \<Rightarrow> int \<Rightarrow> unipoly \<Rightarrow> int \<Rightarrow> unipoly
724 try_new_prime_up p1 p2 d M P g p = new_g
725 assumes d = gcd (lcoeff_up p1, lcoeff_up p2) \<and>
726 M = LANDAU_MIGNOTTE_bound \<and> p = prime \<and> p ~| d \<and> P \<ge> p \<and>
727 p1 is primitive \<and> p2 is primitive
728 yields new_g = [1] \<or> (new_g \<ge> g \<and> P > M)
730 argumentns "a b d M P g p" named according to [1] p.93: "p" is "prime", not "poly" ! *)
731 function try_new_prime_up :: "unipoly \<Rightarrow> unipoly \<Rightarrow> nat \<Rightarrow> nat \<Rightarrow> nat \<Rightarrow> unipoly \<Rightarrow> nat \<Rightarrow> unipoly"
733 "try_new_prime_up a b d M P g p =
734 (if P > M then g else
735 let p = p next_prime_not_dvd d;
736 g_p = centr_up ( ( (normalise (mod_up_gcd a b p) p)
741 if deg_up g_p < deg_up g
743 if (deg_up g_p) = 0 then [1] else try_new_prime_up a b d M p g_p p
745 if deg_up g_p \<noteq> deg_up g then try_new_prime_up a b d M P g p else
748 g = centr_up ((chinese_remainder_up (P, p) (g, g_p)) mod_up P) P
749 in try_new_prime_up a b d M P g p)"
750 by pat_completeness auto --"simp del: centr_up_def normalise.simps mod_up_gcd.simps"
751 termination try_new_prime_up (*by lexicographic_order LOOPS +PROOF:? / by size_change LOOPS*)
752 (*apply (relation "measures
753 [\<lambda>(a, b, d, M, P, g, p). ???,
754 \<lambda>(a, b, d, M, P, g, p). ???,
755 \<lambda>(a, b, d, M, P, g, p). ???]")
757 a) (a, b, d, M, P, g, p) ~> (a, b, d, M, p, g_p {length g_p <= length a b}, p' {> p})
758 b) (a, b, d, M, P, g, p) ~> (a, b, d, M, P, g , p' {> p})
759 c) (a, b, d, M, P, g, p) ~> (a, b, d, M, P {=P*p'}, g {length g <= length a b}, p' {> p})
763 (* HENSEL_lifting_up :: unipoly \<Rightarrow> unipoly \<Rightarrow> int \<Rightarrow> int \<Rightarrow> int \<Rightarrow> unipoly
764 HENSEL_lifting_up p1 p2 d M p = gcd
765 assumes d = gcd (lcoeff_up p1, lcoeff_up p2) \<and>
766 M = LANDAU_MIGNOTTE_bound \<and> p = prime \<and> p ~| d \<and>
767 p1 is primitive \<and> p2 is primitive
768 yields gcd | p1 \<and> gcd | p2 \<and> gcd is primitive
770 argumentns "a b d M p" named according to [1] p.93: "p" is "prime", not "poly" ! *)
771 function HENSEL_lifting_up :: "unipoly \<Rightarrow> unipoly \<Rightarrow> nat \<Rightarrow> nat \<Rightarrow> nat \<Rightarrow> unipoly" where
772 "HENSEL_lifting_up a b d M p =
774 p = p next_prime_not_dvd d;
775 g_p = centr_up (((normalise (mod_up_gcd a b p) p) %* (int (d mod p))) mod_up p) p (*see above*)
777 if deg_up g_p = 0 then [1] else
779 g = primitive_up (try_new_prime_up a b d M p g_p p)
781 if (g %|% a) \<and> (g %|% b) then g else HENSEL_lifting_up a b d M p))"
782 by pat_completeness auto --"simp del: centr_up_def normalise.simps mod_up_gcd.simps"
783 termination HENSEL_lifting_up (*by lexicographic_order LOOPS +PROOF:?next_prime_not_dvd / by size_change LOOPS*)
786 a) (a, b, d, M, p) ~> (a, b, d, M, p {> p next_prime_not_dvd d})
789 (* gcd_up :: unipoly \<Rightarrow> unipoly \<Rightarrow> unipoly
791 assumes not (a = [] \<or> a = [0]) \<and> not (b = []\<or> b = [0]) \<and>
792 a is primitive \<and> b is primitive
793 yields c dvd a \<and> c dvd b \<and> (\<forall>c'. (c' dvd a \<and> c' dvd b) \<longrightarrow> c' \<le> c) *)
794 function gcd_up :: "unipoly \<Rightarrow> unipoly \<Rightarrow> unipoly" where
796 (let d = \<bar>gcd (lcoeff_up a) (lcoeff_up b)\<bar>
799 HENSEL_lifting_up a b (nat d) (2 * (nat d) * LANDAU_MIGNOTTE_bound a b) 1)"
800 by pat_completeness auto --"simp del: lcoeff_up.simps ?+ others?"
801 termination by lexicographic_order (*works*)
803 value "gcd_up [-18, -15, -20, 12, 20, -13, 2] [8, 28, 22, -11, -14, 1, 2] = [-2, -1, 1]"
804 (* gcd (-1 + x^2) (x + x^2) = (1 + x) ...*)
805 value "gcd_up [-1, 0 ,1] [0, 1, 1] = [1, 1]"
809 declare [[simp_trace_depth_limit = 99]]
810 declare [[simp_trace = true]]
812 using [[simp_trace_depth_limit = 99]]
813 using [[simp_trace = true]]