Re: Question on completeness of the qfminin() command on finding all vectors for a given positive definite symmetric matrix

[Karim Belabas <Karim.Belabas@math.u-bordeaux.fr>]

* Bill Allombert [2024-03-09 20:32]:
> On Mon, Mar 04, 2024 at 05:57:06PM -0800, American Citizen wrote:
> > Hermann:
> > 
> > You are exactly correct!. I have to add the negative points, since qfminim
> > only supplies the "positive" vectors. Note that I said "positive" vectors,
> > because the entries might < 0.
> > 
> > I know now that Bill wrote this algorithm to give the most efficient answer,
> > and we have to remember to add the "negative" vectors.
> 
> Thanks but qfminim is older than my involvement with PARI/GP!

Christian Batut wrote a first version (the original minim() function,
using the Fincke-Pohst algorithm), I wrote the current one in 1997.

> When qfminim was written, memory was a serious limitation of computers.
> Storing only half the vectors saved a lot of memory for lattices with lots of
> minimal vectors like the Leech lattice.

Funny, it turns out I am currently thinking about the internal
(re)implementation of qfminim used in bnfinit. That function
Fincke_Pohst_ideal() looks for friable elements of small Euclidean (not
algebraic!) norm in various ideals to find relations in the class group
and ultimately determine it. Given an isometry of finite order n
(attached to x -> ζ x in the number field for some n-th root of unity,
generalizing the obvious x -> -x), then it is enough to enumerate a
single vector in each orbit.

Memory is not the concern here: all such vectors, whether friable or
not, provide the same information so there's no need to consider them all.
We have internal cutoffs so we do not gain a straight factor n; but in the
wost case we do, and it also complicates late stage linear algebra for no
reason (introducing useless relations that will need to be filtered out).
Finally, it makes "compact units" (represented in factored form) more
complicated than they should, since we can end up with various ζ^k x in
the factorization, instead of grouping them together.

I don't know how to gain a factor n in the enumeration in this case,
where gaining a factor 2 from x -> -x was straightforward (make the
first non-zero coordinate positive). I'm not even sure of how to
efficiently choose a representative in each orbit. What I'm currently
doing is enumerating n/2 vectors in the orbit (up to x->-x)
of each FRIABLE element we discover - there are few of them - and
choosing an arbitrary (lexicographic) minimum. I'd very much like to
perform efficiently the same task at the level of the initial
enumeration of vectors, before the expensive friability test.
Can't really afford to enumerate n/2 as many vectors just to choose
"reduced" representatives.

Cheers,

    K.B.
-- 
Pr. Karim Belabas, U. Bordeaux, Vice-président en charge du Numérique
Institut de Mathématiques de Bordeaux UMR 5251 - (+33) 05 40 00 29 77
http://www.math.u-bordeaux.fr/~kbelabas/