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

Suppose $$ P \subseteq \{1,2,\dots,N\},\quad |P| = K $$ We calculate the differences as: $$d=p_i-p_j\mod N,\quad i\ne j$$ Now let $a_d$ denote the number of occurrence of $d$ (for $d = 1, 2, \dots , N − 1$), then we have a set $$A=\{a_1,a_2,...,a_{N-1} \}$$ As you know given $P$ and $N$, it is easy to build $A$. Although given $A$ and $K$ there could be many $P$'s leading to $A$ or even no possible $P$ leading to $A$.

I want to know, given $A$ and $K$, is there any algorithm returning $P$ ?

share|improve this question
    
I changed one tag adding additive-combinatorics, removing combinatorial-group-theory. I do not (yet) have any good information. However, there are investigations on the representations functions of sumsets and difference sets (in the inetegers), which is what you ask about yet for finite cyclic groups. These investigions are rather part of Additive Combinatorics thus the retag. –  quid Jul 1 '13 at 20:42
    
cross-posted on Theoretical Computer Science. –  Kaveh Jul 9 '13 at 8:34
1  
+1 Nice question –  Babak Sorouh Jul 25 '13 at 7:44
add comment

1 Answer 1

up vote 9 down vote accepted

A keyword in this area is homometric, and a key paper this one:

Joseph Rosenblatt and Paul D. Seymour. "The Structure of Homometric Sets." SIAM. J. on Algebraic and Discrete Methods, 3, 343-350, 1982. (PDF download)

The precise question you pose---an algorithm---is called the beltway reconstruction problem in this paper:

Skiena, Steven S., Warren D. Smith, and Paul Lemke. "Reconstructing sets from interpoint distances." Proceedings 6th Symposium on Computational Geometry. ACM, 1990. (ACM link). Later (much later!) published in Discrete and Computational Geometry. Springer. Berlin, Heidelberg, 2003. 597-631.

They provide a worst-case exponential algorithm which nevertheless runs fast under probabilistic assumptions, and proved many variants NP-hard, but not your particular variant. Another, later paper on this topic is below, but I don't think it settled the 1-dimensional reconstruction problem:

R.J. Gardner, P. Gritzmann, D. Prangenberg, On the computational complexity of reconstructing lattice sets from their X-rays. Discrete Math. 202 (1999), no. 1-3, 45-71.

It may be that the computational complexity of the beltway reconstruction problem remains open...?

See also the earlier MO question, "Largest pair of homometric Golomb rulers?"

share|improve this answer
2  
The paper by Skiena et al. is available at cs.sunysb.edu/~skiena/papers/turnpike.ps –  Barry Cipra Jul 1 '13 at 22:45
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.