Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 7 down vote accepted

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.

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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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