Assume: $$ P \subseteq \{1,2,\dots,N\},\quad |P| = K, \qquad x \in \mathbb{R}_+^K , \qquad w = e^{-j\frac{2\pi}N} $$ and, $$ f(l) = \sum_{i=1}^K \sum_{j=1}^K x_i x_j w^{(p_i-p_j)l} $$ I am going to find $x$ and $P$ such that these equalities are satisfied: $$ f(1) = f(2) = \cdots = f(N-1) $$ We can change this problem to an easier problem by defining : $$ S_d = \{(i,j) \quad | \quad p_i - p_j \mod N = d\}, \qquad d=0,1,\cdots,N-1 $$

So :

$$ f(l) = \sum_{d=0}^{N-1} \underbrace{\sum_{(i,j) \in S_d} x_i x_j}_{g[d]} \space w^{ld} $$

Now suppose : $$ S =S_1 \cup S_2 \cup \cdots \cup S_{N-1} = \{(i,j), \quad 1\leq i,j \leq K, \quad i \ne j \} $$

Using properties of Discrete Fourier Transform it can be shown that this problem turns to the problem :

$$ g[d] = \sum_{(i,j) \in S_d} x_i x_j = \frac1{N-1} \sum_{(i,j) \in S} x_i x_j\quad, \qquad d=1,2,\cdots,N-1 $$

i.e. the problem becomes finding partition(s) of $S$ and $\{x_i\}_{k=1}^K$ (up to a scale!) satisfying the above equalities.

If for simplicity we set the values $x_1=x_2=\cdots=x_K = 1$, the problem will reduce to this:

$$ |S_d|=\frac{K(K-1)}{N-1}, \quad d=1,2,\cdots,N-1 $$ so, for the case of $\frac{K(K-1)}{N-1}$ being integer, the solution for $x$ and cardinality of partitions is found. Any idea for the case it is not integer? Even finding cardinality of partitions would be great!

Any contribution would be appreciated.

Edit: I reached the result that the solution of this problem for $|S_d|$ is $\{|S_d|\}$ with minimum variance under constraint of $\sum_{d=1}^{N-1}|S_d| = K(K-1)$ which leads to some of them being $\lfloor \frac{K(K-1)}{N-1}\rfloor$ and the others $\lfloor \frac{K(K-1)}{N-1}\rfloor+1$.

  • 3
    $\begingroup$ The question is a better fit for Math.SE, so I'm voting to close the copy that is here. See also here: meta.mathoverflow.net/questions/543/… $\endgroup$ Jul 25, 2013 at 10:56
  • $\begingroup$ @DanielMoskovich You know I think here it could gather more attention since here there are less number theorists, but they pay more attention to questions asked here! $\endgroup$ Jul 25, 2013 at 10:58
  • $\begingroup$ Let's test this conjecture. $\endgroup$ Jul 25, 2013 at 12:39
  • $\begingroup$ @WlodzimierzHolsztynski Thank you for your comment. Which conjecture do you mean? $\endgroup$ Jul 25, 2013 at 12:41
  • 1
    $\begingroup$ We definitely should close one of the two questions, but I actually think this might be fairly hard. I'll make some easy observations in the next comment. $\endgroup$ Jul 25, 2013 at 16:03

1 Answer 1


These are just obvious observations that are too long to fit in a comment.

Define $g(z) = \sum x_i z^{p_i}$. The goal is that, for $\omega$ a primitive $N$-th root of unity, we have $$g(\omega) g(\omega^{-1}) = g(\omega^2) g(\omega^{-2}) = \cdots = g(\omega^{N-1}) g(\omega^{-(N-1)})$$ or, equivalently, $$|g(\omega)| = |g(\omega^2)| = \cdots = |g(\omega^{N-1})|$$.

Speaking loosely, we want a function on the unit circle which is very nearly constant norm, and whose Fourier transform is sparse.

Taking $K$ to be a cyclic difference set and all the $x_i$ equal to $1$ obviously gives a solution. Also, we effectively have $N/2$ constraints (since $|g(\omega^j)| = |g(\omega^{-j})|$, so I would expect that the problem is solvable for any $P$ of size $N/2$, and is probably not solvable for most $P$ of size less than $N/2$.

After that, it is not clear what to say. It might help if the OP clarified what sort of constructions are good for his purposes. (Why not just take all the $x_i=1$ and use a cyclic difference set, for example?)

  • $\begingroup$ As you said I've written in the question the solution of $x_i=1$ lead to cyclic difference sets , but since $\frac{K(K-1)}{N-1}$ is not always integer, always there is not such a solution available . Since usually this is not the case , it couldn't be considered a general solution, and my problem remains still unsolved. Also, Why do you expect it is not solvable for most $P$ of size less than $\frac N2$ $\endgroup$ Jul 25, 2013 at 16:20
  • $\begingroup$ Naive parameter counting. We have $P$ variables and $N/2$ constraints. $\endgroup$ Jul 25, 2013 at 16:58
  • $\begingroup$ Yes, You are right. But do you have any idea to find those few possible solutions, beside the cyclic difference set one? $\endgroup$ Jul 25, 2013 at 17:10
  • $\begingroup$ Through simulations I found that the solution for $P$ is a set which is close to cyclic difference sets. Close in the sense that number of most of differences are equal, but some of them differ at most by one. But I'm looking for an analytic solution. $\endgroup$ Jul 25, 2013 at 18:15

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.