Opened 2 years ago

Closed 9 months ago

#30078 closed defect (fixed)

Check for duplicate hyperplanes in arrangements over any base ring

Reported by: Julian Ritter Owned by:
Priority: major Milestone: sage-9.6
Component: geometry Keywords: HyperplaneArrangements
Cc: Jean-Philippe Labbé Merged in:
Authors: Julian Ritter Reviewers: Matthias Koeppe
Report Upstream: N/A Work issues:
Branch: b7f7a7f (Commits, GitHub, GitLab) Commit: b7f7a7f44f71ff49e0551b76db5d01d44d500d2d
Dependencies: Stopgaps:

Status badges

Description

A hyperplane arrangement is supposed to be checked for duplicate hyperplanes. This works well in QQ:

sage: H1.<x,y> = HyperplaneArrangements(base_ring=QQ)
sage: A = H1([1,1,0],[2,2,0], warn_duplicates=True)
/usr/local/sagemath/dev/local/lib/python3.7/site-packages/sage/geometry/hyperplane_arrangement/arrangement.py:3352: UserWarning: Input contained 2 hyperplanes, but only 1 are distinct.
  warn('Input contained {0} hyperplanes, but only {1} are distinct.'.format(n, len(hyperplanes)))
sage: A
Arrangement <x + 1>

sage: A.n_regions()
2

In other base rings, this check can fail, resulting in false statements about the arrangement:

sage: R = QQ[sqrt(2)]
sage: H2.<x,y> = HyperplaneArrangements(base_ring=R)
sage: B = H2([1,1,0],[2,2,0], warn_duplicates=True)
sage: B
Arrangement <x + 1 | 2*x + 2>

sage: B.n_regions()
3

Change History (29)

comment:1 Changed 2 years ago by Julian Ritter

Status: newneeds_info

The error can be tracked down to the primitive method for hyperplanes: It is supposed to rescale linear multiples of hyperplane directions to a canonical "primitive" one. This is currently not properly implied for every base_ring, as it uses gcd and lcm which for some base rings are just one regardless of the arguments.

Furthermore, the method currently uses x.denom() and x.numer() instead of x.denominator() and x.numerator(), two aliases which are only defined for QQ.

One solution would be to normalize the hyperplane equations instead of working with gcd and lcm. But this gives "ugly" equations, contrary to what the primitive method is meant to provide.

comment:2 Changed 2 years ago by Julian Ritter

Branch: u/nailuj/check_for_duplicate_hyperplanes_in_arrangements_over_any_base_ring

comment:3 Changed 2 years ago by Matthias Köppe

Cc: Jean-Philippe Labbé added
Commit: 49db0e34eb135c0ecef7b3b09ee2760ae099d8da

New commits:

49db0e3Replace aliases by full method names

comment:4 Changed 2 years ago by Matthias Köppe

Milestone: sage-9.2sage-9.3

comment:5 Changed 21 months ago by Matthias Köppe

Milestone: sage-9.3sage-9.4

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.

comment:6 Changed 17 months ago by Matthias Köppe

Milestone: sage-9.4sage-9.5

Setting a new milestone for this ticket based on a cursory review.

comment:7 Changed 12 months ago by Matthias Köppe

Milestone: sage-9.5sage-9.6

Stalled in needs_review or needs_info; likely won't make it into Sage 9.5.

comment:8 Changed 9 months ago by git

Commit: 49db0e34eb135c0ecef7b3b09ee2760ae099d8da216f6df74100fc78ebf05fd84696d927eb14114d

Branch pushed to git repo; I updated commit sha1. New commits:

216f6dfChange behavior of primitive() for rings other than QQ

comment:9 Changed 9 months ago by Julian Ritter

Authors: Julian Ritter
Status: needs_infoneeds_review

I kept the existing procedure of primitive() for QQ (using numerator, denominator, gcd and lcm) and introduced a new one for other base rings: The linear expression is scaled such that the first nonzero entry of the normal vector is one or negative one (as before, depending on the original sign and whether the option signed is set).

This seems to be compatible with all examples provided in the classes concerned, pass all the existing doctests in the hyperplane_arrangements folder and solve the problem of this ticket. It should also solve ticket #30749. I included suitable tests in the code.

Note however that this does change the coefficients by which hyperplanes are stored in an arrangement not based on QQ. This could break user code whenever it relies on a specific scaling of the linear expression. I would argue that fixing the mathematically incorrect statements yielded by the current implementation outweighs this inconvenience.

comment:10 Changed 9 months ago by Matthias Köppe

+        from sage.rings.all import QQ

Please use a more specific import, see https://doc.sagemath.org/html/en/developer/packaging_sage_library.html#module-level-runtime-dependencies

comment:11 Changed 9 months ago by Matthias Köppe

Likewise here:

+            from sage.arith.all import lcm, gcd

comment:12 Changed 9 months ago by Matthias Köppe

