8
$\begingroup$

Let $f(x)$ be an integral irreducible monic polynomial and $\alpha$ be its root. What is the computational complexity of finding representatives of ideal classes of the integral ring $\mathbb{Q}[\alpha]$? What is a natural bound for "sizes" of the representatives in terms of the coefficients of $f$? As is explained in Keith Conrad's notes, this is related to the conjugacy problem for integral matrices.

$\endgroup$
9
  • $\begingroup$ Is there anything better for matrix conjugacy than the old work of Greenwald, Segal etc? $\endgroup$ Apr 26, 2018 at 20:15
  • $\begingroup$ Grunewald and Segal studied a much more complicated problem of multiple conjugacy. $\endgroup$
    – user6976
    Apr 26, 2018 at 20:16
  • $\begingroup$ I vaguely remember Grunewald had better results for single conjugacy on Gln(Z) but I don't remember a reference $\endgroup$ Apr 26, 2018 at 21:30
  • $\begingroup$ See MathRev0579942 $\endgroup$
    – user6976
    Apr 26, 2018 at 21:40
  • $\begingroup$ That is the one. It is not a great algorithm but better than the multiple conjugacy which is pure enumeration. $\endgroup$ Apr 27, 2018 at 0:35

1 Answer 1

5
$\begingroup$

I'm not an expert, but this is what I learned from Lenstra's Algorithms in Algebraic Number Theory (Bull AMS, 1992) and Kirschmer and Voight's paper Algorithmic enumeration of ideal classes for quaternion orders:

For a number field $F$ of degree $n$ and absolute discriminant $d_F$, it seems that the best general results about computing the ideal class group comes from Buchmann's 1990 papers A subexponential algorithm for the determination of class groups and regulators of algebraic number fields and Complexity of algorithms in algebraic number theory:

One can determine the class group with a deterministic algorithm which runs in time $d_F^{3/4}(2+\log d_F)^{O(n)}$, or in expected run time $d_F^{1/2}(2+\log d_F)^{O(n)})$ with a probabilistic algorithm. (Under GRH, one can improve the latter bound for fixed $n$.)

Edit: Aurel points out in a comment below that an improvement of Schoof gives a deterministic algorithm with runtime $d_F^{1/2}(2+\log d_F)^{O(n)})$, and heuristically it should be computable in subexponential (wrt $\log d_F$) time.

While this does not quite answer your question, it suggests that a natural bound for the "size" is the pair of the degree and discriminant of $F=\mathbb Q(\alpha)$. Your question of course involves more general orders than the full ring of integers of $F$, and I have not thought about the details, but because one can reduce the class number calculation for $\mathbb Q[\alpha]$ to that for $F$ and the conductor of this suborder, I would expect your problem to be reducible to the class group problem for $F$ in time that is essentially the size of the ring of integers of $F$ modulo the size of your suborder. (This seems similar to a reduction Kirschmer and Voight do for Eichler orders in quaternion algebras.)

$\endgroup$
6
  • $\begingroup$ Thank you! It may be exactly what I wanted. At least it shows wherte to look for an answer. I will wait a little for a more close answer (perhaps there were more modern results), and then accept. $\endgroup$
    – user6976
    Apr 28, 2018 at 17:28
  • $\begingroup$ @MarkSapir Yes, I don't know if any progress has been made in the past couple of years, but since Kirschmer and Voight quote Buchmann's algorithm as the current state of the art, and their paper is only a few years old, I suspect there is nothing much better yet. $\endgroup$
    – Kimball
    Apr 28, 2018 at 23:48
  • $\begingroup$ @Kimball The probabilistic running time you quote is incorrect. Nobody knows how to achieve such a running time. It should be something like the exponential of what you write, and even such a running time would only be provably achievable under GRH for quadratic fields, and heuristic+GRH otherwise. In addition, the exponent $3/4$ in the deterministic running time has been improved to $1/2$ by Schoof. $\endgroup$
    – Aurel
    Aug 5, 2018 at 20:51
  • $\begingroup$ @Aurel Thanks for the corrections. Yes, I meant to write $d_F^{1/2}(2+\log d_F)^{O(n)}$ for the expected run time, but is this really not known? Lenstra says this should follow from Buchmann (his "Theorem" 5.5). Kirschmer-Voight also state a similar but slightly different expected run time under GRH. Are neither of these actually proven? Also, do you have a reference for the Schoof improvement? $\endgroup$
    – Kimball
    Aug 5, 2018 at 23:27
  • $\begingroup$ @Kimball Oh ok, without the $\log$ it is correct, but by Schoof (I think the title is Computing Arakelov class groups; I can check tomorrow) this is now also known with a deterministic algorithm. I thought you were refering to the subexponential algorithm of Hafner-McCurley-Buchmann, which has much better complexity but needs GRH and is not provably fast (only heuristically). $\endgroup$
    – Aurel
    Aug 6, 2018 at 9:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.