Paul Liu

My Favourite Proof

2012-04-22T22:36:00.000-07:00

This post is inspired and adapted from Greg Martin's excellent talk on prime numbers (found here).

As a student of mathematics, one of the first things I ever learned was the concept of a proof. In fact, the first proof I ever saw was Euclid's classic proof that there were an infinite number of primes.

If you have never seen Euclid's proof before, it goes something like this:

Suppose there were a finite number of primes. We may label them $p_1, p_2, \ldots, p_n$. Let \[N=p_1 p_2 \ldots p_n + 1.\] Now for every prime $p_i,\,1\leq i\leq n$ that we just labelled, the remainder of $N$ divided by $p_i$ is 1. However, since $N$ is not prime, $N$ must be able to be factorized into a product of primes. What primes are in that factorization if it doesn't contain any of the primes we just listed out?

Hence, $N$ must have some new prime in its factorization or be a prime itself. This contradicts our assumption that there are a finite number of primes, and therefore an infinite number of primes must exist. $\blacksquare$

Recently, I learned that a variant of Euclid’s proof can be used to prove the infinitude of primes of the form 4k-1 and 6k-1. The proof for 4k-1 is below:

Suppose there are a finite number of primes that is of the form 4k-1 for some $k\in\mathbb{N}$. Again, we may label them $p_1, p_2, \ldots, p_n$. Let \[N=4 p_1 p_2 \ldots p_n - 1.\] Again, for every prime $p_i,\,1\leq i\leq n$ that we just labelled, the remainder of $N$ divided by $p_i$ is 1. Note that $N$ is not prime since it is of the form 4k-1 but greater than any of our $p_i$. However, since $N$ is not a prime, $N$ must be able to be factorized into a product of primes.

Furthermore, the factorization of $N$ must only contain primes of the form 4k+1 since $N$ is odd and all primes of the form 4k-1 are used. This is a contradiction since two numbers which are of the form 4k+1 must have a product of the form 4k+1. Hence, if $N$ was entirely the product of primes of the form 4k+1, $N$ must be a number of the form 4k+1 also. But since $N$ is obviously not expressible as 4k+1, $N$ must itself be a prime that is of the form 4k-1 or have some new prime factor that is of the form 4k-1. Again, by contradiction, there must exist an infinite number of primes of the form 4k-1. The case for 6k-1 is similar. $\blacksquare$

Amazingly, there is a general theorem which states that a Euclid-style proof can only be used to prove the infinitude of primes of the form $p \equiv a\bmod{m}$, where $a^2 \equiv 1 \bmod{m}$ for any two natural numbers $a$ and $m$ (proven here by Murty, 1988). For example, this means that infinitude any primes of the form $p \equiv -1 \bmod 4$ may be proven (as we did above), but any primes of the form $p \equiv 3 \bmod 7$ cannot be proven by Euclid's proof.

I find Euclid’s classic proof of the infinitude of primes beautiful -- not just because it establishes an amazing result in an elegant way, but because of its vast reusability. For these reasons, it is easily my favourite proof.

Bonus: From the theorem above, we may also prove infinitude of primes of the form 4k+1 by a Euclid style proof. Try proving this statement! Be warned though, there is an extra trick to defining $N$ than just multiplying all primes of the form 4k+1 together. The solution can be found in the slides of Greg Martin, as referenced in the first sentence of this post.

First they came...

2012-01-23T00:05:00.000-08:00

A very powerful quote that was brought to my attention by a commenter on Hacker News on the proposed Polish Anti-Counterfeiting Trade Agreement. When citizens are inactive on bad government reforms, what seems like one small alteration could build up to monumental changes.

First they came for the communists, and I didn't speak out because I wasn't a communist.

Then they came for the trade unionists, and I didn't speak out because I wasn't a trade unionist.

Then they came for the Jews, and I didn't speak out because I wasn't a Jew.

Then they came for the Catholics, and I didn't speak out because I was Protestant.

Then they came for me and there was no one left to speak out for me.

Martin Niemöller - First They Came

Prove this identity

2011-08-15T16:50:00.000-07:00

A note to future me:

Today you were trying to do probability questions with your pathetically sad probability skills and you found that
\[\sum_{i=0}^{n-1}\frac{m}{t-i}\frac{\binom{t-m}{i}}{\binom{t}{i}}=1-\frac{\binom{t-m}{n}}{\binom{t}{n}}.\]
Dare you to prove it.

From,
Your arrogant younger self.

Here's a hint:
\[\frac{\binom{t-m}{i}}{\binom{t}{i}}=\frac{\binom{t-i}{m}}{\binom{t}{m}}.\]
Why? Can you think of a combinatorial interpretation for this? Proving it through algebra is trivial. Thinking of an interpretation may lead to some actual learning.

Bonus:
From the identity above, you also managed to find that it implies: \[\sum _{i=0}^n \binom{t-i}{m}=\binom{t+1}{m+1}-\binom{t-n}{m+1}.\] Prove this identity.

A curious identity

2011-08-06T16:38:00.000-07:00

I was trying to do a question the other day when I found an interesting identity that is a corollary of the double angle formulae. I've searched online for its name, but it might be so trivial that it doesn't have one. Instead of revealing the identity, I'll let you figure it out for yourself:
\[\frac{1}{2^0}\cos(x_1) = \cos(x_1)\]
\[\frac{1}{2^1}\left(\cos(x_1+x_2)+\cos(x_1-x_2)\right)=\cos(x_1)\cos(x_2)\]
\[\frac{1}{2^{2}}\left(\begin{array}{c}
\phantom{+}\cos(x_{1}+x_{2}+x_{3})\\
+\cos(x_{1}+x_{2}-x_{3})\\
+\cos(x_{1}-x_{2}+x_{3})\\
+\cos(x_{1}-x_{2}-x_{3})\end{array}\right)=\cos(x_{1})\cos(x_{2})\cos(x_{3})\]
Do you see the pattern?
Can you prove the pattern (Hint: Try induction)?
Are there other similar identities involving sines and combinations of sines and cosines?

For those who are curious, the question that led me to this identity was:
Determine the value of \[\cos\left(\frac{\pi}{7}\right)\cos\left(\frac{2\pi}{7}\right)\cos\left(\frac{4\pi}{7}\right).\]

There is a simple way to do this question, and a hard way. Sadly the identity I found led to the hard way.

Need Practice for the GRE?

2011-08-01T19:32:00.000-07:00

Have I got the site for you (see title).

Upon the grave realization that I'll have to take the Physics and Math GRE in a couple years (oh yes, I prepare YEARS in advance), I've started a site that updates daily with Math and Physics GRE questions. Come visit (link below), it'll be fun.

Let us go then, you and I.

Thin Cars and Parking Lots

2011-07-17T01:37:00.000-07:00

A quick question I came across today:

Suppose you had an infinitely thin car. How big do you have to build a parking lot for the car to be able to turn 180 degrees in the parking lot?

Think about it for a while, and then highlight the area below to see the answer.

Surprisingly, there is no lower limit on the size of the parking lot. In other words, the parking lot can be as small as you want.

This is better known as the (thinly disguised) Kakeya Needle Problem. Unfortunately, the proof relies on existence theorems which (as far as I know) do not provide an explicit way to show us how we can jiggle the car around until it rotates 180 degrees. So while it might cool to tell your friend you can turn an infinitely thin car on a parking lot with zero area, I know of no way that you can physically show how it can be done.

Number of Primes with Desired Digit Strings

2011-07-10T19:11:00.000-07:00

This post was previously very, very wrong. It has been corrected as of July 12th, 2011.

Greetings and salutations to my loyal readers (there are about 30 of you I think)!

I've been a bit busy recently organizing an online study group for The Feynman Lectures on Physics, so today I'll just post a short note based on an observation someone made about my last post on the Kempner series.

The observations was that since the prime harmonic series (1/2 + 1/3 + 1/5 + 1/7 + 1/11 + ...) diverges, we can take out all the terms with a specific sequence of digits to make the series convergent as we did with the harmonic series. Or in other words:

"given any finite string of numbers, i.e. 24485983 that there exist infinitely many primes whose base 10 representation contain that string."

We knew from the my last post that the harmonic series became convergent if we took out all the terms with a '9' (or more generally any string of digits). For example, we could take out all primes with the digit string '13'. This would make the harmonic series convergent (after removing all the terms with '13'). Now consider the prime harmonic series, which is a subset of the original full harmonic series. Since the prime harmonic series diverges to infinity, we must have taken out an infinite number of primes with '13'. Therefore, the conclusion is that there are an infinite number of primes with any string of digits you can imagine.

The purpose of this note was to show that the same conclusion could be reached via a direct proof rather than as a corollary of another proof. However, I realized that my direct proof had a rather large flaw in it. As a cop-out, I'll show in this note that one can prove this result as a corollary of another theorem, namely Dirichlet's theorem for prime progressions.

Proof

Dirichlet's theorem states that there are infinitely many primes in the arithmetic sequence \[a, a+d, a+2d, a+3d, \ldots\] where $a$ and $d$ are coprime.

To prove that there are infinitely many primes which contain '13', set $a=13$ and $d=100$. We get the sequence 13, 113, 213, ... in which all terms contain the digit string '13' and by Dirichlet's theorem must contain an infinite number of primes.

$\blacksquare$

Although we used Dirichlet's theorem for showing this particular result, there are other theorems we could have used as well. For example, we could have used the fact that the prime counting function $\pi(x)$ is bound by \[\frac{1}{2}\frac{x}{\log(x)}<\pi(x)<2\frac{x}{\log(x)}.\]
Just so I don't feel like a complete hack, here are some exercises for you guys.

Exercises

Prove that there are infinitely many primes containing 42 (if you use Dirichlet's Theorem, use it carefully).
Prove that there are infinitely many primes starting with the digits 42.

The Kempner Series - A modified harmonic series

2011-07-02T11:00:00.000-07:00

The harmonic series is considered a classic textbook example of a series that seems to converge but is actually divergent. For those that need a reminder, the harmonic series is: \[\sum_{n=1}^{\infty}\frac{1}{n}=1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}\cdots.\]
Now here's an interesting question:

How can we modify the harmonic series to make it convergent?

Disregarding trivial answers such as "remove all the terms", this question is actually pretty hard to answer. Say we removed every second term starting from the first (i.e. 1, 1/3, 1/5, etc). Would that work?
\[\sum_{\substack{n=1 \\ n\ is\ even}}^{\infty}\frac{1}{n}=\frac{1}{2}+\frac{1}{4}+\frac{1}{6}+\frac{1}{8}\cdots=\frac{1}{2}\left(1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}\cdots\right).\]
From above, it seems like it would not work since it just produces half of the original series (which is not a very well defined quantity since the original series was divergent anyway).

Another way to modify the harmonic series

Instead of removing every second term, let us remove every term with a 9 in it (i.e. remove 1/9, 1/19, 1/29, etc). This series is called the Kempner series: \[1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{8}+\frac{1}{10}+\cdots.\]Although removing every term with a 9 doesn't seem like a lot, this bizarrely modified harmonic series is actually convergent (it is also convergent if you choose to remove any other digit/string of digits such as "0", "42", or "8675309")!

We can now state the formal question as:

Consider the series: \[a_{n}=\begin{cases}1/n & if\ n\ does\ not\ contain\ the\ digit\ 9 \\ 0 & otherwise\end{cases}\] Is $\sum a_n$ convergent?

Instead of starting the proof right away, let's look at why this modification to the harmonic series might make it convergent.

The plots below read 1 whenever an integer contains the digit 9, and 0 otherwise.

Upper left: Plot from 1 - 9, Upper right: Plot from 10 - 99, Lower left: Plot from 100 - 999, Lower Right: Plot from 1000 - 9999.

As you can see, the plots have a nice "fractal" quality to them, in that each plot looks like it makes up parts of the next plot. Although the actual number of terms removed by the modification seems fewer than doing something like removing every second term, we can see that there are always points in the series where a long stretch of consecutive terms are removed (in fact, name a number and we can always find a point in the series where the number of consecutive terms removed is greater than that number). As the number of digits in the terms get large, the number of terms we remove increase drastically. As an example, most integers of say 100 digits will have a 9 in them, leading to about 99.99997% of the 100 digit terms being deleted. It is the quirky effect of removing consecutive terms as well as the fractal quality of the series that will allow us to see and prove its convergence.

Just exactly how many terms are removed though?

To do this systematically, we'll exploit the pattern we saw in the plots above. That is, since the plots seem to exhibit fractal qualities in the ranges ([1,9], [10,99], [100, 999] ...) that they are plotted, we'll look at the number of terms removed inside these ranges.

For the interval [1,9], only 1 term is removed. Note that this range starts at 1 because the harmonic series starts at n=1.

For the interval [10, 99], we have 1 term removed from each of 10 - 19, 20 - 29, 30 - 39, ... , 80 - 89. Then we have 10 terms removed from 90 - 99. In total, we have 8 terms removed from 10 - 89, and a further 10 terms removed from 90 - 99. This makes for 8*1 + 10 = 18 terms removed.

For the interval [100, 999], there is one term removed from 100 - 109, 18 terms removed from 110 - 199, 1 term removed from 200 - 219, 18 terms removed from 220 - 299, and so on, with the last being 18 terms removed from 800 - 899 terms. Finally, we have 100 terms removed from [900, 999]. In total this is 8*1 + 8*18 + 10² = 252 terms removed.

Perhaps you are seeing a pattern here. Let's try to make out what that pattern is. Instead of looking at the number of terms removed, let's look at the number of terms we are keeping.

For the interval [1,9], we keep 9 - 1 = 8 terms.
For the interval [10, 99], we keep 90 - 18 = 72 terms.
For the interval [100, 999], we keep 900 - 252 = 648 terms.
The pattern is 8, 72, 648. Dividing by 8, we have the pattern 1, 9, 81. We can see that the next number in the sequence will be 81*9 = 729, making the number of terms kept 8*729 = 5832. So the number of terms kept in a given interval $[10^n,10^{n+1}-1]$ is $8\cdot 9^n$. We will assume this knowledge (though it can be proven by standard methods of mathematical induction) for the proof below.

Before we start the proof, we now can see why our modification to the series is so effective. Consider all integers containing 100 digits. There are $9\cdot 10^{99}$ of them. The number of terms that are kept is $8\cdot 9^{99}$. The fraction of terms that are kept is thus \[\frac{8\cdot 9^{99}}{9\cdot 10^{99}}\approx0.0000262335.\] We took out a lot of terms!

The proof
Consider the series: \[a_{n}=\begin{cases}1/n & if\ n\ does\ not\ contain\ the\ digit\ 9 \\ 0 & otherwise\end{cases}\] Is $\sum a_n$ convergent?

We know from the section above that the number of terms that are not 0 in $a_n$ on an interval $[10^n,10^{n+1}-1]$ is $8\cdot 9^n$. Moreover, the largest term of the harmonic series in each interval $[10^n,10^{n+1}-1]$ is $\frac{1}{10^n}$.

Therefore, we can provide an upper bound for $\sum a_{n}$:
\[\sum a_{n}<\sum8\cdot9^{n-1}\cdot\frac{1}{10^{n-1}}=\sum8\cdot\left(\frac{9}{10}\right)^{n-1}.\] The right hand side is a convergent geometric series with sum \[8\sum_{n=1}^{\infty}\left(\frac{9}{10}\right)^{n-1}=80.\] Thus, $\sum a_n$ is convergent by comparison.

$\blacksquare$

Extra tidbits

Although we have proven the convergence of this series when the digit 9 removed, the series is convergent if you remove any digit or string of digits. For example, when all numbers with "42" is removed from the harmonic series, the sum of the series is about 230. When all 9's are removed, the sum of the series is about 23.

