Counting distinct functional graphs from linear finite dynamical systems

Abstract

Let ${\mathbb{F}}_q$ be the finite field with $q$ elements and, for each positive integer $n$, let $A_q(n)$ be the number of non isomorphic functional graphs arising from ${\mathbb{F}}_q$-linear maps $T:{\mathbb{F}}_q^n\to {\mathbb{F}}_q^n$. In 2013, Bach and Bridy proved that, if $q$ is fixed and $n$ is sufficiently large, the quantity $\frac{\log \log A_q(n)}{\log n}$ lies in the interval $[\frac{1}{2},1]$. By combining some ideas from linear algebra, combinatorics and number theory, in this paper we provide sharper estimates on the function $A_q(n)$ and, in particular, we prove that $\underset{n\to +\infty }{\lim }\frac{\log \log A_q(n)}{\log n}=1$ for every prime power $q$.

10 pages, comments are welcome!