In a Euclidean space, a set is compact if and only if it is closed and bounded. This fails in all infinite-dimensional Banach spaces (and in particular in Hilbert spaces) where the closed unit ball is not compact. However, one still has a simple description of compact sets:

A subset of a Banach space is compact if and only if it is closed, bounded, and flat.

By definition, a set is flat if for every positive number r it is contained in the r-neighborhood of some finite-dimensional linear subspace.

Notes:

The r-neighborhood of a set consists of all points whose distance to the set is less than r.

In a finite-dimensional subspace every subset is vacuously flat.

Necessity: Suppose K is a compact set. Every compact set is closed and bounded, this is true in all metric spaces. Given a positive number r, let F be a finite set such that K is contained in the r-neighborhood of F; the existence of such F follows by covering K with r-neighborhoods of points and choosing a finite subcover. Then the linear subspace spanned by F is finite-dimensional and demonstrates that K is flat.

Sufficiency: to prove K is compact, we must show it’s complete and totally bounded. Completeness follows from being a closed subset of a complete space, so the issue is total boundedness. Given r > 0, let M be a finite-dimensional subspace such that K is contained in the (r/2)-neighborhood of M. For each point of K, pick a point of M at distance less than r/2 from it. Let E be the set of all such points in M. Since K is bounded, so it E. Being a bounded subset of a finite-dimensional linear space, E is totally bounded. Thus, there exists a finite set F such that E is contained in the (r/2)-neighborhood of F. Consequently, K is contained in the r-neighborhood of F, which shows its total boundedness.

It’s worth noting that the equivalence of compactness with “flatness” (existence of finite-dimensional approximations) breaks down for linear operators in Banach spaces. While in a Hilbert space an operator is compact if and only if it is the norm-limit of finite-rank operators, some Banach spaces admit compact operators without a finite-rank approximation; that is, they lack the Approximation Property.

Laguerre polynomials have many neat definitions; I am partial to because it’s so easy to remember:

Begin with

Repeat “subtract the derivative” times

Normalize so the constant term is 1.

For example, for n=3 this process goes as to to to , which normalizes to . This would make a mean exercise on differentiating polynomials: every mistake snowballs throughout the computation.

What would happen if we added the derivative instead? Nothing really new: this change is equivalent to reversing the direction of the x-axis, so we’d end up with . Incidentally, this shows that the polynomial has positive coefficients, which means the behavior of for negative is boring: the values go up as becomes more negative. Laguerre polynomials are all about the interval on which they are orthogonal with respect to the weight and therefore change sign often.

But when I look at the plot shown above, it’s not the zeros that draw my attention (perhaps because the x-axis is not shown) but the horizontal line , the zero-degree polynomial. The coefficients of have alternating signs; in particular, and . So, nonconstant Laguerre polynomials start off with the value of 1 and immediately dive below it. All except the linear one, , eventually recover and reach 1 again (or so it seems; I don’t have a proof).

The yellow curve that is the first to cross the blue line is the 5th degree Laguerre polynomial. Let’s see if any of the other polynomials rises about 1 sooner…

Still, nobody beats (and the second place is held by ). By the way, the visible expansion of oscillations is approximately exponential; multiplying the polynomials by turns the envelopes into horizontal lines:

Back to the crossing of y=1 line. The quantity to study is the smallest positive root of , denoted from now on. (It is the second smallest root overall; as discussed above, this polynomial has a root at x=0 and no negative roots.) For n=2,3,4,5,6, the value of is which evaluates to 4, 3, 2.536…, 2.377…, and 6 respectively. I got these with Python / SymPy:

from sympy import *
x = Symbol('x')
[Poly(laguerre(n, x) - 1).all_roots()[1] for n in range(2, 7)]

For higher degrees we need numerics. SymPy can still help (applying .evalf() to the roots), but the process gets slow. Switching to NumPy’s roots method speeds things up, but when it indicated than and a few others are in double digits, I became suspicious… a closer check showed this was a numerical artifact.

Conjecture: for all . Moreover, when .

Here is a closer look at the exceptional polynomials of degrees 3, 4, 5 and 6, with 1 subtracted from each:

The first local maximum of shifts down and to the left as the degree n increases. The degree n=5 is the last for which exceeds 1 on the first attempt, so it becomes the quickest to do so. On the other hand, n=6 fails on its first attempt to clear the bar, and its second attempt is later than for any subsequent Laguerre polynomial; so it sets the record for maximal .

Evaluating high-degree Laguerre polynomials is a numerical challenge: adding large terms of alternating signs can reduce accuracy dramatically. Here is a plot of the degree 98 polynomial (minus 1): where is its first positive root?

Fortunately, SymPy can evaluate Laguerre polynomials at rational points using exact arithmetics since the coefficients are rational. For example, when it evaluates the expression laguerre(98, 5) > 1 to True, that’s a (computer-assisted) proof that , which one could in principle "confirm" by computing the same rational value of by hand (of course, in this situation a human is far less trustworthy than a computer) . Evaluation at the 13 rational points 3, 3.25, 3.5, … , 5.75, 6 is enough to certify that for up to 200 (with the aforementioned exception of ).

The lower bounds call for Sturm’s theorem which is more computationally expensive than sampling at a few rational points. SymPy offers a root-counting routine based on this theorem (it counts the roots within the given closed interval):

for n in range(2, 101):
num_roots = count_roots((laguerre(n,x)-1)/x, 0, 3)
print('{} roots for n = {}'.format(num_roots, n))

Division by x eliminates the root at 0, so we are left with the root count on (0,3] — which is 1 for n=3,4 and 2 for n=5. The count is zero for all other degrees up to 100, confirming that for .

So, the conjecture looks solid. I don’t have a clue to its proof (nor do I know if it’s something known). The only upper bound on that I know is Szegő’s for , which is not helping here.

Every real number in the interval [0,1] can be written in binary as where each coefficient is either 0 or 1. Another way to put this: the set of all possible sums for b = 1/2 is a line segment.

What is this set for other values of “base” b, then? Let’s stick to |b| < 1 for now, so that the series converges. Nothing interesting happens for real b between 1/2 and 1; the segment grows longer, to length b/(1-b). When b is between 0 and 1, we get Cantor sets, with the classical middle-third set being the case b = 1/3.

There is no need to consider negative b, because of a symmetry between b and -b. Indeed, up to scaling and translation, the coefficients can be taken from {-1, 1} instead of {0, 1}. Then it’s obvious that changing the sign of b is the same as flipping half of coefficients the other way — does not change the set of possible sums.

Let’s look at purely imaginary b, then. Here is b = 0.6i

Why so rectangular? The real part is the sum of over even k, and the imaginary part is the sum over odd k. Each of these yields a Cantor type set as long as . Since the odd- and even-numbered coefficients are independent of each other, we get the product of two Cantor sets. Which changes into a rectangle when :

(I didn’t think a full-size picture of a solid rectangle was necessary here.)

This is already interesting: the phase transition from dust to solid (connected, and even with interior) happens at different values in the real and imaginary directions: 1/2 versus . What will happen for other complex values? Using complex conjugation and the symmetry between b and -b, we reduce the problem to the quarter-disk in the first quadrant. Which still leaves a room for a lot of things to happen…

It’s clear that for |b| < 1/2 we get a totally disconnected set — it is covered by 2 copies of itself scaled by the factor of |b|, so its Hausdorff dimension is less than 1 when |b| is less than 1/2. Also, the argument of b is responsible for rotation of the scaled copies, and it looks like rotation favors disconnectivity… but then again, the pieces may link up again after being scaled-rotated a few times, so the story is not a simple one.

The set of bases b for which the complex Cantor set is connected is a Manderbrot-like set introduced by Barnsley and Harrington in 1985. It has the symmetries of a rectangle, and features a prominent hole centered at 0 (discussed above). But it actually has infinitely many holes, with “exotic” holes being tiny islands of disconnectedness, surrounded by connected sets. This was proved in 2014 by Calegari, Koch, Walker, so I refer to Danny Calegari’s post for an explanation and more pictures (much better looking than mine).

Besides “disconnected to connected”, there is another phase transition: empty interior to nonempty interior. Hare and Sidorov proved that the complex Cantor set has nonempty interior when ; their path to the proof involved a MathOverflow question The Minkowski sum of two curves which is of its own interest.

The pictures were made with a straightforward Python script, using expansions of length 20:

import matplotlib.pyplot as plt
import numpy as np
import itertools
n = 20
b = 0.6 + 0.3j
c = np.array(list(itertools.product([0, 1], repeat=n)))
w = np.array([b**k for k in range(n)]).reshape(1, -1)
z = np.sum(c*w, axis=1)
plt.plot(np.real(z), np.imag(z), '.', ms=4)
plt.axis('equal')
plt.show()

Since we are looking at partial sums anyway, it’s not necessary to limit ourselves to |b| being less than 1. Replacing b by 1/b only scales the picture, so the place to look for new kinds of pictures is the unit circle. Let’s try a 7th root of unity:

The set above looks sparse because many points overlap. Let’s change b to something non-algebraic:

Last time we found that when a sequence with and does not become periodic, its upper limit must be at least . This time we’ll see that can be as low as and determine for which it is equal to 1.

The quadratic polynomial maps the interval onto itself. Since the linear function maps onto , it follows that the composition maps onto . This composition is easy to compute: .

We want to know whether the iteration of , starting from , produces numbers arbitrarily close to . Since the goal is equivalent to finding whether the iteration of , starting from , produces numbers arbitrarily close to . To shorten formulas, let’s write for the th iterate of , for example, .

So far we traded one quadratic polynomial for another, . But satisfies a nice identity: , hence for all . It’s convenient to introduce , so that .

The problem becomes to determine whether the numbers come arbitrarily close to , modulo an integer multiple of . Dividing by rephrases this as: does the fractional part of come arbitrarily close to ?

A number that is close to has the binary expansion beginning either with or with . Since the binary expansion of is just the binary expansion of shifted digits to the left, the property is equivalent to the following: for every the binary expansion of has infinitely many groups of the form “1 followed by k zeros” or “0 followed by k ones”.

A periodic expansion cannot have the above property; this, must be irrational. The property described above can then be simplified to “irrational and has arbitrarily long runs of the same digit”, since a long run of s will be preceded by a , and vice versa.

For example, combining the pairs 01 and 10 in some non-periodic way, we get an irrational number such that the fractional part of does not get any closer to 1/2 than or . Hence, , which leads to the upper bound for the sequence with the starting value .

Let us summarize the above observations about .

Theorem: if and only if (A) the number is irrational, and (B) the binary expansion of has arbitrarily long runs of the same digit.

Intuitively, one expects that a number that satisfies (A) will also satisfy (B) unless it was constructed specifically to fail (B). But to verify that (B) holds for a given number is not an easy task.

As a bonus, let’s prove that for every rational number , except 0, 1/2 and -1/2, the number is irrational. This will imply, in particular, that yields a non-periodic sequence. The proof follows a post by Robert Israel and requires a lemma (which could be replaced with an appeal to Chebyshev polynomials, but the lemma keeps things self-contained).

Lemma. For every there exists a monic polynomial with integer coefficients such that for all .

Proof. Induction, the base case being . Assuming the result for integers , we have
which is a monic polynomial of .

Suppose that there exists such that . Then . By the lemma, this implies , that is . Since is a rational root of a monic polynomial with integer coefficients, the Rational Root Theorem implies that it is an integer.

Define the sequence as follows: and for . What can we say about its behavior as ?

The logistic map leaves the interval [0,1] invariant (as a set), so for all . There are two fixed points: 0 and 3/4.

Can ever be 0? If is the first index this happens, then must be . Working backwards, we find , and . But this is impossible since all elements of the sequence are rational. Similarly, if is the first index when , then and , a contradiction again. Thus, the sequence never stabilizes.

If had a limit, it would have to be one of the two fixed points. But both are repelling: , so and . This means that a small nonzero distance to a fixed point will increase under iteration. The only way to converge to a repelling fixed point is to hit it directly, but we already know this does not happen. So the sequence does not converge.

But we can still consider its upper and lower limits. Let’s try to estimate from below. Since for , the sequence increases as long as . Since we know it doesn’t have a limit, it must eventually break this pattern, and therefore exceed 3/4. Thus, .

This can be improved. The second iterate satisfies for between and . So, once (which, by above, happens infinitely often), the subsequence increases until it reaches . Hence .

The bound is best possible if the only information about is that the sequence does not converge. Indeed, is a periodic point of , with the corresponding iteration sequence .

Further improvement is possible if we recall that our sequence is rational and hence cannot hit exactly. By doubling the number of iterations (so that the iterate also fixes but also has positive derivative there) we arrive at the fourth iterate . Then for , where is the next root of after , approximately . Hence .

This is a colorful illustration of the estimation process (made with Sage): we are covering the line with the iterates of , so that each subsequent one rises above the line the moment the previous one falls. This improves the lower bound on from 0.75 to 0.9 to 0.92.

Although this process can be continued, the gains diminish so rapidly that it seems unlikely one can get to 1 in this way. In fact, one cannot because we are not using any properties of other than “the sequence is not periodic.” And it’s not true that for every non-periodic orbit of . Let’s return to this later.

Google’s BigQuery dataset now includes Stack Overflow data dump, including the text of over 50 million comments posted on the site. What do these comments say? I picked the most frequent ones and grouped them by topic. The counts are an underestimate: there is only so much time I was willing to spend organizing synonymous comments.

“Thank you” comments (128960 in total) are the most common by far. Typical forms: Thank you very/so much!, Thanks a lot :), Perfect, thanks! The popularity of the emoticon in the second version is attributable to the minimal length requirement for comments: they must contain at least 15 characters. The laziest way to pad the text is probably Thank you……

“You are welcome” (50090), presumably posted in response to group 1 comments. You’re welcome. You’re welcome! You’re welcome 🙂 Users need that punctuation or emoticon to reach 15 characters. Although those not contracting “you are” don’t have this problem.

“Updated answer” (30979) invites whoever raised objections about the previous version of the answer to read it again.

“What is your question?” (20830) is the most common type of critical comments toward questions.

“This is not an answer” (17306) is the most common criticism for answers; usually posted automatically by reviewers. Typical form: This does not provide an answer to the question. To critique or request clarification from an author, leave a comment below their post. Another one is for questions posted in the answer box: If you have a new question, please ask it by clicking the Ask Question button. Include a link to this question if it helps provide context.

“What error are you getting?” (13439) is a request for debugging information.

“What have you tried?” (12640) often comes with the link whathaveyoutried.com and is a sufficiently notorious kind of comments that Stack Overflow software deletes them if anyone “flags” the comment. And it’s easy to cast flags automatically, so I substantially reduced the number of such comments since this data dump was uploaded. Further context: Should Stack Overflow (and Stack Exchange in general) be awarding “A”s for Effort?

“Post your code” (11486) can sometimes be a form of “what have you tried”; in other times it’s a logical response to someone posting an error message without the code producing it. Can you post your code? Post your code. Please post your code. Show your code. Where is your code? And so on.

“It does not work” (9674) — either the question author, or someone else with the same issue did not benefit from the solution. Maybe it’s wrong, maybe they used it wrong.

“This is a link-only answer” (9501) usually comes from reviewers in the standard form While this link may answer the question, it is better to include the essential parts of the answer here and provide the link for reference. Link-only answers can become invalid if the linked page changes.

“I updated the question” (8060), presumably in response to critical comments.

“Why the downvote(s)?” (6005) is asking whoever voted down the post to explain their position. Usually fruitless; if the voter wanted to say something, they would already.

“This is a duplicate question” (3859) is inserted automatically when someone moves for a question to be marked as a duplicate. Such comments are normally deleted automatically when the required number of close-votes is reached; but some remain. The most common by far is possible duplicate of What is a Null Pointer Exception, and how do I fix it?

“I edited your title” (3795) is directed at users who title their questions like “Java: How to read a CSV file?”, using a part of the title as a tag. Standard form: I have edited your title. Please see, “Should questions include “tags” in their titles?“, where the consensus is “no, they should not”.

“Post a MCVE” (3775) – the line on which the error is thrown is probably not enough to diagnose the problem; on the other hand, a wall of code with an entire program is too much. One of standard forms: Questions seeking debugging help (“why isn’t this code working?”) must include the desired behavior, a specific problem or error and the shortest code necessary to reproduce it in the question itself. Questions without a clear problem statement are not useful to other readers. See: How to create a Minimal, Complete, and Verifiable example.

“That is correct” (3158) usually refers to a statement made in another comment.

“It works” (3109) is the counterpart of group 9 above. Often used with “like a charm” but do charms actually work?

“What do you mean?” (2998) – for when an exchange in comments leads to more confusion.

“What tool are you using?” (2649) indicates that the question author forgot to specify either the language, OS, or the DBMS they are using.

“Good answer” (2607) – various forms of praise, This should be the accepted answer. This is the correct answer. Excellent answer! The first form additionally indicates that the question author did not pick the best answer as “accepted”.

“This question is off-topic” (2377) is a template for close votes with a custom explanation. For some years Stack Overflow used This question appears to be off-topic because… but then switched to the more assertive I’m voting to close this question as off-topic because…

“This is a low quality answer” (2003) is a response to answers that contain nothing but code, perhaps preceded by “try this”. Example: While this code snippet may solve the question, including an explanation really helps to improve the quality of your post. Remember that you are answering the question for readers in the future, and those people might not know the reasons for your code suggestion.

“Is this homework?” (1995) is not a particularly fruitful type of comments.

“Does this work?” (1916) is meant to obtain some response from question asker who has not yet acknowledged the answer.

“The link is dead” (1250) is a major reason why group 10 comments exist.

“http://stackoverflow.com/help/ . . .” (1117) and nothing but the link. Directs to one of Help Center articles such as “How to ask”. Maybe there should also be “How to Comment”

“Thanks are discouraged” (1046) … so all those group 1 comments aren’t meant to be. But this is mostly about posts rather than comments. Unlike forum sites, we don’t use “Thanks”, or “Any help appreciated”, or signatures on Stack Overflow. See “Should ‘Hi’, ‘thanks,’ taglines, and salutations be removed from posts?.

“Format your code” (967) – yes, please. Select the code block and press Ctrl-K. Thanks in advance. Oops, forgot about the previous group.

“What doesn’t work?” (926) is a response to vague comments of group 9.

“Add tags” (625) often comes up in the context of database questions. Which RDBMS is this for? Please add a tag to specify whether you’re using `mysql`, `postgresql`, `sql-server`, `oracle` or `db2` – or something else entirely.

“Improve title” (585) is like group 14, but invites the user to edit the title instead of doing it for them.

“Use modern JOIN syntax” (301) bemoans obsolete ways of dealing with databases. Bad habits to kick : using old-style JOINs – that old-style *comma-separated list of tables* style was replaced with the *proper* ANSI `JOIN` syntax in the ANSI-92 SQL Standard (more than 20 years ago) and its use is discouraged.

A frequently asked question about numerical integration is: how to speed up the process of computing for many values of parameter ? Running an explicit for over the values of seems slow… is there a way to vectorize this, performing integration on an array of functions at once (which in reality means, pushing the loop to a lower level language)?

Usually, the answer is some combination of “no” and “you are worrying about the wrong thing”. Integration routines are typically adaptive, meaning they pick evaluation points based on the function being integrated. Different values of the parameter will require different evaluation points to achieve the desired precision, so vectorization is out of question. This applies, for example, to quad method of SciPy integration module.

Let’s suppose we insist on vectorization and are willing to accept a non-adaptive method. What are our options, considering SciPy/NumPy? I will compare

The test case is with . Theoretically all these are equal to . But most of these functions are not analytic at , and some aren’t even differentiable there, so their integration is not a piece of cake.

Keeping in mind that Romberg’s integration requires subintervals, let’s use equal subintervals, hence equally spaced sample points. Here is the vectorized evaluation of all our functions at these points, resulting in a 2D array “values”:

import numpy as np
import scipy.integrate as si
x = np.linspace(0, 1, 1025).reshape(1, -1)
dx = x[0,1] - x[0,0]
p = np.arange(0, 100, 0.01).reshape(-1, 1)
values = (p+1)*x**p

This computation took 0.799 seconds on my AWS instance (t2.nano). Putting the results of evaluation together takes less time:

Trapezoidal rule np.trapz(values, dx=dx) took 0.144 seconds and returned values ranging from 0.99955 to 1.00080.

Simpson’s rule si.simps(values, dx=dx) took 0.113 seconds and returned values ranging from 0.99970 to 1.0000005.

Romberg quadrature si.romb(values, dx=dx) was fastest at 0.0414 seconds, and also most accurate, with output between 0.99973 and 1.000000005.

Conclusions so far:

SciPy’s implementation of Romberg quadrature is surprisingly fast, considering that this algorithm is the result of repeated Richardson extrapolation of the trapezoidal rule (and Simpson’s rule is just the result of the first extrapolation step). It’d be nice to backport whatever makes Romberg so effective back to Simpson’s rule.

The underestimation errors 0.999… are greatest when is near zero, so the integrand is very nonsmooth at . The lack of smoothness renders Richardson extrapolation ineffective, hence all three rules have about the same error here.

The overestimation errors are greatest when is large. The function is pretty smooth then, so upgrading from trapezoidal to Simpson to Romberg brings substantial improvements.

All of this is nice, but the fact remains that non-vectorized adaptive integration is both faster and much more accurate. The following loop with quad, which uses adaptive Clenshaw-Curtis quadrature, runs in 0.616 seconds (less than it took to evaluate our functions on a grid) and returns values between 0.99999999995 and 1.00000000007. Better to use exponential notation here: and .

funcs = [lambda x, p=p_: (p+1)*x**p for p_ in np.arange(0, 100, 0.01)]
result = [si.quad(fun, 0, 1)[0] for fun in funcs]

An adaptive algorithm shines when is small, by placing more evaluation points near zero. It controls both over- and under- estimates equally well, continuing to add points until the required precision is reached.

The last hope of non-adaptive methods is Gaussian quadrature, which is implemented in SciPy as fixed_quad (“fixed” referring to the number of evaluation points used). With 300 evaluation points, the integration takes 0.263 seconds (excluding the computation of nodes and weights, which can be cached) and the results are between and . This is twice as fast as a loop with quad, and more accurate for large — but sadly, not so accurate for small . As said before, with near zero is really a showcase for adaptive methods.