# Giving Uniform Bound on Differences of Sums of Converging Polynomials

The title does not quite capture the essence of the difficulty, please allow me to be more explicit here.

I thought of this question when I was trying out an open problem by Ovidiu Furdui(See problem 1.32 b of Furdui).

The problem reads(I changed some notations to make it more concise):

Suppose $f \in C([0,1])$, define $x_{n}=\sum_{k=1}^{n-1} f(\frac{k}{n})$, here n is a non-zero natural number. For $n \ge2$, define $y_{n}=x_{n}-x_{n-1}$. The question is , does the sequence $y_{n}$ converge under this assumption?

Obviously, if $y_{n}$ were to converge at all, then it has to converge to $\int_{0}^{1}f(x)dx$. This is a direct consequence of the Stolz's theorem(https://en.wikipedia.org/wiki/Stolz%E2%80%93Ces%C3%A0ro_theorem) applied to the regular partition of riemann sum of $f$.

What is interesting is that this sequence actually converges if we suppose $f$ is $C^1$. Furdui himself saw this as well. I will only give sketches.

Observe $\frac{k}{n+1} \le \frac{k}{n} \le \frac{k+1}{n+1}$ for the k we care about.

By Mean Value theorem, $f(\frac{k}{n+1})-f(\frac{k}{n})=-\frac{k}{n(n+1)}f^\prime(\theta_{n,k})$ ,where $\theta_{n,k} \in (\frac{k}{n+1},\frac{k}{n})$.

Take difference of $y_{n}-f(1)$ and $\frac{1}{n}$ of riemann sum of $-xf^\prime(x)$ with partition defined by $\frac{k}{n+1}$, by uniform continuity of $f^\prime$ on $[0,1]$ (which we have by compactness and continuity), we see this difference converges to 0. Integrate by parts gives the desired result.

Now, we see there is no way the above approach is going to work if $f$ is merely continuous. In fact, straightforward imitation will not work even if $f$ is assumed to be differentiable.

However, numerical tests on several bad functions, including Cantor function, show the result may remain valid under the continuity hypothesis. This suggests some approximation arguments may help.

We use $x_{n}(f)$ to mean the sequence defined by a fixed $f$. I think I tried to approximate $f$ uniformly by a sequence of polynomial $P_i$. I wanted to somehow make use of the results on the $C^1$ case. Here is how triangle inequality leads to a dead end:

$|y_{n}(f)-\int_{0}^{1}f(x)dx|=|(y_{n}(f)-y_{n}(P_i))+(\int_{0}^{1}P_i(x)dx-\int_{0}^{1}f(x)dx)+(y_{n}(P_i)-\int_{0}^{1}P_i(x)dx)| \le 2n|f-P_i|_{\infty }+|y_{n}(P_i)-\int_{0}^{1}P_i(x)dx|$.

Now we are out of luck: to make the first term on the right small for a fixed n, we need to raise $i$. The second term, which depends on i, is small possibly only if we raise n. Now this loop just goes on and on.

What would be a dream on true is, if $|y_{n}(P_i)-\int_{0}^{1}P_i dx|$ has some bound for all $n \ge n_i$ , then the same bound is satisfied(for all $n \ge n_i$) if we replace i by some $i^\prime \ge i$ . The result will follow immediately. Of course, I don't see why this will be true, particularly after analyzing carefully what made the $C^1$ case work:uniform continuity of derivative was used in a crucial way. Even if the derivatives of all the polynomials in the sequence were equicontinuous(which is rarely the case), one still has no control on the rate of convergence of the riemann sums of $-xP_i^\prime$ with the specific partition we chose.

Triangle inequality is not so useful for our purpose here, since it can at best give $O(n)$ bound on $y_{n}(f)$, which we know is in fact $o(n)$. I think one has to analyze carefully what these $y_{n}$ do to $f$ viewed as operator on $C([0,1])$. The obstacle with sum of difference of this form is that there is no good way to control the contribution from the increase of terms. Perhaps one also needs to choose carefully the sequence of polynomials converging to $f$.

Any suggestions of methods, or references which may contain useful tools, or possible counter-examples will be welcome. I already looked up some results on rate of convergence of polynomial, as well as estimate of riemann sum, nothing there seemed to be directly applicable to this particular situation. What may be useful in my opinion is a linear operator view point, though I am not quite sure which direction I should be looking into.

