Zorn's Potato

this is my math blog of math. if you like proofs then this blog is for you. yes that image is a mandelbrot set being sucked into a black hole

[zornspotato]

The Golden Fibonacci Metric System, Part 1 - Real Analysis

This is a LaTeX-enabled post. For best viewing, use a browser and view this on my blog, not a mobile device or your dash. Difficulty: \((*)(*)\) This post is marked as a Double Star. Prerequisites: It will be helpful to know some introductory real analysis, or at least be comfortable with sequences.

Alright everyone, it’s been a while. It’s actually been significantly more than a “while,” which is a metric unit that you probably hadn’t heard of because it’s a CGS unit, so nobody uses it.

Okay, that’s a total lie. There is no metric unit named a “while.” However, there is a metric unit for a “mile.” 

Okay, that’s also a total lie. However, a US Customary Mile is a rational multiple of an SI base unit, namely the meter. One mile is exactly (yes, exactly) \( 1609.344 \) meters. How is this possible when the meter is determined in terms of the natural speed limit (it’s exactly \( \frac{1}{299,792,458} \) lightseconds) and a mile predates the meter? Well the mile, now known as an International Mile, has since been redefined in terms of the meter. (Or rather, the inch has since been redefined to be exactly \( 2.54 \) centimeters, and everything follows from that.)

Note that I’m using the international mile here, or just a mile. Not to be confused with a “survey mile” which is slightly longer. That is, it’s a different unit also called a “mile” that’s less than half a centimeter longer than a mile. Don’t ask. It’s also not to be confused with a “nautical mile,” which is exactly \( 1852 \) meters.

However, we’re getting sidetracked. The point is that there’s an exact conversion from miles to kilometers. That is, the number of kilometers is exactly \( 1.609344 \) times the number of miles. And that has the nice benefit of being a terminating decimal, which is true because the denominator only contains prime factors of two and five. However, \( 1609344 \) factors into \( 2^7 \times 3^2 \times 11 \times 127 \) which definitely contains prime factors that aren’t two or five. (At least, last time I checked, three, eleven and one hundred twenty-seven were not equal to two or five, but I might be wrong there.) Thus, this magical property of having a terminating decimal disappears when we’re going to convert kilometers to miles.

So, we need to use a fraction. But \( \frac{1609344}{1000000} \) is really ugly (no offense). Because of this, people have come up with a lot of easy approximations that turn out to be fairly decent. If the number we want is \( 1.609344 \), then we can use \( \frac{3}{2} \), \( \frac{5}{3} \), and \( \frac{8}{5} \) all pretty well. A lesser-known one is \( \frac{21}{13} \). These come out to \( 1.500 \), \( 1.66\bar{6} \), \( 1.600 \), and \( 1.\overline{615384} \). Those last two are extremely good, corresponding to a slightly-more-than-nine-meter error per mile, and a slightly-more-than-six-meter error per mile, respectively.

An important thing to notice is that all of these fractions are ratios of consecutive Fibonacci numbers. Is this a coincidence? Well, sort of yes and sort of no. We’re going to spend the rest of this post exploring that, using nothing but elementary real analysis.

The first thing to check is what happens when we continue with the Fibonacci sequence ratios. Let’s consider the sequence of ratios of consecutive Fibonacci numbers. That’s \( 1/1 \), \( 2/1 \), \( 3/2 \), \( 5/3 \), \( 8/5 \), \( 13/8 \), \( 21/13 \), etc. If we were to write out the decimals, we’ll notice that this sequence looks like it converges but it’s unclear what it will converge to (unless you recognize the number. If you recognize the limit of this sequence then SHHH don’t blurt it out!). 

If we let \( A \) and \( B \) be two consecutive Fibonacci numbers, then the next one is \( A+B \), and the one after that is \( A+2B \). The ratio \( \frac{A+B}{B} \) is either less than \( \frac{B}{A} \) or it’s not. (DUH!) Let’s look at the first case, which has \( \frac{A+B}{B} < \frac{B}{A} \). This tells us that \( B^2 > A(A+B) \), or that \( B^2 - A^2 > AB \). If this is true, I claim that \( \frac{A+2B}{A+B} > \frac{A+B}{B} \). That last inequality is true if \( B(A+2B) > (A+B)^2 \), which is true as long as \( AB + 2B^2 > A^2 + 2AB + B^2 \), which is true as long as \( B^2 - A^2 > AB \), which it is! (by hypothesis). These inequalities also work in the other direction, with \( \ge \) instead of \( < \) and \( \le \) instead of \( > \). This tells us that the ratios take turns being greater or less than their predecessor, or in other words, a Fibonacci Ratio is either greater than both its two neighbors or less than both its two neighbors, which we will call “Mountains” and “Valleys,” respectively.

Note that we don't have to worry about equality because no two consecutive Fibonacci ratios could be equal, because that would give us a geometric sequence of length three of Fibonacci numbers (\( A \), \( AR \), and \( AR^2 \)). This would tell us that \( AR^2 = AR + A \). Factoring out \( A \) gives us \( R^2 = R + 1 \), which doesn't have any rational number solution, so there would have to be a non-integer Fibonacci number (either \( A \) or \( AR \)). We know that doesn’t happen, so we’re good. (We can’t have \( R \) be rational, because if \( R = \frac{P}{Q} \) in lowest terms, then \( R^2 = \frac{P^2}{Q^2} \). Multiplying both sides by \( Q \) gives \( \frac{P^2}{Q} = P + Q \). The right-hand side of this is an integer but the left-hand side is not, so we must have borked something somewhere. In this case, we borked it when we said \( R = P/Q \) with \( P \) and \( Q \) integers.)

Another observation is that each mountain is less than the previous mountain. How do we know? Suppose that \( \frac{B}{A} \) is a mountain, which tells us that \( \frac{A+2B}{A+B} \) is the next one. We’d like \( \frac{A+2B}{A+B} < \frac{B}{A} \), which is true as long as \( A(A+2B) < B(A+B) \). Expanding both sides tells us that we win if \( A^2 + 2AB < AB + B^2 \), which is equivalent to (you guessed it!) \( B^2 - A^2 > AB \), which is true as long as \( \frac{B}{A} \) is a mountain (which it is!). As before, we could flip the inequality and get that the valleys are exactly the cases when \( B^2 - A^2 < AB \), and the resulting inequality also flips - that is, each valley is greater than the previous valley.

This gives us a decreasing subsequence of just the mountains and an increasing subsequence of just the valleys. Each mountain is greater than its valley neighbors and each valley is greater than all the valleys before it. This tells us that each mountain is greater than every valley before it. I can use the same argument to show that each valley is less than all the mountains before it. It then follows that all mountains are greater than all valleys. How do I know? Pick a mountain \( M \) and a valley \( V \). If \( V \) is before \( M \), then \( M > V \) because each mountain is greater than all the valleys before it. If \( M \) is before \( V \), then \( V < M \) because each valley is less than all the mountains before it. Either way, any mountain \( M \) is greater than any valley \( V \).

This tells us that the sequence of mountains is decreasing and bounded below by any of the valleys. Similarly, the sequence of valleys is bounded above by any mountain, and it’s increasing. This means that both the subsequence of mountains and the subsequence of valleys converge to some real number, because they’re both monotonic and bounded.

We actually know that the sequence of mountains is bounded below by the supremum of the sequence of valleys, and the sequence of valleys is bounded above by the infimum of the sequence of mountains. How do we know that? YEA THAT’S RIGHT IT’S MATH 295 HOMEWORK 2 PROBLEM 2B IT ALWAYS RETURNS. This is totally irrelevant but I figured I would bring it up. 

The subsequence of mountains converges, which means that if we were to crop off the first element, it would still converge, and to the same number. This allows us to take the difference of the two sequences, which will converge to zero. That is, the difference between two consecutive mountains converges to zero. But what is the difference of two consecutive mountains? It’s \( \frac{A+2B}{A+B} - \frac{B}{A} \). When we put that over a common denominator, we get \( \frac{A(A+2B) - B(A+B) }{A(A+B)} \). Expanding it gives us \( \frac{A^2 + 2AB - AB - B^2}{A^2 + AB} \). I’m going to divide both the numerator and the denominator by \( A^2 \), which gives us

\[ -\frac{\left(\frac{B}{A}\right)^2 - \frac{B}{A} - 1}{1 + \frac{B}{A}} \]

Noe that \( \frac{B}{A} \) converges to some positive real number, so the denominator here converges to some positive real number. This means the only way for this fraction to converge to zero is if the numerator converges to zero. This tells us that \( \left(\frac{B}{A}\right)^2 - \frac{B}{A} - 1 \) has to converge to zero. Because a polynomial function \( p \) is continuous, we know that if a sequence \( (x)_n \) converges to a real number \( x \), then \( p( (x)_n ) \) converges to \( p (x) \). Here, \( (x)_n \) is the sequence of consecutive \( \frac{B}{A} \)s, and it converges to some real number \( x \). If we let \( p(z) = z^2 - z - 1 \), then we get that \( p((x)_n) \to 0 \). We also know that \( p((x)_n) \to p(x) \), which tells us that \( p(x) = 0 \). Well the good news is we remember eighth grade algebra, so we can solve \( x^2 - x  - 1 = 0 \) using the quadratic formula. (Don’t try to factor it - we already know from above that this polynomial doesn’t factor over the rationals.) This gives us that

\[ x = \frac{1 \pm \sqrt{5}}{2} \]

Now, we’re definitely looking for \( \frac{1 + \sqrt{5}}{2} \) because the other root is negative. Let’s call this number something special, like \( \Phi \). What’s that you say? Did you say that \( \Phi \) is already used to denote the golden ratio? Well that’s because that’s literally this number.  The golden ratio is exactly \( \frac{1 + \sqrt{5}}{2} \). This is what I meant when I said, “If you recognize the limit, then don’t blurt it out.” Because many of y’all probably guessed what the limit was, but I wanted to show it without heuristics like “it looks like it goes to that.” Also, note that \( \bar{\Phi} \) is the name of the other root, because it’s the radical conjugate. 

Either way, we just showed that the sequence of mountains converges to \( \Phi \). But nothing we did was unique to mountains - we could have done all of the same things with valleys, and we would have gotten the same result. Thus, we can conclude that the sequence of Fibonacci ratios converges to \( \Phi \). Q.E.D. Potato \( \Box \)

Why do I care? Well, it depends on what that number is. \( \Phi \) is about \( 1.618 \), and the mile-kilometer conversion factor is about \( 1.609 \). That means that if we use \( \Phi \) as an estimation, we’d only be off by around nine meters for every mile. (A mile is about 1609 meters, but this would give us 1618 instead.) In practicality, \( \Phi \) is not really a useful estimate because it’s irrational, but we CAN estimate \( \Phi \) with Fibonacci ratios. By using a very good estimate of a very good estimate, we get an estimate that’s still pretty good.

So to answer the original question... is it a coincidence? I said “Yes and no.” It’s definitely a coincidence that the ratio of the distance between a mile and kilometer is about \( \Phi \). What is not a coincidence is that Fibonacci Ratios are good estimates for \( \Phi \), because the sequence literally converges to it. That is, you can get as good of an estimate as you want, and all you need to do is pick a ratio sufficiently far enough out. Note that when you get very very close to \( \Phi \), you get farther away from \( 1.609344 \), which means that the best Fibonacci estimates are \( \frac{8}{5} \) and \( \frac{21}{13} \). (\( \frac{13}{8} \) is a mountain and is thus it is too far because it is greater than \( \Phi \).)

There’s another extremely important take-away from this. Define a “recursive addition sequence” to be any sequence of real numbers where any element is equal to the sum of the previous two (except the first two elements). There’s several things I assumed in this proof that I didn’t use. First, I didn’t reference the initial conditions of the sequence. I could have started the sequence anywhere and the whole proof still works. Other named examples of a recursive addition sequence are the Lucas numbers, which start with one and three instead of one and one. The sequence of Lucas Ratios also converges to \( \Phi \). The second thing is I didn’t assume that the sequence had to be an integer sequence. Well, sort of. I used that idea to show that we couldn’t have consecutive ratios be equal. This is actually not true. They can be equal, but there’s exactly two cases where they are equal when the ratio sequence is the constant sequence \( \Phi \) or when it’s the constant sequence \( \bar{\Phi} \). Those are the only ratio sequences for which we actually have equality, and those aren’t formed from integer-only recursive addition sequences. 

An assumption I DID make during the proof is that all the ratios are positive. This allowed us to pick \( \Phi \) as the limit of the ratios and not \( \bar{\Phi} \). The actual limit depends on the initial conditions. If \( A \) and \( B \) are, say, \(1 \) and \( \bar{\Phi} \) then this sequence is just the geometric sequence \( \bar{\Phi}^n \), which has a constant ratio sequence of \( \bar{\Phi} \).

If \( A \) and \( B \) are the initial values and if \( C \) is a nonzero real number, then if we start with \( CA \) and \( CB \) instead, we’ll get the same ratio limit, either \( \Phi \) or \( \bar{\Phi} \). This means that instead of starting with \( A = 1 \) and \( B = \bar{\Phi} \) as I did before, we can actually start with any nonzero \( A \) and let \( B = \bar{\Phi} \cdot A \), and that will also give us a ratio limit of \( \bar{\Phi} \).

Now, here’s some food for thought: This is the only way to get a constant ratio of \( \mathrm{\bar{\Phi}} \). If we do not start with \( \mathrm{B = A \cdot \bar{\Phi}} \), then the sequence ratio will always converge to \( \mathrm{\Phi} \).

How do I know this? That’s a secret, which I will reveal next time, in The Golden Fibonacci Metric System, Part 2 - Linear Algebra. That’s right - it always comes back. This will be part four of the Linear Algebra Saga. Until next time, Zorn’s Potato Out. 

[zornspotato]

Today In The Math Lab

I have a different sideblog now, about general stories, ramblings, and musings of being an undergraduate math tutor. Check it out: https://todayinthemathlab.tumblr.com/

Mostly I just share stuff that’s on my mind after I finish my shifts. 

[mathprofessorquotes]

I won’t be giving extra help today. I know I normally give it for about 2 hours on Thursdays but it’s so nice out so I’m going to go home and ride my bike.

AP Calculus teacher (via mathprofessorquotes)

[zornspotato]

The AM/GM Story: Calculus-Free Optmization

This is a LaTeX-enabled post. For best viewing, use a browser and view this on my blog, not a mobile device or your dash. Difficulty: \(({*})\) This post is marked as a Single Star. Prerequisites: None.

Those of you who have taken Calc 1 know how to solve basic optimization problems. A function is maximized or minimized when its derivative is zero. There exists a story of love and life, a story of ingenuity, and a story explaining how you don’t actually need calculus to solve most Calc 1 optimization problems. This is that story.

So, for some reason, you have acquired several tortoises. Maybe you like the tortoises because they make you feel fast. Maybe you like them because reptiles are the best kind of pet. Maybe you just like durdle turtles. For whatever reason, you have tortoises, which you need to encase in a pen next to a river.

You think to yourself, why would I put them next to a river? Because otherwise the smart kid will be like “Use a Square!” and ruin the surprise. Either way, this is the pen you need to create. The problem is that you only have so much fence. You have, in fact, seventeen meters and you want to enclose the largest possible area for your tortoises. So you ask your friendly neighborhood mathematician if they can help you solve this problem and they tell you to take the derivative and set it equal to zero.

Silly mathematicians and their math. What, do they think an ordinary person like you knows calculus? Give me a break.

But wait! “What if I can solve this problem without calculus?” you ask them. They perk up and say, “You can use the AM/GM inequality!”

“The what now?”

They pull out a piece of paper and say, “Say \( a\) and \( b\) are just numbers on the number line,” and write \( (a-b)^2 \ge 0\). You say, “Well yea, a square number can’t be negative.” They then add, “The key here is that \( (a-b)^2 = 0\) exactly when \( a-b=0\). Otherwise, \( (a-b)^2 > 0\).” You nod in agreement. They expand \( (a-b)^2\) and get \( a^2 -2ab + b^2 \ge 0\), with equality still when \( a-b=0\).  You agree. Then, they add \( 2ab\) to both sides, and gets \( a^2 + b^2 \ge 2ab\), with equality only when \( a = b\).

“How’d you get when \( a=b\)?”

“That’s the same thing as \( a-b=0\). I skipped a step.”

“Oh, okay.”

So now you look at \( a^2 + b^2 \ge 2ab\) and you get an idea. You have seventeen meters of fence and you have one section parallel to the river equal to the width, and two stretches perpendicular to the river equal to the height. You write \( w + 2h = 17\). Suddenly, a flash of intuition occurs to you and you write  \( w + 2h = 17\) as \( \left(\sqrt{w}\right)^2 + \left(\sqrt{2h}\right)^2 = 17\). Now, you can use the AM/GM inequality! By AM/GM you know that \( \left(\sqrt{w}\right)^2 + \left(\sqrt{2h}\right)^2 \ge 2\sqrt{w}\sqrt{2h}\) with equality only if \( \sqrt{w} = \sqrt{2h}\), which is just \( 17 \ge 2\sqrt{2}\sqrt{wh}\), with equality only if \( \sqrt{w} = \sqrt{2h}\). The right-hand side is maximized when equality holds, so \( 2\sqrt{2}\sqrt{wh}\) is maximized when \( \sqrt{w}=\sqrt{2h}\). But this is just \( 2\sqrt{2}\sqrt{\mathrm{Area}}\), so the square root of the area is maximized when \( \sqrt{w} = \sqrt{2h}\), so this must maximize the area as well! So the area is maximized when \( \sqrt{w} = \sqrt{2h}\), which is just when \( w = 2h\)! Aha! So it must be twice as wide as it is deep!

The friendly neighborhood mathematician grins and says, “Exactly. I’m Taylor, by the way.”

One and a half years later, you end up married, and the neighborhood mathematician becomes your relative topologist when you intersect your lives. You decide to to go a Bruce Springsteen concert while on your honeymoon.

The first thing you notice is that Bruce has an American flag bandanna and sunglasses on. It’s nighttime, but he’s just that cool. He’s got a humongous Star-Spangled banner behind him because there’s nobody more American than Bruce. Like seriously, how does he do it?

The second thing you notice is that you don’t know the optimal place to stand to maximize the fraction of the view that Bruce occupies. If you’re right below him then you only see his feet and head pretty much. But if you go too far back, he’s far enough away that he takes up a small fraction of your view. You draw a diagram, labeling the distances \( B\) for Bruce’s height, \( A\) for American and also for the height above your eye level that he’s standing, and \( x\) for how xcited you are to be there with your new spouse, at a Bruce concert, and also for your distance on the ground from the slope.

You realize that the angle \( \theta_1\) to Bruce’s feet is \( \tan^{-1}\left(\frac{A}{x}\right)\) and the angle to his head is \( \tan^{-1}\left(\frac{A+B}{x}\right)\). You write down that  you want to maximize the difference of \[\tan^{-1}\left(\frac{A+B}{x}\right)-\tan^{-1}\left(\frac{A}{x}\right)\].

You don’t know calculus so this stumps you, and you ask your spouse. They say, “Inverse Tangent!” and get all excited, then they say “Don’t worry. Your friend AM/GM helps here too.” You think, and then realize that maximizing a function on \( [0, \pi/2)\) is the same as maximizing its tangent. So you take the tangent of your quantity, and get \[\tan\left(\tan^{-1}\left(\frac{A+B}{x}\right)-\tan^{-1}\left(\frac{A}{x}\right)\right)\] Good thing you remember the tangent of a difference formula, or that \[\tan(y-z) = \frac{\tan(y) - \tan(z)}{1+\tan(y)\tan(z)}\] Simplifying, you get \begin{align*} &\phantom{=}\tan\left(\tan^{-1}\left(\frac{A+B}{x}\right)-\tan^{-1}\left(\frac{A}{x}\right)\right) \cr &=\frac{\tan\left(\tan^{-1}\left(\frac{A+B}{x}\right)\right) - \tan\left(\tan^{-1}\left(\frac{A}{x}\right)\right)}{1+\tan\left(\tan^-1\left(\frac{A+B}{x}\right)\right)\tan\left(\tan^{-1}\left(\frac{A}{x}\right)\right)} \cr &= \frac{\frac{A+B}{x} - \frac{A}{x}}{1 + \frac{(A+B)(A)}{x^2}} \cr &= \frac{\frac{A+B}{x} - \frac{A}{x}}{1 + \frac{(A+B)(A)}{x^2}}\cdot\frac{x^2}{x^2} \cr &=\frac{Bx}{x^2+(A+B)A} \end{align*}

You know \( B > 0\) so this is the same as maximizing \( \frac{x}{x^2 + (A+B)A}\). Then you have a flash of ingenuity and write that this is the same as maximizing \( \frac{2\sqrt{A(A+B)}x}{x^2+(A+B)A}\), which means now you can use AM/GM! You know that \( 2\sqrt{A(A+B)} x \le A(A+B) + x^2\) with equality only when \( \sqrt{A(A+B)} = x\)! But this means that \( \frac{2\sqrt{A(A+B)}x}{x^2+(A+B)A} \le 1\) and equals \( 1\) only when \( x=\sqrt{A(A+B)}\), so it’s maximized when \( x=\sqrt{A(A+B)}\). You look at your spouse and say “aha!” and show them your work. They reply, “I knew you had it in you,” and you kiss.

Years later, it comes up again. “Taylor, I’ll deal with dinner tonight. Can you pick up the kids?”

“Sure thing, hun.”

Now that you get to make dinner, you need to head to the grocery store and decide what to buy. Clearly, you have to have potatoes, because what kind of blog post would this be without the obligatory potato reference? Anyway, it’s beautiful out, so you decide to bike there. The grocery store is located on the corner of a large blacktop where kids play:

You think it will be faster to to on the road at least some of the way, because you ride at eight meters per second on the road and two meters per second on the blacktop to avoid kids. The blacktop is a 100-meter square. So, if you ride \( x\) meters on the road, your time on the road is \( x/8\). Your time on the blacktop is \( \sqrt{(100-x)^2+100^2}/2\) by the Pythagorean theorem. So you’re trying to minimize \( x/8 + \sqrt{(100-x)^2+100^2}/2\), which at this point you already know to do using AM/GM. This one’s a tough one, but you think you can do it. The first thing you do is rewrite \( (100-x)\) as \( z\) and write \( \sqrt{(100-x)^2+100^2}\) as \( y\). So now, you’re minimizing \( x/8 + y/2\). Then, because \( z^2 + 100^2 = y^2\), you’d rather use \( z\) instead of \( x\). You write this as \( \frac{100 - z}{8} + \frac{y}{2}\), which is \( \frac{100}{8} - \frac{z}{8} +    \frac{y}{2}\). Minimizing this is the same as minimizing \( \frac{y}{2} - \frac{z}{8}\), which is the same as minimizing \( 4y - z\). You don’t know what to do with the \( -\) sign because you can’t use AM/GM if there’s a \( -\), so you decide to minimize the square and see what happens. Minimizing \( (4y-z)^2\) expands to \( 16y^2 - 8yz + z^2\). You could use AM/GM on the square terms, but you still have this awkward \( -8yz\) term, unless, you think, what if I did it on that? You write \( 8yz = 2\cdot 4y \cdot z\), and you get \( 8yz = 2 \cdot 4y \cdot z \le 16y^2 + z^2\). But of course you know that already because \( 16y^2 + z^2 - 8yz = (4y - z)^2 \ge 0\). But then, you think “I wonder...” as Ollivander did in the first Harry Potter book when Harry bought his wand, and you write \( 8yz = 2 \cdot y \cdot 4z\)! This means that \( 8yz \le y^2 + 16z^2\), so \( -8yz \ge -y^2 -16z^2\). So \( 16y^2 - 8yz + z^2 \ge 16y^2 + z^2 - y^2 - 16z^2\). But that is just \( 15(y^2 - z^2)\), and \( y^2 - z^2 = 100^2\) is a constant! So we have that \( (4y-z)^2 \ge 15 \cdot 100^2\) with equality if and only if \( y = 4z\). This gives us \( 16z^2 = z^2 + 100\), or that \( z = \frac{100}{\sqrt{15}}\), so \( x = 100\left(1-\frac{1}{\sqrt{15}}\right)\). You know that \( 1 - 1/\sqrt{15}\) is just a bit less than \( 1- 1/\sqrt{16} = \frac{3}{4}\), so you need to go about \( \frac{3}{4}\) of the way and then cut across the blacktop. You hop on your bike and

“Dear?” “Yes Taylor?” “What about dinner?” “Oh, well, I just figured out the fastest way to bike to the grocery store via the blacktop. I didn’t even use calculus. I used AM/GM.” “That’s nice honey but the fastest method would have been to just go without calculating for half an hour.” “Oh. Yea. I guess so. Anyway, Goodbye, be back in bit, see you later alligator, et cetera, love you.”

You hop on your bike, content with your AM/GM inequality and understanding spouse who happens to be facepalming at this very moment. So, at least somewhat understanding. That’s understanding enough if you’re going to be irresponsible, you think, as you ride off into the sunset (because it got dark while you were calculating). You end up making a lovely dinner of corned beef and potatoes, and live happily ever after. The end. \( \Box\)

In case anyone’s wondering, I did purposely avoid using gendered pronouns. The protagonist of this story is “you” and I can’t make any assumptions. Tell me what you think of my story!

[zornspotato]

Redesign

I redid the CSS of Zorn’s Potato. I’d appreciate it if you guys could tell me what you think. Be super honest - I won’t be offended. This is an experiment and if you think something looks shitty that is something I’d like to know so I can change it. Thanks in advance for feedback, unless I get none. In which case, love you too, you jerks ;-)

[zornspotato]

In case anyone’s wondering, this is the full resolution image of the mandlebrot set being sucked into a black hole For those who want to know, it’s actually the function Log(z)^2+C rather than z^2+C. I rotated it so it points toward +i rather than -1. 

[mathprofessorquotes]

The world does not suffer from an excess understanding of multivariable calculus.

Analysis Professor (via mathprofessorquotes)

[zornspotato]

A Tale of Lagrange and Cauchy-Schwarz, Part 3

This is a LaTeX-enabled post. For best viewing, use a browser and view this on my blog, not a mobile device or your dash. Difficulty: \(({*}{*}{*})\) This post is marked as a Triple Star. Prerequisites: You won’t actually need Part 1 and Part 2 to read this, but they’ll help with the motivation and the continuity. You should also know what the Cauchy-Schwarz inequality is or you’ll have no idea what I’m doing.

Okay guys. A Tale of Lagrange and Cauchy-Schwarz Part 3 is here. Finally, after this long wait, we come to the thrilling conclusion of the epic tale: we’re going to prove the Cauchy-Schwarz inequality... again. This is where the mashed potatoes come in, First, you have to just kidding. This is not about potatoes. I’m done with the potato analogy for now.

We’re going to need the AM/GM inequality in order to prove Cauchy-Schwarz this way. Fortunately for us, this is exactly what we proved in Part 2. However, in Part 2 we proved the AM/GM inequality for \(n\) variables. We only actually need it for two variables. I’m actually going to prove it for two variables right now, and it’s really easy. Take everyone’s favorite inequality: \(X^2 \ge 0\), with equality if and only if \(X = 0\). Substituting \(a - b\) in for \(X\) gives us \((a - b)^2 \ge 0\) with equality iff \(a - b = 0\) (which is just when \(a = b\)). Expanding that creates \(a^2 + b^2 -2ab \ge 0\) with equality iff \(a = b\), which is just \(a^2 + b^2 \ge 2ab\) with equality iff \(a = b\).

I just proved the version of AM/GM that we’re going to need for this post. This makes Part 2 entirely pointless for this one. At least it was fun though.

Remember that this is called the AM/GM inequality as a shortcut for the Arithmetic Mean/Geometric Mean inequality, because the following two inequalities are interchangeable \[ a^2 + b^2 \ge 2ab \iff \frac{x + y}{2} \ge \sqrt{xy} \] if we substitute \(a \mapsto \sqrt{x}\) and \(b \mapsto \sqrt{y}\) (equality still is iff  \( x = y \) or \(a = b\)). The right hand inequality above states that the arithmetic mean of two numbers is greater than or equal to their geometric mean, which are the two sides of the inequality respectively. The left hand inequality is typically more useful so we’ll use that one instead. It is, in essence, the AM/GM inequality in its most pure form.

Now, let’s actually get to Cauchy-Schwarz. It is enough to show that \(x\) and \( w\) are unit vectors, and prove that \(|\langle x, w \rangle | \le 1\) with equality if and only if \(x = \pm w\), because the inner product is linear in both coordinates. The absolute value of the inner product \(|\langle x, w\rangle|\) is \begin{align*} |\langle x, w\rangle| &= \left|\sum_{i=1}^n x_iw_i\right| \cr &= |x_1w_1 + x_2w_2 + \dots + x_nw_n| \cr &\le |x_1w_1| + |x_2w_2| + \dots + |x_nw_n| \end{align*} where equality only holds in that last one if each \(x_iw_i\) has the same sign as all the others. Continuing, \begin{align*} &= |x_1w_1| + |x_2w_2| + \dots + |x_nw_n| \cr &= |x_1||w_1| + |x_2||w_2| + \dots + |x_n||w_n| \cr &\le \frac{|x_1|^2 + |w_1|^2}{2} + \frac{|x_2|^2 + |w_2|^2}{2} + \dots + \frac{|x_n|^2 + |w_n|^2}{2} \end{align*} with equality if and only if each \(|x_i|\) equals its \(|w_i|\). We just used the two-variable AM/GM inequality there. Regrouping,

\begin{align*} &=\frac{|x_1|^2 + |w_1|^2}{2} + \frac{|x_2|^2 + |w_2|^2}{2} + \dots + \frac{|x_n|^2 + |w_n|^2}{2} \cr &= \frac{1}{2}\left(|x_1|^2 + |x_2|^2 + \dots + |x_n|^2\right) + \frac{1}{2}\left(|w_1|^2 + |w_2|^2 + \dots + |w_n|^2\right) \cr &= \frac{1}{2}|x| + \frac{1}{2}|w| \cr &= \frac{1}{2} + \frac{1}{2} \cr &= 1 \end{align*}

So we have just proven that \(|\langle x, w\rangle| \le 1\) with equality if and only if each \(|x_i| = |w_i|\) and all the \(x_iw_i\)s have the same sign. This means that equality only holds if \(x = \pm w\). So we’re done. QED Potato. \(\Box\)

Hey, that was actually pretty easy. Oh well, that means we don’t necessarily have as much AM/GM as I would have liked, because AM/GM is the best inequality ever, yo. We can fix this. Tune in next time and we’ll do more AM/GM than you ever cared for. It will be delicious. Yes, delicious. And tell your friends, because it’s going to be \(({*})\) Single Star. Until next time, Zorn’s Potato Out.

[thatmathblog]

Prove that the line joining the mid points of two equal chords of a circle subtends equal angles with the chords

I’m not google. Gotta be a bit nicer than that.

[zornspotato]

This is, for once, not LaTeX-enabled post.

It's always amusing when people expect random people on the internet to do their homework for them. The sad part is that it's nearly always totally tactless. When you post the question verbatim and don't provide any preamble or context, then it's pretty easy to tell. If you're going to do it then at least make it less obvious, jeez.

People who blog, peruse Stack Exchange, etc. are not people who are going to do your homework for you and if you think we are then, well, I'm sorry. We're not.

You see, the reason math bloggers such as me blog about math is because we like math. When a particular math thing is intriguing, intriguing enough to tell people, then I write up a post to tell the world about that cool thing.

Seriously, go do your homework. I'm not going to say something stupid like that doing it yourself builds character (WTF does that even mean??) but I will say that it definitely builds mathematical skills.

No really. It's good for you. JUST DO IT. DO IT, DO IT NAOUW.

[zornspotato]

A Tale of Lagrange and Cauchy-Schwarz, Part 2

This is a LaTeX-enabled post. For best viewing, use a browser and view this on my blog, not a mobile device or your dash. Difficulty: \(({*}{*}{*})\) This post is marked as a Triple Star. Prerequisites: Part 1. Before we begin, I want to mention that today my Honors Analysis professor drew a differentiable manifold on the board, kinda like a lump. He described it as a “lumpy potato.” Several of my classmates near me gave me this fake-contemptuous look because they read this blog. This made me feel so honored. I just thought I’d share that.

Anyway, recall from Part 1 the Potato Analogy that I had written, copied here for convenience:

“Suppose you have a potato and you want to make mashed potatoes. First, you clean and peel the potatoes. Next, you boil the potatoes to make them nice and soft. Then you mash them. OR, you could clean and peel the potatoes, then cut them into slices, boil them to make them soft, and mash them. The difference between these is that one has an intermediary step that doesn’t change the final result but does change the journey on how to get there. Despite it being more work to learn how to do it the second way, you end up learning more about the process of cooking potatoes.”

Now, we will learn why this is relevant. You see, in Part 1, I proved that Lagrange Multipliers implies Cauchy-Schwarz. Now that it’s Part 2, I will also prove that Lagrange Multipliers implies Cauchy-Schwarz, but I’m going to do it slightly differently. I’m going to prove that Lagrange Multipliers implies the AM/GM Inequality, which is not the most important inequality ever but it is my favorite. Remember that the AM/GM inequality (which stands for Arithmetic Mean/Geometric Mean) states that the arithmetic mean of \(n\) nonnegative real numbers is always greater than or equal to their geometric mean, with equality if and only if all \(n\) of them are equal to each other. The arithmetic mean of \( n \) real numbers is their sum divided by \(n\), and the geometric mean is the \( n \)th root of their product.

Once we establish the AM/GM inequality, we will then use the AM/GM inequality to prove the legendary Cauchy-Schwarz inequality. This means that we’re actually going to break the second proof of this into two separate posts, so get ready for three-halves the proof and three-halves the fun that you thought you were going to get.

Now, it must seem relevant as to why I made that potato analogy: We’re going to take an intermediary step on the way from the initial setup to the final conditions, and even though it will take longer, we’re going to learn more in the process. Just kidding, this proof is longer because I think that’s more fun. But let’s not dwell on why we’re doing this, just that we’re going to do it and nobody is going to stop me!

Okay. So the first thing I’m going to do is simplify the AM/GM inequality slightly. The AM/GM inequality, as stated, reads like this: \[ \left(y_1y_2\dots y_n\right)^\frac{1}{n} \le \frac{y_1 + y_2 + \dots + y_n}{n} \] with equality if and only if all \(y_i\)s are equal. If we let \(x_i = y_i^{1/n}\), then this inequality is equivalent to the inequality \[ x_1x_2\dots x_n \le \frac{x_1^n + x_2^n + \dots + x_n^n}{n} \] with equality iff all \(x_i\)s are equal. We’re going to add the additional stipulation that \(n \ge 2\) because in the case where \(n = 1\) this is trivially true.

It’s convenient to note that \(x_1^n + \dots + x_n^n\) is exactly the value \( \|x\|_n^n \), where \(\|x\|_n\) is the \(L^n\)-norm of \(x\), and \( x\) is the vector whose entries are \(x_i\)s. (The \(L^n\)-norm is defined as \( (|x_1|^n + \dots + |x_n|^n)^{1/n}\), and satisfies all the nice properties of norms.) This is convenient because now, it is enough to show that \[ x_1\dots x_n \le \frac{1}{n} \] as long as \(\|x\|_n = 1\). We can do this because as long as \(x\) is nonzero, we can scale \(x\) by its \(L^n\)-norm without affecting the inequality, because both sides scale by a factor of \(\|x\|_n^n\). In the case where \(x\) is zero, then the inequality is trivially true. We’re then going to replace this constraint equation with \(\|x\|_n^n = 1\) rather than \(\|x\|_n = 1\), because the former is \( C^\infty \) (this is the same thing we did in Part 1), and we’re going to once more change this, to \(\|x_n\|_n^n/n - 1/n = 0\).

Now, we can define the compact differentiable manifold on which we’re maximizing our function, and which function we’re maximizing. We’re going to maximize the function \begin{align*} h : \mathbb{R}^n &\to \mathbb{R}\cr x &\mapsto x_1x_2\dots x_n \end{align*} subject to the constraints \(f(x) = 0\) and \(x_i \ge 0\), where \begin{align*} f : \mathbb{R}^n &\to \mathbb{R}\cr x &\mapsto \frac{\|x\|_n^n}{n} - \frac{1}{n} \end{align*} This gives us a compact, differentiable manifold whose boundary is the set of \( x\) such that \(x_i\) is zero for some \(i\). Now, we’re going to use Lagrange Multipliers to maximize this function on our differential set, by finding critical points and checking critical points and endpoints. (We also have that \(h\) and \( f\) are \(C^\infty\), so that’s covered.)

Taking the gradient, we get that \[ \nabla h = \left(\begin{array}{c} \phantom{x_1}x_2x_3 \dots x_{n-2}x_{n-1}x_n \cr x_1\phantom{x_2}x_3 \dots x_{n-2}x_{n-1}x_n \cr x_1x_2\phantom{x_3}\dots x_{n-2}x_{n-1}x_n \cr \vdots \cr x_1x_2x_3\dots x_{n-2}\phantom{x_{n-1}}x_n \cr x_1x_2x_3\dots x_{n-2}x_{n-1}\phantom{x_n} \end{array}\right) \] and we get that \[ \nabla f = \left(\begin{array}{c} x_1^{n-1} \cr x_2^{n-1} \cr \vdots \cr x_n^{n-1} \end{array}\right) \] Now, when we get our lagrange multipliers, setting \(\nabla h = \lambda \nabla f\), we get the equations \begin{align*} x_2x_3\dots x_n &= \lambda x_1^{n-1} \cr x_1x_3\dots x_n &= \lambda x_2^{n-1} \cr &\vdots \cr x_1\dots x_{n-1} &= \lambda x_n^{n-1} \end{align*} plus our constraints.

If we multiply all \(n\) of these equations together, we get that \[ x_1^{n-1}x_2^{n-1}\dots x_n^{n-1} = \lambda^n x_1^{n-1}x_2^{n-1 }\dots x_n^{n-1} \] so \( \lambda^n = 1\), so \(\lambda\) is a root of unity. But looking at all of our original equations, we have a nonnegative real number is \(\lambda\) times another nonnegative real number, for all of the equations, which means that \( \lambda \) must be equal to \(1\), and not \(-1\) or a complex root. (Remember that we can’t have \(x = 0\) because \(\|x\|_n = 1\)).

Now that we’ve decided that \(\lambda = 1\) is a necessary condition for a solution, we can look back to our equations: \begin{align*} x_2x_3\dots x_n &= x_1^{n-1} \cr x_1x_3\dots x_n &= x_2^{n-1} \cr &\vdots \cr x_1\dots x_{n-1} &= x_n^{n-1} \end{align*} I claim that if all \(x_i\)s equal each other then this is a solution to these equations. If each \(x_i\) equals each other one, then all of the equations become \(x_i^{n-1} = x_i^{n-1}\), which is satisfied, and the constraint is satisfied as long as they’re all equal to \((1/n)^{(1/n)}\). (This is because if we take each of those to the \(n\)th power we get \(1/n\), which becomes \(1\) when we add all \( n\) of them together.) So it’s not hard to see that this is a sufficient condition for a solution.

I also claim that \(x_i\)s equalling each other is a necessary condition. Because the set of \(x_i\)s is a finite set, there must be some \(x_i\) that is a smallest member, but not necessarily unique. That is \(x_i \le x_j\) for any \(1 \le j \le n\). If we look at the particular equation for that one \(x_i\), we get \[ x_1\dots x_{i-1}x_{i+1}\dots x_n = x_i^n \] If any of the \(x_j\)s on the left-hand side are strictly greater than \(x_i\), then the left-hand side would be strictly greater than the right-hand side. This would not satsify the equation, so the only way for this particular equation to hold is for each \(x_j\) to be equal to \(x_i\). So the only way this can be solved is if each \( x_j\) equals each \(x_i\) for any \(i\) or \(j\).

Now, we have shown that there is only one critical point, i.e. each \(x_i\) equals each other and equals \((1/n)^{(1/n)}\), so it suffices to check the critical point and the boundary points. The boundary of the compact set on which we’re maximizing is the set of all points where at least one \(x_i\) equals zero. If at least one \(x_i\) equals zero, then \(h(x) = 0\) because \(h\) is the product of the entries of \(x\). If \(x\) is the critical point, then \(h(x) = 1/n\). The number \(1/n\) is positive so the maximum occurs at the critical point and the minimum occurs along the boundary.

This means that because the maximum is achieved at the critical point, we have that the function \(h\) must be less than or equal to the maximum value, with equality if and only if we’re at the critical point. That is, \[ h(x) \le \frac{1}{n} \] if \(\|x\|_n = 1\), and with equality if and only if \(x_1 = \dots = x_n\). If we then work backward and remove our stipulation that \(\|x\|_n = 1\), we get the inequality: \[ x_1\dots x_n \le \frac{x_1^n + \dots + x_n^n}{n} \] with equality if and only if \(x_1 = x_2 = \dots = x_n\), which is equivalent to the inequality \[ \left(x_1\dots x_n\right)^\frac{1}{n} \le \frac{x_1 + \dots + x_n}{n} \] with equality if and only if \(x_1 = x_2 = \dots = x_n\). And that is exactly the AM/GM inequality. So we’re done proving the AM/GM inequality! QED Potato. \( \Box\)

We’ve done the bulk of the work at this point, but I do want to mention that we’re not quite done. Now, we have to use the AM/GM inequality to prove Cauchy-Schwartz. “How are we going to do that?” I hear you cry. Well fear not, because this is a proof that will be covered in Part 3 of A Tale of Lagrange and Cauchy-Schwartz. Sit back, relax, wait for me to finish this week’s homework because that’s more important, and THEN you shall receive. Until next time, Zorn’s Potato Out.

[zornspotato]

A Tale of Lagrange and Cauchy-Schwarz, Part 1

This is a LaTeX-enabled post. For best viewing, use a browser and view this on my blog, not a mobile device or your dash. Difficulty: \(({*}{*}{*})\)This post is marked as a Triple Star. Prerequisites: You should know how to do Lagrange Multipliers or you will have no idea what I’m doing. It might also help to be somewhat familiar with the Cauchy-Schwarz inequality because otherwise you might not understand the motivation for this proof. (The CS inequality is sometimes states as the most important inequality in all of math. Proofs of it are numerous and different.)

It appears I haven’t made a post in quite some time. I owe you guys a proof. Now, suppose you have a potato and you want to make mashed potatoes. First, you clean and peel the potatoes. Next, you boil the potatoes to make them nice and soft. Then you mash them. OR, you could clean and peel the potatoes, then cut them into slices, boil them to make them soft, and mash them. The difference between these is that one has an intermediary step that doesn’t change the final result but does change the journey on how to get there. Despite it being more work to learn how to do it the second way, you end up learning more about the process of cooking potatoes. For more information on why this is a relevant anecdote, see part two when it comes out. Unless you are reading this in the future, in which case just go read part two.

So now, we’re going to discuss Lagrange Multipliers. Actually, we’re going to discuss the Cauchy-Schwarz inequality in \(\mathbb{R}^n\). BUT WHICH ONE? What if I told you... that we were going to discuss both AT THE SAME TIME?!?! You’d probably not panic and you’d probably say, “I figured that’s what you were going to do.” This will make me sad that I was so predictable, but that’s okay. We’re going to prove the Cauchy-Schwarz inequality in \(\mathbb{R}^n\) using Lagrange Multipliers.

So I want to do a disclaimer. Most of the proofs on this blog I came up with myself. This one I did as well, and when I found out that this is a well-known fact I got quite sad that I wasn’t original, but at least happy that it meant I was probably right.

Recall that the Cauchy-Schwarz inequality states that if \(w, x \in \mathbb{R}^n\), then \(|\langle w, x\rangle | \le \|w\|\|x\| \) with equality if and only if \(w\) and \(x\) are linearly dependent. What I’m going to do is fix \(w \in \mathbb{R}^n\), and I’m going to prove that for \(x \in \mathbb{R}^n\) where \(\|x\| = 1\), then we have that \( |\langle w, x\rangle | \le \|w\| \) with equality if and only if \(w = \mu x\) for some \(\mu \in \mathbb{R}\). If we can do this, then it works for any non-unit vector too, because we can divide by the norm of it (unless it’s zero, in which case we’ve already won).

The first thing I’m going to do is note that \(\|x\| = 1\) is the same statement as \(\|x\|^2 = 1\) (the norm is always nonegative), so I will use that one instead. We’re going to try to maximize \(h : \mathbb{R}^n \to \mathbb{R}\) where \(h(x) = \langle w, x\rangle\), subject to the constraint equation \(f : \mathbb{R}^n \to \mathbb{R}\) where \(f(x) = \|x\|^2 - 1 = 0\). Now, we need to check to make sure we can actually use lagrange multipliers. First, is our constraint set compact? Well our constraint set is \(\|x\|^2 - 1 = 0\), which is the boundary of the unit ball, which is compact. Second, are \(h\) and \(f\) sufficiently continuous/differentiable? Well, they’re both \(C^\infty\), which is good enough. (This is one of the advantages of using \(\|x\|^2\) over \(\|x\|\): the first one is \(C^\infty\).)

So let’s calculate our derivatives. \(h(x) = \langle w, x\rangle\), which can be rewritten as \(w_1 x_1 + w_2 x_2 + \dots + w_n x_n\). Thus, when we take the gradiant, we get \(\nabla h = (w_1, w_2, \dots, w_n) = w\). \(f(x) = \|x\|^2 - 1\), which can be rewritten as \(x_1^2 + x_2^2 + \dots + x_n^2 - 1\). When we take the gradiant, we get \(\nabla f = (2 x_1, 2 x_2, \dots, 2 x_n) = 2x\). So now, we collect our equations, which are: \begin{align*} \nabla h &= \lambda \nabla f \cr 1 &= \|x\|^2 \end{align*} Substituting, we get that the critical points occur at solutions to \begin{align*} w &= 2\lambda x \cr 1 &= \|x\|^2 \end{align*} But wait! Look at that first equation! That one says critical points only occur when \(w\) is a constant multiple of \(x\)! This means that the function \(h\) is maximized and minimized when \(w = \pm \mu x\) for some real number \(\mu \ge 0\). We know this because there’s only two unit vectors that are a constant multiple of any arbitrary vector, and those are negatives of each other. (Here, if \(w\) is zero, then we only get one solution and that’s \(\mu =0\)).

Now, we have to check our critical points. Checking \(w = \mu x\), we get that \begin{align*} h(x) &= \langle w, x\rangle \cr &= \langle \mu x, x \rangle \cr &= \mu \|x\|^2 \cr &= \mu \|x\| \cr &= \|\mu x\| \cr &= \|w\| \cr \end{align*} Checking \(w = -\mu x\), we get \begin{align*} h(x) &= \langle w, x\rangle \cr &= \langle -\mu x, x \rangle \cr &= -\mu \|x\|^2 \cr &= -\mu \|x\| \cr &= -\|\mu x\| \cr &= -\|w\| \cr \end{align*} Clearly, \(\|w\|\) is the maximum and \(-\|w\|\) is the minimum because \(\|w\| \ge 0\) and \(-\|w\| \le 0\). But wait! If \(h\) is maximized at \(\|w\|\) on our compact set, then we have that \(h(x) \le \|w\|\) for \(\|x\|^2 = 1\), with equality iff we’re at the maximum. Similarly, \(h(x) \ge -\|w\|\), with equality iff we’re at the minimum. But we can combine these two inequalities together to give us \(|h(x)| \le \|w\|\), with equality iff we had equality before, so iff we were at either the max or the min. But \(|h(x)| \le \|w\|\) is exactly the Cauchy-Schwartz inequality when we expand it out: \(h(x) = \langle w, x\rangle\), so this means that we have \(|\langle w, x\rangle| \le \|w\|\) for \(\|x\| = 1\), with equality if and only if \(w = \alpha x\), for some \(\alpha \in \mathbb{R}\). So we’re done! QED Potato \(\Box\).

I just gave a direct proof of the Cauchy-Schwartz inequality in \(\mathbb{R}^n\) with Lagrange Multipliers. Direct proofs aren’t quite as fun as indirect proofs, so tune in next time for Part 2 when we prove the same thing (that is, Lagrange Multipliers \(\implies\) Cauchy-Schwarz), but this time we prove an intermediary theorem. But which one? That’s going to be a surprise (unless you can guess, in which case it won’t be a surprise). Anyway, until next time, Zorn’s Potato out.

[zornspotato]

Oops, I Spilled Linear Algebra on my Analysis Potatoes

This is a LaTeX-enabled post. For best viewing, use a browser and view this on my blog, not a mobile device or your dash. Difficulty: \(({*}{*})\) This post is marked as a Double Star. Prerequisites: You should know just a little bit about the vector space \( \mathbb{R}^n\), and just a little bit about linear algebra. This is a Double Star so I will define everything important, but I won’t prove elementary theorems.

Those of you who have lived in the United States know that potatoes are an almost ubiquitous source of food for people who want to eat things. Some people don’t particularly like eating things. Those people are dumb.

Those of you who have lived in a math department know that linear algebra is an almost ubiquitous source of proofs for people who want to prove things. Some people don’t particularly like proofs. Those people are also dumb.

You like proofs because you’re still reading this, so I suggest a hypothesis: Linear algebra and potatoes are similar. Both Linear Algebra and potatoes represent a large quantity of carbohydrates, with just a sign error. Potatoes make the carbohydrates go in, to be subsequently spent on Linear Algebra.

Whether or not this conjecture is true, what is true is that linear algebra shows up everywhere. This post will represent part three of the Linear Algebra Saga. (For part one, see Prime and Irreducible the Hard Way, Part 2 where we reduce our problem to a matrix equation, find a solution, and prove it’s unique by proving that our matrix is invertible because its determinant is nonzero. For part two, see Dividing Up Students In Class Discussions, Now With More Math where we take the vector space \(\mathbb{F}^2\) over \(\mathbb{F}\), where \( \mathbb{F}\) is a finite field.) This post will not be primarily about linear algebra but rather it will propose a random problem in real analysis and solve it with linear algebra. There may also be potatoes.

First, let me get a bit of conventions out of the way. I will use lowercase Greek letters to denote scalars, that is, elements of \(\mathbb{R}\). I will use lowercase Latin letters (other than \(n\) and \(i\)) to denote vectors, that is, elements of \( \mathbb{R}^n\), or functions. (\(n\) and \(i\) are natural numbers here.) I will use capital Latin letters to denote sets, matrices, or linear transformations.

Without further ado, let’s get this potato out of the bag. Let \(g : \mathbb{R}^n \to \mathbb{R}\) be a non-negative, homogeneous, convex function. Here, homogeneous means that \(g(\alpha x) = |\alpha| g(x)\) for \(\alpha \in \mathbb{R}\), and convex means that if \(\alpha \ge 0\) and \(\beta \ge 0\) and \(\alpha + \beta = 1\), then \(g(\alpha x + \beta y) \le \alpha g(x) + \beta g(y)\). Astute readers will realize that \(g\) is convex if and only if \(\{(x, \lambda) \in \mathbb{R}^{n+1} : \lambda \ge g(x)\}\) is a convex set (which is the motivation for that name) but I won’t dwell on that too much. Now, let \(A\) be the set \(\{x \in \mathbb{R}^n : g(x) \le 1\}\), or in words it’s the set of all potatoes in \(\mathbb{R}^n\) that are mapped to something less than or equal to \(1\).

Here’s the proof at hand: Prove that \(A\) contains \(0\) in its interior. (Recall that \(0 \in \mathrm{int}(A)\) as long as there is some \(\varepsilon > 0\) so \(\{x \in \mathbb{R}^n : \|x\| < \varepsilon\} \subseteq A\), or, “there is some ball around zero entirely within \(A\).”)

First, I will prove that \(g\) obeys the triangle inequality. Consider \(x, y \in \mathbb{R}^n\). \(g\) is convex, so we know that \(g(x/2 + y/2) \le g(x)/2 + g(y)/2\). Mulitplying both sides by two, we get that \(2\cdot g((x + y)/2) = g(x) + g(y)\). But \(g\) is homogeneous, so this just becomes \(g(x + y) \le g(x) + g(y)\), which is exactly the triangle inequality. We can extend this by induction to give us \(g(x_1 + \dots + x_n) \le g(x_1) + \dots + g(x_n)\).

Now, we get to pull out the linear algebra. First, I will prove that \(\dim(\mathrm{span}(A)) = n\). (We’re working in \(\mathbb{R}^n\) and that’s the same \(n\).) Let \(B = A^\perp\), or the orthogonal complement of \(A\), which is the set \(\{b \in \mathbb{R}^n : \langle a, b \rangle = 0, \forall a \in A\}\). This is the set of all vectors that are orthogonal to every element of \(A\). Let’s pick an arbitrary \(b \in B\). Now, I’m going to define this weird scalar \(\mu\):

\[\mu = \left\{\begin{array}{l r} 1 & \mathrm{if}\ g(b) \le 1 \cr 1/g(b) & \mathrm{if}\ g(b) > 1 \end{array}\right.\]

Note that in either case \(0 < \mu \le 1\). Now, let’s consider \(g(\mu b)\). Well, \( g(\mu b) = \mu g(b)\). If we’re in the case where \(g(b) \le 1\) then \(\mu g(b) = 1 \cdot g(b) = g(b) \le 1\), so \(g(\mu b) \le 1\). If we’re in the case where \(g(b) > 1\), then \(\mu g(b) = \frac{1}{g(b)}\cdot g(b) = 1 \le 1\), so \(g(\mu b) \le 1\) as well. This means in either case, \(\mu b \in A\).

Recall that \(b \in B = A^\perp\), which means that \(\langle a, b \rangle = 0, \forall a \in A\). In particular \(\mu b \in A\), which means that \(\langle \mu b , b \rangle = 0\). But \(\langle \mu b , b \rangle = \mu \|b\|^2 = 0\), and \(\mu \neq 0\). So by the property of normed vector spaces, \(b = 0\), so we just proved that any \(b \in A^\perp\) is zero, or that \(A^\perp = \{0\}\). Wait what? Yep. Weird, I know.

Now, we know that \(A \subseteq \mathrm{span}(A)\), so it follows that \(\mathrm{span}(A)^\perp \subseteq A^\perp\). But in this case, we have that \( A^\perp = \{0\}\), so \(\mathrm{span}(A)^\perp = \{0\}\) as well (because \(0\) is always in the \(\perp\) because it’s a subspace). We know that \[\dim(\mathrm{span}(A)) + \dim(\mathrm{span}(A)^\perp) = n\]

(we’re in \(\mathbb{R}^n\), remember?) because of that really handy theorem we learned in linear algebra class. Because \(\dim(\mathrm{span}(A)^\perp) = 0\), it follows that \(\dim(\mathrm{span}(A)) = n\), which means that \(\mathrm{span}(A) = \mathbb{R}^n\).

Okay, now what? It follows from linear algebra that there is a subset of \(A\) that is a basis for \(\mathrm{span}(A)\), which means that there is a subset \(\{a_1, a_2, \dots, a_n\} \subseteq A\) that is a basis for \(\mathbb{R}^n\). Let’s consider the matrix

\[M = \left[\begin{array}{c c c} \vdots & & \vdots \cr a_1 & \cdots & a_n \cr \vdots & & \vdots \end{array}\right]\]

These columns are linearly independent so \(M\) is invertible. Now, let \(z\) be an arbitrary vector in \(\mathbb{R}^n\) such that \(\|z\| \le 1\). We can write \(z\) as a linear combination of \(a_1, \dots, a_n\) because they form a basis, so we have that \(z = \lambda_1 a_1 + \dots + \lambda_n a_n\), and this representation is unique. Now, let \(y = M^{-1}z\). Because \(\|z\| \le 1\), we have that \(\|y\| \le \|M^{-1}\|\) where \(\|M^{-1}\|\) is the operator norm or the induced euclidean norm of \(M^{-1}\). This is the largest norm value we can get by taking the transformation of a unit vector. Also, because \(z = My\), it follows that \(y = \lambda_1 e_1 + \dots + \lambda_n e_n\), where \(\{e_i\}\) forms that standard basis for \(\mathbb{R}^n\), so \(y\) is just the vector \((\lambda_1, \dots, \lambda_n)\).

Now, let’s look at \(g(z)\). We have that \(g(z) = g(\lambda_1 a_1 + \dots + \lambda_n a_n)\). Now, we finally pull out the triangle inequality and use \(g(z) \le g(\lambda_1 a_1) + \dots + g(\lambda_n a_n)\). But \(g\) is homogeneous, so this gives us \(g(\lambda_1 a_1) + \dots + g(\lambda_n a_n) \le |\lambda_1| g(a_1) + \dots + |\lambda_n| g(a_n)\). Each \(a_i \in A\), so \(g(a_i) \le 1\), which means that we get \(|\lambda_1| g(a_1) + \dots + |\lambda_n| g(a_n) \le |\lambda_1| + \dots + |\lambda_n|\). Chaining this inequalities together, we have that

\begin{align*} g(z) &= g(\lambda_1 a_1 + \dots + \lambda_n a_n) \cr &\le g(\lambda_1 a_1) + \dots + g(\lambda_n a_n) \cr &= |\lambda_1| g(a_1) + \dots + |\lambda_n| g(a_n) \cr &\le |\lambda_1| + \dots + |\lambda_n| \cr &\le n \cdot \max\{|\lambda_i|\} \cr &= n \|y\|_\infty \end{align*}

Here, the infinity norm is the maximum of the absolute values of the coordinates. Since \(y = (\lambda_1, \dots, \lambda_n)\), it follows that \(\|y\|_\infty =  \max \{ |\lambda_i|\}\). Another theorem from real analysis states that \(\|y\|_\infty \le \|y\|_2\) for \(y \in \mathbb{R}^n\) (where \(\|y\|_2\) is the standard euclidean norm), so this means that \(n \|y\|_\infty \le n\|y\|_2\). But recall from earlier that \( y = M^{-1}z\) and \(\|z\| \le 1\), so \(\|y\| \le \|M^{-1}\|\). Chaining these together gives us

\begin{align*} g(z) &\le n\|y\|_\infty \cr &\le n \|y\| \cr &= n\|M^{-1}z\| \cr &\le n\|M^{-1}\| \end{align*}

However, recall that \(n\) is our dimension and that \(\|M^{-1}\|\) didn’t depend on our choice of \(z\), just our \(n\) linearly independent vectors of \(A\). So now, let’s take the ball around zero defined by

\[B = \left\{b \in \mathbb{R}^n : \|b\| < \frac{1}{n \|M^{-1}\|}\right\}\]

Fix some \(b \in B\). Let \(z = n \|M^{-1}\| \cdot b\). Here, \(\|z\| \le 1\), so it follows that \(g(z) \le n \|M^{-1}\|\) by the above inequality chain. This means that

\begin{align*} g(b) &= g\left(\frac{z}{n \|M^{-1}\|}\right) \cr &= \frac{1}{n \|M^{-1}\|} g(z) \cr &\le \frac{1}{n \|M^{-1}\|}n \|M^{-1}\| \cr &=1 \end{align*}

So it follows that \(b \in A\) because \(g(b) \le 1\). But \(b\) was just an arbitrary point in \(B\), so we’ve just proved that \(B \subseteq A\). But wait! \(B\) is an open ball containing zero and \(B \subseteq A\), which is exactly the definition for \(0 \in \mathrm{int}(A)\). So we’re done! Q.E.D. Potato. \(\Box\)

[zornspotato]

Forking the Potato

I’ve forked my math blog and all of my math posts will be located here from now on. I’ve reblogged the old posts rather than repost them, but I don’t intend to reblog any more. New ones will be here form now on. 

[thebombzen]

Dividing Up Students In Class Discussions, Now With More Math

This is a LaTeX-enabled post. For best viewing, use a browser and view this on my blog, not a mobile device or your dash. Difficulty: \(({*}{*}{*})\) This post is marked as a Triple Star. Prerequisites: You should be familiar with vector spaces over arbitrary fields, as well as some basic theorems from linear algebra. If I say “Let \(\mathbb{F}\) be a finite field, and \(\mathbb{F}^2\) be a vector space over \(\mathbb{F}\)” you should not panic.

So the math for this problem came from a day where I was bored in English class. It turned out that there were exactly sixteen people in my class, and \(16\) has some cool properties. One fact that’s true about \(16\) is that

\[ \frac{16}{64} = \frac{1\!\!\not\!6}{\not\!64} = \frac{1}{4} \] but this is completely irrelevant. Avid readers will also realize, “But Leo! Sixteen is a square number.” (Hint: That’s me. I am Leo. Please do not ask me a stupid question like “Are you a Leo?”) What this means is that sixteen is not only a square, sixteen is actually a whole bunch of squares! See, look here: \[ \left(\begin{array}{cccc} \Box & \Box & \Box & \Box \cr \Box & \Box & \Box & \Box \cr \Box & \Box & \Box & \Box \cr \Box & \Box & \Box & \Box \end{array}\right) \] This is also what it looks like when you accidentally forgot to enter in your values into your Mathematica matrix, but once again, that is totally irrelevant.

Sixteen is actually equal to \(4 \times 4\), which means that we could divide the sixteen students in my English class into four groups of four, which is, in fact, exactly what we did. On that day in class, I saw three other students because we only had time to split up into groups once. However, there were fifteen students who were not me, and each time we split up I saw three others, so if we did the same activity five separate times, I should be able to see all \(3 \times 5 = 15\) other students. But that raises the question: “Do I have to be special?” Is it possible to divide up into groups five times so each student sees the students who are not him/her exactly once?

The answer to this question is “Yes.” But we can generalize this problem to any square number of students. If there are \(n^2\) students, then when the students divide into \(n\) groups of \(n\), each student sees \(n - 1\) others. This means if you repeat this on \(n + 1\) different class periods, each student will see \((n - 1)\times(n+1) = n^2 - 1\) other students. So for a generic \(n\), is it possible to divide it up so each student sees each other student exactly once?

The answer is actually kind of weird and counterintuitive. A simple “um… yea” or “no” won’t suffice. In fact, if \(n\) is a prime or a power of a prime, then the answer is proveably “yes.” Four falls under this category, because \(4 = 2^2\). Also, if \(n \equiv 1\) or \(n \equiv 2\) (mod 4), and \(n\) cannot be written as a sum of two squares, the answer is provably “no,” but this is very hard and I will not do it here. We also know that if \(n = 10\) the answer is “no,” by checking possibilities with a computer (plus some theorems that let us eliminate some). However, every other number is an open problem. This is a particular case of a problem known as the “social golfer problem,” which is the same idea but instead of dividing into groups with other students, the premise is going golfing with groups of friends. This problem is happens to be equivalent to the question “Is there a finite projective plane of order \(n\)?” but I will not discuss this isomorphism. This problem is also equivalent to the question, “Does there exist a Steiner system \(S(2, n, n^2)\),” but this is also not something I will discuss. Those are up to you to research. What I’m actually going to prove here is that the answer is “yes” for primes and powers of primes. I will not discuss the two “no” cases because those are all proofs that are fairly difficult and don’t relate to the initial problem, but rather to the equivalent problems. 

A bit of a disclaimer: This is a proof that @absurdseagull and I came up with together, although they did most of the heavy lifting in terms of the pattern recognition. I formalized it and had the idea to use vector spaces to make the proof more elegant. 

Let’s get to it. Recall that if \(n = p^m\) for some prime \(p\) and some positive integer \(m\), then there is a finite field \(\mathbb{F}\) with \(|\mathbb{F}| = n\). Now, let’s consider the vector space \(\mathbb{F}^2\) over the field \(\mathbb{F}\). For every nonzero point in \(a \in \mathbb{F}^2\), we get a the set \(S_a = \mathrm{span}\{a\}\). We know that \(\mathrm{span}\{a\} = \mathbb{F}\cdot a\), so there are exactly \(n\) elements in \(S_a\), of which \(n-1\) are nonzero. In fact, for any \(0 \neq b \in S_a\), we have that \(S_b = S_a\), simply because all nonzero elements of \(\mathbb{F}\) are invertible. This means that if we take \(S_x\) for all \(0 \neq x \in \mathbb{F}^2\), then each \(S_x\) was counted a total of \(n - 1\) times, once for each nonzero element of \(S_x\). This means out of the full \(n^2 - 1\) nonzero points in \(\mathbb{F}^2\), we’ve counted \((n^2 - 1) / (n - 1)\) unique sets, or \(n + 1\) unique sets.

For any of our linear subspaces \(S_a\) of \(\mathbb{F}^2\), we can consider the family of affine subspaces parallel to \(S_a\), of which there is one for each element of \(\mathbb{F}\). This gives us \(n+1\) different families of affine subspaces. I claim that one family of affine subspaces represents one configuration of students on a given class day. Our \(n\) different affine subspaces, each with \(n\) elements, divide up \(\mathbb{F}^2\) into \(n\) pairwise disjoint sets of size \(n\). If we pair each student with an element of \(\mathbb{F}^2\), then we get a corresponding way to divide up the students into \(n\) groups of size \(n\).

Now, all we have to do is show that the intersection of any affine subspace in one family with an affine subspace in another family contains at most one point. This means that given any two class groups from two different days, those groups have at most one memeber in common, so for any two groups, those groups don’t have a pair of students that’s repeated. Let \(S_{(x_1, y_1)} + (a_1, b_1)\) be a member of the first family, and \(S_{(x_2, y_2)} + (a_2, b_2)\) be a member of the second family. We’re trying to find a point where \(\alpha (x_1, y_1) + (a_1, b_1)\) equals \(\beta (x_2, y_2) + (a_2, b_2)\), with \(\alpha \in \mathbb{F}\) and \(\beta \in \mathbb{F}\) . If we set these equal to each other and solve, we get that \begin{align*} \alpha (x_1, y_1) + (a_1, b_1) &= \beta (x_2, y_2) + (a_2, b_2) \cr \alpha (x_1, y_1) &= \beta (x_2, y_2) + (a_2 - a_1, b_2 - b_1) \cr \alpha (x_1, y_1) - \beta (x_2, y_2) &= (a_2 - a_1, b_2 - b_1) \end{align*} Remember that the only variables here are \(\alpha\) and \(\beta\), because we’re trying to find an \(\alpha\) and a \(\beta\) that satisfy the above equation. But \((x_1, y_1)\) and \((x_2, y_2)\) are linearly independent because they belong to different linear one-dimensional subspaces (those being \(S_{(x_1, y_1)}\) and \(S_{(x_2, y_2)}\), respectively). This means that if we can write \((a_2 - a_1, b_2 - b_1)\) as a linear combination of \((x_1, y_1)\) and \((x_2, y_2)\), then that linear combination is unique. So our equation \(\alpha (x_1, y_1) - \beta (x_2, y_2) = (a_2 - a_1, b_2 - b_1)\) has at most one solution for \(\alpha\) and \(\beta\). Actually, it’s true that each affine subspace intersects an affine subspace from another family exactly once, not just at most once. Once you have that the intersection is at most once, and you have an affine subspace \(S_x + a\) and a family generated by \(S_y\), you can use a counting argument to show that each of the \(n\) elements of \(S_x + a\) is in one of the \(n\) affine sets generated by \( S_y\), and because there’s no overlap, each family member of \(S_y\) must contain an element of \(S_x + a\). However, we don’t actually need that the intersection is exactly one element, we just need that it’s at most one element, but it’s worth proving that it’s exact. 

So we have just created \(n+1\) different families of subdivisions, where each family is a partition of \(\mathbb{F}^2\) into \(n\) pairwise disjoint sets of size \(n\), and where two elements of different families intersect in at most one location. This means that once we label our students with the elements of \(\mathbb{F}^2\), we get \(n+1\) different class periods where each class period involves dividing up the students into \(n\) groups of \(n\), and over the entire \(n+1\) days, no student sees the same student twice. And all we had to assume was that \(n\) is a prime or a power of a prime. Q.E.D. Potato. \(\Box\)

[thebombzen]

Prime and Irreducible, The Hard Way: Part 2

This is a LaTeX-enabled post. For best viewing, use a browser and view this on my blog, not a mobile device or your dash. Difficulty: \(({*}{*})\) This post is marked as a Double Star. Prerequisites: Part 1. Okay, so this is the moment we’ve all been waiting for. The purpose of this part is to prove that the polynomial \(x^2+x+1\) is prime in the ring \(\mathbb{R}[x]/(x^3-1)\). Recall that a polynomial \(p\) is prime iff it is not a unit, and whenever \(p|ab\) it means \(p|a\) or \(p|b\). Also, recall the special property, that \((ax^2 + bx + c) \cdot (x^2 + x + 1) = (a + b + c)\cdot(x^2 + x + 1)\).

If \((x^2+x+1)|p(x)q(x)\), that means that \((x^2+x+1)\cdot r(x) = p(x)q(x)\) for some polynomial \(r(x) \in R\). However, remember that \((x^2+x+1)\cdot r(x) = \alpha \cdot (x^2 + x + 1)\) for some \(\alpha \in \mathbb{R}\) because of the special property. This means \(\alpha (x^2 + x + 1) = p(x)q(x)\). So we now have two cases to check: \(\alpha = 0\) and \(\alpha \neq 0\). I will deal with the \( \alpha = 0\) case first.

If \(\alpha = 0\), then \(0 = p(x)q(x)\). This means \(p(x)q(x) = s(x)\cdot (x^3-1)\) in the ring \(\mathbb{R}[x]\), for some polynomial \(s(x)\). Our favorite trinomial, \( x^2 + x + 1\), is prime in the ring \(\mathbb{R}[x]\), and it divides the right-hand side of that equation. So we have that it also divides the left-hand side, so \( (x^2 + x + 1)|p(x)q(x)\), which means it must divide one or the other in \( \mathbb{R}[x]\). But if it divides \(p(x)\) or \( q(x)\) in \(\mathbb{R}[x]\), it must also divide \(p(x)\) or \(q(x)\) in \(\mathbb{R}[x]/(x^3-1)\). So we’re done.

In the case where \(\alpha \neq 0\), without loss of generality we can divide both sides by \(\alpha\) and get that \(x^2+x+1 = p(x)q(x) = (ax^2 + bx + c)(dx^2 + ex + f)\). We are going to show that \(x^2 + x + 1\) divides either \(ax^2 + bx + c\) or \(dx^2 + ex + f\). To do this, we are going to prove the statement: “If it is not true that \(a = b = c\), then we must have \(d = e = f\).” This way, in both of the two cases (either we have \(a = b = c\) or we don’t), we still get that either \(a = b = c\) or \(d = e = f\). So without further ado, let’s assume that it is not true that \(a = b = c\) and prove that \(d = e = f\).

Expanding out the right-hand side of that equation yields that \((ax^2 + bx + c)\cdot (dx^2 + ex + f)\) expands into \(adx^4 + aex^3 + afx^2 + bdx^3 + bex^2 + bfx + cdx^2 + cex + cf\), which is just \((af + be + cd)x^2 + (ad + bf + ce)x + (ae + bd + cf)\). That entire polynomial must equal \(x^2 + x + 1\), so it follows that \( af + be + cd = 1\), that \(ad + bf + ce = 1\), and that \(ae + bd + cf = 1\). Now, this gives us the matrix equation \[ \left[\begin{array}{ccc} c & b & a \cr a & c & b \cr b & a & c \end{array}\right] \times \left[\begin{array}{c} d \cr e \cr f \end{array}\right] = \left[\begin{array}{c} 1 \cr 1 \cr 1 \end{array}\right] \]

First, I will prove that \(a + b + c \neq 0\). To do this, I will add the three equations together, which gives us \(af + be + cd + ad + bf + ce + ae + bd + cf = 3\). That factors nicely into \((a + b + c)(d + e + f) = 3\), which seems miraculous at first but on second thought is rather unsurprising given that we originally got to that convolution by multiplying two things together that looked fairly similar to what we have here. Notably, \(a+b+c\) and \(d+e+f\) are real numbers, so neither \(a+b+c\) nor \(d+e+f\) is zero.

Now, I claim that \(d = e = f = 1/(a + b + c)\) satisfies this matrix system, where \( 1/(a+b+c)\) is well-defined because \(a+b+c\) is nonzero. If we want to check this solution, we get that each of the three equations become \(d\cdot(a + b + c) = 1\), as long as \(d = e = f\). If \(d = 1/(a+b+c)\), then each of these equations are satisfied and we get that \(d = e = f = 1/(a + b + c)\) is a solution to this system of linear equations.

This is actually the only solution to this linear system, which I will now prove. This is the only solution as long as that matrix there is invertible. That matrix is invertible as long as its determinant is nonzero. If we take the determinant, and we get \[ \mathrm{det}\left[\begin{array}{ccc} c & b & a \cr a & c & b \cr b & a & c \end{array}\right] = c^3 + b^3 + a^3 - 3abc \] and we want to prove that if \(a, b, c \in \mathbb{R}\), and it is not true that \(a = b = c\), then this determinant is nonzero. If we can show that this polynomial has no real roots other than \(a = b = c\), then  we’ve shown that the determinant can’t be zero. There are again two cases to check here: that \(a\), \(b\), \(c\) all have the same sign, and that \(a\), \(b\), and \(c\) have two of the same sign and one different. I will do that latter case first.

In the latter case, without loss of generality I will assume that \(c \ge 0\), and that \(a \le 0\) and \(b \le 0\), and I will treat this as a polynomial in \(c\). We also know that \(c + (b+a)\) is nonzero, which means that we can divide this polynomial by \(c + (b+a)\) without worrying that we are going to lose a root. So let’s go to this polynomial long division:

\[ \begin{array}{r|rrrr}          & c^2   & - (b+a)c     & + ((b+a)^2 - 3ab)  & \cr \hline c + (b+a) & c^3   & + 0c^2       &-3abc               & +(b^3 + a^3) \cr          & -(c^3 & + (b+a)c^2)  \cr \hline          &       & - (b+a)c^2   &-3abc \cr          &       &  -(-(b+a)c^2 & -(b+a)^2c) \cr \hline          &       &              & ((b+a)^2 - 3ab)c   & + (b^3 + a^3) \cr          &       &              & -(((b+a)^2 - 3ab)c & + (b+a)^3 - 3ab(b+a)) \cr \hline          &       &              &                    & 0 \end{array} \]

because \((a+b)^3\) breaks up into \(a^3 + b^3 + 3ab(a+b)\). So the only roots of this polynomial are the roots of this quadratic, which is \(c^2 -(a+b)c + (b+a)^2-3ab\). However, this is the case where \(c \ge 0\), \(a \le 0\), and \(b \le 0\). If \(a \le 0\) and \(b \le 0\), then \(ab \ge 0\), so \((b+a)^2 - 3ab = (b+a)^2 - 4ab + ab\), and this rearranges to \((b-a)^2 + ab\), which is nonnegative. This means that this quadratic is always nonnegative, and only has a root if \(a = b = c = 0\). However, we know that \(a + b + c \neq 0\), so we can rule that case out too. So this polynomial can’t have any real roots, because the only candidates for real roots are \(a + b + c = 0\), which we know is impossible. Note that \(a + b + c\) is a factor of this polynomial because when we divided we got zero remainder, but again we don’t have to worry about that because it’s nonzero.

This covers the case where one of \(a\), \(b\), or \(c\) has a different sign from the others. If \(a\), \(b\), and \(c\) all have the same sign, then without loss of generality, we can assume that \(a,b,c \ge 0\). But if \(a,b,c \ge 0\), then we know that \[ a^3 + b^3 + c^3 - 3abc \ge 0 \] with equality if and only if \(a = b = c\)! We know this because of AM/GM inequality, or that that that the arithmetic mean of any number of nonnegative real numbers is always greater than or equal to their geometric mean, with equality if and only if they’re all equal. The arithmetic mean of \(a^3\), \(b^3\), and \(c^3\) is \((a^3 + b^3 + c^3)/3\), and their geometric mean is \((a^3 b^3 c^3)^{1/3}\), which morphs into \(a^3 + b^3 + c^3 \ge 3abc\), or that \(a^3 + b^3 + c^3 - 3abc \ge 0\), with equality if and only if \(a = b = c\). We know that we’re not in that case, so that means \(a^3 + b^3 + c^3 -3abc \neq 0\).

Now that we’ve proven that the determinant of this matrix is nonzero, we know that the matrix is invertible. That means \(d = e = f = 1/(a+b+c)\) is a unique solution to our matrix equation, which means that either \(a = b = c\) or \(d = e = f\). If \(a = b = c\) then \(ax^2 + bx + c = a(x^2 + x + 1)\) and if \(d = e = f\) then \( dx^2 + ex + f = d(x^2 + x + 1)\). In either case, \(x^2 + x + 1\) divides one of the two of them, which we proved by assuming it divided their product. This means that \(x^2 + x + 1\) is prime in the ring \(\mathbb{R}[x]/(x^3 - 1)\), and we have succeeded at our glorious rendition of our purposely overcomplicated counterexample to “prime always implies irreducible.” Q.E.F.F.D.P. (Quod Erat FF Demonstrandum Potato) \(\Box\)

[thebombzen]

Prime and Irreducible, The Hard Way: Part 1

This is a LaTeX-enabled post. For best viewing, use a browser and view this on my blog, not a mobile device or your dash. Difficulty: \(({*}{*})\) This post is marked as a Double Star. Prerequisites: It’s best if you know what a group is (even if you don’t know anything about them), and knowing the definition of a ring is helpful but not required. This is going to be a cute, simple exercise in a bit of abstract algebra. Just kidding, it’s a hideously overcomplicated monostrosity-of-a-proof that will take us two parts to complete for no reason other than because I want to, and because you want to as well. We’re going to be looking at Rings, and cases where they are not nice. These rings are actually very rude and will do things like try to mod you out of a discussion, and then scream “divide by zero” when you still seem to be doing fine. If that joke made any sense to you, then you’ve got the necessary background knowledge and an awful sense of humor. Here’s another one: A module is a marriage. That is, a group adjoined with a ring. I believe this is the point where you tell me, “Leave. Just… leave.”

Recall from the last time you heard the definition of a ring that a ring is an Abelian group (that is, commutative group) with multiplication added, for some sufficiently nice way to do multiplication. In this case, multiplication is sufficiently nice if it’s associative and distributes over addition. As usual, mathematicians don’t care if multiplication is commutative, bewildering everyone except other mathematicians. We understand perfectly well why we scream and cry when addition doesn’t commute but with multiplication we say, “eh, okay.” You won’t actually have to worry about that, because all the rings in this post will have commutative multiplication.

It’s also worth noting that rings don’t technically have to have multiplicative identies. But if you like using rings without a multiplicative identity then you are silly and you should feel bad, and you should problably ponder your life decisions that led you to this point and see if you could change anything for the better. That being said, for the rest of this post, rings have multiplicative identities. (That is the number one!)

And now for some terminology! (Hey, this post is rated \(({*}{*})\), and not \(({*}{*}{*})\), so I’m going to define just about everything I use here.) An element of a ring is a unit iff it has a multiplicative inverse. An element of a ring is irreducible iff it is not a unit and whenever it’s factored into two things, one of them must be a unit. An element \(p \in R\) is prime iff it is not a unit and whenever \(p | ab\), that implies that \(p | a\) or \(p | b\).

A ring is an integral domain if it has the zero-product property. In other words, whenever \(ab = 0\), then either \(a = 0\) or \(b = 0\). A ring is also an integral domain if it has cancellation. That is if \(c \neq 0\) then \(ca = cb \implies \not\!ca=\not\!cb \implies a=b\). These two properties are equivalent, and I don’t really feel like explaining why. Do it yourself. Doing math yourself builds character, you know. It’s good for your existential body mass. (Hint: consider \(a-b\)).

A very important fact about integral domains is that all prime elements are irreducible. Furthermore, if an integral domain \(R\) has unique factorization, then irreducible elements are also prime. By Unique Factorization, I mean that there’s only one way to factor elements into irreducibles. (The Fundamental Theroem of Arithmetic states that the ring of integers has unique factorization.) These are facts that I will not prove because I am lazy. They’re also not what I’m getting at and if you are just dreaming to see proofs of these facts then JUST DO IT. DON’T LET YOUR DREAMS BE DREAMS. DO IT!

What I will do is screw around with everything that is not related to the above. Because all primes are irreducible in an integral domain, being prime is somehow more of a big deal that being irreducible. Except when it’s not. What if we were to take a ring that wasn’t an integral domain? That is, what if there were nonzero elements that multiplied to give zero? Could we get a prime element that’s not irreducible?

Yes, and that is what I am going to prove today. Let’s consider the ring \(\mathbb{Z}/6\mathbb{Z}\), or the ring of integers in mod \(6\) arithmetic. Note that \(2 \neq 0\) and \(3 \neq 0\), but \(2 \times 3 = 0\) (mod \(6\)), so we have zero divisors. Also, note that \(2\) does not have a mulitplicative inverse because \(2\) times any number is even, so it can’t be \(1\). The number \(4\) doesn’t have a multiplicative inverse for the same reason, so neither of them are units. Also, \(2 \times 4 = 8 = 2\), so \(2\) factors into \(4 \times 2\) and neither of those factors are units. However \(2\) is prime because if \(2 | n\) then \(n\) must be even (even in mod \(6\)), but the product of two odd numbers is odd (even in mod \(6\)), so if \(2 | a b\) then either \(a\) or \(b\) must be even. So in the ring of integers mod \(6\), the number \(2\) is prime but not irreducible.  

So we’re done. QED. But I know that’s not why you’re reading this. You’re not reading this so you could get more than six (more than SIX! WOW!) paragraphs of background knowledge and then get a one-paragraph proof of the punch line. You’re reading this because this is my blog and on this blog we do things in the most convoluted way possible. (We know there is a maximally convoluted method because of Zorn’s Lemma.) A simple explanation of “prime does not imply irreducible outside a domain” is not what you signed up for so it’s not what you’re going to get. Well okay, you did just get one, but screw it, let’s do this the hard way.

Let’s consider the ring \(\mathbb{R}[x] / (x^3 - 1)\). This is ring of polynomials in \(x\) with real coefficients, but modded out by the equivlence relation where \(x^3 - 1\) is equivalent to \(0\), or that \(x^3 = 1\). Here, \(x\) is a free variable, which means that it’s a standalone algebraic object that doesn’t have any kind of numerical value. We never plug something in for \(x\), it is just this atomic thing that sits around in our expressions and makes us feel like we’re doing actual algebra instead of just number theory. Also, if we multiply the polynomial \(x - 1\) by \(x^2 + x + 1\) then we get \(x^3 - 1\), which is just zero. That means that this ring is not a domain.

In this ring, the polynomial \(x^2 + x + 1\) actually has a very special property that if we multiply any element \(ax^2 + bx + c\) by \(x^2 + x + 1\), we get \(ax^4 + bx^3 + cx^2 + ax^3 + bx^2 + cx + ax^2 + bx + c\), which simplifies to \((a + b + c)(x^2 + x + 1)\) when we replace each \(x^3 \mapsto 1\) and each \(x^4 \mapsto x\). Also, I did write down a generic polynomial in terms of \(x^2\), \(x\), and \(1\) only, because any term of degree at least three can be collapsed by treating \(x^3\) as \(1\), because in this ring \(x^3 = 1\) is a fact. Because of this collapsation property, multiplying by \(x^2 + x + 1\) crushes everything into itself, and thus can’t have a multiplicative inverse. If you’re an algebraist you’ll recognize that \(x^2 + x + 1\) generates an ideal, which I will not define because you know what it means already. If you didn’t recognize this fact then you can ask one of the algebraists for a more rigorous explanation of why \(x^2 + x + 1\) doesn’t have a multiplicative inverse, but for now, the “crushing” explanation will do.

Because of this special property, we know that \(x^2 + x + 1\) factors into \((x^2 + x + 1) \times (\frac{1}{3}x^2 + \frac{1}{3}x + \frac{1}{3})\) (remember that the coefficients are real numbers), and neither of these terms are units, so \(x^2 + x + 1\) is not irreducible in our ring \(\mathbb{R}[x] / (x^3 - 1)\).

I claim that even though  \(x^2 + x + 1\) is not irreducible in our ring, it is prime. That means, whenever \((x^2 + x + 1) | ab\), it means either \((x^2 + x + 1) | a\), or \(( x^2 + x + 1) | b\). The rest of this post will be dedicated to proving that  \(x^2 + x + 1\) is prime in \(\mathbb{R}[x] / (x^3 - 1)\). It will be glorious and the victory will be celebrated by our ancestors for generations, as soon as we invent a time machine.

End Part 1. To be continued in Part 2, but you knew that.  Who the heck calls something Part 1 and doesn’t have any plans to continue it? (Other than Dream Theater, that is.) But now in this sentence, let’s actually end Part 1.

[thebombzen]

Ordinal Slot Machines

This is a LaTeX-enabled post. For best viewing, use a browser and view this on my blog, not a mobile device or your dash. Difficulty: \(({*}{*}{*})\) This post is marked as a Triple Star. Prerequisites: Ordinal numbers and elementary set theory are marked as prerequisites for this post. If you know very little about these topics then be warned that almost none of this will make any sense to you. I will make a \(({*}{*})\) Double Star post about ordinals and hydras sometime soon, and that should cover most of it. I use the notation \(f[x]\) and \(f^{-1}[x]\) for the induced image and preimage functions, respectively.

An Ordinal Slot Machine\(^\mathrm{TM}\) is simply one slot machine for every ordinal number \(\alpha \le \omega_1\). (Remember, \(\omega_1\) is the first uncountable ordinal.) Except these slot machines are special: whenever you put in a coin, you always win. You always get out two coins. So you go to the zeroth slot machine and put in one coin, and receive two. And then it occurs to you how awesome this is so you keep going. And for every ordinal \(\alpha \le \omega_1\), you put in a coin that you’ve received but haven’t spent yet, and it spits out two coins. And then when you get to \(\omega_1\), you realize that you’ve run out of money.

Wait, what? That’s correct. When you get to \(\omega_1\), despite having won every time for the past uncountably many games, you can’t help but notice that you’re out of money. (Noticing you’re out of money is pretty easy though, to be honest.)  “How is this possible?” you ask as you scratch your gray-haired head in confusion. (Well, you did play slots for a long time, did you not?) Then, you look down and realize that despite having played so many winning slots, you have nonetheless spent every coin you have ever earned on the way to \(\omega_1\), and that means you’re left with nothing. Oops.

So then you try again, but this time you’re extra smart to save away some of your earnings and be very conservative about how you go about spending your money. For each natural number \(n \in \omega\), you play the \(n\)th slot machine, get two coins, put the first coin you win into the next machine, and then stash away the second coin. But when you hit \(\omega\), you’ve spent all of the “first” coins so you need to play the \(\omega\)th slot machine with one coin from your reserves. (This is fine, because you’ll generate \(\omega\) more this time around.) So you get very careful and then you arrive at \(\omega_1\) again, and this time, well…, you look down, and you’ve still run out of money. You then punch a wall when you realize you’re broke, but that makes your hand broke as well. That wasn’t smart.

You pull out your pencil in your equally useful ambidextrous hand that isn’t broken and start to jot down notes, and think that you might always run out of money. But how could this be? How could it be that no matter how you do it, you’ve spent every coin you’ve ever earned?

Well, here’s how. Let’s take an arbitrary function \(f: \omega_1 \backslash \{0\} \rightarrow \omega_1\) with this property: \(\forall\alpha\) with \(0 < \alpha < \omega_1\), \(f(\alpha) < \alpha\). This function, in our slot machine example, will be the particular function that maps each ordinal \(0 < \alpha < \omega_1\) slot machine to the ordinal that gave you the coin that you needed to play it. So if the coin you used to play the slot machine at \(\omega^2\) originally came from the slot machine at \(\omega+5\), then \(f(\omega^2) = \omega+5\). If we can show that some ordinal \(\alpha\) has a preimage \(f^{-1}[\{\alpha\}]\) with cardinality greater than two, no matter which \(f\) we chose, then that means it’s impossible to find a function of this form that behaves like the slot machines. That is, at some point before \(\omega_1\), you will have to cheat and reuse a coin that you’ve already spent if you want to keep going. In other words, if you’re not a dirty cheating cheater who cheats, you’ll run out of money.

So let’s get to it. Take an arbitrary function \(f: \omega_1 \backslash \{0\} \rightarrow \omega_1\) with \(\forall \alpha\), \(f(\alpha) < \alpha\). We’re actually going to prove that some point has an uncountable preimage, which suffices to show that some point has a preimage of cardinality greater than two. Suppose for the sake of contradiction that \(\omega_1\) has no points with an uncountable preimage.

I’m going to define a new function of an ordinal \(\alpha\) to be the ordinal \[ c(\alpha) = \sup \{x \le \omega_1 : f(x) < \alpha\} + 1 \] That is, if you take everything that maps somewhere less than alpha, this gives you something greater than all of those. Note that because \(f(\alpha) < \alpha\), we have that \(c(\alpha) \ge \alpha + 1\), so \(c(\alpha) > \alpha\).

A very important fact to note right here is that \(c(\alpha) < \omega_1\), as long as \(\alpha < \omega_1\). We know this because of our assumption for contradiction, that every point has an countable preimage. If every singleton \(\{\alpha\}\) has a countable preimage \(f^{-1}[\{\alpha\}]\), then the preimage \(f^{-1}[\alpha] = f^{-1}[0 \le x < \alpha]\) must be countable as well, simply because \(\alpha\) is countable, making it a countable union of the countable preimages. If there are countably many things that map to something less than \(\alpha\), then \(c(\alpha)\) must be countable and thus \(c(\alpha) < \omega_1\).

Now, I’ll define \(c^n(\alpha)\) for each natural number \(n \in \omega\), with \[ c^0(\alpha) = \alpha \] and \[ c^{n+1}(\alpha) = c(c^n(\alpha)) \] meaning \(c^n\) is just \(c\) nested \(n\) times, with \(c^{n+1}(\alpha) > c^n(\alpha)\). Now, define

\[ c^\omega(\alpha) = \sup\{c^n(\alpha) : n \in \omega\} \] We have that \(c^\omega(\alpha)\) is countable as long as \(\alpha < \omega_1\) because \(c^\omega(\alpha)\) is the countable union of the countable ordinals \(c^n(\alpha) : n \in \omega\).

But now, let’s consider the point \(f(c^\omega(0))\). \(c^\omega(0)\) is countable because \(0\) is countable (philisophical questions aside), so this makes sense. Furthermore, we have that \(f(c^\omega(0)) < c^\omega(0)\) (by our definition of \(f\)). Because we’ve defined \(c^\omega\) to be the union of \(c^n\), \(f(c^\omega(0)) < c^\omega(0)\) simply means that \(f(c^\omega(0)) < c^n(0)\) for some \(n \in \omega\). But if \(f(x) < c^n(0)\), then \(x < c(c^n(0))\) by our definition of \(c\), so we have that \(c^\omega(0) < c^{n+1}(0)\).

But wait! We’ve proven that \(c^\omega(0) < c^{n+1}(0)\), but \(c^{n+1}(0) \le c^\omega(0)\) by the definition of \(c^\omega\). Oops. That looks like a contradiction to me. Can we get a Q.E.D. baked potato-filled snackbox box box? No, it looks like an ordinary box will do. \(\Box\)