November 2013 – Math Circle at UC Davis

Prime Progress

November 29, 2013November 29, 20133 Comments

Some of you may have heard of the recent discovery by Tom Zhang that proves the existence of a bound on the spacing of prime numbers. I highly recommend a short article in Wired that explains the unfolding story quite well. Mathematically, this relates to the Twin Prime Conjecture: There are infinitely many pairs of prime numbers whose difference is 2, like 29 and 31 or 18,409,199 and 18,409,201. So simple to state, yet so hard to prove! This ongoing research says that we now know that there are infinitely many primes with a difference less than 600 (down from 70,000,000 in the groundbreaking result of Zhang). Part of the drama of this research is that a young mathematician named James Maynard discovered the bound of 600 entirely independently of Zhang’s work at almost exactly the same time! Centuries of stalemate followed by simultaneous results! This brings to mind a famous quote of Farkas Bolyai about mathematical discovery from a letter to his son János,

“When the time is ripe for certain things, these things appear in different places in the manner of violets coming to light in early spring.”

János went on to become one of the founders of non-Euclidean geometry, which in turn led to the development of the theory of general relativity, a completely new way of thinking about space, time, and gravity. Also, isn’t it odd to think that emails with your parents might become part of the historical record and be quoted two hundred years from now?

After the initial publication by Zhang, a vast online collaboration known as Polymath8 got together to improve his result. Here we see two extremes in the way mathematical research is done. On the one hand, a lone individual quietly works in isolation for many years to develop a private insight with little connection to other people in his field. Often, this is the picture presented in the media of how mathematicians work. However, this is exceedingly rare! Mathematicians talk to one another and benefit from collaboration just like everybody else. This is exemplified by the Polymath8 group that brings together the expertise of a broad range of people from around the world to contribute to different pieces of the problem. Crowdsourcing! The more standard approach to good research can be seen in the success of Maynard who decided to be thorough by looking back at some neglected work by others and found a way to incrementally improve upon it in order to achieve a radical new discovery, a classic combination of “luck and pluck.”

All of these people are quite intelligent and creative, but mathematical discovery is not a magical “genius” activity. It’s hard yet rewarding work that you can do, too!

Exercise: Prove that there infinitely many prime numbers. [Suppose there is a biggest prime. Can you derive a contradiction?]

Hard Exercise: Prove that $\sum_{n>0} \left(\frac{1}{n}\right)= \infty$ . [Hint: Start by thinking of $\sum_{n=2^{k-1}}^{2^k} \left(\frac{1}{n}\right)$ for $k=1,2,3,4$ and see if you can get a lower bound with an easy formula.]

Hard Challenge: Prove that $\sum_{\text{primes }p} \left(\frac{1}{p}\right)= \infty$ . [This is pretty tough. Let me know if you want to see a relatively approachable proof.]

Easier than it looks: Let S be all positive integers that don’t have the digit 7 anywhere (written in the usual base 10). Show that $\sum_{n \in S} \left(\frac{1}{n}\right)< 100$ . [This time, you want to get an upper bound for which you can find a formula instead of a lower bound. ]

Non-Euclidean Riddle: A woman on a hike steps out of her tent, walks one mile south, then one mile east, and finally one mile north back to her tent. She finds a bear getting into her peanut butter! What color is the bear?

Math and Bicycles

November 26, 2013Leave a comment

We’re still hoping one of our brilliant and creative members will have a stroke of inspiration and contribute a logo capturing the idea of a Math Circle in Davis. Representing the circle with a bicycle wheel and the math with something, well, math-y (perhaps from one of our topics? randomness, fractals, …) seems like a good starting point for some brainstorming. Leave a comment or send me an email with your ideas.

Speaking of math and bicycles, I’m reminded of this design:

Does it look like a bicycle? If it does, maybe you should take a look at a bicycle and make sure we’re on the same page. It turns out that the physics of how bicycles stay upright is quite complicated. You can push your bike (if you try this and break something, it’s not my fault :-p) and it will roll quite a ways without anybody riding it. My first thought was the way the front wheel can move to change direction instead of just flopping over, so-called steering alignment. The weird pseudo-bike pictured above rolls just fine without this. Intuitively, you might think that the spinning of the wheels helps stabilize the bike. Gyroscopes! That must be the answer, like this snazzy two-wheeled ride from 1914:

Well, this bike has tiny wheels paired with oppositely spinning wheels to make that effect as small as possible. Challenge: Provide a physically intuitive explanation of what effect is stabilizing the pseudo-bicycle seen here: http://bcove.me/0fbjlh6l

A while back, I was chatting with Mont Hubbard, an engineering professor here at Davis who specializes in sports biomechanics, and I asked him about this design. His response to our challenge question was, (paraphrasing) “People care far too much about physical intuition! The researchers set up a dynamical system, linearized, looked at eigenvectors, and voila! The math speaks for itself.”

Turing Machines and More

November 24, 2013November 24, 2013Leave a comment

Today, Ben Schiffman gave an introduction to the theoretical machine that is the basis of the actual machine you are using to read this right now. Turing Machine Talk. He showed you a proof of one of the most profound mathematical facts known to humans. Essentially, there are true mathematical statements that cannot be derived, not even by super-smart aliens. There are numbers that can never be known, even approximately. Mathematics seems like something we do with our minds from time to time, so how can there be parts of math that are inaccessible to our minds? Whoa! This rabbit hole goes all the way down.

After inventing his theoretical machines, Alan Turing soon got distracted with the task of breaking Nazi codes in World War II. He then went on to design one of the first computers in 1945. He was easily one of the most brilliant and influential people of the century and suffered a very tragic end by poison apple. Anyway, you can read about these things and more in the wikipedia article or in the acclaimed biography by Andrew Hodges.

I rather like the introduction to Turing machines in his own words, which makes it very clear that he began by thinking of what a person actually does when they sit down and do boring math. Here’s a picture of old-fashioned computers:

That’s right. They’re made of people! Turing tried to imagine a stripped-down, bare-bones version of what somebody following rules to do long division or calculate the square root of 2 is actually doing. He then used this idealization of what humans do in this specialized, rule-following context as the definition of computation and then proceeded to probe its limits. Here’s a slightly abridged version of his own introduction:

“We may compare a man in the process of computing a real number to a machine which is only capable of a finite number of conditions… The machine is supplied with a ‘tape’, (the analogue of paper) running through it, and divided into sections (called ‘squares’) each capable of bearing a ‘symbol’. At any moment there is just one square… which is ‘in the machine’… by altering its configuration the machine can effectively remember some of the symbols which it has ‘seen’ (scanned) previously. The possible behaviour of the machine at any moment is determined by the configuration… In some of the configurations in which the scanned square is blank(i.e. bears no symbol) the machine writes down a new symbol on the scanned square; in other configurations it erases the scanned symbol. The machine may also change the square which is being scanned, but only by shifting it one place to right or left. In addition to any of these operations the configuration may be changed. Some of the symbols written down will form the sequence of figures which is the decimal of the real number which is being computed. The others are just rough notes to ‘assist the memory’… It is my contention that these operations include all those which are used in the computation of a number. The defence of this contention will be easier when the theory of the machines is familiar to the reader.” -Alan Turing, “On Computable Numbers, with an Application to the Entscheidungsproblem”, 1936(7).

The idea of a Universal Turing Machine is a little hard to wrap your head around, but just think of your computer. If you give it a program to run, it can run it! I’m writing on a Mac at the moment, and if I wanted to run a program built for a Windows PC, then am I stuck? Nope! I can first run a program that simulates–or emulates–the actions of a Windows PC and then run the first program using that virtual machine. Given sufficient memory (tape space in the Turing machine model), any computer can emulate any other. You can even play old 8-bit video games!

A question naturally arises: Can a Universal Turing Machine emulate me? That is, can I write a program such that when it runs, the computer can do anything I can do? Notice that I’m not phrasing this as asking if machines can think or have consciousness or anything like that. Of course, I might wonder how a machine that can reproduce anything I can do could possibly not have an internal state as equally sophisticated as whatever is going on inside of me. This gives us the infamous Turing Test. If you have a chat/texting conversation with a computer program and are convinced that you are communicating with a human, then the computer program has passed the Turing Test by emulating a person.

By the by, loooong before Turing, another crazy English guy, Charles Babbage, figured out how to build a purely mechanical, steam-powered computer that he called the Analytical Engine. Alas, he never got around to actually building the thing by the time he died in 1871. A smaller, weaker, crank-operated, glorified calculator weighing in at 10,000 pounds called the Difference Engine has been constructed.

Babbage worked with Ada Lovelace, the only legitimate child of famous poet and rogue Lord Byron, who became the world’s first computer programmer in 1842 when she worked out in complete detail a way to implement an algorithm to compute the sequence of Bernoulli numbers on the analytical engine.

Fractals and Even Wilder Beasts

November 24, 2013November 26, 2013Leave a comment

Today at Math Circle, Owen Lewis gave a quick introduction to fractals by constructing the Koch snowflake and calculating its length, area, and dimension. The odd part is that the length is not a real number $(\infty)$ and the dimension is a transcendental number $(\log_3 4)$ . Weird! This is actually a common characteristic of fractals. To make sure you understood the material today, try making your own fractals out of different shapes and/or divide the sides into different proportions. How does this affect the dimension?

Example 1: Start with a square and make square bumps out of the middle third of sides at each step.

Example 2: Start with the equilateral triangle and sprout little triangles out of one half of each side instead of the middle third.

Example 3: Try a 3D version by starting with a tetrahedron or a cube and compute the surface area and volume instead of the length and area.

Example 4: Make up your own! Can you make a fractal that actually has a finite length?

Owen also mentioned the Mandelbrot sets and Julia sets. These are more complicated than the snowflake that we did in detail today. However, the basic idea can be grasped as long as you know a little bit of how complex numbers work and are willing to dig in. Hopefully, we’ll have a math circle or two related to these topics in the near future.

Here’s a Julia set crop circle next to Stonehenge. Because.

Question: Here’s a famous fractal that has a lot going on despite its simple appearance. Start with a segment of length 1. Now, remove the middle third. Don’t add anything! Next, remove the middle thirds of the remaining segments. Repeat ad infinitum. What do we have left? Call it C and see if you can describe it. Does C have a length? If so, what is that length? Does this object C contain an interval? What is the dimension (as defined today) of C? [Note this is called Hausdorff dimension in the business.] Advanced: Does this object contain as many points as the whole interval? Can you make a one-to-one function that takes every real number in an interval to C? Repeat all of this but remove the middle fourth instead.

Challenge: Prove that any number $x \in [0,2]$ can be expressed as the sum $c_1 + c_2$ where $c_1,c_2 \in C$ . We can write this as $C + C = [0,2]$ . That is, even though we took away so much of $[0,1]$ , there are still enough numbers left that their sum can still make any number in $[0,2]$ .

Weirdness: It’s strange enough that we can have shapes with infinite length that enclose a finite area, but I will try to describe to you an object that doesn’t have a length at all. Note: Leave your visualizations at the door for this one. It’s literally unimaginable. Let’s start with an interval in the real numbers, say $[0,1]$ . Now I’m going to pretend that I can’t tell the difference between two numbers if their difference is rational. That is, if $x-y = \frac{a}{b}$ , then I will suppose that $x \equiv y$ . This is called an equivalence relation. This isn’t as odd as it at first seems. Think about a clock. Everyday, you make calculations like $45+30=15$ because $75-15=60$ and you start over when you hit 60 minutes, so $75 \equiv 15$ . Ok, so instead of considering two numbers to be the same if their difference is a multiple of 60 or 12 or whatever, we call them the same if their difference is any rational number. For example, all rational numbers might as well be one number, and $\frac{\sqrt{2}}{2}$ and $\frac{\pi}{4}$ are still distinct. So, for each batch of numbers that all look the same, I pick one of them to represent the rest and put it in a set V. Sounds reasonable, right? Now I can try to ask what the length of V is.

Claim: It is not possible to assign a length to the set V.

Proof: [warning: hard!] It’s not infinite (it’s contained in $[0,1]$ afterall), it’s not 0, and it’s not any other number either. How could we demonstrate this? Well, suppose it has a length. Then that length wouldn’t change if you slid the set left or right, i.e. length is invariant with respect to translation. This will lead to a contradiction. Let’s think about V for a second. Any two numbers in there have to differ by an irrational number. So, if we take two distinct rational numbers r and s, then $V+r$ and $V+s$ can’t have any overlap. By $V+r$ , I mean the set consisting of numbers $v+r$ where v is in V. Since length doesn’t change when you slide left or right, the length of $V+r$ and $V+s$ have to be the same as V. We’ll write this as $L(V) = L(V+r) = L(V+s)$ . Now, let’s take all of the rational numbers in $[-1,1]$ and label them $q_n$ . If we combine together all of the numbers $\cup_{n=1}^{\infty} (V+q_n) = U$ , then $[0,1] \subset U \subset [-1,2]$ . The idea here is that any number in $[0,1]$ that we didn’t include in V differed from an element in V by a rational number, which must be one of the $q_n$ . And, we clearly can’t get any numbers smaller than -1 or bigger than 2. Well, this implies that $1 = L([0,1]) \leq L(U) \leq L[-1,2] = 3$ . But what is L(U)? Well, it must be the sum of the lengths $L(V + q_n) = L(V)$ since none of them overlap, and these all have length L(V). This gives us 1 $\leq \sum_{n=1}^{\infty} L(V) \leq$ 3. Do you see why this is nonsensical? We can’t have $L(V) = 0$ , since $1 \leq \sum_{n=1}^{\infty} L(V) = 0$ is ridiculous, but if you add some number, no matter how small, to itself infinitely many times then you must get infinity! So, either $3 = \infty$ or V can’t have a length. QED

Such sets are called nonmeasurable. Mathematicians call unintuitive constructions like this “pathological” because they’re just so darn weird. If you actually managed to read the proof above, or you just want to see a really neat “application” of nonmeasurable sets, check out the Banach-Tarski Paradox:

We’ll attach some of Owen’s notes on fractals at a later time. For now, enjoy this quick video of taking successive 3-dimensional slices of a 4-dimensional Julia set of a function on the quaternions.

Randomness in Practice: Where’s Waldo?

November 20, 2013November 20, 2013Leave a comment

This morning, I came across an article about the classic Where’s Waldo? series of books. For those of you not familiar with these books, they consist of large images filled tiny characters and visual jokes. The goal is to find the titular character in each scene. Here’s an example I found online:

One might expect that this character is placed uniformly at random (equally likely to be in any place of the same size) to make him harder to find, but this article points out that this is not the case by a long shot. Why? Well, as we discussed at Math Circle, humans have a very different intuition about what “random” means than the mathematical definition. For example, if you pick a random spot to place Waldo and then realize it’s right next to a corner or near the center, you might think it likely that a reader will look there first, spoiling the fun. This tendency leads to a higher concentration of Waldos in a pair of bands across the page. Even though Waldo is still randomly placed, the fact that this randomness is not uniform means that you can actually develop a strategy for finding Waldo a little more quickly. This relates to the idea of entropy from information and coding theory (definitely to be confused with the entropy of thermodynamics).

