# Verification report — AMR-096-0036 (Aldous: in a SIRSN the subnetwork S(1) cannot be a tree)

Verification date: 2026-10-17.

**Verdict.** The note gives a **complete affirmative answer**, resting on one published lemma used as published.
- **Settled.** For every SIRSN and every weak SIRSN, the set of outcomes in which S(1) contains no simple closed
  curve has outer probability zero; so has the set of outcomes in which the junction graph of S(1) (vertices: the
  Poisson points and the points where one route leaves another) has no finite cycle (Theorem 1.1). Hence S(1)
  contains a circuit almost surely, in the sense that the outcomes without a circuit lie in an event of
  probability zero; every event on which S(1) has no circuit has probability zero; and S(1) is not almost surely
  a tree, in either reading. Whether "S(1) has no circuit" is an event of the σ-field of the source is not
  decided; the theorem does not need it.
- **General form.** For any process of compatible feasible routes with the invariance properties (2.6)–(2.8) and
  (2.13) of the source, if that set has outer probability p > 0, then P(D_1 ≥ t) ≥ cp/t for t ≥ t_0(p), with
  c = 11/(32√2π·10⁹) ≈ 7.7·10⁻¹¹ and t_0 independent of the route process (Theorem 1.2); this contradicts the
  axiom E D_1 < ∞.
- **Credit.** The question is Aldous's. The core argument is Aldous's proof of Theorem 1.2 of "Route lengths in
  invariant spatial tree networks", Electron. Commun. Probab. 26 (2021) no. 31; its Lemma 2.2 (a Peierls-contour
  estimate for Bernoulli site percolation on the k × k grid) is used as published and is not re-proved; its proof
  is written as a sketch at the step leading to (2.6) there.
- **What the note adds.** The transfer of that proof to the routes of a SIRSN, which need not consist of finitely
  many segments: finite unions of compatible routes are finite graphs, trees if they contain no circuit, with a
  centroid bipartition and a route-length bound (Sections 3–4); the replacement of the Palm-probability step by
  Campbell's formula and scale invariance, with the outer-probability formulation (Section 6); the junction
  reading (Section 7); and repairs of the inequality (2.16) and of the constants of Corollary 2.3 of the 2021
  paper (Sections 5 and 8).
- **Not claimed.** No priority: the deduction is short once the 2021 paper is available. The constant c is not
  claimed to be sharp.

The note is unrefereed.

## Statement checked
- **Primary source.** D. Aldous, "Scale-invariant random spatial networks", Electron. J. Probab. 19 (2014),
  no. 15, 1–41, doi:10.1214/EJP.v19-2920 ("Supersedes arXiv:1204.0817").
  - Read in the published version (open copies on the EMIS mirror of EJP and in the University of California
    repository) and in arXiv:1204.0817v1 (its only version; LaTeX source).
  - Section 8.7.2 (journal page 39): after noting that continuum limits of random spanning trees have
    D_1 = ∞, the text says a simple proof should exist "because our definition of SIRSN requires E D_1 < ∞",
    and states **Open Problem 10**: "In a SIRSN, the subnetwork S(1) cannot be a tree (with Steiner points)."
  - In arXiv:1204.0817v1 the same item is **Open Problem 36** (page 52; all theorem-like environments share one
    counter), and the preceding sentence has the misprint E D_1 = ∞.
  - Definitions used (Section 2.2 of the source, equations (2.4)–(2.20); (4)–(20) in arXiv v1): feasible routes
    (Aspect 1), compatibility (2.4), feasible subnetworks (2.5), FDDs with (2.6) consistency, (2.7) translation
    and rotation invariance, (2.8) scale invariance, (2.13) measurability; S(λ) from Poisson points independent
    of the routes, (2.9)–(2.12), (2.14); D_1 and (2.15) 1 < E D_1 < ∞; (2.16) ℓ < ∞; (2.17)–(2.20); weak SIRSN
    = (2.16) in place of (2.20); Lemma 6.2 (ℓ ≤ 2p(1)); Proposition 5.1 (Section 5.1, no straight segment at
    Poisson points); Section 5.5 (Steiner tree constant).
  - Aldous's page https://www.stat.berkeley.edu/~aldous/Research/OP/sirsn.html (accessed 2026-10-16) copies the
    abstract and points to Section 8; it has no progress note.
