Opened 2 years ago

Closed 23 months ago

#28429 closed enhancement (fixed)

Add the classical construction of the 120-cell

Reported by: jipilab Owned by:
Priority: major Milestone: sage-9.0
Component: geometry Keywords: polytopes, non-rational, normaliz
Cc: Winfried, jipilab, mkoeppe, vdelecroix Merged in:
Authors: Jean-Philippe Labbé Reviewers: Jonathan Kliem
Report Upstream: N/A Work issues:
Branch: 9464179 (Commits, GitHub, GitLab) Commit: 94641796685d7bbf0b8dbf14f67898cf3f728119
Dependencies: #27760 Stopgaps:

Status badges

Description

Ticket #27760 introduced the 120-cell in the library, but it does not give the classical construction of Coxeter form 1969 available on Wikipedia:

https://en.wikipedia.org/wiki/120-cell

This ticket provides this classical construction which is much faster since it uses only a degree 2 extension of the rationals.

Change History (23)

comment:1 Changed 2 years ago by jipilab

  • Branch set to u/jipilab/classic120
  • Commit set to 14b49182ed3bebd4c5b8cf19fca52d1400ed1888
  • Dependencies set to #27760
  • Status changed from new to needs_review

Last 10 new commits:

0c5b8d9Fix py3 code and tests for Sage8.9beta3
d66f7e2pep8
a6a5452fixed some doctests
71fbfdfFixed a test
d4260a6trivial doc fix
95d6bdafix coding in library
5971228Added 'polytope' and fixed sum
a1ad959Made a doctest not tested due to time
cc1a6abMerge branch 'develop' into h4_polytopes
14b4918Added classical construction of 120-cell

comment:2 Changed 2 years ago by git

  • Commit changed from 14b49182ed3bebd4c5b8cf19fca52d1400ed1888 to 3ee9569820fbd619223498a43efa19013e27076c

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

bd1fd21fix details
3ee9569Merge branch 'public/uniform_H4_polytopes' of trac.sagemath.org:sage into h4_polytopes

comment:3 Changed 2 years ago by jipilab

I merged the missing commit from #27760 to get a clean bot test.

comment:4 Changed 2 years ago by tscrim

I think this can be simplified:

-list(set([tuple(p) for p in flatten([Permutations(list(c)).list() for c in cp])]))
+list(set([tuple(p) for c in cp for p in Permutations(list(c))]))

so there are less transient (large) lists. Also, you should be able to do

verts += itertools.chain.from_iterable([p(tuple(c)) for p in even_perm] for c in cp)

since += for lists works for iterators and you might as well pass a iterable to from_iterable to avoid storing the entire list in memory (twice). Next, I would use latex formatting here: of type `H_4`::. Finally, is it reasonable to do this test with the backend that comes standard with Sage? In that same vein, how long does the normaliz test take?

comment:5 Changed 2 years ago by jipilab

Hi Travis,

Thanks for the feedback, I'll do the changes.

The new implementation with normaliz takes less than 1 sec. Before, it was taking much longer that's why it was tagged not tested.

Now, for the default 'field' backend, I did not test, but I expect it to take a long while. But I'll test it and write it here for the record.

comment:6 follow-up: Changed 2 years ago by gh-kliem

A few comments:

  • Most importantly exact=False does not work. base_ring is not defined. Also you don't define sqrt5. On that not, it makes sense to define phi outside the if ... else environment.
  • -            sage: polytopes.one_hundred_twenty_cell(backend='normaliz',construction='as_permutahedron') # not tested - long time
    +            sage: polytopes.one_hundred_twenty_cell(backend='normaliz', construction='as_permutahedron') # not tested - long time
    
  • # The 64 permutations of [±2,±2,0,0] (the ± are independant)
    
    I count 24.
  • I somehow don't like the construction with the Cartesian product. In the comments its all so easy and then I have to think about, why this is exactly true.

Couldn't we make a use of product from itertools? This creates all possible signs and then we just multiply (elementwise) all permutations:

verts = [[sign[i]*perm[i] for i in range(4)] for sign in product(*[[1,-1]]*4) for perm in verts_without_sign]

For the record:

sage: %time polytopes.one_hundred_twenty_cell(backend='normaliz')
CPU times: user 1.04 s, sys: 8 ms, total: 1.05 s
Wall time: 255 ms
A 4-dimensional polyhedron in (Number Field in sqrt5 with defining polynomial x^2 - 5 with sqrt5 = 2.236067977499790?)^4 defined as the convex hull of 600 vertices
sage: %time polytopes.one_hundred_twenty_cell(backend='field')
CPU times: user 18.1 s, sys: 28 ms, total: 18.2 s
Wall time: 18.2 s
A 4-dimensional polyhedron in (Number Field in sqrt5 with defining polynomial x^2 - 5 with sqrt5 = 2.236067977499790?)^4 defined as the convex hull of 600 vertices
sage: %time polytopes.one_hundred_twenty_cell(backend='normaliz',construction='as_permutahedron')
CPU times: user 17.2 s, sys: 52 ms, total: 17.2 s
Wall time: 15.5 s

comment:7 in reply to: ↑ 6 Changed 2 years ago by gh-kliem

Replying to gh-kliem:

  • I somehow don't like the construction with the Cartesian product. In the comments its all so easy and then I have to think about, why this is exactly true.

Couldn't we make a use of product from itertools? This creates all possible signs and then we just multiply (elementwise) all permutations:

verts = [[sign[i]*perm[i] for i in range(4)] for sign in product(*[[1,-1]]*4) for perm in verts_without_sign]

I should have read the code better... Didn't know that cartesian product does exactly that. Just figured it's way to many lines for something that simple and then I stopped reading and tried to find a shorter solution.

Still one could do all the signs with one line instead of doing it over and over again. Something like:

-            # The 64 permutations of [±2,±2,0,0] (the ± are independant)
-            verts = Permutations([0,0,2,2]).list() + Permutations([0,0,-2,-2]).list() + Permutations([0,0,2,-2]).list()
-
-            # The 64 permutations of the following vectors:
-            # [±1,±1,±1,±sqrt(5)]
-            # [±1/phi^2,±phi,±phi,±phi]
-            # [±1/phi,±1/phi,±1/phi,±phi^2]
-            from sage.categories.cartesian_product import cartesian_product
-            from sage.misc.flatten import flatten
-            full_perm_vectors = [[[1,-1],[1,-1],[1,-1],[-sqrt5,sqrt5]],
-                                 [[phi_inv**2,-phi_inv**2],[phi,-phi],[phi,-phi],[-phi,phi]],
-                                 [[phi_inv,-phi_inv],[phi_inv,-phi_inv],[phi_inv,-phi_inv],[-(phi**2),phi**2]]]
-            for vect in full_perm_vectors:
-                cp = cartesian_product(vect)
-                # The cartesian product creates duplicates, so we reduce it:
-                verts += list(set([tuple(p) for p in flatten([Permutations(list(c)).list() for c in cp])]))
-
-            # The 96 even permutations of [0,±1/phi^2,±1,±phi^2]
-            # The 96 even permutations of [0,±1/phi,±phi,±sqrt(5)]
-            # The 192 even permutations of [±1/phi,±1,±phi,±2]
-            import itertools
-            even_perm_vectors = [[[0],[phi_inv**2,-phi_inv**2],[1,-1],[-(phi**2),phi**2]],
-                                 [[0],[phi_inv,-phi_inv],[phi,-phi],[-sqrt5,sqrt5]],
-                                 [[phi_inv,-phi_inv],[1,-1],[phi,-phi],[-2,2]]]
-            even_perm = AlternatingGroup(4)
-            for vect in even_perm_vectors:
-                cp = cartesian_product(vect)
-                # The cartesian product creates duplicates, so we reduce it:
-                verts += list(itertools.chain.from_iterable([[p(tuple(c)) for p in even_perm] for c in cp]))
+            # The permutations of:
+            # [2,2,0,0]
+            # [1,1,1,sqrt(5)]
+            # [1/phi^2,phi,phi,phi]
+            # [1/phi,1/phi,1/phi,phi^2]
+            vectors = [[2,2,0,0], [1,1,1,sqrt5], [1/phi**2,phi,phi,phi], [1/phi, 1/phi, 1/phi, phi**2]]
+            verts_no_sign = list(x for vec in vectors for x in Permutations(vec).list())
+
+            # The even permutations of [0,1/phi^2,1,phi^2]
+            # The even permutations of [0,1/phi,phi,sqrt(5)]
+            # The even permutations of [1/phi,1,phi,2]
+            import itertools
+            vectors = [[0,1/phi**2,1,phi**2], [0,1/phi,phi,sqrt5], [1/phi,1,phi,2]]
+            even_perm = AlternatingGroup(4)
+            verts_no_sign += list(itertools.chain.from_iterable([[p(tuple(vec)) for p in even_perm] for vec in vectors]))
+
+            # Adding for each vertex copies in all orthants:
+            # [1,1,1,sqrt(5)] -> [±1,±1,±1,±sqrt(5)]
+            from itertools import product
+            verts = [[sign[i]*perm[i] for i in range(4)] for sign in product(*[[1,-1]]*4) for perm in verts_no_sign]

