## 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$?