On the Column Number of Delta-Modular Matrices: an $O(m^2\Delta )$ Bound via the Shifted Heller Constant

Abstract

In this paper, we build on the analysis initiated by Averkov and Schymura (2022) and prove that the shifted Heller constant for matrices with $m$ rows is at most $m^2+m$ for all sufficiently large $m$. Consequently, the number of distinct columns of a $\Delta$-modular matrix $A\in Z^{m\times n}$ of rank $m$ is at most $O(m^2\Delta )$. This improves upon the earlier bounds of $O(m^4\Delta )$ and $O(m^2{\Delta }^2)$.