Quaternion algebra: bugs in maximal_order and normalize_basis_at_p

[giacomoborin]

Steps To Reproduce

1. On any sage terminal run:

a,b = -292, -732
A = QuaternionAlgebra(QQ,a,b)
A.maximal_order()

2. On any sage terminal run:

from sage.algebras.quatalg.quaternion_algebra import normalize_basis_at_p
A.<i,j,k> = QuaternionAlgebra(-1,-7)
e = [A(1), k, j, 1/2 + 1/2*i + 1/2*j + 1/2*k]
e_norm = normalize_basis_at_p(e, 2)
V = QQ**4
V.span([V(x.coefficient_tuple()) for (x,_) in e_norm]).dimension()

Expected Behavior

1. I expect the code to return a maximal order of the quaternion algebra.
2. I expect a basis to be of rank 4

Actual Behavior

1. It fails.
2. Return a list of rank 3

Additional Information

The error can be traced to a supposedly bug for the function normalize_basis_at_p when $p = 2$. In fact in the faulty execution it returns a supposed basis of rank $3$ instead of $4$.

Trying to debug the function I discovered that actually in some situations it return a list of $4$ vectors with the last two being equal, clearly not a basis! This strange behaviour can be noted also in the examples inserted for the function:

sage: A.<i,j,k> = QuaternionAlgebra(-1,-7)
sage: e = [A(1), k, j, 1/2 + 1/2*i + 1/2*j + 1/2*k]
sage: normalize_basis_at_p(e, 2)
[(1, 0), (1/2 + 1/2*i + 1/2*j + 1/2*k, 0), (-34/105*i - 463/735*j + 71/105*k, 1),
         (-34/105*i - 463/735*j + 71/105*k, 1)]

I already tried to solve the issue myself so I insert here some possibly useful notes:

• it is easy to find more errors (just take random $a,b$ until maximal order crashes), but here 20 of them:
  [(-292, -732), (-48, -564), (-436, -768), (-752, -708), (885, 545), (411, -710), (-411, 593), (805, -591), (-921, 353), (409, 96), (394, 873), (353, -722), (730, 830), (-466, -427), (-213, -630), (-511, 608), (493, 880), (105, -709), (-213, 530), (97, 745)],
• the two functions are Algorithms 7.10, 7.9 and 3.12 from https://arxiv.org/abs/1004.0994
• maximal_order to me seem to be implemented correctly and I believe the error is only traceable to normalize_basis_at_p (that in fact contains some differences from the original algorithm)
• trying to remove the previous differences I noted creates several crashes for even more quaternion algebras, so I suppose they where necessaries.

I'll still try to solve the issue, so add here eventual updates.

Environment

- **OS**: MacOS
- **Sage Version**: Version: 9.2

Checklist

• I have searched the existing issues for a bug report that matches the one I want to file, without success.
• I have read the documentation and troubleshoot guide

[RuchitJagodara]

When I am running your second code it is giving me an error like below

sage: from sage.algebras.quatalg.quaternion_algebra import normalize_basis_at_p
....: A.<i,j,k> = QuaternionAlgebra(-1,-7)
....: e = [A(1), k, j, 1/2 + 1/2*i + 1/2*j + 1/2*k]
....: e_norm = normalize_basis_at_p(e, 2)
....: V = QQ**4
....: V.span([V(x.coefficient_tuple()) for (x,_) in basis]).dimension()
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[1], line 6
      4 e_norm = normalize_basis_at_p(e, Integer(2))
      5 V = QQ**Integer(4)
----> 6 V.span([V(x.coefficient_tuple()) for (x,_) in basis]).dimension()

TypeError: 'function' object is not iterable

[giacomoborin]

When I am running your second code it is giving me an error like below

sage: from sage.algebras.quatalg.quaternion_algebra import normalize_basis_at_p
....: A.<i,j,k> = QuaternionAlgebra(-1,-7)
....: e = [A(1), k, j, 1/2 + 1/2*i + 1/2*j + 1/2*k]
....: e_norm = normalize_basis_at_p(e, 2)
....: V = QQ**4
....: V.span([V(x.coefficient_tuple()) for (x,_) in basis]).dimension()
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[1], line 6
      4 e_norm = normalize_basis_at_p(e, Integer(2))
      5 V = QQ**Integer(4)
----> 6 V.span([V(x.coefficient_tuple()) for (x,_) in basis]).dimension()

TypeError: 'function' object is not iterable

Sorry, copied wrong line from another test. Should be e_norm instead of basis. I corrected it in the initial comment. Thanks for noting it!

[RuchitJagodara]

normalize_basis_at_p (that in fact contains some differences from the original algorithm)

I made a PR and then I realized that it was failing for some cases. So I think, I did something wrong, but to confirm that first I have to confirm that the algo which I am understanding is correct, only. So can you please provide me a link to that algorithm ?

[giacomoborin]

Sure! The basis is evaluated via Algorithms 3.12 from https://arxiv.org/abs/1004.0994, is the only reference I know.