The Lumber Room

"Consign them to dust and damp by way of preserving them"

Archive for November 2008

A “Möbius” inversion formula

leave a comment »

[Not the Möbius inversion formula, but something similar.]
As usual, define the Möbius function μ on the natural numbers as
\mu(n) = \begin{cases}0 \text{ if n is not square free,}\\ -1\text{ if n is squarefree with an odd number of prime factors,}\\ 1\text{ if n is squarefree with an even number of prime factors.}\\\end{cases}
Let f be any function defined on the natural numbers, and let F be the function defined as \displaystyle F(n) = \sum_{j=1}^{n}{f(\left\lfloor{n/j}\right\rfloor)}.
Then it is true that \displaystyle f(n) = \sum_{k=1}^{n}{\mu(k)F(\left\lfloor{n/k}\right\rfloor)}.

Note that f need not be multiplicative; it can be any arbitrarily defined function. I have no idea why it is true. Help?

Written by S

Fri, 2008-11-28 at 18:55:44 +05:30

Posted in Uncategorized

Tagged with , ,

Asimov on ‘The Last Question’

leave a comment »

I like tracking down quotes, but find it terribly hard to track down quotes by Asimov about his writing: there are so many anthologies, and so many comments he has made about a single story in different places. Here, for example, are two comments I remember having read about what is definitely one of his two most famous stories, The Last Question:

  • The first was easier to track down; it’s on Wikipedia with a date. In The Best of Isaac Asimov, published in 1973, he says:

    ‘The Last Question’ is my personal favorite, the one story I made sure would not be omitted from this collection.
    Why is it my favorite? For one thing I got the idea all at once and didn’t have to fiddle with it; and I wrote it in white-heat and scarcely had to change a word. This sort of thing endears any story to any writer.
    Then, too, it has had the strangest effect on my readers. Frequently someone writes to ask me if I can write them the name of a story, which they think I may have written, and tell them where to find it. They don’t remember the title but when they describe the story it is invariably ‘The Last Question’. This has reached the point where I recently received a long-distance phone call from a desperate man who began, ‘Dr. Asimov, there’s a story I think you wrote, whose title I can’t remember–‘ at which point I interrupted to tell him it was ‘The Last Question’ and when I described the plot it proved to be indeed the story he was after. I left him convinced I could read minds at a distance of a thousand miles.
    No other story I have written has anything like this effect on my readers—producing at once an unshakeable memory of the plot and an unshakeable forgettery of the title and even author. I think it may be that the story fills them so frighteningly full, that they can retain none of the side-issues.

  • Read the rest of this entry »

Written by S

Fri, 2008-11-28 at 06:47:42 +05:30

Posted in Uncategorized

Fermat’s last theorem

leave a comment »

Fermat’s last theorem has a long and exciting history. Which everyone knows, so I’ll not mention it here.1 What I suddenly find to be remarkable though, is the very first event. The fact that Fermat scribbled it in a margin of Diophantus’s Arithmetica. That Pierre de Fermat, in France in 1637, was reading an ancient book written by a Greek in the 3rd century. That he was reading it in such a manner that the book’s asking how to split a square into two squares should impel him to not only investigate the question of how to split a nth power into two nth powers, for all n, but to also do it until he believed he had a truly marvelous proof.

When was the last time you made margin notes in a book?


Off topic: The book only answers the question for 16(=4²). Wikipedia has pictures of the relevant page for a 1621 edition, and the 1670 edition that contains Fermat’s notes. (Fermat died in 1665.) I’m not sure I’ve deciphered the Latin correctly (the Greek is right out), but what it says is the following.
[BTW, in case you have been thinking so far and have the objection that 16 cannot be written as the sum of two squares, I should point that for Diophantus, "number" apparently meant "positive rational number", there were no other kinds of numbers. Negative and irrational numbers were "useless", "meaningless", and "absurd".]
Suppose one of the two squares that add up to 16 is Q=N². ["Q" because it is a square, "quadratum".] The other square is 16-Q. If the other square is (2N-4)²=4Q+16-16N, [um, why should it be?] then we get 16-Q=4Q+16-16N so 5Q=16N, or N=16/5 and Q=N²=256/25 (which is misprinted as 256/52 in the 1670 edition), and the other square is 144/25, which add up to 400/25=16. So the (an) answer is that 16 = (16/5)² + (12/5)².
You might notice this is not really an answer; all that Diophantus has done is take 3²+4²=5² and multiplied it appropriately to make two “squares” add up to 16. We could do the same for any square, e.g. for 49=7², we could write (7×3)²+(7×4)²=(7×5)², then divide out by 5² to say (21/5)²+(28/5)²=49. For any x, we could take any a and b such that a²+b²=1 (e.g. 3/5 and 4/5) and write x²=(ax)²+(bx)².


1. I found today (2008-11-27) an anecdote. The setting is this: it was April 1994. Andrew Wiles had first announced his proof in June the previous year, and sent it off to a journal, but a hole had been found. It seemed at first it would take only a few hours, then weeks, to fix it, but months had dragged on without success. And on April 3 1994, Gian-Carlo Rota sent out an email announcing that Noam Elkies had found a counterexample to Fermat’s last theorem! So it seemed that the hole was unfixable after all. There was some disappointment all around before it was realised that the email was an April Fool’s joke, that had somehow got incorrectly dated :-) I found it on Wikibooks, but see Lance Fortnow’s blog post for the email.

Written by S

Fri, 2008-11-21 at 15:05:01 +05:30

Posted in Uncategorized

Tagged with , ,

Thank you for the music

with one comment

Just watched Mamma Mia! The Movie this week (twice!). It sucks, is completely ridiculous, Pierce Brosnan cannot sing to save his life, and there are far too many annoying characters, but because it’s ABBA, all is forgiven. Meryl Streep, perfect as always, appears to be having the time of her life, but maybe it’s just her acting. Some of it would have been better if they simply used “playback singing” the way only we in India seem used to, but it was mostly okay. Apparently there are even thoughts of a “sequel” (wouldn’t be the first time a movie with no plot has had a sequel, anyway), because “there are still plenty of ABBA songs left”.
Read the rest of this entry »

Written by S

Mon, 2008-11-10 at 07:01:58 +05:30

Posted in Uncategorized

Tagged with ,

Lattice points visible from the origin

with 15 comments

[A test of LaTeX-to-Wordpress conversion. Bugs remain, point them out. Original PDF]

Here is a problem I love. It is simple to state, and it has a solution that is not trivial, but is easy to understand. The solution also goes through some beautiful parts, so I can promise it’s worth reading :-)

[The solution is not mine. Also, the question is just an excuse for the ideas in the solution. :P]

Question. Suppose you are standing on an infinite grid in the plane. You can see infinitely in all directions, but you cannot see through grid points: a point is hidden from view if some other grid point lies in your line of sight. What fraction of the grid points can you see?

Let us first imagine that we are standing at the origin, and that the grid is that of the lattice (integer) points.

The blue points are visible; the grey points are not

The blue points are visible; the grey points are not


Read the rest of this entry »

Written by S

Fri, 2008-11-07 at 15:00:30 +05:30

Posted in public

Tagged with , ,

A timeline ends

with one comment

Sad news that was too easy to miss in the ongoing deluge: Michael Crichton passed away on Tuesday, at age 66. See my friend’s post.
Read the rest of this entry »

Written by S

Thu, 2008-11-06 at 07:08:52 +05:30

Posted in Uncategorized

Tagged with , ,

Follow

Get every new post delivered to your Inbox.

Join 75 other followers