co.combinatorics - Wants: Polynomial Time Algorithm for Decomposing a Multiset of Rationals into Two Additive Subsets.

First, allow me to say that this problem was posed to me by a professor in the department. It is related to his research in a way that I do not know. However, since I couldn't come up with anything novel, I decided to ask here.

Alright, let $S$ be a multiset of $n$ rational numbers mod 1. Assume that $0in S$. Define a additive decomposition of the set $S$ as two sets $A$ and $B$ such that

1. Both have elements rational numbers mod 1 and contain 0.


2. For all $ain A$ and $bin B$ the sum, $(a+b)mod{1}in S$


3. Every $sin S$ is the sum of an element from each of $A$ and $B$.

Just to be perfectly clear, lets consider an example. Let $S:=lbrace 0,dfrac{1}{2}, dfrac{1}{3}, dfrac{5}{6} rbrace$, then the only additive decompositions are

1. $A=lbrace 0rbrace$, $B=lbrace 0,dfrac{1}{2}, dfrac{1}{3}, dfrac{5}{6} rbrace$


2. $A=lbrace 0, dfrac{1}{2}rbrace$, $B=lbrace 0,dfrac{1}{3} rbrace$


3. $A=lbrace 0, dfrac{1}{2}rbrace$, $B=lbrace 0,dfrac{5}{6} rbrace$

Second Example:

If $A=lbrace 0, dfrac{1}{2}, dfrac{1}{3}rbrace$, $B=lbrace 0,dfrac{1}{2}, dfrac{1}{3} rbrace$, they would be a decomposition of the set $S=lbrace 0, 0, dfrac{1}{2}, dfrac{1}{2}, dfrac{1}{3}, dfrac{1}{3}, dfrac{2}{3}, dfrac{5}{6}, dfrac{5}{6}rbrace$

At this point there are a few things to mention. First, we quickly reduce the problem to looking at subsets whose orders are $alpha$ and $beta$ s.t. $alphabeta=n$. Additionally, we can see that by the additive structure splitting into these two subsets is adequate in the sense that we can get a complete decomposition recursively by breaking the set into two.

Question:

What is the fastest algorithm you can come up with to find all additive decompositions of a multiset $S$ of order $n$?

A computer has already been used to attack the problem. In small cases, the problem is not too bad. The situation arises in the fact that in the largest cases necissary $nsim 10^5$. The professor said that an algorithm of polynomial time with respect to $n$ would be a great improvement from this current.

A word on the current algorithm. Look at the factorization of $n$. Pick $alphamid n$. Select $alpha$ elements of $S$ and let them be $A$. Then for each $s_iin S$ remove $A+s_imod{1}$ from $S$. After running through $s_i$, the remaining elements for a candidate for $B$. If the cardinality of $B$ is $beta$ for $alphabeta=n$ then we have a decomposition.

In addition to searching for a solution, I want to encourage discussion of other aspects of this problem as they may yield some interesting observations not noticed before.

Thanks in advance!

• Next rt.representation theory - Examples of applications of the Borel-Weil-Bott theorem?
• Previous pr.probability - Random values and their probability of reoccuring