Ferrer's Diagrams can be used to prove X theorems about partitions. What is X?

1978: I took an excellent  ugrad course in combinatorics from James C Frauenthal (he sometimes wrote his name as the biniomial cofficient (J choose F))  and he covered Ferrer's diagrams. They are a nice way to prove equalities about types of partitions.   See here for a definition and a few examples. I have this (possibly false) memory that there were LOTS of partition theorems proven nicely with Ferrer's diagrams.

Fast forward to 2021:

2021: My TA Emily  needs a topic to cover in Honors Discrete Math. I have this memory that there were LOTS of theorems about partitions proven with Ferrer's diagrams. We look at many websites on Ferrer diagrams  and  find only TWO examples:

The numb of partitions of n into k parts is the numb of partitions of n into parts the largest of which is k.

The numb of partitions of n into \le k parts is the numb of partitions of n into parts the largest of which is \le k

We DO find many theorems about partitions such as this corollary to the Rogers-Ramanujan theorem:

The numb of partitions of n such that adjacent parts differ by at least 2 is the numb of partitions of n such that each partition is either \equiv 1 mod 5 or \equiv 4 mod 5.

This is a HARD theorem and there is no Ferrer-diagram or other elementary proof. 

SO, I have one MEMORY but the reality seems different. Possibilities:

1) My memory is wrong. There really are only 2 examples (or some very small number).

2) There are other examples but I can't find them on the web. I HOPE this is true--- if someone knows of other ways to use Ferrer diagrams to get partition results, please comment. 

The Million Dollar Sermon

Illinois Tech has one of the greatest origin stories for a university. In 1890 Frank Gunsaulus, a pastor on the south side of Chicago, gave a sermon where he said "If I had a million dollars I would build a school to provide students from all backgrounds meaningful roles in a changing industrial society". Philip Armour, a wealthy industrialist in the congregation, went up to Gunsaulus after the sermon and said, "if you give me five years for this school, I'll give you the million dollars". Thus started the Armour Institute of Technology which after some mergers became the Illinois Institute of Technology.

The "million dollar sermon" really happened, though the exact wording and even the exact year are lost to posterity or, as speculated, hidden in a cornerstone of one of the original campus buildings. 

In 1890 we were in the beginnings of the second industrial revolution, a revolution of communication, transportation, electrification and soon the assembly line. The first revolution happened a century earlier with mechanization and the steam engine. The third revolution was computers and automation, and we are now in the early parts of the fourth industrial revolution, one based on data and information. 

There are many parallels between 1890 and today. Like 1890, the private economy is dominated by a small number of large companies that have an outsized influence in our society. Like 1890, technology is changing faster than we can manage it. Like 1890, many workers are finding their skills quickly outdated.

Today Gunsaulus's words ring truer than ever. We more than ever need to provide students of all backgrounds meaningful roles in a changing technological society. 

An investment puzzle and speculation as to why some think its hard

 This is a Guest Post by David Marcus. He gives a puzzle and its solution, which is interesting, and then speculates as to why some people get it wrong. 

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

THE PROBLEM:

Investing Puzzle or Arithmetic Can Be Useful

The following is an example of investment results that I saw in an

investment newsletter. There are two portfolios that use different

strategies. Both portfolios start with $1 million twenty years ago and

withdraw 5% each year. The idea is that you are retired and withdrawing

money to spend. Not all years are shown in the tables.

Portfolio A

Year   Return  Withdrawal    Balance

2000   15.31%      57,655  1,095,445

2005    1.81%      59,962  1,139,273

2008  -12.65%      51,000    969,004

2009   34.26%      65,049  1,235,936

2010   11.94%      69,175  1,314,331

2015   -2.48%      64,935  1,233,764

2020   10.27%      66,935  1,271,765

Total Withdrawal: 1,685,190

Change in Balance: 27.18%

======

Portfolio B

Year   Return  Withdrawal    Balance

2000   -0.95%      49,524    940,956

2005    3.80%      44,534    846,154

2008  -20.11%      35,922    682,523

2009   18.27%      40,360    766,833

2010   11.57%      42,777    812,764

2015    0.99%      50,767    964,567

2020   13.35%      65,602  1,246,433

Total Withdrawal: 1,425,573

Change in Balance: 24.64%

Portfolio A has a final balance that is 25,000 more than Portfolio B's and

had about 260,000 more in withdrawals. Does the example lend credence to

the Portfolio A strategy being better than the Portfolio B strategy?

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

THE ANSWER:

Investing Puzzle or Arithmetic Can Be Useful: Analysis

Summary: The two portfolios have about the same performance over the 20

years. The difference is mainly due to Portfolio A having a good year or

years near the beginning before much money was withdrawn. The example

merely shows that it is better to withdraw money after a gain rather than

before.

Detailed Analysis:

The scenario is: Start with X = $1 million. Withdraw 5% a year.

Define "gain factor" to be 1 plus the percentage return. For example, if a

portfolio returns 5%, then the gain factor is 1.05.

Let A_j, j = 1, ..., 20, be the gain factors each year for portfolio A.

Let B_j, j = 1, ..., 20 be the gain factors each year for portfolio B.

The final amount in portfolio A is

   F = X * A_1 * 0.95 * A_2 * 0.95 * ... * A_20 * 0.95 .

The final amount in portfolio B is

   G = X * B_1 * 0.95 * B_2 * 0.95 * ... * B_20 * 0.95 .

From the "Change in Balance" values or the balances for year 2020, we see

that F and G are almost the same:

   F = 1.271865 * X,

   G = 1.246433 * X.

But, as we learned in elementary school, multiplication is commutative, so

   F = X * 0.95^20 * \prod_{j=1}^20 A_j,

   G = X * 0.95^20 * \prod_{j=1}^20 B_j.

Since F and G are almost the same, the total gains (product of the gain

factors) for the two portfolios are almost the same, i.e.,

   \prod_{j=1}^20 A_j \approx \prod_{j=1}^20 B_j.

Then what accounts for the big difference in the amounts withdrawn?

Portfolio A must have had some good years near the beginning. (We see in

the tables that Portfolio A did better in 2000 than Portfolio B.) So, all

the example shows is that it is better to withdraw your money after your

gains rather than before.

To take an extreme example, suppose an investment is going to go up 100%

this year. It is better to take your money out at the end of the year

(after the gain) than at the beginning of the year (before the gain). This

is a triviality.

The example tells us nothing useful about the two strategies.

Note: The total gains aren't exactly the same, but the timing of the yearly

gains is what is driving the results. We have (rounding off)

   ( F - G ) / 0.95^20 = 70942.81 .

So, if there had been no withdrawals, the difference in the portfolio

balances would have been about $71,000, much less than the $260,000 +

$25,000 difference with the withdrawals.

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

WHY IS THIS HARD FOR PEOPLE?

Many people have trouble with this puzzle. The difficulty may be that such

people don't make a mental model (or a written model) of the process that

is producing the balance. If you write down (or have in your head) a

formula for the balance, then you see that the gain factors are independent

of the withdrawal factors. That is, we could withdraw more or less money,

or even deposit money, without affecting the gain factors we would use in

the model. This then leads us to consider the gain factors on their own,

and to recognize that the gain factors are the true measures of how the

strategies perform.

Ordering Beauty

First, congratulations to fellow complexity theorist and blogger Scott Aaronson for receiving the 2020 ACM Prize in Computing for "groundbreaking contributions to quantum computing". The prize is ACM's highest honor for mid-career researchers. Well deserved! 

Now back to our regularly scheduled post...

Every freshman at Cornell back in 1981 had to take two seminar courses, basically one-shot courses in an usually humanities area which required no prerequisites but lots of writing. I took my first course in philosophy. The instructor, a PhD student, at one point described his research, a philosophical argument that there is an intrinsic total ordering of beauty, say that Beethoven would always sit above the Beatles, no matter the beholder. I didn't believe him then and still don't today. A few months ago the Washington Post ran a story with the same theme entitled Maradona was great, and maybe the greatest. Can we make similar claims about artists?

Somehow we have this belief when it comes to conference submissions, that there is some perfect ordering of the submissions and a good PC can suss it out. That's not really how it works. Let's say a conference has an accept rate of 30%. Typically 10% of the submissions are strong and will be accepted by any committee. About half the submissions are just okay or worse and would be rejected. The other 40% of the submissions will be chosen seemingly randomly based on the tastes of the specific members of the program committee. Experiments in the NeurIPS and ESA conferences have bourn this out. 

Why not make the randomness explicit instead of implicit? Have the PC divide the papers into three piles, definite accepts, definite rejects and the middle. Take the third group and randomly choose which ones to accept. It will create a more interesting program. Also randomness removes biases, randomness doesn't care about gender, race and nationality or whether the authors are at senior professors at MIT or first year grad students at Southern North Dakota. 

We put far too much weight on getting accepted into a conference given the implicit randomness of a PC. If we make the randomness explicit that would devalue that weight. We would have to judge researchers on the quality of their research instead of their luck in conferences.

Given that conferences, especially the virtual ones, have no real limits on the number of papers and talks, you might say why not just accept all the papers in the middle. Works for me.

Is the following reaction to getting the first COVID shot logical?

 Alice works at a charity that puts together bag and box lunches for children.

They all wear masks and they are 12 feet apart and very careful, and nobody there has gotten COVID.

Then Alice gets here first COVID shot and says:

I am not going to work for that charity until I have had my second shot and waited  4 weeks so I am immune. 

She is really scared of getting COVID NOW that  she is on the verge of being immune. 

Is that logical? She was not scared before. So does it make sense to be scared now? I see where she is coming from emotionally, but is there a logical argument for her viewpoint? I ask nonrhetorically.

bill g. 

Quantum Stories

Scott Aaronson wrote last month about the hype over quantum computing. I'd thought I'd drop a few stories.

I was once asked to review a grant proposal (outside the US) that claimed it would find a quantum algorithm for NP-hard problems. I wrote a scathing review but the grant was funded because I failed to prove that it was impossible. I replied that they should fund my research to teleport people from Chicago to Paris because they couldn't prove I couldn't do it. I never got a response.

I was at an NSF sponsored meeting on quantum computing. I suggested, as a complexity theorist, that we need to explore the limits of quantum computing. A senior researcher said we shouldn't mention that in the report or it might hurt our chances of funding the field if they think quantum computing might not be a complete success.

I went to a Microsoft Faculty Research Summit which had a big focus on quantum computing. I complained of the quantum computing hype. My friends in the field denied the hype. Later at the summit a research head said that Microsoft will solve world hunger with quantum computing.

I was meeting with a congressional staffer who had worked on the National Quantum Initiative which coincidentally was being announced that day. I said something about high risk, high reward. He looked shocked--nobody had told him before that quantum computing is a speculative technology.

Quantum computing has generated a large number of beautiful and challenging scientific questions. Thinking about quantum has helped generate classical complexity and algorithmic results. But quantum computing having a real-world impact in the near or mid-term is unlikely. Most scientists I know working directly in quantum research are honest about the limitations and challenges in quantum computing. But somehow that message is not often getting to the next layers up, the policy makers, the research managers, the university administrators, the media and the venture capitalists. 

But who knows, maybe some quantum heuristic that doesn't need much entanglement will change the world tomorrow. I can't prove it's impossible.

Do any NP-reductions use deep mathematics? Non-rhetically

BILL: Lets say we didn't know that FACTORING NPC --> NP=coNP.

then what direction would we think Factoring in P or NPC? 

STUDENT: In P. After all, Number Theory is a deep subject and I can imagine some deep Theorem in it leading to FACTORING in P. 

BILL: That cuts both ways. I can imagine some deep theorem in NT being the key to showing 

FACTORING poly-reduces to  SAT

STUDENT: 

Deep mathematics HAS been used for algorithms. Factoring algs is one example, The graph minor theorem yielding MANY problems in P is another. Can you give me an example where deep mathematics has been used for an NPC reduction?

BILL: Oh. Gee. I do not know of any. 

STUDENT: If only you had some mechanism to ask the theory community. Maybe you could call it a web log, or weblog.

BILL: If only...

QUESTIONS

