What Makes a Constructive Proof?

In this weblog, we've used constructive in different ways. Often we talk about constructive as something we can create in polynomial time, like an expander. But how about constructive as in logic, when you don't get to assume the "excluded middle" where you get to assume some statement is either true or false?

The simplest well-known example is the theorem: There exists irrational \(a\) and \(b\) such that \(a^b\) is rational. 

1. \(\sqrt{2}^\sqrt{2}\) is rational. Let \(a = b = \sqrt{2}\).
2. \(\sqrt{2}^\sqrt{2}\) is irrational. Let \(a = \sqrt{2}^\sqrt{2}\) and \(b = \sqrt{2}\).

You don't know which \(a\) is correct. You just know it exists. (A far more complicated argument shows \(\sqrt{2}^\sqrt{2}\) is in fact irrational.) 

When I teach intro theory, my first proof that there are non-computable sets is by claiming the computable sets are countable but their are an uncountable number of sets over \(\Sigma^*\) so there must be an non-computable sets. I claim this is a non-constructive proof because I didn't give you the set and do an aside on constructive proofs using the example above. But that's not correct--the proof that there are uncountable number of sets over \(\Sigma^*\) is a constructive diagonalization. Give me an enumeration of the computable sets and I can easily construct a set not on that list.

In complexity, a well-known non-constructive theorem is by Kannan, showing that \(\Sigma^P_2\) does not have \(n^2\)-size circuits.

1. SAT doesn't have n²-size circuits. Since SAT is in Σ₂ we are done.
2. SAT has n²-size circuits. Then by Karp-Lipton Σ₄ = Σ₂ so L is in Σ₂ and we are done.

Jin-Yi Cai and Osamu Watanabe, and independently Sunny Daniels, gave a constructive \(\Sigma^2_P\) machine and thus a single language in \(\Sigma^P_2\) that doesn't have \(n^2\)-size circuits. But it is not a constructive proof, as the argument the machine works requires the two cases as to whether SAT has small circuits. As far as I know, a true constructive proof of Kannan's theorem remains open.

I have no problem with non-constructive proofs—I'm in a firm believer in \(P\vee\neg P\). But if you do talk about constructivity be sure and use it appropriately. 

Theorems and Lemmas and Proofs, Oh My!

I was recently asked by a non-mathematician about the difference between the terms Theorem, Lemma, etc. My first reaction was I probably have a blog post on that. Actually, I looked and I don't seem to. Since I have, according to Ken Reagan, over 1000 posts (see here and here) I can easily confuse things I meant to write a post on with things I wrote a post on. My next thought was Lance probably has a post on that. I asked him, and he also thought he had, but also had not. So now I will!

Open Question: A well defined question that you don't know the answer to and may not even have a guess as to which way it goes. The above is not quite right: sometimes an open question is not that well defined (e.g., Hilbert's 6th problem: Makes Physics Rigorous) and sometimes you have some idea, or a rooting interest, in how it goes. I tried to find some open questions in Mathematics where people in the know don't have a consensus opinion.  I can think of two off hand: Is Graph Isom in P? and is Factoring in P. Maybe the Unique Game Conjecture, though I think people in the know think it's true. Here is a website of open questions, but I think for all of them people in the know  think we know how they go: here.

Conjecture: A statement that you think is true, and may even have some evidence that its true, but have not proven yet. I am used to using this term in math, and hence I hope someone will PROVE the conjecture. Are there conjectures in empirical sciences? If so, then how do they finally decide it's true? Also note- I blogged about conjectures and how once they are proven the conjecturer is forgotten here. EXAMPLES OF CONJECTURES: The same link as in open problems above. 

True story but I will leave out names: There was a conjecture which I will call B's Conjecture. C & S solved it AS WRITTEN but clearly NOT AS INTENDED.  Even so, C & S got a published paper out of it. This paper made M so mad that he wrote a GREAT paper that solved the conjecture as intended (and in the opposite direction). That paper also got published. So one conjecture lead to two opposite solutions and two papers. 

