Return to Answer

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 the comments below here.

@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}}$.

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}}$.

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.

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 the comments below here.

@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}}$.

If $B$ is a basis of order $k$ such that every integer $n$ has $\asymp n^{o(1)}$ as a sum of $k$ elements from $B$, 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.

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.