Prime power graphs for groups of Lie type (Q1348673)

Let \(G\)~be a finite simple group of Lie type of characteristic \(p\). Define a graph \(\Gamma(G)\) as follows. The vertices of \(\Gamma(G)\) are the prime powers \(r^a\) that occur as orders of some elements of \(G\), for all primes \(r\not=p\) and integers \(a\). The vertices \(r^a,s^b\) are connected if and only if \(G\) has an element of order \(\text{lcm}(r^a,s^b)\) (thus, every vertex of \(\Gamma(G)\) has a loop). Two vertices of \(\Gamma(G)\) called equivalent if they have the same neighbors. Denote the quotient graph with respect to this equivalence relation by \(\Delta(G)\). The graph \(\Delta(G)\) is considered as a graph without loops and multiple edges and as weighted graph: the weight of vertex \(v\) of \(\Delta(G)\) is the least common multiple of the prime powers in the equivalence class \(v\). The main purpose of the present paper is to show that, with an explicit list of exceptions, \(\Delta(G)\) determines \(G\) up to isomorphism (in the class of all finite simple groups of Lie type), and for these exceptions, \(\Delta(G)\) nevertheless determines the characteristic of \(G\). This result was motivated by algorithmic considerations. In the book of the authors [``Black box classical groups'', Mem. Am. Math. Soc. 708 (2001; Zbl 1053.20045)] and in an unpublished paper of the first author and \textit{K. Magaard}, a constructive black-box algorithm for the finite simple groups of Lie type is given. However, in this algorithm the characteristic of the group was part of the input. As a consequence of the main result, the authors prove now that for any finite simple group of Lie type, given as a black-box group with an oracle for the computation of the orders of group elements, \(\Delta(G)\) and the characteristic of \(G\) can be computed by a Monte Carlo algorithm in time polynomial in the input length. But the proof does not provide a practical algorithm. The authors indicate a heuristic shortcut and a conjecture which would make this shortcut a precise argument. The graph \(\Gamma(G)\) is related to the more known prime graph of \(G\) (see the papers of \textit{J. S. Williams} [J. Algebra 69, 487-513 (1981; Zbl 0471.20013)], the reviewer [Mat. Sb. 180, No. 6, 787-797 (1989; Zbl 0691.20013)] and \textit{N. Iiyori} and \textit{H. Yamaki} [J. Algebra 155, No. 2, 335-343 (1993; Zbl 0799.20016)]). The number of connected components is the same in \(\Gamma(G)\) and \(\Delta(G)\), and in most cases this is the same as in the prime graph of \(G\). The authors are interested in \(\Delta(G)\) instead of the prime graph because they cannot construct the prime graph by a Monte Carlo algorithm in polynomial time (since that would require the ability to factor integers).