Multiplicative version of 3-SUM

Question

What is known about the time complexity of the following problem, which we call 3-MUL?

Given a set $S$ of $n$ integers, are there elements $a,b,c\in S$ such that $ab=c$?

This problem is similar to the 3-SUM problem, which asks whether there are three elements $a,b,c\in S$ such that $a+b+c=0$ (or equivalently $a+b=c$). 3-SUM is conjectured to require roughly quadratic time in $n$. Is there a similar conjecture for 3-MUL? Specifically is 3-MUL known to be 3-SUM hard?

Note, the time complexity should apply in a "reasonable" model of computation. For instance, we could reduce from 3-SUM on a set $S$ to 3-MUL on set the $S'$, where $S'=\{2^x\mid x\in S\}$. Then a solution to 3-MUL, $2^a\cdot 2^b=2^c$, exists if and only if $a+b=c$. However, this exponential blow-up of the numbers scales very badly with various models, like the RAM model for example.

Answer 1

Your reduction from $3$SUM to $3$MUL works with a minor standard modification. Suppose your original integers were in {$1,\ldots,M$}. After the transformation $x\rightarrow 2^x$ the new integers are in {$2,\ldots,2^M$}. We will reduce the range.

Consider any triple of integers $a,b,c$ in the new set $S'$. The number of prime divisors of any nonzero $ab-c$ is $<2M$. The number of such triples is $n^3$. Hence the number of primes $q$ which divide at least one of the $ab-c$ nonzero numbers is at most $2Mn^3$.

Let $P$ be the set of the first $2M\cdot n^4$ primes. The largest such prime is of size at most $O(Mn^4\log Mn)$. Pick a random prime $p\in P$. With high probability $p$ will not divide any of the nonzero $ab-c$, so we can represent each $a\in S'$ by its residue, mod $p$, and if $3$MUL finds some $ab=c$ in $S'$, with high probability it will be correct for the original $3$SUM instance. We have reduced the range of the numbers to {$0,\ldots, O(Mn^4\log Mn)$}.

(This is a standard size reduction. You might be able to do better by considering the fact that the $ab-c$ are always differences of two powers of $2$.)

Answer 2

Have you tried the reduction $S'=\{2^{x/M}|x\in S\}$ where $M=\max S− \min S$? The results are real numbers so you'd have to round to some number of digits. To ensure that the numbers add correctly despite the rounding you may need to add a bit of random noise.