Archive

Posts Tagged ‘Math’

A plea for notational common sense

October 13th, 2009

Tradition can often be a retarding force in mathematics. Advancements in logic were held back by centuries due to a collective belief that Aristotle had it all figured out and there was nothing left to discover. Non-Euclidean geometry wasn’t seriously studied until the 1800s because no one could think of the parallel postulate being false.

We nowadays tend to recognize the dangers of blindly following tradition, yet in virtually all areas of mathematics we continue to adhere to notational lunacy, and pass it on to future generations starting as early as in junior high school.

This lunacy is so deeply ingrained in our minds that we see nothing wrong with the following expression:

\sin(f(x)^2)

Let’s decipher the above. We start with a number x, apply f, square the result, and finally apply sin. Yet how do we recover this order of operations from the symbols above? Starting at x in the middle we move left to f, right to the \bullet^2 , and far left to the sin.

Although we read and write left-to-right, and so naturally imagine time evolving in this direction, the notation f(x) (due to Euler) means the opposite: start with x, then apply f. Even worse is when we have an expression like f(g(h(x))). The very first operation is written on the very right, and the final operation is written on the very left, in complete contrast to how we normally think.

Worse still is that we do read some operations left-to-right, like raising to a power, and so we end up mentally zig-zagging across mathematical writing to even decipher mathematical expressions.

But worst of all is the following: when we write a function f:A\to B, A denotes the input domain, and B denotes the output domain: input on the left, output on the right. As we’d expect in a sane world. If we also have a function g:B\to C, this left-to-right notation suggests we should be able to follow the arrows (A to B to C) to compose f and g. Yet, of course, the composite is called gf rather than fg. When reading gf we are meant to mentally reverse the direction of the arrows, so that g:C\gets B and f:B\gets A, although we never write this way!

This is psychotic behaviour, and we should put a stop to it. I suggest we forget tradition, and instead succumb to notational common sense to write expressions like x.f.g rather than g(f(x)).

This may seem bizarre at first, but at least one group of scientists adopted this notation years ago. In object-oriented programming languages a mental shift is required, where one stops thinking that functions have certain inputs, and instead starts to see that inputs have certain functions. In doing so, the left-to-right notation becomes completely natural, and we would write deck.sort.pop to sort a deck of cards and remove the last one, rather than pop(sort(deck)) as we’d expect in the mathematicians’ ridiculous notation.

I believe that a notational shift would make all of our lives easier in the long run, but of course it will likely never happen. Just as negative charge will always correspond to an excess of electrons, Euler’s notation is an unfortunate convention that is simply known by too many people. As a result, already-difficult subjects like category theory are made even more maddening for silly reasons, and high school students have far more difficulty learning precalculus than they should.

Help us, Barack Obama, we need Change.

Uncategorized ,

Twenty questions, in the degenerate case when 20 = lg(n)

August 3rd, 2009

A new post at Computational Complexity asks the following question:

(Problem 1.) You are trying to determine a secret integer x between 1 and n inclusive, using only queries of the form “is x = a (mod b)?” for integers a and b of your choosing. How many queries are required to determine x in the worst case?

And more restrictively,

(Problem 2.) Same as above but you are only allowed to make queries where b is prime.

The comments section seems to reveal at least a partial solution, but these are fun problems, so at least give them a shot before reading the solution there (or here.) If you’d like the solution spoiled anyway, read on! Read more…

Uncategorized , ,

The Fresnel integral

July 29th, 2009

Here’s a deceptively simple-looking integral:

\int_0^{\infty} sin(x^2)dx.

At first glance, it’s not even obvious whether the above converges.

On the other hand, it is easy to see that \int_0^{\infty} sin(x)dx does not exist (at least not in in the traditional sense) and is analogous to the alternating sequence { 1, -1, 1, -1, … }. But what of squaring the x? The function sin(x^2) alternates between positive and negative as well, so one might be tempted to say that its integral also diverges.

But before jumping to conclusions, let’s take a look at its graph:

sin(x^2)

Read more…

Uncategorized

Circles covering squares and points

June 12th, 2009

The following question appeared in an issue of π in the Sky:

Show that given any 201 points inside a 10-by-10 square, there is a unit circle containing at least 3 of those points.

It is natural to ask, for what other number of points n does the above hold? And what is the smallest such n? Read more…

Uncategorized

Easy-peasy symbolic computation with Ruby

January 3rd, 2009

Ruby is a wonderful language, largely deserving of the fanaticism surrounding it. There are a number of ways you can exploit its syntax to write concise, beautiful code. For example, to shuffle an array…

deck.sort_by{ rand }

…or to pick out certain elements of one…

deck.find_all{ |card| card.suit == Clubs }

…or to seamlessly cache computations.

def average_earnings
  @average_earnings ||= some_lengthy_computation
end

(Above, the ||= operator acts analogously to the familiar += operator. So if the instance variable @average_earnings already has a non-nil value, it is returned without any further computation. If on the other hand it is nil, then some_lengthy_computation is performed, @average_earnings is set to it, and returned.)

In addition, there are also a number of ridiculously short applications written in it, including a web server in 70 lines of code, a message board application in 500 lines, and its slightly more verbose successor.

In addition to these, I present a proof of concept of my own: Mathematica and Maple-like symbolic differentiation in about a hundred lines of code.

Read more…

Uncategorized , , ,

Happy eighth day of Christmas!

January 1st, 2009

As we all celebrate another revolution around the sun and come halfway closer to Epiphany, let’s explore a holiday-themed math problem.

The number of gifts one receives at the end of the Twelve Days Of Christmas is ironically 364—a gift for each day of the year except Christmas itself.

But what about the inhabitants of Gaia-n, who celebrate not 12 but n days of Christmas?

On the first day, such an inhabitant receives 1 present; on the second day, 1 + 2; on the third, 1 + 2 + 3; etc. Then, thanks to a theorem by some clever little kid, we can write the number of gifts he receives on day k as T_k = k(k+1)/2, the kth triangular number, and thus the total number of presents he receives in all ndays as the sum of triangular numbers C_n = \sum_{k=1}^n T_k (where C is for Christmas.)

T3 + T4 is a square

A geometric argument easily shows that T_{k-1} + T_{k} = k^2, so (assuming n is even)

 C_n = \sum_{k=1}^{n/2} (2k)^2 = 4\sum_{k=1}^{n/2} k^2

which is four times a pyramid number! Substituting the closed expression for the sum and simplifying gives,

 C_n = n^3/6 + n^2/2 + n/3 = \frac{1}{6} n(n+1)(n+2).

We can easily verify that this expression also gives the correct answer when n is odd, and moreover  C_{12} = 12\cdot 13\cdot 14/2 = 364 as we hoped!

On other planets, inhabitants may celebrate a fraction of a number of days of Christmas, and they may wish to extend the expression  C_n to any real (or complex!) number, i.e.

 C(z) = \frac{1}{6} z(z+1)(z+2)

which we naturally call the Christmas polynomial.

We may also wonder how many gifts someone will receive who has relatives on each of the planets Gaia-1, Gaia-2, …, up to Gaia-n. That is, what is the value of the sum Z_n = \sum_{k=1}^n C_n?

Because we may write T_n = \binom{n+1}{2} and C_n = \binom{n+2}{3}, it is a reasonable guess that  Z_n = \binom{n+3}{4} . This indeed turns out to be the case, and so we may naturally define a generalized Christmas function

 \chi_{m,n} = \binom{n+m}{m+1}

(where χ is for Xmas.) This results in the sequences

 \chi_{0,n} = n
 \chi_{1,n} = T_n
 \chi_{2,n} = C_n

and so on, allowing us to calculate a great number of Christmas gift-giving scenarios.

Uncategorized ,