######################################################################
##
#M  MinimalNormalSubgroups
##
#
#InstallMethod(
#	MinimalNormalSubgroups,
#	"filter OneGeneratedNormalSubgroups",
#	[IsGroup],
#	0,
#  function ( G )
#  local gens;
#    gens := OneGeneratedNormalSubgroups( G );
#    return Filtered( gens, 
#	N -> not ( ForAny( gens, M -> IsSubset( N, M ) and N<>M ) ) );
#  end );

######################################################################
##
#M  GeneratorsOfCongruenceLattice
##

InstallMethod(
	GeneratorsOfCongruenceLattice,
	"by conjugacy classes",
	true,
	[IsGroup],
	0,
  function( G )

  local cc, rep, reps, NList, lengthList, ord, i, j, k, deleted, gens;
    cc := ConjugacyClasses( G );
    reps := List( cc, Representative );
    NList := List( cc, AsList );
    lengthList := Length(reps);
    for i in [1..lengthList] do
      rep := reps[i]; ord := Order(rep); j := 1; deleted := false;
      while not deleted and j<ord-1 do
        rep := rep*reps[i];
        j := j+1;
        if Gcd(j,ord)=1 then
	  k := i;
	  while not deleted and k<lengthList do
	    k := k+1;
	    if Order(reps[k]) = ord and rep in NList[k] then
		Unbind(NList[i]);
		deleted := true;
	    fi;
          od;
        fi;
      od;
    od;
 
    gens := [];
    for i in [1..lengthList] do
      if IsBound(NList[i]) and reps[i]<>Identity(G) then
         Add( gens, Subgroup(G,NList[i]) );
#	 Add( gens, NormalClosure( Subgroup( G, [reps[i]] ) ) );
      fi;
    od;

    Sort( gens, function( x, y ) return Size(x) < Size(y); end );

    if Size( gens[Length(gens)] ) = Size(G) then
	return gens{[1..Length(gens)-1]};
    else
	return gens;
    fi;
  end );

######################################################################
##
#M  GeneratorsOfIntervallInCongruenceLattice
##

InstallMethod(
	GeneratorsOfIntervallInCongruenceLattice,
	"all elements",
	true,
	[IsGroup, IsGroup],
	10,
  function( G, N )
    return Filtered( NormalSubgroups( G ), 
	I -> Size(I)>1 and Size(I)<Size(N) and IsSubset( N, I ) );
  end );
	
######################################################################
##
#F  PeakOfnAtg( <G>, <g>, <n> )
##
##  constructs the tfm with value <n> at <g> and 0 everywhere else
##

InstallGlobalFunction( PeakOfnAtg,
  function( G, g, n )
    return EndoMappingByFunction( G,
		function( x )
		  if x = g then return n; else return Identity(G); fi;
                end );
  end );


######################################################################
##
#F  ConstGrpTfmOnRightCosetOfN( <G>, <N>, <g>, <h> )
##
##  constructs the tfm with value <g> on the coset <h>+<N> and
##  0 everywhere else
##

InstallGlobalFunction( ConstGrpTfmOnRightCosetOfN,
  function( G, N, g, h )
  local elms, posg, vec, i;
    elms := AsSSortedList( G );
    posg := Position( elms, g );
    vec := [];
    for i in [1..Size(G)] do
      if elms[i]/h in N then 
	Add( vec, posg );
      else
	Add( vec, 1 );
      fi;
    od;

  return EndoMappingByPositionList( G, vec );

  end );

######################################################################
##
#M  IsCompatibleEndoMapping
##
##  test f(x+n) - f(x) \in <n>
##  Aufwand: |G| * ? < |G|^2
##

InstallMethod(
	IsCompatibleEndoMapping,
	"on quotients",
	true,
	[IsEndoMapping],
	0,
  function( tfm )
  local G, lattgens, mins, others, minscontained, N, epi, J;
    G := Source( tfm );

    lattgens := GeneratorsOfCongruenceLattice( G );
    mins := MinimalNormalSubgroups( G );
    others := Difference( lattgens, mins );
    
    if not ( ForAll( mins, N -> ( IsEndoMappingCompatibleWithNormalSubgroup( tfm, N ) ) ) ) then
	return false;
    fi;

    for N in others do
      minscontained := Filtered( mins, M -> IsSubset(N,M) );
      J := ClosureSubgroups( G, minscontained );
      epi := NaturalHomomorphismByNormalSubgroup( G, J );
      if not ( IsEndoMappingCompatibleWithNormalSubgroup( CompatibleFunctionModNormalSubgroupNC(tfm,epi), Image(epi,N) ) ) then
	return false;
      fi;
    od;

    return true;
end );

######################################################################
##
#M  IsEndoMappingCompatibleWithNormalSubgroup
##
##  test f(x+n) - f(x) \in N for all n in N
##

InstallMethod(
	IsEndoMappingCompatibleWithNormalSubgroup,
	"default",
	[IsEndoMapping,IsGroup],
	0,
  function ( tfm, N )
  local x, n, G;
      G := Source(tfm);
      if Size(G)=Size(N) or Size(N)=1 then return true; fi;
      for x in G do
        for n in GeneratorsOfGroup( N ) do
          if not ( Image( tfm, x*n ) / Image( tfm, x ) in N ) then
	    return false;
          fi;
        od;
      od;
      return true;
  end );

######################################################################
##
#M  CompatibleFunctionModNormalSubgroupNC 

