Timeline for Known approaches for the lower bound on cap-set problem
Current License: CC BY-SA 4.0
21 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 30, 2022 at 16:36 | vote | accept | JPMarciano | ||
| S Sep 23, 2022 at 6:27 | history | suggested | Fred T | CC BY-SA 4.0 |
Fixed detail on Edels bound
|
| Sep 22, 2022 at 16:36 | review | Suggested edits | |||
| S Sep 23, 2022 at 6:27 | |||||
| Sep 22, 2022 at 15:43 | answer | added | Fred T | timeline score: 8 | |
| Dec 10, 2021 at 0:50 | comment | added | JPMarciano | @DavidESpeyer I didn't quite understand how Remind 7 indicates this idea couldn't work in the uncoloured setting. I understand that a 3-AP-free set "induces" a symmetric tricoloured 3-AP-free set. On the other hand, tricoloured sum-set "induces" a assymmetric tricoloured 3-AP-free set... Can you develop a little bit more? | |
| Dec 9, 2021 at 23:38 | comment | added | Will Sawin | @DavidESpeyer One doesn't need to use randomness for that problem. For $\{0,1,2\}^n$, one can simply take all solutions to $\sum_{i=1}^n (a_i-1)^2 = 2n/3$, or something like that, to find sets of size $3^n/\sqrt{n}$. The Behrend approach Is to restrict to the subset of $\{0,\dots \frac{b-1}{2} \}$, which doesn't have the problem you mention where there are 3-APs that don't lift, but this introduces a loss that shrinks as $b$ grows, which forces you to take $b$ large if you want to optimize. | |
| Dec 9, 2021 at 22:46 | comment | added | David E Speyer | I'm going to disagree with @WillSawin's claim that the ability to optimize $b$ is crucial. In my opinion, the key issue is that many $3$-AP's in $\mathbb{F}_3^n$ don't lift to $3$-AP's in $\{ 0,1,2 \} \subset \mathbb{Z}$. For example, $(1,0,2)$ is an AP modulo $3$ but not in $\mathbb{Z}$. I think you should be able to make subsets of $\{ 0,1,2 \}^n$ of size $(3-o(1))^n$ which are $3$-AP free by taking a random linear map $\{ 0,1,2 \}^n \to \mathbb{Z}/P \mathbb{Z}$ and discarding collisions, as in our paper. I think I might leave an answer about this tonight. | |
| Dec 9, 2021 at 18:01 | comment | added | Will Sawin | Alternately you could say we're working in $\mathbb F_3[t]$ and then can work in base $b$ when $b$ is a polynomial of degree $d$. But then the set of "digits" is $\mathbb F_3^b$, and we have returned to the same problem. So the characteristic 3 structure of $\mathbb F_3^n$ makes it harder to approximate with $\mathbb Z^n$ and then with $\mathbb R^n$. | |
| Dec 9, 2021 at 17:59 | comment | added | Will Sawin | @SamHopkins Behrend's construction relies on a specific progression-free set in $\mathbb R^n$, the sphere. Using base notation, you can approximate a large chunk of $\mathbb Z/N$, $n$ large, by $[0,\dots, b/2]^n \subset \mathbb R^n$, and take a sphere in that, then, crucially, optimize $b$ and $n$. In $\mathbb F_3^n$ we don't have an analogue of base notation except in the special case $b=3$, which is not optimal, so we can't apply the same construction. | |
| Dec 9, 2021 at 17:56 | comment | added | Will Sawin | If any method gives an asymptotic of $c^n$ for the cap-set problem, then by specializing it to a particular value of $n$ and taking products of that, you can get $(c-\epsilon)^n$ for any $n$. Since products can never be too far behind, it should maybe not be surprising when (twisted) products are ahead. | |
| Dec 9, 2021 at 17:48 | history | edited | JPMarciano | CC BY-SA 4.0 |
Typo
|
| Dec 9, 2021 at 10:17 | comment | added | Thomas Bloom | It's also worth pointing out that in Edel's paper are more sophisticated ways of leveraging small cap sets into larger ones than just the direct product argument (basically a sort of 'twisted' product instead). | |
| Dec 9, 2021 at 2:10 | comment | added | JPMarciano | @DavidESpeyer Thanks! I'll definitely take a deeper look into it. | |
| Dec 8, 2021 at 18:42 | comment | added | Seva | Edel's bound seems to be the best one presently known, but there are "algebraic" constructions which also give nontrivial bounds. We can only speculate whether the largest capsets come from blowing up some particular example. | |
| Dec 8, 2021 at 18:39 | comment | added | David E Speyer | Our paper can roughly be summarized as "map $F_3^n$ to $F_P$ for a large prime $P \approx 3^n$ and use a Behrend construction in $F_P$." From this perspective, the $\theta^n$ term bound of Ellenberg-Gijswijt comes from the inefficiency of the $F_3^n \to F_P$ construction. (I can say more if you like.) So one answer is that Ellenberg-Gijswijt is measuring the inadequacy of the heuristic that $F_3^n$ is like $F_P$ for $P \approx 3^n$. @SamHopkins | |
| Dec 8, 2021 at 18:31 | comment | added | Sam Hopkins | Here is a related question: what is the reason for the absence of a Behrend-type construction in this setting? | |
| Dec 8, 2021 at 18:24 | comment | added | David E Speyer | I am pessimistic about adopting our method to the non-colored cap set problem; see Remark 7 in our paper for why. I have wondered whether there might be some way to instead use Remark 7's ideas to improve the Ellenberg and Gijswijt bound, but I haven't found a way. | |
| Dec 8, 2021 at 18:22 | comment | added | David E Speyer | I'll promote my paper with Kleinberg and Sawin arxiv.org/abs/1607.00047 . We construct a lower bound for the colored version (which is easier than the original version) which exactly matches the upper bound coming from the polynomial method of Ellenberg and Gijswijt. | |
| Dec 8, 2021 at 17:53 | comment | added | Sam Hopkins | See Remark 6.2.10 of dropbox.com/sh/6ashj34jk6i905n/AAAhThbmPXvJcYOHS0IU2cQJa/… (draft of book by Yufei Zhao on graph theory and additive combinatorics). It claims Edel's is the best published lower bound. | |
| Dec 8, 2021 at 17:50 | comment | added | mathworker21 | I think it's an open problem whether blowing up an example could yield a tight bound. | |
| Dec 8, 2021 at 17:47 | history | asked | JPMarciano | CC BY-SA 4.0 |