Here is an algorithm running in $\mathcal{O}(n\sqrt{n} + m\log m)$.
Let $w$ denote the function that for integer $t$, counts the number of pairs that their difference is $t$: $w(t)=\lvert\{(x,y): x\in A, y\in B, y-x=t\}\rvert$. If we had access to $w(t)$ we could simply find its maximum and see if it's $n$ or not $\max_t w(t)\le n$. The main idea is to estimate this function using the Fast Fourier transform. If the numbers are bounded it will produce the exact solution, otherwise, one can use modulus to a sufficiently big number and then verify the solutions once they're found.
Let $N,M>n,m$ be integers (to be defined later), and $u,v\in R^N$ be vectros defined as: $$u[i] = \lvert\{x\in A\colon M-x\equiv i \; (\text{mod }N) \}\rvert$$ $$v[i] = \lvert\{y\in B\colon M+y\equiv i \; (\text{mod }N) \}\rvert$$ Let $w=u * v$ denote the circular convolution of these two vectors. Then if there is such $k$ that: $$\forall x\in A\exists y\in B: y-x=k$$ Then we can conclude: $$ w[k\text{ mod } N]=\sum_{i: v[i]\neq 0} v[i] u[(i-k)\text{ mod } N]= n$$ Which by construction, is the maximum value that $w$ can attain. Therefore, we only need check if $\max_i w(i)=n$ or not. Then verify the correctness of the solution by checking the original elements. Computing $w$ can be done by FFT and inverse FFT in $N \log N$ time, and then finding the maximum element and verifying it takes $n$ steps, so overall $\mathcal{O}(N \log N)$ time and space.
If the numbers in both sets are bounded by $N$ this is an exact solution. But if you pick $N$ too small, $w(i)=n$ can happen only because of collisions. So we can verify all elements for all the indices that $w(i)\ge n$, but there might be several of them, but their number can be bounded. To have $\ell$ such indices, one must have at least $1+2+\dots + \ell$ collisions, which implies: $$P\left(\lvert\{i\colon w[i]\ge n\}\rvert \ge \ell\right) \le P\left(\text{# collisions}\ge (\ell+1)\ell/2\right)$$ There are $nm$ pairings of elements of $A$ and $B$. If we pick a prime number such that $N>2m$, and pick $M$ uniformly at random from $[N]$, the collision probability is bounded by $1/2m$, and by Markov: $$\le \frac{nm/N}{\ell^2/2}\le \frac{n}{\ell^2}$$ So with probability as close to $1$ as you want, $\ell=\mathcal{O}(\sqrt{n})$. Therefore, the overall time complexity of the algorithm is $$\mathcal{O}(n\sqrt{n} + m\log m)$$ in which $m\log m$ is the FFT and iFFT step (since we set $N=2m$), and $n \sqrt{n}$ is the verification step.
There are two ways I see to improve this:
- One can run the $\log n$ separate instances of the algorithm without the verification, and take the intersection of maximum indices that $w[i]\ge n$ (after shifting by $M$), and show that the number of shared collisions would drop by $1/2$ or some other constant every time, which would show a total running time of $\mathcal{O}(m\log^2 m)$
- One can construct a better hashing mechanism for $u$ and $v$ and use higher moments for Markov and make the concentration sharper.
Nevertheless, if you're looking for a practical solution this algorithm could work just fine. For instance, if elements of $A$ or $B$ are further away from an arithmetic progression, it will be less likely to have bigger values of $\ell$. Furthermore, you can stop the verification step can be stopped as soon as you find a mistake.