1
$\begingroup$

I haven't worked out all the details yet, but it seems to be true for the following functions:

  • $f(k) = 1$
  • $f(k) = 1/k!$
  • $f(k) = a^k$
  • $f(k) = 1/\log(k+1)$

What are the conditions on $f$ for this to be true? It sounds like a fairly general result that should be easy to prove. Sums like these are related to the discrete self-convolution operator, so I'm pretty sure the result mentioned here must be well known.

Update: A weaker result that applies to a broader class of functions is the following: $$\sum_{k=1}^n f(k)f(n-k) = O\Big(n f^2(\frac{n}{2})\Big).$$ Is it possible to find a counter-example, with a function $f$ that is smooth enough and in wide use?

$\endgroup$
  • 4
    $\begingroup$ What is your calculation for $f(k)=k$? This looks really strange. $\endgroup$ – Mindlack Sep 29 '19 at 12:59
  • 2
    $\begingroup$ Indeed, with $f(x)=x$ the left grows at least $\sim n^2$ from the middle summand whereas the right is $\sim \frac1n$ $\endgroup$ – Hagen von Eitzen Sep 29 '19 at 13:02
  • $\begingroup$ @Mindlack: The exact value for $f(k) = k$ is $n(n^2-1)/6 \sim \frac{1}{6}n^3$. So the result is not valid. But we have $\sum_{k=1}^n f(k)f(n-k) = O(n f^2(n/2)$ though, a weaker result. I updated my question accordingly. $\endgroup$ – Vincent Granville Sep 29 '19 at 13:39
  • 1
    $\begingroup$ @HagenvonEitzen .With $f(x)=x$ the LHS is $n^2(n+1)/2 -n(n+1)(2n+1)/6=n^3/6+o(n^3)$ and the RHS is $n^3/4+o(n^3).$ It is indeed an exception. $\endgroup$ – DanielWainfleet Sep 29 '19 at 21:10
1
$\begingroup$

If you think the error term is produced from approximation of an integral: $$\frac{1}{n} \int_0^n f*f=\frac{1}{f^2(n/2)}$$ That means you should search for functions that mean of their convolution to themselves is equal to inverse of square of them at mid point of interval, that in fact meet each other. There is two natural points that many of functions close to satisfy them:

1) Get mean value at mid point.

2) Since $f$ convulses with itself, the $f^2$ is a good candidate for mean.

So you should more think about functions that satisfy the inverse of that mean we expect more, $1/f^2(n/2)$ instead of $f^2(n/2)$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ There was an error in my result, I fixed it. However, there is no error in your argumentation. $\endgroup$ – Vincent Granville Sep 29 '19 at 13:46
1
$\begingroup$

$\sum_{k=0}^n f(k)f(n-k) = O\Big(n f^2(\frac{n}{2})\Big)$ doesn't hold when $f(0) \ne 0$ and $f(n)$ grows much faster than $f(n/2)^2$ for example with $f(n)= e^{n!}$

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ @VincentGranville I repaired.. $\endgroup$ – reuns Sep 29 '19 at 21:36
0
$\begingroup$

This is not an answer, but rather an upper bound. Using the Cauchy-Schwartz inequality, it is easy to obtain $$\sum_{k=1}^n f(k)f(n-k)\leq \sum_{k=0}^n f^2(k)\sim \int_0^nf^2(x) dx.$$

For a full solution, consider two independently and identically distributed random variables $X_n, Y_n$ with $P(X_n =k) = P(Y_n=k) \propto f(k)$ for $k=0, 1, \cdots, n$. This assumes that $f\geq 0$. Then $$\sum_{k=1}^n f(k)f(n-k)\approx P(X_n+Y_n \leq n) .$$

The distribution of $X_n + Y_n$ can be obtained using the convolution theorem.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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