Nostalgia corner: John Riordan’s referee report of my first paper

In 1971/1972 academic year, I was an undergraduate student at the Hebrew University of Jerusalem and toward the end of the year I wrote a paper about Abel’s sums. I sent it to John Riordan the author of the books  “Combinatorial Identities” and “Combinatorial Analysis”.

I received this letter shortly after my 17th birthday, and I was surely very happy to read the sentence “I think you have had a splendid idea”.  Here is part of Riordan’s remarks. The full report is here.

It took me some time to revise the paper and get it printed. And here is the report for the second version.

And here is part of Riordan’s second round of remarks. The full report is here.

I was certainly happy to read the following sentence: “I would remark that the result for  p = -1  is new and perhaps the simplest derivation of Abel’s result.”

In 1978 I actually visited John Riordan in his office at Rockefeller University, NYC. I remember him as very cheerful and he told me that when his first book appeared he was working at Bell Labs and his managers wanted to talk to him. He was a bit worried that they would not approve of him spending time and effort to write a book in pure mathematics. But actually, they gave him a salary raise!

(If you have a picture of John Riordan, please send me.)

In 1979 the paper appeared.

Posted in Combinatorics, personal | Tagged , , , | 7 Comments

At the Movies III: Picture a Scientist

A few days ago I saw the great, emotionally steering, movie Picture a Scientist. I strongly recommend it. Here is the link to the  hompage trailer, and IMBd page.

SYNOPSIS

PICTURE A SCIENTIST chronicles the groundswell of researchers who are writing a new chapter for women scientists. Biologist Nancy Hopkins, chemist Raychelle Burks, and geologist Jane Willenbring lead viewers on a journey deep into their own experiences in the sciences, ranging from brutal harassment to years of subtle slights. Along the way, from cramped laboratories to spectacular field stations, we encounter scientific luminaries – including social scientists, neuroscientists, and psychologists – who provide new perspectives on how to make science itself more diverse, equitable, and open to all.

Raychelle Burks, Nancy Hopkins, and Jane Willenbring 

Posted in Movies, Women in science | Tagged , , , , | 2 Comments

At the Movies II: Kobi Mizrahi’s short movie White Eye makes it to the Oscar’s short list.

Update:  White eye have made it to the list of five Oscar candidates! Congratulations!

My nephew Kobi Mizrahi is a well known movie producer and it was just announced that his short film “White eye” (עין לבנה) made it to the short list of ten Oscar candidates in the live-action short category. The director is Tomer Shushan.

Congratulations, Kobi!

I saw the movie and I highly recommend it! Let me use use the opportunity to recommend a full-length action movie the Dive  that Kobi produced two years ago.

Kobi Mizrahi

Our previous post: And the Oscar goes to: Meir Feder, Zvi Reznic, Guy Dorman, and Ron Yogev.

Posted in Movies, People, personal | Tagged , | Leave a comment

And the Oscar goes to: Meir Feder, Zvi Reznic, Guy Dorman, and Ron Yogev

My mother Carmela Kalai often said that if there was something she is thankful for it was that she was born in the era of movies. Indeed, she loved movies from a very early age throughout her life.  So, I was especially excited to hear that my long-time friend Meir Feder and his colleagues at the Amimon company won the 2021 Academy Award for scientific contributions to the movie industry. It is very nice to see deep ideas from information theory, computer science and engineering come to play in the movies. Congratulations!

From right to left: Ron Yogev, Meir Feder, Zvi Reznic and Guy Dorman

Here is Meir’s thank-you speech.

Posted in Computer Science and Optimization, Information theory, Movies | Tagged , , , | 1 Comment

Thomas Vidick: What it is that we do

A wonderful post by Thomas Vidick to cheer you up in difficult times with a lot of food for thought and for discussion. What is it that we (mathematicians) do?

It goes back to ancient Greece and also mention the legendary historian, poet, and philosopher Reviel Nets (whose two wonderful talks in Jerusalem we mentioned here and here).

MyCQstate

This post is a follow-up on some somewhat off-hand comments that I made earlier regarding the notion of truth in a “proof-based” discipline such as pure mathematics or theoretical computer science. Since the former is easier to circumscribe and also has a larger literature available on it, for the purposes of the post I will discuss my emerging take on truth in mathematics; what I say applies to TCS as well. (I wasn’t able to find satisfactory writings on the practice of computer science, even more broadly interpreted than just “theory”; any pointers on this are very welcome.) I obviously don’t claim any originality here; I suspect that to some the points I make might be interesting while to others they could feel passé–in the latter case, please help me make progress in the comments!

A circle is a plane figure contained by one line such that all the straight…

View original post 2,277 more words

Posted in What is Mathematics | Tagged | 1 Comment

To cheer you up in difficult times 20: Ben Green presents super-polynomial lower bounds for off-diagonal van der Waerden numbers W(3,k)

What will be the next polymath project? click here for our post about it. 

New lower bounds for van der Waerden numbers by Ben Green

Abstract: We show that there is a red-blue colouring of [N] with no blue 3-term arithmetic progression and no red arithmetic progression of length e^{C(\log N)^{3/4}(\log \log N)^{1/4}}. Consequently, the two-colour van der Waerden number w(3,k) is bounded below by k^{b(k)}, where b(k)=c(\frac{\log k}{\log \log k})^{1/3}. Previously it had been speculated, supported by data, that w(3,k)=O(k^2).

The left side of the picture shows the world record holders for W(3,k). On the left Ben Green (LB) and in the centre Tomasz Schoen (UB). The pictures on the right shows protective mittens for people who make bold mathematical conjectures (see Igor Pak’s post

The two-colour van der Waerden number w(m,k) is the smallest  N such that however [N] = {1, . . . , N} is coloured blue and red, there is either a blue m-term arithmetic progression or a red k-term arithmetic progression. The celebrated theorem of van der Waerden implies that w(m, k) is finite.

The van der Waerden number w(m,k) is analogous to the Ramsey number R(m,k). Finding the behaviors of R(m,k) is an important problem in Ramsey theory and much attention is given to R(k,k) and of R(3,k). Similarly, understanding the values of W(m,k), and especially of W(k,k) and W(3,k)  are also  central problems in Ramsey theory. A big difference between van der Waerden number and Ramsey numbers is that there are density theorems for the existence of k-terms arithmetic progressions. (Roth’s theorem for k=3 and Szemeredi’s theorem for general k.) There are several important methods to derive those density theorems (including Fourier methods, ergodic methods, and Szemeredi-type regularity) and these methods, as far as I know, do not apply for ordinary Ramsey numbers. (But correct me if I am wrong here, and if I am right and you have some insights as to why ergodic methods or Fourier methods do not apply to “ordinary” Ramsey, please share.)

Green’s paper  studies the values of w(3,k). The best known upper bound is of Tomasz Schoen, w(3, k)<e^{k^{1-c}} for some constant c > 0. The best known lower bound until the new paper, was by Li and Shu: w(3, k) \gg (k/ log k)^2. (This result, as the earlier bound by Robertson, used a probabilistic argument and relied on Lovasz’s local lemma.)

Several people conjectured, also based on empirical data, that w(3,k) = O(k^2) but now Green proved a super-polynomial lower bound! This is amazing! Congratulations, Ben!

It is largely conjectured that the Behrend-type bounds give the correct quantitative behaviour for Roth’s theorem (and Szemeredi theorem). In rough terms what we see from Green’s example is that this might be true also for van der Waerden numbers.

The proof is rather involved and long, so, naturally, there is  little I can say about it, which only slightly exceeds the little I actually know about it. The overview and other fragments of the paper I looked at are very illuminating. Here are a few things that caught my eyes.

1) A word about Tomasz Schoen’s upper bound and important paper: A subexponential upper bound for van der Waerden numbers W(3,k).  Among other things Schoen’s proof relies on a lemma developed by Schoen for improved Roth bound. This relies on a structure theory of Bateman and Katz.  The paper gives a nice description of the state of the art regarding the diagonal values w(k,k). (Schoen’s upper bound on w(3,k) follows also from the more recent bound for Roth’s theorem by Bloom and Sisask.)

2) Among the people that speculated that w(3,k) behaves like k^2 is Ben Green himself. This is recorded in reference [9] of the paper. However, Green’s first reaction to this possibility was that it must be false. But he realized that some ideas for showing that it is false are themselves false.

3) Reference [9] in the paper is: B. J. Green, 100 open problems, manuscript, available on request. If you are curious about the list, request it!

4) New lower bounds in Ramsey theory are nor frequent. Thirteen years ago I described Elkin’s improvement to Behrend’s bound and a few days ago I mentioned Linial and Shraibman’s new lower bounds for the corner problem.  Green’s study started by looking at complements of 3-AP free sets. An example by Green and Julia Wolf (that followed Elkin’s result) turned out to be important for reaching some parts of Green’s strategy.

5) In some sense, something about the k^2 prediction is not entirely lost. The construction gives a sort of a multi-scale behaviour where in the rth scale the example’s cardinality is k^r.  (So all the empirical data comes from the r=2 regime.) Ben Green boldly suggests that the true values of w(3,k) might exhibit such multi-scale behaviour. He conjectures that the true value of w(3, k) is quasi-polynomial, namely it lies somewhere in between the bound given by his construction and  something like k^{c\log k} (which is Behrend-bound behaviour on the nose) .

