A normalized quadratic form for quaternion algebras.

[29690f48-ed1c-4fee-9608-169da73154e9]

This algorithm follows John Voight's Algorithm 3.12 in Identifying the Matrix Ring.

CC: @adeines

Component: algebra

Keywords: Normalized Quadratic Form

Author: Sarah Chisholm

Reviewer: tkluck

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

[29690f48-ed1c-4fee-9608-169da73154e9]

Attachment: normalized_quadratic_form.patch.gz

[tkluck]

Reviewer: tkluck

[tkluck]

comment:2

Thanks for contributing! I've had a look at your code. It looks like a good implementation of the algorithm in the article. I don't know much about quadratic forms, so I can't really say much about the math.

My most important review point is that your doctests don't cover all your code paths. The examples you give already have a diagonal inner product matrix, so all but the first step are not being tested.

In fact, the other code paths contain 1/2 in R which I'm not sure will work as you seem to expect. I think it will just throw a ZeroDivisionError if 2 is not a unit. You could replace it by R(2).is_unit().

I'll set this ticket's status to needs_work.

Here's a few additional suggestions to make your code more concise by using a few Python gimmicks:

• Instead of

E = self.basis()
f = []
for i in range(len(E)):
    f.append(E[i])

for copying a list, you can write

f = self.basis()[:]

• You could implement a function T(x,y) because you use that expression a lot. It makes the code a lot more readable.

• Usually, you shouldn't need to have loops like

for i in xrange(len(f)):
    # do something with f[i]

because you can write

for f_i in f:
    # do something with f_i

• One hard part is the sorting prescribed by

  Otherwise, let (i, j) with 1 ≤ i ≤ j ≤ n be such that ord T(e_i, e_j) is minimal, taking i = j if possible and if not taking i minimal.

  I've found a way to implement that using the builtin sort. Namely, this is equivalent to sorting the tuples (valuation, int(i != j), i) lexicographically.

I've attached a patch including these comments.

[29690f48-ed1c-4fee-9608-169da73154e9]

Attachment: trac_13654_suggested_code_cleanup.patch.gz

Attachment: normalized_quadratic_form_v2.patch.gz

[29690f48-ed1c-4fee-9608-169da73154e9]

comment:3

Thanks so much for sharing your savvy techniques!

[tkluck]

comment:4

No problem! :-)

Have you also given some thought about extra doctests to make sure the rest of the code works well? Once you've updated that, you can set the status back to needs_review.