7
$\begingroup$

Fix a positive integer $k>0$. For $p>k$ a prime, let $A_p$ be a subset of the finite field $\mathbb{Z}/p\mathbb{Z}$ of size $k$ which contains a primitive element.

Define $G_p$ to be the (di)graph whose vertices are elements of $\mathbb{Z}/p\mathbb{Z}$, with two vertices $i,j$ joined by an edge provided $j=ia$ or $j=i+a$ for some $a\in A_p$.

(I'm mainly interested in the situation where $A_p$ is closed under the operations of taking multiplicative and additive inverses; under these assumptions I can think of $G_p$ as a graph rather than a digraph.)

Question: Is $(G_p)_{p \textrm{ a prime}}$ a family of expanders?

Background: I'm expecting the answer to be either "possibly" or "no" (because if it were "yes" I'd hope I'd have heard about it already).

My interest comes in studying the Bourgain-Gamburd machinery for proving expansion from results about growth. For the family $(G_p)$, the relevant growth result is the Bourgain-Katz-Tao sum-product theorem for fields of prime order.

One needs more than just a growth result of course, one also needs to have some notion of `quasirandomness' (but I think I can handle this), as well as a lower bound on the girth of the graph. I've not thought much about this last aspect so I guess this is the most likely to be the sticking point.

Improve this question
$\endgroup$
6
  • $\begingroup$ Not an answer, but certainly related is Problem 7.9 from math.haifa.ac.il/~seva/Papers/montpr.dvi . $\endgroup$
    – Seva
    Commented Jan 29, 2013 at 17:07
  • $\begingroup$ Is $A$ the same as $A_p$? $\endgroup$
    – Gerry Myerson
    Commented Jan 29, 2013 at 22:38
  • $\begingroup$ @Gerry: yes! Will edit... $\endgroup$
    – Nick Gill
    Commented Jan 30, 2013 at 13:27
  • $\begingroup$ @Seva, the problem you refer to is very interesting. $\endgroup$
    – Nick Gill
    Commented Jan 30, 2013 at 13:32
  • $\begingroup$ This is basically a duplicate of mathoverflow.net/questions/91657/… $\endgroup$
    – Terry Tao
    Commented Jan 30, 2013 at 17:58

1 Answer 1

Reset to default
2
$\begingroup$

No, because solvable groups are amenable. You're asking: Is is there a set in Z/pZ almost invariant by x->x+1 and 2x? Here's one: take the union of I, I/2, .., I/2^n, where I is an interval of length much bigger than 2^n.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Could you expand just a little? (Pardon the pun :-) $\endgroup$
    – Nick Gill
    Commented Jan 30, 2013 at 17:15
  • $\begingroup$ To my understanding, applied to the Problem 7.9 mentioned in my comment above, this explains why $\lambda=O(1)$ does not work - but does not solve the problem in its full generality. Is this correct? $\endgroup$
    – Seva
    Commented Jan 30, 2013 at 18:27
  • $\begingroup$ The link by Tao gives a more complete answer to my question. It is in the same direction as this answer, so I'm accepting it. $\endgroup$
    – Nick Gill
    Commented Jan 31, 2013 at 13:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .