When did Math Get So Hard?

I have been on many Math PhD thesis defense's  as the Dean's Representative. This means I don't have to understand the work, just make sure the rules are followed. I've done this for a while and I used to understand some of it but now there are times I understand literally none of it. As a result, when the student leaves the room and we talk among ourselves I ask


When did Math get so hard?

I mean it as a statement and maybe a joke, but I decided to email various people and ask for a serious answer. Here are some thoughts of mine and others

1) When you get older math got harder. Lance blogged on this here

2) When math got more abstract it got harder. Blame Grothendieck.

3) When math stopped being tied to the real work it got harder. Blame Hardy. 

4) Math has always been hard. We NOW understand some of the older math better so it seems easy to us, but it wasn't at the time. 

5) With the web and more people working in math, new results come out faster so its harder to keep up.

6) All fields of math have a period of time when they are easy, at the beginning, and then as the low-hanging fruit gets picked it gets harder and harder.  So if a NEW branch was started it might initially be easy. Counterthought- even a new branch might be hard now since it can draw on so much prior math. Also, the low hanging fruit may be picked rather quickly. 

Fall 2021 Jobs Post

We're in the midst of a great transformation in computing, one where data takes center stage and I predict this will start to have a larger effect on hiring in computer science departments. We'll see a bigger need to grow in data science, particularly machine learning and autonomous systems. Cybersecurity and quantum computing will also grow with a push due to competition with China. Quantum winter might be coming but we're not there yet.

Harder to predict is the rest of computer science, such as traditional areas like networks, operating systems, programming languages and, yes, theory, particularly theory unrelated to quantum, learning or security. There is still a need for CS departments to grow in these areas, but we may be moving away from a rising tide raising all boats. On the other hand due to the digital transformation of just about everything, non-CS departments are hiring people who look a lot like computer scientists.

Other factors may cause US universities to be more conservative in hiring such as a drop in male students, the upcoming demographic cliff, an unclear future for international students coming to the states, and a lingering COVID budget hangover.

So go get a job while the going is still good though I would not suggest forgoing a faculty position for a postdoc, particularly if you aren't working in data science.

I also wonder how the post-COVID world will affect the job search. We'll probably see more virtual interviews than the pre-COVID days at least in the early rounds. It's also harder for students to network and make themselves known at virtual and hybrid conferences which will likely persist for some time.

Give yourself a good virtual face. Have a well-designed web page with access to all your job materials and papers. Maintain your Google Scholar page. Add yourself to the CRA's CV database. Find a way to stand out, perhaps a short video describing your research. 

Best source for finding jobs are the ads from the CRA and the ACM. For theoretical computer science specific postdoc and faculty positions check out TCS Jobs and Theory Announcements. If you have jobs to announce, please post to the above and/or feel free to leave a comment on this post. Even if you don't see an ad for a specific school they may still be hiring, check out their website or email someone at the department. You'll never know if you don't ask.

Squaring the circle is mentioned in a Gilbert and Sullivan comic Opera.

The problem of squaring the circle: Given a circle, construct (with straightedge and compass) a square with the same area. While browsing the web for more information on this problem (for the blog entry on problems that might be similar to P vs NP: here)  I came across the following:

In the Gilbert and Sullivan comic opera Princess Ida, in the song Gently, Gently  is the line:

                                    ... and the circle they will square it one fine day.

(To hear the song see here. The line is towards the end.) 

They lyrics are here. That website begins  gsarchive.net which made me wonder Did I at one time set up a website of math refs in Gilbert and Sullivan plays (gsarch is very close to gasarch) ? which IS the kind of thing I would do. The answer is no:  gsarch stands for Gilbert and Sullivan archive. They could have called it gasarch if they used the and in Gilbert and Sullivan but abbreviated archive as arch. Then I would have been far more confused. 

Moving on...

In 1884 Princess Ida opened in 1884. For more on this comic opera see here.

In 1882 pi was proven  transcendental and hence one cannot square the circle. For more on pi being transcendental see here.

