Number Theory Introduction

The initial focus is on establishing a one-to-one correspondence between different types of partitions. The text emphasizes the difficulty of achieving an exact correspondence, noting that such a correspondence would directly prove the equality E(n) = O(n), where E(n) represents partitions into an even number of parts and O(n) represents partitions into an odd number of parts. The inherent challenge lies in the complex nature of partitions and the subtle relationships between them. This section sets the stage for the exploration of more complex aspects of partitions and their properties. The attempt to establish this correspondence highlights the often-unexpected difficulties that arise even in seemingly straightforward problems within number theory.

A graphical method is introduced to represent partitions, using a diagram where the lowest line forms the base and the longest south-westerly line from the northeast node is identified. Manipulations of this graphical representation, such as moving the base to create a new wing, or the reverse operation, are discussed. These operations show how a partition can be transformed from one with an odd number of parts to one with an even number of parts, and vice versa. While these operations generally suggest E(n) = O(n), the existence of exceptional cases that necessitate further analysis is highlighted, demonstrating the nuanced nature of partition analysis and the need for careful consideration of special cases in proving general statements about partitions. The text underscores that intuitive approaches sometimes break down in number theory, leading to more complex investigations.

The section introduces several related functions and their properties. The discussion includes generalizations of the Euler totient function (ϕ), specifically Jordan's generalization φk(n), which counts k-tuples less than or equal to n whose greatest common divisor is relatively prime to n. The text mentions deriving elementary properties of these functions and presenting both solved and unsolved problems surrounding them. A unified approach is discussed that reveals interconnections between these functions. The functions ω(n), Ω(n), and π(n) are also introduced as being of a different nature and requiring specialized treatment. This illustrates the interconnectedness of different aspects of number theory and the presence of both solved and unsolved problems even within relatively well-established areas.

The section provides examples illustrating the complexities of number theory. It examines numbers of the form (2·3·5···p) ± 1 and p! ± 1 and the challenges in determining their factorization. The problem of whether n! + 1 can be a perfect square for integers n greater than 7 is presented as a specific unsolved problem, highlighting how simple-sounding questions in number theory can lead to substantial unsolved problems. The contrast between a trivial observation (n! - 1 is not a perfect square for n > 2) and the unsolved problem concerning n! + 1 serves to illustrate the subtleties and depth of number theory, showing how even relatively simple questions can remain stubbornly resistant to solution.

This section begins by referencing Euler's significant contribution to the theory of prime distribution: his proof that the sum of the reciprocals of prime numbers diverges (Σ 1/p). This is interpreted as demonstrating that primes are 'more numerous' than perfect squares. The section then introduces a new proof of this fact, one that bears a resemblance to Euclid's proof of the infinitude of primes. This approach serves to highlight the ongoing evolution of understanding within prime number theory and emphasizes that even fundamental results can benefit from alternative proofs, potentially unveiling new insights or connections to other areas of mathematics. The presentation of a new proof underscores the ongoing interest in refining our understanding of this fundamental aspect of prime numbers.

The discussion then shifts to Selberg's inequality and its relationship to the Prime Number Theorem. While Selberg's inequality doesn't directly prove the Prime Number Theorem, the text explains that the latter can be derived from the former using various methods without relying on additional number-theoretic results. The mention of multiple proofs of Selberg's inequality, with a specific reference to a simpler proof by Tatuzawa and Iseki, emphasizes the ongoing development and refinement of mathematical proofs. The connection between Selberg's inequality and the Prime Number Theorem is significant, underscoring the deep relationships between seemingly disparate concepts within number theory and highlighting the power of indirect proofs in advancing our understanding.

The section explores the magnitude of arithmetic functions, specifically σk(n), φk(n), and ωk(n). The text acknowledges the difficulty in approximating these functions using elementary functions of analysis because their values depend not only on the size of n but also on its arithmetic structure. However, the section emphasizes that despite this complexity, these functions exhibit relatively simple behavior 'on average.' This aspect of the analysis highlights the power of averaging techniques in simplifying the study of complex number-theoretic functions, suggesting a path toward understanding their overall behavior even if precise values for individual inputs are elusive. The observation about average behavior suggests that even within the realm of seemingly chaotic functions, discernible patterns emerge upon averaging, providing a valuable tool for mathematical investigation.

