An inverse theorem for Generalized Arithmetic Progression with mild multiplicative property

Ernie Croot and Junzhe Mao School of Mathematics, Georgia Institute of Technology, Atlanta, GA 30332-0160 USA [email protected] School of Mathematics, Georgia Institute of Technology, Atlanta, GA 30332-0160 USA [email protected]

Abstract.

In this paper we prove a structural theorem for generalized arithmetic progressions in $\mathbb{F}_{p}$ which contain a large product set of two other progressions.

1. Introduction

Let $p$ be a prime number, $\mathbb{F}_{p}$ be the finite field with $p$ elements. Recall that a generalized arithmetic progression (GAP) of rank $d$ in $\mathbb{F}_{p}$ is a set of the form

B=x_{0}+\{\sum_{i=1}^{d}a_{i}x_{i}:a_{i}\in[0,N_{i}-1]\}

for some elements $x_{0},x_{1},\ldots,x_{d}\in\mathbb{F}_{p}$ and positive integers $2\leq N_{1},\ldots,N_{d}\leq p.$ We say $B$ is proper if $|B|=N_{1}N_{2}\ldots N_{d}.$ GAPs play an important role in additive combinatorics, as they exhibit an almost periodic behavior under addition. Another example of additively structured sets is Bohr sets. Given $\Gamma\subset\mathbb{F}_{p}$ and $\epsilon>0,$ the Bohr set $B(\Gamma,\epsilon)$ is defined as

B(\Gamma,\epsilon)=\left\{x\in\mathbb{F}_{p}:\left\|\frac{xr}{p}\right\|<\epsilon,\forall r\in\Gamma\right\}.

Here $\left\|\cdot\right\|$ denotes the distance to the nearest integer. One can think of Bohr sets as approximate subspaces or (additive) subgroups in $\mathbb{F}_{p}$ . It turns out that GAPs and Bohr sets are closely related. Using the geometry of numbers, one can show that any Bohr set $B(\Gamma,\epsilon)$ must contain a large symmetric proper GAP with bounded rank. This fact has been used to prove a foundational result in additive combinatorics, namely Freiman’s theorem: given a finite set $A\subset\mathbb{F}_{p}$ and some $C>0,$ if $|A+A|\leq C|A|,$ where

A+A=\{a_{1}+a_{2}:a_{1},a_{2}\in A\},

then there exists a GAP $B$ such that $A\subset B$ and $|B|\ll_{C}|A|$ . Here we use the Vinogradov notation $\ll_{C}$ meaning that there is some constant $K>0$ depending on $C$ so that $|B|\leq K|A|.$ Freiman’s theorem tells us that GAPs are the “standard model” for sets with rich additive structures. For more properties and applications of Bohr sets and GAPs, we refer the reader to [9].

One of the reasons people are concerned about these additively structured sets is the sum-product phenomenon, which basically says no set can have rich additive structure and multiplicative structure simultaneously. For example, in [3] Erdös and Szemerédi conjectured that if a set $A\subset\mathbb{Z}$ satisfies

|A+A|\leq K|A|

for some constant $K>0,$ then for any $\epsilon>0,$ $|AA|\gg|A|^{2-\epsilon}$ , where

AA=\{a_{1}a_{2}:a_{1},a_{2}\in A\}.

This has been confirmed for $A\subset\mathbb{R}$ by a result of Elekes and Ruzsa [2], and recently verified for thin sets $A\subset\mathbb{F}_{p}$ by a result of Kerr, Mello and Shparlinski [6]. The case when $A\subset\mathbb{F}_{p}$ and $|A|\sim p^{1/2}$ remains open. We refer the reader to [7, 8] for some relevant results. To prove such an estimate, a common method is to bound the multiplicative energy $E(A)$ of $A,$ defined as the number of solutions to the equation

a_{1}a_{2}=a_{3}a_{4},\ a_{1},a_{2},a_{3},a_{4}\in A.

By Freiman’s theorem, this reduces to bounding the multiplicative energy of GAPs in $\mathbb{F}_{p}.$ Better bounds on the multiplicative energy also have many applications in number theory. For example, Chang [1] used a nontrivial estimate for the multiplicative energy to give a Burgess-type bound for character sums over proper GAPs. Following a similar approach Hanson [4] generalized this to character sums over regular Bohr sets. In fact, if one can prove the optimal bound

