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

Question

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

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

1. $A=\lbrace 0\rbrace$, $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. $\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 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 $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!

Answer 1

Any general algorithm for this problem will require exponential time. In fact, just writing down the answer can take exponential time in some cases.

For example, suppose that $n=2m$ for some odd $m$, and let $S=\lbrace 0,\frac{1}{n},\frac{2}{n},\ldots,\frac{n-1}{n}\rbrace$. Start with $A=\lbrace 0,\frac{1}{2} \rbrace$ and $B=\lbrace 0,\frac{1}{m},\frac{2}{m},\ldots,\frac{m-1}{m} \rbrace$. Adding $0$ or $1/2$ to each nonzero element of $B$ independently results in $2^{m-1}$ other sets $B'$ that when matched with $A$ still form an additive decomposition of $S$. So there are at least $2^{m-1} = 2^{n/2-1}$ additive decompositions of $S$.

Answer 2

Going off of fedja's comment I'll assume you want unique representations. In that case, one small observation is as follows: if $d$ is the least common denominator of the elements of $S$ and $S = \{ \frac{s_1}{d}, ... \frac{s_n}{d} \}$, then the problem is equivalent to determining the possible factorizations of $x^{s_1} + ... + x^{s_n}$ into polynomials with coefficients zero or one in $\mathbb{Z}[x]/(x^d - 1)$. These factorizations are, in turn, at least controlled by factorization in $\mathbb{Z}[\zeta_d]$, so it's possible that known algorithms in algebraic number theory might be of use.