How to do such a partitioning?

Question

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

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