Context
-------


According to the FAQ, questions of the form "the sorts of questions you come across when you're writing or reading articles or graduate level books" are acceptable. This falls into the "reading graduate level books."


Problem Statement
-----------------


Let $N$ be the natural numbers.


$B \subseteq N$ is a basis of order $k$ if $N \setminus kB$ is finite.


I would like to show that there is a basis $B$ of order $k$ s.t.


$|B \cap [1,n]| = O(n^{1/2} \log^{1/k} n)$.


What I've tried
---------------


Suppose all we needed was $O(n^{1/2} \log^{1/2} n)$, then I would define $B$ by randomly sampling from $N$ s.t.


$$P(n \in B) = \frac{c\log^{1/2} n}{\sqrt{n}}$$


By the chernoff bound, with high probability we have $|B \cap [1,n]| = O(n^{1/2}\log^{1/2} n)$.


Furthermore, for any $n$, there does not exists $a,b\in B$ s.t. $a+b=N$ with probability at most $(1-\frac{c\log n}{n})^{n/2} \leq 1/n^2$, and we're done.


Unfortunately, however, I need to push this down to $O(n^{1/2}\log^{1/k} n)$.


What I'm stuck on
-----------------


So far, I've only used $B$ as a order 2 base, rather than an order $k$ base.


Question:
---------


What should I be looking at to go from order 2 to order $k$ and $\log^{1/2} n$ to $\log^{1/k} n$?



Elementary Proof of Basis of Order k
If $B$ is a basis of order $k$ such that every integer $n$ can be written as a sum of $k$ elements from $B$ in $\asymp n^{o(1)}$ ways, then a simple counting argument yields $|B \cap [1 , X]| \asymp X^{\frac{1}{k}+o(1)}$. Thus a stronger estimate $|B \cap [1 , X]| \asymp (X \log X)^{\frac{1}{k}}$ in your problem is certainly a more interesting goal.


Theorem 8.6.3 in "The Probabilistic Method" by Alon & Spencer gives precisely a set $B$ satisfying this estimate when $k=3$ (and the proof can be adapted in order to handle any value $k \geq 3$).
They also give the following reference :


*Erdos, P. and Tetali, P. (1990). Representations of integers as the sum of k terms, 
Random Structures Algorithms 1(3): 245-261.*


**EDIT** : I answer here the comments below.


@Stanley Yao Xiao : I made an assumption on the number of representations of integers by $k$ elements from $B$ which essentially discards basis of smaller order.


@unknown : Writing $r(n)$ for the number of representations of $n$ as a sum $b\_1 + \cdots + b\_k$ with each $b\_i \in B$, we have
$$ |B \cap [1,X]|^k = \sum\_{n \geq 1} \left( \sum\_{b\_1 + \cdots + b\_k = n ;\\ b\_i \leq X} 1 \right) \geq \sum\_{1 \leq n \leq X} r(n) $$
and
$$ |B \cap [1,X]|^k = \sum\_{n \geq 1} \left( \sum\_{b\_1 + \cdots + b\_k = n ;\\ b\_i \leq X} 1 \right) \leq \sum\_{1 \leq n \leq kX} r(n) $$
Under the assumption $r(n) \asymp n^{o(1)}$, both RHS are $X^{1 + o(1)}$, hence the result.
Actually, Erdos & Tetali showed that some basis $B$ of order $k$ satisfies $r(n) \asymp \log n$. By the argument above, this implies $|B \cap [1,X]| \asymp (X \log X)^{\frac{1}{k}}$. 