1) Are there any NPC reductions that use deep math? (I realize that the phrase `deep math' is not well defined,)

2) Are there other reductions that use deep math?

3) If P NE NP then: 

For all epsilon there is no approx-alg for MAX3SAT which yields  \ge  (7/8 + epsilon)OPT

For all delta  there is no approx-alg for CLIQ which yields > n^{-delta} OPT

No approx-alg for SET COVER which yields \ge (ln n + o(1))OPT. 

All of these proofs use  the PCP machinery or something similar. My impression is that the original PCP theorem, while long, hard, and impressive, did not use deep math. I have a vague memory of some paper or PhD thesis stating that the ONLY theorem needed was that a poly of degree d over a finite field has \le d roots. 

However to get the optimal lower bounds seemed to use some deep math. But I am more ASKING than telling. 

Want to Buy a Theorem?

This is embarrassing to admit but after a few badly timed trades on GameStop options I find myself a bit tight on money. To raise some cash, I reluctantly decided to sell one of my prized possessions, one of my theorems.

For Sale: Boolean formula satisfiability cannot be solved in both logarithmic space and quasilinear time. For a more formal and slightly more general statement and a proof, see this paper.

Bidding starts at 12 BTC (about $705,000). 

The winning bid, upon verified payment, will receive:

• The ability to give the theorem the name of your choice such as your own name, your best friend's mother's name or "Teddy McTheoremface".
• A non-fungible token (NFT) attesting ownership of the theorem and the name you have chosen for it.
• Anyone citing this result will be required to note that you own it and use the name you chose above. You cannot, however, limit the use of the theorem or receive compensation for its use. 
• By virtue of owning this theorem you will a Fortnow number of zero. This immediately gives you an Erdős number of 2. If you have previously written a paper with Paul Erdős then both of us will now have an Erdős number of 1.

Frequently Asked Questions

Q: Why this theorem?

A: The theorem is in one of my few solely authored papers and I can't afford to share the proceeds of the sale. 

Q: Doesn't Ryan Williams and others have stronger theorems?

A: The results are incomparable. Ryan gives bounds on a single algorithm with low time and space. My theorem allows different machines for the time and space bounds.

Also, to the best of my knowledge, Ryan's theorem is not for sale.

Q: Doesn't the proof of the theorem rely on other people's theorems such as Nepomnjascii? Shouldn't he get some of the value from this sale?

A: I'm not selling the proof of the theorem, just the theorem itself.

Q: If I purchase this theorem will I get to write next year's April Fools post?

A: No.

Slicing the Hypercube

Here's a neat result I heard about at virtual Dagstuhl last week, a new lower bound on the number of hyperplanes that cuts all the edges of a hypercube.

A n-dimensional hypercube has 2ⁿ vertices corresponding to the binary strings of length n. Edges are between two vertices that differ in exactly one bit, for a total of (n/2) 2ⁿ edges. Hypercubes played a large role in Hao Huang's recent proof of the sensitivity conjecture. 

A hyperplane is just a linear inequality in x₁,…,x_n the bits of the string corresponding to a vertex. An edge is cut if the inequality is true for one vertex and false for the other.

With n hyperplanes you can cut all the edges in two very different ways. 

• The hyperplanes x_i > 0 for each i. These are n orthogonal hyperplanes.
• The hyperplanes x₁+…+x_n > i for each i from 0 to n-1. These are n parallel hyperplanes.

Do you need n hyperplanes to cut all the edges? Mike Paterson found 5 explicit hyperplanes that cuts all the edges of a 6-dimensional hypercube (see survey by Mike Saks). Scaling that up means you need 5n/6 hyperplanes to cut an n-dimensional hypercube. That remains the best known upper bound.

For the lower bound, in 1971 Patrick O'Neil showed that any hyperplane can cut at most O(n^0.5) fraction of the edges (sharp by the hyperplane x₁+…+x_n > n/2). Thus you need at least O(n^0.5) hyperplanes which for 50 years was the best known bound.

Gil Yehuda and Amir Yehudayoff have given a new lower bound of O(n^0.57). The paper gives a O(n^0.51) bound but Yehudayoff said in a talk last week the bound has been improved.

Yehudayoff didn't go into much details in his 20 minute talk but the proofs uses geometry, probability and antichains. 

The result has some applications to complexity, namely you need at least n^1.57 wires in a depth-two threshold circuit for parity. But the main fun is the question itself, that we finally made progress and there is still a long way to go.

The key to my Taylor series problem: Buddy can you spare a penny, nickel, dime, or quarter

 In my last blog post I posed a question about finding the coeff of x^100 in a particular Taylor Series. The question and answer are given  here:

The key to the problem was to recognize that it was asking how many ways you can make change of a dollar using pennies, nickels, dimes, and quarters. This can be done by hand (its 242). 

1) Someone who I gave the problem to solved it by available software, but when he saw the answer was 242 he realized how to do it via making change.

2) How hard would this problem be to do completely by hand- say as a Putnam Problem? Its hard for me to say since I started with the trick and then found the problem. 

3) Is this a well known trick? 

A Taylor Series Problem

 I post a problem today and its solution on Thursday.

Comments are fine, though if you don't want to get a hint, don't read them. 

Find the coefficient of x¹⁰⁰ in the Taylor series for the rational function which has 

numerator 1 

and denominator

x⁴¹ - x⁴⁰ - x³⁶ + x³⁵ -x³¹ + x³⁰ + x²⁶ - x²⁵- x¹⁶ + x¹⁵ + x¹¹ - x¹⁰ + x⁶ - x⁵ -x+1

For better readability see my pdf file with the problem in it here

Is there a clever way to do the problem?  If the way to do it was to actually do the Taylor series then 

1) I wouldn't post it

2) I probably could not do it (or it would take too long to bother)  though maybe there are freely available programs that could. 

So yes, there is a clever solution. At least I think it's clever. 

I read the news today oh boy

I'm absolutely elated that Lázló Lovász and Avi Wigderson won the Abel Prize. More from the New York Times, Quanta Magazine and Gil Kalai. Another example of how complexity theory and theoretical computer science has reached the upper echelons of mathematics.

I'm horrified of the spa shootings in Atlanta. I've driven by those spas many times when I lived there. 

I'm saddened by the closing of Mills College in Oakland, California. I lived in a dorm Berkeley rented at Mills College during my crazy year there.

I've got mixed emotions about the death of James Levine. What he did musically with the Metropolitan opera and orchestra was nothing short of incredible. What he did to the young people he abused is inexcusable. I remember watching a Met taped videocast of Die Walküre with my daughter, enjoying the production but telling her "Do you realize we are watching an opera composed by an anti-Semite and conducted by a child molester?"  Can you separate art from artist?

I didn't understand The Art Market before the NFT sale, and I understand it less now

 (This post is a sequel to my post from Feb 13, 2007 which you can find here. While the gap from 2007 until 2021 seems large, its not as long as the gap between Knuth Vol 3 and Knuth Vol 4, nor as long as the gap between Stan Freberg Vinyl Record History of America Part I and his CD History of America Part 2, both novelty records, and quite good.)

My 2017 post was about people posting a clip on youtube and calling it `rare footage of...' 

My point was: How can something be rare if its on you tube?

I also pondered: if someone can make a REALLY REALLY GOOD copy of the Mona Lisa, that is at talent that should be respected and such a person should be able to sell it for about the same price as the original (not sure if I want the copy to be worth A LOT or the original to be worth LESS than it is.)

IF Art is to-look-at-cause-its-pretty then it should not matter who the artist is. 

IF Art is an investment then that could be risky since it does not have intrinsic value. 

IF Art is neither to-look-at or an investment then... What is it? We'll see below that one answer might be Bragging Rights. 

This is NOT a RANT, this is an admitance of my lack of understanding. (Spell check things admitance is not a word. Maybe its admitence. No, Hmmm.) 

And now there is a new wrinkle in all of this: 

69 million for a NFT (Non-Fungable Token) of an art work:story here

1) What is the buyer getting? Bragging rights?

2) Can anyone SEE the art but doesn't OWN it? I don't know..

3) If someone hacked in and got a perfect copy of the art and posted it on a website, would that be theft? Nothing was taken. 

4) In the normal art world does it happen that prices go DOWN because people wake up and say WHAT? Why did I EVER think that White on White was worth 10 million dollars? 

5) Might this happen here also? 

6) Is My Feb 13 blog, which is in a diff format (or I didn't know how to use the blogger interface then) going to one day be worth something?

Cake Cutting in Overtime

There's a new proposal out of Baltimore for a new way to handle overtime in National Football League games. This post is about American Football, soccer has its own overtime issues we won't talk about here.

Instead of randomly choosing who gets the ball, which gives an advantage to the team on offense, the Raven's coach John Harbaugh suggests a "spot and choose" rule based on cake cutting. One team picks a starting position and the other team decides whether to be on offense or defense.

Sounds intriguing but there's a problem. In cake cutting, if you cut off a crumb, everyone would definitely choose the rest of the cake. But in football suppose the spotting team chose the offensive's team one-yard line (99 yards needed for a touchdown). For spot and choose to work the one-yard line would have to be an obvious choice for defense. But many teams might still choose starting at the one-year line on offense. There's a chance you can march down the field and if not you can always punt it away. So the team that gets to choose whether to be on offense could get an advantage no matter what the spotting team did.

I still like the idea of "spot and choose". Maybe you let the first team choose not only the yard line but what down to start. Because no one would start at their one yard line at 4th down.

Are there variations for spot and choose in other sports? I like using game theory to figure out how to play actual games. 

When do I need to warn about Spoilers?

In a recent post here I mentioned in passing a plot point from the last season of The Big Bang Theory. Note that the last season was in 2019.  WARNING- do not read that post if you are watching The Big Bang Theory and do not want a plot point revealed. 

Someone who perhaps thinks Lance and I are the same person (are we? See here) left Lance a tweet complaining about the spoiler. At least I think they are complaining. The tweet is in Spanish and its here.

Either

1) Some country is two years behind America on showing The Big Bang Theory. 

