My question is somewhat related to this question.

Let us fix natural numbers $k$ and $C$. Let $A$ be an automaton whose alphabet consists of $k\times k$ matrices with integer coefficients of absolute value at most $C$.

We will say that an $n\times n$ matrix $M$ is recognized by $A$ iff the following three conditions hold: (1) $n\ge k$, (2) $M$ has non-zero coefficients only in $k$-neighbourhood of the diagonal, and (3) the word consisting of subsequent $k\times k$ minors of $M$ along its diagonal is recognized by $A$.

Let $\mathcal M = \mathcal M(A)$ be the set of all matrices recognized by $A$. For a given matrix $M$ let $d(M)$ be the dimension of $M$ (i.e. number of rows of $M$.) Consider the "generating function" of $\mathcal M(A)$:

$$ F_{\mathcal{M}}(x) := \sum_{M\in \mathcal M} \dim\ker M \cdot x^{d(M)} $$

Question: What can be said about $F_{\mathcal{M}}$?

Let me be more precise. It is not difficult to see, using the standard result on regular languages, that the function $F(x) := \sum_{M\in \mathcal M} x^{d(M)}$ is rational over $\mathbb Q[x]$. It follows from this preprint that this is not the case for $F_{\mathcal{M}}$: using finite graphs $j(k,l)$ from that paper one can easilly construct an automaton $A$ such that the corresponding generating function $F_{\mathcal M(A)}$ has the property that $$ F_{\mathcal M(A)}(\frac{1}{2}) = p + q\cdot \sum_{k=1}^\infty \frac{1}{2^{k+2^k}}, $$ where $p$ and $q$ are non-zero rationals. This number is known to be transcendental.

An example answer which I would be very happy to get is that $F_{\mathcal M}$ is either rational or transcendental over $\mathbb Q[x]$ and in fact also over $\mathbb C [x]$.

I'd be ecstatically happy if somebody was able to prove that actually $F_{\mathcal M}(p)$ is either a rational or a transcendental number whenever $p\in \mathbb Q$.

Also, I'd be interested in any kind of description of possible values of $F_{\mathcal M}$ on rational numbers (even if it doesn't easilly follow from it that $F_{\mathcal M}(p)$ is either rational or transcendental.) For example, I'm convinced that one can generalize this preprint to get numbers of the form
$$ p + q\cdot \sum_{k=1}^\infty \frac{1}{2^{a(k)}}, $$ where $a(k)$ is an automatic sequence of natural numbers (i.e. there exists automaton whose language is the language of binary expansions of elements of the sequence $a(k)$). Can one get more? Yes, because e.g. $2^k+k$ is not automatic, but it is a sum of such sequences. Can one get even more?

The motivating problem for me is to understand the set of so called $l^2$-Betti numbers which arise from the lamplighter groups $\mathbb Z/p \wr \mathbb Z$. See this preprint again and references there for more on this motivation.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.