Theorem 10 — under #ETH no algorithm counts proper -colorings on supplied layouts
OpenSubspaceConv.Supplement.theorem_10fine-grained-complexitygraph-coloringp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1rank-width
Assume the counting Exponential Time Hypothesis #ETH, and fix . Exact counting of the proper -colorings of an -vertex graph has no deterministic algorithm running in time
even on graphs supplied with a linear layout of width at most .
This is the counting counterpart of Theorem 9.
Formalization Note Algorithms are published multi-tape CookLevin machines that, on the code of followed by the code of the layout, halt with the number of proper maps in binary on the last tape. The exclusion is for every with and all : no machine runs within steps, the width of the supplied layout.
Differences from the source:
- encoding: #ETH [DHM+14]; a deterministic algorithm (no machine named) → SubspaceConv.Supplement.SharpETH as a hypothesis; algorithms are published CookLevin machines, output in binary on the last tape; reason: the standard 2^{δn} form of #ETH; the paper leaves the machine model unspecified (p.4)
- generalization: 2^{o(r²)}N^{O(1)} time with a layout (resp. decomposition) of width at most r → for every g with g(r) ≤ ε r² eventually for each ε > 0, and every d, C: no machine within C·2^{g(w)}·(N+1)^d steps, w the actual width; reason: measuring time at the actual width w excludes every algorithm whose bound holds for all r ≥ w, and more; a one-sided o(r²) condition on g covers every two-sided one
Preamble
import Mathlib import Definitions.Def_CookLevin_Basic import Definitions.Def_ApproxCliqueWidth_Certificate_CutRank import Definitions.Def_SubspaceConv_Supplement_layoutWidth import Definitions.Def_SubspaceConv_Supplement_graphCode import Definitions.Def_SubspaceConv_Supplement_chromPoly import Definitions.Def_DetParamSVP_RunsWithin import Definitions.Def_HiddenPartition_Supplement_encodeLabels import Definitions.Def_SubspaceConv_Supplement_SharpETH set_option autoImplicit false
Formal statement
namespace SubspaceConv.Supplement
/-- **Theorem 10**, Perles–Weinstein, *A Fast Algorithm for Subspace Convolution*, STOC 2027 submission manuscript (sha256 a8ffb1b4…604ab2), App. H, p.30 (PDF p.31). Assume #ETH. For every fixed `c ≥ 3`, exact
counting of proper `c`-colorings has no deterministic `2^{o(r²)} N^{O(1)}` algorithm, even on graphs
supplied with a linear layout of width at most `r`.
**Formalization Note** #ETH is `SubspaceConv.Supplement.SharpETH` (a hypothesis). A deterministic
algorithm is a published `CookLevin` machine; on input `graphCode G ++ layoutCode π` it must halt
with the number of proper maps `Fin N → Fin c` (`properCount G c`, labeled colorings) in binary
(`Nat.bits`) on its last tape (published `HiddenPartition.Supplement.OutputsWithin`). `2^{o(r²)} N^{O(1)}` is excluded for every
`g : ℕ → ℝ` with `g(r)/r² → 0` (for every `ε > 0`, eventually `g(r) ≤ ε r²`) and every `d, C`:
no machine runs within `C · 2^{g(r)} · (N + 1)^d` steps, with `r` the width of the supplied layout
(`layoutWidth`). -/
theorem theorem_10 (hSETH : SharpETH) (c : ℕ) (hc : 3 ≤ c) (g : ℕ → ℝ)
(hg : ∀ ε : ℝ, 0 < ε → ∀ᶠ r : ℕ in Filter.atTop, g r ≤ ε * (r : ℝ) ^ 2) (d : ℕ) (C : ℝ) :
¬ ∃ (M : CookLevin.Machine) (k γ : ℕ), CookLevin.TuringMachine k γ M ∧
∀ (N : ℕ) (G : SimpleGraph (Fin N)) [DecidableRel G.Adj] (π : Fin N ≃ Fin N),
HiddenPartition.Supplement.OutputsWithin M k (graphCode G ++ layoutCode π)
(C * (2 : ℝ) ^ g (layoutWidth G π) * ((N : ℝ) + 1) ^ d)
(Nat.bits (properCount G c)) := by sorry
end SubspaceConv.Supplement
Source
Perles, Weinstein, A Fast Algorithm for Subspace Convolution, STOC 2027 submission manuscript (sha256 a8ffb1b4e583122875209a3e25ee95aa3a7af933526e165d47c274634e604ab2), App. H, Theorem 10, p.30 (PDF p.31)