InstallMethod(
	CompatibleFunctionModNormalSubgroupNC,
	"default",
	[IsEndoMapping,IsMapping],
	0,
  function (phi,epi)
	Print("CFMNS: ", Source(phi),Range(phi),Source(epi),Range(epi),"\n");
    return EndoMappingByFunction( Image(epi),
	x -> Image( epi, Image( phi, PreImagesRepresentative( epi, x ) ) )
    );
  end );

######################################################################
##
#M  ClosureSubgroups
##

InstallMethod(
	ClosureSubgroups,
	"one by one",
	[IsGroup,IsCollection],
	0,
  function( G, list )
   local J, S;
     J := TrivialSubgroup( G );
     for S in list do
       J := ClosureGroup( J, S );
     od;
     return J;
  end );
  
######################################################################
##
#F  FunctionsCompatibleWithNormalSubgroupChain( <G>, <[N1..Ns]> )
##
##  compute the nearring of all functions on <G> compatible with
##  N1..Ns (where <N1> <= <N2> <= ... <= <Ns>)
##

InstallMethod(
	FunctionsCompatibleWithNormalSubgroupChain,
	"compute additive generators explicitely",
	true,
	[IsGroup, IsCollection],
	0,
	function( G, nsgps )
local reps, g, h, i, n, generators;
  nsgps := ShallowCopy( nsgps );
  Add( nsgps, G );
  generators := [];

  # functions from G to smallest subgroup
  for n in GeneratorsOfGroup( nsgps[1] ) do
    for g in G do
      Add( generators, PeakOfnAtg( G, g, n ) );
    od;
  od;

  # piecewise constant functions from h+nsgps[i] to nsgps[i+1]
  for i in [1..Length(nsgps)-1] do
    for g in GeneratorsOfGroup( nsgps[i+1] ) do
      reps := RepresentativesModNormalSubgroup( G, nsgps[i] );
      for h in reps do
        Add( generators, ConstGrpTfmOnRightCosetOfN( G, nsgps[i], g, h ) );
      od;
    od;
  od;

  return TransformationNearRingByAdditiveGenerators( G, generators );

  end);

######################################################################
##
#M  CompatibleFunctionNearRing
##

#InstallMethod(
#	CompatibleFunctionNearRing,
#	"as an intersection (use lattice generators only)",
#	true,
#	[IsGroup],
#	1,
#  function( G )
#  local gens, visited, n, chain, chains, C, compfcts, K, MakeChain, i;
#
#    gens := GeneratorsOfCongruenceLattice( G );
#    if gens = [] then
#	return MapNearRing(G);
#    fi;
#    visited := List( gens, x -> false );
#    n := Length(visited);
#
#    # MakeChain uses gens, visited, n and chain as global variables
#    # when recursing
#    MakeChain := function( j )
#    local K;
#      K := First( [j+1..n],
#	k -> not visited[k] and IsSubset(gens[k],gens[j]) );
#      if K=fail then
#	return;
#      else
#	visited[K] := true;
#	Add( chain, K );
#	MakeChain( K );
#	return;
#      fi;
#    end;
#
#    Info( InfoNearRing, 1, "making subgroup chains..." );
#    chains := [];
#    for i in [1..Length(visited)] do
#      if not visited[i] then
#        visited[i] := true;
#        chain := [i];
#        MakeChain(i);
#	Info( InfoNearRing, 2, "chain ", chain );
#	Add( chains, chain );
#      fi;
#    od;
#    # longer chains of subgroups will hopefully result in smaller
#    # nearrings for intersection, so we begin with the longest chains
#    Sort( chains, function( x, y ) return Length(x)>Length(y); end );
#
#    Info( InfoNearRing, 1, "computing additive generators" );
#    C := FunctionsCompatibleWithNormalSubgroupChain( G,
#					List( chains[1], i->gens[i] ) );
#    chains := chains{[2..Length(chains)]};
#
#    for chain in chains do
#      Info( InfoNearRing, 1, "computing additive generators" );
#      compfcts := FunctionsCompatibleWithNormalSubgroupChain( G,
#					List( chain, i->gens[i] ) );
#      Info( InfoNearRing, 1, "intersecting nearrings");
#      C := Intersection( C, compfcts );
#      Info( InfoNearRing, 3, "intersection has size ", Size(C) );
#    od;
#
#    return C;
#
#  end );

#InstallMethod(
#	CompatibleFunctionNearRing,
#	"as an intersection (use all normal subgroups)",
#	true,
#	[IsGroup],
#	10,
#  function( G )
#  local gens, visited, n, chain, chains, C, compfcts, K, MakeChain, i;
#
#    gens := ShallowCopy( NormalSubgroups( G ) );
#    RemoveElmList( gens, Position( gens, G ) );
#    RemoveElmList( gens, Position( gens, TrivialSubgroup( G ) ) );
#    if gens = [] then
#	return MapNearRing(G);
#    fi;
#    visited := List( gens, x -> false );
#    n := Length(visited);
#
#    # MakeChain uses gens, visited, n and chain as global variables
#    # when recursing
#    MakeChain := function( j )
#    local K;
#      K := First( [j+1..n],
#	k -> Size(gens[k])>Size(gens[j]) and IsSubset(gens[k],gens[j]) );
#      if K=fail then
#	return;
#      else
#	visited[K] := true;
#	Add( chain, K );
#	MakeChain( K );
#	return;
#      fi;
#    end;
#
#    Info( InfoNearRing, 1, "making subgroup chains..." );
#    chains := [];
#    for i in [1..Length(visited)] do
#      if not visited[i] then
#        visited[i] := true;
#        chain := [i];
#        MakeChain(i);
#	Info( InfoNearRing, 2, "chain ", chain );
#	Add( chains, chain );
#      fi;
#    od;
#    # longer chains of subgroups will hopefully result in smaller
#    # nearrings for intersection, so we begin with the longest chains
#    Sort( chains, function( x, y ) return Length(x)>Length(y); end );
#
#    Info( InfoNearRing, 1, "computing additive generators" );
#    C := FunctionsCompatibleWithNormalSubgroupChain( G,
#					List( chains[1], i->gens[i] ) );
#    chains := chains{[2..Length(chains)]};
#
#    for chain in chains do
#      Info( InfoNearRing, 1, "computing additive generators" );
#      compfcts := FunctionsCompatibleWithNormalSubgroupChain( G,
#					List( chain, i->gens[i] ) );
#      Info( InfoNearRing, 1, "intersecting nearrings");
#      C := Intersection( C, compfcts );
#      Info( InfoNearRing, 3, "intersection has size ", Size(C) );
#    od;
#
#    return C;
#
#  end );

