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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented Sep 25, 2012 at 20:16
  • $\begingroup$ Are there any examples of $n_m > \frac32 m^2$? $\endgroup$
    – Harry Richman
    Commented Feb 12, 2018 at 6:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .