Return to Answer

Proof. Consider the set $P \subset G$ consisting of all geodesics in $G \setminus A$ that begin from $\partial A$ (the boundary of $A$, i.e. elements adjacent to $A$ but not inside it), in the component of $h$. Write $P_n$ for the set of nodes first reached by some geodesic in $P$ after exactly $n$ steps. Since every translate of $A$ splits $G$ into at least three components, it is easy to show that for some $\alpha > 1$, we have $|P_n| \geq \alpha^n$ for all large enough $n$. For all $g \in P_n$, fix a geodesic representation $w_g \in S^n$, representing a the path from some element $e_g \in \partial A$ to $G$ arbitrarily.

Now pick $h'$ in $G \setminus A$ in $P_m$ for large $m$. Suppose that for all $g \in P_n$, the set $g(h')^{-1}A$ intersects the range of the geodesic $w_g$ (in the obvious sense of partial products starting from $e_n$). Then, intuitively, we can use this fact to compress the information in the paths in $P_n$. More precisely, if $g \in P_n$ then $g = g'a^{-1}h'$ for some $a \in A$ where $g'$ lies on the range of $w_g$. Because $h' \in P_m$ has word norm at least $m - |e_g|$ and $w_g$ is a geodesic, $g'$ must be in $P_{n-m+k}$ where $k \in [-3r,3r]$ where $r$ is the maximal word norm among elements of $A$. This means we can describe any element of $P_n$ by listing the at most $\lceil n/(m-3r) \rceil$ elements $a^{-1}$ and the element of $P_{n'}$ for $n' < m+3r$ obtained in the end. Now, $C |S|^{m+3r+1} |A|^{\lceil n/(m-r) \rceil}$ (where $C |S|^{m+3r}$ is an upper bound for the number of elements obtained in the end, $C$ is the boundary size of $A$) has slower asymptotic growth in $n$ than $\alpha^n$, as soon as $|A|^{1/(m-3r)} < \alpha$, a contradiction if $m$ was picked large enough.

Edit: The axial part had a chirality issue. That's what you get for trying to be fast, I should maybe just have drawn a picture.

Proof. Consider the set $P \subset G$ consisting of all geodesics in $G \setminus A$ that begin from $\partial A$ (the boundary of $A$, i.e. elements adjacent to $A$ but not inside it), in the component of $h$. Write $P_n$ for the set of nodes first reached by some geodesic in $P$ after exactly $n$ steps. Since every translate of $A$ splits $G$ into at least three components, it is easy to show that for some $\alpha > 1$, we have $|P_n| \geq \alpha^n$ for all large enough $n$. For all $g \in P_n$, fix a geodesic representation $w_g \in S^n$, representing a the path from some element $e_g \in \partial A$ to $g$ arbitrarily.

Now pick $h'$ in $G \setminus A$ in $P_m$ for large $m$. Suppose that for all $g \in P_n$, the set $g(h')^{-1}A$ intersects the range of the geodesic $w_g$ (in the obvious sense of partial products starting from $e_n$). Then, intuitively, we can use this fact to compress the information in the paths in $P_n$. More precisely, if $g \in P_n$ then $g = g'a^{-1}h'$ for some $a \in A$ where $g'$ lies on the range of $w_g$. Because $h' \in P_m$ has word norm at least $m - |e_g|$ and $w_g$ is a geodesic, $g'$ must be in $P_{n-m+k}$ where $k \in [-3r,3r]$ where $r$ is the maximal word norm among elements of $A$. In particular, the distance of $g$ from $\partial A$ is reduced by at least $m-3r$ when we multiply it by a suitable $h^{-1}a$. We can now describe any element of $P_n$ by listing at most $\lceil n/(m-3r) \rceil$ elements $a$, encountered when iteratively applying this observation, starting from $g$, and listing also the element of $P_{n'}$ for $n' < m+3r$ obtained in the end. Now, $C |S|^{m+3r+1} |A|^{\lceil n/(m-r) \rceil}$ (where $C |S|^{m+3r}$ is an upper bound for the number of elements obtained in the end, $C$ is the boundary size of $A$) has slower asymptotic growth in $n$ than $\alpha^n$, as soon as $|A|^{1/(m-3r)} < \alpha$, a contradiction if $m$ was picked large enough.

Edit: The axial part had a chirality issue. That's what you get for trying to be fast, I should maybe have drawn a picture. Fixed some typos as well.

Proof. Let $A$ finite and $G \setminus A$ has all components infinite and has at least three components, you can always find such by flood filling the finitely many finite ones. Let $h_1 \notin A$ and $h_2 \notin A$ be in distinct components of $G \setminus A$. Now, use the previous lemma to find $k_1$ such that $h_1$ and $k_1h_1$ are in the same component of $G \setminus (A \cup k_1A)$ and $A$ and $k_1A$ are disjoint. Then find $k_2$ so that $A$ and $k_2A$ are disjoint and $h_2$ is in the same component of $G \setminus (A \cup k_2A)$ as $k_2h_2$. Then $k_2^{-1}k_1$ is $n$-axial, where $n$ is bigger than the size of $A$. This follows by arguments in Cohen's thesis: Consider the sequence $..., A_{-1} = k_2A, A_0 = A, A_1 = k_1A, A_2 = k_2^{-1}k_1A...$ where you alternate left multiplication by $k_2^{-1}$ and $k_1$. Now, $(A_{-1} : A_0 : A_1)$ by assumption, and $(A_0 : A_1 : A_2)$ because if there is a path from $A_0$ to $A_2$ that does not go through $A_1$, then you can connect $k_1h_1$ to $k_1h_2$ without going through $k_1A$ (which would be a contradiction). This is because $k_1h_1$ is connected to $h_1$ and $k_1h_2$ is connected to $k_2^{-1}k_1h_2$, even in the complement of all three of those sets. By translation symmetry, $(A_i:A_{i+1}:A_{i+2})$ for all $i$, and you can show this implies $(A_i:A_j:A_k)$ for all $i < j < k$. End square.

Proof. Let $A$ finite and $G \setminus A$ has all components infinite and has at least three components, you can always find such by flood filling the finitely many finite ones. Let $h_1 \notin A$ and $h_2 \notin A$ be in distinct components of $G \setminus A$. Now, use the previous lemma to find $k_1$ such that $h_1$ and $k_1h_1$ are in the same component of $G \setminus (A \cup k_1A)$ and $A$ and $k_1A$ are disjoint. Then find $k_2$ so that $A$ and $k_2A$ are disjoint and $h_2$ is in the same component of $G \setminus (A \cup k_2A)$ as $k_2h_2$. Then $k_2^{-1}k_1$ is $n$-axial, if $n$ is bigger than the size of $A$.

Now consider the sequence $B_0 = A, B_1 = k_2^{-1}A, B_2 = k_2^{-1} k_1 A, B_3 = k_2^{-1} k_1 k_2^{-1} A, B_4 = k_2^{-1}k_1k_2^{-1}k_1 A...$ i.e. you multiply the left translation element from the right alternately by $k_2^{-1}$ and $k_1$.

We have $(B_0 : B_1 : B_2)$: The separation $(k_2A : A : k_1A)$ is clear, and gives $(A : k_2^{-1}A : k_2^{-1}k_1A)$ by translating.

We have $(B_1 : B_2 : B_3)$: We prove that $(A : k_1A : k_1k_2^{-1}A)$ holds: suppose there is a path from $A$ to $k_1k_2^{-1}A$ that does not go through $k_1A$. Then, there is a path from $k_1h_1$ to $k_1h_2$ that does not go through $k_1A$ (which would be a contradiction). To see this, take a path from $k_1h_1$ to $h_1$ (using the assumption on $k_1$) that does not visit any of the three sets, then move to $k_1k_2^{-1}A$ and then $k_1k_2^{-1}h_2$ without visiting $k_1A$ (using the counterassumption that $(A : k_1A : k_1k_2^{-1}A)$ does not hold). Now, observe that since $h_2$ and $k_2h_2$ are in the same connected component of $G \setminus (A \cup k_2A)$, by translating by $k_1k_2^{-1}$ we get that $k_1k_2^{-1}h_2$ and $k_1h_2$ are in the same connected component of $G \setminus (k_1k_2^{-1} A \cup k_1A)$, so we have found a path from $k_1h_1$ to $k_1h_2$ that avoids $k_1A$. From $(A : k_1A : k_1k_2^{-1}A)$, we get $(B_1 : B_2 : B_3) = (k_2^{-1}A : k_2^{-1}k_1A : k_2^{-1}k_1k_2^{-1}A)$ by translating, as desired.

We have shown $(B_0 : B_1 : B_2)$ and $(B_1 : B_2 : B_3)$, and by translating by $k_2^{-1}k_1$ from the left we get $(B_i : B_{i+1} : B_{i+2}) \implies (B_{i+2} : B_{i+3} : B_{i+4})$, so by induction $(B_i : B_{i+1} : B_{i+2})$ holds for all $i$. By a basic connectivity lemma (see e.g. Cohen's thesis) we have $(B_i : B_j : B_k)$ for all $i < j < k$. The sequence $B_{2i}$ proves that $k_2^{-1}k_1$ is axial. End square.

Edit: The axial part had a chirality issue. That's what you get for trying to be fast, I should maybe just have drawn a picture.

Proof. Consider the set $P \subset G$ consisting of all geodesics in $G \setminus A$ that begin from $\partial A$ (the boundary of $A$, i.e. elements adjacent to $A$ but not inside it), in the component of $h$. Write $P_n$ for the set of nodes first reached by some geodesic in $P$ after exactly $n$ steps. Since every translate of $A$ splits $G$ into at least three components, it is easy to show that for some $\alpha > 1$, we have $|P_n| \geq \alpha^n$ for all large enough $n$. For all $g \in P_n$, fix a geodesic representation $w_g \in S^n$, representing a the path from some element $e_n \in \partial A$ to $G$ arbitrarily.

Now pick $h'$ in $G \setminus A$ in $P_m$ for large $m$. Suppose that for all $g \in P_n$, the set $g(h')^{-1}A$ intersects the range of the geodesic $w_g$ (in the obvious sense of partial products starting from $e_n$). Then, intuitively, we can use this fact to compress the information in the paths in $P_n$. More precisely, if $g \in P_n$ then $g = g'a^{-1}h'$ for some $a \in A$ where $g'$ lies on the range of $w_n$. Because $h' \in P_m$ has word norm $m$ and $w_g$ is a geodesic, $g'$ must be in $P_{n-m+k}$ where $k \in [-r,r]$ where $r$ is the maximal word norm among elements of $A$. This means we can describe any element of $P_n$ by listing the at most $\lceil n/(m-r) \rceil$ elements $a^{-1}$ and the element of $P_{n'}$ for $n' < m+r$ obtained in the end. Now, $C |S|^{m+r+1} |A|^{\lceil n/(m-r) \rceil}$ (where $C |S|^{m+r+1}$ is the number of elements obtained in the end, $C$ is the boundary size of $A$) has slower asymptotic growth in $n$ than $\alpha^n$, as soon as $|A|^{1/(m-r)} < \alpha$, a contradiction if $m$ was picked large enough.

Proof. Consider the set $P \subset G$ consisting of all geodesics in $G \setminus A$ that begin from $\partial A$ (the boundary of $A$, i.e. elements adjacent to $A$ but not inside it), in the component of $h$. Write $P_n$ for the set of nodes first reached by some geodesic in $P$ after exactly $n$ steps. Since every translate of $A$ splits $G$ into at least three components, it is easy to show that for some $\alpha > 1$, we have $|P_n| \geq \alpha^n$ for all large enough $n$. For all $g \in P_n$, fix a geodesic representation $w_g \in S^n$, representing a the path from some element $e_g \in \partial A$ to $G$ arbitrarily.

Now pick $h'$ in $G \setminus A$ in $P_m$ for large $m$. Suppose that for all $g \in P_n$, the set $g(h')^{-1}A$ intersects the range of the geodesic $w_g$ (in the obvious sense of partial products starting from $e_n$). Then, intuitively, we can use this fact to compress the information in the paths in $P_n$. More precisely, if $g \in P_n$ then $g = g'a^{-1}h'$ for some $a \in A$ where $g'$ lies on the range of $w_g$. Because $h' \in P_m$ has word norm at least $m - |e_g|$ and $w_g$ is a geodesic, $g'$ must be in $P_{n-m+k}$ where $k \in [-3r,3r]$ where $r$ is the maximal word norm among elements of $A$. This means we can describe any element of $P_n$ by listing the at most $\lceil n/(m-3r) \rceil$ elements $a^{-1}$ and the element of $P_{n'}$ for $n' < m+3r$ obtained in the end. Now, $C |S|^{m+3r+1} |A|^{\lceil n/(m-r) \rceil}$ (where $C |S|^{m+3r}$ is an upper bound for the number of elements obtained in the end, $C$ is the boundary size of $A$) has slower asymptotic growth in $n$ than $\alpha^n$, as soon as $|A|^{1/(m-3r)} < \alpha$, a contradiction if $m$ was picked large enough.