A four-edge obstruction to submodular separation of quadratic Boolean monomial images: a counterexample to Brakensiek-Gopi-Guruswami Conjecture 3.33 (arXiv:1902.04740; ECCC TR19-013)
Abstract
Conjecture 3.33 is false at (r,d) = (2,5): no integer- (indeed real-) valued submodular function on {0,1}^16 is negative exactly on the degree-2 monomial image of {0,1}^5.
AI-assisted research preprint. The scoped main statement has a Lean certificate. Internal AI review is not external journal peer review; bounded prior-art searches do not certify worldwide priority. See the paper for exact qualifications and formalization limits.
Supplementary files
Comments
Submitted by Myeongjin Kang. Related MathDB problem 341850. Proof sources are attached as proof-sources.json (gzip-compressed, base64-encoded file contents); extract_sources.py reconstructs all archived files. Original archive SHA-256: 441cb79ec825366931cdee6221b99e4b3235dd2145f343565e8df2fb2bd13db8.