7
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Aleksei Kulikov Nov 12 '18 at 8:05
  • $\begingroup$ @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|}})$ $\endgroup$ – Ethan Nov 12 '18 at 8:23
  • $\begingroup$ @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)$. $\endgroup$ – Aleksei Kulikov Nov 12 '18 at 8:26
  • $\begingroup$ 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$. $\endgroup$ – Aleksei Kulikov Nov 12 '18 at 8:34
  • 3
    $\begingroup$ 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. $\endgroup$ – Aleksei Kulikov Nov 12 '18 at 10:39
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – YCor Nov 12 '18 at 18:44
  • $\begingroup$ @YCor, both $k$ and $n$ depends on $R$. I added this, hope it's clear now. $\endgroup$ – Aleksei Kulikov Nov 12 '18 at 19:25
  • $\begingroup$ @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. $\endgroup$ – Aleksei Kulikov Nov 12 '18 at 19:53
  • $\begingroup$ 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. $\endgroup$ – YCor Nov 12 '18 at 20:50
  • $\begingroup$ @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. $\endgroup$ – Aleksei Kulikov Nov 12 '18 at 20:56

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.