Abstract:
Multivariate Haar functions are constructed on $R^d$ with an arbitrary integer dilation
expansive $d\times d$ matrix $M$ with a certain set of $m = |\mathrm{det} M|$ "digits" from the corresponding
quotient subsets of $Z^d$. Unlike the univariate case, there are many different Haar systems
on $R^d$, they may have various smoothness depending on the matrix $M$ and on the set of
digits. Computation of their Hölder regularity in $L_2$ is notoriously hard problem.
A formula for the Hölder exponent in case of general dilation matrices was recently
obtained in [1]. We show that the $L_2$ Hölder exponent of a Haar function can be expressed
by the boundary dimension of its support $G$. This is an analogue to the Hausdorff
dimension of the boundary, but do not coincide with it. Moreover, the same value has
a rather surprising interpretation in terms of the problem of synchronizing automata. A
finite automata is determined by a directed multigraph with $N$ vertices (states) and
with all edges (transfers) coloured with $m$ colours so that each vertex has precisely
one outgoing edge of each colour. The automata is synchronizing if there exists a finite
sequence of colours such that all paths following that sequence terminate at the same
vertex independently of the starting vertex. The problem of synchronizing automata has
been studied in great detail (see [2] for a survey). It turns out that each Haar function can
be naturally associated with a finite automata and the Hölder exponent is related to the
length of the synchronizing sequence. We introduce a concept of synchronizing rate and
show that it is actually equal to the Hölder exponent of the corresponding Haar function.
Applying this result we prove that the Hölder exponent can be found within finite time
by a combinatorial algorithm.
