{\huge Happy St. Patrick's Day---Again and Again and Again and Again}

Leprechauns are tricky even when they're not

\vspace{.5in} Neil L. is a Leprechaun.

Today I want to share my experience with him this morning of St. Patrick's Day.

Neil L. has visited me the last four years, so I was obviously expecting him to visit again this year. I stayed up late Saturday night, and as the clock hit 12:01am I expected him to appear any second. But no Neil. There I sat on my study sofa waiting. Soon it was nearing one o'clock and the combination of the soft sofa and the late hour overcame my resolve---I was soon fast asleep.

I was awakened to the sweet smell of smoke. The room was dark, and as my eyes adjusted I finally saw him standing next to me puffing on his pipe, each puff filling the air with green smoke. I nodded hi and asked him why he was late this time? Neil said, I forgot about Daylight Savings Time, it is earlier this year. I said it was great to see him anyway, but did not add that the rules on Daylight Savings had changed in the US six years ago---perhaps he was kidding me---in any event I was thrilled to see him again.

Do I get some wishes this year, I asked Neil. He laughed and took his pipe out of his mouth. He said, I only give wishes if you catch me. Not the case this year. With that he laughed and sat down on the sofa near me, and began to puff away on his pipe again.

I asked, why did he visit me anyway? He smiled and said he was still enjoying the way he had fooled me two years ago when I had three wishes and got nowhere. But last year when I had no wishes, he had led down his guard and almost given some secrets away.

That was a learning experience.

He said he felt I had some more to offer in learning to deal with human beings, and would like to test my perception. I wondered what he had in mind.

A Challenge

Neil puffed some more on his pipe and finally with a twinkle in his eyes said, I will grant you two wishes if you can guess my secret today. Good luck to you. I looked at him and thought what could his secret be? He was dressed as always, in green, with that hat; he had the same pipe, with the same smelling tobacco, with the same green smoke. I saw nothing special. What I could be his secret? He loved word games but nothing he had said seemed to strike me. Here I was with that Leprechaun again and was at lost for what his secret might be.

I asked him would I get more that one guess at his secret? He answered after a short pause, You get three. I added, ``I will get three guesses?'' He answered quickly, Yes indeed.

I thought for a while and asked: is the secret in what you have said to me? He said, Indeed indeed. Hmmmm---there was something strange about that last answer, why the repeat? I knew he likes to play with his words. I began to see something. I quickly asked, ``will you just say `yes'?'' He looked upset and said, I cannot just say yes. I had a idea. It had to be it. I smiled and said, ``I see your game: you are always in your prime.'' He looked shocked. I knew his secret. Do you?

Question I

I had ``caught'' him again, but since I hadn't literally caught him in my arms or trapped him some other way, I only had two wishes. And Neil said they had to be questions, not wishes for things like gold.

So I had just two questions this year. I wanted them to really count. When I last had them, you may recall, I asked for proofs of certain problems and got nothing of value. He had beaten me. This year I resolved to be more clever. I thought that I might just ask, ``Is P=NP true?'' But even this worried me. Could he wiggle out by some trick? What if he said no, but simply meant that the symbols ``P'' and ``NP'' are obviously not the same. The logician Willard Quine was an expert at quotes and meanings of sentences, and I had studied him as a graduate student, years ago. But I worried that Neil would get around any question, perhaps using some quote trick.

So I asked Neil, ``Can I ask you a question---a precise question---so that you will answer it the way I mean when I ask it, and not resort to some trick of language?''

Neil puffed on his pipe and replied,

Just so I understand about what you say and what you mean, may I have an example?''

I wanted to make sure he understood concepts like polynomial time, so I phrased it this way: ``If I ask you does a problem have an algorithm that runs in $latex {X(n)}&fg=000000$ time, can you understand that $latex {n}&fg=000000$ is the input length, and $latex {X(n)}&fg=000000$ isn't in some literal units of time like seconds but asymptotic, and that constants or even lower-order terms like logarithmic factors don't matter?''

Neil drew forward and replied:

'Yes' to both your questions---I learned about time long ago from the Venerable Bede, who did the most to standardise our numbering of years. But note you've already asked me two questions. Luckily for you my answer still allows you to ask me a question---a precise question---so that I will answer it the way you said you mean, not by a trick of language.

I glowered---I had just let myself get tricked again. And I felt tricked by language: I hadn't meant to use either of my two questions yet. Neil sensed my upset, so he volunteered:

I will make my answer valid for both worst and average case complexity, just as if you have asked them as separate questions.

Fair was fair, and I still in a sense had two questions. Better yet, I could ask a precise question and get it answered on my terms.

Question II

Only one question left. If I asked about P versus NP I would even get an answer about DistNP as a bonus. But I worried that would be too much to ask for, maybe not precise enough---moreover, I had spoken about running times and Neil's promise was tied to that.

And most-case complexity matters for a question that has been in my inbox a lot these past two weeks, since we passed on the news from Dan Boneh at the RSA Conference about the breakthrough on discrete log. Recall he said there is an attack on discrete log that runs in time $latex {L(1/4)}&fg=000000$ where for all $latex {a > 0}&fg=000000$,

$latex \displaystyle L(a) = \exp(cn^a (\log n)^{1 - a}).&fg=000000$

Here $latex {n}&fg=000000$ is the number of digits in the input number $latex {q}&fg=000000$, and $latex {c}&fg=000000$ can be any constant---I didn't have to say what $latex {c}&fg=000000$ is because it didn't matter. In fact the whole $latex {(\log n)^{1-a}}&fg=000000$ didn't matter---Neil would have to ignore lower-order factors---so only the $latex {a}&fg=000000$ in $latex {\exp(cn^a)}&fg=000000$ mattered. The exponential security condition on discrete log and factoring is that there is some $latex {a > 0}&fg=000000$ such that $latex {\exp(n^a)}&fg=000000$ is a lower bound, indeed a most-case lower bound. This is what the slippage from $latex {L(1/3)}&fg=000000$ to $latex {L(1/4)}&fg=000000$ seems to threaten, what Adi Shamir used to say he believed in and people cared about, what even the ``Natural Proofs'' barrier about proving $latex {\mathsf{P \neq NP}}&fg=000000$ is technically based on. Breaking factoring would ``destroy the world economy'' I had heard Alexander Razborov say in Washington, so I felt this was the most important precise question I could ask Neil:

Does there exist a positive real number $latex {a}&fg=000000$ such that factoring does not have an algorithm with running time $latex {\exp(n^a)}&fg=000000$, answering also for average case?

Neil responded quickly and forthrightly:

Yes---see?

---and vanished in a billow of green smoke.

I was amazed---no wordplay trick, I had a direct answer. And I was sure a lot of people in Washington and Virginia in particular would be thrilled to know of it.

With puffed-up satisfaction at having beaten Neil at last, I watched the smoke he left behind. I thought it would simply dissipate, but it didn't. The smoke wound itself together like a thick short rope, then curled over so that it formed a letter---the letter

c

in a distinctly Gothic font. Then came the horrible realization: Neil had held to the letter and spirit of everything I'd requested, and had given me a mathematically correct answer, yet I had learned nothing.

Open Problems

How had Neil tricked me? What is the relevance of c? Does watching this help?

Happy St. Patrick's Day.

PS: His secret I caught was that the number of words in all his answers was $latex {\dots}&fg=000000$