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.


1 Answer 1


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.

  • $\begingroup$ Could you expand just a little? (Pardon the pun :-) $\endgroup$
    – Nick Gill
    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
    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
    Jan 31, 2013 at 13:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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