Math.Algebra.Group.RandomSchreierSims
In our investigation of graph automorphisms, we've come across the concept of a strong generating set (SGS) for a permutation group. This is a generating set of a special form, which makes certain calculations particularly easy - for example, calculating the order of the group (the number of elements it contains). Our graphAuts algorithm naturally produced a strong generating set for the group. But what if we are just given any old set of generators for a permutation group.
The random Schreier-Sims algorithm is a fast Monte-Carlo algorithm for finding a strong generating set, given a set of generators. Monte-Carlo means that there is a small probability that it will return the wrong answer - in this case, it might return an SGS for a subgroup of the group we are interested in, instead of the whole group. In practice, this isn't an issue. First, we can make the probability of error as small as we like. Second, we usually know the order of the group, so can check whether the SGS is right.
The main function provided in Math.Algebra.Group.RandomSchreierSims is sgs, which takes a set of generators and returns a strong generating set.
(We already have an sgs function in Math.Algebra.Group.SchreierSims. This is guaranteed to give the right answer - but can be significantly slower. So, you have a choice which one to use.)
Math.Projects.MiniquaternionGeometry
A projective plane is an incidence structure of points and lines satisfying the following rules:
- Given any two distinct points, there is exactly one line which passes through both
- Given any two distinct lines, there is exactly one point which lies on both
- There exists a quadrangle: a set of four points, no three of which are collinear
(There is another definition of projective plane, in terms of designs, but we haven't covered those yet.)
For any prime power q = p^n, the projective geometry PG(2,Fq) over the finite field Fq is a projective plane. However, it turns out that there are projective planes which are not of this form, associated with algebraic systems called near-fields, which are nearly fields but not quite.
In Math.Projects.MiniquaternionGeometry I construct PG(2,F9), together with three "non-Desarguesian" planes of order 9, based on the near-field J9 of order 9. The name Miniquaternion Geometry comes from the book of that name by Room and Kirkpatrick, because the multiplicative structure of J9 is the same as that of the unit quaternions.
Math.Combinatorics.LatinSquares
A latin square is an n*n grid, with each cell containing a letter from an alphabet of n letters, such that in each row and in each column, each letter appears exactly once. For example:
1 2 3 4
2 1 4 3
3 4 1 2
4 3 2 1
Two latin squares are orthogonal if, when you superimpose them, each of the n^2 possible letter-pairs appears exactly once in the grid. For example:
1a 2b 3c 4d
2d 1c 4b 3a
3b 4a 1d 2c
4c 3d 2a 1b
It turns out that the existence of mutually orthogonal n*n latin squares is related to the existence of projective planes of order n. Euler's thirty six officers problem asks for a pair of orthogonal latin squares of order 6. It turns out that there is no solution, and this is related to the fact that there is no projective plane of order 6.
(There are projective planes of order q for any prime power q = p^n, and these give rise to mutually orthogonal q*q latin squares. However 6 is not a prime power. It is not known whether there exist projective planes whose order is not a prime power, but it is known by exhaustive computer search that there is no projective plane of order 6, and no pair of mutually orthogonal latin squares of order 6.)
This module lets you construct mutually orthogonal latin squares from projective planes, and other nice stuff.
There is no projective plane of order 6 by Bruck-Ryser_theorem (see https://en.wikipedia.org/wiki/Bruck%E2%80%93Ryser%E2%80%93Chowla)_
ReplyDelete-- no need for computer search here. It's needed for order 10 - the only non-prime power case not covered by this theorem which has been ruled out.