Tensor Product of Polymatroids and Common Information

Carles Padr\'o

REVIEW 3 major objections 3 minor 1 cited by

Tensor Product of Polymatroids and Common Information

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

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

Pith's one-line read A polymatroid that admits a tensor product with the uniform matroid U2,3 must have common information extensions for every pair of subsets.

desk verdict A promising construction for CI extensions from tensor products, but the proof of the main theorem has a false equality and a reversed inequality. read the letter →

arxiv 2502.06714 v2 pith:F5WFM4TH submitted 2025-02-10 math.CO

Carles Padró This is my paper · ORCID

classification math.CO MSC 05B35

keywords polymatroidcommoninformationextensiontensorproductofpolymatroidsuniformmatroidU23Ingleton'sinequalitylinearrepresentabilitysubmodularity

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 establishes a new connection between two necessary conditions a polymatroid must satisfy to be linearly representable. It proves that whenever a polymatroid has a tensor product with the uniform matroid U2,3, that polymatroid is 1-CI: for every pair of subsets, an extension of the polymatroid exists in which a new element has the mutual information value of the pair and is conditionally independent of it. The proof gives an explicit formula for such an extension directly from the tensor product's rank function. As a corollary, the paper obtains a simpler proof that tensor products with U2,3 imply Ingleton's inequality.

What carries the argument

The load-bearing object is the tensor product itself: a polymatroid $(E_1\times E_2,g)$ of two polymatroids with rank functions $f_1,f_2$ satisfies $g(X\times Y)=f_1(X)f_2(Y)$ for all subsets $X\subseteq E_1$, $Y\subseteq E_2$. Here $U_{2,3}$ is the uniform matroid of rank two on three elements. The proof also uses bounds $\beta\le g(A_1^1A_2^2A_3^3)\le \alpha$ on the rank of three-layer sets, derived from submodularity in Proposition 4.2. The common information extension is built by subtracting $f(XY)$ from the tensor rank value $g(X_1Y_2A_3)$, and submodularity of $g$ is shown to carry over to the extension.

What would settle it

To test Theorem 5.1, take a polymatroid that admits a tensor product with $U_{2,3}$ and check whether the proposed function $f(Az)=g(X_1Y_2A_3)-f(XY)$ is submodular for all choices of $X,Y$; a single violation of $f(x;z|A)\ge 0$ in a concrete example would disprove the theorem. More narrowly, evaluating Proposition 4.2's bounds on a linear polymatroid with three independent elements shows the proof's equality $g((A_1A_2)_2)=g((A_1A_2A_3)_2)$ fails, so the bounds themselves are the critical step to verify.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central claim is Theorem 5.1: every polymatroid $(E,f)$ that admits a tensor product $(E\times\{1,2,3\},g)$ with $U_{2,3}$ is 1-CI. For any pair $X,Y\subseteq E$, the extension defined by $f(Az)=g(X_1Y_2A_3)-f(XY)$ for all $A\subseteq E$ is a polymatroid in which $z$ is a common information for $(X,Y)$. The theorem is reached by observing that in the linear case the tensor product's rank on $X_1Y_2A_3$ is $f(X)+f(Y)+f(A)-\dim(U_X\cap U_Y\cap U_A)$, while a common information extension adds a subspace $V_z=U_X\cap U_Y$, so the two constructions coincide; the paper then argues the same identity holds for any tensor product with $U_{2,3}$ via submodularity bounds.

Load-bearing premise

The argument for the key rank bounds assumes that replacing the set $(A_1A_2)$ by the larger set $(A_1A_2A_3)$ in the second factor of the tensor product leaves the rank unchanged; the tensor product definition gives the two values as $f(A_1A_2)$ and $f(A_1A_2A_3)$, which need not be equal.

Editorial extensions

If this is right

Every polymatroid admitting a tensor product with $U_{2,3}$ automatically satisfies the 1-CI necessary condition for linear representability, not just Ingleton's inequality.
There is an explicit rank formula for a common information extension in terms of any tensor product: $f(Az)=g(X_1Y_2A_3)-f(XY)$.
The result ties together two previously separate necessary conditions, showing that tensor-product existence is at least as restrictive as common information at the first iteration.
The new proof of Ingleton's inequality is shorter and more direct than the earlier proof via submodular coupling.

Reading between the lines

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

The explicit formula suggests a recipe for iterating common information extensions: apply the same construction to the extended polymatroid, potentially producing new linear rank inequalities beyond Ingleton's, provided each iteration admits a suitable tensor product.
The theorem leaves open the converse: a 1-CI polymatroid might fail to admit a tensor product with $U_{2,3}$, which would show the two necessary conditions are not equivalent; the Vámos matroid is one natural place to look, since it has no such tensor product.
Because every linearly representable polymatroid has both properties, the construction gives a representation-free way to build common information extensions for linear polymatroids directly from tensor products, which may be useful when explicit rank formulas are needed.

