Newman's conjecture

Last updated
Newman's conjecture
Type conjecture
Field analytic number theory
Conjectured byMorris Newman
Conjectured in25 March 1960
Open problemYes
Known cases Prime powers except powers of 2 or powers of 3, plus selected other numbers (e.g. 16, 40, 65)
ConsequencesErdős-Ivić conjecture
Unsolved problem in mathematics:

Given arbitrary m, r, are there infinitely values of n such that the partition function at n is congruent to r mod m?

Contents

(more unsolved problems in mathematics)

In mathematics, specifically in number theory, Newman's conjecture is a conjecture about the behavior of the partition function modulo any integer. Specifically, it states that for any integers m and r such that , the value of the partition function satisfies the congruence for infinitely many non-negative integers n. It was formulated by mathematician Morris Newman in 1960. [1] It is unsolved as of 2020.

History

Oddmund Kolberg was probably the first to prove a related result, namely that the partition function takes both even and odd values infinitely often. The proof employed was of elementary nature and easily accessible, and was proposed as an exercise by Newman in the American Mathematical Monthly. [2] [3] [4]

1 year later, in 1960, Newman proposed the conjecture and proved the cases m=5 and 13 in his original paper, [1] and m=65 two years later. [5]

Ken Ono, an American mathematician, made further advances by exhibiting sufficient conditions for the conjecture to hold for prime m. He first showed that Newman's conjecture holds for prime m if for each r between 0 and m-1, there exists a nonnegative integer n such that the following holds:

He used the result, together with a computer program, to prove the conjecture for all primes less than 1000 (except 3). [6] Ahlgren expanded on his result to show that Ono's condition is, in fact, true for all composite numbers coprime to 6. [7]

Three years later, Ono showed that for every prime m greater than 3, one of the following must hold:

Using computer technology, he proved the theorem for all primes less than 200,000 (except 3). [8]

Afterwards, Ahlgren and Boylan used Ono's criterion to extend Newman's conjecture to all primes except possibly 3. [9] 2 years afterwards, they extended their result to all prime powers except powers of 2 or 3. [10]

Partial progress and solved cases

The weaker statement that has at least 1 solution has been proved for all m. It was formerly known as the Erdős–Ivić conjecture, named after mathematicians Paul Erdős and Aleksandar Ivić  [ de; pt ]. It was settled by Ken Ono. [6]

Related Research Articles

Modular arithmetic Computation modulo a fixed integer

In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his book Disquisitiones Arithmeticae, published in 1801.

The Collatz conjecture is a conjecture in mathematics that concerns sequences defined as follows: start with any positive integer n. Then each term is obtained from the previous term as follows: if the previous term is even, the next term is one half of the previous term. If the previous term is odd, the next term is 3 times the previous term plus 1. The conjecture is that no matter what value of n, the sequence will always reach 1.

In number theory, Euler's theorem states that if n and a are coprime positive integers, then a raised to the power of the totient of n is congruent to one, modulo n, or:

This article collects together a variety of proofs of Fermat's little theorem, which states that

In number theory, a probable prime (PRP) is an integer that satisfies a specific condition that is satisfied by all prime numbers, but which is not satisfied by most composite numbers. Different types of probable primes have different specific conditions. While there may be probable primes that are composite, the condition is generally chosen in order to make such exceptions rare.

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.

In modular arithmetic, a branch of number theory, a number g is a primitive root modulo n if every number a coprime to n is congruent to a power of g modulo n. That is, g is a primitive root modulo n, if for every integer a coprime to n, there is some integer k for which gk ≡ a. Such a value k is called the index or discrete logarithm of a to the base g modulo n. Note that g is a primitive root modulo n if and only if g is a generator of the multiplicative group of integers modulo n.

Partition function (number theory)

In number theory, the partition functionp(n) represents the number of possible partitions of a non-negative integer n. For instance, p(4) = 5 because the integer 4 has the five partitions 1 + 1 + 1 + 1, 1 + 1 + 2, 1 + 3, 2 + 2, and 4.

In number theory, a Wieferich prime is a prime number p such that p2 divides 2p − 1 − 1, therefore connecting these primes with Fermat's little theorem, which states that every odd prime p divides 2p − 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.

