Number of matrices with bounded products of rows and columns

Question

Fix an integer $d \geq 2$ and for every real number $x$ let $M_d(x)$ be number of $d \times d$ matrices $(a_{ij})$ satisfying: every $a_{ij}$ is a positive integer, the product of every row does not exceed $x$, and the product of every column does not exceed $x$.

I'm looking for a good upper bound for $M_d(x)$ as $x \to +\infty$.

If we forget about the condition on the columns, since it is well known that the number of $d$-tuples $(b_1, \dots, b_d)$ of positive integers satisfying $b_1 \cdots b_d \leq x$ is $\ll_d x (\log x)^{d - 1}$ (a generalization of Dirichlet divisor problem), we get the upper bound $$M_d(x) \ll_d x^d (\log x)^{d(d-1)}.$$

In the special case $d = 2$, we have that $a_{12}, a_{21} \leq \min(x / a_{11}, x / a_{22})$ and consequently $$M_2(x) \leq \sum_{a_{11}, a_{22} \leq x} \min\left(\frac{x}{a_{11}}, \frac{x}{a_{22}}\right)^2 \ll \sum_{a_{11} \leq a_{22} \leq x} \left(\frac{x}{a_{22}}\right)^2 \ll x^2 \log x ,$$ which is a better upper bound than the general one given in the above paragraph. However, I have no idea of how to generalize this trick to $d \geq 3$ (if possible).

Has this problem been studied before? Do you have any idea/suggestion about it?

Answer 1

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).

Answer 2

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$.

Answer 3

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.