Componentwise entropy rigidity and a reduced search for a non-multilinear matroid

Matroid CI representations: private-noise invariance and a failed entropy-rigidity route

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.

A matroid is a finite ground set with an integer-valued rank function satisfying monotonicity, submodularity, and $0\le r(A)\le |A|$. Its CI structure consists of disjoint triples satisfying $r(A\cup C)+r(B\cup C)=r(A\cup B\cup C)+r(C)$. This structure is probabilistically representable when a random vector indexed by the ground set has exactly these conditional-independence relations $X_A\perp X_B\mid X_C$. A multilinear representation realizes a fixed positive integer multiple of this rank function by dimensions of sums of equal-dimensional linear subspaces.

Statement recorded in the supplied source.

Conjecture 22. There exists a connected matroid whose CI-structure is p-representable but not multilinear. [S2]

Scope qualification.

The supplied extraction includes adjacent workshop exposition; the numbered target passage is retained verbatim and that surrounding exposition is omitted. Connected means that the matroid is not a nontrivial direct sum. The question concerns the CI structure, not a prescribed entropy value for every subset.

Source status.

The supplied catalogue labels this record partially solved. 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.

Short English statement

Is there a connected matroid whose conditional-independence pattern can arise probabilistically but has no multilinear representation?

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 20001198 (AIM-COMPUTATION-0036). Catalogue curation and metadata: CC BY 4.0. The supplied source question is retained; definitions and the English summary are editorial additions. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 AIM Workshop Problem Lists, original problem source linked by catalogue record AIM-COMPUTATION-0036 https://aimath.org/WWN/compalgstat/compalgstat.pdf.

Verbatim supplied catalogue question

Conjecture 22. There exists a connected matroid whose CI-structure is p-representable but not multilinear.

Suppose independence vatieties are properly defined, also for the CI constraints involv-ing functional independences, over the field of complex numbers.

Scope of the actual CI definition

The imported definition concerns disjoint triples $A,B,C$ and requires exactly the corresponding conditional-independence pattern. It does not include functional-dependence requirements $H(X_e\mid X_S)=0$. The source's adjacent sentence about defining varieties with functional relations does not silently add all such requirements to Conjecture 22. We test the possible route from ordinary CI representability to an entropy function proportional to the matroid rank, then examine a small candidate family for the requested non-multilinear example.

Private noise preserves every ordinary CI.

Let $(Y_i)$ be any finite-valued random vector. Let $Z_i$ be mutually independent finite-valued variables, jointly independent of all the $Y_i$, and set $X_i=(Y_i,Z_i)$. Then for all disjoint $A,B,C$, \[ X_A\perp X_B\mid X_C\quad\Longleftrightarrow\quad Y_A\perp Y_B\mid Y_C. \] To prove this, condition on a value $(y_C,z_C)$ of positive probability. The conditional mass of $(y_A,z_A,y_B,z_B)$ is $p(y_A,y_B\mid y_C)p(z_A)p(z_B)$. Its two conditional marginals are $p(y_A\mid y_C)p(z_A)$ and $p(y_B\mid y_C)p(z_B)$. Factorization for the $Y$ variables therefore implies factorization for $X$. Conversely, summing an $X$ factorization over $z_A,z_B$ gives the $Y$ factorization. Conditioning on $z_C$ has no effect because all noises are independent. The argument includes zero cells by restricting to conditioning events of positive probability. For entropy in bits, this construction gives \[ H(X_A)=H(Y_A)+\sum_{i\in A}H(Z_i). \] This follows directly by inserting the product probabilities in $-\sum p\log_2p$ and splitting the logarithm. Thus ordinary CI ignores this added modular entropy function.

An exact connected-matroid check.

Take independent uniform bits $U,V$, and let $(Y_1,Y_2,Y_3)=(U,V,U\mathbin{\mathrm{xor}}V)$. Every pair is independent and uniform on four values, whereas each variable is a deterministic nonconstant function of the other two. Conditioning on one variable makes the other two bijectively related, so they are dependent. These statements check all nontrivial disjoint triples on three elements: an unconditional singleton pair is independent; a singleton and the other pair are dependent; and two singletons given the third are dependent. They agree exactly with rank $r(A)=\min(|A|,2)$, namely the matroid $U_{2,3}$. This matroid is connected: every nonempty bipartition has rank sum $1+2=3$ greater than its total rank two, excluding a direct sum. Its entropy vector is $H(Y_A)=\min(|A|,2)$.

Now add three independent fair private bits. The exact CI structure is unchanged, but singleton, pair and triple entropies become $2,4,5$. No constant $c$ can make these values $c\,r(A)$: singletons force $c=2$ and then the triple would have entropy four. Hence the attempted entropy-rigidity inference is false for the ordinary disjoint-triple definition actually supplied. An augmented problem imposing the matroid's functional dependencies would exclude this private-noise construction; that is a different, stronger hypothesis and is not assumed here.

Why this does not give the conjectured witness.

The matroid $U_{2,3}$ is linearly represented over $\mathbb Q$ by $(1,0),(0,1),(1,1)$; singleton spans have dimension one, every pair has dimension two, and the whole span has dimension two. Thus it is already multilinear with scale one. Adding private noise changes the probabilistic representation, not the matroid, and cannot turn this example into a non-multilinear matroid. More generally every rank-two matroid is linearly representable over $\mathbb Q$. Remove loops, and group the remaining elements into parallel classes, where a pair has rank one. Transitivity follows from submodularity: if $r(\{i,j\})=r(\{j,k\})=1$ for nonloops, then $r(\{i,j,k\})\le1+1-r(\{j\})=1$, so $i,k$ are parallel. A subset in one parallel class has rank one by repeating this argument; a subset meeting two classes has rank two, since a nonparallel pair already has rank two. Assign distinct rational slopes $(1,t)$ to classes, proportional vectors within each class, and zero to loops. Its span ranks are exactly these ranks. Consequently a rank-two search cannot produce the requested matroid. The same assertion for rank one follows by using one nonzero vector for every nonloop.

Audit and unresolved target

The primary Conjecture 22 and the adjacent sentence were inspected. The audit separates ordinary CI from functional dependence, exact CI from entropy values, and an unusual distribution from a genuinely non-multilinear matroid. No computational search or current literature classification is claimed. Neither an explicit non-multilinear witness nor a proof that all representable CI matroids are multilinear is obtained. These known elementary invariance and low-rank arguments expose a failed route; they do not resolve the existence conjecture.

Process and contributions

Mathematics and model-assisted adversarial self-audit: OpenAI gpt-6-astra, ultra reasoning, as dispatched for this research batch; exact serving revision not exposed. Codex (GPT-6; exact serving revision not exposed) materially assisted with orchestration and format review. No human mathematical authorship, mathematical edits, or independent human proof checking is asserted. Contribution prompt A was applied to the full definition and supplied source row, then prompt B was applied adversarially to the derived results. The item-specific audit above records the scope checks and rejected extrapolations. Local assembly and structural checks do not establish mathematical correctness. The source catalogue status is preserved in TOP_PROBLEM and is separate from this attempt 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 proved material is a rederivation of known or auxiliary facts rather than a substantiated new advance on the original target. An entropy-rigidity route fails under the supplied ordinary-CI definition, and rank-two candidates are excluded by direct linear representations; no non-multilinear matroid witness or general impossibility theorem is proved.

References

The complete original Sources subsection above is retained, including catalogue attribution and licence notices. The additional list records primary sources actually consulted for this attempt on 11 October 2026; uncited source links reproduced above were not all rechecked.

• American Institute of Mathematics, Computational Algebraic Statistics, prepared by Seth Sullivant, version 27 March 2004; the original numbered source question and its adjacent scope were inspected on 11 October 2026. https://aimath.org/WWN/compalgstat/compalgstat.pdf.

Final status

Unresolved in this attempt. An entropy-rigidity route fails under the supplied ordinary-CI definition, and rank-two candidates are excluded by direct linear representations; no non-multilinear matroid witness or general impossibility theorem is proved.