Share X Bluesky LinkedIn Reddit HN

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

Carles Padró's paper has a genuinely attractive idea: use a tensor product with U2,3 to construct a common information extension via f(Az)=g(X1Y2A3)-f(XY). Were that construction to work, it would answer the open question from [3] and give a more transparent proof of Ingleton's inequality. The paper is clearly written and the citations are appropriate.

The trouble is that the proof of the central Theorem 5.1 is not sound as written. Proposition 4.2, which supplies the bounds, contains an unjustified equality: the proof claims g(A1_2A2_2)=g(A1_2A2_2A3_2). But A1_2A2_2 is the rectangle (A1A2)×{2} and A1_2A2_2A3_2 is (A1A2A3)×{2}. The tensor product condition fixes these to f(A1A2) and f(A1A2A3), which are not equal in general. So the lower bound β≤g is not established. The upper bound α also looks suspect; the text derives it from a submodularity inequality but the equality g(ZT)=2s is asserted without justification and ZT is not a rectangle.

Then in Theorem 5.1, the final verification writes f(z;z|A) ≥ g(X1Y2A3)−α ≥ 0, but Proposition 4.2 gives g ≤ α, not g ≥ α. So the direction is reversed. The construction may be repairable, but as it stands the main claim is not demonstrated.

Despite these flaws, the paper deserves a serious referee. The question is important, the construction is natural, and the errors look fixable rather than fatal to the idea. A referee should focus on whether the CI extension defined in (5) can be proved polymatroid by a different argument, perhaps using the lower bound β instead of α. If the author can repair the proof, this would be a nice contribution. For now, I would not cite the main theorem.

Referee Report

3 major / 3 minor

Summary. The paper claims a new implication between two known necessary conditions for linear representability of polymatroids. The main theorem (Theorem 5.1) states that every polymatroid that admits a tensor product with the uniform matroid U_{2,3} is 1-CI, meaning that for every pair of subsets of the ground set there exists a common-information extension. The argument proceeds by deriving upper and lower bounds for the rank function of any such tensor product (Proposition 4.2), using them to reprove Ingleton's inequality, and then defining the common-information extension by the formula f(Az)=g(X_1Y_2A_3)-f(XY).

Significance. If the theorem were valid, it would establish a genuinely new connection between the tensor-product condition and common-information extensions, and it would give an explicit construction of CI extensions from a tensor product. The paper is concise, well motivated, and does not rely on numerical computation or parameter fitting. However, the proof as written contains several false or unjustified equalities in Proposition 4.2, and the final inequality in Theorem 5.1 uses the wrong direction of the proved bound. The central claim is therefore not established.

major comments (3)

[Section 4, Proposition 4.2 (lower bound)] The proof of the lower bound in (2) uses the equality g(A1_2 A2_2)=g(A1_2 A2_2 A3_2). Under the tensor-product definition, g(A1_2 A2_2)=f(A1A2) and g(A1_2 A2_2 A3_2)=f(A1A2A3), because both are rectangle values with second factor {2}; these ranks are generally different. For example, with f=U_{3,3} and A1,A2,A3 distinct singletons, they are 2 and 3. Consequently the chain g(X)+g(Y) >= g(XY)+g(X∩Y) >= s3+s1+r1+r3 does not follow, and the claimed lower bound beta <= g(...) is unproved. This bound is load-bearing for Theorem 5.1.
[Section 4, Proposition 4.2 (upper bound)] The proof asserts without justification that g(Z)=s1+s2, g(T)=s3+s, and g(ZT)=2s for Z=(A1A3)_1(A2A3)_2A3_3 and T=A1_1(A2A3)_2(A1A2A3)_3. These sets are not rectangles, so their g-values are not fixed by the tensor-product definition. For the canonical linear tensor product of f=U_{3,3} with U_{2,3} described in Proposition 4.1, with A1,A2,A3 distinct singletons, the set T has rank 6, whereas s3+s=5; thus the stated equality g(T)=s3+s is false for a genuine tensor product. Hence the upper bound alpha is also not established.
[Section 5, Theorem 5.1 (final inequality)] The proof concludes f(z;z|A) >= g(X1Y2A3) - alpha(X,Y,A) >= 0. But Proposition 4.2 gives g(X1Y2A3) <= alpha(X,Y,A), so the expression g(X1Y2A3)-alpha(X,Y,A) is nonpositive in general, not nonnegative. To prove f(z;z|A)>=0 one needs g(X1Y2A3) >= f(XY)+f(A), which would follow from the lower bound beta <= g together with beta >= f(XY)+f(A); neither the lower bound nor the correct inequality is available in the written proof. Together with the use of Proposition 4.2 in the equalities for f(z) and f(Xz), this means the proof of the main theorem is incomplete.

minor comments (3)

[Section 3] There is a typo in 'commom information' in the definition of a common-information extension.
[Section 2] The displayed definition 'f(Y|X)=f(Y;Y|Z)' appears to be a typo; it should be f(XY)-f(X).
[Section 5] In the proof of Theorem 5.1, '(Ez,g)' should be '(Ez,f)' since the extension is on the ground set Ez with rank function f.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the theorem is an explicit reduction from tensor products to common information extensions, not a restatement of its assumptions. The proof gap in Proposition 4.2 is a correctness issue, not a circularity.

full rationale

All load-bearing moves in the paper are reductions from the assumed tensor product g to the constructed extension f(Az) = g(X1Y2A3) - f(XY). This is a genuine construction, not a fitted parameter renamed as a prediction, and the checks that z is a common information are derived from the tensor product definition and submodularity of g. In particular, f(z) = f(X;Y), f(z|X) = 0, and f(z|Y) = 0 are obtained by substituting sets into the defining formula, not by assuming the conclusion. The proof of submodularity of the extension reduces to submodularity of g by direct expansion, so the central claim is not equivalent to its inputs by construction. Citations to [2], [7], and [13] are either definitional or standard results with independent proofs; they do not carry the main theorem by self-citation. The serious problem in the paper is Proposition 4.2, where the equality g(A1_2A2_2) = g(A1_2A2_2A3_2) is asserted without justification and is generally false under the tensor product definition, since the two sides equal f(A1A2) and f(A1A2A3) respectively. That is a correctness gap in the proof of the bounds, and hence in Theorem 5.1, but it is not a circularity: it does not make the theorem logically identical to its hypotheses or to a fitted parameter. No circular step satisfying the required standard was found.

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

The central claim rests on standard submodularity results, linear algebra bounds for three subspaces, and the existence of tensor products for linear polymatroids. No free parameters or invented entities are introduced. The main unproven load is the validity of Proposition 4.2's bounds, whose supplied proof contains an unjustified equality.

assumptions (3)

standard math A set function is a polymatroid iff f(Y;Z|X) ≥ 0 for all X,Y,Z (Proposition 2.1).
Quoted from Schrijver [13, Proposition 44.1]; used throughout to verify submodularity.
domain assumption For three vector subspaces, the dimension of their intersection satisfies the bounds (1).
Standard linear algebra result, cited to [7, Section 7.2]; used in Proposition 4.1 and to motivate the bounds.
domain assumption Every linear polymatroid has a tensor product with any other linear polymatroid, given by tensor product of vector spaces (Proposition 4.1).
Cited from Lovász [11] and Mason [12]; used to interpret tensor products of linear polymatroids.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Tensor Product of Polymatroids and Common Information." pith.science (2026). https://pith.science/paper/F5WFM4TH

@misc{pith2026250206714,
  author       = {Pith},
  title        = {Pith review of: Tensor Product of Polymatroids and Common Information},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/F5WFM4TH}},
  note         = {Machine review of arXiv:2502.06714}
}

read the original abstract

A new connection between two different necessary conditions for a polymatroid to be linearly representable is presented. Specifically, we prove that the existence of a tensor product with the uniform matroid of rank two on three elements implies the existence of a common information extension for every pair of subsets of the ground set.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Interaction between skew-representability, tensor products, extension properties, and rank inequalities
math.CO 2025-07 conditional novelty 8.0 of 10

A connected matroid is skew-representable if and only if it admits tensor products with the uniform matroid U_{2,3} at every order, giving verifiable certificates for non-representability and a new rank inequality.

Reference graph

Works this paper leans on

13 extracted references · 10 canonical work pages · cited by 1 Pith paper

[3]

Matroid products via submodular coupling

Krist´ of B´ erczi, Bogl´ arka Geh´ er, Andr´ as Imolay, L´ aszl´ o Lov´ asz, Bal´ azs Maga, Tam´ as Schwarcz: Matroid products via submodular coupling. arXiv.org, arXiv:2411.02197 (2024)

work page Pith review arXiv 2024
[1]

Journal of Combinatorial Theory, Series B 47, 10–19 (1989)

Achim Bachem, Alfred Wanka: Euclidean intersection properties. Journal of Combinatorial Theory, Series B 47, 10–19 (1989)

work page 1989
[2]

arXiv.org, arXiv:2306.15085 (2023)

Michael Bamiloshin, Oriol Farr` as, Carles Padr´ o: A Note on Extension Properties and Representations of Matroids. arXiv.org, arXiv:2306.15085 (2023)

arXiv 2023
[4]

Eindhoven: Technische Universiteit Eindhoven

Guus Pieter Bollen: Frobenius flocks and algebraicity of matroids. Eindhoven: Technische Universiteit Eindhoven. PhD thesis (2018)

work page 2018
[5]

arXiv.org, arXiv:0910.0284 (2009)

Randall Dougherty, Chris Freiling, Kenneth Zeger: Linear rank inequalities on five or more variables. arXiv.org, arXiv:0910.0284 (2009)

arXiv 2009
[6]

arXiv.org, arXiv:1104.3602 (2011)

Randall Dougherty, Chris Freiling, Kenneth Zeger: Non-Shannon Information Inequalities in Four Random Variables. arXiv.org, arXiv:1104.3602 (2011)

arXiv 2011
[7]

Ideal Multipartite Secret Sharing Schemes

Oriol Farr` as, Jaume Mart ´ ı-Farr´ e, Carles Padr´ o. Ideal Multipartite Secret Sharing Schemes. J. Cryptology 25 434–463 (2012)

work page 2012
[8]

Journal of Computer and Systems Sciences 60, 442–464 (2000)

Daniel Hammer, Andrei Romashchenko, Alexander Shen, Nikolai Vereshchagin: Inequali- ties for Shannon entropy and Kolmogorov complexity. Journal of Computer and Systems Sciences 60, 442–464 (2000)

work page 2000

Show all 13 references

[9]

A. W. Ingleton: Representation of matroids. In: Combinatorial Mathematics and its Ap- plications, D.J.A Welsh (ed.), pp. 149–167. Academic Press, London (1971)

1971
[10]

Discrete Mathematics 36, 49–55 (1981)

Michel Las Vergnas: On products of matroids. Discrete Mathematics 36, 49–55 (1981)

1981
[11]

InCombinatorial Surveys (Proc

L´ aszl´ o Lov´ asz: Flats in matroids and geometric graphs. InCombinatorial Surveys (Proc. 6th British Combinatorial Conference) pages 45–86 (1977)

1977
[12]

J. H. Mason. Matroids as the study of geometrical configurations. In: Aigner, M. (eds) Higher Combinatorics. NATO Advanced Study Institutes Series 31, 133–176, (1977)

1977
[13]

Polyhedra and Efficiency

Alexander Schrijver: Combinatorial optimization. Polyhedra and Efficiency. Springer- Verlag, Berlin (2003). 6

2003

Pith tools

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

[1] [3]

Matroid products via submodular coupling

Krist´ of B´ erczi, Bogl´ arka Geh´ er, Andr´ as Imolay, L´ aszl´ o Lov´ asz, Bal´ azs Maga, Tam´ as Schwarcz: Matroid products via submodular coupling. arXiv.org, arXiv:2411.02197 (2024)

work page Pith review arXiv 2024

[2] [1]

Journal of Combinatorial Theory, Series B 47, 10–19 (1989)

Achim Bachem, Alfred Wanka: Euclidean intersection properties. Journal of Combinatorial Theory, Series B 47, 10–19 (1989)

work page 1989

[3] [2]

arXiv.org, arXiv:2306.15085 (2023)

Michael Bamiloshin, Oriol Farr` as, Carles Padr´ o: A Note on Extension Properties and Representations of Matroids. arXiv.org, arXiv:2306.15085 (2023)

arXiv 2023

[4] [4]

Eindhoven: Technische Universiteit Eindhoven

Guus Pieter Bollen: Frobenius flocks and algebraicity of matroids. Eindhoven: Technische Universiteit Eindhoven. PhD thesis (2018)

work page 2018

[5] [5]

arXiv.org, arXiv:0910.0284 (2009)

Randall Dougherty, Chris Freiling, Kenneth Zeger: Linear rank inequalities on five or more variables. arXiv.org, arXiv:0910.0284 (2009)

arXiv 2009

[6] [6]

arXiv.org, arXiv:1104.3602 (2011)

Randall Dougherty, Chris Freiling, Kenneth Zeger: Non-Shannon Information Inequalities in Four Random Variables. arXiv.org, arXiv:1104.3602 (2011)

arXiv 2011

[7] [7]

Ideal Multipartite Secret Sharing Schemes

Oriol Farr` as, Jaume Mart ´ ı-Farr´ e, Carles Padr´ o. Ideal Multipartite Secret Sharing Schemes. J. Cryptology 25 434–463 (2012)

work page 2012

[8] [8]

Journal of Computer and Systems Sciences 60, 442–464 (2000)

Daniel Hammer, Andrei Romashchenko, Alexander Shen, Nikolai Vereshchagin: Inequali- ties for Shannon entropy and Kolmogorov complexity. Journal of Computer and Systems Sciences 60, 442–464 (2000)

work page 2000