What comes first theory or practice? Its Complicated!

Having majored in pure math I had the impression that usually the theory comes first and then someone works out something to work in practice. While this is true sometimes it is often NOT true and this will not surprise any of my blog readers.  Even so, I want to tell you about some times it surprised me. This says more about my ignorance than about math or applications or whatnot.

1) Quantum

a) Factoring was proven to be in BQP way before actual quantum computers could do this in reasonable time (we're still waiting).

b) Quantum Crypto- This really is out there. I do not know what came first, the theory or the practice. Or if they were in tandem.

c) (this one is the inspiration for the post)  When I first heard the term Quantum Supremacy I thought it meant the desire for a THEOREM that problem A is in BQP but is provably not in P.  For example, if someone proved factoring is not in P (unlikely this will be proven, and hey- maybe  factoring is in P). Perhaps some contrived problem like those constructed by diagonalization (my spell checker thinks that's not a word. Having worked in computability theory, I think it is. Darn- my spellchecker thinks computability is not word.) Hence when I heard that Google had a paper proving Quantum Supremacy (I do not recall if I actually heard the word  proven) I assumed that there was some theoretical breakthrough. I was surprised and not in the slightest disappointed to find out it involved actual quantum computers.

Question: When the term Quantum Supremacy was first coined, did they mean theoretical, or IRL, or both?

2) Ramsey Theory

a) For Ramsey's Theorem and Van Der waerden's theorem and Rado's theorem and others I could name, first a theorem showed a upper bound on a number, then later computers and perhaps some math got better bounds on that number.

b) Consider the following statement:

For all c there exists P such that for all c-colorings of {1,...,P} there exists x,y,z the same color such that x² +y² = z².

Ronald Graham conjectured the c=2 case and offered $100 in the 1980's. (I do not know if he had any comment on the general case.)  I assumed that it would be proven with ginormous bounds on the P(c) function, and then perhaps some reasonable bound would be found by clever programming and some math. (see here for the Wikipedia Entry about the problem, which also has pointers to other material).

Instead the c=2 case was proven with an exact bound, P(2)=7825, by a computer program, in 2016. The proof is 200 terabytes. So my prediction was incorrect.

As for the result

PRO: We know the result is true for c=2 and we even know the exact bound. Wow! and for Ramsey Theory its unusual to have exact bounds!

CON: It would be good to have a human-readable proof. This is NOT an anti-technology statement. For one thing, a human-readable proof might help us get the result for c=3 and beyond.

3) This item is a cheat in that I knew the empirical results first. However, I will tell you what I am sure I would have thought (and been wrong) had I not know them.

Given k, does the equation


x³ +y³ +z³ = k

have a solution in Z? I would have thought that some hard number theory would determine
for which k it has a solution (with a proof that does not give the actual solutions)  and for then a computer programs would try to find the solutions. Instead (1) some values of k are ruled out by simple mod considerations, and (2) as for the rest, computers have found solutions for some of them. Lipton-Regan (here) and Gasarch (here) have blogged about the k=33 case. Lipton-Regan also comment on the more recent k=42 case.