Feeds:
Posts

## Estimating roots

In lieu of a real blog post, which will have to wait for at least another two weeks, let me offer an estimation exercise: bound, as best you can, the unique positive real root of the polynomial

$\displaystyle x^{10000} + x^{100} - 1$.

The intermediate value theorem shows that $x \in (0, 1)$, which was the subject of a recent math.SE question that provided the inspiration for this question. I provide a stronger lower bound on $x$ using elementary inequalities and entirely by hand in an answer to the linked question, although I don’t try to improve the upper bound.

## Lower bounds on off-diagonal Ramsey numbers

The goal of this post is to prove the following elementary lower bound for off-diagonal Ramsey numbers $R(s, t)$ (where $s \ge 3$ is fixed and we are interested in the asymptotic behavior as $t$ gets large):

$\displaystyle R(s, t) = \Omega \left( \left( \frac{t}{\log t} \right)^{ \frac{s}{2} } \right).$

The proof does not make use of the Lovász local lemma, which improves the bound by a factor of $\left( \frac{t}{\log t} \right)^{ \frac{1}{2} }$; nevertheless, I think it’s a nice exercise in asymptotics and the probabilistic method. (Also, it’s never explicitly given in Alon and Spencer.)

## Mathematics in real life

A small example, but I thought it was funny.

I am currently at Logan waiting for my flight to Heathrow. An hour or so ago, one of my friends asked me how long my flight is. I knew that my flight would depart at about 7:30pm and arrive at about 7:30am, but both times are local. So the actual length of the flight is about 12 hours minus the time difference – which I didn’t know!

But then I realized I could compute the time difference because I knew two other things – the average ground speed of a commercial airplane, and the circumference of the Earth. The average ground speed of a commercial airplane is about $600$ miles per hour, which I know from idly staring at that one channel that monitors the airspeed of a plane. The circumference of the Earth is $4 \times 10^4$ kilometers (to an accuracy of better than one percent!), which I know from preparing for the Fermi Questions event at Science Olympiad. (This is a very handy number to know for certain types of estimates, such as this one.) Given this number, it follows that the velocity of the surface of the Earth is about $1600$ kilometers per hour, or about $1000$ miles per hour.

Now, suppose the flight takes $x$ hours. Then I have traveled a distance of $600x$ miles, but at the same time I have crossed approximately $\frac{3}{5} x$ time zones. So the difference in local times should be approximately $\frac{8}{5} x$. Setting this equal to $12$ and rounding $\frac{3}{5} x$ to the closest integer, it follows that the time difference between Boston and London is $5$ hours (which it is) and that my flight will take $7$ hours (which it will).

An interesting idea this computation illustrates is that if you can estimate an integer (in this case, the number of time zones my flight will cross) with enough precision, you know it exactly. A more sophisticated variant of this idea is that a continuous function from a connected space to a discrete space must be constant.

(Full disclosure: I messed up the last step when I did this calculation the first time.)

## Test your intuition: consecutive tails

Something very unfortunate has happened: several things I have recently written that could have been blog entries are instead answers on math.SE! In the interest of exposition beyond the Q&A format I am going to “rescue” one of these answers. It is an answer to the following question, which I would like you to test your intuition about:

Flip $150$ coins. What is the probability that, at some point, you flipped at least $7$ consecutive tails?

Jot down a quick estimate; see if you can get within a factor of $2$ or so of the actual answer, which is below the fold.

## Optimizing parameters

I came across a fun problem recently that gave me a good opportunity to exercise my approximation muscles.

Problem: Compute $\displaystyle \lim_{n \to \infty} \frac{n + \sqrt{n} + \sqrt[3]{n} + ... + \sqrt[n]{n}}{n}$, if it exists.

The basic approach to such sums is that the first few terms contribute to the sum because they are large and the rest of the terms contribute to the sum because there are a lot of them, so it makes sense to approximate the two parts of the sum separately. This is an important idea, for example, in certain estimates in functional analysis.

Since $\sqrt[k]{n} \ge 1, k \ge 2$ it follows that the limit, if it exists, is at least $\lim_{n \to \infty} \frac{2n-1}{n} = 2$. In fact, this is the precise value of the limit. We’ll show this by giving progressively sharper estimates of the quantity

$\displaystyle E_n = \frac{1}{n} \sum_{k=2}^{n} \left( \sqrt[k]{n} - 1 \right)$.

In the discussion that follows I’m going to ignore a lot of error terms to simplify the computations.