       Re: Computational aspects of Galois theory?

• To: mathgroup at smc.vnet.net
• Subject: [mg43714] Re: [mg43694] Computational aspects of Galois theory?
• From: Daniel Lichtblau <danl at wolfram.com>
• Date: Thu, 2 Oct 2003 02:51:08 -0400 (EDT)
• References: <200309302042.QAA25641@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

Victor Alexandrov wrote:
>
> Let $p_1$,..., $p_n$ be $n$ different prime numbers.
> For every subset $A$ of the set $\{ 1,...,n\}$ consider
> the product $q_A=\prod_{i\in A} p_i$. If $A$ is empty
> $q_A$ equals 1 by definition. The set of all linear
> combinations of $q_A$ with rational coefficients is
> denoted by $F(1,p_1,...,p_n)$.

I assume you want the p[j]'s to be algebraic (rather than prime)
numbers. Otherwise F is simply the rationals.

Also presumably you have in mind algebraic combinations, not just linear
(so that you in fact get a field).

> It is well-known that
> $F(1,p_1,...,p_n)$ is a field.
> Does there exist a software which, for a given number
> $x$ of $F(1,p_1,...,p_n)$, says whether the square root
> of $x$ belongs to $F(1,p_1,...,p_n)$ and, when possible,
> represents this square root as a linear combination of
> $q_A$ with rational coefficients?

There is probably an easier way to do this, but here is one approach. I
denonstrate with an example. We define three algebraic numbers by
polynomial equations (note that they are indistinguishable from
conjugates; more refined methods would allow one to specify which
conjugate one has in mind when working over the rationals).

algnumdefiningpolys = {a^2-2, a^3+a+5, a^4+3*a^3+a+7};

Now we create an element in this field. We will intentioanlly make it a
square.

xpoly = x - (3*a+a^2+4*a+2*a^3+5*a+4)^2;

We now define a candidate square root using undetermined coefficients.
We also provide a polynomial equation enforcing that it's square is 'x'.

ypoly = y - (Array[b,1].a^Range + Array[c,2].a^Range +
Array[d,3].a^Range + e)
sqrtpoly = y^2-x;

Finally we find a polynomial relation involving just the undetermined
coefficients and the defining elements of the field.

In:= In:= InputForm[bigpoly = Last[GroebnerBasis[
Join[algnumdefiningpolys,{xpoly,sqrtpoly,ypoly}],
Join[Array[b,1],Array[c,2],Array[d,3],{e},Array[a,3]], {x,y}]]]
Out//InputForm=
-398 + 24*a + 19*a + 24*a*a + 23*a^2 + 6*a*a^2 +
68*a + 30*a*a + 40*a*a + 10*a^2*a + 9*a^2 -
156*a^3 + 12*a*a^3 + 16*a*a^3 + 4*a^2*a^3 -
2*b^2 -
2*a*a*b*c - a^2*c^2 - 2*a*a^2*b*c +
10*c*c + 2*a*c*c + 5*a*c^2 + a^2*c^2 -
2*a*a*b*d - 2*a*a*c*d - 2*a^2*a*c*d
-
a^2*d^2 - 2*a*a^2*b*d - 2*a*a^2*c*d -
2*a^2*a^2*c*d - 2*a^3*d*d + 7*d^2 + a*d^2
+
3*a^3*d^2 - 2*a*a^3*b*d - 2*a*a^3*c*d -
2*a^2*a^3*c*d + 14*d*d + 2*a*d*d +
6*a^3*d*d - 42*d*d + 8*a*d*d +
2*a^2*d*d -
18*a^3*d*d + 63*d^2 - 12*a*d^2 + 4*a^2*d^2 +
28*a^3*d^2 - 2*a*b*e - 2*a*c*e -
2*a^2*c*e - 2*a*d*e - 2*a^2*d*e -
2*a^3*d*e - e^2

Setting the coefficients of the powers of algebraic elements to zero
gives solutions for the undetermined coefficients of y. We note that as
we had a square, there are two solutions, being negatives of one
another.

In:= InputForm[SolveAlways[bigpoly==0, Array[a,3]]]
Out//InputForm=
{{b -> -3, c -> -4, c -> -1, d -> -5, d -> 0, d -> -2,
e -> -4}, {b -> 3, c -> 4, c -> 1, d -> 5, d -> 0,
d -> 2, e -> 4}}

Note that if we instead do this with

xpoly = x - (3*a+a^2+4*a+2*a^3+5*a+4)^2 + a^2 + 7

then the SolveAlways step yields {}, telling us there is no solution and
hence that element is not a square in the field.

Daniel Lichtblau
Wolfram Research



• Prev by Date: Re: A question on interval arithmetic
• Next by Date: RE: Plotting functions with undefined values
• Previous by thread: Re: Computational aspects of Galois theory?
• Next by thread: Re: A question on interval arithmetic