Results in Analytic and Algebraic Number Theory

A Thesis

presented to

the Faculty of the Graduate School

University of Missouri

In Partial Fulfillment

of the Requirements for the Degree

Master of Arts

by

Aaron Yeager

Dr. William Banks, Thesis Supervisor

December 2012
The undersigned, appointed by the Dean of the Graduate School, have examined the
thesis entitled

Results in Analytic and Algebraic Number Theory

presented by Aaron Yeager,

a candidate for the degree of Master of Arts and hereby certify that in their opinion
it is worthy of acceptance.

Professor William Banks

Professor Youssef Saab

Professor Jan Segert

Professor Konstantin Makarov

 ACKNOWLEDGEMENTS

To begin, I would like to thank my friends and family members for their support,

guidance, and encouragement; without them I certainly would not be where I am

today. I must also give credit to the numerous excellent math teachers, instructors,

and professors I have had throughout my collegiate career. I would like to thank

Ryan Alvarado and Kevin Brewster for their aid with LaTex commands that made

my thesis possible. I would like to thank my co-authors of the papers I written while

at the University of Missouri: William Banks, Ahmet M. Güloğlu, Zhenyu Guo, and

Roger Baker. I would like to thank Youssef Saab, Konstantin Makarov, and Jan

Segert for being on my master’s committee. On a final note, I would like to express

my gratitude to William Banks for being my advisor and for his assistance on my

thesis.

ii
Contents

ACKNOWLEDGEMENTS ii

Preface iv
0.1 Chapters I and II . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv
0.2 Chapters III, IV, and V . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v

CHAPTERS 1

1 Sums Over Finite Fields 1

1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Generalized Gauss Sums . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Jacobi Sums . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2 Dedekind Zeta Functions 9

2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 The auxiliary function ϑQ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3 The properties of Dedekind Zeta Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

3 Carmichael Numbers composed of Primes from a Beatty Sequence 21

3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.2.1 General notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.2.2 Discrepancy and type . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.2.3 Numbers in a Beatty sequence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.2.4 Sums with the von Mangoldt function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.3 Beatty primes in arithmetic progressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.4 Construction of Carmichael numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.5 Dickson’s conjecture and Beatty primes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

4 Carmichael meets Chebotarev 41

4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.3 Zeros of Dedekind zeta functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.4 Chebotarev Density Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.5 Construction of Carmichael numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

5 Piatetski-Shapiro Primes from Almost Primes 59

5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
5.2 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
5.3 Proof of Theorem 18 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
5.3.1 Initial approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
5.3.2 Refinement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

VITA 77

iii
 RESULTS IN ANALYTIC AND ALGEBRAIC NUMBER THEORY

Aaron Yeager

Dr. William Banks, Thesis Supervisor

Preface

This work is a compilation of five papers that contain some related topics and

techniques. These papers were written during the last two years at the University of

Missouri. The papers are divided as chapters, each having its own introduction and

bibliography. Although the topics are connected and similar techniques are used, the

chapters are mostly self-contained and can be read independently.

0.1 Chapters I and II

The first two chapters are exposition topics in Analytic and Algebraic Number Theory.

I began working on the first chapter while I attended a course in Analytic Number

Theory during Fall 2011. The work in the second chapter started when I took a

course in Algebraic Number Theory in Spring 2012.

The first chapter gives a brief introduction to sums over finite fields. The chapter

also discusses Gauss sums, generalized Gauss sums, exponential sums, and Jacobi

sums. If we let F be a finite field with q elements, it is shown that the modulus of the
√
Gauss sum and the modulus of the Jocobi sum is equal to q. Using these theorems

the chapter concludes by showing that if p is a prime such that p ≡ 1 (mod 4), then

there are integers a and b such that p = a2 + b2 .

The second chapter proves some useful results concerning the Dedekind zeta func-

tion. The chapter starts with some basic properties of this function. An auxiliary

iv
function is then defined and shown to have a functional equation. Using these results

for the auxiliary function, the Dedekind zeta function is shown to have a factorization

in the right half of the complex plane that has the gamma function and sums regard-

ing the incomplete gamma function as some of its factors. Given this factorization

and using properties of the gamma function and the incomplete gamma function as

well as using techniques from real and complex analysis, the function is proven to

be meormorphic on the whole complex plane, shown to have a simple pole, and the

residue is exhibited. The function is also shown to have a functional equation that

has a factor of the gamma function. The chapter concludes by giving the evaluation

of the function at zero and showing that this function is zero on the negative integers.

0.2 Chapters III, IV, and V

The last three chapters were written with co-authors. The chapters are an expan-

sion of a series of new research papers in mathematics with topics from Analytic

and Algebraic Number Theory. The papers that resemble chapters III and IV have

been accepted by journals and the paper that represents chapter V will be submit-

ted shortly. The papers were written in Spring 2011, Fall 2011, and Spring 2012

respectively.

My advisor is the co-author of the third chapter, which has been accepted by Col-

loquium Mathematicum. In the chapter we give a new result concerning Carmicheal

numbers. Specifically, let α, β ∈ R be fixed with α > 1, and suppose that α is irra-

tional and of finite type. We show that there are infinitely many Carmichael num-

bers composed solely of primes from the non-homogeneous Beatty sequence Bα,β =

(bαn + βc)∞
n=1 . The result is proved by appealing to a construction of infinitely many

v
Carmicheal numbers given by Alford, Granville, and Pomerance. To use their con-

struction we bound exponential sums over arithmetic progressions by many techniques

such as exploiting the type of α, using the Balog and Perelli theorem, and by apply-

ing a classical result by Vinogradov on bounds of Fourier coefficients. The chapter

concludes with heuristic evidence via Dickson’s conjecture to support our conjecture

that we obtain same result when α is an irrational number of infinite type.

The fourth chapter was co-authored by my advisor and Ahmet M. Güloğlu and

is accepted by the Canadian Mathematical Bulletin. The chapter contains a proof

of a new result in Algebraic Number Theory that has an application to Carmicheal

numbers. We show that for any finite Galois extension K of the rational numbers Q,

there are infinitely many Carmichael numbers composed solely of primes for which

the associated class of Frobenius automorphisms coincides with any given conjugacy

class of Gal(K|Q). The result has three corollaries: for any algebraic number field K,

there are infinitely many Carmichael numbers which are composed solely of primes

that split completely in K; for every natural number n, there are infinitely many

Carmichael numbers of the form a2 + nb2 with a, b integers; and there are infinitely

many Carmichael numbers composed solely of primes p ≡ a (mod d) with a, d coprime.

To obtain our main result we begin by examining zeros of the Dedekind zeta function

in a region to get the existence of a proper integral ideal. We use this result along

with the Chebotarev Density Theorem to yield a lower bound on a counting function

that detects primes in our setting. Finally after this bound is proven, we show how

the construction of infinitely many Carmichael numbers given by Alford, Granville,

and Pomerance can be applied using these primes.

vi
 The fifth chapter is to be submitted in the near future. It is co-authored by

my advisor, Roger Baker, and Zhenyu Guo. In the chapter we prove a new result

regarding Piatetski-Shapiro primes, primes from sequences of the form (bnc c)n∈N

where c > 1 and c 6∈ N, in relation to almost primes. We show that for any fixed

c ∈ (1, 77
76
) there are infinitely many primes of the form p = bnc c, where n is a natural

number with at most eight prime factors (counted with multiplicity). To achieve

this result we begin by using an approximation by Vaaler for bounds on exponential

sums with the saw-tooth function. Eventually we have to bound type I and type II

exponential sums. One of our main tools in the desired bounds on these sums is the

use of exponential pairs. Furthermore, we show how to find the optimal exponential

pairs for our setting. Using these techniques and appealing to a weighted sieve we

obtain the main result for when c ∈ (1, 8635

8568
). The chapter concludes with giving a

refinement of our argument that shows the same result is true when c ∈ (1, 77
76
).

vii
Chapter 1

Sums Over Finite Fields

1.1 Introduction

The contents of this chapter are a result of studies from [1] and [2]. The main object

of study is a sum that has a character convolved with an exponential function. Some

examples of these types of sums are the quadratic Gauss sum

   
X x ax
Ga (p) = e ,
p p
χ (mod p)

ax
where e( ax
p
) = e2πi p and ( xp ) is the Legendre symbol modulo p, or Kloosterman sums
∗  
X ax + bx
S(a, b; p) = e ,
p
χ (mod p)

where the weight ∗ means that the sum can be extended to all x which are not poles for

the function in the sum and where x is the inverse in Z/pZ of the invertible element

x ∈ (Z/pZ)× . The quadratic Gauss sums are used for many results. Among these

results are the Hasse-Davenport relation and quadratic reciprocity. The Kloosterman

sums can also be used to show many results. One of the most notable results is that

for a1 , ..., a4 ≥ 1 positive integers for n large enough, depending on the a0i s, there

exists at least one integral solution (x1 , ..., x4 ) ∈ Z4 to the diophantine equation

a1 x21 + ... + a4 x24 = n

1
provided there is no congruence obstruction.

The Gauss and Kloosterman sums can be generalized. That is, the Legendre char-

acter can be replaced with an arbitrary multiplicative character and the exponential

function can be replaced with an arbitrary arithmetic function. Sums of this type are

called Complete Sums. We will address these sums in the next section.

To begin our study of these sums let p be a prime number and consider the field

Fp = Z/pZ. Since this field has p elements, the Galois theory is easy to describe. For

n ≥ 1, there exists up to isomorphism a unique field extension of Fp of degree n, Fpn .

Conversely, any finite field F with q elements is isomorphic to a unique field Fpd , so

q = pd , and F has a unique extension of degree n, namely Fpdn .

Let F = Fq be a finite field with q = pd elements. Let F be the algebraic closure

of F and set Fn to be the unique extension of degree n of F for n ≥ 1. Observe

we have the cardinality relation |Fn | = q n . Thus the extension Fn /F is Galois. Set

Gn = Gal(Fn /F). Then by the map Z/nZ → Gn by 1 7→ σ, where σ is the Frobenius

automorphism of Fn given by σ(x) = xq , we have Gn ∼

= Z/nZ. Given this we have
S
F= n≥1 Fn . Furthermore, since F is a Galois extension of F, for x ∈ F we have that

x ∈ F ⇐⇒ σ(x) = x ⇐⇒ xq = x.

Then in general, for the extension Fn over F we have

n
x ∈ Fn ⇐⇒ σ n (x) = x ⇐⇒ xq = x.

n
Given this we can conclude that Fn is the splitting field for xq − x ∈ F[x].

2
1.2 Generalized Gauss Sums

The quadratic Gauss Sum can be generalized by using a multiplicative character and

an additive character. Specifically, let Fq be a field with q elements and let χ be a

multiplicative character on Fq and ψ be additive character of Fq . The general Gauss

sum over the finite field Fq is given by

X
τ (χ, ψ) = χ(x)ψ(x).
x∈F×
q

From this definition, our first theorem regards the size of the modulus of τ (χ, ψ).

Theorem 1. Let χ be non-trivial multiplicative character and ψ be a non-trivial

additive character on Fq . Then

√
|τ (χ, ψ)| = q.

Proof. If we consider the modulus squared, expanding the product of the Gauss sum

and its conjugate yields

X
|τ (χ, ψ)|2 = χ(x)χ(y)ψ(x)ψ(y)
x,y∈F×
q
X
= χ(xy −1 )ψ(x − y).
x,y∈F×
q

Now put u = xy −1 . Then for a fixed y we have

X X
|τ (χ, ψ)|2 = χ(u) ψ(y(u − 1)),
u∈F×
q y∈F×
q

where the inner sum above is purely additive. By the orthogonality relations of the

additive characters on Fq , this inner is sum is such that


X −1 if u 6= 1,
α(u − 1) − 1 =
q−1 if u=1,
α

3
for all α of the additive characters on Fq . Using this and by the orthogonality relations

of the multiplicative character χ, we have

X
|τ (χ, ψ)|2 = − χ(u) + q
u∈F×
q

= q.

Taking the square root of both sides of the above yields the result.

1.3 Jacobi Sums

As with the generalized Gauss Sums, let Fq be a field with q elements. Let χ and φ

be multiplicative characters of Fq . The Jacobi sum associated to the multiplicative

characters χ and φ of Fq is defined by

X X
J(χ, φ) = χ(x)φ(1 − x) = χ(x)φ(y).
x∈Fq x+y=1

The values of such a sum occur in relation to local zeta-functions for diagonal forms.

Our next proposition shows how these sums can be expressed as general Gauss

sums.

Theorem 2. Let χ and φ be non-trivial multiplicative characters such the product

χφ is also a non-trivial on Fq , a field with q elements. Fix a non-trivial additive

character ψ of Fq . Then
τ (χ, ψ)τ (φ, ψ)
J(χ, φ) = . (1.1)
τ (χφ, ψ)

Furthermore,
√
|J(χ, φ)| = q.

Proof. By definition the Jacobi and Gauss sums we have

4
 X X
J(χ, φ)τ (χφ, ψ) = χ(x)φ(1 − x) χφ(y)ψ(y)
x∈Fq y∈F×
q
X X
= χ(x)φ(1 − x) χ(y)φ(y)ψ(y)
x∈Fq y∈F×
q
X X
= χ(x)φ(1 − x)χ(y)φ(y)ψ(y).
x∈Fq y∈F×
q

By χ and φ being nontrivial, the above sum can be restricted to x 6∈ {0, 1}. Set

u = xy and v = y − xy. Then by this change of variables we obtain a bijection from

(x, y) ∈ (Fq − {0, 1}) × F× × ×

q to {(u, v) ∈ Fq × Fq : u + v 6= 0}. Furthermore by χφ

being non-trivial it follows that

X
J(χ, φ)τ (χφ, ψ) = χ(u)φ(v)ψ(u + v)
u,v∈F×
q
u+v6=0
X
= τ (χ, ψ)τ (φ, ψ) − χ(u)φ(−u)
u∈F×
q

= τ (χ, ψ)τ (φ, ψ).

√
Using theorem 1 we have |τ (χφ, ψ)| = q 6= 0. Thus by definition of the modulus it

follows that τ (χφ, ψ) 6= 0. Hence dividing both sides of the above by τ (χφ, ψ) yields

equation 1.1. To obtain the other result, we use equation 1.1 along with Theorem 1

and simplify to complete the proof.

Our final result shows how a Jacobi sum can be used to answer a classical problem

in Number Theory.

Theorem 3. Let p be a prime number such that p ≡ 1 (mod 4). Then there exists

a, b ∈ Z such that

p = a2 + b2 .

Proof. By the theory of characters, since p ≡ 1 (mod 4), there exists a character χ

of order 4 on F×
p . Consider the Jacobi sum J(χ, φ), where φ is the usual Legendre

5
character. Then by definition

X
J(χ, φ) = χ(x)φ(y).
x+y=1

By φ being a Legendre character we have φ(y) ∈ {−1, 0, 1} and by χ being a character

of order 4 on F×
p , we have χ(x) ∈ {−i, −1, 0, 1, i}. Give this observation, the Jacobi

sum J(χ, φ) can be written as J(χ, φ) = a + bi, for some a, b ∈ Z. Therefore with

this in consideration, using Theorem 2 we obtain

p =|J(χ, φ)|2

=|a + bi|2
√
=( a2 + b2 )2

=a2 + b2 .

6
Bibliography

[1] H. Iwaniec, E. Kowalski, ‘Analytic Number Theory,’ Amer. Math., Providence,

RI, (2004), 269–291.

[2] H. Iwaniec, ‘Exponential sums over finite fields, I: elementary methods,’

http://www.math.ethz.ch/ kowalski/exp-sums.pdf (2010), 1–27.

7
8
Chapter 2

Dedekind Zeta Functions

2.1 Introduction

The contents of this chapter are results from studies of the references and working

through problems 25 (a) and (b) and 26 (a) through (f) of [3]. The lemmas and

theorems in the paper are these problems worked out. All proofs are the author’s

work with few proofs using variations of techniques in chapter 10 of [3]. Let K be

an algebraic number field. That is, K is a finite dimensional field extension of the

rational field Q. Let N (·) be the norm on the field K . For s = σ + it ∈ C, with

σ > 1, the Dedekind zeta function is defined to be

X
ζK (s) = N (a)−s
a

where the sum is over all integral ideals in the ring OK of algebraic integers in K. By

[2], the Dedekind zeta function can also be written as

∞
X aK (n)
ζK (s) = ,
1
ns

where aK (n) is the number of integral ideals of K with norm exactly n. When K = Q,

ζK (s) = ζ(s). Hence why the sum bears its name. This function is of great importance

for many reasons. For instance it can be used to show various density theorems such

9
as the Cebatorev Density theorem. It can also be used to get a generalization of

a Dirichlet L-series which leads Dirichlet’s Prime Number Theorem. Some natural

questions to consider would be: What properties does this function have like the

usual ζ function? Does it have an Euler product, a functional equation? Can it be

factored to recover the original ζ function? Is it meromorphic, and if so, what are the

singularities and residues, and so on? To answer some of these questions we need to

start with how the norm acts on ideals in OK . Given that ideals in the ring OK factor

uniquely into prime ideals, and since both the norm N (·) and n−s are multiplicative,

their product is also multiplicative. Hence we have a Euler product of

Y
ζK (s) = (1 − N (p)−s )−1 ,
p

for σ > 1.

2.2 The auxiliary function ϑQ

Let Q(x, y) = ax2 + bxy + cy 2 , where a, b, c are real numbers, and put d = b2 − 4ac.

Suppose that Q is positive-definite, which is to say that a > 0 and d < 0. For z ∈ C

with R(z) > 0, put

X √
ϑQ (z) = e−2πQ(m,n)z/ −d
.
m,n∈Z

Lemma 1. The function ϑQ (z) can be written as

X 2
√ X 2 z/
√
ϑQ (z) = e−πzn −d/(2a)
e−2πa(m+bn/(2a)) −d
.
n m

Proof. Completing the square in the definition of the quadratic form and combining

like terms yields,

10
 Q(m, n) = am2 + bmn + cn2
(bn)2
= a(m + bn/(2a))2 − + cn2
4a
2
(bn) − cn2 4a
= a(m + bn/(2a))2 −
4a
2
nd
= a(m + bn/(2a))2 − .
4a
Thus
X √
ϑQ (z) = e−2πQ(m,n)z/ −d

