LatticePoset: add Frattini sublattice

[jm58660]

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.

Depends on #18567

CC: @tscrim

Component: combinatorics

Keywords: poset, lattice

Author: Jori Mäntysalo

Branch/Commit: 24c9406

Reviewer: Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/17226

[fchapoton]

Changed keywords from none to poset, lattice

[jm58660]

Dependencies: 18567

[jm58660]

Changed dependencies from 18567 to #18567

[jm58660]

Branch: u/jmantysalo/frattini_sublattice

[jm58660]

Author: Jori Mäntysalo

[jm58660]

comment:6

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:

24b10dd	Add maximal_sublattices().
ffe4fb8	Merge branch 'u/jmantysalo/latticeposet__add_maximal_sublattices_iterator__' of git://trac.sagemath.org/sage into u/jmantysalo/latticeposet__add_maximal_sublattices_iterator__
d85c873	Some reviewer tweaks.
b1e97bc	Added function frattini_sublattice().

[jm58660]

Commit: b1e97bc

[tscrim]

comment:7

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).

[sagetrac-git]

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

b20f025

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

[sagetrac-git]

Changed commit from b1e97bc to b20f025

[jm58660]

comment:9

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.

[jm58660]

comment:10

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.

[tscrim]

Reviewer: Travis Scrimshaw

[tscrim]

comment:11

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.

[sagetrac-git]

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

c112de6	Added a todo-note.
c969573	Arghs. Git again.

[sagetrac-git]

Changed commit from b20f025 to c969573

[jm58660]

comment:13

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.

[sagetrac-git]

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

24c9406

Removed a TODO-block.

[sagetrac-git]

Changed commit from c969573 to 24c9406

[jm58660]

comment:15

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.

[vbraun]

Changed branch from u/jmantysalo/frattini_sublattice to 24c9406