6) Until Ben’s list of 100 problems becomes available to you, you may find interest in Francis Su’s 100 questions about mathematics for discussion and reflection.

7) In connection with Linial and Shraibman’s new lower bounds for the corner problem, let me mention that the best upper bound is by I.D. Shkredov. The paper is:  On a two-dimensional analog of Szemeredi’s Theorem in Abelian groups, Izvestiya of Russian Academy of Sciences, 73 (2009), 455–505.

Posted in Combinatorics, Number theory | Tagged , | 2 Comments

To cheer you up in difficult times 19: Nati Linial and Adi Shraibman construct larger corner-free sets from better numbers-on-the-forehead protocols

What will be the next polymath project? click here for our previous post. 

Number on the forehead, communication complexity, and additive combinatorics

Larger Corner-Free Sets from Better NOF Exactly-N Protocols, by Nati Linial and Adi Shraibman

Abstract: A subset of the integer planar grid [N]×[N] is called corner-free if it contains no triple of the form (x,y),(x+δ,y),(x,y+δ). It is known that such a set has a vanishingly small density, but how large this density can be remains unknown. The best previous construction was based on Behrend’s large subset of [N] with no 3-term arithmetic progression. Here we provide the first substantial improvement to this lower bound in decades. Our approach to the problem is based on the theory of communication complexity.

In the 3-players exactly-N problem the players need to decide whether x+y+z=N for inputs x,y,z and fixed N. This is the first problem considered in the multiplayer Number On the Forehead (NOF) model. Despite the basic nature of this problem, no progress has been made on it throughout the years. Only recently have explicit protocols been found for the first time, yet no improvement in complexity has been achieved to date. The present paper offers the first improved protocol for the exactly-N problem. This is also the first significant example where algorithmic ideas in communication complexity bear fruit in additive combinatorics.

This is remarkable for various reasons. On the additive combinatorics side, improved constructions are rare. For example, we reported here in 2008 Elkin’s (small) improvements of Behrend’s bound. For the corner-free problem the paper of Nati and Adi goes beyond the Behrend’s (and Elkin’s) constructions. On the communication complexity side this is significant progress on a classical 1983 problem of Chandra, Furst and Lipton. The connection that goes from improved result on communication complexity to additive combinatorics is exciting — certainly a new frontier for Nati and Adi. On the blogging side, I cannot compete with the beautifully written introduction. Click here to read the paper.

Remark 1: The number of the forehead problem is  related to Levine’s hat problem that we discussed in this post.

Remark 2: Ryan Alweiss just told me about Ben Green’s new paper New lower bounds for van der Waerden numbers. It gives a construction of a red blue colouring of {1,2,…,N} with no 3 term blue or a k-term red arithmetic progression, where N is super-polynomial! Stay tune for a fuller report.

Posted in Combinatorics, Computer Science and Optimization | Tagged , | 3 Comments

Possible future Polymath projects (2009, 2021)

What will be our next polymath project?

A polymath project (Wikipedia) is a collaboration among mathematicians to solve important and difficult mathematical problems by coordinating many mathematicians to communicate with each other on finding the best route to the solution. The project began in January 2009 on Timothy Gowers’s blog when he posted a problem and asked his readers to post partial ideas and partial progress toward a solution. This experiment resulted in a new answer to a difficult problem, and since then the Polymath Project has grown to describe a particular process of using an online collaboration to solve any math problem.

After the success of Polymath1 and the launching of Polymath3 and Polymath4, Tim Gowers wrote a blog post “Possible future Polymath projects” for planning the next polymath project on his blog. The post mentioned 9 possible projects. (Three of them later turned  to polymath projects, and one turned into a project of a different nature.) Following the post and separate posts describing some of the proposed projects, a few polls were taken and a problem – the Erdős discrepancy problem, was selected for the next project polymath5. 

One of our next posts will have the same title and similar purpose as Tim’s 2009 post.  I will describe several possibilities for my next polymath project. (A quick rather vague and tentative preview can be found at the end of this post.) Today we go back to Tim’s 2009 post and the problems posed there.

Comments on the 2009 proposed projects, the new proposed projects, other proposed projects, and on the polymath endeavor, are most welcome. (At the end of the post I also mention a few “meta” questions.)

Let me also mention The PolyTCS Project aimed for proposing projects in theoretical computer science. There are so far three very interesting proposals there, and the first proposal is the Friedgut-Kalai Entropy/Influence conjecture. For various proposals, see also the polymath blog administered by Tim Gowers, Michael Nielsen, Terry Tao, and me, and this MO question.

The proposed projects in Gowers’s 2009 post and updates regarding these projects.

1. Littlewood’s conjecture and related problems.

The conjecture states that if \alpha and \beta are any two real numbers, and \epsilon>0, then there exists a positive integer n such that ||\alpha n||\,||\beta n||\leq\epsilon/n. Famously, Einsiedler, Katok and Lindenstrauss proved that the Hausdorff dimension of the set of counterexamples to the conjecture is zero. Gowers had ideas for an elementary approach, and his ideas  are described in this later post. This project was not launched and I am also not aware of progress related to the problem (but I am not an expert). 

2. A DHJ-related project.

DHJ stands for “density Hales Jewett” which was the topic of polymath1. The second proposed project was to build on the success of polymath1 and at a later post the following problem was proposed.

Conjecture:  For every \delta>0 and every positive integer k there exists n such that if A is any subset of [k]^{[n]^2} of density at least \delta, then A contains a combinatorial line such that the wildcard set is of the form X\times X for some subset X\subset[n].

As far as I know, this conjecture is still open.

Both questions “what kind of forbidden patters in [k]^n force exponentially small density” and “what kind of forbidden patters in [k]^n force vanishing density” are fascinating. Let me recommend again the Frankl-Rodl theorem and its proof as a role model.

3. Four Erdős-style combinatorial problems.

3a. Erdős’s discrepancy problem

This was the problem that was eventually chosen for polymath5. This was a very nice story. The problem was presented in this blog post and selected as polymath5 after some polls among readers. The polymath project was the longest in polymath history. There were six preliminary discussion posts with more than 600 comments followed by 21 official posts EDP1-EDP21. There was some short revival of the project (EDP22-EDP27) in 2012 where I contributed three posts. Famously, in 2015 Terry Tao solved the problem. The paper appeared in the journal Discrete Analysis. Tao’s solution relies on some insights from the polymath project including a crucial reduction that Terry himself contributed. It also crucially relied on a (then) new theory by Kaisa Matomaki and Maksym Radziwill. The solution was triggered  by a blog comment by Uwe Stroinski who pointed to a possible connection to EDP, and a subsequent one by Kodlu who seconded Uwe’s suggestion. This is reported in EDP28, and here on my blog we celebrated the solution in this post.  

3b. The Erdős-Hajnal conjecture.

Let k be a positive integer and let H be a graph. Erdös and Hajnal conjectured that there is a constant C=C(H) such that if G is any graph with at least k^C vertices that does not contain any induced copy of H, then either G or G^c contain a clique of size k.

Tim asserted that the simplest open case is where H is a pentagon. This special case was recently settled by Maria Chudnovsky, Alex Scott, Paul Seymour and Sophie Spirkl. They rely on recent results by Janos Pach and Istvan Tomon. See this videotaped lecture by Paul Seymour at IBS Discrete Mathematics Group, South Korea.

3c. Frankl’s union-closed conjecture.

Continue reading

Posted in Combinatorics, Mathematics over the Internet, Open discussion | Tagged , , | 23 Comments

Peter Cameron: Doing research

To cheer you up in difficult times, here is a wonderful post by Peter Cameron about doing research. And see also this entertaining post by Peter on mathematics and religion.

Peter Cameron's Blog

Probably every research mathematician has been asked the question, “How do you do mathematical research?” Some lay people think we simply figure out ways of doing bigger and bigger long multiplications. Many more people think that all the mathematics must have been discovered by now, so what are we doing?

These misunderstandings are about what we do research on rather than how we do it, the question I want to focus on here.

In 1945, Jacques Hadamard published a remarkable book, The Psychology of Invention in the Mathematical Field. He was a great mathematician himself, one of whose achievements was the proof of the Prime Number Theorem fifty years earlier. He examined his own mental processes, searched the writings of his predecessors, and sent questionnaires to many leading mathematicians and scientists of his time, including Albert Einstein.

Hadamard’s conclusion was that the process of mathematical discovery can be broken…

View original post 1,204 more words

Posted in What is Mathematics | Tagged | Leave a comment

To cheer you up in difficult times 18: Beautiful drawings by Neta Kalai for my book: “Gina Says”

In 2009 I wrote a book “Gina Says” that appeared here on the blog, about the adventures of “Gina” in the blogsphere. In 2017 the book (edited and shortened a little) appeared in “world scientific.” The most important additions were beautiful drawings contributed by my daughter Neta. Here are three of them.  More to come.

“My own heart goes to chemistry”  (Chapter 5)

“Octopus music” (Chapter 25)

anti anti anti missile missile missile missle  (Chapter 17, see also the post Chomskian Linguistics)

 

Posted in Art, Gina Says | Tagged | Leave a comment