Ask Your Question
0

Log concavity of the power partition function

asked 2022-12-15 15:46:11 +0100

brennan gravatar image

Recently I proved that the power partition function is log concave. The power partition function (usually denoted $P_k(n)$) counts the number of ways to partition an integer into perfect kth powers. Log concavity means for a sequence $a(n)$, we have that $a(n)^2>a(n-1)*a(n+1)$.

I know that for every k there is some $N_k$ such that for all $n>N_k$ the power partition function is log concave. What I want is to know the smallest such $N_k$.

Right now, I only know the smallest $N_k$ for the first three powers:

$k=1 \Rightarrow N_1=25$

$k=2 \Rightarrow N_1=1024$

$k=3 \Rightarrow N_1=15656$

I brute forced this in mathematica, but I cannot go any further. When looking, I moved all the terms of the inequality to the left and waited for the graph to always be positive.

$\frac{P_k(n)}{P_k(n-1)P_k(n+1)}>0$

The function toggles between positive and negative values until it is eventually always positive. Capturing the last negative term in the sequence gives the smallest $N_k$. I waited for about 50 terms in a row to be positive and then looked backwards and the last negative term. But my method takes too long now.

Can anyone think of a faster way to return the smallest $N_k$ for $k=4$ or $5$?

edit retag flag offensive close merge delete

Comments

This is a theory question irrelevant to Sage. https://math.stackexchange.com/ would be better place for such question.

Max Alekseyev gravatar imageMax Alekseyev ( 2022-12-17 01:00:14 +0100 )edit

I agree that the question is not Sage specific. However it is not irrelevant to Sage as it is something that could be programmed.

vdelecroix gravatar imagevdelecroix ( 2022-12-17 22:24:43 +0100 )edit

Note that your second equation makes no sense: all of P_k(n), P_k(n-1) and P_k(n+1) are positive numbers so that the ratio P_k(n) / (P_k(n-1) P_k(n+1)) is always positive.

vdelecroix gravatar imagevdelecroix ( 2022-12-18 10:22:54 +0100 )edit

Also for k=2 I found N_k = 1042 rather than the 1024 that you wrote. Possibly you inverted the last two digits?

vdelecroix gravatar imagevdelecroix ( 2022-12-18 10:27:03 +0100 )edit

1 Answer

Sort by ยป oldest newest most voted
0

answered 2022-12-18 10:36:43 +0100

vdelecroix gravatar image

updated 2022-12-18 12:05:42 +0100

Up to the remarks I made in the comments above, the main question is about how to compute rather efficiently P_k(n). The following function computes the generating series of the P_k(n).

def power_partition_generating_series(s, n=20):
    r"""
    Return the generating series of the s-th power partition function up to O(q^n).
    """
    R = ZZ['q']
    ans = R.one()
    m = 1
    while m**s < n:
        l = [0] * n
        l[0] = 1
        for i in range(1, (n + m**s - 1) // m**s):
            l[i*m**s] = 1
        ans = ans._mul_trunc_(R(l), n)
        m += 1
    return ans

From it, you can naively run through the first coefficients to see whether it looks like it stabilizes.

%%time
seq = power_partition_generating_series(4, 1500000).coefficients()
last_neg = None
for n in range(2, len(seq) - 1):
    d = seq[n]**2 / seq[n-1] / seq[n+1]
    if d < 1:
        last_neg = n
print(last_neg)

gives me

637854
CPU times: user 1min, sys: 3.27 s, total: 1min 3s
Wall time: 1min 3s

Hence, your next term is plausibly N_4 = 637855.

edit flag offensive delete link more

Comments

This is perfect, thank you so much! (and yes, both comments are true, sorry for the confusion!)

brennan gravatar imagebrennan ( 2022-12-24 12:05:33 +0100 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2022-12-15 15:46:11 +0100

Seen: 202 times

Last updated: Dec 18 '22