\documentclass[14pt]{article}

\usepackage{epsf}
\usepackage{epsfig}
\usepackage{color}

\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{wrapfig}
\usepackage{subfigure}
\usepackage{hyperref}

%\usepackage{fancyheadings}
%\pagestyle{fancy}

\setlength{\parindent}{0pt}
\setlength{\parskip}{1ex}
\widowpenalty 10000

\usepackage{color}
\definecolor{MyDarkBlue}{rgb}{0.1,0,0.9}
\newcommand{\aside}[1]{\textcolor{MyDarkBlue}{#1}}

\usepackage{enumerate}


\usepackage{lineno}
%\linenumbers

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\mybox}[1] {
\begin{center} {\small
\framebox[3in]{
\begin{minipage}[t]{4.5in} {\sf #1}
\end{minipage} } }
\end{center}}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{definition}[theorem]{Definition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{example}[theorem]{Example}
\newtheorem{remark}[theorem]{Remark}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\setlength\oddsidemargin{0in}
%\setlength{\textwidth}{6.5in}
\setlength{\textwidth}{4in}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\latex{latex }
\newcommand{\header}[1]{\section*{#1}}
\newcommand{\myquote}[1]{''{#1}''}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}

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

{\it Leprechauns are tricky even when they're not}

\vspace{.5in}
%\includegraphics[width=1in]{neil.png}

Neil L. is a Leprechaun.

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

%%KWR: three --> four years.  The three wishes were 2 years ago, in 2011.

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, 
\begin{quotation}
I forgot about Daylight Savings Time, it is earlier this year.
\end{quotation}
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,
\begin{quotation}
I only give wishes if you catch me. Not the case this year.
\end{quotation}
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 that he enjoyed fooling me \href{http://rjlipton.wordpress.com/2012/03/17/leprechauns-are-tricky/}{last year} when I had three wishes and got nowhere. He said with a broad smile,
%\begin{quotation}
%Last year was great fun.
%\end{quotation}
%I replied it might have been fun for him, but was not for me. He clearly had out smarted me: my questions were not very clever and he easily avoided really answering them. 

I asked, why did he visit me anyway?  He smiled and said he was still enjoying the way he had fooled me \href{http://rjlipton.wordpress.com/2011/03/17/happy-st-patricks-day-again-again/}{two years ago} when I had three wishes and got nowhere.  But
\href{http://rjlipton.wordpress.com/2012/03/17/leprechauns-are-tricky/}{last year} when I had no wishes, he had led down his guard and almost given some secrets away.

\begin{quotation}
That was a learning experience.
\end{quotation}

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. 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{A Challenge}

Neil puffed some more on his pipe and finally with a twinkle in his eyes said,
\begin{quotation}
I will grant you two wishes if you can guess my secret today. Good luck to you. 
\end{quotation}
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,
\begin{quotation}
You get three.
\end{quotation}
I added, ``I will get three guesses?'' He answered quickly,
\begin{quotation}
Yes indeed. 
\end{quotation}

I thought for a while and asked: is the secret in what you have said to me? He said,
\begin{quotation}
Indeed indeed.
\end{quotation}
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,
\begin{quotation}
I cannot just say yes.
\end{quotation}
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?


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{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 \href{http://en.wikipedia.org/wiki/Quasi-quotation}{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, 

\begin{quotation}
Just so I understand about what you {\bf say} and what you {\bf mean}, may I have an example?''
\end{quotation}

%%KWR: 17 words

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 $X(n)$ time, can you understand that $n$ is the input length, and $X(n)$ 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:

\begin{quotation}
'Yes' to both your questions---I learned about time long ago from the Venerable Bede, who did the most to \href{http://en.wikipedia.org/wiki/Bede#Use_of_Anno_Domini}{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.
\end{quotation}

%%KWR: 67 words.  Bede was English but entertained Irish missionaries and wrote notably warmly of the Irish---so he is "honorary Irish".

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

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

%%KWR: 23 words


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.







%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Question II}

Only one question left.  If I asked about P versus NP I would even get an answer about \href{https://complexityzoo.uwaterloo.ca/Complexity_Zoo:D#distnp}{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 {\it most-case} complexity matters for a question that has been in my inbox a lot these past two weeks, since we passed on the \href{http://rjlipton.wordpress.com/2013/03/02/cryptography-is-dead/}{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 $L(1/4)$ where for all $a > 0$,

    $$L(a) = \exp(cn^a (\log n)^{1 - a}).$$

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

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

Neil responded quickly and forthrightly:

\begin{quotation}
Yes---see?
\end{quotation}

---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

\begin{quotation}
{\bf c}
\end{quotation}

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.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Open Problems}

How had Neil tricked me?  What is the relevance of {\bf c}?  Does watching \href{http://rjlipton.wordpress.com/2013/01/19/cantors-theorem-the-movie/}{this} help?

Happy St. Patrick's Day. 

{\bf PS}: His secret I caught was that the number of words in all his answers was $\dots$
% they are all primes

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{document}


