This question regards colourings on edges and vertices on countable directed multigraphs. We start with an example. Let $G=\mathbb Z^2$. We define two functions $a_h$ and $a_v$ from $\mathbb Z^2$ to $\mathbb C$ with the property that for all $\epsilon>0$, $$ \{(n,m)\in\mathbb Z^2 : |a_h(n,m)a_v(n+1,m)-a_v(n,m)a_h(n,m+1)|>\epsilon\} $$ is finite.

We want to assume as well that both $a_h$ and $a_g$ take only values of absolute value 1 (or that they're bounded, both questions are interesting I think).

The question is: can we find a function $d : \mathbb Z^2\to\mathbb C$ such that $d$ agrees asymptotically with $a_h$ and $a_v$, meaning that for all $\epsilon>0$ $$ \{(n,m) :|d(n+1,m)-d(n,m)a_h(n,m)|>\epsilon\} $$ and $$\{(n,m) : |d(n,m+1)-d(n,m)a_v(n,m)|>\epsilon\} $$ are finite?

How is this related to graphs? Draw a picture of $\mathbb Z^2$, and colour in blue the directed vertical edge $(n,m)\to (n,m+1)$ and in red the horizontal ones going right. In this setting, we can think as the functions $a_h$ and $a_v$ as $\mathbb C$-valued weights on the edges, with the property that, asymptotically, one can go first right and then up, or first up and then right, and get the same result when multiplying the weights.

The question then transfers to:

Can we weigh the vertices so that, asymptotically, the pattern of the weights of the vertices is determined by the one of the edges?

Let's formalize this connection.

Let $V$ be a set, and suppose that we have partial functions (either finitely or countably many) $s_i: V \to V$, with domain $D(s_i)$.

If $\bar t=t_n...t_1$ is a finite word in $\{s_i\}$, we can think as $\bar t$ as a partial function $\bar t: V \to V$. Its domain is $$ D(\bar t)=\{x \in D(t_1): t_i(t_{i-1}(...(t_1(x)..) \in D(t_{i+1}), \; \forall i <n\}. $$ If $\bar t$ and $\bar t'$ are finite words in $\{s_i\}$, let $$ D(\bar t,\bar t')=\{(x,y): x \in D(\bar t) \cap D(\bar t') \text{ and }\bar t(x)=y=\bar t'(x)\} $$

Suppose that for every $i$, a weight function $$ a_i: D(s_i) \to\mathbb C $$ is given. We also assume that $|a_i(x)|=1$ for all $a\in D(s_i)$. Define $a_{\bar t}: D(\bar t)\to \mathbb C$ by taking the product (i.e., if $\bar t=t_n...t_1$ then $a_{\bar t}(x)=\prod_{1\leq i\leq n} a_i(t_{i-1}(\cdots(t_1(x))\cdots))$), and assume asymptotic coherence, that is, for all $\bar t, \bar t'$ words in $\{s_i\}$, and $\epsilon>0$, the set $$ \{(x,y) \in D(\bar t,\bar t') : |a_{\bar t}(x)- a_{\bar t'}(x)|>\epsilon\} $$ is finite.

Is there an assignment $d: V \to\mathbb C$ such that for all $i$ and $\epsilon>0$, the set $$ \{x : |d(s_i(x))-a_{s_i}(x)d(x)|>\epsilon\}$$ is finite? (This can all be turned in a graph setting, by drawing a directed edge on colour $i$ between $x$ and $y$ whenever $s_i(x)=y$.).

This has a positive answer in case the graph is a tree.

In particular, given a countable group $G$ generated by a subset $S$, we can ask this particular question about the Cayley graph of $(G,S)$. We obtain a positive answer to this question if $G=\mathbb F_n$, the free group on $n$ generators and $s_i: V\to V$ is the multiplication by the $i$-th generator. In general, there is a positive answer to this question (i.e., we can find $d$), whenever the corresponding graph is a tree. In this case, to define $d$ is enough to give value $1$ to a specified vertex, and then to "follow the tree" using $a_{s_i}$.

A more complicated setting in which this can fit is the one of discrete (semi)groups actions. If $X$ is any set, and $G$ is a (semi)group action, we can construct maps $s_i$ for every element of $G$, by using the action of $G$ on $X$. In this setting, our situation is really a lot reminiscent of "asymptotic untwisting of cocycle", and we have the strong suspect that a positive, or negative, answer might be dependent the structure of the action, or of the semigroup itself.

Thanks in advance,

  • $\begingroup$ The function $d=0$ works. Maybe you want to assume that $d$ is valued in $\mathbf{C}^*$? $\endgroup$
    – YCor
    Dec 23, 2018 at 6:27

1 Answer 1


There indeed exists $a$ on $\mathbf{Z}^2$, valued in $\mathbf{U}$, the unit circle in the complex plane, such that no $d$ (valued in $\mathbf{C}^*$) works.

When all functions ($a_h$, $a_v$, $d$) are assumed to have values in $\mathbf{U}$, the question can be rephrased so as only to rely on the structure of topological group of $\mathbf{U}$. (Indeed, for $a,b,c,d$ complex numbers of modulus $1$, we have $|ab-cd|=|abc^{-1}d^{-1}-1|$.)

Therefore, let me rephrase in additive terms. Let $(A,+)$ be a topological group (e.g., $\mathbf{R}/\mathbf{Z}\simeq\mathbf{U}$). Fix an oriented graph (e.g., the standard Cayley graph of $\mathbf{Z}^2$). Let $V$ be the set of vertices, and let $E$ be the set of oriented edges. For $e\in E$, write $e_+$ an $e_-$ its target and origin. Call square a quadruple of edges $s=(e,f,g,h)$ such that $e_-=g_-$, $f_+=h_+$, $e_+=f_-$, $g_+=h_-$.

For $a:E\to A$, write $a[s]=a(e)+a(f)-a(g)-a(h)$. Let $C$ be the space of those $a$ such that $a[s]$ tends to zero when $s\to\infty$ (in the sense that for every neighborhood $W$ of $0$ in $A$ the number of squares $s$ such that $a[s]\notin W$ is finite).

For $d:V\to A$, write $\nabla d(e)=d(e_+)-d(e_-)$, so $\nabla d$ is a function from $E$ to $A$. For $a\in C$, let $B_a$ be the set of functions $d:V\to A$ such that $(\nabla d)-a$ tends to zero (in the sense that for every neighborhood $W$ of $0$ in $A$, the set of $e$ such that $d(e_+)-d(e_-)-a(e)\notin W$ is finite).

Fact: for the standard oriented Cayley graph of $\mathbf{Z}^2$, and $A$ equal to $\mathbf{R}$ or $\mathbf{R}/\mathbf{Z}$, there exists $a\in C$ such that $B_a$ is empty.

Define $a(e)=0$ for $e$ vertical. For horizontal $e$ joining $(m,n)$ to $(m+1,n)$, define $a(e)=0$ if $|n|\ge m$, and $a(e)=(m-|n|)/m$ of $|n|<m$. That $a[s]$ tends to $0$ when $s\to\infty$ is readily checked.

Suppose by contradiction that $d\in B_a$. Since $a=1$ on the edges in the right axis $y=0$, $x\ge 0$, we have $d(m,0)=m+o(m)$ for $m\to +\infty$. But using that we can go from $(0,0)$ to $(m,0)$ with the path of length $3m$ $$(0,0)-\!\!\!\!-(0,1)-\!\!\!\!-(1,1)-\!\!\!\!-(1,2)-\!\!\!\!-\dots -\!\!\!\!-(m-1,m)-\!\!\!\!-(m,m)-\!\!\!\!-(m,m-1)-\!\!\!\!-\dots -\!\!\!\!-(m,0),$$ all of whose edges are labeled by $0$, we have $d(m,0)=o(m)$. This yields a contradiction.

This settles the case when $A=\mathbf{R}$. Next, for convenience, we work in $A=\mathbf{R}/10\mathbf{Z}$. Things seem at first sight not to work, since these functions are defined up to addition by (10$\times$integral)-valued functions so growth arguments do not make sense. But indeed, outside a finite rectangle, all $\epsilon$ are, say, $\le 1$, and we can check that there are unique ways to lift paths and homotopies once initialized. Hence the lift of $d$ is defined modulo addition by an integral constant, and the estimates makes sense, and actually hold, by easy arguments (I skip details), and we get the same contradiction.

Now working multiplicatively (so we work with $a'=\exp(2i\pi a/10)$, for $a$ as above), this shows that no $d$ valued in $\mathbf{U}$ works. Hence, by an obvious projection argument, no $d$ valued in $\mathbf{C}^*\simeq\mathbf{U}\times\mathbf{R}$ works.


Your Answer

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

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