Lattice paths · enumerative combinatorics
Draw a square grid, n steps wide and n steps tall. A traveller starts at the bottom-left corner and walks to the top-right, always going one step east or one step north, never back. There are a great many such routes. Now put a roadblock on one crossing, and ask a simple question: which crossing near the start carries the most surviving routes?
The natural answer is the crossing one step east and one step north, the point (1,1), because it sits on the fat middle of the traffic. And usually it wins. But Gil, Liang, Odetola and Weiner noticed something strange. If you put the roadblock on the anti-diagonal, the line running from the top-left corner to the bottom-right one, then for small and medium boards the winner flips: the point (1,0), sitting flat on the bottom edge, beats it.
They checked every board size up to 495. The flip happens for every size from 8 up to 375. Then it starts to flicker: some sizes yes, some sizes no, in a pattern they described as irregular, until it stops at 375…495. They conjectured it never happens again, for any board size at all. That is what this note proves, and the figure below is the moment it dies.
The paper is five days old at the time of writing. It states the conjecture, verifies it by computer to n = 495, and asks three questions about it. Here is what came out of one session.
Everything below is the technical version. If you read only one more thing, make it figure 2: it is the rounding mechanism, and it is the reason the pattern looked irregular.
Gil, Liang, Odetola and Weiner [GLOW] (arXiv:2609.01562, 1 September 2026) count monotone lattice paths from (0,0) to (n,n) that avoid a forbidden point B, and ask which point A carries the most B-avoiding traffic. They prove that for n ≥ 9 the maximum is attained at one of ten near-corner points whatever B is; they observe that an obstruction B = (a, n−a) on the antidiagonal moves the maximum from (1,1) to the boundary point (1,0) for every 8 ≤ n ≤ 375 and sporadically up to n = 495; and they conjecture (Conjecture 7.4) that this anomaly never reappears for n ≥ 496.
We prove the conjecture, in strict form. Their criterion is the integer inequality a(n−2a+1)·C(n,a)² > (n−1)·C(2n−2,n−1) (Lemma 1). A Robbins–Stirling bound shows that ρ(n) = maxa Rn(a) is below 0.9939 for every n ≥ 3000 (Theorem A), and exact integer arithmetic settles 496 ≤ n ≤ 2999 (Theorem A′, certificate shipped). We also prove ρ(n) → c0 = √(8/π)e−1/2 = 0.96788…, more precisely ρ(n) = c0(1 + 1/√(2n) + O(1/n)) (Theorem B), which places the transition at n ≈ 454; and we show that Rn(a) is log-concave in a with real maximiser n/2 − x*(n), x*(n) = (√(2n+1)−1)/4, so that the sporadic pattern on 376 ≤ n ≤ 495 is the rounding of that number to an integer, alternating with the parity of n (Proposition C). This answers questions (1) and (2) of [GLOW, §7].
| Result | Label | Scope |
|---|---|---|
| Conjecture 7.4: ρ(n) < 1 for all n ≥ 496 | Proved | Analytic for n ≥ 3000; exact finite case analysis for 496…2999 |
| Criterion = Catalan inequality (Lemma 1) | Proved | All n ≥ 3 |
| ρ(n) < U(n) ≤ 0.9939 (Theorem A) | Proved | n ≥ 3000; final numeric step in exact rationals |
| ρ(n) < 1 on 496 ≤ n ≤ 2999 (Theorem A′) | Certified | Exact integers, 12 s, certificate committed |
| ρ(n) = c0(1 + 1/√(2n) + O(1/n)) (Theorem B) | Proved | O(1/n) not made explicit |
| Log-concavity of Rn(·) (Proposition C(a)) | Proved | All n ≥ 3 |
| Maximiser within 1 of n/2 − x*(n) | Certified | 3 ≤ n ≤ 3000 only |
| The 455 anomalous n below 496, listed exactly | Certified | Exact integers |
| Rounding-penalty explanation of the pattern | Numerical | Model, not a theorem |
| Control: [GLOW, Prop. 7.2] re-derived from the definition | Certified | 9 ≤ n ≤ 120, 0 mismatches |
Let 𝓟n be the monotone lattice paths from (0,0) to (n,n). For grid points A, B let fB(A) be the number of paths through A avoiding B. With A = (a1,b1), B = (c,d) and A south-west of B,
[GLOW] prove (Theorems 3.6, 4.4, 5.1) that for n ≥ 9 and every B, the maximum of fB is attained at one of the ten points (1,0), (0,1), (1,1), (2,1), (1,2) and their images under (x,y) ↦ (n−x, n−y). For B = (a, n−a) on the antidiagonal with 2a < n they show (their Proposition 7.2) that fB(1,0) > fB(1,1) exactly when Rn(a) > 1, where
Throughout we write x := n/2 − a, so that 2x + 1 = n − 2a + 1 and 0 ≤ x ≤ n/2 − 1.
One caveat to state up front, since it is load-bearing. The statement proved here is about ρ(n). Turning "ρ(n) < 1" into "the boundary point never wins" uses [GLOW]'s own ten-point theorem and their Proposition 7.2, taken as published. We re-derived Proposition 7.2 from the definition of traffic, at every grid point, only for 9 ≤ n ≤ 120 (0 mismatches; allpoints_control.py).
For n ≥ 3 and 1 ≤ a ≤ n/2,
G(n,a) = C(n,a)²·a(n−2a+1)/(n(n−1)), D(n) = C(2n−2,n−1)/n = Cat(n−1),
so that Rn(a) = a(n−2a+1)·C(n,a)² / ((n−1)·C(2n−2,n−1)), and Rn(a) > 1 if and only if a(n−2a+1)·C(n,a)² > (n−1)·C(2n−2,n−1).
Proof. C(n−2,a−1) = (n−2)!/((a−1)!(n−a−1)!) = C(n,a)·a(n−a)/(n(n−1)); substitute into G and cancel n−a. The second identity is the definition of the Catalan number. ∎
So in the unobstructed grid the margin f(1,1) − f(1,0) is a Catalan number, and the obstruction subtracts G(n,a) from it. The anomaly is the event that a single roadblock destroys more than Cat(n−1) of the advantage. This is the simplification asked for in [GLOW, §7, question (1)].
The Stirling tools are Robbins' two-sided factorial bound (Lemma 2, cited via Feller §II.9, secondary source, not re-derived here), the resulting two-sided bound on C(n,a) (Lemma 3), the entropy inequality t² ≤ (1+t)log(1+t) + (1−t)log(1−t) ≤ t² + t⁴/(6(1−t²)) (Lemma 4) and the central binomial bound (4m/√(πm))e−1/(6m) < C(2m,m) < 4m/√(πm) (Lemma 5). Full statements and proofs are in the note.
Write φn(x) = (2x+1)e−4x²/n and x*(n) = (√(2n+1)−1)/4. Lemma 6 shows φn rises on [0, x*] and falls after it, with an explicit value at the peak.
For every n ≥ 3000 and every integer a with 1 ≤ a ≤ n/2,
Rn(a) < U(n) := c0·√(n/(n−1))·(1 − 1/√(2n))−1·exp( 1/√(2n) + 1/(3(n−1)) ),
with c0 = √(8/π)e−1/2 = 0.967882…, and U(n) ≤ U(3000) < 0.9939. In particular ρ(n) < 1 for all n ≥ 3000.
Proof sketch. Put x = n/2 − a. Lemma 1, the upper bound of Lemma 3 squared, the upper bound of Lemma 4 squared, and the lower bound of Lemma 5 at m = n−1 give
Since a ≤ n/2 we have n/(n−a) ≤ 2; bounding φn(x) ≤ φn(x*) by Lemma 6 collapses everything to U(n), each of whose three correction factors decreases in n. ∎
The final numeric step is the one place a proof of this shape usually leaks floating point, so it is done in exact rational arithmetic (check_bound.py, Fraction only, with ey ≤ 1/(1−y) standing in for the exponential):
| Step | Rational bound used | Verdict |
|---|---|---|
| π from Machin's formula, alternating-series bracketing | π > 3.1415926526 | OK |
| e from a Taylor partial sum | e > 2.7182815256 | OK |
| c0² = 8/(πe) | c0² ≤ 0.9367974091, so c0 < 0.96808 | OK |
| √(3000/2999) | < 1.00017 | OK |
| u = 1/√6000 | < 0.01291, so (1−u)−1 < 1.013079 | OK |
| y = u + 1/8997 | y = 0.01302115, ey ≤ 1/(1−y) < 1.013194 | OK |
| U(3000) | < 0.99384915 | OK |
Output of check_bound.py, reproduced verbatim from results_check_bound.txt: eight lines, all OK, ending ALL CERTIFIED.
ρ(n) < 1 for every n ≥ 496. Consequently, for every n ≥ 496 and every obstruction B = (a, n−a) on the antidiagonal, the boundary point (1,0) carries strictly less traffic than (1,1): the antidiagonal anomaly never reappears.
Proof. For n ≥ 3000 this is Theorem A. For 496 ≤ n ≤ 2999 the script verify_anomaly.py evaluates the integer inequality of Lemma 1 for every 1 ≤ a ≤ n/2, in exact integer arithmetic with running-product binomials and no floating point, and finds no anomalous a. The per-n record (maximising a, number of anomalous a, ⌊109ρ(n)⌋) is the committed certificate certificate_3_3000.csv; the run takes 12 s on one core. The "consequently" is [GLOW, Proposition 7.2] with their ten-point theorem. ∎
The largest value on that range is ρ(497) = 0.999955284, attained at a = 241. On the other side, ρ(495) = 1.000024. The threshold is real but the margin is about two parts in a hundred thousand, which is worth keeping in mind when reading the figures.
On the label. Theorem A is a proof for n ≥ 3000. The finite range 496 ≤ n ≤ 2999 is an exact, reproducible computation shipping a certificate, and on its own it is Certified, not proved. Together they establish the conjecture for all n ≥ 496, and the combined statement is Proved in the sense that a finite exact case analysis is a legitimate step in a proof. A reader who declines to accept computer-checked finite case analysis should read the result as: proved for n ≥ 3000, verified for 496 ≤ n ≤ 2999.
The same computation reproduces [GLOW]'s data below 496 and sharpens it. Anomalous n: every 3 ≤ n ≤ 375 (373 values, the paper reports from 8), then exactly
377, 379–422, the even 424–462, 464, 465, and the odd 467–495
which is 82 values, 455 in all on [3, 3000]. The paper printed only "intermittently up to 495".
ρ(n) → c0 = √(8/π)e−1/2 = 0.9678828980…, more precisely ρ(n) = c0(1 + 1/√(2n) + O(1/n)). In particular the envelope c0(1 + 1/√(2n)) crosses 1 at n ≈ 454.
The proof works with Fn(x) = log(2x+1) − 4x²/n − log(1 + 2x/n), shows it is concave, locates its maximiser within 1 of x*, and matches the upper bound of (3.1) with a lower bound obtained from the lower halves of Lemmas 3 and 4 at a well-chosen integer an. The O(1/n) is not made explicit; that is the one gap between this section and a fully quantitative transition analysis.
Numerically the remainder behaves as advertised. With exact ratios ρ(3000) = 0.980606160, ρ(10000) = 0.974795079, ρ(30000) = 0.971852232, the quantity n(ρ(n)/c0 − 1 − 1/√(2n)) reads 0.707, 0.705 and 0.557, consistent with a remainder of size about 0.6/n. That last sentence is Numerical: three points are not an asymptotic.
(a) For n ≥ 3 the sequence a ↦ Rn(a) on 1 ≤ a ≤ ⌊(n−1)/2⌋ is log-concave, hence unimodal, because
Rn(a+1)/Rn(a) = (n−a)²(n−2a−1) / ( a(a+1)(n−2a+1) )
is a product of three positive factors each decreasing in a. Proved
(b) The integer maximiser an satisfies |an − (n/2 − x*(n))| ≤ 1 for every 3 ≤ n ≤ 3000. Certified on that range only.
(c) is the explanation, and it is a Numerical model rather than a theorem. Write δn for the distance from the real maximiser to the nearest admissible integer position. Then ρ(n) is a smooth envelope diminished by a rounding penalty of roughly exp(−8δn²/n). Near the threshold the envelope exceeds 1 by only 0.1 to 0.3 per cent, while the penalty ranges from 0 to about 8·(1/2)²/n ≈ 0.4 per cent. So on 376 ≤ n ≤ 495 the anomaly survives exactly when δn is small.
The parity alternation follows. x* drifts slowly, from 7.00 at n = 420 to 7.50 at n = 480, while n/2 is a whole number for even n and a half-integer for odd n. Around 420 the even sizes round well and the odd ones badly; around 480 the roles have swapped. Which is exactly the observed list: the even numbers survive to 462, the odd ones to 495.
Still open. An explicit description of the exact anomalous set from the cubic of Proposition C(a) and Theorem B's expansion with explicit constants; and a lower bound ρ(n) ≥ c0(1 + 1/√(2n) − C/n) with a numerical C, which would turn the transition analysis of section 6 from explanatory into rigorous.
| Script | What it does | Cost |
|---|---|---|
verify_anomaly.py 3 3000 certificate_3_3000.csv | Exact integer verification of Lemma 1's inequality for every n, a; writes the certificate | 12 s, one core, Python 3.11, no dependencies |
check_bound.py | The rational-arithmetic evaluation of U(3000) in Theorem A (Fraction only) | instant |
allpoints_control.py 120 | Independent control of [GLOW, Prop. 7.2]: computes fB at all grid points for every antidiagonal B and checks both the argmax and the criterion | 9 ≤ n ≤ 120, 0 mismatches |
transition_table.py | The table behind figures 1 and 2 (n, an, x*, δn, ρ(n)) | instant |
Run them from inside conjectures/antidiagonal-anomaly/: the scripts reference data files by bare relative name.