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 $0\in S$. Define a *additive decomposition* of the set $S$ as two sets $A$ and $B$ such that

- Both have elements rational numbers mod 1 and contain 0.
- For all $a\in A$ and $b\in B$ the sum, $(a+b)\mod{1}\in S$
- Every $s\in 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

- $A=\lbrace 0\rbrace$, $B=\lbrace 0,\dfrac{1}{2}, \dfrac{1}{3}, \dfrac{5}{6} \rbrace$
- $A=\lbrace 0, \dfrac{1}{2}\rbrace$, $B=\lbrace 0,\dfrac{1}{3} \rbrace$
- $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. $\alpha\beta=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

alladditive 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 $n\sim 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 $\alpha\mid n$. Select $\alpha$ elements of $S$ and let them be $A$. Then for each $s_i\in S$ remove $A+s_i\mod{1}$ from $S$. After running through $s_i$, the remaining elements for a candidate for $B$. If the cardinality of $B$ is $\beta$ for $\alpha\beta=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!