Constant-depth Frege oddtown conjecture for nontrivial prime moduli

Let FdF_{d} be the depth-dd fragment of Frege, let oddtownkoddtown_{k} be the oddtown axiom scheme, and let CountnpCount^{p}_{n} be the modular counting principle modulo pp. For a proof system PP, write Ppoly(n)φnP\vdash_{poly(n)}\varphi_{n} when each formula φn\varphi_{n} has a polynomial-size PP-proof.

Constant-depth Frege oddtown conjecture. For each dNd\in\mathbb{N} and each prime p2p\neq 2,

Fd+oddtownk̸poly(n)Countnp.F_{d}+oddtown_{k}\not\vdash_{poly(n)} Count^{p}_{n}.

The preceding result establishes the converse direction for powers of 22 at the level of V0V^{0}. This conjecture strengthens the proposed separation to constant-depth Frege proof size; the paper does not prove it in full.

Sources & referencesView supporting material

Primary source

Eitetsu Ken, “On some Σ^B_0-formulae generalizing counting principles over V^0”, arXiv:2203.10237 (2024).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.