Simple unsolved math problem, 8

Sylver coinage is a game for 2 players invented by John H. Conway.

The two players take turns naming positive integers that are not the sum of non-negative multiples of any previously named integers. The player who is forced to name 1 loses.

James Joseph Sylvester proved the following fact.

Lemma: If a and b are relatively prime positive integers, then (a – 1)(b – 1) – 1 is the largest number that is not a sum of nonnegative multiples of a and b.

Therefore, if a and b have no common prime factors and are the first two moves, this formula gives an upper bound on the next number that can still be played.

R. L. Hutchings proved the following fact.

Theorem: If the first player selects any prime number p>3 as a first move then he/she has a winning strategy.

Very little is known about the subsequent winning moves. That is, a winning strategy exists but it’s not know what it is!

Unsolved problem:Are there any non-prime winning opening moves in Sylver coinage?

For further info, Sicherman maintains a Sylver coinage game webpage.

Sports ranking methods, 4

This is the fourth of a series of expository posts on matrix-theoretic sports ranking methods. This post discusses the Elo rating.

This system was originally developed by Arpad Elo (Elo (1903-1992) was a physics professor at Marquette University in Milwaukee and a chess master, eight-time winner of the Wisconsin State Chess Championships.) Originally, it was developed for rating chess players in the 1950s and 1960s. Now it is used for table tennis, basketball, and other sports.

We use the following version of his rating system.

As above, assume all the $n$ teams play each other (ties allowed)
and let r_i denote the rating of Team i, i=1,2,\dots,n.

Let A=(A_{ij}) denote an $n\times n$ matrix of score results:

