LatticePoset: test if lattice is constructible by doublings

[jmantysalo]

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.

[jmantysalo]

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

[tscrim]

How about is_interval_doubling()?

[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?

[mantepse]

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

5.2 Congruence-normal and congruence-uniform lattices

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.

[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."

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

[jmantysalo]

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.

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

[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!

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

[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()

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

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

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

[jmantysalo]

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

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

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

[git]

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

​2274d37

Change name etc.

[git]

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

​9974715

LaTeX formatting.

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

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

[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)]))

[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?

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

[tscrim]

*cough*authorname*cough*

[jmantysalo]

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.