x3 + y3 + z3 = 33 has a solution in Z. And its big!

Consider the following problem:

Given k, a natural number, determine if there exists x,y,z INTEGERS such that x³+y³+z³=k.

It is not obvious that this problem is decidable (I think it is but have not been able to find an exact statement to that affect; however, if it was not solvable, I would know that, hence it is solvable. If you know a ref give it in the comments.)


If k≡ 4,5 mod 9 then mod arguments easily show there is no solution. Huisman showed that if k≤ 1000, k≡1,2,3,6,7,8 mod 9 and max(|x|,|y|,|z|) ≤ 10¹⁵ and k is NOT one of

33, 42, 114, 165, 390, 579, 627, 633, 732, 795, 906, 921, 975

then there was a solution. For those on the list it was unknown.

Recently Booker (not Cory Booker, the candidate for prez, but Andrew Booker who I assume is a math-computer science person and is not running for prez) showed that

x³ + y³ + z³ =33

DOES have a solution in INTEGERS. It is

x= 8,866,128,975,287,528

y=-8,778,405,442,862,239

z=-2,736,111,468,807,040


does that make us more likely or less likely to think that

x³ + y³ + z³ =42

has a solution? How about =114, etc, the others on the list?

Rather than say what I think is true (I have no idea) here is what I HOPE is true: that the resolution of these problems leads to some mathematics of interest.

Geo-Centric Complexity

An interesting discussion during Dagstuhl last month about the US-centric view of theory. Bad enough that all talks and papers in an international venue are in English but we also have

• Manhattan Distance. How are foreigners supposed to know about the structure of streets in New York? What's wrong with grid distance?
• Las Vegas Algorithms. I found this one a little unfair, after all Monte Carlo algorithms came first. Still today might not Macau algorithms make sense?
• Arthur-Merlin Games. A British reference by a Hungarian living in the US (László Babai who also coined Las Vegas algorithms). Still the Chinese might not know the fables. Glad the Europeans don't remember the Pat and Vanna terminology I used in my first STOC talk. 
• Alice and Bob. The famous pair of cryptographers but how generically American can you get. Why not Amare and Bhati?

I have two minds here. We shouldn't alienate or confuse those who didn't grow up in an Anglo-American culture. On the other hand, I hate to have to try and make all terminology culturally neutral, you'd just end up with technical and ugly names, like P and NP.

Quiz Show Scandals/Admissions Scandal/Stormy Daniels/Beer names:being a lawyer would drive me nuts!!!!!!

0) Charles van Doren (see here) passed away recently. For those who don't know he he was (prob most of you) he was one of the contestants involved in RIGGED quiz shows in the 1950's.  While there was a Grand Jury Hearing about Quiz Shows being rigged, nobody went to jail since TV was new and it was not clear if rigging quiz shows was illegal. Laws were then passed to make them it illegal.

So why are today's so-called reality shows legal? I ask non-rhetorically.

(The person he beat in a rigged game show- Herb Stempel (see here) is still alive.)

1) The college admissions scandal. I won't restate the details and how awful it is since you can get that elsewhere and I doubt I can add much to it.  One thing I've heard in the discussions about it is a question that is often posted rhetorically but I want to pose for real:

There are people whose parents give X dollars to a school and they get admitted even though they are not qualified. Why is that legal?

I ask that question without an ax to grind and without anger. Why is out-right bribery of this sort legal?

Possibilities:

a) Its transparent. So being honest about bribery makes it okay?

b) My question said `even though they are not qualified' - what if they explicitly or implicitly said `having parents give money to our school is one of our qualifications'

c) The money they give is used to fund scholarships for students who can't afford to go. This is an argument for why its not immoral, not why its not illegal.

But here is my question: Really, what is the legal issue here? It still seems like bribery.

2) Big Oil gives money to congressman Smith, who then votes against a carbon tax. This seems like outright bribery

Caveat:

a) If Congressman Smith is normally a anti-regulation then he could say correctly that he was given the money because they agree with his general philosophy, so it's  not bribery.

b) If Congressman smith is normally pro-environment and has no problem with voting for taxes then perhaps it is bribery.

3) John Edwards a while back and Donald Trump now are claiming (not quite) that the money used to pay off their mistress to be quiet is NOT a campaign contribution, but was to keep the affair from his wife. (I don't think Donald Trump has admitted the affair so its harder to know what his defense is). But lets take a less controversial example of `what is a campaign contribution'

I throw a party for my wife's 50th birthday and I invite Beto O'Rourke and many voters and some Dem party big-wigs to the party. The party costs me $50,000.  While I claim it's for my wife's bday it really is for Beto to make connections to voters and others. So is that a campaign contribution?

4) The creators of HUGE ASS BEER are suing GIANT ASS BEER for trademark infringement. I am not making this up- see here

---------------------------------------------------------

All of these cases involve ill defined questions (e.g., `what is a bribe'). And the people arguing either side are not unbiased. The cases also illustrate why I prefer mathematics: nice clean questions that (for the most part) have answers. We may have our biases as to which way they go, but if it went the other way we would not sue in a court of law.

Physics of Everday Life

Based on Scott's review, I read through Stephen Pinker's Enlightenment Now. I can't top Scott's exposition of the book, but it is pretty incredible how far humanity has gone when you step back to look at the big picture.

One line intrigued me, one that Pinker credits to a book called The Big Picture by Sean Carroll

The laws of physics underlying everyday life (that is excluding extreme values of energy and gravitation like black holes, dark matter and the Big Bang) are completely known.

Hasn't this statement almost always been true, in the sense that the leading minds would make this claim at many times in history. The ancient Greeks probably believed they understood physics that underlies everyday life. So did physicists after Newton. Life back then not today. My everyday life involves using a GPS device that requires understanding relativistic effects and computer chips that needed other scientific advances.

Is it possible we could do more in everyday life if we knew more physics? I'd certainly use a teleporter in everyday life.

And is the statement even true today? We all use public key cryptography, even to read this blog. It's not completely clear if we understand the physics enough to know how or if large-scale quantum computers capable of breaking those systems can be built.

Everday life is relative.

Good article, terrible headline

About a month ago (after my P NP poll appeared) I got email from Jacob Aron asking me some questions about it. One thing he was excited about was that the number of people who thought P vs NP would be solved in the next decade had increased from 11% to 22%. I told him that this also surprised me and there had been no major advances to warrant that increase.

Then the article came out. Here is the pointer to the headline and the first few lines, the rest is behind a paywall

here

You may notice that the headline is

We could solve the biggest problem in math in the next decade

I emailed Jacob to send me the article, which he did. The article was fine, even quoting me as saying that the increase of people who thought it would be solved soon was unwarranted.

1) So, article fine, headline terrible.

2)  A more honest headline would be

The Complexity Theory Community slightly more optimistic about when P vs NP will be resolved for no apparent reason.

3) More bad science:here

Headline is

Turing's Oracle: The computer that goes beyond logic

I think the article was about how a Turing Machine with an oracle for HALT can solve HALT. (If I am wrong about this let me know in the comments and I'll correct it.)

4) More bad science:here

Headline

Finally, a problem that only Quantum Computers will ever be able to solve.

This was about the oracle such that BQP is not in PH. Really!

5) I invite you to add your own.

6) OKAY, so why is the press SO BAD at reporting on our field? And is it just our field? I have one explanation, though I am sure there are many.

Our field is about showing the LIMITS of computation. Its hard to make that sexy so they ... lie? exaggerate. They themselves don't really understand our field? Note:

To explain to someone who does not really know CS why its important to have an oracle where BQP is not in PH is hard

To explain this to someone IN CS but not in Theory is still hard!

To explain this to someone IN CS and even in CS Theory, but not complexity (e.g., algorithms) might be hard, though it may depend on the person.

7) The old saying is `I don't care if you get the story wrong so long as you spell my name right' And indeed, they did spell my name right. So there is that! But more seriously and less about me or even the article that refers to my poll--- is it bad that science reporting is often wrong?

Elwyn Berlekamp Died April 9, 2019

Elwyn R. Berlekamp entered this world on Sept 6, 1940, and left it on April 9, 2019.  Wikipedia calls him An American Mathematician which seems to narrow to me. He worked on a variety of topics which were Math, Comp Sci, finance, and likely others --- if you know any that I missed leave comments.

Here are some of the things he worked on:

1) Factoring Polynomials over large finite fields (See here from 1970)

I quote the abstract

This paper reviews some of the known algorithms for factoring polynomials over finite fields and presents a new deterministic procedure for reducing the problem of factoring an arbitrary polynomial over the Galois field GP(p^m) to the problem of finding roots in GF(p) of certain other polynomials over GP(p). The amount of computation and the storage space required by these algorithms are algebraic in both the degree of the polynomial to be factored and the log of the order of the field.

Certain observations on the application of these methods to factorization of polynomials over the rational integers are also included. 

I think he meant what we would call polynomial time when he says algebraic.

2) Combinatorial Games. He co-wrote the classic Winning Ways For your Mathematical Plays with John Conway and Richard Guy.  These books are like NIM on steroids. They are FUN and have some serious math in them. (My blog system thinks Combinatorial is not a word. It is wrong)

3) Combinatorial Games. He was very interested in Go via Combinatorial Games. I have an article (alas, not online) by him entitled Introductory Overview of Mathematical Go Endgames.  There has been further work on this that is on the web, see here. I wonder what ERB would think of the ALPHAGO program.

4) Berlekamp-Massey Algorithm finds the shortest linear feedback shift register for a given binary output sequence.

5) Berlekamp-Welch Algorithm efficiently corrects errors in Reed-Solomon codes.  (Berlekamp also wrote a book on Algebraic Coding Theory.)

6) I didn't know about his work in finance until I began writing this, but the following quote from Wikipedia is impressive

In 1989, Berlekamp purchased the largest interest in a trading company named Axcom Trading Advisors. After the firm's futures trading algorithms were rewritten, Axcom's Medallion Fund had a return (in 1990) of 55%, net of all management fees and transaction costs. The fund has subsequently continued to realize annualized returns exceeding 30% under management by James Harris Simons and his Renaissance Technologies Corporation.

Problems with a point- NOT a plug, just some thoughts on books and book writing

Problems with a Point: Exploring Math and Computer Science by Gasarch and Kruskal, available on amazon here, came out a while back  and I plugged it in my  blog post here. Regan-Lipton reviewed it here.

This post is NOT a plug, its random points about the book and book writing

1) On Feb 28 I checked my Amazon ranking twice. At noon it was at 400,000 and at 4:00PM it was at  roughly 80,000.  Either (a) someone bought a copy, or (b) the number of sales of such books is so small that amazon does rankings arbitrarily. A counter argument to that: Bounded Queries in Recursion Theory, which I wrote in 1998 and, despite an awesome review on amazon that I wrote,  sold literally 0 copies last year, is ranked 5,000,000. So even within the low numbers there is SOME logic to the rankings. (Update- Today, April 7, PWAP is at 800,000 and BQIRT is at 12,000,000. I suspect that nothing has changed with BQIRT and the 5,000,000 or 12,000,000 is arbitrary. As for PWAP--- since its still a new book the ranking might mean something. Oh well- fame is fleeting!)

1.5) At one time my book was 29th in the category Teen and Young Adult Computer Programming. Really? While teens and young adults might read it, I don't think of it as geared towards them (only one use of  OMG and two uses of awesome  in the entire book). And as for Computer Programming... uh... no.

2) I emailed many people about it and many people are buying it. Some tell me that the cover looks great so YES, they are judging a book by its cover. My mom asked how it was selling. I told her that (a) about 20 people told me they bought it, and (b) I doubt that's how JK Rowling responds when she's asked how her Harry Potter books are selling.

3) Many people could actually read this book and would care about its content. When I wrote Bounded Queries in Recursion Theory (with Georgia Martin) I didn't email a lot of people about it since it was rather specialized.

4) Some people said `Gee bill, we didn't know you were working on a book'. That's true- I didn't talk about it much. Clyde knew (my co-author, so he had  to know), Lance knew. Darling knew. Mom Knew. That might be about it. Why so few? see next point.

5) I had heard there are two kinds of people:

Those that talk about writing a book but don't do it

Those that write a book instead of talking about it.

I chose to be the second type.

6) When I got an advanced copy I couldn't stop reading it. Ego? Disbelieve? Some of each?

7) ADVICE for book writers: just get it done. You can polish it later but first get it done so you have something to polish.

8) More advice: You can never have too many proofreaders. Even though its been gone over a lot I still read it and find minor things to fix OR think `gee why didn't I include BLAH in the book'

9) Title: `Problems with a Point' I came up with very early and I liked it a lot. World Scientific (our publisher) pointed out, correctly, that we need a subtitle since  PWAP didn't really tell the reader whats in it. I wanted to make it alliterative but it was hard. Here were some possibilities

PWAP: Mathematical Musing Made Magnificent (can replace Musings with Morsels)

PWAP: Mathematical Meditations  and Computer Science Cogitations

PWAP: Mathematical Musings and the Math that Makes those Musings Matter

All in all I am happy with the non-alliterative, but informative

PWAP: Exploring Math and Computer Science.

10) Odd thing I learned- if I quote someone who made a comment on my blog or emailed me I needed permission. Actually I doubt I NEEDED it but the laws here are murky so I got it just to make sure. That explains this blog from a while back: here

11) ADVICE for book writers: Write the preface last since then you have a better idea of why you wrote the book.

Cuckoo Cycles

Guest Blog by John Tromp (Thanks for the opportunity, Lance)

In the past few months, cycle finding has become one of the most widely run graph theory problems. An estimated quarter-to-half million GPUs are constantly looking for 42-cycles in random bipartite graphs on a billion or more nodes. Customized chips have been designed to perform this specific application an order of magnitude more efficiently, thanks to integrating as much as 1GB of SRAM on a single chip, where Intel/AMD CPUs top out at 64 MB.

The purpose of all this? To compete for block rewards in various cryptocurrencies using the Cuckoo Cycle Proof of Work.

It is named after the Cuckoo Hashtable, in which each data item can be stored at two possible locations, one in each of two arrays. A hash function maps the pair of item and choice of array to its location in that array. When a newly stored item finds both its locations already occupied, one is kicked out and replaced by the new item. This forces the kicked-out item to move to its alternate location, possibly kicking out yet another item. Problems arise if the corresponding Cuckoo graph, a bipartite graph with array locations as nodes and item location pairs as edges, has cycles. While n items, whose edges form a cycle, could barely be stored in the table, any n+1st item mapping within the same set of locations (a chord in the cycle) would not fit, as the pigeonhole principle tells us.
In the Proof-of-Work problem, we typically set n ≥ 29, and use edge indices (items) 0 .. N-1, where N = 2ⁿ. The endpoints of edge i are (siphash(i|0) % N, siphash(i|1) % N), with siphash being a popular keyed hash function. A solution is a cycle of length L in this Cuckoo graph, where typically L = 42.

While looking for cycles takes a lot of time and memory, solutions can be instantly verified. This sets Cuckoo Cycle apart from many other memory hard proofs of work that require computing a memory hard hash function, such as scrypt, both for proving and verifying. Some luck is also required to find a 42-cycle; Slides 18 and 19 of this Grincon.US presentation sketch a proof of the

Cuckoo Cycle Theorem: The expected number of L-cycles tends to 1/L

While there is a known linear time-memory trade-off, it suffers from a large constant factor penalty. A large bounty is offered on the project webpage for better trade-offs.

Cuckoo Cycle solvers spend nearly all cycles on edge trimming; identifying and removing edges that end in a leaf node (of degree 1), as such edges cannot be part of a cycle. Trimming rounds alternate between the two node partitions. This can be done using N bits for the edge bitmap, and N log₂(3) bits for the (truncated) node degrees. The random accesses to the latter, while not a problem for custom chips using enough SRAM, cause large memory latencies on commodity hardware. These can be mostly avoided by storing remaining edges explicitly and (bucket) sorting them to determine node degrees. Despite using an order of magnitude more memory than the edge bitmap, this is still over 4x faster.

The fraction f_i of remaining edges after i trimming rounds (in the limit as N goes to infinity) appears to obey the

Cuckoo Cycle Conjecture: f_i = a_i-1 * a_i, where a_-1 = a₀ = 1, and a_i+1 = 1 - e^-a_i

f_i could equivalently be defined as the fraction of edges whose first endpoint is the middle of a (not necessarily simple) path of length 2i.

So far I have only been able to prove the conjecture for i ≤ 3. For instance, for i = 1, the probability that an edge endpoint is not the endpoint of any other edge is (1-1/N)^N-1 ~ 1/e. Here's hoping someone finds an elegant proof...

An Interdisciplinary approach to P vs NP

I have a grant with some brain scientists on the following exciting approach to P vs NP.

We want to prove:

                               There is no algorithm for SAT in P

This seems hard.  So lets scale down our goals to:

                              Lance cannot find an algorithm for SAT in P

You can replace Lance with someone else, but Lance has volunteered to have brain scans done. The idea is to scan the P vs NP part of his brain and see what we can discern.

I know what you are thinking. Lance truly believes that SAT is NOT in P so perhaps even if SAT is in P, he would have a mental block. Hence I am hoping to also get some serious theorists that think SAT is in P to participate.  This might also shed light on the following conjecture:  is it easier to prove a theorem if you believe it is true.

Lance has proposed another line of research. Barriers. Try to establish

                             Lance cannot prove that SAT is NOT in P

using brain scans and he volunteered.

Brain Scan of Lance's Proving Ability

For this one the mental block problem is gone; however,   as you can clearly see from his brain scan, Lance will never prove that SAT is not in P. Seven years as department chair has caused irreversible damage to his ability to reason logically.

We hope to recruit other theorists to the project. The sticking point might be privacy: if we prove that professor X cannot solve P vs NP will the affect their being hired? For this reason we will restrict the study to professors with Tenure. But this is a weakness of the study since we had wanted to study if younger people have a better chance to resolve P vs NP.  So we need to find very young tenured professors.

After we get the technology working on Theorists and P vs NP we will try to expand it for home use. For example, if a spouse claims I could never learn to cook or I could never learn to drive (that's me) their partner  will be able to verify the statement. It is not clear if this will make the divorce rate go up or down. Or if a child says I just can't do algebra the parents can test the child and say Oh yes you can!