One reason why one would care about the convergence(this is why I care): It uses the same data as one uses to compute riemann sum, but simpler arithmetic operations.

Source of problem:

"Limits, Series, and Fractional Part Integrals: Problems in Mathematical Analysis", Ovidiu Furdiu.

• For $f$ of bounded variation, Koksma's inequality gives a bound for the difference between sum and integral in terms of the discrepancy of the point set on which you are evaluating $f$ and the variation of $f$. Might be worth a look. Aug 7, 2018 at 22:38
• Correct me if I am wrong, but it looks like the Koksma's inequality that I found bounds the difference between the average and the integral. The right hand side of that is what you said it is. What I found was something like this:math.boku.ac.at/udt/vol05/no1/5Harman10-1.pdf. In my opinion, it is precisely the absence of n in the denominator that makes the estimate hard. Thanks for the suggestion. Aug 7, 2018 at 23:02
• If $(1/n)x_n-\int$ and $(1/(n-1))x_{n-1}-\int$ are bounded by essentially the same thing (since the discrepancy doesn't change much when you go from $n-1$ to $n$), then isn't $x_n-x_{n-1}-\int$ also bounded by essentially the same thing? Aug 7, 2018 at 23:11

$\newcommand{\E}{\operatorname{\mathsf E}}$

This conjecture is false. Indeed, take the random function $f=W$, where $W$ is a standard Wiener process (Brownian motion) over the interval $[0,1]$. Then $f$ is continuous with probability $1$; in fact, without loss of generality we may assume that all realizations of this random function are everywhere continuous. The idea here is, while all realizations of $f$ are everywhere continuous, they are pretty bad, in the sense of being nowhere differentiable (not even H\"older with any exponent $\ge1/2$).

A straightforward but tedious calculation -- based on the formula $\E W(u)W(v)=u\wedge v$ for real $u,v$ in $[0,1]$ -- yields, for all natural $s$, $$\E y_{4s}y_{2s}=\frac{12 s^2+9 s+2}{32 s^2+24 s+4}\underset{s\to\infty}\longrightarrow\frac{12}{32}$$ (I re-defined $y_n$ as $x_{n+1}-x_n$.) We also have $\E y_s^2=1/2$, so that $$\E(y_{4s}-y_{2s})^2=\E y_{4s}^2+\E y_{2s}^2-2\E y_{4s}y_{2s}\underset{s\to\infty}\longrightarrow\frac12+\frac12-2\times\frac{12}{32}\ne0.$$ The calculations can be seen in the Mathematica notebook or its pdf image.

Now, if the conjecture were true, we would have $y_{4s}-y_{2s}\to0$ almost surely. Since $y_{4s}-y_{2s}$ is Gaussian, then, by uniform integrability, one would have $\E(y_{4s}-y_{2s})^2\underset{s\to\infty}\longrightarrow0$, which contradicts the above display.

• I am not familiar with probability at all, but I want to ask for some clarification before I go to look up relevant materials in order to check the details. When you say f is continuous with probability 1, do you mean continuous almost everywhere in the sense of real analysis? If so, I think there is still an approximation argument to be made. However, according the page here:en.wikipedia.org/wiki/Wiener_process,continuity was listed as a property. Is this the same Wiener process you used?If it is, then no approximation is needed, it is a counter-example. Aug 8, 2018 at 0:18
• Also, if it is not too much trouble for you, could you provide the details of your calculations? Anyway, I would like to do the computations again by myself later. But I am glad you gave a decisive answer. Aug 8, 2018 at 0:21
• @LucasYin : When we say the random function $W$ is continuous with probability $1$, this means that the set of realizations of $W$ that are not continuous everywhere has probability zero. In fact, one can remove this exceptional, zero-probability set of realizations and then just say that all realizations of $W$ are everywhere continuous. Also, I have given links to the details of the calculations. Aug 8, 2018 at 0:53
• Thanks. I downloaded the two files. I will come back and up-vote this answer as soon as I am qualified. Aug 8, 2018 at 1:03
• I have added details on the idea of the counterexample and on the starting point of the calculations. Also, there was a typo in the Mathematica notebook, which prevented the showing of some of the outputs (which affected no calculations). This is now fixed, anyway -- the links are updated. Aug 8, 2018 at 2:38