Opened 2 years ago

Closed 6 months ago

#30749 closed defect (fixed)

Characteristic polynomial of central Hyperplane arrangement returns wrong result?

Reported by: Jean-Philippe Labbé Owned by:
Priority: major Milestone: sage-9.6
Component: geometry Keywords: hyperplane arrangements, regions
Cc: gh-kliem, Laith Rastanawi, Julian Ritter Merged in:
Authors: Jonathan Kliem Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: d74929d (Commits, GitHub, GitLab) Commit: d74929dfb74820f79d574189a6bc5803dc00dd8d
Dependencies: Stopgaps:

Status badges

Description (last modified by gh-kliem)

A central hyperplane arrangement must have an even number of regions by central symmetry... yet the one below gets 31 regions(!).

R.<y> = QQ[]
v1 = AA.polynomial_root(AA.common_polynomial(y^2 - 3), RIF(RR(1.7320508075688772), RR(1.7320508075688774)))
v2 = QQbar.polynomial_root(AA.common_polynomial(y^4 - y^2 + 1), CIF(RIF(RR(0.8660254037844386), RR(0.86602540378443871)), RIF(-RR(0.50000000000000011), -RR(0.49999999999999994))))
my_vectors = (vector(AA, [-v1, -1, 1]), vector(AA, [0, 2, 1]), vector(AA,[v1, -1, 1]), vector(AA, [1, 0, 0]), vector(AA, [1/2, AA(-1/2*v2^3 + v2),0]), vector(AA, [-1/2, AA(-1/2*v2^3 + v2), 0]))


sage: H = HyperplaneArrangements(AA,names='xyz')
sage: x,y,z = H.gens()
sage: A = H(backend="normaliz")
sage: for v in my_vectors:
....:     a,b,c = v
....:     A = A.add_hyperplane(a*x + b*y + c*z)
sage: A
Arrangement of 6 hyperplanes of dimension 3 and rank 3
sage: A.n_regions()
31
sage: A.is_central()
True

Here is another failure in characteristic polynomial:

sage: tau = AA((1+sqrt(5))/2)                                                                                                                                                                                      
sage: ncn = [[2*tau+1,2*tau,tau],[2*tau+2,2*tau+1,tau+1],[1,1,1],[tau+1,tau+1,tau],[2*tau,2*tau,tau],[tau+1,tau+1,1],[1,1,0],[0,1,0],[1,0,0],[tau+1,tau,tau]]                                                      
sage: H = HyperplaneArrangements(AA,names='xyz')                                                                                                                                                                   
sage: x,y,z = H.gens()                                                                                                                                                                                             
sage: A = H()                                                                                                                                                                                                      
sage: for v in ncn: 
....:     a,b,c = v 
....:     A = A.add_hyperplane(a*x + b*y + c*z) 
....:                                                                                                                                                                                                              
sage: A.n_regions()
Traceback (most recent call last):
...
ValueError: arrangement cannot simultaneously have h and -h as hyperplane

#30078 fixes this and we add another doctest here.

Change History (18)

comment:1 Changed 2 years ago by Frédéric Chapoton

Description: modified (diff)

comment:2 Changed 2 years ago by Frédéric Chapoton

The char poly gives the same answer

sage: p = A.characteristic_polynomial() : p
x^3 - 6*x^2 + 13*x - 11
sage: p(-1)                                                                     
-31

comment:3 in reply to:  2 Changed 2 years ago by Jean-Philippe Labbé

Replying to chapoton:

The char poly gives the same answer

sage: p = A.characteristic_polynomial() : p
x^3 - 6*x^2 + 13*x - 11
sage: p(-1)                                                                     
-31

Yes, this is own the number of regions is computed up to sign. The hyperplane arrangement seems to be sane: computing .regions() computes the expected (number of) regions.

I asked the number of regions to double-check and then got this scary answer...

Version 0, edited 2 years ago by Jean-Philippe Labbé (next)

comment:4 Changed 2 years ago by Jean-Philippe Labbé

Summary: Characteristic polynomial of central Hyperplane arrangement results wrong result?Characteristic polynomial of central Hyperplane arrangement returns wrong result?

comment:5 Changed 2 years ago by Julian Ritter

I encountered this problem in some example a long while ago, before I was contributing to Sage myself. A simple workaround is to have n_regions output len(self.regions()), which was good enough for me. Of course, this is much slower if one doesn’t want to compute the regions anyway. I don’t understand the characteristic polynomial well enough to figure out the error in there.

comment:6 Changed 22 months ago by Jean-Philippe Labbé

Description: modified (diff)

comment:7 Changed 20 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:8 Changed 14 months ago by Matthias Köppe

Milestone: sage-9.4sage-9.5

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

Milestone: sage-9.5sage-9.6

comment:10 in reply to:  5 Changed 7 months ago by Julian Ritter

Replying to nailuj:

I don’t understand the characteristic polynomial well enough to figure out the error in there.

The characteristic polynomial is obtained through recursive deletions and contractions of hyperplane arrangements. During this process, it may occur that some hyperplane h is included in an arrangement multiple times with different scalings of the defining linear expression which are not properly detected as duplicates. This is due to a defect in the method hyperplane.primitive() addressed in #30078.

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

Dependencies: #30078

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

Is this defect solved by #30078?

comment:13 Changed 6 months ago by Travis Scrimshaw

It seems like it is. Using the first example, I get

sage: A.n_regions()
24
sage: len(A.regions())
24
sage: A.characteristic_polynomial()(-1)
-24

So it is now consistent. We probably just want to add a doctest for this ticket.

comment:14 Changed 6 months ago by gh-kliem

Authors: Jonathan Kliem
Branch: public/30749
Commit: 1492ed150e76f36d09317428d9e642986554ec6b
Dependencies: #30078
Description: modified (diff)
Status: newneeds_review

#30078 already adds one doctest. So we can either close it as duplicate or add another doctest. Either way is fine with me.


New commits:

1492ed1add another doctest for 30749

comment:15 Changed 6 months ago by Andrew

  • sage/geometry/hyperplane_arrangement/arrangement.py

    a b  
    11791179            sage: H = HyperplaneArrangements(AA, names='xyz')
    11801180            sage: x,y,z = H.gens()
    11811181            sage: A = H(backend="normaliz")  # optional - pynormaliz
    1182             sage: for v in my_vector:        # optional - pyrormaliz
     1182            sage: for v in my_vectors:       # optional - pynormaliz
    11831183            ....:     a, b, c = v
    11841184            ....:     A = A.add_hyperplane(a*x + b*y + c*z)
    1185             sage: A.n_regions()              # optional - pyrormaliz
     1185            sage: A.n_regions()              # optional - pynormaliz
    11861186            32
    11871187        """
    11881188        if self.base_ring().characteristic() != 0:

comment:16 Changed 6 months ago by git

Commit: 1492ed150e76f36d09317428d9e642986554ec6bd74929dfb74820f79d574189a6bc5803dc00dd8d

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

d74929dtypos

comment:17 Changed 6 months ago by Travis Scrimshaw

Reviewers: Travis Scrimshaw
Status: needs_reviewpositive_review

Thank you. LGTM.

@gh-sheerluck, please add your (real) name to the reviewers (if you want).

comment:18 Changed 6 months ago by Volker Braun

Branch: public/30749d74929dfb74820f79d574189a6bc5803dc00dd8d
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.