Swap differences of powers: a conjecture of Fill and Janson on nonnegative coefficients, and two cases of their root conjecture

Abstract

In an appendix to their study of positive autocorrelation at unit lag for stationary random walk Metropolis–Hastings, Fill and Janson introduce the two-variable polynomial h(t,a;r) &= [1+(3+a)t]ʳ([1+(2+a)t]ʳ⁺¹-[1+at]ʳ⁺¹) &qquad()- [1+(1+a)t]ʳ([1+(4+a)t]ʳ⁺¹-[1+(2+a)t]ʳ⁺¹), prove that it is nonnegative for real r ≥ 1 and real a,t ≥ 0 by a Jensen argument, and then conjecture, "in passing", a considerable strengthening: that for fixed r ∈ ℕ the polynomial h(t,a;r) in (t,a) has nonnegative coefficients. We prove that conjecture, for every r ∈ ℕ. The proof rests on the observation that with P=1+(1+a)t and Q=1+(3+a)t the four inner brackets of h are exactly P ± t and Q ± t, so that h is the swap difference Qʳ((P+t)ʳ⁺¹-(P-t)ʳ⁺¹)-Pʳ((Q+t)ʳ⁺¹-(Q-t)ʳ⁺¹), together with a polynomial identity, valid over any commutative ring, that writes such a swap difference as a sum of products of P, Q, y and Q-P with nonnegative integer scalars. Since Q-P=2t here, positivity is termwise: there is no inequality and no analysis in the argument. What we actually prove is the abstract statement — if P, Q, y and Q-P all have nonnegative coefficients then so does the swap difference — of which Fill and Janson's conjecture is one instance, and we show by explicit counterexamples that neither the exponent balance (r,r+1) nor the hypothesis on Q-P can be dropped. We also settle the first two cases of Fill and Janson's second conjecture, on the roots of g(k;r)=g(k+1;r) with g(k;r)=(2k-1)ʳ/Σ_(i ≤ k)iʳ: the case k=1 has r=1 as its unique real root, and the case k=2 has a unique real root, which lies strictly between 2 and 3. Finally we close six of the thirteen inequalities on which Fill and Janson's own proof of s(r)=max_(k ≤ k₀(r))g(k;r) rests through what they describe as "the clear indication from a plot", and we do so on all of (1,∞). Every theorem below has been formally verified in Lean 4 against Mathlib.

Open review

This founding-collection manuscript received AI review before publication. Independent human review is open. Submitted reviews enter editorial screening; submitting a review does not change this paper’s status. Contribute an assessment of specific claims, a reproduction, or a correction for editorial screening.

Archived files

1. Version 1 · current (opens in a new tab)

   Source snapshot 2026-09-07 03:53 UTC

   File fingerprint

   98d572bb98ef88f69390b60970a1deaba9a298d9f6a08b42e1749c3f0b066d2e