Thursday, September 21, 2017

Acronyms and PHP

Whenever I teach discrete math and use FML to mean Formula the students laugh since its a common acroynm for  Fuck My Life. Now they laugh, and I say I know why you are laughing, I know what it means  and they laugh even harder.

BUT it got me thinking: Pigeonhole Principle! There are more things we want short acroynms for then there are short acroynms. Below are some I thought of. I am sure there are others, in fact I am sure there are websites of such, but I wanted to see which ones I just happen to know.

AMS- American Math Society and much much more:see here


Dead on Arrival

Department of Aging. Scary!


Earned Run Average in Baseball,

Equal Rights Amendment in politics


Phencyclidine, a drug that you should never take.

Prob. Checkable Proofs. Obscure to the pubic but not to us.


Irish Republic Army

Internal Retirement Account

Several companies have had rumors they fund terrorism because they were giving their employees IRA's. The headline `Company X funds IRA's' could be misunderstood.


Standard Aptitute Test

Satisfiability (of Boolena Formulas) Obscure to the pubic but not to us. Actually it may get less obscure as more ``proofs'' resolving P vs NP come out.


Single Jewish Female (in classified ads- more on that later). I think SJF is more common.

Social Justice Warrior (sounds like a good thing but might not be)

Classified ads are a source of many acronyms which can be used to teach combinatorics.


S-single, M-married, W-widowed, D-Divorced, G-Gay (this one I've seen alone making me wonder
about S/M/W/D? I've also seen four-letter acronyms to disambiguate).

B- black, C-Christian, H-Hispanic,  J-Jewish, W-White.

M,F- Male, Female, though I am sure there are ways to say other genders.

Great for combinatorics! especially if you add in other ones (like BD)


Wisconsin  Tourism Federation

You know what else it means so I won't say it (this is a G-rated blog). When I first saw it I thought `what the fuck?- how could they have screwed up so badly?'

TEACHING TOOL- when teaching PHP (Pigeon hole Principle, not the language PHP which stands for Hypertex PreProcessing, not quite in order, or Personal Home Page) you can use the the fact that

number of concepts GREATER THAN  number of 3-letter combos

leads to some 3-letter combos will be used more than once.

Monday, September 18, 2017

A problem I thought was interesting- now...

On Nate Silver's page he sometimes (might be once a week) has a column edited by Oliver Roeder of problems. Pretty much math problems though sometimes not quite.

Some are math problems that I have seen before (e.g., hat problems). I don't bother submitting since that would just be goofy. I would be  ringer.

Some are math problems that I have not seen before, I try to do, I fail, but read the answer and am enlightened. I call that a win.

But some are math problems that I have not seen before, I try to do, I fail, but when I see the solution its a computer simulation or something else that isn't quite as interesting as I had hoped.

I describe one of those now; however, I ask if it can be made more interesting.

The problems is from this column: here

I paraphrase:  Let A be the numbers {1,2,3,...,100}.  A sequence is nice if  (1) it begins with any number in A, (2) every number is from A and is either a factor of multiple of the number just before it, and (3) no number can appear more than once.  Find the LONGEST nice sequence

Example of a nice sequence: 

4, 12, 24, 6, 60, 30, 10, 100, 25, 5, 1, 97

I worked on it

1) By hand I came up with a nice sequence of length 42. This was FUN! You can either have fun trying to find a long nice sequence or you can look at mine here.

2) I tried to prove that it was optimal, hoping that either I would find its optimal or be guided to a longer sequence. Neither happened. More important is that this was NOT FUN.

3) I looked forward to the solution that would be in the next column and would be enlightening. 

4) The next column, which did have the solution, is here! The answer was a sequence of length 77 found by a program that also verified there was no longer sequence. The sequence itself was mildly enlightening in that I found some tricks I didn't know about, but the lack of a real lower bound proof was disappointing.

They mentioned that this is a longest path problem (Graph is {1,..,100} edges are between numbers that are either multiples of factors) and that such problems are NP-complete. That gave the impression that THIS problem is hard since its a case of an NP-complete problem. Thats not quite right- its possible that this type of graph has a quick solution.

But I would like YOU the readers to help me turn lemon into lemonade.

1) Is there a short proof that 77 is optimal?  Is there a short proof that (say) there is no sequence of length 83.  I picked 83 at random.  One can easily prove there is no sequence of length 100.

2) Is the following problem in P or NPC or if-NPC-then-bad-thing-happen:

Given (n,k) is there a nice sequence of {1,...,n} of length at least k. (n is in binary, k is in unary, so that the problem is in NP.)

