# 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}\}$?

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

• Firstly, if we consider graph which consists of oriented cycles with all prime lengths up to $\sqrt{R\log R}$(I’m not distinguishing between graphs and relations) then we will have something of order $\exp(\sqrt{R\log R})$. I have some vague idea how to prove that the answer is $O(c^R)$ for some $c$ (actually $O(lcm(1, 2, \ldots , R))$). When (and if) I’ll check up the details I’ll post it. – Aleksei Kulikov Nov 12 '18 at 8:05
• @AlekseiKulikov Just to make sure I'm following you, you chose $R$ so its digraph consisted of only oriented cycles which had prime lengths so that the least common multiple of their lengths was equal to the product of their lengths. And since $\prod_{p\leq x}p=\mathcal{O}(e^x)$ this means if we have cycles with prime lengths for every prime less then or equal to $x$ then we get $|\langle R \rangle|=\mathcal{O}(e^x)$. Also by the prime number theorem we get that $\log(R)|R|=x^2+\mathcal{O}(\frac{x^2}{\log(x)})$ therefore we have $|\langle R \rangle|=\mathcal{O}(e^{\sqrt{\text{log}(R)|R|}})$ – Ethan Nov 12 '18 at 8:23
• @Ethan Yes, we choose $x=\sqrt{R\log R}$ and as you said product of primes is something of order $e^x$ so we have lower bound $\exp(x)$. – Aleksei Kulikov Nov 12 '18 at 8:26
• Yes, of course we choose $x=\sqrt{R\log R}$, because for this choice we have that sum of primes up to $x$ is of order $R$. – Aleksei Kulikov Nov 12 '18 at 8:34
• Actually, this question true domain is the realm of finite automata! I asked specialist in my University who happens to be nearby and he pointed me to the following article of Chrobak and, more importantly, Chrobak’s normal form, which, I believe, gives us that the correct asymptotic is indeed $\exp(\Theta(\sqrt{R\log R}))$ (ac.els-cdn.com/0304397586901428/…). With some work I believe one can even get the correct constant in exponent. – Aleksei Kulikov Nov 12 '18 at 10:39

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

• Theorem 1 states that for each $m$, the maximum size of $\{R^n:n\ge 0\}$ over all $R$ with $|R|=m$ is $g(m)$. Is that correct? the current wording is not totally clear to me. Also the second claim is that there is $n=n_m=O(m^2)$ satisfying the given condition for each $R$ with $|R|=m$? or that there exists $N=N_m=O(m^2)$ such that for every $R$ with $|R|=m$ one can find $n\le N_m$ with the given condition? this is not equivalent. – YCor Nov 12 '18 at 18:44
• @YCor, both $k$ and $n$ depends on $R$. I added this, hope it's clear now. – Aleksei Kulikov Nov 12 '18 at 19:25
• @YCor after thinking about it a bit more I think $n$ may be chosen independent of $R$ -- indeed, if $R^{n+k} = R^n$ then $R^{n+k+1} = R^{n+1}$. $k$ of course still depends on $R$ though. Also I forgot about pre-peroid, so maximum size of $\{ R^n: n \ge 0\}$ is $g(m) + O(m^2)$. Fixed it now. – Aleksei Kulikov Nov 12 '18 at 19:53
• It's clear that $n$ can be chosen independently of $R$ (to each $R$ with $|R|=m$, choose $n_R$ and take the lcm over all $R$) but this breaks the quadratic bound a priori. – YCor Nov 12 '18 at 20:50
• @YCor I may be wrong, but if for each $R$ some $n <= C|R|^2$ works then $n = C|R|^2$ works as well. So we can always choose $n=C|R|^2$ for fixed $|R|$. n is the length of pre-period, we can always increase it by as much as we want. – Aleksei Kulikov Nov 12 '18 at 20:56