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
    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
    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
    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
    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
    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
    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
    Apr 27, 2013 at 22:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.