Angel "Java" Lopez

He escrito sobre mi librería de grupos finitos AjGroups en mis anteriores posts:

Presenting AjGroups: Finite Groups Library
Presentando AjGroups: una Librería de Grupos Finitos
Permutations in AjGroups
Permutaciones en AjGroups

Ahora, quiero presentar otra de las implementaciones de un grupo finito que usé la solución: una basada, no en permutaciones explícitas, sino en elementos abstractos.

Un elemento abstracto es identificado por un nombre:

Los nombres pueden ser letras: a, b, c, …. Por convención, el elemento e es la identidad. Entonces

a * e = e * a

para cualquier a. Pero, ¿cuál es el resultado de a * b para a, b cualesquiera en un grupo? Los resultados están en un OperationTable:

El OperationTable mantiene una lista de elementos y una matriz. Cada celda de la matriz tiene el resultado de dos elementos:

public void SetValue(IElement left, IElement right, IElement value)
{
    this.SetValue(elements.IndexOf(left), elements.IndexOf(right), value);
}
public IElement GetValue(IElement left, IElement right)
{
    return this.GetValue(elements.IndexOf(left), elements.IndexOf(right));
}
internal void SetValue(int leftpos, int rightpos, IElement value)
{
    cells[leftpos, rightpos] = value;
}
internal IElement GetValue(int leftpost, int rightpos)
{
    return cells[leftpost, rightpos];
}
		
La OperationTable puede ser armada calculando sobre permutaciones (elementos concretos). Un test:
[TestMethod]
public void CalculateSymmetricGroupTable()
{
    IGroup group = new SymmetricGroup(3);
    OperationTable table = new OperationTable(group.Elements);
    table.Calculate();
    foreach (IElement left in group.Elements)
        foreach (IElement right in group.Elements)
            Assert.AreEqual(left.Multiply(right), table.GetValue(left, right));
}

Pero esa no era mi idea: quiero usar OperationTable con elementos abstractos, y construir a mano o por algún cálculo (más detalles abajo) la matriz con los resultados de las multiplicaciones.
La OperationTable tiene métodos como: .HasIdentity, .IsAssociative, .IsConmutative, para determinar sus propiedades. No toda tabla será compatible con los axiomas de grupo. Un test:
[TestMethod]
public void SymmetricGroupThreeOperationIsAssociative()
{
    OperationTable table = new OperationTable((new SymmetricGroup(3)).Elements);
    table.Calculate();
    Assert.IsTrue(table.IsAssociative);
}

Notablemente, la OperationTable puede estar incompleta: puede que algunas celdas esté indefinidas. El método .IsClosed retorna true si la matriz de multiplicación está completamente definida, y cada resultado de la multiplicación de dos elementos cualquiera está completamente definida.
La OperationTable puede ser construida a mano. Por ejemplo, la tabla:
 
se construye y prueba en este test:
[TestMethod]
public void CreateWithNamedIdentityAndOneElement()
{
    NamedElement identity = new NamedElement('e');
    NamedElement aelement = new NamedElement('a');
    OperationTable table = new OperationTable(new List<IElement>() { identity , aelement}, true);
    identity.OperationTable = table;
    aelement.OperationTable = table;
    table.SetValue(aelement, aelement, identity);
    Assert.IsTrue(table.HasIdentity);
    Assert.IsTrue(table.IsAssociative);
    Assert.IsTrue(table.IsClosed);
    Assert.IsTrue(table.IsCommutative);
    Assert.AreEqual(2, table.Elements.Count);
    Assert.AreEqual(identity, table.GetValue(identity, identity));
    Assert.AreEqual(aelement, table.GetValue(aelement, identity));
    Assert.AreEqual(aelement, table.GetValue(identity, aelement));
    Assert.AreEqual(identity, table.GetValue(aelement, aelement));
    Assert.AreEqual(1, identity.Order);
    Assert.AreEqual(2, aelement.Order);
}

Pero mi método preferido en OperationTable es el método .GetSolutions(). Dada una OperationTable incompleta, retorna una lista de OperationTables completas (con todas las multiplicaciones definidas) que son compatibles con los axiomas de grupo. Sea esta tabla inicial incompleta:
 
Aplicando .GetSolutions() a esta tabla de operaciones retorna una lista con un solo elemento (la tabla del único grupo finito de 3 elementos):
 
