Aleshin graphs are expanders

The automata and their level graphs

Malyshev and Pak proved that the diameters of the Aleshin and Bellaterra level graphs grow at most quadratically in the level [3 Theorem 1.1]. They conjectured that both families are two-sided expanders [3 Conjectures 1.2 and 1.3]. The connection between these questions is that uniform spectral expansion gives logarithmic diameter in the number of vertices. Here the number of vertices is $2^n$, so logarithmic diameter means linear growth in $n$. We prove the expansion transfer first and then give explicit linear diameter bounds in § 4. We note that Ramanujan graphs of valence $q + 1$ with $q$ an odd prime power, generated by automata, were constructed by Bondarenko, Grigorchuk and Vdovina in [1 Theorem 2].

Mealy automata and binary words

Let $X = \{0, 1\}$. The vertices of the rooted binary tree $X^*$ are the finite words in $X$, including the empty word, which is the root. The two children of a word $w$ are $w0$ and $w1$. The $n$th level is $V_n = X^n$, so $|V_n| = 2^n$.

A Mealy automaton consists of a finite set of states, an input alphabet, a next-state rule, and an output rule. Starting in a state $s$, it reads a word from left to right. At each step it outputs one letter and changes state according to the current state and the input letter. Thus a state defines a length-preserving map on words. If the output rule at each state permutes the alphabet, these maps are automorphisms of the rooted tree. In particular, they permute each finite level $V_n$.

For a rooted binary-tree automorphism $g$, the notation $g = (g_0, g_1)\pi$ means

Here $\pi$ is the permutation of the first letter, and $g_x$ is the section of $g$ at $x$, namely the action on the remaining word after the first letter $x$ has been read. Put $\sigma= (0\ 1)$. The displayed formulas below are called wreath recursions. They specify each automaton completely.

The Aleshin and Bellaterra automata

We use the Aleshin convention of Vorobets–Vorobets [4]:

The matching Bellaterra states are

For example, $a(0w)=1c(w)$ and $a(1w)=0b(w)$, whereas $\beta_a(0w)=0\beta_c(w)$ and $\beta_a(1w)=1\beta_b(w)$. The next-state rules agree, and the output letters are opposite. Figure 1 displays both automata. An arrow labelled $x/y$ means: read $x$, output $y$, and move to the state at the end of the arrow. Two labels on one arrow specify two transitions with the same next state.

As a short example of reading a word,

In each calculation the remaining input is processed from the state specified by the preceding transition.

The Bellaterra states are involutions. Indeed, their squares satisfy

All three squares fix the empty word. If they fix every word of length $n$, these recursions show that they fix every word of length $n+1$. Simultaneous induction proves $\beta_a^2=\beta_b^2=\beta_c^2=1$ on the whole rooted tree.

Level Schreier graphs and adjacency operators

The directed Aleshin level graph has an edge $w\longrightarrow s(w)$ for each $w\in V_n$ and $s\in\{a,b,c\}$. Its indegree and outdegree are three. Let $A_n$ denote its undirected version, retaining all labelled edges and their multiplicities. Equivalently, $A_n$ is the Schreier graph with the symmetric generating list

It is a degree-six multigraph. A loop contributes two to the degree; parallel edges are counted separately.

For a permutation $s$ of $V_n$, define its column permutation matrix by $P_s e_w=e_{s(w)}$, where $e_w$ is a standard basis vector. Thus $P_sP_t=P_{st}$ and $P_s^*=P_{s^{-1}}$, with $*$ denoting the conjugate transpose. Set

Here $K_n$ is the undirected adjacency matrix and $P_n$ is its normalized random-walk operator. We use the Euclidean inner product on $\mathbb{C}^{V_n}$ and write

The Bellaterra level graph $B_n$ has the same vertex set $V_n$ and one edge labelled $s$ from $w$ to $\beta_s(w)$ for each $s\in\{a,b,c\}$. Since the Bellaterra states are involutions, its adjacency matrix is symmetric:

A fixed point of a state contributes one to the corresponding diagonal entry. These fixed points are sometimes represented by half-loops; the matrix convention fixes their contribution unambiguously. Every row sum of $M_n$ is three. All labels and edge multiplicities are retained in both graph families.

Since $P_n$ is self-adjoint, this bounds the absolute value of every nonconstant normalized eigenvalue. In particular, it bounds the eigenvalues away from both $1$ and $-1$.

The exact Bellaterra comparison

Before comparing the operators, we explain what the states in this comparison represent. The names Aleshin and Bellaterra refer to the two specific three-state binary Mealy automata in Figure 1. Their states are denoted by

respectively. Each state specifies two instructions, one for input $0$ and one for input $1$: which letter to output and which state to use next. Choosing an initial state therefore determines how the automaton transforms an entire input word.

For example, starting the Aleshin automaton in state $a$ means that the first input letter is processed by the rule for $a$. After that step, the remaining letters are processed in the states specified by the transition rules. The notation $a(w)$ denotes the complete output word obtained in this way. Thus the same symbol $a$ denotes both an internal state and the transformation of binary words defined by using that state initially. The symbols $b$, $c$ and $\beta_a,\beta_b,\beta_c$ have the same interpretation.

These transformations preserve word length and the prefix relation. Since each state’s output rule permutes $\{0,1\}$, they are automorphisms of the rooted binary tree. They generate the groups

Products in these groups are compositions of transformations of whole words: $(ab)(w)=a(b(w))$ means first run the automaton from state $b$ on $w$, then run it from state $a$ on the resulting word. Restricting a state transformation to $V_n=\{0,1\}^{n}$ gives a permutation of the $2^n$ words at level $n$. We use the same symbol for this restriction when the level is clear.

The correspondence $a\leftrightarrow\beta_a$, $b\leftrightarrow\beta_b$, $c\leftrightarrow\beta_c$ can be read directly from the following transition table. Each pair in the third column gives the next Aleshin and Bellaterra states.

Current states	Input	Next states	Aleshin output	Bellaterra output
$a,\beta_a$	0	$c,\beta_c$	1	0
$a,\beta_a$	1	$b,\beta_b$	0	1
$b,\beta_b$	0	$b,\beta_b$	1	0
$b,\beta_b$	1	$c,\beta_c$	0	1
$c,\beta_c$	0	$a,\beta_a$	0	1
$c,\beta_c$	1	$a,\beta_a$	1	0

In every row, the next states are again a corresponding pair, and the two output letters are complementary. Consequently, when the automata start in corresponding states and read the same input word, they remain in corresponding states throughout the calculation. For instance, on input 0010 the Aleshin states used are $a,c,a,b$, and

The corresponding Bellaterra calculation is

The output words differ at every position.

The vertices of the level graphs are the input words. Applying a state transformation gives the endpoint of the edge with that label. Thus 0010 and 1001 are joined by an $a$-labelled directed Aleshin edge at level four, while the corresponding Bellaterra edge joins 0010 to 0110. The permutation matrix $P_s$ records the action of the Aleshin state $s$ by $P_s e_w=e_s(w)$; the matrix $P_{\beta_s}$ records the matching Bellaterra action. Here $e_w$ is the coordinate vector indexed by the word $w$. The next lemma expresses the complementary-output relation as an identity of permutations and then of matrices.

The comparison of states

Let $\delta_n$ complement every letter:

Then $D_n^*=D_n$, $D_n^2=I$, and $D_n$ fixes the constant vector.

Therefore

Proof. The two automata have the same state transition for each input letter. Their output letters are opposite for every state and input. Starting in matching states and reading the same word, they therefore follow the same sequence of states and output complementary words. This proves (2.1). To see the induction explicitly, for a word $w$ of length $n-1$ one has

The other states and input letters follow from the same recursions; the initial case is the empty word. The identity is also [4 Lemma 5.1]. The matrix identities follow from $P_{st}=P_sP_t$ and $M_n^*=M_n$, $D_n^*=D_n$.

General transfer of spectral gaps

The relation between the two automata transfers any two-sided Bellaterra spectral bound to the Aleshin graphs. We give the precise comparison. Write

Thus $R_n$ is the normalized Bellaterra adjacency operator, $Q_n$ describes the directed Aleshin walk, and $P_n$ describes the undirected Aleshin walk. The normalizations use the row sums 3 and 6 specified in the graph definitions.

We work on

For a permutation $s$, our convention $P_s e_v = e_{s(v)}$ gives

Every permutation matrix is unitary and preserves both constants and $H_n$, because permuting coordinates preserves their sum and their squared absolute values. In particular, these subspaces are preserved by the operators above and their adjoints.

Proof. Let $\delta_n$ complement every letter of a word in $V_n$. Lemma 2.1 gives $s = \delta_n\beta_s$. The Bellaterra states and $\delta_n$ are involutions. Hence

which proves (7). The identities are compatible with restriction to every finite level, so they hold on the rooted tree as well. Every product of two Bellaterra generators is thus a word of length at most two in the Aleshin generators and their inverses.

The involution properties give

Summing $P_s = D_nP_{\beta_s}$ and dividing by 3 proves $Q_n = D_nR_n$. Taking the adjoint gives $Q_n^* = R_nD_n$, and averaging these identities proves (8). Multiplication then gives (9). The first identity in (9) also follows directly from (7):

The singular values of an operator $T$ are the nonnegative square roots of the eigenvalues of $T^*T$. All the operators in (9) preserve $H_n$, so the identities hold on that subspace. Choose an orthonormal eigenbasis for the self-adjoint operator $R_n|_{H_n}$. For an eigenvector $f$ with eigenvalue $\lambda$,

The corresponding singular value is therefore $|\lambda|$, proving the assertion with multiplicities.

For the norm equality one can also argue directly. The unitarity of $D_n$ gives

Taking the supremum over unit vectors proves $\|Q_n|_{H_n}\|=\|R_n|_{H_n}\|$. An operator and its adjoint have the same norm. Since $H_n$ is preserved by both $Q_n$ and $Q_n^*$, the adjoint of the restriction is the restriction of the adjoint. This proves the remaining equality in (10).

For a self-adjoint normalized adjacency operator $T$, its two-sided spectral gap is

Thus a gap of at least $\varepsilon$ means that all eigenvalues on the orthogonal complement of the constant functions lie in $[-1+\varepsilon,1-\varepsilon]$. Both ends of the spectrum are controlled by this definition.

Proof. Put $\rho_n=\|R_n|_{H_n}\|$. For $f\in H_n$, the triangle inequality and Proposition 2.2 give

Taking the supremum over unit vectors proves (11), and subtracting from 1 proves (12).

There is also a useful proof directly in terms of the eigenvalues. By (8) and our inner-product convention,

Cauchy–Schwarz and the unitarity of $D_n$ yield

Substituting an eigenvector of the self-adjoint operator $P_n|_{H_n}$ shows that

If $\rho_n\leq1-\varepsilon$ uniformly, the same $\varepsilon$ therefore works for every Aleshin level. In unnormalized terms, a Bellaterra bound $|\lambda|\leq3-\eta$ gives the Aleshin bound $|\lambda|\leq6-2\eta$ on $H_n$.

Suppose the undirected Aleshin graph had a component $S$ with $0<|S|<|V_n|$. Then

would be a nonzero vector in $H_n$ with $P_nf=f$. This contradicts (14) when $\rho_n<1$, proving connectedness. If the graph were bipartite, the sign function $f$ equal to $1$ and $-1$ on the two parts would satisfy $P_nf=-f$. Self-adjointness and $P_n1=1$ imply

so $f\in H_n$, again contradicting (14).

Conjectures 1.3 and 1.2 of Malyshev–Pak [3] concern two-sided expansion of the Bellaterra and Aleshin graph families, respectively. In [3 Remark 11.3], they observe that the first implies the second by using products of two Bellaterra generators. Identity (7) describes those products explicitly, and Proposition 2.3 gives the quantitative implication. Their directed Aleshin graph records the three outgoing edges at each vertex; forgetting the directions, with multiplicities retained, gives the normalized operator $P_n$ used here. Their automaton convention is obtained from ours by interchanging 0 and 1 in both the input and output labels. This conjugates the level actions by $\delta_n$ and gives isomorphic labelled level graphs.

The two-sided hypothesis is essential to this general argument. For a self-adjoint $R_n$, the norm on $H_n$ is the maximum absolute value of its eigenvalues there; an upper bound on the largest eigenvalue alone does not control eigenvalues near $-1$. For example, on a two-point set let

The eigenvalue of $R|_H$ is $-1$, so its one-sided gap is 2. Nevertheless, $(DR+RD)/2=I$ has gap zero on $H$. This example shows why the general comparison requires a bound at the negative end of the spectrum as well.

The exact relation in (9) identifies singular values, and the eigenvalues themselves may differ. Already at level one,

Their eigenvalues on $H_1=\operatorname{span}\{(1,-1)\}$ are $1/3$ and $-1/3$, respectively, although both restricted norms are $1/3$.

The Bellaterra bound and Aleshin expansion

We now apply Proposition 2.3 using the Bellaterra spectral theorem from [2 Theorem 2.3].

Proof. Write $\gamma_a,\gamma_b,\gamma_c$ for the Bellaterra states in [2]. They satisfy

Conjugating the states in (2) by letter complementation interchanges the sections at 0 and 1 and leaves the first-letter permutation unchanged. Thus the conjugated states satisfy precisely these recursions. For example, if $w\in V_{n-1}$, then

The other transitions follow in the same way. Starting with the empty word, simultaneous induction on word length therefore gives

Our paper [2] uses the same edge-multiplicity and fixed-point conventions as (4). Its adjacency operator is consequently

Since $D_n$ is unitary and fixes the constant vector, it preserves $H_n$. The estimate in [2 Theorem 2.3] therefore yields

Finally, $2\sqrt{2}<3$ excludes an eigenvector of eigenvalue $3$ in $H_n$. The eigenvalue $3$ is simple, so $B_n$ is connected.

The general comparison in Proposition 2.3 uses only the automaton identities and elementary linear algebra. The particular constants in Theorem 2.5 use the Bellaterra estimate (15). We next derive the edge expansion and diameter bounds from these operators.

Edge expansion and the directed walk

For $S\subset V_n$, let $\partial S$ be the multiset of undirected edges with one endpoint in $S$ and one outside $S$. Count each such edge once, with its multiplicity; loops contribute nothing.

The graph Laplacian is $L_n = 6I - K_n$, and $L_n\mathbf{1} = 0$. The usual quadratic-form identity, valid with the stated multiplicity convention, gives

More generally, if $\|P_n|_{H_n}\| \le1-\varepsilon$, then $L_n = 6(I-P_n)$ gives

where the last step uses $s \le m/2$. By Theorem 2.5, we may take $\varepsilon= 1-2\sqrt{2}/3$. This gives the stated constant $3\varepsilon= 3-2\sqrt{2}$.

For completeness, the positive-generator directed walk also has a uniform contraction estimate. With our column convention, $Q_n = N_n/3$ acts on column probability distributions, while its adjoint acts on observables by

Both preserve the uniform distribution and the mean-zero subspace. Proposition 2.2 gives

Thus the directed walk contracts mean-zero vectors by the same uniform factor in a single step. For every integer $t \ge0$, submultiplicativity of the operator norm gives

This argument does not require $Q_n$ to be self-adjoint or diagonalizable. For instance, if $\mu$ is a probability column vector and $u = m^{-1}\mathbf{1}$, then

We use this contraction estimate for directed paths in the next section.

Linear diameter bounds for both families

The distance between two vertices of an undirected graph is the minimum number of edges in a path joining them. The diameter is the maximum of these distances. For a directed graph, paths must follow the orientations; the directed diameter is the maximum over ordered pairs of vertices. We write $\operatorname{diam}_{\mathrm{dir}}(A_n)$ for the directed Aleshin diameter, using only the transitions $a$, $b$, $c$.

Malyshev–Pak’s quadratic diameter bounds [3 Theorem 1.1] concern undirected distances. We obtain linear bounds for those distances and also for directed Aleshin distances. The argument for undirected graphs uses the following elementary polynomial estimate.

A polynomial bound for the diameter

The Chebyshev polynomials $T_j$ are defined by

They have degree $j$ and satisfy

These identities follow by induction from the corresponding addition formulas. In particular, $|T_j(x)|\le1$ when $-1\le x\le1$.

Proof. Set

The operator $R$ vanishes on constants. On $\mathbf{1}^{\perp}$, the spectrum of $P/\rho$ lies in $[-1,1]$. The spectral theorem and (20) therefore give $\lVert R\rVert\le1$.

For a vertex $v$, put $f_v=e_v-N^{-1}\mathbf{1}$. Then $\lVert f_v\rVert^2=1-N^{-1}$. Since $R$ vanishes on constants and is self-adjoint, the Cauchy–Schwarz inequality gives

Consequently

If $u,v$ had distance greater than $t$, every entry $(P^j)_{uv}$ with $0\le j\le t$ would be zero, because there is no walk of any such length joining them. As $T_t(P/\rho)$ is a polynomial in $P$ of degree $t$, its $uv$-entry would also be zero. This contradicts (22). Thus every pair of vertices has distance at most $t$.

The Bellaterra and undirected Aleshin bounds

Proof. For the two families, the symmetric normalized adjacency operators are

Equation (15) and Theorem 2.5 give the same bound for both operators:

There are $N = 2^n$ vertices. Since

the second identity in (20) gives

In particular,

Apply Lemma 4.1 with $t = 2n + 2$ to each operator.

Directed Aleshin paths

Lower bounds and the order of growth

Proof. In an undirected graph with at most $d \ge3$ neighbors at each vertex, a ball of radius $D$ contains at most

vertices: there are at most $d$ choices for the first step of a shortest path, and at most $d-1$ choices for each later step. Loops and multiple edges cannot increase the number of distinct vertices reached. For Bellaterra, $d=3$, so a graph of diameter $D$ has at most $3 \cdot2^{D}-2$ vertices. For undirected Aleshin, $d=6$, giving at most $(3 \cdot5^{D}-1)/2$ vertices. Substituting $2^n$ for the number of vertices and solving for $D$ gives the first two lower bounds.

The directed Aleshin graph has three outgoing edges at each vertex. At most $1+3+\cdots+3^D=(3^{D+1}-1)/2$ vertices can be reached by directed paths of length at most $D$. This gives the third lower bound. Combine these estimates with Theorem 4.2 and Proposition 4.3. Here $\Theta(n)$ means that the quantity is bounded above and below by positive constant multiples of $n$ for all sufficiently large $n$.

The Aleshin graphs are not Ramanujan from level ten

A connected $d$-regular graph is Ramanujan if every adjacency eigenvalue other than the trivial values $d$ and, when present, $-d$ has absolute value at most $2\sqrt{d-1}$. We use this same spectral definition for the multigraphs in the note, with loops and edge multiplicities counted in their adjacency matrices. For the degree-six Aleshin graphs, the Ramanujan threshold is $2\sqrt{5}$. The expansion bound $4\sqrt{2}$ from Theorem 2.5 is larger than this threshold. The following argument exhibits an eigenvalue above $2\sqrt{5}$ at level ten and carries it to every higher level.

Eigenvalues persist under passage to higher levels

For $n \ge m$, let $\pi_{n,m}:V_n \to V_m$ delete the last $n-m$ letters, and define the pullback of functions by

Each word of length $m$ has exactly $2^{n-m}$ extensions of length $n$, so

In particular, $L_{n,m}$ is injective and carries $H_m$ into $H_n$.

Proof. A rooted-tree automorphism preserves prefixes. Thus, for each $s \in\{a,b,c,a^{-1},b^{-1},c^{-1}\}$,

Using $(P_sf)(w)=f(s^{-1}(w))$, this gives $P_sL_{n,m}=L_{n,m}P_s$, where the two occurrences of $P_s$ act at their respective levels. Summing over the six generators proves Eq. (29). If $K_mf=\lambda f$ with $0\ne f\in H_m$, then $0\ne L_{n,m}f\in H_n$ by Eq. (28), and $K_nL_{n,m}f=\lambda L_{n,m}f$.

An exact certificate at level ten

Proof. We give a finite certificate consisting entirely of integer matrix recursions and exact inner products. Order the words at each level lexicographically, with words starting with 0 before those starting with 1. Let $A_m$, $B_m$, $C_m$ be the column permutation matrices of $a,b,c$ on $V_m$. At level zero they are all the $1 \times1$ matrix $(1)$. The wreath recursions (1) give

Thus the symmetric $1024 \times1024$ integer matrix at level ten is

Let $\chi\in\mathbb{Z}^{V_{10}}$ be the parity vector

It has coordinate sum zero. Define

Since $K$ preserves $H_{10}$, all the $u_j$ and $v$ lie in $H_{10}$. Their construction is explicit from (30) and (31).

The four inner products needed to evaluate the Rayleigh quotient of $v$ are as follows. Put $\mu_j=\langle u_{13},K^j u_{13}\rangle$. Successive application of the displayed integer recursions gives

These are exact integers. Expanding $(K+4I)^2$ and using the symmetry of $K$ now gives

In particular $v\ne0$. The strict comparison with the Ramanujan threshold follows from the two integer inequalities

They imply

To see why this proves an eigenvalue bound, expand $v$ in an orthonormal eigenbasis of the real symmetric operator $K|_{H_{10}}$. Its Rayleigh quotient is a weighted average of the corresponding eigenvalues, with nonnegative weights summing to one. At least one eigenvalue is therefore at least $q/d$. Theorem 2.5 places every eigenvalue on $H_{10}$ strictly below $6$, so the eigenvalue just obtained is nontrivial. This proves that $A_{10}$ is not Ramanujan.

Finally, Lemma 5.1 carries this same eigenvalue to $K_n|_{H_n}$ for every $n\geq10$. It remains strictly between $2\sqrt{5}$ and $6$ and hence violates the degree-six Ramanujan bound at every such level.

The theorem establishes failure of the Ramanujan bound for every level from ten onward. This is compatible with the uniform spectral gap proved earlier: expansion requires a fixed separation from $6$ and $-6$, whereas the Ramanujan condition imposes the smaller interval $[-2\sqrt{5},2\sqrt{5}]$ on the nontrivial spectrum.

Tools used.

The paper was written with ChatGPT 6 Pro editing assistance. The proof of the fact that the Aleshin graphs are not Ramanujan, § 5.2, was done with ChatGPT 6 Pro assistance. The content of the paper was carefully checked by the authors and the authors carry the full responsibility of the content of the paper.