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!

Improve this question
$\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$
    – Noam D. Elkies
    Commented 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
    Commented Feb 4, 2015 at 11:36

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .