make BinaryQF.solve_integer() work for square discriminants

[yyyyx4]

As reported in #32782 comment:8, PARI's qfbsolve() does not work with quadratic forms whose discriminant is a square integer.

This currently triggers failures in random testing, but it is not a regression: BinaryQF.solve_integer() used to reject all positive discriminants prior to #32782.

Depends on #33057

CC: @collares @slel @DaveWitteMorris

Component: quadratic forms

Author: Lorenz Panny

Branch/Commit: 5e8a2a3

Reviewer: Vincent Delecroix

Issue created by migration from https://trac.sagemath.org/ticket/33026

[yyyyx4]

Branch: public/33026

[yyyyx4]

Author: Lorenz Panny

[yyyyx4]

Commit: ee4a650

[yyyyx4]

comment:1

Also fixed: The doctest was checking whether Q(*xy) == 0 rather than Q(*xy) == n.

[sagetrac-git]

Changed commit from ee4a650 to 62a73ec

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

ad491f6	trac 33057 fix doctest
62a73ec	make BinaryQF.solve_integer() work for square discriminants

[yyyyx4]

Dependencies: #33057

[yyyyx4]

comment:3

Rebased onto #33057.

[videlec]

Reviewer: Vincent Delecroix

[videlec]

comment:5

Instead of

+                try:
+                    y = ZZ((n//x - Q._a*x) / Q._b)
+                except TypeError:
+                    continue
+                return tuple(row[0]*x + row[1]*y for row in M.rows())

you would better do

y_num = n // x - Q._a * x
if Q._b.divides(y_num):
    y = y_num // Q._b
    return tuple(row[0]*x + row[1]*y for row in M.rows())

[sagetrac-git]

Changed commit from 62a73ec to 824056f

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

36afbd8	Merge branch 'develop' into public/33026
824056f	use .divides and // instead of try-except and / and ZZ

[yyyyx4]

comment:7

Thanks, done.

[videlec]

comment:8

It is better to avoid the use multiple statements on the same line as

U.rescale_row(0, choice((+1,-1))); assert U.det() in (+1,-1)

See PEP8. (I don't understand why this is not checked by the patchbot.)

Since you have a special treatment for n=0, it would be reasonable to have a dedicated doctest.
Maybe, you could change

sage: n = randrange(-10^3, 10^3)
sage: Q = BinaryQF([n, randrange(-10^3, 10^3), 0][::(-1)**randrange(2)])
sage: U = random_matrix(ZZ, 2, 2, 'unimodular')
sage: U.rescale_row(0, choice((+1,-1))); assert U.det() in (+1,-1)
sage: Q = Q.matrix_action_right(U)
sage: Q.discriminant().is_square()
True
sage: xy = Q.solve_integer(n)
sage: Q(*xy) == n
True

to

sage: Q = BinaryQF([n, randrange(-10^3, 10^3), 0][::(-1)**randrange(2)])
sage: U = random_matrix(ZZ, 2, 2, 'unimodular')
sage: U.rescale_row(0, choice((+1,-1))); assert U.det() in (+1,-1)
sage: Q = Q.matrix_action_right(U)
sage: Q.discriminant().is_square()
True
sage: xy = Q.solve_integer(0)
sage: Q(*xy) == 0
True
sage: n = randrange(-10^3, 10^3)
sage: xy = Q.solve_integer(n)
sage: Q(*xy) == n
True

And I think this will be all my comments for this ticket.

[sagetrac-git]

Changed commit from 824056f to 5e8a2a3

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

5e8a2a3

add doctest; style tweak

[yyyyx4]

comment:10

Thank you! Done.

[vbraun]

Changed branch from public/33026 to 5e8a2a3