10
$\begingroup$

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 @mathworker21, 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?

$\endgroup$
12
  • 2
    $\begingroup$ It seems to me that the 4-sum problem is reducible to this problem. $\endgroup$ Jan 31 at 13:00
  • 2
    $\begingroup$ @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$ $\endgroup$ Jan 31 at 15:43
  • 2
    $\begingroup$ Maybe approximate $\int_0^1 | \sum_{s \in S} e(s\theta) |^4 d\theta$ by Monte-Carlo? $\endgroup$ Feb 1 at 15:18
  • 3
    $\begingroup$ @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). $\endgroup$ Feb 1 at 19:00
  • 4
    $\begingroup$ 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. $\endgroup$
    – Tassle
    Feb 11 at 21:17

2 Answers 2

8
$\begingroup$

Probably OP's problem has no sub-quadratic algorithm, as it is 3-SUM-hard, 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

$\endgroup$
4
$\begingroup$

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!

$\endgroup$
4
  • 5
    $\begingroup$ 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. $\endgroup$
    – Tassle
    Feb 12 at 19:43
  • $\begingroup$ Good point! wondering if I should delete the answer now. $\endgroup$ Feb 13 at 15:07
  • 1
    $\begingroup$ The set I specifically have in mind contains really large integers... But, as pointed out by Neal, your answer still looks quite interesting (+1)! $\endgroup$ Feb 13 at 17:18
  • 1
    $\begingroup$ (i) See the related comment about 3-SUM in its wikipedia page: "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. $\endgroup$
    – Neal Young
    Feb 13 at 19:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.