For every nonnegative integer there exists a (unique) polynomial of degree in and separately with the following reproducing property:

for every polynomial of degree at most , and for every . For example, ; other examples are found in the post Polynomial delta function.

This fact gives an explicit pointwise bound on a polynomial in terms of its integral on an interval:

where . For example, .

Although in principle could be any real or complex number, it makes sense to restrict attention to , where integration takes place. This leads to the search for extreme values of on the square . Here is how this function looks for :

The symmetries are evident here.

Explicitly,

where is the Legendre polynomial of degree and the factor is included to make the polynomials an orthonormal set in . Since oscillates between and , it follows that

and this bound is attained at because and .

Is

the minimum value of on the square ? Certainly not for even . Indeed, differentiating the sum

with respect to and using , we arrive at

which is negative if is even, ruling out this point as a minimum.

What about odd , then: is it true that on the square ?

: yes, is clear enough.

: the inequality is also true… at least numerically. It can be simplified to but I do not see a way forward from there. At least on the boundary of it can be shown without much work:

The quadratic term has no real roots, which is easy to check.

: similar story, the inequality appears to be true but I can only prove it on the boundary, using

The quartic term has no real roots, which is not so easy to check.

: surprisingly, which is about , disproving the conjectural bound . This fact is not at all obvious from the plot.

Questions:

Is on the square with some universal constant ?

Is the minimum of on always attained on the boundary of ?

Can be expressed in closed form, at least for small degrees ?

scipy.integrate.quad is a popular method of numerical integration with Python. Let’s see how it chooses the points at which to evaluate the function being integrated. Begin with a simple example, the exponential function.

The blue dots indicate the evaluation points, their y-coordinate being the order of evaluation. So, it begins with x=0, continues with something close to -1, etc. The function, drawn in red, is not to its true vertical scale.

The placement of dots gives away the method of integration: it is the Gauss-Kronrod quadrature with 10 Gauss nodes and 21 Kronrod nodes, abbreviated (G10, K21). The Gauss nodes are included in the Kronrod nodes, and of course the function is not evaluated there again. The evaluation process is slightly out of order in that 0 is a Kronrod node but comes first, followed by 10 Gauss nodes, followed by 10 remaining Kronrod nodes. The process ends there, as the comparison of G10 and K21 results shows the necessary precision was reached.

The square root on [0, 1] is not such a nice function, so (G10, K21) does not reach the required precision at once. The interval is bisected again and again until it does.

Surely the cube root is even worse. Or is it?
The nodes are symmetric about the midpoint of the interval of integration. So for any odd function on an interval symmetric about 0 we get G10 = 0 and K21 = 0, and the process stops at once. To see the effect of the cube root singularity, one has to use a non-symmetric interval such as [-1, 2].
That’s still fewer subdivisions than for the square root: cancellation between the left and right neighborhoods of 0 still helps. Let’s look at smooth functions next.
Rapid oscillations forces subdivisions here. There are also other reasons for subdivision, such as the loss of analyticity:
Although exp(-1/x) is infinitely differentiable on this interval, the fact that it is not analytic at 0 makes it a more difficult integrand that exp(x). Finally, an analytic function with no oscillation which still needs a bunch of subintervals:
This is the standard example used to illustrate the Runge phenomenon. Although we are not interpolating here, numerical integration is also influenced by the function having a small radius of convergence of its Taylor series. After all, G10 can be thought of as degree-9 interpolation of the given function at the Gauss nodes (the zeros of a Legendre polynomial), with the formula returning the integral of the interpolating polynomial.

The code used to plot these things:

import numpy as np
import matplotlib.pyplot as plt
from scipy.integrate import quad
global eval_points
f = lambda x: np.exp(x)
def f_int(x):
eval_points.append(x)
return f(x)
eval_points = []
a, b = -1, 1
quad(f_int, a, b)
n = len(eval_points)
t = np.linspace(a, b, 1000)
y = f(t)
yy = n*(y - y.min())/(y.max() - y.min())
plt.plot(t, yy, 'r')
plt.plot(eval_points, np.arange(0, n), '.')
plt.show()