A_{ij}= \left\{ \begin{array}{rr} -1,& {\rm if\ team\ } i {\rm \ lost\ to\ team\ } j,\\ +1,& {\rm if\ team\ } i {\rm\ beat\ team\ } j,\\ 0, & {\rm if}\ i=j. \end{array} \right.

Let S_{ij}=(A_{ij}+1)/2.

As in the previous post, the matrix A associated to the example of the Patriot league is the adjacency matrix of a diagraph.

  1. Initialize all the ratings to be 100: {\bf r}=(r_1,\dots,r_n) = (100,\dots,100).
  2. After Team i plays Team j, update their rating using the formula

    r_i = r_i+K(S_{ij}-mu_{ij}),

    where K=10 and

    \mu_{ij} = (1+e^{-(r_i-r_j)/400})^{-1}.

In the example of the Patriot league, the ratings vector is

{\bf r}=(85.124, 104.79, 104.88, 85.032, 94.876, 124.53).

This gives the ranking

Lafayette < Army < Lehigh < Bucknell < Holy Cross < Navy.

This gives a prediction failure rate of 13.3\%.

Some SageMath code for this:

def elo_rating(A):
    """
    A is a signed adjacency matrix for a directed graph.

    Returns elo ratings of the vertices of Gamma = Graph(A) 
        
    EXAMPLES:
        sage: A = matrix(QQ,[
        [0 , -1 , 1  , -1 , -1 , -1 ],
        [1,   0 ,  -1,  1,  1,   -1  ],
        [-1 , 1 ,  0 ,  1 , 1  , -1  ],
        [1 , -1 , -1,  0 ,  -1 , -1  ],
        [1 , - 1 , - 1 , 1 , 0 , - 1  ],
        [1 ,  1  ,  1  , 1  , 1  , 0 ]
        ])
        sage: elo_rating(A)
        (85.124, 104.79, 104.88, 85.032, 94.876, 124.53)

    """
    n = len(A.rows())
    RR = RealField(prec=20)
    V = RR^n
    K = 10
    r0 = 100 # initial rating
    r = n*[r0]
    for i in range(n):
        for j in range(n):
            if ij and A[i][j]==1:
                S = 1
            elif ij and A[i][j]==-1:
                S = 0
            else:
                S = 1/2
            mu = 1/(1+e^(-(r[i]-r[j])/400))
            r[i] = r[i]+K*(S-mu)
    return V(r)

How do I construct … in GAP?

This page is devoted to answering some basic questions along the line
“How do I construct … in GAP?” You may view the html source code
for the GAP commands without the output or GAP prompt.

Please send suggestions, additions, corrections to
David Joyner.

This page itself is under construction…


Questions

How
do I construct a … group?

permutation
dihedral 
cyclicconjugacy classes of a
finitely presented

How
do I … a polynomial?
How do I find the … of a group
representation?
How
do I compute an mod m, where A is …?
Given
a group G, how do I compute … ?

Answers


    • permutation:
      To construct a permutation group, write down generators in disjoint cycle notation,
      put them in a list (i.e., surround them by square brackets), andThe permutation group G generated by the cycles
      (1,2)(3,4) and (1,2,3):
gap> G:=Group((1,2)(3,4),(1,2,3));

Group([ (1,2)(3,4), (1,2,3) ])

This is of course a subgroup of the symmetric group S4 on 4
letters.
Indeed, this G is in fact the alternating group
on four letters, A4.

By virtue of the fact that the permutations generating G employ
integers less than or equal to 4, this group G
is a subgroup of the symmetric group S4 on 4
letters. Some permutation groups have special constructions:

gap> S4:=SymmetricGroup(4);
Sym( [ 1 .. 4 ] )
gap> A4:=AlternatingGroup(4);
Alt( [ 1 .. 4 ] )
gap> IsSubgroup(S4,G);
true
gap> IsSubgroup(A4,G);
true
gap> S3:=SymmetricGroup(3);
Sym( [ 1 .. 3 ] )
gap> IsSubgroup(S3,G);
false


    • dihedral
      To construct a dihedral group, use the special “DihedralGroup” command:
gap> G:=DihedralGroup(6);

gap> Size(G);
6
gap> f:=GeneratorsOfGroup( G );
[ f1, f2 ]
gap> f[1]^2; f[2]^3;
identity of ...
identity of ...
gap> f[1]^2= f[2]^3;
true


  • cyclic group
    To construct a cyclic group, you may
    construct integers mod n:

    gap> R:=ZmodnZ( 12);
    (Integers mod 12)
    gap> a:=Random(R);
    ZmodnZObj( 11, 12 )
    gap> 4*a;
    ZmodnZObj( 8, 12 )
    gap> b:=Random(R);
    ZmodnZObj( 9, 12 )
    gap> a+b;
    ZmodnZObj( 8, 12 )
    

    or use the special “CyclicGroup” command

    gap> G:=CyclicGroup(12);
    pc group of size 12 with 3 generators
    gap> a:=Random(G);
    f3^2
    gap> f:=GeneratorsOfGroup( G );
    [ f1, f2, f3 ]
    gap> f[1]^4;
    f3
    gap> f[1]^12;
    identity of ...
    
    


  • conjugacy:
    The conjugacy classes of a group G are computed using
    the “ConjugacyClasses” command. This is a list
    of classes{x^-1*g*x | x in G}.

    gap> G:=SL(2,7);
    SL(2,7)
    gap> CG:=ConjugacyClasses(G);
    [ [ [ Z(7)^0, 0*Z(7) ], [ 0*Z(7), Z(7)^0 ] ]^G,
      [ [ 0*Z(7), Z(7)^3 ], [ Z(7)^0, Z(7)^5 ] ]^G,
      [ [ 0*Z(7), Z(7)^4 ], [ Z(7)^5, Z(7)^5 ] ]^G,
      [ [ Z(7)^3, 0*Z(7) ], [ 0*Z(7), Z(7)^3 ] ]^G,
      [ [ 0*Z(7), Z(7)^3 ], [ Z(7)^0, Z(7)^2 ] ]^G,
      [ [ 0*Z(7), Z(7)^4 ], [ Z(7)^5, Z(7)^2 ] ]^G,
      [ [ 0*Z(7), Z(7)^3 ], [ Z(7)^0, 0*Z(7) ] ]^G,
      [ [ 0*Z(7), Z(7)^3 ], [ Z(7)^0, Z(7)^4 ] ]^G,
      [ [ 0*Z(7), Z(7)^3 ], [ Z(7)^0, Z(7) ] ]^G,
      [ [ Z(7)^4, 0*Z(7) ], [ 0*Z(7), Z(7)^2 ] ]^G,
      [ [ Z(7)^5, 0*Z(7) ], [ 0*Z(7), Z(7) ] ]^G ]
    gap> g:=Representative(CG[3]); Order(g);
    [ [ 0*Z(7), Z(7)^4 ], [ Z(7)^5, Z(7)^5 ] ]
    14
    gap> g:=Representative(CG[4]); Order(g);
    [ [ Z(7)^3, 0*Z(7) ], [ 0*Z(7), Z(7)^3 ] ]
    2
    gap> g:=Representative(CG[5]); Order(g);
    [ [ 0*Z(7), Z(7)^3 ], [ Z(7)^0, Z(7)^2 ] ]
    7
    gap> g:=Representative(CG[6]); Order(g);
    [ [ 0*Z(7), Z(7)^4 ], [ Z(7)^5, Z(7)^2 ] ]
    7
    gap>                            
    


  • presented
    To construct a finitely presented group in GAP, use the
    “FreeGroup” and “” commands. Here is one example.

    gap> M12 := MathieuGroup( 12 );
    Group([ (1,2,3,4,5,6,7,8,9,10,11), (3,7,11,8)(4,10,5,6), (1,12)(2,11)(3,6)(4,8)(5,9)(7,10) ])
    gap> F := FreeGroup( "a", "b", "c" );
    free group on the generators [ a, b, c ]
    gap> words := [ F.1, F.2 ];
    [ a, b ]
    gap> P := PresentationViaCosetTable( M12, F, words );
    presentation with 3 gens and 10 rels of total length 97
    gap> TzPrintRelators( P );
    #I  1. c^2
    #I  2. b^4
    #I  3. a*c*a*c*a*c
    #I  4. a*b^2*a*b^-2*a*b^-2
    #I  5. a^11
    #I  6. a^2*b*a^-2*b^2*a*b^-1*a^2*b^-1
    #I  7. a*b*a^-1*b*a^-1*b^-1*a*b*a^-1*b*a^-1*b^-1
    #I  8. a^2*b*a^2*b^2*a^-1*b*a^-1*b^-1*a^-1*b^-1
    #I  9. a*b*a*b*a^2*b^-1*a^-1*b^-1*a*c*b*c
    #I  10. a^4*b*a^2*b*a^-2*c*a*b*a^-1*c
    gap> G := FpGroupPresentation( P );
    fp group on the generators [ a, b, c ]
    gap> RelatorsOfFpGroup( G );  
    [ c^2, b^4, a*c*a*c*a*c, a*b^-2*a*b^-2*a*b^-2, a^11, a^2*b*a^-2*b^-2*a*b^-1*a^2*b^-1, a*b*a^-1*b*a^-1*b^-1*a*b*a^-1*b*a^-1*b^-1,
      a^2*b*a^2*b^-2*a^-1*b*a^-1*b^-1*a^-1*b^-1, a*b*a*b*a^2*b^-1*a^-1*b^-1*a*c*b*c, a^4*b*a^2*b*a^-2*c*a*b*a^-1*c ]
    gap> Size(M12);
    95040
    gap> Size(G);
    95040
    gap> IsomorphismGroups(G,M12); 
    ????????
    

    The last command is computationally intensive and requires more
    than the default memory allocation of 256M of RAM.

    Here is another example.

    gap> F := FreeGroup( "a", "b");
    free group on the generators [ a, b ]
    gap> G:=F/[F.1^2,F.2^3,F.1*F.2*F.1^(-1)*F.2^(-1)];
    fp group on the generators [ a, b ]
    gap> Size(G);
    6
    
    


  • rref
    The key command for row reduction is “TriangulizeMat”.
    The following example illustrates the syntax.

    gap> M:=[[1,2,3,4,5],[1,2,1,2,1],[1,1,0,0,0]];
    [ [ 1, 2, 3, 4, 5 ], [ 1, 2, 1, 2, 1 ], [ 1, 1, 0, 0, 0 ] ]
    gap> TriangulizeMat(M);
    gap> M;
    [ [ 1, 0, 0, -1, 1 ], [ 0, 1, 0, 1, -1 ], [ 0, 0, 1, 1, 2 ] ]
    gap> Display(M);
    [ [   1,   0,   0,  -1,   1 ],
      [   0,   1,   0,   1,  -1 ],
      [   0,   0,   1,   1,   2 ] ]
    gap> M:=Z(3)^0*[[1,2,3,4,5],[1,2,1,2,1],[1,1,0,0,0]];
    [ [ Z(3)^0, Z(3), 0*Z(3), Z(3)^0, Z(3) ],
      [ Z(3)^0, Z(3), Z(3)^0, Z(3), Z(3)^0 ],
      [ Z(3)^0, Z(3)^0, 0*Z(3), 0*Z(3), 0*Z(3) ] ]
    gap> TriangulizeMat(M);
    gap> Display(M);
     1 . . 2 1
     . 1 . 1 2
     . . 1 1 2
    gap>
    


  • kernel:
    There are different methods for matrices over the integers and
    matrices over a field.For integer entries, related commands include
    “NullspaceIntMat” and “SolutionNullspaceIntMat”
    in section

    25.1 “Linear equations over the integers and Integral Matrices”

    of the reference manual.

    gap> M:=[[1,2,3],[4,5,6],[7,8,9]];
    [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ]
    gap> NullspaceIntMat(M);
    [ [ 1, -2, 1 ] ]
    gap> SolutionNullspaceIntMat(M,[0,0,1]);
    [ fail, [ [ 1, -2, 1 ] ] ]
    gap> SolutionNullspaceIntMat(M,[0,0,0]);
    [ [ 0, 0, 0 ], [ [ 1, -2, 1 ] ] ]
    gap> SolutionNullspaceIntMat(M,[1,2,3]);
    [ [ 1, 0, 0 ], [ [ 1, -2, 1 ] ] ]
    
    

    Here (0,0,1) is not in the image of M
    (under v-> v*M) but (0,0,0) and (1,2,3) are.

    For field entries, related commands include
    “NullspaceMat” and “TriangulizedNullspaceMat”
    in section

    24.6 “Matrices Representing Linear Equations and the Gaussian Algorithm”

    of the reference manual.

    gap> M:=[[1,2,3],[4,5,6],[7,8,9]];
    [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ]
    gap> NullspaceMat(M);
    [ [ 1, -2, 1 ] ]
    gap> TriangulizedNullspaceMat(M);
    [ [ 1, -2, 1 ] ]
    gap> M:=[[1,2,3,1,1],[4,5,6,1,1],[7,8,9,1,1],[1,2,3,1,1]];
    [ [ 1, 2, 3, 1, 1 ], [ 4, 5, 6, 1, 1 ], [ 7, 8, 9, 1, 1 ], 
      [ 1, 2, 3, 1, 1 ] ]
    gap> NullspaceMat(M);
    [ [ 1, -2, 1, 0 ], [ -1, 0, 0, 1 ] ]
    gap> TriangulizedNullspaceMat(M);
    [ [ 1, 0, 0, -1 ], [ 0, 1, -1/2, -1/2 ] ]
    
    
    


  • characteristic polynomial:
    Please see section
    24.12.1 of the GAP reference manual
    for examples of characteristic polynomial of a
    square matrix (“CharacteristicPolynomial”) and
    section

    56.3
    for examples of the “characteristic polynomial”
    (called a “TracePolynomial”) of an
    element of a field extension.


  • character:
    GAP contains very extensive character theoretic functions
    and data libraries (including an interface the character table in the
    Atlas).
    Here is just one simple example.

    gap> G:=Group((1,2)(3,4),(1,2,3));
    Group([ (1,2)(3,4), (1,2,3) ])
    gap> T:=CharacterTable(G);
    CharacterTable( Alt( [ 1 .. 4 ] ) )
    gap> Display(T);
    CT1
    
         2  2  2  .  .
         3  1  .  1  1
    
           1a 2a 3a 3b
        2P 1a 1a 3b 3a
        3P 1a 2a 1a 1a
    
    X.1     1  1  1  1
    X.2     1  1  A /A
    X.3     1  1 /A  A
    X.4     3 -1  .  .
    
    A = E(3)^2
      = (-1-ER(-3))/2 = -1-b3
    gap> irr:=Irr(G);
    [ Character( CharacterTable( Alt( [ 1 .. 4 ] ) ), [ 1, 1, 1, 1 ] ),
      Character( CharacterTable( Alt( [ 1 .. 4 ] ) ), [ 1, 1, E(3)^2, E(3) ] ),
      Character( CharacterTable( Alt( [ 1 .. 4 ] ) ), [ 1, 1, E(3), E(3)^2 ] ),
      Character( CharacterTable( Alt( [ 1 .. 4 ] ) ), [ 3, -1, 0, 0 ] ) ]
    gap> Display(irr);
    [ [       1,       1,       1,       1 ],
      [       1,       1,  E(3)^2,    E(3) ],
      [       1,       1,    E(3),  E(3)^2 ],
      [       3,      -1,       0,       0 ] ]
    gap> chi:=irr[2]; gamma:=CG[3]; g:=Representative(gamma); g^chi;
    Character( CharacterTable( Alt( [ 1 .. 4 ] ) ), [ 1, 1, E(3)^2, E(3) ] )
    (1,2,3)^G
    (1,2,3)
    E(3)^2
    
    

    For further details and examples, see chapters
    69
    72 of the
    GAP reference manual.

  • brauer:
    Just a simple example of what GAP can do here.
    To construct a Brauer character table:

    gap> G:=Group((1,2)(3,4),(1,2,3));
    Group([ (1,2)(3,4), (1,2,3) ])
    gap> irr:=IrreducibleRepresentations(G,GF(7));
    [ [ (1,2)(3,4), (1,2,3) ] -> [ [ [ Z(7)^0 ] ], [ [ Z(7)^0 ] ] ],
      
    [ (1,2)(3,4), (1,2,3) ] -> [ [ [ Z(7)^0 ] ], [ [ Z(7)^4 ] ] ],
      
    [ (1,2)(3,4), (1,2,3) ] -> [ [ [ Z(7)^0 ] ], [ [ Z(7)^2 ] ] ],
      
    [ (1,2)(3,4), (1,2,3) ] -> [
          
    [ [ 0*Z(7), Z(7)^3, Z(7)^0 ], [ 0*Z(7), Z(7)^3, 0*Z(7) ], 
    [ Z(7)^0, Z(7)^3, 0*Z(7) ] ],
          [ [ 0*Z(7), Z(7)^0, 0*Z(7) ], 
    [ 0*Z(7), 0*Z(7), Z(7)^0 ], [ Z(7)^0, 0*Z(7), 0*Z(7) ] ]
         
    ] ]
    gap> brvals := List(irr,chi-> List(ConjugacyClasses(G),c->
    BrauerCharacterValue(Image(chi, Representative(c)))));
    [ [ 1, 1, 1, 1 ], [ 1, 1, E(3)^2, E(3) ], [ 1, 1, E(3), E(3)^2 ], 
    [ 3, -1, 0, 0 ] ]
    gap> Display(brvals);
    [ [       1,       1,       1,       1 ],
      
    [       1,       1,  E(3)^2,    E(3) ],
      
    [       1,       1,    E(3),  E(3)^2 ],
      
    [       3,      -1,       0,       0 ] ]
    gap>                                               
    

    List(ConjugacyClasses(G),c->BrauerCharacterValue(Image(chi, Representative(c)))));
    #Display(brvals);
    T:=CharacterTable(G);
    Display(T);
    –>


  • polynomial
    There are various ways to construct a polynomial in GAP.

    gap> Pts:=Z(7)^0*[1,2,3];
    [ Z(7)^0, Z(7)^2, Z(7) ]
    gap> Vals:=Z(7)^0*[1,2,6];
    [ Z(7)^0, Z(7)^2, Z(7)^3 ]
    gap> g:=InterpolatedPolynomial(GF(7),Pts,Vals);
    Z(7)^5*x_1^2+Z(7)
    

    Or:

    gap> p:=3;; F:=GF(p);;
    gap> R:=PolynomialRing(F,["x1","x2"]);
    PolynomialRing(..., [ x1, x2 ])
    gap> vars:=IndeterminatesOfPolynomialRing(R);;
    gap> x1:=vars[1]; x2:=vars[2];
    x1
    x2
    gap> p:=x1^5-x2^5;
    x1^5-x2^5
    gap> DivisorsMultivariatePolynomial(p,R);
    [ x1^4+x1^3*x2+x1^2*x2^2+x1*x2^3+x2^4, x1-x2 ]
    

    Or:

    gap> x:=X(Rationals);
    x_1
    gap> f:=x+x^2+1;
    x_1^2+x_1+1
    gap> Value(f,[x],[1]);
    3
    


  • factor
    To factor a polynomial in GAP, there is one command for
    univariate polynomials (“Factors”) and another command for
    multivariate polynomials (“DivisorsMultivariatePolynomial”).For a factoring a univariate polynomial,
    GAP provides only methods over finite fields
    and over subfields of cyclotomic fields.
    Please see the
    examples given in section

    64.10 “Polynomial Factorization”
    for more details.For multivariate polynomials,
    a very slow algorithm has been implemented in GAP
    and an interface to a very fast algorithm in
    Singular
    has been implemented for those who have both Singular and
    the GAP Singular package
    installed. The former of these was
    illustrated above in
    “polynomial” above.
    (Again, the ground field must be a finite field
    or a subfields of cyclotomic fields.)
    For the latter, please see the example
    in the (GAP-)Singular manual
    FactorsUsingSingularNC.


  • roots
    There are some situtations where GAP does find the roots
    of a polynomial but GAP does not do this generally.
    (The roots must generate either a finite field
    or a subfield of a cyclotomic field.) However, there is a package called

    RadiRoot
    which must be installed which does help to do this
    for polynomials with rational coefficients
    (radiroot itself requires other packages to be installed;
    please see the webpage for more details).The “Factors” command actually has an option which allows you to
    increase the groundfield so that a factorization actually
    returns the roots. Please see the
    examples given in section

    64.10 “Polynomial Factorization”
    for more details.Here is a second appoach.

    gap> p:=3; n:=4; F:=GF(p^n); c:=Random(F); r:=2;
    3
    4
    GF(3^4)
    Z(3^4)^79
    2
    gap>  x:=X(F,1); f:=x^r-c*x+c-1;
    x_1
    x_1^2+Z(3^4)^39*x_1+Z(3^4)^36
    gap>  F_f:=FieldExtension( F, f );
    AsField( GF(3^4), GF(3^8) )
    gap>  alpha:=RootOfDefiningPolynomial(F_f);
    Z(3^4)^36
    gap> Value(f,[x],[alpha]);
    0*Z(3)
    
    

    Here is a third. First, enter the following program:

    RootOfPolynomial:=function(f,R)
     local F0,Ff,a;
     F0:=CoefficientsRing(R);
     Ff:=FieldExtension(F0,f);
     a:=RootOfDefiningPolynomial(Ff);
     return a;
    end;
    

    Here’s how this can be used to find a root:

    gap> F:=Rationals;
    Rationals
    gap> x:=X(F,1); f:=x^2+x+1;
    x_1
    x_1^2+x_1+1
    gap> R:=PolynomialRing( F, [ x ]);
    PolynomialRing(..., [ x_1 ])
    gap> a:=RootOfPolynomial(f,R);
    E(3)
    gap> # check:
    gap> Value(f,[x],[a]);
    0
    

    Related links:

    1. In the GAP Forum:

      Hensel lifting discussion
      .
    2. In the manual,

      Galois groups
      .

  • evaluate:
    The relevant command is “Value”. There are several examples already on
    this page. For others, please see the examples given in section
    64.7 Multivariate polynomials of the manual.
    For sparse uivariate polynomials, there is also the command
    “ValuePol” in section
    23.6 of the manual.


  • integer power
    This is easy and intuitive:

    gap> a:=1000; n:=100000; m:=123;
    1000
    100000
    123
    gap> a^n mod m;
    1
    
    


  • matrix power:
    This too is easy and intuitive:

    gap> A:=[[1,2],[3,4]]; n:=100000; m:=123;
    [ [ 1, 2 ], [ 3, 4 ] ]
    100000
    123
    gap> A^n mod m;
    [ [ 1, 41 ], [ 0, 1 ] ]
    

  • polynomial power
    GAP allows you to do arithmetic over the polynomial
    ring R[x], where R = Z/nZ (where n is a positive integer).
    Here’s an example.

    gap> Z4:=ZmodnZ(4);
    (Integers mod 4)
    gap> R:=UnivariatePolynomialRing(Z4,1);
    PolynomialRing(..., [ x ])
    gap> x:=IndeterminatesOfPolynomialRing(R)[1];
    x
    gap> I:=TwoSidedIdealByGenerators( R,[x^8-x^0]);
    two-sided ideal in PolynomialRing(..., [ x ]), (1 generators)
    gap> gen:=x^8-x^0;
    x8-ZmodnZObj(1,4)
    gap> QuotientRemainder(R,x^8,gen);
    [ ZmodnZObj(1,4), ZmodnZObj(1,4) ]
    gap> QuotientRemainder(R,x^15,gen);
    [ x^7, x^7 ]
    gap> QuotientRemainder(R,x^15+x^8,gen);
    [ x^7+ZmodnZObj(1,4), x^7+ZmodnZObj(1,4) ]
    gap> PowerMod( R, x+x^0, 15, gen );
    ZmodnZObj(0,4)
    gap> PowerMod( R, x, 15, gen );
    x^7
    
    


  • Groebner basis
    GAP’s Groebner bases algorithms are relatively slow
    and are included mostly for simple examples and for
    teaching purposes. However, a GAP interface to a very
    fast algorithm in Singular
    has been implemented for those who have both Singular and
    the
    GAP Singular package
    installed. The former of these is
    illustrated in section
    64.17 Groebner bases of the GAP manual.
    For the latter, please see the example
    in the (GAP-)Singular manual
    GroebnerBasis.


  • normal subgroup:
    Here is an example:

    gap> G := AlternatingGroup( 5 );
    Group( (1,2,5), (2,3,5), (3,4,5) )
    gap> normal := NormalSubgroups( G );
    [ Subgroup( Group( (1,2,5), (2,3,5), (3,4,5) ), [  ] ), 
      Subgroup( Group( (1,2,5), (2,3,5), (3,4,5) ), 
        [ (1,2)(3,4), (1,3)(4,5), (1,4)(2,3) ] ) ]
    

    Related links:

    1. Please see Volkmar Felsch’s
      GAP Forum response to a related question.
    2. The

      xgap
      package displays subgroup lattices graphically.

  • abelian subgroup
    One idea to compute all the abelian subgroups is to compute all the
    subgroups then “filter” out the abelian ones.
    Here is an illustration, taked from a
    GAP Forum response Volkmar Felsch.

    gap> G := AlternatingGroup( 5 );
    Group( (1,2,5), (2,3,5), (3,4,5) )
    gap> classes := ConjugacyClassesSubgroups( G );
    [ ConjugacyClassSubgroups( Group( (1,2,5), (2,3,5), 
        (3,4,5) ), Subgroup( Group( (1,2,5), (2,3,5), (3,4,5) ), [  ] ) ),
      ConjugacyClassSubgroups( Group( (1,2,5), (2,3,5), 
        (3,4,5) ), Subgroup( Group( (1,2,5), (2,3,5), (3,4,5) ), 
        [ (2,3)(4,5) ] ) ), ConjugacyClassSubgroups( Group( (1,2,5), 
        (2,3,5), (3,4,5) ), Subgroup( Group( (1,2,5), (2,3,5), (3,4,5) ), 
        [ (3,4,5) ] ) ), ConjugacyClassSubgroups( Group( (1,2,5), 
        (2,3,5), (3,4,5) ), Subgroup( Group( (1,2,5), (2,3,5), (3,4,5) ), 
        [ (2,3)(4,5), (2,4)(3,5) ] ) ), ConjugacyClassSubgroups( Group( 
        (1,2,5), (2,3,5), (3,4,5) ), Subgroup( Group( (1,2,5), (2,3,5), 
        (3,4,5) ), [ (1,2,3,4,5) ] ) ), ConjugacyClassSubgroups( Group( 
        (1,2,5), (2,3,5), (3,4,5) ), Subgroup( Group( (1,2,5), (2,3,5), 
        (3,4,5) ), [ (3,4,5), (1,2)(4,5) ] ) ), 
      ConjugacyClassSubgroups( Group( (1,2,5), (2,3,5), 
        (3,4,5) ), Subgroup( Group( (1,2,5), (2,3,5), (3,4,5) ), 
        [ (1,2,3,4,5), (2,5)(3,4) ] ) ), ConjugacyClassSubgroups( Group( 
        (1,2,5), (2,3,5), (3,4,5) ), Subgroup( Group( (1,2,5), (2,3,5), 
        (3,4,5) ), [ (2,3)(4,5), (2,4)(3,5), (3,4,5) ] ) ), 
      ConjugacyClassSubgroups( Group( (1,2,5), (2,3,5), (3,4,5) ), Group( 
        (1,2,5), (2,3,5), (3,4,5) ) ) ]
    gap> cl := classes[4];
    ConjugacyClassSubgroups( Group( (1,2,5), (2,3,5), 
    (3,4,5) ), Subgroup( Group( (1,2,5), (2,3,5), (3,4,5) ), 
    [ (2,3)(4,5), (2,4)(3,5) ] ) )
    gap> length := Size( cl );
    5
    gap> rep := Representative( cl );
    Subgroup( Group( (1,2,5), (2,3,5), (3,4,5) ), 
    [ (2,3)(4,5), (2,4)(3,5) ] )
    gap> order := Size( rep );
    4
    gap> IsAbelian( rep );
    true
    gap> abel := Filtered( classes, cl -> IsAbelian( Representative( cl ) ) );
    [ ConjugacyClassSubgroups( Group( (1,2,5), (2,3,5), 
        (3,4,5) ), Subgroup( Group( (1,2,5), (2,3,5), (3,4,5) ), [  ] ) ),
      ConjugacyClassSubgroups( Group( (1,2,5), (2,3,5), 
        (3,4,5) ), Subgroup( Group( (1,2,5), (2,3,5), (3,4,5) ), 
        [ (2,3)(4,5) ] ) ), ConjugacyClassSubgroups( Group( (1,2,5), 
        (2,3,5), (3,4,5) ), Subgroup( Group( (1,2,5), (2,3,5), (3,4,5) ), 
        [ (3,4,5) ] ) ), ConjugacyClassSubgroups( Group( (1,2,5), 
        (2,3,5), (3,4,5) ), Subgroup( Group( (1,2,5), (2,3,5), (3,4,5) ), 
        [ (2,3)(4,5), (2,4)(3,5) ] ) ), ConjugacyClassSubgroups( Group( 
        (1,2,5), (2,3,5), (3,4,5) ), Subgroup( Group( (1,2,5), (2,3,5), 
        (3,4,5) ), [ (1,2,3,4,5) ] ) ) ]
    

  • homology
    This depends on how the group is given. For example, suppose that
    G is a permutation group with generators genG and
    H is a permutation group with generators genH. To find a
    homomorphism from G to H, one may use the
    “GroupHomomorphismByImages” or “GroupHomomorphismByImagesNC”
    commands. For examples of the syntax, please see
    section
    38.1 Creating Group Homomorphisms.Here’s an illustration of how to convert a finitely presented
    group into a permutation group.

    gap> p:=7;
    7
    gap> G:=PSL(2,p);
    Group([ (3,7,5)(4,8,6), (1,2,6)(3,4,8) ])
    gap> H:=SchurCover(G);
    fp group of size 336 on the generators [ f1, f2, f3 ]
    gap> iso:=IsomorphismPermGroup(H);
    [ f1, f2, f3 ] -> [ (1,2,4,3)(5,9,7,10)(6,11,8,12)(13,14,15,16),
      (2,5,6)(3,7,8)(11,13,14)(12,15,16), (1,4)(2,3)(5,7)(6,8)(9,10)(11,12)(13,
        15)(14,16) ]
    gap> H0:=Image(iso);                       # 2-cover of PSL2
    Group([ (1,2,4,3)(5,9,7,10)(6,11,8,12)(13,14,15,16),
      (2,5,6)(3,7,8)(11,13,14)(12,15,16), (1,4)(2,3)(5,7)(6,8)(9,10)(11,12)(13,
        15)(14,16) ])
    gap> IdGroup(H0);
    [ 336, 114 ]
    gap> IdGroup(SL(2,7));
    [ 336, 114 ]
    gap>                
    

  • semi-direct product(Contributed by Nilo de Roock):
    As you can easily verify, D8 is isomorphic to C2:C4. Or in GAP…

    N:=CyclicGroup(IsPermGroup,4);
    G:=CyclicGroup(IsPermGroup,2);
    AutN:=AutomorphismGroup(N);
    f:=GroupHomomorphismByImages(G,AutN,GeneratorsOfGroup(G),[Elements(AutN)[2]]);
    NG:=SemidirectProduct(G,f,N);
    

    Verify with

    StructureDescription(NG);
    

  • semi-direct products(Contributed by Nilo de Roock):
    The following shows how to construct all non-abelian groups
    of order 12 as semi-direct products. These products are not
    trivial yet small enough to verify by hand.

    #D12 = (C2 x C2) : C3
    G1:=CyclicGroup(IsPermGroup,2);
    G2:=CyclicGroup(IsPermGroup,2);
    G:=DirectProduct(G1,G2);
    N:=CyclicGroup(IsPermGroup,3);
    AutN:=AutomorphismGroup(N);
    f:=GroupHomomorphismByImages(G,AutN,[Elements(G)[1],Elements(G)[2],Elements(G)[3],Elements(G)[4]],[Elements(AutN)[1],Elements(AutN)[2],Elements(AutN)[1],Elements(AutN)[2]]);
    NG:=SemidirectProduct(G,f,N);
    Print(str(NG));
    Print("\n");
    
    #T = C4 : C3
    G:=CyclicGroup(IsPermGroup,4);
    N:=CyclicGroup(IsPermGroup,3);
    AutN:=AutomorphismGroup(N);
    f:=GroupHomomorphismByImages(G,AutN,[Elements(G)[1],Elements(G)[2],Elements(G)[3],Elements(G)[4]],[Elements(AutN)[1],Elements(AutN)[2],Elements(AutN)[1],Elements(AutN)[2]]);
    NG:=SemidirectProduct(G,f,N);
    Print(str(NG));
    Print("\n");
    
    #A4 = C3 : (C2 x C2)
    G:=CyclicGroup(IsPermGroup,3);
    N1:=CyclicGroup(IsPermGroup,2);
    N2:=CyclicGroup(IsPermGroup,2);
    N:=DirectProduct(G1,G2);
    AutN:=AutomorphismGroup(N);
    f:=GroupHomomorphismByImages(G,AutN,[Elements(G)[1],Elements(G)[2],Elements(G)[3]],[Elements(AutN)[1],Elements(AutN)[4],Elements(AutN)[5]]);
    NG:=SemidirectProduct(G,f,N);
    Print(str(NG));
    Print("\n");
    

  • cohomology
    GAP will compute the Schur multiplier
    H2(G,C) using the
    “AbelianInvariantsMultiplier” command.
    Here is an example showing how to find H2(A5,C),
    where A5 is the alternating group on 5 letters.

    gap> A5:=AlternatingGroup(5);
    Alt( [ 1 .. 5 ] )
    gap> AbelianInvariantsMultiplier(A5);
    [ 2 ]
    

    So, H2(A5,C) is Z/2Z.

    Related links:

    1. See section

      37.23
      and
      section

      37.24
      of the GAP manual.
    2. See D. Holt’s GAP package
      cohomolo.

Sports ranking methods, 3

This is the third of a series of expository posts on matrix-theoretic sports ranking methods. This post discusses the random walker ranking.

We follow the presentation in the paper by Govan and Meyer (Ranking National Football League teams using Google’s PageRank). The table of “score differentials” based on the table in a previous post is:

\begin{tabular}{c|cccccc} \verb+x\y+ & Army & Bucknell & Holy Cross & Lafayette & Lehigh & Navy \\ \hline Army & 0 & 0 & 1 & 0 & 0 & 0 \\ Bucknell & 2 & 0 & 0 & 2 & 3 & 0 \\ Holy Cross & 0 & 3 & 0 & 4 & 14 & 0 \\ Lafayette & 10 & 0 & 0 & 0 & 0 & 0 \\ Lehigh & 2 & 0 & 0 & 11 & 0 & 0 \\ Navy & 11 & 14 & 8 & 22 & 6 & 0 \\ \end{tabular}
This leads to the following matrix:

M_0=\left(\begin{array}{cccccc} 0 & 0 & 1 & 0 & 0 & 0 \\ 2 & 0 & 0 & 2 & 3 & 0 \\ 0 & 3 & 0 & 4 & 14 & 0 \\ 10 & 0 & 0 & 0 & 0 & 0 \\ 2 & 0 & 0 & 11 & 0 & 0 \\ 11 & 14 & 8 & 22 & 6 & 0 \\ \end{array}\right) .

The edge-weighted score-differential graph associated to M_0 (regarded as a weighted adjacency matrix) is in the figure below.

sm261_baseball-ranking-application_teams-digraph2

This matrix M_0 must be normalized to create a (row) stochastic matrix:

M = \left(\begin{array}{cccccc} 0 & 0 & 1 & 0 & 0 & 0 \\ {2}/{7} & 0 & 0 /{7} /{7} & 0 \\ 0 /{7} & 0 /{21} /{3} & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 \\ {2}/{13} & 0 & 0 /{13} & 0 & 0 \\ {11}/{61} /{61} /{61} /{61} /{61} & 0 \\ \end{array}\right) .

Next, to insure it is irreducible, we replace M by A=(M+J)/2, where J is the 6\times 6 doubly stochastic matrix with every entry equal to 1/6:

A=\left(\begin{array}{cccccc} {1}/{12} & 1/{12} & 7/{12} & 1/{12} & 1/{12} & 1/{12} \\ {19}/{84} & 1/{12} & 1/{12} & 19/{84} & 25/{84} & 1/{12} \\ {1}/{12} & 13/{84} & 1/{12} & 5/{28} & 5/{12} & 1/{12} \\ {7}/{12} & 1/{12} & 1/{12} & 1/{12} & 1/{12} & 1/{12} \\ {25}/{156} & 1/{12} & 1/{12} & 79/{156} & 1/{12} & 1/{12} \\ {127}/{732} & 145/{732} & 109/{732} & 193/{732} & 97/{732} & 1/{12} \end{array}\right).

