Submodular separation conjecture for low-degree monomial families
Let be integers and let . Define
and let . A function is submodular if for all .
Submodular separation conjecture. For every such , there exists a submodular function such that is computable in time, for every , and for every . If true, this would yield a hardness result for submodular minimization with modular constraints, complementing the known prime-power algorithms; the source does not resolve the conjecture.
References
- Joshua Brakensiek, Sivakanth Gopi and Venkatesan Guruswami, “CSPs with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations”, arXiv:1902.04740 (2019).
Progress summary
An unverified submission claims the conjecture fails in one small case, but no independent confirmation was found.
The conjecture asks for an efficiently computable submodular function separating the low-degree monomial images from all other Boolean vectors. The catalogued literature described the underlying question as open in February 2019.
Community submission (unverified), November 7, 2026
A submitted argument claims that for , no real-valued submodular function on is negative exactly on the degree-two monomial image. If correct, this refutes the conjecture without invoking efficient evaluation; the claim has not been independently assessed.
Current status (as of November 2026): The general conjecture remains open in the public record, while an unverified community submission claims a counterexample at .
Sources
Solutions 1
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.See full solution
At degree two in five variables, the monomial map has 16 output coordinates, including the empty-product coordinate. A four-edge dependency cycle gives the obstruction; an independent thirteen-row symmetric certificate is the argument formalized in Lean. The result rules out even a real-valued submodular separator, without any efficient-evaluation requirement. The claim concerns the read 2019 preprints; retention in the unread 2022 journal version is not asserted.
Result and scope: 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.
Complete proof and verification sources: 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) · PDF.
The paper page includes the supplementary proof-source JSON attachment and extract_sources.py, which reconstruct the archived proof and verification sources. The linked paper gives the complete rigorous argument and specifies exactly which statements are formalized.
This is an AI-assisted research preprint. Internal review is not external journal peer review; bounded prior-art searches do not certify worldwide priority. See the paper for the source, interpretation, formalization, and trust limitations.