check_note.py: 34 graphs: K_2 (n=2,d=1); K_3 (n=3,d=2); K_4 (n=4,d=3); K_5 (n=5,d=4); K_6 (n=6,d=5); C_3 (n=3,d=2); C_4 (n=4,d=2); C_5 (n=5,d=2); C_6 (n=6,d=2); C_7 (n=7,d=2); C_8 (n=8,d=2); C_9 (n=9,d=2); C_10 (n=10,d=2); C_11 (n=11,d=2); C_12 (n=12,d=2); Q_1 (n=2,d=1); Q_2 (n=4,d=2); Q_3 (n=8,d=3); Q_4 (n=16,d=4); Q_5 (n=32,d=5); S_3, all transpositions (n=6,d=3); S_4, all transpositions (n=24,d=6); S_4, adjacent transpositions (n=24,d=3); D_5{r,r^-1,s} (n=10,d=3); D_7{r,r^-1,s} (n=14,d=3); Z_2xZ_4{(1,0),(0,+-1)} (n=8,d=3); Z_3xZ_3{(+-1,0),(0,+-1)} (n=9,d=4); Z_9{+-1,+-2} (n=9,d=4); Z_13{+-1,+-5} (n=13,d=4); Z_16{+-1,+-3} (n=16,d=4); Z_16{+-3,+-5,8} (n=16,d=5); Z_21{+-2,+-7,+-9} (n=21,d=6); A_4{(012)^+-,(013)^+-} (n=12,d=4); Petersen (vertex-transitive, not Cayley) (n=10,d=3)
all are Cayley graphs except the Petersen graph, which is vertex-transitive (Remark 2.6)

