MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Consider vector X =( X_1 ... X_N), consider the discrete Fourier transform $Y=F(X)$.

I am interested to minimize $|Y|_{\infty}$, by permutation of numbers X_i, how to do it ?

Here $|Y|_{\infty}$ is infinity norm of the vector Y i.e. just the maximum of absolute values of components of Y.

More close to life problem is a little more complicated: my numbers X_i are splited at several subsequences such that |X|=const in each subsequence. And I am allowed to make "block" permutations of these subsequences. The goal is the same as to minimize $|Y|_{\infty}$

Background: roughly speaking the OFDM based ( = most advanced) radio telecommunication systems (LTE, WiMax, new WiFi) make the Fourier transform before transmitting data symbols to the space. Average power is fixed, but people care also about the maximal instant power, which they do not want to be big. Instant power is just the maximal component of the vector.

share|cite|improve this question

I don't see how you can do anything non-trivial without additional restrictions on $X$. The trivial estimate is $|Y|{\infty} \leq |X|_{1}$ (assuming there is no normalizing factor in your definition of F, which, in any event, doesn't change the argument). However, taking $X=(1,1,\ldots 1)$ one sees that this is in fact an equality (for any reordering of the $X_i$'s).

share|cite|improve this answer
May be I did not formulate the question correctly. I mean for GIVEN sequence of (X_1 ... X_N) how to find permutation that minimize ... ? Of course, if X_i=X_j then nothing can be done. – Alexander Chervov Oct 15 '12 at 11:38
Also, if X_i are positive real than |Y|_inf = |X|_1 , and permutation will not have any effect. – Alexander Chervov Oct 15 '12 at 11:40
That was exactly my point. If there is a choice of X such that no reordering improves over the trivial estimate, what do you expect an answer to look like? – Mark Lewko Oct 15 '12 at 23:38
What about other X such that reordering will work? How to choose optimal or suboptimal reordering? – Alexander Chervov Oct 29 '12 at 16:28

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.