8
$\begingroup$

In the course of some recent research, I've sketched out a proof of the following result. My basis question is: is the result interesting?

Proposition There exists an absolute constant $c$ such that, if $A$ is any symmetric subset of a finite field $\mathbb{F}_q$ with $|A|\geq 2$, then there are elements $g_1,\dots, g_n\in \mathbb{F}_q$ with $$Ag_1+\cdots Ag_n = \mathbb{F}_q$$ and $n\leq c\log(q)/\log|A|$.

Please note that I haven't checked every detail of the proof! I think it works but you never know... I also haven't tried to optimise the constant $c$ but it seems like $34$ works. Finally, although I need the fact that $A$ is symmetric for my proof, I would imagine that the same bound holds without this (symmetric here means that $A=-A$).

When I say "is this interesting?" I mean, first, that I'd like to know whether this proposition is easy-peasy for any one with a modicum of knowledge in algebraic combinatorics and, if this is not the case, whether there might be any applications.

Background: I stumbled on this result while trying to prove a statement about width in finite simple groups. There is a famous conjecture in this area due to Liebeck, Nikolov and Shalev ("The Product Decomposition Conjecture") which says the following:

Conjecture: There exists an absolute constant $c$ such that if $G$ is a finite simple group and $S$ is a subset of $G$ of size at least two, then $G$ is a product of $n$ conjugates of $S$, and $n \leq c \log|G|/ \log |S|$.

The proposition I state at the top is basically the same statement but for the group $G=\mathbb{F}_q\rtimes\mathbb{F}_q^*$ (where we restrict $A$ to be in the normal subgroup $\mathbb{F}_q$).

One of the things that surprises me is that one (conjecturally) has a bound on the width of two families of groups that look completely different - i.e. finite simple groups, and $\mathbb{F}_q\rtimes\mathbb{F}_q^*$. Of course these families are also the settings in which the most famous growth statements have been proven (cf. work of Helfgott, Pyber, Szabo, Breuillard, Green, Tao, Bourgain, Katz and many others), so perhaps this is not surprising. Note, though, that the bounds connected to width (i.e. multiplication by conjugates) are much stronger than those given by growth so the connection between the two is not entirely obvious...

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ Note that if $|A| < q^{1/4}$ then there exists $g \in {\bf F}_q$ such that $|A + g A| = |A|^2$ (see Lemma 2.50 of my book with Van Vu). So the non-trivial content of this result is in the large set case $|A| \geq q^{1/4}$. $\endgroup$
    – Terry Tao
    Commented May 23, 2014 at 18:38
  • $\begingroup$ Actually, for the large set case, Exercise 2.8.4 of my book with Van should finish off the problem. $\endgroup$
    – Terry Tao
    Commented May 23, 2014 at 18:43
  • $\begingroup$ @Terry, Thanks for your comments. One query though - it's not quite enough to get $|A+gA|=|A|^2$ as this will only yield a bound that's polynomial in $\log|G|$, rather than linear. You need something more like $|B+gA|=|A|.|B|$ with $A$ and $B$ different sets, and this is harder isn't it? $\endgroup$
    – Nick Gill
    Commented May 23, 2014 at 19:24
  • $\begingroup$ In fact the method I used for large sets is pretty much the one that Terry describes. In the approach I used it was the small set case that was the non-trivial one. $\endgroup$
    – Nick Gill
    Commented May 23, 2014 at 19:33
  • 3
    $\begingroup$ if you iterate my first comment, you get $|g_1 A + \dots + g_{2^k} A| = |A|^{2^k}$ for some $g_1,\dots,g_{2^k}$ whenever $|A|^{2^{k-1}} < q^{1/4}$. This, together with the large set case, already proves what you want with a bound that is linear in $\log q / \log |A|$. $\endgroup$
    – Terry Tao
    Commented May 23, 2014 at 20:26

0

Reset to default

You must log in to answer this question.