Do computers make us more safe or less safe?

Norbert Weiner wrote a paper Some Moral and Technical Consequences of Automation in 1960. It warns of the dangers of computers in two ways:

1) If a chess program is only trained against expert chess players then it might get confused if its opponent makes a bad move. This is not dangerous. But imagine a nuclear missle system that assumes the opponent is rational. If the opponent is not rational then it might launch and have an accidental nuclear war. So there must be a human component so that this won't happen.

I offer a story and a counter narrative. In the 5th season, 23rd episode of the TV show Castle,
title The Human Factor a character had the following story to tell:

The drone on its own was going to bomb a car. But the human noticed that there were red roses on the car, so it was a wedding couple, not a terrorist. If a human had not been involved the drone may have killed an innocent just married couple!

This scene bothered me. It could EASILY be the other way around: the human wants to bomb and the drone (which has better vision) notices the roses. Or there may be many other ways that a computer could be BETTER than a human. I am not saying that a completely automated system is better, I am saying that its not obvious which way to go.  Both in some combination? What combination? Who has the final say? And in the drone scenario there may not be time for a human to consider the options.

2) The Sorcerer's apprentice scenario. In The Sorcerer's Apprentice segment of the (original) movie Fantasia, Mickey mouse tells a broom to get him a glass of water. The broom keeps bringing him water and Mickey almost drowns. Computers may take orders to literally and not stop. I wonder if  automated stock-trading and automated auctions may have this problem. Is there a case known where this really did cause a problem?

So what do you think?

NOW- do computers (or, more generally technology) make us more safe or less safe?

FUTURE- same question.

Virtual Complexity

The Complexity Complexity Conference, the conference that shares its name and URL with this blog, originally scheduled for Saarbrücken will be held virtually next week. Registration is free for non-authors. Talks are already posted. Looking forward to seeing you at the business meeting and the social.

Award winners have already been announced: The Best Student Paper Award goes to Rahul Ilango for Connecting Perebor Conjectures: Towards a Search to Decision Reduction for Minimizing Formulas and the Best Paper Award goes to Daniel Dadush and Samarth Tiwari for On the Complexity of Branching Proofs.

Virtual conferences give an opportunity for far more people to attend since you don't have the expense and time needed to go to Germany. On the other hand it's hard to dedicate time for a conference when you aren't there. I missed STOC which would have been walking distance from where I live but I did attend parts of the Economics and Computation conference which was supposed to be in Budapest. EC made great use of gather.town where you can wander around virtual rooms bumping into and talking to people. I caught up with a few people there. Complexity plans to use gather for its social meeting next week. Looking forward to the virtual beer.

Erdos-Turan for k=3 is True!

(All of the math in this post is summarized (without proofs) in a writeup by Erik Metz and myself which you can find here. It is a pdf file so you can click on links in it to get to the papers it refers to. There have been posts on this topic by Gil Kalai and  Luca Trevisan. If you know of others then let me know so I can add them to this post.)



This is a sequel to A BREAKTHROUGH result on density and 3-AP's and Big news on W(3,r)!

For this post N is large, and all inequalites have a big-O or a big-Omega.

For this post [N] is {1,...,N}

Let

r(N) be the least w such that if A is a subset of [N] and |A|  >  w, then A has a 3-AP.

There has been a long sequence of results getting smaller and smaller upper bounds on r(N).

The motivation for getting these results is that if r(N) is < N/(log N)^{1+\delta} with delta>0 then the following holds:

If sum_{x\in A} 1/x diverges then A has a 3-AP.

This is the k=3 case of one of the Erdos-Turan Conjectures.

Bloom and Sisack HAVE gotten N/(log N)^{1+delta} so they HAVE gotten ET k=3. Wow!

1) I am NOT surprised that its true.

2) I am SHOCKED and DELIGHTED that it was proven.  Shocked because the results leading up to it (see the write up referenced at the beginning of this post) seemed Zeno-like, approaching the result needed got but not getting there. Delighted because... uh, as the kids say, just cause.

I've heard that k=4 really is much harder (see my comments and Gil's response on his blog post, pointed to at the beginning of this post)  and it is true that there has been far less progress on that case (the write up I pointed to at the beginning of this post says what is known). Hence I will again be shocked if it is proven.  So, unlike The Who (see here) I CAN be fooled again. That's okay--- I will  be delighted. (ADDED LATER- there are more comments no Gil's website, from Thomas Bloom and Ben Green about what is likely to happen in the next 10 years.)

Erdos offered a prize of $3000 for a proof that A has, for all k, a k-AP.  The prize is now $5000. After Erdos passed away Ronald Graham became the Erdos-Bank and paid out the money when people solved a problem Erdos put a bounty on. What happens now? (If I have the facts wrong and/or if you know the answer, please leave a polite and enlightening comment.)

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.

All of the answers submitted had some number repeated.

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.

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.

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'