## Constructing expanders in Z/pZ

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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.

-

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

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.

-

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
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 18, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9452728629112244, "perplexity_flag": "middle"}