Inspired by Zhang Yitang, a 17-year-old boy solves the world's number theory problems

Inspired by Zhang Yitang, a 17-year-old boy solves the world's number theory problems

While studying the paper on the twin prime problem, Daniel Larson mastered the mathematical method Maynard used to improve Zhang Yitang's research results, creatively applied this method, and ultimately proved a groundbreaking result on the distribution of Carmichael numbers.

Written by Wu Chaoyang (popular science writer, associate professor of the Department of Mathematics at Nanjing University)

Daniel Larsen, 17, caused a sensation last year for proving an important result about the distribution of Carmichael numbers and was hailed as a "genius boy" by the media. On October 18, 2023, as the revised manuscript of the paper was published online on the preprint website, Daniel Larsen once again attracted the attention of countless mathematics enthusiasts and some students' parents.

Along with Daniel Larsen, Carmichael numbers have also attracted the attention of mathematics enthusiasts. It is noteworthy that Daniel Larsen's proof is closely related to Zhang Yitang's research on the twin prime problem. This article focuses on the interesting Carmichael numbers and briefly tells the growth story of Daniel Larsen, the "genius boy".

"Coprime", "Congruence" and "Congruence Arithmetic"

To understand this story more completely, we need to first have a general understanding of some basic mathematical knowledge related to it.

The first thing you need to understand is prime numbers. Prime numbers are familiar to everyone. They are natural numbers greater than 1 but cannot be decomposed into the product of two factors greater than 1 (for ease of reading, all " numbers " in this article refer to natural numbers). For example, 2, 3, 5, 7, and 11 are all prime numbers. Numbers that are not prime but greater than 1 are called " composite numbers ". For example, 6 and 9 are both composite numbers because they can be written as 2⤫3 and 3⤫3 respectively.

Two numbers are said to be "co- prime " if they have no common factors, or if their "greatest common factor" is 1. For example, 8 and 11 are co-prime, but 6 and 9 are not co-prime; they have a common factor of 3.

Two other mathematical terms we need to understand are "congruence" and congruence arithmetic. In short, " congruence " means "same remainder", which means that two dividends have the same remainder with the same divisor - here, we don't care what the quotient is, we only care about the remainder. For example, with 6 as the divisor, the remainders of the dividends 14 and 8 are the same, so we say "14 and 8 are congruent modulo 6". We record this as

14 ≡ 8 mod (6).

The above expression is called a " congruence ", where mod (6) means that the common divisor of the numbers on both sides of the expression is 6, which is called the " modulus " of the congruence. For the same modulus m , if a ≡ b mod (m) and c ≡ d mod (m) both hold, then the congruence is

a + c ≡ b + d mod (m),

a - c ≡ b - d mod (m),

ac ≡ bd mod (m)

a^k ≡ b^k mod (m)

All of them are also true. Let us prove the third one:

Since c ≡ d mod (m) means that c and d have the same remainder when divided by m, c - d is equal to some multiple of m, that is, there exists an integer k such that c - d = mk. Thus,

ac – bd = a (km + d) – bd

= akm + ad – bd

= akm + d (a - b)

From the known condition a ≡ b mod (m), we know that a - b is divisible by m, therefore, ac - bd is also divisible by m, that is, ac ≡ bd mod (m).

The above three equations show that congruence expressions can be "normally calculated" like equations in terms of addition, subtraction, and multiplication. So, we know that "equations can be divided by equations", can congruence expressions be divided by equations? The answer is: No! Specific situations require specific analysis, and the analysis method is to write congruence expressions as division relations and use these division relations to consider the problem. Despite this, we can still get two simple conclusions:

First, if k and m are relatively prime, then we can use the congruence formula

ka ≡ kb mod (m),

Get the congruence

a ≡ b mod (m).

In other words, when k and m have no common factors, we can indeed "cancel" the factor k from both sides of the congruence.

Second, if k is a factor of m, or equivalently, if m = kn, then from the congruence ka ≡ kb mod (m) we get:

a ≡ b mod (n),

In this case, even the factors in the module m are "reduced" together.

Fermat's Little Theorem and Carmichael Numbers

