5
$\begingroup$

I am interested in recognising graphs (or matrices, or subshifts of finite type) using topological pressure. Suppose that we play the following game:

${\bf Step 1:}$ I write down an irreducible n x n matrix A of zeroes and ones, which I ask you to try and work out. I tell you what n is.

Let $\sigma$ be the left shift on $\Sigma=\{1,2,..,n\}^{\mathbb N}$ and $\sigma_A$ be the left shift on $\Sigma_A$, which is the shift space corresponding to incidence matrix A.

${\bf Step 2:}$ You think of a function $f:\Sigma\to\mathbb R$ and ask me what the value of the topological pressure $P_{\sigma_A}(f|_{\Sigma_A})$ is. I tell you the answer. Repeat step 2 until you can tell me what A is.

${\bf Question:}$ How many times do you have to repeat step 2 before you know the matrix A?

It's easy to see that $n^2$ is enough. Define $f_{i,j}(\underline a) = 1$ if $a_1=i$, $a_2=j,$ 0 otherwise. Then $P_{\sigma_A}(f_{ij}|_{\Sigma_A})$ is different from $h_{top}(\sigma_A)$ if and only if $A_{ij}=1$. You don't know what $h_{top}(\sigma_A)$ is, but you can work this out from the topological pressure information.

Can we do any better? I'm particularly interested in the situation where you are only allowed to pick locally constant functions f, but the general case is also interesting. One could make minor improvements to the above idea to reduce $n^2$, but I'm really interested in whether there is a constant k independent of n such that we can always determine an n x n matrix by knowing k pressure functions.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ If we were to insist that $f$ should be of the form $f_{i,j}$ above then this would correspond to a matrix analysis question: but what question, exactly? How hard is that question, and does it give us any information? (I'm just thinking out loud here.) $\endgroup$
    – Ian Morris
    Nov 22, 2013 at 15:50
  • 2
    $\begingroup$ First, you should allow me to assume that $A$ is irreducible. Otherwise there are some words you only see at most once, and you can never tell what $f$ is like on places you only see once. Given this, I think you must be able to do this with one $f$. Here's how I'd try: Choose $x_1\ll x_2 \ll x_3 \ll x_4\ll\ldots\ll x_{n^2}$, order the edges and let the function be the sum of the $x_i$'s corresponding to the edges. By $\ll$ here I mean there's a really really massive additive difference between the $x$'s. $\endgroup$
    – Anthony Quas
    Nov 22, 2013 at 17:24
  • $\begingroup$ Thanks for your answers. Ian, I'm constantly finding questions that I think should be easy if only I knew more matrix analysis... Anthony, yes sorry I should have written irreducible rather than aperiodic, and after a bit of thought I think I believe that your approach ought to work. Thanks! $\endgroup$
    – Tom Kempton
    Nov 25, 2013 at 8:28

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.