Representation functions with prescribed rates of growth
Let h ≥ 2, and b1, ..., bh be positive integers with gcd = 1. For a set A ⊆ N, denote by rA(n) the number of solutions to the equation
b1k1 + ... + bhkh = n
with k1, ..., kh ∈ A. For which functions F can we find A such that rA(n) ∼ F(n)? Or rA(n) ≍ F(n)? In the asymptotic case, we show that for every F of “regular variation”,
F (x) xh−1 logx→∞asx→∞,andF(x)≲(h−1)!b...b ,
1h
there is A such that rA(n) ∼ F(n). In the order of magnitude case, there is A with rA(n) ≍ F(n) for every F non-decreasing such that F(2x) ≪ F(x) in the range logx ≪ F(x) ≪ xh−1. This extends earlier work of Erd ̋os– Tetali and Vu, and addresses a question raised by Nathanson on which
functions can be the rA of some A.
For 1 ≪ F(x) = o(logx), we obtain a probabilistic heuristic for why
there should not exist A with rA(n) ≍ F(n), agreeing with a conjecture of Erd ̋os.