Ask Your Question

Defining vector partition functions in sage

asked 2021-07-21 15:16:53 +0200

mathstudent gravatar image

updated 2021-07-22 18:16:55 +0200

I want to define a vector partition function starting from a given list of vectors. For example, let's say I have vectors $v_1,v_2,v_1+v_2$ where $v_1,v_2$ are linearly independent and I want to list all the partitions using these three vectors. For convenience I can define the set of positive vectors to be the set ${kv_1+lv_2:k,l \in \mathbb{Z}_{\geq 0} } $, and for the program to be finite I am okay with taking $k,l$ only up to some fixed number, for example I have taken 2 below. I am trying as follows:

sage: v1,v2 = var('v1','v2')
sage: S = [v1,v2,v1+v2]
sage: Pos = [k*v1+l*v2 for k in [0,1,2] for l in [0,1,2]]
sage: def par(x):
sage:       p(x) = []
sage:       for y in S : 
sage:            if x-y in Pos: 
sage:               for z in p(x-y):
sage:                    n = z + y
sage:                    if n not in p(x):
sage:                        p(x)=p(x)+n
sage:       return p(x)

This does not work. I don't understand why. Somehow sage: par(v1) gives () as answer and sage: par(v1+v2) gives TypeError: Must construct a function with a tuple (or list) of variables.

Please help me out.


Vector partition function: I have a fixed set $S={ v_1,...,v_n} $ of vectors, let $v$ be a vector. An expression of the form $v=c_1v_1+...+c_nv_n$ with $c_i\in \mathbb{Z}_{\geq 0}$ is called a partition of $v$. $Par(v)$ be the set of partitions of $v$. I want to find out this set at the end of the program.

Roughly, what I wanted was: Start with L an empty list/set. Find $P(v-v_i)$ for each $i$. For each partition of $v-v_i$ attach $v_i$ to make it a partition of $v$. Now check whether the new partition thus formed is already counted before or not, if not then enter it in L.

edit retag flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted

answered 2021-07-21 19:22:01 +0200

updated 2021-07-22 19:49:55 +0200

  • The line p(x) = [] attempts to construct a symbolic function, and when you call par(v1+v2), it calls p(v1+v2) which tries to construct a symbolic function without the correct form for the arguments. I think a dictionary would be better for this.

  • Is p supposed to be local to the function, or are its values supposed to be remembered from one call to the next?

  • You define p(x) = [], and then you never provide a way to change this: the main loop says for z in p(x-y), but since p(x-y) starts off empty, the loop will never do anything.


You need a place to start: p(x) can't be empty for every x. You also need to know when you're done. Here is a start, not sure if it works:

p = {}

def initialize_p():
    for x in Pos:
        if x:
            # The nonzero vectors should start with the trivial partition.
            p[x] = [[x]]
            # if x is zero, don't include it in the partition.
            p[x] = []

def par(x):
    for y in S:
        if x-y in Pos:
            for z in p[x-y]:
                # z should be a list, so add a new element to that list
                n = z + [y]
                # sort n so we don't get both [v1, v2] and [v2, v1]
                n = sorted(n, key=str)
                if n not in p[x]:
    return p[x]

I put this in a file called vec.sage and did:

sage: var('v1, v2')
sage: S = [v1, v2] # why include v1+v2?
sage: Pos = [k*v1+l*v2 for k in [0,1,2] for l in [0,1,2]]

sage: %attach vec.sage
sage: initialize_p()
sage: par(v1)                                                                                                                
sage: par(v1+v2)                                                                                                             
[[v1 + v2], [v1, v2]]
sage: par(2*v1+v2)                                                                                                           
[[2*v1 + v2], [v1, v1 + v2], [v1, v1, v2], [2*v1, v2]]
edit flag offensive delete link more


Understood. I wanted to get all partitions by somehow subtracting one part and knowing the smaller partitions. Do you have any suggestions for fixing the algorithm?

mathstudent gravatar imagemathstudent ( 2021-07-22 10:58:00 +0200 )edit

You'll have to explain what you mean by a vector partition function, and how you hope the algorithm would work for your small example with Pos as defined.

John Palmieri gravatar imageJohn Palmieri ( 2021-07-22 17:25:16 +0200 )edit

Edited post for clarity... please check.

mathstudent gravatar imagemathstudent ( 2021-07-22 18:16:52 +0200 )edit

See my edit. Another option is to make the function par recursive: when computing par(x), call par(x-y). par(0) should return [], maybe par(v) should return [v] when v is either v1 or v2.

John Palmieri gravatar imageJohn Palmieri ( 2021-07-23 05:54:45 +0200 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2021-07-21 15:16:53 +0200

Seen: 233 times

Last updated: Jul 22 '21