## Mind Boggling: Following the work of Croot, Lev, and Pach, Jordan Ellenberg settled the cap set problem!

A quote from a recent post from Jordan Ellenberg‘s blog Quomodocumque:

Briefly:  it seems to me that the idea of the Croot-Lev-Pach paper I posted about yesterday (GK: see also my last post) can indeed be used to give a new bound on the size of subsets of F_3^n with no three-term arithmetic progression! Such a set has size at most (2.756)^n. (There’s actually a closed form for the constant, I think, but I haven’t written it down yet.)

Here’s the preprint. It’s very short. I’ll post this to the arXiv in a day or two, assuming I (or you) don’t find anything wrong with it, so comment if you have comments!

This is amazing! The cap set problem was quite popular here on the blog, see also Tao’s 2007 post, and Jordan made also quite an effort over the years in proving the other direction before proving this direction. (Fortunately for our profession, success for two conflicting statements was avoided.) Congratulations to Jordan, Ernie, Seva, and Peter!

Update: Congratulations also to Dion Gijswijt who also derived a similar solution to the cap set problem based on CLP! See this comment on Quomodocumque.

Updates: See also this post by Tao (presenting a symmetric version of the proof), this post by Gowers, this post in by Luca Trevisan, and this post by Peter Cameron, and this post by Anurag Bishnoi. See also this lovely quanta article  Set proof stuns mathematicians by Erica Klarreich. See also the post Polynomial prestidigitation on GLL. There, among other things the relation to Smolensky’s early use of the “halving degree trick” for the polynomial method is noted. (See also this comment.)

Of course, there is also plenty of more to desire: Full affine lines for $q>3$, higher dimensional affine subspaces for $q\ge3$, some application to better bounds for Roth’s theorem, Szemeredi’s theorem, (for more, see this comment by Terry Tao,)… It is all very exciting.

Noga Alon also pointed out that the solution of the cap set problem also settles affirmatively the Erdos-Szemeredi weaker version of the Erdos-Rado Delta-system conjecture (via the connections discussed in this post) and also shows that a certain direction for showing that ω=2 for matrix multiplication cannot possibly work. The Erdos-Rado sunflower conjecture is still (at least for a few days) open.

Can the affine results be applied for integers or for combinatorial setting? The geometries are quite different but still… This is of great interest here (and also for other problems like the Kakeya problem). Starting from a positive density set in $Z_3^n$ considered as a subset of $Z_{3^{100}}^m$ we can find there a $10^{100}$-dimensional affine subspace contained in the set. Can’t we use it (or such a subspace with a few additional pleasant properties) to get just a single combinatorial line over $Z_3$, or, easier, just a 3-term arithmetic progression when $A$ represent a subset of {1,2,… , $3^n$ }?  A bit later: These thoughts about the relevance of finite field results to questions for the integers (or reals) are not really relevant to the new discovery.  But what seems to be relevant is the possibility to transfer the new method for the cap set problem back to the question on better lower bounds for Roth’s theorem.

More updates: Eric Naslund and Will Sawin gave a direct proof based on the polynomial method for the Erdos-Szemeredi sunflower conjecture, and an even  stronger result is given by Naslund here. (Eric also has stronger quantitative bounds for Erdos-Szemeredi based on bounds for cap sets.)   Ben Green has studied the analogue of Sarkozy’s theorem in function fields (other results on function fields are mentioned by Bloom in this comment);  Variants on the CLPEG-arguments are described by Petrov and by Bishnoi over the comment threads here and here.  Here is a paper by Jonah Blasiak, Thomas Church, Henry Cohn, Joshua A. Grochow, Chris Umans, on consequences of the cap set result for fast matrix multiplication.

More updates (May 31): New applications are mentioned in a new post on quomodocumque: sumsets and sumsets of subsets including a lovely new application by Jordan, a link to a paper  by Robert Kleinberg: A nearly tight upper bound on tri-colored sum-free sets in characteristic 2. And here is a link to a new manuscript by Fedor Petrov Many Zero Divisors in a Group Ring Imply Bounds on Progression–Free Subsets.

