5
$\begingroup$

Any natural number can be expressed as the sum of three triangular numbers, or as four square numbers. The natural analog for expressing numbers as the sum of two others would apparently be the sum of two "linear" numbers, but all natural numbers are "linear", so this is rather unsatisfying. Is there a well-known sparser set of integers (or, half-integers, for that matter) that has this property?

$\endgroup$
2
  • $\begingroup$ Well, you could always take all the even numbers and $1$; or more generally, $k\mathbb{N}\cup\{1,2,\ldots,k-1\}$. Don't think they will be any more "satisfying", though. $\endgroup$ Mar 7 '11 at 6:51
  • $\begingroup$ It's a start, but unfortunately, I don't find that too satisfying either. The triangular numbers have density 1/n, rather than constant density. $\endgroup$
    – wnoise
    Mar 7 '11 at 7:19
3
$\begingroup$

Assuming Goldbach's conjecture, you can take the set of all primes and successors of primes (plus some small numbers). These have density $2/\log n$.

Not assuming the conjecture, you can take primes, almost-primes and successors of primes (plus some small numbers) - this is the famous Chen's theorem. The resulting density is $\log\log n/\log n$.

Another suggestion is to take the set of all numbers whose binary expansion is "supported" on only odd powers of $2$ or only even powers of $2$. The resulting density is roughly $2/\sqrt{n}$, so this is close to optimal (you need at least $1/\sqrt{n}$).

$\endgroup$
2
  • $\begingroup$ Goldbach's conjecture and Chen's theorem also give nice solutions for the "half-integer" variant. $\endgroup$
    – wnoise
    Mar 7 '11 at 8:05
  • 3
    $\begingroup$ OEIS A126684 says your third suggestion 0, 1, 2, 4, 5, 8, 10, 16, 17, 20, 21, 32, ... is the fastest-growing sequence whose sumset consists of the nonnegative integers. $\endgroup$
    – Henry
    Mar 7 '11 at 8:06
0
$\begingroup$

This math overflow post may be of some interest: https://mathoverflow.net/questions/9731/polynomial-representing-all-nonnegative-integers

$\endgroup$

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.