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?

  • $\begingroup$ Do you believe the $2\times 2$ bound is sharp? $\endgroup$ – Igor Rivin Aug 17 '19 at 14:03
  • $\begingroup$ @IgorRivin I don't have any heuristic supporting such belief. $\endgroup$ – Kate Aug 17 '19 at 14:23
  • $\begingroup$ It is obviously not far from sharp, since diagonal matrices give you $x^2.$ $\endgroup$ – Igor Rivin Aug 17 '19 at 14:34
  • $\begingroup$ What happens when you take logarithms of the aij? Gerhard "Maybe Row-Sum Literature Will Help" Paseman, 2019.08.17. $\endgroup$ – Gerhard Paseman Aug 17 '19 at 17:14
  • $\begingroup$ @GerhardPaseman I think logarithms do not help very much. They turn the problem from multiplicative to additive, but the variables are not integers anymore, making things much more difficult... $\endgroup$ – Kate Aug 17 '19 at 17:56

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

  • 1
    $\begingroup$ Thank you very much! $\endgroup$ – Kate Aug 17 '19 at 17:57

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.

  • $\begingroup$ @Lucia: I fixed my original argument (which is not the one I posted here earlier). $\endgroup$ – GH from MO Aug 18 '19 at 1:58
  • 2
    $\begingroup$ Hi GH: Looks good! $\endgroup$ – Lucia Aug 18 '19 at 2:29
  • $\begingroup$ @Lucia: Thanks! Of course it is standard, but I felt bad about my mistake earlier. $\endgroup$ – GH from MO Aug 18 '19 at 2:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.