In number theory, a Wall–Sun–Sun prime or Fibonacci–Wieferich prime is a certain kind of prime number which is conjectured to exist, although none are known.

A strong pseudoprime is a composite number that passes the Miller–Rabin primality test. All prime numbers pass this test, but a small fraction of composites also pass, making them "pseudoprimes".

In mathematics, Wolstenholme's theorem states that for a prime number , the congruence

Carmichael function function of interest in number theory

In number theory, a branch of mathematics, the Carmichael function associates to every positive integer n a positive integer λ(n), defined as the smallest positive integer m such that

Ramanujan tau function

The Ramanujan tau function, studied by Ramanujan (1916), is the function defined by the following identity:

In additive number theory, Fermat's theorem on sums of two squares states that an odd prime p can be expressed as:

Gauss's lemma in number theory gives a condition for an integer to be a quadratic residue. Although it is not useful computationally, it has theoretical significance, being involved in some proofs of quadratic reciprocity.

A Giuga number is a composite number n such that for each of its distinct prime factors pi we have , or equivalently such that for each of its distinct prime factors pi we have .

In mathematics, Ramanujan's congruences are some remarkable congruences for the partition function p(n). The mathematician Srinivasa Ramanujan discovered the congruences

In mathematics, particularly in the area of number theory, a modular multiplicative inverse of an integer a is an integer x such that the product ax is congruent to 1 with respect to the modulus m. In the standard notation of modular arithmetic this congruence is written as

Mathukumalli (Matukumalli) Venkata Subbarao was an Indo-Canadian mathematician, specialising in number theory. He was a long-time resident of Edmonton, Alberta, Canada.

References

  1. 1 2 Newman, Morris (1960). "Periodicity Modulo m and Divisibility Properties of the Partition Function". Transactions of the American Mathematical Society. 97 (2): 225–236. doi:10.2307/1993300. ISSN   0002-9947. JSTOR   1993300.
  2. ↑ Subbarao, M. V. (1966). "Some Remarks on the Partition Function". The American Mathematical Monthly. 73 (8): 851–854. doi:10.2307/2314179. ISSN   0002-9890. JSTOR   2314179.
  3. ↑ Kolberg, O. (1959-12-01). "Note on the Parity of the Partition Functions". Mathematica Scandinavica. 7: 377–378. doi:10.7146/math.scand.a-10584. ISSN   1903-1807.
  4. ↑ Newman, Morris; van Lint, J. H. (1962). "4944". The American Mathematical Monthly. 69 (2): 175. doi:10.2307/2312568. ISSN   0002-9890. JSTOR   2312568.
  5. ↑ Newman, Morris (March 1962). "Congruences for the partition function to composite moduli". Illinois Journal of Mathematics. 6 (1): 59–63. doi: 10.1215/ijm/1255631806 . ISSN   0019-2082.
  6. 1 2 Ono, Ken (2000). "Distribution of the Partition Function Modulo m". Annals of Mathematics. 151 (1): 293–307. arXiv: math/0008140 . Bibcode:2000math......8140O. doi:10.2307/121118. ISSN   0003-486X. JSTOR   121118.
  7. ↑ Ahlgren, Scott (2000-12-01). "Distribution of the partition function modulo composite integers M". Mathematische Annalen. 318 (4): 795–803. doi:10.1007/s002080000142. ISSN   1432-1807.
  8. ↑ Bruinier, Jan H.; Ono, Ken (2003-03-01). "Coefficients of half-integral weight modular forms". Journal of Number Theory. 99 (1): 164–179. doi: 10.1016/S0022-314X(02)00061-6 . ISSN   0022-314X.
  9. ↑ Ahlgren, Scott; Boylan, Matthew (2003-09-01). "Arithmetic properties of the partition function". Inventiones Mathematicae. 153 (3): 487–502. Bibcode:2003InMat.153..487A. doi:10.1007/s00222-003-0295-6. ISSN   1432-1297.
  10. ↑ Ahlgren, Scott; Boylan, Matthew (2005-01-01). "Coefficients of half-integral weight modular forms modulo ℓj". Mathematische Annalen. 331 (1): 219–239. doi:10.1007/s00208-004-0555-9. ISSN   1432-1807.
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.