One more: (Quoting Arnab Bhattacharyya, June 15 2016 on GLL) Another amazing result that follows from these techniques for one of my favorite problems: http://arxiv.org/pdf/1606.01230v2.pdf. Fox and LM Lovasz improve the bounds for the arithmetic triangle removal lemma dramatically, from a tower of two’s to polynomial!

More (Early July 2016) : An interesting new post on Ellenberg’s blog.

David Conlon pointed out to two remarkable papers that appeared on the arxive:

### Joel Moreira solves an old problem in Ramsey’s theory.

Monochromatic sums and products in $\mathbb N$.

Abstract: An old question in Ramsey theory asks whether any finite coloring of the natural numbers admits a monochromatic pair ${x+y,xy}.$ We answer this question affirmatively in a strong sense by exhibiting a large new class of non-linear patterns which can be found in a single cell of any finite partition of N. Our proof involves a correspondence principle which transfers the problem into the language of topological dynamics. As a corollary of our main theorem we obtain partition regularity for new types of equations, such as $x^2-y^2=z$ and $x^2+2y^2-3z^2=w$.

### Ernie Croot, Vsevolod Lev, Peter Pach gives an exponential improvement to Roth over $\mathbb Z_4^n$.!

Abstract: We show that for integer $n>0$, any subset $A$ of $Z^n_4$ free of three-term arithmetic progressions has size $|A|<2(\sqrt n +1)4^{cn}$, with an absolute constant $c$ approximately equal to 0.926.

David Ellis made a few comments: Three ‘breakthrough’ papers in one week – one in combinatorial geometry (referring to the Erdos-Szekeres breakthrough) , one in additive number theory and one in Ramsey theory – not bad!; . I’ve now read all of the proofs and am sure (beyond reasonable doubt) that they’re all correct – an unusually short time-frame, for me at any rate! The Croot-Lev-Pal Pach paper is a really beautiful application of the polynomial method – a ‘genuinely’ self-contained paper, too, and very nicely written.

I find the $Z_4^n$ result quite mind boggling! What does it say about $Z_3^n$???

### Post by Green

In another facebook post Ben Green writes:  I Wish I could just casually hand Paul Erdos a copy of Annals of Math 181-1. 4 of the 7 papers are: solution to the Erdos distance conjecture by Guth and Nets Katz, solution to the Erdos covering congruence conjecture by Hough, Maynard’s paper on bounded gaps between primes, and the Bhargava-Shankar paper proving that the average rank of elliptic curves is bounded.

## The Erdős Szekeres polygon problem – Solved asymptotically by Andrew Suk.

Here is the abstract of a recent paper by Andrew Suk. (I heard about it from a Facebook post by Yufei Zhao. I added a link to the original Erdős Szekeres’s paper.)

Let ES(n) be the smallest integer such that any set of ES(n) points in the plane in general position contains n points in convex position. In their seminal 1935 paper, Erdős and Szekeres showed that

$ES(n)\le {{2n-4}\choose{n-2}}+1=4^{n-o(n)}$

In 1960, they showed that

$ES(n) \ge 2^{n-2}+1$,

and conjectured this to be optimal. Despite the efforts of many researchers, no improvement in the order of magnitude has ever been made on the upper bound over the last 81 years. In this paper, we nearly settle the Erdős-Szekeres conjecture by showing that

$ES(n)=2^{n+o(n)}$.

This is amazing! The proof uses a 2002 “positive-fraction” version of the Erdős-Szekeres theorem by Pór and Valtr.

Among the many beautiful results extending, applying, or inspired by the Erdős Szekeres theorem let me mention an impressive recent body of works on the number of points in $\mathbb R ^d$ which guarantee n points in cyclic position. A good place to read about it is the paper by Bárány, Matoušek and Pór Curves in $\mathbb R^d$  intersecting every hyperplane at most d+1 times, where references to earlier papers by Conlon, Eliàš,  Fox, Matoušek, Pach, Roldán-Pensado, Safernová, Sudakov, Suk, and others.

## The Quantum Computer Puzzle @ Notices of the AMS

### The Quantum Computer Puzzle

My paper “the quantum computer puzzle” has just appeared in the May 2016 issue of Notices of the AMS. Here are the beautiful drawings for the paper (representing the “optimistic view” and the “pessimistic view”) by my daughter Neta.

And the summary of my view

Understanding quantum computers in the presence of noise requires consideration of behavior at different scales. In the small scale, standard models of noise from the mid-90s are suitable, and quantum evolutions and states described by them manifest a very low-level computational power. This small-scale behavior has far-reaching consequences for the behavior of noisy quantum systems at larger scales. On the one hand, it does not allow reaching the starting points for quantum fault tolerance and quantum supremacy, making them both impossible at all scales. On the other hand, it leads to novel implicit ways for modeling noise at larger scales and to various predictions on the behavior of noisy quantum systems.

The nice thing is that my point of view is expected to be tested in various experimental efforts to demonstrate quantum computational supremacy in the next few years.

Updates (April, 24 2016): Here is an expanded version of the paper, with references, additional predictions and discussion. Here is a related post on GLL.

### Polymath10 Plans, polymath11 news, and other plans.

The plan for polymath10: I hope to come back to it soon, report on some computer experimentation  and, of course, further comments on post 4 are most welcome. I hope to be able to report on some computer experimentation regarding the various conjectures and ideas.  I am planning to launch a fifth post in May.  Overall, I consider one year as a good time span for the project. Post 4 of Polymath11 is still active on Gowers’s blog, and I think that a fifth post is also in planning.

Here on the blog,  I plan a  mathematical post about my visit to Yale on February. The visit have led to Stefan Steinerberger’s beautiful post on Ulam sequences.  There are also newer interesting things, from our combinatorics seminar at HUJI, and from the third Simons’ conference on the analysis of Boolean functions (I hoped Ryan will blog about the conference). In celebration of the recent breakthrough on sphere packing in dimensions 8 and 24  I also plan to write more on sphere packing.

Happy Passover!

Pictures with Avi Wigderson at Nogafest and with Alex Lubotzky at Yale.

## Three Conferences: Joel Spencer, April 29-30, Courant; Joel Hass May 20-22, Berkeley, Jean Bourgain May 21-24, IAS, Princeton

Dear all, I would like to advertise three  promising-to-be wonderful mathematical conferences in the very near future.

Quick TYI. See if you can guess the title and speaker for  a lecture described by  “where the mathematics of Cauchy, Fourier, Sobolev, Gelfand and Bourgain meet. (Answer at the end of the post.)”

## Random Roads – Joel Spencer’s 70 conference,  April 29-30 2016, at Courant NYC.

Joel Spencer’s 70th birthday conference is coming up on April. Here is the website

.

## Geometry, Topology and Complexity of Manifolds, and applications to Biology – Joel Hass’ 60th birthday, May 20-22, 2016 at UC Berkeley.

Joel Hass’ 60th birthday conference is coming up in May at UC Berkeley. Here is the website.

## Analysis and Beyond: Celebrating Jean Bourgain’s Work and Impact, May 21-24, I.A.S., Princeton.

A conference celebrating Jean Bourgain’s work is coming up in May at Princeton. Here is the conference page.

Answer:  Speaker: Haim Brezis; TitleOld-new perspectives on the winding number;

## Math and Physics Activities at HUJI

Between 11-15 of September 2016 there will be a special mathematical workshop for excellent undergraduate students at the Hebrew University of Jerusalem. In parallel there will also be a workshop in physics. These workshops are aimed for second and third year undergraduate students. Here is the list of speakers! You need to register before June 15, 2016. More details below.

## Open day, April 20, 2016

Two days from now on Wednesday April 20 there will be a splendid open day at the math department.  Do not miss it!!

## Stefan Steinerberger: The Ulam Sequence

This post is authored by Stefan Steinerberger.

The Ulam sequence

$1,2,3,4,6,8,11,13, 16, 18, \dots$

is defined by starting with 1,2 and then repeatedly adding the smallest integer that is (1) larger than the last element and (2) can be written as the sum of two distinct earlier terms in a unique way. It was introduced by Stanislaw Ulam in a 1962 paper (On some mathematical problems connected with patterns of growth of figures’) where he vaguely describes this as a one-dimensional object related to the growth of patterns. He also remarks (in a later 1964 paper) that simple questions that come to mind about the properties of a sequence of integers thus obtained are notoriously hard to answer.’ The main question seems to have been whether the sequence has asymptotic density 0 (numerical experiments suggests it to be roughly 0.07) but no rigorous results of any kind have been proven so far.

A much stranger phenomenon seems to be hiding underneath (and one is tempted to speculate whether Ulam knew about it). A standard approach in additive cominatorics is to associate to the first $N$ elements of a sequence $a_1, a_2, \dots, a_N$ a
function

$f_N(\theta) = \exp{(a_1 i \theta)} + \exp{(a_2 i \theta)} + \dots + \exp{(a_N i \theta)}$

and work with properties of $f_N$. If we do this with the elements of the Ulam sequence and plot the real part of the function, we get a most curious picture with a peak around
$\theta \sim 2.571447\dots$

Such spikes are generally not too mysterious: if we take the squares $1,4,9,16, ...$ we can observe a comparable peak at $\theta = 2\pi/4$ for the simple reason that squares are $\equiv 0, 1$ (mod 4). However, here things seem to be very different: numerically, the Ulam sequence does seem to be equidistributed in every residue class. Due to $2\pi-$periodicity, the function $f_N$ only sees the set of numbers

$\left\{ \theta a_n~\mbox{mod}~ 2\pi: 1 \leq n \leq N\right\}$

and it makes sense to look at the distribution of that sequence on the torus for that special value $\theta \sim 2.571447\dots$. A plot of the first 10 million terms reveals a very strange distribution function.

The distribution function seems to be compactly supported (among the first 10 million terms only the four elements $2, 3, 47, 69$ give rise to elements on the torus that lie outside $[\pi/2, 3\pi/2]$.) The same phenomenon seems to happen for some other initial conditions (for example, 2,3 instead of 1,2) as well and the arising distribution functions seem to vary greatly.

Question 1: What is causing this?

