MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.