Opened 6 years ago
Closed 6 years ago
#17226 closed enhancement (fixed)
LatticePoset: add Frattini sublattice
Reported by:  jmantysalo  Owned by:  

Priority:  major  Milestone:  sage6.9 
Component:  combinatorics  Keywords:  poset, lattice 
Cc:  tscrim  Merged in:  
Authors:  Jori Mäntysalo  Reviewers:  Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  24c9406 (Commits, GitHub, GitLab)  Commit:  24c94064ec51c2e539e6197c51e58d0769221c2d 
Dependencies:  #18567  Stopgaps: 
Description (last modified by )
Add a function that computes the Frattini sublattice, i.e. intersection of all proper sublattices of a lattice. AFAIK there is no known good algorithm for this. Maybe making even a slow function will make it easier to search for one.
Change History (16)
comment:1 Changed 6 years ago by
 Keywords poset lattice added
comment:2 Changed 6 years ago by
 Description modified (diff)
comment:3 Changed 6 years ago by
 Dependencies set to 18567
 Description modified (diff)
comment:4 Changed 6 years ago by
 Dependencies changed from 18567 to #18567
comment:5 Changed 6 years ago by
 Branch set to u/jmantysalo/frattini_sublattice
comment:6 Changed 6 years ago by
 Cc tscrim added
 Commit set to b1e97bc9896e7c4ede3a948b4b7d321aba1f3fbb
 Milestone changed from sagewishlist to sage6.9
comment:7 followup: ↓ 9 Changed 6 years ago by
No, what you did is correct. You should merge in the dependency branches. If you don't need to, then there is no dependency. There are ways you can look at the differences in the code from one branch to another using git:
git diff commit1 commit2
where commit1
and commit2
can be names of branches (which are simply pointers to commits).
comment:8 Changed 6 years ago by
 Commit changed from b1e97bc9896e7c4ede3a948b4b7d321aba1f3fbb to b20f025dc034b16e3f1d53968668030131ef8ae1
Branch pushed to git repo; I updated commit sha1. New commits:
b20f025  Index of functions; check for 0, 1 and 2element lattices.

comment:9 in reply to: ↑ 7 Changed 6 years ago by
 Status changed from new to needs_review
Replying to tscrim:
No, what you did is correct.
Good.
Then I mark this as needs_review. I also added this and maximal_sublattices()
to index of functions.
I put the symbol of Frattini sublattice to documentation. Maybe it helps the reader, maybe not? I also use definition where Frattini sublattice of a lattice without proper sublattices (i.e. 1element lattice) is the lattice itself. Compare to Frattini subgroup of 1element group.
I did not found any good and simple example. But they can be added later.
comment:10 Changed 6 years ago by
Btw, creation of a lattice always [pre]computes join and meet matrices. Now, a function returning lattice could precompute them faster  in this case just by taking right rows and colums from the matrices of original lattice.
This is not done here. I suppose that we got faster lattice creation in the future.
comment:11 followup: ↓ 13 Changed 6 years ago by
 Reviewers set to Travis Scrimshaw
Two minor nitpicks:
 Frattini sublattice `\Phi(L)` is the intersection of all + The Frattini sublattice `\Phi(L)` is the intersection of all proper maximal sublattices of `L`. It is also the set of "nongenerators"  if the sublattice generated by set `S` of  elements is whole lattice then also `S \setminus \Phi(L)` + elements is whole lattice, then also `S \setminus \Phi(L)` generates whole lattice.
Once that's done, go ahead and set a positive review on my behalf. Thanks.
I agree that using the join and meet matrices of the ambient lattice could be used to speedup sublattice creation. However, as you said, this would be a separate ticket.
comment:12 Changed 6 years ago by
 Commit changed from b20f025dc034b16e3f1d53968668030131ef8ae1 to c969573f199ff5b008db4c6553ce27dc66d6213e
comment:13 in reply to: ↑ 11 Changed 6 years ago by
Replying to tscrim:
Two minor nitpicks:
Thanks. I corrected them. Can you still make a little check (and put on positive_review if it is good): I also added a todonote to hasse_diagram.py
, just to not forget it.
comment:14 Changed 6 years ago by
 Commit changed from c969573f199ff5b008db4c6553ce27dc66d6213e to 24c94064ec51c2e539e6197c51e58d0769221c2d
Branch pushed to git repo; I updated commit sha1. New commits:
24c9406  Removed a TODOblock.

comment:15 Changed 6 years ago by
 Status changed from needs_review to positive_review
I removed the note, so that I can put this to positive_review as said by tscrim on comment 11.
I may optimize this later, but for now it seems that I got several tickets on queue.
comment:16 Changed 6 years ago by
 Branch changed from u/jmantysalo/frattini_sublattice to 24c94064ec51c2e539e6197c51e58d0769221c2d
 Resolution set to fixed
 Status changed from positive_review to closed
Travis, you might want to check this. I think that I did something wrong, as there is now included code for
maximal_sublattices()
, which should be only dependence. But at least you can see the new function.It is not easy to find good example lattice. I'll continue searching. Maybe something with three maximal sublattices and so that the Frattini sublattice will something more than just a chain, but not almost all elements.
New commits:
Add maximal_sublattices().
Merge branch 'u/jmantysalo/latticeposet__add_maximal_sublattices_iterator__' of git://trac.sagemath.org/sage into u/jmantysalo/latticeposet__add_maximal_sublattices_iterator__
Some reviewer tweaks.
Added function frattini_sublattice().