First time here? Check out the FAQ!

Ask Your Question
1

Finding certain partitions using Sage

asked 4 years ago

klaaa gravatar image

updated 4 years ago

slelievre gravatar image

Context

A partition of is a nonempty list p=[p1,p2,...,pn] of positive integers (called the parts), of length n1.

The list is considered sorted in nondecreasing order: p1p2...pn.

Consider an integer d1. The partition p is called d-admissible if each part pi is at least 2 and inverses of the parts sum to nd1.

In formulas: 2p1 and nd1=ni=11pi.

Question

Is there a quick way to filter all partitions using Sage to find all d-admissible partitions for a fixed d1?

Note that the assumptions imply n2(d+1) but the individual terms pi 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.

Preview: (hide)

Comments

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 ( 4 years ago )

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 ( 4 years ago )

1 Answer

Sort by » oldest newest most voted
1

answered 4 years ago

jipilab gravatar image

updated 4 years ago

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...

Preview: (hide)
link

Comments

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 ( 4 years ago )

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

slelievre gravatar imageslelievre ( 4 years ago )

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

Stats

Asked: 4 years ago

Seen: 548 times

Last updated: Dec 26 '20