Sunday, September 27, 2020

A Quote from Tesla which is very predictive in one way, and perhaps not in another way

Nikola Tesla, famous inventor, who lived 1856--1943 said the following:

When wireless is perfectly applied the whole earth will be converted into

a huge brain, which in fact it is, all things being particles of a real

and rhythmic whole. We shall be able to communicate with one another

instantly, irrespective of distance. Not only this but through television

and telephony, we shall see and hear one another as perfectly as though

we were face to face, despite intervening distances of thousands of miles;

and the instruments through which we shall be able to do this will be

amazingly simple compared with our present telephone. A man will be able to

carry one in his vest pocket.

The vest pocket' at the end really impressed me.

By a man will be able to carry one...' I don't know if he mean all people or if he actually

meant that women would not need such a device. If that is what he meant then,

while high marks for tech-prediction, low marks for social-prediction.

This quote is SO right-on for technology that I offer the following challenge: Find other quotes from year X that were very predictive for year X+Y for a reasonably large Y.

1) On the TV show THE HONEYMOONERS, in 1955, Ralph Cramden predicts 3-Dim TV. I blogged about that here

2) Did the TV show Get Smart foreshadow cell phones. Maxwell Smart's shoe-phone was portable but wearing it on his foot seems odd. It also used dial, not touch tone. Mel Brooks (co-creator of the series) points out that in the Pilot episode Max is enjoying a show and his phone goes off so he has to leave and take the call -- which was very strange then but standard now. So the show did predict one of the problems with cell phones, if not cell phones themselves.

Wednesday, September 23, 2020

Remembering 2000

FOCS 2000 took place in Redondo Beach, just south of Los Angeles, November 12-14. Certainly some great results such as the Reingold-Vadhan-Wigderson Zig-Zag Graph Product Expander construction that would lead to Omer Reingold's Undirected Connectivity in Log Space. Mostly though I remember the discussions about the presidential election held the week before and whether we might find out our next president during the conference. Spoiler alert: We didn't

Consider the following viewpoints for a person X

1. Did X support Bush or Gore?

2. Did X interpret the rules of the election that Bush won or Gore won?

These should be independent events. Your interpretation of the rules should not depend on who you supported. But in fact they were nearly perfectly correlated. Whether you were a politician, a newspaper editorial page writer, a supreme court justice, a computer scientist or pretty much everyone else, if you supported Gore, you believed he won the election and vice-versa. Everyone had their logic why they were right and I'm sure my readers who remember that election still believe their logic was correct.

As this upcoming election gets messy, as it already has, take care with trying to justify your desired endgame by choosing the logic that makes it work. Would you use the same logic if the candidates were reversed? Everyone says "yes" but it's rarely true. Just like Mitch McConnell, you'll just find some excuse why the opposite situation is different. Trust me, my logic is impeccable.

Sunday, September 20, 2020

Baseball can go on forever, it doesn't just seem that way

Most games have some way to make sure they cannot go on forever.

1) Chess: I had thought there was a 50-move rule and a 3-times-same-position rule, but its a byte more complicated than that, see here. There is also a chess clock. Suffice to say, Chess can never on forever (though it may seem like it does).

2) NIM: Eventually all of the stones are gone. There may be more complicated versions where you can add some stones, but in those versions I suspect that there is some parameter that goes to 0.

3) Basketball, Football, Hockey, Soccer: These all have a clock so they are time limited. For overtime there are also rules that make sure the game cannot go on forever. Or maybe its just very rare: what if the Superb Owl (spelled that way to avoid lawsuits, see here) is tied 0-0 at the end of the four quarters and goes into overtime and... nobody scores... ever. Could the game go on forever or would the referees declare it a tie? In the regular season there are ties, but in the in the superb owl? Actually this may be more a problem in the playoffs since you need to determine who goes to the next round.

4) Take your favorite game. I would bet dollars to doughnuts (what an odd phrase---see here for more about the phrase) that there is some mechanism to make sure the game ends. An exception that Darling pointed out to me: If in Gin Rummy both players are terrible then the game can go on forever. This is probably true for other games as well and actually makes the question into two questions (a) will a game terminate no matter what the players do, and (b) (not sure how to formalize) will a game terminate if both players are trying to win and are making reasonable moves.

You may have noticed that in item 3 I left out Baseball. There is no clock in baseball. So one way the game can go on forever is to have a tie and extra innings and nobody scores. I think the umpire has the authority to call it a tie. (Incidentally, the shortened baseball season has a new extra inning rule---each inning starts with a runner on second. See here,) When Lance read an earlier version of this post he pointed me to 5 ways a game can go on forever, not counting the example I have later in this post. Here is where Lance found the question and answer (look on the first page under Speed Department for the question, and the very end of the second page for the answer). I also did my own writuep with more details, see here.  Also of interest (though not if you were actually at the game this happened), the record for number of times a player has a foul with 2 strikes is 16, see here

However, I came across an  example more obscure than any of those.

Here is what happened (and you can see the video of it here, though it really starts about a minute into it. Keep reading- it looks like its another post, but its part of this post:

Back in 2008, the Yankees drafted a pitcher named Pat Venditte. What made Venditte unusual is that he can throw with both hands. In other words, he’s a switch pitcher. When he was drafted, he was assigned to the Staten Island Yankees, a low A ball team.

In his first game (against the Mets farm team, the Brooklyn Cyclones), Venditte came in to pitch. After getting the first two batters out and giving up a single, he then faced Ralph Henriquez, was a switch hitter. What happened next resembled an Abbott and Costello comedy routine. Venditte would put the glove on one hand (he had a specially made glove that could be worn on either hand) and Henriquez would then step across the plate to bat from the other side. Venditte would then switch his glove hand again and Henriquez went back to the other side.

Eventually, after much discussion, the umpires ruled that Henriquez would have to choose a batting side first, before Venditte had to commit. Henriquez was mad and, after he struck out, he slammed the bat against the ground in frustration.

The umpires were, in essence, winging it, because there was no rule to cover the situation. Eventually, the higher ups in baseball did write a rule to cover the situation — the opposite of the umpires’ decision.

Monday, September 14, 2020

An interesting serendipitous number

Last seek I blogged about two math problems of interest to me here.

One of them two people posted answers, which was great since I didn't know how to solve them and now I do. Yeah! I blogged about that here.

The other problem got no comments, so I suppose it was of interest to me but not others. I was interested in it because the story behind it is interesting, and the answer is interesting.

it is from the paper

An interesting and serendipitous number by John Ewing and Ciprian Foias, which is a chapter in the wonderful book

Finite vs Infinite: Contributions to an eternal dilemma

Here is the story, I paraphrase the article (I'll give pointers  later).

In the mid 1970's a student asked Ciprian about the following math-competition problem:

x(1)>0    x(n+1) =  (1 + (1/x(n)))^n. For which x(1) does x(n) --> infinity?

It turned out this was a misprint. The actual problem was

x(1)>0  x(n+1)=(1+(1/x(n))^{x(n)}. For which x(1) does x(n) --> infinity.

The actual math-comp problem  (with exp x(n)) is fairly easy (I leave it to you.) But this left the misprinted problem (with exp n).  Crispian proved that there is exactly ONE x(1) such that x(n)--> infinity.

Its approx 1.187... and may be trans.

I find the story and the result interesting, but the proof is to long for a blog post.

I tried to find the article online and could not. A colleague found the following:

A preview of the start of the article here

Mathworld page on that number here

Most of the article but skips two pages here

Thursday, September 10, 2020

When are both x^2+3y and y^2+3x both squares, and a more general question

In my last post (see here) I asked two math questions. In this post I discuss one of them. (I will discuss the other one later, probably Monday Sept 14.)

For which positive naturals x,y are x^2+3y and y^2+3x both squares?

I found this in a math contest book and could not solve it, so I posted it to see what my readers would come up with. They came up with two solutions, which you can either read in the comments on that post OR read my write up here.)

The problem raises two more general questions

1) I had grad student Daniel Smolyak write a program that showed that if  1\le x,y \le 1000 then the only solutions were (1,1) and (11,16) and (16,11).  (See write up for why the program did not have to look like anything close to all possibly (x,y).)

Is there some way to prove that if the only solutions for 1\le x,y\le N (some N) are the three given above, then there are no other solutions?

2) Is the following problem solvable: Given p,q in Z[x,y] determine if the number of a,b such that both p(a,b) and q(a,b) are squares is finite or infinite.  AND if finite then determine how many, or a bound on how many.

Can replace squares with other sets, but lets keep it simple for now.

Sunday, September 06, 2020

Two Math Problems of interest (at least to me)

I will give two math problems that are of interest to me.

These are not new problems, however you will have more fun if you work on them yourself and leave comments on what you find. So if you want to work on it without hints, don't read the comments.

1) Let x(1)>0. Let x(n+1) = (  1 + (1/x(n))  )^n.

For how many values of x(1) does this sequence go to infinity?

2) Find all (x,y) \in N \times N such that x^2+3y and y^2+3x are both squares.

Tuesday, September 01, 2020

A well known theorem that has not been written down- so I wrote it down- CLIQ is #P-complete

