What is mathematics (or at least, how it feels)

3905485723

(I suppose that this amazing picture can serve as a metaphor also for life, for science, for human rights, for happiness and for a variety of other things.) Picture: AFP Suez Canal: the Ever Green ship blockage.

Posted in What is Mathematics | Tagged | Leave a comment

Alef’s Corner

Alefgil3

After Picasso 1955.

Happy Passover to all our readers.

More from Alef’s corner

Posted in Art, personal | Tagged | 3 Comments

To cheer you up in difficult times 22: some mathematical news! (Part 1)

To cheer you up, in these difficult times, here are (in two parts) some mathematical news that I heard in personal communications or on social media. (Maybe I will write later, in more details,  about few of them that are closer to combinatorics.)

Mathematics and the real world

Zvi Artstein  The pendulum under vibrations revisited

Zvi (Zvika) was one of the first people that I met in 1971 at the university as a high school student and he gave me a lot of good advice and help. Here he shed light on an old mystery!

Abstract: A simple intuitive physical explanation is offered, of the stability of the inverted pendulum under fast violent vibrations. The direct description allows to analyze, both intuitively and rigorously, the effect of vibrations in similar, and in more general, situations. The rigorous derivations in the paper follow a singular perturbations model of mixed slow and fast dynamics. The approach allows applications beyond the classical inverted pendulum model.

I first heard about the stability of the inverted pendulum under fast violent vibrations from Sylvia Serfaty in connection with my study of “forehead-football.” See this post. Let me mention with pride that Endre Szemeredi, who is a fan of football in general (and a capable player), is also a fan of my forehead-football idea.

Imre Bárány, William Steiger, and Sivan Toledo the cocked hat

Abstract (arXive): We revisit the cocked hat — an old problem from navigation — and examine under what conditions its old solution is valid.

This is a great story, read it in The Journal of Navigation, or on the arXive.

Rigidity

Katie Clinch, Bill Jackson, Shin-ichi Tanigawa: Maximal Matroid Problem on Graphs

In mid January, we had a great lecture by Shin-ichi Tanigawa (University of Tokyo). I certainly plan to blog about it. Here is the abstract.
 
The problem of characterizing the 3-dimensional generic rigidity of graphs is one of the major open problems in graph rigidity theory. Walter Whiteley conjectured that the 3-dimensional generic matroid coincides with a matroid studied in the context of bivariate splines.  In this talk I will show a solution to the characterization problem for the latter matroid. 
 
I will explain the idea of our characterization from the view point of constructing maximal matroids on complete graphs. Specifically, for a graph H, a matroid on the edge set of a complete graph is called an H-matroid if every edge set of each subgraph isomorphic to H is a circuit. A main theme of my talk will be about identifying and constructing a maximal H-matroid with respect to the weak order. This talk is based on a joint work with Bill Jackson and Katie Clinch.

 

Here is the video

The papers on the arxive
 

Polytopes

Ardila and Escobar:  The harmonic polytope

Abstract: We study the harmonic polytope, which arose in Ardila, Denham, and Huh’s work on the Lagrangian geometry of matroids. We show that it is a (2n2)-dimensional polytope with $latex (n!)^2 (1+1/2++1/n)$ vertices and $latex 3^n3$ facets. We give a formula for its volume: it is a weighted sum of the degrees of the projective varieties of all the toric ideals of connected bipartite graphs with n edges; or equivalently, a weighted sum of the lattice point counts of all the corresponding trimmed generalized permutahedra.

These polytopes look truly great!

Federico Ardila, Laura Escobar, The harmonic polytope

Percolation

 I am thankful to Itai Benjamini who told me about these results.

At last: Rotation invariance theorem for planar percolation for the square grid.

Rotational invariance in critical planar lattice models

This is very big news: twenty years after Smirnov’s result for the triangular grid, finally rotational invariance is proved for critical percolation on the square grid.

Authors: Hugo Duminil-Copin, Karol Kajetan Kozlowski, Dmitry Krachun, Ioan Manolescu, Mendes Oulamara

