Having received several exhausting answers to [my recent question](https://mathoverflow.net/questions/124708/an-expander-graph) about
the expansion properties of a certain graph, I now wonder whether anything is
known on the following graphs of a similar nature:


1) The graph on ${\rm GF}(p)$ with $z$ adjacent to $-z$ and also to $gz$,
where $g$ is a fixed primitive root mod $p$.


2) The graph on ${\rm GF}(2^n)$ with $z$ adjacent to $z+e$ and also to $gz$,
where $e$ is a fixed non-zero element, and $g$ is a generating element of
${\rm GF}(2^n)$.


3) The graph on $({\mathbb Z}/2^n{\mathbb Z})^\times$ (odd residue classes
mod $2^n$) with $z$ adjacent to $z^{-1}$ and also to $z+2$.


Are these (families of) graphs known to be good expanders? Can one
investigate them using Selberg's 3/16-theorem or other "standard" tools
used to study the graph [my original question](https://mathoverflow.net/questions/124708/an-expander-graph) concerned with?



More expanders?
Freddie Manners is right: graphs (1) and (2) are not expanders
for any choice of $g$.
For (1), he already showed this by exhibiting large vertex sets with
$O(1)$ neighbors. For (2) we prove it below by contructing vectors $v$
orthogonal to the all-$1$ vector for which the Rayleigh quotient
$\langle Av, v \rangle / \langle v, v \rangle$
is within $o(1)$ (indeed $O(1/n)$) of the graph degree,
thus proving that there is no spectral gap.
Graph (3) is probably an expander,
because the maps taking $z$ to $z^{-1}$ and $z+2$
generate a congruence subgroup of index 3 in ${\rm PSL}\_2({\bf Z})$
(as Serre notes in the very last section of *A Course in Arithmetic*),
and the graph vertices can be identified with an orbit of cusps of a modular curve
of level $2^n$, so one should be able to use the $3/16$ bound on that curve;
but I'll leave that to the folks who actually know these techniques.


For (2): let $k$ be a finite field of $2^n$ elements, and consider the graph
where each $z$ is adjacent to $gz$ $-$ and thus also to $g^{-1} z$ $-$
and to $z+e$.
Fix a nontrivial homomorphism $\epsilon$ from $(k,+)$ to the group
$\lbrace\pm1\rbrace$; the usual choice is $\epsilon(x) = (-1)^{{\rm Tr}(x)}$.
Then for each $c \in k$ we have a homomorphism
$\epsilon\_c: (k,+) \rightarrow \lbrace\pm1\rbrace$ defined by
$\epsilon\_c(x) = \epsilon(cx)$,
and these $\epsilon\_c$ form an orthonormal basis for the Euclidean space of
real-valued functions on $k$ with inner product
$$
\langle f, g \rangle := \frac1{2^n} \sum\_{x\in k} f(x) g(x).
$$
So we're seeking a linear combination of the $\epsilon\_c$ with $c \neq 0$
that is almost fixed by the adjacency matrix $A$ in the sense that
$\langle Av, v \rangle / \langle v, v \rangle = 3 - O(1/n)$.


Write $A = A\_1+A\_2$
where $A\_1$ is induced by translation by $e$ 
and $A\_2$ is induced by multiplication by $g^{\pm 1}$.
Then for each $c \in k$ we have $A\_1 \epsilon\_c = \epsilon(ce) \epsilon\_c$
and $A\_2 \epsilon\_c = \epsilon\_{gc} + \epsilon\_{g^{-1}c}$.
We shall take $v = \sum\_{i=1}^{n-1} \epsilon\_{g^i c}$ for some $c\neq 0$,
so $\langle v, v \rangle = n-1$ and $\langle A\_2 v, v \rangle = 2n-4$.
We next show that $c$ can be chosen so that $v$
is an eigenvector of $A\_1$, corresponding to the eigenvalue $1$.
Because $\lbrace c : \epsilon(ce) = +1 \rbrace$ is a
$({\bf Z}/2{\bf Z})$-subspace of $k$ of codimension $1$,
the same is true of $\lbrace c : \epsilon(g^i ce) = +1 \rbrace$
for each $i$, so the intersection of these $n-1$ subspaces
has positive dimension. Choosing nonzero $c$ in this intersection
makes $A\_1 v = v$ as claimed. Then
$$
\langle A v, v \rangle =
\langle A\_1 v, v \rangle + \langle A\_2 v, v \rangle =
(n-1) + (2n-4) = 3n-5 = (3-O(1/n)) \langle v, v \rangle,
$$
**QED**.


**Exercise**: Adapt this technique to show that the graph on
${\bf Z} / p {\bf Z}$ where each $z$ is connected to
$z \pm 1$ and $g^{\pm 1} z$
is not an expander either for any $g \in ({\bf Z} / p {\bf Z})^\*$.
(That's what I first thought graph (1) was when I quickly read the question.)