InstallMethod(
	CompatibleFunctionNearRing,
	"compute the 0-symmetric part first",
	true,
	[IsGroup],
	0,
  function( G )
  local C0, c0gens, const;
    C0 := ZeroSymmetricCompatibleFunctionNearRing( G );
    c0gens := AdditiveGenerators( C0 );
    const := List( GeneratorsOfGroup( G ), g -> ConstantEndoMapping( G, g ) );
    
    return TransformationNearRingByAdditiveGenerators( G,
	Concatenation( c0gens, const ) );
  end );

######################################################################
##
#F  ZeroSymmetricFunctionsCompatibleWithNormalSubgroupChain( <G>, <[N1..Ns]> )
##
##  compute the nearring of all functions on <G> compatible with
##  N1..Ns (where <N1> <= <N2> <= ... <= <Ns>)
##

ZeroSymmetricFunctionsCompatibleWithNormalSubgroupChain := function( G, nsgps )
local reps, g, h, i, n, generators;
  nsgps := ShallowCopy( nsgps );
  Add( nsgps, G );
  generators := [];

  # functions from G to smallest subgroup
  for n in GeneratorsOfGroup( nsgps[1] ) do
    for g in G do
      if g<>Identity(G) then # 0-symmetry !
	Add( generators, PeakOfnAtg( G, g, n ) );
      fi;
    od;
  od;

  # piecewise constant functions from h+nsgps[i] to nsgps[i+1]
  for i in [1..Length(nsgps)-1] do
    for g in GeneratorsOfGroup( nsgps[i+1] ) do
      reps := NontrivialRepresentativesModNormalSubgroup( G, nsgps[i] );
		# 0-symmetry !
      for h in reps do
        Add( generators, ConstGrpTfmOnRightCosetOfN( G, nsgps[i], g, h ) );
      od;
    od;
  od;

  return TransformationNearRingByAdditiveGenerators( G, generators );

end;

######################################################################
##
#M  ZeroSymmetricCompatibleFunctionNearRing
##

InstallMethod(
	ZeroSymmetricCompatibleFunctionNearRing,
	"as an intersection (use all normal subgroups)",
	true,
	[IsGroup],
	1,
  function( G )
  local gens, visited, n, chain, chains, C, compfcts, K, MakeChain, i;

    gens := ShallowCopy( NormalSubgroups( G ) );
    RemoveElmList( gens, Position( gens, G ) );
    RemoveElmList( gens, Position( gens, TrivialSubgroup( G ) ) );
    if gens = [] then
	return ZeroSymmetricPart(MapNearRing(G));
    fi;
    visited := List( gens, x -> false );
    n := Length(visited);

    # MakeChain uses gens, visited, n and chain as global variables
    # when recursing
    MakeChain := function( j )
    local K;
      K := First( [j+1..n],
	k -> not visited[k] and IsSubset(gens[k],gens[j]) );
      if K=fail then
	return;
      else
	visited[K] := true;
	Add( chain, K );
	MakeChain( K );
	return;
      fi;
    end;

    Info( InfoNearRing, 1, "making subgroup chains..." );
    chains := [];
    for i in [1..Length(visited)] do
      if not visited[i] then
        visited[i] := true;
        chain := [i];
        MakeChain(i);
	Info( InfoNearRing, 2, "chain ", chain );
	Add( chains, chain );
      fi;
    od;
    # longer chains of subgroups will hopefully result in smaller
    # nearrings for intersection, so we begin with the longest chains
    Sort( chains, function( x, y ) return Length(x)>Length(y); end );

    Info( InfoNearRing, 1, "computing additive generators" );
    C := ZeroSymmetricFunctionsCompatibleWithNormalSubgroupChain( G,
					List( chains[1], i->gens[i] ) );
    chains := chains{[2..Length(chains)]};

    for chain in chains do
      Info( InfoNearRing, 1, "computing additive generators" );
      compfcts := ZeroSymmetricFunctionsCompatibleWithNormalSubgroupChain( G,
					List( chain, i->gens[i] ) );
      Info( InfoNearRing, 1, "intersecting nearrings");
      C := Intersection( C, compfcts );
      Info( InfoNearRing, 3, "intersection has size ", Size(C) );
    od;

    return C;

  end );

######################################################################
##
#M  RestrictedCompatibleFunctionNearRing( <S>, <G> )
##  the nearring of functions on <G> compatible with all subgroups
##  of <G> which are normal in <S> (<G> is normal in <S>) 