E(B)\ll|B|^{2+o(1)}

for any proper GAP $B\subset\mathbb{F}_{p},$ then for any nonprincipal Dirichlet character $\chi$ of $\mathbb{F}_{p},$ Burgess’s bound can be fully generalized to

\sum_{n\in B}\chi(n)=O(p^{-\delta}|B|)

whenever $|B|\geq p^{1/4+\epsilon}.$ With current techniques one can prove near-optimal bounds on the multiplicative energy of GAPs with some extra structure. For example, Kerr [5] proved the following result:

Theorem 1 (Kerr).

Let $P\subset\mathbb{F}_{p}$ be a GAP given by

P=x_{0}+\{\sum_{i=1}^{d}a_{i}x_{i}:a_{i}\in[1,N]\}

and suppose

P^{\prime}=\{\sum_{i=1}^{d}a_{i}x_{i}:|a_{i}|\leq N^{2}\}

is proper. Then $E(P)\ll|P|^{2}(\log N)^{2d+1}.$

The above discussion suggests that we can only hope for some mild multiplicative structure in a GAP or Bohr set. Let’s consider

B=\{a+bt:|a|,|b|\leq N\},

which is a symmetric GAP. Assume $t$ satisfies a quadratic polynomial equation mod $p$

c_{0}+c_{1}t+t^{2}=0

with $c_{i}\in\mathbb{Z}$ bounded by some constant $C$ independent of $p$ . Let $A=\{a^{\prime}+b^{\prime}t:|a^{\prime}|,|b^{\prime}|\leq\frac{1}{2C}N^{1/2}\},$ then obviously $A$ satisfies the condition of Kerr’s theorem. As a result $E(A)$ is small and $A$ does not possess a rich multiplicative structure. On the other hand, it’s easy to check that $AA\subset B.$ This set $B$ gives us an example of a GAP with some mild multiplicative properties, i.e. containing a large product set. It raises the following question: if a GAP $B$ contains a product set $AA$ with $|B|^{1/2}\ll|A|\ll|B|^{1/2}$ and $A$ also a GAP, what can we say about $B$ ? In this paper we show that under some natural assumptions on $A$ and $B,$ the generators of $B$ must be given by the roots of some low-height, low-degree polynomials.

Notations. For any element $x\in\mathbb{F}_{p},$ we define its integer height

|x|=\min{\{|a|:a\in\mathbb{Z},\ a\equiv x\pmod{p}\}}.

For a polynomial $f\in\mathbb{Z}[x],$ let ${\overline{f}}(x)$ denote the projection of $f(x)$ into ${\mathbb{F}}_{p}[x]$ , let $H(f)$ denote the height of $f,$ which is the maximum of the absolute value of coefficients of $f$ . We use $M_{n}(\mathbb{F}_{p})$ to denote the ring of $n\times n$ matrices over $\mathbb{F}_{p}.$

For any $x>0,$ let $[x]=\{1,2,\ldots,\lfloor x\rfloor\},$ where $\lfloor x\rfloor$ denote the integer part of $x.$

Given $x\in\mathbb{F}_{p},A\subset\mathbb{F}_{p},$ we write the dilation of $A$ by $x$ as $x\cdot A=\{xa:a\in A\}.$

For any $n\in\mathbb{N},A\subset\mathbb{F}_{p},$ we write the iterated sumset as

\begin{matrix}nA=\underbrace{A+A+\cdots+A}\\ \hskip 25.60747ptn\end{matrix}

2. Main Results

We first consider a simple case, namely a proper GAP $B$ of rank $2$ and size at most $o(p^{2/3})$ . We show that if $B$ contains the product set of a sub-GAP $A$ of size $|A|\approx|B|^{1/2}$ , then the generators of $B$ must be “algebraic” in the sense that they are the roots of some low-height quadratic polynomials.

Theorem 2.

Let $0<c<1,N=N(p)\in\mathbb{N}$ with $\lim_{p\to\infty}N(p)=\infty$ , $N=o(p^{1/3})$ , $B=\{a+bt:|a|,|b|\leq N\}\subset\mathbb{F}_{p}$ be proper and $|B|=o(p^{2/3}).$ Suppose $A=\{a^{\prime}+b^{\prime}t:|a^{\prime}|,|b^{\prime}|\leq cN^{1/2}\}$ satisfies $AA\subset B.$ Then there is a constant $C$ depending only on $c$ so that when $p$ is sufficiently large, there exists some quadratic polynomial $f\in\mathbb{Z}[x]\setminus\{0\}$ with $H(f)\leq C$ and $\overline{f}(t)=0$ in ${\mathbb{F}}_{p}$ .

Proof.

Since $t^{2}\in AA\subset B,$ we have

(1)

t^{2}=a_{0}+b_{0}t

for some $|a_{0}|,|b_{0}|\leq N.$ We claim that for any integer $m,n$ with $|m|,|n|\leq 5N,$ $m-nt\neq 0$ in $\mathbb{F}_{p}.$ Suppose for contradiction there exists $|m_{0}|,|n_{0}|\leq 5N$ so that $m_{0}-n_{0}t=0.$ Without loss of generality we may assume ${\rm gcd}(m_{0},n_{0})=1.$ Then (1) implies

(\frac{m_{0}}{n_{0}})^{2}=a_{0}+\frac{b_{0}m_{0}}{n_{0}}

and hence

(2)

m_{0}^{2}=a_{0}n_{0}^{2}+b_{0}m_{0}n_{0}\ \text{in}\ \mathbb{F}_{p}.

By assumption $|B|=(2N+1)^{2}=o(p^{2/3}),$ when $p$ is sufficiently large we get

m_{0}^{2}<\frac{p}{2},\ |an_{0}^{2}+bm_{0}n_{0}|<\frac{p}{2}.

Thus (2) holds not only in $\mathbb{F}_{p}$ but also in $\mathbb{Z}.$ This implies $n_{0}\mid m_{0}^{2}$ and hence $|n_{0}|=1,m_{0}\equiv\pm t\pmod{p}$ . From the fact that $B$ is proper we also know $|m_{0}|\geq|t|\geq N+1,$ therefore

m_{0}^{2}\pm b_{0}m_{0}\geq N+1>a_{0},

which is a contradiction to (2). This finishes the proof of the claim.

Now since $\lambda t^{2}\in B$ for any $\lambda\in\Pi:=\{uv\ :\ |u|,|v|\leq cN^{1/2}\},$ consider

\{(\lambda+\mu)t^{2}:\lambda,\mu\in\Pi\}.

This set will include $wt^{2}$ for any integer $|w|<c^{2}N/2.$ (To see this, take $b=\lfloor cN^{1/2}\rfloor$ and then consider the base- $b$ expansion of all positive integers $\leq c^{2}N/2$ , and note that such integers can be written as $ab+1\cdot r$ , where $0\leq a\leq cN^{1/2}$ and $0\leq r\leq cN^{1/2}$ .) Suppose $\max(|a_{0}|,|b_{0}|)\geq\frac{8}{c^{2}},$ let

w=\left\lfloor\frac{2N+1}{\max(|a_{0}|,|b_{0}|)}\right\rfloor+1,

it is easy to check that $w<c^{2}N/2$ when $p$ is large, hence $wt^{2}\in 2B.$ On the other hand, $2N<\max(|wa_{0}|,|wb_{0}|)\leq 3N$ . From the claim we know

wt^{2}=wa_{0}+wb_{0}t\notin 2B,

a contradiction. Hence $\max(|a_{0}|,|b_{0}|)\leq\frac{8}{c^{2}}$ and equation (1) gives the polynomial we want. ∎

The proof strongly depends on the property that enlarging $B$ by some constant will still give us a proper GAP. We do not know if it remains true for $|B|\geq p^{2/3}$ . This motivates us to define a special class of GAPs.

Definition 1.

A generalized arithmetic progression $B=x_{0}+\{\sum_{i=1}^{d}a_{i}x_{i}:a_{i}\in[0,N_{i}-1]\}$ is called $\kappa$ -isolated if there is no nonzero $(a_{1},...,a_{d})\in{\mathbb{Z}}^{d}$ with $|a_{i}|\leq\kappa N_{i}$ , for all $i=1,...,d$ , such that $\sum_{i}a_{i}x_{i}=0.$

