# On comparing two almost injective divisor maps

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

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.

• As it turns out, running L and S in parallel, and picking the injective map from S if it works, and otherwise picking the map from L and then applying case I (take the even number n and assign it 2 instead of L(n)) fixes all known problems below $4*10^8$. Is there a more natural way to produce a potential Grimm map? Gerhard "Matchmaker Catch Me A Catch" Paseman, 2016.08.23. – Gerhard Paseman Aug 24 '16 at 1:28
• Gerhard, you're very kind. Perhaps you may still make the title more attractive by modifying the first part of it or all together, like "Algorithms L & S. The prime choices (Grimm's conjecture)." (A short Perl code would be nice too :) ). – Włodzimierz Holsztyński Aug 24 '16 at 7:05
• A Grimm's Conjecture attractive corollary: Let $P$ be a finite set of primes, let $\ \pi:=|P|.\$ Then, for every sequence of integers $\ 1<a_0<\ldots<a_{\pi}\$ such that all prime divisors of the terms of this sequence belong to $P$ there exists a prime $p$ such that $\ a_0\le p\le a_n.\$ I guess, special cases of this statement may form quite a challenge. – Włodzimierz Holsztyński Aug 24 '16 at 7:55

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