Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $B \subset \mathbb{Z}^+$. Define $r_{B,h}(n)$ to be the number of ways of writing $n$ as the sum of $h$ elements of $B$ and $R_{B,h}(n)$ the number of ways to write $n$ as the sum of $h$ DISTINCT elements of $B$. In many applications, such as the Erdos-Tetalli theorem which finds a set $B$ such that $R_{B,h}(n) = \Theta(\log(n))$ it is more convenient to work with $R_{B,h}(n)$. The reason why such convenience does not affect the results is because in general, the number of elements in $B^h$ that sum to $n$ counted by $r_{B,h}(n)$ but not by $R_{B,h}(n)$, namely those with repeat summands, is negligible.

To illustrate with a fairly concrete example, consider the famous Goldbach Conjecture which asserts that every positive even integer larger than 2 can be written as the sum of two primes. In other words if $B$ is the set of primes, then Goldbach Conjecture is the assertion that $r_{B,2}(2n) > 0$ for all $n > 1$. But the truth is that one expects $r_{B,2}(2n)$ to tend to infinity. In this case the number of sums with repeat summands are precisely to write $2p = p + p$ for some prime $p$, and if $r_{B,2}(2n)$ does indeed tend to infinity, then this is a complete triviality to replace $r_{B,2}(2n)$ with $R_{B,2}(2n)$, since $0 \leq r_{B,2}(2n) - R_{B,2}(2n) \leq 1$ for all $n$.

So my question is, is there some general argument for this observation? That is, in a sufficiently general setting, one can essentially assume that the summands are distinct.

I note that in some very trivial cases this assumption is not appropriate at all. For example, consider $B =$ {$3k : k \in \mathbb{N}$} $\cup$ {$0,1$}. Then $B$ is an asymptotic basis of order 3, but it would NOT be a basis at all if we demanded that the summands be unique. This of course is a somewhat contrived example, since for a set of positive density the number of representations is very small. So of course our criteria for a 'sufficiently general setting' would have to exclude such trivial cases.

share|improve this question
There seems to be a possibly confusing typo: 'it is more convenient to work with $R_{B,h}(n)$.' I believe $r_{B,h}(n)$ is meant instead of $R_{B,h}(n)$. –  quid Feb 6 '11 at 16:24

3 Answers 3

up vote 4 down vote accepted

Here is a fairly crude first attempt.

First note that for any basis $B$, when $h=2$, we have \[0\leq r_{B,2}(n)-R_{B,2}(n)\leq 1\] for all n, as you note in your question. Hence assume $h\geq 3$. In this case, if $r'_{B,h}(n)=r_{B,h}(n)-R_{B,h}(n)$ counts the number of representations where some elements are identical, then \[ r'_{B,h}(n)=\sum_{m\in 2\cdot(B\cap[1,n])}r_{B,h-2}(n-m)\ll\lvert B_n\rvert r_{B,h-2}(n).\]

Hence if we can show that this upper bound is $o(r_{B,h}(n))$, then we have $R_{B,h}(n)\sim r_{B,h}(n)$ as required.

For example, note that this shows that distinct summands dominate in the case of Waring bases, where $\lvert B_n\rvert\approx n^{1/k}$ and $r_{B,h}(n)\approx n^{h/k-1}$.

Also note that it deals with e.g. the ternary Goldbach case, where $\lvert B_n\rvert\approx n/\log n$ and $r_{B,3}\gg n^2$.

This does not, however, deal with thin bases, where $r_{B,h}(n)\approx\log n$ and $\lvert B_n\rvert\approx n^{1/k}$. For such cases you may need to rely on probabilistic arguments, as in the proof of the Erdos-Tetalli theorem.

share|improve this answer
Yes that context is indeed where my question arose. I am reading the Erdos-Tetalli paper and it seems that they worked with what I called $R_{B,h}(n)$ instead of $r_{B,h}(n)$, and never addressed how one can obtain $r_{B,h}(n)$ from $R_{B,h}(n)$. In Terry Tao and Van Vu's book they did address this issue, but closing the gap in that case seemed to rely on a lot more machinery than one would expect. –  Stanley Yao Xiao Feb 6 '11 at 17:26

First, I will give a soft answer to one interpretation of your question, then I will (try to) back this answer up with a concrete example (I will focus on a finite analog, as I am more familiar with it, however I at least know that similiar issues exist in the infinite setting you explicitly asked about).

There is no known method, sufficiently general to work in all or at least most cases one cares about, for passing from the typically more convenient setting of allowing repetitions to that of distinct summands.

There are various questions that are solved allowing repetitions yet are open for distinct summands; or the proofs in the former setting are much simpler than in the latter setting.

To put it differently that the repetitions setting and the (more difficult) distinct setting are closely related is a useful heuristic that one knows how to make precise in certain cases (yet, considerable effort, or even a different type of argument, can be required to do so).

An example, as said in a slightly different context, for illustration: Let $p$ be a prime, and let $A$ be a subset of the cyclic group of order $p$. A classical result, the Cauchy--Davenport Theorem, which is not too difficult to prove, asserts that $|A + A| \ge \min (p, 2|A| - 1),$ where $A + A$ denotes the set of all elements that can be written as a sum of two possibly equal elements of $A$ (unrestricted setting); in other words the subset of elements $g$ of the group for which $r_{A,2}(g)>0$.

Now, a natural analog is the assertion that $|A \hat{+} A| \ge \min (p, 2|A| - 3)$ where $A \hat{+} A$ denotes the set of all elements that can be written as a sum of two distinct elements of $A$ (restricted setting); in other words the subset of elements $g$ of the group for which $R_{A,2}(g)>0$. While now this assertion is also known to be true, between Erd{\H o}s--Heilbronn conjecturing it (mid 1960s) and Dias da Silva--Hamidoune and Alon--Nathanson--Ruzsa proving it about three decades passed.

Moreover, for the Cauchy--Davenport Theorem a certain generalization to arbitrary finite abelian groups is known since decades, known as Kneser's Theorem---there is also a Kneser's Theorem for subsets of the integers. For the distinct setting such an analog only exists in conjectural form; a detailed discussion of this can be found in the following article: V.F. Lev, Restricted set addition in Abelian groups: results and conjectures, Journal de théorie des nombres de Bordeaux, 2005, available freely, e.g., at http://jtnb.cedram.org/item?id=JTNB_2005__17_1_181_0 .

share|improve this answer

I've found this assumption (that there's no real difference between $r$ and $R$) in countless places. I believe it to be true (in terms of what the theorems are) in many situations, but also false (in terms of how the proofs work) in many situations.

Here's the most simple example that I'm certain is unresolved. Let $A_4(n)$ be the maximum cardinality of a subset $B$ of $\{1,2,\dots,n\}$ so that $r_{B,2}(k)\leq 4$ for all $k$, and let $A_2'(n)$ be the maximum cardinality of a subset of $\{1,\dots,n\}$ so that $R_{B,2}(k)\leq 2$ for all $k$. It is obvious from the definition that $A(n)\leq A_2'(n)$, and the presumption (the subject of your question) is that $A_2'(n)/A(n) \to 1$. It isn't known, however, that the limit even exists. (footnote: $A_2'(n) = A_5(n)$. It is known that $A_2(n) \sim A_3(n)$, but not that $A_4(n) \sim A_5(n)$.)

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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