For each family of finite classical groups, and their associated simple quotients, we provide an explicit presentation on a specific generating set of size at most 8. Since there exist efficient algorithms to construct this generating set in any copy of the group, our presentations can be used to verify claimed isomorphisms between representations of the classical group. The presentations are available in Magma.
The conjecture was motivated by potential complexity applications to questions about matrix groups defined over finite fields (see @cite_21 for details); its proof also provided verification for the first constructive recognition algorithms for classical groups, developed by Kantor and Seress @cite_4 .
@cite_21 @cite_4
2591592591 1980351200 2023348178 1964155237
This paper considers the problem of designing maximum distance separable (MDS) codes over small fields with constraints on the support of their generator matrices. For any given @math binary matrix @math , the GM-MDS conjecture, proposed by , states that if @math satisfies the so-called MDS condition, then for any field @math of size @math , there exists an @math MDS code whose generator matrix @math , with entries in @math , fits the matrix @math (i.e., @math is the support matrix of @math ). Despite all the attempts by the coding theory community, this conjecture remains still open in general. It was shown, independently by and , that the GM-MDS conjecture holds if the following conjecture, referred to as the TM-MDS conjecture, holds: if @math satisfies the MDS condition, then the determinant of a transform matrix @math , such that @math fits @math , is not identically zero, where @math is a Vandermonde matrix with distinct parameters. In this work, we first reformulate the TM-MDS conjecture in terms of the Wronskian determinant, and then present an algebraic-combinatorial approach based on polynomial-degree reduction for proving this conjecture. Our proof technique's strength is based primarily on reducing inherent combinatorics in the proof. We demonstrate the strength of our technique by proving the TM-MDS conjecture for the cases where the number of rows ( @math ) of @math is upper bounded by @math . For this class of special cases of @math where the only additional constraint is on @math , only cases with @math were previously proven theoretically, and the previously used proof techniques are not applicable to cases with @math . We build a theory of black box groups, and apply it to matrix groups over finite fields. Elements of a black box group are encoded by strings of uniform length and group operations are performd by an oracle. Subgroups are given by a list of generators. We prove that for such subgroups, membership and divisor of the order are in NPB. (B is the group box oracle.) Under a plausible mathematical hypothesis on short presentations of finite simple groups, nom membership and exaact order will also be in NPB and thus in NPB ∩ NPB. [1] conjectured the existence of a sharp threshold on model parameters for community detection in sparse random graphs drawn from the stochastic block model. Mossel, Neeman and Sly [2] established the negative part of the conjecture, proving impossibility of non-trivial reconstruction below the threshold. In this work we solve the positive part of the conjecture. To that end we introduce a modified adjacency matrix B which counts self-avoiding paths of a given length e between pairs of nodes. We then prove that for logarithmic length e, the leading eigenvectors of this modified matrix provide a non-trivial reconstruction of the underlying structure, thereby settling the conjecture. A key step in the proof consists in establishing a weak Ramanujan property of the constructed matrix B. Namely, the spectrum of B consists in two leading eigenvalues ρ(B), λ2 and n -- 2 eigenvalues of a lower order O(ne √ρ(B) for all e 0, ρ(B) denoting B's spectral radius. We conjecture that every finite groupGhas a short presentation (in terms of generators and relations) in the sense that the totallengthof the relations is (log|G|)O(1). We show that it suffices to prove this conjecture for simple groups. Motivated by applications in computational complexity theory, we conjecture that for finite simple groups, such a short presentation is computable in polynomial time from the standard name ofG, assuming in the case of Lie type simple groups overGF(pm) that an irreducible polynomialfof degreemoverGF(p) and a primitive root ofGF(pm) are given. We verify this (stronger) conjecture for all finite simple groups except for the three families of rank 1 twisted groups: we do not handle the unitary groupsPSU(3, q) = 2A2(q), the Suzuki groupsSz(q) = 2B2(q), and the Ree groupsR(q) = 2G2(q). In particular,all finite groups G without composition factors of these types have presentations of length O((log|G|)3). For groups of Lie type (normal or twisted) of rank ≥ 2, we use a reduced version of the Curtis–Steinberg–Tits presentation.