I suspect not NPC.

3) Is the following problem in P or NPC or ...

Given a set of numbers A and a number k, is there a nice sequence of elements of A of length at least k (k in unary).

Might be NPC if one can code any graph into such a set.

Might be in P since the input has a long length.

4) Is the following solvable: given a puzzle in the Riddler, determine ahead of time if its going to be interesting? Clyde Kruskal and I have a way to solve this- every even numbered column I read the problem and the solution and tell him if its interesting, and he does the same for odd number columns.

Thursday, September 14, 2017

Random Storm Thoughts

It's Monday as I write this post from home. Atlanta, for the first time ever, is in a tropical storm warning. Georgia Tech is closed today and tomorrow. I'm just waiting for the power to go out. But whatever will happen here won't even count as a minor inconvenience compared to those in Houston, the Caribbean and Florida. Our hearts goes out to all those affected by these terrible storms.

Did global warming help make Harvey and Irma as dangerous as they became? Hard to believe we have an administration that won't even consider the question and keeps busy eliminating "climate change" from research papers. Here's a lengthy list cataloging Trump's war on science. 

Tesla temporarily upgraded to its Florida Owners' cars giving them an extra 30 miles of battery life. Glad they did this but it begs the question why Tesla restricted the battery life in the first place. Reminds of when in the 1970's you wanted a faster IBM computer, you paid more and an IBM technician would come and turn the appropriate screw. Competition prevents software-inhibitors to hardware. Who will be Tesla's competitors?

During all this turmoil the follow question by Elchanan Mossel had me oddly obsessed: Suppose you flip a six-sided die. What is the expected number of dice throws needed until you get a six given that all the throws ended up being even numbers? My intuition was wrong though when Tim Gowers falls into the same trap I don't feel so bad. I wrote a short Python program to convince me, and the program itself suggested a proof.

Updates on Thursday: I never did lose power though many other Georgia Tech faculty did. The New York Times also covered the Tesla update. 

Sunday, September 10, 2017

The Scarecrow's math being wrong was intentional

In 2009 I had a post about Movie mistakes (see here). One of them was the Scarecrow in The Wizard of Oz after he got a Diploma (AH- but not a brain) he said

The sum of the square roots of any two sides of an isoscles triangle is equal to the square root of the remaining side. Oh joy! Rapture! I have a brain!

I wrote that either this mistake was (1) a mistake, (2) on purpose and shows the Scarecrow really didn't gain any intelligence (or actually he was always smart, just not in math), or (3) It was Dorothy's dream so it Dorothy was not good at math.

Some of the comments claimed it was (2).  One of the comments said it was on the audio commentary.

We now have further proof AND a longer story: In the book Hollywood Science: The Next Generation, From Spaceships to Microchips (see here) they discuss the issue (page 90). The point to our blog as having discussed it (the first book not written by Lance or Lipton-Regan to mention our blog?) and then give evidence that YES it was intentional.

They got a hold of the original script. The Scarecrow originally had a longer even more incoherent speech that was so over the top that of course it was intentional. Here it is:

The sum of the square roots of any two sides of an isosceles triangle is equal to the square root of the remaining side: H-2-O Plus H-2-S-O-4 equals H-2-S-O-3 using pi-r-squared as a common denominator Oh rapture! What a brain!

While I am sure the point was that the Scarecrow was no smarter, I'm amused at the thought of Dorothy not knowing math or chemistry and jumbling them up in her dream.

Thursday, September 07, 2017

Statistics on my dead cat policy- is there a correlation?

When I teach a small (at most 40) students I often have the dead-cat policy for late HW:

HW is due on Tuesday. But there may be things that come up that don't quite merit a doctors note, for example your cat dying, but are legit for an extension. Rather than have me judge every case you ALL have an extension until Thursday, no questions asked. Realize of course that the hw is MORALLY due Tuesday. So if on Thursday you ask, for an extension I will deny it on the grounds that I already gave you one. So you are advised to not abuse the policy. For example, if you forget to bring your HW in on thursday I will not only NOT give the extension, but I will laugh at you.

