# How far can the $\mathbb{F}_p$-rank of an integer matrix with small entries drop?

Let $$n$$ and $$k$$ be some fixed integers with $$1 \le k \le n$$. I am interested in conditions on the size of the integer coefficients of a non-singular $$n \times n$$-matrix $$A$$ which ensure that the $$\mathbb{F}_p$$-rank of this matrix can not drop by too much.

More precisely, let $$\alpha(n,k)$$ be the supremum of numbers $$\alpha$$ with the following property: There is a constant $$C=C(n,k)$$ such that if $$A$$ is a non-singular $$n \times n$$-matrix with integer coefficients, all of them bounded in absolute value by $$Cp^{\alpha}$$ from above, then $$A$$ has $$\mathbb{F}_p$$-rank at least $$k$$.

It is trivial that $$\alpha(n,k) \ge \frac{1}{k}$$ for otherwise no non-zero $$k \times k$$-minor can be divisible by $$p$$.

However, a slightly more sophisticated argument (as explained here) shows that $$\alpha(n,k) \ge \frac{n-k+1}{n}$$. Indeed, the main point is that bounding the entries by $$Cp^{\frac{n-k+1}{n}}$$ forces the determinant of the matrix to be less than $$p^{n-k+1}$$ so that in particular it is not divisible by $$p^{n-k+1}$$ from where one can conclude by a simple algebraic argument that the rank is at least $$k$$.

(Incidentally, note that $$\frac{n-k+1}{n} \ge \frac{1}{k}$$ so that this indeed improves on the previous bound.)

Now my question is: Is this bound sharp? That is, do we have $$\alpha(n,k)=\frac{n-k+1}{n}$$ for all $$n$$ and $$k$$?

It is easy to see that this is indeed the case if $$k=1$$ or $$k=n$$.

But already in the first non-trivial case $$n=3, k=2$$, it is not clear to me whether we have $$\alpha(3,2)=\frac{2}{3}$$. That is to say, if the integer entries of a non-singular $$3 \times 3$$-matrix are bounded (only) by $$p^{0.667}$$ (say), can we still say that its $$\mathbb{F}_p$$-rank is at least $$2$$?

Of course proving an upper bound on $$\alpha$$ amounts to proving the existence of certain matrices. It seems natural to try a probabilistic approach, but I did not succeed with this so far.

• Here's another way to get the lower bound of $\lVert A \rVert^n \gg \lvert\det(A)\rvert \gg p^{n-k+1}$. Namely, take a nonsingular $A$ of rank $\leq k-1$ and let $L$ be the lattice $A \mathbb Z^{n}$. Then $L \subset p\mathbb Z^{n} + \text{span of }k-1 \text{ vectors}$, so that $[0,p]^n$ is cut by $L$ into pieces of volume roughly $\text{Vol}([0,p])^n / p^{k-1}$ and you get the lower bound on $\text{Vol}(L)$ you want. Commented Jan 27, 2022 at 15:50

If you believe Bunyakovsky's conjecture, there are infinitely many primes of the form $$x^3+2$$. For such a prime $$p$$, consider the matrix $$\begin{bmatrix} 1&x&x^2 \\ x&x^2&-2 \\ x^2&-2&-2x \\ \end{bmatrix}= \begin{bmatrix} 1\\x\\x^2 \end{bmatrix} \begin{bmatrix} 1&x&x^2 \end{bmatrix} - p \begin{bmatrix} 0&0&0 \\ 0&0&1 \\ 0&1&x \end{bmatrix}.$$ Each entry of this matrix has magnitude at most $$x^2 < p^{2/3}$$, the matrix has rank $$1$$ modulo $$p$$, and the determinant is $$-(x^3+2)^2 = -p^2 \neq 0$$.

I suspect that someone with more knowledge of analytic number theory could replace Bunyakowsky with some more complicated statement which is known to be true. For example, if we knew that there were infinitely many examples of $$p = x^3 + O(x)$$, that would do it.

