|
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).
One(A) : FldAC -> FldACElt
Identity(A) : FldAC -> FldACElt
Zero(A) : FldAC -> FldACElt
Representative(A) : FldAC -> FldACElt
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.
Roots(f) : RngUPolElt -> [ < FldACElt, RngIntElt> ]
Roots(f, A) : RngUPolElt, FldAC -> [ < FldACElt, RngIntElt> ]
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].
Sqrt(a) : FldACElt -> FldACElt
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.
We first show the most common way of creating roots: by the Roots
function.
> 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 + 5776
We 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
This example shows how one can compute Puiseux expansions over an
algebraic closure. The PuiseuxExpansion function calls the
Roots function internally as it needs to.
> 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)
]
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|