The Universe of Discourse

Google query roundup
Once again I am going to write up the interesting Google queries that my blog has attracted this month.

Probably the one I found most interesting was:

           1 if n + 1 are put inside n boxes, then at least one box
             will contain more than one ball. prove this principle by
             induction.

Another mathematical question that came up was:

           1 a collection of 2 billion points is completely enclosed
             by a circle.  does there exist a straight line having
             exactly 1 billion of these points on each side

What might happen in the middle is that you might have one billion minus n points on the left, and then suddenly the line intersects more than n points at once, so that the number of points on the left jumps up by a whole bunch, skipping right past one billion, instead of ticking up by one at a time. So what we really need is to ensure that this never happens. But that's no trouble. Taking the points two at a time, we can find the slope of the line that will pass through the two points. There are at most 499,999,999,500,000,000 such slopes. If we pick a line that has a slope different from one of these, then no matter where we put it, it cannot possibly intersect more than one of the points. Then as we slide the line from one side to the other, as above, the count of the number of points on the left never goes up by more than 1 at a time, and we win.

Another math query that did not come from Google is:

        Why can't there be a Heron's formula for an arbitrary quadrilateral

All three quadrilaterals have exactly the same edge lengths, but their areas are different, so there couldn't possibly be a formula to tell you the area from just the edge lengths.

The following query is a little puzzling:

           1 undecidable problems not in np

It might be that the querent was looking for decidable problems that are not in NP. Here the answer is more interesting. There are many possibilities, but surprisingly few known examples. The problem of determining whether there is any string that is matched by a given regex is known to require exponential time, if regular expressions are extended with a {2} notation so that a{2} is synonymous with aa. Normally, if someone asks you if there is any string that matches a regex, you can answer just by presenting such a string, and then the querent can check the answer by running the regex engine and checking (in polynomial time) that the string you have provided does indeed match.

But for regexes with the {2} notation, the string you would provide might have to be gigantic, so gigantic that it could not be checked efficiently. This is because one can build a relatively short regex that matches only enormous strings: a{2}{2}{2}{2}{2}{2}{2}{2}{2}{2}{2}{2}{2}{2}{2}{2}{2}{2}{2}{2} is only 61 characters long, and it does indeed match one string, but the string it matches is 1,048,576 characters long.

Many problems involving finding the good moves in certain games are known to be decidable and believed to not be in NP, but it isn't known for sure.

Many problems that involve counting things are known to be decidable but are believed to not be in NP. For example, consider the NP-complete problem discussed here, called X3C. X3C is in NP. If Sesame Workshop presents you with a list of episodes and a list of approved topics for dividing the episodes into groups of 3, and you come up with a purported solution, Sesame Workshop can quickly check whether you did it right, whether each segment of Elmo's World is on exactly one video, and whether all the videos are on the approved list.

But consider the related problem in which Sesame Workshop comes to you with the same episodes and the same list of approved combinations, and asks, not for a distribution of episodes onto videotapes, but a count of the number of possible distributions. You might come back with an answer, say 23,487, but Sesame Workshop has no way to check that this is in fact the right number. Nobody has been able to think of a way that they might do this, anyhow.

Such a problem is clearly decidable: enumerate all possible distributions of episodes onto videos, check each one to see if it satisfies Sesame Workshop's criteria, and increment a counter if so. It is clearly at least as hard as the NP-complete problem of determining whether there is any legal distribution, because if you can count the number of legal distributions, there is a legal distribution if and only if the count of legal distributions is not 0. But it may well be outside of NP, because seems quite plausible that there is no quick way to verify a purported count of solutions, short of generating, checking, and recounting all possible distributions.

This is on my mind anyway, because this month I got email from two separate people both asking me for examples of problems that were outside of NP but still decidable, one on March 18:

I was hoping to get some information on a problem that is considered np-hard but not in NP (other than halting problem).

I was visiting your website in search of problems that are NP-Hard but not NP-Complete which are decision problems, but not the halting problem.

Here's one that was surprising:

           1 wife site:plover.com

           1 mathematical solution for eliminating debt

        [18/Jan/2006:09:10:46 -0500] eliminate debt using linear math
        [08/Feb/2006:13:48:13 -0500] linear math system eliminate debt
        [08/Feb/2006:13:53:28 -0500] linear math system eliminate debt
        [25/Feb/2006:15:12:01 -0500] how to get out of debt using linear math
        [23/Apr/2006:10:32:18 -0400] Mathematical solution for eliminating debt
        [23/Apr/2006:10:33:43 -0400] Mathematical solution for eliminating debt

           1 which 2 fraction did archimedes add together to write 3/4

There are several algorithms for writing any fraction as a sum of fractions of the form 1/n. The greedy algorithm suffices. Say you want to write 2/5. This is bigger than 1/3 and smaller than 1/2, so write 2/5 = 1/3 + x. x is now 1/15 and we are done. Had x had a numerator larger than 1, we would have repeated the process.

The greedy algorithm produces an Egyptian fraction representation of any number, but does not always do so conveniently. For example, consider 19/20. The greedy algorithm finds 19/20 = 1/2 + 1/3 + 1/9 + 1/180. But 19/20 = 1/2 + 1/4 + 1/5, which is much more convenient. So the problem of finding good representations for various numbers was of some interest, and the Ahmes papyrus, one of the very oldest mathematical manuscripts known, devotes a large amount of space to the representations of various numbers of the form 2/n.

           1 why does pi appear in both circle area and circumference?

           1 the only two things in our universe starting with m & e

Buy The Cyberiad from Bookshop.org (with kickback) (without kickback)

"Never heard of it," said the machine.

"What? But it's only sodium. You know, the metal, the element..."

"Sodium starts with an s, and I work only in n."

"But in Latin it's natrium."

"Look, old boy," said the machine, "if I could do everything starting with n in every possible language, I'd be a Machine That Could Do Everything in the Whole Alphabet, since any item you care to mention undoubtedly starts with n in one foreign language or another. It's not that easy. I can't go beyond what you programmed. So no Sodium."

I think The Cyberiad is uproarious. It is easily the funniest book I have ever read. I laugh out out every time I read it.

The most amazing thing about it is that it was originally written in Polish. The translator, Michael Kandel, is a genius. I would not have dared to translate a Polish story about a machine that can make anything that begins with n. It is an obvious death trap. Eventually, the story is going to call for the machine to manufacture something like napad rabunkowy ("stickup") that begins with n in Polish but not in English. Perhaps the translator will get lucky and find a synonym that begins with n in English, but sooner or later his luck will run out.

I once met M. Kandel, and I asked him if it had been n in the original, or if it had been some other letter that was easy in Polish but impossible in English, like z, or even ł. No, he said it had indeed been n. He said that the only real difficulty he had was that Trurl asks the machine to make nauka ("science") and he had to settle for "nature".

(Incidentally, I put the word napad rabunkowy into the dictionary lookup at poltran.com and it told me angrily "PLEASE TYPE POLISH WORDS USING CAPITAL LETTERS ONLY!" Yeah, that's a good advertisement for your software.)

Buy Consciousness Explained from Bookshop.org (with kickback) (without kickback)

By the way, narghiles are like hookahs, and nankeens are trousers made of a certain kind of cotton cloth, also called nankeen.

The most intriguing query I got was:

           1 consciousness torus photon core

My favorite result from this query is unfortunately offline, available only from the Google cache:

The photon is actually composed of two tetrahedrons that are joined together, as we see in figure 4.6, and they then pass together through a cube that is only big enough to measure one of them at a time.

Also, I got 26 queries from people looking for the Indiana Pacers' cheerleaders, and 31 queries from people looking for examples of NP-complete problems.

This is article #100 on my blog.

[Other articles in category /google-roundup] permanent link

Google query roundup
A highly incomplete version of this month's Google query roundup appeared on the blog on Saturday by mistake. It's fixed now, but if you are reading this through an aggregator, the aggregator may not give you the chance to see the complete version.

The complete article is available here.

[Other articles in category /google-roundup] permanent link

Google query roundup
Once again I am going to write up the interesting Google queries that my blog has attracted this month. The blog is now about eleven weeks old and has had a meteoric rise. The theme of this month's Google query roundup will be the idea of authority on the web, and the attribution of authority by links.

Of the 32 million blogs that Technorati.com knows about, they consider The Universe of Discourse to be the 13th most-authoritative blog on the subject of mathematics. Okay, I can almost buy that, because I do know a fair amount about mathematics, a lot of people know that about me, and I can probably write more clearly and convincingly than most mathematics experts. But their same ranking process says that The Universe of Discourse is tied for 16th place as one of the most-authoritative blogs on the subject of physics. Considering that I know next to nothing about physics, this is rather sad. If I wrote an article explaining how spacetime was curved like an artichoke, and a thousand people linked to it because they enjoyed the spectacle of someone making a fool of himself in public, my blog would move up the list to fourth place.

Google rankings are similarly weird. My whole web site is considered authoritative in general, because of various articles I've written and projects I've hosted over the years. The way Google works is that each page has an absolute pagerank, and then you get the pages with greatest pagerank that contain your search terms. So if my relatively high-ranking pages happen to contain your search terms, that's what you get, even if that doesn't really make sense.

For example, a Google search for "baroque writing" turns up my blog post about it as hit #5, because my site has high pagerank, and the sites that are really about baroque writing have low pagerank. But the high pagerank of my pages is primarily because I also host a long-established and popular website about Perl, and lots of people have linked to it over the years. So Google recommends my thoughts about Baroque writing because I'm an authority on the Perl programming language. This is not obviously a good reason to recommend a page about Baroque writing.

Of course one can argue that it's unreasonable to expect Google to judge whether I know what I'm talking about or not. But there is a way that they could do it, at least in principle, that would make more sense. Instead of computing pageranks globally, and saying "well, Dominus's pages are generally well thought-of, so we'll recommend those pages whenever they might be relevant to the query", one could compute pageranks per subject. So suppose you first considered only those pages that mention Baroque writing, and discard all the others. Then you do the pagerank calculation to see which of these pages link to which others. You would find a much better pagerank for searches about Baroque writing. My page would have low rank, because it is linked to by few pages about Baroque writing, rather than the high rank it does have because it is linked to by many pages about Perl.

Strange authority

           1 ashley indiana pacemate
           4 "lindsay" indiana pacemate
           1 pacemate lindsay

Not-so-strange authority

Sometimes there are weird side effects. My authority on the puzzle about the banana and the rope and the monkey's mother also pulls in people looking for stuff that sounds similar, but probably isn't:

           1 "monkey rope" joke
           1 monkey & banana game source code
           1 monkeys holding up the moon
           1 steps on how to draw a monkey holding a banana
           1 how to draw a banana
           1 picture of a monkey holding a banana

Other matters

           2 smallest positive value with no leading zeros such that
             rotating it is the same as multiplying it by p/q + puzzle 

Oh, you wanted the smallest value with at least two digits? That's obviously 10.

Oh, you wanted the resulting number to have no leading zeroes either? Then it's obviously 11.

Oh, you wanted the resulting number to be different from the original one? Then it's obviously 12, because when you rotate it, you get 21, which the same as multiplying it by 21/12.

In fact, for any number, rotating it has the same effect as multiplying it by p/q for some p and q. Maybe the author wanted p and q specified in advance.

Islamic history and Arabic etymology

	   1 qamara
	  11 qamara
	   1 qamara arabic
	   2 qamara camera
	   3 qamara camera obscura
	   2 camera obscura qamara
	   1 ibn haitham qamara

There might have been some other queries of a similar nature. For example, this one probably is:

	   1 arabic saqq

	   1 saqq

	   3 etymology cheque
	   1 cheque + etymology

Vallely may have gotten his misinformation from the execrable 1001 Inventions web site, which is a mountain of misinformation on this topic. I expect to write at more length about this in the future. In the meantime, here is my summary of the web site:

Did you know that the belt was invented by Muslim tailor al-Qurashi in the year 1274, and was not widely adopted in Europe until the 14th century? Before that, Europeans had to walk around holding up their trousers with their hands, and had nothing from which to hang their wallets! The word 'belt' is from the Arabic 'balq', which means 'look down!'

[Other articles in category /google-roundup] permanent link

Google query roundup
My blog continues to attract interesting Google queries. I had fun looking over the queries and writing about them last month, so I thought I'd try it again.

Sometimes the queries are for very specific information that I can't provide:

	   1  the four type of flowers by aristotle
	   1 c-source code for earth revolving sun
	   1 colleges christian goldbach went to 
	   1 moon sky rhode island position feb 01-feb 14
	   1 what is robert hooke' s middle name?
	   1 scientific definition on why fingers get pruney
	   1 source code of unrestricted simplex protocol in c

Buy An Essay Towards a Real Character and a Philosophical Language from Bookshop.org (with kickback) (without kickback)

In the "you're asking the wrong question, so all you'll get is the wrong answer" department:

	   1 books typical copies sold

	   1 "typical royalties" 
	   1 total o'reilly books sold
	   1 typical royalties

In the "damn, I wish I had the foggiest idea" department:

	   1 what happens inside the chrysalis

Sometimes, the page to which the user is referred is just perfect for their query:

	   1 every natural number is either a fibonacci number or it
  	     can be written as a sum of nonconsecutive fibonacci numbers 

	   6 how many people can use an armonica properly

Contrary to this, however, is this recurring query:

	   1 linear math system eliminate debt

Some of the queries are even more depressing. For example:

	   1 which expression represents the number 96 written as a
             product of primes? 

Here's another one like that:

	   1 greatest common factor of 36 and 63

But sometimes searching for the exact question you want answered does work:

 	   1 a rope lying over the top of a fence is the same length
  	     on each side.  it weighs one third of a pound per foot.
  	     on one end hangs a monkey holding a banana, and on the
  	     other end a weight equal to the weight of the monkey. the
  	     banana weighs two ounces per inch.  the rope is as long
  	     (in feet) as the age of the monkey (in years), and the
  	     weight of the monkey (in ounces) is the same as the age
  	     of the monkey's mother.  the combined age of the monkey
  	     and its mother is thirty years.  one half of the weight
  	     of the monkey, plus the weight of the banana, is one
  	     forth as much as the weight of the weight and the weight
  	     of the rope.  the monkey's mother is half as old as the
  	     monkey will be when it is three times as old as its
  	     mother was when she she was half as old as the monkey
  	     will be when when it is as old as its mother will be when
  	     she is four times as old as the monkey was when it was
  	     twice as its mother was when she was one third as old as
  	     the monkey was when it was old as is mother was when she
  	     was three times as old as the monkey was when it was one
  	     fourth as old as it is now.  how long is the banana?

Speaking of problems that are simpler than they first appear, Jeff Abrahamson told me a good one a few months ago: One-tenth of a sphere is painted red, the rest blue. Show that there must exist eight blue points that lie at the vertices of a cube.

	   1 how did they invent the chinese symbols

Buy Writing Systems from Bookshop.org (with kickback) (without kickback)

Others are phonetically motivated. For example, the word for "ridgepole" is a compound of "wood" and "east" . The tree makes sense, because ridgepoles are made of wood, but why "east"? It's because the word for "ridgepole" is pronounced dòng, exactly the same as the word for "east". Lots of words are dòng, but this is the wooden dòng. The "east" component tells you how to pronounce it, and the "wood" component hints at the meaning.

Writing Systems, by Geoffrey Sampson, has a chapter about this; I recommend both the chapter and the rest of the book.

	   1 fundamental theorem of phyllotaxis 

Other fundamental theorems include: the fundamental theorem of arithmetic, which says that every positive integer has a unique factorization into primes; the fundamental theorem of algebra, which says that every nth degree polynomial has n roots over the complex numbers; and the fundamental theorem of calculus, which relates the integral and differential calculus by saying that if f' is the derivative function of f, then:

	   1 doctor dolittle racism
	   1 dr dolittle prince bumpo racism
	   1 dr doolittle racism

I think a lot could be said about the presence or absence of racism in the Dolittle books, although I wouldn't expect much agreement on such a hot-button topic. But I imagine there would be more agreement that the changes that were made to the book in the name of greater racial sensitivity are rather weird.

[Other articles in category /google-roundup] permanent link

Google query roundup
Now that I have a reasonably-sized body of blog posts, my blog is starting to attract Google queries. It's really exciting when someone visits one of my pages looking for something incredibly specific and obscure and I can tell from their query in the referrer log that I have unknowingly written exactly the document they were hoping to find. That's one of the wonders of the Internet thingy.

For example:

	   1 monkey rope banana weight
	   1 "how long is the banana"
	   3 monkey's mother problem
	   1 "basil brown" carrot juice
	   1 story about diophantus,how old was diophantus when he got married

And this visitor got rather more than they wanted:

	   1 what pennsylvanian can we thank for daylight savings time

Although you'd think that by now the middle schooler would have figured out that questions that start with "What Pennsylvanian can we thank for..." are about Benjamin Franklin with extremely high probability.

I think this person was probably fairly happy:

	   3 franklin "restoration of life by sun rays"

Similarly, I imagine that this person was pleased:

	   1 monarch-like butterfly

Some of the queries are intriguing. I wonder what this person was looking for?

	   1 spanish armada & monkey

	   1 there is a cabinet with 12 drawers. each drawer is opened
	     only once. in each drawer are about 30 compartments, with
	     only 7 names.

Sometimes I know that the searches did not find what they were looking for.

	   1 eliminate debt using linear math

	   1 armonica how many people can properly use it

I had the good fortune to attend an armonica recital by Dean Shostak as part of the Philadelphia Fringe Festival a few years ago. Mr. Shostak is one of very few living armonica players. (He says that there are seven others.) The armonica is not popular because it is bulky, hard to manufacture, and difficult to play. The bowls must be constructed precisely, by a skilled glassblower, to almost the right pitch, and then carefully filed down until they are exactly right. If you overfile one, it is junk. If a bowl goes out of tune, it must be replaced; this requires that all the other bowls be unmounted from the spindle. The bowls are fragile and break easily.

The operator's hands must be perfectly clean, because the slightest amount of lubrication prevents the operator from setting the glass vibrating. The operator must keep his fingertips damp at all times, continually wetting them from a convenient bowl of water. By the end of a concert, his fingers are all pruney and have been continually rubbed against the rotating bowls; this limits the amount of time the instrument can be played.

Shostak's web site has some samples that you can listen to. Unfortunately, it does not also have any videos of him playing the instrument.

	   1 want did an wang invent 

An Wang invented the magnetic core memory that was the principal high-speed memory for computers through the 1950s and 1960s. In this memory technology, each bit was stored in a little ferrite doughnut, called a "core". If the magnetic field went one way through the doughnut, it represented a 0; the other way was a 1. Thousands of these cores would be strung on wire grids. Each core was on one vertical and one horizontal wire. The computer could modify the value of the bit by sending current on the core's horizontal wire and vertical wire simultaneously. The two currents individually were too small to modify the other bits in the same row and column. If the bit was actually changed, the resulting effect on the current could be detected; this is how bits were read: You'd try to write a 1, and see if that caused a change in the bit value. Then if it turned out to have been a 0, you'd put it back the way it was.

The cores themselves were cheap and easy to manufacture. You mix powdered iron with ceramic, stamp it into the desired shape in a mold, and bake it in a kiln. Stringing cores into grids was more expensive. and was done by hand.

As the technology improved, the cores themselves got smaller and the grids held more and more of them. Cores from the 1950s were about a quarter-inch in diameter; cores from the late 1960s were about one-quarter that size. They were finally obsoleted in the 1970s by integrated circuits.

When I was in high school in New York in the 1980s, it was still possible to obtain ferrite cores by the pound from the surplus-electronics stores on Canal Street. By the 1990s, the cores were gone. You can still buy them online.

An Wang got very rich from the invention and was able to found Wang computers. Around 1980 my mother's employer had a Wang word-processing system. It was a marvel that took up a large space and cost $15,000. ($35,000 in 2006 dollars.) She sometimes brought me in on weekends so that I could play with it. Such systems, the first word processors, were tremendously popular between 1976 and 1981. They invented the form, which, as I recall, was not significantly different from the word processors we have today. Of course, these systems were doomed, replaced by cheap general-purpose machines within a few years.

The undergraduate dormitories at Harvard University are named mostly for Harvard's presidents: Mather House, Dunster House, Eliot House, and so on. One exception was North House. A legend says Harvard refused an immense donation from Wang, whose successful company was based in Cambridge, because it came with the condition that North house be renamed after him. (Similarly, one sometimes hears it said that the Houses are named for all the first presidents of Harvard, except for president number 3, Leonard Hoar, who was skipped. It's not true; numbers 2, 4, and 5 were skipped also.)

[Other articles in category /google-roundup] permanent link