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$?



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}\}$?
$\newcommand{\N}{\mathbb{N}}$
Recall that [Landau function](https://en.wikipedia.org/wiki/Landau%27s_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](https://ac.els-cdn.com/0304397586901428/1-s2.0-0304397586901428-main.pdf?_tid=ac5b7fc1-af2a-499a-8155-5187631c964d&acdnat=1542040803_4f9ccfe2aaa2a38addba9383cd81265b)].


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).