InstallMethod(
	RestrictedCompatibleFunctionNearRing,
	"as an intersection",
	true,
	[IsGroup,IsGroup],
	0,
  function( S, G )
  local gens, visited, n, chain, chains, C, compfcts, K, MakeChain, i;

    gens := GeneratorsOfIntervallInCongruenceLattice( S, G );
    if gens = [] then
	return MapNearRing(G);
    fi;
    visited := List( gens, x -> false );
    n := Length(visited);

    # MakeChain uses gens, visited, n and chain as global variables
    # when recursing
    MakeChain := function( j )
    local K;
      K := First( [j+1..n],
	k -> not visited[k] and IsSubset(gens[k],gens[j]) );
      if K=fail then
	return;
      else
	visited[K] := true;
	Add( chain, K );
	MakeChain( K );
	return;
      fi;
    end;

    Info( InfoNearRing, 1, "making subgroup chains..." );
    chains := [];
    for i in [1..Length(visited)] do
      if not visited[i] then
        visited[i] := true;
        chain := [i];
        MakeChain(i);
	Info( InfoNearRing, 2, "chain ", chain );
	Add( chains, chain );
      fi;
    od;
    # longer chains of subgroups will hopefully result in smaller
    # nearrings for intersection, so we begin with the longest chains
    Sort( chains, function( x, y ) return Length(x)>Length(y); end );

    Info( InfoNearRing, 1, "computing additive generators" );
    C := FunctionsCompatibleWithNormalSubgroupChain( G,
					List( chains[1], i->gens[i] ) );
    chains := chains{[2..Length(chains)]};

    for chain in chains do
      Info( InfoNearRing, 1, "computing additive generators" );
      compfcts := FunctionsCompatibleWithNormalSubgroupChain( G,
					List( chain, i->gens[i] ) );
      Info( InfoNearRing, 1, "intersecting nearrings");
      C := Intersection( C, compfcts );
      Info( InfoNearRing, 3, "intersection has size ", Size(C) );
    od;

    return C;

  end );


######################################################################
##
#M  CompatibleFunctionNearRing
##

InstallMethod(
	CompatibleFunctionNearRing,
	"cyclic p-groups",
	true,
	[IsGroup],
	20,
  function( G )
  local gens, visited, n, chain, chains, C, compfcts, K, MakeChain, i;
    if not ( IsCyclic(G) and IsPGroup(G) ) then
	TryNextMethod();
    fi;
    gens := Subgroups( G ); gens := gens{[2..Length(gens)-1]};
    if gens = [] then
	return MapNearRing(G);
    fi;

    return FunctionsCompatibleWithNormalSubgroupChain( G, gens );

  end );


######################################################################
##
#M  CompatibleFunctionNearRing
##

InstallMethod(
	CompatibleFunctionNearRing,
	"abelian groups",
	true,
	[IsGroup],
	10,
  function( G )
  local Ggens, exp, g1, exp2, hom, F, preImageList, p,
	UniquePreImagesRepresentativePowExp2, sigmaGens, generators, c;
  if not IsAbelian(G) then
	TryNextMethod();
  fi;

  if IsPGroup( G ) then
	Info( InfoNearRing, 1, "group is abelian p-group" );
        Ggens := GeneratorsOfGroup( G );
        exp := Exponent(G);
  	g1 := First( Ggens, g -> Order(g)=exp );
  	exp2 := Exponent( G/Subgroup(G,[g1]) );
  	if exp2 = Exponent(G) or 2*exp2 = exp then
		Info( InfoNearRing, 3, "Group is affine complete" );
		return PolynomialNearRing( G );
  	fi;

        hom := GroupHomomorphismByImages( G, G, 
			Ggens, List( Ggens, g -> g^exp2 ) );
        F := Image( hom, G );

        preImageList := List( AsSSortedList(F),
				f -> (PreImagesRepresentative(hom,f))^exp2 );
        UniquePreImagesRepresentativePowExp2 := function( f )
		return preImageList[ Position( AsSSortedList(F), f ) ];
	end;

        sigmaGens := AdditiveGenerators( CompatibleFunctionNearRing( F ) );

        generators := List( sigmaGens, sigma ->
		EndoMappingByFunction( G,
			x -> UniquePreImagesRepresentativePowExp2( 
				Image( sigma, Image( hom, x ) ) 
			     ) 
					     )
			  );

        for c in GeneratorsOfGroup( G ) do
	    Add( generators, ConstantEndoMapping( G, c ) );
        od;
        Add( generators, IdentityEndoMapping( G ) );

        return TransformationNearRingByAdditiveGenerators( G, generators );
  else
	TryNextMethod();
  fi;
end );

######################################################################
##
#M  ProjectionsOntoDirectFactors
##

InstallGlobalFunction( ProjectionsOntoDirectFactors,
  function( G, factors )
  local projections, S, actSize, gensS, sumSizes, 
	allGenerators, numberOfGenerators;

    allGenerators := Flat( List( factors, GeneratorsOfGroup ) );
    numberOfGenerators := Length( allGenerators );
    projections := []; sumSizes := 0;
    for S in factors do
	gensS := GeneratorsOfGroup(S);
	actSize := Length( gensS );
	Add( projections, 
	      GroupHomomorphismByImages( G, S, allGenerators, 
		  Concatenation( 
		     List( [1..sumSizes], i -> Identity(S) ), gensS,
		     List( [sumSizes+actSize+1..numberOfGenerators], 
			i -> Identity(S) )
		  )
	      )
	);
	sumSizes := sumSizes + actSize;
    od;

    return projections;
  end );

######################################################################
##
#M  CompatibleFunctionNearRing
##