The section initiates its exploration of congruences by focusing on quadratic residues and nonresidues, particularly modulo a prime p. It introduces the concept of expressing elements of the multiplicative group (modulo p) as powers of a generator, g, where even powers represent quadratic residues and odd powers represent quadratic nonresidues. This group-theoretic perspective provides a structured framework for understanding the distribution and properties of quadratic residues and nonresidues. The text highlights that this viewpoint clarifies the relationship between these two types of numbers and offers insights into their distribution and properties. The introduction of the group-theoretic framework underscores the importance of abstract algebra in studying problems in number theory.

A significant portion of the section is dedicated to Gauss's quadratic reciprocity law, noting the existence of over 50 published proofs, including recent work by Zassenhaus and Lehmer. The discussion includes Gauss's first proof (one of seven he provided) which relies on a lemma he found challenging to prove. The lemma states that for primes p congruent to 1 (mod 4), the smallest nonresidue does not exceed 2√p + 1. This highlights the complexity involved in proving seemingly simple statements within number theory. The mention of multiple proofs and the difficulty of Gauss's lemma emphasize both the importance of the quadratic reciprocity law and the ongoing interest in finding elegant and efficient methods of proof. The multitude of proofs itself points to the richness and multifaceted nature of the problem.

The section delves into the distribution of consecutive quadratic residues and nonresidues. It introduces the notation Rn and Nn to represent the number of blocks of n consecutive residues and nonresidues, respectively. The section mentions a conjecture suggesting that Rn and Nn are asymptotically equivalent to 2/pn. Contributions from various mathematicians, including Vandiver, Bennet, Dorge, Hopf, Davenport, and A. Brauer, are acknowledged. The highlight is A. Brauer's proof showing that for sufficiently large primes (p > p0(n)), both Rn and Nn are greater than zero. This result utilizes Van der Waerden's theorem on arithmetic progressions, revealing unexpected connections between seemingly disparate areas of number theory. The discussion of Brauer's result using Van der Waerden's theorem emphasizes the rich interconnections within number theory and the applicability of results from one area to solve problems in another.

The section focuses on the problem of determining the least nonresidue, denoted np, of a prime p. It presents results from various mathematicians, including Nagel, Schur, Polya, Zeitz, Landau, Vandiver, Brauer, and Vinogradov. Nagel's proof that np < √p (for p ≠ 7, 23) is mentioned, along with improvements by Pillai, Friedlander, and Chowla, leveraging the Riemann Hypothesis and Linnik's results on primes in arithmetic progressions. Further contributions are discussed by Brauer, Nagel, Skolem, Redei, and Kanold, with particular emphasis on Redei's method which uses finite projective geometry to establish lower bounds for the number of residues and nonresidues up to √p. The extensive list of contributors and the continuous refinements of bounds underscore the long-standing interest and persistent challenges associated with this fundamental problem in number theory.

The primary focus of this section is the Diophantine equation n! + 1 = x², where n and x are integers. The problem's history is traced back to 1885 with Brochard's conjecture that the only solutions are for n = 4, 5, and 7. Ramanujan independently made the same conjecture. Despite its seemingly elementary nature, the problem's appearance as a problem in the American Mathematical Monthly in the 1940s, followed by an incorrect solution and subsequent flawed attempts, highlights the persistent challenge it presents. The section mentions a brute-force verification up to n = 50 and Kraitchik's verification up to n = 5000, indicating the limited progress made toward a complete solution. The text emphasizes the surprising difficulty of this problem, contrasting its simple appearance with the complexity of its solution. The enduring nature of this unsolved problem underscores the unexpected depth and complexity often found in even seemingly simple Diophantine equations.

The section begins by acknowledging the vastness of the field of Diophantine equations, referencing Dickson's comprehensive History of the Theory of Numbers, Volume 2, which is noted as being larger than the other two volumes combined. Given this breadth, the section explicitly states its intention to focus on specific, interesting problems rather than attempting a comprehensive overview. This limitation in scope is justified by the sheer scale of the topic. The reference to Dickson’s History provides context for the immense scope of the subject matter, emphasizing that while many Diophantine equations are studied, this section will focus on a selective set of interesting problems rather than aiming for comprehensive coverage. This strategic focus allows for a more in-depth analysis of specific, challenging examples within the vast field of Diophantine equations.

