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

[American Citizen <website.reader3@gmail.com>]

Aurel and Karim:

I appreciate your comments. I actually did not catch on to +/- in front of v, so you have my apology.

I was struggling with 2 issues in my code, I actually was NOT catching the torsion points (3 of them) combination with the infinite points, and that led me to discover that the +/- vectors were incomplete and that I had to take the negative also.

Also I had a very subtle problem occurring, when adding in the torsion + infinite point, with the set union command which actually reset the points which the loop was looking at, causing the loop to prematurely exit. This was a bit difficult to find as I had to insert tracing into the program.

I do have the ellpool(curve,basis, height) command now working, and it is MUCH faster than my original naive approach of repetitiously adding points and torsion to each pass through the pool. For a rank 3 curve, I timed the new routine using qfminim at 61x faster, a very significant speed up.

Again I apologize. But I actually did read the documentation as the very first step which I did. But obviously I didn't fully understand a key point, although working with my code caused me to realize that "only 1 vector of the +/- set is saved" was actually happening.

I won't belabor this anymore.

Thank you again for your patience.

Randall

On 3/4/24 23:27, Aurel Page wrote:

Dear Randall,

Here is the citation, copied from the first paragraph of the documentation that you reproduced in your email: "storing at most m pairs of vectors: only one vector is given for each pair ± v". :-)
Maybe you have a suggestion for a different formulation that would be more noticeable?

Cheers,
Aurel

On 05/03/2024 02:55, American Citizen wrote:

I have to point this out to everyone, sorry... but I did read the documentation and please find for me the word "negation" ? Please! I beg you!

The documentation (web page  https://pari.math.u-bordeaux.fr/dochtml/html/Vectors__matrices__linear_algebra_and_sets.html#qfminim)  states

qfminim(x, {B}, {m}, {flag = 0})

x being a square and symmetric matrix of dimension d representing a positive definite quadratic form, this function deals with the vectors of x whose norm is less than or equal to B, enumerated using the Fincke-Pohst algorithm, storing at most m pairs of vectors: only one vector is given for each pair ± v. There is no limit if m is omitted: beware that this may be a huge vector! The vectors are returned in no particular order.

The function searches for the minimal nonzero vectors if B is omitted. The behavior is undefined if x is not positive definite (a "precision too low" error is most likely, although more precise error messages are possible). The precise behavior depends on flag.

* If flag = 0 (default), return [N, M, V], where N is the number of vectors enumerated (an even number, possibly larger than 2m), M ≤ B is the maximum norm found, and V is a matrix whose columns are found vectors.

* If flag = 1, ignore m and return [M,v], where v is a nonzero vector of length M ≤ B. If no nonzero vector has length ≤ B, return []. If no explicit B is provided, return a vector of smallish norm, namely the vector of smallest length (usually the first one but not always) in an LLL-reduced basis for x.

In these two cases, x must have integral small entries: more precisely, we definitely must have d.|x| _oo ² < 2⁵³ but even that may not be enough. The implementation uses low precision floating point computations for maximal speed and gives incorrect results when x has large entries. That condition is checked in the code and the routine raises an error if large rounding errors occur. A more robust, but much slower, implementation is chosen if the following flag is used:

* If flag = 2, x can have non integral real entries, but this is also useful when x has large integral entries. Return [N, M, V] as in case flag = 0, where M is returned as a floating point number. If x is inexact and B is omitted, the "minimal" vectors in V only have approximately the same norm (up to the internal working accuracy). This version is very robust but still offers no hard and fast guarantee about the result: it involves floating point operations performed at a high floating point precision depending on your input, but done without rigorous tracking of roundoff errors (as would be provided by interval arithmetic for instance). No example is known where the input is exact but the function returns a wrong result.

I have hit this problem before, where things get assumed.. as it is NOT IN THE DOCUMENTATION

I try to go by the documentation, but if things are missing, how do I know???

Sorry, but this hit a nerve

Randall

On 3/4/24 14:47, Aurel Page wrote:

Dear Randall,

On 04/03/2024 23:31, American Citizen wrote:

Carefull investigation of the elliptic curve points shows that M seems to be missing some vectors.

[ 0  0 -1 -1 -1 -1 -2 -2]           [ 1 0 2 ]
                           MISSING:
[-1 -2  0 -1  1  2  1  0]           [ 1 2 0 ]

I obtained only 49 points, but there are actually 67 points of height < 13 for curve E. I had to decompose these points as combinations of the basis, to uncover what was missing here.

Questions:

1. should I negate the columns of M and append them to M?  ( I am guessing that the columns need to be unique) It is obvious that the heights stay the same if we negate a column.

2. What about if M > 2 rows here, do the same, negate all columns of n-rows for a basis of n-points?

3. Does qfminin exhaustively find all the vectors? or is just a partial answer given as occurred in this case?

This did take me 2-3 hours to troubleshoot.

Had you read the documentation, you would have known that qfminim returns the solutions up to negation.

Cheers,
Aurel