Computation of the Setwise Stabiliser of a triangular ideal.
1 Introduction
Documented function and procedures above are the Magma implementation
of the algorithm presented in my thesis (Section 3.3 and 3.4, Chapter 4). The function Setwise_Stabiliser computes the Setwise Stabiliser of a triangular ideal I ∈ k[x1,…,xn] . For the natural group action of Sn (the symmetric group of degree n) on k[x1,… ,xn]
Sn X k[x1,…,xn] —→ k[x1,…,xn] |
| (σ,P(x1,…,xn)) ⊢→ P(xσ(1),…,xσ(n)), |
the Setwise Stabiliser of I is defined by :
| Dec(I) = { σ ∈ Sn ∣ σ.f ∈ I }. |
A triangular generating set {f1,…,fn} such that fi depends only on the variables x1,…,xi
is supposed to be known. As this algorithm uses ideal membership tests, this triangular set of generators is supposed to be a lexicographical Groebner basis.
The algorithm implemented here improves the algorithm presented in the paper Computation of the Setwise Stabiliser of a triangular ideal in terms of complexity and efficiency.
Author : S. ORANGE (LIP6 - Paris 6 University / LMAH - University of Le Havre - France).
Source of this file : Documented Magma Code file.
2 Implementations
2.1 Find_One_Permutation
This procedure search a permutation σ ∈ dec(I) such that l is the suffix of σ. If such a permutation σ is found, any other computation are done. For the initial call of procedure Find_One_Permutation, σ is initialised to the permutation Id(Sn). A modular ideal membership preliminary test is performed in order to improve efficiency.
-
Parameter : r an integer
- Parameter : G sequence of generators of the pointwise stabiliser of Dec(I)
- Parameter : l a prefix to complete
- Parameter : sigma a permutation initialy equal to Id(Sn) until an other permutation of Dec(I) with l as prefix is found
- Parameter : S triangular set of generators of I
- Parameter : SP the image of S modulo a prime number p.
- Parameter : n the length of S.
- Parameter : sn the symmetric group of degree n.
procedure Find_One_Permutation(r,G,l,~sigma ,~S,~SP,~n,~sn);
if r eq 0 then
sigma:= sn ! l;
else
Gprime:=Stabilizer(G,l[1]);
elt:=({1..n} diff Set(l)) meet {Max(o): o in Orbits(Gprime)};
while ((not(IsEmpty(elt))) and (sigma eq Id(sn)) ) do
a := Max(elt);
elt := elt diff {a};
ll := [a] cat l;
if NormalForm((SP[r])^(sn!(SetToSequence({1..n} diff Set(ll)) cat ll)) ,SP) eq 0 then
if NormalForm((S[r])^(sn! (SetToSequence({1..n} diff Set(ll)) cat ll)) ,S) eq 0 then
Find_One_Permutation(r-1,Gprime,ll ,~sigma ,~S,~SP,~n,~sn);
end if;
end if;
end while;
end if;
end procedure;
2.2 Next_Setwise_Stabiliser
This procedure computes a strong generating set of the pointwise stabiliser of the set {k,…,n} in dec(I) from a strong generating set of the pointwise stabiliser of the set {k−1,…,n}. As the precedent procedure, a modular ideal membership pretest is performed.
-
Parameter : index an integer
- Parameter : G sequence of generators of the pointwise stabiliser of Dec(I)
- Parameter : S triangular set of generators of I
- Parameter : SP the image of S modulo a prime number p.
- Parameter : n the length of S.
- Parameter : sn the symmetric group of degree n.
- Parameter : orbites the set of orbits of {1, … , n} under the action of <G>.
procedure Next_Setwise_Stabiliser(index,~G,~S,~SP,~n,~sn,~orbites);
elt:={1..(index-1)} meet {Max(o): o in orbites};
while (not(IsEmpty(elt))) do
ak := Max(elt);
elt := elt diff {ak};
ll:= SetToSequence({1..index} diff {ak}) cat [ak] cat [(index+1)..n] ;
if NormalForm((SP[index])^(sn! ll) ,SP) eq 0 then
if NormalForm((S[index])^(sn! ll) ,S) eq 0 then
sigma:= Id(sn);
Find_One_Permutation (index-1,G,[ak] cat [(index+1)..n],~sigma ,~S,~SP,~n,~sn);
if not (sigma eq Id(sn)) then
G:= PermutationGroup<n |GeneratorsSequence(G) cat [sn ! sigma]>;
orbites:=NouvellesOrbites(orbites,sigma);
elt:=elt meet {Max(o): o in orbites};
end if;
end if;
end if;
end while;
end procedure;
2.3 function Setwise_Stabiliser
This function computes a strong generating set of the Setwise Stabiliser of the ideal I=<S> where S is a triangular Groebner basis as defined in the introduction.
-
Parameter : S a triangular Groebner basis given as a sequence.
- Output : the group of decomposition of the ideal < S >.
function Setwise_Stabiliser(S);
n:=Rank(Parent (S[1]));
sn:=Sym(n);
G:=PermutationGroup<n|1>;
orbites := {{i}: i in {1..n}} ;
// A prime p for a modular ideal membership pretest is search.
p:=2;
rep:=false;
while rep eq false do
polmod:=PolynomialRing(FiniteField(p),n);
k:=1;
rep:=true;
while (rep eq true) and (k le n) do
rep:=IsCoercible(polmod,S[k]);
k:=k+1;
end while;
if rep eq false then
p:=NextPrime(p);
end if;
end while;
polmod:=PolynomialRing(FiniteField(p),n);
SP := [(polmod ! S[i]) : i in [1..n]];
// Construction of the decomposittion group
for k:=2 to n do
Next_Setwise_Stabiliser(k,~G,~S,~SP,~n,~sn,~orbites);
end for;
return G;
end function ;
3 Example of application : computation of the Galois group from a relations ideal
The ideal I of Q[x1,…,xn] generated by the triangular Groebner basis (for the lexicographical order induced by x8<…<x1)
S = { x1 − x4x6x87 + x4x6x83,
x2 + x4x6x87 − x4x6x83,
x3 + x4,
x42 − x6x85 + x6x8,
x5 + x6,
x62 + x82,
x7 + x8,
x88 − x84 − 1}
is an relations ideal of f(x) = x88 − x84 − 1 ∈ Q[x] .
The symetric representation of the Galois group of f corresponding to this relations ideal is the Setwise Stabiliser of I. The Magma function Setwise_Stabiliser return the this symetric representation :
> PR8<x1,x2,x3,x4,x5,x6,x7,x8>:= PolynomialRing(RationalField(), 8);
>
> S:=[
> x1 + x2 + x3 + x4,
> x2 + x4*x6*x8^7 - x4*x6*x8^3,
> x3 + x4,
> x4^2 - x6*x8^5 + x6*x8,
> x5 + x6,
> x6^2 + x8^2,
> x7 + x8,
> x8^8 - x8^4 - 1
> ];
>
> Setwise_Stabiliser(I);
Permutation group G acting on a set of cardinality 8
Id(G)
(1, 2)(3, 4)
(1, 3)(2, 4)(5, 6)
(1, 3)(2, 4)(7, 8)
(1, 2)(5, 7)(6, 8)
(1, 8, 4, 6, 2, 7, 3, 5)
This document was translated from a Documented Magma Code
to LATEX by DMC2TEX
beta0.1 version.
This document was translated from LATEX by
HEVEA.