# Sufficient conditions for the convexity of the discrete Fourier transforms

Let $$f : [0,2\pi] \to \mathbb{R}$$ be some function. Then the discrete Fourier transform of $$f$$ when sampled at $$2\pi i/N$$ is then given by $$X_n := \sum_{i=0}^{N-1}\cos\left(\frac{2\pi n i}{N}\right)f\left(\frac{2\pi i}{N}\right), \quad n = 1,\ldots,N-1.$$

Question: What conditions are sufficient on $$f$$ such that there exists a convex function $$G : [0,1] \to \mathbb{R}$$ with $$G(n/N) = X_n$$? That is, when is the DFT a discrete convex function with respect to $$n$$?

• In the references post above it was shown that $$f(x) = |\pi-x|$$ defies this claim.

Notes: This question is related to the recent post: Convexity of discrete Fourier transform

• In view of the previous answer, the smoothness of $f$ will not be enough, because on any finite subset of $[0,2\pi]$ any given function coincides with a smooth function. Also, do you really want necessary (rather than sufficient) conditions on $f$? Dec 14 '20 at 14:05
• @IosifPinelis Thank you, yes, I assume then, some condition on the second derivative would do the job. It seems possibly that the function $|\pi - x|$ flips too quickly at $\pi$ and a slower transition from $f' < 0$ to $f' > 0$ may be necessary. Also, right now, a sufficient condition would be interesting, I will update the question accordingly. Dec 14 '20 at 14:49

Even if you assume that $$f$$ is a convex function symmetric about $$\pi$$ and having a convex second derivative, it is still not enough for there to exist a convex function $$G\colon[0,1]\to\mathbb{R}$$ with $$G(n/N)=X_n$$ for $$n=1,\dots,N-1$$.

For instance, let $$f(x):=\frac{(a-x)_+^3+(x-2\pi+a)_+^3}{(2\pi/N)^3}$$ for $$x\in[0,2\pi]$$, where $$a\in\mathbb R$$ and $$u_+:=\max(0,u)$$. Then $$f$$ is a convex function symmetric about $$\pi$$ and having a convex second derivative. However, if $$N=10$$, $$a=2\pi l/N$$, and $$l=2$$, then $$X_n=16 + 2\cos\frac{\pi n}5,$$ which is not convex in $$n=1,\dots,10-1$$, as seen from this (connected) graph $$\{(n,X_n)\colon n=1,\dotsc,9\}$$: More specifically, here $$X_2\not\le(X_1+X_3)/2$$.

• Excellent, this is very interesting. It seems that the convexity of $X_n$ is broken by $X_1$ and $X_N$, or terms nearby, possibly due to insufficient blow up of the function $f$ near $0$ and $2\pi$. You can see that if $f(x) = \begin{cases}\frac{1}{\sin(x/2)} & 0 < x < 2\pi \\ c & x = 0,2\pi \end{cases}$ for some constant $c\in\mathbb{R}$, then one obtains that the DFT is convex. I am wondering what would be sufficient for a general $f$ to have a convex DFT. Dec 15 '20 at 9:27
• @Orbital : I think you would likely get more informative answers if you could tell us what kind of functions $f$ are of interest to you, rather than going backwards. BTW, as explained in my previous answer, no blowup conditions for $f$ near $0$ and $2\pi$ can suffice by themselves. Dec 15 '20 at 16:02
• +1. Would you be so kind as to reveal how you discovered the counterexample?
– Hans
Sep 11 at 0:18
• @Hans : One can see that any smooth convex function symmetric about $\pi$ and having a convex second derivative is a mixture of the constant function $1$, the function $u\mapsto(u-\pi)^2$, and functions $f$ as in the first display in the answer; cf. e.g. formula (3.2) in projecteuclid.org/journals/annals-of-statistics/volume-22/… Sep 12 at 1:10