Before we talk about the topic of this article, we must also introduce the famous " Fermat's Little Theorem ". One way to state this theorem is:

Fermat's Little Theorem: If p is a prime number and a is a natural number, then a^p - a is divisible by p , that is

a^p – a ≡ 0 mod(p)

Established.

Naturally, curious people will consider the propositions related to this theorem, among which the important propositions are the following two:

Proposition 1 : If n is such that the congruence

2^n – 2 ≡ 0 mod(n)

Then n must be a prime number.

Proposition 2 (the converse of Fermat's Little Theorem): If n is such that the congruence

a^n – a ≡ 0 mod(n)

Here is a small episode. During the Tongzhi and Guangxu years of the Qing Dynasty, a British diplomat named Thomas Wade (1818-1895) was stationed in China. Before the official introduction of Pinyin, the "Wade-Giles romanization" he invented was the most influential Pinyin scheme. Interestingly, Wade misheard someone and sent back a wrong message to Europe. He said that as early as the time of Confucius, the Chinese already had the following "theorem" about prime numbers:

Chinese hypothesis : If n is a prime number, then the congruence

2^n – 2 ≡ 0 mod(n)

On the contrary, if n makes the above congruence true, then n must be a prime number.

Obviously, the first half of the Chinese hypothesis is the corollary of Fermat's Little Theorem, and the second half is the aforementioned Proposition 1. In 1898, James Jeans (1877-1946) pointed out that the aforementioned Proposition 1 is wrong, and the smallest counterexample is 341. He pointed out that 341 = 11⤫31, which is a composite number, but,

2^5 = 32 ≡ 1 mod (31),

2^5 = 32 ≡ -1 mod (11),

so,

2^340 = (2^5)^68≡ 1^68 ≡ 1 mod (31),

2^340=(2^5)^68≡ (-1)^68 ≡ 1 mod (11),

therefore,

2^340 ≡ 1 mod (31⤫11),

2^341 ≡ 2 mod (31⤫11),

That is to say,

2^341- 2 ≡ 0 mod (341),

In 1899, after citing Jens's results, Alwin Korselt (1864-1947) further considered the aforementioned Proposition 2 and gave the following "Kosselt Criterion".

Cosselt's criterion : A natural number n such that the congruence

a^n – a ≡ 0 mod(n)

For all natural numbers a , it holds if and only if n has no square factors and for all prime factors of n , there is **

n–1 ≡ 0 mod(p-1).

From the perspective of Fermat's Little Theorem, composite numbers that satisfy the Cosselt criterion are very similar to prime numbers, so they are called " Fermat pseudoprimes ". In 1910, Robert Carmichael (1879-1967) pioneered the use of Euler's φ-function to study such pseudoprimes, proving that they have at least three prime factors, and gave specific Fermat pseudoprimes with three prime factors, such as 3⤫11⤫17, 5⤫13⤫17, 7⤫13⤫31, and 7⤫31⤫73. Out of respect for his pioneering research, the mathematical community has since called Fermat pseudoprimes " Carmichael numbers ".

In 1939, Jack Chernick (1911-1971) conducted an in-depth study of the product expressions of Carmichael numbers with three, four or more prime factors and obtained several important results. For Carmichael numbers with three prime factors, Chernick proved that they have the following form:

As long as there is a non-negative integer M such that (6M+1), (12M+1), and (18M+1) are all prime numbers, then the product of these three prime numbers, (6M+1)(12M+1)(18M+1), must be a Carmichael number. In fact, when M = 1, we get 7⤫13⤫19, which is indeed a Carmichael number.

There are many three-factor product formulas that can be used to search for Carmichael numbers, and the most common ones are:

To be fair, this research result is far from "solving a world problem" as some reports claim, but it is an extension of Chernik's research and a novel result.

Problem: Prove the Bernard–Chebyshev theorem for Carmichael numbers

From Chernik's research, we can see that for the same d, many Carmichael numbers are the product of a set of prime numbers of the form kd+1.

The number theory community records the number of prime numbers less than x as π(x), which is called the prime number counting function , and obtained the following important results very early:

π(x) ~ x / ln(x)

When d and a are relatively prime, all natural numbers of the form kd+a form an arithmetic progression. The number of prime numbers less than x is expressed as π(x; d, a). Then π(x, d, a) has a formula related to π(x):

π(x; d, a) ~ π(x) / φ(d)

Here, φ(d) is the Euler φ-function, that is, the number of natural numbers not exceeding d and coprime to d.

That is to say, in an arithmetic progression of natural numbers of the form kd+1, as long as x is large enough, the number of prime numbers less than x will at least reach the order of ln(x). The fewer the number of natural numbers that are coprime to d, the more prime numbers there are in the sequence.

Obviously, the more primes less than x there are of the form kd+1, the more likely it is that there is a Carmichael number that is equal to the product of several of those primes. The above prime number counting formula gives a strong hint that there are many Carmichael numbers of this form.

Anyone who studies Carmichael numbers knows that the Cosselt criterion has an important but easily proven consequence:

Assume ****S is a set of odd prime numbers, L is equal to the least common multiple of all numbers in the set { p-1 | p∈S **}. If Q is a subset of S , c is equal to the product of all prime numbers in Q , and c** **≡ 1 ( mod L ), then **c**** is a Carmichael number. **

If all the prime factors of a number are small, then it is what Ramanujan called a "highly composite number". When L is a highly composite number, it is relatively easy to check whether the congruence c **≡ 1 ( mod L )** is true. In 1992, Zhang Mingzhi of Sichuan University took L as a highly composite number and, based on the above inference, gave a new method for searching for huge Carmichael numbers.

Inspired by Zhang Mingzhi, applying the aforementioned counting formula for prime numbers of the form kd+1, Alford (William R. Alford, 1926 - 2022), Granville (Andrew Granville) and Pomerance (Carl Pomerance) proved in 1994 that for a sufficiently large highly composite number L, there exists a natural number d such that the remainders of the products of many groups of prime numbers of the form kd+1 modulo L are all equal to 1, and further proved that there are infinite Carmichael numbers.

Applying the previous counting results of the number of prime numbers from x^(1-E) to x, Alford et al. proved that for sufficiently large x, there are at least x^(*1/3)* Carmichael numbers not exceeding x.

The most concise description of the distribution law of prime numbers is the famous Bernard-Chebyshev theorem: for any natural number n greater than 2, there is at least one prime number between n and 2n.

The method of Alford et al. gives a lower bound on the number of Carmichael numbers in the interval [1, x] (when x is sufficiently large), but cannot prove the existence of Carmichael numbers in the second half of this interval, that is, [x/2, x]. The existence of Carmichael numbers in this second half of the interval is the Bernard-Chebyshev Theorem for Carmichael numbers. Alford et al. concluded that proving the Bernard-Chebyshev Theorem for Carmichael numbers would be an extremely difficult task. Following the ideas of Alford et al., the Bernard-Chebyshev Theorem for Carmichael numbers cannot be proved when only prime numbers of the form kd+1 are considered.

Daniel Larsen's research

It is only at this point that our protagonist appears.

Daniel Larsen proposed a bold idea: considering prime combinations of the form kd+1 and kd'+1 at the same time, perhaps it is possible to prove the existence of Carmichael numbers in [x/2, x]. Fortunately, James Maynard proposed an innovative method to improve Zhang Yitang's conclusion on twin primes, proving the distribution law of "prime pairs" x and x+h with an interval of h for h not less than 246. Daniel Larsen understood Maynard's paper and creatively applied Maynard's method to prime combinations of the form kd+1 and kd'+1, proving a lower limit on the frequency of kd+1 and kd'+1 being prime numbers for d and d' with a small difference.

Because of the large number of "prime pairs" of the form kd+1 and kd'+1, Daniel Larsen was able to use a modified version of the method of Alford et al. to prove the following groundbreaking result:

For any positive decimal ****δ **, and a sufficiently large natural number n that depends on δ , between n and **

Carmichael number .

If you think the above results are too complicated, we can summarize them into a weakened but simple and easy to remember result:

When n > 3300 , there is always a Carmichael number between n and 2n . And when n tends to infinity, the number of Carmichael numbers between n and 2n also tends to infinity.

Readers can see by themselves that this description is the Bernard-Chebyshev theorem of Carmichael numbers under limited conditions ( n ​​> 3300 ).

We can see that the negative research on the so-called "Chinese hypothesis" gave birth to the Cosselt criterion; Zhang Mingzhi's use of highly composite numbers inspired Alford and others, and became the starting point for their proof of the infinity of the number of Carmichael numbers; Zhang Yitang's research ignited Larson's passion for studying mathematics, and Maynard's improvement of Zhang Yitang's proof method became the key to Larson's breakthrough research. It is an interesting coincidence that there are traces of Chinese people at several major nodes in the study of Carmichael numbers.

Daniel Larsen's father, Michael Larsen, and mother, Ayelet Lindenstrauss, were both mathematics professors at Indiana University. The strong mathematical atmosphere at home had a profound impact on him.

Starting in 2013, Zhang Yitang's breakthrough on the twin prime problem became a topic of discussion among his parents, which aroused Daniel Larsen's strong interest as a child. He was determined to understand this mathematical achievement that impressed his parents and to start his own mathematical research when the time was right. Since the first year of high school, Daniel Larsen has tried to study the papers on the twin prime problem written by cutting-edge mathematicians such as Zhang Yitang, Maynard and Tao Zhexuan. Although these papers are too difficult for middle school students, Daniel Larsen is tenacious and never gives up easily. After several months of exploration, he pragmatically determined the research direction to be a problem that seemed relatively easy but was closely related to the work of the above-mentioned mathematicians - the distribution problem of Carmichael numbers. At the age of 17, he proved the aforementioned breakthrough result on the distribution of Carmichael numbers, becoming a sensational "genius boy".

If there is any inspiration in Daniel Larson's story, we can probably say that a superior family education environment, good talent and unremitting efforts are all key factors in creating a "genius boy".

References

[1] Korselt, A. “Problème chinois”, L'Intermédiaire des Mathématiciens, 6 (1899): 142–143.

[2] RD Carmichael, "Note on a new number theory function", Bull. Amer. Math. Soc., Vol.16 No. 5, February, (1910): 232 - 238

[3] Chernick, J. "On Fermat's simple theorem", Bull. Amer. Math. Soc. 45, no. 4 (1939): 269–274.

[4] Zhang Mingzhi, “A method for finding large Carmichael numbers”, Journal of Sichuan University (Natural Science Edition), Vol 29 No. 4, (1992): 472-479.

[5] Alford, WR, Granville, A., and Pomerance, C., “There are infinitely many Carmichael numbers” Ann. of Math. 140 (1994): 703–722.

[6] Zhang, Y. “Bounded gaps between primes”, Ann. of Math. 179 (2014): 1121–1174.

[7] Maynard, J. “Small gaps between primes”, Ann. of Math. 181 (2015): 383–413.

[8] Daniel Larsen, "Bertrand's Postulate for Carmichael Numbers", Int. Math. Res. Not. (2023), No. 15, 13072-13098

This article is supported by the Science Popularization China Starry Sky Project

Produced by: China Association for Science and Technology Department of Science Popularization

Producer: China Science and Technology Press Co., Ltd., Beijing Zhongke Xinghe Culture Media Co., Ltd.

Special Tips

1. Go to the "Featured Column" at the bottom of the menu of the "Fanpu" WeChat public account to read a series of popular science articles on different topics.

2. Fanpu provides a function to search articles by month. Follow the official account and reply with the four-digit year + month, such as "1903", to get the article index for March 2019, and so on.

Copyright statement: Personal forwarding is welcome. Any form of media or organization is not allowed to reprint or excerpt without authorization. For reprint authorization, please contact the backstage of the "Fanpu" WeChat public account.

<<:  Bullfrog is a food safety disaster area. Can't eat it? Remember these four points and eat it with peace of mind!

>>:  Open the window to see green, push the door to enter the garden, this forest city is full of greenery and gold!

Recommend

How to operate and promote industrial Internet products?

The operation of industrial Internet products is ...

2021 WeChat Private Domain Growth Handbook for Enterprises

2021 is worth looking forward to for everyone. We...