A faster way to spoil an injection?

Question

Ultimately this is about how primes jump. I will abstract the situation somewhat as there may be related applications which do not spring to my mind.

I want to find small spoilers to Hall's Marriage Theorem for a specific situation. As the index i increases, I will be processing a sequence S_i of subsets of Y, and I want to find the smallest i such that I cannot find an injective map from the subset of indices I processed so far into the union of the S_i such that every i maps to a member of S_i. Here is one way to go about it.

I create an arrangement of tallies for each subset of Y, and set them all to 0. Each time I encounter a set S_i, I increase the tally by 1 for that subset and also for each subset containing S_i. As I do this, if the tally for some subset T goes above the number of elements of T, I stop, for then I have spoiled the injection by violating the marriage condition, and I have then found i.

Unfortunately, this involves a lot of tallies. Is there a faster way to reach the spoiling i ?

Here is my actual application, and a potentially faster way to reach it. I am given number N and I am looking for the smallest i such that there is no injective map f from [N+1,N+i] into the primes such that f(k) divides k. I start by setting p to 2 and generating the smallest p-smooth numbers above N, and stop when I have 2 of them. I advance p to the next (jth ) prime and repeat, lowering my upper bound for I when I have 1 more than j many such smallest p-smooth numbers above N. I stop when the next prime is larger than the difference between N and the largest smooth number. I now have an upper bound on i, but need to do more work to find i. Again, is there a faster way to find the smallest i?

This is reminiscent of a reverse game of Chomp on a certain poset, and likely this corresponds to a type of cover problem, but I haven't put my finger on which type. Maybe register allocation or something in operations research? Suitable references are welcome.

Gerhard "Looking To Break Things Quicker" Paseman, 2017.04.30.

Answer 1

For the general problem, I do not have a quicker answer. For my application, a nice insight allows me to limit my search space, and provides a teachable moment.

Given N, an upper bound can be found slowly by using very smooth numbers. I do not have a proof, but the feeling is that the i in N+i shrinks like N/(log N)^{k-1} as I generate numbers larger than N whose prime factors are among the k smallest primes. This is the approach above.

However, there is a better bound, by taking not very smooth numbers, namely p^2, pq, and q^2, where p and q are the two smallest primes whose squares are strictly greater than N. I can now focus on a very narrow interval of length roughly $O(\sqrt{N}\log N)$, and sieve or use other methods for finding tight groupings of smooth numbers. I can even try forms like pqrs times five different but close factors for four appropriately chosen primes.

The idea is that going to a different extreme ("roughly smooth" as opposed to "very smooth") can be both quick and fruitful.

Gerhard "Cleverness Is A Learnable Skill" Paseman, 2017.05.02.

Answer 2

I have found a method which works well in finding a small spoiler and moves me toward my goal. It also introduces some additional questions on which I would like help.

After writing a comment above on using a series of consecutive squares (rather than squares of two consecutive primes) to improve my upper bound on i, I had two more thoughts on improving this bound. The first was that the squares did not need to be consecutive, just close together. Thus if one of the k numbers r+j had much more than the average number of factors, I could skip it and use a nearby number with many fewer factors. Thus it seems even more possible that I can keep k near 2 ln ln N, and thus bound i by k $\sqrt{N}$. The second was that I really only needed the prime factors from the squares and not the squares themselves. Moreover, the prime factors involved in the smooth numbers in a spoiling set came in pairs, and thus N+j is going to be i-smooth and sometimes j-smooth for j less than i.

This suggests the following algorithm given input N:

Set upperbound (on i) = 5*N (defensive programming)
Set i = 2 and Q the empty set.
While (N+i less than upperbound)
    If N+i is i-smooth
        add its distinct prime factors to the set Q, and 
        let s be 1 + cardinality of Q.
    Find the s many smallest numbers bigger than N 
        whose prime factors belong to Q.
    Set upperbound to  the largest of these s many Q-smooth numbers.
   Add 1 to i

As i increases, upperbound may also increase briefly as the new number may inspire Q-smooth numbers greater than upper bound to be added. However, s increases by at most the number of distinct prime factors of N+i that have not already appeared in Q; further, these prime factors are all at most i, so s is at most $\pi(i)$. Eventually $\pi(i) $ becomes one less than the count of i-smooth numbers before i gets as big as some absolute constant times $\sqrt{N}$, so we are guaranteed termination. Running a version of the algorithm above places i under $3\sqrt{N}$ for N less than 60000, and under $2\sqrt{N}$ once N goes above 99 (17192 for $\sqrt{N}$).

So I still hope for a faster way, but simulation now suggests that i is not much smaller than $\sqrt{N}$. Indeed, I am trying to judge if the growth is like $\pi(\sqrt{N})$.

Since I jotted the above notes, I read a 1971 paper of Erdos and Selfridge some problems on the prime factors of consecutive integers II. This gives an upper bound with asymptotic of $O((n/\log n)^{1/2})$ for the quantity of interest to me. I am running further computations to form a conjecture as to an explicit bound. I am also studying this and later papers to see if I can make the constants explicit. It seems that counting all prime factors does almost as well as guessing which smooth numbers to count. For those who read the 1971 paper, my focus has shifted slightly to analyzing the functions $f_0$ and $f_1$ in order to get a handle on $f_2$. A recent paper of Shorey and Laishram suggests an upper bound of order $n^c$ for $c$ a real number strictly less than 1/2.

All the new questions relate to updating references on the 1971 paper. Besides the Shorey and Laishram paper (2014, I think), does anyone know of recent work on $f_0$?

Gerhard "Many Functions And Little Time" Paseman, 2017.07.01.

Answer 3

Bipartite matching.

I am using a refactored version of an algorithm of Hopcroft and Karp found at https://en.wikipedia.org/wiki/Hopcroft–Karp_algorithm . I found that instead of reintializing the Pairu and Pairv arrays for each run, I can modify them from the previous run to take advantage of previous work. I may post AWK code here later after I have finished tweaking it. I do not have asymptotics for this version, but even running the algorithm every time a new index and set is added is better than cubic in the number of vertices for low degree situations, which is what I have (average set size is less than 4).

Gerhard "Spared No Rods For This" Paseman, 2017.10.26.