Kolmogorov Random Thoughts on all of this

0) The song is sung my three men who are making fun of the notion of a women's college. The song is about all the things the women are trying to do that are absurd such as squaring the circle. They also mention perpetual motion machines. 

1) Did G and S know that the squaring the circle had been proven impossible, or just that it was thought to be impossible, or just that it was thought to be hard?

2) Was it known that perpetual motion machines were impossible? Or just very hard? 

3) G and S used Mathematics in at least one other song:  I am the very model of a modern major general, from The Pirates of Penzance  has the lines:

                                       I'm very well acquainted too with matters mathematical

                                       I understand equations, both the simple and quadratical,

                                       About binomial theorems I'm teeming with the a lot o' news---

                                       With many cheerful facts about the square of the hypotenuse

and later 

                                        I'm very good at integral and differential calculus

See here for all the lyrics. The website mentioned in the next point has a pointer to a YouTube video of people singing it. 

4) There are many parodies of Modern Major General. The earliest ones I know of is Tom Lehrer's  The Elements. Since making a website of them IS the kind of thing I would do,  while writing this post I did it (Are we compelled to do things that fit our image of ourselves? Yup.) The website is here. It has 36 parodies (as of Oct 17, 2021 when I wrote this blog--- it may have more if you read this later.) That may seem like a lot, but it pales in comparison  to the most satirized song of all time: The 12 days of Christmas which I did an ugly lyrics-only website for back before html had nice tools, see here. It has 143 songs on it but I am sure there are many more. (Note to self: redo that website when you have time. Maybe when I retire.) 

4) I suspect that G and S knew more math, or perhaps knew of more math,  than Broadway composers know now. I suspect this is a more general trend: people are more specialized now. Having said that, I need to mention the off-Broadway musical Fermat's last Tango which I liked more than Lance (see his post on it here). 

5) How much math would you need to know in order to insert some into your play or movie? With Wikipedia and other web sources you could find out some things, but you would have to have some idea what you are looking for. And perhaps you would need some math background in order to even want to insert some math into your work in the first place. 

6)  Here's hoping someone will make a musical about William Rowan Hamilton using this song here as a starting point. I blogged rather optimistically about that possibility here.

Is MATH Ready for P=NP? Is Alexandra Fahrenthold Ready for P=NP?

(This post was inspired by Harry Lewis emailing me about his granddaughter.)

Harry Lewis's grand daughter Alexandra Fahrenthold (see both pictures) wants information

on how to claim the Millennial prize, so she will be ready.

This raises the question: How likely is it that Alexandra will resolve P vs NP (or perhaps some other Millennium problem if she wants to rebel against her grandfather)?

And more seriously:

1) Have we made progress on P vs NP? (I think not.)

(By we  I mean the community, not Harry and I or Harry and I and Alexandra,

for which the answer is a more definite NO.)

2) If not then why not?

3) How does this compare historically to other open problems in Math?

We will refer to progress made in solving an open problem, though that is a tricky notion since only after a problem is solved can you look back and say what was progress.  One might also count subcases (e.g., n=4 case of FLT) as progress even if they don't help lead to the final proof. I quote a letter from Harry Lewis to me upon reading a first draft of this post:

The one larger point I would suggest adding is to add my operational definition of progress: Progress is being made on a problem if, when the solution is published, it will cite work being published today. Of course that is “operational” only after the fact. Demillo Lipton Perlis at the end have a nice riff on this. The alchemists thought they were making progress on turning lead to gold but they weren’t, even though we know that was actually a solvable problem. Likewise jumping off of higher and higher buildings was not making progress toward heavier than air flight.

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

1) Have we made progress on P vs NP?

a) I tell my students that we have made progress on ruling out certain techniques.

They laugh at that, at which point I decide to not tell them that my PhD thesis was about that sort of thing (oracles). I could say

Once you know what's not going to work you can concentrate one what is going to work.

But that sounds hollow since very few people are working on techniques that

might work (The Geometric Complexity Program, see here, is the only exception I know of.)

