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
    Jun 24, 2012 at 22:53
  • $\begingroup$ You are right. I should have written it more carefully. Let me correct it. $\endgroup$
    – Gilyoung Cheong
    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
    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
    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
    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
    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
    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
    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
    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
    Jun 25, 2012 at 3:30

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.