John Selfridge
John Lewis Selfridge (February 17, 1927 – October 31, 2010[1]), was an American mathematician who contributed to the fields of analytic number theory, computational number theory, and combinatorics.
John Selfridge | |
---|---|
Born | Ketchikan, Alaska, United States | February 17, 1927
Died | October 31, 2010 83) [1] DeKalb, Illinois, United States | (aged
Nationality | American |
Alma mater | University of California, Los Angeles |
Scientific career | |
Fields | Analytic number theory |
Institutions | University of Illinois at Urbana-Champaign Northern Illinois University |
Doctoral advisor | Theodore Motzkin |
Education
Selfridge received his Ph.D. in 1958 from the University of California, Los Angeles under the supervision of Theodore Motzkin.[2]
Career
Selfridge served on the faculties of the University of Illinois at Urbana-Champaign and Northern Illinois University (NIU) from 1971 to 1991 (retirement), chairing the NIU Department of Mathematical Sciences 1972–1976 and 1986–1990. He was executive editor of Mathematical Reviews from 1978 to 1986, overseeing the computerization of its operations.[3] He was a founder of the Number Theory Foundation,[4] which has named its Selfridge prize in his honour.
Research
In 1962, he proved that 78,557 is a Sierpinski number; he showed that, when k = 78,557, all numbers of the form k2n + 1 have a factor in the covering set {3, 5, 7, 13, 19, 37, 73}. Five years later, he and Sierpiński proposed the conjecture that 78,557 is the smallest Sierpinski number, and thus the answer to the Sierpinski problem. A distributed computing project called Seventeen or Bust is currently trying to prove this statement, as of April 2017 only five of the original seventeen possibilities remain.
In 1964, Selfridge and Alexander Hurwitz proved that the 14th Fermat number was composite. [5] However, their proof did not provide a factor. It was not until 2010 that the first factor of the 14th Fermat number was found. [6] [7]
In 1975 John Brillhart, Derrick Henry Lehmer, and Selfridge developed a method of proving the primality of p given only partial factorizations of p − 1 and p + 1. [8] Together with Samuel Wagstaff they also all participated in the Cunningham project.
Together with Paul Erdős, Selfridge solved a 150-year-old problem, proving that the product of consecutive numbers is never a power.[9] It took them many years to find the proof, and John made extensive use of computers, but the final version of the proof requires only a modest amount of computation, namely evaluating an easily computed function f(n) for 30,000 consecutive values of n. Selfridge suffered from writer's block and thanked "R. B. Eggleton for reorganizing and writing the paper in its final form".[9]
Selfridge also developed the Selfridge–Conway discrete procedure for creating an envy-free cake-cutting among three people. Selfridge developed this in 1960, and John Conway independently discovered it in 1993. Neither of them ever published the result, but Richard Guy told many people Selfridge's solution in the 1960s, and it was eventually attributed to the two of them in a number of books and articles.
Selfridge's conjecture about Fermat numbers
Selfridge made the following conjecture about the Fermat numbers Fn = 22n + 1 . Let g(n) be the number of distinct prime factors of Fn (sequence A046052 in the OEIS). As to 2016, g(n) is known only up to n = 11, and it is monotonic. Selfridge conjectured that contrary to appearances, g(n) is NOT monotonic. In support of his conjecture he showed: a sufficient (but not necessary) condition for its truth is the existence of another Fermat prime beyond the five known (3, 5, 17, 257, 65537).[10]
Selfridge's conjecture about primality testing
This conjecture is also called the PSW conjecture, after Selfridge, Carl Pomerance, and Samuel Wagstaff.
Let p be an odd number, with p ≡ ± 2 (mod 5). Selfridge conjectured that if
- 2p−1 ≡ 1 (mod p) and at the same time
- fp+1 ≡ 0 (mod p),
where fk is the kth Fibonacci number, then p is a prime number, and he offered $500 for an example disproving this. He also offered $20 for a proof that the conjecture was true. The Number Theory Foundation will now cover this prize. An example will actually yield you $620 because Samuel Wagstaff offers $100 for an example or a proof, and Carl Pomerance offers $20 for an example and $500 for a proof. Selfridge requires that a factorization be supplied, but Pomerance does not. The related test that fp−1 ≡ 0 (mod p) for p ≡ ±1 (mod 5) is false and has e.g. a 6-digit counterexample.[11][12] The smallest counterexample for +1 (mod 5) is 6601 = 7 × 23 × 41 and the smallest for −1 (mod 5) is 30889 = 17 × 23 × 79. It should be known that a heuristic by Pomerance may show this conjecture is false (and therefore, a counterexample should exist).
See also
References
- "John Selfridge (1927–2010)". DeKalb Daily Chronicle. November 11, 2010. Retrieved November 13, 2010.
- John Selfridge at the Mathematics Genealogy Project
- "Chinese Acrobatics, an Old-Time Brewery, and the "Much Needed Gap": The Life of Mathematical Reviews" (PDF). ams.org. 1997-03-01. Retrieved 2023-05-04.
- "Math Times, Fall 2007". Archived from the original on 2011-06-05.
- J. L. Selfridge; A. Hurwitz (January 1964). "Fermat numbers and Mersenne numbers". Math. Comput. 18 (85): 146–148. doi:10.2307/2003419. JSTOR 2003419.
- Rajala, Tapio (3 February 2010). "GIMPS' second Fermat factor!". Retrieved 9 April 2017.
- Keller, Wilfrid. "Fermat factoring status". Retrieved 11 April 2017.
- John Brillhart; D. H. Lehmer; J. L. Selfridge (April 1975). "New Primality Criteria and Factorizations of 2m ± 1". Math. Comput. 29 (130): 620–647. doi:10.1090/S0025-5718-1975-0384673-1. JSTOR 2005583.
- Erdös, P.; Selfridge, J. L. (1975-06-01). "The product of consecutive integers is never a power". Illinois Journal of Mathematics. Duke University Press. 19 (2). doi:10.1215/ijm/1256050816. ISSN 0019-2082.
- Prime Numbers: A Computational Perspective, Richard Crandall and Carl Pomerance, Second edition, Springer, 2011 Look up Selfridge's Conjecture in the Index.
- According to an email from Pomerance.
- Carl Pomerance, Richard Crandall, Prime Numbers: A Computational Perspective, Second Edition, p. 168, Springer Verlag, 2005.
Publications
- Pirani, F. A. E.; Moser, Leo; Selfridge, John (1950). "Elementary Problems and Solutions: Solutions: E903". Am. Math. Mon. 57 (8): 561–562. doi:10.2307/2307953. JSTOR 2307953. MR 1527674.
- Carl Pomerance; John L. Selfridge; Samuel S. Wagstaff, Jr. (July 1980). "The pseudoprimes to 25·109" (PDF). Math. Comput. 35 (151): 1003–1026. doi:10.1090/S0025-5718-1980-0572872-7. JSTOR 2006210.
- Eggan, L. C.; Eggan, Peter C.; Selfridge, J. L. (1982). "Polygonal products of polygonal numbers and the Pell equation". Fibonacci Q. 20 (1): 24–28. MR 0660755.
- Erdos, P; Selfridge, J. L. (1982). "Another property of 239 and some related questions". Congr. Numer.: 243–257. MR 0681710.
- Lacampagne, C. B.; Selfridge, J. L. (1985). "Large highly powerful numbers are cubeful" (PDF). Rocky Mt. J. Math. 15 (2): 459. doi:10.1216/rmj-1985-15-2-459. MR 0823257. S2CID 120373455.
- Lacampagne, C. B.; Selfridge, J. L. (1986). "Pairs of squares with consecutive digits". Math. Mag. 59 (5): 270–275. doi:10.2307/2689401. JSTOR 2689401. MR 0868804.
- Blair, W. D.; Lacampagne, C. B.; Selfridge, J. L. (1986). "Notes: Factoring Large Numbers on a Pocket Calculator". Am. Math. Mon. 93 (10): 802–808. doi:10.2307/2322936. JSTOR 2322936. MR 1540993.
- Guy, R. K.; Lacampagne, C. B.; Selfridge, J. L. (1987). "Primes at a glance". Math. Comput. 48 (177): 183–202. doi:10.1090/s0025-5718-1987-0866108-3. MR 0866108.
- Trench, William F.; Rodriguez, R. S.; Sherwood, H.; Reznick, Bruce A.; Rubel, Lee A.; Golomb, Solomon W.; Kinnon, Nick M.; Erdos, Paul; Selfridge, John (1988). "Problems and Solutions: Elementary Problems: E3243–E3248". Am. Math. Mon. 95 (1): 50–51. doi:10.2307/2323449. JSTOR 2323449. MR 1541238.
- Erdos, P.; Lacampagne, C. B.; Selfridge, J. L. (1988). "Prime factors of binomial coefficients and related problems". Acta Arith. 49 (5): 507–523. doi:10.4064/aa-49-5-507-523. MR 0967334.
- Bateman, P. T.; Selfridge, J. L.; Wagstaff, S. S. (1989). "The New Mersenne conjecture". Am. Math. Mon. 96 (2): 125–128. doi:10.2307/2323195. JSTOR 2323195. MR 0992073.
- Lacampagne, C. B.; Nicol, C. A.; Selfridge, J. L. (1990). "Sets with nonsquarefree sums". Number Theory. de Gruyter. pp. 299–311.
- Howie, John M.; Selfridge, J. L. (1991). "A semigroup embedding problem and an arithmetical function". Math. Proc. Camb. Philos. Soc. 109 (2): 277–286. Bibcode:1991MPCPS.109..277H. doi:10.1017/s0305004100069747. MR 1085395. S2CID 120671857.
- Eggleton, R. B.; Lacampagne, C. B.; Selfridge, J. L. (1992). "Eulidean quadratic fields". Am. Math. Mon. 99 (9): 829–837. doi:10.2307/2324118. JSTOR 2324118. MR 1191702.
- Erdos, P.; Lacampagne, C. B.; Selfridge, J. L. (1993). "Estimates of the least prime factor of a binomial coefficient". Math. Comput. 61 (203): 215–224. Bibcode:1993MaCom..61..215E. doi:10.1090/s0025-5718-1993-1199990-6. MR 1199990.
- Lin, Cantian; Selfridge, J. L.; Shiue, Peter Jau-shyong (1995). "A note on periodic complementary binary sequences". J. Comb. Math. Comb. Comput. 19: 225–29. MR 1358509.
- Blecksmith, Richard; McCallum, Michael; Selfridge, J. L. (1998). "3-smooth representations of integers". Am. Math. Mon. 105 (6): 529–543. doi:10.2307/2589404. JSTOR 2589404. MR 1626189.
- Blecksmith, Richard; Erdos, Paul; Selfridge, J. L. (1999). "cluster primes". Am. Math. Mon. 106 (1): 43–48. doi:10.2307/2589585. JSTOR 2589585. MR 1674129.
- Erdos, Paul; Malouf, Janice L.; Selfridge, J. L.; Szekeres, Esther (1999). "Subsets of an interval whose product is a power". Discrete Math. 200 (1–3): 137–147. doi:10.1016/s0012-365x(98)00332-x. MR 1692286.
- Granville, Andrew; Selfridge, J. L. (2001). "Product of integers in an interval, modulo squares". Electron. J. Comb. 8 (1): #R5. doi:10.37236/1549. MR 1814512.