(I thought I had blogged on this policy before but couldn't find the post.)

Policy PRO: Much less hassling with late HW and doctors notes and stuff

Policy CON: The students tend to THINK of Thursday as the due date.

Policy PRO: Every student did every HW.

Caveat: The students themselves tell me that they DO start the HW on Monday night, but if they can't quite finish it they have a few more days. This is OKAY by me.

I have always thought that there is NO correlation between the students who tend to hand in the HW on Thursday and those that do well in the class.  In the spring I had my TA keep track of this and do statistics on it.

The class was Formal Lang Theory (Reg Langs, P and NP, Computability. I also put in some communication complexity. I didn't do Context free grammars.)  There were 43 students in the class. We define a students morality (M) as the the number of HW they hand in on Tuesday. There were 9 HW.

3 students had M=0

12 students had M=1

9 students had M=2

5 students had M=3

4 students had M=4

4 students had M=5

1 student had M=6

1 student had M=7

2 students had M=8

2 students had M=9

We graphed grade vs morality (see  here)

The Pearson Correlation Coefficient is 0.51. So some linear

The p-value is 0.0003 which means the prob that there is NO correlation is very low.

My opinion:

1) The 5 students with M at least 7 all did very well in the course.This seems significant.

2) Aside from that there is not much correlation.

3) If I tell my next semesters class  ``people who handed the HW in on tuesday did well in the class so you should do the same'' that would not be quite right- do the good students hand thing in on time, or does handing things in on time make you a good student? I suspect the former.

4) Am I surprised that so many students had such low M scores? Not even a little.

Monday, September 04, 2017

Rules and Exceptions

As a mathematician nothing grates me more than the expression "The exception that proves the rule". Either we bake the exception into the rule (all primes are odd except two) or the exception in fact disproves the rule.

According to Wikipedia, "the exception that proves the rule" has a legitimate meaning, a sign that says "No parking 3-6 PM" suggests that parking is allowed at other times. Usually though I'm seeing the expression used when one tries to make a point and wants to dismiss evidence to the contrary. The argument says that if exceptions are rare that gives even more evidence that the rule is true. As in yesterday's New York Times
The illegal annexation of Crimea by Russian in 2014 might seem to prove us wrong. But the seizure of Crimea is the exception that proves the rule, precisely because of how rare conquests are today.
Another example might be the cold wave of 2014 which some say support the hypothesis of global warming because such cold waves are so rare these days.

How about the death of Joshua Brown, when his Tesla on autopilot crashed into a truck. Does this give evidence that self-driving cars are unsafe, or in fact they are quite safe because such deaths are quite rare? That's the main issue I have with "the exception that proves the rule", it allows two people to take the same fact to draw distinctly opposite conclusions.

Thursday, August 31, 2017

NOT So Powerful

Note: Thanks to Sasho and Badih Ghazi for pointing out that I had misread the Tardos paper. Approximating the Shannon graph capacity is an open problem. Grötschel, Lovász and Schrijver approximate a related function, the Lovász Theta function, which also has the properties we need to get an exponential separation of monotone and non-monotone circuits.

Also since I wrote this post, Norbert Blum has retracted his proof.

Below is the original post.

A monotone circuit has only AND and OR gates, no NOT gates. Monotone circuits can only produce monotone functions like clique or perfect matching, where adding an edge only makes a clique or matching more likely. Razborov in a famous 1985 paper showed that the clique problem does not have polynomial-size monotone circuits.

I choose Razborov's monotone bound for clique as one of my Favorite Ten Complexity Theorems (1985-1994 edition). In that section I wrote
Initially, many thought that perhaps we could extend these [monotone] techniques into the general case. Now it seems that Razborov's theorem says much more about the weakness of monotone models than about the hardness of NP problems. Razborov showed that matching also does not have polynomial-size monotone circuits. However, we know that matching does have a polynomial-time algorithm and thus polynomial-size nonmonotone circuits. Tardos exhibited a monotone problem that has an exponential gap between its monotone and nonmonotone circuit complexity. 
I have to confess I never actually read Éva Tardos' short paper at the time but since it serves as Exhibit A against Norbert Blum's recent P ≠ NP paper, I thought I would take a look. The paper relies on the notion of the Shannon graph capacity. If you have a k-letter alphabet you can express kn many words of length n. Suppose some pairs of letters were indistinguishable due to transmission issues. Consider an undirected graph G with edges between pairs of indistinguishable letters. The Shannon graph capacity is the value of c such that you can produce cn distinguishable words of length n for large n. The Shannon capacity of a 5-cycle turns out to be the square root of 5. Grötschel, Lovász, Schrijver use the ellipsoid method to approximate the Shannon capacity in polynomial time.

The Shannon capacity is anti-monotone, it can only decrease or stay the same if we add edges to G. If G has an independent set of size k you can get kn distinguishable words just by using the letters of the independent set. If G is a union of k cliques, then the Shannon capacity is k by choosing one representation from each clique, since all letters in a clique are indistinguishable from each other.

So we have the largest independent set is at most the Shannon capacity is at most the smallest clique cover.

