The “Mathematics Change Plan”

With various attempts to save money, my university has started issuing “change plans” for various disciplines and employment groups. Just this last week the administration has released a Mathematics Change Plan, a Nursing and Midwifery Change Plan, a Science Change Plan, and a Technical Staff Change Plan. My concern is with the Mathematics Change Plan, because it affects me more than the others.

I have rarely seen a document so specious, badly thought out, and based on such poor reasoning. All the change plans are based on the same template, the main differences between them being the numbers used to draw their conclusions. For mathematics, the main changes are to reduce staff by five: a full professor and a lecturer associated with the RGMIA research group, and three full time teaching staff (or equivalent) from the rest.

Now, there is no doubt that student numbers, and associated teaching hours have fallen over the past few years – but less so in Mathematics, with its service teaching to engineering, science, and education than in some other disciplines – and probably some changes are required. But the loss of five staff?

Let’s first look at the teaching hours. The document makes note of a change in total teaching hours from 2178 to 1944. That’s a loss of 234 hours. Given two 12 week semesters, and an average teaching load of 12 contact hours per week, that’s less than one full time staff member. Note that an original report (we’ve had two reports in the past year) counts the number of mathematics teaching staff at 10.4 (effectively 10, as the 0.4 counts for a staff member with no teaching), so if the change plan were to be implemented we would have five staff teaching 1944 hours. That works out, over 24 teaching weeks in the year, at 16.2 contact hours per week – an impossible work load for any academic with the hope of doing any research, planning or development.

One of the two reports recommends “disaggregating” mathematics and computer science – up until recently, we were all together in the School of Computer Science and Mathematics. Leaving aside the wisdom of this idea (which is quite lost on me) it is in practice almost impossible to achieve, as many teaching staff, such as myself, have taught into both disciplines. Over the past few years I’ve taught calculus, discrete mathematics, mathematical cryptography, digital image processing, network security, as well as supervising research students, mainly from our coursework Masters in Computer Science. So am I a mathematician or a computer scientist? I’ve avoided being pigeon-holed, and I’m not alone – many of my colleagues also teach as much computing as mathematics.

Student numbers. Because the disaggregation has not yet happened, it is very difficult to separate mathematics numbers from computer science. And in fact the biggest single drop in numbers (which the Change Plan notes) was in fact caused by a drop in numbers from the Comp Sci Masters program a few years ago. But this is a program which contains no mathematics! No report, or this Change Plan, has made the effort to go beyond total student numbers to numbers specific to individual disciplines.

RGMIA. This is not a formal Research Centre of the University, but rather an informal grouping of local and international academics (about 1300 of them) all with similar interests. A refereed journal is published, and the Chair of RGMIA is an internationally renowned scholar, with hundreds of papers and books to his credit. He was appointed as a research and teaching academic some years ago, and has built up RGMIA with his many international contacts, and by his own research excellence, obtaining nothing from the University aside from a lecturer to help run the Journal. How is he being repaid for his selfless dedication to the University? – by having his position being made redundant even while the Change Plan is officially still in draft status! Even though he himself, officially, is not being made redundant, his position is, which means that either he has to reapply for another position, or take a “voluntary departure” package. Either way, it’s shoddy treatment.

Equity. The University has had a mission to provide high quality post-secondary education to the Western suburbs of Melbourne. These are suburbs with a high proportion of blue-collar workers, and low socio-economic status, and the University, with its value-added programs, has always had many students from this area. In fact the University has the highest percentage of any Australian university of students who are the first in their family to attend university. The Mathematics staff have for many years worked diligently to provide multiple entry points into the university’s programs, as well as some highly regarded outreach programs, and some programs to upskill secondary school mathematics teachers. All these programs and good work will die if the Change Plan is to proceed.

The university seems bent on destroying mathematics as a valid, valued and valuable teaching and learning discipline, and in ruining the goodwill of its teaching staff, and engendering a spirit of disinterestedness and cynicism. Well, it’s doing an excellent job.


I’ve been doing some work on the number of hours taught over last few years, and looking very carefully at the staffing spreadsheets. Well, here are the actual numbers:

2006: 2388
2007: 2140
2008: 2340

So much for falling numbers! And owing to the funding cuts, three staff members who have retired during that time have not been replaced.

Fun with numerical integration

Numerical integration, or quadrature (to use the old-fashioned, but charming, term) is the business of finding approximate values to definite integrals; integrals which are either impossible to be computed analytically, or for which the antiderivative is too complex to be used. In the first category we might have

\int\sin(x+x^3)\,dx

At least, Wolfram|Alpha can’t compute this, so I assume it can’t be done analytically; and in the second category we might have

\int\sin(1+x^3)\,dx

for which the antiderivative is a horrific expression involving the incomplete gamma function.

In an elementary calculus course, students might be introduced to some very simple numerical techniques: the trapezoidal rule or Simpson’s rule, but unless the course is more specifically geared to numerical computations, not much further.

However, there are lots of different methods for numerical integration, some of which are great fun to play with.

Newton-Cotes integration

All these methods are based on one simple idea: sample the function values at equidistant points, find the interpolating polynomial through those points, and integrate the polynomial. Since polynomials are easy to integrate, this method is easy to apply. For example, let’s generate the fourth-order Newton-Cotes rule, which uses a quartic polynomial, and hence requires five points.

Using Maxima:

(%i1) load(interpol);
(%i2) pts:[[a,f1],[a+h,f2],[a+2*h,f3],[a+3*h,f4],[a+4*h,f5]];
(%i3) integrate(lagrange(pts),x,a,a+4*h);
(%i4) ratsimp(%);
(%o4) (14 f5 + 64 f4 + 24 f3 + 64 f2 + 14 f1) h/45

In other words,

\displaystyle{\begin{array}{rcl}\int_a^{a+4h}f(x)\,dx&\approx&\frac{2h}{45}(7f(a)+32f(a+h)+12f(a+2h)\\&&\qquad+32f(a+3h)+7f(a+4h))\end{array}}.

and this is known as Boole’s rule.

The trouble with single Newton-Cotes rules is that as the number of points get larger, the interpolating polynomial may develop more “wiggles” and the resulting integral approximation may get worse. For example, take the integral

\displaystyle\int^5_{-5}\frac{1}{1+x^2}\,dx

for which the exact value is

2\tan^{-1}{5}\approx 2.746801533890031

However, let’s try his with a tenth-order rule:

(%i5) f(x):=1/(1+x^2);
(%i6) pts:makelist([-5+n,f(-5+n)],n,0,10);
(%i7) integrate(lagrange(pts),x,-5,5),numer;
(%o7) 4.673300563481597

We can see why this is so poor by plotting the original function and its interpolant together (click on image to show full-sized image):

Runge phenomenon

For this reason, better results can be obtained by chopping the integral up into small segments, and applying a low order rule (say, Simpson’s) to each segment.

Newton-Cotes with adjustments

If you look up old texts, or search about on the web, you’ll find rules similar to the Newton-Cotes rules, but with much simpler coefficients.

For example, the sixth-order rule is

\displaystyle{\begin{array}{rcl}\int_a^{a+6h}f(x)\,dx&\approx&\frac{h}{140}(41f(a)+216f(a+h)+27f(a+2h)\\&&\qquad+272f(a+3h)+27f(a+4h)\\&&\qquad+216f(a+5h)+41f(a+6h))\end{array}}.

As you can see, the coefficients are already getting cumbersome.

One way of adjusting a Newton-Cotes formula is by adding some function differences. If we denote f(a+nh) by f_n these are defined as

\Delta f_n=f_{n+1}-f_n

and all higher differences can be obtained recursively for k\ge 1:

\Delta^{k+1} f_n=\Delta^kf_{n+1}-\Delta^kf_n.

It is not hard to show that

\Delta^kf_n=\sum_{p=0}^k(-1)^p{n\choose p}f_{n+p}

So, for example

\Delta^6f_0=f_6-6f_5+15f_4-20f_3+15f_2-6f_1+f_0.

The idea is that for most functions, differences tend to get smaller, so by adding some small multiple of a difference, we shouldn’t affect the formula too much, but we may simplify its coefficients. Let’s try this with the Newton-Cotes sixth-order rule, which for simplicity we shall integrate over the range [1,7]:

(%i8) [a,h]:[1,1];
(%i9) remfunction(f);
(%i10) pts:makelist([a+n*h,f(a+n*h)],n,0,6);
(%i11) integrate(lagrange(pts),x,1,7);
(%i12) nc6:ratsimp(%);

This just produces the sixth-order rule seen above. But now!

(%i13) d6:sum(binomial(6,k)*(-1)^k*f(a+k*h),k,0,6);
(%o13) f(7) - 6 f(6) + 15 f(5) - 20 f(4) + 15 f(3) - 6 f(2) + f(1)
(%i14) ratsimp(nc6+d6/140);
(%o14) (3 f(7) + 15 f(6) + 3 f(5) + 18 f(4) + 3 f(3) + 15 f(2) + 3 f(1))/10

This is Weddle’s rule; more commonly written as

\displaystyle{\begin{array}{rcl}\int_a^{a+6h}f(x)\,dx&\approx&\frac{3h}{10}(f(a)+5f(a+h)+f(a+2h)\\&&\qquad+6f(a+3h)+f(a+4h)\\&&\qquad+5f(a+5h)+f(a+6h))\end{array}}.

Notice how much simpler the coefficients are! Another rule, Hardy’s rule, can also be obtained by an adjustment:

(%i15) ratsimp(nc6-d6*9/700);
(%o15) (14 f(7) + 81 f(6) + 110 f(4) + 81 f(2) + 14 f(1))/50

or in integral form as

\displaystyle{\begin{array}{rcl}\int_a^{a+6h}f(x)\,dx&\approx&\frac{h}{50}(14f(a)+81f(a+h)+110(a+4h)\\&&\qquad+81f(a+5h)+14f(a+6h)\end{array}}.

Not only is this simpler than the sixth-order Newton-Cotes rule, but two of the coefficients have vanished.

Averaging different rules

You and your students can invent your own rules by taking some Newton-Cotes rules and forming weighted averages of them. For example, Simpson’s rule (the second order rule) over a difference of 2h is

\displaystyle{\int_a^{a+4h}f(x)\,dx=\frac{2h}{3}(f(a)+4f(a+2h)+f(a+4h))}.

If we, for example, take

\displaystyle{\frac{5}{3}N-\frac{2}{3}S}

where N is the fourth order Newton-Cotes rule, and S is the Simpson rule over 2h, we obtain

\displaystyle{\int_a^{a+4h}f(x)\,dx\approx\frac{2h}{9}(f(a)+8f(a+h)+8f(a+3h)+f(a+4h))}

which certainly has nice coefficients.

Such a formula may not in fact give very accurate results, but students are always excited to discover something “for themselves”, and inventing their own integration rules (and testing them), would be a fascinating exercise.

A weekend with Wolfram Alpha

I’ve spent a little time over the past weekend throwing various expressions at Wolfram Alpha, seeing what I can do with it, and what it can do for me. It certainly has some very fine aspects and can do some things extremely well. But I kept coming up against a wall – finding things I assumed it should be able to do, but can’t.

Mathematics

Given that Mathematica provides the computational engine to Wolfram Alpha, we would expect that its mathematical ability to be second to none. So I threw a few expressions at it: first an integral

\displaystyle{\int\frac{1}{\sqrt{1-x^3}}\,dx}

which I entered as

integrate 1/sqrt(1-x^3)

and which was answered immediately, with a handsome result involving elliptic functions. For free, I got a few plots as well.

Then a differential equation

\displaystyle{\frac{dy}{dx}=x^2+y^2, y(0)=1}

as

y'=x^2+y^2,y(0)=1

and which was identified as a Riccati equation, and solved precisely. I would have liked to find the series solution for this last equation, but I don’t know how to do this using W|Alpha.

For fun, I tried a large matrix expression, in particular to evaluate the weights of the Newton-Cotes fourth-order rule, by means of

\displaystyle{\left[\begin{array}{rrrrr}1&1&1&1&1\\1&2&3&4&5\\1&4&9&16&25\\1&8&27&64&125\\1&16&81&256&625\end{array}\right]^{-1}\left[\begin{array}{c}5-1\\(5^2-1)/2\\(5^3-1)/3\\(5^4-1)/4\\(5^5-1)/5\end{array}\right]}

as

(inv {{1,1,1,1,1},{1,2,3,4,5},{1,4,9,16,25},{1,8,27,64,125},{1,16,81,256,625}}).{{4},{(5^2-1)/2},{(5^3-1)/3},{(5^4-1)/4},{(5^5-1)/5}}

As a super-calculator, then, W|Alpha is completely and utterly wonderful, and in giving us lowly mortals a window into the computational and symbolic power of Mathematica, W|Alpha is a great service indeed.

I started getting some tetchiness when I attempted to experiment with some slightly more abstruse topics. I decided to try to find the primitive root of the next prime after one trillion:

primitive root next prime one trillion

The system choked on this. I found a result first by finding the prime

next prime one trillion

(which turned out to be 1000000000039), and then copying this into

primitive root 1000000000039

I then thought of calculating a few knot groups, starting with the knot group of the (5,2) torus knot. There seemed to be no way of doing this; certainly entering

5 2 torus

gives a lot of information about the knot (some nice plots, various associated polynomials), but not its group. Attempts to find other topological invariants (homotopy groups, homology groups) also ended in disappointment. I don’t know whether Mathematica can do this or not, but it seems that W|Alpha can’t, as yet. When I entered

knot group

I got a sheaf of information about a New York company. This was severely disappointing. I had hoped that from an engine based on mathematical software, “group” would be interpreted in its mathematical, algebraic sense, but apparently not.

There doesn’t seem to be a way of saving a result (with a variable) for use in a subsequent calculation. But you can always cut and paste. It seems then, that the amount of Mathematica knowledge and functionality released into W|Alpha is limited. And although it may be useful for quick results, it can no way take the place of a proper computer algebra system.

Geography

In quick order I found the distances between my home town of Melbourne, Australia, and other cities; each time accompanied with a map indicating the shortest route between them. However, my attempts to find the city furthest from Melbourne couldn’t be done:

furthest city from Melbourne

returned the standard error: “Wolfram|Alpha isn’t sure what to do with your input.” I tried with different words, but to no avail.

Life Sciences

I tried a few biological queries:

smallest mammal

obligingly returned some information about the Etruscan shrew (which is the smallest by weight), but nothing about Kitti’s Hog-Nosed Bat, which is in fact the smallest mammal by length. This seemed to be a lucky dip for me; lots of other queries came to nothing:

largest land mammal
longest jellyfish
heaviest snake

Interestingly, the query

largest snake

returned the reticulated python, which is the world’s longest snake, but in fact the largest snake (by bulk) is the anaconda. When I entered, for the infamous box jellyfish,

chironex fleckeri

I received its biological breakdown (kingdon, phylum, class, order etc), but not its common name, nor any pictures, nor any information about the animal’s behaviour.

Music

According to the instructions, you can enter the name of a song, and indeed

unchained melody

returned information about the song being released in July 1965 by The Righteous Brothers. However, a newer song

how to save a life

(by The Fray; one of my daughter’s favourite songs) returned nothing. Also, by what seems a weird oversight, W|Alpha knows nothing about classical music; the searches:

haffner serenade
eroica symphony
the marriage of figaro

all returned nothing. There’s no way of searching by Koechel numbers for Mozart works, or by BWV numbers for Bach’s works. W|Alpha does know a little about tuning, scales and intervals, but nothing about temperaments:

werkmeister 3

returned nothing.

Conclusions

So how good, then, is Wolfram Alpha? It is touted as a “knowledge engine” – its aims are quite different to Google’s – and it claims to be able to give answers to queries from many disciplines. I found it vaguely annoying, with occasional flashes of amazing brilliance (especially in its mathematics). Maybe as its database grows, and more “intelligence” is added to its system, I will indeed be able to find what city is furthest from Melbourne, or when the next total solar eclipse will be visible in Edinburgh, or what the knot group is for the (5,2) torus knot.

Simpson’s rule

The elementary Newton-Cotes rule of second order, Simpson’s Rule, is known to all undergraduate calculus students – it’s one of the simplest, and best, methods of numerical integration (if the function is not too bizarre), especially in its compound form. But what is the easiest way of introducing it? In trawling through webpages and books, I’ve seen a myriad of approaches: Lagrangian interpolation, general formulas for the weights, and so on.

My favourite approach, which uses as little prior knowledge as possible, starts with the premise that Simpson’s rule is obtained by sampling the function at three equidistant points, fitting a second-order polynomial through those points, and integrating this polynomial.

To make the work easy for ourselves, we start by assuming the three equidistant points are -1, 0 and 1. Then the integral of a second-degree polynomial over this interval is

\begin{array}{rcl}\int_{-1}^1ax^2+bx+c\,dx&=&\left[\frac{1}{3}ax^3+\frac{1}{2}bx^2+cx\right]_{x=-1}^1\\[4mm]&=&\left[\frac{1}{3}a+\frac{1}{2}b+c\right]-\left[\frac{1}{3}(-a)+\frac{1}{2}b-c\right]\\[4mm]&=&\frac{2}{3}a+2c\\[4mm]&=&\frac{1}{3}(2a+6c).\end{array}}

So, our three points are (-1,f(-1)), (0,f(0)), (1,f(1)), and so, evaluating ax^2+bx+c at the three x values produces:

\begin{array}{rcl}a+b+c&=&f(1)\\c&=&f(0)\\a-b+c&=&f(-1)\end{array}.

Then

2(a+c)=f(1)+f(-1)

so

\begin{array}{rcl}2a+6c&=&(2a+2c)+4c\\&=&f(1)+f(-1)+4f(0)\end{array}

which, from the integral computation above, produces

\frac{1}{3}(f(-1)+4f(0)+f(1))

as the rule we require.

Stirling numbers

From my perspective as a tertiary mathematics educator, Stirling numbers are the poor cousins of the binomial coefficients. In spite of their many and various applications, they would rarely make a mention in a general undergraduate syllabus, possibly only in a combinatorics subject, and maybe not even then.

Stirling numbers exist in two forms: numbers of the first kind, and of the second kind. They are very closely connected. Interestingly, there are several different definitions, depending on who you read, and on what computer algebra system you use. For example, Sage:

sage: stirling_number1(6,3)
225

But Maxima:

(%i1) stirling1(6,3);
(%o1) - 225

Maple also gives the number with a negative sign. So, is the value 225 or -225? Well, again, it depends on your definition. But first, some notation. Following Knuth (”Two notes on notation”, American Mathematical Monthly, Volume 99, Issue 5 (May 1992) pages 403 – 422; a copy of the \TeX source is available here), we write

\displaystyle{\left[{n\atop k}\right]}

for the Stirling numbers of the first kind, and

\displaystyle{\left\{{n\atop k}\right\}}

for the Stirling numbers of the second kind.

One definition of the Stirling numbers of the first kind is that they are the coefficients in the expansion of

x(x-1)(x-2)(x-3)\cdots(x-n+1)

So for n=5, for example, we have

x(x-1)(x-2)(x-3)(x-4)=x^5 - 10x^4 + 35x^3 - 50x^2 + 24x

and the numbers [1,-10, 35, -50, 24, 0] are the Stirling numbers of the first kind for n=5. That is, we can write

\displaystyle{x(x-1)(x-2)(x-3)\cdots(x-n+1)=\sum_{k=1}^n\left[{n\atop k}\right]x^k.}

The expression

x(x-1)(x-2)(x-3)\cdots(x-n+1)

is called a falling factorial, and is denoted (x)_n. Thus we have

\displaystyle{(x)_n=\sum_{k=1}^n\left[{n\atop k}\right]x^k.}

The Stirling numbers of the second kind may be defined by

\displaystyle{x^n=\sum_{k=1}^n\left\{{n\atop k}\right\}(x)_k.}

These two generating formulas have a nice dual relationship – in each one, the power (or falling factorial) is expressed in terms of the other, with Stirling numbers as coefficients. Using this definition, the Stirling numbers of the first kind alternate in sign.

Other writers and users of the Stirling numbers prefer all of them to be positive. For this definition we can use the rising factorial

(x)^n=x(x+1)(x+2)\cdots (x+n-1)

to generate Stirling numbers of the first kind. If all these numbers are positive, we have a simple combinatorial definition: the number

\displaystyle{\left[{n\atop k}\right]}

is the number of permutations of n numbers which can be expressed with exactly k cycles. For this reason Knuth recommends the number be spoken as “n cycle k”. Here are the 11 ways in which 4 numbers can be expressed as two cycles:


[1, 2, 3][4], [1, 3, 2][4], [1, 2, 4][3], [4, 2, 1][3],
[1, 3, 4][2], [4, 3, 1][2], [2, 3, 4][1], [4, 3, 2][1]
[1, 2][3, 4], [1, 3][2, 4], [1, 4][2, 3]

The Stirling numbers of the second kind also have a combinatorial interpretation:

\displaystyle{\left\{{n\atop k}\right\}}

is the number of ways a set of n elements can be partitioned into k subsets, and so the number can be spoken as “n subset k”. Here are the 15 ways in which a 5 element set can be split up into two subsets:


{1, 2, 3, 4}{5}, {1, 2, 3, 5}{4}, {1, 2, 4, 5}{3}
{1, 3, 4, 5}{2}, {2, 3, 4, 5}{1}, {1, 2, 3}{4, 5}
{1, 2, 4}{3, 5}, {1, 2, 5}{3, 4}, {1, 3, 4}{2 ,5}
{1, 3, 5}{2, 4}, {1, 4, 5}{2, 3}, {2, 3, 4}{1, 5}
{2, 3, 5}{1, 4}, {2, 4, 5}{1, 3}, {3, 4, 5}{1, 2}

With either the generating functions or the combinatorial interpretations the following recursions are easy to prove:

\displaystyle{\left[{n\atop k}\right]=(n-1)\left[{n-1\atop k}\right]+\left[{n-1\atop k-1}\right]},

\displaystyle{\left\{{n\atop k}\right\}=k\left\{{n-1\atop k}\right\}+\left\{{n-1\atop k-1}\right\}}.

Given the confusion between the exact definition of the Stirling numbers of the first kind, it should be noted that Stirling himself only used the numbers in positive form, and for him the numbers of the first kind (given as his “second table”) arose in conjunction with the summation of infinite series, so that, in modern notation:

\displaystyle{\frac{1}{z^m}=\sum_{k=m}^{\infty}\frac{\left[{k\atop m}\right]}{z(z+1)(z+2)\cdots (z+k)}}

Stirling doesn’t give the recurrences, nor the combinatorial interpretations.

One book which treats the Stirling numbers in considerable detail, and discusses many relationships between them, is Knuth et al’s Concrete Mathematics.

Big numbers

One of my children decided that we need a family points system, and wrote up a table on the whiteboard in our kitchen/dining area giving each child 1000 points, and each parent some number consisting of a 1 followed by zeros pretty much to the far right of the board. My eldest son then wrote a 10 to the bottom left of his 1000, thus giving himself

10^{1000}

points. I retaliated by putting a factorial sign after my large number, which my son responded to by putting a

\times 0

immediately after it. Then he wrote three factorial symbols after his number:

10^{1000}!!!

I split my number into two halves, put a one at the beginning of the second half and wrote:

A(100\ldots 00,100\ldots 00)

where A(m,n) is Ackermann’s function. I reckon I’ve won this round.

Big numbers seem to fascinate people; I’ve always had a delight in them. The main problem is providing a notation which allows one to express them. Merely writing out a number in full isn’t enough; we need some way of describing it. Thus, my son’s number

10^{1000}!!!

is perfectly well defined, but is very big indeed; there would be no way to write it out “in full”.

We need some method to generate large numbers, and we start with some elementary arithmetic operations. From slowest to fastest, these basic operations are

  1. The sucessor function s(x)=x+1.
  2. Addition x+y; this can be implemented by y successors of x.
  3. Multiplication xy; this can be implemented by y additions of x.
  4. Exponentiation x^y; this can be implemented by y multiplications of x.

Each operation is obtained by iterating the previous operation. There’s no reason to stop with exponentiation; it’s just that we need some new notation. Arrows to the rescue! Donald Knuth has devised an elegant notation which starts with exponentiation:

  1. x\uparrow y=x^y.
  2. x\uparrow\uparrow y=\underbrace{x\uparrow x\uparrow x\ldots x\uparrow x}_{y \mbox{ copies}}
  3. x\uparrow\uparrow\uparrow y=\underbrace{x\uparrow\uparrow x\uparrow\uparrow x\ldots x\uparrow\uparrow x}_{y \mbox{ copies }}

and so on. It is to be understood that for all these arrow expressions computation is performed from the right:

\begin{array}{lcl}3 \uparrow\uparrow 4&=&3\uparrow 3\uparrow 3\uparrow 3\\ &=&3\uparrow 3\uparrow 27\\ &=&3\uparrow 7625597484987\\ &=&3^{7625597484987}\end{array}

which is a biggish number. Far to big to write out, anyway.

In order to deal with lots of arrows, one suggestion has been to use a superscript, so that, for example

3 \uparrow^7 5=3\uparrow\uparrow\uparrow\uparrow\uparrow\uparrow\uparrow 5.

This arrow notation has had its greatest effect in describing what has been called “Graham’s number” from an article by Ron Graham and Bruce Rothschild in 1971: “Ramsey’s Theorem for n-Parameter Sets”, Trans. Amer. Math. Soc. 159, 257-292. A copy of this paper is available here. Here is the quote from the paper which includes the definition of this number:

Graham's number

Using Knuth’s arrow notation, this number can be obtained as follows:

  • Start with g_1=3\uparrow^4 3=3\uparrow\uparrow\uparrow\uparrow 3.
  • Define g_2=3 \uparrow^{g_1} 3.
  • In general, g_k=3 \uparrow^{g_{k-1}} 3.

The number we want: Graham’s upper bound, is G=g_{64}.

In a nice example of notational one-upmanship, John Conway has trumped Knuth by developing a chained arrow notation. In this notation numbers are described using arrows pointing to the right:

2\rightarrow 3\rightarrow 4\rightarrow 5\rightarrow 3.

Some idea of the efficiency of this notation for describing large numbers is that for Graham’s number:

3\rightarrow 3\rightarrow 64\rightarrow 2<G<3\rightarrow 3\rightarrow 65\rightarrow 2.

For learning more about large numbers, excellent pages are provided by Robert Munafo and Susan Stepney. From the latter comes the splendid quote: “Numbers go on for ever, but our notation does not.”

We finish with a little problem posed by Daniel J. Velleman, in “Exponential vs. Factorial”, Amer. Math. Monthly, October 2006. He asked for the largest number which can be expressed using only 5 symbols, and after a technical discussion of the relative rates of growth of exponential and factorial functions, came up with

9^9!!!

However, if we enlarge our symbols to include these new arrows, we might have

9\rightarrow 9\rightarrow 9=9\uparrow^9 9

or

9\uparrow\uparrow\uparrow 9.

The first is clearly larger (it has more up arrows), but in Knuth’s notation it uses only four symbols. So, how about:

9\uparrow^{9^9}9

It might not be Graham’s number, but it’s not too bad for only five symbols.


Having written the above, I discovered a nice article about big numbers here.

Online calculators

In my teaching I move around my university, giving classes in different locations, often to the same group of students. And often in a class I need to do a quick and dirty calculation – to demonstrate a computational point, or to work through an example or exercise. For this purpose I like to use a calculator, as the calculator paradigm is one with which all students are familiar. This is not the case with a computer algebra system.

My university has standardized on Microsoft Everything as its desktop of choice, so in all classes I have access to its Windows Calculator. In its current (XP) form, this has two modes: standard, and scientific:

Windows calculator - standard mode
Windows Calculator - scientific mode

In my classes, I always use scientific mode, so I have access to the trigonometric and exponential functions. However, bizarrely enough, there’s no square root key in scientific mode. To obtain square roots, you either have to raise your number to the power of 0.5, or use the key combination INV, x^2. Given that the x^2 key is redundant, as squaring can be done using x,= , the omission of a square root key seems unpardonable. The same omission seems to have continued into the new, “beefed up” calculator which will be bundled with Windows 7, as you can see here.

Given this, I thought it may be interesting to see if there are any good online calculators out there. Well, of course there are – lots in fact. Most however, don’t suit my purposes very well. Here is my wishlist for the perfect calculator:

  1. It must look like a hand-held calculator.
  2. Keyboard entry should be possible – I should be able to type in “sin(sqrt(pi/3+1))” and receive an answer.
  3. All the standard transcendental functions: trigonometric, hyperbolic and their inverses, exponential and logarithmic.
  4. Complex number arithmetic, and conversion between Cartesian and polar forms.
  5. Basic combinatorial functions: factorials, combinations and permutations.
  6. Basic number theory: modular arithmetic (including inverses), gcd.
  7. Some sort of “memory”, or method of defining variables.

Web2.0Calc

This fine calculator is available at http://web2.0calc.com/, and a screenshot of it is:

Web 2.0 Calc

This is very near the perfect calculator. It fulfils my wishlist, and provides much more besides: matrices, some statistical functions, and even some plotting and equation solving. However, there are a few glitches:

  • You can’t change the precision, even though this is supposed to be possible.
  • Even though you can enter “i^3” and receive -i, you don’t seem to be able to raise other complex numbers to integer powers. For example: “(2+5i)^2” returns nothing.
  • There doesn’t seem to be a way of calculating modular inverses. Even though the extended Euclidean algorithm is supposed to be implemented, it doesn’t seem to work

As you can see from the screenshot, your input and result is returned in LaTeX form above the calculator. This is nice, but not always useful. It seems that the LaTeX code is turned into an image, which is then resized if necessary to fit that space. This can result in an unreadably squashed or stretched image.

ecalc

This is a sort of “generic calculator”, whose website describes it as “The Best Online Calculator”:

ecalc

As you see, it does a good line in unit conversion. It does not have the breadth of web2.0calc, but what it does, it does well. For example, it can compute the quotient of two complex numbers, which web2.0calc doesn’t seem to be able to manage. It also can solve equations, and perform conversions between bases (binary, octal, decimal and hexadecimal). However, it provides no way of defining variables.

Encalc

This is a calculator which drops the key-mode entry completely for text entry only:

Encalc

You can find it at http://www.encalc.com/. Its website claims that its strength “lies in its ability handle units and dimensional analysis, to define variables and its large database of constants.” It is in fact a powerful scientific calculator, with a clean simple interface. However, there does not seem to be documentation available (there is a FAQ) so it is not easy to find out exactly what Encalc can and can’t do. It doesn’t seem to support hyperbolic functions, factorials, complex numbers, or number theory. I’d like this calculator greatly if these operations were supported, and if there was better documentation.

Instacalc

This is another calculator which has eschewed keys for text entry:

Instacalc

It’s available at http://instacalc.com/. It has been claimed to be one the “Top 10 Online Applications” at theresourced.com. Instacalc can be embedded in a web page, and its results shared with other users. It has borrowed some of its functionality from spreadsheets, and its ability to update calculations in real time is impressive. For example, suppose you have

a=30

in one cell, and

sin(a)

cos(a)+cos(a/3)+cos(a/5)

in two other cells. If you change the first cell to, for example

a=45

then the results of the other two cells will change automatically.

Documentation is available at http://instacalc.com/blog/.

Conclusions…

I think the perfect online calculator is yet to be produced, although web2.0calc and Instacalc are both in the right direction. Web2.0calc has the most impressive functionality – but not all of it works as it should – and Instacalc has one of the best interfaces.

Trigonometric addition formulas

A week ago, I was discussing with an elementary mathematics class for engineers, the trigonometric addition formulas:

\sin(x+y)=\sin(x)\cos(y)+\sin(y)\cos(x)

\sin(x-y)=\sin(x)\cos(y)-\sin(y)\cos(x)

\cos(x+y)=\cos(x)\cos(y)-\sin(x)\sin(y)

\cos(x-y)=\cos(x)\cos(y)+\sin(x)\sin(y)

I decided not to attempt to prove any of these; instead I gave a few simple examples to at least convince the class that they “worked”. But it left me wondering: is there an easy, natural proof, within the understanding of elementary mathematics students, and in particular students whose needs aren’t primarily mathematical?

We first observe that proving any one formula is enough, as any other formula can be obtained from it by use of the identities

\sin(-x)=-\sin(x)

\cos(-x)=\cos(x)

\cos(\frac{\pi}{2}-x)=\sin(x)

\sin(\frac{\pi}{2}-x)=\cos(x)

Let’s start with this figure, something similar to which can be found in many high school textbooks:

Diagram for naive proof of trigonometric addition formulas

In this figure X and Y are points on the unit circle, YB is perpendicular to OX, and AB is perpendicular to YC. Immediately we have

YB=\sin(y)

OB=\cos(y)

From these we have

CD=AB=\sin(y)\sin(x)

YA=\sin(y)\cos(x)

AC=BD=\cos(y)\sin(x)

OD=\cos(y)\cos(x)

Then

\sin(x+y)=YC=YA+AC=\sin(y)\cos(x)+\sin(y)\sin(x)

and

\cos(x+y)=OC=OD-CD=\cos(y)\cos(x)-\sin(y)\sin(x).

This proof is pretty naive – it seems vaguely convincing – but it is not at all clear how the proof works if x, y and x+y are not all acute angles. On the other hand, it is a proof you might use with some maths classes.

One standard proof involves the complex form of the exponential:

\cos(x+y)+i\sin(x+y)=\exp(i(x+y))

 =\exp(ix+iy)=\exp(ix)\exp(iy)

Thus:

\cos(x+y)+i\sin(x+y)=(\cos(x)+i\sin(x))(\cos(y)+i\sin(y)).

Multiplying the right hand side, and equating real and imaginary parts, produces the addition formulas for cos and sin. This proof is perfectly general, and convincing if you know and understand the complex form of the exponential, which my students currently don’t.

Here’s another simple proof involving vectors. Let

X=\langle\cos(x),\sin(x)\rangle

Y=\langle\cos(y),\sin(y)\rangle

The angle between these vectors is \cos(y-x) and by the well known formula for the dot product:

X\cdot Y=|X||Y|\cos(y-x)

Since the length of each vector is 1, this produces

\cos(y)\cos(x)+\sin(y)\sin(x)=\cos(y-x).

This proof can in fact be written without any recourse to vectors, by developing the cosine rule from scratch. Consider this diagram:

Diagram for proof of trigonometric addition formulas using vector methods

Here A is the foot of the perpendicular from OY to OX. We have immediately

YA^2+AX^2=XY^2

Since YA=\sin(y-x) and AX=1-\cos(y-x), the left hand side is

\sin^2(y-x)+1-2\cos(y-x)+\cos^2(y-x)=2-2\cos(y-x).

And the right hand side is

(\cos y-\cos x)^2+(\sin y-\sin x)^2=2-2\cos y\cos x-2\sin y\sin x.

Equating the left and right hand sides, and simplifying, produces

\cos(y-x)=\cos(y)\cos(x)+\sin(y)\sin(x).

REDUCE released as open source

I was told only a few days ago that the venerable computer algebra system REDUCE has been released as open source. This has to be a good thing – the more software released as open source the better for the mathematical and scientific communities. I don’t know much about REDUCE, although I looked at its Z-transform package a few years ago when I was trying to write something similar for Maxima.

From a glance through its bibliography, REDUCE seems to have found its natural home amongst physicists; I can’t find much in the way of references to its use in teaching (which is my interest). Its lead developer, Anthony Hearn, started writing REDUCE in the early 1960’s when he was trying to calculate Feynman diagrams by hand.

In the early to mid 1980’s when Maple and Mathematica were beginning to stretch their wings, Macsyma and REDUCE were the gold standards of computer algebra systems, and their symbolic capabilities were the standards by which others were (generally poorly) compared. I don’t know how the current version of REDUCE compares with current versions of other systems.

But – because it’s now open source, mathematicians can explore its workings, and either develop it further, or take its best bits and add them to other systems. There’s a nice introduction and discussion about REDUCE here.

And here is the original announcement on the newsgroup sci.math.symbolic.

Arch Linux – a distribution for enthusiasts

For some time now I’ve been meaning to upgrade the system on my old and trusty IBM Thinkpad T42. It’s had Suse 9.3 on it from pretty much when I bought it about four years ago, and as that particular Suse version is no longer supported, it was effectively unable to be upgraded. For example, I couldn’t compile some software, because my gcc was too old. And upgrading gcc would have been a right royal pain. Solution – scrap the lot (after an appropriate backup) and start afresh!

Originally I intended to install OpenSuse 11.0 – I’ve been using it on my desktop at work, and it seems fine. And it’s been getting good reviews. I even bought a copy of a computer magazine, whose monthly attached DVD contained an ISO file of OpenSuse 11.0, and I burnt it to disk. However, before doing the installation, I happen to read a few more reviews, and quite a few responses to the reviews lauded a distribution – hitherto unknown to me – called Arch Linux.

So, I started checking out Arch, and from what I read, became very impressed at the idea of it. I do need a fairly lean mean system – my laptop has only 512 Mb of RAM – and most of my work consists of scientific/numerical/symbolic programming, as well as vast amounts of LaTeX.

As a brief aside, my history as a linux user is this: I started with Slackware and kernel 0.99 – those were the days when Slackware was distributed on 1.44Mb 3 1/2″ floppies (remember them?), and getting it all working – especially X – took quite a bit of effort. My first distribution with a graphical installer was Mandrake (in pre Mandriva days), and I was hooked on the simplicity of its installation – put in the CD, boot, answer a few questions and hey presto! – a fully working Linux system with all the bells and whistles. After that I had a fling for a few years with Redhat, and for a while ran a system which was a sort of Redhat/Fedora hybrid. Then I discovered Suse, and I’ve been using that – first 9.3 both at home and at work, then 10.0 and more recently 11.0 at work.

Back to Arch. What impressed me about my reading was that here was a system designed to be simple from the ground up – you installed only what you needed – and which could be as lean and mean as you liked. It had no graphical installer, and required a fair bit of tinkering with configuration files. Well, I certainly didn’t mind the idea of that, so off I went to the website, grabbed the ftp installer ISO image (only about 150 Mb) and went for it.

The installation and beginners instructions are models of their kind – clear, simple, and highly effective.

First good point: The documentation for Arch Linux (at the website) is excellent.

I commandeered a family desktop for the day, so I could have access to the Arch website while performing the installation. In fact I could have managed without this, as all the installation instruction are provided in the form of text files on the installation disk. But, hey, it was nice to be able to refer to them in all their html-ed glory. There was one hiccup: a file was written unnecessarily, which meant that initially I couldn’t install any packages. A quick question to the forums solved that little issue and I was away.

Second good point: The user forums are full of well-behaved, helpful and encouraging people.

Arch Linux works on what’s called a “rolling release” model. Rather than releasing a new version every few months or years, Arch provides for continuous upgrading, using an excellent package management tool called “pacman“.

Third good point: Pacman is everything a package manager should be – even better, in my opinion, than apt-get. Right from the very earliest stages of the installation, the user is encouraged to upgrade (using pacman) to newer versions of the software than might have been on the installation medium. This ensures that the system, once installed, is as up-to-date as possible.

Much installation requires the user to edit some configuration files, of which

/etc/rc.conf

is the most important. However, this important file is both small and easy to understand – it contains a few useful lines providing such things as the network setup, the kernel modules to be loaded, and the daemons to be run. The developers, in their wisdom, provide the option of the user choosing either vi or nano as their editor of choice during installation. In spite of my long Linux and Unix history, I’ve never got comfortable with vi, and I was delighted to have an alternative.

Within a very short time I had a basic system (without X or wireless, but with wired internet) up and running. From there it was a simple matter of carefully reading through the documentation to get X running. This was in fact not entirely trivial – I’d saved my old

xorg.conf

file from my previous system, but the file has changed considerably over the years, and I couldn’t simply drop my old file in place. So I generated a new file (using command line tools), and edited a few things by hand, using my old file as a guide. I also got wireless going without too much trouble. This was a far cry from my initial installation of Suse 9.3, which as I recall involved downloading new kernel source code, compiling it with the modules I needed, and fiddling for about a day to get wireless working.

I also decided to forgo KDE or Gnome as desktop environments, and use Xfce instead. This is a simpler, leaner, environment, and aside from the minor niggle of not allowing different background images on different workspaces, I’m very happy with it. Arch also allows you to install plenty of other window managers.

As well as the repository of packages in the pacman database – these are all packages which have been decreed safe and appropriate for all users – there is a further repository of 13258 (at last count) packages in the ArchLinux User-community Repository (AUR). These are “use at your own risk” packages, provided by users for other users. There is a tool called yaourt (Yet AnOther User Repository Tool) which is designed to simplify the installation of material from the AUR.

My first test of the system was installing Sage. This required compiling a huge amount of source code – it took my little machine about six hours – and it went without any hitches whatsoever. I was delighted.

Arch Linux is generally described by users as not being suitable for “newbies” – and it’s true that some little experience goes a long way, as well as a willingness to get your hands a bit dirty. But from my use of it over the last few weeks, I do believe that this is a distribution which has done it right.