# Log concavity of the power partition function

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 close merge delete

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

( 2022-12-17 01:00:14 +0200 )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.

( 2022-12-17 22:24:43 +0200 )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.

( 2022-12-18 10:22:54 +0200 )edit

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

( 2022-12-18 10:27:03 +0200 )edit

Sort by ยป oldest newest most voted

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.

more

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

( 2022-12-24 12:05:33 +0200 )edit