This is post is related to Extremal Taylor polynomials where it was important to observe that the Taylor polynomials of the function do not have zeros in the unit disk. Let’s see how far this generalizes.
The function has the rare property that all zeros of its Taylor polynomial have unit modulus. This is clear from
In this and subsequent illustrations, the zeros of the first 50 Taylor polynomials are shown as blue dots, with the unit circle in red for reference.
When the exponent is less than -1, the zeros move inside the unit disk and begin forming nice patterns in there.
When the exponent is strictly between -1 and 1, the zeros are all outside of the unit disk. Some of them get quite large, forcing a change of scale in the image.
Why does this happen when the exponent approaches 1? The function is its own Taylor polynomial, and has the only zero at -1. So, when , the Taylor polynomials are small perturbations of . These perturbations of coefficients have to create additional zeros, but being small, they require a large value of to help them.
For a specific example, the quadratic Taylor polynomial of is , with roots . When , one of these roots is near (as it has to be) and the other is large.
Finally, when and is not an integer, we get zeros on both sides of the unit circle. The majority of them are still outside. A prominent example of an interior zero is produced by the first-degree polynomial .
Let be a graph with vertices . The degree of vertex is denoted . Let be the Laplacian matrix of , so that , is when the vertices are adjacent, and is otherwise. The eigenvalues of are written as .
The graph is regular if all vertices have the same degree: . How can this property be seen from its Laplacian eigenvalues ?
Since the sum of eigenvalues is equal to the trace, we have . Moreover, is the trace of , which is equal to the sum of the squares of all entries of . This sum is because the th row of contains one entry equal to and entries equal to . In conclusion, .
The Cauchy-Schwarz inequality says that with equality if and only if all numbers are equal, i.e., the graph is regular. In terms of eigenvalues, this means that the difference
is always nonnegative, and is equal to zero precisely when the graph is regular. This is how one can see the regularity of a graph from its Laplacian spectrum.
As an aside, is an even integer. Indeed, the sum is even because it double-counts the edges. Hence the number of vertices of odd degree is even, which implies that is even for every positive integer .
Up to a constant factor, is simply the degree variance: the variance of the sequence . What graph maximizes it for a given ? We want to have some very large degrees and some very small ones.
Let be the union of the complete graph on vertices and isolated vertices. The sum of degrees is and the sum of squares of degrees is . Hence,
For the maximum is attained by , that is there is one isolated vertex. For the maximum is . In general it is attained by .
The graph is disconnected. But any graph has the same degree variance as its complement. And the complement is always connected: it consists of a “center”, a complete graph on vertices, and “periphery”, a set of vertices that are connected to each central vertex. Put another way, is obtained from the complete bipartite graph by connecting all vertices of the group together.
Tom A. B. Snijders (1981) proved that and are the only graphs maximizing the degree variance; in particular, is the unique maximizer among the connected graphs. It is pictured below for .
Given a vector space and a map (linear or not), consider the displacement set of , denoted . For linear maps this is simply the range of the operator and therefore is a subspace.
The essentially nonlinear operations of taking the inverse or composition of maps become almost linear when the displacement set is considered. Specifically, if has an inverse, then , which is immediate from the definition. Also, .
When is a topological vector space, the maps for which has compact closure are of particular interest: these are compact perturbations of the identity, for which degree theory can be developed. The consideration of makes it very clear that if is an invertible compact perturbation of the identity, then is in this class as well.
It is also of interest to consider the maps for which is either bounded, or is bounded away from . Neither case can occur for linear operators, so this is essentially nonlinear analysis. In the nonlinear case, the boundedness assumption for linear operators is usually replaced by the Lipschitz condition. Let us say that is -bi-Lipschitz if for all in the domain of .
Brouwer’s fixed point theorem fails in infinite-dimensional Hilbert spaces, but it not yet clear how hard it can fail. The strongest possible counterexample would be a bi-Lipschitz automorphism of the unit ball with displacement bounded away from 0. The existence of such a map is unknown. If it does not exist, that would imply that the unit ball and the unit sphere in the Hilbert space are not bi-Lipschitz equivalent, because the unit sphere does have such an automorphism: .
Concerning the maps with bounded displacement, here is a theorem from Patrick Biermann’s thesis (Theorem 3.3.2): if is an -bi-Lipschitz map in a Hilbert space, , and has bounded displacement, then is onto. The importance of bounded displacement is illustrated by the forward shift map for which but surjectivity nonetheless fails.
It would be nice to get rid of the assumption in the preceding paragraph. I guess any bi-Lipschitz map with bounded displacement should be surjective, at least in Hilbert spaces, but possibly in general Banach spaces as well.
For a vector in a normed space , define the orthogonal complement to be the set of all vectors such that for all scalars . In an inner product space (real or complex), this agrees with the normal definition of orthogonality because as , and the right hand side can be nonnegative only if .
Let’s see what properties of orthogonal complement survive in a general normed space. For one thing, if and only if . Another trivial property is that for all . More importantly, is a closed set that contains some nonzero vectors.
Closed because the complement is open: if for some , the same will be true for vectors close to .
Contains a nonzero vector because the Hahn-Banach theorem provides a norming functional for , i.e., a unit-norm linear functional such that . Any is orthogonal to , because .
In general, is not a linear subspace; it need not even have empty interior. For example, consider the orthogonal complement of the first basis vector in the plane with (taxicab) metric: it is .
This example also shows that orthogonality is not symmetric in general normed spaces: but . This is why I avoid using notation here.
In fact, is the union of kernels of all norming functionals of , so it is only a linear subspace when the norming functional is unique. Containment in one direction was already proved. Conversely, suppose and define a linear functional on the span of so that . By construction, has norm 1. Its Hahn-Banach extension is a norming functional for that vanishes on .
Consider as an example. A function satisfies precisely when its th moment is minimal among all translates . This means, by definition, that its “-estimator” is zero. In the special cases the estimator is known as the median, mean, and midrange, respectively. Increasing gives more influence to outliers, so is the more useful range for it.
The market isn’t so hot for Iraq war movies. And it’s nearly impossible to adapt such an introspective novel into film. I still respect the effort and its outcome, even if all references to the normal distribution got left out of it.
I spent a lot of time trying to identify the exact point at which I noticed a change in Murph, somehow thinking that if I could figure out where he had begun to slide down the curve of the bell that I could do something about it. But these are subtle shifts, and trying to distinguish them is like trying to measure the degrees of gray when evening comes. It’s impossible to identify the cause of anything, and I began to see the war as a big joke, for how cruel it was, for how desperately I wanted to measure the particulars of Murph’s new, strange behavior and trace it back to one moment, to one cause, to one thing I would not be guilty of. And I realized very suddenly one afternoon while throwing rocks into a bucket in a daze that the joke was in fact on me. Because how can you measure deviation if you don’t know the mean? There was no center in the world. The curves of all our bells were cracked.
Two actors with (essentially) the same first name and over 50 years of age difference (Anthony Hopkins 1937-, Anton Yelchin 1989-2016) make this Stephen King adaptation well worth watching.
He made another circuit of his room, working the tingles out of his legs, feeling like a prisoner pacing his cell. The door had no lock on it—no more than his mom’s did—but he felt like a jailbird just the same. He was afraid to go out. She hadn’t called him for supper, and although he was hungry—a little, anyway—he was afraid to go out. He was afraid of how he might find her… or of not finding her at all. Suppose she had decided she’d finally had enough of Bobby-O, stupid lying little Bobby-O, his father’s son? Even if she was here, and seemingly back to normal… was there even such a thing as normal? People had terrible things behind their faces sometimes. He knew that now.
Sure, it’s not as good as the first film in the series (which does not qualify for the challenge, scoring 65% on RT), but a major improvement on the mindless zombie chases of the second part. I like to think of it as a parable illustrating ethical issues in public health… allowing for the customary movie-science vs actual-science differences.
How to measure the nonlinearity of a function where is an interval? A natural way is to consider the smallest possible deviation from a line , that is . It turns out to be convenient to divide this by , the length of the interval . So, let . (This is similar to β-numbers of Peter Jones, except the deviation from a line is measured only in the vertical direction.)
Relation with derivatives
The definition of derivative immediately implies that if exists, then as shrinks to (that is, gets smaller while containing ). A typical construction of a nowhere differentiable continuous function is based on making bounded from below; it is enough to do this for dyadic intervals, and that can be done by adding wiggly terms like : see the blancmange curve.
The converse is false: if as shrinks to , the function may still fail to be differentiable at . The reason is that the affine approximation may have different slopes at different scales. An example is in a neighborhood of . Consider a small interval . The line with is a good approximation to because on most of the interval except for a very small part near , and on that part is very close to anyway.
Why the root of logarithm? Because has a fixed amount of change on a fixed proportion of , independently of . We need a function slower than the logarithm, so that as decreases, there is a smaller amount of change on a larger part of the interval .
Nonlinearity of Lipschitz functions
Suppose is a Lipschitz function, that is, there exists a constant such that for all . It’s easy to see that , by taking the mid-range approximation . But the sharp bound is whose proof is not as trivial. The sharpness is shown by with .
Proof. Let be the slope of the linear function that agrees with at the endpoints of . Subtracting this linear function from gives us a Lipschitz function such that and . Let . Chebyshev’s inequality gives lower bounds for the measures of the sets and : namely, and . By adding these, we find that . Since , the mid-range approximation to has error at most . Hence .
Turns out, the graph of every Lipschitz function has relatively large almost-flat pieces. That is, there are subintervals of nontrivial size where the measure of nonlinearity is much smaller than the Lipschitz constant. This result is a special (one-dimensional) case of Theorem 2.3 in Affine approximation of Lipschitz functions and nonlinear quotients by Bates, Johnson, Lindenstrauss, Preiss, and Schechtman.
Theorem AA (for “affine approximation”): For every there exists with the following property. If is an -Lipschitz function, then there exists an interval with and .
Theorem AA should not be confused with Rademacher’s theorem which says that a Lipschitz function is differentiable almost everywhere. The point here is a lower bound on the size of the interval . Differentiability does not provide that. In fact, if we knew that is smooth, or even a polynomial, the proof of Theorem AA would not become any easier.
Proof of Theorem AA
We may assume and . For let . That is, is the restricted Lipschitz constant, one that applies for distances at least . It is a decreasing function of , and .
Note that and that every value of is within of either or . Hence, the oscillation of on is at most . If , then the constant mid-range approximation on gives the desired conclusion, with . From now on .
The sequence is increasing toward , which implies for some . Pick an interval that realizes , that is and . Without loss of generality (otherwise consider ). Let be the middle half of . Since each point of is within distance of both and , it follows that for all .
So far we have pinched between two affine functions of equal slope. Let us consider their difference:
. Recall that , which gives a bound of for the difference. Approximating by the average of the two affine functions we conclude that as required.
It remains to consider the size of , about which we only know so far. Naturally, we want to take the smallest such that holds. Let be this value; then . Here and . The conclusion is that , hence . This finally yields as an acceptable choice, completing the proof of Theorem AA.
This is now a separate post from Graph theory in Formula 1 so that the evolution of the graph of 1-2 finishes can be tracked. The graphs are shown as they were after the race mentioned in the subheading. At times, when the main F1 graph remained unchanged, I threw in similar graphs for some F1 feeder series.
Obviously, there is only one edge after the first race of the season, a Mercedes 1-2. This turned out to be the beginning of a series of five 1-2 for Mercedes, so the graph did not change again until Monaco.
At Monaco, Mercedes drivers took “only” the first and third place, as Vettel appeared in top 2.
It began with the youngest ever front row of the F1 grid: Leclerc and Verstappen. And ended with the youngest ever 1-2 finish (represented by an edge here) in Formula One: Verstappen and Leclerc. For the moment, the graph is disconnected.
Two predictions: (1) the components will get connected; (2) the graph will stay with 5 vertices, tying the record for the fewest number of vertices (there were 5 in 2000 and 2011). Which is a way of saying, I don’t expect either Gasly or anyone outside of top 3 teams to finish in top two for the rest of the season.
The rain-induced chaos in Hockenheim could have added a third component to the graph, but instead it linked the two existing ones. The graph is now a path on 5 vertices, which is not a likely structure in this context.
Sure, the configuration did not last. The graph is longer a tree, and nor longer bipartite.
A prediction added during the summer break: the season’s graph will contain a Hamiltonian cycle.
Getting closer to constructing a Hamiltonian cycle: only one degree-1 vertex remains. The graph is similar to 1992 season, except the appendage was one edge longer then.
In 1992, the central position was occupied by Mansell, who scored 93% more points than the runner-up to the title. This is where we find Hamilton at present, though with “only” 32% more points than the 2nd place. (The percentages are called for, because the scoring system changed in between.)
A Hamiltonian cycle is now complete. The only way to lose it is by adding another vertex to the graph, which I do not expect to happen.
The graph resembles the 2001 season where Hamilton’s position was occupied by Schumacher. The only difference is that in 2001, there was an extra edge incident to Schumacher.
We have a 4-clique, and are two edges short of the complete graph on 5 vertices.
However, I predict the complete graph will not happen. Achieving it would require two races in which neither Hamilton nor Leclerc finishes in top two. Such a thing happened just once in the first 15 races, in the chaos of rainy Hockenheim. Not likely to happen twice in the remaining 6.
The Formula 1 graph did not change, which is not surprising, considering how unlikely the two missing edges are to appear (see above). But since FIA Formula 3 championship ended in Sochi, here is its complete graph.
The champion, Shwartzman, has the highest vertex degree with 5. Given the level of success of Prema team, one could expect their drivers to form a 3-clique, but this is not the case: Armstrong and Daruvala are not connected (Daruvala’s successful races were mostly toward the beginning of the season, Armstrong’s toward the end). Two Hitech drivers, Vips and Pulcini, each share a couple edges with Prema drivers. All in all, this was a closely fought championship that sometimes made Formula 1 races look like parade laps in comparison.
Unlikely as it was, another edge was created, bringing the graph within one edge of the first non-planar season in F1.
Could we get an even more unlikely Verstappen-Bottas finish in the remaining four races? Red Bull did not look strong enough in recent races for that to happen.
Interlude: Formula 4
The level of Formula 4 championships is highly variable: some struggle to survive with a handful of cars on the grid, some have developed into spectacular competitions. The following summary of F4 history is highly recommended.
The two most noteworthy ones are the “twin” F4 championships held in Germany and Italy which have disjoint calendars and share many of the drivers. Here is a summary of German (ADAC) F4 in 2019:
At times, US Racing team threatened to take positions 1-2-3-4 in the standings. They did get 1, 3, 4, 6 but it was a close fight, with Pourchaire taking the title by 7 points (258 : 251) over Hauger. Hauger and his neighbors in the graph (US Racing quartet and Petecof of Prema team) occupied the top 6 positions. The radius of the graph is 3, with its (unique) center being Pourchaire.
The Italian F4 championship sometimes had over 35 cars on the grid, but its 1-2 graph is smaller, of radius 2. The unique center is Hauger, who won by a landslide (Hauger 369 : 233 Petecof). The only Italian driver on the graph of this Italian championship is Ferrari who once took second place when Hauger and Petecof collided.
Arguably, Hauger is the 2019 driver of the year at F4 level: he won 6 races in ADAC F4 and 12 in Italian F4. Pourchaire won 4 races in ADAC F4 and did not participate in Italian F4.
Another fascinating contest was the season-long battle of two 15-year old F4 rookies: Aron and Stanek. Stanek took ADAC F4 rookie title, Aron did likewise in Italy. One can call it a tie, with a rematch likely next year unless they move to different categories. Mercedes-backed Aron gets more media attention so far.
No new edge, just another repeat of Hamilton-Vettel pairing: it is the 55th time they took the top two spots in Formula 1, an all-time record. They are adjacent on every graph since 2010 except for 2013, where Hamilton’s only race win came with Vettel finishing 3rd. They were also 1-3 in Japan 2009, so one has to go back to 2008, when Vettel drove for Toro Rosso, to find a season where they did not share the podium.
Meanwhile, Formula Renault Eurocup 2019 season ended, so here is its summary graph.
As usual, the highest vertex degree (Piastri, 6) indicates the champion. The 4-clique in the center of the large component took the top 4 places. The small component De Wilde – Lorandi comes from the season opener, where JD Motorsport team claimed the top two. Neither driver was in top two again, as the rest of the season was almost entirely a contest between R-ace GP and MP Motorsport. Not obvious from the graph: despite only appearing in top 2 once, as a second place in Spa, Collet took a handful of 3rd and 4th places on his way to the 5th place in overall standings and the top rookie title. The gap between 5th and 6th places was 207:102, more than a factor of 2, and the championship often felt like there were only 5 cars in the running, all from R-ace GP or MP Motorsport.
It was so close to Bottas-Verstappen finish, which would have completed the graph to , making it the first non-planar F1 graph in history. Could be that some Law of Planarity interfered, causing the yellow flags that denied Verstappen that final chance at overtaking Hamilton. No change to the graph, then.
Another feeder series fills up the spot, then: Formula Regional European Championship (FREC). An unimpressive affair from start to finish, to be frank. Yes, it was the first year the championship took place, and it’s supposed to play an important role as a stepping stone from F4 to FIA F3. (Few drivers can realistically jump into international F3 competition directly from F4, with Hauger and Pourchaire likely to be the only two to pull off this move in 2020.) Still, it is a travesty to award 25 Super License points – same as in Japanese Super Formula – for beating this small field of mostly under-tested cars and some under-prepared drivers. As Floersch put it,
Prema had three cars since November, so they’d been testing since November with three guys who actually can also drive. We had the cars one week before Paul Ricard and had one driver.
At least it was pretty close to a wheel graph. At its center, Vesti won the championship by a wide margin. I included the Fraga-Guzman edge based on my recollection of Guzman finishing second in the second race at Monza – the official standings table gives Guzman no points for any Monza race, as if there was a post-race DQ that nobody mentioned to the press (but given the level of organization, I would not be surprised if it was a clerical error).