5
$\begingroup$

Let $B \subset \mathbb{N}$ be an additive basis of order $h$. Define $r_{B,h}(n)$ to be the number of ways $n$ can be written as a sum of $h$ elements of $B$. In particular, $B$ is a basis of order $h$ if $r_{B,h}(n) > 0$ for all $n$. Erdős showed in 1956 that there exists a $B$ and constants $c_1, c_2 > 0$ such that $c_1 \log(n) \leq r_{B,2}(n) \leq c_2 \log(n)$. This was generalized to arbitrary $h$ in 1990 by Erdős and Tetalli. Their proof employed the probabilistic method and was existential. My question is, can an explicit example of a set $B$ be constructed and what would it look like? More specifically, can a 'prime number theorem' type result be proved about an Erdős thin basis? For example, is it possible to show that if $B$ is an additive basis such that $c_1 \log(n) \leq r_{B,h}(n) \leq c_2 \log(n)$, then there exists an 'explicit' function $f_h(n)$ such that $|B \cap [1,n]| \gg f_h(n)$?

We can see that if $B$ is a thin basis of order 2 constructed by the probabilistic method of Erdős, then the expected value of $|B \cap [1,n]|$ is equal to $\displaystyle \sum_{j=1}^n p_j$ where $p_j = c \displaystyle \sqrt{\frac{\log(j)}{j}}$ for some suitably chosen constant $c > 0$. Then $E[|B \cap [1,n]|] \sim 2\sqrt{n \log(n)}$ by partial summation. This provides a satisfactory answer for the latter question, at least for $h = 2$. However, this doesn't shed much insight on how to construct such a $B$ explicitly. In particular the 'obvious' candidate $\{\lfloor 4n \log(n) \rfloor : n \in \mathbb{N}\}$ is not likely to work since this set is too 'regular', likely leading to much more representations than $C \log(n)$ many for some $C > 0$.

$\endgroup$
6
  • 1
    $\begingroup$ Second question: if $r_{B,h}(n)>X$ then $B\cap [1,n]$ contains at least $\approx X^{1/h}$ elements by pigeonhole principle. As for the first question, I think the answer is that there are no known explicit constructions. $\endgroup$
    – Boris Bukh
    Jan 23, 2011 at 15:04
  • $\begingroup$ How about defining $r_{B,h}(n)$? $\endgroup$ Jan 23, 2011 at 17:17
  • $\begingroup$ @Anthony: $r_{B,h}(n)$ is the number of ways $n$ can be written as a sum of $h$ elements from $B$. BTW I second Boris' response. $\endgroup$
    – GH from MO
    Jan 23, 2011 at 17:27
  • $\begingroup$ @GH. That's what I thought, but it doesn't agree with the the inequalities in the original posting. But I thunk there are plenty of bases e.g. the squares $\endgroup$ Jan 23, 2011 at 17:35
  • $\begingroup$ @Anthony: The post was about special bases whose existence was proved by Erdős and Erdős-Tetalli. It is a famous problem going back to Sidon (I believe) to give a basis which is only "barely a basis", the post is about these guys. Am I missing something? $\endgroup$
    – GH from MO
    Jan 23, 2011 at 18:02

0

Your Answer

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