- **Companion paper.** D. Aldous, "Route lengths in invariant spatial tree networks", Electron. Commun. Probab. 26
  (2021), article no. 31, 1–12, doi:10.1214/21-ECP401. Read completely in the published version (open copy in the
  University of California repository) and in arXiv:2103.00669v1, whose Theorem 2, Lemmas 1–2, Corollary 1 and
  Lemma 3 are Theorem 1.2, Lemmas 2.1–2.2, Corollary 2.3 and Lemma 2.4 of the published version (same statements).
  The note uses the published numbering.
- **Corpus record.** ulamai/UnsolvedMath, record AMR-096-0036 (dataset version 1.6.0; upstream status open):
  "Prove that in a scale-invariant random spatial network the subnetwork S(1) cannot be a tree, even allowing
  Steiner points." This is Open Problem 10 of the source in other words. The record's research summary calls S(1)
  the "unit-speed subnetwork"; in the source the index is the intensity of the Poisson process, not a speed.

## Readings
| Reading | Answer | Where |
|---|---|---|
| Topological: S(1) contains no simple closed curve (junctions as Steiner points) | outer probability 0, for SIRSNs and weak SIRSNs | Theorem 1.1 |
| Junction graph: Poisson points and departure points as vertices, sub-arcs of routes as edges, no finite cycle | outer probability 0 | Theorem 1.1, Proposition 7.3 |
| "cannot be a tree" as "is not almost surely a tree" | proved | Theorem 1.1 |
| "cannot be a tree" as "almost surely contains a circuit" | proved in the outer-probability sense; probability 0 if the event is measurable | Theorem 1.1 |
| Literal graph of segments of Aspect 2 | degenerate (Poisson points isolated; circuits through Poisson points invisible); not considered | Remark 2.1 |
| S(λ) for λ ≠ 1 | the same, since S(λ) is a scaled copy of S(1) by (2.12) | — |
| Route processes with (2.4), (2.6)–(2.8), (2.13) but without (2.15) | P(D_1 ≥ t) ≥ cp/t for large t | Theorem 1.2 |

## Results in the paper
- **Section 3 (Lemmas 3.1–3.4).** Two compatible routes meet in the empty set, a point or a common sub-arc; a
  finite union G_F of compatible routes is a finite topological graph (vertices: endpoints and ends of pairwise
  intersections); circuits and arcs with vertex ends are unions of whole edges; if G_F has no circuit, (V, E) is
  a tree and every route is the unique arc between its endpoints.
