0
$\begingroup$

At the moment I am hearing the lecture named geometric group theory. In the last exercise we got the following exercise: Let $f,g:\mathbb{N}\mapsto \mathbb{R}_{\geq 0}$. We say that $f\leq g$ if there exists a constant $C$, such that

$f(n)\leq C*g(C*n+C)+C*n+C$

We say that $f\sim g$ if $f\leq g$ and $g\leq f$. The exercise is to show that this defines an equivalence realtion on these functions. My problem is to show the reflexivity, because I have no idea how I can choose the C such that I can easy see that $f\sim f$. Maybe I have to use that $C*(n+1)$ is also a monotone function. I think I forgot something important out of the lectures Analysis I+II, which I have to use for a solution. Thanks for help.

  • 1
    Does one assume that $f$ and $g$ are nondecreasing? Then $C=1$ is allright.2011-11-13
  • 0
    Why do you say "is also a monotone function"? What else is a monotone function? Did you forget to specify that $f$ and $g$ are monotone? If there are no further conditions on $f$ and $g$, the statement is false, since you can construct an $f$ for which there is a counterexample to $f(n)\le Cg(Cn+C)+Cn+C$ for each $C\in\mathbb N$ (and presumably $C\in\mathbb N$ since otherwise $g(Cn+C)$ isn't defined).2011-11-14
  • 0
    Thanks. No. I didn't forget anything. Thats the thing. I thought that this can't be true, too. So maybe my professor forget some conditions. $C\in\mathbb N$ is clear but its also not declared. Thanks.2011-11-14
  • 0
    @joriki: You mean a counterexample where $f=g$, right? How can I construct it?2011-11-14
  • 0
    @Peter: Sorry, yes, the $g$ was supposed to be an $f$ -- I'll try to write down the counterexample if I can still remember it :-)2011-11-14
  • 0
    Thanks. And you mean $\geq$ not $\leq$,right? :-)2011-11-14
  • 0
    Sorry. I wanted to say, you mean $\nleq$ not $\leq$,right? So for every $C\in\mathbb N$ there exists $n\in\mathbb N$ such that $f(n)\nleq Cf(Cn+C)+Cn+C$, right? :-)2011-11-14
  • 0
    Yes, but that's what I wrote: a counterexample *to* the inequality means the inequality doesn't hold.2011-11-14

1 Answers 1

1

To construct a counterexample to $f\le f$, we only need pairs of values that we can choose independently such that the inequality is violated at least once for each $C$. So, starting at $C=1$ with $n_1=1$, in each step choose $f(n_C)$ and $f(Cn_C+C)$ such that the inequality is violated for $C$. Then let $n_{C+1}=Cn_C+C+1$ and continue. Since the $n_C$ always increase, these are always new function values that can be chosen arbitrarily, and the remaining function values can also be chosen arbitrarily.

  • 0
    Thanks. Nice. I will ask my professor which conditions he forgot.2011-11-14