The finite basis problem and subvariety intervals for max-plus matrix semirings
Abstract
Let S=(N,max,+) be the max-plus algebra of the nonnegative integers, and let S̅ be obtained from S by adjoining −∞ as a semiring zero. We first prove that the varieties generated by the full matrix semirings Matn(S) and by the upper triangular matrix semirings UTn(S̅) form strictly ascending chains. Every interval between distinct members of either chain has cardinality 2ℵ0 and contains a chain and an antichain of that cardinality. The proof uses finite syntactic semirings associated with prime-cycle languages and an independent family of identities. We then construct finite commutative ai-semirings from languages of monomials closed under divisibility and prove their bounded-variable property by cancellation, explicit integer evaluations and independence in a free abelian group. A loop-block identity for upper triangular matrices and dimension-independent cubic-padding identities for full matrices show that every variety in each of the above intervals has infinite axiomatic rank. In fact, every variety between V(S) and the variety generated by all full matrix dimensions has infinite axiomatic rank. These varieties are therefore nonfinitely based, also relative to the ai-semiring axioms. Finally, for every fixed full matrix dimension, we prove equational equivalence over all six positive or nonnegative integer, rational and real coefficient domains. The original convex-ideal countermodels and their full-matrix transfer proof are recalled separately for comparison; they are not used in the algebraic proofs. Throughout, the signature consists of two binary operations and contains no constant symbols.
Related
- Subvariety intervals and limit varieties of zero extensions of mirror-word semirings
- The finite basis problem for 2× 2 triangular Boolean matrix semirings and incidence semirings
- Matrix varieties over S7: dimension-three stability and continuum-sized subvariety intervals
- The finite basis problem for varieties generated by all semirings of a fixed order
- The Finite Basis Problem for Multiplicatively Idempotent Semirings
BibTeX
@misc{jiao2026finite,
title = {{The finite basis problem and subvariety intervals for max-plus matrix semirings}},
author = {Jun Jiao and Mengya Yue},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.20257},
eprint = {2610.20257},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.20257},
}
RIS
TY - UNPB
TI - The finite basis problem and subvariety intervals for max-plus matrix semirings
AU - Jun Jiao
AU - Mengya Yue
PY - 2026
DA - 2026/10/14
PB - arXiv
DO - 10.48550/arxiv.2610.20257
UR - https://arxiv.org/abs/2610.20257
AB - Let S=(N,max,+) be the max-plus algebra of the nonnegative integers, and let S̅ be obtained from S by adjoining −∞ as a semiring zero. We first prove that the varieties generated by the full matrix semirings Mat_n(S) and by the upper triangular matrix semirings UT_n(S̅) form strictly ascending chains. Every interval between distinct members of either chain has cardinality 2^ℵ_0 and contains a chain and an antichain of that cardinality. The proof uses finite syntactic semirings associated with prime-cycle languages and an independent family of identities. We then construct finite commutative ai-semirings from languages of monomials closed under divisibility and prove their bounded-variable property by cancellation, explicit integer evaluations and independence in a free abelian group. A loop-block identity for upper triangular matrices and dimension-independent cubic-padding identities for full matrices show that every variety in each of the above intervals has infinite axiomatic rank. In fact, every variety between V(S) and the variety generated by all full matrix dimensions has infinite axiomatic rank. These varieties are therefore nonfinitely based, also relative to the ai-semiring axioms. Finally, for every fixed full matrix dimension, we prove equational equivalence over all six positive or nonnegative integer, rational and real coefficient domains. The original convex-ideal countermodels and their full-matrix transfer proof are recalled separately for comparison; they are not used in the algebraic proofs. Throughout, the signature consists of two binary operations and contains no constant symbols.
ER -