m,n∈Z
X 2 +bmn+cn2 )z/
√
= e−2π(am −d

m,n∈Z
XX bn 2 n2 d
√
= e−2π(a(m+ 2a ) − 4a )z/ −d

n m
X 2
√ X 2 z/
√
= e−πzn −d/(2a)
e−2πa(m+bn/(2a)) −d
.
n m

Lemma 2. The function ϑQ (z) has a functional equation of ϑQ (z) = ϑQ (1/z)/z.

bn 2az
Proof. Applying Theorem 10.1 of [3], with choices of α = 2a
and z̃ = √
−d
, to the

inner sum in the previous lemma yields

X √  2az  −1 √
−2πa(m+bn/(2a))2 z/ −d 2
X 2
e = √ e(kbn/(2a))e−πk −d/(2az) .
m
−d k

Using this and switching the sums shows

X 2
√ X 2
√
ϑQ (z) = e−πzn −d/(2a) e−2πa(m+bn/(2a)) z/ −d
n m
 2az  −1
2
X 2
√ X 2
√
= √ e−πzn −d/(2a) e(kbn/(2a))e−πk −d/(2az)
−d n k
 2az  −1
2
X 2
√ X 2
√
= √ e−πk −d/(2az) e−πzn −d/(2a)+πikbn/a .
−d k n

By writing the exponent on the last sum above as

√ √ √ √
−πzn2 −d/(2a) + πikbn/a = −π(n − ikb/(z −d))2 z −d/(2a) − π(kb)2 /(2az −d)

11
we see that
X 2
√ X 2
√ √ 2
√
e−πzn −d/(2a)+πikbn/a = e−π(kb) /(2az −d) e−π(n−ikb/(z −d)) z −d/(2a)
n n
√ √ √
−π(kb)2 /(2az −d)
X
−d))2 z −d/(2a)
=e e−π(n−ikb/(z .
n
−ikb 2az
Using Theorem 10.1 of [3] again, this time with α = √
z −d
and z̃ = √
−d
, we obtain

that the sum above is

2 /(2az
√ √ −1
X √ 2
√
e−π(kb) −d)
(z −d/2a) 2 e(−likb/(z −d))e−πl /(z −d/(2a)) .
l

If we now combine the exponents from the exponential functions and factor them, we

see that

√ √ √ √
−π(kb)2 /(2az −d)+2πlkb/(z −d)−πl2 /(z −d/(2a)) = −2πa/(z −d)(l−kb/(2a))2 .

Putting this in the sum and combining with the previous sum shows
 2az  −12
 z √−d  −1
2
X 2
√ X 2
√
√ e−πk −d/(2az) e−2πa(l−bk/(2a) /(z −d)
−d 2a k l
X √ √
−πk2 −d/(2az)
X 2
−1
= (z) e e−2πa(l−bk/(2a) /(z −d) .
k l

If we let l = m and k = −n we achieve the result.

2.3 The properties of Dedekind Zeta Functions

Let us now consider the case when K is a complex quadratic field. Let d be the
√
discriminant of K. Then K = Q( d), where d < 0. Let w be the number of units in

Ok , and h be the class number of K. Then there are h reduced positive definite binary

quadratic forms of discriminant d, say Q1 , ..., Qh . Consider when (m, n) 6= (0, 0). As

these run over integral values, Qi (m, n) runs over the values of N (a) for ideals a ∈ Ci ,

where Ci is the ith ideal class, each value being taken w times. Hence on each Qi ,
X
ζQi (s) = w N (a)−s .
a∈Ci

12
Theorem 4. For R(z) ≥ 0, let
h
X ∞
X √
ϑK (z) = ϑQi (z) = h + w r(n)e−2πnz/ −d

i=1 n=1
P
where r(n) = rK (n) = k|n χd (k) is the number of ideals in Ok with norm equal to

n. Give this we have ϑK (z) = ϑK (1/z)/z.

Proof. By definition
X √
ϑQi (z) = e−2πQi (m,n)z/ −d

m,n∈OK
X √
=1+ e−2πQi (m,n)z/ −d
.
m,n∈OK
m,n6=0

If we sum from 1 to h, by the definition of how Qi (m, n) runs over the its values, we

see
h
X ∞
X √
ϑK (z) = ϑQi (z) = h + w r(n)e−2πnz/ −d
.
i=1 n=1

By Lemma 2 it follows that ϑQi (z) = ϑQi (1/z)/z. Therefore we have

h
X
ϑK (z) = ϑQi (1/z)/z = ϑK (1/z)/z.
i=1

Theorem 5. If R(z) ≥ 0, then

∞
X √
ζK (s)Γ(s)(−d)s/2 (2π)−s = (−d)s/2 (2π)−s r(n)n−s Γ(s, 2πnz/ −d)
n=1
∞
(1−s)/2 s−1
X √
+ (−d) (2π) r(n)ns−1 Γ(1 − s, 2πn/(z −d))
n=1
hz s−1 hz s
+ − ,
2w(s − 1) 2ws
where Γ(s, a) is the incomplete gamma function
Z ∞
Γ(s, a) = e−w ws−1 dw.
a

13
Proof. By Euler’s integral formula for Γ(s), if σ > 0, then

Z ∞
Γ(s) = e−x xs−1 dx.
0

√
If we make of change of variables of x = 2πnu/ −d we obtain
∞ √ √ √
Z
Γ(s) = e−2πnu/ −d
(2πnu/ −d)s−1 (2πn/ −d)du
0
√ ∞ √
Z
= (2πn/ −d)s e−2πnu/ −d s−1
u du.
0

Thus
Z ∞ √
−s −s/2 −s
n Γ(s)(−d) (2π) = e−2πnu/ −d s−1
u du.
0

Since r(n) is the number of ideals in OK with norm exactly n, for σ > 0, if we multiply

both sides of the equation above by r(n) and then sum over n we achieve,
∞
X Z ∞ √
−s/2 −s
ζK (s)Γ(s)(−d) (2π) = r(n) e−2πnu/ −d s−1
u du
n=1 0
∞ ∞ (2.1)
√ 
Z X
−2πnu/ −d s−1
= r(n)e u du.
0 n=1

I note that the exchange of the integration and the summation above is permitted by

the absolute convergence of the series. Suppose the R(z) > 0. By Cauchy’s theorem,

we may replace the path of integration by a ray from 0 that passes through z. We
R
now consider the integral from 0 to z and z to ∞ separably. Call these integrals 1
R
and 2
respectively. By reversing the steps above we have that

∞
√
Z X
−s
= (−d) s/2
(2π) r(n)n−s Γ(s, 2πnz/ −d).
2 n=1

Notice that the inner sum in (2.1) is (ϑK (u) − h)/(2w). Thus

Z Z z Z z
1 s−1 h
= ϑK (u)u du − us−1 du.
1 2w 0 2w 0

14
 −hz s
The later integral above is 2ws
. From theorem 1 we know that ϑK (z) = ϑK (1/z)/z.

Thus the first integral above is

Z z Z z ∞ √ 
1 1 X
s−2
ϑK (1/u)u du = h + 2w r(n)e−2πn/u −d us−2 du
2w 0 2w 0 n=1
s−1 Z ∞X ∞ √ 
hz
= + r(n)e−2πn/u −d us−2 du.
2w(s − 1) 0 n=1

Using a change of variables of v = 1/u, we see that the integral above is

Z ∞ ∞
X √ 
r(n)e−2πnv/ −d −s
v dv.
1/z n=1

Changing the order of summation and integration and using the change of variables
√
of x = 2πnv/ −d we obtain
∞
(1−s)/2 s−1
X √
(−d) (2π) r(n)ns−1 Γ(1 − s, 2πn/(z −d)).
n=1
R R
Putting the integrals 1
and 2
together we obtain the result.

Theorem 6. The function ζK (s) is a meromorphic function whose only singularity

√
is a simple pole at s = 1 with residue hπ/(w −d).

Proof. Isolating the Dedekind zeta function in the equation in theorem 5 gives that

for R(z) ≥ 0,
∞
1 X √
ζK (s) = r(n)n−s Γ(s, 2πnz/ −d)
Γ(s) n=1
∞
1 X √
+ (−d) (1−2s)/2
(2π)2s−1
r(n)ns−1 Γ(1 − s, 2πn/(z −d)) (2.2)
Γ(s) n=1
(2π)s hz s−1 (2π)s hz s
+ − .
Γ(s)ds/2 2w(s − 1) Γ(s)ds/2 2ws
By properties of the gamma function and the incomplete gamma function, the two

sums above represent entire functions. Hence the right side of the equation above

is analytic for all s except s = 0, 1. The fact that ζK (s) is also analytic at s = 0

15
follows from theorem 8 below. To see that ζK as a simple pole at s = 1, observe that

lims→1 |ζK (s)| = ∞ by the last term above forcing this to happen. Furthermore, by

lims→1 |(s − 1)ζK (s)| =

6 ∞, this pole is simple. Therefore ζK is meromorphic and the

only singularity is a simple pole at s = 1. To find the residue at s = 1, notice

Ress=1 (ζK (s)) = lim(s − 1)ζK (s)
s→1
1 hz s−1
= lim(s − 1) (−d)−s/2 (2π)s
s→1 Γ(s) 2w(s − 1)
1 h
= (−d)−1/2 (2π)
Γ(1) 2w
√
= hπ/(w −d)
where the second equality above follows from all the other terms in the right side of

(2.2) going to zero. This completes the proof.

Theorem 7. Put ξK (s) = ζK (s)Γ(s)(−d)s/2 (2π)−s . Then it follows that ξK (s) =

ξK (1 − s) for all s except s = 1 and s = 0.

Proof. If we replace s by 1 − s in the equality in Theorem 5 we see that

ξK (1 − s) = ζK (1 − s)Γ(1 − s)(−d)(1−s)/2 (2π)s−1
∞
(1−s)s/2 s−1
X √
= (−d) (2π) r(n)ns−1 Γ(1 − s, 2πnz/ −d)
n=1
∞
X √
+ (−d)s/2 (2π)−s r(n)n−s Γ(s, 2πn/z −d)
n=1
hz −s hz 1−s
+ + .
2w(−s) 2w(1 − s)
Now doing a change of variables of z mapped to 1/z and cleaning up the equation we

see that the above is equal to the desired ξK (s).

Theorem 8. The value of the Dedekind zeta function at zero is equal to −h/(2w).

Proof. By Theorem 7 we have that

ζK (s)Γ(s)(−d)s/2 (2π)−s = ζK (1 − s)Γ(1 − s)(−d)(1−s)s/2 (2π)−(1−s) ,

16
for all s 6= 0, 1. If we multiply the above equation by s − 1 and take the limit as s

approaches 1, we see that the left hand side above goes to

Res(ζK (s), 1)(−d)1/2 (2π)−1 = h/(2w)

by the residue calculation in Theorem 3. As s approaches 1 on the right hand side

we get

ζK (0)Res(Γ(s), 0)(−d)0 (2π)0 = −ζK (0).

Thus equating these limits and multiplying by -1 on both sides yields the result.

Theorem 9. For all positive integers k we have that ζK (−k) = 0.

Proof. Solving for ζK (s) from the functional equation in Theorem 4 yields

Γ(1 − s)
ζK (s) = ζK (1 − s) (−d)1−s (2π)2s−1 .
Γ(s)

By Theorem 6 we know that ζK (s) is meromorphic with only one singularity at

s = 1. Hence for k any positive integer, ζK (1 − (−k)) = ζK (1 + k) is well defined.

Also by Γ(s) being analytic for positive real numbers, again for any k a positive

integer, Γ(1 − (−k)) = Γ(1 + k) is also well-defined. However since Γ(s) has poles at

the negative integers, 1/Γ(s) has simple zeros at the negative integers. Thus for all

positive integers k, it follows that

Γ(1 + k)
ζK (−k) = ζK (1 + k) (−d)1+k (2π)−2k−1 = 0.
Γ(−k)

17
18
Bibliography

[1] H. Iwaniec, E. Kowalski, ‘Analytic Number Theory,’ Amer. Math., Providence,

RI, (2004), 269–291.

[2] G. Janusz, ‘Algebraic Number Fields,’ Academic Press, New York (1973), 117–

130.

[3] H. Montgomery, R. Vaughan, ‘Multiplicative Number Theory I. Classical The-

ory,’ Cambridge University Press, New York (2007), 326–344.

[4] J. Neukirch, ‘Class Field Theory,’ Springer, New York (1980), 117–121.

[5] P. Samuel, ‘Algebraic Theory of Numbers,’ Dover Publications, New York (1970).

[6] A. Weil, ‘Basic Number Theory,’ Springer, New York (1974), 120–138.

19
20
Chapter 3

Carmichael Numbers composed of

Primes from a Beatty Sequence

3.1 Introduction

If N is a prime number, Fermat’s little theorem asserts that

aN ≡ a (mod N ) for all a ∈ Z.

Around 1910, Robert Carmichael initiated the study of composite numbers N with the

same property, which are now known as Carmichael numbers. In 1994 the existence

of infinitely many Carmichael numbers was first established by Alford, Granville

and Pomerance [1]. In recent years, using variants of the method of [1], several

arithmetically defined classes of Carmichael numbers have been shown to contain

infinitely many members; see [4, 5, 6, 14].

In the present note we consider the problem of constructing Carmichael numbers

that are composed of primes from a Beatty sequence. We recall that for fixed α, β ∈ R

the associated non-homogeneous Beatty sequence is the sequence of integers defined

by

Bα,β = bαn + βc


n∈Z
.

Beatty sequences appear in many seemingly unrelated mathematical settings, and

21
because of this versatility, the arithmetic properties of Beatty sequences have been

extensively explored in the literature; see, for example, [1, 7, 8, 9, 10, 13, 16, 17, 20,

21, 26] and the references contained therein.

Theorem 10. Let α, β ∈ R with α > 1, and suppose that α is irrational and of finite

type. Then, there are infinitely many Carmichael numbers composed solely of primes

from the Beatty sequence Bα,β .

A quantitative version of this result is given in §3.4; see Theorem 12. To prove

Theorem 18, we show that when α is of finite type (see §3.2.2) the set of primes

in a Beatty sequence is sufficiently well-distributed over arithmetic progressions that

one can construct Carmichael numbers from such primes using an adaptation of the

method of [1]. To do this, we extend various results and techniques of Banks and

Shparlinski [7].

Conjecture. The conclusion of Theorem 10 also holds when α is an irrational number

of infinite type.

For irrational numbers α of infinite type, the approach described above fails. How-

ever, assuming the validity of a certain natural extension of Dickson’s conjecture (see

Conjecture II in §3.5) we establish the above conjecture in the case that β = 1 (see

Theorem 14 in §3.5). This method can be adapted to conditionally establish many

other cases of the conjecture.

22
3.2 Preliminaries
3.2.1 General notation

The notation JtK is used to denote the distance from the real number t to the nearest

integer; that is,

JtK = min |t − n| (t ∈ R).

n∈Z

We denote by btc and {t} the greatest integer 6 t and the fractional part of t,

respectively. We also put e(t) = e2πit for all t ∈ R. As usual, we use Λ(·) and ϕ(·) to

denote the von Mangoldt and Euler functions, respectively.

Throughout the paper, the implied constants in symbols O,  and  may depend

on the parameters α, β and ε but are absolute otherwise. We recall that for functions

F and G the notations F  G, G  F and F = O(G) are all equivalent to the

statement that the inequality |F | 6 C |G| holds for some constant C > 0.

3.2.2 Discrepancy and type

Recall that the discrepancy D(M ) of a sequence of (not necessarily distinct) real

numbers a1 , a2 , . . . , aM ∈ [0, 1) is defined by

V (I, M )
D(M ) = sup − |I| , (3.1)
I⊆[0,1) M

where the supremum is taken over all intervals I contained in [0, 1), V (I, M ) denotes

the number of positive integers m 6 M such that am ∈ I, and |I| denotes the length

of the interval I.

The type τ = τ (γ) of an irrational number γ is defined via the relation

τ = sup t ∈ R : lim inf nt JγnK = 0 .


n→∞

23
By Dirichlet’s approximation theorem, one has τ > 1 for every irrational number

γ. The theorems of Khinchin [15] and of Roth [23, 24] assert that τ = 1 for almost

all real numbers (in the sense of the Lebesgue measure) and all irrational algebraic

numbers γ, respectively; see also [11, 25].

For every irrational number γ, the sequence of fractional parts ({nγ})∞

n=1 is uni-

formly distributed in [0, 1) (see, e.g., [18, Example 2.1, Chapter 1]). In the case that

γ is of finite type, the following more precise statement holds (see [18, Theorem 3.2,

Chapter 2]).

Lemma 3. Let γ be a fixed irrational number of finite type τ . Then, for every δ ∈ R

the discrepancy Dγ,δ (M ) of the sequence ({γm + δ})M

m=1 satisfies the bound

Dγ,δ (M ) 6 M −1/τ +o(1) (M → ∞),

where the function implied by o(·) depends only on γ.

3.2.3 Numbers in a Beatty sequence

The following lemma provides a convenient characterization of the numbers which

occur in a Beatty sequence Bα,β .

Lemma 4. Let α, β ∈ R with α > 1, and put γ = α−1 , δ = α−1 (1 − β). Then,

n ∈ Bα,β if and only if ψ(γn + δ) = 1, where ψ = ψα is the periodic function defined

by
if 0 < {t} 6 α−1 ,

1
ψ(t) = (3.2)
0 otherwise.

3.2.4 Sums with the von Mangoldt function

The next statement is a simplified and weakened version of a theorem of Balog and

Perelli [3] (see also [19]).

24
Lemma 5. For an arbitrary real number θ and coprime integers c and d with 0 6

c < d, if θ − a/q 6 1/x and gcd(a, q) = 1, then

X
Λ(n)e(θn)  q −1/2 x + q 1/2 x1/2 + x4/5 (log x)3 .


n6x
n≡c (mod d)

As an application of Lemma 5 we derive the following statement, which is an

explicit version of [7, Theorem 4.2].

Lemma 6. Let γ be an irrational number of finite type τ , and fix A ∈ (0, 1) and

ε > 0. For any coprime integers c and d with 0 6 c < d and any nonzero integer k

such that |k| 6 xA , the bound

X A+2+1/τ
+ε
Λ(n)e(kγn)  x 2+2/τ + x4/5 (log x)3
n6x
n≡c (mod d)

holds, where the implied constant depends only on the parameters α, β, A and ε.

Proof. It suffices to prove this for ε ∈ (0, 31 ). Put

A+1 τ (1 + ε) A+1
B= , C= , D= + 2ε.
1 + 1/τ 1 − ετ 1 + 1/τ

Note that B ∈ (0, 1) (since τ > 1 for an irrational γ), C ∈ (τ, 2τ ), and

A+1
D = B + 2ε > B(1 + ε) = ,
1 + 1/C

which implies that

−A + C/D > 1 − D. (3.3)

Since C ∈ (τ, 2τ ) and γ is of type τ , we have

JγmK > c0 |m|−C (m ∈ Z, m 6= 0) (3.4)

for some number c0 > 0 that depends only on τ and ε.

25
 Let a/q be the convergent in the continued fraction expansion of kγ which has the

largest denominator q not exceeding c−1 D

0 x ; then,

a 1 c0
kγ − 6 −1 D = D . (3.5)
q qc0 x qx

Multiplying by q and using (3.4) we have

c0 x−D > |qkγ − a| > JqkγK > c0 |qk|−C .

Since |k| 6 xA it follows that q > x−A+D/C . By (3.3) we have q > c0 x1−D for

all sufficiently large x, hence by (3.5) we see that |kγ − a/q| 6 1/x. Applying

Lemma 5 with θ = kγ, and taking into account our choice of D and the inequalities

c0 x1−D 6 q 6 c−1 D
0 x , we derive the stated bound.

3.3 Beatty primes in arithmetic progressions

For the remainder of the paper, let α, β ∈ R be fixed with α > 1, and assume that α

is irrational. The following statement provides an explicit version of [7, Theorem 5.4].

Theorem 11. If α is of finite type τ = τ (α), then for any fixed ε > 0 we have

X 1 X
Λ(n) + O x1−1/(4τ +2)+ε ,


Λ(n) = (3.6)
n6x, n∈Bα,β
α n6x
n≡c (mod d) n≡c (mod d)

where the implied constant depends only on the parameters α, β and ε.

Proof. Let F (x; d, a) denote the left side of (3.6), and let ψ = ψα be defined by (3.2).

In view of Lemma 4 we have

X
F (x; d, a) = Λ(n)ψ(γn + δ),
n6x
n≡c (mod d)

26
where γ = α−1 and δ = α−1 (1 − β). Note that α and γ are of the same type, that is,

τ (α) = τ (γ).

By a classical result of Vinogradov (see [27, Chapter I, Lemma 12]), for any ∆
1
such that 0 < ∆ < 8
and ∆ 6 12 min{γ, 1 − γ}, there is a real-valued function Ψ with

the following properties:

(i) Ψ is periodic with period one;

(ii) 0 6 Ψ(t) 6 1 for all t ∈ R;

(iii) Ψ(t) = ψ(t) if ∆ 6 {t} 6 γ − ∆ or if γ + ∆ 6 {t} 6 1 − ∆;

P
(iv) Ψ(t) = k∈Z g(k)e(kt) for all t ∈ R, where g(0) = γ, and the other Fourier

coefficients satisfy the uniform bound

g(k)  min |k|−1 , |k|−2 ∆−1


(k 6= 0). (3.7)

Using properties (i)–(iii) it follows that

X

F (x; d, a) = Λ(n)Ψ(γn + δ) + O V (I, x) log x , (3.8)
n6x
n≡c (mod d)

where V (I, x) is the number of positive integers n 6 x such that

{γn + δ} ∈ I = [0, ∆) ∪ (γ − ∆, γ + ∆) ∪ (1 − ∆, 1).

Since |I| = 4∆, it follows from the definition (3.1) and Lemma 3 that

V (I, x)  ∆x + x1−1/τ +o(1) (x → ∞). (3.9)

Now let K > ∆−1 be a large real number, and let ΨK be the trigonometric

polynomial defined by
X
ΨK (t) = g(k)e(kt). (3.10)
|k|6K

27
Using (3.7) it is clear that the estimate

Ψ(t) = ΨK (t) + O(K −1 ∆−1 ) (3.11)

holds uniformly for all t ∈ R. Combining (3.11) with (3.8) and taking into account

(3.9), we derive that

X
Λ(n)ΨK (γn + δ) + O ∆x log x + x1−1/τ +ε + K −1 ∆−1 x .


F (x; d, a) =
n6x
n≡c (mod d)

For fixed A ∈ (0, 1) (to be specified below) we now set

∆ = x−A/2 and K = xA .

By the definition (3.10) it follows that

X X
Λ(n)e(kγn) + O x1−1/τ +ε + x1−A/2+ε .


F (x; d, a) = g(k)e(kδ)
|k|6xA n6x
n≡c (mod d)

Using Lemma 6 together with (3.7) we see that

X X X X
g(k)e(kδ) Λ(n)e(kγn)  |k|−1 Λ(n)e(kγn)
|k|6xA n6x |k|6xA n6x
k6=0 n≡c (mod d) k6=0 n≡c (mod d)
A+2+1/τ
+ε
x 2+2/τ + x4/5 (log x)4 .

Since g(0) = γ we therefore have

X  A+2+1/τ 
F (x; d, a) = γ Λ(n) + O x 2+2/τ +ε + x4/5+ε + x1−1/τ +ε + x1−A/2+ε .
n6x
n≡c (mod d)

Taking A = 1/(2τ + 1) we obtain the desired estimate (3.6).

3.4 Construction of Carmichael numbers

In this section, we outline our proof of Theorem 18. We shall be brief since our

construction of Carmichael numbers composed of primes from Beatty sequence Bα,β

28
closely parallels (and relies on) the construction of “ordinary” Carmichael numbers

given in [1]. Here, we discuss only those modifications that are needed to establish

Theorem 18.

Let P denote the set of all prime numbers, and set Pα,β = P ∩ Bα,β . The

underlying idea behind our proof of Theorem 18 is to show that Pα,β is sufficiently

well-distributed over arithmetic progressions so that, following the method of [1], the

primes used to form Carmichael numbers can all be drawn from Pα,β rather than P.

Unfortunately, this idea appears only to succeed in the case that α is of finite type,

which we now assume for the remainder of this section.

Let τ = τ (α) < ∞ be the type of α. Using the standard estimate

X X
Λ(n) = log p + O(x1/2 )
n6x p6x

together with Theorem 11, it follows that

X 1 X
log p − log p 6 x1−1/(4τ +2)+ε (x > x1 (α, β, ε)).
p6x, p∈Bα,β
α p6x
p≡c (mod d) p≡c (mod d)

For any modulus d 6 (4α)−1 x1/(4τ +2)−ε the right side of this inequality does not exceed

x/(4αϕ(d)); therefore, applying [1, Theorem 2.1] and taking into account the above

inequality, we derive the following statement, which plays a role in our construction

analogous to that played by [1, Theorem 2.1].

Lemma 7. For every B ∈ 0, 4τ1+2 there exist numbers ηB > 0, x2 (B) and DB such

that for all x > x2 (B) there is a set DB (x) consisting of at most DB integers such

that
X x x
log p − 6
p6x, p∈Bα,β
αϕ(d) 2α ϕ(d)
p≡c (mod d)

29
whenever d is not divisible by any element of DB (x), 1 6 d 6 xB , and c is coprime

to d. Furthermore, every number in DB (x) exceeds log x, and all, but at most one,

exceeds xηB .

We remark that, in the statement of Lemma 7, ηB , x2 (B), DB and DB (x) all

depend on the parameters α and β, but we have suppressed this from the notation

for the sake of clarity. Similarly, x3 (B) depends on α and β in the statement of

Lemma 8 below.

As an application of Lemma 7 we deduce the following statement, which extends

[1, Theorem 3.1] to the setting of primes in a Beatty sequence.

Lemma 8. Suppose that B ∈ 0, 4τ1+2 . There exists a number x3 (B) such that if

x > x3 (B) and L is a squarefree integer not divisible by any prime exceeding x(1−B)/2

1/q 6 (1−B)/(32α), then there is a positive integer k 6 x1−B

P
and for which prime q | L

with gcd(k, L) = 1 such that

# d | L : dk + 1 6 x and p = dk + 1 is a prime in Bα,β



2−DB −2 
> # d | L : 1 6 d 6 xB .
α log x
Sketch of Proof. Let π(x; d, a) [resp. πα,β (x; d, a)] be the number of primes [resp.

primes in Pα,β ] up to x that belong to the arithmetic progression a mod d. Us-

ing Lemma 7 we can replace the lower bound [1, Equation (3.2)] with the bound

1 dx1−B
πα,β (dx1−B ; d, 1) > .
2α ϕ(d) log x

Also, since πα,β (x; d, a) never exceeds π(x; d, a), the upper bound that follows [1,

Equation (3.2)] can be replaced with the bound

8 dx1−B
πα,β (dx1−B ; dq, 1) 6 .
q(1 − B) ϕ(d) log x

30
 P
Taking into account the inequality prime q | L 1/q 6 (1 − B)/(32α), the proof is

completed using arguments given in the proof of [1, Theorem 3.1].

Let π(x) be the number of primes p 6 x, and let π(x, y) be the number of those

for which p − 1 is free of prime factors exceeding y. As in [1], we denote by E the set

of numbers E in the range 0 < E < 1 for which there exist numbers x4 (E), γ(E) > 0

such that

π(x, x1−E ) > γ(E)π(x)

for all x > x4 (E). With only a very slight modification to the proof of

[1, Theorem 4.1], using Lemma 8 in place of [1, Theorem 3.1], we derive the fol-

lowing quantitative version of Theorem 18.

0, 4τ1+2


Theorem 12. For each E ∈ E, B ∈ and ε > 0, there is a number

x4 = x4 (α, β, E, B, ε) such that for any x > x4 , there are at least xEB−ε Carmichael

numbers up to x composed solely of primes from Pα,β .

3.5 Dickson’s conjecture and Beatty primes

As before, we fix α, β ∈ R with α > 1, and assume that α is irrational. In this section,

we do not assume that α is of finite type.

Let {f1 , . . . , fk } be a set of linear polynomials of the type fj (X) = aj X + bj with

aj , bj ∈ Z and aj > 1. In 1904, Leonard Dickson [12] made the following well known

and widely believed conjecture.

Conjecture I. Suppose that there is no integer n > 1 with the property that n |

f1 (m) · · · fk (m) for all m ∈ Z. Then, there exist infinitely many m ∈ N such that all

of the numbers f1 (m), . . . , fk (m) are prime.

31
 Let S be the set of natural numbers m for which f1 (m), . . . , fk (m) are all prime

numbers. If S is an infinite set, then it seems reasonable to expect that for every irra-

tional number γ the sequence of fractional parts ({mγ})m∈S is uniformly distributed

in [0, 1); in particular, for any interval I contained in [0, 1) we expect that

#{m 6 M : m ∈ S and {mγ} ∈ I}

lim = |I|. (3.12)
M →∞ #{m 6 M : m ∈ S}

This is easy to prove when k = 1 (see [22]), and this is the only case in which the

truth of Conjecture I has been established (Dirichlet’s theorem). For other cases,

numerical evidence in support of (3.12) can be acquired when the set {f1 , . . . , fk }

and the interval I have been specified explicitly. For our purposes here, however, we

require only a weak hypothesis implied by (3.12).

Conjecture II. If S is an infinite set, then for every irrational number γ and every

interval I in [0, 1) with |I| > 0, there are infinitely many numbers m ∈ S for which

{mγ} ∈ I.

Combining both conjectures, we obtain the following conditional result.

32
Theorem 13. Assume both Conjectures I and II are true, and suppose that

(i) there is no integer n > 1 such that n | f1 (m) · · · fk (m) for all m ∈ Z;

(ii) there is an integer m such that all of the numbers f1 (m), . . . , fk (m) lie in the

Beatty sequence Bα,β .

Then, for infinitely many m ∈ N, all of the numbers f1 (m), . . . , fk (m) are prime

numbers that occur in Bα,β .

Proof. For any real numbers c, d with c < d, we denote by (c, d] + Z the sumset of

the interval (c, d] and Z; that is,


(c, d] + Z = x + m : x ∈ (c, d] and m ∈ Z .

Let Ω be the collection of all such sumsets (c, d] + Z together with the empty set ∅,

and let Ω◦ be the collection of all finite unions of sets in Ω. Note that Ω is closed

under finite intersections, and Ω◦ is closed under finite intersections and finite unions.

As before, we let S denote the set of m ∈ N such that f1 (m), . . . , fk (m) are

all prime numbers. Under Conjecture I and using (i) we see that S is an infinite

set. Hence, under Conjecture II it follows that for any irrational number γ, the set

Sγ = {mγ : m ∈ S} has an infinite intersection with every set (c, d]+Z, and therefore

Sγ has an infinite intersection with every nonempty set in Ω◦ .

For each j = 1, . . . , k it follows from Lemma 4 that

fj (m) ∈ Bα,β ⇐⇒ γ(aj m + bj ) + δ ∈ (0, γ] + Z
aj  
[
⇐⇒ γm ∈ (ci,j , di,j ] + Z ,
i=1

where
i − γbj − δ γ
ci,j = and di,j = ci,j + (i = 1, . . . , aj ).
aj aj

33
Hence, if we put
aj 
k [ 
\
T = (ci,j , di,j ] + Z ,
j=1 i=1

then mγ ∈ T if and only if all of the numbers f1 (m), . . . , fk (m) lie in the Beatty

sequence Bα,β . Clearly, T belongs to Ω◦ , and T =

6 ∅ by (ii). By the previous

argument, we conclude that Sγ has an infinite intersection with T , and the result

follows.

Theorem 14. Assume both Conjectures I and II are true and β = 1. Then, there

are infinitely many Carmichael numbers composed solely of primes from the Beatty

sequence Bα,β .

Proof. The linear polynomials

f1 (X) = 6X + 1, f2 (X) = 12X + 1 and f3 (X) = 18X + 1

satisfy condition (i) of Theorem 13, hence it suffices to show that condition (ii)

also holds when β = 1. Indeed, when this is the case, Theorem 13 implies (under

Conjectures I and II) that there are infinitely many triples (p, q, r) of primes in Bα,β

with p = 6m + 1, q = 12m + 1 and r = 18m + 1 for some m ∈ N, and for any such

triple the number N = pqr is a Carmichael number of the required form.

When β = 1 we see that δ = γ(1 − β) = 0. Hence, in the notation of the proof of

Theorem 13 we have

a1 = 6, a2 = 12, a3 = 18, b1 = b2 = b3 = 1,

and therefore,

γ γ γ
c6,1 = 1 − , c12,2 = 1 − , c18,3 = 1 − , d6,1 = d12,2 = d18,3 = 1.
6 12 18
34
 γ
We deduce that T contains the set (1 − 18 , 1] + Z, which shows that condition (ii) of

Theorem 13 is satisfied.

35
36
Bibliography

[1] A. Abercrombie, ‘Beatty sequences and multiplicative number theory,’ Acta

Arith. 70 (1995), 195–207.

[2] W. Alford, A. Granville, and C. Pomerance, ‘There are infinitely many

Carmichael numbers,’ Ann. of Math. (2) 139 (1994), 703–722.

[3] A. Balog and A. Perelli, ‘Exponential sums over primes in an arithmetic progres-

sion,’ Proc. Amer. Math. Soc. 93 (1985), 578–582.

[4] W. Banks, ‘Carmichael numbers with a square totient,’ Canad. Math. Bull. 52 (1)

(2009), no. 1, 3–8.

[5] W. Banks, ‘Carmichael numbers with a totient of the form a2 + nb2 ,’ to appear

in Monat. Math.

[6] W. Banks and C. Pomerance, ‘On Carmichael numbers in arithmetic progres-

sions,’ J. Aust. Math. Soc. 88 (2010), 313–321.

[7] W. Banks and I. Shparlinski, ‘Prime numbers with Beatty sequences,’ Colloq.

Math. 115 (2009), no. 2, 147–157.

[8] W. Banks and I. Shparlinski, ‘Non-residues and primitive roots in Beatty se-

quences,’ Bull. Austral. Math. Soc. 73 (2006), 433–443.

37
 [9] W. Banks and I. Shparlinski, ‘Short character sums with Beatty sequences,’

Math. Res. Lett. 13 (2006), 539–547.

[10] A. Begunts, ‘An analogue of the Dirichlet divisor problem,’ Moscow Univ. Math.

Bull. 59 (2004), no. 6, 37–41.

[11] Y. Bugeaud, Approximation by algebraic numbers. Cambridge Tracts in Mathe-

matics, 160. Cambridge University Press, Cambridge, 2004.

[12] L. E. Dickson, ‘A new extension of Dirichlet’s theorem on prime numbers,’ Mes-

senger of mathematics 33 (1904), 155-161.

[13] A. Fraenkel and R. Holzman, ‘Gap problems for integer part and fractional part

sequences,’ J. Number Theory 50 (1995), 66–86.

[14] J. Grantham, ‘There are infinitely many Perrin pseudoprimes,’ J. Number Theory

130 (2010), no. 5, 1117–1128.

[15] A. Khinchin, ‘Zur metrischen Theorie der diophantischen Approximationen,’

Math. Z. 24 (1926), no. 4, 706–714.

[16] T. Komatsu, ‘A certain power series associated with a Beatty sequence,’ Acta

Arith. 76 (1996), 109–129.

[17] T. Komatsu, ‘The fractional part of nϑ + ϕ and Beatty sequences,’ J. Théor.

Nombres Bordeaux 7 (1995), 387–406.

[18] L. Kuipers and H. Niederreiter, Uniform distribution of sequences. Pure and

Applied Mathematics. Wiley-Interscience, New York-London-Sydney, 1974.

38
[19] A. Lavrik, ‘Analytic method of estimates of trigonometric sums by the primes of

an arithmetic progression,’ (Russian) Dokl. Akad. Nauk SSSR 248 (1979), no. 5,

1059–1063.

[20] G. Lü and W. Zhai, ‘The divisor problem for the Beatty sequences,’ Acta Math.

Sinica 47 (2004), 1213–1216 (in Chinese).

[21] K. O’Bryant, ‘A generating function technique for Beatty sequences and other

step sequences,’ J. Number Theory 94 (2002), 299–319.

[22] P. Ribenboim, The new book of prime number records. Springer-Verlag, New

York, 1996.

[23] K. Roth, ‘Rational approximations to algebraic numbers,’ Mathematika 2 (1955),

1–20.

[24] K. Roth, ‘Corrigendum to “Rational approximations to algebraic numbers”,’

Mathematika 2 (1955), 168.

[25] W. Schmidt, Diophantine approximation. Lecture Notes in Mathematics, 785.

Springer, Berlin, 1980.

[26] R. Tijdeman, ‘Exact covers of balanced sequences and Fraenkel’s conjecture,’

Algebraic number theory and Diophantine analysis (Graz, 1998), 467–483, de

Gruyter, Berlin, 2000.

[27] I. Vinogradov, The method of trigonometrical sums in the theory of numbers.

Dover Publications, Inc., Mineola, NY, 2004.

39
40
Chapter 4

Carmichael meets Chebotarev

4.1 Introduction

The aim of the present work is to prove the following extension of the result mentioned

in the previous chapter, the existence of infinitely many Carmichael numbers from

Alford, Grandville, and Pomerence.

Theorem 15. Let K/Q be a finite Galois extension. Then, there are infinitely many

Carmichael numbers composed solely of primes for which the associated class of Frobe-

nius automorphisms equals a given conjugacy class of Gal(K|Q).

Let K/Q be any number field and K

e its Galois closure. Taking the conjugacy

class of the identity automorphism of K

e in Theorem 18 it follows that there exist

infinitely many Carmichael numbers composed solely of primes that split completely

in K.
e Since such primes will necessarily split completely in K, we immediately obtain

the following result.

Corollary 1. For any fixed algebraic number field K, there are infinitely many

Carmichael numbers which are composed solely of primes that split completely in

K.

Since prime numbers and Carmichael numbers are linked by the common property

41
given by Fermat’s Little Theorem, it is natural to ask whether certain questions about

primes can be settled for Carmichael numbers; see [2, 3]. For example, it is well known

that for every natural number n, there are infinitely many primes of the form a2 + nb2

with a, b ∈ Z (see the book [4] by Cox), so it is natural to ask whether the same

result holds for the set of Carmichael numbers. As a result of Corollary 1, we give an

affirmative answer to this question.

Corollary 2. For any fixed natural number n, there are infinitely many Carmichael

numbers of the form a2 + nb2 with a, b ∈ Z.

Indeed, let Sn = {a2 +nb2 : a, b ∈ Z}, and let Kn be the ring class field associated
√ √
to the order Z[ −n ] in the imaginary quadratic field Q( −n ). According to [4,

Theorem 9.4], if p is an odd prime not dividing n, then p splits completely in Kn if

and only if p ∈ Sn . Applying Corollary 1 with K = Kn , we see that there are infinitely

Carmichael numbers N composed solely of primes p ∈ Sn . Since Sn is closed under

multiplication, every such N also lies in Sn , and the corollary follows.

In a different direction taking K = Q(µd ), where µd is a primitive dth root of

unity, we obtain:

Corollary 3. There are infinitely many Carmichael numbers composed solely of

primes p ≡ a (mod d) with a, d coprime.

4.2 Preliminaries

Let K/Q be a finite Galois extension of degree nK = [K : Q] and absolute discriminant

DK . We put

NK = d ∈ N : gcd(d, DK ) = 1 .

(4.1)

42
For any Galois extension M/N and any unramified prime ideal p of N , (p, M |N ) will

denote the conjugacy class of Frobenius automorphisms of Gal(M/N ) corresponding

to the prime ideals of M above p.

Given a conjugacy class C in Gal(K/Q), let

PC = {p ∈ NK : (p, K|Q) = C}.

For d ∈ N and M a number field, put Md = M (µd ), where µd is a primitive dth

root of unity. According to [12, Proposition 2.7], the discriminant of Qd is

dφ(d)
DQd = (−1)φ(d)/2 Q φ(d)/(p−1)
, (4.2)
p|d p

where φ(·) is the Euler function.

Lemma 9. For each d ∈ NK , Kd is a Galois extension of Q of degree nK φ(d) with

discriminant
φ(d)
DKd = DK DQndK .

Furthermore, Gal(Kd /Q) ' Gal(K/Q) × Gal(Qd /Q), where the isomorphism is given

by the restriction map σ → (σ|K , σ|Qd ).

Proof. In view of (4.1) and (4.2), the discriminants DK and DQd are coprime for every

d ∈ NK . It follows from [10, Ch.3, Corollary 2.10] that K ∩ Qd = Q. The result now

follows from [10, Ch. 1, Proposition 2.11] and [5, 14.4, Corollary 22].

The constants c0 , c1 , c2 , . . . that appear in our proofs are assumed to be positive

and depend only on the field K. All constants implied by the symbols O,  and

 are absolute; we write OK , K and K to indicate that the implied constant

depends on K.

43
4.3 Zeros of Dedekind zeta functions

For each d ∈ NK , let ζd (s) be the Dedekind zeta function ζKd (s) associated with the

field Kd considered in §4.2.

Lemma 10. There are constants c1 , c2 > 0 depending only on K with the property

that for all T > 1 and U > 2 there exists a proper integral ideal f = f(K, U, T ) of K

such that for any d ∈ NK with d 6 U , f | dOK , where OK is the ring of integers of

K, whenever ζd (s) has a zero β + iγ in the region

 
c1
Ω(T, U ) = β + iγ : β > 1 − , |γ| 6 T . (4.3)
log(c2 T U )

Proof. We use the notation of [13, §1]. For each d ∈ NK with d 6 U , and any

Dirichlet character χ modulo (d) = dOK of conductor fχ , we see that

dχ := |DK |NK/Q (fχ )  dnK 6 U nK .

K

Hence, it follows that dχ 6 (c2 U )nK for some constant c2 = c2 (K). Applying [13,

Theorem 1.9] with Q = (c2 U )nK and

L = log(QT nK ) = nK log(c2 T U ),

we see that for some constant c1 = c1 (K), any Hecke L-function L(s, χ) with dχ 6 Q

has at most one zero in the region Ω(T, U ). Moreover, the remark following [13,

Theorem 1.9] asserts that there is at most one function L(s, χ∗ ) vanishing in Ω(T, U )

among all L(s, χ) associated with primitive characters χ with dχ 6 Q. If such a zero

exists, then it is a real number β∗ (which can be bounded in terms of Q). For such a

zero we have
c1 c1
β∗ > 1 − >1− .
log(c2 T U ) log c2

44
Replacing c1 by a smaller constant (which also depends only on K), we can assume

that ζK (β∗ ) 6= 0, i.e., χ∗ is not the trivial character.

By [10, Ch.7, Corollary 10.5]

Y
ζd (s) = ζK (s) L(s, χ, Kd |K)
χ6=1

is the product of Artin L-functions, where χ runs over the irreducible characters of

Gal(Kd /K). Let Kχ be the fixed field of the kernel of χ. Then, χ is injective as a

character of Gal(Kχ /K). Hence, by [10, Ch.7, Theorem 10.6] there exists a primitive

Dirichlet character χ
e modulo the conductor fχ of the extension Kχ /K such that

L(s, χ, Kd |K) = L(s, χ

e).

Furthermore, since K ⊆ Kχ ⊆ Kd , we see by [7, 5.1.5] and the last paragraph of [7,

§6] that the conductor fχ divides (d); thus, dχe 6 Q.

Using the remarks above we conclude that ζd (s) vanishes in Ω(T, U ) if and only

if L(s, χ∗ ) is a factor of ζd (s) and L(β∗ , χ∗ ) = 0. In this case, we know that fχ∗ | (d)

and fχ∗ 6= 1; thus, we can take f = fχ∗ .

Lemma 11. There are constants c3 , c4 , c5 > 0 depending only on K with the property

that for all d ∈ NK , T > c3 d, and σ > 1 − 1/c5 , the number Nd (σ, T ) of zeros β + iγ

of ζd (s) with β > σ and |γ| 6 T satisfies the bound

Nd (σ, T ) 6 c4 (T d)c5 (1−σ) .

Proof. We continue to use notation of [13, §1]. As in the proof of Lemma 10, for each

d ∈ NK let H (in the notation of [13, §1]) denote the trivial subgroup of the ideal

class group I((d))/P(d) modulo (d), and note that the quantities hH and d(H) defined

45
by [13, Equation (1.1b)] satisfy the bound

max{hH , d(H)} 6 (cd)nK

for some constant c = c(K) in view of [13, Lemma 1.16]. The result now follows by

applying [13, Corollary 4.4] with Q = (cd)nK and T > c3 d, where c3 = c3 (K) is any
1/nK
constant that is large enough so that the conditions T  1 and T > n2K hH of [13,

Corollary 4.4] are met (for the latter condition, any number c3 > cn2K suffices by the

inequality above).

4.4 Chebotarev Density Theorem

Our goal in this section is to provide a lower bound for the counting function of the

set

PCd = p ∈ PC : p ≡ 1 (mod d)


using an effective version of the Chebotarev density theorem given by [8].

By [10, Ch.1, Corollary 10.4] we see that p ≡ 1 (mod d) if and only if p splits

completely in Qd if and only if (p, Qd |Q) = {1d } for p ∈ NK , where 1d denotes the

identity element of Gal(Qd |Q). It follows by the isomorphism in Lemma 9 that there

exists a conjugacy class Cd in Gal(Kd /Q) (one that corresponds to C × {1d }) with

the property that

p ∈ PCd ⇐⇒ (p, Kd |Q) = Cd (p ∈ NK ).

Accordingly, we study the function

πC (x; d, 1) = #{p 6 x : p ∈ NK , (p, Kd |Q) = Cd }

46
and its weighted version

X
ψC (x; d, 1) = log p,
pm 6x
p, m:
(pm ,Kd |Q)=Cd

where the sum is taken over primes in NK . Our main result is the following:

Theorem 16. There are constants x1 , B > 0 depending only on K with the property

that for all x > x1 and every d ∈ NK with d 6 xB ,

|C| y
πC (y; d, 1) > (x4/5 6 y 6 x) (4.4)
2nK φ(d) log y

whenever ζd (s) has no zeros in the region

 
c1 3B
ΩB (x) = β + iγ : β > 1 − , |γ| 6 x . (4.5)
log(c2 x4B )
1
Proof. Let B = B(K) be a constant in the interval (0, 100 ) to be further determined

below. For convenience, we set

c1 log y
θB (y) = . (4.6)
log(c2 y 5B )

For x4/5 6 y 6 x, we have

θB (y) c1
1− >1− and y 3B 6 x3B ,
log y log(c2 x4B )

hence the region

 
e B (y) = β + iγ : β > 1 − θB (y) 3B
Ω , |γ| 6 y
log y

is contained in ΩB (x); therefore, ζd (s) has no zeros in Ω

e B (y) whenever it has no zeros

in ΩB (x).

Let g be a fixed element of Cd with d ∈ NK and d 6 xB , H = hgi the cyclic

subgroup of G generated by g, E the fixed field of H, and H

b the dual of H, i.e., the

set of irreducible characters χ : H → C× .

47
 Applying [8, Theorem 7.1] with the choices G = Gal(Kd |Q) and T = y 3B , and

taking into account the bounds

|G| = nKd = φ(d)nK  d 6 y 2B
K
(4.7)
log |DKd |  φ(d) (log |DK | + nK log d)  y 2B log y,
K

which hold by Lemma 9 for all d 6 xB 6 y 5B/4 , we derive that

|C| |C| |C| 1−B

ψC (y; d, 1) − y+ ZB (y)  y log y (4.8)
|G| |G| K |G|

where we have used |Cd | = |C|, and

!
X X yρ X 1
ZB (y) = χ(g) − .
ρ ρ ρ ρ
χ∈H
b
|γ|6T |ρ|< 12

Here, the inner sums are taken over the nontrivial zeros ρ = β + iγ of the Artin

L-functions L(s, χ, Kd |E) so that

Y
ζd (s) = L(s, χ, Kd |E).
χ∈H
b

Assuming ζd (s) has no zeros in the region ΩB (x), it follows by the functional equa-

tion of ζd (s) that every zero ρ = β + iγ of ζd (s), and thus also of each L(s, χ, Kd |E),

lies outside of the region

 
θB (y) 3B
β + iγ : 0 6 β 6 , |γ| 6 y ,
log y

and thus |ρ| > θB (y)/ log y  1/ log y for every such zero. We conclude that
K

X y ρ
X 1 X 1
−  y 1/2  nχ (0) y 1/2 log y,
ρ ρ ρ ρ |ρ|
K
1
ρ: β< 2
|ρ|< 12 |γ|61
|γ|61

where nχ (t) is the number of zeros β + iγ of L(s, χ, Kd |E) such that 0 < β < 1 and

|γ − t| 6 1. By [8, Lemma 5.4],

nK φ(d)
nχ (t)  log dχ + log(|t| + 2), (4.9)
|H|

48
where dχ = |DE |NE/Q (fχ ). Summing over all characters χ ∈ H
b and using (4.9) we

see that
!
X X yρ X 1 X d

1/2
χ(g) − y log y log dχ +
1
ρ ρ ρ
K |H|
χ∈H
b ρ: β< 2 χ∈H
b
(4.10)
|ρ|< 12
|γ|61

= y 1/2 log y log |DKd | + y 2B  y 1/2+2B log2 y,

K
Q
where the equality |DKd | = χ dχ follows from [10, Ch.3, Lemma 2.10] and the

Conductor-Discriminant formula [10, Ch.7, Proposition 11.9]. Moreover,

by c 3B
X yρ X 1 X X 1
 y 1/2 6y 1/2
;
ρ ρ |ρ| ρ |ρ|
ρ: β< 21 j=1
16|γ|6y 3B j6|γ|6j+1
1<|γ|6y 3B

thus, summing over the characters we obtain

by 3B c
X X yρ X 1 X nK φ(d) 
χ(g)  y 1/2 log dχ + log(j + 1)
ρ j |H|
χ∈H
b ρ: β< 12 j=1 χ∈H
b (4.11)
1<|γ|6y 3B

 y 1/2+2B log2 y.
K

In view of (4.10) and (4.11) we have

X X yρ
+ OK y 1/2+2B log2 y .


ZB (y) = χ(C) (4.12)
1
ρ
χ∈H
b ρ: β> 2
|γ|6y 3B

To estimate the sum in (4.12), we use ideas (and notation) from the proof of [1,

Theorem 2.1]. For each zero ρ = β + iγ in the sum, we have |y ρ | = y β and |ρ| >
1 b and write Pα for any sum over all zeros β + iγ of
+ |γ|  1 + |γ|. Fix χ ∈ H
4 σ

L(s, χ, Kd /E) with σ 6 β < α and |γ| 6 y 3B . Put τ = 1 − θB (y)/ log y, and note that
1
X yρ
=0
τ
ρ

e B (y). Hence, using the upper bound y β 6 y 1−1/c5 when

since ζd (s) has no zeros in Ω
Rβ
β 6 1 − 1/c5 and the identity y β = y 1−1/c5 + log y 1−1/c5
y σ dσ when β lies in the

49
range 1 − 1/c5 6 β 6 τ , it follows that
1−1/c5 ρ τ 1−1/c5 τ
X yρ X y X yρ X yβ X yβ
= +  +
ρ ρ ρ ρ 1 + |γ| 1 + |γ|
1/2 1−1/c5 1/2 1−1/c5
β> 21 , |γ|6y 3B
τ τ Z β
1−1/c5
X 1 X 1
y + log y y σ dσ (4.13)
1 + |γ| 1 + |γ| 1−1/c5
1/2 1−1/c5
Z τ τ
!
X 1 X 1
 y 1−1/c5 + log y yσ dσ.
ρ 1 + |γ| 1−1/c5 σ
1 + |γ|
|γ|6y 3B

Summing over all characters and using (4.9) the first term above can be bounded as

before:
3B
X X 1 X byXc X 1
χ(g) 6
ρ 1 + |γ| j=0 ρ 1 + |γ|
χ∈H
b χ∈H
b
|γ|6y 3B j6|γ|6j+1
(4.14)
by 3B c
X d log d + d log(1 + j)
  y 2B log2 y.
K
j=0
j+1

Let Nχ (σ, T ) be the number of zeros β + iγ of L(s, χ, Kd |E) with β > σ and |γ| 6 T .

Then, it follows by partial summation that for σ > 1 − 1/c5 ,

τ y 3B
Nχ (σ, y 3B )
Z
X 1 Nχ (σ, t)
6 Nχ (σ, c3 d) + + dt.
σ
1 + |γ| y 3B c3 d t2

Summing over all characters χ once again we obtain

τ y 3B
Nd (σ, y 3B )
Z
X X 1 Nd (σ, t)
χ(g)  Nd (σ, c3 d) + + dt. (4.15)
σ
1 + |γ| y 3B c3 d t2
χ∈H
b

By Lemma 11, we have for all σ > 1 − 1/c5 and d 6 xB 6 y 2B ,

τ Z y3B
X X 1 2 c5 (1−σ) c4 (y 3B d)c5 (1−σ) c4 (td)c5 (1−σ)
χ(g)  c4 (c3 d ) + 3B
+ 2
dt
σ
1 + |γ| y c3 d t
χ∈H
b
y 3B
tc5 (1−σ)
Z
4c5 B(1−σ) 2c5 B(1−σ)
y +y dt.
K 1 t2
Using the bound
(
y 3B
tc5 (1−σ) if 1 − 1/c5 6 σ 6 1 − 1/(2c5 )
Z
log y
dt 
1 t2 K 1 if σ > 1 − 1/(2c5 ),

50
and assuming that B < 1/(4c5 ), we derive that
Z τ τ
!
X X 1
yσ χ(g) dσ
1−1/c5 σ
1 + |γ|
χ∈H
b
Z τ Z 1−1/(2c5 )
σ 4c5 B(1−σ)
 y ·y dσ + y σ · y 2c5 B(1−σ) log y dσ
K 1−1/c5 1−1/c5
Z τ Z 1−1/(2c5 )
4c5 B σ(1−4c5 B) 2c5 B
=y y dσ + y log y y σ(1−2c5 B) dσ
1−1/c5 1−1/c5
τ (1−4c5 B) (1−1/(2c5 ))(1−2c5 B)
y y
 y 4c5 B + y 2c5 B
(1 − 4c5 B) log y (1 − 2c5 B)
1+B−1/(2c5 )
y exp(−(1 − 4c5 B)θB (y)) y
= +
(1 − 4c5 B) log y (1 − 2c5 B)
where we have used the definition of τ in the last step. Combining this bound with

(4.12), (4.13) and (4.14), and assuming further that B 6 1/(5c5 ), we find that

ZB (y)  y exp(− 51 θB (y)).

K

Finally, using (4.8) we see that

|C| |C|
cy exp(− 15 θB (y)) + y −B log2 y


ψC (y; d, 1) − y 6 (4.16)
|G| |G|

for some sufficiently large constant c = c(K).

To finish the proof, we now put

 
1 1 c1
B = min , , .
100 5c5 30 log(6c)

Note that B depends only on K, the bound (4.16) holds, and we have

 c  1
1
c exp − 6 .
30 B 6

On the other hand, from the definition (4.6) one sees that θB (y) > c1 /(6B) holds for

any y > y1 , where y1 = exp((log c2 )/B). Therefore,

1
c exp(− 15 θB (y)) 6 (y > y1 ). (4.17)
6
51
Increasing the value of y1 if necessary, we also have

1
c y −B log2 y 6 (y > y1 ). (4.18)
6
5/4
Put x1 = y1 so that the condition y > y1 is satisfied whenever x4/5 6 y 6 x and

x > x1 . Combining the bounds (4.16), (4.17) and (4.18) we obtain

2|C|
ψC (y; d, 1) > y (x4/5 6 y 6 x) (4.19)
3|G|

for all x > x1 . Partial summation yields

√
2|C| y 4 y |C| y
πC (y; d, 1) > − > (x4/5 6 y 6 x), (4.20)
3|G| log y log y 2|G| log y
√
where the last inequality holds when y > 24|G|/|C|, which is guaranteed by our

choice of B and d with d 6 xB . We finish the proof by noting that |G| = nK φ(d).

4.5 Construction of Carmichael numbers

In view of Theorem 16, our construction of Carmichael numbers with the property

stated in Theorem 18 follows closely that given in [1]. We shall be brief, since most

of the details are the same. Our principal tool is the following variant of [1, Theorem

3.1]:

Lemma 12. Let the constants x1 , B have the property stated in Theorem 16, and

suppose that x > x1 . If L is any squarefree number in NK that is not divisible by any

prime exceeding x(1−B)/2 , and

X 1 1
6 ,
q 60nK
prime q | L

then there is a positive number k 6 x1−B with gcd(k, L) = 1 such that

1
# d | L : dk + 1 ∈ PC , dk + 1 6 x > · # d | L : d 6 xB .
 
6nK log x

52
Proof. We use ideas (and notation) from the proof of [1, Theorem 3.1].

Observe that the region ΩB (x) defined by (4.5) is the same as the region Ω(T, U )

defined by (4.3) when we put T = x3B and U = xB .

Fix a prime p0 with the property that p0 | NK/Q (f), where f = f(K, xB , x3B ) is

given by Lemma 10. If L is divisible by p0 let L0 = L/p0 ; otherwise, let L0 = L. Note

that
1
# d | L0 : d 6 y > · # d | L : d 6 y
 
(y > 1) (4.21)
2

(see [1, p. 716]). Since p0 - L0 , for every divisor d of L0 with d 6 xB , Lemma 10

shows that ζd (s) has no zeros in ΩB (x); therefore, using the lower bound (4.4) from

Theorem 16 we have
|C| dx1−B
πC (dx1−B ; d, 1) > .
2nK φ(d) log x

On the other hand, since any prime divisor q of L does not exceed x(1−B)/2 , we have

from [9, Theorem 2]:

10 dx1−B
πC (dx1−B ; dq, 1) 6 π(dx1−B ; dq, 1) 6 .
q φ(d) log x

Therefore, the number of primes p ∈ PCd with p 6 dx1−B and such that gcd((p −

1)/d, L) = 1 is at least
X
πC (dx1−B ; d, 1) − πC (dx1−B ; dq, 1)
prime q | L
!
1 X 1 dx1−B x1−B
> − 10 > .
2nK q φ(d) log x 3nK log x
prime q | L

Using this bound together with (4.21) (instead of [1, Equation (3.1)]), the proof can

be concluded in the same manner as that of [1, Theorem 3.1]; the remaining details

are omitted.

We are now in a position to establish a quantitative version of Theorem 18.

53
Theorem 17. There are constants x0 , c0 > 0 depending only on K such that for all

x > x0 , there are at least xc0 Carmichael numbers up to x that are composed solely

of primes which split completely in K.

Proof. To prove this, we only need to modify the proof of [1, Theorem 4.1] slightly,

as follows.

Let E be the set of numbers E ∈ (0, 1) for which there exists a constant x2 > 0

depending only on E such that

π(x, x1−E )  π(x) (x > x2 ), (4.22)

E

where π(x, y) denotes the number of primes p 6 x such that p − 1 is free of prime

factors exceeding y.

Fix E = 3/5, which lies in the set E (see, e.g., [6]), and let x2 be a number for

which the bound (4.22) holds. Let x1 , B be numbers with the property stated in

Theorem 16, and put x3 = max{x1 , x2 }. Note that our choice of x3 depends only on

K.

Let y > 2 be a parameter and Q the set of primes q ∈ NK with

y 5/2 / log y < q 6 y 5/2

for which q − 1 is free of prime factors exceeding y. By (4.22)

X
|Q| > π(y 5/2 , y) − π(y 5/2 / log y) − 1  y 5/2 / log y (4.23)
q|DK

for all sufficiently large y. Let L be the product of primes in Q; then

X X
log L = log q 6 log q = ϑ(y 5/2 ) 6 1.1y 5/2
q∈Q q6y 5/2

54
for all y > 0, where we have used [11] for the last inequality. Furthermore,

Y Y log y 5/2
λ(L) = pa 6 pb log p
c
6 y 5π(y)/2 6 eπ·y (4.24)
pa ||λ(L) p6y

where the last inequality follows again by [11]. We also have

n(GL ) 6 λ(L)(1 + log L) 6 eπy (1 + 1.1y 5/2 ) 6 e5y , (4.25)

where GL = (Z/LZ)∗ .
1+δ
Let x = ey where δ = 5ε/(8B). Since

X 1 X 1 log log y 1
6 64 6
q q 5 log y 60nK
prime q |L y 5/2 / log y<q6y 5/2

for sufficiently large y, it follows from Lemma 12 that there exists an integer k coprime

to L, for which the set P of primes p 6 x with p ∈ PC and p = dk + 1 for some

divisor d of L, satisfies

1
· # d | L : 1 6 d 6 xB .

|P| > (4.26)
6nK log x

The product of any

log(xB )
 
u :=
log y 5/2

distinct prime factors of L, is a divisor d of L with d 6 xB . We deduce from (4.23)

that
   u
ω(L) B ω(L)
#{d|L : 1 6 d 6 x } > >
u u
u (4.27)
cy 5/2
 
> .
2B log x

Thus, by (4.26) and the identity (5/2 − 1 − δ)2B/5 = 3B/5 − ε/4,

b 2B log x
1  c 5 log y
c
|P| > y 5/2−1−δ > x3B/5−ε/3
6nK log x 2B

55
for all sufficiently large values of y. Now take P 0 = P\Q. Since |Q| 6 y 5/2 , it follows

by the above inequality that

|P 0 | > x3B/5−ε/2 (4.28)

for all sufficiently large values of y.

We may view P 0 as a subset of the group (Z/LZ)? by considering the residue class

of each p ∈ P 0 modulo L. If S is a subset of P 0 that contains more than one element

and if
Y
Π(S) := p ≡ 1 (mod L),
p∈S

then Π(S) is a Carmichael number. Indeed, every member of P 0 is 1 mod k so that

Π(S) ≡ 1 (mod k), and thus Π(S) ≡ 1 (mod kL), since (k, L) = 1. However, if p ∈ P 0

then p ∈ P so that p − 1 divides kL. Thus Π(S) satisfies Korselt’s criterion.

1+δ/2
Let t = ey . Then, by [1, Proposition 1.2], we see that the number of Carmichael

numbers of the form Π(S), where S ⊆ P 0 and |S| 6 t, is at least

 0  −1  0 btc
|P | |P 0 | |P |
> |P 0 |−n(GL ) > xt(3B/5−ε)
btc n(GL ) btc

for all sufficiently large values of y, using (4.25) and (4.28). But each such Carmichael

number Π(S) so formed is such that Π(S) 6 xt . Thus for X = xt we have C(X) >

X 3B/5−ε for all sufficiently large y. But X = exp(y 1+δ exp(y 1+δ/2 )), so that C(X) >

X 3B/5−ε for all sufficiently large values of X. Since y can be uniquely determined

from X, we complete the proof by taking c0 = EB/2.

56
Bibliography

[1] W. Alford, A. Granville, and C. Pomerance, ‘There are infinitely many

Carmichael numbers’, Ann. of Math. (2) 139 (1994), 703–722.

[2] W. Banks, ‘Carmichael numbers with a square totient’, Canad. Math. Bull. 52 (1)

(2009), no. 1, 3–8.

[3] W. Banks and C. Pomerance, ‘On Carmichael numbers in arithmetic progres-

sions’, to appear in J. Austral. Math. Soc.

[4] D.A. Cox, Primes of the form x2 + ny 2 . Fermat, class field theory, and complex

multiplication. John Wiley & Sons, Inc., New York, 1989.

[5] D.S. Dummit and R. M. Foote, Abstract Algebra. Third edition. John Wiley &

Sons, Inc., Hoboken, NJ, 2004. xii+932 pp. ISBN: 0-471-43334-9

[6] J.B. Friedlander, ‘Shifted primes without large prime factors’, in Number theory

and applications (ed. R. A. Mollin), (Kluwer, NATO ASI, 1989), 393–401.

[7] G. J., Janusz, Algebraic number fields, Pure and Applied Mathematics, Vol. 55.,

Academic Press [A Subsidiary of Harcourt Brace Jovanovich, Publishers], New

York-London, 1973. x+220 pp.

57
 [8] J. C. Lagarias and A. M. Odlyzko, ‘Effective versions of the Chebotarev density

theorem’, in Algebraic number fields: L-functions and Galois properties (Proc.

Sympos., Univ. Durham, Durham, 1975), 409–464.

[9] H. L. Montgomery and R.C. Vaughan, ‘The large sieve’, Mathematika 20 (1973),

119–134.

[10] J. Neukirch, Algebraic number theory. Grundlehren der Mathematischen Wis-

senschaften, 322. Springer-Verlag, Berlin, 1999.

[11] J. B. Rosser and L. Schoenfeld, ‘Approximate formulas for some functions of

prime numbers’, Illinois J. Math. 6 (1962), 64–94.

[12] L. C. Washington, Introduction to cyclotomic fields. Second edition. Graduate

Texts in Mathematics, 83. Springer-Verlag, New York, 1997.

[13] A. Weiss, ‘The least prime ideal’, J. Reine Angew. Math. 338 (1983), 56–94.

58
Chapter 5

Piatetski-Shapiro Primes from

Almost Primes

5.1 Introduction

The Piatetski-Shapiro sequences are those sequences of the form

(bnc c)n∈N (c > 1, c 6∈ N),

where btc denotes the integer part of any t ∈ R. Such sequences are named in honor
12
of Piatetski-Shapiro, who showed in [6] that for any number c ∈ (1, 11 ) the set

P (c) := p prime : p = bnc c for some n ∈ N



is infinite. The admissible range for c in this result has been extended many times

over the years and is currently known for all c ∈ (1, 243
205
) thanks to Rivat and Wu [8].

For any natural number r, let Nr denote the set of r-almost primes, i.e., the set

of natural numbers having at most r prime factors, counted with multiplicity. In this

chapter, we introduce and study sets of Piatetski-Shapiro primes of the form

Pr(c) := p prime : p = bnc c for some n ∈ Nr .



Our main result is the following:

59
 (c)
Theorem 18. For any fixed c ∈ (1, 77
76
) the set P8 is infinite. More precisely,

x
n 6 x : n ∈ N8 and bnc c is prime

 ,
(log x)2

where the implied constants in the symbol  depend only on c.

5.2 Notation

Throughout the chapter, we set γ := 1/c for a given real number c > 1.

The letter p always denotes a prime number.

We use Λ to denote the von Mangoldt function.

Any implied constants in the symbols O, , , ∼ may depend on c and on the

small parameters ε, δ but are absolute otherwise. We use notation of the form m ∼ M

as an abbreviation for M < m 6 2M .

As is customary, we put

e(t) := e2πit and {t} := t − btc (t ∈ R).

Throughout the chapter, we make considerable use of the sawtooth function defined

by

1 1
ψ(t) := t − btc − 2
= {t} − 2
(t ∈ R) (5.1)

as well as the well known approximation of Vaaler [10]: for any H > 1 there exist

numbers ah and bh such that

X X 1 1
ψ(t) − ah e(th) 6 bh e(th), ah  , bh  . (5.2)
|h| H
0<|h|6H |h|6H

60
5.3 Proof of Theorem 18
5.3.1 Initial approach

We analyze exponential sums that are relevant for finding primes in Pr(c) with the

number r as small as possible. The set that we sieve is

A := n 6 x : bnc c is prime .


For any d 6 D, where D is a fixed power of x to be specified later, we must estimate

accurately the cardinality of

Ad := n ∈ A : d | n .


Since md ∈ A if and only if

p 6 (md)c < p + 1 and md 6 x,

to within O(1) the cardinality of Ad is equal to the number of primes p 6 xc for which

the interval pγ d−1 , (p + 1)γ d−1 contains a natural number; thus,



p 6 xc : −(p + 1)γ d−1 < −m 6 −pγ d−1 for some m ∈ N


|Ad | = + O(1)
X 
−pγ d−1 − −(p + 1)γ d−1 + O(1)
  

=
p6xc
X
= Xd−1 + ψ(−(p + 1)γ d−1 ) − ψ(−pγ d−1 ) + O(1),


p6xc

where ψ is given by (5.1), and

X X x
X := ((p + 1)γ − pγ ) = γpγ−1 + O(1) ∼ (x → ∞).
p6xc p6xc
c log x

It is unnecessary to evaluate X more precisely than this; however, for any sufficiently

small ε > 0 we need to show that

X x1−ε/3
|Ad | − Xd−1 6 Xx−ε/3  (x → ∞). (5.3)
d6D
log x

61
Splitting the range of d into dyadic subintervals and using partial summation in a

standard way, it suffices to prove that the bound

X X
Λ(n) ψ(−(n + 1)γ d−1 ) − ψ(−nγ d−1 )  x1−ε/2


(5.4)
d∼D1 N <n6N1

holds uniformly for D1 6 D, N 6 xc , N1 ∼ N . In turn, (5.4) is an immediate

consequence of the uniform bound

X
Λ(n) ψ(−(n + 1)γ d−1 ) − ψ(−nγ d−1 )  x1−ε/2 d−1


(5.5)
N <n6N1

for d 6 D, N 6 xc , N1 ∼ N . Our aim is to establish (5.5) with D as large as possible,

and in this subsection we show that (5.5) holds when

D 6 x1−136c/157 (5.6)

and ε > 0 is sufficiently small. Suppose this has been done, and observe that

136c 8 8635
1− > whenever c < .
157 63 8568

Then, for any fixed c ∈ (1, 8635

8568
8
) and α ∈ ( 63 ,1 − 136c
157
), the inequality (5.3) with

D := xα implies the bound

X X
|Ad | − Xd−1  ,
d6D
(log X)2

thus we can apply the weighted sieve in the form [4, Ch. 5, Prop. 1] with the choices

63
R := 8, δR := 0.124820 · · · and g := .
8

Note that g < R − δR , and (if x is large enough) the inequality a < Dg holds for

all a ∈ A since αg > 1; thus, the conditions of [4, Ch. 5, Prop. 1] are met, and we

conclude that A contains at least  X/ log X numbers with at most eight prime

factors. This yields the statement of the theorem for all c in the interval (1, 8635
8568
).

62
 We now turn to the proof of (5.5) for all D satisfying (5.6). Let S denote the sum

on the left side of (5.5). From Vaaler’s approximation (5.2) we derive the inequality

X
|S| 6 |S1 | + S2 + S3 + 2b0 Λ(n), (5.7)
N <n6N1

where

X X
ah e(−h(n + 1)γ d−1 ) − e(−hnγ d−1 ) ,


S1 := Λ(n)
N <n6N1 0<|h|6H
X X
S2 := Λ(n) bh e(−h(n + 1)γ d−1 ),
N <n6N1 0<|h|6H
X X
S3 := Λ(n) bh e(−hnγ d−1 ).
N <n6N1 0<|h|6H

To ensure that the last term on the right side of (5.7) satisfies the bound

X
2b0 Λ(n)  x1−ε/2 d−1 ,
N <n6N1

we choose

H := x−1+ε N d. (5.8)

Next, we use a partial summation argument from the book of Graham and Kolesnik [3].

Writing
X X
S1 = ah Λ(n)φh (n)e(hnγ d−1 )
0<|h|6H N <n6N1

with

φh (t) := e(h(t + 1)γ d−1 − htγ d−1 ) − 1,

we would like to show that

X X
h−1 Λ(n)φh (n) e(hnγ d−1 )  x1−ε d−1 (d 6 D). (5.9)
0<|h|6H N <n6N1

Taking into account the bounds

φh (t)  hN γ−1 d−1 and φ0h (t)  hN γ−2 d−1 (N 6 t 6 N1 ),

63
the left side of (5.9) is, on integrating by parts, bounded by
X X
 h−1 φn (N1 ) Λ(n) e(hnγ d−1 )
h6H N <n6N1
X Z N1 X
+ h−1 φ0h (t) Λ(n) e(hnγ d−1 ) dt
h6H N N <n6t
X X
 N γ−1 d−1 Λ(n) e(hnγ d−1 )
h6H N <n6N2

for some number N2 ∈ (N, N1 ]. Therefore, it suffices to show that the bound
X X
Λ(n) e(hnγ d−1 )  x1−ε N 1−γ (5.10)
h6H N <n6N2

holds uniformly for d 6 D, N 6 xc , N2 ∼ N .

To establish (5.10) we use the decomposition of Heath-Brown [5]; it suffices to

show that our type I and type II sums satisfy the uniform bounds
X X X
SI := a` e(h`γ mγ d−1 )  x1−2ε N 1−γ , (5.11)
H1 6h6H2 `∼L m∼M
`m∈J
X X X
SII := a` bm e(h`γ mγ d−1 )  x1−2ε N 1−γ , (5.12)
H1 6h6H2 `∼L m∼M
`m∈J

in some specific ranges. Here, J is an interval in (N, N1 ], H1 6 H, H2 ∼ H1 ,

LM  N , and the numbers a` , bm ∈ C satisfy |a` | 6 1, |bm | 6 1. In view of [5, pp.

1367–1368] we need to show that (5.12) holds uniformly for all L in the range

u  L  N 1/3 for some u 6 x−ε N 1/5 , (5.13)

and for such u we need to show that (5.11) holds uniformly for all M satisfying

M  N 1/2 u−1/2 .

Put F := H1 N γ d−1 . For the type II sum, we apply Baker [1, Thm. 2], which

yields the bound

SII  TII,1 + TII,2 H1 N xε

64
with
 k/(2+2k)
−1/2 F
TII,1 := (H1 L) and TII,2 := M −(1+k−`)/(2+2k)
H1 L

for any exponent pair (k, `) provided that F > H1 L. For the type I sum, by Robert

and Sargos [9, Thm. 3] we have the bound

SI  TI,1 + TI,2 + TI,3 H1 N xε

with
 1/4
F
TI,1 := , TI,2 := M −1/2 and TI,3 := F −1 .
H1 LM 2

Hence, to establish (5.11) and (5.12) it suffices to verify that

max TI,1 , TI,2 , TI,3 , TII,1 , TII,2  x1−3ε H1−1 N −γ .


(5.14)

From the definition of F we see that the bound

TI,3 = F −1  x1−3ε H1−1 N −γ (5.15)

is equivalent to d  x1−3ε and thus follows from the inequality D 6 x1−3ε which is

implied by (5.6) when ε is small enough.

To guarantee that

TII,1 = (H1 L)−1/2  x1−3ε H1−1 N −γ (5.16)

holds for all L > u we simply define

u := x−2+6ε H1 N 2γ .

We need to check that the condition u 6 x−ε N 1/5 of (5.13) is met. For this, taking

into account (5.8), it suffices to have

D 6 x3−8ε N −4/5−2γ .

65
The worst case occurs when N = xc , leading to the constraint D 6 x1−4c/5−8ε , which

follows from (5.6) if ε is sufficiently small.

Next, if M satisfies the lower bound

−1/2
M  N 1/2 u−1/2 = x1−3ε H1 N 1/2−γ ,

then the upper bound

1/4
M −1/2  x−1/2+2ε H1 N −1/4+γ/2 (5.17)

holds; therefore, the bound

TI,2 = M −1/2  x1−3ε H1−1 N −γ (5.18)

holds provided that

H1  x6/5−4ε N 1/5−6γ/5 .

Using (5.8) again, we see that (5.18) follows from the inequality

D 6 x11/5−5ε N −4/5−6γ/5 .

Taking N := xc leads to the restriction D 6 x1−4c/5−5ε , and this is implied by (5.6)

when ε is small enough.

Next, using the definition of F and the relation LM  N one sees that the bound
 1/4
F
TI,1 =  x1−3ε H1−1 N −γ (5.19)
H1 LM 2

holds whenever

H1 M −1/4 d−1/4  x1−3ε N 1/4−5γ/4 .

Taking into account (5.8) and (5.17) this bound follows from the condition

D  x19/7−7ε N −6/7−12γ/7 .

66
With N := xc we derive the constraint D 6 x1−6c/7−7ε , which is a consequence of

(5.6) if ε is sufficiently small.

Our next goal is to establish the bound

k/(2+2k)
Nγ

TII,2 = M −(1+k−`)/(2+2k)  x1−3ε H1−1 N −γ . (5.20)
Ld

To begin, we check that the condition F > H1 L is met, or equivalently, that d 6

N γ L−1 . Since L  N 1/3 for the type II sum, it is enough to have

D 6 N γ−1/3−ε . (5.21)

If ε is sufficiently small, then (5.21) follows essentially from (5.6). Indeed, since c > 1

and γ := 1/c, the inequality

(1 − 136c/157)(2/3 + 2γ) < 2(γ − 1/3)

is easily verified; hence, for small enough ε (depending only on c) we have by (5.6):

2/3+2γ−ε
γ−1/3−ε
D2/3+2γ−ε 6 x1−136c/157 6 x2−3ε ,

which implies that

γ−1/3−ε
x2−3ε

1+γ
D 6 .
D

On the other hand, we can certainly assume that HN > x1−2ε N 1−γ , for otherwise

(5.11) and (5.12) are trivial; therefore

N 1+γ > x2−3ε d−1 ,

and we have
γ−1/3−ε γ−1/3−ε
x2−3ε x2−3ε
 
1+γ

γ−1/3−
D 6 6 6 N 1+γ ,
D d

67
which yields (5.21).

Using the relation LM  N , the upper bound M  N 2/3 (which follows from

L  N 1/3 ) and the definition (5.8), we see that the bound (5.20) holds if

dν−k  x2ν−4νε N −ν−γν−γk+k+2(1−`)/3 ,

where we have put ν := 2k + 2. The exponent of N is negative since

k + 2(1 − `)/3 < k + 1/3 < ν/2;

therefore, the worst case occurs when N = xc , and it suffices to have

D 6 x1−cµ/3−2ε , (5.22)

where
ν − k − 2(1 − `)/3 3k + 2` + 4
µ := = .
ν−k k+2
57 64
With the choice (k, `) := ( 126 , 126 ) (which is BA5 ( 12 , 21 ) in the notation of Graham [2])

we have
µ 803 136
= < ,
3 927 157

and therefore (5.22) follows from (5.6) if ε is small enough. This proves (5.20).

Combining the bounds (5.15), (5.16), (5.18), (5.19) and (5.20), we obtain (5.14),

and this completes the proof of Theorem 18 for c ∈ (1, 8635

8568
).

5.3.2 Refinement

Here, we extend the ideas of §5.3.1 to show that for any δ > 0, the bound (5.5) holds

for all sufficiently small ε > 0 (depending on δ) under the less stringent condition

that
380c
D 6 x1− 441 −δ . (5.23)

68
After this has been done, taking into account that

380c 8 77
1− > whenever c < ,
441 63 76

the proof of Theorem 18 for the full range c ∈ (1, 77

76
) is completed using the sieve

argument presented after (5.6).

Following Rivat and Sargos [7, Lem. 2] it suffices to show that

(i) The type II bound (5.12) holds for L in the range u0  L  u20 for some

u0 ∈ [N 1/10 , N 1/6 ];

−1/2
(ii) For such u0 , the type I bound (5.11) holds whenever M  N 1/2 u0 ;

(iii) For such u0 and any numbers am , ch ∈ C with |am | 6 1, |ch | 6 1, the type I 0

bound
X X X
SI 0 := ch am e(h`γ mγ d−1 )  x1−2ε N 1−γ
h∼H m∼M `∼L

holds whenever u20  L  N 1/3 .

Taking u := x−2+6ε H1 N 2γ as in §5.3.1, we put

u0 := max{N 1/10 , u}.

The condition u0 6 N 1/6 follows from the inequality x−2+6ε HN 2γ 6 N 1/6 , which in

view of (5.8) is implied by

D 6 x3−7ε N −5/6−2γ .

380 5
Taking N := xc leads to D 6 x1−5c/6−7ε , which follows from (5.23). Since 441
> 6

and u  L  N 1/3 holds whenever u0  L  u20 , the condition (i) is a consequence

of our work in §5.3.1.

69
 Condition (ii) also follows from §5.3.1 in the case that u > N 1/10 . When u < N 1/10

it suffices to show that

max TI,1 , TI,2 , TI,3  x1−3ε H1−1 N −γ


(5.24)

when M  N 9/20 . Taking into account (5.8) we see that the bound

TI,2 = M −1/2  x1−3ε H1−1 N −γ (5.25)

holds provided that

D 6 x2−4ε N −31/40−γ .

380 31
The worst case N = xc leads to D 6 x1−31c/40−4ε , and since 441
> 40
this is implied

by (5.23) when ε is small enough. We also know that (5.19) holds whenever

H1 M −1/4 d−1/4  x1−3ε N 1/4−5γ/4 .

Taking into account (5.8) this bound follows from the inequality

D 6 x8/3−3ε N −51/60−5γ/3 .

380 51
With N := xc we derive the constraint D 6 x1−51c/60−3ε , and as 441
> 60
this a

consequence of (5.23) if ε is small enough. Combining (5.15), (5.19) and (5.25) we

obtain (5.24) as required.

It remains to verify condition (iii). Rather than adapting Rivat and Sargos [7], we

quote an abstraction of their method due to Wu [11]. Taking k := 5 in [11, Thm. 2]

we have (in Wu’s notation) a bound of the form

(log x)−1 SI 0  (X 32 H 114 M 147 N 137 )1/174 + · · · .

However, in place of (X, H, M, N ) we use the quadruple (H1 N γ d−1 , M, H1 , L). The

triple of exponents (α, β, γ) becomes (γ, 1, γ) in our case, and it is straightforward to

70
check that the various hypotheses of [11, Thm. 2] are satisfied. Applying the theorem

and taking into account that H1 6 x−1+ε N d, it follows that

SI 0  TI 0 ,1 + TI 0 ,2 + TI 0 ,3 + TI 0 ,4 + TI 0 ,5 + TI 0 ,6 + TI 0 ,7 xε ,

where

1/174 1/2
TI 0 ,1 := H1179 N 114+32γ L23 d−32 , TI 0 ,5 := H1 N L−1/2 ,

3/4
TI 0 ,2 := H1 N 1/2+γ/4 L1/2 d−1/4 , TI 0 ,6 := H1 N 1/2 L1/2 ,

5/4 1/2
TI 0 ,3 := H1 N 1/2+γ/4 d−1/4 , TI 0 ,7 := H1 N 1−γ/2 d1/2 .

TI 0 ,4 := H1 N L−1 ,

It suffices to show that

max TI 0 ,1 , TI 0 ,2 , TI 0 ,3 , TI 0 ,4 , TI 0 ,5 , TI 0 ,6 , TI 0 ,7  x1−3ε N 1−γ


(5.26)

given that

N 6 xc , H1 6 x−1+ε N d and N 1/5  L  N 1/3 . (5.27)

First, we note that the bound

1/174
TI 0 ,1 = H1179 N 114+32γ L23 d−32  x1−3ε N 1−γ (5.28)

is equivalent to

H1179 N −60+206γ L23 d−32  x174−522ε .

Using the first two inequalities and the upper bound on L in (5.27), it suffices to have

D147 6 x147−380c/3−701ε ,

71
which is (5.23). Similarly, the bounds

3/4
TI 0 ,2 = H1 N 1/2+γ/4 L1/2 d−1/4  x1−3ε N 1−γ , (5.29)

TI 0 ,6 = H1 N 1/2 L1/2  x1−3ε N 1−γ , (5.30)

follow from the inequalities

D 6 x1−5c/6−15ε/2 and D 6 x1−2c/3−4ε ,

380 5
respectively, and these are easy consequences of (5.23) since 441
> 6
> 23 . On the

other hand, using the first two inequalities and the lower bound on L in (5.27), we

see that both bounds

TI 0 ,4 = H1 N L−1  x1−3ε N 1−γ , (5.31)

1/2
TI 0 ,5 = H1 N L−1/2  x1−3ε N 1−γ , (5.32)

follow from the inequality

D 6 x1−4c/5−7ε ,

380
which is implied by (5.23) since 441
> 54 . Next, using the first two inequalities in

(5.27) and disregarding the bounds on L, it is easy to check that

5/4
TI 0 ,3 = H1 N 1/2+γ/4 d−1/4  x1−3ε N 1−γ (5.33)

follows from

D  x1−3c/4−17ε/4 ,

380
which is implied by (5.23) since 441
> 34 . Similarly,

1/2
TI 0 ,7 = H1 N 1−γ/2 d1/2  x1−3ε N 1−γ (5.34)

72
is a consequence of the inequality

D  x1−c/2−7ε/2 ,

380
which follows from (5.23) since 441
> 12 .

Combining the bounds (5.28), (5.29), (5.30), (5.31), (5.32), (5.33) and (5.34), we

obtain (5.26), and Theorem 18 is proved.

73
74
Bibliography

[1] R. C. Baker, ‘The square-free divisor problem,’ Quart. J. Math. Oxford 45

(1994), 269–277.

[2] S. W. Graham, ‘An algorithm for computing optimal exponent pairs,’ J. London

Math. Soc. (2) 33 (1986), no. 2, 203–218.

[3] S. W. Graham and G. Kolesnik, Van der Corput’s method of exponential sums.

London Mathematical Society Lecture Note Series, 126. Cambridge University

Press, Cambridge, 1991.

[4] G. Greaves, Sieves in Number Theory. Results in Mathematics and Related Areas

(3), 43. Springer-Verlag, Berlin, 2001.

[5] D. R. Heath-Brown, ‘Prime numbers in short intervals and a generalized Vaughan

identity,’ Canad. J. Math. 34 (1982), no. 6, 1365–1377.

[6] I. I. Piatetski-Shapiro, ‘On the distribution of prime numbers in the sequence of

the form bf (n)c,’ Mat. Sb. 33 (1953), 559–566.

[7] J. Rivat and P. Sargos, ‘Nombres premiers de la forme bnc c,’ Canad. J. Math.

53 (2001), no. 2, 414–433.

75
 [8] J. Rivat and J. Wu, ‘Prime numbers of the form bnc c,’ Glasg. Math. J. 43 (2001),

no. 2, 237–254.

[9] O. Robert and P. Sargos, ‘Three-dimensional exponential sums with monomials,’

J. Reine Angew. Math. 591 (2006), 1–20.

[10] J. D. Vaaler, ‘Some extremal problems in Fourier analysis,’ Bull. Amer. Math.

Soc. 12 (1985), 183–216.

[11] J. Wu, ‘On the primitive circle problem,’ Monatsh. Math. 135 (2002), no. 1,

69–81.

76
 VITA

Aaron Yeager was born on December 28, 1976 in Springfield, Missouri. In 1995

he graduated from Kickapoo High School. In 2002, after a few years spent pursuing

a career in professional skateboarding, he began college at Los Angeles City College.

He graduated with an AS in mathematics from LACC in 2005. From 2005 to 2006

Aaron attended Cal State Los Angeles. In 2006 Aaron returned home to be with

family and attend Missouri State University. He graduated from MSU with a BS in

mathematics in 2008. Aaron began his graduate work at the University of Missouri

in 2008. In fall 2012, Aaron received his MA in mathematics from the University of

Missouri-Columbia.

77