Computation of the Hilbert Series for the Support-Minors Modeling of the MinRank Problem
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916850849284096 |
|---|---|
| author | Bardet, Magali Gilard, Alban |
| author_facet | Bardet, Magali Gilard, Alban |
| contents | The MinRank problem is a simple linear algebra problem: given matrices with coefficients in a field, find a non trivial linear combination of the matrices that has a small rank. There are several algebraic modeling of the problem. The main ones are: the Kipnis-Shamir modeling, the Minors modeling and the Support-Minors modeling. The Minors modeling has been studied by Faug{è}re et al. in 2010, where the authors provide an analysis of the complexity of computing a Gr{ö}bner basis of the modeling, through the computation of the exact Hilbert Series for a generic instance. For the Support-Minors modeling, the first terms of the Hilbert Series are given by Bardet et al. in 2020 based on an heuristic and experimental work. In this work, we provide a formula and a proof for the complete Hilbert Series of the Support Minors modeling for generic instances. This is done by adapting well known results on determinantal ideals to an ideal generated by a particular subset of the set of all minors of a matrix of variables. We then show that this ideal is generated by |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_12721 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Computation of the Hilbert Series for the Support-Minors Modeling of the MinRank Problem Bardet, Magali Gilard, Alban Cryptography and Security Symbolic Computation The MinRank problem is a simple linear algebra problem: given matrices with coefficients in a field, find a non trivial linear combination of the matrices that has a small rank. There are several algebraic modeling of the problem. The main ones are: the Kipnis-Shamir modeling, the Minors modeling and the Support-Minors modeling. The Minors modeling has been studied by Faug{è}re et al. in 2010, where the authors provide an analysis of the complexity of computing a Gr{ö}bner basis of the modeling, through the computation of the exact Hilbert Series for a generic instance. For the Support-Minors modeling, the first terms of the Hilbert Series are given by Bardet et al. in 2020 based on an heuristic and experimental work. In this work, we provide a formula and a proof for the complete Hilbert Series of the Support Minors modeling for generic instances. This is done by adapting well known results on determinantal ideals to an ideal generated by a particular subset of the set of all minors of a matrix of variables. We then show that this ideal is generated by |
| title | Computation of the Hilbert Series for the Support-Minors Modeling of the MinRank Problem |
| topic | Cryptography and Security Symbolic Computation |
| url | https://arxiv.org/abs/2502.12721 |