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?


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.

  • $\begingroup$ This particular +1 goes to Google ;-) $\endgroup$ – joriki Jul 15 '11 at 18:45
  • $\begingroup$ @joriki: Thanks. I guess this isn't a good book to learn analytic number theory from? $\endgroup$ – Damien Jul 15 '11 at 18:48
  • $\begingroup$ I'm not competent to make a recommendation on that. I do love the crazy dice example, though :-) $\endgroup$ – joriki Jul 15 '11 at 18:54
  • 1
    $\begingroup$ @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. $\endgroup$ – Aryabhata Jul 15 '11 at 19:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.