Denote $m = \lfloor \log_{2} n \rfloor +1. $ Let on the contrary assume that $|A| \geq m,\, |B| \geq m $. Choose some $a_i \in A, \, b_i \in B,\, i=1,2, \ldots,m,\, a_1 < a_2 <\ldots < a_m,\, b_1 < b_2 <\ldots < b_m$. According to the problem's hypothesis $a_ib_i +1= r_i^2,\, r_i \in \mathbb{N}$. We also have $2 \leq r_1 < r_2 < \ldots < r_m \leq n$. It is easy to see that there exists $i,\, 1 \leq i \leq m-1$, such that $r_i < r_{i+1} \leq 2 r_i$. This is a key part and it is why $\log_2 n$ stands for. Let assume, for simplicity of the wording, that $i=1$ i.e. (1) $r_1 < r_2 \leq 2r_1$. We have: (2) $a_1 b_1 = r_1^2-1 $ $a_2 b_2 = r_2^2-1 $. Also holds: (3) $a_1 b_2 = s_1^2-1 $ $a_2 b_1 = s_2^2 -1 $ for some $s_1,s_2 \in \mathbb{N}$ for which $r_1 < s_1,\, s_2 < r_2$ (2) and (3) yield: (4) $r_1^2r_2^2-r_1^2-r_2^2 = s_1^2s_2^2 - s_1^2 - s_2^2 $ $r_1 <s_1,\, s_2 < r_2 \leq 2r_1 $ The main idea is to show that if (4) holds then $\{r_1,r_2\} = \{s_1,s_2\}$, which is impossible. Let first assume $s_1 s_2 < r_1 r_2$, so $s_1s_2 = r_1r_2 - k,\, k \geq 1$. Then we have: $s_1^2s_2^2 - s_1^2 - s_2^2 < r_1^2 r_2^2 - 2kr_1 r_2 + k^2 - \frac{r_1r_2-k}{2}=$ $ = r_1^2r_2^2 - 2r_1r_2 - \frac{r_1r_2}{2} - \left( 2(k-1)r_1 r_2 - k^2 + \frac{k}{2} \right) $. $r_1^2r_2^2-r_1^2-r_2^2 > r_1^2r_2^2 - 2r_1r_2 - \frac{r_1r_2}{2} $ It is easy to see that it is impossible when $k\geq 1$. The case $s_1 s_2 > r_1 r_2$ can be treated in a similar way. Therefore, the only possible case is $s_1 s_2 = r_1 r_2 $ and thus: $r_1^2+ r_2^2 = s_1^2 + s_2^2$. Now we use some properties of the function $x^2 + \frac{a^2}{x^2}$ to conclude that $\{r_1,r_2\} = \{s_1,s_2\}$, so (4) is impossible.

Other solution, maybe not nice Let $\mid A\mid =a, \mid B \mid =b$ If a=1 we are done. If $a\geq 2$ let x,y are elements in A and $y_{1},y_{2},..., y_{b}$ are all elements in B. Each i<b+1 we have $u_{i},v_{i}$ such that: $y(u_{i}^{2}-1)=x(v_{i}^{2}-1)$(*) All solution of equation(*) $u_{k+1}=m_{k+1}u_{0}+xv_{0}r_{k+1} ,v_{k+1}=m_{k+1}v_{0}+yu_{0}r_{k+1}$ $m_{k+1},r_{k+1}$ are roots of $m^2-xy.r^2=1$ easy to see that: $m_{k+1}\geq 2. m_{k}$ $r_{k+1}\geq 2r_{k}$ Then $u_{k+1}\geq. 2u_{k}$ then $n\geq u_{b}\geq 2^{b}$ Hence we are done

dgrozev wrote: The main idea is to show that if (4) holds then $\{r_1,r_2\} = \{s_1,s_2\}$, which is impossible. Let’s write this part more clearly: we assert that if different pairs of positive integers $(x,y)$ and $(z,w)$ satisfy \[2\leq x\leq y\leq\frac{3+\sqrt{5}}{2}x,2\leq z\leq w\leq\frac{3+\sqrt{5}}{2}z,\]then $(x^2-1)(y^2-1)\neq(z^2-1)(w^2-1)$. Since if the equality holds, then we’ll have \[(xy)^2-3xy+1\leq(x^2-1)(y^2-1)=(z^2-1)(w^2-1)\leq(zw-1)^2,\]i.e. $xy(xy-3)\leq zw(zw-2)$. As $xy,zw$ are integers greater than $3$ it follows that $xy\leq zw$, while symmetrically we’ll also have $xy\geq zw$, so $xy=zw$, which contradicts that $(x,y)\neq(z,w)$. As a corollary, the upper bound of $\min\{|A|,|B|\}$ can be improved to $\lceil\log_{\frac{3+\sqrt{5}}{2}}{\frac{n-1}{2}}\rceil$ (though it seems there should exist a uniform bound).