Question 2: Are there other `natural’ sequences of integers with that property?

See also Stefan’s paper  A Hidden Signal in the Ulam sequence .

Update: See also Daniel Ross’  subsequent study of Ulam’s sequence, presented in Daniel’s sort of public ongoing “research log”.  (“It includes a summary at the top of the most interesting observations to date, which usually lags a couple weeks behind the most current stuff.”)

Posted in Guest blogger, Open problems | | 8 Comments

## TYI 26: Attaining the Maximum

(Thanks, Dani!) Given a random sequence $a_1,a_2,\dots , a_n$, ***$a_i \in \{-1,1\}$***, $n>2$, let $S_k=a_1+a_2+\cdots +a_k$. and assume that $S_n=0$.  What is the probability that the maximum value of $S_k$ is attained only for a single value of $k$?

Test your intuition: is this probability bounded away from 0? tends to 0 like $1/\sqrt n$? Quicker? Slower? Is there a nice formula?

Posted in Combinatorics, Probability, Test your intuition | Tagged | 21 Comments

Maryna Viazovska

## The news

Maryna Viazovska has solved the densest packing problem in dimension eight! Subsequently, Maryna Viazovska with Henry Cohn, Steve Miller, Abhinav Kumar, and Danilo Radchenko solved the densest packing problem in 24 dimensions!

Here are the links to the papers:

Maryna Viazovska, The sphere packing problem in dimension 8

Henry Cohn, Abhinav Kumar, Stephen D. Miller, Danylo Radchenko, Maryna Viazovska,
The sphere packing problem in dimension 24

(I thank Steve Miller and Peter Sarnak for telling me about it.)

Update: The February 2017 issue of the Notices of the AMS has a beautiful paper by Henry Cohn  entitled A conceptual breakthrough in sphere packing about the developments described in the post.

## Some Background

Kepler, Gauss, Hales, Cohn and Kumar. A central mathematical problem is to find the densest sphere packing in $R^d$. The case $d=3$ is known as the Kepler conjecture. Gauss solved it for lattice packings, and Thomas Hales proved it for general packing using a massive use of computations. Cohn and Kumar settled the lattice case for dimensions 8 and 24.

Conway and Sloane. The “bible” regarding sphere packing is the classic book by two major player of the theory John Conway and Neil Sloane.

Hales and Fejes Toth.  Announced in 1998 and published a few years later, Hales’ proof  relies on some early work of Laszlo Fejes Toth. Since a full verification would require developing much of  the whole project from scratch, Hales himself led a team of researchers to find a formal proof which was published in 2015.

Lie and  Leech.   Lower bounds for higher dimensions. For some dimensions, special lattices of Lie type give surprisingly dense lattice packings. The Leech lattice gives a remarkably dense packing in dimension 24.

Minkowski,…, Ball, Vance and Venkatesh,  For asymptotically large dimensions a probabilistic method by Minkowski gives the best known lower bound up to small (but exciting) improvements. It gives a packing of density $2 \cdot 2^{-n}$.  Here is a slide from a lecture by Henry Cohn on the state of the art for the asymptotic question. (And here is the link to the slides of the full lecture.)

Delsartes, Kabatiansky and Levenshtein. Upper bounds via linear programming. Delsartes’ linear programming method (that can be seen as a Fourier/spectral attack with special features,) had led to important results towards general upper bounds by Kabatiansky and Levenshtein.

Cohn and Elkies developed related spectral methods applying directly to sphere packing, which allow to improve the upper bounds in dimensions 4–31 and give strikingly good results in dimensions 8 and 24.  Cohn and Kumar used these linear programming methods to settle the densest lattice problem in dimensions 8 and 24 and to give extremely good numerical upper bounds for the non-lattice case.

This is the starting point for Viazovska’s breakthrough.

Related problems/issues  to keep in mind: The densest packing problem in other dimensions and when the dimension tends to infinity; Kissing numbers and spherical codes; Upper bounds for error correcting codes; packing in other symmetric spaces; packing covering and tiling in combinatorics and geometry.

## Viazovska’s breakthrough

The little I can tell you is that for a solution one needs to identify certain functions to plug in to the spectral machine. And Maryna’s starting point was some familiar extraordinary elliptic functions and modular forms.  More details on the comment section are most welcome.  (Update:) John Baez wrote on the n-Category Cafe some elementary comments on the proofs: E8 is the best.

## The 24-dimensional case

A key ingredient for the result in dimension 24 is the earlier numerical rationality conjectures by Cohn and Miller.  Those now appear in the preprint: Henry Cohn, Stephen D. Miller, Some properties of optimal functions for sphere packing in dimensions 8 and 24 .

Congratulations to Maryna, Abhinav,  Danilo,  Henry, and Steve!

I remember a decade ago that Steve Miller explained to me some developments, ideas, and dreams  regarding two problems. One was the sphere packing problem in dimensions 8 and 24 that he now took part in solving, and the other was the irrationality questions regarding zeta functions at odd integers (and maybe also the Euler constant.)  Time to move to the second problem, Steve 🙂

(And a trivia question: name a player in both these stories. As usual if you answer in the comment section please give a zero-knowledge answer demonstrating that you know the solution without revealing it.)

## Polymath10-post 4: Back to the drawing board?

It is time for a new polymath10 post on the Erdos-Rado Sunflower Conjecture. (Here are the links for post1, post2, post3.) Let me summarize the discussion from Post 3 and we can discuss together what directions to peruse. It is a pleasure to mention that in parallel Tim Gowers is running polymath11 aimed for resolving Frankl’s union closed conjecture. Both questions were offered along with the Erdos discrepancy problem and the Erdos-Hajnal conjecture in this 2009 post by Tim. In fact, some people participate both in polymath10 and polymath11. The acronym for polymath 11 is FUNC and I suppose we can choose between SUN or ERSC or some other options for polymath10.

Because of polymath10, I did not discuss over here other things. Let me mention two super major developments that I am sure you all know about. One is Laci Babai’s  quasi-polynomial algorithm for Graph isomorphism. (This is a good time to mention that my wife’s mother’s maiden name is Babai.) You can read about it here (and the next three posts) and here. Another is the solution by Jean Bourgain, Ciprian Demeter, Larry Guth of Vinogradov’s main conjecture. You can read about it here and here.

## Polymath10:

We denoted by $f(k,r)$ the largest cardinality of a family of $k$-sets without a sunflower of size $r$, and  $f(k,r,m,n)$ the largest cardinality in a family of $k$-subsets of $[n]$ with the property $P(r,m)$, namely without a sunflower of size $r$ with head of size at most $m$. Adding the subscript $b$ for $f_b(k,r),f_b(k,r,m,n)$ refer to balanced families rather than to arbitrary family. The “Erdos-Ko-Rado regime” is when $r=2$ and $m$ is arbitrary or when $m=1$ and $r$ is arbitrary. (In this regime the property $P(r,m)$ is preserved under shifting.)

### Results by Ferdinand Ihringer

Ferdinand gave interesting upper bounds and lower bounds for $f(k,r,m,n)$ in terms of $f(k,r)$.

$f(m, r) \leq f(k, r, m, n) / \binom{n-m}{k-m} \leq 10 f(k, r)^3.$

For the upper bound see this writeup by Ferdinand. For more details see this comment and the following ones. It will be interesting to find sharp lower and upper bounds.

### Proposal by Domotor Palvolgyi

Domotor raised   in this comment and the following ones some ideas for using algebraic methods for the sunflower conjecture. This have led to an interesting discussion (following these comments) between Domotor and Ferdinand on connection between Sunflowers and Ramsey numbers (mainly $R_3(k)$).

So that this post will not interrupt this interesting discussion let me quote the beginning of Domotor’s comment posted minutes ago:

“So let us denote the size of the largest $k$-uniform family without $r$ (different) sets whose pairwise intersection has the same size by $g(k,r)$. As we have seen in the earlier discussion, trivially $g(k,r)\le f(k,r)$ and $g(k,r)\le R_r(k)$ (where in the last Ramsey notation we forbid $K_r$ in a $k$-coloring of the complete graph). Mysteriously, for all three functions we have similar lower and upper bounds. In this comment I propose to try proving $f(k,r) \le g(ck,r)$ for some $c$.”

### Proposal by Shachar Lovett.

Shachar Lovett proposed in this comment how to use the topological Tverberg theorem for attacking a certain important special case of the conjecture.

### Reminder: Reduction to the balanced case, Phillip Gibbs’ construction, and more drastic reductions.

We started with the observation that every family $F$ of $k$-sets contains a balanced subfamily of size $\frac {k!}{k^k}|F|$. (BTW for graphs there is a sharper result by Noga Alon and it would be interesting to extend it to hypergraphs!) This gives that

$f(k,r) \le e^kf_b(k,r).$

Phillip Gibbs showed in this comment that if the sunflower conjecture is true then

$f_ (k,r) \le (1+o(1))^kf_b(k,r).$

It will be interesting to describe precisely what (1+o(1)) stands for, and improve it as much as possible. All left to be done for a counterexample to the sunflower conjecture is to complement Phillip construction by another one showing an exponential gap between the balanced and general case. This is certainly a tempting direction.

More drastic reductions then the very basic one are also possible, for example: for families of $k$-subsets without a sunflower of size 3 it is enough to consider families with elements colored by $100k$ colors such that every set is colored by consecutive colors and two sets sharing $k-1$ elements are not using the same color-intervals. (This implies “high girth” of some sort.) We can ask if this type of reductions is useful for proving the conjecture, if one can show (like Phillip) that assuming the conjecture, the gap between the bounds for this version is not too large compared to the general version, and hope that this can be part of a construction going in the negative direction.

## The Homological/Algebraic Approach

In quite a few comments to post 3, I tried to further develop the homological ideas   (and to mention some low hanging fruits and related questions). We did reach a major obstacle sending us back to the drawing board. I see some possible way around the difficulty and I will now describe it. For this purpose I will review the homological ideas in somewhat more general and very elementary context. (We only briefly mention the connection with cycles/homology but it is not needed).

### Compound matrices, weak isomorphism and dominance.

Let $X=(x_ij)_{1 \le i \le n, 1 \le j \le n}$ be a generic matrix. The $k$-th compound matrix $C_k(X)$ is the matrix of $k$ by $k$ minors. Namely, $C_k(X)=x_{ST}$, $S,T \in {{[n]} \choose {k}}$ where $x_{ST}=det(x_{ij})_{i \in S,j\in T}$.

Given two $k$-unform hypergraphs $F,G$ we say that $F$ and $G$ are weakly isomorphic if the $m\times m$ minor $C_{F,G}(X)$ of $C_k(X)$ whose rows and columns correspond to sets in $F$ and $G$ respectively is non-singular. (It is fairly easy to see that if $F$ and $G$ are isomorphic then they are weakly isomorphic. This relies on the condition that $X$ is generic.) We will say that $F$ dominates $G$ if  $|F|\ge |G|$ and $C_{F,G}(X)$ is full rank. Thus, $F$ and $G$ are weakly isomorphic if each dominates the other.

Let $D[b,c]$ be the set of $k$-subsets $S$ of $[n]$ such that $|S \cap [b]|\ge c$.  The connection with our notions of acyclicity is as follows: $F$ is acyclic (i.e. $Z_{k-1}(K)=0$) iff $F$ is dominated by $D[1,1]$. In greater generality,   $K_{k-1}[b,c]=0$ iff $F$ is dominated by $D[b,c]$. (In particular,  $Z_{k-1} [r,1](K)=0$ iff $F$ is dominated by $D[r,1]$, and $Z_{k-1}[m,m](K)=0$ iff $F$ is dominated by $D[m,m]$.) Remark: Here and later in the post $Z_*[b,c]$ with $H_*[b,c]$ since we deal only with cycles for the top dimension, so there are no “boundaries” to mod out.

### Algebraic shifting

A family $F$ of $k$-subsets of $[n]$ is shifted if whenever $S \in F$ and $R$ is obtained by replacing an element by a smaller element then $R \in F$.  It can be shown that two shifted families of the same size are weakly isomorphic only if they are equal! We can use our compound matrix to describe an operation (in fact, several operations) called shifting which associated to a family $F$ a shifted family $\Delta_T(F)$.  Suppose that $|F|=m$. $\Delta (F)$ is the lexicographically smallest family of sets which is weakly isomorphic to $F$. In more details: we first consider a total ordering $T$ on $k$-subsets of $[n]$. Then we greedily  build a hypergraph which is dominated by $F$.  When we reach $m$ sets we obtain a  hypergraph $\Delta_T(F)$ weakly isomorphic to $F$.

Now, if the total ordering is the lexicographic order on ${{[n]} \choose {k}}$ then we denote $\Delta(F)=\Delta_T(F))$ and call $\Delta(F)$ the “algebraic shifting” of $F$. In this case, it can be shown that the resulting family is shifted. Also of special importance is the case that $T=RL$ is the reverse lexicographic order.

For sets of integers of size $k$, the lexicographic order refers to the lexicographic order when we ordered the elements of every set from increasingly, and the reverse lexicographic order is the lexicographic order when we order the elements decreasingly.

From 12<13<14<15<…<21<22<…<31<32<… we get

$\{1,2\} <_L \{1,3\} <_L \{1,4\}$ $\dots <_L$ $\{ 2,3\} <_L$ $\{2,4\} <_L \dots$

and from  21<31<32<41<42<43<51<52<…  we get

$\{1,2\} <_{RL} \{1,3\}<_{RL}\{2,3\}<_{RL}\{1,4\}\dots$

We mention again some connection with acyclicity and homology: $F$  is acyclic if all sets in $\Delta (F)$ contains ‘1’. $F$ is $[r,1]$-acyclic iff all sets in in $\Delta (F)$ intersect $[r]$. $F$ is $[m,m]$-acyclic iff all sets in $\Delta(F)$ contains $[r]$. For general $b,c$, $[b,c]$-acyclicity is not expressed by those two versions of algebraic shifting, however, $F$ is $[s,k]$-cyclic if $\Delta_{RL}(F) \subset {{[s]}\choose{k}}$.

### Algebraic shifting in  the Erdos-Ko-Rado regime.

The following properties are preserved under algebraic shifting:

(1) Every two members of $F$ has at least $m$ elements in common.

(2) There are no $r$ pairwise disjoint sets in $F$.

For balanced families we know even more:

(3) If $F$ is balanced and every two members of $F$ has at least $m$ elements in common then all sets in $\Delta(F)$ contains $[m]$.

and

(4) If $F$ is balanced and there are no $r$ pairwise disjoint sets in $F$, then every set in $\Delta(F)$ intersects $[r-1]$.

### Reverse shifting in the Erdos-Ko-Rado regime.

As it turns out we have much stronger statements:

The following properties are preserved under reverse-lexicographic algebraic shifting:

(5) Every two members of $F$ has at least $m$ elements in common.

(6) There are no $r$ pairwise disjoint sets in $F$.

(I dont know if (3) and (4) extends as well. It  certainly worth the effort to check it.)

### Modified plan for attack:

Our ultimate conjecture remains the same:

Main Conjecture:  If $F$ has no sunflower of size $r$ then it is $[xk,k]$-acyclic. (I.e., $Z_{k-1}[(xk,k](K)=0.$)

For balanced family we conjectured that $x=(r-1)$ and for the non-balance we had a larger value $x=r$.

Our homological approach mainly for the balanced case was to use the local homological condition from  (2) (or(4)) (with some additional homological condition yet to be proved – this was Conjecture A) to conclude (This was Conjecture B) that $F$ is $[xk,k]$-acyclic. However,  Conjecture B turned out to be false.  Our new idea is to replace the local conditions on homology obtained from (2), (4) by those given by (6) which are apparently quite stronger.

We also tried to explore how to prove the main conjecture via  an even stronger statement for “combinatorial cycles”. This works for the balanced case in the Erdos-Ko-Rado-regime (leading to some interesting consequences). But we did not manage to extend it beyond this regime. Domotor  shoot down some half-baked attempts towards such a goal.

What we propose now is to use the following theorem instead of Conjecture A and to greatly modify Conjecture B accordingly. (For general families; being balanced is not used.)

Theorem: Let $F$ is a family of $k$-sets without a sunflower of size $r$. Then

(*) For every family of $i$-sets $F'$ which is the link of a set of size $k-i$ (including the case $F'=F)$ , Every set in $\Delta _{RL}(F')$ intersect $[(r-1)i]$.

Conjecture B (greatly modified): For a family $F$ of $k$-sets satisfying (*) we have

(**) $\Delta_{RL}(F) \subset {{[rk]}\choose{k}}$.

This is the new plan! Below are a couple of comments.

### A new homological translation:

We can, I think,  translate the condition on reverse lexicographic shifting also to some conditions on homology, given in this comment,  but the connection is still a little dubious and need some further checking and explanation. (Specifically, it relies on a comment I make in my paper on algebraic shifting that if $F$ is a family of $k$-subsets of $[n]$ and  $G$ is its complement, then the shifting of $F$ is related to the reverse lexicographic shifting of $G$ as follows: takes the complement of $\Delta (F)$ and apply the involution sending element $i$ to $n-i$.)

If $K$ is the simplicial complex spanned by our family $F$ and $L$ is the simplicial complex spanned by the complement of $F$  we want to replace conditions of the form

(*) $Z_{k-1}[s,1] (K)=0$

by the stronger condition

(**) $Z_{k-1}[n-s-k,1] (L)\ne 0$

For example, for a graph $G$ with $n$ vertices and $n-1$ edges $\Delta (G)$ gives all edges containing ‘1’ (which is equivalent to (*) for $s=1$) if and only if $G$ is a tree. But requiring it for $\Delta_{RL}(G)$  implies (I think) that $G$  be a star and is equivalent (I think) to $Z_1[n-3,1](\bar G)\ne 0$, where $\bar G$ is the complement of $G$.

### Planned experimentation.

We plan to run computer experimentation to test some of these ideas on small cases.

### A few words on symmetric shifting and related notions of homology.

Let me mention that there is a variant of compound matrix, weak equivalence and of algebraic shifting (and hence also of the various homology groups we considered,) when we use symmetric products instead of exterior products.  The theories based on those variants are very similar, and the advantage of the notions based on symmetric powers is that they are closer to studied notions of commutative algebra. (But I think they will be harder to compute as determinants are replaced by permanents.)