Complexity in Enumerative Combinatorics — Problem 9

Definitions and mathematical statement

Let $G$ be a group and $S\subseteq G$. The set $S$ is symmetric if $S=S^{-1}$, where $S^{-1}=\{s^{-1}:s\in S\}$. The Cayley graph $\Gamma(G,S)$ has vertex set $G$, with an edge from $g$ to $gs$ for each $g\in G$ and $s\in S$. For symmetric $S$, these adjacencies are reversible. The supplied fragment does not specify whether $S$ must be finite or generate $G$, or how loops and edge multiplicities are treated.

For clarity about the terminology suggested by the context, fix a field $K$ of characteristic zero. A formal power series $A(z)\in K[[z]]$ is differentially algebraic over $K(z)$ if there exist an integer $r\geq 0$ and a nonzero polynomial $P\in K(z)[Y_0,\ldots,Y_r]$ such that \[ P\left(A(z),A'(z),\ldots,A^{(r)}(z)\right)=0. \] It is differentially transcendental over $K(z)$ if no such $r$ and $P$ exist. The source uses the terms "D-algebraic sequence" and "D-transcendental Cayley graph" without defining the associated series or its coefficient field in the supplied record; the preceding definition therefore explains terminology without resolving those missing choices.

Problem fragment (Pak, 2018, Problem 9). Find an explicit construction of $\Gamma(G,S)$ with $S$ symmetric. The supplied statement ends immediately after "and $\$$", leaving an additional required condition missing. Its surrounding discussion suggests that the intended construction should yield a D-transcendental Cayley graph, but this interpretation cannot replace the missing text.

The source introduces the quantity \[ \rho(G,S):=\lim_{n\to\infty}a_n(G,S)^{1/n}, \] calling it a spectral radius. It does not define $a_n(G,S)$ or supply hypotheses ensuring that this limit exists. Consequently, neither a counting interpretation for $a_n(G,S)$ nor a normalization of $\rho(G,S)$ is imposed here. If the intended series is $\sum_{n\geq0}a_n(G,S)z^n$, that identification still requires confirmation.

The supplied background reports an explicit but highly artificial non-symmetric set $S\subset F_k\times F_\ell$ in a then-forthcoming paper labelled [GP-ADE], where $F_k$ and $F_\ell$ denote free groups of the indicated, unspecified ranks. It also reports that [KP2], using tools from [KP1], establishes an uncountable set of spectral radii for groups, and argues from countability of D-algebraic sequences that D-transcendental Cayley graphs with symmetric $S$ exist nonconstructively. These are supplied contextual claims; their hypotheses, coefficient conventions, and bibliographic identities are unavailable in this record.

Short English statement

Pak's supplied Problem 9 asks for an explicit Cayley graph with a symmetric defining set. The context suggests a D-transcendence requirement, but the statement is truncated before its final condition, and its counting sequence is undefined. The registry labels the problem open; that label and the contextual existence claims are supplied information, not independently verified mathematical assessments.

Sources

• Local UnsolvedMath registry, permanent ID $800325$, exact source problem code catalogue entry, title "Complexity in Enumerative Combinatorics --- Problem 9". The supplied record belongs to the AMR Open Problem Lists collection and attributes the problem to Pak (2018). Local registry locations are data/unsolvedmath/problems.json, data/unsolvedmath/additions/, and catalog/problems.json; the particular containing file was not independently inspected.
• Supplied source attribution: Pak, Complexity Problems in Enumerative Combinatorics (2018), Problem 9, https://arxiv.org/abs/1803.06636. The record gives access date 2026-10-16 and extraction method arxiv_latex. These are supplied provenance details; no source visit or independent verification was performed.
• The statement cites [GP-ADE], described there as forthcoming, and [KP2] and [KP1]. No bibliographic entries or links identifying these three references are supplied. The word "forthcoming" is retained as historical source wording, not a current publication-status assertion.
• The registry supplies status open, creation date 2026-10-16, update date 2026-10-16, and upstream revision d371ee917ac9647fbb06cd6fc529deec6f3dda82. These metadata do not establish mathematical correctness or independently verified current status.