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: sage-8.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:

Status badges

Description

Add functions to test if a lattice is constructible from the one-element lattice with Day doubling of 1) interval, 2) lower pseudo-interval, 3) upper pseudo-interval and 4) any convex subset.

Change History (30)

comment:1 Changed 5 years ago by jmantysalo

  • Cc chapoton tscrim added
  • Status changed from new to needs_info

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

comment:2 follow-up: Changed 5 years ago by tscrim

How about is_interval_doubling()?

comment:3 in reply to: ↑ 2 Changed 5 years ago by jmantysalo

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 follow-up: Changed 5 years ago by mantepse

Some people (at least McConville? https://arxiv.org/abs/1504.05213) use congruence_uniform instead of bounded, I think.

Version 0, edited 5 years ago by mantepse (next)

comment:5 Changed 5 years ago by mantepse

  • Reviewers set to Martin Rubey

comment:6 in reply to: ↑ 4 Changed 5 years ago by jmantysalo

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 congruence-normal if there exists a sequence of lattices L_1,..., L_l such that L_1 is the one-element 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 congruence-uniform if it is both congruence-normal and semidistributive.

Page 3 says this more directly "congruence-uniform lattice is any lattice constructable by a sequence of interval doubings."

comment:7 follow-up: Changed 5 years ago by mantepse

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 jmantysalo

  • Milestone changed from sage-8.0 to sage-wishlist

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.archives-ouvertes.fr/hal-01282151/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 jmantysalo

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 mantepse

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 jmantysalo

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 jmantysalo

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 one-element 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 n-len(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 jmantysalo

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 jmantysalo

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 jmantysalo

New try, kind of proof-of-concept:

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 jmantysalo

  • Branch set to u/jmantysalo/latticeposet__test_if_lattice_is_constructible_by_doublings

comment:17 Changed 5 years ago by jmantysalo

  • Commit set to 94ad32ce12bbc0a39a9fab4af83a8f2127e936a4
  • Milestone changed from sage-wishlist to sage-8.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:

94ad32cAdd is_doubling_constructible().

comment:18 Changed 5 years ago by mantepse

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 follow-up: Changed 5 years ago by mantepse

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 git

  • Commit changed from 94ad32ce12bbc0a39a9fab4af83a8f2127e936a4 to 2274d3765ec515b4e6efa021fe59870ab31d8219

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

2274d37Change name etc.

comment:21 Changed 5 years ago by git

  • Commit changed from 2274d3765ec515b4e6efa021fe59870ab31d8219 to 9974715d4de393b776eaefdc8f33113224a888cd

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

9974715LaTeX formatting.

comment:22 in reply to: ↑ 19 Changed 5 years ago by jmantysalo

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 short-circuit 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 "de-doubling" algorithm quite naturally. Every interval doubling adds exactly one meet- and one join-irreducible 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 "de-doubling" congruence.

comment:23 follow-up: Changed 5 years ago by 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...

comment:24 Changed 5 years ago by mantepse

  • Status changed from needs_review to positive_review

comment:25 in reply to: ↑ 23 Changed 5 years ago by jmantysalo

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(N-2):
    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[i-2] if attrcall(f)(L)]))

comment:26 follow-up: Changed 5 years ago by 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?

comment:27 in reply to: ↑ 26 Changed 5 years ago by jmantysalo

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 non-connected subset, then L[S][T] and L[T][S] are isomorphic.

comment:28 follow-up: Changed 5 years ago by tscrim

*cough*authorname*cough*

comment:29 in reply to: ↑ 28 Changed 5 years ago by jmantysalo

  • Authors set to Jori Mäntysalo

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 vbraun

  • 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
Note: See TracTickets for help on using tickets.