Graph-Automatic Structures for Thompson's Group $F$

Definitions and mathematical statement

Let $D={\mathbb{Z}}[1/2]=\{m/2^k:m\in{\mathbb{Z}},\ k\in{\mathbb{Z}}_{\geq 0}\}$. Thompson's group $F$ is the group, under composition, of increasing piecewise linear homeomorphisms $f:[0,1]\to[0,1]$ with finitely many breakpoints, all breakpoints in $D\cap(0,1)$, and every linear slope in $\{2^n:n\in{\mathbb{Z}}\}$. In particular, $f(0)=0$ and $f(1)=1$.

For words $u,v$ over a finite alphabet, their padded convolution pairs corresponding letters, padding the shorter word on the right with a new symbol $\square$ until both words have the same length. A binary relation on words is synchronously regular if its set of padded convolutions is accepted by a finite automaton.

Use the following standard finite-state interpretations of the two structures in the question. A finitely generated group $G$ is automatic if there exist a finite symmetric generating set $S$ and a regular language $L\subseteq S^*$ such that the evaluation map $\pi:L\to G$ is bijective and, for every $s\in S$, the relation \[ R_s=\{(u,v)\in L\times L:\pi(u)s=\pi(v)\} \] is synchronously regular. Here words in $L$ represent the products of their generator letters; the use of unique representatives is a standard equivalent convention for automatic groups.

The group $G$ admits a graph-automatic structure if there exist a finite symmetric generating set $S$, a finite alphabet $A$, a regular language $K\subseteq A^*$, and a bijection $\nu:K\to G$ such that, for every $s\in S$, \[ E_s=\{(u,v)\in K\times K:\nu(u)s=\nu(v)\} \] is synchronously regular. The labels in $K$ need not be words evaluating to their assigned group elements. Thus this is a finite-state presentation of the generator-labelled Cayley graph.

Questions. The supplied source asks: "Why should Thompson's group $F$ fail to be automatic, and does $F$ admit a graph-automatic structure?" Under the conventions above, the first question asks whether $F$ has no automatic structure and, if that expected negative answer is correct, for a proof of nonexistence. Its phrasing does not supply a theorem that $F$ is nonautomatic. The second question asks whether there exist $S,A,K,\nu$ satisfying the graph-automatic conditions above for $G=F$.

Source qualifications. The supplied record labels the problem open and reports that $F$ has $1$-counter and $3$-counter graph-automatic structures, while ordinary automaticity and graph automaticity in the finite-state sense remain unresolved. These counter-automaton claims are supplied background, not assertions that the finite-state conditions above have been established. The record does not give the automaton conventions used for those counter structures. Its literature assessment and its formulation-verification labels are supplied curation, not independent verification in this draft.

Short English statement

Determine whether Thompson's group $F$ is nonautomatic, as the source question anticipates, and whether its Cayley graph admits a presentation by a regular language with finite automata recognizing each generator relation. Ordinary automaticity requires representatives to be words in the generators; graph automaticity permits arbitrary word labels. The supplied counter-automaton results and open-status assessment require independent review.

Sources

• Local UnsolvedMath registry, permanent ID $30003839$, exact source problem code catalogue entry, title: Graph-Automatic Structures for Thompson's Group $F$. The supplied record belongs to the Oberwolfach Reports Open Problems collection and lists proposed year $2018$; no individual proposer is supplied.
• Supplied source citation: Cohomological and Metric Properties of Groups of Homeomorphisms of R (2019), Oberwolfach Reports, pp. 1579--1633, DOI 10.4171/owr/2018/26. https://doi.org/10.4171/owr/2018/26. The supplied background describes these reports as documenting mathematical workshops and their open-problem discussions.
• Supplied literature source: Elder--Taback. https://arxiv.org/abs/1501.04313.
• Supplied literature source: Taback--Younes. https://arxiv.org/abs/1501.04315.
• Supplied literature source labelled "Oberwolfach Report 2019". https://ems.press/content/serial-article-files/46748?nt=1.
• Literature checked at: 2026-08-21. This exact date records supplied dated curation, not an independently verified assessment. The supplied assessment labels the problem open and states that $F$ has $1$-counter and $3$-counter graph-automatic structures, whereas ordinary automaticity and finite-state graph automaticity remain unresolved. The background explicitly calls this dated literature triage derived from the supplied OWR curation and requests independent verification of time-sensitive status and cited claims.