Thursday, September 17, 2009

Possibly Recruits for the Polymath Primes Project

In the book The Man who Mistook his Wife for a Hat and other Clinical Tales by Oliver Sacks there is a true story about two twin brothers (John and Michael), both autistic, who have the following properties (Sentences in italics are direct quotes from the books.)
  1. They cannot do simple addition or subtraction with any accuracy, and cannot even comprehend what multiplication and division mean. (page 197)
  2. John would say a number--- a six figure number. Michael would catch the number, nod, smile and savour it. (page 201). Oliver Sacks wrote down their numbers and, following a hunch, found out they were all primes.
  3. Oliver Sacks joined them and spoke an 8-digit prime. There was a long pause--- it was the longest I had ever known them to make, it must have lasted half a minute or more---- and then suddenly, simultaneously, they both broke into smiles.... An hour later they were swapping 20 figure primes, at least I assume this was so as I had no way of checking. (Page 203. Note that this happened in 1966.)
This raises several questions.
  1. How are they doing it? These brothers were unable to tell Oliver Sacks. However, in other essays in books when Oliver Sacks gets to talk to savants that are not autistic they also can't explain how they do it.
  2. Since these twins do not know basic arithmetic they are not using the Sieve of Eratosthenes. Nor are they using the AKS Primality algorithm to test their primes. I speculate that they are using a different model of computation then we work with. One is tempted to say Neural Nets! or Analog Computers, but I suspect it is something completely unfamiliar to us.
  3. If we could figure out what they are doing could it lead to a solution to the polymath problem on finding primes? Alas no, since I doubt what they are doing would fit into what we are doing.
  4. Prediction:
    1. Someone will devise a model of Savant Computing. The Polymath problem referred to above will be in SAVANT-P, giving the field a push (not as big a push as FACTORING IN QP gave Quantum).
    2. People will come up with 1 or 2 more real problems in SAVANT-P, and dozens of complexity classes and theorems about SAVANT computing.
    3. There will be some results in lower bounds on classical models (which my then may include quantum) that are claimed to be easy to prove with SAVANT concepts but not otherwise. People will argue about is it really easier?.
    4. I will write a blog Is Savant the next Quantum?.
  5. Could the twins get a job at the NSA? Today no, since they need primes far bigger than 20 digits. But back in 1966...

21 comments:

  1. "Since these twins do not know basic arithmetic they are not using the Sieve of Eratosthenes."

    I would argue that this is a false assumption. Since they do not know basic arithmetic, they are not consciously using the Sieve of Eratosthenes, but they could be applying basic arithmetic at a subconscious level.

    Of course, it seems unlikely that they're using the Sieve of Eratosthenes anyway, but their inability to consciously use arithmetic doesn't mean that their savant ability doesn't apply it in some way.

    Very interesting, however!

    ReplyDelete
  2. Savant complexity seems to be backward, in the sense that the prime number seems to come in a momentary flash of inspiration, but it takes more time for the savant to realize that it is actually a prime. That is, it is faster to generate primes than it is to check them.

    ReplyDelete
  3. They probably use some kind of heuristic. Lets try :

    1) If the number end by 0, 2, 4, 5, 6, 8 it is trivialy composite

    2) Ok, now what to do if it end by 1, 3, 7, 9 ?

    If the sum of the digit, applyed recursively gives a multiple of 3 (3, 6, 9), the number is composite*.

    3) what else ?

    After doing this, you can eliminate a lot of chance that the number is composite and safely say "prime !"

    * ok, the book say that they don't know how to do addition, so they probably use a stranger shortcut.

    ReplyDelete
  4. Let's find some savants who can solve SAT instances!

    ReplyDelete
  5. Maybe they also both had Synesthesia?

    ReplyDelete
  6. @3: As you get into 6- 8-, and 20-digit numbers, your changes of finding a prime using that heuristic are pretty slim.

    ReplyDelete
  7. From the wikipedia article :

    "synesthesia is usually easily achieved by means of psychedelic drugs, such as LSD, psilocybin or Cannabinoids"

    Let me see if I can solve SAT after ;-)

    ReplyDelete
  8. I am skeptical. Does Sacks give any stronger evidence? The idea of looking at twenty digit numbers and just assuming that they are prime seems ridiculous. Did he even write them down?

    ReplyDelete
  9. For me, all of Sacks' stories feel a bit suspicious. It is often quite obvious that he alters minor facts for dramatic impact. His favorite trick is to present what must have been weeks of careful observations as a single eventful, emotionally charged encounter. One hopes that it is only the minor details that he doctors.

    ReplyDelete
  10. How could they interpret numbers that are encoded through a sequence of digits without some concept of addition and multiplication?

    ReplyDelete
  11. A better-documented book (but with no mathematical feats in it that I recall) is Luria's Mind of a Mnemonic.

    Luria's patient, Solomon Shereshevskii (who has his own Wikipedia page) has a fictional counterpart in Borges Funes el memorioso (which also has an interesting Wikipedia page).

    It would indeed be interesting if these computationally extravagant mathematical feats could be better documented; I know of no such cases however.

    As they teach in medicine, "The plural of anecdote is not data", and "anecdote" is the category into which Oliver Sacks' account must be classified.

    ReplyDelete
  12. As a followup, clinical professor Darold A. Treffert, MD, of the Wisconsin Medical Society, maintains a web page called Savant Profiles that provides numerous case histories and many further references.

    Does the amazing working of these minds require only PTIME resources (as orthodox neurophysiology predicts)?

    If so, these case histories testify to the *amazing* power of PTIME algorithms; this is what I take to be the main thrust of GASARCH's post.

    ReplyDelete
  13. but aren't the twins representative of the oracle in the tcs world ?

    ReplyDelete
  14. Sacks wrote that he confirmed the primes they found in a book he owned that listed all up to ten digit primes.

    That's 400 million numbers, way too big for a book you could carry around, or one that has no record of being published.

    Sacks later claimed to have 'lost' the book, and that perhaps he got the number wrong....

    ReplyDelete
  15. JC: That's very interesting. Did anyone ever take him to task for making sh.t up so shamelessly?

    ReplyDelete
  16. Since this topic is winding down, perhaps it is appropriate to emphasize that Oliver Sacks' popular writings should *not* be mistaken for peer-reviewed research.

    Which is not to say savant syndrome is not real and fascinating ... a PubMed search finds a recent review article by the above-mentioned Darold A. Treffert:

    The savant syndrome: an extraordinary condition. A synopsis: past, present, future.

    "Savant syndrome is a rare but extraordinary condition in which persons with serious mental disabilities, including autistic disorder, have some “island of genius” that stands in marked, incongruous contrast to overall handicap. In fact, as many as one in 10 autistic persons has such remarkable abilities in varying degrees ... While there is as yet no over-arching theory to explain all instances of savant syndrome, more progress has been made in better understanding this condition in the past 15 years than in the prior 100 ... No model of brain function, including memory, will be complete until it can account for, and fully incorporate, the rare but spectacular condition of savant syndrome."

    This review is highly recommended for the impressive lower bounds thast it sets on the limits of human cognitive capability! :)

    ReplyDelete
  17. An hour later they were swapping 20 figure primes, at least I assume this was so as I had no way of checking.

    There doesn't seem to be the slightest reason to think the 20-digit numbers were actually prime. They might have been, but it's plausible that the twins had slightly different interests. For example, instead of thinking about primality in any strict sense, maybe they were just impressed by numbers for which they could think of no proper factors. In fact, it could have been a game: one twin proposes a number, and the other wins if he can find a proper factor. Perhaps over time they got very good at avoiding composites, but they enjoyed playing it despite its eventual predictability. They may have found the predictability comforting, or maybe they simply liked playing with numbers.

    Their powers were great enough that this process might coincide exactly with primality for six-digit numbers (after all, there are only 168 primes under 1000, so it's not out of the question to check exhautively for small factors). However, for 20-digit numbers the two notions could diverge dramatically.

    It would have been so much better if Sacks had recorded the numbers. I can see why he wouldn't include them in his book, but I'm surprised that he observed this remarkable behavior and made no attempt to document it carefully.

    Incidentally, this must be the book Sacks was using:

    D. N. Lehmer, List of Prime Numbers from 1 to 10,006,721. Washington, D. C., Carnegie Institution of Washington, 1914. xvi+133 pp.

    If it is, then his memory was slightly off about the number of digits. That's not so unreasonable, given that he was writing about it nearly twenty years later.

    ReplyDelete
  18. It is also interesting that eventually the twins lose their computing capacity as soon as they are divided and force to join the society

    ReplyDelete
  19. Could the twins get a job at the NSA? Today no, since they need primes far bigger than 20 digits. But back in 1966...

    Back in 1966, it's not clear the NSA had any use for primes at all. (If they did, it's still classified.)

    ReplyDelete
  20. Although, I have heard of savants and their surprising abilities, this story seems to me a bit of exaggeration.

    Unless, I see some closed scientific study of the twins abilities, I will be skeptical that anyone can come with large primes within minutes.

    ReplyDelete
  21. I agree that Oliver Sack's story may be exaggerated or smoother out in some form. One of his critics called him
    ``The man who mistook his patients for a literary device.''

    However, the questions of
    HOW DO SAVANTS DO IT? is still
    interesting, unless the answer is
    THEY DON"T.

    ReplyDelete