Let

{\bf v}_0 = \left( \frac{1}{6} , \frac{1}{6} , \frac{1}{6} , \frac{1}{6} , \frac{1}{6} , \frac{1}{6}\right).

The ranking determined by the random walker method is the reverse of the left eigenvector of A associated to the largest eigenvalue \lambda_{max}=1 (by reverse, I mean that the vector ranks the teams from worst-to-best, not from best-to-worst, as we have seen in previous ranking methods).
In other words, the vector

{\bf r}^*=\lim_{n\to \infty}{\bf v}_0A^n.

This is approximately

{\bf r}^* \cong \left(0.2237\dots ,\,0.1072\dots ,\,0.2006\dots ,\,0.2077\dots ,\,0.1772\dots ,\,0.0833\dots \right).

Its reverse gives the ranking:

Army < Lafayette < Bucknell < Lehigh < Holy Cross < Navy.

This gives a prediction failure rate of 13.3\%.

Sports ranking methods, 2

This is the second of a series of expository posts on matrix-theoretic sports ranking methods. This post discusses Keener’s method (see J.P. Keener, The Perron-Frobenius theorem and the ranking of football, SIAM Review 35 (1993)80-93 for details).

See the first post in the series for a discussion of the data we’re using to explain this method. We recall the table of results:

X\Y Army Bucknell Holy Cross Lafayette Lehigh Navy
Army x 14-16 14-13 14-24 10-12 8-19
Bucknell 16-14 x 27-30 18-16 23-20 10-22
Holy Cross 13-14 30-27 x 19-15 17-13 9-16
Lafayette 24-14 16-18 15-19 x 12-23 17-39
Lehigh 12-10 20-23 13-17 23-12 x 12-18
Navy 19-8 22-10 16-9 39-17 18-12 x
sm261_baseball-ranking-application_teams-digraph

Win-loss digraph of the Patriot league mens baseball from 2015

Suppose T teams play each other. Let A=(a_{ij})_{1\leq i,j\leq T} be a non-negative square matrix determined by the results of their games, called the preference matrix. In his 1993 paper, Keener defined the score of the ith team to be given by

s_i = \frac{1}{n_i}\sum_{j=1}^T a_{ij}r_j,

where n_i denotes the total number of games played by team i and {\bf r}=(r_1,r_2,\dots ,r_T) is the rating vector (where r_i\geq 0 denotes the rating of team i).

One possible preference matrix the matrix A of total scores obtained from the pre-tournament table below:

A = \left(\begin{array}{rrrrrr} 0 & 14 & 14 & 14 & 10 & 8 \\ 16 & 0 & 27 & 18 & 23 & 28 \\ 13 & 30 & 0 & 19 & 27 & 43 \\ 24 & 16 & 15 & 0 & 12 & 17 \\ 12 & 20 & 43 & 23 & 0 & 12 \\ 19 & 42 & 30 & 39 & 18 & 0 \end{array}\right),

(In this case, n_i=4 so we ignore the 1/n_i factor.)

In his paper, Keener proposed a ranking method where the ranking vector {\bf r} is proportional to its score. The score is expressed as a matrix product A{\bf r}, where A is a square preference matrix. In other words, there is a constant \rho>0 such that s_i=\rho r_i, for each i. This is the same as saying A {\bf r} = \rho {\bf r}.

The Frobenius-Perron theorem implies that S has an eigenvector {\bf r}=(r_1,r_2,r_3,r_4,r_5,r_6) having positive entries associated to the largest eigenvalue $\lambda_{max}$ of A, which has (geometric) multiplicity 1. Indeed, A has maximum eigenvalue \lambda_{max}= 110.0385..., of multiplicity 1, with eigenvector

{\bf r}=(1, 1.8313\dots , 2.1548\dots , 1.3177\dots , 1.8015\dots , 2.2208\dots ).

Therefore the teams, according to Kenner’s method, are ranked,

Army < Lafayette < Lehigh < Bucknell < Holy Cross < Navy.

This gives a prediction failure rate of just 6.7\%.

Memories of TS Michael, by Thomas Quint

TS Michael passed away on November 22, 2016, from cancer. I will miss him as a colleague and a kind, wise soul. Tom Quint has kindly allowed me to post these reminiscences that he wrote up.


