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

  • 2
    $\begingroup$ 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)$. $\endgroup$ – Mateusz Kwaśnicki Sep 30 '19 at 7:22
  • $\begingroup$ 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]? $\endgroup$ – kodlu Sep 30 '19 at 21:47
  • $\begingroup$ 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. $\endgroup$ – Kurisuto Asutora Oct 1 '19 at 8:06
  • $\begingroup$ Sorry for being silly, but which consequences you make from squaring a complex-valued function? $\endgroup$ – Ilya Bogdanov Oct 1 '19 at 8:45
  • 1
    $\begingroup$ 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. $\endgroup$ – 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.

enter image description here

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]
  • $\begingroup$ Have you found any other minimizers in an analytical form? $\endgroup$ – Ilya Bogdanov Oct 1 '19 at 10:42
  • $\begingroup$ 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. $\endgroup$ – Mateusz Kwaśnicki Oct 1 '19 at 11:51
  • $\begingroup$ 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$. $\endgroup$ – Kurisuto Asutora Oct 1 '19 at 12:18
  • $\begingroup$ 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$. $\endgroup$ – David E Speyer Oct 2 '19 at 21:07
  • $\begingroup$ @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. $\endgroup$ – Mateusz Kwaśnicki Oct 2 '19 at 21:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.