This section introduces Schur's theorem (1917), which states that if sufficiently many consecutive integers are partitioned into n classes, at least one class will contain elements a, b, and c such that a + b = c. The surprising connection between Schur's theorem and Fermat's Last Theorem is mentioned, although the proof is not provided. It is noted that Schur's theorem demonstrates the limitations of a particular approach to Fermat's Last Theorem—attempting to show that xⁿ + yⁿ = zⁿ (mod p) is insolvable modulo some prime p. The text explains that Schur's theorem implies this approach is ultimately unsuccessful; if p > n!e, a solution exists where p does not divide x, y, or z. This unexpected link highlights the surprising interconnections between seemingly disparate areas of number theory and demonstrates that seemingly intuitive approaches can sometimes be definitively ruled out by deeper theoretical results.

The section then discusses Van der Waerden's theorem, which asserts the existence of an integer W(k, ℓ) such that if integers from 1 to W(k, ℓ) are partitioned into k classes, at least one class will contain an arithmetic progression of length ℓ. The text explicitly notes the absence of a proof for Van der Waerden's theorem due to its complexity and the extremely large bounds it yields. The absence of a proof is contrasted with the presentation of the theorem itself as a significant result, highlighting the existence of important results whose proofs might be extraordinarily difficult to construct or comprehend. The omission of the proof is justified by its difficulty and the emphasis placed on the challenge of finding simpler proofs and more reasonable bounds for the Van der Waerden function as an important unsolved problem in combinatorial number theory.

The concept of 'non-averaging' sequences is introduced: a sequence where no element is the average of two other elements. The primary question is to determine the maximum size of a non-averaging sequence A(n) not exceeding n. A method of constructing such a sequence is explained. The text contrasts the initial conjecture by Szekeres regarding the density of such a sequence with the surprising result by Salem and Spencer, demonstrating a considerably higher density is achievable than initially thought. This highlights the difference between intuitive expectations and the actual behavior of sequences in number theory, as well as the potential for unexpected results even within seemingly well-understood areas. The contrasting conjectures and results emphasize the surprises and counterintuitive findings often discovered within the field of combinatorial number theory.

This section introduces Minkowski's fundamental theorem in geometry of numbers. The theorem states that a centrally symmetric convex region in the plane with area greater than 4 must contain a lattice point other than the origin. The section emphasizes that the constant 4 is optimal and discusses the significance of the conditions of central symmetry and convexity. The text explains that while the theorem might seem intuitive, examples demonstrate that neither central symmetry nor convexity is strictly necessary. The geometric nature of the theorem is highlighted, demonstrating the power of combining geometric and number-theoretic techniques. This introduction establishes a foundation for applying geometric methods to solve problems in number theory, demonstrating that geometric intuition can provide valuable insights into number-theoretic problems.

The section presents Hajos' proof of Minkowski's fundamental theorem. This proof involves partitioning the plane into squares of area 4, overlaying these squares on the region, and showing that the overlap indicates the presence of a lattice point. The section notes that this proof leads to the conclusion that the area of a rectangle containing a line segment connecting two points within a region R cannot exceed 4. From this, the text explains, we can derive information about how closely an irrational number can be approximated by rational numbers. The use of a geometric construction (partitioning into squares) to prove a number-theoretic result illustrates a key approach in the field of geometry of numbers. This demonstrates that geometric intuition and methods can provide proofs and insights that are not readily apparent from purely number-theoretic approaches. The connection to approximating irrational numbers by rationals further highlights the broader applications of this theorem.

The section extends Minkowski's theorem to higher dimensions, discussing its use in finding integer solutions to systems of inequalities. The text explains that the theorem provides sufficient conditions for the existence of a non-zero integer solution provided the determinant of the coefficients is less than the product of certain parameters defining the inequalities. The geometric interpretation is related to the volume of a parallelepiped. Finally, the section presents an unsolved problem: determining the function M(n), which represents the minimum area of a convex region that guarantees it can cover n lattice points. The values M(1) and M(2) are given, while the difficulty of determining M(3) is highlighted, illustrating the persistence of open problems even within well-established areas of geometry of numbers. This discussion showcases the continuing exploration and the existence of unsolved problems even after the establishment of fundamental theorems like Minkowski's.