Check character systems using Chevalley groups

Claudia Broecker, Ralph-Hardo Schulz and Gernot Stroth

Dedicated to Prof. Dr. Hanfried Lenz on occasion of his 80^{th} birthday

Abstract: We show that the Sylow 2-subgroups of nearly all Chevalley groups in even characteristic allow the definition of a check-character-system which detects all single and the most important double errors.

Key words: check character system, check digit system, error detecting code, Suzuki-2-groups, fixed-point-free automorphisms, p-groups, Chevalley groups

0. Introduction Defining a check character system over a finite group using one of its automorphisms, we derive the necessary conditions for the detection of the most frequent errors (cf. [?], [?] ). In the abelian case, there are many groups fulfilling these conditions ([?]). Here, we give examples for the non-abelian case; indeed the Sylow-2-groups of nearly all Chevalley groups can be used for the construction of such a check character system.

1. The Problem

Definition 1 :Check-character-system ([?]) Let (G, ·) be a finite group and δ_{1}, ..., δ_{n} permutations of the set G. Then a check character system on the alphabet G ( defined implicitely ) is given by G^{n−1} → G^{n} with g_{1}...g_{n−1} ↦ g_{1}...g_{n−1}g_{n} where the check character g_{n} is determined from the information digits by the check equation

∏_{i=1}^{n} δ_{i}(g_{i}) = 1.

In this article we put δ_{i} := T^{i} for a fixed automorphism T of the group G.

In tabular 1 we give a list of the most important errors (cf. [?] ) and state sufficient conditions on the automorphism T for the detection of these errors. For n ≥ 4 the conditions are also necessary.

Tabular 1

Type  Conditions on T
( for all a, y ∈ G, a ≠ 1)
1. g_{1}...g_{i}...g_{n} ⇝ g_{1}...g′_{i}...g_{n} none
2.a) g_{1}...g_{i}g_{i+1}...g_{n} ⇝ g_{1}...g_{i+1}g_{i}...g_{n}  T (a) ≠ y^{−1}ay
b) ...g_{i}g_{i+1}g_{i+2}... ⇝ ...g_{i+2}g_{i+1}g_{i}...  T^{2}(a) ≠ y^{−1}ay
3.a) ...g_{i}bbg_{i+3}... ⇝ ...g_{i}b′b′g_{i+3}...  T (a) ≠ y^{−1}a^{−1}y
b)  ...bg_{i}b... ⇝ ...b′g_{i}b′...  T^{2}(a) ≠ y^{−1}a^{−1}y

Proof . Consider e.g. type 2.a). The error is detected iff T^{i}(g_{i})T^{i+1}(g_{i+1}) ≠ T^{i}(g_{i+1})T^{i+1}(g_{i}) which is equivalent to T (g_{i+1}g_{i}^{−1}) ≠ g_{i}^{−1}(g_{i+1}g_{i}^{−1})g_{i}. The other conditions follow in the same way. □

Definition 2: Let G be a finite group. An automorphism T of G is called good provided for all x ∈ G, x ≠ 1 we have

(i) x^{T} is not conjugate to x or x^{−1} in G
(ii) x^{T ^{2}} is not conjugate to x or x^{−1} in G

We are going to show that there are many groups G possessing a good automorphism.

Remarks: 1.) If G is abelian, then T satisfies the conditions 1, 2.a), 2.b) and 3.a) if T^{2} is fixed-point free on G and T is good if T^{4} is fixed-point free. 2.) Note that for any group G and automorphism T of odd order t already condition 2a) implies that T is good: Since gcd (4, t) = 1 there exist integers r and s with 4r + st = 1; therefore, any conjugate class fixed by T^{4} must be fixed by T = T^{4r+st} too.

2. A first example We consider the following group in the non-abelian case: The set Q of matrices of the type

(x, y) := ( \begin{matrix}1 & x & y \\ 0 & 1 & x^{q} \\ 0 & 0 & 1 \end{matrix} )

with x, y ∈ GF (q^{2}), q = 2^{m} > 2 and y+y^{q} +x^{q+1} = 0 and its automorphisms induced by conjugation with

H_{λ} := ( \begin{matrix}λ^{−q} & 0 & 0 \\ 0 & λ^{q−1} & 0 \\ 0 & 0 & λ \end{matrix} ) (λ ∈ GF (q^{2})^{⋆})

form a Suzuki-2-group of type B ([?], cf. [?] pp 314-315 ).

Proposition 1 Let Q be the Suzuki-2-group of order q^{3} defined above. Then the automorphism T : (x, y) ↦ (xλ^{2q−1}, yλ^{q+1}) is a good automorphism if the multiplicative order of λ is not a divisor of (q + 1).

Proof . Let \overline{(x, y)} denote the conjugacy class of an element (x, y) of Q. Then \overline{(x, y)} = \{(x, y + xa^{q} + x^{q}a) : (a, b) ∈ Q\} and \overline{(x, y)^{−1}} = \{(x, y^{q} + xa^{q} + x^{q}a) : (a, b) ∈ Q}. To fulfill condition 2.a) it is sufficient to have λ^{q+1} ≠ 1 for the involutions (0, y) with y ∈ GF (q) and λ^{2q−1} ≠ 1 otherwise. But λ^{2q−1} = 1 = λ^{q^{2}−1} means that the multiplicative order of λ is 3 in which case the two conditions are equivalent. Since o (λ) is odd we can use Remark 2 from section 1. □

Corollary The check character system defined over the Suzuki-2-group Q using the automorphism T of order q − 1 detects all single errors, neighbour-transpositions, twin errors, jump-transpositions and jump-twin-errors.

3. Good automorphisms on p-groups The following Lemma shows that it is not possible to classify even the pgroups admitting a good automorphism.

Lemma 1: Let P be a p-group and α ∈ Aut (P). Suppose gcd (o(α), p (p − 1)) = 1. Then α is good if and only if α is fixed point free on P.

Proof . There exists an α-invariant chain P_{o} = 1<P_{1} <…< P_{n} = P of normal subgroups of P such that P_{i}/P_{i−1} is elementary abelian and [P, P_{i}] ⊆ P_{i−1} for i = 1, …, n: Take for instance P_{1} := Ω_{1}(Z(P)) and define P_{i} inductively such that P_{i}/P_{i−1} = Ω_{1}(Z(P/P_{i−1})). (Here Ω_{1}(G) denotes the subgroup of G generated by the elements of order p).

Suppose first that α acts fixed point freely on P. Then α acts fixed point freely on each P_{i}/P_{i−1} (cf. [?] p 335). Choose x ∈ P such that x^{α} is conjugate in P to x. Let i be minimal with x ∈ P_{i}. Suppose i > 0. Then x ∉ P_{i−1} and so x^{α} ∈ P_{i} ∖ P_{i−1}. Now (xP_{i−1})^{α} is conjugate to xP_{i−1}. As x^{−1}x^{P} ⊆ [P_{i}, P] ⊆ P_{i−1} we have x^{P} ⊆ xP_{i−1}. Hence ⟨xP_{i−1}⟩^{α} = ⟨xP_{i−1}⟩. As Aut(⟨xP_{i−1}⟩) is cyclic of order p − 1, and gcd (o(α), p − 1) = 1, we see (xP_{i−1})^{α} = xP_{i−1}, which contradicts the fact that α acts fixed point freely on P_{i}/P_{i−1}. Hence i = 0 and so x = 1. As o(α) is odd we can apply Remark 2 of section 1 and see that α is good.

If α is good, then by definition α acts fixed point freely on P. □

Proposition 2: Let G ≅ L_{2}(q), q = 2^{m}, m > 1, and S ∈ Syl_{2} (G) . Then for every u with u|(q − 1), u ≠ 1 there is some α ∈ G of order u, such that α induces a good automorphism on S.

Proof . We have

S = \{\binom{1 0}{v 1}|v ∈ GF (q) \} and T = \{\binom{x 0}{0 x^{−1}}|x ∈ GF (q)^{∗}\}

Let t ∈ T, t ≠ 1.Then t acts fixed point freely on S. As o(t) is odd, the assertion follows with Lemma 1. □

Proposition 3: Let G ≅ U_{3} (q), q = 2^{m} > 2, and S ∈ Syl_{2} (G). Then for every u with u|(q − 1), u ≠ 1 there is some α ∈ G of order u, such that α induces a good automorphism on S.

Proof . S is of the form considered in section 2. □

Proposition 4: Let G ≅ Sz (q), q = 2^{2m+1} > 2, and S ∈ Syl_{2} (G), furthermore 1 ≠ u|(q − 1). Then there is some α ∈ G of order u, such that α induces a good automorphism on S.

Proof . Defining x^{π} := x^{2^{m+1}}, we have (cf. [?] pp 182-184) without loss of generality

S = \{( \begin{matrix}1 & 0 & 0 & 0 \\ a & 1 & 0 & 0 \\ b & a^{π} & 1 & 0 \\ a^{2+π} + ab + b^{π} & a^{π+1} + b & a & 1 \end{matrix} ) | a, b ∈ GF (q)\}

and

T = \{( \begin{matrix}λ^{1+2^{m}} & 0 & 0 & 0 \\ 0 & λ^{2^{m}} & 0 & 0 \\ 0 & 0 & λ^{−2^{m}} & 0 \\ 0 & 0 & 0 & λ^{−1−2^{m}} \end{matrix} ) | λ ∈ GF (q)^{⋆}\}

Then |T | = (q − 1) and T acts fixed point freely on S. The assertion follows with Lemma 1. □

From the propositions 2, 3 and 4 we get:

Result 1: The Sylow 2-subgroups of L_{2}(q), Sz(q) and U_{3}(q) with q = 2^{m} are examples of groups which admit a good automorphism.

Corollary The groups mentioned in Result 1 admit a check character system which detects all single errors, neighbour-transpositions, twin errors, jump transpositions and jump-twin-errors.

Result 2: Let S be a Sylow 2-subgroup of a Chevalley group (twisted or not) over GF (q), q = 2^{m}. Then there is some α ∈ G such that α induces a good automorphism α of S with o(α)|(q − 1), provided q is large enough.

Sketch of the proof. (The details can be worked out easily by the interested reader.) The main idea is to prove the assertion by an induction to the Lie rank. The statement is true for the groups of Lie rank 1, i. e. L_{2}(q), Sz(q) and U_{3}(q), see Result 1. All Lie groups possess a maximal parabolic H such that H/O_{2}(H) possesses a normal subgroup K which is a Lie group of smaller rank, |H/O_{2}(H) : K| is odd and K is centralized by a cyclic group T of order (q − 1)/d, where d = 1, 3 or d = gcd (n, q − 1) in case G ≅ L_{n} (q) (see [Ca] for details). Let T = ⟨β⟩. Then β^{i} acts fixed point freely on O_{2}(H) for β^{i} ≠ 1(cf. [?] ). By induction on the Lie rank there is some γ ∈ K, with o(γ)|(q − 1), such that γ induces a good automorphism on S/O_{2}(H), S ∈ Syl_{2} (G).

As any K-composition factor in O_{2}(H) is a module over GF (q) we get that γ is diagonizable. Suppose q is large enough, then there is a power β^{i} such that β^{i} does not share any eigenvalue with γ on the modules of K in O_{2}(H). Set α = γβ^{i}. Then α acts fixed point freely on S. The conclusion follows with Lemma 1. □

The result is also true for Sylow p-subgroups of Chevalley groups over GF (p), p odd. For example the Sylow 3-subgroup of L_{3}(3^{3}) possesses a good automorphism α of order 13.