Abstract:  In this paper, we prove that the large scale properties of a number of two-dimensional lattice models are rotationally invariant. More precisely, we prove that the random-cluster model on the square lattice with cluster-weight 1q4 exhibits rotational invariance at large scales. This covers the case of Bernoulli percolation on the square lattice as an important example. We deduce from this result that the correlations of the Potts models with q{2,3,4} colors and of the six-vertex height function with Δ[1,1/2] are rotationally invariant at large scales.

Noise sensitivity for planar percolation without Fourier

Endre Szemeredi sometimes say that we should try to avoid the use of his regularity lemma “at all costs”. Similarly, we should try to avoid Fourier tools if we can. Vincent and Hugo could!

Noise sensitivity of percolation via differential inequalities, Vincent Tassion and Hugo Vanneuville

Abstract: Consider critical Bernoulli percolation in the plane. We give a new proof of the sharp noise sensitivity theorem shown by Garban, Pete and Schramm. Contrary to the previous approaches, we do not use any spectral tool. We rather study differential inequalities satisfied by a dynamical four-arm event, in the spirit of Kesten’s proof of scaling relations. We also obtain new results in dynamical percolation. In particular, we prove that the Hausdorff dimension of the set of times with both primal and dual percolation equals 2/3 a.s.

Plaquette Percolation on the Torus by  Paul Duncan, Matthew Kahle, and Benjamin Schweinhart

Harry Kesten famously proved that the critical probability for planar percolation is 1/2. Planar duality is crucial.  Many people expected or speculated that a similar statement for 2d-dimensions holds if we replace “connectivity” by some statement about d dimensional homology. This is what the new paper does.

(Next part: Topology, graph theory, algebra, Boolean functions, and Mathematics over the media.)

 

Posted in Combinatorics, Convex polytopes, Convexity, Geometry | Leave a comment

Cheerful News in Difficult Times: The Abel Prize is Awarded to László Lovász and Avi Wigderson

The Abel Prize was awarded earlier today to László Lovász and Avi Wigderson

“for their foundational contributions to theoretical computer science and discrete mathematics, and their leading role in shaping them into central fields of modern mathematics.”

Congratulations to Laci and Avi, to their families, and to the communities of theoretical computer science and combinatorics. Let me quote one more sentence from the citation:

“They have both made fundamental contributions to understanding randomness in computation and in exploring the boundaries of efficient computation.”

For the full citation and more material see the Abel Prize page.

Avi and Laci, Oslo 2012. (source, Oberwolfach pictures)

Both Avi and Laci are frequently mentioned over my blog. The post Four derandomization problems is related to both. Here are a few posts on Laci: Posets and the perfect graph theorem; Building bridges II; ICM2010; Laci’s theorem about two families of sets (and subspaces); Building bridges I. On Avi: Fractional Sylvester Gallai; Avifest 1; Layish; Must-read book by Avi Wigderson ;Avi Wigderson’s: “Integrating computational modeling, algorithms, and complexity into theories of nature, marks a new scientific revolution!” (An invitation for a discussion.) There were also two posts on conjectures by Laci that were recently solved (almost completely): The EFL conjecture and the KLS conjecture.

I will not write today about computer science or mathematics but rather I will show you some pictures and give some links. (I will add most of the pictures later today.)

Here is the link to Building bridges II Laci’s 70th birthday conference. There were lectures  by Noga Alon on Lovász, vectors, graphs and codes, by Lex Schrijver  On ϑ and Θ by Jennifer Chayes on Graphons and Graphexes as Limits of Sparse Graphs, by Santosh Vempala With or Without KLS by Avi Wigderson Mathematics and Computation (through the lens of one problem and one algorithm) by Eva Tardos on Small-loss bounds for online learning with partial information and many other inspiring lectures. (I linked here lectures directly related to Laci’s work.)

And here is a link to Avi’s 60th birthday conference: Avi Wigderson Is 60: A Celebration of Mathematics and Computer Science with lectures by Noga Alon on Avi, Graphs, and Communication, by Dorit Aharonov on Quantum Physics and the Computational Lens by Shafi Goldwasser on New Pseudo-deterministic Algorithms, by Nati Linial on Transitions and Phase Transitions by Alex Lubotzky on High Dimensional Expanders, by Laci Lovasz on What is generic? and also by Eyal Wigderson on Brains are Better Computers than Computers and by Einat Wigderson and me on Happy Days, and many other inspiring talks.

(Update 1) Links: NYT (Kenneth Chang), Quanta Magazine (Kevin Hartnett), (and many other places); blogs:  In theory (Finally, a joy), Computational Complexity (Ohh Boy), Shtetl Optimized, Igor Pak. Luca’s post describes very nicely how early results of Laci and Avi interlace. (Update 2) A very nice post on GLL featuring Dorit Aharonov as the post’s “saint patron”, and connections to people and papers of quantum computation.

Trivia questions:

Who are these people? (1,2,3,4,5)

NA

Continue reading

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

Amazing: Feng Pan and Pan Zhang Announced a Way to “Spoof” (Classically Simulate) the Google’s Quantum Supremacy Circuit!

Feng Pan and Pan Zhang uploaded a new paper on the arXive  “Simulating the Sycamore supremacy circuits.” with an amazing announcement.

Abstract: We propose a general tensor network method for simulating quantum circuits. The method is massively more efficient in computing a large number of correlated bitstring amplitudes and probabilities than existing methods. As an application, we study the sampling problem of Google’s Sycamore circuits, which are believed to be beyond the reach of classical supercomputers and have been used to demonstrate quantum supremacy. Using our method, employing a small computational cluster containing 60 graphical processing units (GPUs), we have generated one million correlated bitstrings with some entries fixed, from the Sycamore circuit with 53 qubits and 20 cycles, with linear cross-entropy benchmark (XEB) fidelity equals 0.739, which is much higher than those in Google’s quantum supremacy experiments.

Congratulations to Feng Pan and Pan Zhang for this remarkable breakthrough!

Of course, we can expect that in the weeks and months to come, the community will learn, carefully check, and digest this surprising result and will ponder about its meaning and interpretation. Stay tuned!

Here is a technical matter I am puzzled about: the paper claims the ability to compute precisely the amplitudes for a large number of bitstrings. (Apparently computing the amplitudes is even more difficult computational task than sampling.) But then, it is not clear to me where the upper bound of 0.739 comes from? If you have the precise amplitudes it seems that you can sample with close to perfect fidelity. (And, if you wish, you can get a F_XEB score larger than 1.)

Update: This is explained just before the discussion part of the paper. The crucial thing is that the probabilities for the 2^21 strings are distributed close to Porter-Thomas (exponentials). If you take samples for them indeed you can get samples with F_XEB between -1 and 15. Picking the highest 10^6  strings from 2^21 get you 0.739 (so this value has no special meaning.) Probably by using Metropolis sampling you can get (smaller, unless you enlarge 2^21 to 2^25, say) samples with F_XEB close to 1 and size-biased distribution (the distribution of probabilities of sampled strings) that fits the theoretical size biased distribution.  And you can also use metropolis sampling to get a sample of size 10^6 with the correct distribution of probabilities for somewhat smaller fidelity. 

The paper mentions several earlier papers in this direction, including an earlier result by Johnnie Gray and Stefanos Kourtis in the paper Hyper-optimized tensor network contraction and another earlier result in the paper Classical Simulation of Quantum Supremacy Circuits by a group of researchers Cupjin Huang, Fang Zhang, Michael Newman, Junjie Cai, Xun Gao, Zhengxiong Tian, Junyin Wu, Haihong Xu, Huanjun Yu, Bo Yuan, Mario Szegedy, Yaoyun Shi, and Jianxin Chen, from Alibaba co.  Congratulations to them as well.

I am thankful to colleagues who told me about this paper.

Some links:

Scientists Say They Used Classical Approach to outperform Google’s Sycamore QC (“The Quantum” Written by Matt Swayne with interesting quotes from the paper. )

Another axe swung at the Sycamore (Shtetl-Optimized; with interesting preliminary thoughts by Scott;  )

Posted in Computer Science and Optimization, Physics, Quantum | Tagged , , | Leave a comment

To cheer you up in difficult times 21: Giles Gardam lecture and new result on Kaplansky’s conjectures

