small bug with PartitionsGreatestLE(0,n);

[rtange]

Observed behaviour

PartitionsGreatestLE(0,n); gives [[]] for n=0 and [] for n>0

Expected behaviour

It should be [[]] for all n>=0
This can be awkward when you need the union of the PartitionsGreatestLE(i,n) for all i>=0 and n fixed.

Copy and paste GAP banner (to tell us about your setup)

 ┌───────┐   GAP 4.12.2 built on 2022-12-19 10:30:03+0000
 │  GAP  │   https://www.gap-system.org
 └───────┘   Architecture: x86_64-pc-cygwin-default64-kv8
 Configuration:  gmp 6.2.1, GASMAN, readline
 Loading the library and packages ...
 Packages:   AClib 1.3.2, Alnuth 3.2.1, AtlasRep 2.1.6, AutPGrp 1.11, Browse 1.8.19, CaratInterface 2.3.4, CRISP 1.4.6, Cryst 4.1.25, CrystCat 1.1.10, CTblLib 1.3.4,
             curlInterface 2.3.1, FactInt 1.6.3, FGA 1.4.0, Forms 1.2.9, GAPDoc 1.6.6, genss 1.6.8, IO 4.8.0, IRREDSOL 1.4.4, LAGUNA 3.9.5, orb 4.9.0, Polenta 1.3.10, Polycyclic 2.16,
             PrimGrp 3.4.3, RadiRoot 2.9, recog 1.4.2, ResClasses 4.7.3, SmallGrp 1.5.1, Sophus 1.27, SpinSym 1.5.2, TomLib 1.2.9, TransGrp 3.6.3, utils 0.81
 Try '??help' for help. S

[ChrisJefferson]

Looking at the code, i can see this was an intentional design decision, not just an accident, see ( lib/combinat.gi:1987) : That doesn't mean it can't be changed, or better documented, or course, but given this is such old code I'd be worried about changing it in case someone else's code depends on this behaviour?

 if n = 0  then
            if m = 0  then
                parts := [ [  ] ];
            else
                parts := [  ];
            fi;
        else
            if m = 0  then
                parts := [  ];
            else
                parts := GPartitionsGreatestLE( n, m );
            fi;
        fi;

[rtange]

OK. No idea what the reasoning behind this convention was.
I would say that if you consider a partition to have all parts <=s, then you should also consider it to have all parts <=m for any m>=s. I can imagine people who used PartitionsGreatestLE weren't aware of this convention. Maybe the description in the Gap Manual should be adapted. Anyway, it's a minor thing.

[fingolfin]

Looking at the manual, "partition of $n$" is only ever defined for positive $n$. So the first issue is that either the documentation needs to be extended (to describe how $n=0$ or even negative $n$ are interpreted), or the code should be update to reject arguments outside the documented domain.

Since the behavior is not specified, it is difficult to reverse engineer what the intent behind the current behavior of PartitionsGreatestLE is. But let's try...

First, one might of course try to extrapolate from the definition in the manual. E.g. one could argue that 0 can be decomposed into a "sum" with zero summands, and then [] would indeed be a valid partition -- and indeed, Partitions(0); returns [ [ ] ].

Next I'd also expect the following relations to hold, no matter what the exact definition is:

1. PartitionsGreatestLE(n,k) $\subseteq$ PartitionsGreatestLE(n,k+1)
2. Partitions(n) = PartitionsGreatestLE(n,n)
3. Difference(PartitionsGreatestLE(n,k+1),PartitionsGreatestLE(n,k)) = PartitionsGreatestEQ(n,k+1)

All of these are violated here.

The minimal "fix" to support this would indeed be to let PartitionsGreatestLE(0,k) always return [[]].

So let's go back to the git history of this function. It was never really changed since it was added by Max N. back in August 2001 (for anyone with access to the "private" history, it is in commit 6007aab576230b6869dfe83198f027bba9685d18 there). Back then the old Partitions was renamed to PartitionsRecursively (which still exists) and new code was added to implement Partitions as it is today; and as a bonus side effect, PartitionsGreatestLE was also added. Only a call to Error was changed, otherwise it looked like it does today:

InstallGlobalFunction( PartitionsGreatestLE,
function(n,m)
    local parts;
    if not(IsInt(n) and IsInt(m)) then
        ErrorNoReturn("usage: PartitionsGreatestLE( <n>, <m> )");
    elif n < 0 or m < 0 then
        parts := [];
    else
        if n = 0  then
            if m = 0  then
                parts := [ [  ] ];
            else
                parts := [  ];
            fi;
        else
            if m = 0  then
                parts := [  ];
            else
                parts := GPartitionsGreatestLE( n, m );
            fi;
        fi;
    fi;
    return parts;
end);

Now, I can't help but notice the striking similarity to the code in PartitionsRecursively:

InstallGlobalFunction(PartitionsRecursively,function ( n, arg... )
    local   parts, k;
    if Length(arg) = 0  then
        parts := PartitionsA( n, n, [], 1 );
    elif Length(arg) = 1  then
        k := arg[1];
        if n = 0  then
            if k = 0  then
                parts := [ [  ] ];
            else
                parts := [  ];
            fi;
        else
            if k = 0  then
                parts := [  ];
            else
                parts := PartitionsK( n, n, k, [], 1 );
            fi;
        fi;
    else
        Error("usage: Partitions( <n> [, <k>] )");
    fi;
    return parts;
end);

I can't help but notice how strikingly similar that code is (also OrderedPartitions looks almost the same as Partitions). OK, in one we have k and in the other m, and an error check is moved etc -- but overall, I wonder if this isn't a simple case of copy&paste?

---

There are no calls to PartitionsGreatestLE in GAP itself nor in any distributed package. As such, I think a change to it actually wouldn't be too bad -- but IMHO such a change should then be accompanied by at least a minor improvement to the documentation.

[ChrisJefferson]

That sounds reasonable to me. @rtange , would you be interested in writing some better documentation, and tests as well to check all these cases (which is probably more work than the actual fix itself)? If you don't fancy that let me know, but I thought I'd suggest it as you've most recently thought about this :)

[rtange]

It seems to me that the documentation (i.e. the manual) matches the proposed new version better than the old one.
But I suppose one can add one example including the empty partition:
r:=3;;n:=2;;Concatenation(List([0..r],i->PartitionsGreatestLE(i,n))); which should give
[ [ ], [ 1 ], [ 1, 1 ], [ 2 ], [ 1, 1, 1 ], [ 2, 1 ] ], but gives at the moment [ [ 1 ], [ 1, 1 ], [ 2 ], [ 1, 1, 1 ], [ 2, 1 ] ].
I think it's more important to add some annotation to any changes made in combinat.gi.

I can do the testing, provided I can just paste in the new combinat.gi file and not redo an installation.

I wonder whether PartitionsRecursively should also be adapted, since it has the same issue.
Of course it is not in the documentation, but it probably should be consistent with PartitionsGreatestLE (i.e. give the same output).
Are there any calls to PartitionsRecursively in GAP itself or in any distributed package?