Undecidability of Polynomial Inequalities in Subset Densities and Additive Energies

Yaqiao Li

REVIEW 4 major objections 4 minor 20 references

Undecidability of Polynomial Inequalities in Subset Densities and Additive Energies

T0 review · 4 major / 4 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Subset-density and additive-energy inequalities over finite abelian groups are undecidable.

desk verdict 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. read the letter →

arxiv 2505.07378 v1 pith:C6XS6XQX submitted 2025-05-12 math.CO cs.CCmath.LO

Yaqiao Li This is my paper · ORCID

classification math.COcs.CCmath.LO MSC 03D3505C3511B30

keywords undecidabilitysubsetdensityadditiveenergypolynomialinequalitiesfiniteabeliangroupscombinatoricsgraphhomomorphismdensitieslinearforms

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

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.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the 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.

The 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.

What 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.

The negated linear form in (9) also steps outside the definition of t(L,A) in (6), but that is a minor notational fix.

Net: 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.

Referee Report

4 major / 4 minor

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).

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 (4)

[Section 2.2, Eqs. (14)–(15)] 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 2.2, application of (7) to U_j(g)] 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 2.1, Eq. (9) and Theorem 1 statement] 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 2.2, proof of (16) and construction of A] 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.

minor comments (4)

[Section 3.2, Lemma 6] 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 3.1, proof of Lemma 5] 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 3.2, proof of Theorem 2] 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.
[Throughout, notation H−H_j] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the undecidability reductions rest on external theorems fully cited; no prediction is equivalent to its inputs by construction.

full rationale

The paper's derivation chain is transparent and non-circular. Theorem 1 reduces the validity of a linear inequality in subset densities to the Hatami–Norine undecidability result (Lemma 3) by constructing systems of linear forms V_j, E_j, and T_j whose t-values become graph edge and triangle densities. The key identity (14) is asserted as a reduction, not as a fitted input; the content of the undecidability comes from the external Matiyasevich theorem and from Lemma 3, which is borrowed from [11]. Theorem 2 reduces via Matiyasevich to a problem on reciprocal integers (Lemma 6) and uses the in-paper Parseval-based energy bound (Lemma 5) to encode subset densities and additive energies into a region R. No parameter is fitted to data, no prediction is a renamed fit, and no load-bearing self-citation appears. The only notable concern is whether (14) correctly relates unconditional t-values to fixed-g conditional graph densities, but that is a potential correctness flaw, not a circularity: even if (14) failed, the argument would be wrong rather than tautological. The formal-product rule t(L·L',A)=t(L,A)t(L',A) is a definition used to build ψ(q*), and the undecidability content is supplied by independent external results. Therefore the paper merits a circularity score of 0.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The proof relies on standard external theorems and introduces no fitted parameters or new entities. The main unproved input is the undirected Bollobás bound, which is used in a directed setting without justification.

assumptions (3)

standard math Matiyasevich's theorem: nonnegativity of integer polynomials over natural numbers is undecidable
Used in Lemma 6 and the proof of Theorems 1-2 as the base undecidable problem.
standard math Bollobás lower bound for triangle density in undirected graphs
Invoked in the proof of Theorem 1 via Lemma 3; the paper does not supply a directed version.
standard math Parseval identity and Karush-Kuhn-Tucker conditions for the Fourier optimization
Used to prove Lemma 5, the additive energy bound.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Undecidability of Polynomial Inequalities in Subset Densities and Additive Energies." pith.science (2026). https://pith.science/paper/C6XS6XQX

@misc{pith2026250507378,
  author       = {Pith},
  title        = {Pith review of: Undecidability of Polynomial Inequalities in Subset Densities and Additive Energies},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/C6XS6XQX}},
  note         = {Machine review of arXiv:2505.07378}
}

read the original abstract

