Opened 5 years ago
Closed 5 years ago
#22648 closed enhancement (fixed)
LatticePoset: test if lattice is constructible by doublings
Reported by:  jmantysalo  Owned by:  

Priority:  major  Milestone:  sage8.0 
Component:  combinatorics  Keywords:  
Cc:  chapoton, tscrim  Merged in:  
Authors:  Jori Mäntysalo  Reviewers:  Martin Rubey 
Report Upstream:  N/A  Work issues:  
Branch:  9974715 (Commits, GitHub, GitLab)  Commit:  9974715d4de393b776eaefdc8f33113224a888cd 
Dependencies:  Stopgaps: 
Description
Add functions to test if a lattice is constructible from the oneelement lattice with Day doubling of 1) interval, 2) lower pseudointerval, 3) upper pseudointerval and 4) any convex subset.
Change History (30)
comment:1 Changed 5 years ago by
 Cc chapoton tscrim added
 Status changed from new to needs_info
comment:2 followup: ↓ 3 Changed 5 years ago by
How about is_interval_doubling()
?
comment:3 in reply to: ↑ 2 Changed 5 years ago by
Replying to tscrim:
How about
is_interval_doubling()
?
For case 1 only? Could be, got to think about this.
We now have is_orthocomplemented()
(by me) with optional parameter unique
. What you think about that, and having something like is_doubling_constructable()
with mandratory string parameter having possible values 'convex', 'intevar'
etc?
comment:4 followup: ↓ 6 Changed 5 years ago by
Some people (at least McConville? https://arxiv.org/abs/1504.05213) use congruence_uniform
instead of bounded, I think.
comment:5 Changed 5 years ago by
 Reviewers set to Martin Rubey
comment:6 in reply to: ↑ 4 Changed 5 years ago by
Replying to mantepse:
Some people (at least McConville? https://arxiv.org/abs/1504.05213) use
congruence_uniform
instead of bounded, I think:
Duh. We already have is_uniform
after #21861.
A finite lattice L is congruencenormal if there exists a sequence of lattices L_1,..., L_l such that L_1 is the oneelement lattice, L_l = L, and for all i, there exists an order convex subset C_i of L_i such that L_{i+1} = L_i[Ci].
A lattice is congruenceuniform if it is both congruencenormal and semidistributive.
Page 3 says this more directly "congruenceuniform lattice is any lattice constructable by a sequence of interval doubings."
comment:7 followup: ↓ 9 Changed 5 years ago by
In case it's possible, it would be great if the code could also produce a certificate.
For myself personally, what would be wonderful is a function that takes a lattice and produces all intervals that can be collapsed. (I assume that, no matter which intervall is collapsed, the result should again be congruence uniform, if the original was. But I admit that I do not know.)
comment:8 Changed 5 years ago by
 Milestone changed from sage8.0 to sagewishlist
Certificate should be possible.
First see a term 'inflation' in http://www.math.hawaii.edu/~jb/inflation.pdf and also figure 3 at page 8. Maybe doubling construction should be expanded to municipal subsets?
For decomposing see https://hal.archivesouvertes.fr/hal01282151/document.
But I can't be sure when I will look at this, and so I mark this as wishlist queue.
comment:9 in reply to: ↑ 7 Changed 5 years ago by
Replying to mantepse:
For myself personally, what would be wonderful is a function that takes a lattice and produces all intervals that can be collapsed.
I think it should be something like this:
def antidouble(self): ji = self.join_irreducibles() mi = self.meet_irreducibles() h = {} i = 0 for l in self.level_sets(): for e in l: h[e] = i i += 1 for a in ji: a_ = self.lower_covers(a)[0] for b in mi: if self.compare_elements(a, b) is not None: continue b_ = self.upper_covers(b)[0] if h[b]h[a_] == h[b_]h[a]: A = self.interval(a_, b) B = self.interval(a, b_) if len(A) == len(B): if self.subposet(A).is_isomorphic(self.subposet(B)): if LatticePoset(self.subposet([e for e in self if e not in B])).day_doubling(A).is_isomorphic(self): print((a_, b), (a, b_))
but of course is much faster to work directly with Hasse Diagram. Having temporary posets is bad, as they eat memory that is not released until you restart the whole worksheet.
comment:10 Changed 5 years ago by
Wow! Thank you!
There must be a small bug however, because
antidouble(posets.PentagonPoset())
should print a collapsible interval (the middle relation in the longer chain), but doesn't.
In case I find out, I'll let you know!
comment:11 Changed 5 years ago by
True, but I think they are just the double irreducible elements that are not seen by this code.
Anyway, I guess I should extend Posets.RandomLattice
to get some test material.
comment:12 Changed 5 years ago by
Random code could be like
def random_bounded(n, p): """ Return a random "bounded" lattice. I.e. a lattice that can be made from the oneelement lattice by doubling an interval. """ if n < 4: return Posets.ChainPoset(n) g = digraphs.Path(2) g = Posets.PentagonPoset().hasse_diagram() n = n  2 while n: a = g.random_vertex() a_up = list(g.depth_first_search(a)) b = a_up[randint(0, ceil(len(a_up)*p*random())1)] b_down = list(g.depth_first_search(b, neighbors=g.neighbors_in)) S = [x for x in a_up if x in b_down] if nlen(S) < 0 or len(S) == 0: continue # New try... g_S = g.subgraph(S) g_S.relabel(lambda x: (1, x)) g = g.union(g_S) for e in g.neighbor_out_iterator(b): g.delete_edge(b, e) g.add_edge((1, b), e) for e in S: g.add_edge(e, (1, e)) g.relabel() n = len(S) return LatticePoset(g)
to test try for example
set_random_seed(0) random_bounded(15, 1).show()
comment:13 Changed 5 years ago by
This needs more reading and thinking.
But a question: If we have a decomposition  as certificate
or as a specific function  what should be the output type? Some kind of tuple or list, I guess.
comment:14 Changed 5 years ago by
More about this. Free Lattices by Ralph S. Freese, Jaroslav Ježek and James Bryant Nation p. 76 says that a lattice L
is lower bounded iff Ji(L) = Ji(Con L)
, and of course dually for upper bounded. The congurence lattice of a lattice is always distributive. A distributive lattice L has Ji(L) = Mi(L)
. Hence a lattice L
can be (totally) bounded only if it has Ji(L) = Mi(L)
. That can be used as a fast check to reject lattices that clearly can't be (totallyt) bounded.
And of course Posets.DiamondPoset(5)
shows that the last "if" is not "iff".
But I must continue to think and code. For me they are almost the same thing.
comment:15 Changed 5 years ago by
New try, kind of proofofconcept:
def antidouble(L): H = L._hasse_diagram at = H.atoms_of_congruence_lattice() for cong in at: if all(len(p) <= 2 for p in cong): tmp = [p for p in cong if len(p) == 2] tmp1 = [min(p) for p in tmp] tmp2 = [max(p) for p in tmp] LatticePoset(L.subposet([L._vertex_to_element(e) for e in H if e not in tmp2])).show() print([L._vertex_to_element(e) for e in tmp1]) break else: print("Nothing to double.")
comment:16 Changed 5 years ago by
 Branch set to u/jmantysalo/latticeposet__test_if_lattice_is_constructible_by_doublings
comment:17 Changed 5 years ago by
 Commit set to 94ad32ce12bbc0a39a9fab4af83a8f2127e936a4
 Milestone changed from sagewishlist to sage8.0
 Status changed from needs_info to needs_review
OK, I started working with this. I think it is easier to proceed with smaller parts, and so put this on needs_review. The code is trivial, so the main question is about the design.
New commits:
94ad32c  Add is_doubling_constructible().

comment:18 Changed 5 years ago by
Currently compiling...
In any case, I'd prefer is_constructible_by_doublings
over is_doubling_constructible
. I am somewhat surprised that the test is now so simple.
comment:19 followup: ↓ 22 Changed 5 years ago by
Another minor thing is that you should include something like the following in the docstring:
A lattice L is lower bounded if and only if Ji(L) = Ji(Con L), dually for upper bounded, see Free Lattices by Ralph S. Freese, Jaroslav Ježek and James Bryant Nation p. 76.
Note that a congruence lattice of a lattice is always distributive, and a distributive lattice L has Ji(L) = Mi(L). Hence a lattice L can be totally)bounded only if it has Ji(L) = Mi(L).
I'd like to ask you to also include a reference to the term congruence uniform (eg. McConville?).
comment:20 Changed 5 years ago by
 Commit changed from 94ad32ce12bbc0a39a9fab4af83a8f2127e936a4 to 2274d3765ec515b4e6efa021fe59870ab31d8219
Branch pushed to git repo; I updated commit sha1. New commits:
2274d37  Change name etc.

comment:21 Changed 5 years ago by
 Commit changed from 2274d3765ec515b4e6efa021fe59870ab31d8219 to 9974715d4de393b776eaefdc8f33113224a888cd
Branch pushed to git repo; I updated commit sha1. New commits:
9974715  LaTeX formatting.

comment:22 in reply to: ↑ 19 Changed 5 years ago by
Replying to mantepse:
I changed the name and add a reference. I think that
Another minor thing is that you should include something like the following in the docstring:
Note that a congruence lattice of a lattice is always distributive, and a distributive lattice L has Ji(L) = Mi(L). Hence a lattice L can be totally)bounded only if it has Ji(L) = Mi(L).
is not needed to say, as we don't rely on it. This only uses Python's shortcircuit evaluation of a==b==c
as an optimization.
I'd like to ask you to also include a reference to the term congruence uniform (eg. McConville?).
I don't think it is necessary.
I am somewhat surprised that the test is now so simple.
I think it comes from "dedoubling" algorithm quite naturally. Every interval doubling adds exactly one meet and one joinirreducible element, i.e. the upper cover of bottom of the set to double and the top of the set to double. On the other direction if Ji(Con L)
equals to Ji(L)
, then every principal congruence must correspond to one of those "dedoubling" congruence.
comment:23 followup: ↓ 25 Changed 5 years ago by
Looks good! The sequence
[len([1 for L in posets(r) if L.with_bounds().is_lattice() and LatticePoset(L.with_bounds()).is_constructible_by_doublings('interval')]) for r in range(1,8)] [1,2,4,9,22,60,174]
is not in the OEIS...
comment:24 Changed 5 years ago by
 Status changed from needs_review to positive_review
