# Matrix with small elements and prescribed determinant

Let $p$ be a large prime number. I want a $k\times k$ matrix with determinant $p$ and bounded integer elements (say, from -100 to 100). For which minimal $k$ such a matrix does always exist? We can not hope for anything better than $k=O(\log p/\log\log p)$, which corresponds to $p\sim k^{Ck}$, and we may always achieve $k=O(\log p)$ if I understood correctly the answers to this question (determinant of (0,1) $k\times k$ matrices achieve all values between 0 and something exponential in $k$.)

• Alternatively, the bound $k = O(\log p)$ can be achieved by writing $p=Q(2)$ where $Q$ is a polynomial with coefficients in $\{ 0 ,1 \}$ (base $2$ expansion), and then by noting that $p = \det(2 I - M)$ where $M$ is the companion matrix of $Q$. The matrix $2I - M$ has coefficients in $\{-1,0,1,2,3 \}$. – js21 Feb 6 '17 at 14:32
• Yes, but such constructions can not give better bounds, since after an elementary transform the rows of our matrix (almost all of them) have bounded norms. – Fedor Petrov Feb 6 '17 at 19:12
• So, you need something better than just saying it's between $\log p$ and $\log p/\log\log p$? – Gerry Myerson Feb 6 '17 at 22:10
• I think he wants a proof that it is O(log p/ log log p). I don't have a proof, but a darned good idea (augmentation) in that direction. Gerhard "It's The Idea That Counts" Paseman, 2017.02.06. – Gerhard Paseman Feb 6 '17 at 22:51
• @GerryMyerson Yes, I am not completely satisfied by this double logarithm gap between lower and upper bound. – Fedor Petrov Feb 7 '17 at 13:46

As p is a prime, the Smith Normal Form of such a matrix will have all entries equal to 1, save for the last. This means the matrix will need to have small (determinants for some of its) minors and that (by truncating to lower dimensions) the span of some rows will have a small volumed facet. It may be possible to set k to that value so that $(Mk^{1/2})^k$ is a little larger than p (and $M$ plays the role of 100) and then use random matrices with large and sufficiently coprime entries, but it might be better to try to reverse engineer a SNF matrix to build what you want.