The polytope of all q q -rank functions

Gianira N. Alfarano 1, Sebastian Degen 2 · 2025

Read The polytope of all q q -rank functions by Gianira N. Alfarano 1, Sebastian Degen 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-2505-08018.txt.

Introduction

Gianira Alfarano and Sebastian Degen study the polytope of all q-rank functions in a 2025 mathematics paper. A q-rank function assigns values to subspaces, bounded by dimension, never decreasing, and obeying a submodularity law. Each such function matches the rank function of a q-polymatroid, a structure used in coding theory and combinatorics.

The authors show these functions can be viewed as points in a polytope. That polytope holds no interior lattice points, so the points for q-matroids sit among its vertices. They then study convex combinations of two lattice points, looking at independence, flats, and cyclic flats. Special attention goes to combinations of paving and uniform q-matroids.

Catalog record

CREATORGianira N. Alfarano 1, Sebastian Degen 2
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE102 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-08018

Browse the full library · About the Tower of Babel

Full text

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

The polytope of all q q -rank functions Gianira N. Alfarano 1, Sebastian Degen 2 Abstract . A q q -rank function is a real-valued function defined on the subspace lattice that is non-negative, upper bounded by the dimension function, non-drecreasing, and satisfies the submodularity law. Each such function corresponds to the rank function of a q q -polymatroid. In this paper, we identify these functions with points in a polytope. We show that this polytope contains no interior lattice points, implying that the points corresponding to q q -matroids are among its vertices. We investigate several properties of convex combinations of two lattice points in this polytope, particularly in terms of independence, flats, and cyclic flats. Special attention is given to the convex combinations of paving and uniform q q -matroids. Keywords. polytopes, q -rank function, q -polymatroids, rank-metric codes. 1. Introduction The concept of matroid abstracts the notion of independence in vector spaces and graphs. Matroids have been extended in various directions, including polymatroids [ 8 ] , valuated matroids [ 7 ] , and, more recently, latroids [ 26 , 18 ] and q -analogues such as q -matroids [ 21 ] , q -polymatroids [ 17 , 25 ] , and \mathcal{L} -polymatroid [ 1 , 5 ] . In the classical setting, let S be a finite set of cardinality n . The rank function of a polymatroid is a real-valued function defined on all the subsets of S , which is non-decreasing, submodular, and upper bounded by the cardinality function. The cone of all such polymatroid rank functions has been studied in [ 23 ] , particularly to characterize its extremal rays and extremal polymatroids. Further developments appear in [ 11 , 22 ] , and analogous investigations have been conducted for supermodular functions; see [ 19 ] . In this paper, we focus on q -rank functions , i.e. rank functions of q -polymatroids. Let \mathbb{F}_{q} be the finite field of order q , let E be an n -dimensional vector space over \mathbb{F}_{q} and let \mathcal{L}(E) be the lattice of subspaces of E ordered with inclusion. A q -rank function is defined on \mathcal{L}(E) , and it is real-valued, non-negative, upper bounded by the dimension function, non-decreasing and submodular. If, in particular, such a function is integer-valued, then it is the rank function of a q -matroid. We define the polytope of all q -rank functions \mathcal{P}_{q}^{n}\subseteq\mathbb{R}^{|\mathcal{L}(E)|} as the polytope defined by the linear inequalities given by the above properties. More specifically, up to ordering the spaces in \mathcal{L}(E) , we have that a point in (p_{X})_{X\in\mathcal{L}(E)}\in\mathcal{P}_{q}^{n} has coordinates indexed by the spaces in \mathcal{L}(E) and the entries are precisely the values that a q -rank function takes in each X\in\mathcal{L}(E) . Hence, the integer points in this polytope correspond precisely to q -matroids. We show that \mathcal{P}_{q}^{n} has dimension |\mathcal{L}(E)|-1 ; see Proposition 3.5 . However, as this dimension grows rapidly with n , analyzing its geometry becomes challenging. One of our main results in this direction is that \mathcal{P}_{q}^{n} contains no integer points (lattice points) in its interior; see Theorem 3.8 . In particular, this means that all q -matroids correspond to the vertices with integer coordinates. It is clear that as soon as n grows, the number of vertices also increases. Being this a polytope described by constraints with rational coefficients, it is a rational polytope, i.e. all its vertices have rational coordinates. We introduce convex combinations of points in \mathcal{P}_{q}^{n} as an operation on q -polymatroids. Beyond establishing general results on the flats of such combinations (see Section 4.1 ), we focus in particular on the convex combination with rational coefficients of q -matroids. We investigate how key structural elements, such as cyclic spaces and \mu -independent spaces (where \mu is a denominator of the resulting q -polymatroid), behave under this operation. Specifically, we express these features of the resulting q -polymatroid in terms of the cyclic spaces and independent spaces of the original q -matroids. We specialize our analysis to convex combinations involving two important families of q -matroids: paving q -matroids and uniform q -matroids. For paving q -matroids, we focus particularly on a construction introduced in [ 13 ] . In this context, we introduce the notion of \mu -pavingness for q -polymatroids and show that the convex combination of two paving q -matroids, built using this special construction, yields a \mu -paving q -polymatroid, where the denominator \mu is not necessarily principal; see Theorem 5.6 . We further characterize important structural features of the resulting q -polymatroid: its flats (Theorem 5.11 ), cyclic spaces (Theorem 5.12 ), and cyclic flats (Corollary 5.13 ). For the convex combination of two uniform q -matroids, we provide characterizations of \mu -independent spaces, under specific constraints (see Theorems 6.1 and 6.2 ), and cyclic flats (see Proposition 6.8 ). These ideas are then extended to the convex combination of n-2 uniform q -matroids, yielding further results on \mu -independence (see Theorem 6.5 ). Another well-studied concept in matroid theory is the characteristic polynomial. Generalizations of this invariant have been proposed for q -matroids, integer q -polymatroids, and \mathcal{L} -matroids; see [ 20 , 3 , 1 ] . In this work, we introduce a broader notion of the characteristic polynomial, tailored for q -polymatroids whose q -rank functions take rational values. Specifically, we define an invariant, the characteristic Puiseux polynomial , associated with such q -polymatroids. This invariant is not a polynomial in the classical sense: it is a truncated Puiseux series, meaning a finite linear combination of monomials whose exponents may be rational (and possibly negative). Despite this departure from classical polynomials, we adopt the name characteristic Puiseux polynomial to emphasize its structural role and its connection to existing generalizations in matroid theory. We show that the characteristic Puiseux polynomial of the convex combination with rational coefficients of two paving q -matroids obtained from the construction in [ 13 ] not only can be expressed in terms of their characteristic polynomials, but only one of them is enough; see Theorem 7.4 . One of the drawbacks of the polytope of all q -rank function is that we are not able to distinguish representable q -polymatroids. This difficulty is due to the lack of an axiomatic definition that applies only for the representable case. However, we illustrate some examples of convex combination of special representable q -polymatroids arising from rank-metric codes; see Theorem 8.8 . The rest of the paper is organized as follows. In Section 2 , we provide the basic notions on q -polymatroids. In Section 3 , we introduce the polytope of all q -rank functions and initiate the study of its geometric properties. In Section 4 , we define the convex combination of q -polymatroids and provide its first properties. In Section 5 , we characterize the convex combination with rational coefficients of some paving q -matroids. In Section 6 , we consider the convex combination of uniform q -matroids. In Section 7 , we introduce the Puiseux characteristic polynomial for rational q -rank functions and we study the one of the convex combination of paving q -matroids. In Section 8 , we provide

Read the complete text