Opened 5 years ago

Closed 4 years ago

#17226 closed enhancement (fixed)

LatticePoset: add Frattini sublattice

Reported by: jmantysalo Owned by:
Priority: major Milestone: sage-6.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) Commit: 24c94064ec51c2e539e6197c51e58d0769221c2d
Dependencies: #18567 Stopgaps:

Description (last modified by jmantysalo)

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 5 years ago by chapoton

  • Keywords poset lattice added

comment:2 Changed 5 years ago by jmantysalo

  • Description modified (diff)

comment:3 Changed 4 years ago by jmantysalo

  • Dependencies set to 18567
  • Description modified (diff)

comment:4 Changed 4 years ago by jmantysalo

  • Dependencies changed from 18567 to #18567

comment:5 Changed 4 years ago by jmantysalo

  • Branch set to u/jmantysalo/frattini_sublattice

comment:6 Changed 4 years ago by jmantysalo

  • Authors set to Jori Mäntysalo
  • Cc tscrim added
  • Commit set to b1e97bc9896e7c4ede3a948b4b7d321aba1f3fbb
  • Milestone changed from sage-wishlist to sage-6.9

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:

24b10ddAdd maximal_sublattices().
ffe4fb8Merge branch 'u/jmantysalo/latticeposet__add_maximal_sublattices_iterator__' of git://trac.sagemath.org/sage into u/jmantysalo/latticeposet__add_maximal_sublattices_iterator__
d85c873Some reviewer tweaks.
b1e97bcAdded function frattini_sublattice().

comment:7 follow-up: Changed 4 years ago by tscrim

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 4 years ago by git

  • Commit changed from b1e97bc9896e7c4ede3a948b4b7d321aba1f3fbb to b20f025dc034b16e3f1d53968668030131ef8ae1

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

b20f025Index of functions; check for 0-, 1- and 2-element lattices.

comment:9 in reply to: ↑ 7 Changed 4 years ago by jmantysalo

  • 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. 1-element lattice) is the lattice itself. Compare to Frattini subgroup of 1-element group.

I did not found any good and simple example. But they can be added later.

comment:10 Changed 4 years ago by jmantysalo

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 follow-up: Changed 4 years ago by tscrim

  • 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
         "non-generators" - 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 4 years ago by git

  • Commit changed from b20f025dc034b16e3f1d53968668030131ef8ae1 to c969573f199ff5b008db4c6553ce27dc66d6213e

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

c112de6Added a todo-note.
c969573Arghs. Git again.

comment:13 in reply to: ↑ 11 Changed 4 years ago by jmantysalo

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 todo-note to hasse_diagram.py, just to not forget it.

comment:14 Changed 4 years ago by git

  • Commit changed from c969573f199ff5b008db4c6553ce27dc66d6213e to 24c94064ec51c2e539e6197c51e58d0769221c2d

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

24c9406Removed a TODO-block.

comment:15 Changed 4 years ago by jmantysalo

  • 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 4 years ago by vbraun

  • Branch changed from u/jmantysalo/frattini_sublattice to 24c94064ec51c2e539e6197c51e58d0769221c2d
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.