Dgt.dvi

Acta Sci. Math. (Szeged) 63 (1997) 341–351 We examine the minimal distance (number of differing entries) between different group tables of the same order n. Here group table means amatrix of order n with entries from a fixed set of n symbols, which (with suitableborder elements) is the multiplication table of a group. (The border elementsare not considered part of the table. A group is defined up to isomorphism byits multiplication table without border elements.) With the exception of somepairs of groups of orders 4 and 6, which are listed explicitly, different grouptables of order n differ in at least 2n places; and with the exception of somepairs of groups of orders 4, 6, 8 and 9, which are listed explicitly, tables ofnon-isomorphic groups of order n always differ in strictly more than 2n places.
We use the notion of group table, or Cayley table of a group, that is set forthin [2]: for every natural number n we consider all binary operations definedon the set n = {1, . . . , n} that satisfy the group axioms; a group table is amultiplication table of such a group (n, ·). By the existence of an identity,some column contains the elements in the same order as they appear on thevertical border of the table and some row is equal to the horizontal border. Theborder is not regarded as part of the table, however. The abstract group defined(up to isomorphism) by the multiplication table is uniquely determined by theremaining n × n matrix, since any row and column can be used as borders:the resulting operations define isomorphic groups. A group table is necessarilya Latin square, that is, a matrix whose every row and every column containsevery symbol from n exactly once. Given a group table A = (ai,j) of ordern, the set of all tables arising from the same abstract group is the orbit of Aunder Sn × Sn × Sn, acting on Latin squares by permuting rows, columns andnames of entries: (π, σ, ρ)A = (a′i,j) with a′i,j = ρ(aπ(i),σ(j)).
In [1] J. D´enes investigates how many entries can be deleted from a group table such that it remains uniquely reconstructible, and claims [1; Theorem 1and Corollary] that two arbitrary group tables of order n = 4 differ in at least 2n places. In contrast to this we exhibit a pair of tables of the cyclic group oforder 6 of distance 9 (By “distance,” we always mean Hamming distance, ornumber of differing entries.).
D´enes makes two statements: 1) two different group tables of the same group G of order n differ in at least 2n places [1; Lemma 2], and, 2) grouptables of non-isomorphic groups of order n = 4 differ in at least 2n places [1;Lemma 3]. These are reproduced in [2] and also in [3], where 1) is acknowledgedto be false, but no corrected version is given. While 1) is incorrect, (D´enes’proof wrongly assumes that any table of a group can be transformed into anyother by permuting rows and columns), 2) is correct and its proof can beadapted to cover the case of different tables of the same group. We shall showthat exceptions to 1) occur only between tables of the cyclic group of order 4and between tables of the cyclic group of order 6. By suggestion of the refereewe will also classify all pairs of non-isomorphic groups that admit tables ofdistance 2n or less. Note that every group of order n > 1 has tables that differin exactly 2n places: one can get such, for instance, by interchanging two rowsin a table.
Theorem 1. Different tables of groups of order n differ in at least 2n places,except for the following three pairs of groups, for which we give the minimaldistance between different tables below: Z2 × Z2 and Z4: minimal distance 4,Z4 and Z4: minimal distance 7,Z6 and Z6: minimal distance 8.
Corollary. Different tables of groups of order n ∈ {4, 6} differ in at least 2nplaces.
Theorem 2. Tables of non-isomorphic groups of order n always differ instrictly more than 2n places, except for the pair Z2 × Z2 and Z4 that hastables of distance 4 and the following pairs of groups, for which the minimaldistance between tables is 2n: Z6 and D3; Z8 and Z2 × Z4; any pair of non-cyclic groups of order 8; and Corollary. Tables of non-isomorphic groups of order n > 9 differ in more than2n places.
Tables of groups of order n of distance less than 2n Tables of Z2 × Z2 (left) and Z4 (the other three tables), where the table of Z2 × Z2 is of distance 4 from each table of Z4, while different tables of Z4differ in 7 places (these are all possible group tables of order 4 with first rowand first column in natural order): Tables of non-isomorphic groups of distance 2n Tables of Z2 × Z2 × Z2 (upper left), Q8 (upper right), Z2 × Z4 (lower left) and D4 (lower right) of distance 16 from each other. (Differences from the tableof Z2 × Z2 × Z2 are marked): Tables of D3 (left) and Z6 of distance 12: Tables of Z8 (left) and Z2 × Z4 of distance 16: Tables of Z3 × Z3 (left) and Z9 of distance 18: Lemma 1. Let A and A′ be group tables of order n such that some pair ofcorresponding rows is of distance d. If every pair of corresponding rows is ofdistance less than n−d then the groups are isomorphic.
Proof. Let A and A′ be tables of groups G and G′ as indicated, of distanced in row x. Let π be the permutation that, applied to the columns of A,would arrange the elements in row x in the same order as they appear in rowx of in A′, then π moves exactly d letters. Viewed as a permutation of theelements in row x of A′, the i-th row of A is ψiπ and the i-th row of A′ isϕi, where P ′ = {ϕ1, . . . , ϕn} is a regular permutation representation of G′ andP = {ψ1, . . . , ψn} is one of G. We claim that f: P −→ P ′, f(ψi) = ϕi is anisomorphisms of groups. Since ϕi differs from ψiπ and ϕj from ψjπ in less than (n − d)/3 places each, ϕiϕ−1 differs from ψ than 2(n − d)/3 places. Therefore ϕiϕ−1, which occurs in some row of A′, differs from ψiψ−1π, which occurs in some row of A, in e < d + 2(n − d)/3 Since ψiψ−1π has n − e > (n − d)/3 values in common with ϕ these elements must occupy corresponding rows, since ψiψ−1π would differ from every other element of P ′ in at least n − e > (n − d)/3 places, and weknow that corresponding rows are of distance less than (n − d)/3. This meansf (ψiψ−1) = ϕ for all i, j. Now it is an easy exercise that every function between groups that satisfies f (ab−1) = f (a)f (b)−1 is a homomorphism.
Regular permutations of small distance. Consider multiplying a permutation ϕfrom the left by a permutation π that fixes all but a few letters, πϕ = ψ. Everyletter whose image under ϕ is not moved by π has the same image under ψ, andevery letter that is not moved by π has the same pre-image under ψ as under ϕ.
Therefore every block of letters in the cycle representation of ϕ starting with aletter x moved by π and reaching up to the next letter moved by π also occursas a block of adjacent letters in the cycle representation of ψ. We can multiplyϕ by π by considering only the letters moved by π and treating each block ¯ (starting with the letter x moved by π) just like the letter x. Cycles of ϕ thatdo not contain elements moved by π of course remain completely unchanged.
We illustrate this by an example: x represents the block of digits starting with x and . . . stands for possible additional cycles not containing any of the letters moved by π =(a b c d).
(For multiplication with π from the right, one uses the blocks of letters that end with a letter moved by π, beginning just after the previous occurrenceof a letter moved by π in each cycle of ϕ.) d represent non-empty blocks of digits, and . . .
denotes possible additional cycles, which the permutations in question have incommon. The pairs of regular permutations are unordered pairs.
(I) Every pair of regular permutations of distance 2 is of the form (¯ a and ¯b are blocks equal length (and therefore 2 | n).
(II) Every pair of regular permutations of distance 3 is of the form (III) Every pair of regular permutations ϕ and ψ, where ϕ = πψ with π aproduct of two disjoint transpositions, is of one of the following types (IV) Every pair of regular permutations ϕ and ψ, where ϕ = πψ with π a4-cycle, is of one of the following types Sketch of proof. We discuss case III, the others are similar. Consider allproducts (a b)(c d)ϕ = ψ, where ϕ runs through all elements of the symmetricgroup on the letters a, b, c and d. If we replace these letters by ¯ respectively, in the cycles of ϕ and ψ and represent possible additional cycleswhich remain unchanged by . . . , we get a list of all possible ways in whichmultiplication by (a b)(c d) from the left can transform a permutation ¯ ψ. We identify the cases that only differ by a renaming We omit the cases that are incompatible with the requirement that ϕ and We also omit the mention of additional cycles . . . common to ¯ if the length of cycles is different in ϕ and ψ, since common cycles cannot existbetween regular permutations of different cycle lengths. In this way we arriveat the list of types given.
We have already displayed group tables of the distances claimed to be minimal in the exceptional cases of Theorems 1 and 2. It now remains toshow that group tables of order n differ in at least 2n places, unless the groupsare listed in Theorem 1 as an exception, (in which case we must show thatthe distance is at least the claimed minimum); and further, that tables oforder n and distance 2n belong to isomorphic groups or to one of the pairs ofnon-isomorphic groups listed in Theorem 2.
To avoid unnecessary clutter in a proof that is already fraught with case distinctions, we relegate some of the computational details to a separate sectionfollowing the body of the proof.
Let A and A′ be tables of groups G and G′ of order n. For n = 1 or 2 theassertions are evident; we assume n ≥ 3.
Case I: A and A′ differ in every row and every column.
Since two different permutations differ in at least 2 places, A and A′ differin at least 2n places. If there are exactly 2n differences, then every pair ofcorresponding rows is of distance 2 (and similarly for the columns) and Lemma1 implies that the groups are isomorphic if n > 8. Also, 2n is greater or equalthan the minimal distance claimed for pairs of non-isomorphic groups of ordern < 8 and for most pairs of non-isomorphic groups of order 8; it only remainsto check that Z8 does not have a table that differs from a table of a non-cyclicgroup of order 8 other than Z2 × Z4 in exactly two places in every row andcolumn, see (1) below.
Case II: A and A′ agree in some row or column.
Suppose A and A′ agree in row x. (We talk about rows, but the argumentworks mutatis mutandis for columns.) The rows of A and A′, interpreted aspermutations of the elements in row x, give regular permutation representationsP = {ϕ1, . . . , ϕn} of G and P ′ = {ψ1, . . . , ψn} of G′. Let H = P ∩ P ′. If theelements of H do not each occur in the same row in both tables then we canpermute the rows of one table to bring matching elements into correspondingrows without increasing the distance of the tables: Consider the rows whereeither A or A′ has an element of H and the other table has something different;then the number of differences between A and A′ in each of these rows is n, sopermuting them cannot increase the distance. We may therefore assume thatevery element of H occurs in the same position in both tables. Now let s bethe number of rows in which A and A′ agree, then s = |H| and in particulars | n.
Two Latin squares of order 3 that have a row in common consist of the same 3 rows in different order and therefore differ at 6 places. All regularpermutation groups of order 4 are given by the rows of the four tables oforder 4 displayed earlier, the possible distances between tables that agree ina row are easily found by considering the distances between the non-identitypermutations of these groups, and we assume n > 4 from now on.
Case 1: There are no rows of distance 2.
Case 1.1: s ≤ n .
d(A, A′) ≥ 3(n − n ) = 9 n > 2n.
In this case, 3 | n. d(A, A′) ≥ 3(n − n ) = 2n. If all distances between different corresponding rows are 3, then, since there are rows of distance d = 0, thegroups must be isomorphic by Lemma 1 when n > 9. If the tables differ in atleast 4 places in some row, then d(A, A′) ≥ 3(n − n ) + 1 > 2n. (The pairs of non-isomorphic groups of orders 6 and 9 do admit tables of distance 2n.) Note that n is even in this case. Every row of distance d gives elements ϕ ∈ Pand ψ ∈ P ′ with ϕ = πψ, where π moves exactly d elements x, y, . . . and thecycle representations of ϕ and ψ contain the same d (non-empty) blocks ofdigits ¯ y, . . . in different order, as described in the remark before Lemma 2.
If the length of some block is at least 3, say ¯ ϕ2(x1) = ψ2(x1) while ϕ2(xk−1) = ψ2(xk−1). This is impossible: since theindex of H in P ′ is 2, ψ2 ∈ H = P ∩ P ′, so ψ2 and ϕ2 are both elements ofthe regular permutation group G. Therefore the blocks moved by π must beof length at most 2, which implies d ≥ n . This holds for every row in which A and A′ differ, so d(A, A′) ≥ n2 . (In general we get, by the same principle, that d(A, A′) ≥ (n − s)s, where s = |H|.) For n ≥ 8 the distance between A and A′ is therefore at least 2n, and for n > 8 it is more than 2n. We have to check non-isomorphic groups of order 8and groups of order 6 separately, see (2) and (3).
Case 2: Rows of distance 2 exist.
There exist ϕ = (i1 . . . in) ∈ P and σ = (i1 . . . in/2)(i(n/2)+1 . . . in) ∈ P ′. (Notethat n is even in this case, and that at least one of the groups is cyclic.) We haveP = [ϕ], [P ′ : [σ]] = 2 and P ∩ [σ] = {id} (because every cycle of a nontrivialpower of ϕ contains both im with m ≤ n/2 and il with l > n/2), therefore|P ∩ P ′| ≤ 2. Besides ϕ−1 and σ−1 there is no further pair of permutationsof this type, when n = 4. (If ϕk = (j1 . . . jn) ∈ P , 1 < k < n − 1, andρ = (j1 . . . jn/2)(j(n/2)+1 . . . jn) ∈ P ′ then each cycle of ρ contains both im withm ≤ n/2 and il with l > n/2, therefore [σ] ∩ [ρ] = {id}, which is impossibleif n = 4.) Only if both P and P ′ are cyclic can there be an additional pair(j1 . . . jn) ∈ P ′ and (j1 . . . jn/2)(j(n/2)+1 . . . jn) ∈ P , a maximum of 4 rows ofdistance 2 in all. We get d(A, A′) ≥ 3(n − 6) + 4 · 2 = 3n − 10, and evend(A, A′) ≥ 3(n − 4) + 2 · 2 = 3n − 8, if not both groups are cyclic. For n > 8,this means d(A, A′) > 2n for non-isomorphic groups, and d(A, A′) ≥ 2n for twocyclic groups. It remains to check the cases n ∈ {6, 8}, see (4).
(1) We show that Z8 does not have a table that differs from a table of anon-cyclic group of order 8 in exactly two places in every row and column.
Suppose otherwise. In the first row, the differences are in columns x and y,say. We exchange columns x and y in A and get a table B of G that agreeswith A′ in the first row. The rows of B and A′, considered as permutationsof the elements in the first row, form a regular permutation representationP = {ϕ1, . . . , ϕ8} of G = Z8 and P ′ = {ψ1, . . . , ψ8} of G′. Since there areprecisely two differences between A and A′ in every column, either B and A′agree in one further row, or there are two rows of distance 3. In both cases,ψi and ϕi differ by multiplication with a product of two disjoint transpositionsin all further rows, ψi = πiϕi, where πi = (ai bi)(ci di). Among these rowsthere would be one with ϕi an 8-cycle and ψi of some other cycle structure.
By Lemma 2, III this is impossible, as 3 ∤ 8.
(2) We show that there are no tables of Z8 and a non-cyclic group other thanZ2 × Z4, that agree in four rows and are of distance 4 in each of the remainingrows.
Suppose otherwise. The regular permutation representation of Z8 consists of the powers of ϕ = (a1 a2 b1 b2 c1 c2 d1 d2), and H = {id, ϕ2, ϕ−2, ϕ4}. If ψis a regular permutation of distance 4 from ϕ then the 4 blocks of digits thatoccur in different positions in the cycle representation of ψ and ϕ are each oflength 2.
Using Lemma 2, we see that the possible regular permutations of distance 4 from ϕ are α = (a1 a2)(b1 b2)(c1 c2)(d1 d2), β = (a1 d2)(b1 a2)(c1 b2)(d1 c2),γ = (a1 a2 c1 c2)(b1 b2 d1 d2) and δ = (a1 b2 c1 d2)(b1 c2 d1 a2). For ϕ−1, thepossibilities are exactly the inverses of these permutations. The regular per-mutations of distance 4 from ϕ3 are α′ = (a1 b2)(b1 c2)(a2 d1)(c1 d2), β′ =(a1 c2)(b1 d2)(c1 a2)(d1 b2) and also γ and δ; for ϕ−3 they are the inversesof these elements. G′ \ H cannot contain only elements of order 4, becauseH ∪ {γ, γ−1, δ, δ−1} is not a group. We show that if G′ \ H contains anelement of order 2, it also contains an element of order 4.
If α is in a row with ϕ, then δ−1 or γ−1 must be in a row with ϕ−1, since αβ cannot occur in a regular permutation group containing ϕ2, and similarlyfor β in a row with ϕ. (The case of any of the other 8-cycles and an elementof order 2 next to it, is up to conjugation the same as the one we considered).
Now that G′ has more than 2, but less than 6 elements of order 4, it can onlybe Z2 × Z4.
(3) Two tables of Z6 can indeed agree in 3 rows and be of distance 3 each inthe remaining rows, as show in an example earlier. By considering a regularpermutation representation of D3 and the possibilities to complete the subgroupof order 3 to a cyclic group of order 6, one checks easily that tables of Z6 and D3that agree in 3 rows differ in exactly 4 places in each of the remaining rows. Iftwo tables of D3 agree in three rows, the remaining rows are of distance at least4 each, because the only regular permutation that a product of transpositionscould have distance 3 to is a 6-cycle.
(4) Two tables of the cyclic group of order 8 do not admit more than 2 rows ofdistance 2: If (1 2 3 4 5 6 7 8) ∈ P , (1 2 3 4)(5 6 7 8) ∈ P ′ then there is no 8-cyclein P ′ of distance 2 to either (1 3 5 7)(2 4 6 8) or (1 7 5 3)(2 8 6 4), because it wouldhave to contain 4 odd numbers in a row, which is incompatible with its squarebeing (1 2 3 4)(5 6 7 8) or (1 4 3 2)(5 8 7 6), so that d(A, A′) ≥ 3n − 8 in this casetoo. Between a table of Z8 and one of a non-cyclic group there are at most 2rows of distance 3, since each would involve one of the elements of order 4 ofZ8, so d(A, A′) ≥ 18.
Tables of Z6 and D3 differ by at least 12 entries in the case where rows of distance 2 occur: If there are two rows of distance 2, then there are no rows ofdistance 3, because every row of distance 3 would either involve a 6-cycle of Z6or a product of 3-cycles in D3, and these are all spent for the rows of distance2. If there is only one row of distance 2, then the inverses of the elements inthis row, which differ in 2 places, and therefore agree in 4, do not occur in thesame position and produce two rows of distance 4. Since |H| ≤ 2, the distancesadd up to at least 12. Tables of Z6 of distance 3n − 10 = 8 do exist, as shownearlier.
enes, On a problem of L. Fuchs, Acta Sci. Math. (Szeged) 23 (1962), enes and A. D. Keedwell, Latin Squares and Their Applications, enes and A. D. Keedwell, Latin Squares (New Developments in the Theory and Applications), North Holland, Amsterdam, 1991.
Steyrergasse 30A-8010 Graz, Austriae-mail: [email protected]

Source: http://blah.math.tu-graz.ac.at/~frisch/wwwpdf/dgt.pdf