But I guess it's up to taste, what one prefers.

Last edited 2 years ago by gh-kliem (previous) (diff)

comment:8 Changed 2 years ago by gh-kliem

  • Status changed from needs_review to needs_work

comment:9 Changed 2 years ago by git

  • Commit changed from 3ee9569820fbd619223498a43efa19013e27076c to 7defa3c99e618c5c8820b107ff73f792e54a360d

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

2f15255Merge branch 'u/jipilab/classic120' into sage 9.0.beta2
7defa3cfixed the construction

comment:10 Changed 2 years ago by jipilab

  • Status changed from needs_work to needs_review

I did the changes. I decided to keep the construction as is.

I added a raise ValueError? if one tries to construct it with RDF as cdd returns a numerical inconsistency error.

comment:11 follow-up: Changed 2 years ago by gh-kliem

Some minor things:

  • The order should be consistent here:
    +            # The 64 permutations of [±2,±2,0,0] (the ± are independant)
    +            verts = Permutations([0,0,2,2]).list() + Permutations([0,0,-2,-2]).list() + 
    Permutations([0,0,2,-2]).list()
    
    also I still count 24 permutations as I already mentioned.
  • I'm a bit puzzled, where you remove the duplicates here:
    +                # The cartesian product creates duplicates, so we reduce it:
    +                verts += itertools.chain.from_iterable([p(tuple(c)) for p in even_perm] for c in cp)
    
  • Instead of importing itertools I would vote for importing just itertools.chain. Otherwise you might also consider to use itertools.product instead of sage.categories.cartesian_product.
  • Whats the point of naming it K here?
    K = QuadraticField(5, 'sqrt5')
    base_ring = K
    

comment:12 Changed 2 years ago by gh-kliem

  • Status changed from needs_review to needs_work

comment:13 in reply to: ↑ 11 ; follow-up: Changed 2 years ago by jipilab

  • Branch changed from u/jipilab/classic120 to u/jipilab/classic120bis
  • Commit changed from 7defa3c99e618c5c8820b107ff73f792e54a360d to 5e37f0e0c6886ed762e0c3e8c13e92b91926eb07

Replying to gh-kliem:

  • The order should be consistent here:
    +            # The 64 permutations of [±2,±2,0,0] (the ± are independant)
    +            verts = Permutations([0,0,2,2]).list() + Permutations([0,0,-2,-2]).list() + 
    Permutations([0,0,2,-2]).list()
    
    also I still count 24 permutations as I already mentioned.

