Correct bug in symmetric functions caused by Symmetrica using integers longer than 32 bits

[saliola]

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 (spkg diff)

apply attachment: 13413_symmetrica.patch​

Upstream: Reported upstream. No feedback yet.

CC: @sagetrac-sage-combinat @anneschilling @zabrocki @mguaypaq @darijgr @tscrim @mwhansen

Component: combinatorics

Keywords: symmetric functions, symmetrica

Author: Jeroen Demeyer

Reviewer: Mike Zabrocki

Merged: sage-5.13.beta2

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

[saliola]

Description changed:

--- 
+++ 
@@ -30,7 +30,7 @@
     s[1, 1, 1, 1] - s[2, 1, 1] + 4631047636*s[2, 2] - s[3, 1] + s[4]

-In the 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": +In 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')
@@ -48,3 +48,7 @@
 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.

[mguaypaq]

Running "sage symmetrica-test.py" may exhibit the bug.

[mguaypaq]

comment:3

Attachment: symmetrica-test.py.gz

Running the attached file symmetrica-test.py exhibits the problem on some machines (e.g., a Mac of some sort, I don't have the specs with me) but on my own laptop (ancient Dell laptop running Ubuntu 10.04 LTS) the test runs out of memory before finding a problem. Curiously enough, for the Mac I tried the problem appears at size 47, same as in the problem description.

I think this shows that the problem is in (or extremely close to) Symmetrica, not Sage itself.

Also, given that the coefficients change even without any intervening computations, I strongly suspect that we're seeing a memory leak in Symmetrica, not an integer overflow error. Most likely,

1. Symmetrica computes some result,
2. caches a pointer to the result,
3. frees the memory containing the result,
4. this memory eventually gets reused,
5. so the cached result now points to garbage.

It's interesting to note that the error only seems to happen when dealing with coefficients in QQ, not in ZZ, as Anne's testing shows. However, given the state of the Symmetrica source code, I'm not optimistic about actually finding (and fixing) the bug.

Do we know if there are other changes of basis which exhibit similar problems?

For convenience, note that the content of symmetrica-test.py is simply:

from sage.all import QQ, ZZ, Partition
from sage.libs.symmetrica.all import t_POWSYM_SCHUR as convert
from time import time

one = QQ(1)
bad_input = {Partition([ZZ(2)] * 2): one}

good_output = convert(bad_input)

start_time = time()
k = 1
while True:
    dummy = convert({Partition([ZZ(1)] * k): one})
    if convert(bad_input) != good_output: break
    print 'Size %d seems fine after %d seconds.' % (k, time() - start_time)
    k += 1

print 'Found a problem at size %d:' % k
for k in range(10):
    print convert(bad_input)

[d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db]

comment:5

This problem is much worse than originally stated. Mercedes Rosas contacted me and said that they are getting strange answers for calculations in the symmetric function package. I started to do some experiments.

sage: s = SymmetricFunctions(QQ).s()
sage: p = SymmetricFunctions(QQ).p()
sage: %time s(p([1]*36))==sum(StandardTableaux(la).cardinality()*s(la) for la in Partitions(36))
CPU times: user 91.50 s, sys: 0.26 s, total: 91.75 s
Wall time: 91.65 s
False
sage: s(p([1]*35))==sum(StandardTableaux(la).cardinality()*s(la) for la in Partitions(35))
True
sage: s(p[2,2])
s[1, 1, 1, 1] - s[2, 1, 1] + 2*s[2, 2] - s[3, 1] + s[4]

The first statement should return True and the second and third are not returning the clearly false coefficients that we are seeing when the calculation goes as high as degree 47.

WARNING: calculations using the symmetric function package should not be believed beyond a certain degree. I will continue to see what we can do to track down this bug.

[d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db]

comment:6

Hmmm. I wonder if this has something to do with Mac's being a 64 bit architecture? I checked the size of the coefficients for [1]*35 v. [1]*36 and found:

sage: s = SymmetricFunctions(QQ).s()
sage: p = SymmetricFunctions(QQ).p()
sage: g = s(p([1]*35))
sage: max(float(log(c)/log(2)) for c in g.coefficients())
62.76221725889632
sage: g = s(p([1]*36))
sage: max(float(log(c)/log(2)) for c in g.coefficients())
64.9241936394965

I suspect the function _py_longint in symmetrica.pxi is at fault but I haven't been able to track down some of the definitions in that file.

[d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db]

comment:7

If others are experiencing/not experiencing the same problems please let me know. I am running sage on mac running OSX 10.8.5 with Intel Core i7 processors. I am seeing the same bug at degree 36 on a linux machine at work.

[d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db]

comment:8

There is a function test_integer in the symmetrica package. It passes on some integers, but not all!

sage: from sage.libs.symmetrica.symmetrica import test_integer
sage: s = SymmetricFunctions(QQ).s()
sage: p = SymmetricFunctions(QQ).p()
sage: g = s(p([1]*35))
sage: all( test_integer(c)==c for c in g.coefficients())
True
sage: g = s(p([1]*36))
sage: all( test_integer(c)==c for c in g.coefficients())
False
sage: c=StandardTableaux([10,9,8,7,6,5,4,3,2,1]).cardinality()
sage: test_integer(c)==c
False

[d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db]

comment:9

Simple test:

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

[d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db]

comment:10

Attachment: trac_13413_firstfix-mz.patch.gz

I have a fix (see patch) for only one problem. A two line change fixes the issue with test_integer.

But sadly :( this does not fix the issue with s(p([1]*36)).

[d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db]

comment:11

The error seems to be within Symmetrica. I computed s(p([1]*36)) and stuck in a print statement to print out the intermediate symmetrica object. I found that the coefficient of the partition 111122334567 is 5.061293.630159.021056 and this agrees with what is returned by the command g = s(p([1]*36))

sage: g.coefficient([7,6,5,4,3,3,2,2,1,1,1,1])
5061293630159021056

however the coefficient should be

sage: StandardTableaux([7,6,5,4,3,3,2,2,1,1,1,1]).cardinality()
12961662907729536000

[darijgr]

Changed keywords from symmetric functions to symmetric functions, symmetrica

[darijgr]

comment:13

Ouch.

I can't help with understanding C code, but if anyone needs some of the German in Symmetrica translated, I can help.

Has the error so far only occurred in high degrees or with big coefficients only, or should all of Sym be considered a minefield until further notice?

[d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db]

comment:14

This is bad. Technically any calculation that involves the p basis over degree 20 and other bases of degree 30+ should be suspect. I make this assessment because it seems that the integer calculations with coefficients using 64 bits may be a problem. If you check sage.combinat.sf.sfa.zee(la) for la partitions of 21 and the number of standard tableaux of degree 35 have values > 2**64.

I can understand C, but it is a bit rusty for me. The fact that the C is written in German makes it slightly more of a challenge since for some functions I really have to make wild guesses.

[d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db]

comment:15

Mike H. posted a test.c program to try out in Symmetrica.

#include "def.h"
#include "macro.h"

ANFANG
scan(POW_SYM,a); 
t_POWSYM_SCHUR(a, b); 
println(b); 
ENDE

Run this program with input "36" followed by thirty-six "1"'s, followed by "1" (to indicate an integer coefficient), followed by "1" (to indicate that the coefficient is 1) "n" and the output says again 5.061293.630159.021056 111122334567. This means that the error is within Symmetrica.

[tscrim]

comment:16

I shouldn't be too rusty with my C, but this might take a combined effort at Sage Days to fully complete it. I'll take a look at the code as well.

Here's my two guesses about the problem from the discussion:

• It is an overflow error and the big fix will be to convert Symmetrica to use mpz instead of the usual machine integers.
• Symmetrica is using its own high precision integers (perhaps with a fixed maximum size) and it's overflowing that block of memory.

[d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db]

comment:17

I've spent some time looking through the Symmetrica code. It is not hard to figure out the basic ideas behind the library, but it uses some very terse C, non-obvious abbreviations, and a mix of German and English. It also has very little documentation.

Symmetrica "longints" are a structure of three INTs w2,w1,w0 with 0<=w_i<=2^15-1 plus a pointer to the next batch of 3 or NULL.

I've played with some programs that do some addition and multiplication with these longints and I haven't been able to make them fail, but it must be that in the calculation of p([1]*36) that some arithmetic fails when some overflow occurs. It will almost definitely easier to identify the bug in the library than to adapt it to another data structure.

[jdemeyer]

comment:18

Please report this upstream then.

[d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db]

Upstream: Reported upstream. No feedback yet.

[d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db]

comment:19

So I wrote to symmetric(at)symmetrica.de and told them about the bug and pointed them to the ticket for the example.

[jdemeyer]

comment:20

Maybe it's good to indicate in the ticket description where/how you reported this upstream.

[d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db]

comment:21

Yea! I think I found it! I thought about it and realized that the coefficient that I have been concentrating on as my example must be coming from adding the number of standard tableaux of shape formed by removing an outer corner together. I tried the following as a test.c.

#include "def.h"
#include "macro.h"

ANFANG
sscan_integer("1003805253100650000",a); 
println(a);
sscan_integer("1357888495095475200",b);
println(b);
sscan_integer("1472208106707261000",c);
println(c);
sscan_integer("1336535106226320000",d);
println(d);
sscan_integer("2194567264800768000",e);
println(e);
sscan_integer("2252538987957858600",f);
println(f);
sscan_integer("3344119693841203200",g);
println(g);
printf("-------------------\n");
add(a,b,h);
println(h);
add(c,h,h);
println(h);
add(d,h,h);
println(h);
add(e,h,h);
println(h);
add(f,h,h);
println(h);
add(g,h,h);
println(h);
ENDE

So above the line we will see the numbers of standard tableaux formed by removing a corner (which I calculated in sage, but compared them to the output of the program in comment 15. And the output is....

SYMMETRICA VERSION 3.0 - STARTING
 Thu Feb 26 14:58:10 MET 1998 
1003805253100650000
1357888495095475200
1472208106707261000
1336535106226320000
2194567264800768000
2252538987957858600
3344119693841203200
-------------------
2361693748196125200
3833901854903386200
5170436961129706200
7365004225930474200
 2.252539.342021.485568 
 5.596659.035862.688768 

SYMMETRICA VERSION 3.0 - ENDING
last changed:  Thu Feb 26 14:58:10 MET 1998 

Lets do the same thing by hand in sage:

sage: 1003805253100650000+1357888495095475200
2361693748196125200
sage: _+1472208106707261000
3833901854903386200
sage: _+1336535106226320000
5170436961129706200
sage: _+2194567264800768000
7365004225930474200
sage: _+2252538987957858600
9617543213888332800

Notice that as soon as I add two 'integer' objects together so that they become a 'longint' object (marked by where the program starts printing out periods in the number) the answer is wrong. So now I just have to find the routine which adds two ints and gives an overflow into longints.

[d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db]

comment:22

Here is a mini test.c to verify if the programs are working

#include "def.h"
#include "macro.h"

ANFANG
sscan_integer("7365004225930474200",a); 
println(a);
sscan_integer("2252538987957858600",b);
println(b);
printf("+------------------\n");
add(a,b,h);
println(h);
printf("but the answer should be....\n");
printf("9617543213888332800\n");
ENDE

Currently on my computer the answer is... 7.365004.528389.219328

[d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db]

comment:23

I sent a second bug report to symmetrica(at)symmetrica.de with the above example.

[d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db]

comment:24

Here seems to be the problem. If I take an integer and convert it into a long integer then it isn't right.

#include "def.h"
#include "macro.h"

ANFANG
sscan_integer("2252538987957858600",a);
println(a);
printf("but when I convert it into a long integer...\n");
t_int_longint(a,b);
println(b);
ENDE

The output on my computer:

SYMMETRICA VERSION 3.0 - STARTING
 Thu Feb 26 14:58:10 MET 1998 
2252538987957858600
but when I convert it into a long integer...
 302458.745128 

SYMMETRICA VERSION 3.0 - ENDING

[mwhansen]

comment:26

That makes sense since it's always expecting ints to be at most 32 bits. I'm testing out a patch now.

[d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db]

comment:27

It seems as though ints can be as large as 45 bits and the function t_int_longint will still work properly.

[mwhansen]

comment:28

Okay, the fix is to make def.h look like the following:

#include <stdint.h>

#ifdef __alpha
typedef  int32_t INT;
typedef  uint32_t  UINT;
#else /* __alpha */
typedef int32_t INT;
typedef uint32_t UINT;
#endif /* __alpha */

(and you probably don't need to change the first part.

[d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db]

comment:29

Thanks Mike.

The first two lines of def.h read:

/* file def.h SYMMETRICA */
/* INT should always be 4 byte */

Now it is becoming clearer to me...

[d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db]

comment:30

So I haven't the first clue about how to muck with the spkg's. Will you post your fix? I haven't even been able to check that it corrects the problems with the symmetric function calculations in sage. Essentially there are two problems that need to be checked (or three if you count the first issue that I provide a fix for above).

The first one is that at degree 36 the calculation is not correct. The second one is that after a calculation at degree 47 the coefficients start to become random.

[jdemeyer]

comment:31

I can easily make a spkg.

[jdemeyer]

Description changed:

--- 
+++ 
@@ -52,3 +52,5 @@
 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](http://boxen.math.washington.edu/home/jdemeyer/spkg/symmetrica-2.0.p8.spkg)

[jdemeyer]

Author: Jeroen Demeyer

[jdemeyer]

comment:33

I'm a bit worried by some of the compiler warnings, but these already existed before the patches...

[d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db]

comment:34

I'm having some issues installing it because I seem to be getting errors and not just warnings.

Are you getting the same error messages?

symmetrica-2.0.p8
====================================================
Extracting package /Users/zabrocki/Downloads/symmetrica-2.0.p8.spkg
-rw-r--r--@ 1 zabrocki  staff  680547 Oct 17 09:26 /Users/zabrocki/Downloads/symmetrica-2.0.p8.spkg
Finished extraction
****************************************************
Host system:
Darwin Mikes-MacBook-Pro.local 12.5.0 Darwin Kernel Version 12.5.0: Sun Sep 29 13:33:47 PDT 2013; root:xnu-2050.48.12~1/RELEASE_X86_64 x86_64
****************************************************
C compiler: gcc
C compiler version:
Using built-in specs.
COLLECT_GCC=gcc
COLLECT_LTO_WRAPPER=/Applications/sage/local/bin/../libexec/gcc/x86_64-apple-darwin12.3.0/4.7.3/lto-wrapper
Target: x86_64-apple-darwin12.3.0
Configured with: ../src/configure --prefix=/Users/dehayebuildbot/build/sage/dehaye/dehaye_binary/build/sage-5.10/local --with-local-prefix=/Users/dehayebuildbot/build/sage/dehaye/dehaye_binary/build/sage-5.10/local --with-gmp=/Users/dehayebuildbot/build/sage/dehaye/dehaye_binary/build/sage-5.10/local --with-mpfr=/Users/dehayebuildbot/build/sage/dehaye/dehaye_binary/build/sage-5.10/local --with-mpc=/Users/dehayebuildbot/build/sage/dehaye/dehaye_binary/build/sage-5.10/local --with-system-zlib --disable-multilib --disable-nls  
Thread model: posix
gcc version 4.7.3 (GCC) 
****************************************************
patching file de.c
patching file def.h
patching file macro.h
patching file bar.c
patching file def.h
Hunk #1 succeeded at 3100 (offset -5 lines).
Hunk #2 succeeded at 3266 (offset -5 lines).
patching file di.c
patching file ga.c
patching file galois.c
patching file macro.h
patching file nc.c
patching file nu.c
patching file part.c
patching file perm.c
patching file rest.c
patching file ta.c
patching file zyk.c
gcc -O2 -g  -DFAST -DALLTRUE   -c -o bar.o bar.c
gcc -O2 -g  -DFAST -DALLTRUE   -c -o bi.o bi.c
gcc -O2 -g  -DFAST -DALLTRUE   -c -o boe.o boe.c
gcc -O2 -g  -DFAST -DALLTRUE   -c -o bruch.o bruch.c
gcc -O2 -g  -DFAST -DALLTRUE   -c -o classical.o classical.c
gcc -O2 -g  -DFAST -DALLTRUE   -c -o de.o de.c
gcc -O2 -g  -DFAST -DALLTRUE   -c -o di.o di.c
gcc -O2 -g  -DFAST -DALLTRUE   -c -o ff.o ff.c
gcc -O2 -g  -DFAST -DALLTRUE   -c -o galois.o galois.c
gcc -O2 -g  -DFAST -DALLTRUE   -c -o ga.o ga.c
gcc -O2 -g  -DFAST -DALLTRUE   -c -o gra.o gra.c
gcc -O2 -g  -DFAST -DALLTRUE   -c -o hash.o hash.c
gcc -O2 -g  -DFAST -DALLTRUE   -c -o hiccup.o hiccup.c
gcc -O2 -g  -DFAST -DALLTRUE   -c -o io.o io.c
gcc -O2 -g  -DFAST -DALLTRUE   -c -o ko.o ko.c
gcc -O2 -g  -DFAST -DALLTRUE   -c -o list.o list.c
gcc -O2 -g  -DFAST -DALLTRUE   -c -o lo.o lo.c
lo.c:84:5: error: conflicting types for 'loc_index'
In file included from lo.c:3:0:
macro.h:559:13: note: previous declaration of 'loc_index' was here
lo.c:85:5: error: conflicting types for 'loc_size'
In file included from lo.c:3:0:
macro.h:559:24: note: previous declaration of 'loc_size' was here
lo.c:86:5: error: conflicting types for 'loc_counter'
In file included from lo.c:3:0:
macro.h:559:33: note: previous declaration of 'loc_counter' was here
lo.c:88:5: error: conflicting types for 'mem_counter_loc'
In file included from lo.c:3:0:
macro.h:562:35: note: previous declaration of 'mem_counter_loc' was here
lo.c:89:5: error: conflicting types for 'longint_speicherindex'
In file included from lo.c:3:0:
macro.h:562:13: note: previous declaration of 'longint_speicherindex' was here
lo.c:90:5: error: conflicting types for 'longint_speichersize'
In file included from lo.c:3:0:
macro.h:562:51: note: previous declaration of 'longint_speichersize' was here
make: *** [lo.o] Error 1
Error building Symmetrica.

real    0m28.966s
user    0m27.970s
sys 0m0.759s
************************************************************************
Error installing package symmetrica-2.0.p8
************************************************************************
Please email sage-devel (http://groups.google.com/group/sage-devel)
explaining the problem and including the relevant part of the log file
  /Applications/sage/logs/pkgs/symmetrica-2.0.p8.log
Describe your computer, operating system, etc.
If you want to try to fix the problem yourself, *don't* just cd to
/Applications/sage/spkg/build/symmetrica-2.0.p8 and type 'make' or whatever is appropriate.
Instead, the following commands setup all environment variables
correctly and load a subshell for you to debug the error:
  (cd '/Applications/sage/spkg/build/symmetrica-2.0.p8' && '/Applications/sage/sage' --sh)
When you are done debugging, you can type "exit" to leave the subshell.
************************************************************************

Any ideas?

[jdemeyer]

comment:35

This is work in progress, not yet needs_review.

[jdemeyer]

Attachment: symmetrica-2.0.p8.diff.gz

[jdemeyer]

Description changed:

--- 
+++ 
@@ -53,4 +53,6 @@

 > 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](http://boxen.math.washington.edu/home/jdemeyer/spkg/symmetrica-2.0.p8.spkg)
+**spkg**: [http://boxen.math.washington.edu/home/jdemeyer/spkg/symmetrica-2.0.p8.spkg](http://boxen.math.washington.edu/home/jdemeyer/spkg/symmetrica-2.0.p8.spkg) ([spkg diff](https://github.com/sagemath/sage-prod/files/10656268/symmetrica-2.0.p8.diff.gz))
+
+**apply** [attachment: 13413_include.patch](https://github.com/sagemath/sage/files/ticket13413/13413_include.patch.gz)

[jdemeyer]

Attachment: 13413_symmetrica.patch.gz

[jdemeyer]

Description changed:

--- 
+++ 
@@ -55,4 +55,4 @@

 **spkg**: [http://boxen.math.washington.edu/home/jdemeyer/spkg/symmetrica-2.0.p8.spkg](http://boxen.math.washington.edu/home/jdemeyer/spkg/symmetrica-2.0.p8.spkg) ([spkg diff](https://github.com/sagemath/sage-prod/files/10656268/symmetrica-2.0.p8.diff.gz))

-**apply** [attachment: 13413_include.patch](https://github.com/sagemath/sage/files/ticket13413/13413_include.patch.gz)
+**apply** [attachment: 13413_symmetrica.patch​](https://github.com/sagemath/sage/files/ticket13413/a9579ddf249ced046ea569cac0f1cb29.gz)

[jdemeyer]

comment:39

Added doctests

[d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db]

comment:40

The version you just posted seems to compile (I was having issues before) but it looks like the fix only solves 1/2 of the problem.

sage: s = SymmetricFunctions(QQ).s()
sage: p = SymmetricFunctions(QQ).p()
sage: g = s(p([1]*36))
sage: g.coefficient([7,6,5,4,3,3,2,2,1,1,1,1])
12961662907729536000
sage: g = s(p([1]*47))
sage: s(p[2,2])
s[1, 1, 1, 1] - s[2, 1, 1] + 1589352607*s[2, 2] - s[3, 1] + s[4]

Are you getting similar results? We may have to go back to the drawing board.

[jdemeyer]

comment:41

I get

sage:  s = SymmetricFunctions(QQ).s()
sage: p = SymmetricFunctions(QQ).p()
sage: g = s(p([1]*36))
sage: g.coefficient([7,6,5,4,3,3,2,2,1,1,1,1])
12961662907729536000
sage: g = s(p([1]*47))
sage: s(p[2,2])
s[1, 1, 1, 1] - s[2, 1, 1] + 2*s[2, 2] - s[3, 1] + s[4]

Sorry to ask the obvious, but you did run ./sage -b after installing the spkg, right?

[d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db]

comment:42

I did. I just touched all the files in the sage/libs/symmetrica directory and re-ran the sage -b. It fixes the problem so now both problems are fixed. I'll do a few more tests but that looks fantastic! Thanks.

[d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db]

comment:43

I don't know if this kicks the can down the road or if something else is going wrong. I am still finding failing tests if I go higher in degree.

sage: s = SymmetricFunctions(QQ).s()
sage: p = SymmetricFunctions(QQ).p()
sage: g = s(p([1]*47))
sage: g.coefficient([9,8,7,6,5,4,3,2,2,1])
14333651730948448927581696000
sage: StandardTableaux([9,8,7,6,5,4,3,2,2,1]).cardinality()
14333651730948448927581696000
sage: g = s(p([1]*55))
sage: g.coefficient([10,9,8,7,6,5,4,3,2,1])
8018556129655805634621347419399180139888640
sage: StandardTableaux([10,9,8,7,6,5,4,3,2,1]).cardinality()
44261486084874072183645699204710400
sage: s(p[2,2])
s[1, 1, 1, 1] - s[2, 1, 1] + 2*s[2, 2] - s[3, 1] + s[4]
sage: g = s(p([1]*61))
sage: g.coefficient([10,9,8,7,6,5,5,4,3,2,1,1])
776260975585827810735172007007698644433817545700
sage: StandardTableaux([10,9,8,7,6,5,5,4,3,2,1,1]).cardinality()
5801010788714895536587439870454056838000
sage: s(p[2,2])
s[1, 1, 1, 1] - s[2, 1, 1] + 498984676*s[2, 2] - s[3, 1] + s[4]

Note that computing the degree 61 calculations takes a long time. Are you finding the same errors?

[jdemeyer]

comment:44

I get

jdemeyer@boxen:/release/merger/sage-5.12$ ./sage
┌────────────────────────────────────────────────────────────────────┐
│ Sage Version 5.12, Release Date: 2013-10-07                        │
│ Type "notebook()" for the browser-based notebook interface.        │
│ Type "help()" for help.                                            │
└────────────────────────────────────────────────────────────────────┘
sage: s = SymmetricFunctions(QQ).s()
sage: p = SymmetricFunctions(QQ).p()
sage: g = s(p([1]*47))
sage: g.coefficient([9,8,7,6,5,4,3,2,2,1])
14333651730948448927581696000
sage: StandardTableaux([9,8,7,6,5,4,3,2,2,1]).cardinality()
14333651730948448927581696000
sage: g = s(p([1]*55))
sage: g.coefficient([10,9,8,7,6,5,4,3,2,1])
44261486084874072183645699204710400
sage: StandardTableaux([10,9,8,7,6,5,4,3,2,1]).cardinality()
44261486084874072183645699204710400
sage: s(p[2,2])
s[1, 1, 1, 1] - s[2, 1, 1] + 2*s[2, 2] - s[3, 1] + s[4]
sage: g = s(p([1]*61))
sage: g.coefficient([10,9,8,7,6,5,5,4,3,2,1,1])
5801010788714895536587439870454056838000
sage: StandardTableaux([10,9,8,7,6,5,5,4,3,2,1,1]).cardinality()
5801010788714895536587439870454056838000
sage: s(p[2,2])
s[1, 1, 1, 1] - s[2, 1, 1] + 2*s[2, 2] - s[3, 1] + s[4]

[d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db]

comment:45

Trials on linux machine give correct answers, on Mac I am getting errors. I am running sage -ba to see if this makes a difference.

[d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db]

comment:46

On two different macs am getting:

sage: s = SymmetricFunctions(QQ).s()
sage: p = SymmetricFunctions(QQ).p()
sage: sage: g = s(p([1]*47))
sage: g.coefficient([9,8,7,6,5,4,3,2,2,1])
14333651730948448927581696000
sage: sage: g = s(p([1]*47))
sage: g.coefficient([9,8,7,6,5,4,3,2,2,1])
6813423452539470910666189837844044800

The first time the value is computed it seems to be correct. The second time it is random. This does not happen on linux.

[d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db]

comment:47

So I ran on an old copy of sage (no correction installed) on the same linux machine:

sage: s = SymmetricFunctions(QQ).s()
sage: p = SymmetricFunctions(QQ).p()
sage: g = s(p([1]*47))
sage: s(p([1]*5))
s[1, 1, 1, 1, 1] + 4*s[2, 1, 1, 1] + 5*s[2, 2, 1] + 6*s[3, 1, 1] + 5*s[3, 2] + 4*s[4, 1] + s[5]

On an old copy of sage on mac (correction installed or not):

sage: s = SymmetricFunctions(QQ).s()
sage: p = SymmetricFunctions(QQ).p()
sage: g = s(p([1]*47))
sage: s(p([1]*5))
s[1, 1, 1, 1, 1] - 1004621421*s[2, 1, 1, 1] - 2015815354*s[2, 2, 1] - 2018818386*s[3, 1, 1] - 2013245610*s[3, 2] - 1015866049*s[4, 1] + s[5]

This means that there are two (at least partially) independent problems going on here. One of them does not seem to appear on linux machines. When I run the examples in the patch description, I do not see the random coefficients in the expansion of s(p([2,2])). Do you see it on boxen?

[d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db]

comment:48

I am running on the hypothesis that on (at least certain) linux machines that the bug described in the patch description never existed. It was only a bug on Macs. However starting in comment 5, I identified a second bug that we can recreate at degree 36. This second bug is all corrected by installing the spkg and the patch (maybe there is a third bug around test_integer?).

I've only tested this on a couple of Macs and one linux machine and Jeroen has been posting the results from boxen. All evidence that I have says that the first bug is not resolved, but is only a problem on Macs. Can someone recreate the bug in the patch description on a linux machine?

The original description points to "some wrapper functions around symmetrica." This is probably still the case.

[darijgr]

comment:49

Ubuntu in a virtualbox, 64bit, sage 5.13.beta0 with patches installed (hopefully correctly: I -i'd symmetrica 2.0p8, but I never explicitly uninstalled 2.0p7).

Exhibit A:

sage: s = SymmetricFunctions(QQ).s()
sage: 
sage: p = SymmetricFunctions(QQ).p()
sage: g = s(p([1]*47))
sage: g.coefficient([9,8,7,6,5,4,3,2,2,1])
14333651730948448927581696000
sage: g = s(p([1]*47))
sage: g.coefficient([9,8,7,6,5,4,3,2,2,1])
14333651730948448927581696000

Exhibit B:

sage: p = SymmetricFunctions(QQ).powersum()
sage: s = SymmetricFunctions(QQ).schur()
sage: 
sage: s(p[2,2])
s[1, 1, 1, 1] - s[2, 1, 1] + 2*s[2, 2] - s[3, 1] + s[4]
sage: time g = s(p([1]*47))
/home/darij/sage-5.13.beta0/local/lib/python2.7/site-packages/sage/misc/sage_extension.py:371: DeprecationWarning: Use %time instead of time.
See http://trac.sagemath.org/12719 for details.
  line = f(line, line_number)
CPU times: user 19.23 s, sys: 0.06 s, total: 19.29 s
Wall time: 19.81 s
sage: s(p[2,2])
s[1, 1, 1, 1] - s[2, 1, 1] + 2*s[2, 2] - s[3, 1] + s[4]

This speaks for it being a Mac problem. (No, I don't have one to test.)

Seeing that there really seem to be two separate issues here, can we get the current patch into beta1 without waiting for the Mac issue to be resolved? I am scared of working with Sym now...

EDIT: And to verify that the other issue has been resolved, Exhibit C:

sage: s = SymmetricFunctions(QQ).s()
sage: p = SymmetricFunctions(QQ).p()
sage: %time s(p([1]*36))==sum(StandardTableaux(la).cardinality()*s(la) for la in Partitions(36))
CPU times: user 122.02 s, sys: 0.52 s, total: 122.53 s
Wall time: 129.03 s
True

Many thanks for this, Mike and Jeroen!!