# Verification report — AMR-096-0015 (Aldous's conjecture on excursion lengths of a uniform Eulerian circuit of the complete graph)

Verification date: 2026-09-30.

**Verdict.** The conjecture holds exactly in the range i = o(n^{3/2}) and fails beyond it. Let N_i be the number of
length-i excursions from a fixed vertex in a uniform Eulerian circuit of the bidirected K_n. For i = i(n) ≥ 2,
E N_i ~ e^{−i/n} holds if and only if i = o(n^{3/2}). This range contains fixed i, the scale i ~ xn, and essentially all
excursions. More precisely:
- E N_i = exp(−i/n − i²/(2n³))(1 + O_K(n^{−1/2} log n)) uniformly in 2 ≤ i ≤ K n^{3/2};
- E N_i e^{i/n} → 0 when i/n^{3/2} → ∞;
- the length of a uniformly chosen excursion, divided by n, converges in distribution to Exp(1).

The literal reading "for all i" is false, but only at the scale n^{3/2} and beyond. The note is unrefereed.

## Statement checked
- **Primary source.** D. Aldous and J. Yu, "Random Eulerian circuits", Open Problems in Mathematics 2 (2014), 4 pp.,
  example (a) on p. 4 (sponsor P. Diaconis).
  - Two copies were read: the Wayback copy of opmath.org and Aldous's own copy
    (stat.berkeley.edu/~aldous/Papers/aldous_eulerian.pdf). The text is identical.
  - Setting: the complete n-vertex graph, with each edge replaced by two directed edges.
  - Wording: the natural conjecture is that "the expected number of length-i excursions is asymptotic to e^{−i/n}".
  - The source's aside "n excursions, each of mean length n − 1" is a slip. There are n − 1 excursions of mean length n,
    which does not matter asymptotically.
- **Aldous's open-problem index** (stat.berkeley.edu/~aldous/Research/OP/index.html). It lists the whole topic
  "Random Eulerian circuits". The "(2.2)" next to it is Aldous's rating on his conceptual–technical spectrum, not a
  problem number, and the index does not single out example (a).
- **Aldous's talks** of 6 April 2022 (Bristol) and 24 February 2023 (UCSB). Both pose the torus problem as open and say
  there is very little literature on uniform random Eulerian circuits. Neither mentions the complete graph.
- **Corpus record.** ulamai/UnsolvedMath v1.6.0, record AMR-096-0015, "Excursion counts in a random Eulerian circuit
  on a complete graph", status `open`. Its question is whether the expected number of length-i excursions is
  asymptotic to e^{−i/n}.

## Readings
| Reading | Answer | Where |
|---|---|---|
| For each fixed i ≥ 2, E N_i → 1 (= lim e^{−i/n}) | yes | Cor. 1.3(a) |
| For each fixed x > 0, E N_{⌈xn⌉} → e^{−x} (the natural scale) | yes | Cor. 1.3(a) |
| E N_i ~ e^{−i/n} for every sequence i = i(n) ≥ 2 with i = o(n^{3/2}), uniformly | yes | Thm 1.1, Cor. 1.3(a) |
| Distributional form: (length of a uniform excursion)/n → Exp(1) | yes, with Kolmogorov distance O(n^{−1/2} log n) | Cor. 1.3(c) |
| E N_i ~ e^{−i/n} uniformly over all i ≥ 2 (literal) | no; at i ~ y n^{3/2} the ratio tends to e^{−y²/2}, and to 0 when i/n^{3/2} → ∞ | Thm 1.1, Thm 1.2 |
| i = 1 | trivially excluded (N_1 = 0: no loops) | Intro |

## Results in the paper
- **Lemmas 2.1–2.4 (exact representation).**
  - E N_i = (n − 1) P(τ = i), where τ is the first-excursion length of a uniform rooted circuit.
  - A uniform rooted circuit is generated by the Kandel–Matias–Unger–Winkler walk (BEST theorem).
  - At the j-th visit of w before τ, the walk returns to v with hazard 1{w ∉ A}/(n − 1 − j). The case j = n − 1 occurs
    only at w = X_1 ∈ A, with hazard 1.
  - A change of measure to an auxiliary walk that avoids v, with absorbed paths handled explicitly, gives
    E N_i = (n − 1) μ[W_i] (formula (2)).
- **Remark 2.5.** An independent exact formula via BEST and the directed matrix-tree theorem, used as a check.
- **Remark 2.6.** Closed forms E N_2 = (n − 1)/n and E N_3 = (n − 1)(n² − 3n + 3)/(n²(n − 2)).
- **Lemmas 3.1–3.4.**
  - Landing probabilities.
  - Visit counts, via a stopped exponential supermartingale.
  - The root degree: C − 1 ~ Bin(n − 2, 1/n).
  - The deterministic convexity bound S_i ≥ f(m), with inequality (3).
- **Theorem 1.1.** For every K, |E N_i exp(i/n + i²/(2n³)) − 1| ≤ C_K n^{−1/2} log n for 2 ≤ i ≤ K n^{3/2}.
- **Theorem 1.2.** For n ≥ 23 and all i ≥ 2, E N_i ≤ e^{−i/n}(12 e^{−(i−2)²/(2n³)} + ε_n) with an explicit ε_n → 0.
  - The constants are not optimized. By a numerical evaluation, ε_n < 1 only for n ≳ 5.9·10^5, so the theorem is
    asymptotic in content.
- **Corollary 1.3.**
  - (a) The limit e^{−y²/2}, and the "if and only if i = o(n^{3/2})".
  - (b) Σ_i |E N_i − e^{−i/n}| = O(n^{1/2} log n). This uses only Theorem 1.1 and Σ_i E N_i = n − 1.
  - (c) Λ_n/n → Exp(1), with E Λ_n = n.

## Computations (scripts and outputs in reproducibility/)
Exact computations are sanity checks; the proofs are not computer-assisted.
- **Finder** (`claimant/`).
  - `exact_small.py` enumerates all 256 (n = 4) and 972,000 (n = 5) Eulerian circuits, in exact rationals.
  - It checks them against two independent dynamic programs, one for the tree walk and one for the hazard identity,
    over all n^{n−2} trees. All values agree; for example E N_5 = 1624/3375 at n = 5.
  - `is_mc.c` is an unbiased importance sampler based on formula (2), run for n = 5 … 6400 (TESTED). It produces the
    table of Section 7 via `tables.py`.
- **Referee 1** (`referee/referee1/`, independent code, 2026-09-29).
  - `direct_sim.c`: full uniform circuits with Aldous–Broder trees. It matches the exact n = 5 values (|z| ≤ 1.5) and
    the finder's sampler at n = 60.
  - `is_mine.c`: an independent importance sampler with Aldous–Broder trees. It reproduces the table for
    n = 400, 1600, 6400.
