Log24

Tuesday, May 28, 2013

Codes

Filed under: General,Geometry — Tags: , , , — m759 @ 12:00 PM

The hypercube  model of the 4-space over the 2-element Galois field GF(2):

IMAGE- A hyperspace model of the 4D vector space over GF(2)

The phrase Galois tesseract  may be used to denote a different model
of the above 4-space: the 4×4 square.

MacWilliams and Sloane discussed the Miracle Octad Generator
(MOG) of R. T. Curtis further on in their book (see below), but did not
seem to realize in 1977 that the 4×4 structures within the MOG are
based on the Galois-tesseract model of the 4-space over GF(2).

IMAGE- Octads within the Curtis MOG, which uses a 4x4-array model of the 4D vector space over GF(2)

The thirty-five 4×4 structures within the MOG:

IMAGE- The 35 square patterns within the Curtis MOG

Curtis himself first described these 35 square MOG patterns
combinatorially, (as his title indicated) rather than
algebraically or geometrically:

IMAGE- R. T. Curtis's combinatorial construction of 4x4 patterns within the Miracle Octad Generator

A later book co-authored by Sloane, first published in 1988,
did  recognize the 4×4 MOG patterns as based on the 4×4
Galois-tesseract model.

Between the 1977 and 1988 Sloane books came the diamond theorem.

Update of May 29, 2013:

The Galois tesseract appeared in an early form in the journal
Computer Graphics and Art , Vol. 2, No. 1, February 1977
(the year the above MacWilliams-Sloane book was first published):

IMAGE- Hypercube and 4x4 matrix from the 1976 'Diamond Theory' preprint, as excerpted in 'Computer Graphics and Art'

Wednesday, July 6, 2011

Nordstrom-Robinson Automorphisms

Filed under: General,Geometry — Tags: , — m759 @ 1:01 AM

A 2008 statement on the order of the automorphism group of the Nordstrom-Robinson code—

"The Nordstrom-Robinson code has an unusually large group of automorphisms (of order 8! = 40,320) and is optimal in many respects. It can be found inside the binary Golay code."

— Jürgen Bierbrauer and Jessica Fridrich, preprint of "Constructing Good Covering Codes for Applications in Steganography," Transactions on Data Hiding and Multimedia Security III, Springer Lecture Notes in Computer Science, 2008, Volume 4920/2008, 1-22

A statement by Bierbrauer from 2004 has an error that doubles the above figure—

The automorphism group of the binary Golay code G is the simple Mathieu group M24 of order |M24| = 24 × 23 × 22 × 21 × 20 × 48 in its 5-transitive action on the 24 coordinates. As M24 is transitive on octads, the stabilizer of an octad has order |M24|/759 [=322,560]. The stabilizer of NR has index 8 in this group. It follows that NR admits an automorphism group of order |M24| / (759 × 8 ) = [?] 16 × 7! [=80,640]. This is a huge symmetry group. Its structure can be inferred from the embedding in G as well. The automorphism group of NR is a semidirect product of an elementary abelian group of order 16 and the alternating group A7.

— Jürgen Bierbrauer, "Nordstrom-Robinson Code and A7-Geometry," preprint dated April 14, 2004, published in Finite Fields and Their Applications , Volume 13, Issue 1, January 2007, Pages 158-170

The error is corrected (though not detected) later in the same 2004 paper—

In fact the symmetry group of the octacode is a semidirect product of an elementary abelian group of order 16 and the simple group GL(3, 2) of order 168. This constitutes a large automorphism group (of order 2688), but the automorphism group of NR is larger yet as we saw earlier (order 40,320).

For some background, see a well-known construction of the code from the Miracle Octad Generator of R.T. Curtis—

Click to enlarge:

IMAGE - The 112 hexads of the Nordstrom-Robinson code

For some context, see the group of order 322,560 in Geometry of the 4×4 Square.

Powered by WordPress