Percolation of words on the hypercubic lattice with one-dimensional long-range interactions

Basic Information

• Paper ID: 2202.13190
• Title: Percolation of words on the hypercubic lattice with one-dimensional long-range interactions
• Authors: Pablo A. Gomes (Universidade de São Paulo), Otávio Lima (Universidade Federal de Minas Gerais), Roger W. C. Silva (Universidade Federal de Minas Gerais)
• Classification: math.PR (Probability Theory)
• Publication Date: February 2022 (arXiv preprint)
• Paper Link: https://arxiv.org/abs/2202.13190

Abstract

This paper investigates the word percolation problem in random environments. Letters 0 or 1 are independently assigned to each vertex according to Bernoulli random variables with parameter $p$. The environment is a graph obtained from independent long-range bond percolation configurations on $\mathbb{Z}^{d-1} \times \mathbb{Z}$ ($d \geq 3$), where each unit-length edge parallel to $\mathbb{Z}^{d-1}$ is open with probability $\varepsilon$, and each length-$n$ edge parallel to $\mathbb{Z}$ is open with probability $p_n$. We prove that if $\sum p_n$ diverges, then for any $\varepsilon$ and $p$, there exists $K$ such that the probability that all words are seen from the origin is close to 1, even if all connections of length greater than $K$ are suppressed.

Research Background and Motivation

Problem Definition

The word percolation problem was introduced by Benjamini and Kesten in a seminal paper. On a graph $G=(V,E)$, each vertex $v \in V$ is independently assigned a random variable $X(v)$ taking values 0 or 1 with probabilities $1-p$ and $p$, respectively. Given a word $\xi = \{\xi_n\}_{n \in \mathbb{N}} \in \{0,1\}^{\mathbb{N}}$, the word $\xi$ is said to be seen from vertex $v$ if there exists a path $(v, v_1, v_2, \ldots)$ such that $X(v_i) = \xi_i$.

Research Significance

1. Theoretical Value: Word percolation is a natural generalization of classical Bernoulli percolation (which degenerates to classical percolation when the word is $(1,1,\ldots)$)
2. Mathematical Challenge: Compared to percolation of "almost all words," percolation of "all words" is technically more difficult
3. Long-Range Interactions: First systematic study of the effects of long-range connections in the word percolation problem

Limitations of Existing Work

• The original Benjamini-Kesten result requires dimension $d > 10$ (all words) or $d > 40$ (all words seen from a single point)
• Existing long-range percolation work primarily focuses on percolation of specific words like $(1,1,\ldots)$
• Lack of theoretical analysis of the "truncation" effect of long-range connections

Core Contributions

1. Main Theorem: Proves that under the condition $\sum_{n=1}^{\infty} p_n = \infty$, for any $p \in (0,1)$, $\varepsilon > 0$, and $\alpha > 0$, there exists $K$ such that the probability that all words are seen from the origin in the truncated model is $> 1-\alpha$
2. Truncation Equivalence: First proves that the infinitude of long-range connections is not necessary for word percolation events to occur—there exists a finite truncation $K$ with equivalent effects
3. Technical Innovation:
   • Develops dynamic coupling techniques linking the long-range model with highly supercritical oriented percolation processes
   • Establishes stochastic domination relationships between truncated long-range percolation and oriented percolation
   • Employs entropy-probability balance arguments to handle joint events over all words
4. Generalized Results: Extends the results of van Enter et al. on specific words to all possible words

Detailed Methodology

Model Setup

Graph Structure: Consider a directed graph $G_d = (\mathbb{Z}^d, E_V \cup E_H)$ on $\mathbb{Z}^d$, where:

• $E_V = \{\langle u, u+ne_d \rangle : u \in \mathbb{Z}^d, n \in \mathbb{N}\}$ (vertical long-range edges)
• $E_H = \{\langle u, u+e_i \rangle : u \in \mathbb{Z}^d, i = 1,\ldots,d-1\}$ (horizontal short-range edges)

Randomness:

• Bond percolation: edge $\langle u,v \rangle$ is open with probability $p_{\|u-v\|}$ (vertical) or $\varepsilon$ (horizontal)
• Vertex assignment: each vertex is independently assigned 0 or 1 with probabilities $1-p$ and $p$, respectively

Truncated Model: Define the $K$-truncated sequence $p_n^K = p_n \mathbf{1}_{n \leq K}$

Core Technique: Dynamic Coupling

Construct inductive sequences $\{A_n, B_n\}_{n \geq 0}$ and function $\psi: A_n \to \mathbb{Z}_+$:

1. Initialization: $A_0 = \{O\}$, $B_0 = \emptyset$, $\psi(O) = 0$
2. Exploration Rule: For the earliest vertex $x_n \in \partial_e A_n \cap B_n^c$, check whether it is a "black point"
3. Black Point Condition: There exists $i \in \{1,\ldots,N\}$ such that:
   • $X(y_n, \psi(y_n)+i) = \xi_{2\|y_n\|+1}$
   • $X(x_n, \psi(y_n)+i) = \xi_{2\|y_n\|+2}$
   • The corresponding vertical and horizontal edges are both open

Key Lemmas

Lemma 1: For sufficiently large $N,M$, the black point process is stochastically dominated by an oriented percolation process with density $\gamma$

Lemma 2: Establishes conditional stochastic domination relationships between the truncated long-range model and oriented percolation

Proposition 1: Entropy-probability balance argument controlling the probability of "bad events"

Main Results

Theorem 1 (Main Result)

In the long-range oriented percolation process on $\mathbb{Z}^d$ with $d \geq 3$, assume $\sum_{n=1}^{\infty} p_n = \infty$. Then for all $p \in (0,1)$, $\varepsilon > 0$, and $\alpha > 0$, there exists $K = K(\{p_n\}, p, \varepsilon, \alpha)$ such that:

$P_p,\varepsilon^K(W_0 = \Xi) > 1 - \alpha$

where $W_0$ is the set of words seen from the origin and $\Xi = \{0,1\}^{\mathbb{N}}$ is the set of all words.

Corollary

By translation invariance, $P_p,\varepsilon^K(W_v = \Xi \text{ for some } v) = 1$, that is: $P_p^{\omega_B}(W_v = \Xi \text{ for some } v) = 1, \quad P_\varepsilon^K\text{-a.s.}$

Proof Strategy

Step One: Event Decomposition

$\{W_0 = \Xi\} \supseteq \bigcap_{m \in \Lambda} D_m$ where $\Lambda = \{4^j : j \in \mathbb{N}\}$, $D_m = \bigcap_{\eta \in \Xi_{4m}} B_m(\eta)$

Step Two: Probability Estimation

Using complement decomposition: $\left(\bigcap_{m \in \Lambda} D_m\right)^c = \bigcup_{m \in \Lambda, m \neq 1} (D_{4m}^c \cap D_m) \cup D_1^c$

Step Three: Entropy Control

Key estimate: $\sum_{m \in \mathbb{N}} P_p,\varepsilon^{N+M}(D_{4m}^c \cap D_m) \leq \sum_{m \in \mathbb{N}} |\Xi_{16m}| a^m \leq \sum_{m \in \mathbb{N}} (2^{32}a)^m$

Since $a$ is arbitrarily small, the series converges.

Technical Innovation Points

1. Multiscale Analysis: Achieves coupling at different scales through partitioning into segments like $L_{4m,2}$
2. Directionality Handling: Distinguishes between $i \in \{1,\ldots,N\}$ and $i \in \{N+1,\ldots,N+M\}$ to avoid dependence issues
3. Stochastic Domination: Employs the Liggett-Steif theorem to establish stochastic domination relationships between oriented percolation and product measures
4. Contour Argument: Uses contour counting techniques on the dual lattice in the proof of Lemma 1

Related Work

Historical Development

• Benjamini-Kesten (1995): Seminal work on word percolation, results for $d > 10$
• Kesten-Sidoravicius-Zhang (1998,2001): Results on triangular lattices and closure graphs
• van Enter-de Lima-Valesin (2016): Truncation results for specific words in long-range percolation
• Nolin-Teixeira-Tassion (2019): Latest results on visibility of all words on $\mathbb{Z}^d$ for $d \geq 3$

Position of This Work

This paper is the first to incorporate long-range interactions into the complete word percolation problem and resolves the fundamental theoretical question of truncation equivalence.

Conclusions and Discussion

Main Conclusions

Proves that under one-dimensional long-range interactions, the occurrence of word percolation does not require truly "long-range" connections—there exists a finite truncation with equivalent effects. This provides a new perspective for understanding the nature of long-range interactions.

Limitations

1. Dimension Restriction: Still requires $d \geq 3$; the two-dimensional case remains unresolved
2. Directionality: Results are limited to oriented percolation; the non-oriented case is more complex
3. Truncation Dependence: The specific value of $K$ depends on all parameters and may be very large

Future Directions

1. Investigate word percolation in the two-dimensional case
2. Extend to non-oriented long-range percolation
3. Obtain more precise estimates of the truncation parameter $K$
4. Study other types of long-range interaction patterns

In-Depth Evaluation

Strengths

1. Theoretical Depth: Resolves a fundamental question in long-range percolation theory
2. Technical Innovation: Dynamic coupling and multiscale analysis techniques have general applicability
3. Complete Results: Not only proves the main theorem but also provides a complete technical framework
4. Clear Exposition: Mathematical statements are precise and proof structure is clear

Weaknesses

1. Limited Applications: Primarily theoretical results with limited direct applicability
2. Technical Complexity: Proofs involve multiple complex lemmas with high technical barriers
3. Parameter Dependence: The specific construction of truncation parameters is somewhat abstract

Impact

• Academic Value: Provides new analytical tools for percolation theory
• Theoretical Contribution: Deepens understanding of the nature of long-range interactions
• Methodological Significance: Dynamic coupling techniques may be applicable to other stochastic models

Applicable Scenarios

This methodology is applicable to:

1. Analysis of other types of long-range percolation models
2. Connectivity problems on random graphs
3. Study of phase transitions in statistical physics

References

The paper cites 15 important references, with key ones including:

• Benjamini & Kesten (1995): Seminal work on word percolation
• van Enter et al. (2016): Truncation results for long-range percolation
• Liggett & Steif (2006): Key techniques for stochastic domination
• Nolin et al. (2019): Latest results on word percolation