Entropy approximations of algebraic matroids over finite fields

Guillermo Matera 1,2 · 2025

Read Entropy approximations of algebraic matroids over finite fields by Guillermo Matera 1,2 (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-15348.txt.

Introduction

Guillermo Matera studies how well entropy can stand in for rank in a branch of algebra. His objects are algebraic matroids, which track which sets of items depend on each other. For each such object over a finite field, random sampling gives entropy values that form a shape of their own. Earlier work showed that shape nears the true rank as the field grows.

Matera makes that claim exact. He gives clear error bounds that depend on the size of the field, the set, and the shape's degree. His proof joins tools from geometry with facts about entropy and shared information. The result ties two ideas of independence, one from algebra and one from information theory, with firm numbers.

Catalog record

CREATORGuillermo Matera 1,2
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE56 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-15348

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Entropy approximations of algebraic matroids over finite fields Thanks: The author is partially supported by the grant PIP CONICET 11220130100598 Guillermo Matera 1,2 Abstract . We investigate the asymptotic behavior of entropy polymatroids associated with algebraic matroids over finite fields. Given an algebraic matroid 𝖬 := ( ℰ , r ) {\sf M}:=(\mathcal{E},r) and the irreducible variety V V associated with 𝖬 {\sf M} , we consider the polymatroid h 𝔽 h_{\mathbb{F}} induced by the entropies of the projections of V ⁡ ( 𝔽 ) V(\mathbb{F}) , where 𝔽 \mathbb{F} is a finite extension of 𝔾 \mathbb{G} . Revisiting a construction of Matú s ˇ \check{\mathrm{s}} , we show that the polymatroid h 𝔽 h_{\mathbb{F}} converges to the rank function r r of 𝖬 {\sf M} as q := | 𝔽 | q:=|\mathbb{F}| tends to infinity. Our main contribution is to make this convergence quantitative: we derive explicit uniform error bounds for the deviation | h 𝔽 − r | |h_{\mathbb{F}}-r| , expressed in terms of the degree of V V , the ground set size | ℰ | |\mathcal{E}| , the rank r ⁡ ( ℰ ) r(\mathcal{E}) , and q q . The proofs combine tools of algebraic geometry (effective Lang-Weil estimates and intrinsic degree bounds for annihilating polynomials of circuits) with information-theoretic arguments (submodularity of entropy and conditional entropy estimates). These results provide the first effective and uniform approximation bounds for algebraic matroids by entropy polymatroids, clarifying the quantitative link between algebraic independence (captured by matroid rank) and information-theoretic independence (captured by entropy). 1991 Mathematics Subject Classification 05B35 (Primary); 94A15, 14G15, 11G25 (Secondary) 1. Introduction Matroid theory provides a unifying framework for combinatorial structures arising in graph theory, geometry, and optimization. Among the various classes of matroids, algebraic matroids occupy a distinguished position. They arise naturally from sets of algebraically dependent elements in a field extension and serve as a bridge between combinatorial independence and algebraic geometry. Classical references such as [ 12 ] (see also [ 13 ] ) emphasize their central role both in combinatorics and in applications to algebraic geometry. An important line of research initiated by Matú \check{\textrm{s}} [ 10 , 11 ] (see also [ 4 ] ) concerns the relationship between algebraic matroids and entropic matroids . In particular, Matú \check{\textrm{s}} showed that every algebraic matroid is almost entropic , meaning that its rank function can be approximated by entropic polymatroids. This result establishes a deep connection between information theory and algebraic combinatorics. While the original proof is qualitative in nature, it leaves open the problem of obtaining explicit quantitative bounds— a question that is the focus of the present work. A quantitative refinement of Matú \check{\textrm{s}} ’s theorem is important not only from a conceptual perspective, but also for potential applications. Explicit bounds on the rate at which entropic polymatroids approximate the rank function of an algebraic matroid are relevant, for instance, in the design of information-theoretic protocols such as polynomial secret sharing schemes [ 16 , 2 ] , where sequences of entropic inequalities allow one to construct secret sharing schemes with information ratio tending to one (see [ 3 ] for details). At the same time, quantitative approximations play a key role in network coding [ 17 ] , where entropic polymatroids provide outer bounds for feasible rate regions. The purpose of this paper is to present a refined and quantitative version of Matú \check{\textrm{s}} ’s theorem. As shown in [ 11 ] , it suffices to consider the case of algebraic matroids over a finite field. Our main contribution is an explicit approximation scheme showing that algebraic matroids over a finite field are almost entropic, with the error bounded in terms of geometric invariants of the associated algebraic variety. More precisely, we obtain the following result. Theorem 1.1 . Let {\sf M}:=(\mathcal{E},r) be an algebraic matroid defined over a finite field \mathbb{G} , where \mathcal{E} is its ground set and r is the corresponding rank function. Let V\subset\mathbb{A}^{n}_{\overline{\mathbb{G}}} be the variety associated with {\sf M} , and let \mathbb{F} be a finite field extension of \mathbb{G} with |\mathbb{F}|\geq(5\deg(V)^{7/3}+1) . For an arbitrary subset \mathcal{K}\subseteq\mathcal{E} , with n:=|\mathcal{E}| , m:=r(\mathcal{E}) , \delta:=\deg(V) and q:=|\mathbb{F}| , we have |h_{\mathbb{F}}(\mathcal{K})-r(\mathcal{K})|\leq\frac{nm\delta^{2}}{q^{1/2}}+\frac{n\ln\delta}{\ln q}-\frac{\ln(1-{5\delta^{7/3}}{q^{-1/2}})}{\ln q}. This yields a quantitative refinement of Matú \check{\textrm{s}} ’s theorem, with effective constants associated to the underlying variety V . Beyond the proof of this quantitative version, we also undertake a systematic study of theoretical aspects of the varieties associated with algebraic matroids. In this part of the paper we analyze some of their algebraic, geometric, and arithmetic properties, and explain how these features influence the entropic behavior of the corresponding matroids. In particular, we highlight the role of dimension theory, degrees, and rational points in controlling the quality of entropic approximations. As an example, we obtain the following result. Proposition 1.2 . With hypotheses and notations as in Theorem 1.1 , let \mathcal{C}\subset\mathcal{E} be a circuit and let j\in\mathcal{C} . Then there exists a nonzero absolutely irreducible polynomial f_{\mathcal{C}}\in\mathbb{G}[X_{i}:i\in\mathcal{C}]\setminus\mathbb{G}[X_{i}:i\in\mathcal{C}\setminus\{j\}] of degree at most \delta such that f_{\mathcal{C}}((f_{i})_{i\in\mathcal{C}})=0. The existence of an annihilating polynomial f_{\mathcal{C}} for the set \{f_{i}:i\in\mathcal{C}\} is well-known (see, e.g., [ 13 , Theorem 11] ). Furthermore, an extrinsic upper bound on the degree of this polynomial in terms of the degrees of the polynomials \{f_{i}:i\in\mathcal{C}\} can be obtained applying [ 1 , Corollary 6] . Our contribution relies on the intrinsic bound of the proposition in terms of the degree of the variety V . The paper is organized as follows. In Section 2 we review the necessary background on information theory, matroid theory, and algebraic geometry. Section 3 discusses theoretical aspects of algebraic, geometric, and arithmetic nature of the variety underlying an algebraic matroid. Finally, Section 4 contains the precise statement and proof of our main theorem. 2. Preliminaries In this section we recall basic notions on information theory, matroid theory, and algebraic geometry that will be used throughout the paper. 2.1. Entropy and polymatroids Given a discrete random variable S taking values in a finite set \mathcal{S} with probability mass function p(s):=\mathbb{P}(S=s) , the Shannon entropy of S is defined by H(S):=-\sum_{s\in\mathcal{S}}p(s)\ln p(s), where \ln represents the logarithm in base e , and where terms with p(s)=0 are omitted. For two random variables S and T with joint probability distribution p(s,t) , one defines the joint entropy H(S,T):=-\sum_{s\in\mathcal{S}}\sum_{t\in\mathcal{T}}p(s,t)\log p(s,t), and the conditional entropy of S given T as H(S\mid T):=\sum_{t\in\mathcal{T}}p(t)H(S\mid T=t), where H(S\mid T=t):=-\sum_{s\in\mathcal{S}}p(s\mid t)\,\ln p(s\mid t). Equivalently, H(S\mid T):=H(S,T)-H(T). These notions extend to random vectors S:=(S_{i})_{i\in\mathcal{E}} indexed by a finite set \mathcal{E} , where for \mathcal{A}\subset\mathcal{E} one considers the subvector S_{\mathcal{A}}:=(S_{i})_{i\in\mathcal{A}} . Associated to such a vector is the set function h:2^{\mathcal{E}}\to\mathbb{R}_{\geq 0} , h(\mathcal{A}):=H(S_{\mathcal{A}}) . A function h:2^{\mathcal{E}}\to\mathbb{R}_{\geq 0} is called a polymatroid if it is: • normalized ( h(\emptyset)=0 ), • monotone ( \mathcal{A}\subset\mathcal{B} implies h(\mathcal{A})\leq h(\mathcal{B}) ), and • submodular ( h(\mathcal{A})+h(\mathcal{B})\geq h(\mathcal{A}\cup\mathcal{B})+h(\mathcal{A}\cap\mathcal{B}) for all \mathcal{A},\mathcal{B} ). When h arises as above from the entropies of a random vector S , it is said to be entropic . More precisely, h is called the entropic polymatroid induced by the random vector S . 2.2. Matroids and algebraic matroids We next recall basic notions of matroid theory; see [

Read the complete text