Given any finite relation $R$ what is the cardinality of $\langle R\rangle=\{\underbrace{R\circ R\cdots \circ R}_{n\text{ times}}:n\in\mathbb{N}\}$?

Question

Given any finite relation $R$ if we let $\circ$ denote relation composition and define $R^n=\underbrace{R\circ R\cdots \circ R}_{n\text{ times}}$ then does there exist an explicit formula for the cardinality of the set $\langle R\rangle=\{R^n:n\in\mathbb{N}\}$? If not, then are there any decent bounds for $|\langle R\rangle|$? I mean clearly we have that: $$\{R^n:n\in\mathbb{N}\}\subseteq\wp(\text{dom}(R)\times\text{rng}(R))\implies |\{R^n:n\in\mathbb{N}\}|\leq 2^{|\text{dom}(R)||\text{rng}(R)|}\leq 2^{|R|^2}$$ But this is a terrible upper bound. How can it be improved?

Also I can prove if $R$ is functional and we define the digraph $D=(\text{dom}(R)\cup\text{rng}(R),R)$ then if we let $m$ be the length of any longest directed path in the condensation of $D$ and we let $n$ be the least common multiple of the lengths of every directed cycle in $D$, then we have:

$$|\langle R\rangle|=\begin{cases}n&\text{ if }D\text{ is the graph of a permutation}\\m+1&\text{ if }D\text{ is a directed acyclic graph}\\m+n-1&\text{ otherwise}\end{cases}$$

However again this is just a special case, so to reiterate given any finite relation $R$ does there exist a general expression or formula for the cardinality of $\langle R\rangle$?

Answer 1

$\newcommand{\N}{\mathbb{N}}$ Recall that Landau function $g(n)$ is the biggest possible $\mbox{lcm}$ of numbers wich sum up to $n$. It's asymptotic is well-studied.

I'll prove the following

$\textbf{Theorem 1.}$ There is some $C > 0$ such that we have $|\{ R^n : n\in \N\}| \le g(|R|) + C|R|^2$, moreover we can find $0 < k \le g(|R|)$ such that $R^{n + k} = R^n$ for $n = C|R|^2$.

Instead of talking about relations I prefer to talk about finite oriented graphs and nondeterministic finite automata over unary language. Let us prove the following

$\textbf{Theorem 2.}$ Let $G$ be a directed graph and let $C_1, \ldots , C_m$ be its strongly connected components. Then for every vertex $v\in G$ we have that set of vertices that one can reach from $v$ in exactly $M$ steps is up to some pre-period of length $O(|G|^2)$ is something wich is periodic with period $\mbox{lcm}(c_1, \ldots , c_m)$, where $c_i$ is $\mbox{gcd}$ of length of all cycles in $C_i$.

Let us prove Theorem 1 from Theorem 2:

Using cycles of different length one can easily construct example where period is at least $g(|R|)$.

On the other hand we have that up to very small pre-period we have that everything is periodic with period $\mbox{lcm} (c_1, \ldots , c_m)$. Since $c_i \le |C_i|$ we have that $c_1 + \ldots + c_m \le |G|$. Now it is obvious that $|G| \le 2|R|$ (we do not consider vertices of degree $0$). But we can say a bit more: note that any vertex of total degree $1$ can not be a part of any strongly connected component thus we may not consider these vertices as well. And number of other vertices is at most $|R|$ so we got that length of the period is at most $g(|R|)$.

It remains to prove Theorem 2.

To do so we need the (proof of) Lemma 4.3 from Chrobak's paper [1].

Consider vertices $v, u\in G$. Let us build NFA: it's graph will be just $G$, every edge corresponds to the same letter, we begin at $v$ and the only accepting state is $u$. It is enough to prove that set of all $m$ such that we can reach $u$ from $v$ in exactly $m$ steps is up to pre-period of size $O(|G|^2)$ is something with period $\mbox{lcm}(c_1, \ldots , c_m)$. But that is exactly what Chrobak did! So the Theorem 2 is also proved.

Now it remains to use asymptotic of Landau function to get that maximum possible $k = \exp( (1 + o(1))\sqrt{|R|\log |R|})$.

As a final remark note that everyting here depends mostly on the number of elements we have our relation on (that is $|G|$) rather than $|R|$ (that is number of edges).