MA4011: Combinatorial and Analytic Number Theory

School Cardiff School of Mathematics
Department Code MATHS
Module Code MA4011
External Subject Code 100405
Number of Credits 20
Level L7
Language of Delivery English
Module Leader Dr Matthew Lettington
Semester Spring Semester
Academic Year 2015/6

Outline Description of Module

Number theory is the branch of mathematics concerned with the structure of the positive integers.  This lecture based module begins with the study of elementary and combinatorial number theory, before introducing the fascinating world of analytic number theory.

The first part of this module studies how properties of divisibility can be used to characterise the integers and some special numbers, such as Bernoulli numbers, using elementary and combinatorial techniques.

The second part of the module introduces the standard arithmetic functions and studies how these counting functions vary and what their typical and extreme values are.  The most basic questions concern prime numbers and how they are distributed amongst the integers.  For example, a forty-digit number usually only has five or six prime factors, one of them much bigger than all of the others.  The course culminates with the derivation of the prime number theorem which states that the n-th prime is roughly n log n.

Recommended Modules: MA0216 Elementary Number Theory II, MA3004 Combinatorics

On completion of the module a student should be able to

  • Understand and use congruences, solve power congruences using primitive roots.
  • Understand and describe some standard counting functions in number theory.
  • Derive some standard number theoretic relations using combinatorial functions.
  • Manipulate `multiplicative’ arithmetic functions.
  • Understand and estimate the average sizes and the extreme values of arithmetic functions using order of magnitude notation.
  • Understand the distribution of prime numbers.
  • Construct and use Dirichlet characters and Dirichlet L functions.

How the module will be delivered

30 - 50 minute lectures

Some handouts will be provided in hard copy or via Learning Central, but students will be expected to take notes of lectures.

Students are also expected to undertake at least 120 hours private study including preparation of worked solutions for problem classes.

Skills that will be practised and developed

Skills: 
Working with congruences. Using generating functions. Deriving number theoretic properties of combinatorial relations. Manipulating multiplicative functions. Calculating sums and averages as main term plus an error term whose order of magnitude is estimated. Finding the table of Dirichlet characters for a given modulus.

Transferable Skills: 
Recognising patterns. Reasoning logically. Understanding orders of magnitude. Analysing complex expressions as a main term plus smaller order terms.

How the module will be assessed

Formative assessment is carried out in the problem classes. Feedback to students on their solutions and their progress towards learning outcomes is provided during these classes.

The summative assessment is the written examination at the end of the module. This gives students the opportunity to demonstrate their overall achievement of learning outcomes. It also allows them to give evidence of the higher levels of knowledge and understanding required for above average marks.

The examination paper has a choice of four from five equally weighted questions.

Assessment Breakdown

Type % Title Duration(hrs)
Exam - Spring Semester 100 Combinatorial And Analytic Number Theory 3

Syllabus content

  • Euler’s phi function
  • Primitive roots modulo prime powers
  • Generating Functions
  • Bernoulli and Euler Numbers/Polynomials
  • Von Staudt Clausen's Theorem
  • The Riemann zeta function at integer values – Euler and Ramanujan’s formula
  • Multiplicative functions
  • Mobius inversion
  • Orders of magnitude
  • Sizes and averages of arithmetic functions
  • Chebychev’s bounds
  • The Riemann zeta function revisited
  • Dirichlet characters
  • The prime number theorem
  • Dirichlets theorem on primes in arithmetic progression

Essential Reading and Resource List

Introduction to the Theory of Numbers, Hardy G H and Wright E M, OUP

The Higher Arithmetic: An Introduction to the Theory of Numbers, Davenport H, CUP

The Distribution of Prime Numbers, Ingham A E ed. Vaughan R C, CUP

The Prime Number Theorem, Jameson G J O, CUP


Copyright Cardiff University. Registered charity no. 1136855