To be human, that is

Neil L. has graced these pages many times before. Every eve of St. Patrick’s Day he has visited Dick. Sometimes Dick has been hard to find, but Neil has always managed.

Today we relate some medical news while wishing a Happy St. Patrick’s Day 2018.

Neil knew to go to the apartment shared with Kathryn which is adjacent to MoMA in Manhattan. He appeared and took in the grand view of St. Patrick’s Cathedral through their east-facing window. But he did not find either of them there.

What Neil found was a sheet of paper on a table near the window. “A message for me?”, he breathed. He read in big letters across the top “IDEA FOR GOLD-” and that was enough. He snatched the sheet and vanished. But he had to go somewhere. So he came to me.

## A Hardy Story

I had seen Neil for the first time only a year ago. Since I knew what Neil didn’t, I was expecting him. I had gone down to my basement ostensibly to watch “March Madness” while on the exercise machine. I was riveted by bottom-seed UMBC sinking three straight 3-point shots to hold #1 Virginia to a 21-21 tie at halftime, but at the first sign of green smoke I switched off the TV and pulled up two chairs and a small table with ashtray.

Neil intoned as he lit his pipe,

“A blessed eve to ye.”

I replied, “Same to you—I guess it has already turned St. Patrick’s Day in your home isle.” Neil nodded and as he was about to speak I interjected, “You did not find Dick—”

“Aye—aught I saw of him.”

I had permission to inform Neil of why:”He is in intensive care after heart surgery. Kathryn is with him.”

Neil doffed his green hat with a long and serious “Ahhhh…” Then he took a long drag on his pipe. “To be mortal…”, he whispered. But forcing his lip corners brightly up, he said,

“Yet ideas are immortal—that is why I come. Every year, at this time. I have a message from Dick to show ye.”

He pulled out the sheet. I read the entire top line: Idea for Goldbach. “He means the Goldbach Conjecture,” I informed Neil. I expected Neil to recognize the conjecture—if leprechauns can be nerds, he is one. Duly Neil intoned:

“Every x > 2 that is divisible by 2 is the sum of two—“

“Primes.” I completed his sentence—the pause struck me as strange—and I went on: “With Fermat’s Last Theorem having been solved, Goldbach is now the easiest unsolved problem in mathematics to state. The fact that Pierre Fermat got 357 years of credit for a ‘Theorem’ just because he left a marginal note saying he’d proved it emboldened Godfrey Hardy…” On my new I-Pad I called up the story:

Hardy was known for his eccentricities. … He always played an amusing game of trying to fool God (which is also rather strange since he claimed all his life not to believe in God). For example, during a sea trip to Denmark he sent back a postcard claiming that he had proved the Riemann hypothesis. He reasoned that God would not allow the boat to sink on the return journey and give him the same fame that Fermat had achieved with his “last theorem.”

A long green puff accompanied the reply,

“Would Dick do that?”

I reflexively replied “naw” with my mouth but the part of me that really wanted to see the idea had control of my hands. I reached for the sheet and there was a flash of white light.

## A Scripted Lesson

The sheet no longer had Dick’s handwriting. I expected Neil to chide my haste and withdraw it, but instead he laid it flat and folded his arms:

I goggled a bit, but I knew what I was looking at without googling. “That’s not leprechaun writing. That’s Nigerian script as used in the movie Black Panther.”

“Aye.”

“You can’t do that. That’s cultural appropriation.”

Neil emptied his pipe, straightened his gold buckle, tipped his hat again, folded his arms the other way, and gave me a long stare.

“Oh who would ye tattle me to, the First Minister o’ the Irish?”

Neil meant Leo Varadkar, but why “first” minister? This was the second time he had avoided saying “prime.” Nor did he use the proper title Taoiseach or say “Ireland.” Clearly he was trying to convey something beyond a lesson of intercultural embrace. Neil piped up again:

“It matters aught what the characters are, but which ye tell away from each other.”

Neil was right—the information content resides wholly in the ability to distinguish pairs of symbols. Impatiently I asked, “So what is the information? Can you read it?”

“It is coded with the starkest cosmic scrambler—a black hole—so that I may tell little from it.”

## The Immortality Drive

My thoughts sprang ahead owing to this week’s passing of Stephen Hawking. In a children’s book written with his daughter Lucy Hawking and Christophe Galfard, the children’s astronaut father falls into a black hole but is resurrected through the Hawking radiation, though it takes a galactic computer “a long time” to reconstruct him. On the serious side, Dick and I have wanted to blog about the proposed solution by Patrick Hayden and Daniel Harlow to the black hole firewall paradox, whereby the one-wayness of Hawking radiation staves off the reckoning of the paradox. I’ve also wondered whether every computational process that can occur in nature must occur in proximity to any black hole, combined with every computation we can program ipso facto being one that occurs in nature. I then sprang back, however, to what Neil had said about immortality, so I asked:

“Neil, from your immortal perspective, would you say that Hawking of all humans came the closest to states that you recognize as pertaining to immortal beings?”

Neil unexpectedly flinched from my question.

“Steve—“

Stephen,” I corrected. “It makes a difference.”

“—he had little to share with us folk. Try Google. You will see.”

Indeed, there was basically no webpage connecting “Hawking” to “leprechauns” at all. Plenty for trolls and a few for elves, plus “fairy” as an adjective, but none for leprechauns. Nor gnomes. Noting what Hawking said about the brain possibly continuing in articles like this and this, and that he also had his DNA sequence shot into space on the Immortality Drive, I pressed Neil on my question. After long pause he replied softly:

“What do ye most celebrate about him this week, after all? If ye look at the Web everywhere it seems…”

Indeed I have been struck how so many of the memorial appreciations of his life were playing up his human qualities. The stories… Well, Hawking was human after all.