Working with isolated GAPs we are able to generalize Theorem 2 to arbitrary rank and product set of two different GAPs. Our main result is the following:

Theorem 3.

Let $0<c,c^{\prime},\epsilon<1,d\in\mathbb{N},N=N(p)\in\mathbb{N}$ with $\lim_{p\to\infty}N(p)=\infty$ ,

B=\{\sum_{i=1}^{d}a_{i}x_{i}:|a_{i}|\leq N\}\subset\mathbb{F}_{p}

be $6$ -isolated with $x_{1}=1.$ Suppose there exist proper GAPs

A=\{\sum_{i=1}^{d}a_{i}y_{i}:|a_{i}|\leq cN^{1-\epsilon}\},\ A^{\prime}=\{\sum_{i=1}^{d}a_{i}y_{i}^{\prime}:|a_{i}|\leq c^{\prime}N^{\epsilon}\}

such that $AA^{\prime}\subset B.$ Then there is a constant $C=C(c,c^{\prime},d)$ so that when $p$ is sufficiently large, for any $i\in[d],$ there exists some polynomial $f_{i}\in\mathbb{Z}[x]\setminus\{0\}$ of degree at most $d$ with $H(f_{i})\leq C$ and $\overline{f}_{i}(x_{i})=0$ in ${\mathbb{F}}_{p}$ .

To prove Theorem 3, we need the following lemma from linear algebra.

Lemma 4.

Let $T=(t_{ij})\in M_{d}(\mathbb{F}_{p})$ . Suppose there exists $C\geq 1$ so that $|t_{ij}|\leq C$ and $T$ is not invertible. Then there exists a nonzero vector $(a_{1},a_{2},\ldots,a_{d})\in\mathbb{F}_{p}^{d}$ with $|a_{i}|\leq d!C^{d}$ such that

(a_{1},a_{2},\cdots,a_{d})T=0.

Proof.

Let

\vec{v_{i}}=(t_{i1},t_{i2},\ldots,t_{id})\in\mathbb{F}_{p}^{d}

be the $i$ th row vector of $T.$ If $\vec{v_{i}}=0$ for some $i,$ we can take $a_{i}=1$ and $a_{j}=0$ for $j\neq i.$ Hence we may assume $\vec{v_{i}}\neq 0$ for all $i.$ Without loss of generality, assume $\{\vec{v_{1}},\ldots,\vec{v_{k}}\}$ forms a maximal linearly independent set, since $T$ is not invertible we must have $k<d.$ Let $T^{\prime}\in M_{k}(\mathbb{F}_{p})$ be a submatrix of $T$ using the first $k$ rows so that ${\rm rank}(T^{\prime})=k.$ Suppose the columns of $T^{\prime}$ correspond to the $j_{1}<j_{2}<\cdots<j_{k}$ th columns of $T,$ let

\vec{u}_{i}=(t_{ij_{1}},t_{ij_{2}},\ldots,t_{ij_{k}})\in\mathbb{F}_{p}^{k},

We claim that $\vec{u}_{(k+1)}\neq 0.$ Indeed, by our choice of $\{v_{i}\}$ , there exists a linear combination

\vec{v}_{(k+1)}=\sum_{i=1}^{k}b_{i}\vec{v}_{i},

where the $b_{i}$ ’s are not all zero since $\vec{v}_{k+1}\neq 0.$ This implies

\vec{u}_{(k+1)}=\sum_{i=1}^{k}b_{i}\vec{u}_{i}

and hence $\vec{u}_{k+1}\neq 0.$

Now by adding the $(k+1)$ th row and another column to $T^{\prime},$ we obtain a matrix $T^{\prime\prime}\in M_{k+1}(\mathbb{F}_{p})$ with ${\rm rank}(T^{\prime\prime})=k$ and all the row vectors of $T^{\prime\prime}$ are nonzero. It follows that the adjugate matrix ${\rm adj}(T^{\prime\prime})$ ¹¹1Which is the $(k+1)\times(k+1)$ matrix such that ${\rm adj}(T^{\prime\prime})\cdot T^{\prime\prime}={\rm det}(T^{\prime\prime})I_{k+1}$ , where $I_{k+1}$ is the $(k+1)\times(k+1)$ identity matrix. of $T^{\prime\prime}$ has the $(k+1)$ th row $(a_{1},a_{2},\ldots,a_{k+1})$ with $a_{k+1}\neq 0$ . Since ${\rm det}(T^{\prime\prime})=0$ , we get

