# Verification report — AMR-099-0065 (Benjamini, "Euclidean vs. Graph Metric", Question 9.1: first-passage percolation on hierarchical graphs)

Verification date: 2026-10-14.

**Verdict.** The note gives a **partial answer**; every statement it makes is proved (Theorem C with computer
assistance), and the scope is as follows.
- **Settled: the "in particular" part.** γ_rec > γ_brw for every non-degenerate law of positive weights with
  finite mean, indeed for every non-degenerate law that is bounded below and has finite mean (Theorem A).
- **Not new as a method.** The proof is a standard first-moment (union) bound taken one level up the hierarchy,
  combined with the pointwise inequality exp(−t min(x,y)) < exp(−tx) + exp(−ty). The identification of the
  level-0 bound with γ_brw is the classical theorem of Hammersley, Kingman and Biggins, cited from Biggins,
  "Branching out" (2010), Theorem 3.1. No published resolution was found; no priority is claimed.
- **Partial for "compute γ_rec in terms of ξ".** Theorem B: γ_rec = lim↑ γ_k = lim↓ 2^−k E D_k with explicit
  first-moment bounds γ_k; D_n/2^n → γ_rec in L¹ (the expectation stated after Question 9.1); and
  0 ≤ 2^−n E D_n − γ_rec ≤ ((1+√2)/2)‖ξ − ess inf ξ‖₂ 2^−n/2. Theorem C: certified enclosures for three laws.
- **Open.** A closed formula for γ_rec in terms of ξ. Question 9.2 (concentration, lower-order terms) is not
  treated.
- **Corpus remark.** The summary of the UnsolvedMath record says that the constant equals the minimal rate of the
  branching random walk and that γ_rec equals the branching random walk constant in the exponential case. Both are
  incorrect: Theorem A, and for exponential weights γ_rec ≥ g_1(11/5) = log(3.36)/4.4 > 0.27544 > 0.23197 > γ_brw.
- **Verification.** Two independent AI-assisted verification runs examined the first written version; a third,
  the second verification stage (`reproducibility/independent_run_2/`), examined the final text and the package.
  None found an error in a proof or in a stated number; all their corrections are applied.

The note is unrefereed.

## Statement checked
- **Primary source.** I. Benjamini, "Euclidean vs. Graph Metric", in *Erdős Centennial*, Bolyai Society
  Mathematical Studies 25 (2013) 35–57, doi:10.1007/978-3-642-39286-3_2 (Crossref; volume and pages also in
  zbMATH, Zbl 1293.05199).
  - Read in the author-hosted version dated 16.07.12, Section 9 with Figure 1 (PDF pages 13–15), from a copy
    saved in 2026 (1,339,034 bytes, sha256 `d49f0423f4420e0c3469ce4af09e07b3e5051ef4ab0f65b578c6f1fd58061745`).
    The author's address returned HTTP 404 on 2026-10-14 (during the verification runs the connection was
    reset); no other copy was used. The published chapter was not compared.
  - §9.1: a pattern G_1 with source and sink, edges oriented from source to sink; G_n is obtained from G_{n−1} by
    replacing each oriented edge by a copy of G_1. Figure 1, third row: one edge followed by two parallel edges.
  - §9.2: independent positive weights (for example uniform on [0,1]); D_n is the weight of a minimal path
    linking source and sink; equation (1), third line, D_n =d D_{n−1} + min(D'_{n−1}, D''_{n−1}), stated for
    n ≥ 2 (it holds for n ≥ 1 with D_0 = ξ, Lemma 2.1).
  - Comparison with the branching random walk: T_n is the full binary tree starting with an edge, up to level n;
    M_n = ξ + min(M_{n−1}, M'_{n−1}); M_n ≈ γ_brw n with γ_brw explicit in ξ. The source shows D_n ≥ M_{2^n}
    by induction, so γ_brw 2^n ≤ E D_n ≤ 2^n (weights in [0,1]), and states that for non-degenerate ξ the
    limit γ_rec = lim 2^−n E D_n exists and lies in [γ_brw, 1).
  - Question 9.1 (verbatim, 12 words): "Compute γrec in terms of ξ in particular show (if true) γrec > γbrw."
    After it, the authors expect that convergence in mean implies, through (1), convergence in probability.
    Question 9.2 asks for the concentration and the lower-order terms of D_n. The section is described as based
    on an ongoing project with N. Curien.
- **Corpus record.** ulamai/UnsolvedMath, version 1.6.0, AMR-099-0065 (record_id 10000065): the statement matches
  the source. Upstream status `partially_solved`. The upstream summary asserts that the constant "equals the
  branching-random-walk minimum rate" and that γ_rec equals the BRW constant "in the solvable exponential case";
  both assertions are refuted by the note (Theorem A; Theorem C(b)).

## Readings
| Reading | Answer | Where |
|---|---|---|
| "show (if true) γ_rec > γ_brw", non-degenerate positive weights with finite mean (the source's setting) | true | Theorem A |
| the same for laws bounded below, D_n defined over oriented paths | true; equivalent to the positive case by the shift ξ ↦ ξ + c, which moves both constants by c | Theorem A, convention (iii) |
| weights in {0,1} (nonnegative, not positive) | equivalent to the positive laws on {c, 1 + c}; all constants shift by c | convention (iii), Section 6.5 |
| degenerate ξ ≡ c | γ_rec = γ_brw = c (excluded by the source) | convention (iv), Remark 4.6(a) |
| positive ξ with E ξ = ∞ | γ_rec = ∞ by the source's definition | Remark 4.6(b) |
| minimal paths in the unoriented graph vs oriented paths | the same for nonnegative weights | Lemma 2.1(a) |
| the mirror pattern (two parallel edges, then one edge) | same law of D_n | convention (vi) |
| γ_rec as a limit in probability instead of in mean | same constant (L¹ convergence) | Theorem B(ii) |
| "compute γ_rec in terms of ξ" | convergent characterisation with rate and certified values; no closed formula | Theorems B, C; open |

## Results in the paper
- **Lemma 2.1 (structure).** G_n ≅ G_{n−k}[G_k]; every simple source–sink path of the unoriented multigraph is
  oriented and has 2^n edges; there are 2^{2^n−1} of them; D_n = min over the paths of G_{n−k} of sums of
  independent copies of D_k; (1) for n ≥ 1.
- **Theorem 3.1 (Hammersley, Kingman, Biggins).** For ξ bounded below, M_n/n → γ_0 = sup_{t>0} −log(2E e^{−tξ})/t
  almost surely (and in L¹ if E|ξ| < ∞); derived from Biggins (2010), Theorem 3.1, for the reflected walk. Only
  γ_brw ≤ γ_0 is used in Theorem A.
- **Lemmas 4.1–4.5.** Exact decrement a_{n+1} = a_n − E|X'_n − X''_n|/4, existence of γ_rec, L¹ convergence;
  first-moment bound γ_rec ≥ g_k(t) at every level k; strict increase g_{k+1} > g_k from
  exp(−t min) < exp(−tx) + exp(−ty); attainment of sup g_k when the atom at the minimum is below 1/2; the atom
  recursion q_{k+1} = q_k²(2 − q_k) → 0.
- **Theorem A.** With k the first level where P(D_k = 2^k m) < 1/2: γ_brw = γ_0 ≤ γ_k = g_k(t_k*) <
  g_{k+1}(t_k*) ≤ γ_{k+1} ≤ γ_rec. Remark 4.7: explicit gap g_1(t_0*) − g_0(t_0*) when P(ξ = m) < 1/2.
- **Theorem B.** (i) γ_rec = lim↑ γ_k; (ii) γ_rec = lim↓ a_k and L¹ convergence; (iii) Var D_n ≤ 2^n E(ξ − m)²
  (Efron–Stein, Steele's form) and 0 ≤ a_n − γ_rec ≤ ((1+√2)/2)‖ξ − m‖₂ 2^{−n/2}. Remark 5.1: fluctuations are
  O(2^{n/2}); Question 9.2 is not answered.
- **Lemma 5.2 (truncation).** a_n(min(ξ, L)) ≤ a_n(ξ) ≤ a_n(min(ξ, L)) + E(ξ − L)^+.
- **Theorem C (computer-assisted).** U[0,1]: γ_brw ∈ [0.184827520905, 0.184827520906], γ_rec ∈ [0.268785599,
  0.268808710]. Exp(1): γ_brw = 1/u* with log(u*/2) = 1 − 1/u*, γ_brw ∈ [0.231960952986, 0.231960952987],
  γ_rec ∈ [0.379282228, 0.379412906], and γ_rec ≥ log(3.36)/4.4 > 0.27544 without a computer. Weights in {0,1},
  P(ξ = 0) = p: γ_brw = 0 for p ≥ 1/2; γ_rec ∈ [0.12392609, 0.14126638] (p = 1/2) and [0.00964880, 0.01735090]
  (p = 3/4). Table 1 (first-moment bounds γ_1 ≥ 0.211023660047 (U); γ_1 ≥ 0.275441130448, γ_2 ≥ 0.307222167962,
  γ_3 ≥ 0.329920004276 (Exp); γ_1, γ_2 (p = 1/2) and γ_4, γ_5 (p = 3/4) positive) and Table 2 (enclosures of a_6,
  a_8, a_40).
- **Lemma 6.1 (floating point).** The one-sided margins (factor 1 + 10^−9, addition of 10^−300) dominate all
  rounding errors on the V side.

## Computations (programs and outputs in reproducibility/)
- **Programs of the note** (`programs/`, recorded outputs in `outputs/`): `bracket.py` (U side, exact int64
  arithmetic), `bracket_down.py` (V side, doubles with one-sided margins), `assemble.py` (Theorem C(a),(b)),
  `certify_constants.py` (γ_brw, first-moment bounds, exact a_k for Exp(1) with sympy), `bernoulli_atom.py`,
  two Monte Carlo programs on the literal graph (sanity checks: all estimates within 2.5 standard errors of the
  certified enclosures), `explore_float.py` (non-certified).
- **Interval check of the initial exponential grids (new at the writing).** In the first version,
  `bracket_down.py` rounded its 2^20 initial values 1 − e^{−(i+1)h} upwards relative to a 40-digit evaluation,
  without an error bound. Both bracket programs now check every initial value against an enclosure in 200-bit
  mpmath interval arithmetic and abort on a violation. Result: 0 violations; smallest margins 9.328·10^−24 (V
  side, i = 981626) and 1.287·10^−6 units of 2^−31 (U side, i ≥ 1, i = 462207). The second verification run had
  obtained the same numbers with its own check.
- **Re-run at the writing** (2026-10-14; `RERUN_LOG.txt`, `rerun_at_writing/`): all programs of the note were
  run again; every output is identical to the recorded one up to runtime fields and the added interval-check
  line (0 files differ in content). Wall-clock times: 101 s and 209 s (U side, uniform and exponential law),
  56 s and 206 s (V side), the others below 30 s.
- **check_note.py** (about 10 s; exact and interval arithmetic only): 58 checks, ALL CHECKS PASSED
  (`rerun_at_writing/check_note.log`). It enumerates all simple paths of G_n for n ≤ 4 and compares the minimum
  with the recursion (exact integer weights); encloses γ_brw for both laws; computes the exact laws of D_0..D_3
  (exponential polynomials, Exp(1)) and D_0..D_2 (piecewise polynomials, U[0,1]), the exact means
  a_1..a_3 = 3/4, 29/48, 52201/100800 (Exp(1)) and 5/12, 229/630, 4747708908589/14399277984000 (U[0,1]),
  the exact Laplace values ψ_{D_1}(11/5) = 25/168, ψ_{D_2}(31/20) = 193280000/2596876191 and ψ_{D_3}(11/10), and
  all first-moment bounds of Table 1; re-assembles the enclosures of Theorem C(a),(b) and Table 2 from the
  recorded exact means; checks that the enclosures of both verification runs lie inside; treats the {0,1}
  laws up to level 8 exactly, including the decrement identity and the variance bound of Theorem B(iii).

## Independent verification runs (first stage)
Two independent verification runs, both AI-assisted, examined the first written version of the results; they
did not see each other. Each re-derived every proof line by line, compared the statement with the source, and
wrote its own programs.

| Item | Run A | Run B |
|---|---|---|
| Statement, pattern, normalisation 2^n, BRW convention, readings | CONFIRMED (source read; no reading changes the answer) | CONFIRMED (source read; sha256 recomputed) |
| Lemma 2.1 (structure) | CONFIRMED (re-derived; brute force n ≤ 3) | CONFIRMED (re-derived; brute force on the literal unoriented multigraph, n ≤ 4, exact weights) |
| Lemmas 4.1–4.5, Theorem A | CONFIRMED (re-derived line by line) | CONFIRMED (re-derived; atom case tested with exact Bernoulli laws) |
| HKB input (Theorem 3.1) | CONFIRMED against Biggins (2010), Theorem 3.1 | CONFIRMED against Biggins (2010), Theorem 3.1; BRW recursion iterated to n = 32000 (convention test) |
| Theorem B, Lemma 5.2 | CONFIRMED (re-derived; constant (1+√2)/2 recomputed) | CONFIRMED (re-derived; decrement identity and variance bound checked exactly on Bernoulli laws) |
| Certified enclosures of γ_rec | CONFIRMED by an independent program: [0.2687907726, 0.2688051565] (U), [0.3793380918, 0.3793643414] (Exp) | CONFIRMED by an independent program starting from the exact law of D_3: [0.2687943832, 0.2688019634] (U), [0.3793410791, 0.3793636293] (Exp) |
| γ_brw, first-moment certificates, exact means, Bernoulli examples | CONFIRMED (own programs) | CONFIRMED (own programs; improved Bernoulli brackets) |
| Programs of the note | read line by line; bracket programs re-run, all exact means reproduced | read line by line; all programs except the non-certified exploration re-run, outputs identical up to runtimes; negative tests with deliberately wrong inputs all rejected |
| Literature, novelty | no resolution found; method standard | no resolution found; method standard; novelty only "no published resolution found" |

Neither run found a wrong theorem, lemma or stated number, or a gap in a proof.

**Corrections required by the runs**, all applied in the note and the package:
1. (Run A) The {0,1} weights are nonnegative, not positive: the shift ξ ↦ ξ + c changes both constants by c, so
   they stand for the positive laws on {c, 1 + c}: convention (iii) of Section 1.1 and Section 6.5.
2. (Run A) The sentence after Question 9.1 is an expectation of the authors; Theorem B(ii) proves it
   (D_n/2^n → γ_rec in probability, indeed in L¹, for E|ξ| < ∞): text after Theorem B.
3. (Run A, optional) Record the independent enclosures: Verification paragraph, this report, check_note.py.
4. (Run A, optional) Note on the initial exponential grid of `bracket_down.py`: docstring and Section 6.3.
5. (Run A, optional) Record that the author-hosted PDF was not reachable: "Scope and priority", this report.
6. (Run B) Make the rounding of the initial exponential grid in `bracket_down.py` rigorous, or record the interval
   check of all 2^20 values: both were done (interval check now part of `bracket_down.py` and `bracket.py`;
   Section 6.3; the run's own check is recorded in `verification_run_B/outputs/check_claim_init2.json`).
7. (Run B) DOIs and pages of Khristoforov–Kleptsyn–Triestino (CMP 345 (2016) 1–76, doi:10.1007/s00220-016-2650-7),
   Hambly–Jordan (AAP 36 (2004) 824–838, doi:10.1239/aap/1093962236) and the "Hipster random walks" paper
   (PTRF 178 (2020) 437–473, doi:10.1007/s00440-020-00980-z); the Semantic Scholar count of works citing the
   source includes a merged record of a different 2026 paper: bibliography and "Scope and priority".

**Changes made when the note was written.**
- Credits and related literature (Khristoforov–Kleptsyn–Triestino, Hambly–Jordan, the hipster paper,
  Dekking–Host, Benjamini–Zeitouni, Lacoin–Moreno), one sentence each on why they do not settle the question.
- The enclosures for the {0,1} laws were sharpened to level 8 with `check_note.py` (exact laws, interval
  bounds); the first version had γ_rec ∈ [0.0666, 0.1575] (p = 1/2) and [0.00464, 0.0254] (p = 3/4).
- The per-level enclosures of Table 2 are rounded outwards (the first written version had rounded two endpoints
  of a_8 to the nearest decimal).
- The overwrite guard in all programs; `assemble.py` takes its output file as an argument.

## Second verification stage: independent run 2 (third run, on the final text)
A third independent verification run, also AI-assisted, examined the final text of the note, the package
(`release/source.zip`, extracted into a fresh folder) and the sources on 2026-10-14, as if nothing had been checked
before; it compared lists of corrections with the earlier runs only after its own checks. Programs and outputs:
`reproducibility/independent_run_2/` (with its own README).

| Item | Verdict | How it was checked |
|---|---|---|
| Statement and scope | CONFIRMED | Section 9 of the source read again from the saved copy (sha256 recomputed), Figure 1 rendered and inspected; the question, the model, the source's bounds, the expectation after Question 9.1 and Question 9.2 as in Section 1.1; two wording corrections (1, 2 below) |
| Lemma 2.1 | CONFIRMED | re-derived; `r2_structure.py`: all simple paths of the unoriented multigraph built literally (n ≤ 4: 1, 2, 8, 128, 32768 paths, all oriented, length 2^n), Dijkstra against the recursion (n ≤ 7), weights of both signs on oriented paths (n ≤ 4), block decomposition (4) (k = 1, 2, n ≤ 5) |
| Theorem 3.1 (HKB) | CONFIRMED | Biggins, arXiv:1003.4715v1, Section 2 and Theorem 3.1 with the paragraph after it read again; hypotheses and attributions as stated; the reflection argument and the L¹ part re-derived |
| Lemmas 4.1–4.5, Theorem A, Remarks 4.6–4.7 | CONFIRMED | re-derived line by line; Remark 4.6(a) reworded (correction 3) |
| Theorem B, Remark 5.1, Lemma 5.2 | CONFIRMED | re-derived (Efron–Stein step, constants (1+√2)/2 and (3+√2)/2, the inclusion in the truncation lemma) |
| Section 6 and Lemma 6.1 | CONFIRMED | rounding directions and the floating-point bound checked against `bracket.py` and `bracket_down.py` line by line |
| Exact low levels | CONFIRMED | `r2_exact_laws.py` (conditioning on the minimum instead of D_k): a_0..a_3 = 1, 3/4, 29/48, 52201/100800 (Exp) and 1/2, 5/12, 229/630, 4747708908589/14399277984000 (U); the exact values of E e^{−tD_k} of Section 6.4 |
| γ_brw, Table 1, Remark 4.7 | CONFIRMED | `r2_constants.py` in Arb ball arithmetic: γ_brw = 0.18482752090556833… (U), 0.23196095298653443… (Exp); every first-moment bound of Table 1; gaps 0.0194177702… and 0.0315014700… |
| Weights in {0,1} | CONFIRMED | `r2_bernoulli.py`: exact integer laws to level 8, k* = 1 and 4, every bound of Table 1 and Theorem C(c) (g_8(31/100) = 0.12392609675…, g_8(19/25) = 0.00964880177…, a_8 = 0.14126637672…, 0.01735089932…); Lemma 4.1 and the variance bound exactly |
| Certified enclosures of γ_rec | CONFIRMED | `r2_bracket.py`, exact integer arithmetic (units 2^−160, exact convolutions with FLINT, start at level 1 from the exact law of D_1, exponential law truncated at L = 40, 48 levels): [0.2687956521, 0.2688009027] (U) and [0.3793364429, 0.3793661592] (Exp), inside Theorem C(a),(b); per-level enclosures overlap those of the note for k = 1..40 and lie inside Table 2 at k = 6, 8, 40; a variant with units 2^−256 gives [0.2687955818, 0.2688009027], [0.3793363062, 0.3793661592] and the level-48 first-moment bounds γ_rec ≥ 0.266485 (U, s = 300), ≥ 0.375870 (Exp, s = 200) |
| Programs of the note | CONFIRMED | all run again from the extracted archive (bracket programs 56–213 s, Monte Carlo 22–25 s, check_note.py 58 checks passed in 10 s); outputs identical to the recorded ones up to running times and the line of the interval check (own comparison `r2_compare.py` and `compare_outputs.py`); Table 2 and Theorem C(a),(b) recomputed from the recorded exact means with own outward rounding: identical |
| Literature, novelty, credits | CONFIRMED | arXiv API (14 queries), Crossref (15 DOIs, all agree with the bibliography), OpenAlex (15 citing works), zbMATH (3 requests; the review of Dekking–Host as described), one web search: no answer to Question 9.1 found; credits complete; no priority claimed |
| House style and rendering | CONFIRMED | author line, date, keywords with the identifier, abstract ending, Verification and Scope paragraphs, one AI paragraph; every page rendered and inspected before and after the corrections; no overfull box |

It found no error in a proof or in a stated number. **Corrections required by this run**, all applied:
1. Abstract and Zenodo description: the question asks to show γ_rec > γ_brw *if true* (the source's words).
2. Convention (ii): the source speaks of a minimal path linking source and sink and does not say whether paths
   follow the orientation; the note no longer attributes the unoriented reading to the source.
3. Remark 4.6(a): for ξ ≡ c, γ_brw = γ_k = γ_rec = c for every k, the suprema are not attained, no k as in Theorem A
   exists and the strict inequality fails (the old wording said that "all terms of (3) equal c").
4. Sections 6.5 and 7: the level-8 enclosures of Theorem C(c) (and the last column of Table 1, rows 3–4) are
   computed by `check_note.py`; `bernoulli_atom.py` stops at level 6; "re-assembled from the recorded exact means"
   refers to Theorem C(a),(b).
5. "Scope and priority": Biggins (2010) was read in the arXiv version (v1), whose numbering is used.
6. This run is recorded in the Verification paragraph, after Theorem C ("Three independent verification runs"), in
   Section 7 and "Scope and priority", in this report and in `reproducibility/independent_run_2/`.
7. Package rebuilt (PDF, source archive, Zenodo copies and metadata).
Also applied (recommended by the run): Section 1.1 now mentions both claims of the record's summary; Section 7 says
that the larger Monte Carlo run agrees with Table 2 within 0.3 standard errors.

## Relation to the literature, novelty and scope
- **Searches** (2026-10-14, when the results were first obtained, in both verification runs of the first stage
  and, in part, in the third run): arXiv API
  (first-passage percolation on hierarchical and series–parallel graphs, min-plus recursive distributional
  equations, the authors of the question), Crossref, OpenAlex, Semantic Scholar, zbMATH, the works citing the
  source (15 in OpenAlex; 19 in Semantic Scholar, two of them through a record merging the source with
  arXiv:2606.13271, a different 2026 paper of Benjamini), and a few web searches. Only
  Khristoforov–Kleptsyn–Triestino among the citing works concerns hierarchical graphs.
- **Closest work and why it does not settle the question.** Khristoforov–Kleptsyn–Triestino (CMP 2016): stationary
  random metrics on limits of hierarchical graphs with multiplicative-cascade edge lengths, renormalised; no
  i.i.d. weights on a fixed G_n, no γ_rec, no comparison with γ_brw. Hambly–Jordan (AAP 2004): random
  series/parallel substitution (random graphs), not a fixed pattern with random weights. Addario-Berry, Cairns,
  Devroye, Kerriou, Mitchell (PTRF 2020): recursions with a random choice of operation. Dekking–Host (PTRF 1991)
  and Benjamini–Zeitouni (LNM 2050, 2012): tightness of the BRW minimum and of first passage on other graphs;
  no hierarchical graphs or time constants. Lacoin–Moreno (SPA 2010): polymers on hierarchical lattices at
  positive temperature.
- **What was read.** The source (author-hosted version, Section 9 and Figure 1). Biggins (2010), Section 2 and
  Theorem 3.1 with the paragraph after it (arXiv:1003.4715v1, read again at the writing and by the third run). The abstracts of the related works
  above; the introduction and Section 8.3 of Khristoforov–Kleptsyn–Triestino (first version and run A); a zbMATH
  review of Dekking–Host and the abstract of Lacoin–Moreno (run B). The proofs of the cited theorems were not
  checked. All bibliographic data were checked with Crossref at the writing (15 DOIs); the pages of four
  classical papers and the volumes of two books with zbMATH.
- **Novelty.** No answer to Question 9.1 was found in the literature accessible to us; a search that finds
  nothing is not a proof of novelty. The method is standard and may be known to experts; no priority is claimed.
- **Scope.** The note settles the "in particular" part of Question 9.1. The "compute" part is answered only by
  the convergent characterisation of Theorem B and by certified values; a closed formula remains open, and
  Question 9.2 is not treated.

## Public release and license
This paper, its source files, and this verification report are licensed under the Creative Commons Attribution
4.0 International License (CC BY 4.0): https://creativecommons.org/licenses/by/4.0/