On comparing two almost injective divisor maps

Question

Edit 2018.08.08 This answer https://mathoverflow.net/a/307881 will be updated to give recent information about S, especially a forthcoming preprint. End Edit 2018.08.08

In an introductory post on Grimm Machines, I give a narrative to suggest why the following link between a given algorithm S and Grimm's conjecture should be studied. In this post, I give a summary (as suggested by Wlodzimierz Holsztynski) as well as new information and a new technical question.

Let a map $f$ on natural numbers greater than 1 be called a divisor map if for every $n$ one has $f(n)$ divides $n$. This post looks at divisor maps which take on prime values. For such maps $f(2)=f(4)=2$, so $f$ is not injective, not even when restricted to the interval $[2,4]$.

This post looks at maximal prime-free intervals, i.e. for each pair of consecutive primes $p$ and $q$, let $I=(p,q)$. If for every such $I$, $f$ restricted to $I$ is injective, then I call $f$ an injective divisor map, and Grimm's conjecture effectively asks if such a map exists. (Technically, Grimm asked about subintervals of such $I$ as well. By Bertrand's postulate or other results, a map for $(p,q)$ implies one for $[p,q]$ and possibly larger intervals.)

The algorithm S has been described in detail elsewhere. Briefly, consider at the start $n=2$ and the natural numbers $\geq n$ having a stone on each prime $p$ labeled with that prime, then find $n+kp \gt n$ least without a stone and move that stone there; now repeat with $n+1$. Each number gets paired with exactly one stone, and the map from numbers to the labels gives a divisor map $S(n)$, which is almost an injective divisor map. The other post discusses where $S(n)$ is known not to be injective, and how to modify it to be injective on the known portion.

A different map is given by $L(n)$, the largest prime divisor of $n$. Below $4*10^8$ it has over three hundred failures of injectivity; each failed interval with one exception (with smooth $n,L(n)$ pairs 265635,17, 264639,41, 265650,23, 265680, 41, and 265696,23) has precisely one point of failure, and the largest number of smooth $n$ in a failed interval which contains another multiple of $L(n)$ in that interval is 7, giving much room for fixing the map. Further, most of the intervals yield to an obvious Case II fix. I counted those intervals where a potential conflict might arise (is $L(m)$ a non-largest prime factor of $n$ for smooth $m$ and $n$ in the interval) and found less than twenty such intervals. Since most such failures are resolved by $S(n)$, I did not bother to find resolutions for these potential conflicts.

Of course more references are wanted, and questions regarding S in the other post can be asked about $L$ here. However, I point out a few specific questions about $L$ and the statistics gathered.

Why does $L$ do a much worse job than S in providing a Grimm mapping? Can we estimate how much worse?

Notice the embarrassing example (523,541) has a Case II (even Case I) fix now. Are all the failures fixable by case II?

Suppose we just look for improvements. Can we find a natural definition of a divisor map which (for the first $10^9$ intervals) does better than $L$? Better than S?

A combination (pick $L$ or S, which ever gives an injective map) leaves only 6 intervals all less than 1,000,000 in doubt, and each of those 6 is easily fixed, most of them by case I. However, this is not as natural a method as I would hope.

After browsing through papers of Erdos, Laisham and Murty, and Zhang, I found some generalizations of Grimm's conjecture being considered. I recommend the Laisham and Murty paper for an overview, where is mentioned that Grimm's conjecture implies the existence of a prime between consecutive squares. Grimm's conjecture along with a conjecture on smooth numbers implies a bound on prime gaps eventually strictly smaller than $p^\epsilon$ for every fixed real $\epsilon \gt 0$.

The literature shows connections to smooth numbers, prime gaps, number of factors of binomial coefficients and so on, and has a connection to another MathOverflow question Prime divisors of the respectively minimal binomial coefficients

• http://arxiv.org/abs/1306.0765 Laisham, Murty: Grimm's Conjecture and Smooth Numbers

• http://arxiv.org/abs/0811.0966 Shaohua Zhang : A Refinement of the function g(m) on Grimm conjecture

Edit 2016.08.24 At W.H.'s polite request, I revised the title. I ran computations for $L$ out to $1.6*10^9$ and found about 100 additional intervals on which $L$ is not injective. I will try a modified version that combines S and $L$ and report back. It seems many (maybe all but one?) of the $L$ intervals have a Case I fix, because there are very few smooth numbers between consecutive primes, and powers of 2 seem to avoid most of the problematic intervals. Until another natural divisor map suggests itself to me as being a good candidate for a Grimm map, I am going with a modified version which runs S and $L$ and uses S unless $L$ works better.

I have a part of an idea which suggests why S works better. Every jump of a prime $p$ for a distance $kp$ requires that its target $n+kp$ have its largest prime factor at most $kp$. Thus small primes tend to skip over nonsmooth numbers in a fashion where I am trying to quantify nonsmooth. In any case, $L$ fails to be injective through multiples of many pairs of consecutive or nearby pairs of smooth numbers, while $S$ fails to be injective due to short jumps of a prime when longer jumps might normally be expected. END Edit 2016.08.24.

Gerhard "Matchmaker Find Me A Find" Paseman, 2016.08.23.

Answer 1

Jose Brox has investigated and reported on a few algorithms for generating Grimm maps. I will update this answer later with a link. One algorithm essentially works on an interval of composites and (working from greatest to smallest) assigns the largest available prime number that divides the integer. (Actually, it is a little more subtle, working only on those intervals that aren't automatically provided a map by a theorem of M. Langevin. I may expand on these subtleties later.) Edit 2018.10.21 Here is the promised link. Apologies for the delay! Link to EACA slides of Jose End Edit 2018.10.21

I am also using this space to list some updates on the problem that I included in the Short Communication at ICM2018. Briefly, S was run up to 10^12, with the last two failures at 5^13 with a jump of 5 and 23^7 with a jump of 23, which means no failures found in [4*10^9,10^12]. Also, computations on $f_2$ and modifications I call $g^p$ were performed: $f_2(n)$ is $O(n^{0.44})$ in the observed range and suggests $O(n^\epsilon)$ is appropriate to conjecture as the actual order of growth, and $g^p$ appear to be the same order of growth as $f_2$ away from powers of $p$, contrary to what was hoped. Also $f_2$ (and also $g_p$ for $n$ not below and close to a power of $p$) is much bigger than needed for an upper bound for the jump sizes made by $S$.

I am also using this to herald the companion paper, which has not made it to Arxiv yet. Some other items to be included: a mild extension to Langevin's result that an injective prime divisor map exists on certain arithmetic progressions of length n, where the extension is that the progression is allowed to contain one large divisor of lcm(1...n); a proof of the repetition of the version of S where finitely many primes are used; an explicit upper bound on f_2 after Erdos and Selfridge; and suggestions for further research.

To those who discussed this work with me in Rio, many thanks for your time and patience. I intend to reward it soon with an enjoyable account. Thanks again to MathOverflow for allowing me to ask and answer such questions here.

Gerhard "Also Looking Forward To Write-up" Paseman, 2018.08.08.