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
  • 4
    $\begingroup$ What is your calculation for $f(k)=k$? This looks really strange. $\endgroup$
    – Aphelli
    Commented Sep 29, 2019 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
    Commented Sep 29, 2019 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
    Commented Sep 29, 2019 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
    Commented Sep 29, 2019 at 21:10

3 Answers 3

Reset to default
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)$.

$\endgroup$
1
  • $\begingroup$ There was an error in my result, I fixed it. However, there is no error in your argumentation. $\endgroup$
    – Vincent Granville
    Commented Sep 29, 2019 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!}$

$\endgroup$
1
  • 1
    $\begingroup$ @VincentGranville I repaired.. $\endgroup$
    – reuns
    Commented Sep 29, 2019 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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .