Root of Unity

by SL Huang

  I poked again at the ashes, frustrated. “Dammit.”

  “I took a piece,” rambled on the old man. “She kept saying it was the end of the world, and I wanted to hedge my bets, you know. But I couldn’t make a lick of sense of it. I think maybe she’d gone round the twist. Poor woman.”

  I stood up so fast I almost knocked the fire pit over. “You took some? Where is it?”

  “You’re her daughter, right? Not with the government?”

  “I’m not with the government,” I said. “I swear.”

  “They’re spying on us, you know.”

  “Yes,” I said ironically. “I know. Where’s the stuff you took? Do you still have it?”

  “I still got it.” He squinted at me with rheumy eyes, thumping his cane against one leg. “I give it to you, you have to promise to visit her more. Rita never had any family come. You owe her that.”

  “Sure,” I said, giving up.

  “And you gotta explain it to me.”

  “Explain?”

  “Yeah. Why she kept saying it was the end. We already got earthquakes and police raids and all those dumb nuts in Washington mucking around printing money, and now there’s these papers that will collapse our country, I want to know why.”

  “Okay,” I said. “It’s a deal.”

  He sniffed like he had won. Then he turned and started shuffling back toward the building. “Come on, then.”

  He was so slow I had to resist the urge to pick him up and throw him over my shoulder, but finally his fumbling steps came to the back door of the ground-floor condo, and he negotiated his key ring with shaky hands.

  I followed him into a dim apartment only to be confronted with a hoarder’s paradise. Stacks of books and magazines climbed in threatening towers to the ceiling, and all manner of junk was crammed in at odd angles, from broken televisions to piles of clothing to at least two old bicycles. There were also mountains of bottled water, loose and in flats, and a row of five-gallon gasoline jugs behind a jumble of model rockets and bird cages. I was surprised the condo hadn’t broken apart at the seams.

  “It’s here somewhere,” said the old man. He started poking through the piles.

  I heaved a sigh and went to help, digging through clouds of old receipts and moving crusty paint cans to search for anything vaguely mathematical-looking, and trying not to breathe through my nose. This place was probably a health hazard—one that needed a card catalogue to find anything.

  Forty-three minutes later, the old man was still mumbling, “I know it’s here somewhere…my eyes aren’t what they once were…” and I was starting to wonder if he’d put me on. Still, there was no way I was going to leave. This was the closest thing to a lead we’d had on this, and if I had to stay here for a week and dig through every last stale piece of trash in the place, I was going to do it.

  Then I picked up a copy of National Geographic from the 1970s and saw something underneath.

  The pages were crumpled up and crammed against an old-school boom box. I picked them up and smoothed them out. I recognized Martinez’s dense script from the note she’d left for Halliday.

  I read them. Then I read them again.

  Holy shit. I knew why she thought she’d broken the world.

  Because…she had.

  She had.

  I moved toward the door in a daze.

  “Are you leaving?” asked the old man. He sounded sad. “You could stay for dinner. I have the kind in the little trays.”

  “I have to go,” I got out.

  “We didn’t find your mother’s notes,” he said. He turned his head from side to side, lost. “I know they were here somewhere. She said the end was coming, you know.”

  She had been right.

  He’d better stock up on more of those dinners with the trays. I didn’t tell him that. I didn’t say anything. I just let myself out.

  Once on the street, my legs went limp and I sat down hard on the curb. Martinez hadn’t found a factoring proof. She’d found something so much more explosive, so much more deadly.

  She’d proven the Holy Grail of mathematics. The impossible dream. She’d solved the P versus NP problem, and she’d proven them equal.

  Chapter 28

  I didn’t have enough of her notes to see how she’d done it. But there was enough context around the lemmas, enough explanation in her cramped handwriting, to know something of what she’d been doing. She’d been building a polynomial-time algorithm for 3-SAT.

  She’d been right: this would break the world. Rend it in two and shatter humanity in the upheaval. Civilization would never be the same…if it even survived.

  I sat on the curb for a long time. Everything around me—the cool evening air, the slight breeze, the deepening twilight, and the math, especially the math—felt different. It wasn’t, of course—except it was, because this so fundamentally changed our understanding of the universe that nothing ever could be the same.

  Finally I steadied myself. Stood up. Went to the car. Drove to Halliday’s safe house. The cars passed around me on the freeway like it was a normal fucking day.

  Arthur answered the door. “I need to talk to Professor Halliday,” I said. “And to you, too. Let’s go for a walk.”

  “Course,” Arthur said. “I’ll get her.” He disappeared for a minute and came back with Halliday, who grabbed a coat from next to the door and shrugged into it.

  We walked down by the lake. The night had deepened enough to make it hard to see each other. I pulled out the bug scanner that had become attached to my hip and pressed a button; it flashed green.

  “What’s going on?” said Arthur. “Is everything all right?”

  “I found out Martinez’s reason.” My tongue felt thick in my mouth. I didn’t know where to start.

  “What is it, Russell?” Arthur prompted, when I hadn’t said anything. He sounded concerned.

  He should be.

  I pulled the crumpled pages I’d gotten at Martinez’s condo out of my pocket and handed them to Halliday. Arthur passed her a penlight.

  “She burned Professor Halliday’s work after she burned her own,” I explained with a dry mouth, as Halliday read. “Because she was afraid. Because she had found something.”

  Halliday let out a gasp.

  “What? What is it?” said Arthur.

  “She proved P equals NP,” I said. The sentence didn’t sound real. It felt like I was saying a line, lying, pretending this impossible thing was true. Halliday had her eyes fixed on the paper, frozen. I was pretty sure she had stopped breathing.

  “Hey,” said Arthur, his voice low and tense as he put a supportive hand on Halliday’s back. “Help a layman out. What does that mean?”

  “There’s a…a problem, in mathematics,” I said. “It’s called the P versus NP problem. What do you know about complexity classes?”

  “Nothing,” said Arthur.

  I closed my eyes. It felt absurd, somehow, that the world was ending and I had to stop and explain why. Absurd and surreal. “We can categorize problems according to how difficult they are computationally,” I said. “Any problem in the set we call ‘P’ is something that can be quickly solved. We say ‘quickly’—meaning we can solve it in polynomial time on a deterministic Turing machine, but don’t worry about that. Any problem in NP is something that, if we have a solution, we can verify that solution quickly—but we wouldn’t necessarily know how to solve it quickly.” I tried to steady my voice. “It’s like if you have the solution to a maze, you can walk through that maze and make sure the solution works. But if you’re trying to find the solution, it’s a lot more difficult.”

  “Okay,” Arthur said. “So, P problems you can solve quick, NP problems not so much. Yeah?”

  “Well, so we thought,” I said. “We’ve never—mathematics has never,” I corrected, too loudly, “been able to prove, one way or another, whether P equals NP, or whether they aren’t equal, or whether it’s something that’s impossible to prove at all. It’s been one o
f the biggest unsolved problems in mathematics. Possibly the biggest—the question of whether anything we can quickly verify, we can also quickly solve.”

  “Okay,” Arthur said again. “So?”

  “So, most people figured P didn’t equal NP. We’d never been able to find a way to solve an NP-complete problem fast. Our whole understanding of the world…” I couldn’t explain.

  “My proof threatened the economy,” Halliday managed hoarsely. “This proof, Rita’s proof—it could do so much more. It would revolutionize. Logistics, protein folding—everything would suddenly become easy. And encryption—” She made a choked sound. “A lot of encryption works because once you have the code, you have access. Which means once you have the answer…you can verify it, very fast.”

  “And if P equals NP, finding that code is as easy as having it already and checking you’re right?” said Arthur. He let out a low whistle.

  “It’s possible there’s a big enough constant in her reduction to prevent that, but the proof’s clearly constructive. She seems to have found an algorithm…” Halliday trailed off.

  “Professor, even you aren’t getting this.” I spread my hands. “P equaling NP, it doesn’t just mean we can visit a bunch of cities quickly or break codes. It would mean any problem, any one we can put into numbers, would be near-instantly solvable. By anyone. We’re talking—we’re talking an overnight ballooning of technology into science fiction; we’re talking all of society going haywire, the basic functions of how we interact dissolving—”

  “Implementation would still take some innovation; it wouldn’t quite happen overnight,” Halliday interjected, her voice firming up as she focused on the theory. “Even with a constructive proof, we’d have to translate the mathematics into programming. But, um—yes. Yes, I…I think you’re right.”

  “Wait, you saying she’s right about society dissolving? From one math problem?” Arthur said. “How? Ain’t matter what Martinez found, the world’s the same place, right?”

  “This one math problem rewrites our understanding of literally everything,” I said. “We can’t imagine what it might do. Everybody would suddenly be able to use a cheap desktop computer to find out—to find out anything. Science, medicine, economics, society—all the rules would get thrown out the window overnight, and when that happened…Arthur, I’m not exaggerating. Every piece of civilization might have to be reframed. Possibly rebuilt.”

  “Rita thought so, too,” Halliday said. “Her note—it makes so much sense now.”

  I’d forgotten about the note. Halliday took it out of her pocket, uncreased it in the circle of the penlight. “‘The world is dust,’” she read. “‘I made mathematics dust, your mathematics, our mathematics’—I thought she was referring to destroying my notes—”

  “Keep reading,” I said.

  “‘I cannot break the world. I cannot let you live in the world I see. It is too barren, too empty. No place for any mathematician. Particularly not for you, Sonya.’”

  The words took on new meaning. “She wasn’t talking about the economy collapsing,” I breathed. “She was talking about just the prospect of knowing the reduction from NP to P, because—” My breath caught. I hadn’t realized. How had I not realized?

  “What?” said Arthur.

  “Her proof would make mathematicians obsolete,” I said. “Theorem-solving software—right now we can’t replicate the—the creative, the analytical leaps a human mathematician makes…” I was glad Checker wasn’t here at the moment. I would be too transparent in front of him. “But what we can do, if we put it in a proper logical language—”

  “We can verify a proof is correct,” said Halliday. “We can do that already, Arthur. And if Rita’s proof checks out, if we can verify—”

  “We can solve,” I said.

  If we could understand, we could create.

  Those mathematical leaps of intuition would no longer be mysterious. No longer be something unquantifiable and out of my reach. Because I wouldn’t need them anymore. Martinez’s proof might break the world, but it would also let me do math again.

  Holy God. I had to find Martinez. We would find her, and I would make her tell me.

  “She was trying to protect me,” said Halliday, still staring fixedly at the note. “Mathematics is…it’s everything to us. If a computer can replicate what we do, if there’s nothing special about human mathematical intuition…” I couldn’t see her face in the darkness. “She must have thought something in my own proof was getting close, that it was leading toward the breakthrough for hers. I—I think she overestimated me, as I don’t see how, but…”

  “So let me get this straight,” said Arthur. “She works this out, then she suddenly cottons on to what it means, so she destroys it?”

  “She thought she was saving the world,” Halliday said. “Maybe she was.”

  “But what’s to stop someone else from coming along and finding out the same thing?” Arthur asked. “If it’s true, someone’s gotta find it eventually—”

  “You don’t understand,” I said. I’d started to feel dizzy. “People have been trying to solve this problem forever. There’s a million-dollar prize for it, and that’s not even the reason everyone’s so obsessed. But nobody’s ever gotten close, and some mathematicians even started to suspect it couldn’t be solved at all. What Martinez came up with—it might well be hundreds of years before someone else thinks of the same breakthrough, if ever. Unless there really was something in your factoring proof,” I added to Halliday. “You two did work together; maybe something you used was the jumping-off point for her. It sounds like she was afraid you’d get there the same way.”

  “I don’t know what she might have been thinking of,” Halliday answered haplessly. “Rita sometimes—she thought too well of me. She was the type of person who could make me feel slow. She would always expect I would make the leap with her, and I would have to ask her to go back, to explain—” She gave a humorless laugh. “I’m one of the top handful of people in my field, and she made me feel like a child sometimes. Often. It nearly gave me a complex.”

  “It’s okay,” I said. “We won’t need to jump off your proof, because we’re not going to give up until we find her.” Figuring out the context of Martinez’s note had given me an idea. A brilliant idea. If there was one thing in the world that might be as important to Martinez as her proof, it was Sonya Halliday. “We know she cares for you, Professor, in her, uh, in her own way. We can use that to lure her out. We fake some trouble for you, make it seem like you need her.” I was gaining steam. This would work; I knew it would. “Or spread the word that you’re sick, or that you died, if you think she’d be sentimental enough to come out of hiding for that.”

  “May God protect her,” murmured Halliday. “What will the NSA do to her, if they find out?”

  “Sounds like we’re talking major national security stuff,” said Arthur. “Ain’t know what they would think.”

  “Well, we’ll find her first,” I said. “And we can decide whether to hand her over or just make her cough up the proof. What she wrote to you, Professor—she was trying to save you. You’ll be our way in.”

  “No.”

  I turned sharply to Halliday. “What?”

  She’d clicked off the light, leaving only her silhouette visible in the darkness. “I don’t want to go after her. Let her go.”

  “What? What the fuck are you on?” I exploded, so harshly Arthur winced. “This is P versus NP! This is it! It’s everything! It’s—”

  “And Rita made her decision.” Halliday took a breath. “It was clearly a decision she did not undertake lightly.”

  “How can you let her—she screwed you over! She stole all your work. At the very least, don’t you still want it back?” If Halliday wouldn’t help—

  “Well, she burned it, didn’t she?” Halliday’s voice had a caustic bite to it. “So whether or not we find her, it’s already gone. I could rewrite the factoring proof again now, thanks to y
ou. The rest, her papers—those were hers to destroy.”

  “And you’re just going to accept that?” I couldn’t believe what I was hearing. This had to be impulsiveness, the madness of a moment—Halliday would come around, she would see—“Your friend Dr. Zhang was right. This is too big to be left to one person’s whims, especially when that one person is a senile old lady!”

  Halliday sniffed, hard, but when she spoke her voice was steady. “Rita was as sharp as ever. And she wanted to solve the P versus NP problem more than anything in her entire life. If the knowledge terrified her this much…” The dark shapes of her hands tightened on the papers she held, crumpling them. “I have to trust her.”

  “No,” I said. “You really, really don’t.”

  “Then let me rephrase. I’m choosing to trust her. If she says this broke the world for her, if she says she was only trying to protect me—”

  “You’re not making any sense!” I cried. “If her proof was valid, then P equaling NP is true whether or not you’ve seen the reduction. Besides, how could you not want to know? Her emotional response is immaterial—for Christ’s sake, the Pythagoras cult thought irrational numbers were demonic and refused to accept them; that doesn’t mean—” I stuttered, out of words, out of ways to explain. “This isn’t right, what she’s doing. The world should know. Even if all you do is turn it over to the NSA, the knowledge should be out there. You can’t just delete it from the world; it’s wrong!”

  But I didn’t care about the world, if I was honest with myself.

  I needed this proof.

  Without it, I was nothing. With it, with the algorithm Rita Martinez claimed she had…I could discover any result, make mathematics unfurl before me, answer the most profound questions in the universe.

  With it, I could do real math.

  And that was all that fucking mattered.

  “Arthur, talk some sense into her,” I said, desperate and no longer caring. We’d already tried everything else to find Martinez. Now we’d caught on that the best and maybe the only thing we could use to lure her out was Halliday herself, and we knew what she had, and Halliday was saying no?