4
$\begingroup$

The following function comes up in my research as part of a sufficient condition for capability of $p$-group of class two and prime exponent. Given a nonnegative integer $m$, express $m$ as a triangular number plus a remainder, $$ m = \binom{T}{2}+s,\qquad 0\leq s \lt T.$$ Then $$f(m) = \binom{T}{3}+\binom{s}{2}.$$ (The values of the function are sequence A111138 in the OEIS).

(There are a number of ways to describe the function $f$; for example, starting with $f(0)=0$, you then start adding nonnegative integers to the running total up to one more than the previous "run"; thus, $$\begin{align*} f(0)&=0;\\ f(1)&=f(0)+0=0\\ f(2)&=f(1)+0=0,\ f(3)=f(2)+1=1;\\ f(4)&=f(3)+0=1,\ f(5)=f(4)+1=2,\ f(6)=f(5)+2=4;\\ f(7)&=f(6)+0=4,\ f(8)=f(7)+1=5,\ f(9)=f(8)+2=7,\\ &f(10)=f(9)+3 = 10;\\ f(11)&=f(10)+0=10,\ f(12)=f(11)+1=11, f(13)=f(12)+2=13,\\ &f(14)=f(13)+3=16,\ f(15)=f(14)+4=20;\\ \end{align*}$$ etc.)

I would like a formula for $f$ in terms of $m$. The best I can do right now is to find the value of $T$, which if I'm not mistaken is given by: $$T = \left\lfloor \frac{1+\sqrt{1+8m}}{2}\right\rfloor$$ and then replace $s$ with $n-T$ and just expand the binomial coefficients.

Is there a simpler expression for $f$? Also, am I correct that the function grows as $(8m)^{3/2}$ ?

Improve this question
$\endgroup$
8
  • $\begingroup$ Note that for 3s less than 2(T-2) you get f(m) less than m(T-2)/3; this should bring you close to your asymptotic estimate. Gerhard "Who Needs Those Additional Terms" Paseman, 2014.02.03 $\endgroup$
    – Gerhard Paseman
    Commented Feb 3, 2014 at 18:48
  • $\begingroup$ @Eckhard: I don't follow. For example, if $m=8$, we could take $(8,0)$, $(7,1)$, $(6,2)$, $(5,3)$, $(4,4)$; the first gives me, using your formula, $56$; the second $36$, then $23$, and the last two give $16$, none of which is the correct value (which is $5$). If your $M$ is supposed to be my $T$, then you are just computing the binomial coefficients explicitly (modulo correcting $(1/2)j(1+j)$ to $(1/2)j(j-1)$). $\endgroup$
    – Arturo Magidin
    Commented Feb 3, 2014 at 19:09
  • $\begingroup$ Looking at the OEIS entry, I think you can show $cm^{3/2}$ as an upper bound. c=1 should be doable, and likely c is smaller. Gerhard "Basing This On Small m" Paseman, 2014.02.03 $\endgroup$
    – Gerhard Paseman
    Commented Feb 3, 2014 at 19:10
  • 2
    $\begingroup$ As you note $T$ is about $\sqrt{2m}$. Clearly then $f(m)$ is about $T^3/6\sim \sqrt{2} m^{3/2}/3$ asymptotically. $\endgroup$
    – Lucia
    Commented Feb 3, 2014 at 19:18
  • 1
    $\begingroup$ In fact $c=\sqrt{1/2} + \epsilon$ is straightforward using f(m) less than m(T-1)/2. Gerhard "Hope This Helps You Out" Paseman, 2014.02.03 $\endgroup$
    – Gerhard Paseman
    Commented Feb 3, 2014 at 19:21

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .