Composition of random functions and word reconstruction

View PDF HTML (experimental)

Abstract:Given two functions $\mathbf{a}!:! [n] \rightarrow [n]$ and $\mathbf{b}!:! [n] \rightarrow [n]$ chosen uniformly at random, any word $w=w_1w_2\dots w_k\in {a,b}^k$ induces a random function $\mathbf{w}!:! [n] \rightarrow [n]$ by composition, i.e. $\mathbf{w}=\phi_{w_k}\circ \dots \circ \phi_{w_1}$ with $\phi_a=\mathbf{a}$ and $\phi_b=\mathbf{b}$. We study the following question: assuming $w$ is fixed but unknown, and $n$ goes to infinity, does one sample of $\mathbf{w}$ carry enough information to (partially) recover the word $w$ with good enough probability? We show that the length of $w$, and its exponent (largest $d$ such that $w={u}^d$ for some word ${u}$) can be recovered with high probability. We also prove that the random functions stemming from two different words are separated in total variation distance, provided that certain ``auto-correlation'' word-depending constant $c(w)$ is different for each of them. We give an explicit expression for $c(w)$ and conjecture that non-isomorphic words have different constants. We prove that this is the case assuming a major conjecture in transcendental number theory, Schanuel's conjecture.

Subjects:

Probability (math.PR); Data Structures and Algorithms (cs.DS); Combinatorics (math.CO); Number Theory (math.NT); Statistics Theory (math.ST)

Cite as: arXiv:2603.28936 [math.PR]

(or arXiv:2603.28936v1 [math.PR] for this version)

https://doi.org/10.48550/arXiv.2603.28936

arXiv-issued DOI via DataCite (pending registration)

Submission history

From: Guillaume Chapuy [view email] [v1] Mon, 30 Mar 2026 19:16:13 UTC (1,099 KB)