# Discrete harmonic analysis with infinite/unbounded number of variables

Is there any study of harmonic analysis for Boolean functions of the form $$f:\{0,1\}^*\to \{0,1\}$$, or $$f:\{0,1\}^\omega\to \{0,1\}$$?

That is, similar notions to standard harmonic analysis of $$\{0,1\}^n$$, but with $$n$$ being either unbounded or (countably) infinite.

To put this in context, consider for example an automaton $$A$$ (either over finite or over infinite words). Has there been any study of e.g., the influence of variables on such functions?

If not, is there a fundamental reason that all definitions break down over such domains? (e.g., compactness issues), or is it purely out of lack of interest?

• Maybe this is more similar to continuous-variable harmonic analysis on a totally disconnected space? Harmonic analysis on Cantor sets has been studied a bit, in various contexts. Geometric analysis on Cantor sets and trees provides some references. An Interesting Cantor Set gives another perspective. Besov spaces etc. has also been considered. But I guess this is far away from what you are looking for? Commented Nov 30, 2020 at 11:31
• @MateuszKwaśnicki - I don't know enough about this to decide if it's too far away, but I'll check. I would indeed be surprised of totally disconnect sets capture the monoid structure of $\Sigma^*$ adequately. Commented Nov 30, 2020 at 11:42
• Yes, no doubt $\{0,1\}^*$ is something different. My comment was about the countable product $\{0,1\}^\omega$ only (and even in that case I guess it is not very useful). Commented Nov 30, 2020 at 11:45
• Indeed, as @MateuszKwaśnicki (I think) suggests, when you talk about harmonic analysis on functions $f : \{0, 1\}^\omega \to \{0, 1\}$, what structure on the domain are you exploiting? If only the topological structure, it literally is harmonic analysis on a Cantor set. (Which you could transpose to harmonic analysis on the $2$-adic integers $\mathbb Z_2$, say, to impose some algebraic structure!) Commented Nov 30, 2020 at 11:50
• One reference for the Harmonic analysis for $f :\{0,1\}^{\mathbb{N}} \to \mathbb{C}$ functions equipped with Haar measure (I would call it dyadic martingale harmonic analysis) is the book of F Schipp, WR, Wade, P Simon, "Walsh series: an introduction to dyadic harmonic analysis". Some key words are: Fourier Walsh series, Cantor group Commented Nov 30, 2020 at 15:56

Harmonic analysis on $$\{0,1\}^{\mathbb{N}}$$ can be different depending on how one enumerates orthonormal basis, so called Walsh functions.

One usually considers Haar measure $$dm$$ on $$\{0,1\}^{\mathbb{N}}$$ which is a probability measure in the following sense: if you have a function $$f :\{0,1\}^{\mathbb{N}} \to \mathbb{R}$$ which depends only on the first $$n$$ variables, say $$f(x_{1}, ... ) =g(x_{1}, \ldots, x_{n})$$ then $$\int_{\{0,1\}^{\mathbb{N}}} f(x)dm(x) = \frac{1}{2^{n}} \sum_{(x_{1}, \ldots, x_{n}) \in \{0,1\}^{n}}g(x_{1}, \ldots, x_{n}).$$ Orthonormal system on $$L^{2}(\{0,1\}^{\mathbb{N}}, dm)$$ is called Walsh system, and perhaps it was first time introduced by Walsh in 1923: this is a certain family of functions on $$\{0,1\}^{\mathbb{N}}$$ taking values $$+1$$ or $$-1$$.

I have seen 4 different enumerations of this family of functions used in the literature (perhaps there are more). The first 3 of them (original Walsh, Paley, and Walsh--Kaczmarz) is well described in the book I provided in the comments, see Section 1.4. The 4th one which I find kind of exceptional is not there.

1. Walsh's original enumeration: Walsh defined his system recursively. Later, it turned out that they can be written as follows: $$\varphi_{n}(x) = (-1)^{\sum_{k=0}^{\infty}(n_{k}+n_{k+1})x_{k+1}}, \quad n \in \mathbb{N},$$ where $$n=\sum_{k=0}^{\infty} n_{k} 2^{k}$$ with $$n_{k} \in \{0,1\}$$, and $$x=(x_{1}, \ldots ) \in \{0,1\}^{\mathbb{N}}$$. In other words $$(n_{0}, n_{1}, \ldots)$$ is the binary representation of the positive integer $$n$$. The system $$\{\varphi_{n}(x)\}_{n\geq 1}$$ is the Walsh's original system. Partial sums $$S_{m}f = \sum_{k=0}^{m} c_{k} \varphi_{k}$$, where $$c_{k} = \int_{\{0,1\}^{\mathbb{N}}}f \varphi_{k} dm$$, converge to $$f$$ in $$L^{p}$$, $$p>1$$. The latter is equivalent to the statement that $$\sup_{n \geq 1}\| S_{n} f\|_{p} \lesssim \|f\|_{p}, \quad 1 Moreover, $$S_{n}f$$ converges a.e. to $$f$$ for any $$f \in L^{p}(\{0,1\}^{\mathbb{N}}, dm)$$ provided that $$p>1$$. This is a consequence of Carleson's maximal inequality $$\|\sup_{n \geq 1} |S_{n} f|\|_{p} \lesssim \|f\|_{p}, \quad 1 Luzin asked in the trigonometric case on the unit circle $$\mathbb{T}$$. Carleson proved for $$p=2$$; Hunt extended to $$1. Billard proved for the original Walsh system for $$p=2$$; Sjölin extended for $$1. Fejer means are bounded, i.e., $$\sup_{n\geq 1}\left\| \frac{S_{1}+...+S_{n}}{n} f\right\|_{p} \lesssim \|f\|_{p}, \quad 1\leq p \leq \infty$$ In the book I provided there is a more "martingale proofs" of these results. Dyadic martingales naturally appear here. For example, $$\{ S_{2^{k}}f\}_{k \geq 0}$$ is a martingale. In fact, $$S_{2^{k}}f = \mathbb{E} (f | \mathcal{F}_{k})$$, where $$\mathcal{F}_{k}$$ is $$\sigma$$-algebra, which is generated by atoms, where atoms are $$I_{k}(x) = \{ y \in \{0,1\}^{\mathbb{N}} : y_{1}=x_{1}, \ldots ,y_{k}=x_{k}\}$$. In probabilistic language you condition on the first $$k$$ variables, and let the tail be the everything. Then, for example, the statement that $$\|\sup_{k \geq 0}|S_{2^{k}} f|\|_{p} \lesssim \|f\|_{p} \quad 1 is exactly Doob's maximal inequality. The book F. Schipp, WR. Wade, P. Simon, "Walsh series: an introduction to dyadic harmonic analysis" provides more martingale techniques. The paper A guide to Calreson's theorem by Chiprian Demeter has more time-frequency analysis introduction.
1. Paley's enumeration (Walsh--Paley functions). In 1932, Paley proposed a different enumeration of Walsh functions $$w_{n}(x) = (-1)^{\sum_{k=0}^{\infty} n_{k}x_{k+1}}, \quad n \in \mathbb{N}.$$ Paley's enumeration perhaps is more close to the classical trigonometric system $$\sin(ns)$$ and $$\cos(ns)$$. We can "identify" $$[0,1)$$ with $$\{0,1\}^{\mathbb{N}}$$ as follows: $$s \in [0,1), \quad s = \sum_{k=1}^{\infty} s_{k} 2^{-k}$$ for some $$s_{k} \in \{0,1\}$$. This identification is not unique, for example, $$\frac{1}{2^{2}}$$ can be written as $$(0,1,0,0,\ldots)$$ and also as $$(0,0,1,1,1\ldots,)$$. Among these two one choose the first one, i.e., when number of 1's terminate starting from some place. Such bad points are not too many, they have zero measure so we do not bother with them. In particular $$\omega_{n}(s)$$ is defined for $$s \in [0,1)$$. Then $$w_{2^{k}}(s) = (-1)^{s_{k+1}} =\mathrm{sign}(\sin(2^{k+1} \pi s)) \approx \sin(2^{k+1} \pi s), \quad s \in (0,1].$$ In general, $$\omega_{n}(s)$$ is close to $$\sin(ns)$$ or $$\cos(ns)$$ depending $$n$$ is even or odd. Frequencies $$\sin(2^{k+1} \pi s)$$ are independent pretty much in the same way as $$\omega_{2^{k}}(s) = (-1)^{s_{k+1}}$$ are independent: Khinchin's inequality holds for both of them $$\| \sum c_{k} \omega_{2^{k}} \|_{2} \asymp \| \sum c_{k} \omega_{2^{k}} \|_{1}$$, and $$\| \sum c_{k} \sin(2^{k+1} \pi s) \|_{1} \asymp \| \sum c_{k} \sin(2^{k+1} \pi s)\|_{2}$$. One has the notion of "dyadic derivative" $$df(x) = 2^{0} \frac{f(x_{1}, x_{2}, \ldots) - f(1-x_{1}, x_{2}, \ldots)}{2}+2^{1}\frac{f(x_{1}, x_{2}, \ldots) - f(x_{1},1-x_{2}, \ldots)}{2}+2^{2} \ldots$$ provided that the sum converges. Perhaps one should call it "dyadic Laplacian" instead of the derivative. One can verify that Walsh--Paley functions are eigenfunctions: $$d\omega_{n}(x) = n \omega_{n}(x)$$. One can study polynomials of degree $$m$$, say finite sums $$x \mapsto \sum_{k=0}^{d} c_{k}\omega_{k}(x)$$, and ask questions similar to Markov--Brother's and Bernstein estimates for such polynomials. One can ask regularity questions: if $$f$$ is regular on $$(0,1]$$ how regular it is on $$\{0,1\}^{\mathbb{N}}$$ with respect to dyadic derivative and vice versa. What happens with partial sums if we have some regularity in terms of dyadic derivatives etc. The results about $$L^{p}$$ convergence of partial sums, Carleson--Hunt theorem also hold for this enumeration.
2. Sneider's enumeration (Walsh-Kaczmarz system) was introduced by Sneider: $$k_{0}(x) =1, \quad k_{n}(x) = (-1)^{x_{A}+\sum_{k=0}^{A-1} n_{A-k-1}x_{k+1}}\quad \text{where} \quad 2^{A}\leq n < 2^{A+1}$$ I won't say much about this system except that the same $$L^{p}$$ convergence theorems hold in this case. Perhaps an interesting observation in all these 3 enumerations is that Dirichlet Kernels $$D_{n}(x) = \sum_{k=0}^{n-1} a_{n}(x)$$ where $$a_{n}$$ is either Walsh, Walsh--Paley, Walsh--Kaczmarz, for $$n=2^{k}$$ are the same. In fact $$D_{2^{k}}(x) =\prod_{j=1}^{k}(1+(-1)^{x_j})$$.

Frequencies: when working with these 3 enumerations one usually thinks that $$a_{n}(x)$$ is "high-frequency" element if $$n$$ is large, and "low-frequency" element if $$n$$ is small. For example $$\omega_{2^{k}}(x) = (-1)^{x_{k+1}}$$ for large $$k$$ are high frequency elements similar to $$\sin(2^{k+1}\pi s)$$. All these 3 enumerations and concepts of frequencies tend to mimic the harmonic analysis on $$L^{p}(\mathbb{T}, d\theta)$$, where $$d\theta$$ is the uniform measure on the unit circle, i.e., trigonometric polynomials.

1. Probabilistic enumeration (from independent towards dependent). In this enumeration the concept of "high/low frequencies" is changed in a very opposite way. In fact, the elements $$\{ \omega_{2^{k}}(x)\}_{k \geq 0}$$ will be the lowest frequencies, say frequencies of degree $$1$$. Elements $$\omega_{n}(x)$$ where $$n$$ has two bits in its binary representation will be frequencies of order $$2$$. These are precisely Walsh functions $$(-1)^{x_{i}+x_{j}}$$, $$i. In a certain sense enumeration starts from "independent frequencies to dependent ones", and probabilistic ideas, measure concentration phenomena, dimension independent phenomena, and the concept of "independence" happen to be useful. The goal is to represent functions $$f : \{0,1\}^{\mathbb{N}} \to \mathbb{R}$$ as follows: $$f(x_{1},x_{2}, \ldots) = c_{0} + \underbrace{c_{1}(-1)^{x_{1}}+c_{2}(-1)^{x_{2}}+\ldots+c_{i}(-1)^{x_{i}}+\ldots}_{\mathrm{linear\; terms}}+\underbrace{c_{12}(-1)^{x_{1}+x_{2}}+c_{13}(-1)^{x_{1}+x_{3}}+\ldots+c_{ij}(-1)^{x_{i}+x_{j}}+\ldots}_{\mathrm{second\, order\, terms}}+\mathrm{higher\, order \, terms} \quad (1)$$ Of course, if one takes $$f \in L^{2}(\{0,1\}^{\mathbb{N}}, dm)$$, writes into Walsh--Paley system $$f(x) = \sum_{n\geq 0} a_{k} \omega_{k}(x)$$, and wants to rearrange the terms to write in the form (1) then rearranged infinity sums may give different results unless $$\sum |a_{n}| <\infty$$ which is very unlikely for a "typical" $$f \in L^{2}$$. However, if one considers functions $$f$$ which depend only on the first $$n$$ variables the rearranged sums will be the same. This is not a big restriction on the class of functions because when one wants to prove a statement for functions on $$\{0,1\}^{\mathbb{N}}$$ one does not start with $$f \in L^{2}$$ which depends on all its variables, one starts from a "finite dimensional problem" when $$f$$ depends only on the first $$n$$ variables, and one proves the corresponding statements for such functions, requires the constants involved in the statement to be independent of $$n$$, and then passes to a limit, i.e., to an infinite dimensional problem. Thus if we consider functions $$f$$ which depend only on the first $$n$$ variables then $$f(x_{1}, \ldots, x_{n}) = c_{0}+c_{1}(-1)^{x_{1}}+\ldots +c_{n}(-1)^{x_{n}}+\sum_{1\leq i The latter notation seems to be compact and convenient. Here $$a_{S}$$ are Fourier coefficients, and $$(-1)^{\sum_{j \in S} x_{j}}$$ are Walsh functions (enumerated in a strange way) indexed by the sets $$S$$. Since this enumeration works well provided that $$f$$ depends only on finite number of variables, the questions about $$L^{p}$$ convergence, Carleson--Hunt theorem etc do not make any sense. So the direction of harmonic analysis in which Luzin was interested ends here. Well, one can still consider partial sums $$S_{d} f (x) = \sum_{\substack{S \subset \{1, \ldots, n\}\\ |S|\leq d}} a_{S} \, (-1)^{\sum_{j \in S} x_{j}},$$
where $$|S|$$ denotes the cardinality of the set $$S$$, and ask similar questions $$\| S_{d} f\|_{p} \lesssim \|f\|_{p}$$ with uniform bound for all $$d$$, $$1\leq d \leq n$$, for all $$n\geq 1$$, and all $$f$$ depending on the first $$n$$ variables. Such estimate holds if and only if $$p=2$$. Interesting connection arises with Gauss space. For example $$\frac{\ell!}{n^{\ell/2}} \sum_{\substack{S \subset\{1, \ldots, n\}\\ |S|=\ell}} (-1)^{\sum_{j \in S} x_{j}} \stackrel{d}{\to} H_{\ell}(\xi)$$ where $$H_{\ell}$$ is degree $$\ell$$ probabilists' Hermite polynomial, $$\xi \in \mathcal{N}(0,1)$$ is the standard normal Gaussian random variable, and the convergence is in the sense of distributions. By Taking tensor products of the above example one recovers Hermite polynomials on $$\mathbb{R}^{N}$$ with arbitrary $$N$$. So, because of this limit, it is reasonable to think about $$(-1)^{\sum_{j \in S} x_{j}}$$ as low frequency element if $$|S|$$ is small, and high frequency element if $$|S|$$ is large (which is very opposite compared to the original Walsh enumeration). In fact, the analysis with such enumeration (1) for functions $$f$$ depending on $$n$$ variables is similar to the one on $$L^{p}(\mathbb{T}^{n}, d\theta^{n})$$. Dscrete Laplacian is defined in a different way $$\Delta f(x) = \sum_{j=1}^{n} D_{j}f(x),$$ where $$D_{j}f(x_{1}, \ldots, x_{n}) = \frac{f(x_{1}, \ldots,x_{j}, \ldots, x_{n})-f(x_{1}, \ldots, 1-x_{j}, \ldots, x_{n})}{2}$$. One also considers discrete gradient $$Df(x) = (D_{1} f(x), \ldots, D_{n}f(x)).$$ One has integration by parts formula $$\int_{\{0,1\}^{\mathbb{N}}} g \Delta f dm=\int_{\{0,1\}^{\mathbb{N}}} Df \cdot Dg\, dm$$ for all functions $$f,g$$ depending on the first $$n$$ variables. Heat semigroup
$$e^{-t\Delta} f = \sum_{S \subset \{1, \ldots, n\}}a_{S} e^{-t|S|} (-1)^{\sum_{j\in S}x_{j}}$$ satisfies heat equation $$\frac{\partial }{\partial t} e^{-t\Delta}f = -\Delta e^{-t\Delta}f$$. Discrete gradient $$|\nabla f|(x) = \sqrt{\sum_{j=1}^{n} |D_{j}f(x)|^{2}}$$ when applied to $$f(x_{1}, \ldots, x_{n}) = g\left(\frac{(-1)^{x_{1}}+\ldots+(-1)^{x_{n}}}{\sqrt{n}}\right)$$ for some smooth bounded $$g :\mathbb{R} \to\mathbb{R}$$, converges to the classical derivative
$$\int_{\mathbb\{0,1\}^{\mathbb{N}}} M(|\nabla f|(x)) dm(x) \stackrel{n \to \infty}{\to} \int_{\mathbb{R}}M(|g'(s)|) \frac{e^{-s^{2}/2}}{\sqrt{2\pi}}ds$$ for any smooth functions $$M$$. The case $$M(t)=|t|^{p}$$ is a typical application. Denoting $$(-1)^{x_{j}} = \varepsilon_{j}$$, then $$\ell$$ degree polynomials with respect to this enumeration can be written as $$g(\varepsilon_{1}, \ldots, \varepsilon_{n}) =\sum_{\substack{S \subset \{1, \ldots, n\} \\ |S|\leq \ell}} a_{S} \prod_{j \in S} \varepsilon_{j}$$ and the latter expression can be extended in a natural way for all $$\varepsilon_{1}, \ldots, \varepsilon_{n} \in \mathbb{R}$$ as a multilinear classical polynomial in $$n$$ variable of degree $$d$$. Due to the identity $$\| g\|_{L^{\infty}([-1,1]^{n})} = \| g\|_{L^{\infty}(\{-1,1\}^{n})}$$ tools from approximation theory enter in an unexpected way applied to actual degree $$\ell$$ multilinear polynomials. Discrete derivatives coincide with the actual derivatives for such multilinear polynomials. Boolean functions $$f :\{0,1\}^{\mathbb{N}} \to \{0,1\}$$ have an extra property $$f^{2}=f$$ and this gives more cancelations when proving statements for all real valued functions.

To summarize: Harmonic analysis on $$\{0,1\}^{\mathbb{N}}$$ depends on how one encodes Walsh functions, i.e., frequencies in the Hilbert space $$L^{2}(\{0,1\}^{\mathbb{N}}, dm)$$, who are the low and who are the high frequency functions.

• This is a fantastic answer! Unfortunately, my setting fails the basic premise: functions defined by automata very much depend on infinitely many coordinates. Can anything be said in this case? For example, the function that assigns 1 to all infinite sequences that have infinitely many 1's, and 0 otherwise. Commented Dec 4, 2020 at 8:11