Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2603.28936 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911555913777152 |
|---|---|
| author | Chapuy, Guillaume Perarnau, Guillem |
| author_facet | Chapuy, Guillaume Perarnau, Guillem |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_28936 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Composition of random functions and word reconstruction Chapuy, Guillaume Perarnau, Guillem Probability Data Structures and Algorithms Combinatorics Number Theory Statistics Theory 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. |
| title | Composition of random functions and word reconstruction |
| topic | Probability Data Structures and Algorithms Combinatorics Number Theory Statistics Theory |
| url | https://arxiv.org/abs/2603.28936 |