0
$\begingroup$

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.

$\endgroup$

1 Answer 1

4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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