Well, I guess I could start with the reason TS and I met in the first place. I was a postdoc at USNA in about 1991 and pretty impressed with myself. So when USNA offered to continue my postdoc for two more years (rather than give me a tenure track position), I turned it down. Smartest move I ever made, because TS got the position and so we got to know each other.

We started working w each other one day when we both attended a talk on “sphere of influence graphs”. I found the subject moderately interesting, but he came into my office all excited, and I couldn’t get rid of him — wouldn’t leave until we had developed a few research ideas.

Interestingly, his position at USNA turned into a tenure track, while mine didn’t. It wasn’t until 1996 that I got my position at U of Nevada.

Work sessions with him always followed the same pattern. As you may or may not know, T.S. a) refused to fly in airplanes, and b) didn’t drive. Living across the country from each other, the only way we could work together face-to-face was: once each summer I would fly out to the east coast to visit my parents, borrow one of their cars for a week, and drive down to Annapolis. First thing we’d do is go to Whole Foods, where he would load up my car with food and other supplies, enough to last at least a few months. My reward was that he always bought me the biggest package of nigiri sushi we could find — not cheap at Whole Foods!

It was fun, even though I had to suffer through eight million stories about the USNA Water Polo Team.

Oh yes, and he used to encourage me to sneak into one of the USNA gyms to work out. We figured that no one would notice if I wore my Nevada sweats (our color is also dark blue, and the pants also had a big “N” on them). It worked.

Truth be told, TS didn’t really have a family of his own, so I think he considered the mids as his family. He cared deeply about them (with bonus points if you were a math major or a water polo player :-).

One more TS anecdote, complete with photo.  Specifically, TS was especially thrilled to find out that we had named our firstborn son Theodore Saul Quint.  Naturally, TS took to calling him “Little TS”.  At any rate, the photo below is of “Big TS” holding “Little TS”, some time in the Fall of 2000.

tslittlets_photo2000

TS Michael in 2000.

Simple unsolved math problem, 7

Everyone’s heard of the number \pi = 3.141592…, right?

pi-pie

Robert Couse-Baker / CC BY http://2.0 / Flickr: 29233640@N07

And you probably know that \pi is not a rational number (i.e., a quotient of two integers, like 7/3). Unlike a rational number, whose decimal expansion is eventually periodic, if you look at the digits of \pi they seem random,

3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823066470938446095505822317253594081284811174502841027019385211055596446229489549303819644288109756659334461284756482…

But are they really? No one really knows. There’s a paper that explores the statistics of these digits using the first 22.4 trillion digits of \pi. Does any finite sequence of k digits (say, for example, the 4-digit sequence 2016) occur just as often as any other sequence of the same length (say, 1492), for each k? When the answer is yes, the number is called ‘normal.’ That is, a normal number is a real number whose infinite sequence of digits is distributed uniformly in the sense that each digit has the same natural density 1/10, also all possible k-tuples of digits are equally likely with density 1/k, for any integer k>1.

The following simple problem is unsolved:

Conjecture: \pi is normal.