A simple closed curve on the plane can be parameterized by a homeomorphism in infinitely many ways. It is natural to look for “nice” parameterizations: smooth ones, for example. I do not want to require smooth here, so let us try to find that is nonexpanding, that is for all . Note that Euclidean distance is used here, not arclength.

What are some necessary conditions for the existence of a nonexpanding parameterization?

The curve must have length at most , since nonexpanding maps do not increase length. But this is not sufficient: an equilateral triangle of sidelength has no nonexpanding parameterization, despite its length being .

The curve must have diameter at most 2 (which the triangle in item 1 fails). Indeed, nonexpanding maps do not increase the diameter either. However, is not sufficient either: an equilateral triangle of sidelength has no nonexpanding parameterization, despite its diameter being 2 (and length ).

The curve must be contained in some closed disk of radius 1. This is not as obvious as the previous two items. We need Kirszbraun’s theorem here: any nonexpanding map extends to a nonexpanding map , and therefore is contained in the closed disk of radius 1 centered at . (This property fails for the triangle in item 2.)

The combination of 1 and 3 (with 2 being superseded by 3) still is not sufficient. A counterexample is given by any polygon that has length but is small enough to fit in a unit disk, for example:

Indeed, since the length is exactly , a nonexpanding parametrization must have constant speed 1. But mapping a circular arc onto a line segment with speed 1 increases pairwise Euclidean distances, since we are straightening out the arc.

Since I do not see a way to refine the necessary conditions further, let us turn to the sufficient ones.

It is sufficient for to be a convex curve contained in the unit disk. Indeed, the nearest-point projection onto a convex set is a nonexpanding map, and projecting the unit circle onto the curve in this way gives the desired parameterization.

It is sufficient for the curve to have length at most 4. Indeed, in this case there exists a parameterization with . For any the length of the shorter subarc between and is at most . Therefore, the length of is at most , which implies .

Clearly, neither of two sufficient conditions is necessary for the existence of a nonexpanding parameterization. But one can consider “length is necessary, length is sufficient” a reasonable resolution of the problem: up to some constant, the length of a curve can decide the existence one way or the other.

Stay tuned for a post on noncontracting parameterizations…

In how many ways can a series of real-valued functions on an abstract set converge? Having no measure on the domain eliminates the infinitude of modes of convergence based on integral norms. I can think of five modes of convergence of where :

(P) Pointwise convergence: converges for each .

(U) Uniform convergence: the partial sums of the series converge to some function uniformly, i.e., .

(PA) Pointwise convergence of absolute values: converges for each .

(UA) Uniform convergence of absolute values: like uniform, but for .

(M) Weierstrass M-test convergence: converges.

Implications (all easy): (M) implies (UA), which implies both (U) and (PA). Neither (U) nor (PA) implies the other one, but each of them implies (P).

Perhaps (U) and (PA) deserve an illustration, being incomparable. Let . The constant functions form a series that converges uniformly but not in the sense (PA). In the opposite direction, a series of triangles with height 1 and disjoint supports converges (PA) but not (U).

Notably, the sum of the latter series is not a continuous function. This had to happen: by Dini’s theorem, if a series of continuous functions is (PA)-convergent and its sum is continuous, then it is (UA)-convergent. This “self-improving” property of (PA) convergence will comes up again in the second part of this post.

From abstract sets to normed spaces

In functional analysis, the elements of a normed space can often be usefully interpreted as functions on the unit ball of the dual space . Indeed, each induces for . Applying the aforementioned modes of convergence to with , we arrive at

(P) ⇔ Convergence in the weak topology of E.

(U) ⇔ Convergence in the norm topology of E.

(PA) ⇔ Unconditional convergence in the weak topology of E.

(UA) ⇔ Unconditional convergence in the norm topology of E.

(M) ⇔ Absolute convergence, i.e., converges.

