Why does algebra work?

When I was in middle school, my teachers taught me the mechanics of algebra — try to isolate to variable by adding, subtracting, multiplying, and dividing both sides. And then in later years, my teachers expanded that toolbox to include stuff like logarithms and whatnot.

But I think that it’s easy to get lost in the details and overlook one crucial piece of logic. It’s the basis of all algebra, but it’s a kind of hidden fact that becomes important in more complicated problems.

Let’s say we have the equation $2x + 1 = 5$, and we’re trying to find all possible values of $x$.

By instinct, one might jump directly into subtracting $1$ from both sides and dividing both sides by $2$:

$$\begin{gather*}
2x + 1 = 5 \\
2x + 1 – 1 = 5 – 1 \\
2x = 4 \\
\frac{2x}{2} = \frac{4}{2} \\
x = 2 \\
\end{gather*}$$

But here’s why the algebra works: these clauses are linked by “if and only if”s.

$2x + 1$ equals $5$ if and only if $2x$ equals $4$, which is true if and only if $x = 2$. Therefore, we can conclude that $2x + 1 = 5$ if and only if $x = 2$.

One way to look at it is that we’re replacing the original equation with equivalent forms. $2x + 1 = 5$ says exactly the same information as $x = 2$, just written slightly differently. That’s really the whole idea of algebra (and logic) — replacing one statement with another exactly equivalent until it’s obvious what your result is.

That’s why, in general, it’s not a productive idea to multiply both sides by zero: $2x + 1 = 5$ is not exactly equivalent to $0 \cdot (2x + 1) = 0 \cdot 5$ because the latter is true no matter what $x$ is. Therefore, we’ve lost some information in multiplying by zero.

“If and only if” is abbreviated $\Leftrightarrow$, and I wish that I was taught algebra with that notation. It’d be easier to remember that $\sqrt{x^2} = 1$ is not exactly equivalent to $x = 1$ (it can be $-1$ too!) if I had that symbol to remind me.

January 31, 2013, 11:15am by Casey
Categories: Math | Permalink | 2 comments

How to download a Facebook album

A friend came to me, saying that he wanted to download a photo album off of Facebook. He said he had tried different solutions on the internet, but they didn’t work. I decided to help him out and hack together my own solution, and this is the end result.

The first thing I needed to do was to find the URLs of all the photos. I wrote this quick JavaScript snippet that does that. To get the URLs, I navigate to the page with the album, open the console (Ctrl-Shift-J in Chrome), and paste in this code:

console.log(Array.prototype.map.call(document.querySelectorAll('table.uiGrid.fbPhotosGrid a.uiMediaThumb'), function (a) {
    // The URL to the photo is within the 'ajaxify' attribute of each thumbnail link
    // Construct an 'a' element to parse the query string
    var b = document.createElement('a');
    b.href = a.getAttribute('ajaxify'); 
    
    var params = b.search.replace(/^\?/, '').split('&');
    for (var i = 0; i < params.length; i++)
        if (params[i].indexOf('src') == 0)
            return unescape(params[i].split('=')[1]);
    return '';
}).join('\n'));

I hit enter and get a list of URLs:

Now that I have the URLs, I pasted that in a file named urls. I made a directory named album and then wrote this simple PHP script that downloads the files and then compresses them into a ZIP file.

<?php

$fp = fopen('urls', 'r');

$i = 1;
while ($url = fgets($fp)) {
        file_put_contents("album/$i.jpg", file_get_contents($url));
        echo "Downloaded $i\n";
        $i++;
}

shell_exec('zip album.zip album/*');

And now, I have a file named album.zip with all the photos!

June 5, 2012, 12:13am by Casey
Categories: Programming | Permalink | 2 comments

Explanation of the Dirichlet function

My calculus teacher gave an example of a function that was discontinuous everywhere, the Dirichlet function. It indicates whether a number is rational or irrational:

$$D(x) = \begin{cases}1 & \text{ if } x \in \mathbb{Q} \\ 0 & \text{ otherwise }\end{cases}$$

That’s cool, but what’s even cooler is that there exists this expression for the Dirichlet function:
$$D(x) = \lim_{m \to \infty} \lim_{n \to \infty} [\cos(m! \pi x)]^{2n}$$

Unfortunately, neither Wikipedia nor Wolfram’s web site explains why this is equivalent to the Dirichlet function, so I spent a long time thinking about it. Here’s what I’ve come up with.

Let’s consider a simplified version first. Consider the function $f(x) = \cos^2\pi x$. It equals $1$ so long as $x$ is an integer, and a positive decimal less than $1$ otherwise. This is simple to see by graphing the function.

Now, if you exponentiate the result an infinite number of times — i.e., $\lim_{n \to \infty} f(x)^n$ — you end up with two outcomes. If $x$ is an integer, then $f(x) = 1$, and $f(x)$ exponentiated infinitely will still equal $1$. If $x$ is not an integer, then $f(x) < 1$ and will therefore get smaller after every exponentiation, eventually hitting $0$. That is to say, the limit will equal $0$ for non-integers. We've basically created an indicator function for integers: $$\operatorname{isInteger}(x) = \lim_{n \to \infty} (\cos\pi x)^{2n} = \begin{cases}1 & \text{ if } x \in \mathbb{Z} \\ 0 & \text{ otherwise }\end{cases}$$ Now we can rewrite the Dirichlet function in terms of this $\operatorname{isInteger}$ function: $$D(x) = \lim_{m \to \infty} \operatorname{isInteger}(m! x)$$ This is the especially cool part: we can show that if $x$ is rational, then $\lim_{m \to \infty} m! x$ is an integer. If we let $m$ approach $\infty$, then we have a product of all positive integers multiplied by the input $x$. If $x$ is rational, then $x$ can be written as a fraction of integers $\frac{p}{q}$ where $p$ and $q$ are integers. The $q$ will then cancel with one of the integers in the factorial, thus making the whole product $m! x$ an integer. In the other case — where $x$ is irrational — this won't happen, and $m!x$ will not be an integer. Visually, for rational numbers (because $x = \frac{p}{q}$): $$\lim_{m \to \infty} m! x = \lim_{m \to \infty} \frac{p}{\not{q}} \cdot (1 \cdots \not{q} \cdots m)$$

Now if we plug the either-integer-or-non-integer result into our $\operatorname{isInteger}$ function, what results is an indicator function for rationality — the Dirichlet function.

March 28, 2012, 2:05pm by Casey
Categories: Math | Permalink | 3 comments

Markov chain text generator

Back in December, I was learning about Markov chains in my linear algebra class, and I read on Wikipedia that they could be used to generate real-looking text from a bunch of source texts. Since I wanted to procrastinate on my college applications anyway, I decided to make my own text generator!

How it works is that it takes a source document and records the probability that certain words appear after each word. For example, if the sentence is “I think that I will think of the will that I wrote,” it would record that “I” is followed by “think” a third of the time, “will” a third of the time, and “wrote” a third of the time. “Think” is followed by “that” and “of” half of the time each, and “that” is followed by “I” a hundred percent of the time, etc.

Visually:

Markov chain diagram

Once the program records the probability, it can generate realistic-sounding texts. It’ll start with the root node (I) and follow random paths until it reaches a node that doesn’t go anywhere. For example, a text it might generate is: “I will think of the will that I will think that I wrote.” Obviously, it doesn’t sound perfect, but if you feed it more source text, it usually produces some pretty hilarious text.

Here’s the demo. Paste some source text into the first box, click Add, and repeat. Then, click Generate, and it should produce some Markov chain text! You can keep clicking Generate for new text. I’ve prepopulated the source textbox with some text about lions from Wikipedia, but feel free to try it with something else!

Sadly, the generator wasn’t able to produce a usable essay for my college applications.

Click here for the code.

March 26, 2012, 10:45pm by Casey
Categories: Programming | Tags: , | Permalink | Leave a comment

Minimum and maximum of two functions

Let’s say you want a function that outputs the smaller of two functions along its domain. It turns out that the expression for that function is this:
$$\operatorname{min}(f(x),\ g(x)) = \frac{f(x) + g(x) – |f(x) – g(x)|}{2}$$

For example, take $f(x) = x^2$ and $g(x) = x + 2$. Then,
$$\operatorname{min}(x^2,\ x + 2) = \frac{x^2 + x + 2 – |x^2 – (x + 2)|}{2}$$
whose graph looks like this:

As you can see, it takes on the shape of $f(x)$ (the parabola) when $f(x)$ is smaller and $g(x)$ (the linear part) when $g(x)$ is smaller.

This can be explained by splitting the fraction for the expression up:
$$\begin{align}
\operatorname{min}(f(x),\ g(x)) &= \frac{f(x) + g(x) – |f(x) – g(x)|}{2} \\
&= \frac{f(x) + g(x)}{2} – \frac{|f(x) – g(x)|}{2}
\end{align}$$

You can see that the first term in the split formula is the average of the two functions, and the second term is half the distance (absolute value) between the two functions. When you subtract half the distance between the two functions from the average of the two functions, you always get the smaller function.

What would happen if you add the distance between the two functions instead of subtracting? You get the greater of the two functions:
$$\operatorname{max}(f(x),\ g(x)) = \frac{f(x) + g(x) + |f(x) – g(x)|}{2}$$

I don’t remember where I found this, but it’s pretty awesome!

March 26, 2012, 2:58pm by Casey
Categories: Math | Permalink | 2 comments

← Older posts

Newer posts →