Can I efficiently verify if given $h$ is the class number of a quadratic field?
Can I efficiently verify if given $h$ is the class number of a quadratic field?
Computing the class number is not tractable.
I tried pari's Qfb
and did some experiments with Lidia, but I must be missing something.
What I tried is for random $a$ compute $a^h$ but I don't get the identity and in Lidia I can't check if it is principal.
If i correctly understand the question, the question is as follows: There are given a quadratic number field $K=\mathbb Q(\sqrt D)$ and a to-be-class number integer $h^?$. We want to verify $h^?=h(K)$ efficiently, in particular without calling the computation of the class number.
(So the question is NOT if for a given $h$ there exists a $K$ realizing $h=h(K)$...)
Is it enough / necessary to verify, that $h^?$ is a multiple of $h(K)$? If yes, then one may have "only" to compute $a$ to the power $h^?$ for each $a$ in the Minkowski cage insured by theory. But we are still not able to claim $h^?=h(K)$, but only $h(K)\ |\ h^?$. This may not even be really effective for the half problem.
The question is a sage question or a math one?
If it is a math question, why not use analytic methods?