The constructive recognition complexity conjecture for special linear groups

Let d4d\geq 4, let qq be a prime power, and let SL(d,q)\operatorname{SL}(d,q) be given by a generating set. Let ξ\xi denote an upper bound on the number of field operations for computing a random element in SL(d,q)\operatorname{SL}(d,q), and let ζ(q)\zeta(q) denote an upper bound on the number of field operations for constructively recognising SL(4,q)\operatorname{SL}(4,q). The algorithm StandardGenerators\operatorname{StandardGenerators} is the one-sided Monte Carlo algorithm from the paper for constructive recognition of SL(d,q)\operatorname{SL}(d,q). The complexity conjecture. The complexity of StandardGenerators\operatorname{StandardGenerators} is

O(d3log(d)+d2log(d)log(log(d))log(q)+log(d)log(log(d))ξ+ζ(q)).\mathcal{O}\left(d^3 \log(d) + d^2 \log(d) \log(\log(d)) \log(q) + \frac{\log(d)}{\log(\log(d))}\xi + \zeta(q)\right).

This would complete the complexity analysis of the constructive recognition algorithm; the paper states that the detailed analysis is almost complete, while the corresponding adaptations to other classical groups are deferred to follow-up work.

Sources & referencesView supporting material

Primary source

Max Horn, Alice Niemeyer, Cheryl Praeger and Daniel Rademacher, “Constructive Recognition of Special Linear Groups”, arXiv:2404.18860 (2024).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.