2) The person who tweeted has them on DVR (or something like that) and is watching them a few years after they air (I watched Firefly on a DVD I borrowed from a friend 10 years after it went off he air. Ask your grandparents what a DVD used to be.) 

3) They are kidding us and making fun of the notion of spoilers.

This raises the question: When is it okay to post spoilers without warning? A few random thoughts:

1) ``Don't tell me who won the superb owl! I have it on tape and want to watch it without knowing who won!''  This always seemed odd to me.  Routing for events to happen that have already happened seems weird to me. When I was 10 years old I was in New York listening to a Knicks-Celtics Basketball game on the radio and during halftime I accidentally found a Boston radio station that had the game 30 minutes later (I did not realize that the channel I was on originally was 30 minutes behind). So I heard how the game ended, then switched back listening to a game knowing how it would end. I didn't route for my team (the Knicks, who lost) but it just felt very weird listening to it. If I had thought of it I might have noticed how the different broadcasts differ and got a paper out of the data, but as a 10 year old I was not thinking about how to pad my resume quite yet. 

2) I like seeing a mystery twice- first time I don't know who did it, second time I do but can look for clues I missed the first time.

3) I would have thought 2 years after a show is off the air its fine to spoil. But... maybe not.

4) It also matters how important the plot point is. I didn't think the plot point I revealed was that important. 

5) Many TV shows are predictable so I am not sure what `spoiler' even means. If I said to Darling:

 The bad guy is an unimportant character we meet in the first 10 minutes.

that does not show I've seen it before. It shows that I am a master of TV-logic.

6) With Arc TV shows this is more of a problem. While it was possible to spoil an episode (Captain Kir will survive but Ensign Red Shirt will bite the dust) it was impossible to spoil a long-term arc. TV has gotten to complicated. And I say that without having watched Game of Thrones. 

Using number-of-PhD's as a measure of smartness is stupid.

In Thor:Ragnorak Bruce Banner mentions that he has 7 PhDs. Gee, I wonder how he managed to slip that into a conversation casually.  Later in the movie:

Bruce: I don't know how to fly one of those (it an Alien Spacecraft)

Thor: You're a scientist. Use one of your PhD's 

Bruce: None of them are for flying alien spaceships.

On the episode Double Date of Archer (Season 11, Episode 6) Gabrielle notes that she has 2 PhD's whereas Lana only has 1 PhD. 

I am sure there are other examples of a work of fiction using number of PhDs as a way to say that someone is smart. In reality the number of PhD's one has is... not really a thing. 

In reality if a scientist wants to do work in another field they... do work in that field.

Godel did research in Physics in the 1950's, but it would have been silly to go back and get a PhD in it.

Fortnow did research in Economics, but it would have been silly to go back and get a PhD in it. 

Amy Farrah Fowler worked in neurobiology and then in Physics. Her Nobel prize in physics (with Sheldon Cooper) is impressive, getting a PhD in Physics would be ... odd. Imagine someone looking at here resume: She has a Nobel Prize in Physics, but does she have a PhD? Did she pass her qualifying exams?  This is the flip side of what I mentioned in a prior post about PhD's: Not only does Dr. Doom want to take over the world, but his PhD is from The University of Latveria, which is not accredited. 

There are other examples.

There ARE some people who get two PhDs for reasons of job market or other such things. That's absolutely fine of course. However, I wonder if in the real world they brag about it. I doubt it. 

Is there anyone who has 3 PhDs? I would assume yes, but again, I wonder if they brag about it. Or should. 

WHY do TV and movies use number-of-PhDs as a sign of genius? I do not know- especially since there are BETTER ways say someone is a genius in a way the audience can understand:  number-of-Nobel-prizes, number-of-times-mentioned-in-complexityblog,  number of Dundie's (see here), etc. 

Complexity is the Enemy of Speed

The title of this post came from an opinion piece in the Wall Street Journal yesterday on vaccine distribution. Many attempts to get the vaccines to the right groups first have slowed down distribution and sometime even caused vaccines to go to waste. Rules to help spread vaccines across minority groups often backfire. Often when some rules lead to inequity, we try to fix it with more rules when we need less much less. Attempts to distribute vaccines to multiple medical and pharmacy sites have made it difficult to get appointments even if you are eligible.

Randomness is the simplest way to fairness. The movie Contagion got it right, just choose birthdays by picking balls from a bin to distribute the vaccine. Then people can just show up at a few chosen sites with proof of birthday. No need to sign up.

You could argue to add back conditions like age, medical conditions, jobs but that just leads you down the same problematic path. The fastest way to get past this pandemic is to get vaccines into arms. Trust the randomness.

Good Names and Bad Names of Game Shows and theorems

 In my post on Alex Trebek, see here, I noted that Jeopardy! is not a good name for the game show since it doesn't tell you much about the show. Perhaps Answers and Questions is a better name.

The following game shows have names that tell you something about the game and hence have better names: 

Wheel of Fortune, The Price is Right, Lets make a Deal, Beautiful women have suitcases full of money (the original name for Deal-No Deal), Win Ben Stein's Money, Beat the Geeks. 

In Math we often name a concept  after a person. While this may be a good way to honor someone, the name does not tell us much about the concept and it leads to statements like:

A Calabi-Yau manifold is a compact complex Kahler manifold with a trivial first Chern class. 

A Kahler manifold is a Hermitian manifold for which the Hermitian form is closed.

A Hermitian manifold is the complex analog of the Riemann manifold. 

(These examples are from an article I will point to later---I do not understand any of these terms, though I once knew what a Riemann manifold was. I heard the term Kahler Manifold in the song Bohemian Gravity.  It's at about the 4 minute 30 second place.) 

While I am amused by the name Victoria Delfino Problems (probably the only realtor who has problems in math named after her, see my post here) it's not a descriptive way to name open problems in descriptive set theory. 

Sometimes  a name becomes SO connected to a concept that it IS descriptive, e.g.:

The first proof of VDW's theorem yields ACKERMAN-LIKE bounds. 

but you cannot count on that happening AND it is only descriptive to people already somewhat in the field. 

What to do? This article makes the  ballian point that we should   STOP DOING THIS and that the person who first proves the theorem should name it in a way that tells you something about the concept. I would agree. But this can still be hard to really do.

In my book on Muffin Mathematics (see here) I have a sequence of methods called

Floor Ceiling, Half, Mid, Interval, Easy-Buddy-Match, Hard-Buddy-Match, Gap, Train. 

There was one more method that I didn't quite name, but I used the phrase `Scott Muffin Problem' to honors Scott Huddleton who came up with the method, in my description of it. 