The equivalences (P), (U), (M) are straightforward exercises, but the unconditional convergence merits further discussion. For one thing, there are subtly different approaches to formalizing the concept. Following “Normed Linear Spaces” by M. M. Day, let’s say that a series is

(RC) Reordered convergent if there exists such that for every bijection

(UC) Unordered convergent if there exists such that for every neighborhood of there exists a finite set with the property that for every finite set containing .

(SC) Subseries convergent if for every increasing sequence of integers the series converges.

(BC) Bounded-multiplier convergent if for every bounded sequence of scalars , the series converges.

In a general locally convex space, (BC) ⇒ (SC) ⇒ (UC) ⇔ (RC). The issue with reversing the first two implications is that they involve the existence of a sum for some new series, and if the space lacks completeness, the sum might fail to exist for no good reason. All four properties are equivalent in sequentially complete spaces (those where every Cauchy sequence converges).

Let’s prove that interpretation of (PA) stated above, using the (BC) form of unconditional convergence. Suppose converges in the sense (PA), that is for every linear functional the series converges. Then it’s clear that has the same property for any bounded scalar sequence . That is, (PA) implies bounded-multiplier convergence in the weak topology. Conversely, suppose enjoys weak bounded-multiplier convergence and let . Multiplying each by a suitable unimodular factor we can get for all . Now the weak convergence of yields the pointwise convergence of .

A theorem of Orlicz, proved in the aforementioned book by Day, says that (SC) convergence in the weak topology of a Banach space is equivalent to (SC) convergence in the norm topology. Thanks to completeness, in the norm topology of a Banach space all forms of unconditional convergence are equivalent. The upshot is that (PA) automatically upgrades to (UA) in the context of the elements of a Banach space being considered as functions on the dual unit ball.

The standard orthonormal basis (ONB) in the Hilbert space consists of the vectors
(1, 0, 0, 0, …)
(0, 1, 0, 0, …)
(0, 0, 1, 0, …)
…
Let S be the forward shift operator: . The aforementioned ONB is precisely the orbit of the first basis vector under the iteration of S. Are there any other vectors x whose orbit under S is an ONB?

If one tries to construct such x by hand, taking some finite linear combination of , this is not going to work. Indeed, if the coefficient sequence has finitely many nonzero terms, then one of them, say, , is the last one. Then is not orthogonal to because the inner product is and that is not zero.

However, such vectors x exist, and arise naturally in complex analysis. Indeed, to a sequence we can associate a function . The series converges in the open unit disk to a holomorphic function which, being in the Hardy space , has boundary values represented by an square-integrable function on the unit circle . Forward shift corresponds to multiplication by . Thus, the orthogonality requires that for every the function be orthogonal to in . This means that is orthogonal to all such ; and since it’s real, it is orthogonal to for all by virtue of conjugation. Conclusion: |f| has to be constant on the boundary; specifically we need |f|=1 a.e. to have a normalized basis. All the steps can be reversed: |f|=1 is also sufficient for orthogonality.

So, all we need is a holomorphic function f on the unit disk such that almost all boundary values are unimodular and f(0) is nonzero; the latter requirement comes from having to span the entire space. In addition to the constant 1, which yields the canonical ONB, one can use

A Möbius transformation where .

A product of those (a Blaschke product), which can be infinite if the numbers converge to the boundary at a sufficient rate to ensure the convergence of the series.

The function which is not a Blaschke product (indeed, it has no zeros) yet satisfies for all .

Most generally, an inner function which is a Blaschke product multiplied by an integral of rotated versions of the aforementioned exponential function.

Arguably the simplest of these is the Möbius transformation with ; expanding it into the Taylor series we get

Thus, the second simplest ONB-by-translations after the canonical one consists of
(-1/2, 3/4, 3/8, 3/16, 3/32, 3/64, …)
(0, -1/2, 3/4, 3/8, 3/16, 3/32, …)
(0, 0, -1/2, 3/4, 3/8, 3/16, …)
and so on. Direct verification of the ONB properties is an exercise in summing geometric series.

What about the exponential one? The Taylor series of begins with

