Elementos abstractos en AjGroups

Published on Author lopezLeave a comment

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

Leave a Reply

Your email address will not be published. Required fields are marked *