Combinatorics on signals

If $|u| = 0$, then the claim is trivial. Assume $|u| > 0$ and $uv = vu$. Let $\mathrm{seq}(u) = \sigma_1^{\delta_1} \cdots \sigma_n^{\delta_n}$. For the sake of contradiction, suppose there exists $i \in [1..n]$ such that $\sigma_i \neq a$. Let $i$ be minimal. Let $\alpha = \delta_1 + \ldots + \delta_{i-1}$ and $\beta = \alpha + \delta_i$. By minimality of $i$, we have $u(\tau) = a$ for all $\tau \in (0, \alpha]$, and $u(\tau') \neq a$ for all $\tau' \in (\alpha, \beta]$. We make a case distinction, and obtain a contradiction in both cases.

Case $\alpha \geq \delta$. Since $\delta > 0$, we have $\alpha > 0$. Let $\gamma = \min(\delta_i, \delta)$, $\tau = \alpha - \delta + \gamma$ and $\tau' = \alpha + \gamma$. Note that $0 < \tau \leq \alpha - \delta + \delta = \alpha$ and $\alpha < \tau' \leq \alpha + \delta_i = \beta$. Thus, we obtain the following contradiction:

Case $\delta > \alpha$. Let $\gamma = \min(\delta - \alpha, \delta_i)$ and $\tau = \alpha + \gamma$. Since $\tau \in (0, \delta]$, we have $v(\tau) = a$. Moreover, since $\alpha < \tau \leq \alpha + \delta_i = \beta$, we have $u(\tau) \neq a$. Thus, we obtain a contradiction:

$\Leftarrow$) If $u = \sigma^\alpha$ and $v = \sigma^\beta$ for some $\sigma \in \Sigma$ and $\alpha, \beta \in \R_{>0}$, then $uv = \sigma^{\alpha + \beta} = \sigma^{\beta + \alpha} = vu$. If $u = w^i$ and $v = w^j$ for some $w \in \mathcal{S}(\Sigma)$ and $i, j \in \N$, then $uv = w^{i+j} = w^{j+i} = vu$.

$\Rightarrow$) We proceed by induction on $\# u + \# v$. If $u$ or $v$ is empty, then the claim is trivial. If $|u| = |v|$, then we must have $u = v$, and hence we are done. Assume $|u| > |v| > 0$ (the other case is symmetric).

Let $\mathrm{seq}(u) = \sigma_1^{\delta_1} \cdots \sigma_n^{\delta_n}$. Since $uv = vu$ and $|u| > |v|$, we have $u = vx$ for some $x \in \mathcal{S}(\Sigma)$. Thus, there exist $\alpha, \beta \in \R_{\geq 0}$ and $i \in [1..n]$ such that

If $\# v = 1$, then we are done by Lemma 1. Thus, we may assume that $\# v > 1$. We have

By cancelling $v$ on the left, we obtain $xv = vx$. Observe that

Thus, by induction, we either have $\mathrm{seq}(x) = \sigma^\alpha$ and $\mathrm{seq}(v) = \sigma^\beta$ for some $\sigma \in \Sigma$ and $\alpha, \beta \in \R_{>0}$, or $x = w^i$ and $v = w^j$ for some $w \in \mathcal{S}(\Sigma)$ and $i, j \in \N$. The first case cannot hold since $\# v > 1$. So, the second case holds, and we are done since $u = vx = w^i w^j = w^{i + j}$ and $v = w^j$.

$\Rightarrow)$ Let $x, y \in \mathcal{S}(\Sigma)$ be such that $u = xy$ and $v = yx$. Let $z = x$. We are done since

$\Leftarrow$) Let $z \in \mathcal{S}(\Sigma)$ be such that $uz = zv$. If $|u| = 0$, then the claim is trivial. Thus, we may assume that $|u| > 0$. We proceed by induction on $\# z$. If $\# z = 0$, then $u = v$ and we are done. Suppose $\# z > 0$.

Case $|u| \geq |z|$. We have $u = zw$ for some $w \in \mathcal{S}(\Sigma)$. Thus, we have $zwz = uz = zv$. By cancelling $z$ on the left, we obtain $wz = v$. We are done since $u = zw$ and $v = wz$ are conjugates.

Case $|z| > |u|$ and $\#u = 1$. We have $\mathrm{seq}(u) = \sigma^\delta$ for some $\sigma \in \Sigma$ and $\delta \in \R_{>0}$. Since $|z| > |u|$, we can decompose $z$ as $z = \sigma^\gamma w$ where $w \in \mathcal{S}(\Sigma)$ and $\gamma \geq \delta$ is maximal. By maximality of $\gamma$, we have $\#w = \#z - 1$. Moreover,

By cancelling $\sigma^\gamma$ on the left, we obtain $uw = wv$. Since $\#w = \#z - 1$, by induction, we conclude that $u$ and $v$ are conjugates.

Case $|z| > |u|$ and $\#u > 1$. We have $z = uw$ for some $w \in \mathcal{S}(\Sigma)$ with $|w| > 0$. Let $\mathrm{seq}(z) = \sigma_1^{\delta_1} \cdots \sigma_n^{\delta_n}$. There exist $\alpha, \beta \in \R_{\geq 0}$ and $i \in [1..n]$ such that

Since $\#z = n$ and $2 \leq \# u \leq i$, we obtain $\#w \leq n - i + 1 \leq n - 2 + 1 = \#z - 1$.

We have $uuw = uz = zv = uwv$. By cancelling $u$ on the left, we obtain $uw = wv$. Since $\#w < \#z$, by induction, we conclude that $u$ and $v$ are conjugates.