b) Are there any partial results? Ryan Williams showed that SAT (and also counting mod versions of it) cannot be done in time n^c and space n^{o(1)} where c is 2cos(2pi/7) (see here).  That is the only concrete lower bound on SAT that I know of.  Is it progress? Sam Buss and Ryan Williams later showed (see here) that, using current techniques, this cannot be improved. If that inspires new techniques that push it further, that would be great. So it is progress? Hard to know now. 

c) There are some circuit lower bounds. One can debate if this is progress.

It will be a much better informed debate once the problem is solved.

So I would say VERY LITTLE PROGRESS.

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

2) If not then why not?

a) It's only been open for 50 years. A drop in the mathematical bucket.

Counterargument: 50 years of 20th and 21st century mathematics is A LOT.

b) Sociology: The academic computer science conference-model induces us to get out a paper in time for the next conference deadline, and not think deeply about a problem.  Carl Smith thought that P vs NP would be solved by the son of a member of the communist party in the USSR (when there was a USSR) who did not have the pressure to get tenure and grants and such. He may be right.

Counterargument: there are some (1) mavericks who buck the system, and (2) people like Carl's son-of-a-party-member who are allowed to think deeply for years.

c) It's just dang hard! That's the real question. Paul Erdos said of the Collatz Conjecture:

        Mathematics may not be ready for such problems.

Is that true of P vs NP as well?

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

3) History and Philosophy.

(In college I once took the following four courses in one semester: History of Philosophy, Philosophy of History, Philosophy of Philosophy, History of History.)

Let's look at problems that were open and then solved:

a) The Three Greek Problems of Antiquity: Squaring the circle (given a circle, construct a square with the same area), doubling the cube (given a line that is the edge of cube, construct another line that is the edge of a cube with twice the volume), trisecting an angle (given an angle, construct two lines whose angle is 1/3 of the given angle), with a straightedge and compass. (When I first heard of this problem I wondered how knowing what direction was North would help trisect an angle.) Posed in roughly 400BC. Not clear what posed means in this context. Did the ask for a construction OR did they ask for EITHER a construction OR a proof that there wasn't one?

This might be the closest analogy to P vs NP: At the time the problem was stated

 MATHEMATICS WAS NOT READY FOR SUCH PROBLEMS. 

It took lots of new math, a better notation, and a different way of looking at numbers, to show that they  could not be done: Pierre Wantzel--doubling the cube (1837),Pierre Wantzel--trisection (1837), Lindemann-Weierstrass--squaring the circle (1882).

NOTE: Some sources list a fourth problem: constructing every regular polygon. Pierre Watnzel proved, in 1837, that a regular n-gon is constructible iff n is the product of a power of 2 and distinct Fermat  primes. (Why isn't Wantzel better known?) 

b) Fermat's Last Theorem. Given its origin, not quite clear when it was posed but 1640's seems fair. This could not be solved when it was posed (On an episode of Dr. Who they claim that Fermat had a simple proof. Note that Dr. Who is fictional and their PhD (if they has one) is probably not in mathematics.) 

MATHEMATICS WAS NOT READY FOR SUCH PROBLEMS, 

but not as much as the three Greek problems. Very steady progress on it, see  here. One of the real milestone was connecting it to other problems in Math. And then Wiles proved it in the 1990's. While the solution was a surprise when it happened it was not that much of a surprise.

QUESTION: Is P vs NP more similar to Greek3 or to FLT? 

c) Peano Arithmetic (and similar systems) are incomplete. Hilbert's 2nd problem (1900) asked to show the axioms of PA were consistent. Godel (1931) showed this could not be done.  Moreover, there are TRUE statements about numbers that PA cannot prove. I think people mostly thought PA was complete so one of the innovations was to think it was incomplete.  

MATHEMATICS WAS READY FOR SUCH PROBLEMS 

but it took the boldness to think PA was incomplete to solve it.  The math needed was known when Hilbert posed the problem. But of course, how to put it together was still quite a challenge.

