Elementary Proof of Basis of Order k - MathOverflow

Elementary Proof of Basis of Order k

2012-09-02T06:33:49Z

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

Answer by js for Elementary Proof of Basis of Order k

2012-09-02T10:20:54Z

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

Answer by Stanley Yao Xiao for Elementary Proof of Basis of Order k

2012-09-02T15:40:25Z

To elaborate on the above comment, the problem with order $k$ bases is precisely that Chernoff's inequality does not work. The joint independence assumption for Chernoff's inequality is essential; as seen by the following example taken from Tao and Vus' Additive Combinatorics:

Color the elements of $[1, N]$ either black or white independently and with equal probability. For each $A \subset [1, N]$ let $s_A$ denote the parity of black elements of $A$ (so say if $A$ contains 3 black elements then $s_A = 1$). One can check that the $s_A$'s are independent events. Write $X = \displaystyle \sum_{A \subset [1, N]} s_A$. One can check that $\mathbb{E}X = 2^N - 1/2$ and $\textbf{Var} X = 2^{N-2} - 1/4$. Further, $\mathbb{P}(X = 0) = 2^{-N}$. The upper-bound on Chernoff's inequality would be $2\exp(-2^{N-2})$, which is much smaller than $\mathbb{P}(X = 0)$, so the inequality fails.

The reason why a simple argument suffices for additive bases of order 2 is because we have

$$\displaystyle r_{2,B}(n) = \sum_{x < n/2} \mathbb{I}(x \in B) \mathbb{I}(n - x \in B) + E$$

where $E$ is a suitably small error, and $r_{2,B}(n)$ is the number of ways to write $n$ as a sum of two elements in $B$. The key here is that the events $\mathbb{I}(x \in B) \mathbb{I}(n - x \in B)$ are independent for $1 \leq x < n/2$. This is not the case when there are more summands. In the Erdos-Tetali paper cited above, this issue is circumvented via Janson's inequality. In particular, Erdos-Tetali showed that there are additive bases of order $k$ satisfying $| B \cap [1,N]| = \Theta(N^{1/k} \log^{1/k} N)$.

The main difficulty you have to circumvent is how to deal with the non-independence of the random variables $\mathbb{I}(x_1 \in B) \cdots \mathbb{I}(x_k \in B)$.