To get a quick idea of how entropy captures the idea of uncertainty (lack of information), consider the game of 20 questions. In this game, somebody thinks of a person and the other player(s) are allowed twenty yes/no questions in order to determine his/her identity. Typical questions might be “Is the person female?” Yes. “Is the person alive?” Yes. “Is the person Miley Cyrus?” Yes. etc. Let’s modify the game a bit. Suppose that it is known that the person is a resident of Sacramento, with a population of 466,488 according to the 2010 census. Your opponent is very competitive and has decided that the best way to win is to pick a completely random person from a list of residents of Sacramento. How in the world could you possibly hope to guess a person off of such a list in only 20 questions?? Well, I guarantee that it can be done in only 19 questions because $2^{19}$ = 524,288 > 466,488. Here’s the strategy:

Number the citizens of sacramento from 1 to 466,488.
Convert the numbers to binary. [Note: when I googled “binary” the number of results was given in binary!]
Ask the following questions from n=1 to n=19: “Is the nth digit of the person’s binary code a 1?”
Write down a 1 if they say yes, and a 0 if they say no.
Look for the person on the list with the resulting number.

Tada! As you can see, given a pool of n people (or objects of any kind) you can always identify one of them in at most $\lceil \log_2 n \rceil$ questions. In this example, we had no information other than the number of people, so we had to assume that each one was equally likely. However, if the probability is not uniformly distributed, then we can develop a different coding scheme in order to use fewer questions. The theoretical best (the fewest number of questions required in the worst case scenario) that we can ever hope to do is called the entropy: $H(X) = -\sum_{i=1}^n p(x_i)\log_2 p(x_i)$ , where $p(x_i)$ is the probability that person $x_i$ is the one you seek, X.

Quick exercise: Show that H(X) reduces to $\log_2 n$ in the uniform case $p(x_i) = \frac{1}{n}$ .

Challenge: Show that $H(X) \leq \log_2 n$ . This means that the uniformly random distribution of probabilities has the least information. Hint: Is $x\log x$ convex or concave?

Also, I hope those of you who took the AMC 8 last night enjoyed the contest. Let me know if you want to do some training for the AMC 10/12 coming up in February.

Math Circle Material from November 9

November 17, 2013Leave a comment

I hope those of you who made it had fun with problems inspired by counterfeiting, poisoning, and gambling. Technically, topics today came from the mathematical areas of combinatorics, information theory, and probability. The sheets that they handed out are attached below.

MathCircle Tim MathCircle Laura

And now, a pair of bonus challenge problems:

The Noodler:

First, a problem that I think connects with both themes from today (start by thinking of small cases, use recursion, and apply probability with caution) starts with a bowl of your favorite noodles. Maybe it’s spaghetti, maybe it’s ramen… the result is sufficiently general so as to allow noodles from anywhere in the world. One day, you have a big bowl of noodles for a snack and realize that you’d like to first play with your food. So, you reach in at random, grab two noodle ends, and tie them together. They’re all tangled up, so you can’t tell if it’s the same noodle or not. You continue doing this until you’re all out of noodle ends. Finally, you can eat your noodle-loops. On average, if you started with n noodles, how many loops are there? That is, what is the expected value of the number of loops? You might like to start by figuring out the average number of loops consisting of k noodles for each k.

Impossible Odds:

Here’s a related (<–spoiler) problem that’s a favorite of mine concerning students. Suppose your school has 1000 students who each have exactly one locker that is conveniently labeled with the student’s name. One day, all the adults go completely insane and force the students to play a game. They take the 1000 names of the students, mix them up, and write the names inside the lockers. That is, we have a randomly chosen permutation of the names. Now, the game is that each student is allowed to open 500 lockers in search of their own name. If they don’t all find their names, they will all get detention even worse than playing this game. After each student goes through, the lockers are closed behind them and nothing is changed or communicated. Luckily, the math club has put their heads together and announces to the other students that they can win with odds better than 30%. How?? It seems like each student has a 50/50 chance, which would make the odds for all of them to succeed 1 in $2^{1000}$ or about a $9\times 10^{-300}\%$ chance.

Hint: the strategy is easy enough for anybody in the school to follow, even if they don’t understand why.

Note: this was discovered in the last 10 years, and the paper won a prize. Let me know if you want another hint.

Davis Math Circle of November 16

November 17, 2013Leave a comment

Hello Everybody!

I hope those of you who came today enjoyed the talks on the Art Gallery Theorem and Random Walks. Both of these talks just scratched the surface of very deep and beautiful mathematics with applications throughout science, economics, and programming.

Reminders:

Tuesday at 7pm, back in MSB 2112, we’ll have the AMC 8. Nate will be proctoring. Let us know if you’d be interested in a separate group that focuses on training for math competitions (like the ARML group from last year).

Next week will be our last meeting until January. Then we should have Math Circle for at least 10 weeks in a row! Remember, we meet Saturday 10am-noon in MSB 2112. Next week, Owen Lewis will give some insights on the mathematical nature of fractals (nifty objects with non-integer dimension), and Ben Schiffman will discuss Turing machines, the mathematical concept of a computer that’s basically the grandfather of the Information Age in which we live today.

Let us know if there is something you’ve heard about and would like to see turned into a Math Circle talk.

And now for a little more info related to today’s topics:

Graph Coloring:

Anybody who cares about the internet should care about graphs (vertices connected by edges). For a famous example of graph coloring, I recommend reading about the Four Color Theorem (inspired by ordinary maps).

Ramsey Theory:

Here’s a quick application of coloring edges instead of vertices: If you are in a group of six people (including yourself), why is it automatically true that either (1) at least three of you are mutual friends or (2) at least three of you don’t know each other? Is this still true in a group of 5 people? (No. Why not?) How many people do you need to guarantee a group of 4 mutual friends or strangers? This line of thinking quickly takes you to questions that nobody knows the answer to! We call that kind of question a research topic, and it’s the primary occupation of a mathematician to discover new methods that will lead to the answers and thereby expand human knowledge. We also teach from time to time. :-p

Atoms and Random Walk:

As for random walk, one example of its use historically was to theorize the existence of atoms! Before constructing sufficiently powerful microscopes with the help of quantum mechanics, it was impossible to directly observe atoms. Over 2000 years ago, the Epicurean philosopher Lucretius wrote a poem called “On the Nature of Things” that included the observation that dust motes dancing in the sunlight must be randomly bombarded by gazillions of tiny, invisible particles in order to move like that. Albert Einstein‘s most referenced paper (and hence his greatest contribution to science by some measures) has nothing to do with relativity. In fact, it mathematically explains this dancing-dust-mote phenomenon (Brownian motion) as arising from random walk. Even in 1905, the atomic theory was not yet completely established, and Einstein’s theoretical use of atoms (and random walk) helped convince the world of their existence.

Arcsine Law:

To fit in with last week’s Paradoxes in Probability, here’s a conundrum for the random walk studied today. We plotted out where we ended up after 25 random steps and figured out that the odds of being to the left or right of 0 were basically 50/50. But! While you’re doing the random walk, before you finish, how much of the time are you on one side or the other of 0? Do you spend half the time to the right and half the time to the left? Nope! It turns out that the answer is related to the function $\frac{2}{\pi}\arcsin{\sqrt{x}}$ … not at all obvious! If you’d like to see how this works, let me know. Warning: a detailed answer requires a little calculus, but it’s mostly just careful/clever counting.

See you next week!

Math Circle Blog!

November 17, 2013Leave a comment

Welcome to the Davis Math Circle Blog!

After numerous problems adapting the old Davis Math Circle website to our new set up, we’ve decided to convert to a blog that will contain current information on the Explore Math program as well as fun extras. This should make it simple for students and instructors to post comments and share ideas. A nice thing about WordPress is that it’s pretty easy to add math: $\int_{-\infty}^{\infty} e^{-x^2} \,dx = \sqrt{\pi}$

The site should be set up in the next few days. If you have any design ideas, please let me know. It’d be fun to have a cool, mathy logo that we made ourselves. Something that suggests Davis and math, maybe with a bicycle?

Speaking of math and bicycles, check out this old-fashioned, square-wheeled bicycle:

And a gif showing how it works: