Rings/Euclidean rings need better documentation

[ulthiel]

It took me several days to succeed with my trivial project of implementing a ring; I've taken the Gaussian integers as an example. Maybe we can link this somewhere so that others can be a bit quicker with their projects.

I noticed a few things:

1. The documentation of "canonical_unit" is not very clear. I think what we do/want is fixing a system P of representatives of non-associates in R, i.e. a system of representatives of ~ where f ~ g iff f=gu for some u. Then for given f, canonical_unit(f) should return u such that fu^-1 \in P (I think the u^-1 should match your conventions). For a field, you will take P={0,1}, and canonical_unit(f)=f for non-zero f. You should mention that you use this for example to get leading entries in P in the Hermite normal form.

2. There needs to be some explanation of uniqueness/non-uniqueness of the Hermite normal form etc. and how you can control this using the Euclidean ring interface. I think the whole (and only!) control comes from the implementation of divrem. This basically fixes functions r,q:R \times R \setminus { 0 } \to R such that x=q(x,y)*y + r(x,y) for all x,y with y non-zero. Now, in some cases this choice produces a canonical system of representatives of residues mod r \in R. Namely, if r(x,y) = r(x+wy, y) for all y \in R (I believe). This holds for example for the Z, K[X], Z[i] if I'm not mistaken. If this is not true, you may produce non-unique HNFs and have to do something additionally to make them unique.

3. In the documentation of "gcdx" I currently don't understand what is meant by "with s reduced modulo g and t reduced modulo f."

[wbhart]

1. Thanks. We'll look into making it clearer.

2. We haven't yet decided how to handle non-unique representatives. Almost certainly the HNF code just fails in some such cases. But agreed, we need to sort this out.

3. Reduced with respect to the Euclidean function. I don't think we guarantee that it is the choice made by divrem, just some choice. For ZZ we might be able to say more.

[fieker]

I'd love to fully implement the above suggestion, but in general don't know how... Mathematically, I'd love to just say we fix a system of reps modulo units and use canonical unit to obtain it. For Z, Z/nZ, k[t] (and some others): no problem. There is a canonical, computable set of reps and this will be used.
However, for Z_K/A (maximal order of a number field modulo some non-trivial ideal) I do not know how to get a canonical system of reps, so we cannot promise this in general.

HNF: mathematically: if the ring is a domain, you fix a set of reps modulo units and for each such rep x a system of representatives of R/x, then the HNF is unique. Again, for many rings (see above) this is done and the HNF is unique.
For others, HNF will return a HNF but make no further promises.

If there are zero divisors, not even the number of non-zero rows in an HNF is unique, you'd need to take annihilators into account and move to the Howell form. Here uniqueness would follow as in the HNF case. For some rings that is achieved, for others not.

gcdx no real idea apart from what Bill said: one co-factor is divremed (thus "small") and the other adjusted (thus automaticall small(ish)). However, remember that divrem is in general not unique either. In fact, for Z_K/A as above, the "best" algorithm for divrem is take a random element as residue (untill it is small enough) and compute the quotient afterwards.

for 0 I'd favour 1 as well...(apart from as was said before

• iszero can be expensive
• isunit can be expensive
• inv may not be available at all (although most rings do support inv for units)
• inv of a unit might have a catastrophic size (try px+1 in Z/p^k)
• divrem migh be more widely supported, while *inv might be faster