<p>Probably OP's problem has no sub-quadratic algorithm, as it is <a href="https://en.wikipedia.org/wiki/3SUM" rel="noreferrer">3-SUM-hard</a>, per [1]:</p>
<blockquote>
<p><strong>Corollary 1.2 [1].</strong> <em>Under the 3-SUM hypothesis, for all <span class="math-container">$\delta &gt; 0$</span>, determining whether a given set of <span class="math-container">$n$</span> integers ... is a Sidon set requires <span class="math-container">$n^{2-o(1)}$</span> time.</em></p>
</blockquote>
<p>The ``3-SUM hypothesis'' is that there is no sub-quadratic algorithm for 3-SUM, meaning one running in time <span class="math-container">$O(n^\delta)$</span>-time for some constant <span class="math-container">$\delta &lt; 2.$</span></p>
<p>By the above corollary, showing that OP's problem has a sub-quadratic algorithm would falsify the 3-SUM hypothesis.
This is considered unlikely
because it would imply (by known reductions)
sub-quadratic algorithms for many well-studied problems
for which sub-quadratic algorithms have never been found.</p>
<p>Note that this doesn't rule out algorithms running (just barely) in time <span class="math-container">$o(n^2)$</span> (e.g. in time <span class="math-container">$O(n^2 \textsf{polyloglog}(n)/\log n)$</span>).
Indeed, the wikipedia entry linked to above
cites a couple of such algorithms for 3-SUM.
So, technically, OP's problem probably has an algorithm
that runs faster than brute force.
But not by much,
and I don't know whether any such algorithm
is likely to be faster in practice.</p>
<hr />
<p>Handwaving a little, it also seems plausible that
there may be a relatively easy direct reduction
from the <em>4-SUM</em> problem to OP's problem,
starting perhaps with something along the lines
of the proof of Theorem 3.2 in [2],
which suggests that, when reducing to or from <span class="math-container">$k$</span>-SUM,</p>
<blockquote>
<p>WLOG, we may assume that the instance of <span class="math-container">$k$</span>-SUM has <span class="math-container">$k$</span> parts, where we want to pick exactly one number from each part such that the <span class="math-container">$k$</span> numbers sum to zero.</p>
</blockquote>
<p>In the corresponding variant of OP's problem,
four parts <span class="math-container">$(W, X, Y, Z)$</span> are given,
and the question is whether there is <span class="math-container">$(w, x, y, z)\in W\times X\times Y\times Z$</span> such that <span class="math-container">$w + x = y + z$</span>.
This problem is equivalent to the 4-part variant of 4-SUM
simply by negating the entries in <span class="math-container">$Y$</span> and <span class="math-container">$Z.$</span></p>
<p>Note that 4-SUM is probably not (much) harder than 3-SUM,
as 4-SUM also admits an <span class="math-container">$O(n^2)$</span>-time algorithm.</p>
<hr />
<p>[1] Ce Jin and Yinzhan Xu. 2023. Removing Additive Structure in 3SUM-Based Reductions. In STOC 2023, 405–418. <a href="https://doi.org/10.1145/3564246.3585157" rel="noreferrer">https://doi.org/10.1145/3564246.3585157</a></p>
<p>[2] Williams and Williams. 2022. Fixed-Parameter and Fine-Grained Complexity, lecture notes for Lecture 9 of MIT 6.1420/6.S974. <a href="https://web.archive.org/web/20240214020338/https://people.csail.mit.edu/virgi/6.1420/lecture9.pdf" rel="noreferrer">Cached copy on Internet Archive</a></p>

CC BY-SA 4.0
2024-02-14T01:49:18.337Z
2024-02-14T02:25:14.463Z
2024-02-14T02:25:14.463Z
Neal Young
<p>In what range are the values in your set <span class="math-container">$S$</span>?</p>
<p>Note that if the range is not too large you can represent <span class="math-container">$S$</span> by a polynomial <span class="math-container">$P_S$</span> (<span class="math-container">$P_S = \sum_{s \in S} x^s$</span>) and compute <span class="math-container">$P_S^{2}$</span> with the FFT algorithm, which should tell you about how many ways there are to achieve a value as a sum of two elements. In particular, <span class="math-container">$S$</span> is Sidon if and only if no coefficient of <span class="math-container">$P_S^2$</span> is greater than <span class="math-container">$2^{^{*}}$</span>. This approach would run in <span class="math-container">$O(\max(S) \lg \max(S) + |S|)$</span>.</p>
<p><span class="math-container">$[*]$</span> We need to keep the trivial solution in mind!</p>

CC BY-SA 4.0
2024-02-12T19:43:35.157Z
If $max(S)$ is less than $n(n-1)/4$ then by pigeonhole the set is not Sidon. So in the range where the problem isn't trivial this approach wouldn't beat quadratic time.
Tassle
CC BY-SA 4.0
2024-02-13T15:07:38.750Z
Good point! wondering if I should delete the answer now.
Bernardo Subercaseaux
CC BY-SA 4.0
2024-02-13T17:18:21.670Z
The set I specifically have in mind contains _really_ large integers... But, as pointed out by Neal, your answer still looks quite interesting (+1)!
Sayan Dutta
CC BY-SA 4.0
2024-02-13T19:20:01.877Z
(i) See the related comment about 3-SUM in its [wikipedia page](https://en.wikipedia.org/wiki/3SUM): *"When the elements are integers in the range $[-N, N]$ 3SUM can be solved in 
$O(n+N\log N)$ time by representing the input set $S$ as a bit vector, computing the set $S+S$ of all pairwise sums as a discrete convolution using the fast Fourier transform, and finally comparing this set to $S$."*  (ii) Per the same page, there are 3-SUM algorithms with run time (slightly) $o(n^2)$.  (iii) I think this answer is interesting (even if the alg is too slow).  I vote to keep it.
Neal Young
CC BY-SA 4.0
2024-02-12T17:44:11.510Z
2024-02-16T01:24:05.260Z
2024-02-16T01:24:05.260Z
Bernardo Subercaseaux
<p>We call a set of natural numbers <span class="math-container">$\mathcal S$</span> to be a <a href="https://en.wikipedia.org/wiki/Sidon_sequence" rel="nofollow noreferrer"><em>Sidon Set</em></a> if <span class="math-container">$a+b=c+d$</span> for <span class="math-container">$a,b,c,d\in \mathcal S$</span> implies <span class="math-container">$\{a,b\}=\{c,d\}$</span>. In other words, all pairwise sums are distinct.</p>
<p>What algorithms do we know of (better that brute force) to check whether a given set is a Sidon set or not? Notice that the brute force algorithms checks through all the sums and hence takes about <span class="math-container">$n^2$</span> operations for an <span class="math-container">$n$</span> element set.</p>
<hr />
<p>Taking suggestions from @mathworker21, I tried to count the cardinality of the set <span class="math-container">$\{(s_1,s_2,s_3,s_4) \in S^4 : s_1+s_2 = s_3+s_4\}$</span> by approximating the integral
<span class="math-container">$$\int_0^1 \left\lvert \sum_{s\in \mathcal S} e^{2\pi i s\theta}\right\rvert^4 \text{d}\theta$$</span>
using Monte-Carlo. Here's the approach I tried :-</p>
<pre><code>def integrand(theta, S):
    return np.abs(np.sum(np.exp(1j * np.pi * np.array(S) * theta))**4)

def monte_carlo_integration(S, num_samples=100000):
    np.random.seed(42)  # Set a seed for reproducibility
    samples = np.random.uniform(0, 1, num_samples)
    values = [integrand(theta, S) for theta in samples]
    integral_approximation = np.mean(values)
    return integral_approximation
</code></pre>
<p>The problem with this is that the error term in the approximation is increasing rapidly with the cardinality of <span class="math-container">$\mathcal S$</span> increasing. To get even a decent approximation for large cardinality of <span class="math-container">$\mathcal S$</span>, I have to keep increasing the value of <code>num_samples</code> which is slowing down the algorithm drastically.</p>
<p>I also tried other methods to approximate the integral like using Adaptive quadrature or Gauss–Kronrod quadrature formula. But, the theme persists - to get even a decent accuracy, these methods are taking much more time than the brute force method!</p>
<p>So, can anyone give me some information on the size of the error term? Is it possible to improve the algorithm by adding an approximation of the error term to the integral? Please let me know.</p>
<hr />
<p>Alternatively, does anyone have any other ideas?</p>

CC BY-SA 4.0
2024-01-31T13:00:30.540Z
It seems to me that the 4-sum problem is reducible to this problem.
Yoshio Okamoto
CC BY-SA 4.0
2024-01-31T15:43:19.987Z
@YoshioOkamoto I can't see why you think so - you may have 4 elements summing up to a given sum $S$ without having two that sum up to $S/2$
Sayan Dutta
CC BY-SA 4.0
2024-02-01T15:18:23.843Z
Maybe approximate $\int_0^1 | \sum_{s \in S} e(s\theta) |^4 d\theta$ by Monte-Carlo?
mathworker21
CC BY-SA 4.0
2024-02-01T19:00:54.533Z
@SayanDutta Yes, $e(t) := e^{2\pi i t}$. Also, for any set $S$, it holds that $$\int_0^1 \left|\sum_{s \in S} e(s\theta)\right|^4 d\theta = \#\{(s_1,s_2,s_3,s_4) \in S^4 : s_1+s_2 = s_3+s_4\}.$$ For $|S|$ of a given size, the above is minimized exactly when $S$ is a Sidon set, in which case it is equal to ... (you can figure this out).
mathworker21
CC BY-SA 4.0
2024-02-02T08:21:33.120Z
@mathworker21 yes, that's actually a very nice idea! Thanks!
Sayan Dutta
CC BY-SA 4.0
2024-02-10T14:53:06.520Z
@SayanDutta Yea, the idea probably won't work. To get a sense of the integral near $\theta = 0$, you'd probably need asymptotically more than $n$ test points (near $\theta = 0$).
mathworker21
CC BY-SA 4.0
2024-02-10T19:06:35.953Z
@mathworker21 even using other methods to approximate the integral doesn't seem to work - to get even a decent accuracy, these methods are taking much more time than the brute force method!
Sayan Dutta
CC BY-SA 4.0
2024-02-11T16:26:59.753Z
*"Notice that the brute force algorithms checks through all the sums and hence takes about n^2 operations for an n element set."* << That's awfully pessimistic; for most non-Sidon sets, I expect the check to fail on the very first two pairs examined. Have you been able to construct a family of non-Sidon sets for which the bruteforce method grows linearly with the size of the set?
Stef
CC BY-SA 4.0
2024-02-11T21:17:18.927Z
In the $4$-linear decision tree model of computation, $\Theta(n^2)$ runtime is optimal (see Jeff Erickson: Lower bounds for linear satisfiability problems). This is a somewhat weak model of computation, but it is very natural for the problem at hand. This at least hints at the fact that you probably need a decent amount of cleverness to beat quadratic runtime in the worst-case.
Tassle
<ds.algorithms><co.combinatorics><nt.number-theory><comp-number-theory><extremal-combinatorics>
Algorithm to check whether a given set is Sidon
Sayan Dutta
# Algorithm to check whether a given set is Sidon

(Asked by: username_0 on 2024-01-31)

We call a set of natural numbers $\mathcal S$ to be a Sidon Set if $a+b=c+d$ for $a,b,c,d\in \mathcal S$ implies $\{a,b\}=\{c,d\}$. In other words, all pairwise sums are distinct.
What algorithms do we know of (better that brute force) to check whether a given set is a Sidon set or not? Notice that the brute force algorithms checks through all the sums and hence takes about $n^2$ operations for an $n$ element set.

Taking suggestions from @username_2, I tried to count the cardinality of the set $\{(s_1,s_2,s_3,s_4) \in S^4 : s_1+s_2 = s_3+s_4\}$ by approximating the integral
$$\int_0^1 \left\lvert \sum_{s\in \mathcal S} e^{2\pi i s\theta}\right\rvert^4 \text{d}\theta$$
using Monte-Carlo. Here's the approach I tried :-
def integrand(theta, S):
    return np.abs(np.sum(np.exp(1j * np.pi * np.array(S) * theta))**4)

def monte_carlo_integration(S, num_samples=100000):
    np.random.seed(42)  # Set a seed for reproducibility
    samples = np.random.uniform(0, 1, num_samples)
    values = [integrand(theta, S) for theta in samples]
    integral_approximation = np.mean(values)
    return integral_approximation

The problem with this is that the error term in the approximation is increasing rapidly with the cardinality of $\mathcal S$ increasing. To get even a decent approximation for large cardinality of $\mathcal S$, I have to keep increasing the value of num_samples which is slowing down the algorithm drastically.
I also tried other methods to approximate the integral like using Adaptive quadrature or Gauss–Kronrod quadrature formula. But, the theme persists - to get even a decent accuracy, these methods are taking much more time than the brute force method!
So, can anyone give me some information on the size of the error term? Is it possible to improve the algorithm by adding an approximation of the error term to the integral? Please let me know.

Alternatively, does anyone have any other ideas?

**Tags:** ds.algorithms, co.combinatorics, nt.number-theory, comp-number-theory, extremal-combinatorics

> **Comments:**
> **username_1**: It seems to me that the 4-sum problem is reducible to this problem.  
> **username_0**: @YoshioOkamoto I can't see why you think so - you may have 4 elements summing up to a given sum $S$ without having two that sum up to $S/2$  
> **username_2**: Maybe approximate $\int_0^1 | \sum_{s \in S} e(s\theta) |^4 d\theta$ by Monte-Carlo?  
> **username_2**: @SayanDutta Yes, $e(t) := e^{2\pi i t}$. Also, for any set $S$, it holds that $$\int_0^1 \left|\sum_{s \in S} e(s\theta)\right|^4 d\theta = \#\{(s_1,s_2,s_3,s_4) \in S^4 : s_1+s_2 = s_3+s_4\}.$$ For $|S|$ of a given size, the above is minimized exactly when $S$ is a Sidon set, in which case it is equal to ... (you can figure this out).  
> **username_0**: @username_2 yes, that's actually a very nice idea! Thanks!  
> **username_2**: @SayanDutta Yea, the idea probably won't work. To get a sense of the integral near $\theta = 0$, you'd probably need asymptotically more than $n$ test points (near $\theta = 0$).  
> **username_0**: @username_2 even using other methods to approximate the integral doesn't seem to work - to get even a decent accuracy, these methods are taking much more time than the brute force method!  
> **username_3**: *"Notice that the brute force algorithms checks through all the sums and hence takes about n^2 operations for an n element set."* << That's awfully pessimistic; for most non-Sidon sets, I expect the check to fail on the very first two pairs examined. Have you been able to construct a family of non-Sidon sets for which the bruteforce method grows linearly with the size of the set?  
> **username_4**: In the $4$-linear decision tree model of computation, $\Theta(n^2)$ runtime is optimal (see Jeff Erickson: Lower bounds for linear satisfiability problems). This is a somewhat weak model of computation, but it is very natural for the problem at hand. This at least hints at the fact that you probably need a decent amount of cleverness to beat quadratic runtime in the worst-case.  

---

## 2 answers

### Answer by username_5 on 2024-02-14. Score: 8

Probably OP's problem has no sub-quadratic algorithm, as it is [3-SUM-hard](https://en.wikipedia.org/wiki/3SUM), per [1]:

> **Corollary 1.2 [1].** *Under the 3-SUM hypothesis, for all $\delta > 0$, determining whether a given set of $n$ integers ... is a Sidon set requires $n^{2-o(1)}$ time.*

The ``3-SUM hypothesis'' is that there is no sub-quadratic algorithm for 3-SUM, meaning one running in time $O(n^\delta)$-time for some constant $\delta < 2.$

By the above corollary, showing that OP's problem has a sub-quadratic algorithm would falsify the 3-SUM hypothesis.
This is considered unlikely
because it would imply (by known reductions)
sub-quadratic algorithms for many well-studied problems
for which sub-quadratic algorithms have never been found.

Note that this doesn't rule out algorithms running (just barely) in time $o(n^2)$ (e.g. in time $O(n^2 \textsf{polyloglog}(n)/\log n)$).
Indeed, the wikipedia entry linked to above
cites a couple of such algorithms for 3-SUM.
So, technically, OP's problem probably has an algorithm
that runs faster than brute force.
But not by much,
and I don't know whether any such algorithm
is likely to be faster in practice.

---

Handwaving a little, it also seems plausible that
there may be a relatively easy direct reduction
from the *4-SUM* problem to OP's problem,
starting perhaps with something along the lines
of the proof of Theorem 3.2 in [2],
which suggests that, when reducing to or from $k$-SUM,

> WLOG, we may assume that the instance of $k$-SUM has $k$ parts, where we want to pick exactly one number from each part such that the $k$ numbers sum to zero.

In the corresponding variant of OP's problem,
four parts $(W, X, Y, Z)$ are given,
and the question is whether there is $(w, x, y, z)\in W\times X\times Y\times Z$ such that $w + x = y + z$.
This problem is equivalent to the 4-part variant of 4-SUM
simply by negating the entries in $Y$ and $Z.$

Note that 4-SUM is probably not (much) harder than 3-SUM,
as 4-SUM also admits an $O(n^2)$-time algorithm.

---

[1] Ce Jin and Yinzhan Xu. 2023. Removing Additive Structure in 3SUM-Based Reductions. In STOC 2023, 405–418. <https://doi.org/10.1145/3564246.3585157>

[2] Williams and Williams. 2022. Fixed-Parameter and Fine-Grained Complexity, lecture notes for Lecture 9 of MIT 6.1420/6.S974. [Cached copy on Internet Archive](https://web.archive.org/web/20240214020338/https://people.csail.mit.edu/virgi/6.1420/lecture9.pdf)


---

### Answer by username_6 on 2024-02-12. Score: 4

In what range are the values in your set $S$?

Note that if the range is not too large you can represent $S$ by a polynomial $P\_S$ ($P\_S = \sum\_{s \in S} x^s$) and compute $P\_S^{2}$ with the FFT algorithm, which should tell you about how many ways there are to achieve a value as a sum of two elements. In particular, $S$ is Sidon if and only if no coefficient of $P\_S^2$ is greater than $2^{^{\*}}$. This approach would run in $O(\max(S) \lg \max(S) + |S|)$.

$[\*]$ We need to keep the trivial solution in mind!

> **Comments:**
> **username_4**: If $max(S)$ is less than $n(n-1)/4$ then by pigeonhole the set is not Sidon. So in the range where the problem isn't trivial this approach wouldn't beat quadratic time.  
> **username_6**: Good point! wondering if I should delete the answer now.  
> **username_0**: The set I specifically have in mind contains _really_ large integers... But, as pointed out by Neal, your answer still looks quite interesting (+1)!  
> **username_5**: (i) See the related comment about 3-SUM in its [wikipedia page](https://en.wikipedia.org/wiki/3SUM): *"When the elements are integers in the range $[-N, N]$ 3SUM can be solved in  $O(n+N\log N)$ time by representing the input set $S$ as a bit vector, computing the set $S+S$ of all pairwise sums as a discrete convolution using the fast Fourier transform, and finally comparing this set to $S$."*  (ii) Per the same page, there are 3-SUM algorithms with run time (slightly) $o(n^2)$.  (iii) I think this answer is interesting (even if the alg is too slow).  I vote to keep it.  

---

