5
$\begingroup$

Suppose that $f \colon [0, 1] \to \mathbb{R}$ is a $C^\infty$ function satisfying the constraints $$ f(0) = f'(0) = f(1) = f'(1) = 0, \quad \mbox{and} \quad \int_0^1 (f''(y))^2 \, dy \leq 1. $$ Denote this class of functions $\mathcal{F}.$

I want to know what is the best approximation one can give of the $L^2$ norm of $f$ in terms of the evaluation of $f$ on a uniform grid. Basically, I want to know what we can say about $$ \sup_{f \in \mathcal{F}} \Big\{\int_0^1 f^2(y) \, dy - \frac{1}{n}\sum_{i=1}^n f^2(i/n) \Big\}. $$ My conjecture is that the error should go down as $n^{-4}$ since the quadratic interpolant should have this error, but I had difficulty checking this to be the case.


Addendum: I have added an additional periodicity constraint, primarily because as indicated by the argument from Iosif below, one can apply the Euler-Maclaurin formula to obtain $n^{-p}$ for any $p$ provided that $f \in C^\infty$ is periodic on $[0, 1]$. Hence, let's make the problem easier. We assume periodicity for the function and first order derivative. The naive application of Euler-Maclaurin gives an upper bound on the quantity above of $O(1/n^2)$ uniformly over the class. However, I cannot construct an $f$ that actually achieves this, subject to my constraints.

$\endgroup$
9
  • $\begingroup$ I don't think this sounds plausible. If you just take any increasing function, $f(x)=cx^3$, say, then you are comparing the integral with its upper Riemann sum, and on each interval of size $1/n$ not close to zero, you are making an error $\simeq 1/n^2$ for an overall error of $1/n$. $\endgroup$ Commented Feb 25, 2023 at 1:12
  • $\begingroup$ Yes, with no absolute values you'd need a decreasing function $f^2$ (to make the sum the lower Riemann sum) for a $1/n$ error, which however is prevented by your assumptions. $\endgroup$ Commented Feb 25, 2023 at 17:38
  • $\begingroup$ Also, we don't really need your calculation since $0$ is an obvious upper bound for my function, if I had noticed the absence of an absolute value. $\endgroup$ Commented Feb 25, 2023 at 18:21
  • $\begingroup$ Have you tried to begin with $x^2$ and then to glue the upside down parabola (with the leading coefficient $-1$, say) to it extended until it hits $0$ so that an extra $1/2f(1)^2$ would be useless? $\endgroup$
    – fedja
    Commented Feb 25, 2023 at 20:28
  • $\begingroup$ I still think, on closer reflection, that this is implausible. For example, if $g(x)=x^N$, then the discrepancy between the integral $\int_0^1 g(x)\, dx$ and its upper Riemann sum is $-1/(2n)+N/(12n^2)+O(n^{-3})$. So if we follow up such a function with its decreasing counterpart on $[1,2]$, but with a different $N$, then the $\simeq 1/n^2$ won't cancel and we expect an error $\gtrsim 1/n^2$. Of course, we need an intermediate piece for a smooth transition, but I wouldn't expect this to somehow cancel out the $1/n^2$ contribution we already have, independently of its shape. $\endgroup$ Commented Feb 25, 2023 at 22:11

1 Answer 1

2
$\begingroup$

By the Euler–Maclaurin formula (with $p=4$, $m=0$, and $g(x):=\frac1n\,f^2(\frac xn)$ in place of $f(x)$ there in the formula), $$d_n(f):=\int_0^1 f^2(y) \, dy - \frac{1}{n}\sum_{i=1}^n f^2(i/n) \\ =-\frac1{2n}\,f^2(1)-\frac1{6n^3}\,f(1)f'(1)+O(n^{-4})\le O(n^{-4})$$ for each $f\in\mathcal F$.


