3
$\begingroup$

In looking at OEIS sequence A063539, $1,8,12,16,18,24,27,30,32,36,40,45,...$ I noticed that the first 1000 members were less than 4000, and thought there were no large gaps between them. What (if any) is the limiting density of this set of $\sqrt {n-1}$-smooth numbers? Is it more than 1/4? More importantly, is there a finite bound on the gap size? Specifically, let $d_i= a_{i+1} - a_i$ represent the size of the $i$th gap between consecutive members, is there a finite $C$ larger than all the $d_i$?

While I would appreciate references that answer this question, I would settle for some guiding intuition that suggests how to determine $C$ or even a very slowly growing $C(n)$ upper bound on the gaps. Note that for the density Dickman's function doesn't quite work as (for u=2) it includes all integers less than $\sqrt{n}$ and then some. If someone can show me that the error is small, I would accept using Dickman's function.

Gerhard "Hoping For A Royal Road" Paseman, 2016.11.21.

Improve this question
$\endgroup$
4
  • $\begingroup$ It looks like the density should be the same as if we throw in the squares of primes. This would make the density 1- ln 2, and I would appreciate an undergraduate level reference for the result with prime squares. I still hope for the constant C. Gerhard "Dreams Of Nice Upper Bounds" Paseman, 2016.11.21. $\endgroup$
    – Gerhard Paseman
    Commented Nov 21, 2016 at 20:10
  • 1
    $\begingroup$ Primes have density zero, a fortiori squares of primes have density zero, so, yes, the answer is $1-\log2$. $\endgroup$
    – Gerry Myerson
    Commented Nov 21, 2016 at 21:45
  • $\begingroup$ OEIS points to "D. H. Greene and D. E. Knuth, Mathematics for the Analysis of Algorithms; see pp. 95-98." I don't have the book handy to see whether it answers the questions. $\endgroup$
    – Gerry Myerson
    Commented Nov 21, 2016 at 21:52
  • $\begingroup$ Looking at maximal gaps (so we have first occurrence of gap g has g many rough numbers below n), my unverified program has (7,8), (9,374), (10,1116), (12,1421), (13,2940), (16,6992), all the way up to (40,26173683). I am finding some of these gaps do not have any 3 mod 4 primes in them. I am now hoping for C(n) to be O(log n). Gerhard "Still Hoping And Hanging On" Paseman, 2016.11.21. $\endgroup$
    – Gerhard Paseman
    Commented Nov 21, 2016 at 23:43

1 Answer 1

Reset to default
2
$\begingroup$

The local behaviour of smooth numbers is extremely difficult.

If $p\equiv 3\pmod{4}$ is prime, and $n$ is the least quadratic non-residue modulo $p$, then all integers with prime factors $<n$ are squares modulo $p$. In particular, since $p-1, p-2, \ldots, p-n+1$ are non-residues, we have that $n-1$-smooth numbers have a gap of length $n-1$ below $p$. The best bound we have for $n$ is $p^{\frac{1}{4\sqrt{e}}+\varepsilon}$, so for all we know there could be gaps of $x^{0.15}$-smooth numbers below $x$ of length $x^{0.15}$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Interesting! I will run some computations to see how things look for small numbers. Would the assumption that $C(n)$ is $O((\log(n))^\alpha)$ contradict ( or be as strong as) any conjectured or proved results? I am having trouble believing the growth would be $\Omega(n^\alpha)$ instead. Also, just for clarity, it's "the best upper bound we have for n", right? Gerhard "Somewhat Ignorant Regarding Quadratic Non-Residues" Paseman, 2016.11.21. $\endgroup$
    – Gerhard Paseman
    Commented Nov 21, 2016 at 22:18
  • $\begingroup$ It is widely believed that the distribution of smooth numbers can be modeled by a random variable. In particular the maximal distance between $x^c$-smooth numbers should be $\mathcal{O}_c(\log x)$, and the density in short intervals should be the same as in long intervals. This conjucture fits the numerical data, and is successfully applied in computational number theory, but proving any non-trivial result is extremely difficult. $\endgroup$
    – Jan-Christoph Schlage-Puchta
    Commented Nov 22, 2016 at 9:07
  • $\begingroup$ I'm slowly working my way through Granville's MSRI survey from 2008 "Smooth numbers: computational number theory and beyond". Is there a reference you would recommend in addition to this? Gerhard "Looking For A Good Read" Paseman, 2016.11.22. $\endgroup$
    – Gerhard Paseman
    Commented Nov 22, 2016 at 18:31
  • $\begingroup$ I would recommend Tenenbaum's "Introduction to analytic and probabilistic number theory" (Chapter III.5) and Moree's "Psixyology and diophantine equations". However, it appears that both texts are not availabe online. $\endgroup$
    – Jan-Christoph Schlage-Puchta
    Commented Nov 23, 2016 at 10:05

You must log in to answer this question.

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