# Bounds for the largest divisor of n less than n^0.5

Let $d(n)$ denote the largest divisor of $n$ less than $\sqrt{n}$. Are there good lower bounds for $d$ that hold for almost all natural numbers?

More precisely, is there a function $f$, say $f(n)=\frac{\sqrt{n}}{(\log{n})^{100}}$, such that for large $x$, $d(n)\geq f(n)$ holds for almost all $n\leq x$.

-
There is some work of Knuth and Trabb-Pardo, which says what the size of the largest prime factor of all numbers below x is expected to be (or something similar and pertinent to your question. I think their work implies that for almost all n less than x, your d(n) is less than n^0.4. Gerhard "Ask Me About System Design" Paseman, 2013.04.27 – Gerhard Paseman Apr 27 '13 at 21:22
I believe there is a big difference between the largest prime factor and the largest divisor - I think it is known that the average value of $d(n)$ when $1\leq n \leq x$ is at least $\sqrt{x}/log(x)^C$ for some constant $C$. – trebe Apr 27 '13 at 22:16
The state of the art for questions such as this is Kevin Ford's paper arxiv.org/pdf/math/0401223v5.pdf. For the $f(n)$ given in the question, or in fact any $f(n)$ with $f(n) = n^{1/2+o(1)}$, one gets from Ford's work that the set of $n$ with $d(n) \ge f(n)$ has asymptotic density zero. – Anonymous Apr 27 '13 at 22:34
@Anonymous : Could one get asymptotic density one from say $f(n)=n^{1/2 - \epsilon}$; if not, do you know how slow $f$ would have to be to get asymptotic density one? – trebe Apr 27 '13 at 23:09
From Ford's paper, cited above, Theorem 1(v): when $\epsilon$ is sufficiently small, you still don't get density 1 from $f(n) = n^{1/2-\epsilon}$. You do get density 1 from $f(n) = n^{1/4}$, although I can't immediately tell whether that's the best exponent or not. – Greg Martin Apr 28 '13 at 2:47

If $n$ has a prime factor $p<y$ then $pd(n) > \sqrt{n}$ so $d(n) > \sqrt{n}/y$. The number of integers without a prime factor less than $y$ (for suitably small $y$) is approximately $x\prod_{p<y} (1-1/p)$ which in turn is approximately $cx/\log y$. Taking $y = (\log x)^{a}$, for some $a$ probably works ok.
Dear Felipe, Apologies if I've misunderstood your answer but I'm not sure how your reasoning works. Why must $pd(n)>\sqrt{n}$ hold? If $n=2p$ for some large prime $p$, then $d(n)=2$ and it is certainly not the case that $2d(n)>\sqrt{n}$. – trebe Apr 27 '13 at 22:08
@trebe: My mistake. If $pd(n)$ is itself a divisor of $n$, then my argument works. As your example shows, this is not always the case. – Felipe Voloch Apr 27 '13 at 22:35