All but the last concept were given ballian names.  Even so, you would need to read the book to see why the names make sense. Still, that would be easier than trying to figure out what a Calabi-Yau manifold is. 

Two examples of Journalists being... Wrong. One BIG one small

 Journalists sometimes get things wrong.

This is not news, but it is interesting when you KNOW they are wrong. 

1) Scott Aaronson has a GREAT example regarding an IMPORTANT story. I recommend you to read his blog post here. Most of the comments are good also, though they go off on some tangents (e.g., is the Universal Basic Income a progressive idea?)

2) I have my own example. It is far less important than the one Scott discusses; however, inspired by Scott, I will discuss it. My example also involves Scott, but that's a coincidence. 

Quanta Magazine emailed me that they wanted to talk to me about an upcoming article on The Busy Beaver Problem. Why me? Because Scott's (same Scott as above!) survey/open problems column appeared in the SIGACT News Open Problem Column that I edit. 

This sounded fine (Spoiler Alert: It was fine, the errors they made were odd, not harmful).

Here is the Quanta Article (though I do not know if it is behind paywalls- I can never tell if I am getting access because I have a UMCP account of or anyone can have access or if I am breaking copyright laws by posting the link):    here

Here is Scotts article: here

The interviewer asked me 

a) Why did I ask Scott to write the article?

ANSWER: He had a blog post on it, and I was skeptical of why these numbers are interesting, so I asked a question in the comments. He gave a great answer, so I asked him if he wanted to write a column for my open problems column. Actually I asked him if either he or perhaps a grad student would do it- I assumed he would be too busy since his `day job' is quantum  computing. However, much to my surprise and delight he said YES he would do it.

b) Is the Busy Beaver Function important?

ANSWER: In my opinion the actual numbers are not that important but its really neat that (a) we know some of them, and (b) they are far smaller than I would have thought. Also these numbers are interesting for the following reason:  there is some  n so that proving 

BB(n)=whatever it equals

 is Ind of Peano Arithmetic. When I hear that I think the number must be really large. Its not. Its 27. NEAT! And stronger theories are related to bigger numbers. This is a way to order theories. For  ZF they have something in the 700's- MUCH SMALLER than I would have thought. Scott and others can even relate BB to open problems in Math! 

There were some other questions also, but I don't recall what they were. 

SO when the article came they mentioned me once, and its... not quite wrong but odd:

William Gasarch, a computer science professor at the University of Maryland College Park,

said he's less intrigued by the prospect of pinning down the Busy Beaver numbers than by 

``the general concept that its actually uncomputable.'' He and other mathematicians are mainly interested in using the yardstick for gauging the difficulty of important open problems in mathematics--or for figuring out what is mathematically knowable at all. 

The oddest thing about the paragraph is they do not mention my connection to Scott and the article he wrote! I reread the article looking for something like `Scotts article appeared in the SIGACT News Open Problems column edited by William Gasarch' Nothing of that sort appears. 

