Finite Geometry Notes   | Home | Site Map | Author |

Pattern Groups:
Notes Toward a Definition

by Steven H. Cullinane

Some groups of transformations of square and rectangular arrays preserve interesting families of subsets of the arrays.  Subsets in the preserved families may, for instance, be symmetric, even though the transformations are themselves asymmetric and discontinuous.  Similarly for cubical arrays.

 Geometry of the 4x4 Square The Diamond 16 Puzzle The Eightfold Cube The Diamond Theorem Diamond Theory Notes on Finite Geometry

In the 1970's, R. T. Curtis discovered that the large Mathieu group may be represented as a group of discontinuous transformations acting on a rectangular 4x6 array of square cells, or tiles, in such a way that the Carmichael-Witt family of 759 "octads" forming a Steiner system S(5,8,24), previously known to be preserved by the large Mathieu group, appears as a family of geometrically natural subsets of the rectangular array.  The relevant paper:
Curtis, R. T., A new combinatorial approach to M24, Math. Proc. Camb. Phil. Soc. 79 (1976), pp. 25-42
For details of how the Curtis model of the 759 octads is related to a group of 322,560 symmetry-preserving discontinuous transformations of a 4x4 array of square tiles, see Geometry of the 4x4 Square.

These groups act on square cells, or tiles, but discontinuous transformations may also act on, say, plane 2-colored tilings by equilateral triangles, with each triangle all black or all white; permutations of the triangles are induced by permutations of the triangles' centers.  Groups of such discontinuous transformations may preserve families of two-colored infinite plane patterns, each of which has some symmetry. Groups of discontinuous transformations may, of course, also act on tilings of non-Euclidean surfaces such as the hyperbolic plane.

There is as yet no general theory of families of patterns (i.e., of families of subsets) invariant under discontinuous transformations acting on plane or 3-space tilings.

#### An elementary example:

The above observations may contribute to the beginnings of such a theory. Clearly, letting a family of patterns generate a vector space under binary addition (i.e., symmetric difference of subsets) is a central strategy. What geometric properties of such vector spaces we may expect to emerge under group actions is, as the work of Curtis shows, not so clear. It seems that such a general theory of pattern-invariance might throw some additional light on such phenomena as the connection of the affine hyperplanes that underlie the diamond theorem with the Curtis model of the 759 octads (which includes versions of those affine hyperplanes).

Since n×n square patterns of black and white cells-- i.e., (0,1)-matrices-- are, essentially, binary relations on a finite set, such a theory would be rather closely related to the 1938 work of Marc Krasner on certain Galois connections:

From Ferdinand Börner, Martin Goldstern, and Saharon Shelah,
Automorphisms and strongly invariant relations (pdf),
a preprint dated Sept. 9, 2003

(Related material: A. Schleiermacher,
"Über einen Satz von Krasner,"
1. Teil (pdf) and 2. Teil (pdf))

Related material may be found by a Google search on, say, "Galois connection" + "permutation group" + "relation."

What might be a suitable name for such a theory of patterns?  "Discontinuous transformations" seems both too general and too close to the name of another theory, that of "discontinuous (i.e., discrete) groups."  "Tiling groups" is already taken.  The name "pattern groups" seems brief, descriptive, and reasonably new.

Note that the above-mentioned work of R. T. Curtis shows that under a suitably inclusive definition of pattern, the large Mathieu group is a "pattern group"-- i.e., a group of automorphisms of a pattern (that is, a subset), or a family of patterns, or a family of families* of patterns, etc.

(Some restriction in the definition is needed to prevent every finite group being called a "pattern group," since every finite group may be represented as a group of discontinuous transformations acting on square (0,1)-matrices, i.e., on permutation matrices-- "patterns" of a sort.  It is not, however, clear what this restriction should be.)

The name "pattern groups" also serves to correct a serious error at the heart of what at first glance appears to be a closely related treatise:
Branko Grunbaum and G. C. Shephard,
Tilings and Patterns, W. H. Freeman and Co.,
New York 1987
Grunbaum and Shephard say that

"In every civilization and culture, colored tilings and patterns appear among the earliest decorations.... An early paper with remarkable counterchange designs formed by diagonally divided squares -- one-half black, one-half white -- was published by Truchet [1704]. For a more recent treatment, with many illustrations, see Cullinane [1976]. However, all these were more or less 'accidental' occurrences, independently reinvented many times.... The only artist who deliberately and consistently tried to investigate colored patterns (more specifically, colored tilings) was M. C. Escher...."

-- Pages 463 and 464; the "Cullinane [1976]" reference is to a preprint, "Diamond Theory," named on page 661.

The statement that "Cullinane [1976]" was "accidental" and not "deliberate and consistent" is an error... An understandable error, since the mathematics in the 1976 preprint and a later 1979 abstract (see The Diamond Theorem) involves a level of sophistication (matrix algebra over Galois fields) that Grunbaum and Shephard clearly lack.

#### * On "families of families" of subsets

`From: Robin Chapman Subject: Re: Automorphism group of S_nDate: Sun, 11 Feb 2001 10:26:17 GMTNewsgroups: sci.mathIn article <20010210221446.08836.00000412@ng-co1.news.gateway.net>,  jamesrheckman@gateway.netnospam (Jim Heckman) wrote:>> Yeah, I've seen that in a few places. Perhaps more to the OP's> point is actually constructing Aut(S_6), which I've only seen done> by laboriously exploring the detailed structure of S_6, or by> making use of the (not obvious) isomorphism between A_6 and> PSL(2,9) -- which requires knowing a lot about finite groups of> Lie type. Is there a "simple" way to construct Aut(S_6), or at least> to show that its order is 2*|S_6|?The argument used to show that Aut(S_n) is usually S_n gives you thatAut(S_6) has order |S_6| or 2|S_6|. So we have to find an automorphismof S_6 not an inner automorphism. The classical approach is due toSylvester (or was it Cayley)?S_6 acts on the numbers 1, 2, 3, 4, 5, 6. A duad is an unorderedpair of these numbers, eg 13 or 25. S_6 acts on these. A synthemeis an unordered triple of disjoint duads e.g. 13/25/46. S_6 actson these too. A synthematic total is an unordered quintuple ofsynthemes incorporating all 15 duads, e.g13/25/46//14/26/35//12/34/56//15/24/36//16/23/45.There are 15 duads, 15 synthemes and 6 synthematic totals.Each permutation of S_6 gives rise to a permutation of the duads,of the synthemes and of the synthematic totals. Labelling thetotals arbitrarily from 1 to 6 we see that each element of S_6 givesrise to another via the permutation of the totals. Thus we geta homomorphism from S_6 to S_6 which we see cannot be trivial.But we can checkthat a transposition (i j) permutes the totals without fixed pointsso this automorphism is not linear.The whole setup can be reversed. Each duad of totals corresponds to asyntheme. Each syntheme of totals correponds to a duad and eachsynthematic total of totals corresponds to a number. If we look at thepermutations of the set {numbers} u {totals} preverving the "structure"we get a group of order 1440 having S_6 as a subgroup. This isAut(S_6).`

-- Source:
http://www.math.niu.edu/~rusin/known-math/01_incoming/aut_S6

For related material, see "The alternating group of degree 6 in geometry of the Leech lattice and K3 Surfaces" (pdf) by Jonghae Keum, Keiji Oguiso, and De-Qi Zhang.

Update of March 5, 2009:

Since this page was created, others have used the phrase "pattern group" with a different meaning:

 From "Supercharacter Formulas for Pattern Groups," by Persi Diaconis and Nathaniel Thiem, preprint of Oct. 4, 2006: Let Un(Fq) be the group of uppertriangular n × n matrices with entries in the finite field Fq, and with ones on the diagonal.... The primary focus of this paper is on a large class of subgroups called pattern subgroups. Let J ⊆ {(i, j) | 1 ≤ i < j ≤ n} be a subset that is closed in the sense that (i, j), (j, k) ⊆ J implies (i, k) ⊆ J (i.e. J is a partial order on {1, 2, . . . , n}). The pattern group UJ is the subgroup of Un(Fq) consisting of matrices whose (i, j)th entry is permitted to be nonzero only if (i, j) ∈ J.

Page created October 2, 2005.