{"id":"c783947b-e50a-4cbc-8151-e2de7678fb30","arxiv_id":"2505.07378","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"Deciding whether an arbitrary integer polynomial in subset densities and additive energies is nonnegative for all subsets of all finite abelian groups is undecidable.","lead":"This paper proves that it is impossible to algorithmically decide whether a certain class of polynomial inequalities about subset densities and additive energies in finite abelian groups always hold. The result extends a known undecidability theorem for graph densities to additive combinatorics.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1's reduction conflates fixed-g conditional densities with the marginal densities t(V_j), t(E_j), t(T_j), so Eq. (15) does not follow; the directed Bollobás bound is a separate unsupported step.","rationale":"The reader's identified weakness, the use of the undirected Bollobás bound for directed graphs, is a genuine gap in Theorem 1, but I find an even more basic problem: the proof of Theorem 1 equates unconditional marginal densities with fixed-g conditional densities. Equation (14) only holds pointwise in g after conditioning, while t(ψ(q*),A) is a polynomial in the unconditional t-values of the atomic systems. The reverse direction of Theorem 1 can likely be repaired by averaging over g, since the bad g's contribute a positive weight times a negative q-value, and the forward direction would follow if the average is the true definition of t(ψ); but this is not what the paper defines. The directed Bollobás step is then also unresolved. For the central claim Theorem 2, however, the proof is independent of the graph construction and appears essentially sound, modulo a sketchy but fillable calculus step showing that the auxiliary function \\tilde q attains its minima on S^k. Thus the correct overall assessment remains CONDITIONAL: the theorems may be true, but Theorem 1's proof is currently incomplete for reasons beyond the reader's stated assumption. I mark agreement as partial because the reader's directed-Bollobás concern is secondary and does not address the marginal/conditional conflation, which is the more load-bearing obstacle.","tokens_in":9547,"tokens_out":35248,"duration_ms":374775,"concrete_test":"Take k=1 and the simplest polynomial q(x,y)=y, so that ψ(q*)=T_1. Write both sides of (15) explicitly for a small explicit example, e.g. G=Z_5 and A={0,1,2}. The left side is the unconditional probability E_{g,z,z',z''}[1_{T_1∈A}], while the right side is the conditional quantity 1_{M(g)∈A}·t(K3,U_1(g))·t(V_1)^3, which still depends on g. Averaging the right side over g gives a sum over good g of conditional probabilities; comparing this averaged expression with the unconditional t(T_1,A) will show whether (15) is an identity or whether the proof is missing the g-average. This single check discriminates between a notational shorthand and a genuine gap in the reduction.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central reduction in Section 2.2 is not established as written. Equation (14) defines t(K2,U_j(g)) and t(K3,U_j(g)) as ratios of t(E_j,A) and t(T_j,A) to powers of t(V_j,A). These t-values are unconditional probabilities over all formal variables in the systems (Eq. (6)), whereas the displayed identities in (14) hold only after conditioning on a fixed g with M(g)∈A: for such g, Pr[E_j∈A|g] = Pr[z∈B_j(g)]^2 t(K2,U_j(g)), and similarly for T_j. No such identity holds for the unconditional t(E_j,A), t(T_j,A), and t(V_j,A). Moreover, t(ψ(q*),A) is defined as q*(t(V_1),...,t(T_k)) under the formal-product rule t(L·L')=t(L)t(L'), so the right-hand side of (15), which is a function of the single tuple g, cannot be equal to t(ψ(q*),A) without an additional averaging over g. Even if one repairs this by making g common across the factors, the proof still invokes the undirected Bollobás bound (7) for the directed difference graphs U_j(g); no directed version is proved, and the directed analogue is not automatic for general directed graphs.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper claims two undecidability results for inequalities involving subset densities and additive energies over finite abelian groups. Theorem 1 states that deciding whether a linear combination of quantities t(L,A), where L is a formal system of linear forms, is nonnegative for every subset A of every finite abelian group is undecidable. Theorem 2 states the same for polynomial inequalities in the densities α(A_i) and normalized additive energies E(A_i). The proofs adapt Hatami and Norine's graph-density undecidability framework: a reduction from nonnegativity on the Bollobás region R is implemented through group gadgets and directed difference graphs (Theorem 1), and an upper bound on additive energy is used together with Matiyasevich's theorem (Theorem 2).","tokens_in":9816,"tokens_out":31021,"duration_ms":317697,"significance":"If the results are correct, this is a natural and interesting counterpart to Hatami and Norine's theorem in additive combinatorics: it would show that a large family of true-looking polynomial inequalities in subset densities and additive energies cannot be decided algorithmically in full generality. The proof of Theorem 2 is largely self-contained, gives an explicit finite-variable statement, and builds on a clean energy bound and a reduction to a variant of Hilbert's tenth problem. The paper also states that k=9 suffices via Jones's bound. These are positive features. The main liability is that Theorem 1's proof, as written, contains a load-bearing gap in the step from unconditional densities to per-tuple conditional densities, and it applies an undirected graph inequality to directed graphs without proof; Theorem 1 is therefore not established in its current form.","major_comments":[{"comment":"The identity t(ψ(q*),A) = q(t(K2,U_1(g)),...,t(K3,U_k(g))) · ∏_j t(V_j(g,z),A)^{3deg q} for M(g)∈A does not follow. In (14), t(E_j(g,z,z'),A) and t(V_j(g,z),A) are unconditional probabilities over all variables, including the tuple g, whereas the displayed verification computes the probability for a fixed g. With p_j(g)=Pr_z[V_j(g,z)∈A | g], the unconditional values satisfy t(E_j,A)=E_g[p_j(g)^2 t(K2,U_j(g))] and t(V_j,A)=E_g[p_j(g)], so t(E_j,A)/t(V_j,A)^2 is not equal to t(K2,U_j(g)) for a single g. Since by the formal-product convention t(ψ(q*),A) is a polynomial in the unconditional t(V_j,A), t(E_j,A), t(T_j,A), the right-hand side of (15) does not represent t(ψ(q*),A). The equivalence claimed for Theorem 1 is therefore not established. The same equations also divide by t(V_j(g,z),A)^2, which is zero whenever M(g)∉A.","section":"Section 2.2, Eqs. (14)–(15)"},{"comment":"The Bollobás lower bound t(K3,G) ≥ h(t(K2,G)) in (7) is stated for undirected graphs, but U_j(g) is a directed graph and t(K3,U_j(g)) counts directed 3-cycles. No directed analogue of (7) is stated or proved, and the directed triangle density is a different functional from the undirected one. The first implication in the proof of Theorem 1 uses (7) for every U_j(g), so this is a load-bearing gap.","section":"Section 2.2, application of (7) to U_j(g)"},{"comment":"The system L(g) in (9) contains the negated form ¬(k+1)g1, which is outside the definition of t(L,A) in (6) and outside the problem statement of Theorem 1. The manuscript extends the notation by fiat but does not show that systems with negated forms can be eliminated within the stated formalism, for example by inclusion-exclusion into a linear combination of nonnegated t-values. As written, the proof addresses a broader problem than the one declared in Theorem 1.","section":"Section 2.1, Eq. (9) and Theorem 1 statement"},{"comment":"The verification of B_1(g)=1×H appears to ignore the second-coordinate membership condition in A=∪_{s∈S}(s×(H−H_s)). To check (k+1)z∉A for z=(z_1,z_2), when (k+1)z_1∈S one must also require (k+1)z_2∈H_{(k+1)z_1}; the argument only uses (k+1)z_2∈H and concludes z_1≠0. The treatment of p(g_j−jz)∈A similarly omits the second-coordinate condition. In addition, the notation H−H_j is ambiguous: if it means the difference set, then for a subgroup H_j one has H−H_j=H and the computation |H−H_j|/|H|=1−1/n_j is false; the computation only makes sense if H−H_j denotes set-theoretic complement. This part needs clarification and a corrected proof.","section":"Section 2.2, proof of (16) and construction of A"}],"minor_comments":[{"comment":"The reduction uses reciprocals 1/x_i, so the natural numbers are implicitly taken to be positive; if N includes 0, the equivalence requires an additional argument.","section":"Section 3.2, Lemma 6"},{"comment":"The statement that the KKT conditions imply that E(A) is maximized by taking as many |Â(ξ)|=α as possible is not a complete proof; the bound follows more transparently by the elementary bin-filling observation for numbers u_ξ=|Â(ξ)|^2 ∈ [0,α^2] with fixed sum α.","section":"Section 3.1, proof of Lemma 5"},{"comment":"The assertion that the local minima of q(x,y) on R^k are achieved at x∈S^k is used in the converse direction but is only sketched. A formal argument should cover the boundary case x_i=0 and explain how the coordinatewise monotonicity and concavity statements combine for the multivariate function.","section":"Section 3.2, proof of Theorem 2"},{"comment":"Since the size computation |H−H_j|/|H|=1−1/n_j is needed, the notation H−H_j should be explicitly defined as set-theoretic difference if that is what is intended; standard additive-combinatorics notation uses H−H_j for the difference set, which would give |H−H_j|=|H| for a subgroup H_j.","section":"Throughout, notation H−H_j"}],"recommendation":"major_revision","confidential_remarks":"Theorem 2 appears to be a plausible contribution and its proof is mostly local to fix, but Theorem 1's proof as written has a serious gap: Eq. (15) confuses unconditional densities with per-tuple conditional probabilities, and the directed version of the Bollobás bound is not proved. I would encourage the author to rework Section 2.2 substantially, perhaps by defining the quantum systems with a shared tuple g and a joint probability, and to add a directed Bollobás-type lemma for the difference graphs used here. If such a directed bound is not true, Theorem 1 may require a different approach."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First, the takeaway: the paper is aiming at a genuine open direction—undecidability for polynomial inequalities in subset densities and additive energies—and the constructions are not just rehashed Hatami-Norine. But Theorem 1 as written does not prove what it claims. The reduction in Section 2.2 conflates conditional and unconditional densities. Equation (14) writes t(E_j,A)/t(V_j,A)^2 as t(K_2,U_j(g)), but the t() functions are defined in (6) as unconditional probabilities over all group variables. The right identities hold only after conditioning on a fixed g with M(g)∈A. Unconditional ratios are weighted averages over g, so (14) is false. Likewise, (15) puts a g-dependent expression on the right-hand side of an equality whose left side, t(ψ(q*),A), is a single number after the formal product rule. That is an internal inconsistency.\n\nThe directed Bollobás bound is a separate unsupported step. The paper invokes (7) for the directed graphs U_j(g). No directed analogue is proved, and it is not automatic. That might be fixable for these special Cayley-type graphs, but it needs to be shown.\n\nWhat deserves credit: Theorem 2 has a more self-contained proof. Lemma 5, the Fourier-analytic bound on additive energy, is a useful tool; the KKT argument is short and the calculus in the reduction looks careful. The citation pattern is honest—it builds on Hatami-Norine and cites the recent tournament and weighted-density extensions.\n\nThe negated linear form in (9) also steps outside the definition of t(L,A) in (6), but that is a minor notational fix.\n\nNet: the paper has a real idea and the second theorem may well be correct, but the first theorem's proof has a load-bearing gap. It should not be desk-rejected; it deserves a referee, but the author needs to repair the reduction before the claims can stand. I would not cite it as a theorem yet. If the author fixes the conditional/unconditional issue, this could be a solid contribution to the Hatami-Norine line.","headline":"Theorem 1's reduction has a conditional/unconditional density gap that breaks Eq. (14)-(15); the additive-energy theorem looks more plausible and the paper deserves a major-revision path, not a desk reject.","tokens_in":10319,"tokens_out":6944,"would_cite":false,"duration_ms":64397,"reading_group":"maybe","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["03D35","05C35","11B30"],"pacs":[],"model":"deepseek-v4-flash","headline":"Subset-density and additive-energy inequalities over finite abelian groups are undecidable.","keywords":["undecidability","subset density","additive energy","polynomial inequalities","finite abelian groups","additive combinatorics","graph homomorphism densities","linear forms"],"falsifier":"Test Lemma 5 directly: search for a finite abelian group and a subset A with density α whose normalized additive energy E(A)/|G|^3 exceeds $α^{3}$ − $α^{4}$({1/α} − {1/α}^2). A single such subset would refute the Fourier bound that anchors the second theorem.","tokens_in":9339,"feed_emoji":"🧮","tokens_out":9557,"duration_ms":103899,"temperature":0.7,"pith_summary":"This paper proves that there is no algorithm that can decide whether a given polynomial inequality in subset densities and additive energies holds for every subset of every finite abelian group. It establishes two undecidability results: Theorem 1 covers linear inequalities in probabilities attached to systems of linear forms, and Theorem 2 covers arbitrary polynomial inequalities in densities α(A_i) and normalized additive energies E(A_i). Many results in additive combinatorics are statements of exactly this form, so the theorem shows that the general validity problem for such inequalities is algorithmically unsolvable. The proof reduces the classical undecidable problem of whether an integer polynomial is nonnegative on natural numbers to the validity of these density inequalities.","feed_headline":"Deciding density-energy inequalities is undecidable","feed_subtitle":"A single polynomial can encode an unsolvable number-theory problem, so no general algorithm exists.","key_machinery":"Two constructions carry the argument. For Theorem 1, a subset A ⊆ G and tuples of group variables build directed difference graphs whose edge density equals a conditional probability t(E_j)/t(V_j)^2 and whose triangle density equals the analogous t(T_j)/t(V_j)^3; a known lower bound on triangle density in terms of edge density then transfers the subset-density inequality to a graph-density inequality and back. For Theorem 2, a Fourier-analytic bound on normalized additive energy, E(A) ≤ $α^{3}$ − $α^{4}$({1/α} − {1/α}^2), defines a region R = {(α,β) : β ≤ h(α)}. The proof adds a large penalty M∑($α_i^{3}$ − β_i) to the target polynomial so that all local minima of the resulting function lie at α ∈ {1/n}, where the bound is tight and the problem reduces to nonnegativity of an integer polynomial at reciprocal integers.","core_discovery":"The central discovery is an equivalence between a family of subset-density inequalities and integer-polynomial nonnegativity. The paper shows that deciding whether q(α(A_1),...,α(A_k), E(A_1),...,E(A_k)) ≥ 0 for all finite abelian groups G_i and all subsets A_i ⊆ G_i is undecidable. The proof works by constructing a polynomial q whose negative values, if any, are forced to occur at densities α = 1/n (n ∈ N), where the normalized additive energy E(A) = $α^{3}$ is exactly attainable by a singleton subset of Z_n. Thus each Diophantine failure of an integer polynomial becomes a violation of the density inequality, and vice versa. Theorem 1 is the same phenomenon for more general linear-form probabilities, built through a graph-density reduction.","pith_inferences":["A natural next step is to test whether the same undecidability holds for higher additive energies counting solutions to a_1 + ... + a_k = a_{k+1} + ... + a_{2k}; the Fourier-bound method appears adaptable, but the paper does not claim this.","The results suggest that automated theorem provers or flag-algebra-style search cannot be complete for additive combinatorics inequalities; any practical method must restrict the class of groups, densities, or polynomial shapes.","Because the counterexamples in the second proof are built from singleton subsets of cyclic groups, the hardness is not a consequence of exotic group structure; even highly structured examples can encode universal Diophantine behavior.","The paper leaves the single-variable case k = 1 untouched; checking whether the reduction can be adapted there is a concrete open question."],"forward_implications":["Undecidability already occurs with nine variables, so restricting to a small fixed number of densities and energies does not make the validity problem algorithmically tractable.","Every valid inequality of this form is a genuine theorem of additive combinatorics, but any general algorithm that tries to certify validity for all such inequalities must fail on some input.","The new energy-density bound (Lemma 5) is a standalone constraint: for any subset of a finite abelian group, the normalized additive energy lies below the piecewise-polynomial curve h(α), with equality when the density is 1/n.","Theorems 1 and 2 together imply that the undecidability is not an artifact of exotic graph-like objects; it already appears in the natural language of subset densities and additive energies."],"supporting_citations":[{"why":"Supplies the graph-density undecidability technique and the triangle-density lower-bound curve used to transfer inequalities between graphs and subset densities.","marker":"[11]"},{"why":"Provides the foundational undecidability of nonnegativity of integer polynomials over natural numbers, the source problem for both reductions.","marker":"[15]"},{"why":"Supplies a universal Diophantine equation with a bounded number of variables, used to keep the variable count finite in the undecidability statement.","marker":"[12]"}],"fun_headline_variants":["No algorithm can decide density-energy inequalities","Undecidable: subset density and additive energy inequalities","Density-energy inequality checking is undecidable","Unsolvable problem: polynomial inequalities in subset densities","Additive combinatorics undecidability: density-energy inequalities"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The first theorem's proof applies an undirected triangle-density lower bound to directed graphs whose edges record differences of subset elements; if that bound can fail for such directed difference graphs, the bridge between subset-density inequalities and graph-density inequalities breaks.","fun_headline_variants_meta":{"raw":{"variants":["No algorithm can decide density-energy inequalities","Undecidable: subset density and additive energy inequalities","Density-energy inequality checking is undecidable","Unsolvable problem: polynomial inequalities in subset densities","Additive combinatorics undecidability: density-energy inequalities"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000208,"raw_usage":{"total_tokens":1341,"prompt_tokens":822,"completion_tokens":519,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":438,"completion_tokens_details":{"reasoning_tokens":445}},"tokens_in":438,"tokens_out":519,"duration_ms":5343,"temperature":1.0,"reasoning_tokens":445,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T22:19:35.228222+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Test Lemma 5 directly: search for a finite abelian group and a subset A with density α whose normalized additive energy E(A)/|G|^3 exceeds $α^{3}$ − $α^{4}$({1/α} − {1/α}^2). A single such subset would refute the Fourier bound that anchors the second theorem.","supporting_citations":[{"cited_title":"Undecidability of linear inequalities in graph homomorphism densities","cited_arxiv_id":null,"evidence_quote":"Supplies the graph-density undecidability technique and the triangle-density lower-bound curve used to transfer inequalities between graphs and subset densities."},{"cited_title":"Enumerable sets are diophantine","cited_arxiv_id":null,"evidence_quote":"Provides the foundational undecidability of nonnegativity of integer polynomials over natural numbers, the source problem for both reductions."},{"cited_title":"Universal diophantine equation","cited_arxiv_id":null,"evidence_quote":"Supplies a universal Diophantine equation with a bounded number of variables, used to keep the variable count finite in the undecidability statement."}],"review_version":1}