Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question
2  
It is unclear whether you require the uniqueness of the representation of every number in $S$ in the form $a+b$. You do not in the list of properties but your remark about cardinalities strongly suggests that you do. Can you clarify this? –  fedja Feb 2 '10 at 5:48
    
@fedja Uniqueness is not necessary, I had made the mistake of assuming S was a set. In reality it is a multiset. Thank you for your relevant comment, I have corrected the question and added an example of the situation which you pointed out. Also, I added some details on the current method he is using to decompose S. –  B. Bischof Feb 2 '10 at 16:49
    
@B.: The current answers are just as relevant now as before your edit. –  Reid Barton Feb 2 '10 at 17:34
add comment

2 Answers

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

share|improve this answer
    
thank you for this answer, but there was an error in my original question. Please take another look, now that it has been fixed. –  B. Bischof Feb 2 '10 at 16:50
    
@B.Bischof: I think that my response answers the new version of your question too, as Reid said. –  Bjorn Poonen Feb 6 '10 at 7:23
add comment

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.

share|improve this answer
    
I should also add that I guess this is a reasonable heuristic argument that this problem is at least as hard as factoring. –  Qiaochu Yuan Feb 2 '10 at 6:14
    
I have fixed the previous error, sorry for the confusion. However, thanks for this observation. –  B. Bischof Feb 2 '10 at 16:50
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.