I don’t know if these coefficients in parentheses have any significance. Well perhaps they do because the sum of their squares is . But I don’t know anything else about them. For example, are there infinitely many terms of either sign?

Geometrically, a Möbius transform corresponds to traversing the boundary circle once, a Blaschke product of degree n means doing it n times, while the exponential function, as well as infinite Blaschke products, manage to map a circle onto itself so that it winds around infinitely many times.

Finally, is there anything like that for the backward shift ? The vector is orthogonal to if and only if is orthogonal to , so the condition for orthogonality is the same as above. But the orbit of any vector under tends to zero, thus cannot be an orthonormal basis.

The choice of piecewise polynomials of degree 3 for interpolation is justifiably popular: even-degree splines are algebraically awkward to construct, degree 1 is simply piecewise linear interpolation (not smooth), and degree 5, while feasible, entails juggling too many coefficients. Besides, a cubic polynomial minimizes the amount of wiggling (the integral of second derivative squared) for given values and slopes at the endpoints of an interval. (Recall Connecting dots naturally.)

But the derivative of a cubic spline is a quadratic spline. And one needs the derivative to find the critical points. This results in an awkward example in SciPy documentation, annotated with “(NB: sproot only works for order 3 splines, so we fit an order 4 spline)”.

Although not implemented in SciPy, the task of computing the roots of a quadratic spline is a simple one. Obtaining the roots from the internal representation of a quadratic spline in SciPy (as a linear combination of B-splines) would take some work and reading. But a quadratic polynomial is determined by three values, so sampling it at three points, such as two consecutive knots and their average, is enough.

Quadratic formula with values instead of coefficients

Suppose we know the values of a quadratic polynomial q at -1, 0, 1, and wish to find if it has roots between -1 and 1. Let’s normalize so that q(0)=1, and let x = q(-1), y = q(1). If either x or y is negative, there is definitely a root on the interval. If they are positive, there is still a chance: we need the parabola to be concave up, have a minimum within [-1, 1], and for the minimum to be negative. All of this is easily determined once we note that the coefficients of the polynomial are a = (x+y)/2 – 1, b = (y-x)/2, and c = 1.

The inequality ensures the suitable sign of the discriminant. It describes a parabola with vertex (1, 1) and focus (2, 2), contained in the first quadrant and tangent to the axes at (4, 0) and (0, 4). Within the orange region there are no real roots.

The line x+y=2, tangent to the parabola at its vertex, separates convex and concave parabolas. While concavity in conjunction with x, y being positive definitely precludes having roots in [-1, 1], slight convexity is not much better: it results in real roots outside of the interval. Here is the complete picture: green means there is a root in [-1, 1], orange means no real roots, red covers the rest.

Back to splines

Since the derivative of a spline is implemented in SciPy (B-splines have a nice formula for derivatives), all we need is a root-finding routine for quadratic splines. Here it is, based on the above observations but using built-in NumPy polynomial solver np.roots to avoid dealing with various special cases for the coefficients.

def quadratic_spline_roots(spl):
roots = []
knots = spl.get_knots()
for a, b in zip(knots[:-1], knots[1:]):
u, v, w = spl(a), spl((a+b)/2), spl(b)
t = np.roots([u+w-2*v, w-u, 2*v])
t = t[np.isreal(t) & (np.abs(t) <= 1)]
roots.extend(t*(b-a)/2 + (b+a)/2)
return np.array(roots)

A demonstration, which plots the spline (blue), its critical points (red), and original data points (black) as follows:

import numpy as np
import matplotlib.pyplot as plt
from scipy.interpolate import InterpolatedUnivariateSpline
x = np.arange(7)
y = np.array([3, 1, 1, 2, 2, 4, 3])
f = InterpolatedUnivariateSpline(x, y, k=3)
crit_pts = quadratic_spline_roots(f.derivative())
t = np.linspace(x[0], x[-1], 500)
plt.plot(t, f(t))
plt.plot(x, y, 'kd')
plt.plot(crit_pts, f(crit_pts), 'ro')
plt.show()