Gillies' conjecture

Last updated October 23, 2021

In number theory, Gillies' conjecture is a conjecture about the distribution of prime divisors of Mersenne numbers and was made by Donald B. Gillies in a 1964 paper^[1] in which he also announced the discovery of three new Mersenne primes. The conjecture is a specialization of the prime number theorem and is a refinement of conjectures due to I. J. Good ^[2] and Daniel Shanks.^[3] The conjecture remains an open problem: several papers give empirical support, but it disagrees with the widely accepted (but also open) Lenstra–Pomerance–Wagstaff conjecture.

The conjecture

{\text{If }}

A<B<{\sqrt {M_{p}}}{\text{, as }}B/A{\text{ and }}M_{p}\rightarrow \infty {\text{, the number of prime divisors of }}M

{\text{ in the interval }}[A,B]{\text{ is Poisson-distributed with}}

{\text{mean }}\sim {\begin{cases}\log(\log B/\log A)&{\text{ if }}A\geq 2p\\\log(\log B/\log 2p)&{\text{ if }}A<2p\end{cases}}

He noted that his conjecture would imply that

The number of Mersenne primes less than $x$ is $~{\frac {2}{\log 2}}\log \log x$ .
The expected number of Mersenne primes $M_{p}$ with $x\leq p\leq 2x$ is $\sim 2$ .
The probability that $M_{p}$ is prime is $~{\frac {2\log 2p}{p\log 2}}$ .

Incompatibility with Lenstra–Pomerance–Wagstaff conjecture

The Lenstra–Pomerance–Wagstaff conjecture gives different values:^[4]^[5]

The number of Mersenne primes less than $x$ is $~{\frac {e^{\gamma }}{\log 2}}\log \log x$ .
The expected number of Mersenne primes $M_{p}$ with $x\leq p\leq 2x$ is $\sim e^{\gamma }$ .
The probability that $M_{p}$ is prime is $~{\frac {e^{\gamma }\log ap}{p\log 2}}$ with a = 2 if p = 3 mod 4 and 6 otherwise.

Asymptotically these values are about 11% smaller.

Results

While Gillie's conjecture remains open, several papers have added empirical support to its validity, including Ehrman's 1964 paper.^[6]

Related Research Articles

In number theory, a Carmichael number is a composite number $which satisfies the modular arithmetic congruence relation:$

In number theory, integer factorization is the decomposition of a composite number into a product of smaller integers. If these factors are further restricted to prime numbers, the process is called prime factorization.

Prime number Positive integer with exactly two divisors, 1 and itself

A prime number is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways of writing it as a product, 1 × 5 or 5 × 1, involve 5 itself. However, 4 is composite because it is a product in which both numbers are smaller than 4. Primes are central in number theory because of the fundamental theorem of arithmetic: every natural number greater than 1 is either a prime itself or can be factorized as a product of primes that is unique up to their order.

In number theory, a perfect number is a positive integer that is equal to the sum of its positive divisors, excluding the number itself. For instance, 6 has divisors 1, 2 and 3, and 1 + 2 + 3 = 6, so 6 is a perfect number.

The Liouville Lambda function, denoted by λ(n) and named after Joseph Liouville, is an important arithmetic function. Its value is +1 if n is the product of an even number of prime numbers, and −1 if it is the product of an odd number of primes.

The Lenstra elliptic-curve factorization or the elliptic-curve factorization method (ECM) is a fast, sub-exponential running time, algorithm for integer factorization, which employs elliptic curves. For general-purpose factoring, ECM is the third-fastest known factoring method. The second-fastest is the multiple polynomial quadratic sieve, and the fastest is the general number field sieve. The Lenstra elliptic-curve factorization is named after Hendrik Lenstra.

A primality test is an algorithm for determining whether an input number is prime. Among other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating whether the input number is prime or not. Factorization is thought to be a computationally difficult problem, whereas primality testing is comparatively easy. Some primality tests prove that a number is prime, while others like Miller–Rabin prove that a number is composite. Therefore, the latter might more accurately be called compositeness tests instead of primality tests.

The Miller–Rabin primality test or Rabin–Miller primality test is a probabilistic primality test: an algorithm which determines whether a given number is likely to be prime, similar to the Fermat primality test and the Solovay–Strassen primality test.

In number theory, a Wieferich prime is a prime number p such that p² divides $2 p - 1 - 1$ , therefore connecting these primes with Fermat's little theorem, which states that every odd prime p divides $2 p - 1 - 1$ . Wieferich primes were first described by Arthur Wieferich in 1909 in works pertaining to Fermat's Last Theorem, at which time both of Fermat's theorems were already well known to mathematicians.

A Wilson prime, named after English mathematician John Wilson, is a prime number p such that p² divides (p − 1)! + 1, where "!" denotes the factorial function; compare this with Wilson's theorem, which states that every prime p divides (p − 1)! + 1.

In number theory, the Mertens function is defined for all positive integers n as

In mathematics, a harmonic divisor number, or Ore number, is a positive integer whose divisors have a harmonic mean that is an integer. The first few harmonic divisor numbers are:

Richard Peirce Brent is an Australian mathematician and computer scientist. He is an emeritus professor at the Australian National University and a conjoint professor at the University of Newcastle (Australia). From March 2005 to March 2010 he was a Federation Fellow at the Australian National University. His research interests include number theory, random number generators, computer architecture, and analysis of algorithms.

In number theory, a practical number or panarithmic number is a positive integer $such that all smaller positive integers can be represented as sums of distinct divisors of . For example, 12 is a practical number because all the numbers from 1 to 11 can be expressed as sums of its divisors 1, 2, 3, 4, and 6: as well as these divisors themselves, we have 5 = 3 + 2, 7 = 6 + 1, 8 = 6 + 2, 9 = 6 + 3, 10 = 6 + 3 + 1, and 11 = 6 + 3 + 2.$

The following tables list the computational complexity of various algorithms for common mathematical operations.

In analytic number theory, the Dickman function or Dickman–de Bruijn functionρ is a special function used to estimate the proportion of smooth numbers up to a given bound. It was first studied by actuary Karl Dickman, who defined it in his only mathematical publication, and later studied by the Dutch mathematician Nicolaas Govert de Bruijn.

In mathematics, the Mersenne conjectures concern the characterization of prime numbers of a form called Mersenne primes, meaning prime numbers that are a power of two minus one.

In mathematics, Montgomery's pair correlation conjecture is a conjecture made by Hugh Montgomery (1973) that the pair correlation between pairs of zeros of the Riemann zeta function is

References

↑ Donald B. Gillies (1964). "Three new Mersenne primes and a statistical theory". Mathematics of Computation. 18 (85): 93–97. doi: 10.1090/S0025-5718-1964-0159774-6 .
↑ I. J. Good (1955). "Conjectures concerning the Mersenne numbers". Mathematics of Computation. 9 (51): 120–121. doi: 10.1090/S0025-5718-1955-0071444-6 .
↑ Shanks, Daniel (1962). Solved and Unsolved Problems in Number Theory. Washington: Spartan Books. p. 198.
↑ Samuel S. Wagstaff (1983). "Divisors of Mersenne numbers". Mathematics of Computation. 40 (161): 385–397. doi: 10.1090/S0025-5718-1983-0679454-X .
↑ Chris Caldwell, Heuristics: Deriving the Wagstaff Mersenne Conjecture. Retrieved on 2017-07-26.
↑ John R. Ehrman (1967). "The number of prime divisors of certain Mersenne numbers". Mathematics of Computation. 21 (100): 700–704. doi: 10.1090/S0025-5718-1967-0223320-1 .

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Donald B. Gillies (1964). "Three new Mersenne primes and a statistical theory". Mathematics of Computation. 18 (85): 93–97. doi: 10.1090/S0025-5718-1964-0159774-6 .

[2] I. J. Good (1955). "Conjectures concerning the Mersenne numbers". Mathematics of Computation. 9 (51): 120–121. doi: 10.1090/S0025-5718-1955-0071444-6 .

[3] Shanks, Daniel (1962). Solved and Unsolved Problems in Number Theory. Washington: Spartan Books. p. 198.

[4] Samuel S. Wagstaff (1983). "Divisors of Mersenne numbers". Mathematics of Computation. 40 (161): 385–397. doi: 10.1090/S0025-5718-1983-0679454-X .

[heur-5] Chris Caldwell, Heuristics: Deriving the Wagstaff Mersenne Conjecture. Retrieved on 2017-07-26.

[6] John R. Ehrman (1967). "The number of prime divisors of certain Mersenne numbers". Mathematics of Computation. 21 (100): 700–704. doi: 10.1090/S0025-5718-1967-0223320-1 .

[1]

[2]

[3]

[4]

[5]

[6]