Consider 
Here is an illustrative representation of “nice norms,” combining societal harmony with mathematical hints (ChatGPT).
It is time for the horrible war to end
Polymath3 dealt with the following problem:
Is there a polynomial
such that the graph of every
-polytope
with
facets has diameter at most
If anybody is interested to take part in a renewed polymath project, please comment over here or drop me an email.
Update (Jan. 1): I Just saw the impressive performance of “FrontierMath” in solving pretty difficult mathematics problems. (h/t Assaf Katz).
Peter Sarnak is in town and when we met he had a question for me:
Will AI take over mathematics?
Peter told me what he thinks, and was surprised and a bit disappointed that I don’t have an opinion. I promised to think about it and to try to have some answer in a week (Thursday, January 2) 🙂 .
Meanwhile, I asked ChatGPT and this is what it answered. Here is one quote:
(ChatGPT) Many breakthroughs in mathematics involve conceptual leaps that are hard to formalize in a way AI can process.
I disagree; I don’t see reasons to think that conceptual leaps will be harder for AI compared to other aspects of math. (I disagree with several other assertions in ChatGPT’s answer.)
“Some quantum mysteries” is the name of an ambitious post that I am planning for some time and I hope to conclude in a few weeks. I will mention several quantum physics mysteries many of which are related to quantum information theory and the first one is about the elusive “Majorana zero modes”. A spinoff of this post which may be ready even earlier is a summary of few skeptical views about quantum computing of Robert Alicki, Michel Dyakonov, Leonid Levin, Oded Goldreich, and others.
Next week in Weizmann Institute there will be a Winter school in expansion in groups combinatorics and complexity. (The link includes abstracts for the lectures.)
Dates: January 5-8, 2025
Venue: The beautiful Lopatie conference center, Weizmann Institute of Science, Israel.
Registration: Registration is free but mandatory. Click [here] for a link to the registration page.
Organizers: Irit Dinur and Thomas Vidick
This workshop will have several mini-courses that will go in depth into a topic, together with several more standard one-hour lectures. Here is the program. (In square brackets related posts.)
Good news: the slice conjecture is now completely settled with combined effort of two separate papers.
Abstract: This note is to study Bourgain’s slicing problem following the routes investigated in the last decade. We show that the slicing constant 
Abstract: We provide the final step in the resolution of Bourgain’s slicing problem in the affirmative. Thus we establish the following theorem: for any convex body 
where 
For earlier posts on the slice conjecture see: To Cheer You Up in Difficult Times 15: Yuansi Chen Achieved a Major Breakthrough on Bourgain’s Slicing Problem and the Kannan, Lovász and Simonovits Conjecture (2020); Bo’az Klartag and Joseph Lehec: The Slice Conjecture Up to Polylogarithmic Factor! (2022).
An artistic depiction of the concept “slice,” capturing a surreal and vibrant visualization. (ChatGPT)
Peter Sarnak will give the Gordon memorial lectures at the Hebrew University of Jerusalem.
At the end of December 2024, Peter Sarnak will deliver the Mark Gordon memorial lecture series on Spectra of locally symmetric geometries at the Hebrew University of Jerusalem. This event will be part of a workshop focusing on the same theme. The lecture series will feature additional talks by esteemed mathematicians, including Omri Solan, Nattalie Tamam, Uri Shapira, Alex Gamburd, Elon Lindenstrauss, Zeev Rudnick, Borys Kadets, Alex Smith, Barak Weiss, Menny Aka, Amos Nevo, Lior Bary-Soroker, Snir Ben Ovadia, and Bryce Orloski.
You are warmly invited to attend!
If you cannot make it to Jerusalem but are curious about the subject, consider watching Peter Sarnak’s Chern’s lecture at Berkeley on a related topic. I looked at the slides of the first lecture, and while the mathematics was new to me, Peter’s familiar handwriting raised fond memories of previous lectures.
Oh, and if you are looking for my previous post, here is the link : The Case Against Google’s Claims of “Quantum Supremacy”: A Very Short Introduction.
A few months ago I decided to celebrate Peter’s 70 birthday conference with a new Möbius randomness conjecture. At the same time, I also decided to celebrate Richard Stanley’s 80 birthday conference with a new conjecture about Stanley-Reisner rings. Progress on both projects was slower than anticipated, and the conjectures were not ready in time for the conferences.
We will use algebraic circuits. Here is a link to Ramprasad Saptharishi’s A survey of lower bounds in arithmetic circuit complexity. I am thankful to several colleagues and especially to Ben Lee Volk for helpful conversations on arithmetic circuits.
Here is a tentative version of the conjecture for Peter:
The arithmetic Bounded-Depth Prime Number Conjecture (tentative version): The correlation between the Möbius function and any complex function 
Let me state the “pre-conjecture” that was my starting point:
Complexity theoretic Möbius Randomness pre-conjecture:
Formulate a Möbius randomness conjecture based on computational complexity notions that:
a) It should be potentially feasible from the perspective of computational complexity theory.
b) It should include the Davenport theorem (regarding polynomials), the Green-Tao theorem (on bracket polynomials; see this post) and other known concrete Möbius Randomness theorems.
Of course, once we have a vague idea like my pre-conjecture maybe AI can lead us to useful mathematical conjectures? I asked (free-version) ChatGPT the following.
Question: Please, formulate seven Möbius randomness conjectures based on computational complexity notions that will be potentially feasible from the point of view of computational complexity.
I found the answer striking. (You can try it yourself or look here.)
All seven ChatGPT conjectures are interesting. It almost looks that they are taken from a paper on the subject.
For background on Möbius randomness, see this 2010 videotaped lecture by Peter Sarnak, A further lecture by Peter Möbius randomness and dynamics six years later; and Tamar Ziegler – Sign Patterns of the Möbius Function.
From the computational complexity side, this line of research has roots in the late 90s in works by Bernasconi, Damm, Shparlinski, Saks, and others. I will add some links at the end of the post. In the meantime, let me offer you Igor Shparlinski’s paper: Problems on Exponential and Character Sums (it looks great!).
Prime Number Theorem:In February 2011 I proposed over here the following conjecture:
The
This conjecture was inspired by a lecture of Peter Sarnak in our math colloquium and by some comments made in real time by me and by other participants of the colloquium (including Dorit Aharonov and Michael Ben-Or). A few days later, in March 2011, I proposed over MathOverflow three related problems that relate Möbius randomness with Fourier-Walsh coefficients of the Möbius function.
My MO post included three questions. In these questions, I considered 
Fourier-Walsh Coefficients (Full):
Show that all Fourier-Walsh coefficients 
Fourier-Walsh Coefficients (Restricted):
Prove the above for coefficients 
Fourier-Walsh Coefficients under GRH (Still Open):
Assuming the Generalized Riemann Hypothesis (GRH), prove that 
The second MO question and with it the
The first MO question was solved in the positive by Jean Bourgain in the paper: Möbius-Walsh correlation bounds and an estimate of Mauduit and Rivat. Bourgain proved a uniform bound of the form 
Theorem (Bourgain): Möbius Randomness for monotone Boolean functions: The correlation between the Möbius function and any function
Let me state together four plausible conjectures; except for the third one they could be realistic:
1) Möbius Randomness conjecture for ACC(p): The correlation between the Möbius function 
2) Möbius Randomness conjecture for low degree polynomials: The correlation between 
3) Möbius Randomness conjecture for TC0: The correlation between the Möbius function and any function
Returning to the arithmetic Bounded-Depth Prime Number Conjecture, let me state it again with a couple comments.
4) Möbius Randomness conjecture for arithmetic AC0 (tentative version): The correlation between the Möbius function and any complex function
Bernasconi, Damm, and Shparlinski (1999): “On the Average Sensitivity of Testing Square-Free Numbers“
Bernasconi, Damm, and Shparlinski: “Detecting Square-Free Numbers is Hard for 
Allender, Saks, and Shparlinski: “A Lower Bound for Primality“
Allender, Bernasconi, Damm, von zur Gathen, Saks, and Shparlinski: “Complexity of Some Arithmetic Problems for Binary Polynomials“
An important technique for lower bounds for arithmetic circuits is based on looking at all partial derivatives of a function. This method shows that bounded depth AC0 functions (or, say depth-3 AC0 functions) are included in a class of functions defined in terms of the space of all its partial derivatives. Extending out conjecture to such classes of functions could actually be more approachable. Here is a paper from 1995 by Noam Nisan and Avi Wigderson where this method is developed and see especially Theorem 0 that has a half-page proof. Ben Lee Wolk mentioned another breakthrough paper about AC0 circuits Low-Depth Algebraic Circuit Lower Bounds over Any Field by Michael A. Forbes.
A lot have happened in the area of Mobius Randomness in the last decade and it is quite possible that my treatment here is little old-fashioned. Asaf’s comment discusses various interesting concrete Mobius randomness theorems (and a related weaker notion of Mobius disjointedness).
The 2019 paper “Quantum supremacy using a programmable superconducting processor” asserted that Google’s Sycamore quantum computer, with 53 qubits and a depth of 20, performed a specific computation in about 200 seconds. According to Google’s estimate, a state-of-the-art classical supercomputer would require approximately 10,000 years to complete the same computation.
The Google experiment had two major components:
There are valid reasons to question both of these claims in the context of Google’s 2019 experiment. In my view, these claims may reflect serious methodological mistakes rather than an objective scientific reality. I do not recommend treating Google’s past or future claims as a solid foundation for policy-making decisions.
Below is a brief review of the case against Google’s 2019 claims of quantum supremacy:
A) The “Supremacy” Assertions: Flawed Estimation of Classical Running Time
A.1) The claims regarding classical running times were off by 10 orders of magnitude.
A.2) Moreover, the Google team was aware that better classical algorithms existed. They had developed more sophisticated classical algorithms for one class of circuits and subsequently changed the type of circuits used for the “supremacy demonstration” just weeks before the final experiment.
A.3) The 2019 Google paper states, “Quantum processors have thus reached the regime of quantum supremacy. We expect that their computational power will continue to grow at a double-exponential rate.” It is surprising to encounter such an extraordinary claim in a scientific paper.
The google paper relies on a very simple a priori prediction of the fidelity based on the error-rates of individual components. (Formula (77).)
B.1) The agreement between the a priori prediction and the actual estimated fidelity is statistically implausible (“too good to be true”): It is unlikely that the fidelities of samples from hundreds of circuits would agree within 10-20% with a simple formula based on the multiplication of the fidelities of individual components. In my opinion, this suggests a methodologically flawed optimization process, such as the one described in item C.
B.2) The Google team provided a statistical explanation for this agreement based on three premises. The first premise is that the fidelities for the individual components are exact up to ±20%. The second premise is that this ±20% instability is unbiased. The third premise is that all these fidelities for individual components are statistically independent. These premises are unreasonable and they contradict various other experimental findings.
B.3) As of now, the error rates for individual components have not been released by the Google team. (Most recently, in May 2023, they promised “to push” for this data.) Analysis of the partial data provided for readout errors reinforces these concerns.
According to the Google paper, calibration was performed prior to running the random circuit experiments and was based on the behavior of 1- and 2-qubit circuits. This process involved modifying the definitions of 1-gates and 2-gates to align with how the quantum computer operates.
C.1) Statistical evidence suggests that the calibration process involved a methodologically flawed global optimization process. (This concern applies even to Google’s assertions about the fidelity of the smallest 12-qubit circuits.)
C.2) Non-statistical evidence also supports this claim. For example, contrary to the description provided by the Google team, it was revealed that they supplied an outdated calibration version (for the experimental circuits) to the Jülich Research Center scientists involved in the experiment. This calibration was later further modified after the experiment was conducted. (This discrepancy is also reflected in a video released by Google particularly between 2:13-3:07.)
C.3) The Google team has not disclosed their calibration programs, citing them as a commercial secret. For technical reasons, they were also unable to share the inputs for the calibration program, although they promised to do so in future experiments—a promise that has not yet been fulfilled.
A slide from my 2019 lecture “The Google quantum supremacy demo” (post), highlights that the error rates for two-qubit gates 
As far as we know, there is a significant gap (in favor of Google) between what IBM quantum computers—which are in some ways more advanced than Google’s quantum computers—can achieve for random circuit sampling and what Google claims, even for circuits with 7–12 qubits. While one might argue that Google’s devices or team are simply better, in my view, this gap more likely reflects methodological issues in Google’s experiments.
In our discussions with the Google team, they endorsed several of our suggestions for future experiments aimed at improving control over the quality of their experiments. However, in practice, later experiments did not implement any of these suggestions. Moreover, the structure of these later experiments makes them even harder to verify compared to the 2019 experiment. Additionally, unlike the 2019 experiment, the data for a subsequent random circuit sampling experiment does not include the amplitudes computed for the experimental circuits, further complicating efforts to scrutinize the results.
Google Quantum AI’s claims (including published ones) should be approached with caution, particularly those of an extraordinary nature. These claims may stem from significant methodological errors and, as such, may reflect the researchers’ expectations more than objective scientific reality. I do not recommend treating Google’s past or future claims as a solid basis for policy-making decisions.
G.1) Google’s supremacy claims (from the 2019 paper) have been refuted in a series of papers by several groups. This began with work by IBM researchers Pednault et al. shortly after Google’s original paper was published and continued with studies by Pan and Zhang; Pan, Chen, and Zhang; Kalachev, Panteleev, and Yung; Gao et al.; Liu et al.; and several other groups. For further details, see this post and the associated comment section, as well as this post.
G.2) Google now acknowledges that using the tensor network contraction method, their 2019 53-qubit result can be computed classically in less than 200 seconds. However, in their more recent 2023/24 paper, “Phase Transitions…” (see Table 1), they claim that with 67 to 70 qubits, classical supercomputers would require many years to generate 1 million such bitstrings, even with tensor network contraction.
G.3) Items B) and C) highlights methodological issues with Google’s fidelity assertions, even for 12-qubit circuits. These concerns persist independently of the broader question of quantum supremacy for larger circuits, where the fidelity assertions are taken at face value.
G.4) For a more comprehensive view of our study of Google’s fidelity claims, refer to the following papers:
These papers describe an ongoing project with Yosi Rinott and Tomer Shoham, supported by Ohad Lev and Carsten Voelkmann. Together with Carsten, we plan to expand our study and apply our tools to other experiments. Additionally, see my earlier paper:
G.5) There is also supporting evidence for Google’s 2019 claims, such as a 2020 replication by a group from the University of Science and Technology of China (USTC) and later verifications of some of Google’s fidelity estimations.
G.6) There are some additional concerns regarding the Google experiment. In particular, there are problematic discrepancies between the experimental data, the Google noise model, and simulations.
G.7) In my opinion, the main current challenge for experimental quantum computing is to improve the quality of two-qubit gates and other components, as well as to carefully study the quality of quantum circuits in the 5–20 qubit regime. Experiments on quantum error correction for larger circuits are also important.
I usually don’t mind “hype” as a reflection of scientists’ enthusiasm for their work and the public’s excitement about scientific endeavors. However, in the case of Google, some caution is warranted, as the premature claims in 2019 may have had significant consequences. For example, following the 2019 “supremacy” announcement, the value of Bitcoin dropped (around October 24, 2019, after a period of stability) from roughly $9,500 to roughly $8,500 in just a few days, representing a loss for investors of more than ten billion dollars. (The value today is around $100,000.) Additionally, Google’s assertions may have imposed unrealistic challenges on other quantum computing efforts and encouraged a culture of undesirable scientific methodologies.
Sergio Boixo, Hartmut Neven, and John Preskill in a video “Quantum next leap: Ten septillions years beyond-classic”
I) Update (Dec. 10): The Wind in the Willow
Yesterday, Google Quantum AI announced that their “Willow” quantum computer “performed a standard benchmark computation in under five minutes that would take one of today’s fastest supercomputers 10 septillion (that is, 10^25) years.” As far as I know there is no paper with the details. Google AI team announced also the appearance in Nature of their recent paper on distance-5 and distance-7 surface codes. It is asserted that the distance-7 codes exhibit an improvement of a factor of 2.4 compared to the physical qubits. The ratio of improvement Λ from distance-5 to distance-7 is 2.14. (We mentioned it in an August post following a comment by phan ting.)
We did not study yet these particular claims by Google Quantum AI, but my general conclusion apply to them “Google Quantum AI’s claims (including published ones) should be approached with caution, particularly those of an extraordinary nature. These claims may stem from significant methodological errors and, as such, may reflect the researchers’ expectations more than objective scientific reality.” (Our specific contention points are relevant to Google’s newer supremacy experiments but not directly to the quantum error-correction experiment.)
There is a nice very positive blog post over SO about the new developments where Scott wrote: “besides the new and more inarguable Google result, IBM, Quantinuum, QuEra, and USTC have now all also reported Random Circuit Sampling experiments with good results.” For me, the gap between Google and IBM for RCS is a serious additional reason not to take the Google assertions seriously (item D) and and if I am wrong I will gladly stand corrected. Update: Scott’s claim about RCS experiments with good results by IBM and QuEra appears to be incorrect. Scott clarified that what he meant to say was that since the Google 2019 experiment there were several other experiments that challenge my position. (This is correct.) More updates on Google’s septillion advantage claims will appear in a separate post.
Optimality of Gerver’s Sofa, by Jineon Baek (h/t for Dan Romik who told me about it)
Abstract: We resolve the moving sofa problem by showing that Gerver’s construction with 18 curve sections attains the maximum area 2.2195⋯.
Gerver’a 1992 sofa (source:Dan Romik)
Original post
A story about the mathematical experience as told by Anton Kapustin (over Facebook):
While working out at the gym I was thinking about Kolmogorov-Arnold-Moser theory and whether it has a quantum analog. Suddenly I heard a guy say, “This was Arnold’s favorite exercise!” It took me several seconds to realize he meant a different Arnold.
Arnold (left) and a different Arnold (right). The different Arnold from Anton’s story may well be different from both.
In this post we will mention eight recent papers: 1) Reconstructing a Shellable Sphere from its Facet-Ridge Graph, by Yirong Yang; 2) Face Numbers of Shellable CW Balls and Spheres, by Joshua Hinman; 3) A short proof of the existence of designs, by Peter Keevash; 4) Reasonable Bounds for Combinatorial Lines of Length Three, by Amey Bhangale, Subhash Khot, Yang P. Liu, Dor Minzer; 5) Improved bounds for the Furstenberg-Sárközy theorem, by Ben Green, and Mehtaab Sawhney; 6) q-deformed rationals and q-continued fractions, by Sophie Morier-Genoud and Valentin Ovsienk; 7) A new approach to strong convergence, by Chi-Fang Chen, Jorge Garza-Vargas, Joel A. Tropp, Ramon van Handel; 8) The Aldous–Lyons Conjecture I: Subgroup Tests, by Lewis Bowen, Michael Chapman, Alexander Lubotzky, Thomas Vidick.
Reconstructing a Shellable Sphere from its Facet-Ridge Graph, by Yirong Yang
Abstract: We show that the facet-ridge graph of a shellable simplicial sphere Δ uniquely determines the entire combinatorial structure of Δ. This generalizes the celebrated result due to Blind and Mani (1987), and Kalai (1988) on reconstructing simple polytopes from their graphs. Our proof utilizes the notions of good acyclic orientations from Kalai’s proof as well as k-systems introduced by Joswig, Kaibel, and Körner.
My commentary: A central open problem about triangulated spheres is the conjecture that the dual graph (also known as the facet-ridge graph and the puzzle) of a simplicial sphere determines its full combinatorial structure. For simplicial polytopes this was proved by Blind and Mani in 1987 and I gave a simple proof in 1988. My proof applied to a restricted class of shellable simplicial spheres and now Yang proved it to all shellable spheres. I wrote about the problem in this 2009 post.
Face Numbers of Shellable CW Balls and Spheres, by Joshua Hinman
Imre Bárány posed in the late 1990s the following question:
For a 
Two years ago Hinman proved the conjecture (and some stronger inequalities) for polytopes and his proof strongly used metric properties and especially a result of Perles and Shephard about angles sums of convex polytopes. (See also this post.) Now Hinman goes on to extend his 2022 result to shellable strongly regular spheres. Also here, removing the condition of shellability would be interesting. Hindman also discusses some connections with the strong upper bound conjecture for polytopes and more general cellular objects.
A short proof of the existence of designs, by Peter Keevash
Abstract: We give a new proof of the existence of designs, which is much shorter and gives better bounds.
We wrote about earlier breakthroughs about designs here (2014), here(2016), here (2018) and here (2015). The new proof may come close to the ultimate test for a mathematical proof: To make it to the classroom.
Reasonable Bounds for Combinatorial Lines of Length Three, by Amey Bhangale, Subhash Khot, Yang P. Liu, Dor Minzer
Abstract (slightly shortened): We prove that any subset ![A \subseteq [3]^n](https://web-archive.nli.org.il/National_Library/im_/https://s0.wp.com/latex.php?latex=A+%5Csubseteq+%5B3%5D%5En&bg=ffffff&fg=333333&s=0&c=20201002)
My commentary: Amey Bhangale, Subhash Khot, and Dor Minzer are involved in a long term project (now joined by Yang P. Liu) primarily addressing approximability of satisfiable constraint satisfaction problems that have interesting applications to additive combinatorics. We mentioned some of their earlier results in this post. DHJ[3] was the goal of the first polymath project and I hope that there will be a detailed DHJ post devoted to the new paper. In Polymath1 an ultra-optimistic conjecture for the best DHJ[3] bound was made.
Improved bounds for the Furstenberg-Sárközy theorem, Ben Green, and Mehtaab Sawhney
Abstract: Suppose that 
From the paper: “The proof of Theorem 1.2 makes very substantial use of the results and ideas in a paper of Keller, Lifshitz and Marcus concerning global hypercontractivity in product spaces. This is the culmination of body of work, of which we mention in particular the earlier work of Keevash-Lifshitz-Long-Minzer. We remark in our context, a “local” function is one which strongly correlates with an arithmetic progression with common difference which is a product of “few” elements of Q. A global function by contrast does not correlate strongly with such functions. “
We discussed global hypercontractive inequalities in this post and this one (both posts were authored by Noam Lifshitz). The very recent sharp global hypercontractive inequalities of Keller, Lifshitz and Marcus turned out to be useful for various applications in extremal combinatorics.
q-deformed rationals and q-continued fractions, by Sophie Morier-Genoud and Valentin Ovsienko
Abstract: We introduce a notion of q-deformed rational numbers and q-deformed continued fractions. A q-deformed rational is encoded by a triangulation of a polygon and can be computed recursively. The recursive formula is analogous to the q-deformed Pascal identitiy for the Gaussian binomial coefficients, but the Pascal triangle is replaced by the Farey graph. The coefficients of the polynomials defining the q-rational count quiver subrepresentations of the maximal indecomposable representation of the graph dual to the triangulation. Several other properties, such as total positivity properties, q-deformation of the Farey graph, matrix presentations and q-continuants are given, as well as a relation to the Jones polynomial of rational knots.
My commentary: q-analogs is a central theme in enumerative combinatorics and in other areas of mathematics. Now, the q-analog of an integer ![[n]=1+q+q^2+\cdots+q^{n-1}](https://web-archive.nli.org.il/National_Library/im_/https://s0.wp.com/latex.php?latex=%5Bn%5D%3D1%2Bq%2Bq%5E2%2B%5Ccdots%2Bq%5E%7Bn-1%7D&bg=ffffff&fg=333333&s=0&c=20201002)
![[m/n]](https://web-archive.nli.org.il/National_Library/im_/https://s0.wp.com/latex.php?latex=%5Bm%2Fn%5D&bg=ffffff&fg=333333&s=0&c=20201002)
![\displaystyle [\frac 52] = \frac {1+2q+q^2+q^3}{1+q}~](https://web-archive.nli.org.il/National_Library/im_/https://s0.wp.com/latex.php?latex=%5Cdisplaystyle+%5B%5Cfrac+52%5D+%3D+%5Cfrac+%7B1%2B2q%2Bq%5E2%2Bq%5E3%7D%7B1%2Bq%7D%7E&bg=ffffff&fg=333333&s=0&c=20201002)
A new approach to strong convergence, Chi-Fang Chen, Jorge Garza-Vargas, Joel A. Tropp, Ramon van Handel
From the abstract: “… strong convergence is notoriously difficult to prove and has generally required delicate problem-specific methods. In this paper, we develop a new approach to strong convergence that uses only soft arguments.”
From the paper:
We discussed Charles Bordenaves new simple proof of Friedman’s second eigenvalue Theorem (Alon’s conjecture) and its extension to random lifts, in this 2015 post.
The Aldous–Lyons Conjecture I: Subgroup Tests, by Lewis Bowen, Michael Chapman, Alexander Lubotzky, Thomas Vidick.
From the abstract: “This paper, and its companion [BCV24], are devoted to a negative resolution of the Aldous–Lyons Conjecture [AL07, Ald07]. This conjecture, originated in probability theory, is well known (cf. [Gel18]) to be equivalent to the statement that every invariant random subgroup of the free group is co-sofic. We disprove this last statement.
… By composing this correspondence with a stronger variant of the reduction in MIP*=RE [JNV+21], proved in the companion paper [BCV24], we deduce that approximating the sofic value of a subgroup test is as hard as the Halting Problem, and in particular, undecidable. The combination of our two main results proves the existence of non co-sofic invariant random subgroups of the free group.”
We discussed the MIP*=RE result and the connection to group theory in this post.
Figures and formulas
Moshe Vardi wrote a short interesting essay “What is theoretical computer science?” (It followed by interesting posts on Facebook.) Moshe argues that
Thinking of theoretical computer science (TCS) as a branch of mathematics is harmful to the discipline.
I personally do not regard TCS as part of mathematics and I also don’t think that thinking of TCS as part of mathematics is harmful. Certainly there are parts of TCS that are also parts of mathematics as well. (I will try to add a schematic Venn-diagram a bit later.)
Update: Moshe Vardi gave me pointers to two related works: a) The paper FPRAS Approximation of the Matrix Permanent in Practice by James E. Newman, Moshe Y. Vardi argues that the constants in the “rapid mixing” algorithms for approximating permanents are too large to be realistic (related to item 10 below). b) The 2003 paper: Random 3-SAT the plot thickens describes experiments with SAT solvers on random 3-SATs.
Here are some unorganized quotes from the essay, my thoughts and related links.
(Karp’s committee:) In order for TOC to prosper in the coming years, it is essential to strengthen our communication with the rest of computer science and with other disciplines, and to increase our impact on key application areas.
(Oded and Avi’s view:) In order for TOC to prosper in the coming years, it is essential that Theoretical Computer Scientists concentrate their research efforts in Theory of Computing and that they enjoy the freedom to do so.
steps by Ben Cousins and Santosh Vempala. The question to be asked is: are there practically good algorithms for these tasks?Moshe’s article is part of the opinion section of the Communication ACM, where Moshe has a regular column. Let me also mention the European counterpart “The Bulletin of the European association of Theoretical Computer Science”.
A schematic Venn diagram of TCS, CS, Mathematics and other fields. Of course, every field represented here by a circle is by itself a complex fractal-like object. Avi Wigderson’s lovely book “Mathematics and Computation” gives a great description of some mathematical areas of TCS with a special chapter on connections between TCS and mathematics and another chapter on connections between TCS and other sciences. See also this post.
“Time for Peace” (זמן לשלום), Lyrics: Amnon Abutbul, Yair Dalal, Fathi Kasem; Melody: Amnon Abutbul. Performing Shlomit Aharon and Yevgeni Shapovalov.
This year I had the rare event that the new Jewish year coincides with my birthday, and “time for peace” expresses my wishes for both these occasions.
Click here for the previous post on exciting mathematical irrationality news.
There are very many irrational numbers but proving irrationality of a specific number is not a common event. A few weeks ago Frank Calegari, Vesselin Dimitrov, and Yunqing Tang posted a paper that proved the irrationality of
In fact they proved even more: that 
According to the short abstract, “The argument applies a new kind of arithmetic holonomy bound to a well-known construction of Zagier.”
h/t to Ido Kaminer and members of the “Ramanujan machine team” who told about this result in a recent workshop.
Other number theory updates (Oct 26): Hector Pasten proved that the largest prime factor of 
Shana Tova to all the readers: happy new (Jewish) year!
Some more links: Apéry’s 1979 theorem that ζ(3) is irrational. A blog post on Persiflage about the new irrationality result. A videotaped lecture by Frank Calegari.
![\displaystyle ~[\frac 53] = \frac {1+q+2q^2+q^3}{1+q+q^2}](https://web-archive.nli.org.il/National_Library/im_/https://s0.wp.com/latex.php?latex=%5Cdisplaystyle+%7E%5B%5Cfrac+53%5D+%3D+%5Cfrac+%7B1%2Bq%2B2q%5E2%2Bq%5E3%7D%7B1%2Bq%2Bq%5E2%7D&bg=ffffff&fg=333333&s=0&c=20201002)
Combinatorics and more 
