The Existence of Minimal Logarithmic Signatures for Classical Groups.

摘要

A logarithmic signature (LS) for a finite group G is an ordered tuple alpha = [A1, A 2, ..., An] of subsets A i of G, such that every element g ∈ G can be expressed uniquely as a product g = a1a2 ..., an, where ai ∈ Ai. Logarithmic signatures were defined by Magliveras in the late 1970's for arbitrary finite groups in the context of cryptography. They were also studied for abelian groups by Hajos in the 1930's. The length of an LS alpha is defined to be ℓ(alpha) = i=1n |Ai|. It can be easily seen that for a group G of order j=1kp jmj , the length of any LS alpha for G satisfies ℓ(alpha) ≤ j=1k mjpj. An LS for which this lower bound is achieved is called a minimal logarithmic signature (MLS). The MLS conjecture states that every finite simple group has an MLS. If the conjecture is true then every finite group will have an MLS. The conjecture was shown to be true by a number of researchers for a few classes of finite simple groups. However, the problem is still wide open.;This dissertation addresses the MLS conjecture for the classical simple groups. In particular, it is shown that MLS's exist for the symplectic groups Sp2n(q), the orthogonal groups O-2n (q') and the corresponding simple groups PSp2n( q) and W-2n (q') for all n ∈ N , prime power q and even prime power q'. The existence of an MLS is also shown for all unitary groups GU n(q) for all odd n and q = 2s under the assumption that an MLS exists for GUn--1( q). The methods used are very general and algorithmic in nature and may be useful for studying all finite simple groups of Lie type and possibly also the sporadic groups. The blocks of logarithmic signatures constructed in this dissertation have cyclic structure and provide a sort of cyclic decomposition for these classical groups.