d) The Continuum Hypothesis, CH, is that there is no cardinality between N and R. Cantor in 1878 asked for a proof that CH was true. It was Hilbert's first problem in 1900.

When Hilbert posed this problem in 1900

MATHEMATICS WAS NOT QUITE  READY FOR SUCH PROBLEMS.

The math to solve it wasn't quite there, but wasn't so far off (of course, that's in hindsight). Godel's model L (1940) was brilliant, though Lowenhiem-Skolem had constructed models.  A model of set theory that was defined by levels was, I think, though of by Russell (though in a very diff way than L). When Cohen did a model where CH is false (1963) he invented forcing for Set Theory, though forcing had already been used in Recursion theory (The Kleene-Post construction of intermediary Turing degrees.)

e) Hilbert's tenth problem (1900): Find an algorithm that will, given a poly in many variables over Z, determine if it has a solution in Z.

MATHEMATICS WAS ALMOST READY FOR SUCH PROBLEMS.

I turns out that there is no such algorithm. Similar to CH: Once it was thought that it was unsolvable, the proof that it was unsolvable just took a few decades. However, it did need  the definition of computable to be pinned down.  Davis-Putnam-Robinson outlined what was needed in the 1950's,and Matiyasevich finished it in 1970.  While it required just the right combination of ideas, and lots of cleverness, the math needed was known.

CAVEAT: There are many restrictions of H10 that are still open. My favorite: is the following solvable: given k, does x^3 + y^3 + z^3 = k have a solution in Z? (See my blog post on this problem here.) For a survey of what is known about subcases see (1) my paper here, though it is has been argued that I am looking at the wrong subcases (see my blog post on this here), and (2) Bogdan Grechuk's paper here

CAVEAT: Matiyasevich has suggested that Hilbert really meant to ask about equations and solutions over  Q. That problem is still open. If it is unsolvable, that might be proven reasonably soon. If it is solvable, then

MATHEMATICS IS NOT READY FOR SUCH PROBLEMS.

f) The four color theorem. Posed in 1852 by Francis Guthrie, proven in 1976. Haken, Appel, and Koch (more on that last name later) did do some very impressive math to set the problem up, and the computer program to finish it off. When the problem was posed (1852) the computing power was not up to the task. So 

COMPUTER SCIENCE WAS NOT READY FOR SUCH PROBLEMS.

Could the ideas to set it up have been done earlier? Maybe, but not much earlier. The result is often attributed to Haken and Appel, but actually there are two papers, and Koch is an author on the second one. Note that (1) Robertson, Sanders, Seymour, Thomas had a simpler, though still computer proof (1996), and (2) Werner Gonthier formalized the proof inside the Coq proof assistant in 2005.

CAVEAT: An open problem that is hard to state precisely is to come up with a non-computer proof.

CAVEAT: There is a non-computer proof that every planar graph is 4.5-colorable, see my blog post in this here. (No, this is not a joke. If it was I would make if funnier and claim there is a non-computer proof that every planar graph is 4 + 1/e colorable.)

g) Poincare Conjecture. Conjectured in 1904 and solved in 2002. To bad---if it was solved in 2004 it would be exactly 100 years. There was some progress on this all along so I don't know which step was the hard one though probably they were all hard. This one is harder for me to speculate on. When it was solved and Darling wanted to know why it was worth $1,000,000 I told her that it says if something tastes and smells and feels like a sphere, its a sphere. She was unimpressed.  But back to our story:  in hindsight,

MATH WAS READY FOR SUCH PROBLEMS

 since there was steady progress. I think of NOT READY as meaning NO progress, NO plan.

h) The Erdos Distance Problem: Show that for any n points in the plane the number of distinct distances is Omega(n/\sqrt{log n}). Not quite solved, but a big milestone was Gutz and Katz proof of Omega(n/log n). For that result

MATH WAS READY FOR SUCH PROBLEMS

Steady progress:  see the Wikipedia entry here. What's of interest to us is that there was a barrier result of Omega(n^{8/9}) by Ruzsa (apparently unpublished) that said the techniques being used could not do better-- so people, in short order, found new techniques.  Here is hoping that happens with P vs NP.

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

Let's look at problems that are open and unsolved.

a) Collatz Conjecture (also called the 3x+1 conjecture). I asked

Jeff Lagarias, who is an expert on the problem:

Is it true? When will it be resolved? He said Yes and Never.

I once heard there has been NO progress on this problem, though I later  heard that Terry Tao has made some progress. In any case, not much progress has been made. Maybe Erdos was right.

QUESTION: Why does my spell checker think that Collatz is not a word? 

b) Small Ramsey Numbers. I asked Stanislaw Radziszowski, who is an expert on Small Ramsey Numbers (he has a dynamic survey on small Ramsey numbers here) 

What is R(5)?  When will we know? He said 43 and Never.

Worse than being hard, I don't think any nice math has come out of trying to find R(5,5). Too bad. The coloring that gives the lower bound for R(4) and some (perhaps all) of the R(i,j) where i,j\le 4 can be derived from group theory. YEAH! But then connections to interesting math just... stopped. For now? Forever? Joel Spencer told me this is an example of the law of small numbers: patterns that hold for small numbers stop holding when the numbers get too big. (I've seen other things  called the law of small numbers as well.) 

MATH MAY NEVER BE READY FOR SUCH PROBLEMS 

If no interesting math comes out of the attempt to find the exact values of the Ramsey Numbers, then it is not a good problem. 

Note:  The conversations about Collatz and R(5) were within 10 minutes of each other. Depressing day!

c) The Twin Primes Conjecture. Sieve methods have been used to get partial result. YEAH! Yitang Zhang showed there exists infinite x such that x and x + 70million (something like that are prime. YEAH. Its been gotten down to x, x+246 and with various assumptions x,x+12 or x, x+6). YEAH! but Sieve methods are known to NOT be able to prove the  conjecture. Dang it!

DO NOT KNOW IF MATH IS READY FOR SUCH PROBLEMS.

I think people are kind of stuck here. Much like P vs NP, though at least they have some partial results. By contrast, with regard to P vs NP we don't even have that (unless you count Ryan's lower bound on SAT---maybe you do).

Note: I found that information here which seems to be an Encyclopedia Britannica  website. I would have thought that, with the web and Wikipedia, they would be out of business. Good for them to still be in business! 

d) I am not qualified to write about any of the Millennium prizes except P vs NP (am I even qualified for that?)  so I ask my readers to leave opinions (informed or not) about, for which of them, 

MATH IS NOT READY FOR SUCH PROBLEMS

One of the people who worked on the Riemann Hypothesis said: 

I do not recommend spending half your life on the Riemann Hypothesis. 

That raises a different question: When do you give up? (topic for a different blog post). 

