Wednesday, October 07, 2015

Randomness by Complexity

Let n be the following number
135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563 (RSA 1024)

What is the probability that the fifth least significant bit of the smallest prime factor of n is a one? This bit is fully defined--the probability is either one or zero. But if gave me better than 50/50 odds one way or the other I would take the bet, unless you worked for RSA Labs.

How does this jibe with a Frequentist or Bayesian view of probability? No matter how often you factor the number you will always get the same answer. No matter what randomized process was used to generate the original primes, conditioned on n being the number above, the bit is determined.

Whether we flip a coin, shuffle cards, choose lottery balls or use a PRG, we are not creating truly random bits, just a complex process who unpredictability is,we hope, indistinguishable from true randomness. We know from Impagliazzo-Wigderson, and its many predecessors and successors, that any sufficiently complex process can be converted to a PRG indistinguishable from true randomness. Kolmogorov complexity tells us we can treat a single string with no short description as a "random string".

That's how we ground randomness in complexity: Randomness is not some distribution over something not determined, just something we cannot determine.

Monday, October 05, 2015

Is Kim Davis also against Nonconstrutive proofs?

Recall that Kim Davis is the Kentucky clerk who refused to issue marriage licenses for same-sex couples and was cheered on by Mike Huckabee and other Republican candidates for Prez. Had she refused to issue marriage license for couples that had been previously divorced than neither Mike Huckabee would not be supporting her, and the Pope wouldn't have a private 15 minute meeting with her telling her to stay strong (NOTE- I wrote this post in that tiny window of time when it was believed she did have such a meeting with the Pope, which is not true. The Pope DID meet with a former student of his who is gay, and that studen'ts partner.) Had she refused to issue marriage licenses to inter-racial couples (this did happen in the years after the Supreme court said that states could not ban interracial marriage, Loving vs Virginia, 1967 ) then ... hmm, I'm curious what would happen. Suffie to say that Mike H and the others would prob not be supporting her.

David Hilbert solved Gordon's problem using methods that were nonconstructive in (I think) the 1890's. This as considered controversial and Gordon famously said this is not math, this is theology. Had someone else solved this problem in 1990 then the fact that the proof is non-constructive might be noted, and the desire for a constructive proof might have been stated, but nobody would think the proof was merely theology.

I don't think the Prob Method was ever controversial; however, it was originally not used much and a paper might highlight its use in the title or abstract. Now its used so often that it would be unusual to point to it as a novel part of a paper. If I maintained a website of Uses of the Prob Method in Computer Science then it would be very hard to maintain since papers use it without commentary.

The same is becoming true of Ramsey Theory. I DO maintain a website of apps of Ramsey Theory to CS (see here) and its geting harder to maintain since using Ramsey Theory is not quite so novel as to be worth a mention.

SO- when does a math technique (e.g., prob method) or a social attuitude (e.g., acceptance of same-sex marriage) cross a threshold where its no longer controversial? Or no longer novel? How can you tell? Is it sudden or gradual? Comment on other examples from Math! CS!

Thursday, October 01, 2015

Cancer Sucks

Karsten Schwan said the title quote when we were gathered as a faculty two years ago mourning the Georgia Tech School of Computer Science faculty member Mary Jean Harrold who died from the disease. Karsten just lost his own battle with cancer monday morning and my department is now mourning another great faculty member.

Just a few months ago, Alberto Apostolico, an algorithms professor at Georgia Tech, also passed away from cancer

I went back through the obituaries in the blog and we lost quite a few to cancer, often way too young, including Mihai PătraşcuBenoît MandelbrotPartha NiyogiIngo Wegener, Clemens Lautemann and Carl Smith. I just taught Lautemann's proof that BPP is in Σp2∩Πp2 in class yesterday.

With apologies to Einstein, God does play dice with people's lives, taking them at random in this cruel way. Maybe someday we'll find a way to cure or mitigate this terrible disease but for now all I can say is Cancer Sucks. 

Monday, September 28, 2015

Venn Diagrams are used (yeah) but abused (boo)

In a prior blog entry I speculated about which math phrases will enter the English Language and will they be used correctly.  I thought Prisoner's Dilemma would enter and be used correctly, but Turing Test and Venn Diagram would not enter.

Since then I've seen Turing Test used, but only because of the movie The Imitation Game. I don't think it will enter the human language until a computer actually passes it for real, which might not be for a while. See this excellent post by Scott Aaronson about a recent bogus claim that a machine passed the Turing Test.

Venn Diagrams seem to be used more (Yeah!) but incorrectly (Boo!)

1) In this article (which inspired this post), about who might replace John Boehner as speaker of the house, there is the following passage:

Option 3: An acceptable and respected conservative like Jeb Hensarling or
Tom Price emerges as speaker. Why these two? First, Paul Ryan doesn’t seem
to want the gig, so that leaves us with only a few options for someone who
fits in the Venn diagram of being enough of an outsider, well liked, and
sufficiently conservative

Is this correct use? They really mean  the intersection of oustider, well-liked,
and suff conservative. One can picture it and it sort of makes sense, but its not
quite correct mathematically.

2)  In this ad for Venn Beer (in celebration of John Venn's 180th birthday!) they really mean union, not intersection.

3) This Venn Diagram about Vladmir Putin's and your Aunt's record collection doesn't really make sense but I know what they mean and its funny.

4) This Venn Diagram about how to woo women is incorrect, not funny, not mathematically meaningful.

5) This Venn Diagram involved Doctors, Prostitutes, and TSA agents. At first it is funny and seems to make sense. But then you realize that the intersection of Doctors and Prostitutes  is NOT People who make more per hours than you make all day, its actually prostitutes with medical degrees. Its still funny and I see what they are getting at.

6)  This Venn Diagram (it's later in the article) of Republican Candidates for the 2016 nomination for Prez is correct for the math and informative, though one may disagree with some of it (Is Trump really Tea-Party or should he be in his own category of Trumpness?)

Thursday, September 24, 2015

21st Century Problems

My youngest daughter, Molly, a high school senior talking colleges with a woman about ten years her senior. The woman remembered all her friends watching the clock so they could go home to check their emails to see if they were accepted. Molly said "Sheesh, you had to go home to check email?"

My other daughter Annie, a college junior, went on an overnight last Thursday to a place without cell phone reception. She spent Friday night with her friends in her class catching up on emails, texts and Facebook messages.

Now back in my day (that being the early 80's) we got our college acceptances and rejections by postal mail, where that one crucial bit of information could be determined by the thickness of the envelope. Some of my friends had their mail held by the post office so they could find out a few hours earlier.

In college I did have email access, in fact I wrote an email system for Cornell. But most students didn't use email so we resorted to other means. Student organizations could hire a service that put posters on key locations throughout campus. Chalk on sidewalks worked particularly well. The personals section of the Cornell Daily Sun served as a campus bulletin board. In my freshman dorm we had phones in our rooms but no answering machines. We did put little whiteboards on our doors so people could leave us messages. We had a lounge on our floor where you could find most people and talk to them in person. You young people should try that more often.

We had to coordinate activities and meeting places ahead of time, if someone was late you waited for them. On the other hand I never had to spend my Friday nights catching up on emails and texts.

Monday, September 21, 2015

When did Mathematicians realize that Fermat did not have a proof of FLT?

I recently came across the following passage which is about  Fermat's Last Theorem (FLT).

Pierre de Fermat had found a proof, but he did not bother to write it down. This is perhaps the most frustrating note in the history of mathematics, particularly as Fermat took his secret to the grave.

AH- so at one time people thought Fermat DID have a proof of FLT.  That is, a proof using just the math of his time, likely a very clever proof. I doubt anyone thinks that Fermat had a proof in this day and age. Actually it has been in fiction: in a 2010 episode Dr. Who episode The eleventh hour, the doctor has to prove to some very smart people that they should take his advice. He does this by showing them Fermat's proof of FLT. Good Science Fiction but highly unlikely as Science Fact. In an episode of ST-TNG  (Title: The Royale. Year: 1989) it is claimed that FLT is still open. Whoops. But in an episode of ST-DSN (Title: Facets. Year: 1995) they refer to `Wiles proof of FLT'.

Wikipedia states: It  is not known whether Fermat had actually found a valid proof for all exponents n, but it appears unlikely. I think that understates the case.

So here is a question for all you math historians out there: When did the math community realize that FLT was really hard?

We have one clue- the quote I began with. Its from... 2013. Whoops. The book is  The Simpsons and their mathematical secrets by Simon Singh (Author of Fermat's Enigma  which is about the quest to proof FLT).  I've read the passages about FLT in the Simpsons book over again to make sure he doesn't someplace say that Fermat prob didn't have a proof. No--- he seems to really say the Fermat had a proof. So whats going on here? Possibilities:

1) I'm wrong. There are serious credible people who think Fermat had a proof and he talked to them; perhaps while working Fermat's Enigma. I find this unlikely- I have never, literally never,  heard of  anyone, not even math cranks, who think Fermat had a simple proof.  Some cranks think THEY have a simple proof, though even that seems far less common after FLT was proven.

2) I'm right. He didn't have anyone who was both serious and credible check his book. I find this unlikely. He has written Fermat's 't Enigma so surely he is in contact with people that are both credible and serious.

3) He did have someone check his book but thought the story was better the way he told it. (This was common on the TV show Numb3rs which never let a mathematical truth get in the way of a good story.)
I find this unlikely since a better way to say it is we'll never know if Fermat had a proof!

One problem with such mistakes is that it destroys his credibility on other math things he writes of. That info about Dr. Who I got from the book, but I suspect its correct. And the stuff about the math that appears in the Simpsons is checkable and seems correct. I give one example: in one episode you see in the background

398712 + 436512= 447212

which is correct on a calculator with only 10 digits of precision. Cute! But I have stopped reading any of the math history in the book for fear that I will get incorrect notions in my head.

However, back to my original question: Was there a time when people thought Fermat really had a proof?Was  there a time when people thought there was an easy proof? When did that change?

Thursday, September 17, 2015

The Theorems Conference

All too often theoretical computer scientists get more obsessed by proofs than the theorems themselves. I suggest a theorems conference. Here's how it would work:

Authors would submit two versions of a paper. One has the statement of the theorem and why that theorem matters, but no proofs. The second version includes the proofs.

The program committee first makes tentative decisions based on the first version of the paper. If tentatively accepted the PC then looks at the second version. The PC can reject the paper if the the proofs have significant flaws, gaps or readability issues. The PC cannot reject the paper for any other aspect of the proof such as length or lack of technical depth or originality.

This way we truly judge papers based on what they prove--what the results add to the knowledge base of the field.

Of course my plan has many flaws. Some papers with their proofs may have already been posted on archive sites which the PC members could have seen. More likely, the PC will guess the difficulty of the proof and judge the paper based on this perceived difficulty, and not on the theorem itself.

We need a culture shift, away from an emphasis on proofs. That's the only way we can judge our results for the results themselves.

Monday, September 14, 2015

An Open(?) Question about Prime Producting Polynomials Part II in 3-D!

(Apologies- No, this post is not in 3-D)

I posted last week about An Open(?) Question about Prime Producing Polynomails

I got several emails about the post with more information, inspiring this post!
All the math in this post can be found in my writeup  Polynomials and Primes,
unless otherwise specified. NONE of the results are mine.

You can read this post without reading the prior one.

1) KNOWN: Let  f(x) ∈ Z[x]  be  a poly of degree d. Then there exists a non prime in f(x)'s image (actually there are an infinite number of  non primes, in fact there are an infinite number of composites).  If f(1) is prime then of  f(1+mf(1)) as m=0,1,2,... at most 2d-2 of them are prime.

2) Algorithm to find an x such that f(x) is not prime: compute f(1), f(1+f(1)),...,f(1+(2d-2)f(1)) until you find one that is not prime. This takes 2d-1 evals. OPEN(?): Is there a better deterministic algorithm where we measure complexity by number of evals? Since this is a simple model of computation lower bounds might be possible.

3) There is the following randomized algorithm: Eval f(1)- if its not prime you're done. If f(1) is prime then pick a random m where 0≤ m ≤ (2d-2)2 and eval f(1+mf(1)). This is non prime with prob 1- (1/(2d-1)).

4) What is it about Z that makes this theorem true? In my write up I show that if D is an integral domain with only a finite number of units (numbers  that have mult inverses) then any poly in D[x] has to produce non-primes infinitely often. (A prime in D is a number a such that if a=bc then either b or c is a unit.)

5) What about if D has an infinite number of units? See this  paper for examples of polynomials over integral domains D such that the poly only takes on  only prime or unit values.

6) What about polys over Q? over R? over C? In my write up I prove similar theorems for Q and then use that to get theorems for C.

7)  Looking at polys in Z[x,y] is much harder, see this survey. 

8) If f(x)∈Z[x] is a poly then does there exist a prime in f(x)'s image? An infinite number of primes? Easy but stupid answer is no: f(x)=2x. Better question: assume that f(x)'s coefficients are rel prime.

Dirichlet's theorem: if GCD(a,b)=1 then ax+b is prime infinitely  often.

Open: is x2  + 1 prime infinitely often?