# Asymptotic number of $3$-AP's in a set $A\subseteq\mathbb{F}_{p}^{n}$ of density $\epsilon$

Problem: Let $$p$$ be an odd prime number and consider the $$n$$-dimensional vector space over the field with $$p$$ elements. I want to prove that the number of $$3$$-term arithmetic progressions in a subset $$A\subseteq\mathbb{F}_{p}^{n}$$ is $$cp^{2n}$$ for every $$n\geq N_{0}$$, for sufficiently large $$N_{0}$$ and a constant $$c>0$$.

Fact 1: I shall use Meshulam's theorem which states that if a subset $$B\subseteq\mathbb{F}_{p}^{n}$$ has density bigger than $$2/n$$, i.e. $$|B|> \frac{2p^{n}}{n}$$, then $$Β$$ contains a $$3$$-term arithmetic progression.

Fact 2: I also may use the following fact: First observe that if $$U$$ is a subspace of $$\mathbb{F}_{p}^{n}$$, then there are $$p^{n-k}$$ distinct cosets of $$U$$. Now, let $$A\subseteq\mathbb{F}_{p}^{n}$$ be a subset of density $$\epsilon>0$$. Then, there are at least $$\frac{\epsilon}{2}p^{n-k}$$ cosets $$V$$ of $$U$$ such that $$|A\cap V|\geq \frac{\epsilon}{2}p^{k}$$.

As an affine subspace of $$\mathbb{F}_{p}^{n}$$ is just a coset of a subspace of $$\mathbb{F}_{p}^{n}$$, we have that the above implies that there exist at least $$\frac{\epsilon}{2}f(k,n)$$ $$k$$-dimensinal affine subspaces $$V$$ of $$\mathbb{F}_{p}^{n}$$ such that $$|A\cap V|\geq \frac{\epsilon}{2}p^{k}$$, where $$f(k,n)$$ is the total number of the $$k$$-dimensional affine subspaces of $$\mathbb{F}_{p}^{n}$$. This number equals to $$$$f(k,n)=p^{n-k}\binom{n}{k}_{p}$$$$ where $$\binom{n}{k}_{p}$$ is the Gaussian coefficient and id defined as $$$$\binom{n}{k}_{p}=\frac{(p^{n}-1)(p^{n}-p)\cdots(p^{n}-p^{k-1})}{(p^{k}-1)(p^{k}-p)\cdots (p^{k}-p^{k-1})}.$$$$

My attempt goes as follows: Let $$n$$ be large enough so that there exists $$k such that $$\frac{\epsilon}{2}>\frac{2}{k}$$. Then, we consider $$p^{n-k}$$ $$k$$-dimensional affine subspaces $$V$$ of $$\mathbb{F}_{p}^{n}$$ pairwise disjoint (we can take such by taking the $$p^{n-k}$$ of a $$k$$-dimensional subspace). We know that there $$\frac{\epsilon}{2}p^{n-k}$$ of them such that $$|A\cap V|\geq \frac{\epsilon}{2}p^{k}>\frac{2p^{k}}{k}$$. Then, considering each $$A\cap V$$ as a subspace of $$V\cong\mathbb{F}_{p}^{n}$$, Meshulam's theorem implies that each one of them contains a $$3$$-AP and since they are pairwise disjoint there are $$\frac{\epsilon}{2}p^{n-k}$$ $$3$$-AP's in $$A$$.

That is as far as I get. My idea is to use the more powerful statement of Fact 2, where by finding $$cp^{2n}$$ disjoint $$k$$-dimensional affine subspaces of $$\mathbb{F}_{p}^{n}$$ it implies the desired. But I have no clue how to find them. Any ideas?

• Are you aware of Varnavides' paper academic.oup.com/jlms/article-abstract/s1-34/3/358/… , or, say, arxiv.org/pdf/1203.2383.pdf by Serra and Vena?
– Seva
Mar 3 '20 at 8:33
• I was now aware and I think I am talking about Varnavide' s paper. Unfortunately, I have no access in that paper. Is there a way to find it? Mar 3 '20 at 11:12
• No, these two papers do not refer to $\mathbb{F}_{p}^{n}$. Mar 3 '20 at 11:50
• I found the wording of the question a little confusing. But if I have understood it correctly, you want some result saying that large subsets contain many progression? Perhaps Corollary 3.2 in this paper answers your question...arxiv.org/pdf/1905.08457.pdf Mar 10 '20 at 13:39
• Yeah, Corollary 3.2 answers my question, though it is based upon the work of E. Croot, V. Lev, P. P. Pach and J. Ellenberg and D. Gijswijt, rather thatn Meshulam's as I wanted to. Thank you. Yet, I read again my question and I do not seem to understand what do you mean by "confusing wording". Mar 11 '20 at 20:58