InstallMethod(
	CompatibleFunctionNearRing,
	"nilpotent groups", 
	true,
	[IsGroup],
	5,
  function( G )
  local sylowSystem, proj, generatorsOfCompFunctNROnFactors,
	generators;
    if (not IsNilpotent( G ) ) or IsPGroup( G ) then
	TryNextMethod();
    fi;

    sylowSystem := SylowSystem( G );
    Info( InfoNearRing, 2, "computing nearrings of compatible functions" );
    Info( InfoNearRing, 2, "on groups of size ", List( sylowSystem, Size) );

    proj := ProjectionsOntoDirectFactors( G, sylowSystem );
    generatorsOfCompFunctNROnFactors :=
	List( sylowSystem, S -> 
		AdditiveGenerators( CompatibleFunctionNearRing( S ) ) );
    generators := Flat( 
	List( [1..Length(sylowSystem)],
		i -> List( generatorsOfCompFunctNROnFactors[i],
			tfm -> EndoMappingByFunction( G,
				x -> Image( tfm, Image( proj[i], x ) ) )
			) )
		  );
    return TransformationNearRingByAdditiveGenerators( G, generators );
  end);

######################################################################
##
#M  DirectFactorisation
##

InstallGlobalFunction( DirectFactorisation,
  function ( G )
   local factorList, rest, N12, c, C, factorsFound; 

   factorList := [];
   rest := G; 
   C := Combinations (NormalSubgroups (G), 2);
   for c in C do
      Sort (c, function (x,y) return Size (x) < Size (y); end);
   od;

   Sort (C, function (p,q) 
              return  Size (p[1]) < Size (q[1]) or 
                        (Size (p[1]) = Size (q[1]) and
                         Size (p[2])< Size (q[2]));
            end);

   while Size (rest) > 1 do
      factorsFound := false;
      for N12 in C do
         if (not factorsFound) and
               Size (N12 [1]) > 1 and Size (N12 [2]) > 1 and
               Size (N12 [1]) * Size (N12 [2]) = Size (rest) and
               Size (Intersection (N12 [1], N12 [2])) = 1 then
            Add (factorList, N12 [1]);
            rest := N12 [2];
            C := Filtered (C, x -> IsSubgroup (rest, x[1]) and
                                   IsSubgroup (rest, x[2]));    
            
            #  Print (List (C, c -> List (c, Size)));
            factorsFound := true;
         fi;
      od;

      if not factorsFound then 
         Add (factorList, rest);
         rest := TrivialSubgroup (G);
      fi;   
   od;
   return factorList;

  end );

######################################################################
##
#M  DirectFactorisationRelativePrime
##

InstallGlobalFunction( DirectFactorisationRelativePrime,
  function ( G )
   local factorList, rest, N12, c, C, factorsFound; 

   factorList := [];
   rest := G; 
   C := Combinations (NormalSubgroups (G), 2);
   for c in C do
      Sort (c, function (x,y) return Size (x) < Size (y); end);
   od;

   Sort (C, function (p,q) 
              return  Size (p[1]) < Size (q[1]) or 
                        (Size (p[1]) = Size (q[1]) and
                         Size (p[2])< Size (q[2]));
            end);

   while Size (rest) > 1 do
      factorsFound := false;
      for N12 in C do
         if (not factorsFound) and
               Size (N12 [1]) > 1 and Size (N12 [2]) > 1 and
	       Gcd( Size (N12 [1]), Size (N12 [2]) ) = 1 and
               Size (N12 [1]) * Size (N12 [2]) = Size (rest) and
               Size (Intersection (N12 [1], N12 [2])) = 1 then
            Add (factorList, N12 [1]);
            rest := N12 [2];
            C := Filtered (C, x -> IsSubgroup (rest, x[1]) and
                                   IsSubgroup (rest, x[2]));    
            
            #  Print (List (C, c -> List (c, Size)));
            factorsFound := true;
         fi;
      od;

      if not factorsFound then 
         Add (factorList, rest);
         rest := TrivialSubgroup (G);
      fi;   
   od;
   return factorList;

  end );

######################################################################
##
#M  CompatibleFunctionNearRing
##

InstallMethod(
	CompatibleFunctionNearRing,
	"direct products rel. prime order", 
	true,
	[IsGroup],
	4,
  function( G )
  local factors, proj, generatorsOfCompFunctNROnFactors,
	generators;
    if IsPGroup( G ) then
	TryNextMethod();
    fi;

    factors := DirectFactorisationRelativePrime( G );
    if Length(factors)=1 then
	TryNextMethod();
    fi;
    proj := ProjectionsOntoDirectFactors( G, factors );
    generatorsOfCompFunctNROnFactors :=
	List( factors, S -> 
		AdditiveGenerators( CompatibleFunctionNearRing( S ) ) );
    generators := Flat( 
	List( [1..Length(factors)],
		i -> List( generatorsOfCompFunctNROnFactors[i],
			tfm -> EndoMappingByFunction( G,
				x -> Image( tfm, Image( proj[i], x ) ) )
			) )
		  );
    return TransformationNearRingByAdditiveGenerators( G, generators );
  end);







ConjugateCompatible := function( f, h )
local G,H;
  G := Source(h);
  H := Image(h,G);
  return EndoMappingByFunction( H, x->Image(h,Image(f,
		PreImagesRepresentative(h,x))));
end;

RestrictToSubgroup := function( f, S )
  return EndoMappingByFunction( S, x -> Image( f, x ) );
end;

######################################################################
##
#M  Is1AffineComplete
##

InstallMethod(
	Is1AffineComplete,
	"small groups",
	true,
	[IsGroup],
	120,
  function( G )
  if Size(G)<=64 then return IdGroup(G) in 
	[ [ 1, 1 ], 
	  [ 2, 1 ], 
	  [ 4, 2 ], 
	  [ 8, 2 ], [ 8, 5 ], 
	  [ 9, 2 ], 
	  [ 16, 2 ], [ 16, 10 ], [ 16, 14 ], [ 16, 12 ], [ 16, 11 ], 
	  [ 18, 5 ], [ 18, 4 ], 
	  [ 25, 2 ], 
	  [ 27, 5 ], 
  	  [ 32, 3 ], [ 32, 21 ], [ 32, 45 ], [ 32, 51 ], [ 32, 46 ], 
	  [ 32, 47 ], [ 32, 27 ], [ 32, 34 ], [ 32, 35 ], 
	  [ 36, 13 ], 
	  [ 50, 4 ], 
	  [ 54, 14 ], 
	  [ 64, 2 ], [ 64, 55 ], [ 64, 73 ], [ 64, 76 ], [ 64, 83 ], 
	  [ 64, 173 ], [ 64, 174 ], [ 64, 175 ], [ 64, 179 ], [ 64, 181 ], 
	  [ 64, 192 ], [ 64, 202 ], [ 64, 211 ], [ 64, 212 ], [ 64, 260 ], 
	  [ 64, 261 ], [ 64, 262 ], [ 64, 267 ] 
	];
  else
	TryNextMethod();
  fi;
  end );

InstallMethod(
	Is1AffineComplete,
	"abelian groups",
	true,
	[IsGroup and IsAbelian],
	110,
  function( G )
  local inv, bases, primes, exponents, p, pexps, i;
    inv := List( AbelianInvariants( G ), Factors );
    bases := List( inv, i -> i[1] );
    exponents := List( inv, Length );
    primes := Set( bases );
    for p in primes do
      pexps := [];
      for i in [1..Length(bases)] do
        if p=bases[i] then
	  Add( pexps, exponents[i] );
        fi;
      od;
      Sort(pexps); pexps := Reversed(pexps);
      if p=2 then
	if Length( pexps ) <> 1 and 
	   pexps[1]-pexps[2]>1 then
		return false;
	fi;
      else
	if Length( pexps ) = 1 or
	   pexps[1]<>pexps[2] then
		return false;
	fi;
      fi;
    od;

    return true;
   
  end );

InstallMethod(
	Is1AffineComplete,
	"2-group",
	true,
	[IsGroup and IsPGroup],
	105,
  function( G )
    local complement;
    if Factors( Size( G ) )[1] <> 2 then
	TryNextMethod();
    fi;
    if Size( DerivedSubgroup( G ) ) <> 2 then
	TryNextMethod();
    fi;
    complement := function( G, I )
  	return ClosureSubgroups( G, 
	Filtered( NormalSubgroups(G), 
			n -> Size( Intersection( n, I ) ) = 1 ) );
    end;
    return Size(G)=4*Size(Centre(G)) and
	   Exponent(G)=4 and
	   Exponent(G/DerivedSubgroup(G))=2 and
	   Size(G)=4*Size(complement( G, DerivedSubgroup( G ) ));
end );

InstallMethod(
	Is1AffineComplete,
	"small centre",
	true,
	[IsGroup and IsPGroup],
	102,
  function ( G )
    if Factors( Size( G ) )[1] = 2 then
	TryNextMethod();
    fi;
    if Length( Factors( Size( Centre( G ) ) ) ) < 3 then
	return false;
    else
	TryNextMethod();
    fi;
  end );

InstallMethod(
	Is1AffineComplete,
	"small factor by centre",
	true,
	[IsGroup and IsPGroup],
	101,
  function ( G )
    if Factors( Size( G ) )[1] = 2 then
	TryNextMethod();
    fi;
    if Length( Factors( Size( G / Centre( G ) ) ) ) < 3 then
	return false;
    else
	TryNextMethod();
    fi;
  end );
 
InstallMethod(
	Is1AffineComplete,
	"cyclic centre",
	true,
	[IsGroup and IsPGroup],
	100,
  function ( G )
    if Factors( Size( G ) )[1] = 2 then
	TryNextMethod();
    fi;
    if IsCyclic( Centre( G ) ) then
	return false;
    else
	TryNextMethod();
    fi;
  end );

InstallMethod(
	Is1AffineComplete,
	"small commutator",
	true,
	[IsGroup and IsPGroup],
	97,
  function ( G )
    if Factors( Size( G ) )[1] = 2 then
	TryNextMethod();
    fi;
    if Length( Factors( Size( DerivedSubgroup( G ) ) ) ) < 3 then
	return false;
    else
	TryNextMethod();
    fi;
  end );

InstallMethod(
	Is1AffineComplete,
	"cyclic commutator",
	true,
	[IsGroup and IsPGroup],
	95,
  function ( G )
    if Factors( Size( G ) )[1] = 2 then
	TryNextMethod();
    fi;
    if IsCyclic( DerivedSubgroup( G ) ) then
	return false;
    else
	TryNextMethod();
    fi;
  end );

InstallMethod(
	Is1AffineComplete,
	"cyclic centre",
	true,
	[IsGroup and IsPGroup],
	90,
  function ( G )
    if Factors( Size( G ) )[1] = 2 then
	TryNextMethod();
    fi;
    if IsCyclic( Intersection( DerivedSubgroup(G), Centre( G ) ) ) then
	return false;
    else
	TryNextMethod();
    fi;
  end );

InstallMethod(
	Is1AffineComplete,
	"nilpotent group",
	true,
	[IsGroup],
	80,
  function ( G )
  if IsPGroup(G) or not( IsNilpotentGroup( G ) ) then
	TryNextMethod();
  fi;
  return ForAll( SylowSystem( G ), Is1AffineComplete );
end
);


