Given a subset $E\subset \mathbb N\setminus \{0\}$ of integers, we say that $E$ is independent if for any choice of $k\in \mathbb N$, $\epsilon_i\in\{-1,0,1\}$ for $i=1,\dots,k$, if $\Sigma_{i=1}^k\epsilon_in_i=0$ for $n_i\in E$, then $\epsilon_i=0$ for any $i$.

My Question is the following. Is the set $\{5^n3^m\}_{n,m\in \mathbb N}$ a finite union of independent sets? (one can take any two primes $p,q\neq 2$.

Moreover, is this set a Sidon set? (Sidon sets are the following - the definition from: Rudin, Walter, Trigonometric series with gaps, J. Math. Mech. 9, 203-227 (1960); DOI: 10.1512/iumj.1960.9.59013, jstor. ZBL0091.05802, MR116177.)

(b) A set $E$ is said to be a Sidon set if there is a finite constant $B$ such that $$\sum_{-\infty}^\infty |\hat{f}(n)| \le B \|f\|_\infty$$ for every $E$-polynomial $f$.

where $\hat{f}(n)$ is the $n$'th Fourier coefficient of $f$.


  • $\begingroup$ I had just worked out that $\{2^n3^m\}$ is not independent (since $3+6+9 = 18$) when you edited the question. $\endgroup$ May 30, 2021 at 17:01
  • 1
    $\begingroup$ Also $1+3+5-3^2=0$. $\endgroup$
    – GH from MO
    May 30, 2021 at 17:02
  • $\begingroup$ Thanks. I am modifying the question a bit more now, to so that it will ask whether this set is Sidon. $\endgroup$ May 30, 2021 at 17:06

3 Answers 3


It was proved by Pisier (Arithmetic characterizations of Sidon sets) that a set $\Lambda \subset \mathbf{Z}$ is Sidon if and only if there is a constant $c$ such that any finite subset $A \subset \Lambda$ contains an independent set $B$ of cardinality $\ge c|A|$. Together with Fedor Petrov's answer, this implies that, in a Sidon set, the number of elements in $[0,x]$ is $O(\log x)$. In particular, $\{3^n 5^m\}_{n,m}$ is not Sidon.


No, it is not.

By pigeonhole principle, an independent set $E$ has $O(\log x) $ elements not exceeding $x$: otherwise two subsets have equal sums (since there are $2^{|E\cap [1,x]|}$ subsets, and only at most $x^2$ possible sums), and the difference of these two sums gives a vanishing linear combination of elements of $E$ with coefficients $0,1,-1$.

Thus the same holds for a finite union of independent sets. But the set $\{5^n3^m\}$ has at least ${\rm const}\cdot (\log x)^2$ elements not exceeding $x$ (choose arbitrary $n,m$ between 1 and $\log x/10000$).

  • $\begingroup$ Thanks. Does it mean also that the set is not Sidon? by what I understand, Sidon sets are finite unions of something called "$k$ independent sets", where one only requires that there are no trivial sums of $k$ elements (I believe this is a result by Bourgain). In this case the number of subsets of size $k$ is considerably smaller than 2^{\abs{E\cap[1,x]}}, so the set may still be Sidon $\endgroup$ May 31, 2021 at 13:31

The set has a Sidon-like property. There is a constant $s,$ such that any difference $d$ appears at most $s$ times, i.e. the number of solutions of $x+y=d$ is at most $s,$ where $x,y$ are from your set. It would be nice to find a simple proof of this.

Also, the number of solutions of $\Sigma_{i=1}^k\epsilon_in_i=0$ in coprime $n_i$ elements is bounded by a constant $s_k$ depending on $k$ only. You can find references in the classical paper by Erdős, P.; Stewart, C. L.; Tijdeman, R.: Some Diophantine equations with many solutions. Compositio Math. 66 (1988), no. 1, 37-56. https://users.renyi.hu/~p_erdos/1988-31.pdf and in the more recent paper of Kálmán Győry https://doi.org/10.48550/arXiv.1901.11289


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .