1
$\begingroup$

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$.

Improve this question
$\endgroup$
7
  • $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented Apr 27, 2013 at 21:22
  • $\begingroup$ 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$. $\endgroup$
    – trebe
    Commented Apr 27, 2013 at 22:16
  • 1
    $\begingroup$ 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. $\endgroup$
    – Anonymous
    Commented Apr 27, 2013 at 22:34
  • $\begingroup$ @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? $\endgroup$
    – trebe
    Commented Apr 27, 2013 at 23:09
  • 1
    $\begingroup$ 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. $\endgroup$
    – Greg Martin
    Commented Apr 28, 2013 at 2:47

1 Answer 1

Reset to default
-1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ 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}$. $\endgroup$
    – trebe
    Commented Apr 27, 2013 at 22:08
  • 1
    $\begingroup$ @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. $\endgroup$
    – Felipe Voloch
    Commented Apr 27, 2013 at 22:35

You must log in to answer this question.

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