4

(This question is in fact related to growth functions of groups)

For two functions $f$ and $g$ (on the set of natural numbers) let us write $f\preceq g$ if there is $C\ge 1$ such that $f(n)\le g(Cn)$ for every $n\ge 1$. Let us write $f\sim g$ if $f\preceq g$ and $g \preceq f$.

For such a function $f$ let $\bar{f}(n)=\sum_{i=1}^n f(i)$.

If for all $d\ge 1$ we have $n^d \preceq f$, is it true that $f\sim \bar{f}$?.

user17488
  • 405

1 Answers1

1

There is a counterexample of the form $f(n)=n^{\omega(n)}$ for a slowly growing function $\omega:\mathbb N\to\mathbb N.$ I suspect something of the order of $\log\log n$ would do for $\omega,$ but I will just use a diagonalization argument. Let $1=t_1<t_2<\dots$ be to be chosen, and $\omega(n)=\max\{i\mid t_i\leq n\}.$ Pick $t_2$ large enough so we get $\overline f(n)>f(2n)$ for some $n$ with $2n<t_2.$ This is possible because $f$ has linear behavior until $t_2,$ so $\overline f$ has quadratic behaviour and eventually dominates $f.$ We can similarly pick each $t_i$ large enough such that $\overline f(n)>f(in)$ for some $n$ with $in<t_i.$ The resulting $f$ satisfies $n^d\preceq f$ for each $d$ but $\overline f\not\preceq f.$

Dap
  • 25,286
  • $\omega(n)=\log\log{n}$ does indeed work. To see this, let $f(x)=x^{\log\log{x}}$. Compute $f'(Cx)$ where $C\geq 1$ is a constant and observe that $Cf'(Cx) = o(f(x))$. By integrating, one has $f(Cx)=o(\overline{f}(x))$. Since this is true for every $C$, one has $\overline f \not\preceq f$. – tristan Mar 12 '18 at 11:39