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 9 hours ago
-
$\\begingroup$ @IgorRivin I don't have any heuristic supporting such belief. $\\endgroup$ – Kate 9 hours ago
-
$\\begingroup$ It is obviously not far from sharp, since diagonal matrices give you $x^2.$ $\\endgroup$ – Igor Rivin 9 hours ago
-
$\\begingroup$ What happens when you take logarithms of the aij? Gerhard "Maybe Row-Sum Literature Will Help" Paseman, 2019.08.17. $\\endgroup$ – Gerhard Paseman 6 hours ago
-
$\\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 5 hours ago
2 Answers
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 5 hours ago
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$.
