For $A\subseteq \mathbb{N}$ and an integer $k\geq 1$ we set $S_A(k) = \{B\subseteq A: B\text{ is finite and } \sum_{b\in B} b = k\}.$ We say that a set $A\subseteq \mathbb{N}$ is sparse if $$\text{lim inf}_{n\to\infty}\frac{|A\cap\{1,\ldots,n\}|}{n} = 0.$$

Is there a sparse set $A\subseteq \mathbb{N}$ such that for every $n\in\mathbb{N}$ there is an integer $z\in \mathbb{N}$ such that $$|S_A(z)| \geq n?$$

  • 2
    $\begingroup$ The Fibonacci sequence? Gerhard "And So Many Others Too" Paseman, 2017.04.20. $\endgroup$ – Gerhard Paseman Apr 20 '17 at 15:32
  • $\begingroup$ By multiplying by a constant, you can make the possible sums have a low but nonzero density in the integers and maintain your property, but I cannot see how to get your property and how to make the set of possible sums also have density approaching zero. Gerhard "Now That's An Interesting Question" Paseman, 2017.04.20. $\endgroup$ – Gerhard Paseman Apr 20 '17 at 16:12
  • $\begingroup$ Ah, here we go. Set A1 to have 1, and An+1 to have c=100^{100^n} and c-b for every b in An. Gerhard "And Then Sums Of Sums..." Paseman, 2017.04.20. $\endgroup$ – Gerhard Paseman Apr 20 '17 at 16:21
  • 1
    $\begingroup$ It might be interesting to note that every IP set has your summation property. There are plenty of examples of sparse IP sets. One particularly easy example is the set of all natural numbers whose base-10 representation contains only zeros and ones. (@GerhardPaseman's observation about the Fibonacci sequence shows that not every set with your summation property is an IP set.) $\endgroup$ – Will Brian Apr 20 '17 at 17:57
  • 1
    $\begingroup$ @Turbo Here it is: mathoverflow.net/questions/268003/… Again caution, it contains a wrong formulation of the conjecture $\endgroup$ – Dominic van der Zypen Apr 25 '17 at 12:47

Summarizing the commentary of Will Brian and myself, there is a notion of IP set (https://en.m.wikipedia.org/wiki/IP_set) (edit: Will says "has your summation property", which I misinterpreted to mean the following ) which has the property that Dominic points out: for every positive integer $n$ there is a member (in fact an infinite subset of them) $z_n$ of the IP set which is the sum in at least $n$ different ways of the members of the base set $A$ which generates the IP set.

Dominic wants a thin or sparse set $A$ to build an IP set. The Fibonacci sequence F provides an example of a sparse $A$ with Dominic's property, as every sufficiently large member of F itself has multiple representations as sums of Fibonacci numbers. However F is not an IP set ( as an infinite IP set has a partial closure property: given a in the IP set there are infinitely many b in the IP set with a+b also in the IP set). Will mentions the example of base 10 numbers having only ones or zeros in their decimal expansion as a sparse IP set.

One can make A, S(A), and further iterations of S on A simultaneously sparse with a modification of the following technique: let A have 1, and for each positive integer n, throw in c=100^{100^n} and c-a for all a put in at an earlier stage. Then A and S(A) have small but widely separated dense clumps of integers, and one can arrange further iterates to be sparse.

Gerhard "And That Ends The Commentary" Paseman, 2017.04.24.

| cite | improve this answer | |
  • $\begingroup$ Although apparent to the zealous observer, a clear example of a set A in which S(A) does not have Dominic's property is the set A of powers of 2. Gerhard "Leaves Other Generalizations To You" Paseman, 2017.04.24. $\endgroup$ – Gerhard Paseman Apr 24 '17 at 21:09
  • $\begingroup$ I am suffering some confusion. Dominic's property of A says S(A) is rich in some sense. Will says given B=S(A) B has Dominic's property, so S(B) is rich. Will does not say that B is rich. Gerhard "Money Makes Cents To Me" Paseman, 2017.04.24. $\endgroup$ – Gerhard Paseman Apr 24 '17 at 21:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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