4
$\begingroup$

I came across the following problem about representation functions:

Produce a set $A$ such that $r(n) > 0$ for all $n \in [1,N]$, but with $|A| \leq \sqrt{4N+1}$.

Note that r(n) = \left|\{(a, a'): a, a' \in A, n = a+a' \} \right|

I think $A = \{0,1,2 \}$ would work with the interval being $[1,4]$. Then $3 \leq \sqrt{17}$.

A second part of the question shows that one can prove that $|A| \leq \sqrt{N}$ if it satisfies the above conditions. But $3 > \sqrt{4} = 2$. Does this mean that my set $A$ is wrong?

1 Answers 1

7

This appears to be a misprint in (the first edition of) Analytic Number Theory by Donald Newman (p. 15). Several Amazon reviews (here and here) state that that printing is full of errors (and that some have also remained in the second edition).

It should be $|A|\ge\sqrt{N}$, since you need at least that many numbers in $A$ to form enough pairs to produce all the $N$ numbers.

  • 1
    @Damien: Don't let the typos deter you from reading that book! It is not intended to be a text book for analytic number theory, but I found it pretty interesting nonetheless and IMO, a good motivator to further learn the subject.2011-07-15