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$.)
$\begingroup$
$\endgroup$
5
asked Feb 6, 2017 at 8:01
-
2$\begingroup$ 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 \}$. $\endgroup$– js21Commented Feb 6, 2017 at 14:32
-
$\begingroup$ 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. $\endgroup$– Fedor PetrovCommented Feb 6, 2017 at 19:12
-
1$\begingroup$ So, you need something better than just saying it's between $\log p$ and $\log p/\log\log p$? $\endgroup$– Gerry MyersonCommented Feb 6, 2017 at 22:10
-
$\begingroup$ 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. $\endgroup$– Gerhard PasemanCommented Feb 6, 2017 at 22:51
-
1$\begingroup$ @GerryMyerson Yes, I am not completely satisfied by this double logarithm gap between lower and upper bound. $\endgroup$– Fedor PetrovCommented Feb 7, 2017 at 13:46
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
No answer, but an observation and a suggestion.
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.
Another approach is augmentation. Start with an order n matrix Q with large determinant near p in size. The determinant will likely have few or no prime factors larger than log(p). Build an order n+1 matrix with Q as minor, and play with the additional row and column to get the determinant closer to p. If Q resembles a Hadamard matrix, the determinant of the augmented matrix will share many prime factors in common because the minors of Q will be mostly the same. Call this attempt P.
Now the minors of P will have more variation, and you can augment P to get a determinant even closer to p. My intuition suggests that fewer than log n augmentations will be needed to reach p. If you decide to try it, I suggest playing with Mersenne and Proth primes with b binary digits, M something less than b, and start with n about square root of b or smaller.
MathOverflow has references of which I remember only fragments. Richard Stanley has recently been coauthor on a paper involving SNF of such matrices, and there have been questions asking about determinant spectra for matrices with small entries. I recommend you ask Will Orrick directly if he does not respond to this post.
Gerhard "Hasn't Improved On Exponential Lately" Paseman, 2017.02.06.
answered Feb 6, 2017 at 20:25