I was thinking about functions, $f : \mathbb{Q}_{\geq 0} \to \mathbb{Q}$, (where $\mathbb{Q}_{\geq 0}$ is $\{x\in \mathbb{Q} : x \geq 0\}$) with the following property:

\begin{equation*} \forall a,b,e \in \mathbb{Q}_{\geq 0} : a \neq b \implies \exists i \in (a,b) :f(i) > e \end{equation*}

That is to say, functions on positive rational numbers that have no upper bound on any non-empty open interval on the positive rationals.

Now while thinking of example candidates for this function I came up with a number of functions of the form:

\begin{equation*} f \dfrac{i}{j} : \left(i,j\in\mathbb{Z}\land\gcd(i,j) = 1\right) = \dfrac{g(i)}{j} \end{equation*}

Where $g : \mathbb{Z} \to \mathbb{Q}$ was some other function. Some observations here lead me to the conjecture:

\begin{align*} \forall (g : \mathbb{Z} \to \mathbb{R}): \left(g \neq O(\lambda n . n) \implies \\ \forall a,b,e \in \mathbb{Q}_{\geq 0} : a \neq b \implies \exists \dfrac{i}{j} \in (a,b) : \left(i,j \in \mathbb{Z} \land \gcd(i,j) = 1 \implies \dfrac{g(i)}{j} > e\right)\right) \end{align*}

Where $O(x)$ represents the big-O-notation of $x$.

Since that is a mess of symbols here it is stated in plain English:

For every function $g : \mathbb{Z} \to \mathbb{Q}$ such that $g$ grows faster than the identity, the function, $f$, defined such that for any rational number in reduced form it is equal to $g$ of the numerator divided by the denominator, is a function that is bounded on no non-empty open interval of the positive rationals.

Both me and my roommate have been unable to prove this conjecture so far and we were hoping to get some help. Any level of help is welcome, we don't mind people spoiling the solution for us. Since this is a recreational problem I came up with the conjecture may be false.

  • $\begingroup$ What do you mean with $\mathbb Q^*$? $\endgroup$ – celtschk Dec 6 '17 at 21:14
  • $\begingroup$ @celtschk I intend to mean $\{x\in\mathbb{Q}: x\geq 0\}$ or the non-negative rationals. $\endgroup$ – Sriotchilism O'Zaic Dec 6 '17 at 21:15

Let $a,b$ be fixed, with $0<a<b.$

By the Prime Number Theorem, for $i>0$ the number of primes between $i/b$ and $i/a$ is $$P(i)=(i/a)(1+d(i))/\ln (i/a)- (i/b)(1+e(i))/\ln (i/b)$$ where $\lim_{i\to \infty}d(i)=0=\lim_{i\to \infty}e(i).$

So $P(i)\to \infty$ as $i\to \infty.$

Let $S$ be the set of $i\in \Bbb N$ with $i>1,$ such that every prime in $(i/b,i/a)$ divides $i$. Then $S$ is a finite set. Because for $i\in S$ we have $i\geq (i/b)^{P(i)},$ which implies $\ln i\geq (\ln i-\ln b) P(i),$ which implies $1\geq (1-(\ln b)/\ln i))P(i),$ which implies a finite upper bound on $\{P(i):i\in S\}.$

Let $i_0=\max (S\cup \{1\})$. For $i>i_0$ there exists a prime $j\in (i/b,i/a)$ with $j\not |\; i$ .

Given $r>0,$ take $i>i_0$ such that $g(i)>(r/a)i$ and let $j\in (i/b,i/a)$ be prime and not a divisor of $i.$ So $\gcd(i,j)=1 .$ And $i/j\in (a,b).$ And $g(i)/j>(r/a)i/j>(r/a)a=r.$


Given $N> 0$, there is an $i$ such that $g(i) > Ni$, or $\frac {g(i)}{i} > N$. In fact, since there is an $i_M$ for each $M \ge N$ with $\frac {g(i_M)}{i_M} > M \ge N$, there are infinitely many $i$ with $g(i) > Ni$.

So let $i$ be such a value, chosen large enough to also satisfy $$i > 2\frac{ab}{b-a}$$ and therefore that $$\frac ia - \frac ib =i\left(\frac {b -a}{ab}\right)> 2$$ Therefore, there are at least two $j \in (\frac ib, \frac ia)\cap \Bbb Z$, of which one must be relatively prime to $i$. Choosing a relatively prime value and rearranging, this is equivalent to $$a < \frac ij < b$$

But then $$f\left(\frac ij\right) = \frac{g(i)}j > \frac {Ni}j > Na$$

Hence $f$ can be found as high as desired in $(a, b)\cap \Bbb Q$.

  • $\begingroup$ Still trying to find a fix for the problem of choosing $j$ relatively prime to $i$. If you also require $g$ to be increasing, then $i$ can be chosen to be prime, which solves the issue. But for more general $g$, there is no guarantee that any prime $i$ satisfies $g(i) > Ni$. $\endgroup$ – Paul Sinclair Dec 7 '17 at 2:08
  • $\begingroup$ My answer uses the Prime Number Theorem. I dk whether that is over-kill. $\endgroup$ – DanielWainfleet Dec 7 '17 at 10:06
  • $\begingroup$ @DanielWainfleet - it only becomes overkill when someone demonstrates a much easier way to kill. I certainly haven't found one. $\endgroup$ – Paul Sinclair Dec 8 '17 at 0:12
  • $\begingroup$ In my A the PNT was used to show that for any sufficiently large $i$ there is a prime $j\in (i/b,i/a).$ But it would suffice to show there exists $ j\in (i/b,i/a)$ that is co-prime to $ i$....I dk whether this could be shown by a more elementary method. $\endgroup$ – DanielWainfleet Dec 8 '17 at 22:53

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.