3
$\begingroup$

Let $A_{a,b}$=$\{pq:p\leq a,q\leq b\}$, where $ab=n^2$ and $n^2$ is fixed.

How large is $A_{a,b}$? Does $A_{a,b}$ attain its lower value when $a=b=n$?

The case when $a=b=n$ is settled by Ford, and a stronger conjecture by Erdos is asking if $|M(G)|\geq |M(K_{n,n})|$ in general for all bipartite $G$ such that $e(G)=n^2$. Yet is there any development about the above weaker problem?

$\endgroup$
11
  • 2
    $\begingroup$ Your notation is confusing. Are $a,b$ fixed, or can they vary here? Also is $n$ in the index of $A_n$ the same as the one appearing in $mn$? $\endgroup$
    – Wojowu
    Jun 21, 2021 at 13:00
  • $\begingroup$ @Wojowu Thx I've edited my notation $\endgroup$
    – x100c
    Jun 21, 2021 at 13:12
  • $\begingroup$ Is the $n$ in $mn$ the same one as the one in $ab=n^2$? $\endgroup$
    – Wojowu
    Jun 21, 2021 at 13:16
  • 2
    $\begingroup$ I think OP is asking if, given $n$, the lowest value in $\{|A_{a,b}\;|\; ab=n^2\}$ is attained at $|A_{n,n}|$. I checked that this is so if $1\le a\le b \le 1000$. $\endgroup$ Jun 21, 2021 at 14:40
  • 1
    $\begingroup$ The closest two pairs whose product is a square can be is for $(n(n+1),n(n+1))$ and $(n^2,(n+1)^2)$. In this case Legendre's conjecture easily implies $A_{n^2,(n+1)^2}>A_{n(n+1),n(n+1)}$. Some more mileage can be got out of this approach and I wonder if maybe it can be used to fully answer the OP's question. $\endgroup$ Jun 23, 2021 at 12:08

1 Answer 1

4
$\begingroup$

Ford's methods provide lower bounds for this "asymmetric" multiplication table problem that match the lower bounds for the standard multiplication table problem.

Define $H(x,y,z) := \#\{n \le x : \exists d \in (y,z] \text{ with } d \mid n\}$. Ford proved that $$H(x,y,cy) \asymp \frac{x}{(\log Y)^\delta (\log\log Y)^{2/3}}$$ whenever $c>1$ and $\frac{1}{c-1} \le y \le \frac{x}{c}$, where $Y := \min(y,x/y)+3$.

Now take $a \ge 1$ and consider $|[a]\cdot [n^2/a]|$, which is $|A_{a,n^2/a}|$ in your notation. If $a \le 4$ or $a \ge n^2/4$, then clearly $|[a]\cdot[n^2/a]| = \Omega(n^2)$, so we may assume otherwise. We claim $$\left|[a]\cdot[\frac{n^2}{a}]\right| \ge H(\frac{n^2}{4},\frac{a}{4},\frac{a}{2}).$$ Indeed, if $b \le n^2/4$ has some $d \in (a/4,a/2]$ with $d \mid b$, then $b/d \le (n^2/4)/(a/4) = n^2/a$, so $b = d\cdot \frac{b}{d} \in [a]\cdot[n^2/a]$. Therefore, using $x = n^2/4, y = a/4, c=2$, we obtain $$\left|[a]\cdot[\frac{n^2}{a}]\right| \gg \frac{n^2/4}{(\log Y)^\delta(\log\log Y)^{2/3}},$$ where $Y = \min(a/4,n^2/a)+3$. Since $Y \le n^2$, $\log Y \ge 2\log n$, so we obtain the desired result $$\left|[a]\cdot[\frac{n^2}{a}]\right| \ge c'\frac{n^2}{(\log n)^\delta (\log\log n)^{2/3}}$$ for some absolute $c' > 0$.

$\endgroup$
1
  • 1
    $\begingroup$ Using Theorem 1(v) of Ford's "The distribution of integers with a divisor in a given interval" combined with the argument in Corollary 3 in said paper, it seems that the order of magnitude of $|[a] \cdot [n^2/a]|$ is $n^2 (\log m)^{-\delta} (\log \log m)^{-2/3}$ where $m = \min\{a,n^2/a\}$. $\endgroup$ Jun 21, 2021 at 20:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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