9
$\begingroup$

Let $r(n):=r_3(\mathbb{F}_3^n)=\max\{|A|: A \subset \mathbb{F}_3^n, \ A \text{ is 3-AP-free}\}$.

Edel proved that $r(n)\geq 2.217^n$ for sufficiently large $n$. His proof is by giving a construction of a cap-set $A$ in $\mathbb{F}_3^{480}$. Then observing that $A^k \subset \mathbb{F}_3^{480k}$ is also a cap set, that is, $$r(480k)\geq |A^k|=|A|^k.$$

Is this the best known lower bound? Are there other known approaches to this problem other than construction in low dimension and then using this product argument?

Is this product argument expected to be the best we could expect? That is, do we hope to construct an $A$ such that this argument is tight?

I'd appreciate any references or answers to some of these questions.

Any help on the tags or on how to better ask these questions would be nice also.

Improve this question
$\endgroup$
15
  • 2
    $\begingroup$ 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. $\endgroup$
    – David E Speyer
    Dec 8, 2021 at 18:22
  • 2
    $\begingroup$ 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. $\endgroup$
    – David E Speyer
    Dec 8, 2021 at 18:24
  • 2
    $\begingroup$ 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. $\endgroup$
    – Will Sawin
    Dec 9, 2021 at 17:56
  • 3
    $\begingroup$ @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. $\endgroup$
    – Will Sawin
    Dec 9, 2021 at 17:59
  • 2
    $\begingroup$ 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. $\endgroup$
    – David E Speyer
    Dec 9, 2021 at 22:46

1 Answer 1

Reset to default
8
$\begingroup$

I've just proved a new lower bound of $2.218^n$, in my paper 'New lower bounds for cap sets': https://arxiv.org/abs/2209.10045.

My new bound comes from extending Edel's ideas, with better computational methods (including a SAT solver) and introducing a new theoretical construction. I also conjecture that a lower bound of $2.233^n$ is possible, which is explained in section 4 of my paper.

My lower bound comes from a cap set in $\mathbb{F}_3^{56232}$, although I do also give cap sets in 396, 420 and 462 dimensions which beat Edel (slight correction to your post: Edel's bound comes from a cap set in $\mathbb{F}_3^{480}$).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.