\sum_{i=1}^{k+1}a_{i}\vec{u}_{i}=0.

From the fact that $\{\vec{v}_{1},\vec{v}_{2},\ldots,\vec{v}_{k}\}$ forms a maximal linearly independent set we can deduce

\sum_{i=1}^{k+1}a_{i}\vec{v}_{i}=0.

Set $a_{i}=0$ for all $i>k+1$ , since each entry of ${\rm adj}(T^{\prime\prime})$ is the determinant of some submatrix of $T^{\prime\prime},$ it follows that $|a_{i}|\leq d!C^{d}.$ This gives us a nonzero vector $(a_{1},\ldots,a_{d})\in\mathbb{F}_{p}^{d}$ so that

(a_{1},a_{2},\cdots,a_{d})T=\sum_{i=1}^{d}a_{i}\vec{v}_{i}=0.

∎

Proof of Theorem 3.

For any $i,j\in[d],$

(3)

y_{i}y_{j}^{\prime}=\sum_{k}a_{ij}^{(k)}x_{k},\ {\rm where\ }|a_{i,j}^{(k)}|\leq N.

Now since $\lambda y_{i}y_{j}^{\prime}\in B$ for any $\lambda\in\Pi:=\{uv\ :\ |u|\leq cN^{1-\epsilon},\ |v|\leq c^{\prime}N^{\epsilon}\}$ , consider

\{(\lambda+\mu)y_{i}y_{j}^{\prime}\ :\ \lambda,\mu\in\Pi\},

As in the proof of Theorem 2, this set will include $wy_{i}y_{j}^{\prime}$ for any $|w|<c^{\prime\prime}N,$ where $0<c^{\prime\prime}<1$ is some constant depending on $c$ and $c^{\prime}.$ This implies that

wy_{i}y_{j}^{\prime}\in AA^{\prime}+AA^{\prime}\subset 2B

for any $|w|<c^{\prime\prime}N.$ Therefore we have

w\sum_{k}a_{ij}^{(k)}x_{k}=\sum_{k}b_{w}^{(k)}x_{k}

where $|b_{w}^{(k)}|\leq 2N.$ If

\max\{|a_{ij}^{(k)}|:k\in[d]\}\geq\frac{3}{c^{\prime\prime}},

then for some $|w|<c^{\prime\prime}N$ we would have

2N<\max\{|wa_{ij}^{(k)}|:k\in[d]\}\leq 4N,

contradicts with $B$ being $6$ -isolated. Hence

(4)

\max\{|a_{ij}^{(k)}|:k\in[d]\}<\frac{3}{c^{\prime\prime}}.

Now fix some $i\in[d],$ and let $\vec{v}=(x_{1},x_{2},\ldots,x_{d})^{T}$ , $\vec{u^{\prime}}=(y_{1}^{\prime},y_{2}^{\prime},\ldots,y_{d}^{\prime})^{T}\in\mathbb{F}_{p}^{d}$ . Also, let $T\in M_{d}(\mathbb{F}_{p})$ be the matrix whose entry in the $j$ th row and $k$ th column is

T_{j,k}\ =\ a_{ij}^{(k)}

so that (3) becomes

(5)

T\vec{v}\ =\ y_{i}\vec{u^{\prime}}.

From (4) it follows that all the entries of the adjugate matrix ${\rm adj}(T)$ are bounded by

C=(d-1)!3^{d-1}/(c^{\prime\prime})^{d-1}.

Moreover, $T$ must be invertible since otherwise from Lemma 4, there exists a nonzero vector $(a_{1},a_{2},\ldots,a_{d})\in\mathbb{F}_{p}^{d}$ with $|a_{i}|$ bounded by some constant depending on $c^{\prime\prime}$ and

(a_{1},a_{2},\ldots,a_{d})T=0.

Combining this with (5) gives us

y_{i}\cdot\sum_{j=1}^{d}a_{j}y_{j}^{\prime}=(a_{1},a_{2},\ldots,a_{d})T\vec{v}=0,

which would imply that $A^{\prime}$ is not proper, a contradiction.

Multiplying (5) by ${\rm adj}(T)$ on the left on both sides we get

{\rm det}(T)\vec{v}\ =\ y_{i}\cdot{\rm adj}(T)\vec{u^{\prime}}.

Taking linear combinations of coordinates on both sides (using coefficients $b_{j}$ ), we can deduce

A_{1}:=\{{\rm det}(T)\sum_{j}b_{j}x_{j}:|b_{j}|<\frac{c^{\prime}}{C}N^{\epsilon}\}\subset y_{i}\cdot A^{\prime}.

Let $\vec{u}=(y_{1},y_{2},\ldots,y_{d})^{T}$ . As before, we define a matrix $T^{\prime}\in M_{d}(\mathbb{F}_{p})$ where the entry in the $j$ th row, $k$ th column is

T^{\prime}_{j,k}\ =\ a_{ji}^{(k)}.

Again (3) becomes

(6)

T^{\prime}\vec{v}\ =\ \vec{u}y_{i}^{\prime},

and from (4), all the entries of ${\rm adj}(T^{\prime})$ are bounded by $C$ . Using the same argument that we did earlier for the matrix $T$ , we can deduce that $T^{\prime}$ is also invertible since $A$ is proper. Multiplying both sides of (6) on the left by ${\rm adj}(T^{\prime})$ we get

A_{2}:=\{{\rm det}(T^{\prime})\sum_{j}b_{j}x_{j}:|b_{j}|<\frac{c}{C}N^{1-\epsilon}\}\subset A\cdot y_{i}^{\prime}.

Hence

A_{1}A_{2}\subset y_{i}\cdot(A^{\prime}A)\cdot y_{i}^{\prime}\subset y_{i}By_{i}^{\prime}.

Now for any $j,k\in[d],$ we have

{\rm det}(T){\rm det}(T^{\prime})x_{j}x_{k}\ =\ y_{i}\left(\sum_{l=1}^{d}s_{jk}^{(l)}x_{l}\right)y_{i}^{\prime}

and the set

\{{\rm det}(T){\rm det}(T^{\prime})wx_{j}x_{k}:|w|<\frac{cc^{\prime}}{C^{2}}N\}

will be a subset of $y_{i}(2B)y_{i}^{\prime}$ from the same argument as the one at the beginning of our proof. Again from the fact that $B$ is $6$ -isolated we would have

\max\{|s_{jk}^{(l)}|:l\in[d]\}<C^{\prime}

for some $C^{\prime}=C^{\prime}(c,c^{\prime},d)$ . Thus there exists $T_{j}\in M_{d}(\mathbb{F}_{p})$ whose entries are bounded by $C^{\prime}$ so that

{\rm det}(T){\rm det}(T^{\prime})x_{j}\vec{v}\ =y_{i}(T_{j}\vec{v})y_{i}^{\prime}.

This equality implies that for any $j\in[d]$ , ${\rm det}(T){\rm det}(T^{\prime})x_{j}/(y_{i}y_{i}^{\prime})$ is an eigenvalue of $T_{j}$ , hence is the root of the characteristic polynomial of $T_{j},$ which has degree $d$ and height bounded by some constant depending on $C^{\prime}.$ From Lemma 4 and the fact that $B$ is proper, $T_{1}$ must be invertible. Notice that all these eigenvalues share the same eigenvector $\vec{v},$ thus

({\rm adj}(T_{1})T_{j})\vec{v}={\rm det}(T_{1})T_{1}^{-1}T_{j}\vec{v}={\rm det}(T_{1})\frac{x_{j}}{x_{1}}\vec{v}={\rm det}(T_{1})x_{j}\vec{v}.

This shows that ${\rm det}(T_{1})x_{j}$ is the root of the characteristic polynomial of ${\rm adj}(T_{1})T_{j},$ hence $x_{j}$ is the root of some polynomial of degree at most $d$ with bounded height. ∎

Remark 1.

The same proof works for non-symmetric GAP $B$ under slightly stronger conditions. Consider $B-B,$ which is a symmetric GAP, and assume the two symmetric GAPs $A-A$ and $A^{\prime}-A^{\prime}$ are proper, then $AA^{\prime}\subset B$ implies that $(A-A)(A^{\prime}-A^{\prime})\subset 2(B-B).$ If $B$ is $24$ -isolated, then $2(B-B)$ is $6$ -isolated and we can repeat the proof for $2(B-B),A-A$ and $A^{\prime}-A^{\prime}.$

Remark 2.

If we remove the condition that $x_{1}=1,$ we can only prove that the ratio $x_{i}/x_{j}$ of any two generators $x_{i},x_{j}$ satisfies a low-height, low-degree polynomial equation. This is what we expect since the condition $AA^{\prime}\subset B$ is not invariant under dilation in general.

Since the conclusion of Theorem 3 is about roots of polynomials, which also make sense in the non-commutative ring $M_{n}(\mathbb{F}_{p})$ , a natural question is if we consider GAPs in $M_{n}(\mathbb{F}_{p}),$ can we get a result similar to Theorem 3? It turns out that under some extra conditions, we can modify the proof of Theorem 3 to get the following:

Corollary 5.

Let $0<c,c^{\prime},\epsilon<1,n,d\in\mathbb{N},N=N(p)\in\mathbb{N}$ with $\lim_{p\to\infty}N(p)=\infty$ ,

B=\{\sum_{i=1}^{d}a_{i}X_{i}:|a_{i}|\leq N\}\subset M_{n}(\mathbb{F}_{p})

be $6$ -isolated with $X_{1}=I_{n}.$ Suppose there exist proper GAPs

A=\{\sum_{i=1}^{d}a_{i}Y_{i}:|a_{i}|\leq cN^{1-\epsilon}\},\ A^{\prime}=\{\sum_{i=1}^{d}a_{i}Y_{i}^{\prime}:|a_{i}|\leq c^{\prime}N^{\epsilon}\}

such that $AA^{\prime}\subset B,A^{\prime}A\subset B.$ Moreover, assume $Y_{i},Y_{j}^{\prime}$ are invertible for some $i,j\in[d]$ . Then there is a constant $C=C(c,c^{\prime},d)$ so that when $p$ is sufficiently large, for any $k\in[d],$ there exists some polynomial $f_{k}\in\mathbb{Z}[x]\setminus\{0\}$ of degree at most $d$ with $H(f_{k})\leq C$ and $\overline{f}_{k}(X_{k})=0$ in $M_{n}(\mathbb{F}_{p})$ .

Proof.

Replacing $x_{i},y_{i},y_{i}^{\prime}$ by $X_{i},Y_{i},Y_{i}^{\prime}$ in the proof of Theorem 3, in the same way we obtain

A_{1}\subset Y_{i}\cdot A^{\prime},\ A_{2}\subset A\cdot Y_{j}^{\prime}.

By assumption $A^{\prime}A\subset B,$ it follows that

A_{1}A_{2}\subset Y_{i}\cdot B\cdot Y_{j}^{\prime}.

Now for any $k\in[d],$ there exists $T_{k}\in M_{d}(\mathbb{F}_{p})$ with bounded entries so that

{\rm det}(T){\rm det}(T^{\prime})X_{k}\vec{v}\ =Y_{i}(T_{k}\vec{v})Y_{j}^{\prime}.

Since $X_{1}=I_{n},$ $Y_{i},Y_{j}^{\prime}$ are invertible, by Lemma 4 and the fact that $B$ is proper, we conclude that $T_{1}$ must be invertible. Moreover,

T_{k}\vec{v}\ ={\rm det}(T){\rm det}(T^{\prime})Y_{i}^{-1}X_{k}\vec{v}(Y_{j}^{\prime})^{-1},\ {\rm det}(T){\rm det}(T^{\prime})T_{1}^{-1}\vec{v}\ =Y_{i}\vec{v}Y_{j}^{\prime}.

Therefore

({\rm adj}(T_{1})T_{k})\vec{v}={\rm det}(T_{1})T_{1}^{-1}T_{k}\vec{v}={\rm det}(T_{1})Y_{i}^{-1}X_{k}Y_{i}\vec{v}.

Let $f_{k}(x)\in\mathbb{Z}[x]$ be the characteristic polynomial of ${\rm adj}(T_{1})T_{k},$ then by Cayley-Hamilton’s theorem

\overline{f}_{k}({\rm det}(T_{1})Y_{i}^{-1}X_{k}Y_{i})\vec{v}=\overline{f}_{k}({\rm adj}(T_{1})T_{k})\vec{v}=0.

In particular, using the fact $X_{1}=I_{n}$ we can deduce

Y_{i}^{-1}\overline{f}_{k}({\rm det}(T_{1})X_{k})Y_{i}=\overline{f}_{k}({\rm det}(T_{1})Y_{i}^{-1}X_{k}Y_{i})=0,

which implies

\overline{f}_{k}({\rm det}(T_{1})X_{k})=0.

∎

3. Open questions

A natural question is can we weaken the condition on $B$ or $A$ to get the same result as in Theorem 3. A simple example shows that if we remove the isolated condition on $B$ and allow $A$ to be some arbitrary set with $|A|\approx|B|^{1/2}$ , then the conclusion of Theorem 3 is no longer true. Let $B=\{a+bN:a,b\in[0,N-1]\}=[0,N^{2}-1],$ which is a degenerate rank- $2$ GAP. We can take $A=[0,N-1]$ so that $AA\subset B$ and $|A|\approx|B|^{1/2}.$ By choosing $N$ to be about $p^{1/4}$ so that it’s not the root of a low-height, low-degree polynomial, we’ve got a counterexample. From the argument of Theorem 2 we guess the isolated condition could probably be replaced by some restriction on the size of $B.$

One can also consider unbalanced GAPs. Suppose

B=\{\sum_{i=1}^{d}a_{i}x_{i}:|a_{i}|\leq N_{i}\}\subset\mathbb{F}_{p}

and

A=\{\sum_{i=1}^{d}a_{i}y_{i}:|a_{i}|\leq cM_{i}\},\ A^{\prime}=\{\sum_{i=1}^{d}a_{i}y_{i}^{\prime}:|a_{i}|\leq c^{\prime}M_{i}^{\prime}\}

with $|A||A^{\prime}|\approx|B|.$ If we make no restriction on the $N_{i}$ ’s, then there is no hope to obtain the same result. For example, $B$ can be constructed with $N_{i}=1$ for some $i,$ and the corresponding $x_{i}$ is not the root of some low-height, low-degree polynomial. The question is whether the conclusion of Theorem 3 remains true if we assume

\lim_{p\rightarrow\infty}N_{i}=\lim_{p\rightarrow\infty}M_{i}=\lim_{p\rightarrow\infty}M_{i}^{\prime}=\infty

for each $i\in[d]$ to rule out the extreme case.

References

[1] M.-C. Chang. On a question of Davenport and Lewis and new character sum bounds in finite fields. Duke Math. J., 145(3):409–442, 2008.
[2] G. Elekes and I. Z. Ruzsa. Few sums, many products. Studia Sci. Math. Hungar., 40(3):301–308, 2003.
[3] P. Erdős and E. Szemerédi. On sums and products of integers. In Studies in pure mathematics, pages 213–218. Birkhäuser, Basel, 1983.
[4] B. Hanson. Character sums over Bohr sets. Canad. Math. Bull., 58(4):774–786, 2015.
[5] B. Kerr. Some multiplicative equations in finite fields. Finite Fields Appl., 75:Paper No. 101883, 28, 2021.
[6] B. Kerr, J. Mello, and I. E. Shparlinski. An effective local-global principle and additive combinatorics in finite fields. J. Anal. Math., 152(1):109–135, 2024.
[7] A. Mohammadi and S. Stevens. Attaining the exponent 5/4 for the sum-product problem in finite fields. Int. Math. Res. Not. IMRN, (4):3516–3532, 2023.
[8] M. Rudnev, G. Shakan, and I. D. Shkredov. Stronger sum-product inequalities for small sets. Proc. Amer. Math. Soc., 148(4):1467–1479, 2020.
[9] T. Tao and V. Vu. Additive combinatorics, volume 105 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 2006.