Let G' be the complement of a graph G, i.e. {u,v} is an edge of G' iff {u,v} is not an edge of G. Tardos' insight is to look at the function f(G) = the Shannon capacity of G'. Now f is monotone in G. f(G) is at least the largest independent set of G' which is the same as the largest clique in G. Likewise f(G) is bounded above by the smallest partition into independent sets which is the same as the chromatic number of G since all the nodes with the same color form an independent set. We can only approximate f(G) but by careful rounding we can get a monotone polynomial-time computable function (and thus polynomial-size AND-OR-NOT circuits) that sits between the clique size and the chromatic number.

Finally Tardos notes that the techniques of Razborov and Alon-Boppana show that any monotone function that sits between clique and chromatic number must have exponential-size monotone (AND-OR) circuits. The NOT gate is truly powerful, bringing the complexity down exponentially.

Sunday, August 27, 2017

either pi is algebraic or some journals let in an incorrect paper!/the 15 most famous transcendental numbers

Someone has published three papers claiming that

π is 17 -8*sqrt(3) which is really =3.1435935394...

Someone else has published eight papers claiming

π is (14 - sqrt(2))/4 which is really 3.1464466094...

The first result is closer, though I don't think this is a contest that either author can win.

Either π is algebraic, which contradicts a well known theorem, or some journals accepted some papers with false proofs. I also wonder how someone could publish the same result 3 or 8 times.

I could write more on this, but another blogger has done a great job, so I'll point to it: here

DIFFERENT TOPIC (related?) What are the 15 most famous transcendental numbers? While its a matter of opinion, there is an awesome website that claims to have the answer here. I"ll briefly comment on them. Note that some of them are conjectured to be trans but have not been proven to be. So should be called 12 most famous trans numbers and 3 famous numbers conjectured to be trans. That is a bit long (and as short as it is only because I use `trans') so the original author is right to use the title used.

1) pi YEAH (This is probably the only number on the list such that a government tried to legally declare its value, see here for the full story.)

2) e YEAH

3) Eulers contant γ which is the limit of (sum_{i=1}^n  1/i) -  ln(n). I read a book on γ  (see here) which had interesting history and math in it, but not that much about γ . I'm not convinced the number is that interesting. Also, not known to be trans (the website does point this out)

4) Catalan's number  1- 1/9 + 1/25 - 1/49 + 1/81  ...  Not known to be trans but thought to be. I had never heard of it until reading the website so either (a) its not that famous, or (b) I am undereducated.

5) Liouville's number 0.110001... (1 at the 1st, 2nd, 6th, 24th, 120th, etc - all n!- place, 0's elsewhere)
This is a nice one since the proof that its trans is elementary. First number ever proven Trans. Proved by the man whose name is on the number.

6) Chaitian's constant which is the prob that a random TM will halt. See here for more rigor. Easy to show its not computable, which implies trans.  It IS famous.

7) Chapernowne's number which is 0.123456789 10 11 12 13 ... . Cute!

8) recall that ζ(2) = 1 + 1/4 + 1/9 + 1/6 + ... = π2/6

ζ(3) = 1 + 1/8 + 1/27 + 1/64 + ... known as Apery's constant, thought to be trans but not known.

It comes up in Physics and in the analysis of random minimal spanning trees, see here which may be why this sum is here rather than some other sums.

9) ln(2). Not sure why this is any more famous than ln(3) or other such numbers

10) 2sqrt(2) - In the year 1900 Hilbert proposed 23 problems for mathematicians to work on (see here for the problems, and see here  for a joint book review of two books about the problem, see  here for a 24th problem found in his notes much later). The 7th problem  was to show that ab is trans when a is rational and b is irrational (except in trivial cases). It was proven by Gelfond and refined by Schneider (see here). The number 2sqrt(2) is sometimes called Hilbert's Number. Not sure why its not called the Gelfond-Schneider number. Too many syllables?

11) eπ  Didn't know this one. Now I do!

12) πe (I had a post about comparing eπ to πe  here.)

13) Prouhet-Thue-Morse constant - see here

14) i^i. Delightful! Its real and trans! Is it easy to show that its real? I doubt its easy to show that its trans. Very few numbers are easy to show are trans, though its easy to show that most numbers are.

15) Feigenbaum's constant- see here

 Are there any Trans numbers of which you are quite fond that aren't on the list?

If you proof any of the above algebraic then you can probably publish it 3 or 8 or ii times!

 I can imagine a crank trying to show π or maybe even e is algebraic. ζ(3) or the Feigenbaum's constant, not so much.