• Thanks a lot! I can imagine that similar constructions work for other values of $n$ and $k$, but do you believe there is a construction that works in general (assuming Bunyakovsky)? Commented Jan 27, 2022 at 19:24
• It is easy to see how to adapt this to the other $(n,2)$ cases. Also, $(4,3)$ is easy, because we just take two solutions to $(2,2)$ and direct sum them. But $(5,3)$ seems hard still. Commented Jan 27, 2022 at 19:25
• Incidentally, I'd like to shift your indexing by one and put $r=k-1$. This answer handles the case of $(n,r) = (3,1)$, and my comment above is that the direct sum of two $(2,1)$ solutions is a $(4,2)$ solution. Commented Jan 27, 2022 at 19:26
• I don't see it? I think you need to know that $x$ and $y$ can be taken of very different sizes for this to work. But I'd be glad to be proven wrong. Commented Jan 27, 2022 at 21:01
• Hm, what goes wrong if I take $$\begin{pmatrix} y^2 & xy & x^2\\xy & x^2 & -2y^2\\x^2 & -2y^2 & -2xy \end{pmatrix}$$? Commented Jan 27, 2022 at 21:14

I have a probabilistic approach showing your lower bound on $$\alpha$$ is sharp, and in fact your result can't be improved by more than a logarithmic factor, using the geometry of numbers.

The strategy is to count matrices with bounded entries of rank $$\leq r$$ (where $$r=k-1$$) and subtract off the ones which are not invertible. To count the non-invertible ones, we look at the lattice generated by their columns, which is a lattice of rank $$m, and then we prove an upper bound for the counting problem with the columns of the matrix restricted to lie in a lattice.

In fact, when counting matrices with rank $$\leq r$$, it is better to count them with a weight function that takes value $$1$$ on rank $$r$$ and larger values on ranks strictly smaller than $$r$$, as this weight function allows simple counts using geometry of numbers methods.

We begin by proving an upper bound in the lattice setting, and then, by similar methods, a lower bound. Using the lower bound for $$\mathbb Z^n$$ and then subtracting off the upper bound for sublattices, we will show that there are many such matrices with entries $$< C p^{ \frac{n-r}{n}} \log p$$.

Lemma 1: Let $$\Lambda$$ be a rank $$m$$ lattice and $$R$$ a positive real number. The number of tuples $$v_1,\dots, v_n \in \Lambda$$ with $$|v_i| such that $$v_1,\dots, v_n$$ generate a subspace of rank $$r$$ of $$\Lambda/p\Lambda$$ and a sublattice of rank $$m$$ of $$\Lambda$$ is $$\ll\frac{R^{mn}}{ \operatorname{vol}(\Lambda)^n p^{ (m-r)(n-r) }} .$$

Proof: For each such tuple, there exists at least $$1$$ subspace $$W$$ of $$\Lambda/ p \Lambda$$ of dimension $$r$$ such that $$v_1,\dots, v_n \in W$$. Let's estimate the number of allowable tuples $$v_1,\dots, v_n$$ for a fixed $$W$$. Let $$\Lambda'$$ be the sublattice of $$\Lambda$$ consisting of vectors that modulo $$p$$ lie in $$W$$. Then $$\Lambda'$$ has volume $$\operatorname{vol}(\Lambda) p^{ (m-r)}$$. For any such tuple to exist, the $$m$$ successive minima of $$\Lambda'$$ must be $$. For a lattice $$\Lambda'$$ with all successive minima $$, the number of vectors of length $$ in the lattice is $$\ll R^m / \operatorname{vol}(\Lambda')$$. So the number of $$n$$-tuples is $$\ll\frac{ R^{mn} }{ \operatorname{vol}(\Lambda')^n} =\frac{ R^{mn} }{\operatorname{vol}(\Lambda)^n p^{ n (m-r)} } .$$ Summing over the $$\ll p^{r (m-r)}$$ choices of $$W$$, we get the claim.

A similar geometry of numbers approach can be used to get a lower bound. However, the lower bound is not quite for the quantity we want.

Lemma 2: Let $$\Lambda$$ be a rank $$m$$ lattice and $$R$$ a positive real number. The sum over tuples $$v_1,\dots, v_n \in \Lambda$$ with $$|v_i| of the number of $$r$$-dimensional subspaces of $$\Lambda / p\Lambda$$ containing $$v_1,\dots, v_n$$ is $$\gg \frac{R^{mn}}{ \operatorname{vol}(\Lambda)^n p^{ (m-r)(n-r) }} .$$

Proof: Exchanging the order of summation, this is the sum over subspaces $$W$$ of $$\Lambda/p\Lambda$$ of dimension $$r$$ of the number of $$n$$-tuples of vectors of length $$ in $$\Lambda$$ congruent mod $$p$$ to elements of $$W$$. Let $$\Lambda'$$ be the sublattice of $$\Lambda$$ consisting of vectors that modulo $$p$$ lie in $$W$$, with volume $$\operatorname{vol}(\Lambda)/p^{n-r}$$. We now use the fact that, regardless of the successive minima, the number of vectors of length $$ in the lattice is $$\gg R^n / \operatorname{vol}(\Lambda')$$ (Blichfeldt's theorem). Since the number of possible $$W$$ is $$\gg p^{ r(m-r)}$$, this gives the claim.

Specializing Lemma 2 to the integer lattice with $$m=n$$, we see that the sum over $$n \times n$$ integer matrices with column norms $$ of the number of rank $$r$$ subspaces of $$\mathbb F_p^n$$ containing the image mod $$p$$ is $$\gg \frac{R^{n^2}}{ p^{(n-r)^2}}$$. This sum is supported on matrices of rank $$\leq r$$ mod $$p$$, so to show there exists an invertible matrix of rank $$\leq r$$ mod $$p$$, it suffices to show that the restriction of this sum to invertible matrices is nonzero. That is, it suffices to show

$$\sum_{m=0}^{n-1} \sum_{ \substack{v_1,\dots, v_n \in \mathbb Z^m \\ \operatorname{rank} \langle v_1,\dots,v_n \rangle=m}} \# \{ W \subset \mathbb F_p^n \mid \dim W =r, v_i \mod p \in W\} = o \left( \frac{R^{n^2}}{ p^{(n-r)^2}} \right)$$ as then the contribution of the non-invertible matrices would be smaller than the total contribution and so the sum over invertible matrices is nonzero. We have (explanations to be offered after the chain of inequalities)

$$\sum_{m=0}^{n-1} \sum_{ \substack{v_1,\dots, v_n \in \mathbb Z^m \\ \operatorname{rank} \langle v_1,\dots,v_n \rangle=m}} \# \{ W \subset \mathbb F_p^n \mid \dim W =r, v_i \mod p \in W\}$$

$$\ll \sum_{m=0}^{n-1} \sum_{s=0}^{\min(m,r)} \sum_{ \substack{v_1,\dots, v_n \in \mathbb Z^m \\ \operatorname{rank} \langle v_1,\dots,v_n \rangle=m \\ \dim \langle v_1,\dots,v_n \mod p \rangle=s }} p^{ (m-r) (r-s)}$$

$$= \sum_{m=0}^{n-1} \sum_{s=0}^{\min(m,r)} \sum_{\substack{ \Lambda \subset \mathbb Z^n \\ \operatorname{rank} \Lambda = m \\ \Lambda \textrm{ primitive}\\ \operatorname{vol}(\Lambda) \leq R^m}} \sum_{ \substack{v_1,\dots, v_n \in \Lambda \\ \operatorname{rank} \langle v_1,\dots,v_n \rangle=m \\ \dim \langle v_1,\dots,v_n \mod p \rangle=s }} p^{ (m-r) (r-s)}$$

$$\ll \sum_{m=0}^{n-1} \sum_{s=0}^{\min(m,r)} \sum_{\substack{ \Lambda \subset \mathbb Z^n \\ \operatorname{rank} \Lambda = m \\ \Lambda \textrm{ primitive}\\ \operatorname{vol}(\Lambda) \leq R^m}} \frac{R^{mn}}{ \operatorname{vol}(\Lambda)^n p^{(m-s)(n-s)}} p^{ (m-r) (r-s)}$$

$$\ll \sum_{m=0}^{n-1} \sum_{s=0}^{\min(m,r)} \frac{R^{mn} \log R}{ p^{(m-s)(n-s)}} p^{ (m-r) (r-s)}$$ where the first inequality uses the fact that that the number of subspaces containing a given subspace is the number of $$\mathbb F_p$$-points on a Grassmanian, which is $$\ll p$$ raised to the dimension of that Grassmanian, the second equality uses the fact that $$\langle v_1,\dots, v_n\rangle$$ is contained in a unique primitive lattice $$\Lambda$$ of the same rank, and since $$\Lambda$$ is primitive, $$\Lambda / p \Lambda \to \mathbb Z^n/p \mathbb Z^n$$ is injective, so $$v_1,\dots, v_n$$ generate a subspace of the same rank in each, the next line uses Lemma 1, and the last inequality uses Schmidts theorem that the number of primitive lattices in $$\mathbb Z^n$$ with volume $$ is $$\ll X^n$$, together with an integration by parts.

We now investigate the sums in $$m$$ and $$s$$ in the final bound. The dependence on $$m$$ is given by $$(R^n p^{r-s - (n-s)})^m$$ or $$(R^n p^{r-n})^m$$. If $$R > p^{\frac{n-r}{n}}$$ then this is maximized at $$m=n-1$$, where we get a term of

$$\sum_{s=0}^r R ^{n(n-1)} p^{ (n-1-r)(r-s) - (n-s) (n-1-s) } \log R.$$

Differentiating the exponent with respect to $$s$$, we see it is maximized at $$s =\frac{n+r}{2}$$, which means on the interval $$[0,r]$$ it is maximized at $$r$$, meaning the sum is $$\ll R^{ n(n-1)} p^{ - (n-r)(n-1-r)}\log R$$, which, divided by the main term $$R^{n^2} p^{-(n-r)^2}$$, is $$p^{n-r} \log R / R^n$$. Assuming $$R$$ is greater than $$p^{ (n-r)/n}$$ by a logarithmic factor, there are matrices with row norms $$ which are invertible and have rank $$\leq r$$ modulo $$p$$.

• The statement of Lemma 2 seems to be missing an $m$? Commented Jan 27, 2022 at 21:03
• @DavidESpeyer Sorry, that was meant to be the rank of the lattice, fixed. Commented Jan 27, 2022 at 21:16
• In Lemma 1, "subspace of rank $r$ of $\Lambda$" should be "subspace of rank $r$ of $\Lambda/p\Lambda$", right? (This is clearly the right approach, but I am having trouble checking the details, so I'm asking questions as I go.) Commented Jan 28, 2022 at 1:49
• @DavidESpeyer Yes - Thanks for reading it carefully! Commented Jan 28, 2022 at 1:53
• Okay, I now agree this works. Besides the summation by parts, the other thing that took me a while to see is that, if $\Lambda$ is primitive in $\mathbb{Z}^n$, and $v_1$, $v_2$, \dots, $v_n \in \Lambda$ generate a rank $r$ subspace of $\mathbb{Z}^n/p \mathbb{Z}^n$, then they also generate a rank $r$ subspace of $\Lambda/p \Lambda$. This might be worth pointing out explicitly, since you need it to use Lemma 1. Commented Jan 28, 2022 at 2:27