# Difference Sets

Suppose we have a set $$P=\{p_1,p_2,...,p_K\}$$ where $$1\leq p_k\leq N , k=1,...,K \qquad \& \quad p_k \in \mathbb{N}$$ and $p_k$'s are distinct. 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 just saying whether there is a $P$ leading to this $A$ or not?

• – Kaveh Jul 9 '13 at 8:34

Your problem seems a special case of the turnpike reconstruction problem (for which no polynomial time algorithm is known).

See for example: Shiteng Chen, Zhiyi Huang, and Sampath Kannan, "Reconstructing Numbers from Pairwise Function Values".

Abstract: The turnpike problem is one of the few natural problems that are neither known to be NP-complete nor solvable by efficient algorithms. We seek to study this problem in a more general setting. We consider the generalized problem which tries to resolve set $A = \{a_1, a_2, ... , a_n\}$ from pairwise function values $\{f(a_i, a_j)\mid 1 \leq i, j \leq n\}$ for a given bivariate function $f$. We call this problem the Number Reconstruction problem. Our results include efficient algorithms when $f$ is monotone and non-trivial bounds on the number of solutions when $f$ is the sum....

• Thank You for your help. But there is a little difference between turnpike problem and what i asked. The difference in my question is in modulus N, while in the references it is just the distance : $|p_i - p_j|$ – Mahdi Khosravi Jul 3 '13 at 18:28

"Beltway Reconstruction Problem” - arxiv.org/pdf/1212.2386.pdf may help. Note that you're asking for the function corresponding to $P$ whose autocorrelation is the given function corresponding to $A$.

I've often thought that there's some relation to factoring, at least to for the turnpike version.

You can consider $A$ as an integer $Z=a_1x^1+a_2x^2+⋯a_Nx^N$ in base $N$, and by factoring $Z$, some of those factors would be the indicator function of $P$, i.e. would be $1$ at the $k$'th position and $0$ otherwise. So maybe the turnpike problem is in $\mathsf{BQP}$.