@DaveWitteMorris. One thing I'm worried about is the multiplication of the additional_vectors by artificial_length. Since we are no longer using the identity matrix I'm wondering if we are multiplying by the correct amount. Also when I run my code on the examples you have in the issue with the inequalities I don't seem to be getting the correct amount. I'm definitely getting less inequalities but I'm not sure what's happening. If I try your last example but with v = vector(ZZ, [1,-1]) instead and then do C.plot() I do get a slab however.

Also this pull request doesn't depend on the pull request with the updated orthogonal complement stuff. I wanted to keep them separate just in case that other PR doesn't make it through. However complement will need to be updated to orthogonal_complement if it does to avoid the warning.

Documentation preview for this PR (built with commit 1a7901c; changes) is ready! 🎉
This preview will update shortly after each push to this PR.

I think you can solve the problems by rearranging the code to work as follows:

1. Apply LLL to basis. (This is not necessary, but should improve efficiency.)
2. Calculate a radius from this new basis, by using the QR decomposition as described in this comment.
3. Choose additional_vectors (integer vectors that span the orthogonal complement).
4. Apply LLL to additional_vectors, so you can estimate the length of the shortest lattice vector in the orthogonal complement.
5. Multiply additional_vectors by an integer factor so large that the square of the length of the shortest vector is guaranteed to be (slightly) greater than radius.
6. Combine (the new) basis with (the new) additional_vectors to get a basis of the whole space.
7. Continue as in the code that is there, but replace the calculation of radius with radius = radius/4 (because you have already calculated a radius, and just need to rescale it because of the line basis = basis/2). Actually, for clarity, this rescaling of radius should happen right after basis = basis/2, instead of being after the definition of Q.

The diamond_cut method will only add inequalities for vectors that are in the span of basis (because all other vectors have a length whose square is larger than radius), so the "if artificial_length is not None" code block should give correct results.

Edit: Correction - Do not calculate a radius unless radius is None.

@DaveWitteMorris. I've implement your changes. It works correctly for the following example:

from sage.modules.free_module_integer import IntegerLattice
sage: v = vector(ZZ, [1,1,1,-1])
sage: L = IntegerLattice([v])
sage: C = L.voronoi_cell()
sage: C.Hrepresentation()

However for the following example it produces an error:

from sage.modules.free_module_integer import IntegerLattice
sage: v = vector(ZZ, [1,1,-1])
sage: L = IntegerLattice([v])
sage: C = L.voronoi_cell()

It seems to be failing on the final cut of the diamond cutting algorithm. I'm not sure what is causing this error? If you have any idea let me know.

The error comes from a bug in the original code that arises when diamond_cut doesn't do any cuts (i.e., when inequalities is the empty list). For example, we have the following error in the develop branch:

sage: from sage.modules.free_module_integer import IntegerLattice
sage: v = vector(ZZ, [1,1,-1])
sage: L = IntegerLattice([v])
sage: C = L.voronoi_cell(radius=0.1)
     ...
TypeError: no common canonical parent for objects with parents: 
'Polyhedra in QQ^3' and 'Polyhedra in ZZ^0'

So this should fix it:

-    cut = Polyhedron(ieqs=inequalities)
-    V = V.intersection(cut)
+    if inequalities:
+        cut = Polyhedron(ieqs=inequalities)
+        V = V.intersection(cut)

Please add a doctest to show that this bug has been fixed.

@DaveWitteMorris. I have made the fraction_field changes. I have some questions regarding these changes. 1. do we still convert our matrices back to integers? I think we should get rid of it but you seem to have removed the comment telling me to change that. 2. We are still dividing the basis by 2 which I don't think works if we have an arbitrary group that can be turned into a fractional field so it still might not work. Even if we convert the additional_vectors to integers we would need to convert the original basis to integers to get this to work.

line 130:

- and radius ``C``.
+ and squared radius ``C``.

line 260:

    - ``radius`` -- radius of basis vectors to consider
    - ``radius`` -- square of radius of basis vectors to consider

Delete lines 284 and 285. (They are duplicates of 278 and 279.)

line 306:

- sage: C = IntegerLattice(M).voronoi_cell(radius=35)
+ sage: C = IntegerLattice(M).voronoi_cell()

I am worried that the radius computed by sagemath may be so large that this example is too slow, but let's see.

I did not intend to delete my comment about not converting to integers. Please delete all of lines 334-339, except line 337.

The formula for artificial_length in line 357 is not correct. The length will be squared, so there should be a square root in this formula. This should work:

artificial_length = ceil(2.001 * sqrt(radius / shortest_vector_lower_bound))

I don't think I understand this question:

2. We are still dividing the basis by 2 which I don't think works if we have an 
arbitrary group that can be turned into a fractional field so it still might not 
work. Even if we convert the additional_vectors to integers we would need 
to convert the original basis to integers to get this to work.

The scalars can be expected to be a subring of the reals (probably integers or rational numbers). I think dividing by 2 is handled correctly.

@DaveWitteMorris I've made the changes you suggested. Also for my question it makes sense to be now that you can use real numbers for matrices and modules of different groups. I was worried that they did not have this functionality.

All tests passed locally, so I do not think the CI doctest failure was caused by this ticket.

I will set to positive review on Wednesday if there are no other comments.

However, please correct the minor mistake in the title of this web page: change "it's" to "its" (no apostrophe).

No, I cannot set to positive review yet, because the example from #34091 gives an error: ValueError: math domain error. This will have to be fixed.

Here is the example:

from sage.modules.free_module_integer import IntegerLattice
L = IntegerLattice( [ (2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
 (0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
 (0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
 (0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
 (0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
 (0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
 (0, -1, 0, 1, -1, -1, 0, 1, 0, 1, 0, 0, 0, 0, 1, -1),
 (0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0),
 (1, -1, -1, 0, 0, -1, 0, 1, 0, 0, -1, 1, 0, 0, 0, -1),
 (1, -1, -1, 0, 0, -1, 0, 1, 0, 0, 1, -1, 0, 0, 0, -1),
 (-1, 1, 1, 0, 0, 1, 0, -1, 0, 0, 1, 1, 0, 0, 0, 1),
 (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0),
 (0, 1, -1, 0, 1, 0, 0, -1, -1, 0, 0, 1, 0, 1, -1, 0),
 (0, 1, -1, 0, 1, 0, 0, -1, 1, 0, 0, 1, 0, 1, -1, 0),
 (-1, 0, 1, 0, -1, 0, 1, 1, 0, 0, -1, 0, 1, -1, 0, 0),
 (1, 0, -1, 0, 1, 0, 1, -1, 0, 0, 1, 0, -1, 1, 0, 0)
 ] )
L.closest_vector( (1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0) )

Thanks for fixing these issues, which were bad bugs. I'll set to positive review if make ptestlong does not have errors.

However, as I said earlier, please change the typo in the title of this web page. It should be "its", not "it's" (i.e., the apostrophe should be deleted).