Wild-Ass Guess: You can take a wild-ass guess what this is. 

Hypothesis: An assumption that you may not think is true but are curious what may be derived from it. The Continuum Hypothesis is one. For some reason Riemann's problem is called The Riemann Hypothesis even thought it's really a conjecture.  So is my notion of Hypothesis wrong? In any case, if you know other things that are called Hypothesis then please leave a comment. 

Lemma: A statement that is proven but only of interest in the service of proving a theorem. There are exceptions where a Lemma ends up being very important, see here. The word is also used in English, see here, but I've never heard of the word being used that way.

Theorem: A statement that has been proven. Usually it is somewhat general. There are a few exceptions: Fermat's Last Theorem was called that before it was a Theorem. If you know other things that were called theorems but weren't,  please comment.  EXAMPLES OF THEOREMS: The Fundamental Theorem of X (fill in the X), Ramsey's Theorem, VDW's theorem, Cook-Levin Theorem, The Governor's theorem (see here). There are many more theorems that have names and many that do not. 

Corollary: A statement that follows directly from a Theorem. Perhaps an interesting subcase of a Theorem. Often this is what you really care about. When trying to find a famous corollary I instead found The Roosevelt Corollary to the Monroe Doctrine,  Corollaries of the Pythagorean theorem, and Uses of the word Corollary in English. Are there any famous corollaries in mathematics that have names?

Claim: I do the following though I do not know if its common: During a proof I have something that I need for it, but it is  tied-to-the-proof-of-the-theorem so it would be hard to make a lemma. So I prove it inside the proof of the theorem and call it a claim. I use Claim, Proof of Claim, End of Proof of Claim to delimit it. 

Porism: A statement that you can get from a theorem by a minor adjustment of the proof. I've also heard the phrase Corollary of the proof of Theorem X. I first saw this in Jefferey Hirst's Phd Thesis which is here, on Reverse Mathematics. I liked the notion so much I've used it a few times. It does not seem to have caught on; however,  there is a Wikipedia entry for the term here which also gives two examples of its use, which are not from Hirst's  thesis or my papers. 

Proposition: I see this so rarely that I looked up what the difference is between a Proposition and a Theorem. From what I read a Proposition is either of lesser importance, or is easy enough to not need to give a prove, as opposed to a Theorem which is important and needs a proof.

Axiom: A statement that one assume is true and usually they are self-evident and true. Exceptions are The Axiom of Choice which some people reject since it is non-constructive. Also some people do not thing The Axiom of Determinacy is self-evident. Same for Large Cardinal Axioms. But really, most axioms are self-evident. Note that all branches of math use Axioms.

Postulate: Euclid used the term Postulate instead of Axiom. Actually, Euclid wrote in Ancient Greek so to say he used the term Postulate is probably not quite right. However, the term Postulate seems to mean an axiom of Euclid's, or perhaps an axiom in Geometry. One exception: Bertrand's Postulate which was a conjecture but is now a theorem. The link is to a math-stacks where there is some explanation for the weird name. 

Paradox:  A Paradox is a statement that is  paradoxical. Hmmm. that last sentence is self-referential, so its not enlightening. A paradox is supposed to be a statement that seems absurd or self contradictory, though under closer examination may make sense. Russell's Paradox shows that Frege's definition of a set does not work. The Monty Hall paradox, and the Banach-Tarski Paradox are just theorems that at first glance seem to be absurd. The Monty Hall Paradox is not absurd. Darling thinks the BT-paradox means that math is broken, see this post here for more on that.

Transcripts for the 21st Century

When I start a new academic job, I need to prove that I actually have a PhD. I have to log in my MIT alumni page, pay my $10 and they email my graduate transcript to whomever, all to verify that one bit of information. Why don't I just have a digitally signed certificate I can just hand over?

Our CS department spends an inordinate amount of time looking through transcripts of accepted Masters students to determine if they the right prerequisites for various classes. Great if could automate this process but the transcript come in PDF or JPEG and don't have a standardized format, especially from foreign countries. Also a course name does not give enough information to know what it covers. 

The Chronicle of Higher Education did a forum on The Transcript of the Future, and maybe some solutions to these problems on the horizon. Here are three potential future trends and an elephant in the room.

Modality

Since I went to school, transcripts have moved from paper to PDF. PDFs work for humans to look at, but don't work well to feed into computers to allow for better analysis. Transcripts should move to a structure format, perhaps JSON, to make them readable to machines. It's easy to go from JSON to PDF but less easy in the other direction. 

To make this work you need a standards so each university's transcript doesn't use a different format. Some standards are in the works but this doesn't seem quite settled yet, as best I can figure out from Internet searching.

Content

Once you go digital you can add much more information. You can add a syllabus, the topics a course covers, not just its title. You can add competencies, credentials, certificates, projects and skills achieved. You can add student's activities such as internships, athletics, clubs, leadership roles. You can give grad schools and companies a much fuller picture of a student beyond the grades.

The more stuff we stick into a transcript, the more standards you need to make sense of it. 

Provenance

Who owns the transcript? Right now it is the university, that's why I have to pay $10 for MIT to send it out. But why not in some common database, or on a blockchain, or a file owned by an individual with all the proper technology so it can't be forged. There are privacy and security issues that we would need to figure out. You don't want a student to lose access to a transcript because they lost a password, the way many have lost cryptocurrency. 

Artificial Intelligence

If we do have access to standardized digital transcripts, there will be the temptation to outsource to AI decision making related to them, such as job interviews (already happening) and grad admissions. We can use AI responsibly to help in the process but we need to remember that all these students are individuals and we need people to judge the people behind them.

Why I have some sympathy for the Simulation Theory (We are all characters in a video game.)

There are some people who believe that we are all characters in a video game written by Abisola (this is sometimes called The Simulation Hypothesis). I first dismissed this as nonsense. Then I read about it in the great  book But What if We're Wrong by Chuck Klosterman. He had  some reasons why The Simulation Hypothesis  is plausible. I thought about some more examples of his reasons. I still DO NOT believe it, but the reasons TO believe it do raise some questions.

There is one word that describes all of the reasons: Glitches!  That is Abisola, who wrote the code, made some mistakes that sometimes show through. Actually some might not be mistakes, perhaps Abisola, planned it. She has the bug/feature issue as do we. 

Here are some of those glitches: 

1) Real people who, from an accident, gained an ability that they did not have before.

a) Jason Padget: After being attacked and getting a concussion, woke up and was a math genius. 

b) Derek Amato: After a head injury became a brilliant composer.

c) McMahon: After a head injury woke up speaking fluent mandarin. I could not find a Wikipedia Entry for him.

d) Tony Cicero: After being struck my lightening was an excellent musician. I read this on a Quora entry but could not find it anywhere else. If you have more evidence on this one, please leave a comment and I will add it here later.

2) While I dismiss most accounts of ghosts, ESP, miracles, etc, there are so many of them that perhaps some are real and caused by glitches. Or features. 

3) This happens a lot to me and I am sure others (or analogs of it): I have a LaTeX bug. I delete a line.  The  bug goes away.   I put the line back. Now the bug is gone. 

4) What color is the dress?

5) Neil Degrasse Tyson and Elon Musk are fans of the Simulation Hypothesis.Not sure if this is any kind of justification for the Simulation Hypothesis or if Abisola coded them up to be that way.

6) All of a sudden the spell-check mechanism this blogger uses stops working AND when I leave a comment it does not automatically put my name on it, nor does it automatically bypass moderation (which is how it used to work).  Lance and I try to fix it, to no avail. The staff here tries to fix it, to no avail. a week later it works again. And YES the first thing I did was turn everything off and on again and that didn't work. (Update: this problem seems to come and go.) 

7) A watched pot never boils. Lost socks in the laundry. Etc.

8) On a more positive side, The Unreasonable Effectiveness of Mathematics in the Natural Sciences and The unreasonable effectiveness of Physics in the Mathematical Sciences. You can google to find more unreasonable effectiveness's. Thanks Abisola, though I wish you made Physics and Math easier. 

9) I emailed a HIGH-TECH colleague. My system says that YES I send that mail. He remembers READING that email when it came. Later on he can't find it- not in is normal files, not in trash, not in spam. gmail search can't find it anywhere. (My spell check thinks gmail is not a word. Nor Gmail. Really?)

10) The speed by which humans went from PONG to DWARF FORTRESS is not plausible. Maybe Abisola  found a way to speed up her program.  (This observation has been made by others.)

11) A relative got Eye Surgery recently. (a) The technology for the surgery was fantastic- outpatient, able to drive in 3 days, drive at night in 7 days, totally painless. (b) Still waiting for the paperwork that will allow him to drive without glasses. Gee- eye surgery should be hard, and paperwork should be easy. I think Abisola  found switching the two to be amusing. 

12) Aaronson's law of dark irony, see here.

13) The possibility of  Elon Musk and Mark Zuckerberg having an actual physical fight (see here), makes no sense. Whatever they disagree on (e.g., how a social network should be run, who is wealthier, who has the biggest....) will NOT be settled by a fight. If M wins then we know that M can beat Z in a fight. That is all that will be established. If Z wins then we know that Z can beat M in a fight. That is all that will be established. In both cases a fight will not settle whatever they disagree on. So why might they fight? Ask Abisloa if it is a bug or a feature. 

14) I am sure you can add your own reasons. 

Turning Sixty

I turn sixty today, spending my birthday reviewing a computer science department in Asia. Sixty is a good time to look back and reflect in a rambling way.

I started grad school in 1985. The P v NP problem was only 14 years old when I started. 38 years later we are no closer to solving it.

Nevertheless the field of computational complexity has remained strong, producing exciting research nearly every year. We're not seeing the surprising results that we saw through the early 90s but we've gained a much better understanding of pseudorandomness, coding theory, proof complexity, communication complexity, quantum complexity and circuit complexity (to an extent). The hard problems remain hard but that hasn't hampered progress in the field.

The field hasn't grown as dramatically as some others in theoretical computer science but neither has it shrunk. We have many great young researchers coming up in the field and its future is secure for decades to come.

I have some regrets for the field. Computational complexity has moved more towards mathematics with a focus on technical difficulty over conceptual novelty. We were quick to pick up on probabilistic, parallel and quantum computing, much slower on the cloud and machine learning. Combinatorial optimization has gotten extremely good, we can solve many NP-complete problems in practice, a point we rarely acknowledge.

For myself, I had an active research career for a good two decades. But then the field moved, away from my strength in the structure of complexity classes and more towards more combinatorial, algebraic and analytic techniques. A field should evolve but I found it difficult to keep up. So I focused on this blog, wrote a book, took on larger leadership and administrative roles. I try to follow what's going on in the field, but I'm happy to leave the research to the next generations, especially to my former students, several of whom have become leaders in the field themselves.

Someone recently asked me if I have regrets in my research career. I said that I’ve lived through some incredible advances in computing, but my research has played no significant role in any of it. 

Nevertheless as the computing world, if not the world as a whole, continually gets more complex, computational complexity has a continual mission to make sense of it. And so we shall.

The Acting Professor

When I taught Programming for Engineers at Northwestern in 2008, the textbook gave access to PowerPoint slides I could use to teach the class. Since C++ is not a specialty of mine, I tried using the slides for the course. It just felt wrong and lazy--it wasn't me teaching and the students were picking up on it. So I went back to teaching my own way and even though I would occasionally make a mistake (or two or ten), they were my mistakes and the class learned better with me.

The Chronicle of Higher Education recently ran a series on Courseware where it goes much further.

Romano’s instructor was using a courseware product from the publishing titan Cengage. In a departure from traditional supplementary class materials, like textbooks, many courseware tools offer the “soup to nuts” of an entire course: Not only the digital version of a textbook, but homework assignments and assessments that an instructor can select from a bank of premade options. Educational videos, slide presentations, and study flashcards. Auto-grading and performance-analytics capabilities.

It all made for an underwhelming, and often frustrating, learning experience. “There were never ways we could learn from the instructor,” said Romano, who double-majored in political science and environmental science. “It was just a really weird class.” 

At what point are lecturers just actors, reading the material and running the course on autopilot? Is this an advantage over pre-recorded online courses?

With AI perhaps you remove the instructor completely and a course just becomes a fancy computer game. Will the students learn? Will they want to?

Permutable Primes and Compatible Primes

This post is about an open problems column by Gasarch-Gezalyn-Patrick so they can be considered co-authors on this post. The column is here.

Known: A permutable prime is a prime so that, no matter how you permute the digits, you get a prime.

The first 22 of them are: 

2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97, 113, 131, 199, 311, 337, 373, 733, 919, 991.

11 might seem like a silly example. However, all of the known  ones past 991 are just all 1's. Let \(R_n\) be the base 10 number which is represented by n 1's. 

The next three permutable primes are \(R_{23}\), \(R_{317}\), \(R_{1031}\). 

Those are all of the permutable primes that are known. The 2  conjecture is that there are 

(1) there are an infinite number of them

(2)  all those past 991 are of the form \(R_n\). 

There is more information and more conjectures about them in the open problems col pointed to above. 

I know of three online papers on permutable primes, see my website of them here.

New: A number n is a k-compatible (henceforth k-comp) prime if there are k permutations of n that are prime but not k+1 such permutations.

Examples:

a) 103 is 3-comp: 013, 031, 103 are  prime BUT 130, 310,301 are NOT prime.

b) 97 is 2-comp: 79 and 97 are prime and there are no other perms of 97.

c) 41 is 1-comp: 41 is prime BUT 14 is NOT prime. 

We have some (though not much) empirical data that suggests the following. Fix L, the length of numbers being considered. If you look at L-length primes that are 1-comp, 2-comp, etc the number of them will (with some exceptions)  first increase then (with some exceptions) decrease, though past k=L/2 (actually smaller) the are no L-length, k-comp primes. 

For rigorous conjectures and more information  see the paper pointed to above. 

The College Visits

My wife's cousin and her daughter came and visited Chicago. The daughter, between junior and senior year of high school, is on the tail end of college tour season and visited Northwestern and University of Chicago while here. She's visited a dozen plus schools at this point.

As an academic and administrator I think of universities in terms of the faculty who are there, their academic strengths and reputation and sometimes the internal and external politics (people like to talk). All academic departments and universities have issues, in their own unique ways.

The visiting prospective students get a thoroughly different view: A tour highlighting the architecture and amenities, giving cherry-picked statistics that puts the school in its best light. The impressions students get have little to do with the quality of the education and can get affected by the personality of the tour guide or even the weather the day of the visit.

The daughter is interested in computer science but the Northwestern tour focused on South campus, the more artsy part of the university where she wouldn't be spending much of her days. Her favorite school, which I won't name, has by far the weakest CS program of the ones she has visited. But it seems those first impressions are also the lasting ones.

If you are a high school student take the tour but don't let that be your only impression. Track down the places on campus that matter to you, whether a department, college or extra-curricula and talk to the people there, particularly the students. Understand the parts of the university that matter to you, not just the ones that they put on display. 

Or perhaps avoid the campus visits entirely. You'll probably make a better choice if you aren't distracted by the size of the spires.