The V AMMCS International Conference

Waterloo, Ontario, Canada | August 18-23, 2019

AMMCS 2019 Plenary Talk

New Results on the Erdős-Selfridge Function

Jon Sorenson (Butler University)

Let g(k) be the smallest integer larger than k+1 such that the binomial coefficient C(g(k),k) has no prime divisors ≤k. So for example, we have g(2)=5, since C(5,2)=15, and 15's smallest prime divisor is 3. Also we have g(3)=g(4)=7, since C(7,3)=C(7,4)=35, and 35's smallest prime divisor is 5. The problem of estimating g(k) has interested number theorists since Paul Erdős introduced the problem back in 1969. For example, Richard Guy mentions the problem in his well-known book Unsolved Problems in Number Theory. Ecklund, Erdős, and Selfridge published the first paper on this problem back in 1974, where they proved upper and lower bounds on g(k), stated several conjectures on its behavior, and tabulated g(k) for k up to 40, plus g(42), g(46), and g(52). The best current upper bound, g(k) < exp[k(1+o(1))], is from this same 1974 paper. The best current lower bound, g(k) > exp[c(log k)2] for an absolute constant c>0, is due to Konyagin (1999). Others who published lower bounds for g(k), all in the 1990s, include Lacampagne, Granville, and Ramaré.

Scheidler and Williams (1992) described how to use Kummer's theorem to construct a sieving algorithm to compute g(k), and computed g(k) for all k≤140. Finally, Lukes, Scheidler, and Williams (1997) improved their sieve and computed g(k) for all k≤200. A complete table of known values of g(k) is available from the Online Encyclopedia of Integer Sequences (A003458) at

In this talk, we present some new results and work-in-progress on g(k). We have a new sieve algorithm to compute g(k), based on a wheel datastructure that was used previously to find pseudosquares, pseudoprimes, and primes in patterns. This algorithm runs in time sublinear in g(k), and we used it to find g(k) for all k up to 272 so far. In particular we have

g(272) = 57 61284 34192 78614 55093 37498.

Let M=M(k) be the product of the primes p≤k, raised to the power ⌊ logp k ⌋+1, and let R=R(k) be the number of acceptable residues modulo M under Kummer's theorem. Our unproven Uniform Distribution Heuristic states that the smallest acceptable residue modulo M is roughly M/R, which implies that

log g(k) = log (M/R) + O(log k)

with high "probability". We then show unconditionally that log(M/R) is roughly k/log k, or more specifically, that the ratio of log(M/R) over k/log k is, in the limit, at least (1-log 2)/2, and at most 2. The data from our computations supports this so far, and in fact, our data implies that 

g(k) ≈ exp[ 1.19 k/log k ].

This is joint work with Brianna Sorenson (undergraduate student) and Jonathan Webster, both of Butler University.
Jonathan Sorenson graduated from the University of Wisconsin-Madison in 1991 with a Ph.D. in Computer Science and an M.S. in Mathematics. He has taught at Butler University in Indianapolis, Indiana since then. He was promoted to Professor in 2004 and became chair of Computer Science and Software Engineering in 2005. Jon won college-level awards as Natural Science Faculty Member of the Year in 2007, and Outstanding Teacher in 2014. Jon's research focuses on the design and analysis of sequential and parallel algorithms for problems in number theory, including computing integer greatest common divisors, counting smooth numbers, and sieving for primes, pseudoprimes, pseudosquares, and perfect powers. He recently served as co-chair of the program committee and co-editor of the proceedings volume for ANTS XIII.