Noten: cada fila y cada columna ES una permutación de los elementos originales. Esa regla es necesaria según los axiomas de grupo.
Un test:
[TestMethod]
public void GetGroupsOfOrderThree()
{
    NamedElement identity = new NamedElement('e');
    NamedElement aelement = new NamedElement('a');
    NamedElement belement = new NamedElement('b');
    OperationTable table = new OperationTable(new List<IElement>() { identity, aelement, belement }, true);
    IList<OperationTable> solutions = table.GetSolutions().ToList();
    Assert.IsNotNull(solutions);
    Assert.AreEqual(1, solutions.Count);
    Assert.IsTrue(solutions[0].IsClosed);
}

Pero una OperationTable no es un IGroup. Hay otra clase TableGroup:
 
Su constructor recibe una OperationTable: clona sus elementos (que deben ser abstracots), clona su OperationTable, para armar un nuevo grupo abstracto.
Las tablas retornadas por .GetSolutions() no son todos diferentes según isomorfismos. Tengo un método, internamente usado por los tests, que retorna todos los grupos esencialmente distintos de orden n, partiendo en cada caso de una tabla incompleta y aplicándole .GetSolutions() y filtro por isomorfismo:
private static IList<IGroup> GetGroupsOfOrder(int order)
{
    IList<IElement> elements = new List<IElement>();
    for (int k = 0; k < order; k++)
        elements.Add(new NamedElement(k));
    OperationTable table = new OperationTable(elements, true);
    IList<OperationTable> solutions = table.GetSolutions().ToList();
    foreach (OperationTable solution in solutions)
    {
        Assert.IsTrue(solution.HasIdentity);
        Assert.IsTrue(solution.IsAssociative);
        Assert.IsTrue(solution.IsClosed);
    }
    IList<IGroup> groups = new List<IGroup>();
    foreach (OperationTable ot in solutions)
        groups.Add(new TableGroup(ot));
    IList<IGroup> dgroups = GroupUtilities.GetNonIsomorphic(groups);
    return dgroups;
}

El método .GetSolutions() se basa en el uso del método .GetCompatibleTable(a,b,c) que trata de agregar la ecuación:
a * b = c
a una OperationTable, sin romper los axiomas de grupo. Si una tabla compatible existe, el método la retorna, sin alterar la original. Si no existe, retorna null.
Todo esto fue construido usando Test-Driven Development (TDD). Notablemente, el diseño original no incluía elementos abstractos: estaba basado totalmente en permutaciones. Próximo post: describir cómo TDD “salvó mi día”, cuando tuve que agregar elementos abstractos.
Nos leemos!
Angel “Java” Lopez

  
http://www.ajlopez.com 
http://twitter.com/ajlopez


				

En mi anterior post presenté a AjGroups, una librería de clases escrita en C# que implementa conceptos y operaciones de grupos finitos. El código fuente está en mi AjCodeKata Google Project, en trunk/AjGroups.

En este post, quisiera explicar una de las implementaciones que están dentro de AjGroups: grupos basados en permutaciones.

Una permutación es una aplicación biyectiva de un conjunto S a S. Sea

S = { 0, 1, 2, 3, 4 }

Entonces, un ejemplo de permutación es:

i(0)=0, i(1)=1, i(2)=2, i(3)=3, i(4)=4

Es la permutación identidad. Otro ejemplo:

s(0)=1, s(1)=0, s(2)=2, s(3)=3, s(4)=4

Esta es un “swap”, un intercambio de los dos primeros elementos. Una permutación “rotación”:

r(0)=1, r(1)=2, r(2)=3, r(3)=4, r(4)=0

Las permutaciones pueden combinarse para dar otras permutaciones, r*s:

(r*s)(n) = r(s(n))

Las permutaciones de S son los elementos de un grupo que usa la operación *. AjGroups implementa una permutación usando la clase Element:

    public class Element : AjGroups.IElement
    {
        private byte[] values;
        public Element(params byte[] values)
        {
//....
    }
La permutación se representa en un arreglo de bytes, donde values[k] es el resultado de f(k), siendo f la permutación representada por el Element.
Element.Multiply(Element element) implementa la multiplicación:
       public Element Multiply(Element element)
        {
            int k;
            int length1 = this.values.Length;
            int length2 = element.values.Length;
            int newlength = Math.Max(length1, length2);
            byte[] newvalues = new byte[newlength];
            for (k = 0; k < newlength; k++)
            {
                if (k >= length2)
                {
                    newvalues[k] = this.values[k];
                }
                else if (element.values[k] >= length1)
                {
                    newvalues[k] = element.values[k];
                }
                else
                {
                    newvalues[k] = this.values[element.values[k]];
                }
            }
            return new Element(newvalues);
        }
Noten que el método soporta la multiplicación de permutaciones de diferentes tamaños. 
Element.CreateIdentity genera un elemento identidad, de tamaño n.
Creando un swap de las dos primeras posiciones:
        public static Element CreateSwap(int size) 
        {
            Element element = CreateIdentity(size);
            element.values[0] = 1;
            element.values[1] = 0;
            return element;
        }

Creando un intercambio en una posición:
        public static Element CreateSwap(int size, int position)
        {
            Element element = CreateIdentity(size);
            element.values[position] = (byte) (position+1);
            element.values[position+1] = (byte) position;
            return element;
        }

Creando la rotación:
        public static Element CreateRotation(int size)
        {
            byte[] values = new byte[size];
            for (int k = 0; k < size; k++)
            {
                values[k] = (byte)(k == size - 1 ? 0 : k + 1);
            }
            return new Element(values);
        }

Un CompleteGroup es un grupo con todos sus elementos dados en el constructor:
    public class CompleteGroup : BaseGroup
    {
        private List<IElement> elements;
        public CompleteGroup(List<IElement> elements)
        {
            this.elements = elements.Distinct().ToList();
        }
//...
    }
Un GeneratedGroup es el resultado de combinar un conjunto de elementos generadores:
    public class GeneratedGroup : CompleteGroup
    {
        public GeneratedGroup(params IElement[] generators)
            : base(ElementUtilities.ElementsClosure(generators))
        {
        }
    }

ElementsUtilities.ElementsClosure es generada por todas las multiplicaciones (a(a*b, b*a, a*b*b, a*c*b… ) de los elementos iniciales presentados (a, b, c, …)
Notablemente, las permutaciones de S son generadas usando un swap y una rotación:
    public class SymmetricGroup : GeneratedGroup
    {
        public SymmetricGroup(int size)
            : base(Element.CreateSwap(size), Element.CreateRotation(size))
        {
        }
    }

Se puede probar que todo grupo finito es un subgrupo de un grupo generado por estos dos elementos: el llamado grupo simétrico de permutaciones de n elementos.
Como mencioné en el anterior post, hay otra implementación de grupos finitos en AjGroups: usando elementos abstractos, no permutaciones concretas. Seré el tema de un próximo post.
Nos leemos!
Angel “Java” Lopez

  
http://www.ajlopez.com 
http://twitter.com/ajlopez


				

Estuve escribiendo una librería de clases C# para manejar grupos finitos. Un grupo es un conjunto G de elementos dotados de una operación binaria *, dondee:

a * b  is in G    (clausura)

a * (b * c) = (a * b) * c        (asociatividad)

a * a’ = e     (existencia de inverso e identidad)

a * e = e * a   (identidad)

El código de la solución está en AjCodeKata Google Project, en trunk/AjGroups:

Las principales interfaces son:

IElement tiene un método Multiply, que recibe otro IElement y retorna el resultado IElement. IElement.Order es el número de elementos a ser multiplicados para obtener la identidad:

a * a * a ….. * a = e

IGroup.Elements es la colección de IElements que son elementos del grupo. IGroup.Order es la cantidad de elementos.

Hay dos implementaciones de esas interfaces: una basada en permutaciones, otra basada en elementos con nombre (como “a”, “e”) y una tabla describiendo sus multiplicaciones.

Hay métodos para:

– Obtener los subgrupos de un grupo
– Obtener los subgrupos normales de un grupo
– Determinar si dos grupos son isomorfos

Seguí Test-Driven Development (TDD). Todos los tests en verde:

Buen code coverage:

Debería hacer algún refactoring, pero el proyecto va tomando forma. Escribiré posts describiendo la implementación de permutaciones, y la otra, la basada en elementos abstractos.

Nos leemos!

Angel “Java” Lopez
http://www.ajlopez.com
http://twitter.com/ajlopez