Polynomial with infinitely many roots
The zero polynomial every number is a root of P. This is the only polynomial with infinitely many roots. A non-zero polynomial is of some degree n (n may be 0,1,2,...) and cannot have more than n roots since, by a well-known theorem of algebra, if (for pairwise different ), then necessarily for some non-zero polynomial Q of degree
Integer values versus integer coefficients
Every polynomial P with integer coefficients is integer-valued, that is, its value P(k) is an integer for every integer k; but the converse is true only for first degree polynomials (linear functions). For example, the polynomial
takes on integer values whenever x is an integer. That is because one of x and x-1 must be an even number. The values are the binomial coefficients.
More generally, for every n=0,1,2,3,... the polynomial is integer-valued; are the binomial coefficients.
In fact, every integer-valued polynomial is an integer linear combination of these Pn.
Polynomial mimics cosine: interpolation
The cosine function, satisfies also and for all x, which gives infinitely many x such that is one of the numbers that is, infinitely many points on the graph. A polynomial cannot satisfy all these conditions, because as for every non-constant polynomial P; can it satisfy a finite portion of them?
Let us try to find P that satisfies the five conditions For convenience we rescale x letting and rewrite the five conditions in terms of Q: In order to find such Q we use Lagrange polynomials.
Using the polynomial of degree 5 with roots at the given points 0, 2, 3, 4, 6 and taking into account that (check it by differentiating the product) we consider the so-called Lagrange basis polynomial of degree 4 with roots at 2, 3, 4, 6 (but not 0); the division in the left-hand side is interpreted algebraically as division of polynomials (that is, finding a polynomial whose product by the denominator is the numerator ) rather than division of functions, thus, the quotient is defined for all x, including 0. Its value at 0 is 1. Think, why; see the picture; recall that .
Similarly, the second Lagrange basis polynomial takes the values 0, 1, 0, 0, 0 (at 0, 2, 3, 4, 6 respectively).
The third one takes the values 0, 0, 1, 0, 0. And so on (calculate the fourth and fifth). It remains to combine these five Lagrange basis polynomials with the coefficients equal to the required values of Q:
As we see on the picture, the two functions are quite close for in fact, the greatest for these x is about 0.00029.
A better approximation can be obtained via derivative. The derivative of being we have The corresponding derivatives are close but different; for instance,
In order to fix the derivative without spoiling the values we replace with where is a polynomial of degree 4 such that the derivative of is equal to for it means, since for these x; so,
We find such R as before:
and get a better approximation in fact, If you still want a smaller error, try second derivative and
Polynomial mimics cosine: roots
The cosine function, satisfies and has infinitely many roots: A polynomial cannot satisfy all these conditions; can it satisfy a finite portion of them?
It is easy to find a polynomial P such that and namely (check it). What about and
The conditions being insensitive to the sign of x, we seek a polynomial of that is, where Q satisfies and It is easy to find such Q, namely, (check it), which leads to
As we see on the picture, the two functions are rather close for in fact, the greatest for these x is about 0.028, while the greatest (for these x) is about 0.056.
The next step in this direction:
And so on. For every the polynomial
satisfies and which is easy to check. It is harder (but possible) to prove that as which represents the cosine as an infinite product
On the other hand, the well-known power series gives another sequence of polynomials converging to the same cosine function. See the picture for Q3;
Can we check the equality
by opening the brackets? Let us try. The constant coefficient: just 1=1. The coefficient of x2:
that is, really? Yes, the well-known series of reciprocal squares is instrumental.
Such non-rigorous opening of brackets can be made rigorous as follows. For every polynomial P, the constant coefficient is the value of P at zero, P(0); the coefficient of x is the value at zero of the derivative, P '(0); and the coefficient of x2 is one half of the value at zero of the second derivative, ½P''(0). Clearly, and for all (as before, ). The calculation above shows that as n tends to infinity. What about higher derivative, does it converge to ? It is tedious (if at all possible) to generalize the above calculation to k=4,6,...; fortunately, there is a better approach. Namely, for all complex numbers z, and moreover, for every R>0. Using Cauchy's differentiation formula one concludes that (as ) for each k, and in particular,
Limit of derivatives versus derivative of limit
For we have (think, why) as Nevertheless, the derivative at zero does not converge to 0; rather, it is equal to 1 (for all n) since, denoting we have
Thus, the limit of the sequence of functions on the interval is the zero function, hence the derivative of the limit is the zero function as well. However, the limit of the sequence of derivatives fails to be zero at least for What happens for ? Here the limit of derivatives is zero, since (check it; the exponential decay of the second factor outweighs the linear grows of the first factor). Thus,
It is not always possible to interchange derivative and limit.
Note the two equivalent definition of the function f; one is piecewise (something for some x, something else for other x, ...), but the other is a single expression for all these x.
The function f is discontinuous (at 0), and nevertheless it is the limit of continuous functions This can happen for pointwise convergence (that is, convergence at every point of the considered domain), since the speed of convergence can depend on the point.
Otherwise (when the speed of convergence does not depend on the point) convergence is called uniform; by the uniform convergence theorem, the uniform limit of continuous functions is a continuous function.
It follows that convergence of (to f) is non-uniform, but this is a proof by contradiction.
A better understanding may be gained from a direct proof. The derivatives fail to converge uniformly, since fails to be small (when n is large) for some x close to 0; for instance, try
for all and is not zero (unless ).
In contrast, uniformly on that is, as since the maximum is reached at (check it by solving the equation ) and And still, it appears to be impossible to interchange derivative and limit. Compare this case with a well-known theorem:
- If is a sequence of differentiable functions on such that exists (and is finite) for some and the sequence converges uniformly on , then converges uniformly to a function on , and for .
Uniform convergence of derivatives is required; uniform convergence of functions is not enough.
Complex numbers, helpful in Sect. "Polynomial mimics cosine: roots", are helpless here, since for we have for all
Everyone knows how to visualize the behavior of a continuous function by a curve on the coordinate plane. To this end one samples enough points on the graph of the function, plots them on the plane and, connecting these points by a curve, sketches the graph. However, this seemingly uncontroversial idea is challenged by some strange functions, sometimes called "continuous monsters". Often they are sums of so-called lacunary trigonometric series
- (where the numbers are far apart).
The most famous of these is the Weierstrass function
- (for appropriate such that ).
According to Jarnicki and Pflug (Section 3.1), this is (and the similar series of sine functions is ).
This image (reproduced here by Michael McLaughlin with reference to the above-mentioned Wikipedia article, and here by Richard Lipton without reference) is in fact a graph of the approximation to the function obtained by connecting sample points (which can be seen by inspecting the XML code in the SVG file). It looks like a curve albeit rather strange one. The last two summands are distorted, since the step size exceeds the period of and is close to half the period of However, all terms with contribute at most that is, for all this difference is barely visible unless one zooms the image.
So far, so good. But this monster is not the worst. In order to get a more monstrous lacunary trigonometric series one may try frequencies increasing faster than or coefficients decreasing slower than or both.
Let us try the series
these coefficients are convenient, since their sum is (finite and) evident:
Accordingly, (since ), and for all (since ).
Similarly, and Accordingly, partial sums and tails satisfy and for all
Due to evident symmetries (see the graphs of on the period ) it is enough to plot this function on
Partial sum zoom 4
Looking closely at the graph of we come to some doubt. At first glance, it is drawn with a thicker pen. But no; some (almost?) vertical lines are thin. So, what do we see here, a curve, or rather, the area between two "parallel" curves?
and zoom 40
and zoom 400
The graph of becomes clearly visible after a zoom, but the doubt returns, hardened, with One more zoom only worsens. We realize that the graph of on looks too nice. In particular, it appears that the graph of crosses the upper side of the red box. So, how to get closer to the graph of
Fortunately, for some special values of the exact value of is evident. First, (see above), whence for all integers due to periodicity: for all Similarly, since for all odd integers (in particular, ). And on the other hand, for all
Without the first summand we have the first tail with the period Accordingly, and for all integers And on the other hand, for all Thus,
Special values and bounds of
- for all integers
- for all
Similarly, for all
- for all integers
- for all
Via zoom 400; also
Returning to and on we add special values and bounds via and see that is much further from than from We have more than 440 points on the red curve, and equally many points on the blue curve.
Graph of zoom 400.
Thus, if the horizontal size of picture is less than 440 pixels, then inevitably the graph of crosses all the pixels between the red curve and the blue curve! Within the given resolution the graph of does not look like a curve, but as the area between two parallel curves.
This, in itself, isn't surprising. For example, a 10 megahertz radio wave modulated by a 100 hertz sound may be described by the function The graph of on, say, does not look like a curve, but as the region between two curves, And on it looks like a rectangular region. However, zoom ultimately helps; the graph of on (or any other 1 microsecond interval) does look like a curve.
In contrast, for zoom never helps, it only worsens. In fact, it ultimately leads to a graph that looks like a rectangular region. This shows the monstrous nature of On the other hand, the height of the (nearly) rectangular region converges to zero as zoom tends to infinity; this shows the continuous nature of
Random sample of points on the graph of
Visualization by a region-like graph leaves much to be desired. Unable to draw a curve-like graph, we still can do more. We can choose at random many values of compute the corresponding values of the given function, and draw the points This picture shows a sample of random points on the graph of the tail in the first quarter of the period of this tail (which is sufficient due to the evident symmetries, as was noted). Truth be told, the function was used here as a satisfactory approximation of and each was specified by more than ternary (that is, base 3) digits in order to compute
As before, the red line and the blue line are bounds of the given function (via ), and the points on these curves are special values. A wonder: all the random points are far from these bounds! Usually points is enough to get a satisfactory picture of the maximum value of the function. But for this monster, points are few.
Generally, for the sum of a lacunary trigonometric series, it is quite a challenge, to find its maximum and minimum (on a given interval) even approximately, say, with relative error less than 10%. Our choice of frequencies in concert with our use of cosine rather than sine, allow us to find unusually high values of the sum. In order to fully appreciate this good luck, try to maximize such function as or to minimize and you will realize, why Weierstrass preferred cosine functions and frequencies of the form where is a positive odd integer.
Usual numerical optimization methods fail because local extrema are numerous and very sharp. By continuity, a monster function is close to its maximum in some neighborhood of its maximizer, but this neighborhood is very small; a random point has very little chance of getting into such neighborhood. The vast majority of values are far from extreme.
Increasing rearrangement of sample points on the graph of
In order to investigate the distribution of values of the tail on its period, one may took the values in the first quarter of the period (used above), together with the opposite numbers (these are values in the second quarter), sort the list of all these numbers in ascending order, and treat the result as values of a new function at equally spaced points. Here is the result plotted, see the red curve. This is a numeric approximation of the so-called monotone (increasing) rearrangement of the given function.
Significantly, the result is quite close to the famous normal distribution , and the red curve is quite close to the corresponding quantile function indicated by the black points.
(Here ) A wonder: the function is monstrous, but its monotone rearrangement is nice. Why so?
The given function is the sum of many summands (of the form ); and "The central limit theorem states that under certain (fairly common) conditions, the sum of many random variables will have an approximately normal distribution."
Choosing a point at random according to the uniform distribution we may treat the summands as random variables. However, one of the conditions is independence; and our summands are dependent, moreover, functionally dependent, since (More generally, being the Chebyshev polynomial.) Nevertheless, probabilistic approach to lacunary trigonometric series exists and bears fruit; in particular, appearance of normal distribution in this context is a well-know phenomenon.
But clearly, the normal approximation must fail somewhere, since our function is bounded (by ), while a normal random variable is not.
The word "central" in the name of the central limit theorem is interpreted in two ways: (1) of central importance in probability theory; (2) describes the center of the distribution as opposed to its tails, that is, large deviations.
Increasing rearrangement of zoom 40.
In the normal distribution, deviations above appear with the probability accordingly, for the inequality holds on intervals of total length and a random sample of size should contain about such values. This is indiscernible on the previous picture, but clearly visible on the zoomed picture.
Increasing rearrangement of log scale.
For the normal probability is only and is only in order to see what happens for and we need larger samples and logarithmic scale. This last picture presents a sample of size (that took a computer several hours). We see that the distribution is close to normal at but moves away from normal at Hopefully, the approximate normality follows from some moderate deviations theory that applies at while the departure from normality follows from some large deviations theory that applies at and further; but for now, in spite of the recent progress in the probabilistic approach to lacunary series, such theories are not available, and the situation near the big red question mark on the picture remains unknown.
It is natural to guess that is this domain the probability of deviation is smaller than its normal approximation, therefore, smaller than
Assuming that this conjecture is true, and taking into account that and we conclude that the function exceeds of its maximum on intervals of total length less (probably, much less) than
But, again, this monster is not the worst. In order to get a more monstrous lacunary trigonometric series one may try frequencies increasing faster than or coefficients decreasing slower than or both. Unexpectedly, or not so unexpectedly, such functions, being more monstrous analytically, are more tractable probabilistically. (In the paper by Delbaen and Hovhannisyan, note the coefficients for in Remark 2.3; note also the "big gaps" theorems 1.4, 2.15, 2.16 for ) This is a special case of a general phenomenon formulated by De Bruijn as follows:
- It often happens that we want to evaluate a certain number [...] so that the direct method is almost prohibitive [...] we should be very happy to have an entirely different method [...] giving at least some useful information to it. And usually this new method gives (as remarked by Laplace) the better results in proportion to its being more necessary [...]