(The two proofs that CLIQ is #P-complete that I discuss in this blog are written up by Lance and myself and are here. I think both are well known but I have not been able to find a writeup,so Lance and I did one.)

I have been looking at #P (see my last blog on it it, here, for a refresher on this topic) since I will be teaching this topic in Spring 2021.  Recall

#SAT(\phi) = the number of satisfying assignments for phi

#CLIQ((G,k))= the number of cliques of size \ge k of G

#SAT is #P-complete by a cursory look at the proof of the Cook-Levin theorem.

A function is #P-complete if everything else in #P is Turing-Poly red to it. To show for some set A

in NP, #A is #P-complete one usually uses pars reductions.

I wanted a proof that #CLIQ is #P-complete, so I wanted a parsimonious reduction from SAT to CLIQ (Thats a reduction f: SAT--> CLIQ such that the number of satisfying assignments of phi equals the number of cliques of size \ge k of G.)

I was sure there is such a reduction and that it was well known and would be on the web someplace. So I tried to find it.

ONE:

I tracked some references to a paper by Janos Simon (see here)  where he claims that the reduction of SAT to CLIQ  by Karp (see here) was pars.  I had already considered that and decided that Karps reduction was NOT pars.  I looked at both Simon's paper and Karp's paper to make sure I wasn't missing something (e.g., I misunderstood what Simon Says or what Karp ... darn, I can't think of anything as good as Simon Says'). It seemed to me that Simon was incorrect. If I am wrong let me know.

TWO

Someone told me that it was in Valiant's  paper (see here). Nope. Valiant's paper shows that counting the number of maximal cliques is #P-complete. Same Deal Here- if I am wrong let me know. One can modify Valiant's argument to get #CLIQ #P-complete, and I do so in the write up. The proof is a string of reductions and starts with PERM is #P-complete. This does prove that# CLIQ is  #P-complete, but is rather complicated. Also, the reduction is not pars.

THREE
Lance told me an easy pars reduction that is similar to Karp's non-pars reduction, but it really is NOT Karp's reduction. Its in my write up. I think it is well known since I recall hearing it about 10 years ago. From Lance. Hmmm, maybe its just well known to Lance.

But here is my question: I am surprised I didn't find it on the web. If someone can point to a place on the web where it is, please let me know. In any case, its on the web NOW (my write up) so hopefully in the future someone else looking for it can find it.

Sunday, August 23, 2020

Sharp P and the issue of natural problems'

#P was defined by Valiant as a way to pin down that the PERMANENT of a matrix is hard to compute.

The definition I give is equivalent to the one Valiant gave.

g is in #P if there exists p a poly and B in P such that

g(x) = | { y : |y| = p(|x|) and (x,y) \in B } |

A function f is #P-complete if g is in #P and for all g in #P,  f is poly-Turing reducible to g.

#SAT is the function that, given a formula, returns the number of satisfying assignments. It is #P-complete by looking at the proof the Cook-Levin Theorem. The reduction of f to #SAT only makes one query to #SAT. A common way to show that #A is #P-complete is to show that SAT \le A with a reduction that preserves the number of solutions.

Valiant proved that PERM was #P-complete (his reduction only used 1 call to PERM).

There are problems in P whose #-version is #-P complete: Matching and DNF-SAT are two of them.

Notice that I defined #SAT directly, not in terms of a poly p and a set B as above. Here is why: if you use poly p and set B one can do obnoxious things like:

SAT = { phi : exists yz 2n-bits long such that phi(y)=T and z is prime }

The # version of this definition is not really what I want (though I am sure its #P-complete).

Valiant (see here and here) and Simon (see here) showed that  for many known NPC-problems A, #A is #P-complete. They meant NATURAL problems. Is it true for all natural NP-complete problems?

Unfortunately the statement All NATURAL NPC problems give rise to #P-complete functions' is hard (impossible?) to state rigorously and hence hard (impossible?) to prove.

1) Is there a natural A in NP such that #A is NOT #P-complete (under assumptions)?

2) Are there any theorems that show a large set of NPC problems have #P counterparts? Or are we doomed to, when we want to show some #A is #P-complete, come up with a new proof?

3) Can one PROVE there are NPC problems A such that #A is NOT #P-complete? (under assumptions).

Monday, August 17, 2020

Mathematics is not commutative

In my poll of P vs NP and other issues, one of the questions was

Is factoring in P?

One of the most interesting answers was

I don't really see why it shouldn't be. - Peter Shor

Recall that Peter Shor proved Factoring is in Quantum-P which lead to intense interest in Quantum Computing.

1) What if factoring was in P and this was shown before Shor's algorithm? Would Shor or someone else have ever proven factoring in quantum P? Would there be as much intense interest in quantum computing as there is now? Perhaps by physicists more than CS people?

2) What if factoring was in P and this was shown before RSA? Where would crypto be now? Zip drives with a googleplex random (or nearly random) bits and more 1-time pads? More lattice based crypto? Or RSA but with larger numbers? This may depend on how good the factoring algorithm is.

3) More generally, how much does the order of events matter for science?

a) If the Banach-Tarski paradox was discovered early on, would we have just tossed out the Axiom of Choice before so much more was build on it? Darling thinks we should toss out AC NOW because of Banach-Tarski.

b) In the model of set theory L you can do ALL of math except some parts of set theory and maybe a few other things (note quite: Harvey Friedman has found some combinatorial statements that need large cardinals to prove). Had L been discovered earlier then could we all now be working in L (except a few people who look at other models, but they are not in the mainstream)? We might know more about L and less about forcing. We would KNOW that AC and CH are true. Or we would think we know.

c) If  Engineers were the first ones to look at SAT and reductions, might they have been content to know that  if SAT \le A then A is probably hard? No need for the Cook-Levin Theorem! And then when someone proved Cook-Levin would the Engineers not really cares since they already knew SAT was hard?

d) I can imagine Ramsey's Theorem being discovered much later for some application, or perhaps never being discovered at all.

e) VDW's theorem has so few application, I can imagine it never being discovered.

4) There are cases where if A was discovered before B then B has an easy proof, whereas if B was discovered before A, then B has a hard proof. I'll give one example:

Given HALT is undecidable, Godel's theorem is easy.

Assume HALT is undecidable.

Let STAT(e) be the statement M_e(0) does not  halt.

There is some e such that M_e(0) does not halt  but ZFC cannot prove this.

PROOF: Assume, By Way of Contradiction that for all e such that M_e(0) does not halt,
ZFC could prove this. Then HALT is DECIDABLE:

Given e, run M_e(0) and at the same time enumerate all proofs in ZFC. It is guaranteed that
you will either find M_e(0) halts or a proof that M_e(0) does not halt. Hence you will,
in finite time, know if M_e(0) halts OR NOT.

END OF PROOF

Is the sequence of events where HALT is proven undecidable  before Godel's theorem plausible.
I  think so

I INVITE my readers to give there own examples of when Math is not commutative- meaning that
the order of events matters.

Thursday, August 13, 2020

Great news out of the Simons Institute.

Sunday, July 12, 2020

Ronald Graham: A summary of blog Posts We had about his work

To Honor Ronald Graham I summarize the blog posts we had about his work.

1) Blog post New Ramsey Result that will be hard to verify but Ronald Graham thinks its right which is good enough for me.

Wikipedia (see here) says that in the early 1980's (can't Wikipedia be more precise than that?) Ronald Graham conjectured the following:

For all 2-colorings of N, there exists x,y,z all the same color such that (x,y,z) form a Pythagorean triple.

I cannot imagine he did not also conjecture this to be true for all finite colorings.

I suspect that when he conjectured it, the outcomes thought to be likely were:

a) A purely combinatorial (my spell check says that combinatorial  is not a word. Really? It gets 14,000,000 hits) proof. Perhaps a difficult one. (I think Szemeredi's proof of his density theorem is a rather difficult but purely combinatorial proof).

b) A proof that uses advanced mathematics, like Roth's proof of the k=3 case of Sz-density, or Furstenberg's proof of Sz theorem.

c) The question stays open though with some progress over the years, like R(5).

What actually happened was

d) A SAT Solver solves it AND gets exact bounds:

For all 2-colorings of {1,...,7285} there is a mono Pythag triple.

There exists a 2-coloring of {1,...,7284} with no mono Pythag triple.

I wonder if this would have been guessed as the outcome back in the early 1980's.

-------------------------------------------------------------------------------
2) Blog Post Ronald Graham's Other Large Number- well it was large in 1964 anyway

Let

a(n) = a(n-1) + a(n-2)

I have not given a(0) and a(1). Does there exists rel prime values of a(0) and a(1) such that for all n, a(n) is composite.

In 1964 Ronald Graham showed yes, though the numbers he found (with the help of 1964-style computing) were

a(0) = 1786772701928802632268715130455793

a(1) = 2059683225053915111058164141686995

I suspect it is open to get smaller numbers, though I do not know.

------------------------------------------------------------------------------
3) Blog Post Solution to the reciprocals problem

Prove or disprove that there exists 10 natural numbers a,...,j such that

2011= a+ ... + j
1 = 1/a + ... + 1/j

I had pondered putting this on a HS math competition in 2011; however, the committee thought it was too hard. I blogged on the problem asking for solutions, seeing if there was one that a HS student could have gotten. The following post (this one) gave those solutions. My conclusion is that it could have been put on the competition, but its a close call.

So I wondered if there was a way to do this with distinct a,...,j.

I was told about Ronald Grahams result:

For all n at least 78, n can be written as the sum of DISTINCT naturals, where the sum of
the reciprocals is 1.

This is tight: 77 cannot be so written.

Comment on that blog DID include solutions  to my original problem with all distinct numbers

----------------------------------------------------------------------
4) Blog Post A nice case of interdisplanary research tells the story of how the study of history lead to R(5) being determined (see here for the actual paper on the subject). One of the main players in the story is the mathematician

Alma Grand-Rho.

Note that this is an anagram of

Ronald Graham.

What is the probability that two mathematicians have names that are anagrams. I suspect very small. However, see this blog post to see why the probability is not as small as it might be.

-----------------------------------------------------------------------
5) Blog Post Winner of Ramsey Meme Contest This post didn't mention Ronald Graham; however I think he would have liked it.

Thursday, July 09, 2020

Reflections on Ronald Graham by Steve Butler

Ronald Graham passed away on July 6 at the age of 84. We present reflections on Ronald Graham by Steve Butler.

Getting to work with Ron Graham

Ron Graham has helped transform the mathematics community and in particular been a leader in discrete mathematics for more than 50 years. It is impossible to fully appreciate the breadth of his work in one sitting, and I will not try to do so here. Ron has put his papers online and made them freely available, a valuable treasure; and there are still many a hidden gem inside of these papers that are waiting to be picked up, polished, and pushed further.

I want to share about how I got to know and work with Ron. To be fair I knew about Ron long before I ever knew Ron. He was that rare pop-star mathematician who had managed to reach out and become visible outside of the mathematical community. And so as a teenager I read about Ron in a book about Erdos. I thought to myself that this guy sounds really cool and someday I might even get to see him give a talk (if I was lucky).

I went to UC San Diego for graduate school and after a series of near-misses ended up studying under Fan Chung. I passed Ron in the stairwell once, and then also helped them move some furniture between their two adjoining homes (graduate students are great for manual labor). But I became determined to try and find a way to start a conversation with Ron and maybe work up to working on a problem. So I took the usual route: I erased the chalkboards for him.

Before his class on discrete mathematics would start, I would come in and clean the chalkboards making them pristine. It also gave me time to occasionally engage in some idle chat, and he mentioned that his papers list was far from complete. I jumped on it and got to work right away and put his papers online and have been maintaining that list for the last fifteen years. This turned out to be no small feat and required about six months of work.  Many papers had no previous online version, and there were even a few papers that Ron had written that he had forgotten about! But this gave me a reason to come to Ron and talk with him about his various papers and then he would mention some problems he was working on with others and where they were stuck and thought I might give them a try.

So I started to work on these problems and started to make progress. And Ron saw what I was able to do and would send me more problems that fit my abilities and interests, and I would come back and show him partial solutions, or computations, and then he would often times fill in the gaps. He was fun to work with, because we almost always made progress; even when we didn't make progress we still understood things more fully. Little by little our publications (and friendship) grew and we now have 25+ joint publications, and one more book that will be coming out in the next few years about the enumerating juggling patterns.

After all of that though, I discovered something. I could have just gone to Ron's door and knocked and he would have talked to me, and given me problems (though our friendship would not become so deep if I had chosen the forthright method). But almost no graduate students in math were brave enough to do it; they were scared off by his reputation. As a consequence, Ron had far fewer math graduate students than you would expect. (To any math graduate student out there, don't let fear stop you from talking with professors; many of them are much nicer than you think, and the ones that are not nice are probably not that great to work with.)

So one of the most important lessons I learned from Ron was the importance of kindness. Ron was generous and kind to everyone (and I really stress the word everyone) that he met. It didn't matter what walk of life you were in, what age you were, or what level of math (if any) that you knew, he was kind and willing to share his time and talents. He always had something in reach in his bag or pocket that he could pull out and show someone and give them an unexpected sense of wonder.

Richard Hamming once said "you can be a nice guy or you can be a great scientist", the implication being that you cannot do both. Ron showed that you can be a nice guy and a great scientist. And I believe that a significant portion of his success is owed to his being kind; all of us should learn from his examples and show more kindness towards others.

This is only one of many lessons I learned from Ron. Another thing I learned from Ron is the importance of data. I have seen multiple times when we would work on a problem and generate data resulting in what I thought were hopeless numbers to understand. But Ron looked at that same data and with a short bit of trial and error was able to make a guess of what the general form was. And almost inevitably he would be right! One way that Ron could do this was to start by factoring the values, and if all the prime factors were small he could guess that the expression was some combination of factorials and powers and then start to play with expressions until things worked out. Even when I knew what he did, I still am amazed that he was able to do it.

I will miss Ron, I will never have a collaboration as deep, as meaningful, and as personal. I am better for having worked with him, and learning from him about how to be a better mathematician and a better person.

Thank you, Ron.

Sunday, July 05, 2020

A table for Matrix Mortality- what I wanted for Hilbert's 10th problem

In this post I speculated on why I could not find anywhere a table of which cases of Hilbert's 10th problem were solvable, unsolvable, and unknown. (I then made such a table. It was very clunky,  which may answer the question.)

I told my formal lang theory class about Hilbert's 10th problem as a natural example of an undecidable question- that is, an example that had nothing to do with Turing Machines. On the final I asked

Give an example of an undecidable problem that has nothing to do with Turing Machines.

Because of the pandemic this was a 2-day take home final which was open-book, open-notes, open-web. So they could have looked at my slides.

And indeed, most of them did give Hilbert's 10 problem (more formally, the set of all polynomials in many vars over Z which have a Diophantine solution).

But some did not. Some said there could never be such a problem (this is an incorrect answer), Some were incoherent. One just wrote Kruskal Trees''  (not sure if he was referring to MSTs or WQOs or to something that Clyde Kruskal did in class one day).

One student said that the problem of, given a CFG G, is the complement of L(G) also CFG.
This is indeed undecidable and does not have to do with TMs. I doubt the student could have proven that. I doubt I could have proven that. I do not doubt that my advisor Harry Lewis could have proven that, and indeed I emailed him asking for a proof and he emailed me a sketch, which I wrote out in more detail here.

The most interesting answer was given by some students who apparently looked at the web (rather than at my slides) for lists of problems and found the following called Matrix Mortality:

{ (M_1,...,M_L) : such that some product of these matrices (you are allowed to use a matrix many times) is the 0 matrix}

Why was this the most interesting? The TA did not know this problem was undecidable until he saw it on the exams and looked it up. I did not know it was undecidable until my TA told me.

I then raised the question: How many matrices to you need and how big do their dimensions have to be?

Unlike H10, there IS a table of this. In this paper they have such a table. I state some results:

Undecidable:
6 matrices, 3x3
4 matrices, 5x5
3 matrices 9x9
2 matrices 15x15

Decidable
2 matrices 2x2

So there are some gaps to fill, but there is not the vast gulf that exists between dec and undec for Hilberts 10th problem. I also note that the paper was about UNDEC but mentioned the DEC results, where as the papers on H10 about UNDEC seem to never mention the DEC.

I am glad to know another natural Undec problem and I will likely tell my students about it next spring. And much like H10, I won't be proving it.

An open problem in education: how come some of my students got it wrong? gave an answer that was not in my notes or slides? One student told me it was easier to google

Natural Undecidable Questions

then look through my slides. Another one said:

In class you said this is a natural undecidable problem'.

On the exam you said a problem that does not mention Turing Machines'

I did not know they were the same.

That student submitted the Matrix problem stated above. It IS a fair point that natural' is an
undefined term.  But the problem on the final used the well defined concept does not mention Turing Machines'

Monday, June 29, 2020

Can you name a famous living Chemist? Can anyone?

I was re-watching the  Greatest-of-all-time Jeopardy championship and the following happen (I paraphrase)

----------------------
Alex Trebek: The category is Chemistry and we have a special guest reading the clues.

Darling: I wonder who that will be.

Bill: Hmm. I assume some famous chemist.
------------------------

So who was it? Bryan Cranston, the actor who PLAYED chemist Walter White on Breaking Bad.

Why couldn't they get a famous living chemist to read the clues?

My guess: there are no famous living chemists.

The number of famous living scientists is fairly short and they are often known for things that are not quite their science. Some are famous because the popularize science (deGrasse Tyson, Dawkins) or because of something unusual about their life (Hawkings when he was alive) or for something else entirely that they did (Ted Kaczynski).  Are any famous for the actual work that they do in the science?

Andrew Wiles was famous for a brief time, and even made People Magazine's 25 most intriguing people of the year list in the early 1990's (after he solved Fermat's Last Theorem). So he was famous but it was short lived.

Terry Tao was on the Colbert Report (see here) after he won the Fields Medal, the MacAuthor Genius award, and the Breakthrough prize. And even that fame was short lived.

I looked at the web page of Nobel Prize winners, here.

The only Chemistry Nobel's I recognized were Marie Curie,  Irene Joilet-Curie (Marie's Daughter), and Erst Rutherford.

The only Physics Nobel's I recognized were

Richard Feynman,

Eugene Wigner (for writing about The unreasonable effectiveness of mathematics in the natural sciences),

Richard Hofstadter (since he was the father of Douglas H and an uncle of Leonard H)

Andrew Geim (since he won  both an Ig-Noble prize and a Nobel prize, see  here)

Wolfgang Pauli (I've heard the term Pauli Principle" though I did not know what it was until I looked it up while preparing this blog. I prob still don't really know what it means.)

Enrico Fermi

Erwin Schrodinger

Paul Dirac

Robert Millikan

Albert Einstein

Max Karl Ernest Ludwig Planck (I thought his last name was Institute')

Johannes Diderik van der Waals

Pierre Curie

Marie Curie

So, some questions:

a) Am I wrong? Are there famous living chemists I never heard of? Are there any famous living scientists who are famous for their work in science?

b) If I am right then was there ever a time when there were famous scientists?

c) If there was such a time, what changed?

(I ask all of this non-rhetorically and with no agenda to push.)

Monday, June 22, 2020

Winner of Ramsey Meme Contest

My REU program had a Ramsey Meme Contest.

The winner was Saadiq Shaik with this entry:

I Don't Always...

I challenge my readers to come up with other Ramsey Memes! or Complexity Memes! or point me to some that are already out there.

Thursday, June 18, 2020

On Chain Letters and Pandemics

Guest post by Varsha Dani.

My 11-year-old child received a letter in the mail. "Send a book to the first person named," it said, "then move everyone's name up the list, add your own name and send copies of the letter to six friends. In a few weeks you will receive 36 books from all over the world!". Wow. When I first encountered chain letters in the mid eighties, it was postcards, but even then it hadn't taken me in. Since then I hadn't seen one of these in a long time, but I guess with a lot of people suddenly at home for extended periods, people crave both entertainment and a connection to others.

What's wrong with chain letters? Well quite apart from the fact that they are illegal, even a child can comprehend that the number of books (or postcards or other gifts) received must equal the number sent, and that for every participant who does get a rich reward, there will be many who get nothing.

But there is another kind of chain communication going around. It is an email, asking the recipient to send a poem or meditation to somebody, and later they will receive many communications of the same sort. How endearing. Poetry. Sweetness and Light. No get-rich-quick pyramid schemes here. What's wrong with that?

Of course, it depends on what one means by "wrong". Maybe you like exchanging poetry with strangers. Maybe you don't find it onerous or wish that your spam filter would weed it out. But let's leave aside those issues and look at the math alone. You send the email to two friends, each of whom forwards it to two of their friends and so on. So the number of people the email reaches ostensibly doubles every step. Exponential growth. But in fact that is not what the graph of human connections looks like. Instead, what happens is that the sets of friends overlap, so that after a while the growth stops being exponential and tapers down.

Where else have we seen something like that? Oh, right. The pandemic. The virus jumps from infected people to the people they meet, and from them to the people they meet and so on. Initially, that's exponential growth fof new cases, but after a while  it tapers off, forms a peak and then starts to decrease. Why? Because eventually there is overlap in the sets of people that each infected person is "trying" (unintentionally) to infect, and a newly infected person who got the virus from one or many previously infected people is still just one newly infected person.

So the chain letter spreads just like a virus. Indeed if one were to, somewhat fancifully, think of the chain letter as an independent entity whose goal is to self-replicate, then it looks even more like a virus, and, like a virus, it can only achieve its self-replication goal through the help of a host. But here's a way in which it is not like a virus. Once one has got the virus and recovered, one (hopefully) does not get it again. Not so the chain letter, of which one may get many copies over time! So maybe you will get some gifts or poetry, but you will likely also get more requests for them!

So what's wrong with the poetry chain email? It depends on your perspective.  To those of you who are wistfully waiting for that Poem from a Stranger, I dedicate the following to you.

An open letter to my 2n dearest friends:

A letter came for me today
It promised wondrous ends
If only I would forward it
To just two other friends.

If they in turn should send it on
to two more that they know,
the goodwill that we're sending out
would grow and grow and grow.

Is this as pleasant as it seems?
Alas, dear friends, it's not.
To quite a sticky spot.

Friends of friends of friends of mine
The further that the letters go.
These folks are not distinct!

Ensuring there's no overlap
Is a logistic* pain.
As you will see, when you receive
That letter yet again.

So while you're stuck at home this year
Pick up the phone and make a call
Or see your friends on Zoom.

Your real thoughts would make me smile.
Chain letters are a con.
Do everyone a favor and
Don't send that letter on!

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

Monday, June 15, 2020

Presentations of Diffie-Helman leave out how to find g

When I first taught Diffie Helman I read the following
1) Alice and Bob agree on p a prime and g a generator
2) Alice picks a, sends g^a to Bob, Bob picks b, sends g^b to Alice
3) Alice computes (g^b)^a and Bob computes (g^a)^b so they both have g^{ab}

I knew how to find a prime- pick a number of length n (perhaps make sure the last digit is not even) and test for primality, if not then try again, you'll get one soon enough. I did not know how to find g. I had thought you first find p, and then given p you find g. I then figured out that you make actually pick  p to be a  safe prime, so q=(p-1)/2 is a prime, and then just pick random g and test them via computing  g^2  and g^q: if neither is 1 then g is a generator. You will find a generator soon enough.

That was all fine. But how come my source didn't say how to find g.?You need to know that to run the algorithm. That was years ago. Then I wondered how common it is for an explanation to not say how to find g. So I Googled Diffie-Helman'' I only record those that had some technical content to them, and were not about other DH such as Elliptic Curves.

0) The Original DH paper Page 34: alpha is a fixed primitive element of GF(alpha). No mention of how to find either the prime q or the prim root alpha.

1) Wikiepdia: ... protocol uses the mult group of integers mod p, where p is a prime and g is a prim root mod p. NO mention of how they find p or g.

2) Wolfram's MathWorld: They agree on two prime numbers g and p, where p is large and g is a prim root mod p. In practice it is good to choose p such that (p-1)/2 is also prime. They mention (p-1)/2 but not for the reason I give. (There are algorithms for Discrete Log that do well if (p-1)/2 has many factors.)

3) Comparatech: Alice and Bob start out by deciding two numbers p and g. No mention of how to find p or g.

4) Searchsecurity Won't bother quoting, but more of the same, no mention of how to find p or g.

5) The Secret Security Wiki Alice and Bob agree on p and g.

6) Science Direct More of the same.

7) Notes from a UCLA Crypto Course YEAH! They say how to find g.

8) Brilliant (yes that really is the name of this site) Brilliant? Not brilliant enough to realize you need to say how to find p and g.

9) OpenSSL Hard to tell. Their intuitive explanation leaves it out, but they have details below and code that might have it.

I looked at a few more but it was the same story.

This is NOT a RANT or even a complaint, but its a question:

Why do so few expositions of DH mention how to find p,g? You really need to do that if you really want to DO DH.

Speculation

1) Some of the above are for the laymen and hence can not get into that. But some are not.

2) Some of them are for advanced audiences who would know how to do it. Even so, how to find the generator really needs to be mentioned.

3) Goldilocks: Some papers are for the layman who would not notice the gap, and some papers are for the expert who can fill in the gap themselves, so no paper in between. I do not believe that.

4) The oddest of the above is that the original paper did not say how to find g.

Monday, June 08, 2020

The Committee for the Adv. of TCS- workshop coming up SOON!

(Posted by request from Jelani Nelson.)

The Committee for the Advancement of Theoretical Computer Science (CATCS)
is organizing a Visioning workshop.  The primary objective of the workshop
is for TCS participants to brainstorm directions and talking points for TCS
program managers at funding agencies to advocate for theory funding.

There was some question of whether or not it would run this summer, but
YES, it is going to run.

If you are interested then reply (at the link below) by June 15.
This is SOON so click that link SOON.

The time commitment is 4-5 hours during the week of July 20-July 24 for
most participants, or roughly 10 hours for those who are willing to

Tuesday, June 02, 2020

How to handle grades during the Pandemic

In March many Colleges sent students home and the rest of the semester was online. This was quite disruptive for the students. Schools, quite reasonably, wanted to make it less traumatic for students.

So what to do about grades? There are two issues. I state the options I have heard.

ISSUE ONE  If P/F How to Got About it?

2) Make all classes P/F.

PRO: Much less pressure on students.

CON: Might be demoralizing for the good students.

3) Make all classes P/F but allow students to opt for letter grades BUT they must decide before the last day of class. Hence teachers must post cutoffs before the final is graded

CON: Complicated and puts (a) teachers in an awkward position of having to post cutoffs before the final, and (b) puts students in an awkward position of having to predict how well they would do.

CON: A student can blow off a final knowing they will still get a D (passing) in the course.

PRO: Good students can still get their A's

CAVEAT: A transcript might look very strange. Say I was looking at a graduate school applicant and I see

Operating Systems: A

Theory of Computation: P

I would likely assume that the Theory course the student got a C. And that might be unfair.

3) Make all classes P/F but allow students to opt for letter grades AFTER seeing their letter grades.

PRO: Less complicated an awkard

PRO: A students blah blah

CAVEAT above still applies.

ISSUE TWO If P/F what about a D in the major

At UMCP COMP SCI (and I expect other depts)

a D is a passing grade for the University

but

a D is not a passing grade for the Major.

So if a s CS Major gets a D in Discrete Math that does not count for the major--- they have to take it over again.

But if classes are P/F what do do about that.

Options

1) Students have to take classes in their major for a letter grade.

CON: The whole point of the P/F is to relieve pressure on the students in these hard times.

PRO: None.

2) Students taking a course in their major who get a D will still get a P on the transcript but will be told that they have to take the class over again.

3) Do nothing, but tell the students

IF you got a D in a course in your major and you are taking a sequel, STUDY HARD OVER THE SUMMER!

4) Do nothing, but tell the teachers

Students in the Fall may have a weak background. Just teach the bare minimum of what they need for the major.

(Could do both 3 and 4)

SO- what is your school doing and how is it working?

Monday, May 25, 2020

Oldest Living Baseball Players- can you estimate...

(The Baseball season is delayed or cancelled, so I post about baseball instead.)

This post is going to ask a question that you could look up on the web. But what fun with that be?

The following statements are true

1) Don Larsen, a professional baseball player who played from 1953 to 1967, is still alive. He is 90 years old (or perhaps 90 years young---I don't know the state of his health).  He was born Aug 7, 1929. He is best know for pitching a perfect game in the World Series in 1956, pitching for the Yankees. He played for several other teams as well, via trades (this was before free agency).
(CORRECTION- I wrote this post a while back, and Don Larsen has died since then.)

2) Whitey Ford, a professional baseball player who played from 1950 to 1967, is still alive. He is 91 years old (or perhaps 91 years young---I don't know the state of his health).  He was born Oct 21,  1928. He had many great seasons and is in the hall of fame. He played for the New York Yankees and no other team.

3) From 1900 (or so) until 1962 there were 16 professional baseball teams which had 25 people each. From 1962 until 1969 there were 20 teams which had 25 people each. There were also many minor league teams.

4) The youngest ballplayers are usually around 20. The oldest around 35. These are not exact numbers

SO here is my question: Try to estimate

1) How many LIVING  retired major league baseball players are there now who are older than Don Larsen?

2) How many LIVING retired major league baseball players are of an age between Don and Whitey?

3) How  many LIVING retired major league baseball players are older than Whitey Ford?

Tuesday, May 19, 2020

Obit for Richard Dudley

Richard M. (Dick) Dudley died on Jan. 19, 2020 (NOT from Coronavirus).You can find obituaries for him  herehere, and here and an interview with him from 2019  here.

Professor Dudley worked in Probability and Statistics. His work is now
being used in Machine Learning. Here is a guest-post-obit by

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

Guest Blog Obit by David Marcus:

Dick was my thesis advisor at M.I.T. After I got my Ph.D. in 1983, I went
to work in industry, so did not work closely with him, as some of his other
students did. But, I enjoyed working with him very much in graduate school.

Dick was very precise. His lecture notes and articles (and later his books)
said exactly what needed to be said and didn't waste words. In his classes,
he always handed out complete lecture notes, thus letting you concentrate
on the material rather than having to take a lot of notes.

Dick was very organized, but his office had piles of papers and journal
articles everywhere. There is a picture here.

Before Dick was my advisor, I took his probability course. My orals were
going to be towards the end of the term, and I was going to use probability
as one of my two minor areas. So, I spent a lot of time studying the
material. Dick gave a final exam in the course. The final exam was unlike
any other final exam I ever took: The exam listed twelve areas that had
been covered in the course. The instructions said to pick ten and for each
area give the main definitions and theorems and, if you had time, prove the
theorems. Since I had been studying the material for my orals, I didn't
have much trouble, but if I hadn't been studying it for my orals, it would
have been quite a shock!(COMMENT FROM BILL: Sounds like a lazy way to make up an exam, though on this
level of may it works. I know of a prof whose final was

Make up 4 good questions for the final. Now Solve them.

)

Once Dick became my advisor, Dick and I had a regular weekly meeting. I'd
tell him what I'd figured out or what I'd found in a book or journal
article over the last week and we'd discuss it and he'd make suggestions.
At some point, I'd say I needed to think about it, and I'd leave. I never
did find out how long these meetings were supposed to last because I was
always the one to end them.(COMMENT FROM BILL: It's good someone ended them! Or else you might never

When I began working with Dick, he said he already had a full
load of students, but he would see if he had something I could work on. The
problem Dick came up with for me to work on was to construct a
counterexample to a theorem that Dick had published. Dick knew his
published proof was wrong, and had an idea of what a counterexample might
look like, so suggested I might be able to prove it was a counterexample.
In retrospect, this was perhaps a risky thesis problem for me since if the
student gets stuck, the professor can spend time figuring out how to do it.
But, in this case, presumably Dick had already put some effort into it
without success. Regardless, with Dick's guidance, I was able to prove it,
and soon after got my Ph.D.(COMMENT FROM BILL: Sounds risky since if Dick could not do it, maybe it's too hard.)

In 2003 there was a conference in honor of Dick's 65th birthday. All of his
ex-students were invited, and many of them attended. There was a day of
talks, and we all went out to dinner (Chinese food, if I recall correctly)
in the evening. At dinner, I asked Dick if any of his other students had
written a thesis that disproved one of his published theorems. He said I
was the only one.(COMMENT FROM BILL: Really good that not only was he okay with you disproving
his theorem, he encouraged you to!)