- **Referee 2** (`referee/referee2/`, independent code, written before reading the finder's scripts, 2026-09-30).
  - `bf.c`: brute force for n = 3, 4, 5, counting excursions from every vertex.
  - `best.c`: the formula of Remark 2.5 in exact integer arithmetic for n = 3 … 6. It agrees with the brute force for
    n ≤ 5 and gives the exact n = 6 values, e.g. E N_2..E N_5 = 5/6, 35/48, 5/8, 7405/13824, with Σ E N_i = 5 and
    Σ i E N_i = 30.
  - `hz_exact.c`: for n = 4, 5, 6, over all trees, dynamic programs for the literal walk and for the hazard form. They
    agree with best.c to within 2·10^{−12}. At every state they check the hazard formula (1), the count of used
    out-arcs, and that j = n − 1 occurs only at X_1.
  - `direct_mc.c`: full circuits with Wilson trees, validated at n = 6 (`d6.txt`), run at n = 100 and 200.
  - `is_mine.c`: an importance sampler with Wilson trees, validated at n = 6 (`is6.txt`), run at n = 400, 1600, 6400.
- **Lead** (`lead/`, 2026-09-30).
  - `exact_checks.py` cross-checks all exact outputs as rationals. It covers the finder vs referee brute force vs BEST,
    the floating-point DPs, the closed forms of Remark 2.6, and E C, E D_2 by enumerating all trees for n ≤ 8.
  - `check_constants.py` checks every constant and elementary inequality of Sections 3–5, in exact rational arithmetic
    on finite ranges. Examples: inequality (3) for all n ≤ 30, i ≤ n(n − 1) and c' ≤ i − 2; E e^{C/8} ≤ 1.2946;
    2e^{1.5}·1.2946 < 12; the Range II thresholds. It also evaluates ε_n and finds ε_n < 1 from n ≈ 5.9·10^5 on.
  - `corollary_mc.py` (TESTED) computes Σ_i |E N_i − e^{−i/n}| ≈ 2.16 (n = 100) and ≈ 2.18 (n = 400) from full-range
    importance-sampling runs.
  - The lead also reran every finder and referee exact program, and they reproduced their recorded outputs
    byte-for-byte.

## Independent adversarial audit
Two independent verifications: round 3 (2026-09-29) and a second one for the paper stage (2026-09-30). Both classified
the claim as PAPER_CANDIDATE, correct, and answering the question as intended.

| Item | Verdict |
|---|---|
| Statement fidelity | CONFIRMED (source read directly by both verifiers) |
| Proofs | CONFIRMED (both checked every lemma and theorem line by line; no mathematical error) |
| Computations | CONFIRMED (all finder outputs reproduced byte-for-byte; independent exact and Monte Carlo code agrees) |
| Answer as posed | CONFIRMED (proved in the intended sense; literal "all i" reading false only beyond n^{3/2}) |
| Novelty | CONFIRMED as far as can be checked (no priority claim) |
| Presentation | CONFIRMED_WITH_FIXES |

All required fixes were applied:
1. Full proof of the visit-count lemma. It now covers the stopped supermartingale, the first step
   (P(X_1 = u) = 1/(n − 1) ≤ q), absorbed paths, and the inclusion G ⊆ {M_{N−1} ≤ L} with N = i − 2 (Lemma 3.2, §4).
2. Lemma 2.3(iii): if X_1 ∉ A, the walk returns to v at the (n − 2)-th visit of X_1, so j = n − 1 occurs only when
   X_1 ∈ A.
3. Theorem 1.2 is stated for all n ≥ 23 with an explicit ε_n, and the text says that ε_n < 1 only for n ≳ 5.9·10^5.
4. The distributional corollary was added (Cor. 1.3(b), (c)).
5. The error rate and the numerics:
   - "for i = xn the ratio is 1 + O(1/n)" is now labelled a numerical observation;
   - the numerics suggest an O(n^{−1/2}) error at fixed y, with next term ≈ −y³/(3√n);
   - all Monte Carlo results are labelled TESTED.
6. The "(2.2)" wording and the scope of Aldous's index were corrected.
7. Optional: the BEST + matrix-tree formula and the exact n = 6 values were added (Remark 2.5, §7).
8. Literature:
   - the six arXiv queries that had returned HTTP 429 were repeated successfully, and six new ones were run;
   - the citation search on Aldous–Yu 2014 was attempted again via OpenAlex and Semantic Scholar (see below);
   - one web search was made for citing works.

**One change beyond the fixes.** In the proof of Theorem 1.1 the cut-off L = ⌊n^{3/4}⌋ was replaced by
L = ⌈√n log n⌉, which improves the error from O(n^{−1/4}) to O(n^{−1/2} log n). The argument is unchanged, and all error
terms were rederived by the lead:
- μ(G^c) ≤ n e^{−2√n log n};
- αq = n^{−3}(1 + O(L/n));
- the lower-bound terms e^{−7K n^{−1/2}} and 1 − 5/n;
- the upper-bound factors (1 + 2L/n) e^{27K n^{−1/2} + 2L/n}.

The verifiers checked the n^{−1/4} version, and the paper says so in its Verification paragraph.

## Relation to the literature, novelty and scope
- **Searches** (finder 2026-09-29, two verifiers, lead 2026-09-30; every request logged in `queries.log`, anonymous,
  no personal data).
  - arXiv API: "random/uniform Eulerian", "Eulerian circuit(s)" with excursion, random, spanning tree, complete graph;
    "Euler tour(s)" with random, excursion, complete graph; BEST theorem with random; Aldous with Eulerian;
    Eulerian in math.PR titles.
  - Crossref, zbMATH, Aldous's web pages, and one web search each by the finder, both verifiers and the lead.
  - Hits concern counting (McKay–Robinson 1998; Isaev 2011, 2013; Creed–Cryan 2013), sampling
    (Kandel–Matias–Unger–Winkler 1996; Tetali–Vempala 2001; Anari 2026), the last-exit-tree bijection
    (Hu–Lyons–Tang), multi-Eulerian tours (Farrell–Levine), rotor-router walks and Markov loops. None concerns
    excursion lengths.
  - OpenAlex and Semantic Scholar (the citation search on Aldous–Yu 2014): see the final paragraph of this section.
- **Novelty.** No prior result on excursion lengths of uniform Eulerian circuits of K_n was found, and no statement of
  the correction factor e^{−i²/(2n³)} or of the n^{3/2} threshold. This negative search is not a proof of priority.
- **Scope.**
  - The note settles example (a) of Aldous–Yu 2014 in the sense stated above.
  - Still open: the main torus conjecture of that article, its d = 2 variant, and example (b) on the Hamming cube.
  - Also open: the second-order term, and the precise behaviour of E N_i for n^{3/2} ≪ i ≤ n(n − 1). Theorem 1.2 gives
    only an upper bound there.

- **Citation search on Aldous–Yu 2014 (required fix).**
  - Semantic Scholar returned HTTP 429 (rate limit) in all attempts: once by verifier 2 and three times by the lead
    on 2026-09-29/30.
  - OpenAlex returned HTTP 429 (anonymous daily budget exhausted) to the finder, to verifier 2 and to the lead
    before 00:00 UTC. After the daily reset it returned HTTP 503 three times to the lead ("anonymous search is
    paused while the search cluster recovers").
  - The Aldous–Yu article has no DOI, so Crossref and OpenCitations cannot list its citations.
  - A web search for works citing it (2026-09-30) found only Aldous's own pages, McKay–Robinson, Farrell–Levine and
    Anari. None concerns excursion lengths.
  - So a systematic citation search was not possible, and the paper says so. It should be repeated with an API key
    before any journal submission.

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