Coverage for /usr/lib/python3/dist-packages/sympy/polys/numberfields/galoisgroups.py: 12%
225 statements
« prev ^ index » next coverage.py v7.9.1, created at 2025-06-14 15:55 +0200
1"""
2Compute Galois groups of polynomials.
4We use algorithms from [1], with some modifications to use lookup tables for
5resolvents.
7References
8==========
10.. [1] Cohen, H. *A Course in Computational Algebraic Number Theory*.
12"""
14from collections import defaultdict
15import random
17from sympy.core.symbol import Dummy, symbols
18from sympy.ntheory.primetest import is_square
19from sympy.polys.domains import ZZ
20from sympy.polys.densebasic import dup_random
21from sympy.polys.densetools import dup_eval
22from sympy.polys.euclidtools import dup_discriminant
23from sympy.polys.factortools import dup_factor_list, dup_irreducible_p
24from sympy.polys.numberfields.galois_resolvents import (
25 GaloisGroupException, get_resolvent_by_lookup, define_resolvents,
26 Resolvent,
27)
28from sympy.polys.numberfields.utilities import coeff_search
29from sympy.polys.polytools import (Poly, poly_from_expr,
30 PolificationFailed, ComputationFailed)
31from sympy.polys.sqfreetools import dup_sqf_p
32from sympy.utilities import public
35class MaxTriesException(GaloisGroupException):
36 ...
39def tschirnhausen_transformation(T, max_coeff=10, max_tries=30, history=None,
40 fixed_order=True):
41 r"""
42 Given a univariate, monic, irreducible polynomial over the integers, find
43 another such polynomial defining the same number field.
45 Explanation
46 ===========
48 See Alg 6.3.4 of [1].
50 Parameters
51 ==========
53 T : Poly
54 The given polynomial
55 max_coeff : int
56 When choosing a transformation as part of the process,
57 keep the coeffs between plus and minus this.
58 max_tries : int
59 Consider at most this many transformations.
60 history : set, None, optional (default=None)
61 Pass a set of ``Poly.rep``'s in order to prevent any of these
62 polynomials from being returned as the polynomial ``U`` i.e. the
63 transformation of the given polynomial *T*. The given poly *T* will
64 automatically be added to this set, before we try to find a new one.
65 fixed_order : bool, default True
66 If ``True``, work through candidate transformations A(x) in a fixed
67 order, from small coeffs to large, resulting in deterministic behavior.
68 If ``False``, the A(x) are chosen randomly, while still working our way
69 up from small coefficients to larger ones.
71 Returns
72 =======
74 Pair ``(A, U)``
76 ``A`` and ``U`` are ``Poly``, ``A`` is the
77 transformation, and ``U`` is the transformed polynomial that defines
78 the same number field as *T*. The polynomial ``A`` maps the roots of
79 *T* to the roots of ``U``.
81 Raises
82 ======
84 MaxTriesException
85 if could not find a polynomial before exceeding *max_tries*.
87 """
88 X = Dummy('X')
89 n = T.degree()
90 if history is None:
91 history = set()
92 history.add(T.rep)
94 if fixed_order:
95 coeff_generators = {}
96 deg_coeff_sum = 3
97 current_degree = 2
99 def get_coeff_generator(degree):
100 gen = coeff_generators.get(degree, coeff_search(degree, 1))
101 coeff_generators[degree] = gen
102 return gen
104 for i in range(max_tries):
106 # We never use linear A(x), since applying a fixed linear transformation
107 # to all roots will only multiply the discriminant of T by a square
108 # integer. This will change nothing important. In particular, if disc(T)
109 # was zero before, it will still be zero now, and typically we apply
110 # the transformation in hopes of replacing T by a squarefree poly.
112 if fixed_order:
113 # If d is degree and c max coeff, we move through the dc-space
114 # along lines of constant sum. First d + c = 3 with (d, c) = (2, 1).
115 # Then d + c = 4 with (d, c) = (3, 1), (2, 2). Then d + c = 5 with
116 # (d, c) = (4, 1), (3, 2), (2, 3), and so forth. For a given (d, c)
117 # we go though all sets of coeffs where max = c, before moving on.
118 gen = get_coeff_generator(current_degree)
119 coeffs = next(gen)
120 m = max(abs(c) for c in coeffs)
121 if current_degree + m > deg_coeff_sum:
122 if current_degree == 2:
123 deg_coeff_sum += 1
124 current_degree = deg_coeff_sum - 1
125 else:
126 current_degree -= 1
127 gen = get_coeff_generator(current_degree)
128 coeffs = next(gen)
129 a = [ZZ(1)] + [ZZ(c) for c in coeffs]
131 else:
132 # We use a progressive coeff bound, up to the max specified, since it
133 # is preferable to succeed with smaller coeffs.
134 # Give each coeff bound five tries, before incrementing.
135 C = min(i//5 + 1, max_coeff)
136 d = random.randint(2, n - 1)
137 a = dup_random(d, -C, C, ZZ)
139 A = Poly(a, T.gen)
140 U = Poly(T.resultant(X - A), X)
141 if U.rep not in history and dup_sqf_p(U.rep.rep, ZZ):
142 return A, U
143 raise MaxTriesException
146def has_square_disc(T):
147 """Convenience to check if a Poly or dup has square discriminant. """
148 d = T.discriminant() if isinstance(T, Poly) else dup_discriminant(T, ZZ)
149 return is_square(d)
152def _galois_group_degree_3(T, max_tries=30, randomize=False):
153 r"""
154 Compute the Galois group of a polynomial of degree 3.
156 Explanation
157 ===========
159 Uses Prop 6.3.5 of [1].
161 """
162 from sympy.combinatorics.galois import S3TransitiveSubgroups
163 return ((S3TransitiveSubgroups.A3, True) if has_square_disc(T)
164 else (S3TransitiveSubgroups.S3, False))
167def _galois_group_degree_4_root_approx(T, max_tries=30, randomize=False):
168 r"""
169 Compute the Galois group of a polynomial of degree 4.
171 Explanation
172 ===========
174 Follows Alg 6.3.7 of [1], using a pure root approximation approach.
176 """
177 from sympy.combinatorics.permutations import Permutation
178 from sympy.combinatorics.galois import S4TransitiveSubgroups
180 X = symbols('X0 X1 X2 X3')
181 # We start by considering the resolvent for the form
182 # F = X0*X2 + X1*X3
183 # and the group G = S4. In this case, the stabilizer H is D4 = < (0123), (02) >,
184 # and a set of representatives of G/H is {I, (01), (03)}
185 F1 = X[0]*X[2] + X[1]*X[3]
186 s1 = [
187 Permutation(3),
188 Permutation(3)(0, 1),
189 Permutation(3)(0, 3)
190 ]
191 R1 = Resolvent(F1, X, s1)
193 # In the second half of the algorithm (if we reach it), we use another
194 # form and set of coset representatives. However, we may need to permute
195 # them first, so cannot form their resolvent now.
196 F2_pre = X[0]*X[1]**2 + X[1]*X[2]**2 + X[2]*X[3]**2 + X[3]*X[0]**2
197 s2_pre = [
198 Permutation(3),
199 Permutation(3)(0, 2)
200 ]
202 history = set()
203 for i in range(max_tries):
204 if i > 0:
205 # If we're retrying, need a new polynomial T.
206 _, T = tschirnhausen_transformation(T, max_tries=max_tries,
207 history=history,
208 fixed_order=not randomize)
210 R_dup, _, i0 = R1.eval_for_poly(T, find_integer_root=True)
211 # If R is not squarefree, must retry.
212 if not dup_sqf_p(R_dup, ZZ):
213 continue
215 # By Prop 6.3.1 of [1], Gal(T) is contained in A4 iff disc(T) is square.
216 sq_disc = has_square_disc(T)
218 if i0 is None:
219 # By Thm 6.3.3 of [1], Gal(T) is not conjugate to any subgroup of the
220 # stabilizer H = D4 that we chose. This means Gal(T) is either A4 or S4.
221 return ((S4TransitiveSubgroups.A4, True) if sq_disc
222 else (S4TransitiveSubgroups.S4, False))
224 # Gal(T) is conjugate to a subgroup of H = D4, so it is either V, C4
225 # or D4 itself.
227 if sq_disc:
228 # Neither C4 nor D4 is contained in A4, so Gal(T) must be V.
229 return (S4TransitiveSubgroups.V, True)
231 # Gal(T) can only be D4 or C4.
232 # We will now use our second resolvent, with G being that conjugate of D4 that
233 # Gal(T) is contained in. To determine the right conjugate, we will need
234 # the permutation corresponding to the integer root we found.
235 sigma = s1[i0]
236 # Applying sigma means permuting the args of F, and
237 # conjugating the set of coset representatives.
238 F2 = F2_pre.subs(zip(X, sigma(X)), simultaneous=True)
239 s2 = [sigma*tau*sigma for tau in s2_pre]
240 R2 = Resolvent(F2, X, s2)
241 R_dup, _, _ = R2.eval_for_poly(T)
242 d = dup_discriminant(R_dup, ZZ)
243 # If d is zero (R has a repeated root), must retry.
244 if d == 0:
245 continue
246 if is_square(d):
247 return (S4TransitiveSubgroups.C4, False)
248 else:
249 return (S4TransitiveSubgroups.D4, False)
251 raise MaxTriesException
254def _galois_group_degree_4_lookup(T, max_tries=30, randomize=False):
255 r"""
256 Compute the Galois group of a polynomial of degree 4.
258 Explanation
259 ===========
261 Based on Alg 6.3.6 of [1], but uses resolvent coeff lookup.
263 """
264 from sympy.combinatorics.galois import S4TransitiveSubgroups
266 history = set()
267 for i in range(max_tries):
268 R_dup = get_resolvent_by_lookup(T, 0)
269 if dup_sqf_p(R_dup, ZZ):
270 break
271 _, T = tschirnhausen_transformation(T, max_tries=max_tries,
272 history=history,
273 fixed_order=not randomize)
274 else:
275 raise MaxTriesException
277 # Compute list L of degrees of irreducible factors of R, in increasing order:
278 fl = dup_factor_list(R_dup, ZZ)
279 L = sorted(sum([
280 [len(r) - 1] * e for r, e in fl[1]
281 ], []))
283 if L == [6]:
284 return ((S4TransitiveSubgroups.A4, True) if has_square_disc(T)
285 else (S4TransitiveSubgroups.S4, False))
287 if L == [1, 1, 4]:
288 return (S4TransitiveSubgroups.C4, False)
290 if L == [2, 2, 2]:
291 return (S4TransitiveSubgroups.V, True)
293 assert L == [2, 4]
294 return (S4TransitiveSubgroups.D4, False)
297def _galois_group_degree_5_hybrid(T, max_tries=30, randomize=False):
298 r"""
299 Compute the Galois group of a polynomial of degree 5.
301 Explanation
302 ===========
304 Based on Alg 6.3.9 of [1], but uses a hybrid approach, combining resolvent
305 coeff lookup, with root approximation.
307 """
308 from sympy.combinatorics.galois import S5TransitiveSubgroups
309 from sympy.combinatorics.permutations import Permutation
311 X5 = symbols("X0,X1,X2,X3,X4")
312 res = define_resolvents()
313 F51, _, s51 = res[(5, 1)]
314 F51 = F51.as_expr(*X5)
315 R51 = Resolvent(F51, X5, s51)
317 history = set()
318 reached_second_stage = False
319 for i in range(max_tries):
320 if i > 0:
321 _, T = tschirnhausen_transformation(T, max_tries=max_tries,
322 history=history,
323 fixed_order=not randomize)
324 R51_dup = get_resolvent_by_lookup(T, 1)
325 if not dup_sqf_p(R51_dup, ZZ):
326 continue
328 # First stage
329 # If we have not yet reached the second stage, then the group still
330 # might be S5, A5, or M20, so must test for that.
331 if not reached_second_stage:
332 sq_disc = has_square_disc(T)
334 if dup_irreducible_p(R51_dup, ZZ):
335 return ((S5TransitiveSubgroups.A5, True) if sq_disc
336 else (S5TransitiveSubgroups.S5, False))
338 if not sq_disc:
339 return (S5TransitiveSubgroups.M20, False)
341 # Second stage
342 reached_second_stage = True
343 # R51 must have an integer root for T.
344 # To choose our second resolvent, we need to know which conjugate of
345 # F51 is a root.
346 rounded_roots = R51.round_roots_to_integers_for_poly(T)
347 # These are integers, and candidates to be roots of R51.
348 # We find the first one that actually is a root.
349 for permutation_index, candidate_root in rounded_roots.items():
350 if not dup_eval(R51_dup, candidate_root, ZZ):
351 break
353 X = X5
354 F2_pre = X[0]*X[1]**2 + X[1]*X[2]**2 + X[2]*X[3]**2 + X[3]*X[4]**2 + X[4]*X[0]**2
355 s2_pre = [
356 Permutation(4),
357 Permutation(4)(0, 1)(2, 4)
358 ]
360 i0 = permutation_index
361 sigma = s51[i0]
362 F2 = F2_pre.subs(zip(X, sigma(X)), simultaneous=True)
363 s2 = [sigma*tau*sigma for tau in s2_pre]
364 R2 = Resolvent(F2, X, s2)
365 R_dup, _, _ = R2.eval_for_poly(T)
366 d = dup_discriminant(R_dup, ZZ)
368 if d == 0:
369 continue
370 if is_square(d):
371 return (S5TransitiveSubgroups.C5, True)
372 else:
373 return (S5TransitiveSubgroups.D5, True)
375 raise MaxTriesException
378def _galois_group_degree_5_lookup_ext_factor(T, max_tries=30, randomize=False):
379 r"""
380 Compute the Galois group of a polynomial of degree 5.
382 Explanation
383 ===========
385 Based on Alg 6.3.9 of [1], but uses resolvent coeff lookup, plus
386 factorization over an algebraic extension.
388 """
389 from sympy.combinatorics.galois import S5TransitiveSubgroups
391 _T = T
393 history = set()
394 for i in range(max_tries):
395 R_dup = get_resolvent_by_lookup(T, 1)
396 if dup_sqf_p(R_dup, ZZ):
397 break
398 _, T = tschirnhausen_transformation(T, max_tries=max_tries,
399 history=history,
400 fixed_order=not randomize)
401 else:
402 raise MaxTriesException
404 sq_disc = has_square_disc(T)
406 if dup_irreducible_p(R_dup, ZZ):
407 return ((S5TransitiveSubgroups.A5, True) if sq_disc
408 else (S5TransitiveSubgroups.S5, False))
410 if not sq_disc:
411 return (S5TransitiveSubgroups.M20, False)
413 # If we get this far, Gal(T) can only be D5 or C5.
414 # But for Gal(T) to have order 5, T must already split completely in
415 # the extension field obtained by adjoining a single one of its roots.
416 fl = Poly(_T, domain=ZZ.alg_field_from_poly(_T)).factor_list()[1]
417 if len(fl) == 5:
418 return (S5TransitiveSubgroups.C5, True)
419 else:
420 return (S5TransitiveSubgroups.D5, True)
423def _galois_group_degree_6_lookup(T, max_tries=30, randomize=False):
424 r"""
425 Compute the Galois group of a polynomial of degree 6.
427 Explanation
428 ===========
430 Based on Alg 6.3.10 of [1], but uses resolvent coeff lookup.
432 """
433 from sympy.combinatorics.galois import S6TransitiveSubgroups
435 # First resolvent:
437 history = set()
438 for i in range(max_tries):
439 R_dup = get_resolvent_by_lookup(T, 1)
440 if dup_sqf_p(R_dup, ZZ):
441 break
442 _, T = tschirnhausen_transformation(T, max_tries=max_tries,
443 history=history,
444 fixed_order=not randomize)
445 else:
446 raise MaxTriesException
448 fl = dup_factor_list(R_dup, ZZ)
450 # Group the factors by degree.
451 factors_by_deg = defaultdict(list)
452 for r, _ in fl[1]:
453 factors_by_deg[len(r) - 1].append(r)
455 L = sorted(sum([
456 [d] * len(ff) for d, ff in factors_by_deg.items()
457 ], []))
459 T_has_sq_disc = has_square_disc(T)
461 if L == [1, 2, 3]:
462 f1 = factors_by_deg[3][0]
463 return ((S6TransitiveSubgroups.C6, False) if has_square_disc(f1)
464 else (S6TransitiveSubgroups.D6, False))
466 elif L == [3, 3]:
467 f1, f2 = factors_by_deg[3]
468 any_square = has_square_disc(f1) or has_square_disc(f2)
469 return ((S6TransitiveSubgroups.G18, False) if any_square
470 else (S6TransitiveSubgroups.G36m, False))
472 elif L == [2, 4]:
473 if T_has_sq_disc:
474 return (S6TransitiveSubgroups.S4p, True)
475 else:
476 f1 = factors_by_deg[4][0]
477 return ((S6TransitiveSubgroups.A4xC2, False) if has_square_disc(f1)
478 else (S6TransitiveSubgroups.S4xC2, False))
480 elif L == [1, 1, 4]:
481 return ((S6TransitiveSubgroups.A4, True) if T_has_sq_disc
482 else (S6TransitiveSubgroups.S4m, False))
484 elif L == [1, 5]:
485 return ((S6TransitiveSubgroups.PSL2F5, True) if T_has_sq_disc
486 else (S6TransitiveSubgroups.PGL2F5, False))
488 elif L == [1, 1, 1, 3]:
489 return (S6TransitiveSubgroups.S3, False)
491 assert L == [6]
493 # Second resolvent:
495 history = set()
496 for i in range(max_tries):
497 R_dup = get_resolvent_by_lookup(T, 2)
498 if dup_sqf_p(R_dup, ZZ):
499 break
500 _, T = tschirnhausen_transformation(T, max_tries=max_tries,
501 history=history,
502 fixed_order=not randomize)
503 else:
504 raise MaxTriesException
506 T_has_sq_disc = has_square_disc(T)
508 if dup_irreducible_p(R_dup, ZZ):
509 return ((S6TransitiveSubgroups.A6, True) if T_has_sq_disc
510 else (S6TransitiveSubgroups.S6, False))
511 else:
512 return ((S6TransitiveSubgroups.G36p, True) if T_has_sq_disc
513 else (S6TransitiveSubgroups.G72, False))
516@public
517def galois_group(f, *gens, by_name=False, max_tries=30, randomize=False, **args):
518 r"""
519 Compute the Galois group for polynomials *f* up to degree 6.
521 Examples
522 ========
524 >>> from sympy import galois_group
525 >>> from sympy.abc import x
526 >>> f = x**4 + 1
527 >>> G, alt = galois_group(f)
528 >>> print(G)
529 PermutationGroup([
530 (0 1)(2 3),
531 (0 2)(1 3)])
533 The group is returned along with a boolean, indicating whether it is
534 contained in the alternating group $A_n$, where $n$ is the degree of *T*.
535 Along with other group properties, this can help determine which group it
536 is:
538 >>> alt
539 True
540 >>> G.order()
541 4
543 Alternatively, the group can be returned by name:
545 >>> G_name, _ = galois_group(f, by_name=True)
546 >>> print(G_name)
547 S4TransitiveSubgroups.V
549 The group itself can then be obtained by calling the name's
550 ``get_perm_group()`` method:
552 >>> G_name.get_perm_group()
553 PermutationGroup([
554 (0 1)(2 3),
555 (0 2)(1 3)])
557 Group names are values of the enum classes
558 :py:class:`sympy.combinatorics.galois.S1TransitiveSubgroups`,
559 :py:class:`sympy.combinatorics.galois.S2TransitiveSubgroups`,
560 etc.
562 Parameters
563 ==========
565 f : Expr
566 Irreducible polynomial over :ref:`ZZ` or :ref:`QQ`, whose Galois group
567 is to be determined.
568 gens : optional list of symbols
569 For converting *f* to Poly, and will be passed on to the
570 :py:func:`~.poly_from_expr` function.
571 by_name : bool, default False
572 If ``True``, the Galois group will be returned by name.
573 Otherwise it will be returned as a :py:class:`~.PermutationGroup`.
574 max_tries : int, default 30
575 Make at most this many attempts in those steps that involve
576 generating Tschirnhausen transformations.
577 randomize : bool, default False
578 If ``True``, then use random coefficients when generating Tschirnhausen
579 transformations. Otherwise try transformations in a fixed order. Both
580 approaches start with small coefficients and degrees and work upward.
581 args : optional
582 For converting *f* to Poly, and will be passed on to the
583 :py:func:`~.poly_from_expr` function.
585 Returns
586 =======
588 Pair ``(G, alt)``
589 The first element ``G`` indicates the Galois group. It is an instance
590 of one of the :py:class:`sympy.combinatorics.galois.S1TransitiveSubgroups`
591 :py:class:`sympy.combinatorics.galois.S2TransitiveSubgroups`, etc. enum
592 classes if *by_name* was ``True``, and a :py:class:`~.PermutationGroup`
593 if ``False``.
595 The second element is a boolean, saying whether the group is contained
596 in the alternating group $A_n$ ($n$ the degree of *T*).
598 Raises
599 ======
601 ValueError
602 if *f* is of an unsupported degree.
604 MaxTriesException
605 if could not complete before exceeding *max_tries* in those steps
606 that involve generating Tschirnhausen transformations.
608 See Also
609 ========
611 .Poly.galois_group
613 """
614 gens = gens or []
615 args = args or {}
617 try:
618 F, opt = poly_from_expr(f, *gens, **args)
619 except PolificationFailed as exc:
620 raise ComputationFailed('galois_group', 1, exc)
622 return F.galois_group(by_name=by_name, max_tries=max_tries,
623 randomize=randomize)