PART A. Lemma 2.1, Remarks 2.2 and 2.3, Corollary 2.5
  [PASS] Lemma 2.1(a): mu_p(x) = p delta_e(x) + (q/d) sum_s mu_p(xs), sum = 1  (exact, 34 graphs x 5 values of p)
  [PASS] Lemma 2.1(b): mu_p > 0 and mu_p(e) > mu_p(x) for x != e  (exact)
  [PASS] Lemma 2.1(d): N(x)/d^|x| <= mu_p(x)/(p q^|x|) <= N(x)/d^|x| + q/p  (exact)
  [PASS] Lemma 2.1(c): mu_p = 1/n + sum_{lambda != 1} p/((1-lambda)+p lambda) Pi_lambda delta_e   max deviation 8.11e-31
  [PASS] Lemma 2.1(c): mu_p -> uniform as p -> 0 (bipartite graphs included): n max|mu_p - 1/n| at p = 1e-6   3.7e-5
  [PASS] Remark 2.2(a): lazy walk: mu'_p = mu_{p'}, p' = 2p/(1+p), and P' = (I + P_{p'})/2  (exact, 6 graphs x 3 p)
  [PASS] Remark 2.2(b): one loop per vertex: mu''_p = mu_{p''}, p'' = p(d+1)/(d+p), P'' - I = (d/(d+1))(P_{p''} - I)  (exact)
  [PASS] Remark 2.2(c): Poisson(t) mixed over an exponential time of rate theta is geometric with p = theta/(1+theta)
  [PASS] Remark 2.2(d): P_p(e,e) > 0 for p > 0 (the Metropolis chain is aperiodic)  (exact)
  [PASS] Remark 2.3: on Z_16{+-1,+-3}, p = 1/100: 5 and 6 adjacent, |6| = 2, |5| = 3, mu_p(5) > mu_p(6)  (exact)   mu_p(5)/mu_p(6) = 1.00043105738
  [PASS] Corollary 2.5: tau(p) -> tau(0) as p -> 0: |tau(1e-9) - tau(0)| < 1e-6 tau(0) on all graphs

PART B. Proposition 3.1 and Proposition 1.1 (complete graph)
  [PASS] Proposition 3.1: (delta_x1 - pi) P = beta (delta_x1 - pi), beta = 1 - 1/((n-1) pi_max); E(f,f) >= Var(f)/((n-1) pi_max)  (exact, n = 2..8, 42 random rational targets)
  [PASS] Proposition 3.1: second largest eigenvalue = beta, i.e. relaxation time (n-1) pi_max  (30 digits)
  [PASS] Proposition 1.1: mu_p(e) = (1+(n-2)p)/(n-p), mu_p(x) = (1-p)/(n-p); both forms of tau(p) agree and equal (n-1) mu_p(e)  (exact, n = 2..12, 22 values of p)
  [PASS] Proposition 1.1 / Remark 7.2: spectrum of P_p on K_n is {1, 1 - 1/tau(p), -1/(n-1) (n-2 times)}, and 1 - 1/tau(p) >= -1/(n-1)  (exact: eigenvectors and trace)
  [PASS] Proposition 1.1: d tau/dp = (n-1)^3/(n-p)^2  (symbolic)

PART C. Theorem 1.2, Corollary 4.1, Remark 4.2 (limit p -> 1)
  [PASS] Theorem 1.2: P_1 is block lower triangular for the level order and P_1(e,e) = 1  (exact, 34 graphs)
  [PASS] Theorem 1.2: row sums of B_k are 1 - d^-(x)/d with d^-(x) >= 1, and d^- = 1 on level 1; B_k >= 0  (exact)
  [PASS] Theorem 1.2: N(x) P_1(x,y) = N(y) P_1(y,x) on each level  (exact)
  [PASS] Theorem 1.2: the largest eigenvalue of the blocks B_k, k >= 1, is 1 - 1/d, and all have modulus <= 1 - 1/d
  [PASS] Theorem 1.2: P_p -> P_1 entrywise (max deviation at p = 1 - 1e-12: 1.0e-12)
  [PASS] Theorem 1.2: |tau(1-eps) - d| decreases along eps = 1e-4, 1e-8, 1e-12 and is < 1e-5 at 1e-12
  [PASS] Remark 7.2: also tau_abs(1 - 1e-12) is within 1e-5 of d
  [PASS] Corollary 4.1: cycles: tau(0) = 1/(1-cos(2 pi/n)) is < 2 for n <= 5, = 2 for n = 6, > 2 for n >= 7  (n = 3..40)
  [PASS] Remark 4.2: targets theta^|x|: relaxation time d/(1+theta) on Q_d (d = 2..5) and N(N-1)/(2(theta(N-1)+1)) on S_N with all transpositions (N = 3, 4)
  [PASS] Remark 4.2: for the targets theta^|x| the relaxation time at theta = 1e-8 is within 1e-3 of d on all 34 graphs

PART D. Theorem 1.3 (two lower bounds)
  [PASS] Theorem 1.3(a): tau(p) >= (1-p) m (1-m)/(m-p) on 34 graphs x 25 values of p (min ratio 1.0)
  [PASS] Theorem 1.3(a): equality on K_n: the bound equals (n-1) mu_p(e)  (exact)
  [PASS] Theorem 1.3(b): tau(p) >= 2 Var_p(|x|) (min ratio 1.000050005)

PART E. Corollary 1.4, Propositions 5.1 and 5.2 (hypercube)
  [PASS] Proposition 5.1(a): mu_p(x) = w(|x|), w strictly decreasing and log-convex; Fourier coefficients a_1, a_2  (exact, d = 2..5)
  [PASS] Proposition 5.1(b): E_p|x| = qd/(pd+2q), Var_p|x| = [qd/(pd+4q)][1 + pqd^2/(pd+2q)^2]  (exact)
  [PASS] Proposition 5.1(c): Dirichlet form of |x| equals E_p|x|/d, and Var/Dirichlet = H_d(p)  (exact)
  [PASS] Corollary 1.4: tau(p) >= H_d(p)  (d = 2..5, full chain)
  [PASS] Proposition 5.2: level chain: down-probability k/d, up-probability ((d-k)/d) theta_k with theta_k non-decreasing  (exact)
  [PASS] Proposition 5.2: tau of the full chain = tau of the level chain (max relative difference 3.57e-30)
  [PASS] Corollary 1.4(a): H_d(1/d) >= d(d-1)/15  (exact, d = 2..40, 64, 100, 256, 400, 1000)
  [PASS] Corollary 1.4(b): H_d(p) >= (1-p)d/(3p) whenever pd >= 4  (exact, grid of 99 values of p)
  [PASS] Corollary 1.4(c): H_d(p) - d = d q (p(d^2-2d+4) - 4)/((pd+4q)(pd+2q)); H_d(p) > d iff p > 4/(d^2-2d+4)  (exact)
  [PASS] Corollary 1.4: H_d(0+) = d/2 and H_d(1-) = d  (values at p = 1e-12 and 1 - 1e-12)
  [PASS] Corollary 1.4(c): the identity for H_d(p) - d  (symbolic)
  [PASS] Remark 6.3: 1/H_d(p) = 2/d - ((d+1)/2) p + O(p^2)  (symbolic)
  level chain (= tau by Proposition 5.2), 30 digits:   d | tau(1/d) | d(d-1)/15 | tau(1/d)/d^2 | tau(p)-d at p = (1+thr)/2, thr = 4/(d^2-2d+4)
        3 | 2.67487993 | 0.4 | 0.29721 | 0.113758
        4 | 3.87408754 | 0.8 | 0.24213 | 0.425322
        8 | 11.1075618 | 3.733333 | 0.17356 | 2.87075
       16 | 39.7652552 | 16.0 | 0.15533 | 9.72428
       17 | 44.7567518 | 18.13333 | 0.15487 | 10.6443
       32 | 157.663006 | 66.13333 | 0.15397 | 24.9767
       64 | 637.530021 | 268.8 | 0.15565 | 56.5274
  [PASS] Corollary 1.4(a), (c) on the level chain: tau(1/d) >= d(d-1)/15 and tau(p) > d at p = (1+thr)/2  (d = 3, 4, 8, 16, 17, 32, 64)

PART F. Corollary 1.5 (the steps of the proof)
  [PASS] Step 2: 1 + d + ... + d^r <= 2 d^r (d = 2..11, r < 40); log_d 32 <= 5
  [PASS] Step 4 (arithmetic): r+5 <= t <= (r+6)/kappa, P(A) = 1-(1-1/t)^(floor(r/2)+1) >= kappa/5, (3/4)(1-1/t)^t >= 1/4 for t >= 11, (kappa/5)(1/4)(r/2+1)^2 >= kappa r^2/80  (grid of kappa and r)
  [PASS] Step 1: K^j(e,x) <= 2/n + rho^(j-1), j = 1..300; Step 2: P(|X(j)| <= r) <= 2 d^r (2/n + rho^(j-1))  (10 graphs, double precision)
  [PASS] Step 4: Var(Y) >= P(A) P(B) (r/2+1)^2 for several (r, t); tau(0) <= 1/(1-rho)

PART G. Lemmas 6.1 and 6.2, Theorem 1.6, Remark 6.3 (increase at p = 0)
  [PASS] Lemma 6.2(a): (I-K) g = delta_e - 1/n, sum g = 0, g(e) > g(x) for x != e  (exact, 34 graphs)
  [PASS] Lemma 6.2(b): |mu_p(x) - 1/n - p g(x)| <= C_1 p^2, C_1 = 2n/(1-lambda_2)^2, p = 1/2, 1/4, 1/10, 1/100, 1e-4 (max of lhs/(C_1 p^2): 0.1667)
  [PASS] Lemma 6.2(c): max entry of |S(p) - (I-K) - p S_1| / p^2 stays bounded as p = 1e-2, 1e-3, 1e-4, 1e-5 (largest value at 1e-5 over all graphs: 1151.2)
  [PASS] Lemma 6.2(d): <f, S_1 f> = -(1/2)(n f(e)^2 - sum f^2) - (n/4) Gamma(f)  (exact, 4 random integer f per graph)
  [PASS] Theorem 1.6: n f_0(e)^2 = m_2; Gamma(f_0) > 0 and c_0 > 0; s* >= c_0
  [PASS] Theorem 1.6: tau(p) > tau(0) at p = 1e-4, 1e-6, 1e-8 on all graphs
  [PASS] Theorem 1.6: [1/tau(0) - 1/tau(p)]/p -> s*: deviation decreasing along p = 1e-4, 1e-6, 1e-8 and < 1e-5 max(1,s*) at 1e-8
  graph | n | d | m_2 | tau(0) | c_0 | s* | [1/tau(0)-1/tau(p)]/p - s* at p = 1e-4, 1e-6, 1e-8
    K_2                          |  2 | 1 | 1 | 0.5 | 1.0 | 1.0 | -4.24e-27, -7.54e-25, -4.2e-23
    K_3                          |  3 | 2 | 2 | 0.666666667 | 2.0 | 2.0 | -0.0002, -2.0e-6, -2.0e-8
    K_4                          |  4 | 3 | 3 | 0.75 | 3.0 | 3.0 | -0.0006, -6.0e-6, -6.0e-8
    K_5                          |  5 | 4 | 4 | 0.8 | 4.0 | 4.0 | -0.0012, -1.2e-5, -1.2e-7
    K_6                          |  6 | 5 | 5 | 0.833333333 | 5.0 | 5.0 | -0.002, -2.0e-5, -2.0e-7
    C_3                          |  3 | 2 | 2 | 0.666666667 | 2.0 | 2.0 | -0.0002, -2.0e-6, -2.0e-8
    C_4                          |  4 | 2 | 2 | 1.0 | 1.5 | 1.5 | -0.0002, -2.0e-6, -2.0e-8
    C_5                          |  5 | 2 | 2 | 1.4472136 | 1.381966011 | 1.381966011 | -0.00038, -3.8e-6, -3.8e-8
    C_6                          |  6 | 2 | 2 | 2.0 | 1.25 | 1.25 | -0.000548, -5.48e-6, -5.48e-8
    C_7                          |  7 | 2 | 2 | 2.65597056 | 1.162011348 | 1.162011348 | -0.000741, -7.42e-6, -7.42e-8
    C_8                          |  8 | 2 | 2 | 3.41421356 | 1.085786438 | 1.085786438 | -0.000949, -9.49e-6, -9.49e-8
    C_9                          |  9 | 2 | 2 | 4.27431609 | 1.027260923 | 1.027260923 | -0.00118, -1.18e-5, -1.18e-7
    C_10                         | 10 | 2 | 2 | 5.23606798 | 0.9774575141 | 0.9774575141 | -0.00143, -1.43e-5, -1.43e-7
    C_11                         | 11 | 2 | 2 | 6.29935278 | 0.9368638431 | 0.9368638431 | -0.00169, -1.7e-5, -1.7e-7
    C_12                         | 12 | 2 | 2 | 7.46410162 | 0.9019237886 | 0.9019237886 | -0.00198, -1.98e-5, -1.98e-7
    Q_1                          |  2 | 1 | 1 | 0.5 | 1.0 | 1.0 | -4.24e-27, -7.54e-25, -4.2e-23
    Q_2                          |  4 | 2 | 2 | 1.0 | 1.5 | 1.5 | -0.0002, -2.0e-6, -2.0e-8
    Q_3                          |  8 | 3 | 3 | 1.5 | 2.0 | 2.0 | -0.000483, -4.83e-6, -4.83e-8
    Q_4                          | 16 | 4 | 4 | 2.0 | 2.5 | 2.5 | -0.000645, -6.44e-6, -6.44e-8
    Q_5                          | 32 | 5 | 5 | 2.5 | 3.0 | 3.0 | -0.000259, -2.55e-6, -2.55e-8
    S_3, all transpositions      |  6 | 3 | 4 | 1.0 | 3.333333333 | 3.333333333 | -0.00102, -1.02e-5, -1.02e-7
    S_4, all transpositions      | 24 | 6 | 9 | 1.5 | 6.625 | 6.625 | 0.000318, 3.37e-6, 3.37e-8
    S_4, adjacent transpositions | 24 | 3 | 3 | 5.12132034 | 1.627628326 | 1.628940236 | -0.00231, -2.31e-5, -2.31e-7
    D_5{r,r^-1,s}                | 10 | 3 | 2 | 2.17082039 | 1.381966011 | 1.381966011 | -0.000403, -4.03e-6, -4.03e-8
    D_7{r,r^-1,s}                | 14 | 3 | 2 | 3.98395583 | 1.162011348 | 1.162011348 | -0.0011, -1.1e-5, -1.1e-7
    Z_2xZ_4{(1,0),(0,+-1)}       |  8 | 3 | 3 | 1.5 | 2.0 | 2.0 | -0.000483, -4.83e-6, -4.83e-8
    Z_3xZ_3{(+-1,0),(0,+-1)}     |  9 | 4 | 4 | 1.33333333 | 3.0 | 3.0 | -0.000834, -8.33e-6, -8.33e-8
    Z_9{+-1,+-2}                 |  9 | 4 | 2 | 1.88624548 | 1.379229865 | 1.379229865 | -0.000345, -3.45e-6, -3.45e-8
    Z_13{+-1,+-5}                | 13 | 4 | 4 | 1.52508935 | 2.915030581 | 2.915030581 | 0.000838, 8.41e-6, 8.41e-8
    Z_16{+-1,+-3}                | 16 | 4 | 2 | 2.884184 | 1.29809586 | 1.29809586 | -0.000592, -5.92e-6, -5.92e-8
    Z_16{+-3,+-5,8}              | 16 | 5 | 2 | 4.26776695 | 1.085786438 | 1.085786438 | -0.00115, -1.15e-5, -1.15e-7
    Z_21{+-2,+-7,+-9}            | 21 | 6 | 2 | 3.98395583 | 1.162011348 | 1.162011348 | -0.001, -1.0e-5, -1.0e-7
    A_4{(012)^+-,(013)^+-}       | 12 | 4 | 3 | 2.0 | 2.0 | 2.0 | -0.000669, -6.69e-6, -6.69e-8
    Petersen (vertex-transitive, not Cayley) | 10 | 3 | 5 | 1.5 | 3.666666667 | 3.666666667 | -0.00224, -2.24e-5, -2.24e-7
  [PASS] Remark 6.3: s* = n-1 on K_n (n = 2..6); s* = c_0 = (d+1)/2 on Q_d (d = 1..5); S_4 with adjacent transpositions: c_0 = 1.62762833 < s* = 1.62894024
  [PASS] Lemma 6.1: |sigma_k(A_0 + p A_1 + p^2 R) - sigma - p nu| <= (2a^2/gamma + C_0) p^2 for p <= gamma/(4a)  (300 random symmetric matrices, 3 values of p; max ratio 0.2171)

PART H. Section 7 (Table 1, comparison bound, absolute gap, shapes)
  [PASS] Remark 7.1: tau(p) <= tau(0) max mu_p / min mu_p  (all graphs, 5 values of p)
  [PASS] Remark 7.2: tau_abs(p) = 1/p on K_2, = 2 on K_3, = max(tau(p), (n-1)/(n-2)) on K_n (n = 4, 5, 6)
  [PASS] Remark 7.2 (computation): odd cycles C_5, C_7, C_9, C_11: tau_abs(0) = 1/(1-cos(pi/n)) and tau_abs(p) < tau_abs(0) at p = 1e-2, 1e-4, 1e-6
  [PASS] Remark 7.2: tau_abs(0) is infinite exactly on the bipartite graphs of the list
  shapes on the grid p = j/200, j = 0..199 (computation):  graph | tau(0) | turning points (p, tau) | tau(199/200) | d
      C_12                 | 7.4641016 | max at p = 0.08: 8.8492473 | 2.1841599 | 2
      Q_5                  | 2.5 | max at p = 0.47: 5.9834968 | 5.0149649 | 5
      Z_16{+-3,+-5,8}      | 4.267767 | max at p = 0.23: 5.6834186; min at p = 0.815: 4.8107715 | 4.9910747 | 5
      Z_21{+-2,+-7,+-9}    | 3.9839558 | max at p = 0.41: 5.9229417; min at p = 0.725: 5.854211 | 5.9947776 | 6
      K_5                  | 0.8 | none | 3.980025 | 4
  [PASS] Remark 7.3 (computation): on this grid K_5 is increasing, C_12 and Q_5 go up and then down, Z_16{+-3,+-5,8} and Z_21{+-2,+-7,+-9} go up, down and up

TOTAL failures: 0      (33 s)
