3
$\begingroup$

Let $p(n)$ be the integer partition. It is already known that for $0 < x < 1$, we have

$\sum_{j=0}^{\infty} p(j)x^j = \prod_{i=1}^{\infty}\dfrac{1}{1-x^{i}}$.

But what if the sum on the left side stops on some $k \geq 0$? That is, do we have any clue about what the sum $\sum_{j=0}^{k} p(j)x^j$ is for each $k \geq 0$?

My specific interest is when $x = 1/q$ where $q$ is the size of a finite filed whose characteristic is larger than 2. If this is not a difficult problem, I think the answer should be out there but it is just that I cannot find it so far. My naive conjecture is $\sum_{j=0}^{k} p(j)x^j \approx 1/(1-x)$ although I haven't thought very deeply about how close they are.

If the above solution is not known, it will be equally as great if I can hear whether

$\sum_{j=0}^{(n-2)m} p(j)/q^j \approx (1 + q^{-1} + q^{-2} + \cdots + q^{-n})^{m}$, where $q$ is as same as above, where $0 \leq m \leq q$ (with as much detail as possible).

Improve this question
$\endgroup$
8
  • $\begingroup$ $x/(x-1)$ is going to be negative for the kind of $x$ you ask about, so that seems like an odd conjecture. $\endgroup$
    – Gerry Myerson
    Commented Jun 24, 2012 at 22:53
  • $\begingroup$ You are right. I should have written it more carefully. Let me correct it. $\endgroup$
    – Gilyoung Cheong
    Commented Jun 24, 2012 at 23:33
  • $\begingroup$ @Gerry Myerson: Thanks for pointing out. In my head it was looking like the left-hand side of $q/(q-1) = 1/(1-q^{-1})$. $\endgroup$
    – Gilyoung Cheong
    Commented Jun 24, 2012 at 23:35
  • $\begingroup$ Moreover, it looks like as $x$ become close to zero the conjecture seems a lot better. I have only investigated when $x = 1/N$ where $N > 1$. But the property is probably what's happening over a continuum (subset of $\mathbb{R}$), and I also suspect if there is, any argument must be easier in continuous or differentiable $x$ than discrete $x = n$. $\endgroup$
    – Gilyoung Cheong
    Commented Jun 24, 2012 at 23:42
  • $\begingroup$ I am perfectly fine with any argument with all $x$ in any interval near $0$ since that will be useful for most of the finite fields that I am interested in. $\endgroup$
    – Gilyoung Cheong
    Commented Jun 24, 2012 at 23:45

1 Answer 1

Reset to default
3
$\begingroup$

The series $\sum p(j) x^j$ converges for $|x|<1$, so for $x = 1/q$ the difference between the infinite series and the partial sum drops exponentially with $k$. The difference is asymptotically smaller than $c^k$ for any $1/q \lt c \lt 1$. In other words, a good approximation to the truncated series is the infinite series itself, which does not depend on $k$.

Your approximation $(1 + q^{-1} + q^{-2} + ... + q^{-n})^m$ is not good for large $m$ and $q$. That is $1 + m/q + {m \choose 2}/q^2 + ...$ instead of $1 + 1/q + 2/q^2+ ...$ so it is only right in the constant term.

If it helps, the asymptotic growth rate for partitions is known: $p(j) \sim \frac {1}{4\sqrt 3 ~j}\exp (\pi \sqrt{2j/3}).$ For the above, you only need that the growth rate is subexponential. You can use this to get a slightly better approximation than the infinite series since you can estimate the first few missing terms.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks for the comment and yes, just like you said, partial sum drops fairly quickly, so that's really optimistic for me. I also forgot to mention that m≤q. Moreover, m is the number of roots that a monic nth power-free polynomial of a large degree takes over a fixed finite field Fq where q is the same. My computation tells me the last approximation is plausible or there exist only certain m that make me think in that way. $\endgroup$
    – Gilyoung Cheong
    Commented Jun 25, 2012 at 0:30
  • $\begingroup$ I am investigating a family of monic $n$th power-free polynomials with an arbitrary large fixed degree over a finite field. If you have more questions on my computation, please let me know. I think it is either I made a huge mistake somewhere along (although I tried to check thoroughly) or a very weird behavior of root distribution of this family of polynomials. $\endgroup$
    – Gilyoung Cheong
    Commented Jun 25, 2012 at 0:33
  • $\begingroup$ @Douglas Zare: "In other words, a good approximation to the truncated series is the infinite series itself, which does not depend on k." --- Can you elaborate this part a bit more? $\endgroup$
    – Gilyoung Cheong
    Commented Jun 25, 2012 at 1:02
  • $\begingroup$ If you have approximations at $k=k_0$ and at $k=k_1$, then these approximations better be close to each other (exponentially close, $c^{\min(k_0,k_1)})$ or else at least one is off, since both truncated sums are exponentially close to the infinite sum. That is enough to say that your $(1+1/q+...)^m$ can't be very accurate except for an occasional numerical coincidence. $\endgroup$
    – Douglas Zare
    Commented Jun 25, 2012 at 1:41
  • $\begingroup$ You are right that $(1 + 1/q + 1/q^{2} + \cdots)^{m}$ is not a good estimation, but for that since there are some weird restriction on $m$, I was hoping something easier to understand was happening. I think your advice is great for me to deal with the partition issue on my problem. Thanks :) $\endgroup$
    – Gilyoung Cheong
    Commented Jun 25, 2012 at 3:30

You must log in to answer this question.

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