- **Section 4.** Lemma 4.1: Jordan's weighted centroid with Aldous's merging step gives v_* and B with
  N/3 ≤ |B| ≤ N/2 such that tree paths from B to W \ B pass through v_*. Corollary 4.2: (T1) and (T2)
  len r(v, v') ≥ |v − v_*| + |v_* − v'| for finite unions of compatible routes without circuit.
- **Section 5.** Lemma 5.1 (= Lemma 2.1 of the 2021 paper, proved); Lemma 5.2 (= Lemma 2.2, quoted, used as
  published, extended to q ≤ q_0 by monotone coupling); Corollary 5.3 (replaces Corollary 2.3: blocks of side
  ⌈k/2000⌉, k ≥ 16000, colour classes ≥ k²/4 + 2δ²k², uniform in colouring and block, ≥ k/4000 pairs);
  Lemma 5.4 (replaces Lemma 2.4: thresholds 0.09 m² and 0.93 m², |B^c| ≥ N/2, Case A constant 0.0465, Case B
  bounds 194/775 and 663/1550, β_0 = 5.5·10⁻⁶; deterministic for every v_* and every admissible B outside an
  event E_{m,k} determined by the Poisson process).
- **Section 6.** Lemma 6.1: E X ≤ (π/2)n²r² P(D_1 ≥ d/r) by scale invariance and Campbell's formula; proof of
  Theorem 1.2 (outer probability, Markov's inequality, interpolation in t) and of Theorem 1.1.
- **Section 7.** Lemma 7.1 (finitely many departure points on a route; Ramsey's theorem and the finite-length
  property (2.5)); Lemma 7.2 (a vertex on a route is a Poisson point or a departure point on that route; edges are
  equal or disjoint); Proposition 7.3 (no finite cycle of the junction graph ⇒ no circuit in a finite union of
  routes).
- **Section 8.** The published inequality (2.16) does not follow from the two counts (exact LP minimum 98/445 <
  1/4 for S^<) and is false (Example 8.1: every subsquare balanced with exactly m² points, S = 0.005k²,
  N/3 ≤ |B| ≤ N/2, but S^< = 0.2465k² < k²/4); the outline of Corollary 2.3 does not close with block side
  0.001k (about 0.004k boundary edges against the k/400 pairs of Lemma 2.2). The other points of that outline are
  sound (recolouring the block in the colour with fewer vertices keeps k²/4 of each colour; the block may depend
  on Ξ^k, so the statement applied to the worst block is uniform in the block). Repairs as in Corollary 5.3 and
  Lemma 5.4. The structure of the argument is unchanged, and with the repaired lemmas the proof of Theorem 1.2 of
  the 2021 paper goes through with other constants.

## Computations (sanity and exactness checks; program and output in reproducibility/)
No theorem, lemma or corollary depends on a computation.
- **Program of the note** (`check_note.py`, Python 3 standard library, about 9 seconds, 39 checks, 0 failed):
  Part A, Lemma 5.1; Part B, Corollary 5.3 for every k in [16000, 200000] and analytically; Part C, Lemma 5.4,
  with Case B as exact linear programs (minima 194/775 and 663/1550); Part D, the constant c = 7.737·10⁻¹¹ and the
  final chain of inequalities; Part E, Lemma 4.1 on all trees with at most 10 vertices and all W with |W| ≥ 3
  (130,947 cases), with the path property and two negative controls; Part F, the published bookkeeping (exact
  minima 98/445 and 118/465) and Example 8.1 (m = 1000, k = 200, and m ∈ {130, …, 390}, k ∈ {100, 200, 300}).
- **First program** (with which the result was first obtained): constants of Section 5 and the final step, and a
  random test of the merge in Lemma 4.1; 13 checks. Both verification runs re-ran it and obtained its recorded
  output. It is not part of the package.
- **Programs of the verification run on the final text** (`reproducibility/independent_run_2/`, Python 3 with
  NumPy, SciPy, SymPy, mpmath, NetworkX; recorded outputs included): `run2_constants.py` (39 checks, 0 failed),
  `run2_trees.py` (13 checks, 0 failed, about 6.5 minutes), `run2_campbell.py` (3 checks, 0 failed). See the
  section "Independent verification run 2" below.

## Independent verification runs
The result was first obtained with a written proof and the first program. Two independent verification runs, both
AI-assisted, followed (2026-10-17); each re-derived the proof and wrote its own programs, and neither read the
other's report.

| Item | Run A | Run B | Run 2 (final text) |
|---|---|---|---|
| Statement, numbering (Open Problem 36 of arXiv v1 = Open Problem 10 of EJP), definitions (2.4)–(2.20) | CONFIRMED (both versions read) | CONFIRMED (both versions read) | CONFIRMED (both versions read again) |
| Lemmas 3.1–3.4 (finite unions of compatible routes) | CONFIRMED (re-derived) | CONFIRMED (re-derived; tested on 1,000 random planar trees, Delaunay networks as negative control) | CONFIRMED (re-derived; 200 tree networks, Delaunay negative control) |
| Lemma 4.1, Corollary 4.2 | CONFIRMED (re-derived; 3,859 weighted trees with the path property) | CONFIRMED (re-derived; all trees with ≤ 11 vertices, 596,482 cases) | CONFIRMED (re-derived; all trees with ≤ 12 vertices, 2,809,849 cases) |
| Lemma 5.1 | CONFIRMED (re-derived; 191,021 colourings of strips) | CONFIRMED (re-derived; adversarial search, no violation; the bound used in the proof is attained) | CONFIRMED (re-derived; strip-level test) |
| Use of Lemma 5.2 within its hypotheses (i.i.d. marks, q ≤ q_0, colourings with ≥ k²/4 of each colour, uniformity) | CONFIRMED | CONFIRMED | CONFIRMED |
| Lemma 5.2 itself | read, not re-proved (sketch at the step to (2.6)) | read in both versions, not re-proved | read in the published version, not re-proved |
| Corollary 5.3 and the remarks on Corollary 2.3 | CONFIRMED (re-derived; exact constants) | CONFIRMED (re-derived; exact constants) | Corollary 5.3 CONFIRMED (all 16000 ≤ k ≤ 2·10⁶); two remarks on Corollary 2.3 incorrect, removed |
| Lemma 5.4 (E_1, E_2, E_3, block, Cases A and B) | CONFIRMED (re-derived; exact constants; LP relaxations) | CONFIRMED_WITH_FIXES (block count for closed squares) | CONFIRMED (block count by brute force; LP minima certified by dual solutions) |
| (2.16) of the 2021 paper fails; threshold 0.93 repairs it | CONFIRMED (LP) | CONFIRMED (exact LP; a configuration satisfying (2.13)) | CONFIRMED (Example 8.1 checked exactly, with an explicit placement) |
| Lemma 6.1 and the final chain | CONFIRMED (re-derived; simulation of the pair count) | CONFIRMED (re-derived) | CONFIRMED (t_0 independent of the route process) |
| Strength of the conclusion | CONFIRMED_WITH_FIXES (outer-probability argument supplied) | CONFIRMED_WITH_FIXES (measurability proviso) | CONFIRMED |
| Lemmas 7.1–7.2, Proposition 7.3 | CONFIRMED_WITH_FIXES (missing step in 7.2 supplied) | CONFIRMED_WITH_FIXES (same step) | CONFIRMED |
| Literature and novelty | no prior answer found | no prior answer found | no prior answer found (searches repeated) |

Required corrections, all made: the outer-probability form of Theorem 1.1 (run A) together with the measurability
proviso (run B); the missing step in Lemma 7.2 (both runs); an explicit statement of the dependence on Lemma 2.2
of the 2021 paper; the section references 5.1 (no straight segments at Poisson points) and 5.5 (Steiner tree
constant) of the source; Remark 2.1 on the degenerate segment reading; the Semantic Scholar artifact and a softer
statement on the agreement of the arXiv and published versions; the published numbering of the 2021 paper; a block
count valid for closed squares; the number of checks of the first program (13, not 14) and a wrong comment in it
(δ·16000 = 8, not 4; it affects no check); bibliographic additions (Blanc, Ann. Inst. Henri Poincaré Probab.
Stat. 60 (2024) 1356–1386, doi:10.1214/22-AIHP1354; the title of Blanc–Curien–Kahn; article number 31 of the
2021 paper).

Added when the note was written, after the two runs: Example 8.1 (a counterexample to (2.16) with exactly m²
points in every subsquare and N/3 ≤ |B| ≤ N/2; the runs had the LP values and a configuration with 1.02 m² points
per subsquare), the program `check_note.py`, and the formulation of Theorem 1.2 with t_0 independent of the route
process (the probability of E_{m,k} depends only on the Poisson process). These were examined by the run below.

## Independent verification run 2 (final text, 17 October 2026)
A further independent verification run, AI-assisted, examined the final text of the note, the additions first, and
wrote its own programs (in `reproducibility/independent_run_2/`, with recorded outputs).
- **Sources.** Read again: the published EJP 2014 paper (EMIS copy) and the LaTeX source of arXiv:1204.0817v1
  (the item is the 36th numbered statement and the 10th Open Problem; equation numbers (4)–(20) = (2.4)–(2.20));
  the published ECP 2021 paper completely (eScholarship copy) and the source of arXiv:2103.00669v1; Aldous's
  open-problem pages; the arXiv sources of the five follow-up papers.
- **Proofs.** Every proof re-derived line by line, including Sections 3, 4 and 7 and the outer-probability argument;
  Example 8.1 and the independence of t_0 from the route process confirmed (m_0 and E_{m,k} are determined by Lemma
  2.2 of the 2021 paper and the Poisson process alone). No error in the theorems, lemmas and proofs.
- **Programs.** `run2_constants.py` (39 checks): the constants of Lemmas 5.1, 5.4 and Corollary 5.3 (for all
  16000 ≤ k ≤ 2,000,000), the block count by brute force over positions, the four LP minima 194/775, 663/1550,
  98/445, 118/465 certified exactly by rational primal and dual solutions, Example 8.1 in integer arithmetic for
  m = 130, …, 390 and k ∈ {100, 200, 300, 1000} with two explicit placements of the points (m = 120 as negative
  control), the constant c to 50 digits and the interpolation in t. `run2_trees.py` (13 checks): Lemma 4.1 on all
  trees with at most 12 vertices and all W with |W| ≥ 3 (2,809,849 cases, every start vertex for n ≤ 10) and on
  20,000 random trees; Sections 3–4 on 200 Euclidean-MST networks with the structure of Section 3 computed from the
  routes alone, and compatible shortest-path routes in Delaunay networks as a negative control (circuits present,
  (T2) failing). `run2_campbell.py` (3 checks): Monte Carlo sanity check of Lemma 6.1. `check_note.py` re-run from
  the extracted source archive: output identical to the recorded one except the timing field.
- **Corrections required and made.** (1) Section 8.2 said that the recoloured colouring in the outline of
  Corollary 2.3 of the 2021 paper needs a margin over k²/4, and that the corollary does not give a bound uniform in
  the block; both remarks were not correct (recolour in the colour with fewer vertices; the block may depend on
  Ξ^k, so the worst block is allowed) and were removed; only the constants problem is kept. (2) The date (October
  17, 2026). (3) Section 1.3 no longer reads local finiteness into the hypotheses of Theorem 1.2 of the 2021 paper.
  (4) Example 8.1 now says how the points are placed. (5) This record, the Verification paragraph and Section 9.
- **Literature.** Searches repeated on 17 October 2026 (arXiv API, Crossref, zbMATH Open, OpenAlex, one web search):
  nothing new.

## Relation to the literature, novelty and scope
- **Searches (16 and 17 October 2026).** arXiv (SIRSNs, scale-invariant random spatial networks, invariant tree
  networks, route lengths, Steiner points with scale invariance, Aldous's papers in probability since 2014);
  Crossref; zbMATH Open (no work citing the 2021 paper; Kendall 2017 and Kahn 2016 cite the 2014 paper);
  Semantic Scholar (no work citing the 2021 paper; the 24 works listed as citing the 2014 paper belong to a record
  that merges it with Aldous–Ganesan, PNAS 2013, because the arXiv record of 1204.0817 carries the DOI
  10.1073/pnas.1304329110; none concerns the question); OpenAlex (citation counts 0 for the 2021 paper and 20 for
  the 2014 paper; the lists of citing works were not available, HTTP 429); Aldous's web pages; web searches.
  Repeated on 17 October 2026 by verification run 2 (arXiv API, Crossref, zbMATH Open, OpenAlex, one web search).
  - No printed answer to the question was found in these sources. A search that finds nothing is not a proof of
    novelty.
  - The follow-up papers on SIRSNs — Kendall, Ann. Probab. 45 (2017); Kahn, Ann. Probab. 44 (2016); Kendall,
    Electron. J. Probab. 25 (2020); Blanc, Ann. Inst. Henri Poincaré Probab. Stat. 60 (2024); Blanc–Curien–Kahn,
    arXiv:2407.07887 — were searched in their arXiv sources for "tree", "Steiner" and "open problem"; none
    discusses whether S(1) can be a tree.
  - The 2021 paper does not mention SIRSNs, S(1) or the open problem; it cites the SIRSN programme only through
    Aldous–Ganesan (2013), in its Section 3.5. Section 5.5 of the 2014 paper outlines an argument that the minimal
    edge-intensity of a SIRSN exceeds the Steiner tree constant, which concerns networks of minimal length only.
- **Caveats.** Lemma 2.2 of the 2021 paper is used as published and not re-proved. The measure-theoretic
  construction of S(1) is taken from the source, which omits its details; the note uses it in the form stated in
  its Section 2.1. Whether the set of outcomes without circuit is measurable is not decided.
- **Scope.** The note answers Open Problem 10 (Open Problem 36 of arXiv v1) in the affirmative for SIRSNs and weak
  SIRSNs, in both readings of "tree". No priority is claimed.

## 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/