3
$\begingroup$

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 \begin{equation} f(k,n)=p^{n-k}\binom{n}{k}_{p} \end{equation} where $\binom{n}{k}_{p}$ is the Gaussian coefficient and id defined as \begin{equation} \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})}. \end{equation}


My attempt goes as follows: Let $n$ be large enough so that there exists $k<n$ 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?

$\endgroup$
7
  • 1
    $\begingroup$ 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? $\endgroup$
    – Seva
    Mar 3 '20 at 8:33
  • $\begingroup$ 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? $\endgroup$ Mar 3 '20 at 11:12
  • $\begingroup$ No, these two papers do not refer to $\mathbb{F}_{p}^{n}$. $\endgroup$ Mar 3 '20 at 11:50
  • 2
    $\begingroup$ 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 $\endgroup$ Mar 10 '20 at 13:39
  • 1
    $\begingroup$ 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". $\endgroup$ Mar 11 '20 at 20:58
3
$\begingroup$

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<n$ 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$.

$\endgroup$
2
  • 2
    $\begingroup$ 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? $\endgroup$
    – Ivan Meir
    Aug 4 '20 at 19:37
  • 2
    $\begingroup$ 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. $\endgroup$ Aug 4 '20 at 20:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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