Fix equality of combinatorial free module on non totally ordered basis

[hivert]

The following is obviously wrong:

sage: F = CombinatorialFreeModule(QQ, Subsets([1,2,3]))
sage: x = F.an_element()
sage: x+0 == x
False
sage: x+F.zero() == x
False

The reason is

sage: (x+F.zero()).terms()  # random
[2*B[{1}], 3*B[{2}], B[{}]]
sage: x.terms()             # random
[2*B[{1}], B[{}], 3*B[{2}]]

Fixing equality testing also revealed a bug in sage.combinat.sf.dual: the conversion back from the dual basis did not strip cancelled terms from the dictionary. This conversion now uses dict_linear_combination which fixes the bug, factors out code and should be faster.

See also the possible optimization in #12508

[hivert]

I uploaded the patch on behalf of Nicolas and put a positive review since I'm Ok with it (the test suite is currently running).

Nicolas: I just put the correct trac ticket number and added one more test compared to your patch. I don't think this needs a new review.

[nthiery]

+1! Thanks for the review!

[jdemeyer]

sage -t --long "devel/sage-main/sage/combinat/sf/dual.py"
**********************************************************************
File "/mnt/usb1/scratch/jdemeyer/merger/sage-5.0.beta4/devel/sage-main/sage/combinat/sf/dual.py", line 33:
    sage: TestSuite(f).run()  # long time (11s on sage.math, 2011)
Expected nothing
Got:
    Failure in _test_one:
    Traceback (most recent call last):
      File "/mnt/usb1/scratch/jdemeyer/merger/sage-5.0.beta4/local/lib/python/site-packages/sage/misc/sage_unittest.py", line 275, in run
        test_method(tester = tester)
      File "/mnt/usb1/scratch/jdemeyer/merger/sage-5.0.beta4/local/lib/python/site-packages/sage/categories/monoids.py", line 126, in _tes
t_one
        tester.assert_(x * one == x)
      File "/mnt/usb1/scratch/jdemeyer/merger/sage-5.0.beta4/local/lib/python2.7/unittest/case.py", line 420, in assertTrue
        raise self.failureException(msg)
    AssertionError: False is not true
[...]

[nthiery]

Replying to jdemeyer:

sage -t --long "devel/sage-main/sage/combinat/sf/dual.py"
**********************************************************************
File "/mnt/usb1/scratch/jdemeyer/merger/sage-5.0.beta4/devel/sage-main/sage/combinat/sf/dual.py", line 33:
    sage: TestSuite(f).run()  # long time (11s on sage.math, 2011)
Expected nothing
Got:
    Failure in _test_one:
    Traceback (most recent call last):
      File "/mnt/usb1/scratch/jdemeyer/merger/sage-5.0.beta4/local/lib/python/site-packages/sage/misc/sage_unittest.py", line 275, in run
        test_method(tester = tester)
      File "/mnt/usb1/scratch/jdemeyer/merger/sage-5.0.beta4/local/lib/python/site-packages/sage/categories/monoids.py", line 126, in _tes
t_one
        tester.assert_(x * one == x)
      File "/mnt/usb1/scratch/jdemeyer/merger/sage-5.0.beta4/local/lib/python2.7/unittest/case.py", line 420, in assertTrue
        raise self.failureException(msg)
    AssertionError: False is not true
[...]

Thanks for catching that. I am working on it. First thing, I am extracting the call to _test_associativity to only set # long on it, and not on the full testsuite (otherwise I would have caught the error myself). The other thing is that the new equality test highlighted a preexisting bug: x*f.one() contains zero coefficients in its dictionary.

[hivert]

Replying to jdemeyer:

sage -t --long "devel/sage-main/sage/combinat/sf/dual.py" [...]

AssertionError?: False is not true

}}}

Sorry for not catching this ealier ! I didn't launch the -long tests during my review.

[hivert]

Nicolas: using dict_linear_combination is clearly the good solution here. I'm testing all these and will get back to positive review if the tests pass. Do you have auto tests on sageange working the way we had on massena ?

Florent

[nthiery]

Replying to hivert:

Nicolas: using dict_linear_combination is clearly the good solution here. I'm testing all these and will get back to positive review if the tests pass. Do you have auto tests on sageange working the way we had on massena ?

Yes, that's where I ran the test mentionned above. I'll put sage-combinat-commits in CC next time.

[hivert]

I put back to positive review while waiting for the result of the tests.