8
$\begingroup$

Every nonnegative integer can be written (eventually in many ways) as a sum of three triangular numbers by the Gauss Eureka theorem.

What is the smallest positive integer $n=n_m$ which can not be written in the form $$n=\binom{a}{2}+\binom{b}{2}+\binom{c}{2}.$$ subject to $\max(a,b,c) \le m?$

The answers for $m$ from $1$ to 60 are

$ \begin {array}{cccccccccc} 1&4&8&11&24&29&29&47&68&68 \\95&99&137&141&173&173&245&281&314&314 \\314&407&419&419&470&470&617&617&711&800 \\863&911&911&911&911&1118&1118&1118&1118&1118 \\1383&1433&1433&1679&1679&1679&1868&1868&1868&1868 \\1868&2360&2493&2493&2519&2925&3044&3044&3098&3098 \end {array} $

The sequence does not seem to be in the OEIS even with a superseeker search. It just seems a curious sequence. Any information would be welcome. What bounds or asymptotics can be established? It would appear that $n_m \lt m^2$ although $m_{105}=11018 \lt 11025=105^2$ leaves some doubt. I'd conjecture (rashly) that $$\limsup \frac{n_m}{m^2}=1$$ but $n_{110}=n_{111}=n_{112}=n_{113}=11625$ and $\frac{11625}{113^3} \approx 0.91$ so the $\liminf$ might be less. I wonder what explains the repeated values and what can be said about them.

UPDATE Noam makes a nice argument that $\lim \frac{n_m}{m^2}=3/2.$ I'd accept it if it was an answer and not a comment. Let me spell out that $8\binom{t}{2}+1=(2t+1)^2$ so $n=\binom{a}{2}+\binom{b}{2}+\binom{c}{2}$ exactly if $8n+3=(2a+1)^2+(2b+1)^2+(2c+1)^2$ and this allows one to pull in results on sums of squares.

I still don't see why things such as $n_{36}=n_{37}=n_{38}=n_{39}=n_{40}$ happen, but I have not thought about it very deeply.

For any fixed $k$, $n_m \lt \frac{3m^2}{2}-km$ with finitely many exceptions. so one could wonder about things like $\frac{3m^2}{2}-\sqrt{m^3}.$ However this result was great for the problem I wanted to apply it to. I would have mentioned the connection sooner but the answer came before I ggot to that.

Improve this question
$\endgroup$
9
  • $\begingroup$ I get 1,1,4,7 to start. Perhaps you can tell us what you did to compute the values? Gerhard "And They Aren't Triangular Numbers" Paseman, 2012.09.25 $\endgroup$
    – Gerhard Paseman
    Sep 25, 2012 at 17:04
  • $\begingroup$ They do count triangles in complete graphs,but triangular numbers have a 2 in the bottom of the choice notation. Gerhard "Ask Me About System Design" Paseman, 2012.09.25 $\endgroup$
    – Gerhard Paseman
    Sep 25, 2012 at 17:06
  • $\begingroup$ I checked a couple of cases to verify that you meant $a \choose 2$ instead of $a \choose 3$, then made that edit. The question with $a \choose 3$ is not absurd, though, if $a$ could be negative. $\endgroup$
    – Douglas Zare
    Sep 25, 2012 at 17:48
  • 1
    $\begingroup$ The question has an obvious analog for the "four-square theorems". Has this analog been considered? $\endgroup$
    – Joël
    Sep 25, 2012 at 19:41
  • 13
    $\begingroup$ The limit of $n_m / m^2$ is $3/2$. Writing $n$ as a sum of three triangular numbers is equivalent to writing $8n+3$ as a sum of three (necessarily odd) squares. It is known that the integer solutions of $x^2+y^2+z^2=8n+3$ are asymptotically equidistributed on the sphere of radius $(8n+3)^{1/2}$ [though this uses Siegel's ineffective lower bound on the number of solutions]. In particular, for each $\epsilon>0$ there's a solution with $\max(x,y,z) < (1+\epsilon) \min(x,y,z)$ once $n > n_0(\epsilon)$, etc. $\endgroup$
    – Noam D. Elkies
    Sep 25, 2012 at 19:44

1 Answer 1

Reset to default
6
$\begingroup$

I get $n_{m} > m^2$ for the following values of $m$ (up to 322): $$\eqalign{ &118, 139, 140, 141, 152, 153, 176, 177, 179, 180, 182, 183, 184, 185, 186, 188,\cr &189, 190, 191, 192, 193, 194, 196, 197, 198, 199, 200, 201, 202, 203, 209, 210,\cr &220, 221, 222, 223, 224, 225, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236,\cr &242, 243, 244, 249, 250, 251, 252, 253, 254, 259, 260, 261, 262, 263, 264, 265,\cr &266, 267, 270, 271, 272, 273, 274, 275, 278, 279, 280, 281, 282, 283, 284, 285,\cr &286, 287, 288, 289, 290, 291, 292, 293, 294, 295, 296, 297, 298, 299, 300, 301,\cr &302, 303 }$$

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Ha, and I somewhat arbitrarily stopped at $115$. $\endgroup$
    – Aaron Meyerowitz
    Sep 25, 2012 at 20:16
  • $\begingroup$ Are there any examples of $n_m > \frac32 m^2$? $\endgroup$
    – Harry Richman
    Feb 12, 2018 at 6:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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