{\huge Happy St. Patrick's Day}

A trick of language and echoing

\vspace{.25in}

Neil L. is a leprechaun who has been visiting me since I started GLL. I had never seen a leprechaun before I began the blog---there must be some connection.

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

Neil L. has visited me many times before, usually late at night just as St. Patrick's Day starts here in Atlanta. I felt it would be different this year, since I am now happily engaged to my fiancée Kathryn Farley. She is---as you may have guessed---of Irish descent. We have discussed Neil and she has mixed feelings about him.

She has a PhD in theater from Northwestern University, and is currently teaching a course at Tech on computational improv. Kathryn feels, as an expert in story telling of all kinds, that leprechauns are fundamentally anti-Irish. I have explained that Neil is different, but she may be right. Our friends at Wikipedia say:

Films, television cartoons and advertising have popularised a specific image of leprechauns which bears scant resemblance to anything found in the cycles of Irish folklore. Irish people can find the popularised image of a leprechaun to be little more than a series of stereotypes of the Irish.

Yet the mascot of the University of Notre Dame is The Notre Dame Leprechaun. Perhaps Kathryn is still right.

The Arrival

Nonetheless I told Kathryn I'd stay up late to see Neil this year again. She and I watched CNN's usual repetitive discussion on the US election primaries, with CNN's usual talking heads, until she said she would call it a night. It was already 2am and she retired to our bedroom and fell asleep.

I sat alone on our study sofa waiting. Toward three o'clock the soft sofa and boring CNN discussion with the sound set low were too much, and I was soon fast asleep too.

I was awakened by the sweet smell of smoke. The room was dark and as my eyes adjusted I finally saw him standing near me puffing his pipe, each puff filling the air with green smoke. I nodded hi, realized that Neil had turned off the TV, and asked him, why was he late this time? Neil replied,

You moved again.

I was surprised since yes I had moved, but Neil is a leprechaun. How could he be confused? He said he just forgot about my move---even leprechauns mess up their online calendars it seems. He said he'd appeared at my previous place and even my old house and scared the people who lived there now. Neil chuckled and smiled, and took another puff of his pipe. He added: ``it put their hearts crossways dead right.''

Groggily I said hi and that I thought he might have decided to skip this year. But he said:

Skip?---go way outta that. I love seeing you.

Neil sat down next to me and puffed some more green smoke, filling the room with that sweet smell.

Our Discussion Starts

In past years I've sometimes been granted the ability to ask Neil questions. None of that has ever worked---he's always outsmarted me---see this for example. So this year I said right away that it was great to see him, but I desired no questions. I was tired of being made to look foolish. Neil smiled and said:

Aw, sure look it. I see you are more clever than I had imagined. Good choice.

But I knew that Neil was magical, knew all, and could help me: was there some way to get information out of him? Hmmm... I had an idea.

No Yes and No No

I had prepared for Neil's visit. While he spoke English to me, his native tongue is Gaelic, which some call Irish. I had discovered that Gaelic has one very distinct property:

There are no words for `yes' or `no' in Gaelic.

Yes. Really. You cannot just say ``yes'' or ``no'' to answer a question. You have to echo the question. Here is an explanation:

For instance, there are no words for ``yes'' or ``no'' in Gaelic. It's the truth. If you want to answer somebody in the positive or negative, you actually have to refer back to the question itself in the form of a positive or negative statement. So, when somebody asks you ``ar mhaith leat cupan tae?'' (would you like a cup of tea?) you cannot just say ``yes'' or ``no''---there simply aren't any words for that. You have to keep up the chatter by answering: ``ba mhaith liom cupan tae'' (I would like a cup of tea) or if you're feeling lazy you can reduce this as far as ``ba mhaith liom'' (I would like) but absolutely no further.

I wondered if I could use the lack of the words ``yes'' and ``no'' in some clever way to trick Neil.

My Trick

Here is what I tried. I figured I should start by asking him something I already knew the answer to: ``Neil, is it true that in your native tongue you cannot say simply `yes' and `no'?'' He smiled, then frowned, and then he took several more puffs. Then he nodded. I told him I had a challenge for him. He nodded again. I said:

I know you are very smart---smarter than I---but perhaps you could give me the answer to does P=NP or not, yet still keep it hidden form me.

Neil was clearly intrigued and nodded once again. He replied:

'Tis clever of you to know about my Gaelic language, but what does it have to do with answering you without answering you?

I thought that I had him at least interested. I explained my plan. He should write out a Gaelic answer to whether P=NP, of course without using ``yes'' or ``no,'' and then encrypt using a clever code. So clever that I would be unable to decode it.

Neil looked at me, puffed out a large green ring of smoke, and then glanced at me with narrowed eyes.

This is possible, but I wonder if I have the right...

A green spark flared in Neil's pipe. He said, ``Aye---Tom Gallagher grants the right.'' Out came a parchment---from where I did not see. Its contents were instantly familiar to me since after all I have read about and taught crypto:

\includegraphics[width=3.5in]{DorabellaCode.png}

I said, ``What---wait---this isn't P=NP; this is El-'' but Neil hushed me: ``It be the answer you requested. It comes with a story.''

The Enigma

Neil refilled his pipe---I had never seen him do this and so I leaned forward keenly despite my tiredness. He spoke in low tones.

``Although Charles Babbage never promoted his Engines as cryptographic devices, of course others thought of it and after Babbage's death in 1871 started to act. Edward Elgar pursued codes as well as music from boyhood and thought the Wheel of Fifths and Babbage's gears all came together. Elgar tinkered with gear diagrams like this all his life:

\includegraphics[width=3in]{ElgarNotebookCrop.png}

But Elgar never had any money to invest and his music career was failing---it didn't help that he scribbled cryptograms on music he was supposed to be studying or writing. Old Tom took pity---ye need not be Irish but it helps if ye be Catholic---and on July 14, 1897 paid him a visit. Tom wasn't trapped---no wishes---but he granted one question like I've done wi' ye. Tom hoped he would ask something practical like, ``How can I compose better music?''---which he could answer not yes/no but do something to help. But Elgar asked:

``Is it possible to encode by machine so that no man or machine can decode quickly?''

Of course you recognize this as a form of your ``P=?NP'' question---technically if multiple decodings can be right. As ye know, Tom could not answer yes or no. So he echoed the question by encoding his answer using Elgar's diagrams as you see, so that Elgar could gain the answer in the doing---or not.''

Well, I thought this was all blarney---by definition, it was blarney. Recalling some Irish phrases myself, I said, ``That's a fret. How can you prove your story?'' Neil missed nary a beat and declaimed:

Old Tom, who wrote the book on leprechauns, signed his name `Th G' in a way disguised as `July.' His luck still rubbed off since Elgar tried rotating musical themes on his gears and soon came up with his ``Enigma Variations,'' which changed his fortunes. When the German engineer Arthur Scherbius named his machine `Enigma' after Elgar's work, it wasn't to honor some English music but Elgar's cryptographic work. So your Alan Turing in World War II had some luck o' the Irish on his side. Ach ní Turing ná Elgar ná man ná machine has ever decoded what old Tom writ.

And with a final puff of green smoke Neil was gone. I joined Kathryn in the bedroom and fell fast asleep.

Open Problems

Can you resolve Tom's enigma---and Neil's?

Happy St. Patrick's Day.