Also, it would be good if you could rewrite these doctests so that they do not go through SR.

+        Check that :trac:`30078` is fixed::
+
+            sage: R = QQ[sqrt(2)]

comment:13 Changed 9 months ago by Matthias Köppe

(This is for modularization purposes, see #32432)

comment:14 Changed 9 months ago by Matthias Köppe

Also the list brackets can be omitted here:

+            d = lcm([x.denominator() for x in coeffs])
+            n = gcd([x.numerator() for x in coeffs])

comment:15 Changed 9 months ago by Matthias Köppe

Also ./sage -tox -e pycodestyle src/sage/geometry/hyperplane_arrangement/hyperplane.py complains about style, some of the warnings are on the code changed in the ticket

comment:16 Changed 9 months ago by Matthias Köppe

Status: needs_reviewneeds_work

comment:17 Changed 9 months ago by git

Commit: 216f6df74100fc78ebf05fd84696d927eb14114d63a2b4ea5e8ceeb49f3f7ae41a21931545124ed8

Branch pushed to git repo; I updated commit sha1. New commits:

cecc4b5More specific imports
1778600Simplified doctests
63a2b4epycodestyle cleanup

comment:18 Changed 9 months ago by git

Commit: 63a2b4ea5e8ceeb49f3f7ae41a21931545124ed8bec2e96b3547e44518149073b94a1284610355ac

Branch pushed to git repo; I updated commit sha1. New commits:

bec2e96Limit pycodestyle cleanup to the method modified in this ticket

comment:19 in reply to:  12 Changed 9 months ago by Julian Ritter

Status: needs_workneeds_review

Thanks for the helpful suggestions!

Replying to mkoeppe:

Also, it would be good if you could rewrite these doctests so that they do not go through SR.

+        Check that :trac:`30078` is fixed::
+
+            sage: R = QQ[sqrt(2)]

I am not really sure about what goes through SR and what doesn’t. For the tests to be meaningful, the base ring would have to contain some non-rationals. I replaced QQ[sqrt(2)] by AA. Is that fine?

comment:20 Changed 9 months ago by Matthias Köppe

sage: ((1+sqrt(5))/2).parent()
Symbolic Ring
sage: ((1+AA(5).sqrt())/2).parent()
Algebraic Real Field

comment:21 Changed 9 months ago by Matthias Köppe

and instead of QQ[sqrt(2)] you can write

sage: QuadraticField(2)
Number Field in a with defining polynomial x^2 - 2 with a = 1.414213562373095?

comment:22 Changed 9 months ago by git

Commit: bec2e96b3547e44518149073b94a1284610355acc1f4173bf8dcfdd7e1b9bb899f58f38ef8e54db1

Branch pushed to git repo; I updated commit sha1. New commits:

c1f4173Avoid computations using Symbolic Ring in doctests

comment:23 in reply to:  21 Changed 9 months ago by Julian Ritter

Replying to mkoeppe:

and instead of QQ[sqrt(2)] you can write

sage: QuadraticField(2)
Number Field in a with defining polynomial x^2 - 2 with a = 1.414213562373095?

Thanks, I didn’t know that!

comment:24 Changed 9 months ago by Matthias Köppe

+            sage: R = QuadraticField(2)
+            sage: H.<x,y> = HyperplaneArrangements(base_ring=R)
+            sage: B = H([1,1,0], [2,2,0], [sqrt(2),sqrt(2),0])

Make that R.<sqrt2> = QuadraticField(2) and use sqrt2 instead of sqrt(2)

comment:25 Changed 9 months ago by git

Commit: c1f4173bf8dcfdd7e1b9bb899f58f38ef8e54db1b7f7a7f44f71ff49e0551b76db5d01d44d500d2d

Branch pushed to git repo; I updated commit sha1. New commits:

b7f7a7fCorrect variable name in quadratic field

comment:26 in reply to:  24 Changed 9 months ago by Julian Ritter

Replying to mkoeppe:

+            sage: R = QuadraticField(2)
+            sage: H.<x,y> = HyperplaneArrangements(base_ring=R)
+            sage: B = H([1,1,0], [2,2,0], [sqrt(2),sqrt(2),0])

Make that R.<sqrt2> = QuadraticField(2) and use sqrt2 instead of sqrt(2)

Oh, I see. When sqrt(2) is used, it will initially be a symbolic expression and turned into an element of R later, which can be avoided by explicitly using the element of the quadratic field, correct?

comment:27 Changed 9 months ago by Matthias Köppe

That's right.

comment:28 Changed 9 months ago by Matthias Köppe

Reviewers: Matthias Koeppe
Status: needs_reviewpositive_review

comment:29 Changed 9 months ago by Volker Braun

Branch: u/nailuj/check_for_duplicate_hyperplanes_in_arrangements_over_any_base_ringb7f7a7f44f71ff49e0551b76db5d01d44d500d2d
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.