comment:25 in reply to: ↑ 23 Changed 5 years ago by
Replying to mantepse:
Looks good! The sequence
[len([1 for L in posets(r) if L.with_bounds().is_lattice() and LatticePoset(L.with_bounds()).is_constructible_by_doublings('interval')]) for r in range(1,8)] [1,2,4,9,22,60,174]is not in the OEIS...
Thanks for the review.
OEIS is missing most of series related to lattice enumeration. I have added some, see for example https://oeis.org/A261994. Here is code if you want to add more:
N = 8 LL = [] for i in range(N2): x = [] for P in Posets(i): try: x.append(LatticePoset(P.with_bounds())) except ValueError: pass LL.append(x) functions = ['is_planar', 'is_upper_semimodular'] for f in functions: print(f) for i in range(2, N): print(i, len([L for L in LL[i2] if attrcall(f)(L)]))
comment:26 followup: ↓ 27 Changed 5 years ago by
Side question: is it clear (or false) that the number of doublings of intervals to construct a lattice is independent of the particular doublings chosen?
comment:27 in reply to: ↑ 26 Changed 5 years ago by
Replying to mantepse:
Side question: is it clear (or false) that the number of doublings of intervals to construct a lattice is independent of the particular doublings chosen?
I think so, and even more has been said in some paper: If S
and T
are convex subsets so that their union is convex nonconnected subset, then L[S][T]
and L[T][S]
are isomorphic.
comment:28 followup: ↓ 29 Changed 5 years ago by
*cough*authorname*cough*
comment:29 in reply to: ↑ 28 Changed 5 years ago by
Replying to tscrim:
*cough*authorname*cough*
Duh. Added.
Btw, this can be optimized much more. First, we don't need to count all Ji(Con L)
, as if we found a, b \in Ji(L)
such that Cong(a, a_) == Cong(b, b_)
, where e_
is the only element covered by e
, we can't have Ji(Con L)
as big as Ji(L)
.
Next, a congruence generated by "antidoubling" can only have blocks of one or two element. Hence we can stop when we found even one e
such that Cong(e, e_)
has at least one congruence block of three or more elements.
comment:30 Changed 5 years ago by
 Branch changed from u/jmantysalo/latticeposet__test_if_lattice_is_constructible_by_doublings to 9974715d4de393b776eaefdc8f33113224a888cd
 Resolution set to fixed
 Status changed from positive_review to closed
What should be the names for these functions?
4 is called congruence normal, 2 and 3 as lower bounded and upper bounded and 1 as bounded. But we can't add
is_bounded()
with different meaning to lattices that we already have for posets.(See for example http://www.math.hawaii.edu/~jb/inflation.pdf.)