The usual way of creating elements within an algebraically closed field A is by coercion from the base field into A, or by construction of roots of polynomials over A (and this may be done indirectly via other functions).
These generic functions create A!1, A!1, A!0 and A!0, respectively.
Given an algebraically closed field A, create the element specified by a; here a is allowed to be an element coercible into A, which means that a may be:
- (i)
- an element of A;
- (ii)
- an integer or rational.
Max: RngIntElt Default:
Given a polynomial f over an algebraically closed field A, or given a polynomial f over some subring of A together with A itself, this function computes all roots of f in A, and returns a sorted sequence of tuples (pairs), each consisting of a root of f in A and its multiplicity. Since A is algebraically closed, f always splits completely.If the parameter Max is set to a non-negative number m, at most m roots are returned. This feature can be quite useful when one wishes, say, only one root of a polynomial and not all the conjugates of the root, as they will cause the field to have more variables than necessary and this can make the full simplification of the field much more difficult later (if that is requested).
Note that the function Factorization(f) is also supported, and simply returns the linear factors and multiplicities corresponding to the roots returned by Roots(f).
Return a primitive n-th root of unity in A, i.e., an element ω∈A such that ωn = 1 and ωi not=1 for 1≤i<n. This always exists since the field is algebraically closed, and the return value is invariable. This function is equivalent to Roots(CyclotomicPolynomial(n), A: Max := 1)[1, 1].
A square root of the element a from the field A, i.e., an element y of A such that y2 = a. A square root always exists since the field is algebraically closed, and the return value is invariable.
Return {true} and a square root of the element a from the field A, i.e., {true} and an element y of A such that y2 = a. A square root always exists since the field is algebraically closed, and the return value is invariable.
Return an n-th root of the element a from the field A, i.e., an element y of A such that yn = a. A root always exists since the field is algebraically closed, and the return value is invariable.
Return {true} and an n-th root of the element a from the field A, i.e., {true} and an element y of A such that yn = a. A root always exists since the field is algebraically closed, and the return value is invariable.
Return the i-th variable of A. i must be between 1 and the rank of A (the current number of variables in A). Initially A has no variables, and new variables are only created by calling Roots above (or similar functions such as Sqrt). As long as Prune or Absolutize are not called (which shift the variable numbers -- see below), the return value of this function is invariable, so A.i for fixed i will always return the same mathematical object despite any simplifications or constructions of new roots. New roots are always assigned higher generator numbers.
> A := AlgebraicClosure();
> P<x> := PolynomialRing(IntegerRing());
> r := Roots(x^3 + x + 1, A);
> r;
[
<r1, 1>,
<r2, 1>,
<r3, 1>
]
> A;
Algebraically closed field with 3 variables
Defining relations:
[
r3^3 + r3 + 1,
r2^3 + r2 + 1,
r1^3 + r1 + 1
]
> a := r[1,1];
> a^3 + a;
-1
> A.1;
r1
> A.2;
r2
> A.3;
r3
> A.1 eq a;
true
It is often useful to use the Max parameter with the Roots
function. Note that in this case A does not have the extra variables
found in the previous example.
> A := AlgebraicClosure();
> r := Roots(x^3 + x + 1, A: Max := 1);
> A;
Algebraically closed field with 1 variable
Defining relations:
[
r1^3 + r1 + 1
]
One can also create elements by Sqrt, etc.
> A := AlgebraicClosure();
> sqrt2 := Sqrt(A ! 2);
> cube3 := Root(A!3, 3);
> A;
Algebraically closed field with 2 variables
Defining relations:
[
r2^3 - 3,
r1^2 - 2
]
> sqrt2^2;
2
> cube3^3;
3
The n-th Swinnerton-Dyer polynomial is defined to be ∏(x ∓ Sqrt(2) ∓ Sqrt(3) ∓ Sqrt(5) ∓ ... ∓ Sqrt(pn)), where pi is the i-th prime and the product runs over all 2n possible combinations of + and - signs. Such polynomials lie in Z[x] and are irreducible over Z. It is very easy to compute them using algebraically closed fields. We simply construct the square roots we need and multiply out the expression, coercing the resulting polynomial to Z[x].
> Z := IntegerRing();
> function SwinnertonDyer(n)
> P := [2];
> for i := 2 to n do
> Append(~P, NextPrime(P[#P]));
> end for;
> A := AlgebraicClosure();
> S := [Sqrt(A ! p): p in P];
> P<z> := PolynomialRing(A);
> f := &*[z + &+[t[i]*S[i]: i in [1..n]]: t in CartesianPower({-1, 1}, n)];
> return PolynomialRing(Z) ! f;
> end function;
> P<x> := PolynomialRing(Z);
> [SwinnertonDyer(i): i in [1..5]];
[
x^2 - 2,
x^4 - 10*x^2 + 1,
x^8 - 40*x^6 + 352*x^4 - 960*x^2 + 576,
x^16 - 136*x^14 + 6476*x^12 - 141912*x^10 + 1513334*x^8 -
7453176*x^6 + 13950764*x^4 - 5596840*x^2 + 46225,
x^32 - 448*x^30 + 84864*x^28 - 9028096*x^26 + 602397952*x^24 -
26625650688*x^22 + 801918722048*x^20 - 16665641517056*x^18 +
239210760462336*x^16 - 2349014746136576*x^14 +
15459151516270592*x^12 - 65892492886671360*x^10 +
172580952324702208*x^8 - 255690851718529024*x^6 +
183876928237731840*x^4 - 44660812492570624*x^2 +
2000989041197056
]
The Swinnerton-Dyer polynomials yield worse-case inputs for the
Berlekamp-Zassenhaus factorization algorithm for polynomials over Z,
but they are no longer difficult to factor using van Hoeij's new
algorithm (see Example H24E7).
We can even define a simple extension of the Swinnerton-Dyer polynomials. Let Q = { q1, ..., qn } be a set of n distinct primes or negatives of primes. Define: (GSD)Q := ∏(x ∓ Sqrt(q1) ∓ Sqrt(q2) ∓ ... ∓ Sqrt(qn)), where the product runs over all 2n possible combinations of + and - signs. Then (GSD)Q ∈Z[x], is irreducible over Z, has degree 2n, and has at least 2n - 1 factors mod any prime. A function to compute these polynomials is only a slight variation on the previous function.
> function GSD(Q)
> n := #Q;
> A := AlgebraicClosure();
> S := [Sqrt(A ! x): x in Q];
> z := PolynomialRing(A).1;
> f := &*[z + &+[t[i]*S[i]: i in [1..n]]: t in CartesianPower({-1, 1}, n)];
> return PolynomialRing(Z) ! f;
> end function;
One can multiply (GSD)Q for various Q to construct more reducible
polynomials with many modular factors. We first note the effects
of changing the sign of the input primes.
> GSD([2, 3, 5]); x^8 - 40*x^6 + 352*x^4 - 960*x^2 + 576 > GSD([-2, -3, -5]); x^8 + 40*x^6 + 352*x^4 + 960*x^2 + 576 > GSD([-2, 3, 5]); x^8 - 24*x^6 + 224*x^4 + 960*x^2 + 1600 > GSD([2, -3, 5]); x^8 - 16*x^6 + 184*x^4 + 960*x^2 + 3600 > GSD([2, 3, -5]); x^8 + 152*x^4 + 1920*x^2 + 5776We now form a polynomial f which is the product of two degree-64 irreducible polynomials. f has at least 64 factors modulo any prime, but is not difficult to factor using van Hoeij's algorithm.
> f := GSD([2, 3, 5, 7, 11, 13])*GSD([-2, -3, -5, -7, -11, -13]); > Degree(f); 128 > Max([Abs(x): x in Coefficients(f)]); 74356932844713201802276382813294219572861455394629943303351262856515487990904 17 > time L:=Factorization(f); Time: 9.850 > [Degree(t[1]): t in L]; [ 64, 64 ] > Max([Abs(x): x in Coefficients(L[1,1])]); 1771080720430629161685158978892152599456 11
> A := AlgebraicClosure();
> S<y> := PuiseuxSeriesRing(A);
> P<x> := PolynomialRing(S);
> f := (x^2 - y^2 - 1)^5 + x*y + 1;
> time S := PuiseuxExpansion(f, 3);
Time: 0.210
> S;
[
r1*y + (102/2525*r1 - 2/505)*y^3 + O(y^4),
r2*y + (102/2525*r2 - 2/505)*y^3 + O(y^4),
r3 + (1/10*r3^2 - 1/10)*y + (-101/1000*r3^7 + 101/200*r3^5 -
209/200*r3^3 + 26/25*r3)*y^2 + O(y^3),
r4 + (1/10*r4^2 - 1/10)*y + (-101/1000*r4^7 + 101/200*r4^5 -
209/200*r4^3 + 26/25*r4)*y^2 + O(y^3),
r5 + (1/10*r5^2 - 1/10)*y + (-101/1000*r5^7 + 101/200*r5^5 -
209/200*r5^3 + 26/25*r5)*y^2 + O(y^3),
r6 + (1/10*r6^2 - 1/10)*y + (-101/1000*r6^7 + 101/200*r6^5 -
209/200*r6^3 + 26/25*r6)*y^2 + O(y^3),
r7 + (1/10*r7^2 - 1/10)*y + (-101/1000*r7^7 + 101/200*r7^5 -
209/200*r7^3 + 26/25*r7)*y^2 + O(y^3),
r8 + (1/10*r8^2 - 1/10)*y + (-101/1000*r8^7 + 101/200*r8^5 -
209/200*r8^3 + 26/25*r8)*y^2 + O(y^3),
r9 + (1/10*r9^2 - 1/10)*y + (-101/1000*r9^7 + 101/200*r9^5 -
209/200*r9^3 + 26/25*r9)*y^2 + O(y^3),
r10 + (1/10*r10^2 - 1/10)*y + (-101/1000*r10^7 + 101/200*r10^5 -
209/200*r10^3 + 26/25*r10)*y^2 + O(y^3)
]
> A;
Algebraically closed field with 10 variables
Defining relations:
[
r10^8 - 5*r10^6 + 10*r10^4 - 10*r10^2 + 5,
r9^8 - 5*r9^6 + 10*r9^4 - 10*r9^2 + 5,
r8^8 - 5*r8^6 + 10*r8^4 - 10*r8^2 + 5,
r7^8 - 5*r7^6 + 10*r7^4 - 10*r7^2 + 5,
r6^8 - 5*r6^6 + 10*r6^4 - 10*r6^2 + 5,
r5^8 - 5*r5^6 + 10*r5^4 - 10*r5^2 + 5,
r4^8 - 5*r4^6 + 10*r4^4 - 10*r4^2 + 5,
r3^8 - 5*r3^6 + 10*r3^4 - 10*r3^2 + 5,
r2^2 + 1/5*r2 - 1,
r1^2 + 1/5*r1 - 1
]
We check that f evaluated at each expansion in S is zero up to
the precision.
> [Evaluate(f, p): p in S];
[
O(y^5),
O(y^5),
O(y^3),
O(y^3),
O(y^3),
O(y^3),
O(y^3),
O(y^3),
O(y^3),
O(y^3)
]