binary_qf tests fail for a particular random seed

[dimpase]

Is there an existing issue for this?

• [X] I have searched the existing issues for a bug report that matches the one I want to file, without success.

Did you read the documentation and troubleshoot guide?

• [X] I have read the documentation and troubleshoot guide

Environment

- **Fedora, Ubuntu**:
- **10.0.beta4**:

Steps To Reproduce

See below (Additional info) for an easy reproducer at Sage prompt:

build 10.0.beta4 and run

./sage -tp --random-seed=11559027636060728728796865698718805166 src/sage/quadratic_forms/binary_qf.py

on #35290 (where I was lucky to get this random seed), and also reproducible on Fedora box, an error as below. OK with several other seeds.

Expected Behavior

no error

Actual Behavior

Doctesting 1 file using 8 threads.
sage -t --random-seed=11559027636060728728796865698718805166 src/sage/quadratic_forms/binary_qf.py
**********************************************************************
File "src/sage/quadratic_forms/binary_qf.py", line 1597, in sage.quadratic_forms.binary_qf.BinaryQF.solve_integer
Failed example:
    xy = Q.solve_integer(n)
Exception raised:
    Traceback (most recent call last):
      File "/home/scratch/scratch2/dimpase/sage/sage/src/sage/doctest/forker.py", line 695, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/home/scratch/scratch2/dimpase/sage/sage/src/sage/doctest/forker.py", line 1093, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.quadratic_forms.binary_qf.BinaryQF.solve_integer[18]>", line 1, in <module>
        xy = Q.solve_integer(n)
      File "/home/scratch/scratch2/dimpase/sage/sage/src/sage/quadratic_forms/binary_qf.py", line 1634, in solve_integer
        y = y_num // Q._b
      File "sage/structure/element.pyx", line 1838, in sage.structure.element.Element.__floordiv__
        return (<Element>left)._floordiv_(right)
      File "sage/rings/integer.pyx", line 2091, in sage.rings.integer.Integer._floordiv_
        raise ZeroDivisionError("Integer division by zero")
    ZeroDivisionError: Integer division by zero
**********************************************************************
File "src/sage/quadratic_forms/binary_qf.py", line 1598, in sage.quadratic_forms.binary_qf.BinaryQF.solve_integer
Failed example:
    Q(*xy) == n
Exception raised:
    Traceback (most recent call last):
      File "/home/scratch/scratch2/dimpase/sage/sage/src/sage/doctest/forker.py", line 695, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/home/scratch/scratch2/dimpase/sage/sage/src/sage/doctest/forker.py", line 1093, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.quadratic_forms.binary_qf.BinaryQF.solve_integer[19]>", line 1, in <module>
        Q(*xy) == n
    TypeError: 207872*x^2 - 2156672*x*y + 5593868*y^2 argument after * must be an iterable, not NoneType
**********************************************************************
1 item had failures:
   2 of  23 in sage.quadratic_forms.binary_qf.BinaryQF.solve_integer
    [313 tests, 2 failures, 0.21 s]
----------------------------------------------------------------------
sage -t --random-seed=11559027636060728728796865698718805166 src/sage/quadratic_forms/binary_qf.py  # 2 doctests failed
----------------------------------------------------------------------

Additional Information

here is the reproducer without random stuff - obtained by printing values in the test for the random seed in question:

sage: RR.<x,y>=ZZ[]
sage: Q=BinaryQF(207872*x^2 - 2156672*x*y + 5593868*y^2)
sage: Q.solve_integer(812)
---------------------------------------------------------------------------
ZeroDivisionError                         Traceback (most recent call last)
Cell In [10], line 1
----> 1 Q.solve_integer(Integer(812))

File /home/scratch/scratch2/dimpase/sage/sage/src/sage/quadratic_forms/binary_qf.py:1638, in BinaryQF.solve_integer(self, n)
   1636     y_num = n // x - Q._a * x
   1637     if Q._b.divides(y_num):
-> 1638         y = y_num // Q._b
   1639         return tuple(row[0]*x + row[1]*y for row in M.rows())
   1641 return None

File /home/scratch/scratch2/dimpase/sage/sage/src/sage/structure/element.pyx:1838, in sage.structure.element.Element.__floordiv__()
   1836 cdef int cl = classify_elements(left, right)
   1837 if HAVE_SAME_PARENT(cl):
-> 1838     return (<Element>left)._floordiv_(right)
   1839 if BOTH_ARE_ELEMENT(cl):
   1840     return coercion_model.bin_op(left, right, floordiv)

File /home/scratch/scratch2/dimpase/sage/sage/src/sage/rings/integer.pyx:2091, in sage.rings.integer.Integer._floordiv_()
   2089 """
   2090 if not mpz_sgn((<Integer>right).value):
-> 2091     raise ZeroDivisionError("Integer division by zero")
   2092 
   2093 cdef Integer z = <Integer>PY_NEW(Integer)

ZeroDivisionError: Integer division by zero

[dimpase]

@yyyyx4 - the errors are in a function you've written, according to git blame

[dimpase]

@JohnCremona - maybe you know what's going on here?

[dimpase]

here is what's going on: (complete error dump in the issue description):

sage: RR.<x,y>=ZZ[]
sage: Q=BinaryQF(207872*x^2 - 2156672*x*y + 5593868*y^2)
sage: Q.solve_integer(812)
---------------------------------------------------------------------------
ZeroDivisionError                         Traceback (most recent call last)
...

[JohnCremona]

The form has zero discriminant -- it is a multiple of (16x - 83y)^2. In the code for solve_integer() it explicitly states that reducible forms are not supported.

Looking at the code, it makes a change of variables so that the form becomes ax^2+bx*y, but then assumes that b is nonzero which it is not. So the method solve_integer() needs to catch this case. Instead of dividing y_num by Q._b when Q._b is 0, it should test whether y_num is 0 (and skip this x if not). Otherwise there are infinitely many solutions (e.g. think of solving x^2=1 for (x,y)) and it seems to meet the documentation to return just one.

I volunteer to make a patch for this.

[yyyyx4]

@JohnCremona Sorry, I already fixed this in #35262! (GitHub shows a cross-reference above your comment for this reason, but indeed it's not easy to spot...)

[JohnCremona]

That's great, and your solution looks better than what I was thinking of doing anyway

[GMS103]

This is on SageMath 10.0.beta8. I am getting a similar error with a different seed:

% ./sage -t --long --warn-long 26.5 --random-seed=164104516405977008420373837524113607070 src/sage/quadratic_forms/binary_qf.py
Running doctests with ID 2023-04-08-16-49-52-0cdd6b93.
Git branch: develop
Git ref: 10.0.beta8
Running with SAGE_LOCAL='[…]/sage/local' and SAGE_VENV='[…]/sage/local/var/lib/sage/venv-python3.11'
Using --optional=homebrew,pip,sage,sage_spkg
Features to be detected: 4ti2,benzene,bliss,buckygen,conway_polynomials,csdp,cvxopt,cvxopt,database_cremona_ellcurve,database_cremona_mini_ellcurve,database_cubic_hecke,database_jones_numfield,database_knotinfo,dvipng,fpylll,gfan,graphviz,imagemagick,ipython,jupymake,kenzo,latte_int,lrcalc_python,lrslib,mcqd,meataxe,mpmath,msolve,nauty,networkx,numpy,palp,pandoc,pdf2svg,pdftocairo,pexpect,phitigra,pillow,plantri,polytopes_db,polytopes_db_4d,pplpy,primecountpy,ptyprocess,pynormaliz,python_igraph,requests,rubiks,sage.combinat,sage.geometry.polyhedron,sage.graphs,sage.groups,sage.libs.gap,sage.libs.pari,sage.libs.singular,sage.misc.cython,sage.modules,sage.plot,sage.rings.finite_rings,sage.rings.function_field,sage.rings.number_field,sage.rings.padics,sage.rings.real_double,sage.rings.real_mpfr,sage.symbolic,sage_numerical_backends_coin,sagemath_doc_html,scipy,singular,sphinx,sympy,tdlib
Doctesting 1 file.
sage -t --long --warn-long 26.5 --random-seed=164104516405977008420373837524113607070 src/sage/quadratic_forms/binary_qf.py
**********************************************************************
File "src/sage/quadratic_forms/binary_qf.py", line 1620, in sage.quadratic_forms.binary_qf.BinaryQF.solve_integer
Failed example:
    (xy1 is None) == (xy2 is None)
Expected:
    True
Got:
    False
**********************************************************************
1 item had failures:
   1 of  35 in sage.quadratic_forms.binary_qf.BinaryQF.solve_integer
    [325 tests, 1 failure, 0.13 s]
----------------------------------------------------------------------
sage -t --long --warn-long 26.5 --random-seed=164104516405977008420373837524113607070 src/sage/quadratic_forms/binary_qf.py  # 1 doctest failed
----------------------------------------------------------------------
Total time for all tests: 0.2 seconds
    cpu time: 0.1 seconds
    cumulative wall time: 0.1 seconds
Features detected for doctesting: 
% 

[yyyyx4]

Thanks for the report. This appears to be a PARI bug:

? qfbcornacchia(1, 1223277844)
[]

[GMS103]

Thanks. Are you telling them, or should I try?

Thanks for the report. This appears to be a PARI bug:

? qfbcornacchia(1, 1223277844)
[]

[yyyyx4]

I just submitted it to the PARI bug tracker. (It's #2471.)

[GMS103]

Thanks, Lorenz. But I do not understand Bill's answer.

When D is not 3 mod 4, Cornacchia algorithm only works (reliably) for prime n.

[dimpase]

https://en.m.wikipedia.org/wiki/Cornacchia's_algorithm

does not seem to require the condition Bill mentions, so all this is very misleading.

[dimpase]

Either it is a bug in Wikipedia article, or in Pari...

[KBelabas]

It's a documentation bug in Pari. I have fixed the doc in 'master'. The only point of allowing 4*p is to handle x^2 + xy + (1 + D)/4 y^2 = p when D = 3 (mod 4) by a change of variable. For the general case, one should use qfbsolve (a bit slower because the general case is more complicated), or make a change of variable to try both n = 1223277844 and n / 4 (non primitive solution).

The special case handled in PARI only looks for a primitive solution (but may find a non-primitive one).