Macaulay2 / Macaulay2/M2

Posets package: Unexpected behavior of poset method

Open
#718 1 comment 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

package issue
Dominant language
Macaulay2
Stars
435
Forks
297
Avg merge
4d 20h
Merged PRs (30d)
11

Description

From the documentation of the poset method we have

This method creates a Poset by defining the set and giving the order relations between the elements in the set. The function assumes that each element in the ground set G is distinct and operates by taking the transitive and reflexive closure of the relations in R.

It seems that the poset method only operates this way in case poset (List) or poset (List, List) is called. On the other hand, both poset (List, List, Matrix) and poset (List, Function) exhibit aberrant behavior.

For example, here is the Boolean lattice on one element, built from the single relation using poset (List) .

i1 : R = {{set {}, set {0}}};
i2 : P = poset R;
i3 : peek P
o3 = Poset{cache => CacheTable{...1...}    }
           GroundSet => {set {}, set {0}}
           RelationMatrix => | 1 1 |
                             | 0 1 |
           Relations => {{set {}, set {0}}}

The same poset can be built with the poset (G, cmp) method where cmp is set inclusion.

i4 : cmp = (s,t) -> set s <= set t;
i5 : P == poset (subsets 1, cmp)
o5 = true

But taking cmp to be strict set inclusion gives devious results. The method throws an error if we use the default antisymmetry strategy.

i6 : cmp = (s,t) -> set s < set t;
i7 : poset (subsets 1, cmp)
stdio:7:1:(3): error: The relations are not anti-symmetric.

The error message is incorrect: the relation defined by cmp is clearly anti-symmetric. The issue with the relation defined by cmp is that it is irreflexive, an issue that, according to the documentation, should be taken care of by the method.

Mysteriously, we can avoid the error message in the above example by using the digraph antisymmetry strategy.

i8 : poset (subsets 1, cmp, AntisymmetryStrategy => "digraph")
o8 = Relation Matrix: | 0 1 |
                      | 0 0 |
o8 : Poset

The result is of type Poset but the relation matrix does not encode the reflexive relations, so this also seems to be a bug.

Examining the source code we see that poset (List, List) is the only poset constructor that calls transitiveClosure. So since poset (List) calls poset (List, List), it yields the right result. On the other hand, poset (List, Function) calls poset (List, List, Matrix) which does not call transitiveClosure and so strange behavior ensues.

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Read the Posets.m2 source linked in the issue, especially the poset(List, List), poset(List, List, Matrix), and poset(List, Function) constructors and their use of transitiveClosure. Reproduce the supplied strict-inclusion examples, then verify that each constructor produces the expected transitive and reflexive relation and reports the correct validation error.

Written by the indexing model from the issue text.

Assessment

Domain
tooling
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Clearly specified
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.