e) I am also not qualified to write about the Hilbert Problems where are still unsolved. Note that some of them are not well enough defined  to ever be resolved (H6: Make Physics rigorous) and some are either solved or unsolved depending on who you ask (H4: Construct ALL metrics where lines are geodesics-- surely, he didn't mean ALL metrics. Probably right, but  stop calling me Shirley!) For a byte more about Hilbert's problems, including a few paragraphs on H4,  see my reviews of two books on them, here. Same as the last item- if you have an opinion (informed or not) about, for which of them that are though to be sort-of open, is math ready for them, leave a comment. 

CODA: Alexandra will be working on Collatz this summer!

Let's wish her luck!

A Young Person's Game?

When László Babai first announced his graph isomorphism in quasipolynomial time result, I wrote

We think of theory as a young person's game, most of the big breakthroughs coming from researchers early in their careers. Babai is 65, having just won the Knuth Prize for his lifetime work on interactive proofs, group algorithms and communication complexity. Babai uses his extensive knowledge of combinatorics and group theory to get his algorithm. No young researcher could have had the knowledge base or maturity to be able to put the pieces together the way that Babai did.

Babai's proof is an exceptional story, but it is exceptional. Most CS theorists have done their best work early in their career. I got myself into a twitter discussion on the topic. For me, I'm proud of the research I did through my forties, but I'll always be best known, research wise, for my work on interactive proofs around 1990. It would be hard to run a scientific study to determine cause and effect but here are some reasons, based on my own experiences, on why we don't see research dominated by the senior people in theory.

The field changes - Computation complexity has moved from a computational-based discipline to one now dominated by combinatorics, algebra and analysis. I'm not complaining, a field should evolve over time but it plays less to my strengths. It's hard to teach this old dog new tricks.

The fruit hanged lower - there were important problems with easier proofs available then not available now

Responsibilities - You have fewer as a PhD student, postdoc or assistant professor.

Family - becomes more of a focus.

Taking on new jobs - Many academics, though not all, take on administrative roles at their university or , or leave academics completely. 

The young people have the new ideas - And older people get settled in their ways

The thrill is gone or at least decays - Your first theorem, your first talk, your first conference paper gives you a level of excitement that's hard to match.

Existentialism - The realization that while computing has no doubt changed the world, my research, for the most part, hasn't.

Cognitive Decline - Probably the most controversial but for me I find it hard to focus on problems like I used to. Back in the day I prided myself on knowing all the proofs of my theorems, now I can't even remember the theorems.

Honestly there is just nothing wrong with taking on new roles, writing books, surveys and blogs, focusing on teaching and mentorship and service and leaving the great research to the next generation.

I have a book out on muffins (you prob already know that)

Lance: How come you haven't blogged on your muffin book? You've blogged about two books by Harry Lewis (see here and here) one book by the lesswrong community (see here), and you even did a mashup of a post by two different Scott A's (see here),  but not on your own work.

Bill: I thought I did a post on my muffin book.

Lance: No. You have blogged about the muffin problem, and sometimes you mention either the book or the problem in passing, but you haven't had a post that says

HEY, I wrote a book!

And this is all the more strange since you asked me to have the book on our blog page. 

Bill: (Searches blog with keyword muffin and finds no ref to muffin book). Well pierce my ears and call be drafty! I have not posted on the muffin book! Do you recall my thoughts on when to tell people you are working on a book?

Lance: No

Bill:  I had a college roommate who was an aspiring science fiction writer who told me there are two kinds of people: Those who talk about writing a book, and those who write a book. I have adapted this to:

Do not tell people you are writing a book until you are picking out the cover art.

Lance: I posted about my book when I hadn't even decided on the title. But your cover art is picked out (see here).  And, by the way, its very nice, though it makes me hungry. So I think you can begin talking about the book.

Bill: Indeed! I will!

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

Hey I have a book! (See here to buy it on amazon.) 

Title: Mathematical Muffin Morsels: Nobody Wants a Small Piece

by Gasarch, Metz, Prinz, Smolyak

(The other authors were undergraduates when we wrote the book. Prinz and Smolyak are now grad students in CS, Metz is in Finance.) 

Origin: 

Martin Gardner wrote a Mathematics Recreational column for Scientific American for many years, starting in 1956 and ending in the early 1980s. For many STEM people of my generation (Using my fake birthday of Oct 1, 1960, I am 62 years old) Martin Gardner's columns were both an inspiration and an early exposure to mathematics. His columns also made the line between Mathematical Recreation and so-called serious mathematics thin or nonexistent. (See here for a review of Martin Gardner in the 21st century, a book about the kind of math Gardner wrote of. The book makes a mockery of the distinction between recreational and serious mathematics.) He passed away in 2010 at the age of 95.

There is a gathering in his honor that is hold roughly every 2 years, called Gathering For Gardner. (It was cancelled in Spring 2020 and Spring 2021 because of COVID- though its in Atlanta where the CDC is, so they could have had it as an experiment and told the CDC the results). You have to be invited to goto it. I got an invite for 2016 from my contact at World Scientific who published my previous book, Problems with a Point: Exploring Math and Computer Science co-authored with Clyde Kruskal  (I had two blogs on it, here and here, and you can buy it on amazon here.) I did three posts on G4G-2016 (here, here, and here).

Aside from seeing some great talks that I understood and liked, I also picked up a pamphlet titled:

The Julia Robinson Math Festival

A Sample of Mathematical Puzzles

Compiled By Nancy Blackman

One of the problems, credited to Alan Frank, was

How can you divide and distribute 5 muffins for 3 students so that everyone gets 5/3 and the smallest piece is as big as possible?

They had some other values for muffins and students as well. 

I solved the (5,3) problem and the other ones as well. That was fun. 

When I got home I began looking at the problem for m muffins and s students. I let f(m,s) be the biggest smallest piece possible for giving out m muffins to s students. I proved a general theorem, called the Floor-Ceiling theorem, that always gives an upper bound, FC(m,s) on f(m,s). I worked out formulas for 

f(m,1) (trivial), 

f(m,2) (trivial), 

f(m,3) (its always FC(m,3),

 f(m,4) (its always FC(m,4)).

While working on f(m,5) I found that  f(m,5) was always FC(m,5) EXCEPT for m=11. So what's up with f(11,5)?  

By the Floor Ceiling theorem f(11,5) \le 11/25. We (at that point several ugrads and HS students had joined the project)  were unable to find a protocol that would show f(11,5)\ge 11/25. Personally I thought there WAS such an protocol but perhaps it was more complicated than the ones we had found (We were finding them by hand using some easy linear algebra.) Perhaps a computer program was needed. We did find a protocol for f(11,5)\ge 13/30, which surely was not optimal. 

While on an Amtrak I began working out the following train of thought: The protocol for f(11,5)\le 11/25 MUST have 

(1) every muffin cut into two pieces,

(2) 3 students get 4 pieces, 

(3) 2 students get 5 pieces. 

While working on getting a protocol for f(11,5)\le 11/25 with these properties I found that... there could be no such protocol! Then by reworking what I did I found that f(11,5)\le 13/30. So it was done! and we had a new technique, which we call The Half Method. To see the full proof see my slides here

The story above is typical: We get f(m,k) for all 1\le k\le SOMETHING, we get stuck, and then we find ANOTHER technique to show upper bounds (which in this case are limits on how well we can do). This happened about 8 times depending on how you count.  After a while we realized that this could not just be an article, this was a book! World Scienfiic agreed to publish it, and its out now.

Misc Notes

1) I got a conference paper out of it, in the Fun with Algorithms Conference, with some of the co-authors on the book, and some other people. here is the conf paper.

2) Early on we realized that f(m,s) = (m/s)f(s,m) so we only had to look at the m>s case.

3) The fact that f(m,s) exists and is rational is not obvious, but is true. In fact, f(m,s) can be found by a mixed-int program. 

4) Late on in the process I found that there was a by-invite-only math newsgroup that had discussed the problem, and in fact was where Alan Frank first posted it. I obtained their materials and found that they had already shown f(m,s)=(m/s)f(s,m) and also that the answer is always rational and exists. Aside from that our results did not overlap.

5) Even later in the process Scott Huddleston emailed me (out of the blue) that he had a program that solved the muffin problem quickly. I was skeptical at first, but he did indeed have a whole new way to look at the problem and his code was very fast (I had Jacob Prinz, one of the co-authors on the book, recode it). Later Richard Chatwin (see here) seems to have proven that Scott's method always works. The approach of Scott and Richard is where to go if you want to do serious further research on Muffins. My book is where you want to go if you want to learn some easy and fun math (a HS student could read it). 

6) I co-authored a column with Scott H, Erik Metz, Jacob Prinz on Muffins, featuring his technique, in Lane's complexity column, here.

7) I had an REU student, Stephanie Warman, write a muffin package based on the book.

8) I gave a talk an invited talk on The Muffin Problem  at a Joint AMS-MAA meeting. 

9) I gave a talk at Gathering for Gardner 2018 on The Muffin Problem. 

10) I often give talks on it to groups of High School students.

11) When I teach Discrete Math Honors I talk about it and assign problems on it- it really is part of the course. As such its a good way to reinforce the pigeon hole principle. 

12) I contacted Alan Frank about my work. We arranged to meet at an MIT combinatorics seminar where I was to give a talk on muffins. He brought 11 muffins, with 1 cut (1/2,1/2), 2 cut (14/30,16/30),

and 8 cut (13/30,17/30) so that the 11 of us could each get 11/5 with smallest piece 13/30. 

13) Coda: 

Why did I keep working on this problem?  I kept working on it because I kept hitting barriers and (with co-authors) breaking them with new techniques that were interesting.  If early on a barrier was not breakable then I would have stopped. If (say) Floor-ceiling solved everything than I might have gotten a paper out of  this, but surely not a book.

Lesson for all of us: look around you! Its not clear what is going to inspire a project!

Lasting effect: I am reluctant to throw out old math magazines and pamphlets since you never know when one will lead to a book.

C++ is for Cookie and That's Good Enough for Me

Potbelly, a local sandwich chain, made me an offer I couldn't refuse: change my password and earn a free (and quite tasty) oatmeal chocolate chip cookie. A free cookie is a great motivator, and checking that this wasn't some clever phishing attack, changed my password and got my cookie. Not sure why Potbelly wanted me to change my password but happy to take their cookie.

Potbelly likely didn't make this offer to everyone so what if you want a cookie?

1. Use an app to get a cookie delivered.
2. Visit a specialty cookie store.
3. Go to your local supermarket and pick up a package of Chip's Ahoy.
4. Buy some pre-made cookie dough and put it in the oven.
5. Buy some cookie mix, add ingredients and bake.
6. Find a cookie recipe, buy the ingredients and get cooking
7. Get fresh ingredients direct from a farm stand
8. Grow and gather your own ingredients, ala Pancakes Pancakes

In machine learning we seem to be heading into a similar set of choices

1. Not even realize you are using machine learning, such as recommendations on Netflix or Facebook.
2. Using ML implicitly, like talking to Alexa
3. Using pre-trained ML through an app, like Google Translate
4. Using pre-trained ML through an API
5. Using a model like GPT-3 with an appropriate prompt
6. Use an easily trained model like Amazon Fraud Detector
7. An integrated machine learning environment like Sagemaker
8. Use pre-built ML tools like TensorFlow or PyTorch
9. Code up your own ML algorithms in C++
10. Build your own hardware and software

and probably missing a few options.

When you want cookies or learning, do you buy it prepackaged or do you roll your own? And when people offer it to you for free, how wary should you be?

How have computers changed society? Harry Lewis (with co-authors) have a book out on that.

 (Disclosure - Harry Lewis was my PhD advisor.)

It seems like just a few weeks ago I I blogged about a book of Harry Lewis's that was recently available (see here).  And now I am blogging about another one. Writing two books in two years seems hard! I can only think of one other computer scientist who has done that recently (see here and here).

In 2008 Abelson, Ledeen, and Lewis wrote 

Blown to Bits: Your Life, Liberty, and Happiness after the Digital Explosion

which I reviewed in SIGACT news, see here

Both computers and society have changed since 2008. Hence an update was needed. 

In 2021 Adelson, Ledeen, Lewis, and Seltzer wrote a second edition.

Should you buy the new version if you bought the old version? 

1) Not my problem- I got them both for free since I reviewed them. 

2) Not your problem- The second edition is available free-on-line here. Is that a link to some dark corner of the dark web? No, its the formal webpage about the book. So the book is available free-on-line legally, if you care (and even if you don't care). 

3) If you like paper, the book is on amazon. (If you don't like paper, the book is still on amazon). 

I reviewed it in SIGACT news. A non-paywalled link: here (is that link legal? I have no idea.) 

In this post I'll just mention two things that changed since the last book

1) Shared Music and pirating were an issue back in 2008.  It does not seem to be anymore since there is now a variety of services that seem to make pirating not worth it: itunes, streaming services, and some bands give it away for free and ask you to pay what its worth. Movies are still struggling with this issue. 

2) AI systems that reinforce existing bias is a new problem.