Pith. sign in

REVIEW 3 major objections 4 minor 32 references

Large Deviations of Cover Time of Tori in Dimensions $d\geq 3$

T0 review · 3 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper proves that for a simple random walk on $(\mathbb{Z}/N\mathbb{Z})^d$ with $d\ge 3$, the probability of covering the torus by time $\gamma$ times its expected cover time is $\exp(-(1+o(1))N^{d(1-\gamma)})$ for…

desk verdict Likely resolves the conjectured large-deviation exponent for torus cover times in d≥3, with a new sharp asymptotic, but one load-bearing lemma is asserted rather than proved. read the letter →

arxiv 2411.16398 v3 pith:7QX2L5DO submitted 2024-11-25 math.PR

Xinyi Li , Jialu Shi , Qiheng Xu This is my paper · ORCID
classification math.PR MSC 05C8160F1060G70
keywords randomwalkcovertimelargedeviationsinterlacementsdiscretetoruslatepointsloopinsertionstrongcoupling
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Simple random walk on the discrete torus $(\mathbb{Z}/N\mathbb{Z})^d$, $d\ge 3$, typically covers every site by time $t_{\rm cov}=g(0)N^d\log(N^d)$. This paper studies how unlikely it is to finish noticeably earlier, at time $\gamma t_{\rm cov}$ for $\gamma\in(0,1)$. Its main theorem shows that for $\gamma\in((d+2)/(2d),1)$ the probability is $\exp(-(1+o(1))N^{d(1-\gamma)})$; combined with the existing upper bound, the same exponential order $\exp(-N^{d(1-\gamma)+o(1)})$ holds for every $\gamma\in(0,1)$. The proof supplies sharp large-deviation lower bounds by coupling the random walk trace to random interlacements and by inserting recoverable loops into the trajectory to cover late points near the edge.

What carries the argument

The machinery is the strong coupling between the trace of a simple random walk on the torus up to time $uN^d$ and the trace of random interlacements at level $u$ in the same region (Proposition 1.5). Random interlacements are a Poissonian cloud of bi-infinite simple random walk trajectories on $\mathbb{Z}^d$, with the property that the probability a finite set $K$ is avoided is $\exp(-u\,\mathrm{cap}(K))$. The coupling gives simultaneous inclusions $I^{u(1-\rho)}\cap Q_\delta \subset X[0,uN^d]\cap Q_\delta \subset I^{u(1+\rho)}\cap Q_\delta$, up to an error term $C N^{2d}\lceil uN^{d-2}\rceil\exp(-c\rho\sqrt{uN^{d-2}})$. The lower-bound proof then combines this coupling with Harris-FKG to cover the bulk late points and with a deterministic loop-insertion surgery to cover the edge late points, adding loops whose total length is of order $N^{d(1-\gamma)}$ and which can be uniquely deleted from the modified trajectory.

What would settle it

For $d=3$ and $\gamma=0.9$ (above the sharp-range threshold $5/6$), estimate $\log P(C_N\le 0.9\,t_{\rm cov})/N^{0.3}$ by Monte Carlo for $N=20,40,60$; the theorem predicts this ratio approaches $-1$, so a systematic deviation would contradict the claimed asymptotic. On the theoretical side, proving or refuting the stronger coupling error $\exp(-c\rho^2 uN^{d-2})$ would settle whether the sharp range can be extended to $\gamma>2/d$.

Watch

Extended reading notes

Core claim

The central claim is Theorem 0.1: for $\gamma\in((d+2)/(2d),1)$, $$\lim_{N\to\infty}\frac{\log P(C_N\le \gamma t_{\rm cov})}{$N^{{d(1-\gamma)}}$}=-1,$$ where $C_N$ is the cover time of the torus and $t_{\rm cov}=g(0)N^d\log N^d$. Equivalently, $P(C_N\le \gamma t_{\rm cov})=\exp(-(1+o(1))N^{d(1-\gamma)})$. The paper also proves a matching lower bound for the whole range $\gamma\in(0,1)$ (Theorem 0.2), which together with the known upper bound yields the full-rate statement $P(C_N\le \gamma t_{\rm cov})=\exp(-N^{d(1-\gamma)+o(1)})$ for all $\gamma\in(0,1)$ (Corollary 0.3).

