LatticePoset: bug in testing semidistributivity

[jm58660]

Sage says that the Boolean lattice of 2^3=8 elements is not [meet|join]-semidistributive. This is due to comparison in logarithm of Sage Integer.

CC: @nexttime

Component: combinatorics

Author: Jori Mäntysalo

Branch/Commit: 68419a4

Reviewer: Frédéric Chapoton

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

[jm58660]

Branch: u/jmantysalo/latticeposet__bug_in_testing_semidistributivity

[jm58660]

comment:2

Ready for review, but let's first wait if discussion at https://groups.google.com/forum/#!topic/sage-devel/ZtwUc5c4Js0 founds better solution.

---

New commits:

1a72740

Workaround for log bug.

[jm58660]

Commit: 1a72740

[sagetrac-git]

Changed commit from 1a72740 to 9edd77b

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

9edd77b

Workaround for logarithm bug.

[jm58660]

comment:4

Leif, can you check this basically one line patch?

[tscrim]

comment:5

This is a massive hack solution that comes from this behavior:

sage: log(8, 2)
3
sage: log(8, int(2))
log(8)/log(2)
sage: log(int(8), int(2))
log(8)/log(2)

If we are to accept this hack, we should well document it as such.

[jm58660]

comment:6

Well, of course right solution would be correcting log. For example output type should depend on input type, not on input value. But

sage: type(log(8, 2))
<type 'sage.rings.integer.Integer'>
sage: type(log(9, 2))
<type 'sage.symbolic.expression.Expression'>

Should I just remove the quick test of non-semidistributivity then? Won't make much difference.

[tscrim]

comment:7

The biggest thing is just documenting why we are doing certain things, so when we go back and look again or someone else comes and looks at it, it is clear why things were done this way.

One option would be wrapping the inequality test in bool(...). This evaluates the symbolic expression to a boolean and doesn't affect boolean values:

sage: bool(13 > 8 * log(8, 2) / 2)
True
sage: bool(12 > 8 * log(8, 2) / 2)
False
sage: bool(True)
True
sage: bool(False)
False

Again, there should be a comment. Another option would be to do log(8,2).n(), which could introduce some numerical noise. Or just force both values to ZZ.

[nexttime]

comment:8

Replying to @tscrim:

One option would be wrapping the inequality test in bool(...). This evaluates the symbolic expression to a boolean and doesn't affect boolean values:

sage: bool(13 > 8 * log(8, 2) / 2)
True
sage: bool(12 > 8 * log(8, 2) / 2)
False
sage: bool(True)
True
sage: bool(False)
False

Quoting from sage-devel:

Ralf Stephan wrote:
> On Saturday, August 27, 2016 at 7:05:28 AM UTC+2, Jori Mäntysalo wrote:
>
>     But shouldn't it work in any case? I.e. comparison of
>     log(a+b*c^2...) to
>     some number should work when a,b,c... are sage Integers.
>
>
> log(integer) will not be expanded numerically except for log(0) and log(1).
> If you want it expanded, either give a float argument, eg log(2.), or
> append n().

N() wasn't the problem, but (also) rounding:

(s is 12 here.)

sage: n*log(n, 2)
24
sage: n*log(n, 2r)
8*log(8)/log(2)
sage: N(n*log(n, 2r))
24.0000000000000
sage: 2*s < n*log(n, 2)
False
sage: 2*s > n*log(n, 2)
False
sage: 2*s > n*log(n, 2r)
24 > 8*log(8)/log(2)
sage: bool(2*s > n*log(n, 2r))
True
sage: bool(2r*s > n*log(n, 2r))
True
sage: bool(2r*s > n*log(n, 2))
False
sage: 24 > N(n*log(n, 2r))
True

So I'd suggest to rewrite the code, and/or call the proper log(), or (first) check whether n is a power of 2.

[nexttime]

comment:9

(The left side of the comparison doesn't matter here, but note that

bool(2*s > n*log(n, 2r))

and

bool(2*s > n*log(n, 2))

give different results due to the behaviour of log() and rounding issues.)

[jm58660]

comment:10

Maybe I just wrote the log_2 myself:

def _log_2(n):
    """
    Return the 2-based logarithm of `n` rounded up.
    
    `n` is assumed to be a positive integer.
    
    EXAMPLES::
        
        sage: sage.combinat.poset.lattices._log_2(10)
        4
    """
    bits = -1
    i = n
    while i:
        i = i >> 1
        bits += 1
    if 1 << bits == n:
        return bits
    return bits+1

(On x86 one could use LZCNT and POPCNT. :=))

[nexttime]

comment:11

See also the ffs() family, [__builtin_]clz(), ... (also on ARM etc.)

If you just want to know whether n is an exact power of two (<=> n==0 or popcnt(n)==1), you can use n & ~(n-1) == n.

You could likewise use Python's math.log(int(n), 2), or various functions from GMP (since Sage Integers are based on mpz_t).

[jm58660]

comment:12

Replying to @nexttime:

You could likewise use Python's math.log(int(n), 2), or various functions from GMP (since Sage Integers are based on mpz_t).

Isn't there the same rounding problem with math.log?

[nexttime]

comment:13

Replying to @jm58660:

Replying to @nexttime:

You could likewise use Python's math.log(int(n), 2), or various functions from GMP (since Sage Integers are based on mpz_t).

Isn't there the same rounding problem with math.log?

Probably not for true powers of 2; don't know why Sage's log() is so bad in that regard. (How large does n, or log(n, 2), practically get?)

FWIW, if you want to stay in the integer domain, you could as well use 4s> nn, where the right-hand side is as cheap as the left if (n is sufficiently small or ctz(n) is relatively large or) n is a power of 2.

But that's perhaps already towards bike-shedding.

Especially if you know n is a power of 2, you could do appropriate rounding as well, but I'd rather fix log() or use a different one.

But doesn't already using sage.misc.functional.log(n, Integer(2)) solve (or, more precisely, work around) the main problem here?

[nexttime]

comment:14

Replying to @nexttime:

Replying to @jm58660:

Isn't there the same rounding problem with math.log?

Probably not for true powers of 2; don't know why Sage's log() is so bad in that regard. (How large does n, or log(n, 2), practically get?)

It should be safe up to at least 2⁵²+ (maybe even up to 2¹⁰²²+) because Python's floats (returned by math.log()) are actually doubles AFAIK.

[nexttime]

comment:15

Distantly related:

While we (you?) are at it, HasseDiagram has a couple of .is_...() methods which do not return True or False, but either None or some sample. Shouldn't these return the former unless a keyword argument certificate :-) (which they currently don't have) is passed?

[jm58660]

comment:16

Replying to @nexttime:

Distantly related:

While we (you?) are at it, HasseDiagram has a couple of .is_...() methods which do not return True or False, but either None or some sample. Shouldn't these return the former unless a keyword argument certificate :-) (which they currently don't have) is passed?

Other than is_semidistributive?

But yes, you are right. Kevin said the same at #21002. Suggestion for better name?

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

68419a4

Logarithm in semidistributive.

[sagetrac-git]

Changed commit from 9edd77b to 68419a4

[jm58660]

comment:18

OK, should work now. Also function name changed.

[nexttime]

comment:19

Replying to @jm58660:

OK, should work now. Also function name changed.

Doesn't the latter require a deprecation of the old function first?

[nexttime]

comment:20

Replying to @jm58660:

Replying to @nexttime:

Distantly related:

While we (you?) are at it, HasseDiagram has a couple of .is_...() methods which do not return True or False, but either None or some sample. Shouldn't these return the former unless a keyword argument certificate :-) (which they currently don't have) is passed?

Other than is_semidistributive?

Yes. The first (I think) being .is_complemented(self), but there are more IIRC.

But yes, you are right. Kevin said the same at #21002. Suggestion for better name?

certify, prove[_if_(true|false)], [return_]witness[_if_false]? ;-)

(I guess you were referring to is_...(), not the keyword argument, though.)

I'd rather keep the is_...(), but add (a) keyword or boolean argument(s), and only change the return type(s).

But then you'd have to first make the old behaviour the default, for backwards compatibility.

[nexttime]

comment:21

Perhaps a bit late, but did you look at Integer.{log,exact_log}()?

[jm58660]

comment:22

Replying to @nexttime:

OK, should work now. Also function name changed.

Doesn't the latter require a deprecation of the old function first?

I have thinked that hasse_diagram.py is an internal implementation file that can be changed. And the function is one release old only.

[jm58660]

comment:23

Replying to @nexttime:

(I guess you were referring to is_...(), not the keyword argument, though.)

I'd rather keep the is_...(), but add (a) keyword or boolean argument(s), and only change the return type(s).

I can think those later in another ticket. Actually there is more to think about in splitting code in posets.py and lattices.py vs. hasse_diagram.py.

But is there more to do for this ticket?

exact_log rounds down, my helper function rounds up. Of course I could use it, but the code would not be much simpler. Waiting for Python 3 and log_2...

[jm58660]

comment:24

Assuming that #21419 get accepted it offers a faster way to chech if a lattice is semidistributive.

[jm58660]

comment:25

Just a ping... Currently Sage says that a distributive lattice is not semidistributive, which is bad. There are more to add, but IMO bugs should be corrected first.

Replying to @jm58660:

But is there more to do for this ticket?

[fchapoton]

comment:26

ok, ok. It would have been better to put this log2 in some other place.

[fchapoton]

Reviewer: Frédéric Chapoton

[jm58660]

comment:27

Replying to @fchapoton:

It would have been better to put this log2 in some other place.

But I think that someone, "Frédéric" if I remember the name correctly, is converting SageMath to Python 3. :=) Then we will have math.log2().

[vbraun]

Changed branch from u/jmantysalo/latticeposet__bug_in_testing_semidistributivity to 68419a4