# Minimization problem for convolution

Let $$g(x)$$ be a non-negative function supported on $$[0,1]$$. Let $$g \ast g$$ denote the convolution of $$g$$ with itself. Question: What is the smallest possible $$L^1(0,1)$$ norm of $$g$$, if I require that $$(g \ast g) (t) \geq 1$$ for all $$t \in [0,1]$$.

Clearly one needs $$\|g\|_1 \geq 1$$. However, $$\|g\|_1=1$$ cannot be achieved. But what is the best value that can actually be achieved?

(Maybe the optimizing function is explicitly known? Something like $$g(x) = 1/\sqrt{\pi x}$$ works and gives $$\|g\|_1 \approx 1.13$$, but probably something smaller is possible.)

• Interestingly, exactly the same norm $\|g\|_1 = 2/\sqrt{\pi} \approx 1.13$ is attained both by $g(x) = (\pi x)^{-1/2}$ and by $g(x) = \max\{(\pi x)^{-1/2},(\pi (1/2-x))^{-1/2}\} \mathbb{1}_{(0,1/2)}(x)$. – Mateusz Kwaśnicki Sep 30 '19 at 7:22
• Silly question. Is the reason that the L_1 norm lower bound of 1 cannot be achieved the normalization of the Fourier transform on [0,1]? – kodlu Sep 30 '19 at 21:47
• The Fourier transform of an indicator function is not non-negative real. In contrast, a convolution of a function with itself leads to a non-negative real Fourier transform (since we are squaring). So 1 cannot be reached exactly. However, I don't have an estimate how close to 1 one can actually get. – Kurisuto Asutora Oct 1 '19 at 8:06
• Sorry for being silly, but which consequences you make from squaring a complex-valued function? – Ilya Bogdanov Oct 1 '19 at 8:45
• I would rather say that the Laplace transform of the uniform distribution is not a square of an entire function, due to the behaviour at zeroes. – Ilya Bogdanov Oct 1 '19 at 8:49

Rick Barnard and I looked at the same problem for the auto-convolution instead of the convolution: arXiv. Our constants are a bit worse because you basically need two square-root singularities, one on each side. These types of inequalities tend to be relevant in combinatorics and they tend to be pretty hard (we discuss some in our paper). One I like a lot can be found in this MO post. (I would have commented but you need 50 reputation for that, sorry.)

(Too long for a comment.)

Numerical experiments suggests that one cannot do better than $$1 / \sqrt{\pi x}$$ (or one of the equivalent variants, the set of minimizers appears to be quite large). Here is a plot of three minimizers obtained numerically for the discrete analogue of the problem on $$\{0, 1, 2, \ldots, n - 1\}$$ with $$n = 75$$. These minimizers were found by Mathematica with three different numerical optimization methods (blue: "DifferentialEvolution", yellow: "NelderMead", green: "SimmulatedAnnealing"). The corresponding norms are 1.12145, 1.12842, 1.1265, respectively.

Mathematica code:

n = 75;
expr = Sum[x[i], {i, 0, n - 1}]/Sqrt[n];
constr = Join[
Table[Sum[x[j] x[i - j], {j, 0, i}] >= 1, {i, 0, n - 1}],
Table[x[i] >= 0, {i, 0, n - 1}]];
vars = Table[x[i], {i, 0, n - 1}];
{min1, subst1} =
NMinimize[{expr, constr}, vars, Method -> "DifferentialEvolution"];
{min2, subst2} =
NMinimize[{expr, constr}, vars, Method -> "NelderMead"];
{min3, subst3} =
NMinimize[{expr, constr}, vars, Method -> "SimulatedAnnealing"];
{min1, min2, min3}
ListPlot[{vars /. subst1, vars /. subst2, vars /. subst3},
Joined -> True, PlotRange -> All]

• Have you found any other minimizers in an analytical form? – Ilya Bogdanov Oct 1 '19 at 10:42
• I have not tried that, but apparently one can find intermediate solutions between the two that I mentioned in my comment. If I find time later today, I will see if I can figure out the details. – Mateusz Kwaśnicki Oct 1 '19 at 11:51
• I am not quite sure if that has any real significance. The numerical values I get using the same code for n=85 are {1.12831, 1.12672, 1.1287}, and for n=95 they are {1.12594, 1.13249, 1.1269}. In comparison, $2 / \sqrt{\pi} \approx 1.1284$. – Kurisuto Asutora Oct 1 '19 at 12:18
• Note that $x_k = \tfrac{1 \cdot 3 \cdot 5 \cdots (2k-1)}{2 \cdot 4 \cdot 6 \cdots 2k}$ solves $\sum_{j=0}^i x_j x_{i-j}=1$ exactly and has the same asymptotic $2\sqrt{n}/\sqrt{\pi}$. However, your data suggests that it is possible to improve on this a little for finite $n$. – David E Speyer Oct 2 '19 at 21:07
• @DavidESpeyer: This explicit solution corresponds to the green line in the plot, I believe. I am not sure if one can really improve upon this, differences between minimizers found by different algorithms seem to be within the range of admissible error. – Mateusz Kwaśnicki Oct 2 '19 at 21:16