{"id":"9bb15f4d-502b-407c-9880-5d17da39b3a2","arxiv_id":"2412.20493","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For 2-CNF formulas the maximum number of accepted weight-t assignments is q^{n-t-r}(q+1)^r, and for t=n-k the general problem is equivalent to the Turán problem.","lead":"This paper asks how many exactly-true assignments a k-CNF formula can accept without accepting any below-weight assignment, and resolves the exact answer for 2-CNF. It also links the general question to the Turán problem and shows that an optimal construction would improve depth-3 circuit lower bounds.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 13's t-admissibility step is invalid: on a cyclic 3-admissible 2-CNF for n=5, t=3, the prescribed substitution yields F' that accepts a weight-2 assignment, so the upper-bound proof of Theorem 12 is not established.","rationale":"The reader's weakest assumption is exactly the Lemma 13 t-admissibility gap, and the constructed example confirms it concretely: the proof's key inference F(α)=F_{x<-Y}(α) fails precisely when the lower-weight assignment has x=0, Y=1, a case the text does not handle. The paper's Theorem 12 may still be true — the lower-bound block construction is acyclic and attains the claimed value — but the proof as written cannot establish the upper bound because it relies on transforming an arbitrary optimal formula into an acyclic one. I do not see grounds to reject the paper: the small-threshold result, the Turán equivalence, and the Steiner-system connection appear independently solid, and the k=2 proof may be repairable. The appropriate recommendation remains the reader's conditional verdict, so no change is needed; the concern is significant but not a demonstrated counterexample to the theorem itself.","tokens_in":14835,"tokens_out":28517,"duration_ms":273350,"concrete_test":"Verify the explicit counterexample: for n=5, t=3, let F = (x1∨x2) ∧ (x3∨x4) ∧ (x3∨x5) ∧ (x4∨x5) ∧ (¬x1∨¬x2). Check that (1) F is 3-admissible and G(F) contains the cycle x1→¬x2→x1; (2) the Lemma 13 substitution with X=x1, Y=¬x2 gives F' = (x3∨x4)∧(x3∨x5)∧(x4∨x5)∧(x1∨¬x2); (3) F'(0,0,1,1,0)=1 with weight 2, so F' is not 3-admissible. To test local repairability, enumerate all cycle pairs in this F and determine whether any choice yields a t-admissible acyclic formula with sat_3=6; if none, the upper-bound argument of Theorem 12 needs a different approach.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The upper-bound proof of Theorem 12 depends on Lemma 13, which transforms an optimal t-admissible 2-CNF F containing a cycle into F' = F_{x<-Y} ∧ (x∨Y), claiming F' is still t-admissible. The proof's t-admissibility argument infers from F'(α)=1 and F_{x<-Y}(α)=1 that F(α)=1, but this only holds when α(x)=α(Y); the case α(x)=0, α(Y)=1 is never excluded. This is not a hypothetical gap. Take n=5, t=3 and F = (x1∨x2) ∧ (x3∨x4) ∧ (x3∨x5) ∧ (x4∨x5) ∧ (¬x1∨¬x2). F is 3-admissible, has |sat_3(F)|=6 (the value claimed by Theorem 12), and in G(F), x1 and ¬x2 lie on the cycle x1 → ¬x2 → x1. Applying the Lemma 13 construction with X=x1, Y=¬x2 yields F' = (x3∨x4)∧(x3∨x5)∧(x4∨x5)∧(x1∨¬x2). The weight-2 assignment (0,0,1,1,0) satisfies F', so F' is not 3-admissible. Thus the transformation does not preserve t-admissibility even on a cyclic t-admissible formula, and the reduction to acyclic formulas used for the upper bound is unproven.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies S(n,t,k), the maximum number of Hamming-weight-t assignments accepted by a t-admissible k-CNF formula. The main results are: (i) an exact small-threshold result S(n,t,k)=k^t with a uniqueness statement; (ii) an adaptive block construction for linear thresholds t=alpha n with conjectured optimality; (iii) the exact formula S(n,t,2)=q^{n-t-r}(q+1)^r for all t, where n=(n-t)q+r; (iv) an equivalence for t=n-k between S(n,n-k,k) and the Turan number T(n,k+1,k); and (v) a connection to Steiner systems yielding exact values when appropriate designs exist. The paper also derives conditional depth-3 circuit lower bounds from the optimality conjecture for the adaptive construction.","tokens_in":15124,"tokens_out":11627,"duration_ms":112661,"significance":"If the k=2 result and the Turan equivalence are correct, the paper resolves a natural extremal question for all 2-CNF formulas and gives a clean new bridge between threshold-capture and classical Turan-type problems. The proofs rely on independent external results (Song-Yao on maximal independent sets, Keevash on designs, standard entropy bounds), and the paper contains no fitted parameters. The significance is conditional, however: the upper-bound proof for the central k=2 theorem currently rests on a transformation whose t-admissibility preservation is not established, and the manuscript's own later note states that Conjecture 2 is false for k=4.","major_comments":[{"comment":"Lemma 13's transformation does not preserve t-admissibility as claimed. In the proof, from F'(alpha)=1 and F_{x<-Y}(alpha)=1, the authors infer F(alpha)=1; this only follows when alpha(x)=alpha(Y), and the case alpha(x)=0, alpha(Y)=1 is never excluded. The gap is concrete: for n=5, t=3, take F=(x1∨x2)∧(x3∨x4)∧(x3∨x5)∧(x4∨x5)∧(¬x1∨¬x2). This F is 3-admissible and has |sat3(F)|=6, matching Theorem 12 with q=2, r=1, and x1 and ¬x2 lie on a cycle in G(F). Applying the Lemma 13 construction with X=x1, Y=¬x2 yields F'=(x3∨x4)∧(x3∨x5)∧(x4∨x5)∧(x1∨¬x2), and the weight-2 assignment (0,0,1,1,0) satisfies F', so F' is not 3-admissible. Thus the reduction to acyclic formulas used in the upper-bound proof of Theorem 12 is unproven; a different argument is needed if the lemma's existence claim is true.","section":"§4, Lemma 13"},{"comment":"The t-admissibility verification in Lemma 14 also appears to have a sign error. From an assignment alpha that falsifies the removed clause (x∨Y), we have alpha(x)=1 and alpha(Y)=0. For every added clause (Z∨Y) with Z in pred(x), satisfaction of F' then forces alpha(Z)=1, not alpha(Z)=0 as the proof states. The subsequent flip beta therefore does not obviously preserve satisfiability or the claimed weight inequality. As written, the monotonicity reduction needed for Theorem 12 is also not established.","section":"§4, Lemma 14"},{"comment":"Conjecture 2 is stated for every k>=2, but the later note in the same section states that [2] already showed Conjecture 2 is false for k=4. This is an internal inconsistency in the manuscript's main conjecture. The conjecture and the circuit-lower-bound consequence in Observation 5 should be reformulated, e.g., as a conjecture for odd k plus a suitably modified statement for even k, rather than presented without the known counterexample.","section":"§1, Conjecture 2 and Related and Subsequent Works"}],"minor_comments":[{"comment":"The title contains a typo: 'ofk-CNF' should be 'of k-CNF'; the abstract also has a missing space before the sum in the definition of the threshold function.","section":"Title and Abstract"},{"comment":"The uniqueness proof of Theorem 8 uses a stronger inductive claim than the one stated: it asserts that the weight-(t-1) satisfying assignments of F' are exactly the one-per-block assignments, but the induction hypothesis only says that an optimal formula contains t-1 disjoint clauses. Please make the strengthened induction hypothesis explicit.","section":"§3, Theorem 8"},{"comment":"The description of the transformation in Lemma 14 is difficult to parse because the clause (x∨Y) does not correspond to an edge named (x,Y) in the implication graph as defined earlier; the notation pred(x), succ(Y), and the deleted edge should be defined precisely in terms of the implication graph.","section":"§4, Lemma 14"},{"comment":"The informal Theorem 3 states only the case where b=1/(1-alpha) is an integer dividing n; Theorem 12 is the general and exact statement and should be advertised as the main k=2 result in the introduction.","section":"§1, Theorem 3"}],"recommendation":"major_revision","confidential_remarks":"For the editor: the main obstacle is the gap in Lemma 13, which is load-bearing for the paper's central k=2 theorem. The counterexample in my report does not disprove Theorem 12 itself, and the claimed value still matches the theorem, so a repair may be possible. If the authors can restore the upper-bound proof by a correct argument, the paper would be a strong contribution. The paper should also reconcile Conjecture 2 with the already-known counterexample for k=4."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The stress-test note is right: Lemma 13 has a real gap, and the k=2 upper bound is not proven as written. The counterexample works. Take n=5, t=3 and F = (x1∨x2)∧(x3∨x4)∧(x3∨x5)∧(x4∨x5)∧(¬x1∨¬x2). It is 3-admissible with |sat_3(F)|=6, and the substitution in Lemma 13 yields F' that accepts the weight-2 assignment (0,0,1,1,0). So the reduction to acyclic formulas fails for the proof given. That is the flagship result, so the paper needs revision before Theorem 12 is taken as established.\n\nBut I would not throw the paper out. The Turán equivalence (Theorem 1) is a clean and genuinely new observation, and it explains why the general case is hard. The small-threshold uniqueness proof is nice, the Steiner-system connection is interesting, and the adaptive construction plus its circuit lower-bound consequence is a solid contribution even if Conjecture 2 needs qualification. The authors are also honest: they flag Wolfovitz's oversight and note that Amano disproved Conjecture 2 for k=4.\n\nThe soft spots are the gap in Lemma 13 and the sloppy statement of Conjecture 2. As printed, it covers all k≥2, while the paper's own related-work paragraph says it is false for k=4. That should be fixed with an odd-k conjecture or a caveat. Neither issue is fatal to the paper's value, but the burden falls on the proof of Theorem 12.\n\nI would accept this for peer review. The ideas are worth refereeing, and the gap may be repairable. For a reading group, I would bring it to talk about the Turán connection and the adversarial flavor of the t-admissibility transformation. Recommendation: send to a serious referee, but flag Lemma 13 prominently. The authors should be asked to fix the proof or state Theorem 12 as conditional.","headline":"Lemma 13's t-admissibility step is genuinely broken, but the paper's Turán equivalence and adaptive construction are solid enough to warrant a serious referee.","tokens_in":15707,"tokens_out":4970,"would_cite":true,"duration_ms":44162,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C35","05C69","05D05"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper pins down exactly how many weight-$t$ assignments a $t$-admissible 2-CNF can accept, and shows that for thresholds near $n$ the problem becomes the Turán problem.","keywords":["k-CNF","threshold functions","circuit lower bounds","Turán problem","maximal independent sets","Steiner systems","depth-3 circuits","extremal combinatorics"],"falsifier":"Enumerate all 2-CNFs on $n\\le 8$ variables and compute $S(n,t,2)$ by brute force; a single value differing from $q^{n-t-r}(q+1)^r$ would disprove Theorem 12. Separately, search for an optimal $t$-admissible 2-CNF where applying the lemma's literal substitution produces a formula accepting a weight-$(t-1)$ assignment not accepted by the original, which would invalidate the proof's reduction step.","tokens_in":14608,"feed_emoji":"🧮","tokens_out":14643,"duration_ms":115252,"temperature":0.7,"pith_summary":"The paper asks: among $k$-CNF formulas that reject every assignment with fewer than $t$ ones, what is the largest number of assignments with exactly $t$ ones they can accept? It answers this exactly for $k=2$, giving $S(n,t,2)=q^{n-t-r}(q+1)^r$ when $n=(n-t)q+r$, by reducing the problem to counting maximal independent sets of fixed size in a graph. For general $k$ it shows the threshold $t=n-k$ coincides with the classical Turán hypergraph problem, so a closed form for all $t$ would solve a famous open extremal problem. It also constructs adaptive block formulas for linear thresholds and conjectures they are optimal, which would push depth-3 circuit lower bounds for threshold functions from $2^{\\Omega(n/k)}$ to $2^{\\Omega((n/k)\\log k)}$.","feed_headline":"2-CNF threshold capture solved exactly","feed_subtitle":"The k=2 case is closed; larger k hits a Turán barrier and a path to better depth-3 lower bounds.","key_machinery":"The proof rests on several distinct mechanisms. The adaptive block construction splits variables into blocks of size $b=(k-1)/(1-\\alpha)$, where each block realizes a perfect threshold at its own scale, producing the lower bound $\\binom{b}{\\alpha b}^{n/b}$. For $k=2$, a cycle-breaking step on the implication graph of an optimal formula, followed by an elimination of negative literals, yields an acyclic monotone 2-CNF with the same count of weight-$t$ satisfying assignments; those assignments correspond one-to-one with maximal independent sets of size $n-t$ in the clause graph. A recent bound on the maximum number of maximal independent sets of a fixed size in an $n$-vertex graph supplies the final upper bound. For $t=n-k$, a set-system duality shows that a monotone $k$-CNF with only width-$k$ clauses is equivalent to a $k$-uniform covering family, giving $S(n,n-k,k)=\\binom{n}{k}-T(n,k+1,k)$, where $T$ is the Turán number.","core_discovery":"The paper's central discovery is that the extremal threshold-capture problem $S(n,t,k)$ has a clean solution in the width-2 case and a deep combinatorial obstruction in general. For $k=2$, every optimal $t$-admissible formula can be taken acyclic and monotone, and the accepted weight-$t$ assignments correspond bijectively to maximal independent sets of size $n-t$ in the formula's clause graph; together with a bound on the number of such independent sets, this yields $S(n,t,2)=q^{n-t-r}(q+1)^r$. For general $k$, the paper proves that $S(n,n-k,k)=\\binom{n}{k}-T(n,k+1,k)$, equating the problem at threshold $n-k$ with the Turán problem for $(k+1)$-uniform set families, and shows that when $n-k$ and $t$ are constant the extremal value is governed by the existence of Steiner systems. For intermediate linear thresholds $t=\\alpha n$, it constructs block formulas that beat the naive uniform partition and conjectures their optimality.","pith_inferences":["A natural extension the authors leave implicit: the $k=2$ closed form implies a 'rounding' formula for all $k$ if one conjectures that optimal formulas are products of independent blocks, with each block at the largest threshold it can express; the Turán equivalence shows this cannot hold universally without resolving the covering problem.","The unverified case in the cycle-removal lemma could be checked by a small exhaustive search; if a counterexample turns up, the exact $k=2$ formula would need a modified proof strategy even if the formula itself survives.","The Turán equivalence gives a two-way street: any improved upper or lower bound on $T(n,k+1,k)$ yields a corresponding bound on $S(n,n-k,k)$, so circuit-complexity tools might be brought to bear on extremal hypergraph problems.","The observation that optimality is only needed at $t=n^{o(k)}$ to improve circuit bounds suggests a weaker conjecture that might be easier to prove than full optimality at $t=\\alpha n$."],"forward_implications":["For $k=2$, the quantity $S(n,t,2)$ is now known exactly for every $n$ and $t$, so the expressiveness of 2-CNF formulas for thresholds is closed.","For $t=n-k$, any progress on the Turán number $T(n,k+1,k)$ immediately translates into the extremal threshold-capture value, and vice versa.","For linear thresholds $t=\\alpha n$, the adaptive block construction beats the naive uniform partition, and proving its optimality would show that $\\mathrm{THR}_{\\alpha n}$ requires $\\Sigma\\Pi\\Sigma_k$ circuits of size $2^{\\Omega(n/k \\log k)}$.","When $n-k$ and $t$ are constant, extremal formulas exist exactly when the corresponding Steiner systems exist, with explicit value $\\binom{n}{t-1}\\cdot k/t$.","If the main conjecture holds, the known depth-3 circuit lower bounds for threshold functions improve asymptotically, closing a gap to matching upper-bound constructions."],"supporting_citations":[{"why":"Supplies the bound on the maximum number of maximal independent sets of a fixed size, the key upper-bound ingredient for the $k=2$ theorem.","marker":"[24]"},{"why":"Establishes the small-threshold value $S(n,t,k)=k^t$ that the paper extends and whose construction it generalizes.","marker":"[27]"},{"why":"Quoted for the known bounds on the Turán number $T(4,3)$, showing the $t=n-k$ case is genuinely open.","marker":"[11]"},{"why":"Provides the asymptotic existence of Steiner systems used to realize the extremal value in the constant $n-k$ regime.","marker":"[12]"},{"why":"Poses the depth-3 circuit lower-bound problem the paper's conjecture would improve, anchoring the motivation.","marker":"[10]"},{"why":"Gives the matching upper-bound construction for majority circuits that the conjectured lower bound would meet.","marker":"[3]"}],"fun_headline_variants":["Exact 2-CNF threshold capture; Turán barrier for k>2","k-CNF threshold capture meets Turán problem at n-k","Steiner systems decide constant-gap k-CNF threshold capture","Depth-3 lower bounds hope from k-CNF threshold bounds","2-CNF exact, k>2 open, Turán and Steiner shed light"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The $k=2$ upper bound depends on an unverified case in the cycle-removal lemma: it does not rule out that the transformed formula accepts a weight-$(t-1)$ assignment whose $x$-flip satisfies the original formula, and the paper offers no proof that this cannot happen in an optimal formula.","fun_headline_variants_meta":{"raw":{"variants":["Exact 2-CNF threshold capture; Turán barrier for k>2","k-CNF threshold capture meets Turán problem at n-k","Steiner systems decide constant-gap k-CNF threshold capture","Depth-3 lower bounds hope from k-CNF threshold bounds","2-CNF exact, k>2 open, Turán and Steiner shed light"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000702,"raw_usage":{"total_tokens":3165,"prompt_tokens":940,"completion_tokens":2225,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":556,"completion_tokens_details":{"reasoning_tokens":2145}},"tokens_in":556,"tokens_out":2225,"duration_ms":18034,"temperature":1.0,"reasoning_tokens":2145,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T23:21:23.041310+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate all 2-CNFs on $n\\le 8$ variables and compute $S(n,t,2)$ by brute force; a single value differing from $q^{n-t-r}(q+1)^r$ would disprove Theorem 12. Separately, search for an optimal $t$-admissible 2-CNF where applying the lemma's literal substitution produces a formula accepting a weight-$(t-1)$ assignment not accepted by the original, which would invalidate the proof's reduction step.","supporting_citations":[],"review_version":1}