#15312: fix integer overflow (?) in conversion of powersums to Schur functions
-------------------------------------------------+-------------------------
Reporter: zabrocki | Owner:
Type: defect | Status:
Priority: critical | needs_review
Component: combinatorics | Milestone: sage-5.13
Keywords: symmetric functions, | Resolution:
symmetrica, memleak | Merged in:
Authors: Mike Zabrocki | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
Dependencies: #13413 | Stopgaps:
-------------------------------------------------+-------------------------
Changes (by jdemeyer):
* cc: jdemeyer (added)
Old description:
> The following bug seems to appear on Macs only (linux machines do not
> seem to be effected).
>
> 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.
>
> This is a bug which is carried over from #13413 . When we realized that
> there are actually two bugs and one has been corrected, these tickets
> were split.
New description:
The following bug seems to appear on Macs only (linux machines do not seem
to be effected).
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.
This is a bug which is carried over from #13413 . When we realized that
there are actually two bugs and one has been corrected, these tickets were
split.
'''spkg''': [http://garsia.math.yorku.ca/~zabrocki/symmetrica-2.0.p9.spkg]
'''apply''': [attachment:trac_15312_doctest-mz.patch]
--
--
Ticket URL: <http://trac.sagemath.org/ticket/15312#comment:23>
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.