There is a very famous conjecture of Irving Kaplansky that asserts that the group ring of a torsion free group does not have zero-divisors. Given a group G and a ring R, the group ring R[G] consists of formal (finite) linear combinations of group elements with coefficients in the ring. You can easily define additions in R[G], and can extend the group multiplication to R[G], which makes the group ring a ring. (And if R is a field, R[G] is an algebra, called group-algebra.)

Kaplansky’s zero divisor conjecture asserts that if G is torsion-free and K is a field then K[G] has no zero-divisors.

Irving Kaplansky

This conjecture was made in the 1950s or even 1940s. It is known to hold for many classes of groups. If G has torsion, namely an element g of order n, then (1-g)(1+g+g^2+\cdots +g^{n-1})=0.

Kaplansky made also in the 50s two other conjectures.

Kaplansky’s unit conjecture asserts that if G is torsion-free and K is a field the only units in the face ring of K[G] are of the form kg where k in a non-zero element in the field and g is an element of the group,

Kaplansky’s idempotents conjecture asserts that if G is torsion-free and K is a field then the only idempotents in K[G] are 0 and 1.

If G has torsion, namely an element g of order n, then $(1-g)(1+g+g^2+\cdots +g^{n-1})=0$. It is not very hard to see that the unit conjecture implies the zero-divisor conjecture which in turn implies the idempotent conjecture.

A few days ago, Giles Gardam gave a great, very pleasant, lecture about Kaplansky’s conjectures.

After introducing the conjectures themselves, Giles explained that these conjectures are related to several other conjectures like the Baum-Connes conjecture or Farrell-Jones and a conjecture of Atiyah. So this implies, for example that the zero divisors conjecture holds for residually torsion free solvable group. Now, as an aside let me say that it is good to know what does it mean for a property X to say that a groups G is “residually X”. I tried to explain it in this post. But I myself forgot, so together with you, devoted readers, I will go to the old post to be reminded. Let’s get reminded also of the easier concept of “virtually X”.

The assertion of Kaplansky’s unit conjecture holds for torsion-free unique-product groups. The unique product property says the following if A and B are finite subsets of the group there is an element c that can be written in a unique way as c=ab where a belongs to A and b belongs to B.

This concept was defined in 1964 by Rudin and Schneider and for two decades it was not even known that there are groups without the unique-product property. The first example of a group without this property was discovered by Rips and Segev.

Let me make a small diversion here. From time to time I talk about results by people I personally know and usually I don’t mention that in the posts. For example, in the post about Yuansi Chen’s work on Bourgain’s slicing conjecture and the KLS conjecture I personally knew about 70% of the heroes in that story (update: 19:25). In fact, both Bo’az Klartag and me are living in the very same apartment building in Tel Aviv.  (Officially, I am in number 9 and Bo’az is in number 7 but topologically it is the same building.)

But here I must mention that Yoav Segev is my class mate in undergraduate years and is now a Professor at Ben Gurion University in Beer-Shava. He is responsible to one of the final steps in the classification program, to knocking down several other conjectures in algebra, and also to works on fixed-point free actions of non solvable groups on simplicial complexes. This last topic is close to my own interests and from time to time we chat about it. And of course, Ilya Rips is extraordinary mathematician and we are emeritus colleagues at HUJI – see this post about Ripsfest.

So let me go back to Giles’s lecture. Giles discussed two classes of examples of groups without the unique product property. And at minute 49 of the (50-minute) lecture Giles said: “I am nearly at the end of the talk and its time for me to tell you what’s new, um, what’s my contribution to this story, um, so I am really happy to be able to announce today for the first time, that, in fact, the unit conjecture is false.”

Theorem (Giles Gardam, 2021): Let P be the torsion-free virtually abelian group

<a,b | (a^2)^b=a^{-2}, (b^2)^a=b^{-2}>

And lt K be the field with two elements. Then there is a nontrivial unit \alpha in K[G], so that both \alpha and \alpha^{-1} have support of size 21.

(This group does satisfy the zero-divisor conjecture.)

Here is the paper: Giles Gardam, A counterexample to the unit conjecture for group rings. Congratulations, Giles!

Posted in Algebra | Tagged , | 7 Comments

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