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

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$.

share|improve this question
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/… –  Daniel Moskovich Jul 25 '13 at 10:56
@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! –  Mahdi Khosravi Jul 25 '13 at 10:58
Let's test this conjecture. –  Wlodzimierz Holsztynski Jul 25 '13 at 12:39
@WlodzimierzHolsztynski Thank you for your comment. Which conjecture do you mean? –  Mahdi Khosravi Jul 25 '13 at 12:41
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. –  David Speyer Jul 25 '13 at 16:03
add comment

1 Answer

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?)

share|improve this answer
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$ –  Mahdi Khosravi Jul 25 '13 at 16:20
Naive parameter counting. We have $P$ variables and $N/2$ constraints. –  David Speyer Jul 25 '13 at 16:58
Yes, You are right. But do you have any idea to find those few possible solutions, beside the cyclic difference set one? –  Mahdi Khosravi Jul 25 '13 at 17:10
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. –  Mahdi Khosravi Jul 25 '13 at 18:15
add comment

Your Answer


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.