Many results in extremal graph theory can be formulated as certain polynomial inequalities in graph homomorphism densities. Answering fundamental questions raised by Lov{\'a}sz, Szegedy and Razborov, Hatami and Norine proved that determining the validity of an arbitrary such polynomial inequality in graph homomorphism densities is undecidable. We observe that many results in additive combinatorics can also be formulated as polynomial inequalities in subset's density and its variants. Based on techniques introduced in Hatami and Norine, together with algebraic and graph construction and Fourier analysis, we prove similarly two theorems of undecidability, thus showing that establishing such polynomial inequalities in additive combinatorics are inherently difficult in their full generality.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

20 extracted references · 17 canonical work pages

[1]

Simple graph density inequalities with no sum of squares proofs

Grigoriy Blekherman, Annie Raymond, Mohit Singh, and Rekha R Thomas. Simple graph density inequalities with no sum of squares proofs. Combinatorica, 40(4):455–471, 2020

work page 2020
[2]

Undecidability of polynomial inequalities in weighted graph homomorphism densities

Grigoriy Blekherman, Annie Raymond, and Fan Wei. Undecidability of polynomial inequalities in weighted graph homomorphism densities. In Forum of Mathematics, Sigma , volume 12, page e40. Cambridge University Press, 2024

work page 2024
[3]

Additive energy and the metric poissonian property

Thomas F Bloom, Sam Chow, Ayla Gafni, and Aled Walker. Additive energy and the metric poissonian property. Mathematika, 64(3):679– 700, 2018

work page 2018
[4]

Undecidability of poly- nomial inequalities in tournaments

Hao Chen, Yupeng Lin, Jie Ma, and Fan Wei. Undecidability of poly- nomial inequalities in tournaments. arXiv preprint arXiv:2412.04972 , 2024

arXiv 2024
[5]

Additive energies on discrete cubes

Jaume de Dios Pont, Rachel Greenfeld, Paata Ivanisvili, and Jose Madrid. Additive energies on discrete cubes. Discrete analysis, 2023

work page 2023
[6]

Hilbert’s tenth problem: Refinements and variants

William Gasarch. Hilbert’s tenth problem: Refinements and variants. ACM SIGACT News , 52(2):36–44, 2021

work page 2021
[7]

On an entropic analogue of additive energy

Marcel K Goh. On an entropic analogue of additive energy. arXiv preprint arXiv:2406.18798, 2024

arXiv 2024
[8]

On sets of acquaintances and strangers at any party

Adolph W Goodman. On sets of acquaintances and strangers at any party. The American Mathematical Monthly , 66(9):778–783, 1959

work page 1959

Show all 20 references

[9]

On a conjecture of marton

WT Gowers, B Green, F Manners, and T Tao. On a conjecture of marton. Annals of Mathematics , 2025. 13

2025
[10]

A quantitative inverse theorem for the u4 norm over finite fields

WT Gowers and Luka Mili´ cevi´ c. A quantitative inverse theorem for the u4 norm over finite fields. arXiv preprint arXiv:1712.00241 , 2017

2017 arXiv
[11]

Undecidability of linear inequalities in graph homomorphism densities

Hamed Hatami and Serguei Norine. Undecidability of linear inequalities in graph homomorphism densities. Journal of the American Mathemat- ical Society, 24(2):547–565, 2011

2011
[12]

Universal diophantine equation

James P Jones. Universal diophantine equation. The journal of symbolic logic, 47(3):549–571, 1982

1982
[13]

On additive doubling and energy

Nets Hawk Katz and Paul Koester. On additive doubling and energy. SIAM Journal on Discrete Mathematics , 24(4):1684–1693, 2010

2010
[14]

Improved exponent for marton’s conjecture in fn 2

Jyun-Jie Liao. Improved exponent for marton’s conjecture in fn 2 . arXiv preprint arXiv:2404.09639, 2024

2024 arXiv
[15]

Enumerable sets are diophantine

Y Matiyaseviˇ c. Enumerable sets are diophantine. Mathematical logic in the 20th century , pages 269–273, 2003

2003
[16]

Additive number theory: inverse problems and the geometry of sumsets , volume 165

Melvyn B Nathanson. Additive number theory: inverse problems and the geometry of sumsets , volume 165. Springer New York, 1996

1996
[17]

Additive energies of subsets of discrete cubes

Xuancheng Shao. Additive energies of subsets of discrete cubes. Pro- ceedings of the Royal Society of Edinburgh Section A: Mathematics , pages 1–22, 2024

2024
[18]

Further results on hilbert’s tenth problem

Zhi-Wei Sun. Further results on hilbert’s tenth problem. Science China Mathematics, 64:281–306, 2021

2021
[19]

The dichotomy between structure and randomness, arith- metic progressions, and the primes

Terence Tao. The dichotomy between structure and randomness, arith- metic progressions, and the primes. In International Congress of Math- ematicians (Madrid, 2006) , volume 1, pages 581–608, 2007

2006
[20]

Additive combinatorics, volume 105

Terence Tao and Van H Vu. Additive combinatorics, volume 105. Cam- bridge University Press, 2006. 14

2006

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.

[1] [1]

Simple graph density inequalities with no sum of squares proofs

Grigoriy Blekherman, Annie Raymond, Mohit Singh, and Rekha R Thomas. Simple graph density inequalities with no sum of squares proofs. Combinatorica, 40(4):455–471, 2020

work page 2020

[2] [2]

Undecidability of polynomial inequalities in weighted graph homomorphism densities

Grigoriy Blekherman, Annie Raymond, and Fan Wei. Undecidability of polynomial inequalities in weighted graph homomorphism densities. In Forum of Mathematics, Sigma , volume 12, page e40. Cambridge University Press, 2024

work page 2024

[3] [3]

Additive energy and the metric poissonian property

Thomas F Bloom, Sam Chow, Ayla Gafni, and Aled Walker. Additive energy and the metric poissonian property. Mathematika, 64(3):679– 700, 2018

work page 2018

[4] [4]

Undecidability of poly- nomial inequalities in tournaments

Hao Chen, Yupeng Lin, Jie Ma, and Fan Wei. Undecidability of poly- nomial inequalities in tournaments. arXiv preprint arXiv:2412.04972 , 2024

arXiv 2024

[5] [5]

Additive energies on discrete cubes

Jaume de Dios Pont, Rachel Greenfeld, Paata Ivanisvili, and Jose Madrid. Additive energies on discrete cubes. Discrete analysis, 2023

work page 2023

[6] [6]

Hilbert’s tenth problem: Refinements and variants

William Gasarch. Hilbert’s tenth problem: Refinements and variants. ACM SIGACT News , 52(2):36–44, 2021

work page 2021

[7] [7]

On an entropic analogue of additive energy

Marcel K Goh. On an entropic analogue of additive energy. arXiv preprint arXiv:2406.18798, 2024

arXiv 2024

[8] [8]

On sets of acquaintances and strangers at any party

Adolph W Goodman. On sets of acquaintances and strangers at any party. The American Mathematical Monthly , 66(9):778–783, 1959

work page 1959