Let $P \subseteq (0, |w|]$ be the set of periods of $w$. Let $\rho = \inf P$. We must show that $\rho$ is a period of $w$. Let $\rho_0 > \rho_1 > \cdots \in P$ be such that $\lim_{n \to \infty} \rho_n = \rho$. Let $\mathrm{seq}(w) = \sigma_1^{\delta_1} \cdots \sigma_k^{\delta_k}$, where $k = \# w > 1$. Let $\tau_i = \sum_{j=1}^i \delta_j$ for every $i \in [0..k]$. We say that $\tau \in (0, |w|]$ lies in piece $i \in [1..k]$ if $\tau \in (\tau_{i-1}, \tau_i]$.

We cannot have $\rho = 0$, as otherwise we would have $w(\tau_1) = \lim_{x \to \tau_1^+} w(x)$.

For the sake of contradiction, suppose there exists $\tau \in (0, |w| - \rho]$ such that $w(\tau + \rho) \neq w(\tau)$. Let $i \in [1..k]$ be such that $\tau$ lies in piece $i$. Since $w(\tau + \rho_\ell) = w(\tau)$ for all $\ell \in \N$, we have

This means that $\tau + \rho$ is a “breakpoint”, i.e. $\tau + \rho = \tau_j$ for some $j \in [0..k-1]$. By $w(\tau_i) = w(\tau) \neq w(\tau + \rho) = w(\tau_j)$, we must have $i < j$.

Let $\epsilon \in \R_{> 0}$ be small enough so that $\tau - \epsilon$ lies in piece $i$, and $\tau + \rho - \epsilon$ lies in piece $j$. Let $\ell \in \N$ be large enough so that $\rho_\ell - \rho \leq \epsilon$. Let $\tau' = \tau + \rho_\ell - \epsilon$. Note that $\tau + \rho - \epsilon < \tau' \leq \tau + \rho$ and hence that $\tau'$ lies in piece $j$. We obtain a contradiction:

Recall that $0 < \rho \leq |w|$. By definition, $u$ is the signal $u \colon (0, \rho] \to \Sigma$ with $u(\tau) = w(\tau)$. Since $\rho$ is a period of $w$, we have

Let $k = \lfloor |w| / \rho \rfloor$ and let $\alpha \in [0, \rho)$ be the unique value such that $|w| = k \cdot \rho + \alpha$. By the above, we have $w = u^k u^{\alpha / \rho} = u^{k + \alpha / \rho}$. We are done since $k + \alpha / \rho = (k \cdot \rho + \alpha) / \rho = |w| / \rho$.

Existence. We proceed by induction on $\# w$. If $\# w = 2$, then we are done as $w$ is primitive. Indeed, if we had $w = u^k$ with $k \geq 2$, then we would either have $\# u = \# w = 1$, or $\# u \geq 2$ and so $\#w \geq 4$.

Suppose $\# w \geq 3$. If $w$ is primitive, then we are done. Otherwise, we have $w = v^m$ for some non-empty signal $v$ and integer $m \geq 2$. We necessarily have $\# v \geq 2$. In $v^m$, the only reductions that may occur are at the concatenation of the last and first piece of $v$. Thus,

By induction, there exists a primitive signal $u$ and an integer $k \geq 1$ such that $v = u^k$. We are done since $w = v^m = (u^k)^m = u^{km}$.

Uniqueness. Let $u, v \in \mathcal{S}$ be primitive and let $i, j \geq 1$ be integers such that $w = u^i = v^j$. Let $\alpha = |u|$ and $\beta = |v|$. Since $w = u^i$ and $w = v^j$, the numbers $\alpha$ and $\beta$ are periods of $w$, i.e.

• $w^\omega(\tau) = w^\omega(\tau + \alpha)$ for any $\tau \in \R_{>0}$,

• $w^\omega(\tau) = w^\omega(\tau + \beta)$ for any $\tau \in \R_{>0}$.

We now make a case distinction.

Case with $\alpha / \beta \in \mathbb{Q}_{> 0}$. By assumption, there exist coprime integers $m, n \geq 1$ such that $\alpha / \beta = m / n$. Let $\rho = \alpha / m$. We have $\alpha = m\rho$ and $\beta = n\rho$. By Bézout’s identity, there are $k, \ell \in \Z$ such that $mk + n\ell = 1$. By multiplying the equation with $\rho$ , we obtain $k\alpha + \ell\beta = \rho$. Without loss of generality, we have $k \geq 0$. So, for all $\tau \in \R_{>0}$, we have

Consequently, there exists $x$ with $|x| = \rho$ such that $w = x^{im} = x^{jn}$, $u = x^m$ and $v = x^n$. Since $u$ and $v$ are primitive, we must have $m = n = 1$. Thus, $u = v = x$ and hence $i = j$.

Case with $\alpha / \beta \in \mathbb{R}_{> 0} \setminus \mathbb{Q}_{> 0}$. Let $\tau \in (0, |w|]$ be a breakpoint of $w$, i.e. with $w(\tau) \neq \lim_{x \to \tau^+} w(x)$. It exists by $\# w > 1$. By Kronecker’s approximation theorem, for all $\epsilon \in \R_{>0}$, there exist $k, \ell \in \Z$ such that $k > 0$ and $|k(\alpha / \beta) - \ell| < \epsilon$. By multiplying by $\pm\beta$, this means that for all $\epsilon \in \R_{>0}$, there exist $k, \ell \in \Z$ with $\max(k, \ell) \geq 0$ and $k\alpha + \ell\beta \in (0, \epsilon)$. As $w^\omega(\tau) = w^\omega(\tau + k\alpha + \ell\beta)$, we obtain a contradiction: