Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2003
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2003

[Date Index] [Thread Index] [Author Index]

Search the Archive

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[1]^2-2, a[2]^3+a[2]+5, a[3]^4+3*a[3]^3+a[3]+7};

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

xpoly = x - (3*a[1]+a[2]^2+4*a[2]+2*a[3]^3+5*a[3]+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[1]^Range[1] + Array[c,2].a[2]^Range[2] +
  Array[d,3].a[3]^Range[3] + e[1])
sqrtpoly = y^2-x;

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

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

Note that if we instead do this with

xpoly = x - (3*a[1]+a[2]^2+4*a[2]+2*a[3]^3+5*a[3]+4)^2 + a[3]^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