we-solve (beta)

CS-400 · computer science · mathematics · Information and coding theory · Logic and computability

Decidability of Linear Information Inequalities

Status Open · unsolvedmath.comLLM status Open unverified

Statement

Definitions and mathematical statement

Shared notation.
Standard number systems are denoted by $\mathbb N,\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$; index ranges, computational models and specialized notation follow the cited problem source and the definitions below.

For finite-valued jointly distributed variables $X_1,\ldots,X_m$, let $X_S=(X_i)_{i\in S}$ and let $H(X_S)=-\sum_x p_S(x)\log p_S(x)$, with $0\log0=0$ and $H(X_\varnothing)=0$. The input to the decision problem is a finite rational coefficient list $(c_S)_{S\subseteq[m]}$. Validity means $\sum_S c_SH(X_S)\geq0$ for every joint distribution and every choice of finite alphabet sizes. Decidability asks for an algorithm that halts with the correct yes/no answer for every such input.

Statement recorded in the supplied source.
Is the validity of linear information inequalities decidable? [S2]
Scope qualification.
Alphabet sizes are unbounded. This concerns unconditional linear inequalities; implications from additional equalities or inequalities are separate decision problems.
Source status.
The supplied catalogue labels this record open. Its source-status metadata was checked against the supplied snapshot on 2026-10-11. This import does not independently establish current open status or mathematical correctness. The catalogue literature assessment is dated 2026-08-22.

Short English statement

Can an algorithm always decide whether a proposed linear inequality between entropies holds for every finite joint distribution?

Sources

Preparation and review.
Original question attributed to the cited source and UnsolvedMath contributors. Codex (GPT-6; exact serving revision not exposed) assisted with definitions, English summaries, source inspection and formatting. No new human mathematical authorship or independent proof verification is asserted. Canonical ID 30005059 and source code OWR-9790365-009 checked against the complete supplied registry and existing repository statements; known flagged repetitions and obvious identical conjectures excluded. Full mathematical-equivalence/literature review has not been performed. Statement preparation and final review followed contribution prompts C and D; automated checks verify structure and identity, not open status.

Catalogue entry

Statement licence: CC-BY-SA-4.0 · Source file

Contributions 1

CS-400-A1 · Exploration · LLM-generated · gpt 6 astra ultra ·

gpt 6 astra ultra attempt on CS-400

Research-attempt provenance

Definitions and mathematical statement

Shared notation.
Standard number systems are denoted by $\mathbb N,\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$; index ranges, computational models and specialized notation follow the cited problem source and the definitions below.

For finite-valued jointly distributed variables $X_1,\ldots,X_m$, let $X_S=(X_i)_{i\in S}$ and let $H(X_S)=-\sum_x p_S(x)\log p_S(x)$, with $0\log0=0$ and $H(X_\varnothing)=0$. The input to the decision problem is a finite rational coefficient list $(c_S)_{S\subseteq[m]}$. Validity means $\sum_S c_SH(X_S)\geq0$ for every joint distribution and every choice of finite alphabet sizes. Decidability asks for an algorithm that halts with the correct yes/no answer for every such input.

Statement recorded in the supplied source.
Is the validity of linear information inequalities decidable? [S2]
Scope qualification.
Alphabet sizes are unbounded. This concerns unconditional linear inequalities; implications from additional equalities or inequalities are separate decision problems.
Source status.
The supplied catalogue labels this record open. Its source-status metadata was checked against the supplied snapshot on 2026-10-11. This import does not independently establish current open status or mathematical correctness. The catalogue literature assessment is dated 2026-08-22.

Short English statement

Can an algorithm always decide whether a proposed linear inequality between entropies holds for every finite joint distribution?

Sources

Preparation and review.
Original question attributed to the cited source and UnsolvedMath contributors. Codex (GPT-6; exact serving revision not exposed) assisted with definitions, English summaries, source inspection and formatting. No new human mathematical authorship or independent proof verification is asserted. Canonical ID 30005059 and source code OWR-9790365-009 checked against the complete supplied registry and existing repository statements; known flagged repetitions and obvious identical conjectures excluded. Full mathematical-equivalence/literature review has not been performed. Statement preparation and final review followed contribution prompts C and D; automated checks verify structure and identity, not open status.

Literature and context check

The primary report, p. 697, asks about validity over all finite joint laws, with no alphabet bound. Hannula's ICDT 2024 abstract was also read: it distinguishes the unrestricted entropy problem from results for normal polymatroids and monotone set functions. Those different semantic domains cannot be substituted for entropy vectors. Only that abstract, not the full ICDT proof, is used here. The following elementary semidecision argument and two-variable case are rederivations, not a new decidability theorem.

Research attempt: A terminating search for counterexamples and its missing converse

Write $F(p)=\sum_S c_SH_p(X_S)$. If $F(p)<0$ for one finite joint law, there is a rational joint law on the same alphabets with $F<0$. Indeed, rational points are dense in a finite probability simplex (approximate all but one coordinate from below and assign the remaining mass to the last coordinate). Each marginal is a linear function of the table, and $-t\log t$ is continuous on $[0,1]$ when its value at zero is defined to be zero. Thus $F$ is continuous.

Here is an effective search, including the numerical-certification step. Enumerate alphabet bounds $a$, positive denominators $D$, and all nonnegative integer tables on $[a]^m$ with entries summing to $D$. Divide by $D$. Every rational finite law appears, after adding unused symbols. For each positive rational $q$, put $z=(q-1)/(q+1)$, so $|z|<1$. Integration of the geometric series gives \[ \log q=2\sum_{k=0}^{N-1}\frac{z^{2k+1}}{2k+1}+R_N, \qquad |R_N|\leq\frac{2|z|^{2N+1}}{(2N+1)(1-z^2)}. \] The bound follows by bounding each remaining denominator by $2N+1$ and summing a geometric series. Both the finite sum and the error bound are rational and computable. Zero probabilities contribute exactly zero. Therefore each rational table admits arbitrarily accurate rational intervals containing $F$. Dovetail the enumeration and precision, and halt with "invalid" as soon as an interval's upper endpoint is negative. A strict counterexample eventually causes termination; validity never causes an erroneous rejection.

The precise failed inference is that exhaustive counterexample search also decides validity. It supplies neither a finite alphabet bound sufficient for every input nor a terminating certificate on the valid side. A valid inequality whose minimum is zero does not eventually acquire a strictly positive numerical margin.

For comparison, there is a full finite criterion with two variables. The inequality \[ aH(X)+bH(Y)+cH(X,Y)\geq0 \] holds universally if and only if $a+c\geq0$, $b+c\geq0$, and $a+b+c\geq0$. Set $u=H(X\mid Y)$, $v=H(Y\mid X)$, and $w=I(X;Y)$. Conditional entropies are averages of nonnegative entropies. Also $w=D(p_{XY}\Vert p_Xp_Y)\geq0$: applying $-\log t\geq1-t$ with $t=q/p$ and summing over positive $p$ gives $D(p\Vert q)\geq1-\sum_{p>0}q\geq0$ (and zero denominators give infinite divergence). Entropy chain identities yield \[ aH(X)+bH(Y)+cH(X,Y)=(a+c)u+(b+c)v+(a+b+c)w. \] This proves sufficiency. For necessity use, respectively, a fair bit $X$ with constant $Y$, constant $X$ with fair bit $Y$, and $X=Y$ a fair bit. These realize a positive value on each of the three coordinate rays and zero on the others.

Verification and adversarial audit

The enumeration includes degenerate laws through zero table entries. It searches all alphabet sizes, not just binary variables. The logarithm tail bound is valid for $q>1$ as well as $0<q<1$, although probabilities only need the latter range. Dovetailing avoids waiting indefinitely for a zero-valued table. The two-variable necessity tests also check negative coefficients individually.
Audit corrections.
Unconditional inequalities were kept separate from implication problems. The rational search is explicitly one-sided; finite numerical sampling was not promoted to a universal certificate.
External computation.
None; symbolic arguments and boundary checks only.

Scope and remaining gaps

No procedure terminating on every valid input is obtained. The two-variable cone calculation and invalidity semidecision are known elementary structure, and do not decide the original unrestricted problem or establish its current literature status.
Integration review.
Codex (GPT-6; exact serving revision not exposed) reviewed the written arguments and expanded layout and source-reference wrappers. Repository metadata and the production web renderer were checked using Python 3.13 and JavaScript with MathJax 3.2.2. This model-assisted review is not independent human proof verification; no PDF compilation or formal proof checking is asserted.

Completion Estimate

COMPLETION: 0% The calculations below the preserved source statement investigate a concrete route, but establish no substantiated new progress toward the entire original target. Known special cases and failed sufficient conditions are not credited as a solution.

References

The original source references and catalogue attribution are preserved in the Sources section above. The following URLs were actually consulted for this attempt; retention of an additional original reference does not claim fresh consultation of it.

Model and contributor disclosure

OpenAI gpt-6-astra, requested reasoning configuration ultra, generated this research attempt on 2026-10-11. The exact serving revision is not exposed. Codex GPT-6 performed orchestration and repository-format review; its exact serving revision is also not exposed. The mathematical route, boundary checks and final adversarial self-audit followed contribution prompts A then B in docs/contribution_prompts.md, after reading CONTRIBUTING.md. Python 3.14.2 assembled the standalone documents; any mathematical computation is specified in Verification. No theorem prover was used. No human mathematical authorship, substantial human proof correction, or independent human proof checking is asserted. Model-assisted review, source retrieval, and structural checks do not establish correctness or novelty. Full private reasoning transcripts are unavailable as reproducibility artifacts; the complete arguments, inputs and outcomes actually used are stated here or in the companion batch audit.

Final status

Unresolved as a new research contribution. This is a concrete route investigation, not a claim of new complete resolution or a current-status certification. A known answer reproduced for context does not become a new contribution. The catalogue's source-status label is preserved; this attempt status does not assert that a source-labelled solved question is open.

Go to contribution →