Typo. Fixed.

  • I'm a bit puzzled, where you remove the duplicates here:
    +                # The cartesian product creates duplicates, so we reduce it:
    +                verts += itertools.chain.from_iterable([p(tuple(c)) for p in even_perm] for c in cp)
    

Well, this does what I want, what else can I say? It is very annoying to write something that creates them without duplicates, and we are dealing with a negligible amount of vertices, so I see now reason to make a fuss about inefficiency here.

  • Instead of importing itertools I would vote for importing just itertools.chain.

Done.

  • Whats the point of naming it K here?
    K = QuadraticField(5, 'sqrt5')
    base_ring = K
    

That's a wonderful rhetorical question. My rhetorical answer: to make you ask rhetorical questions. ;-)


New commits:

6454b0bAdded classical construction of 120-cell
8b64decfixed the construction
5e37f0esome more fixes

comment:14 Changed 2 years ago by jipilab

  • Status changed from needs_work to needs_review

comment:15 in reply to: ↑ 13 Changed 2 years ago by gh-kliem

Replying to jipilab:

Replying to gh-kliem:

  • I'm a bit puzzled, where you remove the duplicates here:
    +                # The cartesian product creates duplicates, so we reduce it:
    +                verts += itertools.chain.from_iterable([p(tuple(c)) for p in even_perm] for c in cp)
    

Well, this does what I want, what else can I say? It is very annoying to write something that creates them without duplicates, and we are dealing with a negligible amount of vertices, so I see now reason to make a fuss about inefficiency here.

Well, as every entry is unique, the cartesian product creates no duplicates. Hence, you don't have to remove them.

This is why I find this comment very confusing. You comment that you will remove duplicates, but neither are there duplicate nor do you do any instructions that would remove duplicates, if they where there.

Also you have a typo in your chain import, so this doesn't build.

comment:16 Changed 2 years ago by gh-kliem

  • Status changed from needs_review to needs_work

comment:17 Changed 2 years ago by jipilab

Oops, yes, I changed the import to from.

Perhaps my comment is not clear enough, it is not the cartesian product but the action of the even permutations:

+            import itertools import chain
+            even_perm_vectors = [[[0],[phi_inv**2,-phi_inv**2],[1,-1],[-(phi**2),phi**2]],
+                                 [[0],[phi_inv,-phi_inv],[phi,-phi],[-sqrt5,sqrt5]],
+                                 [[phi_inv,-phi_inv],[1,-1],[phi,-phi],[-2,2]]]
+            even_perm = AlternatingGroup(4)
+            for vect in even_perm_vectors:
+                cp = cartesian_product(vect)
+                # The cartesian product creates duplicates, so we reduce it:
+                verts += chain.from_iterable([p(tuple(c)) for p in even_perm] for c in cp) <----------- p acts here and creates duplicates
Version 0, edited 2 years ago by jipilab (next)

comment:18 Changed 2 years ago by git

  • Commit changed from 5e37f0e0c6886ed762e0c3e8c13e92b91926eb07 to 6cb1552841d2df9a4ecccc13a59cc351b8c17f6e

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

6cb1552more fixes

comment:19 Changed 2 years ago by git

  • Commit changed from 6cb1552841d2df9a4ecccc13a59cc351b8c17f6e to 94641796685d7bbf0b8dbf14f67898cf3f728119

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

9464179Last edits

comment:20 Changed 2 years ago by jipilab

  • Status changed from needs_work to needs_review

Should be good to go now.

comment:21 Changed 2 years ago by gh-kliem

  • Reviewers set to Jonathan Kliem
  • Status changed from needs_review to positive_review

LGTM

comment:22 Changed 2 years ago by chapoton

  • Milestone changed from sage-8.9 to sage-9.0

comment:23 Changed 23 months ago by vbraun

  • Branch changed from u/jipilab/classic120bis to 94641796685d7bbf0b8dbf14f67898cf3f728119
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.