Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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).

share|improve this question
    
$x/(x-1)$ is going to be negative for the kind of $x$ you ask about, so that seems like an odd conjecture. –  Gerry Myerson Jun 24 '12 at 22:53
    
You are right. I should have written it more carefully. Let me correct it. –  GilYoung Cheong Jun 24 '12 at 23:33
    
@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})$. –  GilYoung Cheong Jun 24 '12 at 23:35
    
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$. –  GilYoung Cheong Jun 24 '12 at 23:42
    
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. –  GilYoung Cheong Jun 24 '12 at 23:45

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
    
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. –  GilYoung Cheong Jun 25 '12 at 0:30
    
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. –  GilYoung Cheong Jun 25 '12 at 0:33
    
@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? –  GilYoung Cheong Jun 25 '12 at 1:02
    
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. –  Douglas Zare Jun 25 '12 at 1:41
    
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 :) –  GilYoung Cheong Jun 25 '12 at 3:30

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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