Composition of random functions and word reconstruction
This work addresses the theoretical limits of recovering combinatorial structure from random function compositions, relevant to cryptography and computational learning theory, but remains largely theoretical with conjectural dependencies.
The authors study whether a single sample of a random function formed by composing two random functions according to an unknown word can recover properties of that word. They show that the word length and exponent can be recovered with high probability, and that functions from different words are separated in total variation distance under a constant condition linked to Schanuel's conjecture.
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}=Ï_{w_k}\circ \dots \circ Ï_{w_1}$ with $Ï_a=\mathbf{a}$ and $Ï_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.