# How to determine if a set is a sumset

Let $$G$$ be a commutative group (assume whatever you want on $$G$$ if needed. I am mainly interested in $$G = \mathbb{Z}/n\mathbb{Z}$$).

Let $$k$$ be a fixed integer. Let $$(a_1, \dots, a_{k^2})$$ be a list of $$k^2$$ elements of $$G$$. I am interested in the following problem: Determine if there exist:

• $$(x_1, \dots, x_{k})$$ a list of $$k$$ elements of $$G$$.
• $$(y_1, \dots, y_{k})$$ a list of $$k$$ elements of $$G$$.
• a bijection $$\sigma: [1,k] \times [1,k] \rightarrow [1,k^2]$$.
• such that: for all $$i,j=1 \dots k$$, one has $$x_i + y_j = a_{\sigma(i, j)}$$.

My question is: has this problem been studied, and what do we know about it?

For example, I would like to know if this problem is NP-complete, or if there is an algorithm to solve the problem.

There is a similar question here, but it was asked a long time ago and didn't catch much attention.

This is a variant of so-called turnpike / beltway reconstruction problems. In the case of $$G = \mathbb{Z}/n\mathbb{Z}$$ it can be solved via cyclotomic factorization by noticing that $$\sum_{i=1}^{k^2} z^{a_i} \equiv \big( \sum_{i=1}^{k} z^{x_i}\big)\cdot \big( \sum_{i=1}^{k} z^{y_i}\big)\pmod{z^n-1}.$$
Alternatively, solution can be based on spectral convolution - by noticing that pairwise differences of $$x$$'s as well as pairwise differences of $$y$$'s must have large multiplicities (at least $$k$$ each) in the multiset of pairwise differences of $$a$$'s.