“Aught may ye have both ways, me lad.”

Whatever Neil meant by “aught,” there was the sheet of Dick’s ideas to decode. Neil had said he might tell a little from it. Jumping from Theory of Everything to the technical pivot of the Imitation Game movie, I realized we did have some of the plaintext: ‘idea’ and ‘Goldbach’ and associated words. Neil understood and gave it a go.

## A Goldbach Variation

After much play of green light over the sheet, Neil sighed and announced:

“I could decode just this early theorem.”

Neil copied it out in his hand and I read:

Theorem 1 Suppose that almost all even numbers are sums of two distinct primes. Then almost every prime is the middle of an arithmetic progression of length three.

Proof: Let ${N}$ be given. We can clearly assume that all even numbers larger than ${N}$ are the sums of two different primes. Let ${r>N}$ be a prime and let ${2r=p+q}$ where ${p and both ${p}$ and ${q}$ are primes. Take

$\displaystyle \Delta = (q-p)/2.$

Now ${p}$, ${p+\Delta}$, and ${p+2\Delta}$ form a progression of length three. But each is a prime:

$\displaystyle p + \Delta = p+(q-p)/2 = (p+q)/2 = r$

and

$\displaystyle p + 2\Delta = p+(q-p) = q.$

$\Box$

So this leans on the slight strengthening of Goldbach where writing ${2p}$ as ${p + p}$ is disallowed. After ${6 = 3+3}$ every even number tested has been written as the sum of two different primes. An equivalent form is whether every number ${n > 3}$ is the average of two distinct primes. Dick’s conclusion is just the restriction where ${n}$ itself is prime.

Is this open? It still is. Neil and I scoured the writing but we could glean nothing more. Even to prove the existence of infinitely many length-3 progressions of primes had been difficult in the 1930s. What else was there about Goldbach, or did Dick’s sheet move on? I am looking forward to asking Dick next week when he will be up to having visitors.

Neil looked at his watch and gave a start.

“Begorrah—I must be off. Yea though the Irish laddies missed the basketball this year, still I must take care of malarkey me fellows might wreak… To boot, the ladies start tomorrow.”

I had time just to ask one more question: “Neil, if you were in this position and wanted to make sure your ideas for a big theorem were put down—even if not sure which side is true—which one would you choose?” Neil replied:

“With the totality of my uttered words here I have told ye. They have held throughout two attributes each of which literally makes it follow.”

And with a green flash he was gone. I turned on the TV and saw instantly that he was too late: “UMBC 74, Virginia 54” flashed on the screen.

## Open Problems

Can you process Neil’s speech to find his answer?

What chance might there be of proving that every prime ${p > 3}$ is an average of two other primes, short of proving the full Goldbach Conjecture?

I am sure all our readers will wish Dick a safe and speedy recovery. We were working on this on Thursday before his operation, including the math.

Update (3/18): Dick continues mending in the ICU. As for Neil L., he either failed to contain leprechaun excesses or joined them. This is what a graph of leprechaun involvement looks like.

A revel and revelation in Sweden

 Cropped from “Knuth at Brown” video source

Donald Knuth’s 80th=0x50th birthday was on January 10. In the array ${B}$ of his birthdays, numbering from zero so that ${B[0]}$ stands for his birth day in 1938, that was indeed ${B[80]}$. However, as the 81st entry in the array it might have to be called his 81st birthday. Oh well.

Today we salute his 80th year—wait, it really is his 81st year—and wish him many more.

How might it be applied in complexity theory?

 St. Andrews history source

William Burnside was a well-known researcher into the early theory of finite groups.

Today Ken and I thought we would talk about one of his most-cited results—a result that is really due to others.

From “readymade” works to surreal hash table wildness in chess programs fooled by him

 Toutfait.com source

Marcel Duchamp was a leading French chess player whose career was sandwiched between two forays into the art world. He played for the French national team in five chess Olympiads from 1924 to 1933. He finished tied for fourth place out of fourteen players in the 1932 French championship.

Today we look afresh at some of his coups in art and chess and find some unexpected depth.

Tid-bit: delicacy, dainty, snack, nibble, appetizer, hors d’oeuvre, goody, dipper, finger food

Adam Engst is the publisher of the site TidBITS. This is a site dedicated to technical insights about all aspects of Apple machines: from nano to servers.

Today I want to talk about mathematical tidbits not Apple devices, but look at the above site for information about Apple stuff of all kinds.

Variations on Montgomery’s trick

Peter Montgomery is a cryptographer at Microsoft. Just recently, Joppe Bos and Arjen Lenstra have edited a book titled Topics in Computational Number Theory Inspired by Peter L. Montgomery. The chapters range to Montgomery’s work on elliptic curves, factoring, evaluating polynomials, computing null-spaces of matrices over finite fields, and FFT extensions for algebraic groups. Bos and Lenstra say in their intro that most of this was “inspired by integer factorization, Peter’s main research interest since high school.” Factoring, always factoring…

Today we discuss one of Montgomery’s simpler but most influential ideas going back to a 1985 paper: how to compute mod ${N}$ when you can only do operations mod ${R}$.
Cody Murray is a PhD student of Ryan Williams at MIT. He and Ryan have a new paper that greatly improves Ryan’s separation of nonuniform ${\mathsf{ACC}}$ circuits from uniform nondeterministic time classes. The previous best separation was from ${\mathsf{NEXP}}$, that is, nondeterministic time ${2^{n^{O(1)}}}$. The new one is from ${\mathsf{NQP}}$, which is nondeterministic time ${2^{(\log n)^{O(1)}}}$. The ‘Q’ here means “quasi-polynomial,” not “quantum.”