Number of matrices with bounded products of rows and columns

This problem was considered in passing in the proof of Theorem 4.1 in Granville and Soundararajan, see the argument starting at the bottom of page 17. They show (in your notation) that $M_d(x)$ is of order $x^d (\log x)^{(d-1)^2}$. You should also look at work of Harper, Nikeghbali and Radziwill which shows an asymptotic formula for closely related objects (see Theorem 3 there).


Nice question. Some thoughts on lower bounds: for $d=2$, the order of magnitude $x^2\log x$ is correct—here is an argument giving such a lower bound.

For any real numbers $U,V$ such that $UV=x$ (and say $U,V\ge2$), any $2\times 2$ matrix such that $a_{11},a_{22}\in\big(\frac U2,U\big]$ and $a_{21},a_{12}\in\big(\frac V2,V\big]$ is counted by $M_2(x)$, and the number of such matrices is $\gg U^2V^2 = x^2$. We can sum this dyadic-interval lower bound over $U=2^k$ for a suitable range of $k$ to obtain the lower bound $M_2(x) \gg x^2\log x$.

A similar argument gives a lower bound for general $d\ge3$. If $U_1U_2\cdots U_d=x$, with the convention that $U_{d+j}=U_j$, then the matrices such that $a_{ij} \in \big( \frac{U_{i+j}}2, U_{i+j}\big]$ for all $1\le i,j\le d$ contribute $\gg U_1^d \cdots U_d^d = x^d$ to $M_d(x)$. We then sum over all $U_1=2^{k_1},\dots,U_d=2^{k_d}$ such that $k_1+\cdots+k_d\le(\log x)/\log 2$; the number of such $d$-tuples of positive integers is $\gg_d(\log x)^d$, giving the lower bound $M_d(x) \gg_d x^d(\log x)^d$.


Let $M_d(x_1,y_1,\dotsc,x_d,y_d)$ be the number of matrices $(a_{ij})$ with positive integer entries such that the product of the $i$-th row is at most $x_i$, and the product of the $i$-th column is at most $y_i$. I claim that $$M_d(x_1,y_1,\dotsc,x_d,y_d)\ll_d\sqrt{x_1y_1}\prod_{i=2}^d\sqrt{x_iy_i}\log(2x_iy_i)^{2i-3}.\tag{$\ast$}$$ In particular, this implies the bound in Lucia's response: $$M_d(x)=M_d(x,x,\dotsc,x,x)\ll_d x^d\log(2x)^{(d-1)^2}.$$ We can prove $(\ast)$ by induction on $d$. For $d=1$ the statement is clear (the empty product means $1$). So let us assume that $d\geq 2$, and $(\ast)$ holds with $d-1$ in place of $d$.

For a matrix $(a_{ij})$ to be counted, let us abbreviate $$s_i:=a_{id},\qquad t_j:=a_{dj},\qquad a:=a_{dd}.$$ Then we see that \begin{align*}M_d(x_1,y_1,\dotsc,x_d,y_d) &\ll_d\sum_{a\leq\sqrt{x_dy_d}}\sum_{\substack{s_1\dots s_{d-1}\leq y_d/a\\t_1\dots t_{d-1}\leq x_d/a}}M_{d-1}\left(\frac{x_1}{s_1},\frac{y_1}{t_1},\dotsc,\frac{x_{d-1}}{s_{d-1}},\frac{y_{d-1}}{t_{d-1}}\right)\\ &\ll_d\sum_{a\leq\sqrt{x_dy_d}}\sum_{\substack{s_1\dots s_{d-1}\leq y_d/a\\t_1\dots t_{d-1}\leq x_d/a}}\sqrt{\frac{x_1y_1}{s_1t_1}}\prod_{i=2}^{d-1}\sqrt{\frac{x_iy_i}{s_it_i}}\log(2x_iy_i)^{2i-3}. \end{align*} On the right hand side, we observe that \begin{align*} \sum_{\substack{s_1\dots s_{d-1}\leq y_d/a\\t_1\dots t_{d-1}\leq x_d/a}}\frac{1}{\sqrt{s_1t_1\dots s_{d-1}t_{d-1}}} &=\left(\sum_{m\leq x_d/a}\frac{\tau_{d-1}(m)}{\sqrt{m}}\right) \left(\sum_{n\leq y_d/a}\frac{\tau_{d-1}(n)}{\sqrt{n}}\right)\\ &\ll_d\frac{\sqrt{x_dy_d}}{a}\log(2x_dy_d)^{2d-4}. \end{align*} Therefore, we can bound $M_d(x_1,y_1,\dotsc,x_d,y_d)$ as \begin{align*}M_d(\cdots) &\ll_d\sqrt{x_1y_1}\left(\prod_{i=2}^{d-1}\sqrt{x_iy_i}\log(2x_iy_i)^{2i-3}\right)\sum_{a\leq\sqrt{x_dy_d}}\frac{\sqrt{x_dy_d}}{a}\log(2x_dy_d)^{2d-4}\\ &\ll_d\sqrt{x_1y_1}\prod_{i=2}^d\sqrt{x_iy_i}\log(2x_iy_i)^{2i-3}. \end{align*} The proof of $(\ast)$ is complete.