Although the Kempner series converges, the convergence rate is extremely slow. After summing about 10 million terms, I am still 9 off from 23. It is known that even after summing 10²⁷ terms, the sum is still about 1 off from 23. Can you think of a way to make the series sum faster?

References
1. The source of the question is from an old professor of mine, whose page can be found here (under teaching and Science One).
2. R. Baillie, Sums of Reciprocals of Integers Missing a Given Digit, American Mathematical Monthly 86, 372-374.
3. T. Schmelzer and R. Baillie, Summing a Curious, Slowly Convergent Series, American Mathematical Monthly 115, 525-540.

$\frac{d}{dx}(f(x)g(x)) \neq f^\prime(x)g^\prime(x)$? Think again!

2011-06-25T15:30:00.000-07:00

One of the most unintuitive and frustrating facts about calculus is that \[\frac{d}{dx}(f(x)g(x))\neq f^\prime(x)g^\prime(x).\]
It is said in certain apocryphal tales that the great man himself once made the above mistake. Instead of the pretty but untrue equation above, we have the unsightly but true "product rule":
\[\frac{d}{dx}f(x)g(x)= f(x)g^\prime(x)+f^\prime(x)g(x).\]

If you're like me, you'll despise this terrible rule for all the extra algebra it usually introduces into typical calculus questions. My wrists would often hurt from applying and reapplying the product rule in repeated differentiations. So, with a bit of free time and a a desire for vengeance, I have compiled a list of functions (zoom in if you cannot see some of the variables) for which the equation \[\frac{d}{dx}(f(x)g(x))=f^\prime(x)g^\prime(x)\] is absolutely positively true. Take that product rule (all c's, n's, and a's are arbitrary constants)!

\[f(x)=c_{1}, g(x)=c_{2}\]
\[f(x)=c_{1}(a+nx)^{\frac{1}{n}}, g(x)=c_{2}(a+nx-1)^{-\frac{1}{n}}\]
\[f(x)=c_{1}e^{nx}, g(x)=c_{2}e^{\frac{n}{n-1}x}\]
\[f(x)=c_{1}e^{x}(a^{nx}-1)^{-\frac{1}{n\log(a)}}, g(x)=c_{2}e^{-\frac{a^{-nx}}{n\log(a)}}\]

"Pfft," you say. "I could have guessed those ones!" Well, let's make things a little more exciting and introduce some trig.

\[f(x)=c_{1}\left(1-a\arccos(\sin(nx))\right)^{\frac{\sqrt{\cos^{2}(nx)}\sec(nx)}{an}}, g(x)=c_{1}\arccos(\sin(nx))^{-\frac{\sqrt{\cos^{2}(nx)}sin(nx)}{an}}\]
\[f(x)=c_{1}e^{\frac{\coth(a+nx)}{n}}, g(x)=c_{2}e^{\frac{\tanh(a+nx)}{n}}\]
\[f(x)=c_{1}e^{\frac{-\cot(a+nx)}{n}}, g(x)=c_{2}e^{\frac{\tan(a+nx)}{n}}\]

That wasn't much. Let's step it a notch (at this point you will appreciate the ability on this blog to zoom on the formulae to any degree).

\[f(x)=c_{1}e^{\frac{2\arctan\left(\tanh\left(\frac{a+nx}{2}\right)\right)}{n}}, g(x)=c_{1}e^{\frac{\coth\left(\frac{a+nx}{2}\right)}{n}}\]
\[f(x)=c_{1}e^{\frac{2(a+nx)+\sin(2(a+nx))}{4n}}, g(x)=c_{2}e^{\frac{\cot(a+nx)}{n}+x}\]

Finally, I found these gems after a bit of searching. Beautiful, right?

\[f(x)=c_{1}\exp\left(-\frac{2\arctan\left(\frac{a-\tan\left(\frac{nx}{2}\right)}{\sqrt{1-a^{2}}}\right)}{n\,\sqrt{1-a^{2}}}\right), g(x)=c_{2}\sin\left(\frac{nx}{2}\right)^{\frac{1}{an}}\cos\left(\frac{nx}{2}\right)^{-\frac{1}{an}}\]
\[f(x)=c_{1}\exp\left(\frac{2\sin\left(\frac{a+nx}{2}\right)\left(\csc\left(\frac{a}{2}\right)\sin\left(\frac{nx}{2}\right)-nx\sin\left(\frac{a+nx}{2}\right)\right)}{n(\cos(a+nx)-1)}\right), g(x)=c_{2}e^{\frac{\sin(a+nx)}{n}}\]
\[f(x)=c_{1}\exp\left(\frac{nx-a\log(a\sin(nx)-\cos(nx))}{a^{2}n+n}\right), g(x)=c_{2}\sin(nx)^{\frac{1}{an}}\]

These functions all obey the "nice" product rule \[\frac{d}{dx}(f(x)g(x))=f^\prime(x)g^\prime(x)\] with typical restrictions such not allowing constants which cause divisions by zero.

So how did I do it?
A bit of calculus and creativity.

Using the product rule on the original equation:
\[(f(x)g(x))^{\prime}=f^{\prime}(x)g^{\prime}(x)\] \[f(x)g^{\prime}(x)+f^{\prime}(x)g(x)=f^{\prime}(x)g^{\prime}(x)\]

Dividing both sides by $f^{\prime}(x)g^{\prime}(x)$ we obtain:

\[\frac{f(x)}{f^{\prime}(x)}+\frac{g(x)}{g^{\prime}(x)}=1\]
Now comes the creative part. I pick a function, say $x+(1-x)=1$. Let $\frac{f(x)}{f^{\prime}(x)}=x$, $\frac{g(x)}{g^{\prime}(x)}=1-x$

We now have two differential equations we can solve:

\[\frac{f}{f^\prime}=x,\frac{g}{g^\prime}=1-x\]

Solving these differential equations we obtain:

\[f(x)=c_{1}x,g(x)=\frac{c_{2}}{1-x}\]

which obey the nice equation \[\frac{d}{dx}(f(x)g(x))= f^\prime(x)g^\prime(x).\]

The more functions that you can think of which adds up 1, the more functions you can produce which obey our "nice" product rule.

I'd love to see what you guys can come up with, so post your functions in the comments below! To make it more challenging, try to make the functions you find as general as possible, and only find functions which are composed of elementary functions!

Making your own pendulum wave machine

2011-06-21T16:08:00.000-07:00

This post is a continuation of a three part post started here.

To make your own pendulum wave machine, you can see from the video that you just need to place 15 pendula or so beside each other at equal separations. What is hard to see however, is how long the length of string should be. Below we'll derive a function for you to calculate the lengths of each pendulum on your machine (or just scroll to the bottom to see some precalculated lengths).

In the small angle approximation, the period of a pendulum is \[T=2\pi\sqrt{\frac{l}{g}}\implies \omega=\frac{2\pi}{T}=\sqrt{\frac{g}{l}}\] where $g$ is 9.8 m/s and $l$ is the length of the pendulum.

Since length of the pendulum depends on its location on the apparatus, we have $l(n)$ instead of a constant $l$ (where $n$ is the pendulum number). Putting it all together, \[\omega(x)=\sqrt{\frac{g}{l(x)}}.\]

But we also know from the previous post that \[\omega(x)=\frac{2\pi}{T}=\frac{2\pi \left(N+\frac{x}{d}\right)}{\Gamma}=\frac{2\pi \left(N+n\right)}{\Gamma}.\]

Isolating for $l(n)$, we have \[l(n)=g\left(\frac{\Gamma}{2\pi\left(N+n\right)}\right)^2\] where $\Gamma$ is the duration for the entire dance (60s in the video), $N$ is the number of oscillations the longest pendulum performs in the cycle (51 in the video - I always mistake this for the number of pendula for some reason), $n$ is the pendulum index (starting from 0).

As an example, we can calculate the lengths of the pendula in the video of the previous post.

Pendulum Index	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
Length (m)	0.343	0.330	0.318	0.306	0.295	0.285	0.275	0.265	0.256	0.248	0.240	0.232	0.225	0.218	0.211

You can calculate your own pendulum lengths on the online spreadsheet file I've posted here.

UPDATE: I've newer much better simulations and calculators. You can find them at https://cs.stanford.edu/people/paulliu/webapps/pendulumcalc.html,
https://cs.stanford.edu/people/paulliu/webapps/pendulum.html

All that left to do is decide on the dimensions of your pendulum wave machine. For example, if I wanted to make the machine above, I'd place each pendulum above 5 cm apart, making the entire machine at least 70 cm long and 34.3 cm tall. However, one thing to note is that these pendulum wave demonstrations are made perfect by careful timing of the periods on each pendulum, not by careful measurement of the pendulum lengths. As such, make the individual pendulums on your machine adjustable! The very first design of this demonstration used 15 adjustable screws to which each pendulum tied on to. By carefully adjusting each screw and timing each pendulum, the correct number of oscillations can be tuned for each individual pendulum.

That's all there is to it, I'll leave the nitty-gritty details of the design to all you talented folks out there. They make for great gifts! I made my girlfriend one for her birthday and she loved it! OK, that was a lie. But it did get her parents to like me.

Pendulum Waves - Mathematical Description cont. 2

2011-06-21T16:07:00.000-07:00

If you missed the first two parts to this post, you can start here to get some context.

Well, perhaps the equation is not fantastically clear to you how the waves act at all (don't worry, it's not clear to me either). Let's actually graph this equation and figure out how to make sense of it.

This is a top view of the pendulum wave machine. The x-axis represents the pendulums location on the machine, the y-axis represents each pendulums displacement from equilibrium.

We can see that at the beginning, all pendula are exactly in phase at maximum amplitude, as expected. Afterwards, we see a series of patterns until we reach the middle of the "dance", during which all adjacent pendula are exactly out of phase. After this, the dance plays out in the reverse order until we get all the pendulums back in phase again.

If you want to explore this graph dynamically and play around with a simulation of the pendulum waves (and have Mathematica/Wolfram CDF Player), go to this interactive demonstration.

Whats wrong with the graphs we see above?

Well, whats what is that although the pendulum dance seems periodic, the equation we've figured out tells us that it's not. As you can see, the function $y(x,t)$ has increasingly smaller wavelengths as time progresses. It's only by looking at specific points on the function (i.e. by looking at where the pendula are located) that we get the illusion of a periodic function.

The proper term for this phenomenon is aliasing (an example is below - from Wikipedia):

I think you get the idea of what type of confusion aliasing can cause.

With the function we've derived, we could check many things mathematically, such as the symmetry of the patterns before and after $\frac{\Gamma}{2}$ as well as whether we'll get the same patterns in the time from 0 to $\Gamma$ vs. $\Gamma$ to $2\Gamma$. If you want to see these properties shown from our function, the original paper that this derivation was distilled from can be found in the references below. If there are enough requests for me to show these properties on my blog, I'll be glad to write another post.

If you wish to apply the equation we've derive to make your own pendulum wave machine, see my next post.

***********

References:

[1] Harvard Demonstrations - Simple Harmonic Motion
[2] J. Flatten and K. Parendo, Pendulum Waves: A lesson in aliasing, American Journal of Physics 69, 778-782 (2001).
[3] R. Berg, Pendulum Waves: A demonstration of wave motion using pendula, American Journal of Physics 59, 186-187 (1991).

Pendulum Waves - Mathematical Description cont.

2011-06-21T16:06:00.000-07:00

This is the second of a three part post on mathematically explaining the pendulum waves apparatus (below). The first part is located here.

We'll start off from where we ended last time.
We had two possible equations that we could use to continue our derivation with:

\[y(x,t)=A\cos\left(k_{0}x+\omega(x)t\right)\]\[y(x,t)=A\cos\left(k(t)x+\omega_{0}t\right).\]

Let's use the first of the two equations above.

Since we start the pendulum waves by setting all the pendula to maximum amplitude, we have \[y\left(x,0\right)=A=A\cos\left(k_{0}x+\omega\left(0\right)\cdot0\right)\]\[A=A\cos\left(k_{0}x\right)\implies k_{0}=0.\]

Let's figure out what $\omega(x)$ is. We'll forget about $\omega$ as a function of $x$ for a moment and look at $\omega$ as a function of the n-th pendulum instead.

Recall that the total time of the dance is $\Gamma$ during which the longest pendulum performs $N$ oscillations. So the period of the longest pendulum is $T=\frac{\Gamma}{N}$. OK, so we have the period of one pendulum now. How do we figure out the gabajillion other pendulums on the thing? Well, we also know that as the pendulums get shorter, their number of oscilations increases. More specifically, if the longest pendulum has 51 oscillations, then its shorter neighbour will have 52 oscillations, its shorter neighbour will have 53 oscillations, and so forth. So letting $n$ represent the n-th pendulum (counting from 0), the period of any pendulum on the apparatus is $T=\frac{\Gamma}{N+n}$.

To express $\omega$ as a function of $x$, note that the x-position of the pendulum is $x=nd$ (so $n=\frac{x}{d}$ where $d$ is the common spacing between adjacent pendulums. We're almost done now. Now we can see that: \[\omega(x)=\frac{2\pi}{T}=\frac{2\pi}{\frac{\Gamma}{N+\frac{x}{d}}}\] \[\omega(x)=\frac{2\pi \left(N+\frac{x}{d}\right)}{\Gamma}=\frac{2\pi \left(Nd+x\right)}{\Gamma d}\]

Therefore, our complete wave equation is: \[y(x,t)=A\cos\left(\frac{2\pi \left(Nd+x\right)}{\Gamma d}t\right)\]

As a note of interest, we can rewrite the equation above as

\[y(x,t)=A\cos\left(\frac{2\pi t}{\Gamma d}x + \frac{2\pi N}{\Gamma}t\right)\] which corresponds to \[y(x,t)=A\cos\left(k(t)x+\omega_{0}t\right).\]

And we are done! That's the equation describing all of the waves you see in the video above.

Now that we are finished, we can take a nice break and prepare ourselves for the next post, where I'll discuss the properties of the equation we've just found.

Pendulum Waves - Mathematical Description

2011-06-21T16:05:00.000-07:00

Everyone likes bling, so let's start this post off with some eye-candy (skip to 20s if you've got very little patience):

That was pretty damn cool. Even if you're not admitting it, I know you're thinking it.

Lately, that video has been posted and reposted all over the internet. Now, don't get me wrong, I love spreading the joy of physics to no end. For those unsatisfied with simply seeing the video however, this post will be dedicated to presenting the nitty-gritty mathematical details of this marvelous phenomenon. If you would like to skip the math and just get some specifications to making your own pendulum wave machine, proceed here.

This is how the apparatus works in a nutshell:

The period of one complete cycle of the dance is 60 seconds. The length of the longest pendulum has been adjusted so that it executes 51 oscillations in this 60 second period. The length of each successive shorter pendulum is carefully adjusted so that it executes one additional oscillation in this period. Thus, the 15th pendulum (shortest) undergoes 65 (51 oscillations + 14 pendulums from the first) oscillations. When all 15 pendulums are started together, they quickly fall out of sync—their relative phases continuously change because of their different periods of oscillation. However, after 60 seconds they will all have executed an integral number of oscillations and be back in sync again at that instant, ready to repeat the dance. [1]

Let's begin. In a typical undergraduate physics course, you have most likely come across the (somewhat useless) travelling wave equation:

\[y(x,t)=A\cos\left(kx+\omega t+\phi\right)\]
where $A$ is the amplitude, $k=\frac{2\pi}{\lambda}$ is the wave number, $\omega=\frac{2\pi}{T}$ is the angular frequency, and $\phi$ is the phase shift. By convention, $\lambda$ and $T$ are used to denote the wavelength and period of the wave respectively. Lets also call the number of oscillations the longest pendulum goes thru $N$ (51 in this case) and the total time for the entire "dance" $\Gamma$ (60s in this case).

From the video, we can see that at $t=0$ and for any $x$ (we pick $x=0$), we have the maximum amplitude, $A$:

\[y\left(0,0\right)=A\cos\left(k\cdot0+\omega\cdot0+\phi\right)\]\[A=A\cos\left(\phi\right)\implies\phi=0.\]
Another thing we can see is that because the waves change shape in time, the wavelength must be a function of time and so the wave number (since it depends on $\lambda$) must also be a function of time. So instead of a fixed $k$, we have $k(t)$. Another thing to note is that since each individual pendulum is adjusted to give one more oscillation than their longer neighbour, the period and therefore the angular frequency must be a function of location, so we have $\omega(x)$.

Putting it all together, we have the equation:

\[y(x,t)=A\cos\left(k(t)x+\omega(x)t\right).\]
Now lets think for a moment. If $k(t)$ and $\omega(x)$ were independent of each other, the combination of some random $k$ and $\omega$ probably would not create the pretty patterns we see in the video. Aha! We have to conclude that $k(t)$ and $\omega(x)$ are some how working together - that these two functions are not independent of each other. More specifically, the cause to $k$ changing with time is due to constructing the machine so that the oscillations of each adjacent pendulum differs by 1 (i.e. due to tuning $w$ with x). With a bit of handwaving, we can choose to express one function in terms of the other and essentially throw away one of them. Our wave equation can now be modified to either one of:

\[y(x,t)=A\cos\left(k_{0}x+\omega(x)t\right)\]\[y(x,t)=A\cos\left(k(t)x+\omega_{0}t\right).\]
The constants $k_{0}$ and $\omega_{0}$ are used to describe the wave at $t=0$ and $x=0$ respectively.

Now the two expressions above are really the same, since they're both very general functions of $x$ and $t$. This means we can pick our choice of which equation to use.

Since I don't like overly long, dry, and boring posts, I'll end this post right here and continue the derivation in my next post. If you feel like doing the derivation yourself, go for it! It's a great way to learn.

Proof - Equal temperatures for opposing points on a circle

2011-06-17T14:01:00.000-07:00

If you would like a bit of intuition before we delve into the proof, see my last post.

Ready to go? Great.

Let the function $T(x)$ represent the temperature at some position $x$. Around a circle, $T(x)$ is periodic about $2\pi$ radians when $x$ lies on the circle's circumference. Thus, $T(x)=T(x+2\pi)$. Let us define a new function $D(x)=T(x)-T(x+\pi)$. Note that $D(x)$ is continuous as it is a difference of continuous functions $T(x)$ and $T(x+\pi)$.

Let:

$D(0)=L$ and $D(\pi)=-D(0)=-L$.

If $L=-L=0,$ $T(x)-T(x+\pi)=0$ and we are done.

If $L\neq0,$ then one of $L$ or $-L$ must be above zero and the other below zero.

Since $D(x)$ is a continuous function, we can apply the Intermediate Value Theorem to it. By the Intermediate Value Theorem, the function $D(x)=0$ for some $x\in[0,\pi]$.
Therefore, $T(x)-T(x+\pi)=0$, and $T(x)=T(x+\pi)$ for some $x\in[0,\pi]$.

$\blacksquare$

Equal temperatures at two opposite points across the earth

2011-06-17T14:00:00.000-07:00

This is a neat question I got in my first year calculus course:

Imagine a circle anywhere in the universe. (For example, draw a circle on a sheet of paper, or imagine the equator is a circle.) Prove that there are two points directly opposite each other on the circle with the same temperature.

Yes. It is true. And not just with temperature either. The above fact is true if you replace "temperature" with "humidity", "air pressure", or any other continuous phenomenon. Coincidentally, this is also why nobody is ever as cool as they think they are, since there could always be someone right on the other side of the world who is just as cool (ok, that was completely false and un-funny, but you can't blame a guy for trying).

If you're a big boy and you want to skip to the proof, see my next post. If not, let's settle down and get some intuition as to why this surprising fact is true.

First of all, lets stop thinking about temperature as an actual physical thing and start thinking about it like a function, perhaps some function that looks like this:

For our question, you may imagine the y-axis as temperature, and the x-axis as some indicator of where we are on the circle (e.g. an angle). Additionally, there are two properties that are unique to the function we are describing in this problem:

It is continuous. We don't expect temperature to "jump" from one temperature to another without hitting all the temperatures in between (at macroscopic levels at least).
It is periodic (think sin, cos, etc.). If we go from 0 radians to $2\pi$ radians, we'll have gone full circle and ended back at where we started. So we know that the temperature at 0 radians and $2\pi$ radians are the same.

These properties should drastically change what our function looks like. Instead of the mess of a function above, our temperature function should look something like the graphs below:

Yes. That last graph is periodic (crazy isn't it?). If you look closely, all graphs have a period of $2\pi$ (i.e. they are all zero at 0, $2\pi$, $4\pi$). Unfortunately, if you were to plot temperatures on a circle around the Earth, it'd probably resemble the third graph more than the first or second graph. Don't worry though, the shape of the graph doesn't complicate things as long as its periodic.

Let's get back to the original question now. We need to find two equal temperatures at two locations directly opposite to each other on a circle. This means that the two temperatures are separated by an angle of $\pi$ (or $\pi$ units on the x-axis above). This means we can verify that there exists opposing points with the same temperature by simply drawing a horizontal line of length $\pi$ and moving it around until the ends hit two points on our graph (do you see why?). What the question says is that if you draw a horizontal line of length $\pi$ on your temperature graph, you can always find endpoints for the line which lie right on the temperature function. For $\sin{x}$, this horizontal line has endpoints $(0,0)$ and $(\pi,0)$ (or $(\pi,0)$ and $(2\pi,0)$ if you prefer). The same goes for the triangle wave graph. For the third graph, the line is drawn below:

I'll leave you with a little puzzle. Although we only drew two lines above, we could have drawn two more lines corresponding to the two we just drew. Where are the other two lines? How many unique solutions are there?

Now that we've gained some intuition to this problem, we are ready to proceed with the proof (in the next post).

Update: This post has gotten quite a bit of attention from reddit! Thanks to all who took the time to read and spread this post!

Proof - Reducing prime checking bounds to $\sqrt{n}$

2011-06-16T18:01:00.000-07:00

This is a simple proof accompanying my last post on generating primes.

Let $n$ be a non-prime (i.e. composite), then it must have factors $a$ and $b$ less than $n$.

In other words: $n=ab$, with $n>a>1$ and $n>b>1$.

Suppose $a>\sqrt{n}$ and $b>\sqrt{n}$. This would mean $ab>n$. This cannot be as we just stated that $n=ab$.

Thus, the conclusion we draw is that either $a$ or $b$ is less than or equal to $\sqrt{n}$.

Let us say that it is $a\leq \sqrt{n}$.

Since $a>1$ , there must exist a prime $p$ that divides $a$. Furthermore, $p\leq a$ since it divides $a$.

We saw earlier that $a$ divides $n$. Since $p$ divides $a$, our prime $p$ must divide $n$. This gives us the result we are trying to prove: $p\leq a$ and $a\leq \sqrt{n}$. Therefore: $p\leq a\leq\sqrt{n}$.

Conclusion: If $n$ is not prime, it must have a prime factor (or regular factor) below $\sqrt{n}$. Otherwise, $n$ must be prime.

$\blacksquare$

Prime Number Generation

2011-06-16T18:00:00.000-07:00

If I asked you right now: what is the 10001st prime number? It would be very hard to come up with an answer on the spot. (this is question #7 on Project Euler). However, if one did want to find the answer, one method to use would be simple “trial division”.

The idea behind trial division is simple: since a prime must not have any factors other than itself and 1, just divide all the numbers from 2 to N-1 from the number (call it N) to be tested. If the division carries out and has no remainders, then the divided number must be a factor of the number we are checking and so the number we are checking is not prime.

Simple right? However, think of how many operations that would take to test a single number: one would need N-2 operations to loop from 2 to N-1, N-2 operations to carry out the division, N-2 operations to check if the division was carried out, all of which contribute to a massive computation time.

Luckily, there are methods to optimize our trial division prime checker. For instance, a commonly known fact about primes is that one only needs to check up to the integer before $\sqrt{n}$ instead of N-1 (a simple proof is offered in the next post). Furthermore, if we check right off the bat if the number is divisible by 2 or 3, the we will not need to check every second and third number from 4 to $\sqrt{n}$. This is really wheel factorization with two spokes. Such a type of trial division also leads one to the realization that all primes greater than 3 can be expressed in the form $6k +/- 1$, an interesting fact proven by the great mathmatician Leonhard Euler.

We are now set to create our prime checking algorithm!

The tricks we will employ are:

1. Checking only up to $\sqrt{n}$.

2. Checking first if the number is divisible by 2 or 3

3. Starting from 5 and checking every number of the form $6k +/- 1$.

Excellent. Now we are ready to write our algorithm. I will be writing in pseudocode.

Pseudocode:
function prime?[n]

if n mod 2 or n mod 3 == 0

return false // if the number is divisible by 2 or 3, it is not prime (only works for numbers above 3)

else

limit = sqrt(n) // bounds our testing limit to under $\sqrt{n}$

for (i = 5, i <= limit, i+= 6) // creates a FOR loop that starts at 5, stops when exceeding the limit, and increments the counter variable (i) by 6 each iteration

if n mod i or n mod (i+2) = 0

return false // if the function is divisible by numbers of the form $6k+/-1$, the number is not prime.

end if

end for

end if

return true // the number has passed all the tests we have given it; it is a prime

end function prime?[n]

And there it is! Just run this function with a counter until it reaches 10001 if you want to find the 10001st prime! Of course, there is a faster way to create a list of primes up to 10001st, namely using the sieve of Eratosthenes. This very effective and elegant algorithm may be covered in future blog entries. Keep readin’ til then.

********

References:

1. Project Euler (the pseudocode for the algorithm was heavily borrowed from PE).

2. The Prime Number Glossary (for interesting and useful facts about primes).

A bit of an introduction

2011-06-15T22:42:00.000-07:00

Hello.

My name is Paul Liu. It's nice to meet you. I was going to have a lovely conversation with you. However, since my current readership is zero, I'll edit more info into this page when people start giving a damn. For now, lets just get started. It's going to be a long long journey. I hope you'll find the time to share it with me.