I was going to comment with a link to where this Varnavides idea is written up, but to my surprise I couldn't find one simply done in the case of $$\mathbb{F}_p^n$$, so I thought I'd sketch the idea here. (Of course none of this is original to me, it's one of those proofs that is well-known in the field, and is a routine generalisation of the Varnavides proof.)

Let $$A\subset \mathbb{F}_p^n$$ be a set with density $$\lvert A\rvert/p^n=\epsilon$$. Let $$k$$ be some integer to be chosen later, and let $$T$$ be the number of three-term arithmetic progressions in $$A$$ (where here I'm only talking about genuine 3APs, i.e. $$x,x+d,x+2d$$ with $$d\neq 0$$).

Let $$U$$ be an affine subspace of $$\mathbb{F}_p^n$$ of dimension $$k chosen uniformly at random. We compute the expected number of 3APs in $$A\cap U$$ in two different ways.

Let $$q$$ be the probability that a fixed 3AP is in $$U$$ (this is clearly independent of which 3AP we're talking about). Then by linearity of expectation the expected number of 3APs in $$U\cap A$$ is just $$qT$$.

On the other hand, the expected density of $$A\cap U$$ in $$U$$ is $$\epsilon$$. We convert this into a lower bound for the expected number of 3APs as follows. Let $$L$$ be the total number of affine subspaces we're choosing from, and let $$L'$$ be the number of such subspaces $$U$$ where $$\lvert A\cap U\rvert \geq \frac{2}{k}\lvert U\rvert$$ (such subspaces are 'good'). In particular, by Meshulam's bound, any such $$U$$ has the property that $$A\cap U$$ contains at least one non-trivial three-term arithmetic progression

We know that $$\sum_{U} \lvert A\cap U\rvert \geq \epsilon p^k L$$. The contribution from non-good $$U$$ is at most $$\frac{2}{k}(L-L')p^k$$. The contribution from good $$U$$ is trivially at most $$L'p^k$$. Therefore, $$L'+\frac{2}{k}(L-L')\geq \epsilon L,$$ and hence after rearranging, assuming $$\epsilon\geq 4/k$$ and $$k\geq 4$$, say, $$L'\geq \frac{\epsilon}{4}L$$, and hence the probability that $$U$$ is good is $$\geq \epsilon/4$$.

Since any good affine subspace contains at least one 3AP, the expected number of 3APs in $$U\cap A$$ is $$\geq \frac{\epsilon}{4}$$. Comparing this to the other calculation, we see that $$T\geq \epsilon/4q$$. We can calculate $$q$$ as follows.

We know that the total number of 3APs in $$\mathbb{F}_p^n$$ is exactly $$p^n(p^n-1)$$. Similarly the number in any fixed affine subspace of dimension $$k$$ is exactly $$p^{k}(p^{k}-1)$$. Therefore

$$q p^n(p^n-1)= p^{k}(p^{k}-1),$$

and so

$$q = \frac{p^{k}-1}{p^{n-k}(p^n-1)}\ll p^{-2n+2k}.$$

Therefore $$T \gg p^{2n-2k}$$. Our requirement on $$k$$ was that $$\epsilon \geq 4/k$$, and so we can select some $$k=O(\epsilon^{-1})$$, and hence

$$T \gg \epsilon p^{O(\epsilon^{-1})}p^{2n}$$

as required.

Notice that the type of dependence on $$\epsilon$$ was dependent on Meshulam's bound, but for a qualitative bound (so just $$T\geq c(\epsilon)p^{2n}$$ for some $$c_\epsilon$$ depending only on $$\epsilon$$) any density result will do. Similarly, the more powerful result of Ellenberg-Gijswijt yield a correspondingly better dependence on $$\epsilon$$.

• Hi Thomas forgive me if I am misunderstanding your argument but I am not able to see why it follows from Meshulam's theorem that if the expected density of $A \cap U$ in $U$ is high enough to get a single 3-AP then the expected number of 3-APs in $A \cap U$ must be at least 1. Isn't it possible for $A$ to be concentrated in a small number of subspaces in which case Meshulam's criteria would not be triggered very often which would lead to a lower average? Aug 4 '20 at 19:37
• Yes, you're absolutely right - one needs to use some kind of 'popularity principle' to show that there is in fact a high probability that $A\cap U$ has large enough density, which would then give the required lower bound for the expected count of 3APs. I've corrected this in the answer. Aug 4 '20 at 20:02