module Algebra::Galois

Public Instance Methods

complete(ary, sf) click to toggle source
# File lib/algebra/galois-group.rb, line 78
def complete(ary, sf)
  # INPUT:
  #   ary: the first l-part of g
  #   sf: splitting field
  # OUTPUT:
  #   ary0: the complete expression of g

  ary0 = ary.dup
  roots = sf.proots

  n = roots.size
  m = sf.def_polys.size
  for i in m...n
    ri = roots[i].abs_lift
    h = if ri.is_a? Algebra::Polynomial
          r = roots.values_at(*ary0[0...m])
          ri.evaluate(*r)
        else
          ri
        end
    for k in 0...n
      ary0.push k if !ary0.include?(k) && roots[k] == h
    end
  end
  raise "complete: #{ary.inspect} is not extendable." if ary0.size != n
  ary0
end
galois_group(pre_facts = nil, sw = nil) click to toggle source
# File lib/algebra/galois-group.rb, line 18
def galois_group(pre_facts = nil, sw = nil)
  # sw : Ordinary, sw is asumed to be nil.

  poly = sqfree

  sf = poly.splitting_field(pre_facts, nil, true)

  gens = []
  reps0 = []
  n = poly.deg
  dpn = sf.def_polys.size
  for i in 0...dpn do
    reps = []
    for j in (sw ? i : i + 1)...n do
      if g = prolong((0...i).to_a + [j], sf)
        reps << g
      end
    end
    gens.unshift reps
    #      gens.push reps
  end

  for i in dpn...n; gens << [(0...n).to_a]; end if sw
  gs = gens.map { |a| a.map { |g| complete(g, sf) } }
  ary_of_gens = gs.collect { |a| a.collect { |x| Permutation.new(x) } }
  PermutationGroup.generate_strong(Permutation.unity(n), *ary_of_gens)
end
prolong(ary, sf) click to toggle source
# File lib/algebra/galois-group.rb, line 46
def prolong(ary, sf)
  # INPUT
  #  ary: a set of defining polynomial
  #  sf: splitting field
  # OUTPUT:
  #  ary0: the first l-part of g if g exists; nil other wize

  t = ary.size
  roots = sf.proots

  pn = sf.def_polys.size
  defs = sf.def_polys
  for i in 0...t do
    r = roots.values_at(*ary)[0..i]
    return nil unless defs[i].abs_lift.evaluate(*r).zero? # this eval. needs no_sq
  end

  ary0 = ary.dup
  for k in t...defs.size do
    sw = false
    for c in (0...roots.size).to_a - ary0 do
      r = roots.values_at(* ary0 + [c])[0..k]
      next unless defs[k].abs_lift.evaluate(*r).zero? # this eval. needs no_sq
      ary0.push c
      sw = true
      break
    end
    return nil unless sw
  end
  ary0
end