InstallMethod(
	Is1AffineComplete,
	"default",
	true,
	[IsGroup],
	0,
  G -> Size( CompatibleFunctionNearRing(G) ) = Size( PolynomialNearRing(G) ) );

#CanBe1AffineComplete := function ( G )
#
# local p, normals, minimals, J, Jlist, canbeaffinecomplete, i, j;
 
#
#
# p := FactorsInt (Size(G)) [1];
# normals := NormalSubgroups (G);
# minimals := Filtered (normals, x -> Size(x) = p);
# canbeaffinecomplete := true;
# i := 1;
# while canbeaffinecomplete and i <= Length(minimals) do
##    Print (i);
#    Jlist := Filtered (normals, x -> not IsSubgroup (x, minimals [i]));
#    J := Jlist[1];
#    for j in [2..Length (Jlist)] do
#       J := ClosureGroup (J, Jlist[j]);
#    od;
#    canbeaffinecomplete := (Size(J) = Size (G));
#    if canbeaffinecomplete then
#       i := i + 1;
##       Print(i);
#    fi;
# od;
# return canbeaffinecomplete;
#end;

NarrowCongruences := function( G )
local gens, nsgs;
  gens := GeneratorsOfCongruenceLattice( G );
  nsgs := NormalSubgroups( G );
  return Filtered( nsgs, N -> 
	Size(N)>1 and Size(N)<Size(G) and
	ForAll( gens, I -> IsSubset(I,N) or IsSubset(N,I) ) );
end;


######################################################################
##
#F  PrintAsTerm( <poly> )
##
##  print a polynomial function as a term

DeclareGlobalFunction( "PrintAsTerm" );

InstallGlobalFunction( PrintAsTerm,

function ( p )
local names, P, Pgen, Pgroup, F, Fgen, hom, term,
	letter, exponent, first, i, len;
  P := PolynomialNearRing( Source(p) );
  if not p in P then
	Error("Transformation has to be a polynomial function");
  fi;
  Pgroup := GroupReduct( P );
  Pgen := GeneratorsOfGroup( Pgroup );
  names := List( [1..Length(Pgen)-1],
			i -> Concatenation( "g", String(i) ) );
  Add( names, "x" );
  F := FreeGroup( names );
  Fgen := GeneratorsOfGroup(F);
  hom := GroupHomomorphismByImagesNC( F, Pgroup, Fgen, Pgen );
  term := PreImagesRepresentative( hom, AsGroupReductElement(p) );

  len := Length(term);
  if term = Identity(F) then
	Print( " 0 " );
  else
	letter := Subword(term,1,1);
	exponent := 1;
	first := true;
	for i in [2..len] do
		if Subword(term,i,i)<>letter then
			if letter in Fgen then
				if not first then
					Print(" + ");
				else
					first := false;
				fi;
				if exponent>1 then
					Print(exponent," * ");
				fi;
				Print(letter);
			else
				Print(" - ");
				if exponent>1 then
					Print(exponent," * ");
				fi;
				Print(letter^-1);
				first := false;
			fi;
			letter := Subword(term,i,i);
			exponent := 1;
		else
			exponent := exponent + 1;
		fi;
	od;
	if letter in Fgen then
		if not first then
			Print(" + ");
		fi;
		if exponent>1 then
			Print(exponent," * ");
		fi;
		Print(letter);
	else
		Print(" - ");
		if exponent>1 then
			Print(exponent," * ");
		fi;
		Print(letter^-1);
	fi;
  fi;
  Print("\n");

 end );

LiftCompGenFromQuotByMinDistNormSgp :=
  function( G, A, K, phi )
# phi is a compatible function on G/A
# K is the sum of all ideals of G having trivial intersection with A  
  local R, S, epsA, epsK, E, listG, gens, phiA, 
	t, e, si, x, s, dx, cx, psix, pos;

    # coset representatives
    epsA := NaturalHomomorphismByNormalSubgroup( G, A );
    epsK := NaturalHomomorphismByNormalSubgroup( G, K );
    phiA := epsA*phi;

    R := List( Image(epsA), x -> PreImagesRepresentative( epsA, x ) );
    S := List( Image(epsK), x -> PreImagesRepresentative( epsK, x ) );

    E := Enumerator( A );
    listG := AsSSortedList( G );

    gens := [];

    for t in Tuples( [1..Size(A)], Length(S) ) do
      psix := [];
      # compute offset cx for every x in G
      for x in listG do
	s := PreImagesRepresentative( epsK, Image( epsK, x ) );
        dx := PreImagesRepresentative( epsA, Image( phiA, x ))^(-1)
            * PreImagesRepresentative( epsA, Image( phiA, s ));
        cx := Intersection( RightCoset( K, dx ), A )[1];
        Add( psix, PreImagesRepresentative( epsA, Image( phiA, x )) * cx*
	 E[ t[ Position( S, s) ] ] );
      od;
      pos := List( psix, y -> Position( listG, y ) );
      Add( gens, EndoMappingByPositionList( G, pos ) );
#       Add( gens, AsEndoMapping( GroupGeneralMappingByImages( G, G, listG, psix ) ) );
    od;
    Info( InfoNearRing, 3, "single generator lifted" );
    return gens;
end;

######################################################################
##
#M  DistributiveMinimalNormalSubgroupsAndComplements
##