Load-bearing premise

The proof depends on an approximation of the random walk's path by a Poissonian cloud of infinite random walk trajectories, and the approximation must be accurate enough that its error is negligible compared with the tiny probability being computed; this accuracy only holds when $\gamma$ is larger than $(d+2)/(2d)$.

Editorial extensions

If this is right

  • For $\gamma\in((d+2)/(2d),1)$, the probability of early cover has the sharp asymptotics $\exp(-(1+o(1))N^{d(1-\gamma)})$.
  • For every $\gamma\in(0,1)$, $P(C_N\le \gamma t_{\rm cov})=\exp(-N^{d(1-\gamma)+o(1)})$, closing the exponent for the full large-deviation regime.
  • Upward deviations satisfy $P(C_N\ge \gamma t_{\rm cov})=(1+o(1))N^{-d(\gamma-1)}$ for $\gamma>1$.
  • For random interlacements on a cube, the paper sketches the analogous sharp rate $P(M_N\le \gamma u_N)=\exp(-(1+o(1))N^{d(1-\gamma)})$ for $\gamma\in(2/d,1)$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the strong-coupling error were improved to $\exp(-c\rho^2 uN^{d-2})$, the same strategy would extend the sharp range from $\gamma>(d+2)/(2d)$ down to $\gamma>2/d$; the paper identifies this error as the main obstacle.
  • The rate constant 1 in the exponent is consistent with a simple heuristic: at the cover threshold there are of order $N^{d(1-\gamma)}$ untouched sites, each missed with probability about $e^{-1}$, giving the same exponential rate as independent miss events.
  • The loop-insertion surgery is a general combinatorial device that could also be applied to the maximal-local-time large-deviation question on $\mathbb{Z}^d$ raised in the paper, where the analogous conjecture is $\exp(-N^{1-\gamma+o(1)})$.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper studies downward large deviations of the cover time C_N of the discrete torus (Z/NZ)^d, d ≥ 3, by simple random walk. The main result, Theorem 0.1, states that for γ in ((d+2)/(2d), 1), the probability that C_N ≤ γ t_cov, with t_cov = g(0)N^d log N^d, satisfies log P(U_{γ,N}) / N^{d(1-γ)} → -1. The proof combines the recently developed strong coupling between the random walk trace and random interlacements (Prévost–Rodriguez–Sousi) with a four-stage lower-bound construction: late-point regularity, bulk coverage via interlacements, explicit loop-insertion surgeries for the edge, and final free roaming. The paper also states Theorem 0.2, a lower bound of the form exp(-C N^{d(1-γ)}) for all γ ∈ (0,1), and Corollary 0.3, which upgrades this to exp(-N^{d(1-γ)+o(1)}) using a sketched upper bound (0.6). Appendix B sketches a related sharp asymptotic for the cover level of random interlacements on cubes.

Significance. If the proof is completed, Theorem 0.1 would be the first sharp large-deviation prefactor for the cover time of tori in dimensions d ≥ 3, matching the conjecturally correct exponent from the upper bounds of Goodman–den Hollander and Comets–Gallesco–Popov–Vachkovskaia. The paper articulates clearly why the threshold γ > (d+2)/(2d) arises from the coupling error in Proposition 1.5, and it honestly notes that an improved coupling would extend the range. The deterministic loop-insertion surgery in Section 4 is an interesting and potentially reusable construction, and the upper-bound argument in Section 2 is concrete, with explicit error terms. The main weakness is that a load-bearing technical lemma on late points, Lemma 1.7, is asserted as a generalization of a result from [26] without proof; several auxiliary statements are also only sketched. These gaps are acknowledged in the text but are not merely cosmetic, because the lower bound of Theorem 0.1 depends on the uniformity in α stated in Lemma 1.7.

major comments (3)
  1. [§1.3, Lemma 1.7 and Lemma 1.9] Lemma 1.7 is stated as a uniform generalization of [26, Lemma 6.1] to all α ∈ [α0, α1] with error O((log N)^{3/2}/N^{(d-2)/2}), but no proof is given; the text only says that the proof 'still goes through.' This is load-bearing for Theorem 0.1: Lemma 1.9 uses (1.17) to sum two-point probabilities over ~N^{2d} pairs, Lemma 1.8 derives the concentration of |L_α^F| from Lemma 1.9, and Lemma 3.4 together with Propositions 3.5 and 3.7 use that concentration to control the event E1 and hence the event E in Proposition 3.1. Since α_N = γ - K/(d g(0) log N) varies with N and approaches γ, the uniformity in α at the stated rate is exactly what the lower bound needs; a weaker uniformity could introduce logarithmic factors into (1.20), destroying the o(1) in Lemma 1.9 and the concentration estimate (1.19). Please provide a complete proof of the uniform version of Lemma 1.7, or state the precise hypotheses that the application requires and verify them.
  2. [§3.2, proof of Proposition 3.1] The proof of Proposition 3.1 invokes 'the weaker version of Proposition 3.6 with d∞(x, X[0,4εN^d - 1]) in place of r^{3ε}_x,' but Proposition 3.6 and its proof are written only for the 3ε time scale, while the event E3 in (3.10) concerns the interval (T2, T3] of length 4εN^d. Since Proposition 3.1 is the key exponential estimate for the lower bound in Theorem 0.1, the version actually used must be stated and proved. Please state the 4ε analogue of Proposition 3.6 and give the short adaptation of the proof of Proposition 3.7, or adjust the parameters so that the statement matches the proof.
  3. [§3.3, Lemma 3.8 and Theorem 0.2] Lemma 3.8, which asserts the existence of a high-probability event E′ with the required regularity and distance bounds, is stated with 'We omit the proof.' Theorem 0.2 rests entirely on this lemma together with Proposition 3.3, so the proof cannot be omitted from a formal paper. Please include a full proof, or a precise reduction to Lemmas 1.8 and 1.9 with all constants and uniformity statements tracked.
minor comments (4)
  1. [§2 and Appendix B, definition of K_N] The definition K_N = Q(0, N^{1+δ}) ∩ (s_N Z)^d appears to be a typo: with this cube, the claimed properties that K_N is (1+δ)R_N-well separated and that Q(x, R_N) ⊂ Q_{δ/2} for all x ∈ K_N fail, and the count |K_N| ∼ (N/(1+δ)/s_N)^d in (2.4) corresponds to a cube of side length N/(1+δ). Please correct this to Q(0, N/(1+δ)) or the intended analogue, both in Section 2 and in Appendix B.
  2. [§4.1 and Table 5.3] The phrase 'self-disjoint loop' in Table 5.3 should be 'self-avoiding loop', which is the term used elsewhere in Section 4.
  3. [§1.1 and throughout] The same symbol P (and E) is used both for the law of the random walk on the torus and for the law of random interlacements; this is a recurring source of potential confusion, especially in Propositions 1.4 and 1.5 where extended measures are denoted eP. Consider using a different symbol such as P^I for the interlacement law.
  4. [§0.1] There are several typos in the exposition, for example 'we devide' in the description of Stage 3 and 'sa espérance' in the French résumé; these should be corrected in a final revision.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular reduction: the sharp lower bound is derived from external coupling and late-point estimates; the unproved Lemma 1.7 is a rigor gap, not a circular step.

full rationale

The paper's central result, the sharp lower bound in Theorem 0.1, is not obtained by assuming its own conclusion or by renaming a fitted quantity. The upper bound (0.6) is imported from [18]/[12] and sketched independently in Appendix A; the lower bound is built from a four-stage path construction whose probability cost is computed from first principles. The prefactor -1 in (0.4) has two independent sources: the upper bound uses cover-level Gumbel asymptotics [5, Theorem 0.1] via Lemma 1.2, and the lower bound uses the FKG lower bound Lemma 1.3 together with late-point cardinality estimates. The calibration alpha_N = gamma - K/u_N is not circular: Lemma 1.8 proves that |L_{alpha_N}| is approximately e^{K/g(0)} N^{d(1-gamma)}, and Proposition 3.5 shows the covering cost is approximately exp(-e^{-K/g(0)} |F|), so the K factors cancel to yield exponent -(1+o(1)) N^{d(1-gamma)}. This is a genuine two-sided estimate, not a fit renamed as prediction. The load-bearing Lemma 1.7 is an unproved generalization of [26, Lemma 6.1], which is an external paper rather than a self-citation; its failure would break Lemma 1.9, Lemma 1.8, and the regularity input Lemma 3.4, so it is a substantive rigor gap, but it is not a circular reduction because the cited lemma does not contain the target Theorem 0.1 and no parameter is fitted to the target probability. The coupling Proposition 1.5 is imported from [26] with an explicit error; the restriction gamma > (d+2)/(2d) is exactly where that error is negligible, and the paper honestly records in footnote 3 that improving the error would extend the range. Self-citations [21]-[23] appear only in the discussion of related problems and are not used in the proofs of Theorems 0.1 or 0.2. No equation in the paper reduces by construction to an earlier equation or to the claimed result; the derivation is self-contained relative to the cited external benchmarks.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central claim rests on external theorems ([26], [5], [12], [4]) rather than on new postulates. No free parameters are fitted. The most fragile inputs are the unproved generalization of [26, Lemma 6.1] and the unproved extension of the soft-local-time coupling to d ≥ 3.

assumptions (4)
  • domain assumption Strong coupling between the torus random walk trace and random interlacements with explicit error bound (from [26, Theorem 5.1], stated as Proposition 1.5)
    This is the central tool used in Sections 2 and 3 to transfer estimates between the walk and interlacements. The threshold γ > (d+2)/(2d) is determined by this error term. If this coupling failed, the lower-bound proof would collapse.
  • standard math Cover-level fluctuations of random interlacements follow the Gumbel law (from [5, Theorem 0.1], used in Lemma 1.2)
    Used to show that the probability a cube of side N^γ is covered at intensity close to u_N(γ) is e^{-1}. This supplies the sharp constant in the asymptotic.
  • ad hoc to paper The generalization of [26, Lemma 6.1] to all α ∈ [α0, α1] (Lemma 1.7) is asserted without proof
    The authors state that the proof of [26, Lemma 6.1] 'still goes through under such generalization', but no details are given. This lemma underpins the late-point moment estimates in Lemmas 1.8 and 1.9.
  • ad hoc to paper Soft local times decoupling in higher dimensions (Appendix A, based on [12, Lemma 2.1])
    The proof of the upper bound (0.6) assumes the 2D soft local time coupling of Comets et al. extends to d ≥ 3 without modification; this is a sketch and not proven in the paper.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Large Deviations of Cover Time of Tori in Dimensions $d\geq 3$." pith.science (2026). https://pith.science/paper/7QX2L5DO

@misc{pith2026241116398,
  author       = {Pith},
  title        = {Pith review of: Large Deviations of Cover Time of Tori in Dimensions $d\geq 3$},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/7QX2L5DO}},
  note         = {Machine review of arXiv:2411.16398}
}
abstract

We consider large deviations of the cover time of the discrete torus $(\mathbb{Z}/N\mathbb{Z})^d$, $d \geq 3$ by simple random walk. We prove a lower bound on the probability that the cover time is smaller than $\gamma\in (0,1)$ times its expected value, with exponents matching the upper bound from [Goodman-den Hollander, Probab. Theory Related Fields (2014)] and [Comets-Gallesco-Popov-Vachkovskaia, Electron. J. Probab. (2013)]. Moreover, we derive sharp asymptotics for $\gamma \in (\frac{d+2}{2d},1)$. The strong coupling of the random walk on the torus and random interlacements developed in a recent work [Pr\'evost-Rodriguez-Sousi, arXiv:2309.03192] serves as an important ingredient in the proofs.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

32 extracted references · 29 canonical work pages

  1. [26]

    Phase transition for the late points of random walk

    P RÉVOST , A., R ODRIGUEZ , P.-F. and S OUSI , P. (2023). Phase transition for the late points of random walk. arXiv preprint arXiv:2309.03192

    work page Pith review arXiv 2023

  2. [1]

    A BE, Y. (2021). Second-Order Term of Cover Time for Planar Simple Random Walk.J. Theoret. Probab.34 1689-1747. https://doi.org/10.1007/ s10959-020-01011-2

    work page 2021

  3. [2]

    A BE, Y. (2021). Avoided points of two-dimensional random walks. In Stochastic Analysis, Random Fields and Integrable Probability—Fukuoka 2019, 87 199–212. Mathematical Society of Japan

    work page 2021

  4. [3]

    and F ILL , J

    A LDOUS , D. and F ILL , J. A. (2002). Reversible Markov Chains and Random Walks on Graphs. Unfinished monograph, recompiled 2014, available at http://www.stat.berkeley.edu/~aldous/RWG/book.html

    work page 2002

  5. [4]

    B ELIUS , D. (2011). Cover times in the discrete cylinder. arXiv preprint arXiv:1103.2079

    work page Pith review arXiv 2011

  6. [5]

    B ELIUS , D. (2012). Cover levels and random interlacements. Ann. Appl. Probab. 22 522–540. https://doi.org/10.1214/11-AAP770

    work page doi:10.1214/11-aap770 2012

  7. [6]

    B ELIUS , D. (2013). Gumbel fluctuations for cover times in the discrete torus. Probab. Theory Related Fields 157 635–689. https://doi.org/10. 1007/s00440-012-0467-7 MR3129800

    work page 2013

  8. [7]

    and K ISTLER , N

    B ELIUS , D. and K ISTLER , N. (2017). The subleading order of two dimensional cover times. Probab. Theory Related Fields 167 461-552. https://doi.org/10.1007/s00440-015-0689-6

    work page doi:10.1007/s00440-015-0689-6 2017

Show all 32 references
  1. [8]

    and Z EITOUNI , O

    B ELIUS , D., R OSEN , J. and Z EITOUNI , O. (2020). Tightness for the cover time of the two dimensional sphere. Probab. Theory Related Fields 176 1357–1437

    2020

  2. [9]

    and M ORRIS , B

    B ENJAMINI , I., G UREL -GUREVICH , O. and M ORRIS , B. (2013). Linear cover time is exponentially unlikely.Probab. Theory Related Fields155 451–461

    2013

  3. [10]

    and G IACOMIN , G

    B OLTHAUSEN , E., D EUSCHEL , J.-D. and G IACOMIN , G. (2001). Entropic repulsion and the maximum of the two-dimensional harmonic crystal. Ann. Probab. 29 1670–1692

    2001

  4. [11]

    and Z EITOUNI , O

    B OLTHAUSEN , E., D EUSCHEL , J.-D. and Z EITOUNI , O. (1995). Entropic repulsion of the lattice free field. Comm. Math. Phys. 170 417–443. MR1334403

    1995

  5. [12]

    and V ACHKOVSKAIA , M

    C OMETS , F., G ALLESCO , C., P OPOV, S. and V ACHKOVSKAIA , M. (2013). On large deviations for the cover time of two-dimensional torus. Electron. J. Probab.18 1–18. https://doi.org/10.1214/EJP.v18-2856

    2013 doi

  6. [13]

    and R OSEN , J

    D EMBO , A., P ERES , Y. and R OSEN , J. (2003). Brownian Motion on Compact Manifolds: Cover Time and Late Points. Electron. J. Probab. 8 1–14. https://doi.org/10.1214/EJP.v8-139

    2003 doi

  7. [14]

    and Z EITOUNI , O

    D EMBO , A., P ERES , Y., ROSEN , J. and Z EITOUNI , O. (2004). Cover times for Brownian motion and random walks in two dimensions. Ann. of Math. (2) 160 433–464. https://doi.org/10.4007/annals.2004.160.433

    2004 doi

  8. [15]

    and S APOZHNIKOV , A

    D REWITZ , A., R ÁTH, B. and S APOZHNIKOV , A. (2014). An introduction to random interlacements . SpringerBriefs in Mathematics. Springer, Cham. https://doi.org/10.1007/978-3-319-05852-8 MR3308116

    2014 doi

  9. [16]

    and K AHN , J

    D UBROFF , Q. and K AHN , J. (2025). Linear cover time is exponentially unlikely. Ann. Probab. 53 1–22

    2025

  10. [17]

    and TAYLOR , S

    E RD ˝OS, P. and TAYLOR , S. J. (1960). Some problems concerning the structure of random walk paths.Acta Math. Acad. Sci. Hungar11 137–162. 32

    1960

  11. [18]

    and DEN HOLLANDER , F

    G OODMAN , J. and DEN HOLLANDER , F. (2014). Extremal geometry of a Brownian porous medium.Probab. Theory Related Fields160 127-174. https://doi.org/10.1007/s00440-013-0525-9

    2014 doi

  12. [19]

    L AWLER , G. F. (2012). Intersections of Random Walks. Modern Birkhäuser Classics. Springer New York

    2012

  13. [20]

    Coupling from the past

    L EVIN , D. A., P ERES , Y. and WILMER , E. L. (2017). Markov chains and mixing times, Second ed. American Mathematical Society, Providence, RI With a chapter on “Coupling from the past” by James G. Propp and David B. Wilson. https://doi.org/10.1090/mbk/107 MR3726904

    2017 doi

  14. [21]

    L I, X. (2017). A lower bound for disconnection by simple random walk. Ann. Probab. 45 879–931

    2017

  15. [22]

    and S HI, J

    L I, X. and S HI, J. Large deviations of the cover level of random interlacements. In preparation

  16. [23]

    and S ZNITMAN , A.-S

    L I, X. and S ZNITMAN , A.-S. (2014). A lower bound for disconnection by random interlacements. Electron. J. Probab.19 1–26. https://doi.org/ 10.1214/EJP.v19-3067

    2014 doi

  17. [24]

    and SOUSI , P

    M ILLER , J. and SOUSI , P. (2017). Uniformity of the late points of random walk onZd n for d ≥ 3. Probab. Theory Related Fields167 1001–1056

    2017

  18. [25]

    and T EIXEIRA , A

    P OPOV, S. and T EIXEIRA , A. (2015). Soft local times and decoupling of random interlacements. J. Eur. Math. Soc. 17 2545–2593. https: //doi.org/10.4171/JEMS/565 MR3420516

    2015 doi

  19. [27]

    S ZNITMAN , A.-S. (2010). Vacant set of random interlacements and percolation. Ann. of Math. (2) 171 2039–2087. https://doi.org/10.4007/ annals.2010.171.2039 MR2680403

    2010

  20. [28]

    S ZNITMAN , A.-S. (2017). Disconnection, random walks, and random interlacements. Probab. Theory Related Fields 167 1–44. https://doi.org/ 10.1007/s00440-015-0676-y MR3602841

    2017 doi

  21. [29]

    T EIXEIRA , A. (2009). Interlacement percolation on transient weighted graphs. Electron. J. Probab. 14 1604–1627. https://doi.org/10.1214/EJP. v14-670

    2009 doi

  22. [30]

    and W INDISCH , D

    T EIXEIRA , A. and W INDISCH , D. (2011). On the fragmentation of a torus by random walk. Comm. Pure Appl. Math. 64 1599–1646

    2011

  23. [31]

    W INDISCH , D. (2008). Random walk on a discrete torus and random interlacements. Electron. Commun. Probab.13 140-150. https://doi.org/10. 1214/ECP.v13-1359

    2008

  24. [32]

    and T EIXEIRA , A

    ˇCERNÝ , J. and T EIXEIRA , A. (2016). Random walks on torus and random interlacements: Macroscopic coupling and phase transition.Ann. Appl. Probab. 26 2883–2914. https://doi.org/10.1214/15-AAP1165

    2016 doi

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.