We will conclude this paper with some general Remarks. 1.) If a group G possesses a good automorphism of prime order, then by a result of J. Thompson [Go, 10.2.1] G is nilpotent. So the Sylow groups are characteristic and we can apply Lemma 1. 2.) If G possesses a good automorphism α with gcd (o(α), |G|) = 1 then by [Ro] G is solvable. For solvable groups a similar lemma as Lemma 1 holds if gcd (o(α), |G|φ(|G|)) = 1 as one can derive by analyzing G · ⟨α⟩. But this condition is not necessary for the existence of a good automorphism, as can be seen from the following. 3.) Let N be the additive group of the 3-dimensional vector space K^{3} over K = GF (8); then N is elementary abelian of order 2^{9}. We see that N admits the linear mappings with matrices from

T = \{( \begin{matrix}a & & O \\ & a^{2} \\ O & & a^{4} \end{matrix} ) |a ∈ GF (8)^{⋆}\} ≤ SL_{3}(8),

furthermore the automorphisms γ̄ and β̄ with matrix

( \begin{matrix}0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix} ) and ( \begin{matrix}b & & O \\ & b \\ O & & b \end{matrix} ) = b I_{3}

(for a fixed b ∈ GF (8) ∖ {0, 1}) respectively. Let G = T N be the semidirect product of T and N, defined by (t_{1}, n_{1}) (t_{2}, n_{2}) = (t_{1} · t_{2}, n_{1}^{t_{2}} + n_{2}). Now G, a group of order 7 · 2^{9}, is soluble but not nilpotent. Any automorphism ξ̄ of N normalizing T can be extended to an automorphism ξ of G by defining (t, n)^{ξ} := (ξ̄^{−1} t ξ̄, nξ̄). So, from γ̄ and β̄, one gets automorphisms γ and β of order 3 and 7. Since γ and β commute, α := βγ is an automorphism of order 21 of G. Assume that α is not good. By remark 2 of section 1 we can assume without loss of generality that there exists an element x ∈ G^{⋆} which is conjugate to x^{α}. Let (t, n)^{α} = (s, m)^{−1}(t, n) (s, m). Since γ̄^{−1}tγ̄ = t^{2} we see that t^{2} = t = id and bnγ̄ = n^{s}. But this equation holds only for n = 0 or b^{3} = b = 1, a contradiction. So we have found a good automorphism α of the group G with

gcd (o(α), |G|) = gcd (21, 7 · 2^{9}) ≠ 1 .

References

[Ca] R. Carter, Simple groups of Lie type, Wiley 1972

[Go] D. Gorenstein, Finite groups, Harper and Row 1968

[Hi] Higman,G., Suzuki-2-Groups, Illinois J. Math. 7, pp 79-96 (1963)

[Hu1] Huppert,B. & N.Blackburn, Finite Groups II, Berlin etc. Springer V. (1982)

[Hu2] Huppert, B. & N.Blackburn, Finite Groups III, Berlin etc. Springer V. (1982)

[Ro] P. Rowley, Finite groups admitting a fixed point free automorphism group, J. Algebra, to appear

[S1] Schulz,R.-H., Codierungstheorie ,Vieweg Verlag, pp 58-62 (1991)

[S2] Schulz,R.-H., Check character systems over groups and orthogonal Latin squares, Applic. Algebra in Eng., Comm. and Computing, AAECC, to appear

[Ve] Verhoeff,J., Error Detecting Decimal Codes, Math.Centre Tracts 29, Math. Centrum Amsterdam (1969)

Claudia Broecker,  Gernot Stroth
Ralph-Hardo Schulz  Martin-Luther-Universität
2. Mathematisches Institut  Halle-Wittenberg
Freie Universität Berlin  Fachbereich Mathematik und Informatik
Arnimallee 3  Institut für Algebra und Geometrie
D-14195 Berlin  D-06099 Halle
e-mail: schulz@math.fu-berlin.de e-mail:
or broecker@math.fu-berlin.de  stroth@coxeter.mathematik.uni-halle.de