Return to Answer

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. The main idea is to estimate $w$ 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$ be integers (to be defined later), and $u,v\in \mathbb{R}^N$ be vectors defined as $$u[i] = \lvert\{x\in A\colon M-x\equiv i \pmod N \}\rvert$$ $$v[i] = \lvert\{y\in B\colon M+y\equiv i \pmod N \}\rvert$$ Let $w=u * v$ denote the circular convolution of these two vectors. Then if there is $k$ such that $$\forall x\in A \exists y\in B: y-x=k,$$ then we can conclude $$ w[k \bmod N]=\sum_{i: v[i]\neq 0} v[i] u[i-k \bmod 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, we verify the correctness of the solution by checking the original elements. Computing $w$ can be done by FFT and inverse FFT in $\mathcal{O}(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 because of collisions. So we can verify all elements for all the indices that $w(i)\ge n$; 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[\lvert\{i\colon w[i]\ge n\}\rvert \ge \ell] \le P[\text{# collisions}\ge (\ell+1)\ell/2].$$ There are $nm$ pairings of elements of $A$ and $B$. If we pick a prime number $N$ such that $N>2m$, and pick $M$ uniformly at random from $\{1,\dots,N\}$, the collision probability is bounded by $1/2m$, so by Markov's inequality is $$\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:

1. 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)$
2. 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, the worst-case behavior $\ell\approx\sqrt{n}$ only occurs when the sets are nearly arithmetic progressions. If you pick elements nearly randomly, the guarantee will be much stronger. Furthermore, you can stop the verification step can be stopped as soon as you find a mistake.

Here is an algorithm running in $\mathcal{O}(n\sqrt{n} + m\log m)$ time.

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. The main idea is to estimate $w$ 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$ be integers (to be defined later), and $u,v\in \mathbb{R}^N$ be vectors defined as $$u[i] = \lvert\{x\in A\colon M-x\equiv i \pmod N \}\rvert$$ $$v[i] = \lvert\{y\in B\colon M+y\equiv i \pmod N \}\rvert$$ Let $w=u * v$ denote the circular convolution of these two vectors. Then if there is $k$ such that $$\forall x\in A \exists y\in B: y-x=k,$$ then we can conclude $$ w[k \bmod N]=\sum_{i: v[i]\neq 0} v[i] u[i-k \bmod 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, we verify the correctness of the solution by checking the original elements. Computing $w$ can be done by FFT and inverse FFT in $\mathcal{O}(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 because of collisions. So we can verify all elements for all the indices that $w(i)\ge n$; 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[\lvert\{i\colon w[i]\ge n\}\rvert \ge \ell] \le P[\text{# collisions}\ge (\ell+1)\ell/2].$$ There are $nm$ pairings of elements of $A$ and $B$. If we pick a prime number $N$ such that $N>2m$, and pick $M$ uniformly at random from $\{1,\dots,N\}$, the collision probability is bounded by $1/2m$, so by Markov's inequality is $$\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:

1. One can run $\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$). If one can show that the number of shared collisions drops by $1/2$ or some other constant every time, this would show a total running time of $\mathcal{O}(m\log^2 m)$.
2. 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, the worst-case behavior $\ell\approx\sqrt{n}$ only occurs when the sets are nearly arithmetic progressions. If you pick elements nearly randomly, the guarantee will be much stronger. Furthermore, you can stop the verification step as soon as you find a mistake.

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:

1. 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)$
2. 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, the worst-case behavior $\ell\approx\sqrt{n}$ only occurs when the sets are nearly arithmetic progressions. If you pick elements nearly randomly, the guarantee will be much stronger. Furthermore, you can stop the verification step can be stopped as soon as you find a mistake.

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. The main idea is to estimate $w$ 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$ be integers (to be defined later), and $u,v\in \mathbb{R}^N$ be vectors defined as $$u[i] = \lvert\{x\in A\colon M-x\equiv i \pmod N \}\rvert$$ $$v[i] = \lvert\{y\in B\colon M+y\equiv i \pmod N \}\rvert$$ Let $w=u * v$ denote the circular convolution of these two vectors. Then if there is $k$ such that $$\forall x\in A \exists y\in B: y-x=k,$$ then we can conclude $$ w[k \bmod N]=\sum_{i: v[i]\neq 0} v[i] u[i-k \bmod 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, we verify the correctness of the solution by checking the original elements. Computing $w$ can be done by FFT and inverse FFT in $\mathcal{O}(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 because of collisions. So we can verify all elements for all the indices that $w(i)\ge n$; 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[\lvert\{i\colon w[i]\ge n\}\rvert \ge \ell] \le P[\text{# collisions}\ge (\ell+1)\ell/2].$$ There are $nm$ pairings of elements of $A$ and $B$. If we pick a prime number $N$ such that $N>2m$, and pick $M$ uniformly at random from $\{1,\dots,N\}$, the collision probability is bounded by $1/2m$, so by Markov's inequality is $$\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:

1. 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)$
2. 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, the worst-case behavior $\ell\approx\sqrt{n}$ only occurs when the sets are nearly arithmetic progressions. If you pick elements nearly randomly, the guarantee will be much stronger. Furthermore, you can stop the verification step can be stopped as soon as you find a mistake.

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:

1. 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)$
2. 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.

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:

1. 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)$
2. 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, the worst-case behavior $\ell\approx\sqrt{n}$ only occurs when the sets are nearly arithmetic progressions. If you pick elements nearly randomly, the guarantee will be much stronger. Furthermore, you can stop the verification step can be stopped as soon as you find a mistake.