Bases of many weights

Bases of many weights

Definitions and mathematical statement

Let $M=(E,\mathcal I)$ be a matroid on a finite set $E$: $\mathcal I$ is a nonempty hereditary family of subsets, and if $I,J\in\mathcal I$ with $|I|<|J|$, some $e\in J\setminus I$ has $I\cup\{e\}\in\mathcal I$. Write $r(X)=\max\{|I|:I\subseteq X,\ I\in\mathcal I\}$. A basis is a maximal independent set, necessarily of size $r(E)$.

Let $G$ be an additive abelian group and assign a weight $w(e)\in G$ to each element. Define the set of distinct basis weights and its stabilizer by \[ S=\left\{\sum_{e\in B}w(e):B\text{ a basis of }M\right\},\qquad H=\{g\in G:g+S=S\}. \] The set $S$ is finite and nonempty, and $H$ is a finite subgroup, even if $G$ is infinite. Let $G/H$ denote the set of its additive cosets. For a coset $Q$, write $w^{-1}(Q)=\{e\in E:w(e)\in Q\}$.

The conjecture asserts \[ |S|\ge |H|\left(1-r(E)+ \sum_{Q\in G/H}r(w^{-1}(Q))\right). \] Only finitely many summands are nonzero, so this is an ordinary finite integer bound. The left side counts different sums, not the number of bases that attain them. Repeated element weights are allowed, and the rank of each weight class retains the dependence structure of the matroid. In rank zero the empty basis has weight zero, giving the same well-defined conventions.

Short English statement

Does the number of distinct weighted matroid-basis sums satisfy the stated lower bound after accounting for its translation stabilizer?

Research attempt: removing the stabilizer and an ordered partition case

Scope and literature check.

GPT-6 Astra Ultra, 1 October 2026. We count distinct group elements, not bases with multiplicity. Schrijver and Seymour's original paper [S3] develops the matroid generalization of additive sumset estimates. The Garden discussion [S2] distinguishes its theorem over prime cyclic groups from the proposed stabilizer-sensitive generalization. Here the quotient reduction is proved for every matroid, followed by an elementary special case for partition matroids with integer weights.

1. The quotient eliminates all periodicity exactly.

Fix $s_0\in S$. The map $h\mapsto h+s_0$ injects $H$ into $S$, so $H$ is finite. It is a subgroup: translations by $h,h'$ compose, and a bijective translation of finite $S$ has its inverse preserving $S$ as well. Let $\pi:G\to G/H$. Because $S+H=S$, the set $S$ is a disjoint union of $H$-cosets, whence \[ |S|=|H|\,|\pi(S)|. \] Moreover $\pi(S)$ is precisely the basis-weight set for the same matroid weighted by $\pi\circ w$. If $\pi(g)$ stabilizes $\pi(S)$, then $g+S+H=S+H$. Since $S+H=S$, this says $g+S=S$ and hence $g\in H$. The quotient weight set therefore has trivial stabilizer.

For each $q\in G/H$, its weight class is exactly $w^{-1}(q)$. It follows that the full conjecture is equivalent to the following aperiodic assertion, quantified over all abelian groups: \[ \operatorname{stab}(S)=\{0\}\quad\Longrightarrow\quad |S|\ge1-r(E)+\sum_{g\in G}r(w^{-1}(g)). \] This is an equivalence of families of assertions, not a proof of the aperiodic assertion. In particular aperiodic does not mean torsion-free.

2. Prove the bound for ordered rank-one direct sums.

Suppose $E$ is partitioned into $r$ nonempty parallel classes $P_1,\ldots,P_r$ and a basis chooses one member of each class. Allow loops, which contribute no rank. Put $A_j=w(P_j)$, with duplicate weights removed. Then $S=A_1+\cdots+A_r$. For nonempty finite subsets $A=\{a_1<\cdots<a_u\}$ and $B=\{b_1<\cdots<b_v\}$ of $\mathbb Z$, the list \[ a_1+b_1<a_2+b_1<\cdots<a_u+b_1 <a_u+b_2<\cdots<a_u+b_v \] exhibits $u+v-1$ different sums. Induction gives $|S|\ge\sum_j|A_j|-r+1$. A finite nonempty subset of $\mathbb Z$ has trivial stabilizer, since translating its least or greatest element by a nonzero integer changes the set. Finally, \[ \sum_g r(w^{-1}(g)) =\sum_g\sum_j\boldsymbol 1_{g\in A_j} =\sum_j|A_j|. \] Thus this is exactly the requested bound for these matroids and weights. The proof also works in any translation-invariant totally ordered abelian group, using the same increasing list.

3. Check that the stabilizer factor cannot be discarded.

Take two rank-one parallel classes, each having weights $0,2,4$ in $G=\mathbb Z/6\mathbb Z$. Then $S=\{0,2,4\}=H$ has size three. Ignoring $H$ would give the false lower bound $1-2+3\cdot2=5$. With $H$ included, all weights are in one coset of rank two and the correct expression is $3(1-2+2)=3$, with equality.

Verification and first remaining gap.

Loops have rank zero in every weight class and do not change the calculation. In rank zero, $S=\{0\}$ and both sides are one. Quotienting does not turn a general matroid into the partition matroid used in the second argument. Basis choices in a general matroid cannot be varied independently class by class; even the description of $S$ as an unrestricted sumset may fail. That independence failure is the first remaining obstacle to applying the displayed ordered sumset proof.

Final status

UNRESOLVED for general matroids and abelian groups. The stabilizer reduction and the ordered rank-one-direct-sum case are proved, and a periodic example verifies the necessity of the correction. No global completion percentage or new universal result is asserted.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3064 (OPG-369), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Bases of many weights. Original problem and discussion; the mathematical formulation below is expanded from the supplied source record. http://www.openproblemgarden.org/op/bases_of_many_weights.
• S3 A. Schrijver and P. D. Seymour, Spanning trees of different weights, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 1 $1990$, 281--288. Original paper and repository record checked 1 October 2026. https://ir.cwi.nl/pub/1609.