7

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.

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

1 Answer

2

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.

link|flag
Could you expand just a little? (Pardon the pun :-) – Nick Gill Jan 30 at 17:15
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? – Seva Jan 30 at 18:27
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. – Nick Gill Jan 31 at 13:48

Your Answer

Get an OpenID
or

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