However, one cannot get a constant factor $O(n^{-4})$ good for all $f\in\mathcal F$ at once. Specifically, for $n\ge2$, $$\sup_{f\in\mathcal F}d_n(f)\ge d_n(f_n) =\frac{1}{\pi ^4 (2 n+1)^2}\sim\frac1{4\pi^4 n^2} \tag{1}\label{1}$$ as $n\to\infty$, where $$f_n(x):=\frac1{\pi^2}\, \Big(\sin (\pi x)-\frac{\sin (\pi (2 n+1) x)}{(2 n+1)^2}\Big),$$ so that $\int_0^1(f_n'')^2=1$ and $f_n(0)=0=f_n(1)$.

(Note that $f_n\notin\mathcal F$, since $f_n'(0)\ne0$ and $f_n'(1)\ne0$. However, $f_n$ can be approximated however closely by functions in $\mathcal F$ with respect to the norm given by the formula $$\|f\|^2=\max_{[0,1]}(f^2)+\int_0^1(f'')^2.$$ More generally, this approximation shows that $\sup_{f\in\mathcal F}d_n(f)$ will not change if the conditions $f'(0)=0=f'(1)$ are removed from the definition of $f\in\mathcal F$.)


On the other hand, even without the conditions $f(1)=f'(1)=0$ on $f\in\mathcal F$ (added later by the OP), one can see that $$\sup_{f\in\mathcal F}d_n(f)\le \frac1{72 n^5}+\frac1{12 n^2}\sim\frac1{12 n^2} \tag{2}\label{2}$$ as $n\to\infty$, so that the lower bound on $\sup_{f\in\mathcal F}d_n(f)$ in \eqref{1} is sharp up to a universal positive real constant factor.

To get \eqref{2}, use the Euler–Maclaurin formula again, but this time with $p=2$, which together with the condition $\int_0^1(f'')^2\le1$ yields $$d_n(f)\le-\frac1{2n}\,f^2(1)-\frac1{6n^3}\,f(1)f'(1)+\frac1{12 n^2} \tag{3}\label{3}$$ for all $f\in\mathcal F$. Using the condition $\int_0^1(f'')^2\le1$ again, now together with the condition $f'(0)=0$, we get $|f'(1)|\le\int_0^1|f''|\le1$, whence $$-\frac1{2n}\,f^2(1)-\frac1{6n^3}\,f(1)f'(1) \le-\frac1{2n}\,f^2(1)+\frac1{6n^3}\,|f(1)|\le\frac1{72 n^5},$$ so that \eqref{2} follows from \eqref{3}.

$\endgroup$
7
  • $\begingroup$ I'm afraid you are using the control over more derivatives than are given to you (all you know is that $f''\in L^2$) in this argument. The truth for the original question seems to be $n^{-3}$, not $n^{-4}$ as well as the precision in the Euler-Maclaurin without the control over the third derivative. But you are absolutely right that some version of Euler-Maclaurin is the key. $\endgroup$
    – fedja
    Commented Feb 26, 2023 at 20:28
  • $\begingroup$ @fedja : I used the condition that $f$ is $C^\infty$. Per this argument, the constant factor in $O(n^{-4})$ may depend on $f$. As noted in the answer, getting a constant factor in $O(n^{-4})$ good for all $f$ at once would require more care. $\endgroup$ Commented Feb 26, 2023 at 21:22
  • $\begingroup$ @DrewBrady : According to en.wikipedia.org/wiki/… , here for the remainder $R_p$ in the Euler–Maclaurin formula we have $|R_p|=O(n^{-p})$, so that I can actually take $p=4$ (as is now done) to get $|R_p|=O(n^{-4})$. $\endgroup$ Commented Feb 26, 2023 at 21:32
  • 1
    $\begingroup$ The consideration is now quite complete: One cannot get a constant factor $O(n^{-4})$ good for all $f$ at once. $\endgroup$ Commented Feb 27, 2023 at 6:40
  • $\begingroup$ @IosifPinelis, thanks. I checked the calculations, and this looks right to me. Would you mind explaining somewhat your construction? Is the appearance of sinusoids related to some Fourier interpretation of the (incorrectly) conjectured inequality? $\endgroup$
    – Drew Brady
    Commented Feb 27, 2023 at 7:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .