A virtually nilpotent group whose Green series is not D-finite

1. Problem Statement and Context

The Green Series:
The paper investigates the Green series (also known as the cogrowth series), denoted $\Gamma(G, S)(z)$, for a group $G$ with a finite generating multiset $S$. It is defined as:
$$\Gamma(G, S)(z) = \sum_{\ell \geq 0} c_\ell z^\ell$$
where $c_\ell$ is the number of closed paths of length $\ell$ starting and ending at the identity element $e_G$ in the Cayley graph of $(G, S)$.

The Hierarchy of Series:
The author seeks to classify these series within a specific algebraic hierarchy:
$$\text{Rational} \subset \text{Algebraic} \subset \text{Diagonal of Rational} \subset \text{D-finite} \subset \text{D-algebraic}$$

• D-finite (Holonomic): A series is D-finite if its coefficients satisfy a linear recurrence relation with polynomial coefficients.
• Known Results:
  • Rational iff $G$ is finite.
  • Algebraic if $G$ is virtually free.
  • Diagonal of rational if $G$ is virtually $F_m \times \mathbb{Z}^n$.
  • Not D-finite for amenable groups of super-polynomial growth (Bell & Mishna).
  • Not D-finite for specific generating sets of $F_2 \times F_2$ and $SL_4(\mathbb{Z})$ (Garrabrant & Pak).

The Open Question:
For virtually nilpotent groups, the consensus was unclear. While asymptotic growth rates of coefficients often matched those of D-finite series, it was unknown if the series itself was always D-finite. A previous result by Pak and Soukup showed that for a specific nilpotent group $UT_m(\mathbb{Z})$ (with $m \approx 10^8$), either the series is not a diagonal of rational series, or no algorithm exists to compute it. They did not prove the series was strictly non-D-finite.

Goal:
To provide the first example of a virtually nilpotent group with a specific generating set whose Green series is not D-finite.

---

2. The Group and Generating Set

The paper focuses on the group $vH$, defined as the semidirect product $H_3(\mathbb{Z}) \rtimes C_2$.

• Structure: $vH = \langle x, y, t \mid [x, [x, y]] = [y, [x, y]] = t^2 = e, txt = y \rangle$.
• Properties: It is virtually 2-step nilpotent. It was previously identified as the first example of a group with polynomial geodesic growth that is not virtually abelian.
• Generating Set: The specific multiset used is $S = \{x, x^{-1}, t, t, t, t, t, t, t, t\}$. Note the multiplicity of the generator $t$ (eight copies).

Main Theorem (Theorem 1):
The Green series $\Gamma(vH, S)(z)$ is not D-finite.

Corollary:
Since $vH$ embeds into $SL_3(\mathbb{Z})$, it follows that $SL_3(\mathbb{Z})$ admits a generating multiset for which the Green series is not D-finite. This extends previous results known only for $SL_m(\mathbb{Z})$ with $m \geq 4$.

---

3. Methodology

The proof strategy adapts the approach used by Garrabrant and Pak for $F_2 \times F_2$, relying on subword complexity and multiplicative sequences.

A. Reduction to Reduced Words

The author first relates the Green series $\Gamma(z)$ to the growth series of "reduced" words $R(z)$ (words with no immediate backtracking $xx^{-1}$). Using a variation of the Bartholdi–Grigorchuk cogrowth formula, it is shown that $\Gamma(z)$ is D-finite if and only if $R(z)$ is D-finite.

B. Decomposition of Paths

The set of reduced words $R$ is partitioned into three subsets based on the number of $t$ generators:

1. $R_1$: Words with few $t$'s (at most 4, or 6 with consecutive $t$'s). This set corresponds to a context-free language and yields an algebraic (hence D-finite) series.
2. $R_3$: Words with many $t$'s (at least 8). The contribution of these terms is divisible by high powers of 2, making them negligible modulo specific powers of 2.
3. $R_2$: Words with exactly six $t$'s and no consecutive $t$'s. This is the critical set.

C. Combinatorial Analysis of $R_2$

Paths in $R_2$ correspond to specific geometric shapes in the Cayley graph of the Heisenberg subgroup. The counting of these paths reduces to solving a Diophantine system for integers $(a, b, c, d)$:
$$a + b + c + d = n, \quad ab = cd$$
The number of solutions, denoted $|S_n|$, is analyzed modulo powers of 2. The author identifies symmetries (actions of the dihedral group $D_8$) to simplify the counting.

D. Connection to Multiplicative Functions

The analysis reveals that the number of solutions $|S_n|$ (specifically for odd indices) is directly related to a function $m(n)$, defined as the largest integer such that $m^2$ divides $n$.
The author constructs a derived series $S(z)$ whose coefficients modulo 2 depend on the value of a multiplicative function $f(n)$:
$$f(n) = m\left(\frac{n}{2^{\nu_2(n)}}\right) \pmod 4$$
where $f(n) \in \{+1, -1\}$.

E. Subword Complexity Argument

The core of the proof relies on Theorem 7 (Garrabrant–Pak): If a series is D-finite, the subword complexity of its coefficients modulo 2 must be $o(2^n)$.
The author proves Theorem 9: For the specific multiplicative function $f(n)$ constructed above, the subword complexity is maximal ($p_f(n) = 2^n$).

• Proof of Theorem 9: Uses the Chinese Remainder Theorem and the sparseness of prime powers where $f(q) = -1$ to show that any pattern of $\pm 1$ of length $n$ can be realized by $f(x+i)$ for some $x$.

Since the coefficients of the derived series $S(z)$ exhibit maximal subword complexity, $S(z)$ cannot be D-finite. Since $S(z)$ is constructed from $R(z)$ using D-finite preserving operations (extraction of even/odd terms, linear combinations), the original series $R(z)$ and consequently $\Gamma(z)$ cannot be D-finite.

---

4. Key Contributions

1. Resolution of the Virtually Nilpotent Case: The paper provides the first counterexample to the conjecture that Green series of virtually nilpotent groups are D-finite.
2. Refinement of Pak-Soukup: It strengthens the result of Pak and Soukup by proving the series is strictly not D-finite (rather than just not a diagonal of rational series or non-computable) for a virtually nilpotent group.
3. Extension to $SL_3(\mathbb{Z})$: By embedding $vH$ into $SL_3(\mathbb{Z})$, the result extends the non-D-finiteness phenomenon to the special linear group in dimension 3 (previously known only for $m \geq 4$).
4. Methodological Advancement: The paper successfully applies the "subword complexity of multiplicative sequences" technique to a nilpotent setting, overcoming the difficulty that standard asymptotic growth rates in nilpotent groups usually mimic D-finite behavior.

---

5. Significance and Future Directions

• Theoretical Impact: This result challenges the intuition that "nice" geometric groups (like nilpotent ones) always yield "nice" generating functions. It highlights that the arithmetic properties of the group structure (specifically the interaction between the generator $t$ and the Heisenberg subgroup) can induce chaotic behavior in the cogrowth series.
• Open Problems:
  • The Discrete Heisenberg Group $H_3(\mathbb{Z})$: The paper notes that the specific trick of adding multiple copies of a generator ($t$) used here does not immediately apply to $H_3(\mathbb{Z})$ itself. Extending the result to $H_3(\mathbb{Z})$ remains an open and significant challenge.
  • Asymptotic Frequencies: The author mentions that an alternative proof using asymptotic densities of square-free numbers would rely on the unproven conjecture that $\pi^2$ and the Catalan constant $G$ are linearly independent over $\mathbb{Q}$.
• Broader Context: The result suggests that the boundary between D-finite and non-D-finite series in group theory is more complex than previously thought, particularly for groups that are "close" to being abelian or nilpotent.

In summary, Bodart's paper utilizes a sophisticated interplay between combinatorial group theory, number theory (multiplicative functions), and formal language theory to demonstrate that even in the relatively tame world of virtually nilpotent groups, Green series can exhibit maximal complexity.