#13413: Correct bug in symmetric functions caused by Symmetrica using integers
longer than 32 bits
-------------------------------------------------+-------------------------
Reporter: saliola | Owner: sage-
Type: defect | combinat
Priority: critical | Status:
Component: combinatorics | positive_review
Keywords: symmetric functions, | Milestone: sage-5.13
symmetrica, memleak | Resolution:
Authors: Jeroen Demeyer | Merged in:
Report Upstream: Reported upstream. No | Reviewers:
feedback yet. | Work issues:
Branch: | Commit:
Dependencies: | Stopgaps:
-------------------------------------------------+-------------------------
Changes (by zabrocki):
* status: needs_review => positive_review
Old description:
> To begin with, let's do a change of basis in a small degree:
> {{{
> sage: p = SymmetricFunctions(QQ).powersum()
> sage: s = SymmetricFunctions(QQ).schur()
> sage: s(p[2,2])
> s[1, 1, 1, 1] - s[2, 1, 1] + 2*s[2, 2] - s[3, 1] + s[4]
> }}}
> Now let's do one in a larger degree:
> {{{
> sage: time g = s(p([1]*47))
> Time: CPU 19.16 s, Wall: 20.91 s
> }}}
> Now let's do that first one again:
> {{{
> sage: s(p[2,2])
> s[1, 1, 1, 1] - s[2, 1, 1] + 4571483302*s[2, 2] - s[3, 1] + s[4]
> }}}
> That's not the correct answer ! And the next time you ask Sage, it
> gives different, still incorrect, answers:
> {{{
> sage: s(p[2,2])
> s[1, 1, 1, 1] - s[2, 1, 1] + 4614252243*s[2, 2] - s[3, 1] + s[4]
> sage: s(p[2,2])
> s[1, 1, 1, 1] - s[2, 1, 1] + 4634718110*s[2, 2] - s[3, 1] + s[4]
> sage: s(p[2,2])
> s[1, 1, 1, 1] - s[2, 1, 1] + 4631047636*s[2, 2] - s[3, 1] + s[4]
> }}}
>
> In [https://groups.google.com/d/topic/sage-combinat-
> devel/fWMuS4R5M9Q/discussion this discussion] on sage-combinat-devel,
> Anne noticed that the problem is "not symmetrica per se, but some wrapper
> functions around symmetrica, as the following example shows":
> {{{
> sage: f = eval('symmetrica.t_POWSYM_SCHUR')
> sage: f({Partition([2,2]):Integer(1)})
> s[1, 1, 1, 1] - s[2, 1, 1] + 2*s[2, 2] - s[3, 1] + s[4]
> sage: time g = f({Partition([1]*47):Integer(1)})
> Time: CPU 13.03 s, Wall: 13.04 s
> sage: f({Partition([2,2]):Integer(1)})
> s[1, 1, 1, 1] - s[2, 1, 1] + 2*s[2, 2] - s[3, 1] + s[4]
> sage: Sym = SymmetricFunctions(QQ)
> sage: p = Sym.power()
> sage: s = Sym.schur()
> sage: s(p[2,2])
> s[1, 1, 1, 1] - s[2, 1, 1] + 4631790164*s[2, 2] - s[3, 1] + s[4]
> sage: f({Partition([2,2]):Integer(1)})
> s[1, 1, 1, 1] - s[2, 1, 1] + 2*s[2, 2] - s[3, 1] + s[4]
> }}}
>
> And Travis commented that:
>
> > When (random) big numbers appear like that, it almost always is an
> integer overflow. I suspect the communication with Symmetrica goes
> through the native integer. Is this correct? If so, then that's where I'd
> say the problem lies.
>
> '''spkg''':
> [http://boxen.math.washington.edu/home/jdemeyer/spkg/symmetrica-2.0.p8.spkg]
> ([attachment:symmetrica-2.0.p8.diff spkg diff])
>
> '''apply''' [attachment:13413_symmetrica.patch]
New description:
There are two examples of bugs that this patch corrects.
The first is in the conversion of integers between Symmetrica and Sage:
{{{
sage: from sage.libs.symmetrica.symmetrica import test_integer
sage: test_integer(2^76)==2^76
False
sage: test_integer(2^75)==2^75
True
}}}
The second is that coefficients in symmetric function package are not
always correct.
{{{
sage: s = SymmetricFunctions(QQ).s()
sage: p = SymmetricFunctions(QQ).p()
sage: c = s(p([1]*36)).coefficient([7,6,5,4,3,3,2,2,1,1,1,1])
sage: c==StandardTableaux([7,6,5,4,3,3,2,2,1,1,1,1]).cardinality()
False
}}}
This bug is corrected by modifying the Symmetrica spkg to ensure that
computations are done assuming that INT's are 4 bytes.
'''spkg''':
[http://boxen.math.washington.edu/home/jdemeyer/spkg/symmetrica-2.0.p8.spkg]
([attachment:symmetrica-2.0.p8.diff spkg diff])
'''apply''' [attachment:13413_symmetrica.patch]
--
Comment:
Since 95% of this discussion really is about the correction of the second
bug, I decided to move the original description to a new trac ticket
#15312.
--
Ticket URL: <http://trac.sagemath.org/ticket/13413#comment:50>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/groups/opt_out.