Without that its not clear why they are soliciting my opinion. My colleague Clyde says this is GOOD:  people will ASSUME I am some sort of expert. Am I an expert? I proofread Scott's paper so... there is that...

Also I come off as more down on BB than I really am. 

Did I claim that Mathematicians are more interested in using it as a yardstick. Actually I may have said something like that. I don't know if its true. That's my bad- I should have said that I am interested in that.

After the article came out I asked the interviewer why my role was not in the article. He said it was cut by the editor. 

NOW- NONE of this is important, but even on small and easily correctable things, they get it wrong. So imagine what happens on hard issues that are harder to get right. 

MISC: One comment on Scott's blog was about the Gell-Mann amnesia effect, see this article on it:

here

The Victoria Delfino Problems: an example of math problems named after a non-mathematician

 If you Google Victoria Delfino you will find that she is a real estate agent in LA (well, one of the Victoria Delfino's you find is such).  After this blog is posted you may well get this post on the first Google page. 

If you Google Victoria Delfino Problems you will find a paper:

The fourteen Victoria Delfino Problems and their Status in the year 2015

(ADDED LATER: a comment pointed me to an updated version, so  you can see that- I got to a pay wall.) 

How did a real estate agent get honored by having 14 problems in descriptive set theory named after her?

Possibilities before I tell you which one.

1) Real estate is her day job. Her hobby is Descriptive Set Theory. Recall that Fermat was a lawyer (or something like that- see his Wikipedia page) so perhaps she is similar. Doubtful- I think math is too hard for that now.  Or at least descriptive  set theory is too hard for that now. 

2) She just happened to remark one day, Gee, I wonder if

 ZFC + SEP(Sigma_3^1) + #   implies DET(Delta_2^1). 

Its just the kind of thing someone might just say. That was problem 4 of the 14. 

3) There are two Victoria Delfino's- one is a realtor, one is a mathematician. While plausible, that would not be worth blogging about. 

4) And now the truth: Victoria was the realtor who helped Moschovakis (a descriptive set theorist who I will henceforth describe as M) buy his house. When Tony Martin (another Desc. Set Theorist) moved to UCLA, M referred him to Victoria and she did indeed help Tony find a house. Victoria gave M a large commission which he tried to turn down. She did not want it returned, so M used the money to fund five problems. Later problems were added, but for no money. The article The Fourteen... linked to above has the full story. It also has the curious line: 

Contrary to popular belief, no monetary prize is attached to further problems. 

I didn't think any of this was so well known as to have popular believes. 

ANYWAY, this is an example of a math problem named after a non-math person. Are there others? Will the name stick? Probably not- already 12 of the 14 are solved. I have noted in a prior blog (here) once a conjecture gets proven, the one who made the conjecture gets forgotten. Or in this case the person who the conjectures is named after. 

So are there other open problems in math named after non-math people? How about Theorems?

Near Misses: 

Pythagoras: Not clear what he had to do with the theorem that bears his name. 

L'hopital's Rule: the story could be a blog in itself, and in fact it is! Not mind, but someone else: here. However L'hopital was a mathematician. 

Sheldon's conjecture (see here) was named after a FICTIONAL physicist. Note that Sheldon inspired the conjecture but did not make it. It has been solved. 

The Governor's  Theorem (see here) was named because Jeb Bush was asked for the angles of a 3-4-5 right triangle (not a fair question). 

The Monty Hall Paradox.

SO- are there Open Problems, Theorems, Lemmas, any math concepts, named after non-math people? I really mean non-STEM people. If a Physicist or an Engineer or a Chemist or Biologist or...  has their name on something, that would not really be what I want.

(ADDED LATER - someone emailed me two oddly-named math things:

Belphegor's prime, see here

Morrie's law- odd since Morrie is the FIRST name of who the name is honoring, see here 

)

Are there any other open problems in descriptive set theory  named after realtors?