#InstallMethod(
#	DistributiveMinimalNormalSubgroup,
#	"filter OneGeneratedNormalSubgroups",
#	[IsGroup],
#	0,
DistributiveMinimalNormalSubgroupsAndComplements :=
  function( G )
  local M, A, I, J, K, nondist, DMNSGC;
    M := MinimalNormalSubgroups( G );
    A := NormalSubgroups(G);
    DMNSGC := [];
    for J in M do
      nondist := false;
      K := TrivialSubgroup( G );
      for I in A do
        if not( IsSubset( I, J ) ) then
	  K := ClosureGroup( K, I );
	  if IsSubset( K, J ) then
	     nondist := true;
	     break;
	  fi; 
        fi;
      od;
      if not(nondist) then
	Add( DMNSGC, [J,K] );
      fi;
    od;
    return DMNSGC;
end;

InstallMethod(
	CompatibleFunctionNearRing,
	"distributive minimal normal subgroup",
	[IsGroup],
	3,
  function( G )
  local H, A, K, CGAgens, psi, CGgens, epsA, R, x, gen, e, g, numbersofgens;
    H := DistributiveMinimalNormalSubgroupsAndComplements( G );

    if H=[] then
	TryNextMethod();
    fi;
    
    # case 1: unique minimal normal subgroup

    if Length(H)=1 and Size(H[1][2])=1 then
      Info( InfoNearRing, 1, "group has a unique minimal normal subgroup" );
      A := H[1][1];
      CGAgens := AdditiveGenerators( CompatibleFunctionNearRing( G/A ) );
      epsA := NaturalHomomorphismByNormalSubgroup( G, A );
      R := List( Image(epsA), x -> PreImagesRepresentative( epsA, x ) );
      CGgens := List( CGAgens, gen ->
	EndoMappingByFunction( G, 
	x -> PreImagesRepresentative( epsA, Image( gen, Image( epsA, x ) ) ) ) );
      for g in G do
        for e in GeneratorsOfGroup( A ) do
	   Add( CGgens, PeakOfnAtg( G, g, e ) );
        od;
      od;
      return TransformationNearRingByAdditiveGenerators( G, CGgens );
    fi;

    # case 2: low index complement

    numbersofgens := List( H, AK -> Size(AK[1])^(Size(G)/Size(AK[2])));
    SortParallel( numbersofgens, H );
    
    if numbersofgens[1] < 500 then
      Info( InfoNearRing, 1, 
	"group has a distributive minimal normal subgroup" );
      Info( InfoNearRing,1,
	"with a low exponent complement" );
      A := H[1][1]; K := H[1][2];
      Info( InfoNearRing, 2, "computing nearring of compatible functions" );
      Info( InfoNearRing, 2, "on a quotient of size ", Size(G)/Size(A) );
      CGAgens := AdditiveGenerators( CompatibleFunctionNearRing( G/A ) );
      Info( InfoNearRing, 2, "lifting ", Length( CGAgens )," generators" );
      if Length( CGAgens ) * numbersofgens[1] > 1000 then
	Info( InfoNearRing, 1, "giving up, too many generators" );
	TryNextMethod();
      fi;
      CGgens := Flat( List( CGAgens, 
            psi -> LiftCompGenFromQuotByMinDistNormSgp( G, A, K, psi ) ) );
      return TransformationNearRingByAdditiveGenerators( G, CGgens );
    fi;

    # case 3: more than 1000 generators expected, give up

    TryNextMethod();

  end );    

#InstallMethod(
#	Is1AffineComplete,
#	"distributive minimal normal subgroup",
#	true,
#	[IsGroup],
#	70,
#  function( G )
#  if ForAny( DistributiveMinimalNormalSubgroupsAndComplements( G ),
#	P -> not( Is1AffineComplete( G/P[1] ) ) ) then
#    return false;
#  fi;
#  TryNextMethod();
#end
#);


SizeOfCentralizerOfJmodIinG := function(G, J, I )
  local e, c;
    e := NaturalHomomorphismByNormalSubgroup( G, I );
    c := Centralizer( Image(e,G), Image(e,J) );
    return Size(c)*Size(I);
end;

InstallMethod(
	Is1AffineComplete,
	"distributive minimal normal subgroup",
	true,
	[IsGroup],
	70,
  function( G )
  local P, p, a, astar, sizec;
    P := DistributiveMinimalNormalSubgroupsAndComplements( G );
    if P=[] then
	TryNextMethod();
    fi;
    if ForAny( P, p -> not( Is1AffineComplete( G/p[1] ) ) )
	then return false;
    fi;
    p:=P[1];
    a := p[1]; astar := p[2]; 
    sizec := SizeOfCentralizerOfJmodIinG( G, G, astar );
    return (sizec=Size(G) and sizec/Size(astar)=2) or
	   (sizec=Size(astar) and not (IsAbelian( a ) ) );
end
);  

InstallMethod(
	Is1AffineComplete,
	"minimal normal subgroup with 1ac quotient",
	true,
	[IsGroup],
	60,
  function( G )
  local M, Mstar;
    M := Filtered(
	MinimalNormalSubgroups( G ), m -> Is1AffineComplete( G/m ) );
    if M=[] then
	TryNextMethod();
    fi;
    if ForAny( M, m -> not IsAbelian(m) ) then
	return true;
    fi;
    M := M[1];
    Mstar := ClosureSubgroups( G, 
	Filtered( NormalSubgroups(G), I -> not( IsSubset(I,M) ) ) );
    if Size(Mstar)<Size(Centre(G)) and IsSubset( Centre(G), Mstar ) then 
	return false;
    else
    	return Size(PolynomialNearRing(G)) = 
		Size( PolynomialNearRing( G/M ) ) * 
		Size(M)^(Size(G)/Size(Mstar));
    fi;
end 
);

	

    





