57
$\begingroup$

I'm interested in examples where the sum of a set with itself is a substantially bigger set with nice structure. Here are two examples:

  • Cantor set: Let $C$ denote the ternary Cantor set on the interval $[0,1]$. Then $C+C = [0,2]$. There are several nice proofs of this result. Note that the set $C$ has measure zero, so is "thin" compared to the interval $[0,2]$ whose measure is positive.
  • Goldbach Conjecture: Let $P$ denote the set of odd primes and $E_6$ the set of even integers greater than or equal to 6. Then the conjecture states is equivalent to $P + P = E_6$. Note that the primes have asymptotic density zero on the integers, so the set $P$ is "thin" relative to the positive integers.

Are there other nice examples?

$\endgroup$
11
  • 4
    $\begingroup$ The prime numbers are not that thin... subsets of their density have a very high chance of being an additive basis of order 2. $\endgroup$ Sep 4, 2019 at 22:35
  • 1
    $\begingroup$ @StanleyYaoXiao Of course, much depends on one's definition of "thin". With this said, the primes are "thin" in a rather strong sense (see Corollary 3.4 in arxiv.org/abs/1905.08075). Something similar is also true for the squares, the cubes, etc.; and it's straightforward from the solution of Waring's problem that, for each of these sets, say $S$, there is an integer $k \ge 2$ s.t. the $k$-fold sumset $kS$ satisfies the condition "thin + thin = thick and nice" (e.g., if $S$ is the set of squares, then $k = 2$ by Lagrange's four-square thm). $\endgroup$ Sep 4, 2019 at 22:56
  • 2
    $\begingroup$ Or, following the Cantor set example, we can look at the set of natural numbers with only zeroes and 1s in their base $3$ expansion. This set is thinner than many of the others considered here, as its density is an inverse power of $n$? $\endgroup$
    – Will Sawin
    Sep 5, 2019 at 0:48
  • 5
    $\begingroup$ Sums of two squares also count? $\endgroup$ Sep 5, 2019 at 5:40
  • 2
    $\begingroup$ Stretching things slightly, there are examples in classical harmonic analysis where the convolution of two singular measures on the circle can be a continuous measure, and you can also get the supports of these singular measures to have Hausdorff dimension $<1$. $\endgroup$
    – Yemon Choi
    Sep 5, 2019 at 12:29

5 Answers 5

33
$\begingroup$

I proved this fact not too long ago: if $G$ is a finite group of cardinality $n$, then there exists a subset $S$ of $G$ of cardinality no more than $\lceil 2\sqrt{n\ln n}\rceil$ such that $SS^{-1} = G$. Possibly this is already known ...?

Edit: It IS known, in fact Seva points out in this answer that it has been shown that there exists a subset of size $\lceil \frac{4}{\sqrt{3}} \sqrt{n}\rceil$ satisfying $S^2 = G$. (I still think it's interesting that a probabilistic argument gets us within $\sqrt{\ln n}$ of this. The stronger result relies on the classification of finite simple groups ...)

$\endgroup$
8
  • 4
    $\begingroup$ (Obviously, such a set must have cardinality at least $\sqrt{n}$.) $\endgroup$
    – Nik Weaver
    Sep 4, 2019 at 23:24
  • 1
    $\begingroup$ The proof used the probabilistic method: choose a random subset of this size and show that it satisfies $SS^{-1}=G$ with nonzero probability. $\endgroup$
    – Nik Weaver
    Sep 5, 2019 at 0:48
  • 1
    $\begingroup$ Could $O(|G|^{1/2})$ hold? I think it does for solvable groups, $\text{SL}(2, p)$, $S_n$, ... $\endgroup$ Sep 5, 2019 at 8:13
  • 2
    $\begingroup$ Oh, I see. That's a neat idea! Then $O(\sqrt{n})$ seems like a nice conjecture. $\endgroup$
    – Nik Weaver
    Sep 5, 2019 at 11:42
  • 10
    $\begingroup$ This WAS a nice conjecture ("Rohrbach conjecture") before it got proved; the details are here: mathoverflow.net/a/282795/9924 (also @SeanEberhard). $\endgroup$
    – Seva
    Sep 5, 2019 at 12:34
30
$\begingroup$

Every real number is the sum of two Liouville numbers, see

P. Erdős: Representations of real numbers as sums and products of Liouville numbers, Mich. Math. J. 9, 59-60 (1962). ZBL0114.26306.

So, denoting by $L \subset \mathbb{R}$ the set of Liouville numbers, we have $$\mathbb{R}=L+L.$$

Interestingly, in the the same paper it is also proved that every non-zero real number is the product of two Liouville numbers, so we have an equality for the multiplicative group of the form $$\mathbb{R}^{\times} = L L.$$

Note that $L$ has Lebesgue measure 0, hence it is "thin" with respect to measure theory.

$\endgroup$
24
$\begingroup$

Every real number is the sum of two numbers whose continued fraction expansion has no partial quotient exceeding $4$. Marshall Hall, Jr., On the sum and product of continued fractions, Annals of Mathematics, Second Series, Vol. 48, No. 4 (Oct., 1947), pp. 966-993, DOI: 10.2307/1969389, https://www.jstor.org/stable/1969389

Here, $4$ is best possible.

$\endgroup$
4
  • $\begingroup$ This falls somehow into the "Cantor-like" category of examples. $\endgroup$ Sep 5, 2019 at 12:07
  • 3
    $\begingroup$ @Francesco yes; for each $n$, the set of numbers with no partial quotient exceeding $n$ forms a Cantor set. But not every Cantor set has the "everything is a sum of two" property. $\endgroup$ Sep 5, 2019 at 12:10
  • 2
    $\begingroup$ Yes, of course. I just intended to make a remark, I was not suggesting that this example is not interesting. $\endgroup$ Sep 5, 2019 at 12:17
  • 2
    $\begingroup$ @Francesco I appreciate your remark, it was something I ought to have included in my answer in the first place. I did not mean to sound critical of your remark. $\endgroup$ Sep 5, 2019 at 12:22
12
$\begingroup$

The set $Q$ of all squares in $\mathbb F_p$ is definitely thick and very nice. Can it be represented as a difference set $A-A$? An open conjecture due to Sárközy is that this is impossible. (It has been recently shown that if $A-A=Q$, then every non-zero element of $Q$ has exactly one representation as $a-b$ with $a,b\in A$, so that $A$ must be thin.)

$\endgroup$
7
$\begingroup$

I know you asked for examples of the "thin + thin = nice and thick" phenomenon but, since Palindrome Week is all the rage these days, I can't avoid mentioning the following example of "thin + thin + thin = nice and thick".

A couple of years ago, J. Cilleruelo(†), F. Luca, and L. Baxter proved that every natural number $n$ can be written as a sum of three palindromic numbers. Since the natural density of the set of palindromic numbers is $0$, if we agree to regard $\mathbb{N}$ as "nice" and "thick", we do have here--as promised--an example of the "thin + thin + thin = nice and thick" phenomenon.

$\endgroup$

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.