57

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?

Marc Chamberland
  • 644
  • 4
    The prime numbers are not that thin... subsets of their density have a very high chance of being an additive basis of order 2. – Stanley Yao Xiao Sep 04 '19 at 22:35
  • 1
    @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 https://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). – Salvo Tringali Sep 04 '19 at 22:56
  • 2
    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$? – Will Sawin Sep 05 '19 at 00:48
  • 5
    Sums of two squares also count? – Ilya Bogdanov Sep 05 '19 at 05:40
  • 2
    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$. – Yemon Choi Sep 05 '19 at 12:29
  • @FrancescoPolizzi: Goodness! You're right of course. I will delete my comment. – Jochen Glueck Sep 05 '19 at 20:23
  • You seem to be treat $A+B$ as being ${a+b:a \in A,b \in B}$. I think that deserves being made explicit. – Acccumulation Sep 06 '19 at 15:54
  • @Acccumulation I think that the intended definition was clear from context, as can be seen from all the responses. It is a fairly standard notational convention – Yemon Choi Sep 06 '19 at 17:58
  • Let $A$ be the sums of distinct powers of 4 (including $4^0 = 1$) together with 0, and let $B = { 2a : a \in A }$. Then $A + B$ is the set of positive integers. (Admittedly this example is a bit contrived.) – Michael Lugo Sep 06 '19 at 17:58
  • Is the question asking in general for cases where, for $A$ and $B$ thin, $A+B$ is thick? The examples are all the special case $A=B$, i.e. "$A+A$ is thick". – R.. GitHub STOP HELPING ICE Sep 07 '19 at 14:43
  • 1
    The two examples given have $A=B$. If there is an interesting example where $A\neq B$, that would be welcome, but not if it can be simplified to an example where $A=B$. In the Cantor set example, one could augment one of the sets $C$ with a subset of $[0,1]$ that has measure zero. Perhaps the better question is to allow $A\neq B$, but see how thin $A$ and $B$ can be. – Marc Chamberland Sep 07 '19 at 16:07

5 Answers5

33

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 ...)

Nik Weaver
  • 42,041
  • 4
    (Obviously, such a set must have cardinality at least $\sqrt{n}$.) – Nik Weaver Sep 04 '19 at 23:24
  • 1
    The proof used the probabilistic method: choose a random subset of this size and show that it satisfies $SS^{-1}=G$ with nonzero probability. – Nik Weaver Sep 05 '19 at 00:48
  • 1
    Could $O(|G|^{1/2})$ hold? I think it does for solvable groups, $\text{SL}(2, p)$, $S_n$, ... – Sean Eberhard Sep 05 '19 at 08:13
  • @SeanEberhard: that sounds interesting. Are you making separate arguments for the different cases or is there a single idea at work? – Nik Weaver Sep 05 '19 at 11:03
  • 1
    It suffices to show that $G$ has an approximate subgroup $A$ of order $\asymp n^{1/2}$: then by a packing argument $G$ is covered by $O(n^{1/2})$ translates of $A$. If $G$ is solvable then it has plenty of approximate subgroups: one of every possible size in fact. Thus we're done as long has $G$ has a solvable subgroup of size $\gg |G|^{1/2}$. In $\text{GL}(n, q)$ you have the Borel subgroup, which works unless $q = 2$ and $n$ is large. In $\text{SL}(2, q)$ and $S_n$ you can concoct a subgroup of size $\asymp |G|^{1/2}$ by more ad hoc means. – Sean Eberhard Sep 05 '19 at 11:18
  • 2
    Oh, I see. That's a neat idea! Then $O(\sqrt{n})$ seems like a nice conjecture. – Nik Weaver Sep 05 '19 at 11:42
  • 10
    This WAS a nice conjecture ("Rohrbach conjecture") before it got proved; the details are here: https://mathoverflow.net/a/282795/9924 (also @SeanEberhard). – Seva Sep 05 '19 at 12:34
  • 1
    I see, cool. It would be nice to have a CFSG-free proof of course... – Sean Eberhard Sep 05 '19 at 13:00
30

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.

Francesco Polizzi
  • 65,122
24

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.

Gerry Myerson
  • 39,024
  • This falls somehow into the "Cantor-like" category of examples. – Francesco Polizzi Sep 05 '19 at 12:07
  • 3
    @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. – Gerry Myerson Sep 05 '19 at 12:10
  • 2
    Yes, of course. I just intended to make a remark, I was not suggesting that this example is not interesting. – Francesco Polizzi Sep 05 '19 at 12:17
  • 2
    @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. – Gerry Myerson Sep 05 '19 at 12:22
12

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.)

Seva
  • 22,827
7

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.

José Hdz. Stgo.
  • 8,732