Ask Your Question

Finding certain partitions using Sage

asked 2020-12-11 18:25:45 +0200

klaaa gravatar image

updated 2020-12-26 23:53:01 +0200

slelievre gravatar image


A partition of is a nonempty list $p = [p_1, p_2, ..., p_n]$ of positive integers (called the parts), of length $n \ge 1$.

The list is considered sorted in nondecreasing order: $p_1 \le p_2 \le ... \le p_n$.

Consider an integer $d \ge 1$. The partition $p$ is called $d$-admissible if each part $p_i$ is at least $2$ and inverses of the parts sum to $n - d - 1$.

In formulas: $2 \le p_1$ and $n - d - 1 = \sum \limits_{i=1}^{n} {\frac{1}{p_i}}$.


Is there a quick way to filter all partitions using Sage to find all $d$-admissible partitions for a fixed $d \ge 1$?

Note that the assumptions imply $n \le 2(d+1)$ but the individual terms $p_i$ might get quite large (for $d=2$ the largest is already 42), which makes it very complicated to obtain a program that is quick and works for large $d$.

For example for $d=1$ there are four 1-admissible partitions, namely: [2,2,2,2], [3,3,3] ,[2,4,4] and [2,3,6]. For $d=2$ there are eighteen 2-admissible partitions.

edit retag flag offensive close merge delete


The partition [2,2,2,2] does not seem to be 1-admissible. The sum of the inverse gives 2 which is not 8 - 1 - 1 = 6. Is it 1-admissible when k-d-1 is the sum of the inverse of their parts?

jipilab gravatar imagejipilab ( 2020-12-16 13:31:22 +0200 )edit

Sorry, in an early edit of this question I misunderstood the notation and thought $n$ was the sum of the parts, rather than the number of parts. Restored now.

slelievre gravatar imageslelievre ( 2020-12-26 23:53:48 +0200 )edit

1 Answer

Sort by ยป oldest newest most voted

answered 2020-12-16 13:44:16 +0200

jipilab gravatar image

updated 2020-12-16 14:09:45 +0200

If I adapt the problem to the comment, it is possible to use integer points in polyhedra. First, one creates the polyhedron of partitions in chamber. Then, one fixes the sum of the parts to be N in the coord_sum. Taking the intersection and then the integral points, we get at least the potential partitions. Then, one can iterate to test the inverse sum and the minimal part.

For d=1 I get:

sage: d = 1 
....: bound = 25
....: adm_part = set() 
....: for k in range(2,2*(d+1)+1): 
....:     chamber = Polyhedron(rays=[[0]*_+[1]*(k-_) for _ in range(k)],backend='normaliz') 
....:     for N in range(2*k,bound): 
....:         coord_sum = Polyhedron(eqns=[[-N]+[1]*k],backend='normaliz') 
....:         start_partitions = (chamber & coord_sum).integral_points() 
....:         for p in start_partitions: 
....:             non_zero = tuple([_ for _ in p if _ > 0]) 
....:             if min(non_zero) >= 2 and sum([1/_ for _ in non_zero]) == len(non_zero) - d - 1: 
....:                 if non_zero not in adm_part: 
....:                     adm_part.add(non_zero) 
....:                     print(non_zero) 
(3, 3, 3)
(2, 4, 4)
(2, 3, 6)
(2, 2, 2, 2)

If my code is not correct, one may still modify it to get the proper definition of admissibility...

edit flag offensive delete link more


Thank you very much. Sorry, there was a mistake in my formula. In the sum there is an n and not a k.

klaaa gravatar imageklaaa ( 2020-12-26 20:17:04 +0200 )edit

Sorry @klaaa it was me who messed up your question which originally had the correct formula. Fixed now.

slelievre gravatar imageslelievre ( 2020-12-26 23:55:34 +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: 2020-12-11 18:25:45 +0200

Seen: 463 times

Last updated: Dec 26 '20