1
$\begingroup$

Let $S \subset \mathbb{N}$. We say $S$ is of type $B_2(g)$ if the number of representation of the form $n = s_1 + s_2 \ (s_1 \leq s_2)$ is bounded by $g$ for every $n \in \mathbb{N}$. Let $S(n)$ be the number of elements of $S$ not exceeding $n$.

There is a theorem by Erdos and Renyi, which states that for any $\epsilon > 0$, there exists $g =g(\epsilon)$ and a set $S \subseteq \mathbb{N}$ such that $S$ is of type $B_2(g)$ and $$ S(n) > n^{1/2 - \epsilon} $$ for $n$ sufficiently large. My question is, is this best up to $\epsilon$? In other words, if $S$ is of type $B_2(g)$, then does it follow that $$ S(n) \ll n^{1/2} $$ for $n$ sufficiently large? I am guessing that this is the case, but I was wondering if someone could possibly explain this to me.
Thank you!

$\endgroup$
2
  • 3
    $\begingroup$ Looks like this is just counting in two ways solutions of $k=s_1+s_2$ with $s_1 \leq s_2 \leq n$ and $k \leq 2n$ to get $S(n)^2 \leq 4gn$. $\endgroup$ Jan 31, 2015 at 0:44
  • $\begingroup$ That depends on your definition of $A\ll B$. If it mean $A<cB$, then as Noam said, this is true. If it means $A/B\to 0$ then the answer is less clear. For example, if we change the problem to count solutions of $s_1+2s_2=n$ then it is easy to get $S(n) \ge n^{1/2}$, even with $g=1$. $\endgroup$
    – Omer
    Feb 4, 2015 at 11:36

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.