Opened 3 years ago
Closed 3 years ago
#28429 closed enhancement (fixed)
Add the classical construction of the 120cell
Reported by:  jipilab  Owned by:  

Priority:  major  Milestone:  sage9.0 
Component:  geometry  Keywords:  polytopes, nonrational, normaliz 
Cc:  Winfried, jipilab, mkoeppe, vdelecroix  Merged in:  
Authors:  JeanPhilippe Labbé  Reviewers:  Jonathan Kliem 
Report Upstream:  N/A  Work issues:  
Branch:  9464179 (Commits, GitHub, GitLab)  Commit:  94641796685d7bbf0b8dbf14f67898cf3f728119 
Dependencies:  #27760  Stopgaps: 
Description
Ticket #27760 introduced the 120cell in the library, but it does not give the classical construction of Coxeter form 1969 available on Wikipedia:
https://en.wikipedia.org/wiki/120cell
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 3 years ago by
 Branch set to u/jipilab/classic120
 Commit set to 14b49182ed3bebd4c5b8cf19fca52d1400ed1888
 Dependencies set to #27760
 Status changed from new to needs_review
comment:2 Changed 3 years ago by
 Commit changed from 14b49182ed3bebd4c5b8cf19fca52d1400ed1888 to 3ee9569820fbd619223498a43efa19013e27076c
comment:3 Changed 3 years ago by
I merged the missing commit from #27760 to get a clean bot test.
comment:4 Changed 3 years ago by
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 3 years ago by
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 followup: ↓ 7 Changed 3 years ago by
A few comments:
 Most importantly
exact=False
does not work.base_ring
is not defined. Also you don't definesqrt5
. On that not, it makes sense to definephi
outside theif ... 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
fromitertools
? 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 4dimensional 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 4dimensional 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 3 years ago by
Replying to ghkliem:
 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
fromitertools
? 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.
comment:8 Changed 3 years ago by
 Status changed from needs_review to needs_work
comment:9 Changed 3 years ago by
 Commit changed from 3ee9569820fbd619223498a43efa19013e27076c to 7defa3c99e618c5c8820b107ff73f792e54a360d
comment:10 Changed 3 years ago by
 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 followup: ↓ 13 Changed 3 years ago by
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 justitertools.chain
. Otherwise you might also consider to useitertools.product
instead ofsage.categories.cartesian_product
.  Whats the point of naming it
K
here?K = QuadraticField(5, 'sqrt5') base_ring = K
comment:12 Changed 3 years ago by
 Status changed from needs_review to needs_work
comment:13 in reply to: ↑ 11 ; followup: ↓ 15 Changed 3 years ago by
 Branch changed from u/jipilab/classic120 to u/jipilab/classic120bis
 Commit changed from 7defa3c99e618c5c8820b107ff73f792e54a360d to 5e37f0e0c6886ed762e0c3e8c13e92b91926eb07
Replying to ghkliem:
 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 justitertools.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:
6454b0b  Added classical construction of 120cell

8b64dec  fixed the construction

5e37f0e  some more fixes

comment:14 Changed 3 years ago by
 Status changed from needs_work to needs_review
comment:15 in reply to: ↑ 13 Changed 3 years ago by
Replying to jipilab:
Replying to ghkliem:
 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 3 years ago by
 Status changed from needs_review to needs_work
comment:17 Changed 3 years ago by
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
comment:18 Changed 3 years ago by
 Commit changed from 5e37f0e0c6886ed762e0c3e8c13e92b91926eb07 to 6cb1552841d2df9a4ecccc13a59cc351b8c17f6e
Branch pushed to git repo; I updated commit sha1. New commits:
6cb1552  more fixes

comment:19 Changed 3 years ago by
 Commit changed from 6cb1552841d2df9a4ecccc13a59cc351b8c17f6e to 94641796685d7bbf0b8dbf14f67898cf3f728119
Branch pushed to git repo; I updated commit sha1. New commits:
9464179  Last edits

comment:20 Changed 3 years ago by
 Status changed from needs_work to needs_review
Should be good to go now.
comment:21 Changed 3 years ago by
 Reviewers set to Jonathan Kliem
 Status changed from needs_review to positive_review
LGTM
comment:22 Changed 3 years ago by
 Milestone changed from sage8.9 to sage9.0
comment:23 Changed 3 years ago by
 Branch changed from u/jipilab/classic120bis to 94641796685d7bbf0b8dbf14f67898cf3f728119
 Resolution set to fixed
 Status changed from positive_review to closed
Last 10 new commits:
Fix py3 code and tests for Sage8.9beta3
pep8
fixed some doctests
Fixed a test
trivial doc fix
fix coding in library
Added 'polytope' and fixed sum
Made a doctest not tested due to time
Merge branch 'develop' into h4_polytopes
Added classical construction of 120cell