# Integral Points Close to Smooth Plane Curves

ZiAn Zhao (Cody)

###### Abstract

This is an exposition of a class of problems and results on the number of
integral points close to plane curves. We give a detailed proof of a theorem
of Huxley and Sargos, following the account of Bordellès. Along the way we
correct an oversight in the proof, changing some of the explicit values of the
constants in the theorem.

###### Contents

  1. 1 Introduction
  2. 2 The Theorem of Huxley and Sargos
    1. 2.1 Lagrange Interpolation Polynomial
    2. 2.2 The First, Second and $k$th Derivative Test
    3. 2.3 Preparatory Lemmas and Major Arcs
    4. 2.4 The Proof of the Theorem of Huxley and Sargos
  3. 3 Optimality of The Methods
    1. 3.1 Integral Points Around Polynomials
    2. 3.2 Further Refinements
    3. 3.3 Smooth Curves
  4. 4 Applications
    1. 4.1 Diophantine Inequality
    2. 4.2 The Squarefree Number Problem

##  1 Introduction

The topic of this essay is the methods used to estimate the number of integer
points around smooth curves in $\mathbb{R}^{2}$. In the second chapter, we
will look at some relatively weaker statements and eventually build up to a
theorem by Huxley and Sargos [11]. The explicit statement [1, Theorem 5.5] of
the main theorem given by Huxley and Sargos has some issues. In Lemma 7, the
only English-language version [1, Lemma 5.13] suggest that if a point is
outside the proper major arc, then the Lagrange polynomial won’t intersect it,
but this is not the case. If we only fix the erroneous lemma, the proof of the
main theorem will have to assume that two major arcs do not intersect for it
to work, which is also not clear. However, we have developed some techniques
to go around this oversight by proving that two proper majors do not
intersect, which fortunately is enough to prove the most important part of the
main theorem that the asymptotic inequality still holds. In the third chapter,
we will introduce some improvements given by Huxley, Braton, and Tritonov to
the main theorem and discuss why they work. In the final chapter, we will
introduce two applications of the methods—the square-free number problems and
estimating solutions for diophantine inequalities. This essay aims to
introduce and understand this class of problems and methods in detail and
illustrate them in a way that best fits my understanding. Hopefully, in the
continuation of my studies, I will be able to use these interesting methods to
solve problems in related subjects. The main source of this essay comes from
the book Arithmetic Tales [1] by Olivier Bordellès, it contains a neatly
translated version of results coming from Huxley and Sargos and others in the
related topics. Beside changes in proves and statements cause by the oversight
we mentioned, most of other proofs are also modified to some degree.

##  2 The Theorem of Huxley and Sargos

One of the goals of this essay is to discuss a certain class of problems in
regards of estimating the number of integral points around a smooth curve. At
the start, we will take a look at some less generalized methods with strict
conditions, their appearances follow directly from the classical mean value
theorem and the divided differences. The problem is then complicated by the
appearance of major arcs which allows us to bound the integers in a different
way, the goal of the first chapter is to use tools and definitions we will
introduce to prove a finer version of the theorem comes from Huxley and Sargos
involving major arcs [11], which is considered to be a more generalized
method. In this chapter, we may assume that $N\geq 4$ is an integer and
$\delta$ and $c_{0}$ are small positive real numbers such that
$0<\delta<\frac{1}{4}$. We introduce the following notations

$\displaystyle\mathcal{S}(f,N,\delta)=\\{n\in[N,2N]\cap Z:\parallel
f(n)\parallel<\delta)\\}.$

$\parallel f(n)\parallel<\delta$ means the nearest integer point has distance
less than $\delta$ to $f(n)$ i.e. $(n,y)$ is the nearest integral point to
$(n,f(n))$ where $y$ is an integer such that $|f(n)-y|<\delta$. Also

$\displaystyle\mathcal{R}(f,N,\delta)=|\mathcal{S}(f,N,\delta)|.$

Notice the trivial bound $\mathcal{R}(f,N,\delta)\leq N+1$.

The theorem of Huxley and Sargos will be stated here as a motivation, the
proof of the theorem will come in at the end of this chapter when we are in a
position to do so. The theorem below is stated differently from the book
Arithmetic Tales [1, p. 373–374 Theorem 5.5] and the original paper by Huxley
and Sargos [11] and the reason why is discussed in the introduction.

######  Theorem 2.1 (Theorem of Huxley and Sargos).

Let $k\geq 3$ be an integer and $f\in C^{k}[N,2N]$ such that there exist
$\lambda_{k}>0$ and $c_{k}\geq 1$ such that, for all $x\in[N,2N]$, we have

$\displaystyle\lambda_{k}\leq|f^{(k)}(x)|\leq c_{k}\lambda_{k}.$ (1)

Let $0<\delta<\frac{1}{4}$ be a real number. Then

  * •

If the set of points in each proper major arc with denominator
$\leq(a_{k}\delta)^{-1}$ can be covered with interval of length
$L_{j}(a_{k}q_{j}\delta)^{-1/k}$ which is disjoint from all such covers for
other major arcs, where $L_{j}$ and $q_{j}$ are the length and denominator
associated with their proper major arcs:

$\displaystyle\mathcal{R}(f,N,\delta)\leq\alpha_{k}N\lambda_{k}^{\frac{2}{k(k+1)}}+\beta_{k}N\delta^{\frac{2}{k(k-1)}}+8k^{3}(\frac{\delta}{\lambda_{k}}\Big{)}^{\frac{1}{k}}+2k^{2}(5e^{3}+1);$

where

$\displaystyle\alpha_{k}=2k^{2}c_{k}^{\frac{2}{k(k+1)}}\quad\text{and}\quad\beta_{k}=4k^{2}(5e^{3}c_{k}^{\frac{2}{k(k-1)}}+1);$

  * •

otherwise:

$\displaystyle\mathcal{R}(f,N,\delta)\leq$
$\displaystyle\alpha_{k}N\lambda_{k}^{\frac{2}{k(k+1)}}+\beta_{k}N\delta^{\frac{2}{k(k-1)}}+16k^{3}(\frac{\delta}{\lambda_{k}}\Big{)}^{\frac{1}{k}}+2k^{2}(5e^{3}+1);$

where

$\displaystyle\alpha_{k}=2k^{2}c_{k}^{\frac{2}{k(k+1)}}\quad\text{and}\quad\beta_{k}=30e^{3}k^{2}c_{k}^{\frac{2}{k(k-1)}}+4k^{2};$

or alternatively we could write and use the above results as

$\displaystyle\mathcal{R}(f,N,\delta)\ll
N\lambda_{k}^{\frac{2}{k(k+1)}}+N\delta^{\frac{2}{k(k-1)}}+\big{(}\frac{\delta}{\lambda_{k}}\big{)}^{\frac{1}{k}}+1.$

Using Vinogradov notation, $f(x)\ll g(x)$ is equivalent to $f(x)=O(g(x)$, also
the implied constant above depends only on $k$ and $c_{k}$. We will have an in
depth look on how we can use this method, if there exists any weaker version
of it and could we improve it. At the end of this section, we will try and
prove Theorem 2.1.

###  2.1 Lagrange Interpolation Polynomial

First, we will introduce an interpolation method. That is, for a finite set of
data points, we will try to construct a function which must go exactly through
the values at these data points. The reason why this method will be useful is,
for the following sections, we will try to bound the number of certain integer
points around a smooth curve. To avoid a trivial bound we could always assume
there are more than $k$ such points. By taking multiple intervals which each
contain $k$ points, we could reduce the question to bounding the length of the
interval by using the classical mean value theorem or a generalization of the
mean value theorem which involves using Lagrange polynomials. This would be a
common trick to give a bound through out the essay.
Here is a simple construction of such a polynomial. Let’s say it interpolates
at the points $x_{0},x_{1},x_{2},x_{3},\dots,x_{k}$ of some function $f$.
Consider a sequence of functions such that each function equals 0 at all the
points except at one point it equals $f(x_{i})$. By adding these functions
together, we get a polynomial passing through exactly these $k+1$ points.
Following some straightforward computations we get

$\displaystyle f_{i}(x)=\begin{cases}1,&x=x_{i}\\\ 0,&x=x_{j},i\neq
j\end{cases}$ $\displaystyle\Rightarrow f_{i}(x)=\prod_{j=0,i\neq
j}^{k}\frac{x-x_{j}}{x_{i}-x_{j}}f(x_{i})$
$\displaystyle\Rightarrow\mathcal{P}(x)=\sum_{i=0}^{k}\Big{(}\prod_{j=0,i\neq
j}^{k}\frac{x-x_{j}}{x_{i}-x_{j}}f(x_{i})\Big{)}.$ (2)

The leading coefficient of $\mathcal{P}(x)$, $b_{k}$, is called the divided
difference of $f$ at the points $x_{0},x_{1},x_{2},x_{3},\dots,x_{k}$ and it
is denoted by $f[x_{0},x_{1},\dots,x_{k}]$. With some brute force calculation,
we can show that

$\displaystyle b_{k}=\sum_{j=0}^{k}\frac{f(x_{j})}{\prod_{0\leq i\leq k,i\neq
j}(x_{j}-x_{i})}=\frac{A}{\prod_{0\leq i<j\leq k}(x_{j}-x_{i})},$ (3)

with

$\displaystyle A=\begin{vmatrix}1&1&\cdots&1\\\ x_{0}&x_{1}&\cdots&x_{k}\\\
\vdots&\vdots&\ddots&\vdots\\\ x_{0}^{k-1}&x_{1}^{k-1}&\cdots&x_{k}^{k-1}\\\
f(x_{0})&f(x_{1})&\cdots&f(x_{k})\end{vmatrix}\begin{matrix}\vphantom{x}\\\
\vphantom{y}\\\ \vphantom{z}\\\ \vphantom{s}\\\ \vphantom{f}.\end{matrix}$ (4)

It might seem like the degree of the Lagrange interpolating polynomial is
directly related to the number of data points it is fitting, specifically, if
you have $n$ data points, the Lagrange interpolating polynomial should be of
degree $n-1$. But this is simply not the case, we will give a somewhat trivial
example here which both showcase the power of this new tool and to prove the
point we are making here. Let $f(x)=x$ and let the points we will try to
interpolate be $x_{i}=i$ for $i\in\\{1,2,3,4\\}$. Following the way we
construct the polynomial (2), we get

$\displaystyle\frac{(x-2)(x-3)(x-4)}{-6}+\frac{(x-1)(x-3)(x-4)}{-2}2+\frac{(x-1)(x-2)(x-4)}{-2}3$
$\displaystyle+\frac{(x-1)(x-2)(x-3)}{6}4=x.$

To amend our statement, we could say if you have $n$ data points, the Lagrange
interpolating polynomial should be of degree $\leq n-1$. The next thing we
will do is to justify that Lagrange interpolation polynomial is well defined
by proving its existence and uniqueness [13, p. 271–287].

######  Definition 2.2.

$\mathbb{P}_{n}[x]$ is a set of all polynomials of degree $n$ and smaller.

######  Theorem 2.3 (Existence and uniqueness).

Given $n+1$ distinct points $(x_{i})_{i=0}^{n}\in[a,b]$ and $n+1$ real numbers
$(f_{i})_{i=0}^{n}$, there is exactly one polynomial $p\in\mathbb{P}_{n}[x]$,
namely that given by (2), such that $p(x_{i})=f_{i}$ for all $i$.

###### Proof.

First we define the Lagrange cardinal polynomials for the points
$x_{0},x_{1},\dots,x_{n}$ as follows

$\displaystyle l_{k}(x)=\prod_{i=0,i\neq
k}^{n}\frac{x-x_{i}}{x_{k}-x_{i}},\quad k=0,1,\dots,n.$

Each $l_{k}$ is the product of $n$ linear factors, hence
$l_{k}\in\mathbb{P}_{n}[x]$, and from (2), $p\in\mathbb{P}_{n}[x]$. We have
shown by construction before such $l_{k}(x_{k})=1$ and $l_{k}(x_{j})=0$ for
$j\neq k$. Hence

$\displaystyle p(x_{j})=\sum_{k=0}^{n}f_{k}l_{k}(x_{j})=f_{j},\quad
j=0,\dots,n,$

thus $p$ is a polynomial interpolate at our given data points. For the
uniqueness part, let’s suppose both $p\in\mathbb{P}_{n}[x]$ and
$q\in\mathbb{P}_{n}[x]$ interpolate same $n+1$ data points. The polynomial
$r=p-q$ is of degree at most n and equals to 0 at $n+1$ distinct points. Such
a polynomial can only be the zero polynomial, therefore $r\equiv 0$ and thus
the interpolating polynomial is unique. ∎

Notice that the result for uniqueness is only in one direction, for $n+1$
distinct points, you will get an unique Lagrange polynomial associated to it.
But for a given Lagrange polynomial, it could interpolate a different set of
points at the same time. The example we discussed before is a good
illustration of this.
The Lagrange interpolation polynomials are often the appropriate forms to use
when we wish to manipulate the interpolation polynomial as part of a larger
mathematical expression. However, they are not ideal for numerical evaluation,
both because of the speed of calculation and because of the accumulation of
rounding error. But it is good enough to give us a practical bound in the
following theorems.

###  2.2 The First, Second and $k$th Derivative Test

The initial aim of theorem 2.1 was to improve a restriction on the $k$th
derivative test, which we will state more clearly later. The $k$th derivative
test was intended to generalize the first and the second derivative test. We
will go through them briefly. First we will state and prove the first
derivative test as follows [1, p. 364–366 Theorem 5.3].

######  Definition 2.4.

$[x]$ is the nearest integer below $x$ such that $x-1<[x]\leq x$.

######  Theorem 2.5 (First derivative test).

Let $f\in C^{1}[N,2N]$ such that there exists $\lambda_{1}>0$ and $c_{1}\geq
1$ such that for all $x\in[N,2N]$, we have

$\displaystyle\lambda_{1}\leq|f^{\prime}(x)|\leq c_{1}\lambda_{1},$ (5)

then

$\displaystyle\mathcal{R}(f,N,\delta)\leq
2c_{1}N\lambda_{1}+4c_{1}N\delta+\frac{2\delta}{\lambda_{1}}+1.$

In practice, using Titchmarsh-Vinogradov notation, the result can be stated as
follows. If

$\displaystyle|f^{\prime}(x)|\asymp\lambda_{1},$

then we have

$\displaystyle\mathcal{R}(f,N,\delta)\ll
N\lambda_{1}+N\delta+\frac{\delta}{\lambda}+1.$

$f\asymp g$ is equivalent to $f\ll g$ and $g\ll f$.

The result above follows naturally from the classical mean-value theorem. It’s
rather restrictive and becomes useless when $\lambda_{1}$ is big, but it is a
starting point of more elaborate estimates.

Also the statement itself could be a bit more general, since the proof only
invokes the property of $f$ being continuous and differentiable, the
derivative $f^{\prime}$ is not necessarily needed to be continuous.

###### Proof.

First we would like to get rid of some trivial cases. If $4c_{1}\delta\geq 1$,
then $4c_{1}\delta+1\geq N+1\geq\mathcal{R}(f,N,\delta)$, similar thing can be
said for $2c_{1}\lambda_{1}\geq 1$. So we may as well suppose that
max$(4c_{1}\delta,2c_{1}\lambda_{1})<1$. We can also assume that there is more
than one point in the set otherwise the inequality is trivial. Let $n$ and
$n+a$ be any integers in $\mathcal{S}(f,N,\delta)$ (not necessarily
consecutive), using the mean value theorem we could show that either

$\displaystyle a>\frac{1}{2c_{1}\lambda_{1}}=a_{1};$ (6)

or

$\displaystyle a<\frac{2\delta}{\lambda_{1}}=a_{2};$ (7)

we assume the above is true for now and continue, will come back to that
later. Also notice that max($4c_{1}\delta$,$2c_{1}\lambda_{1}$)$<1$ implies

$\displaystyle
a_{1}=\frac{1}{2c_{1}\lambda_{1}}>max(\frac{2\delta}{\lambda_{1}},1)=max(a_{2},1).$

More specifically, $a_{1}>1$, therefore we can sub-divide the interval
$[N,2N]$ into $s=[\frac{N}{a_{1}}]+1$ sub-intervals
$\mathcal{I}_{1},\dots,\mathcal{I}_{s}$ where each interval has length $\leq
a_{1}$. Which means if there is more than one element from
$\mathcal{S}(f,N,\delta)$ inside the interval $\mathcal{I}_{j}$, we would have
a distance between any of the two elements $\leq a_{1}$ (not necessarily $2$
consecutive elements) and by (6) and (7), we have their distance $\leq a_{2}$.
For any two elements inside the interval, choose the pair with the largest
distance, we would still have the previous result. Let $n$ and $n+a$ be such a
pair with $a\leq a_{2}$. Then if there are more elements lie in the interval,
they must lie in between $n$ and $n+a$. Thus, we could infer the following to
be true,

$\displaystyle|\mathcal{S}(f,N,\delta)\cap\mathcal{I}_{j}|\leq a_{2}+1,$

which still holds if there is only one element inside the interval. From here
we could easily deduce the result.

$\displaystyle\mathcal{R}(f,N,\delta)\leq\Big{(}\frac{N}{a_{1}}+1\Big{)}(a_{2}+1)=2c_{1}N\lambda_{1}+4c_{1}N\delta+\frac{2\delta}{\lambda_{1}}+1.$

Now we will try to end the argument by deducing (7) and (6) to be true by
using the mean value theorem. For any two elements $n$ and $n+a$ in
$\mathcal{S}(f,N,\delta)$, there exist $m_{1}$ and $m_{2}$ integers and
$\delta_{1}$ and $\delta_{2}$ real numbers such that $f(n)=m_{1}+\delta_{1}$
and $f(n+a)=m_{2}+\delta_{2}$ with $|\delta_{i}|<\delta$ for $i\in\\{1,2\\}$.
Which means there exists $m\in\mathbb{Z}$ and $\delta_{3}\in\mathbb{R}$ such
that $|\delta_{3}|<2\delta$ and

$\displaystyle f(n+a)-f(n)=m+\delta_{3}.$

Using the mean value theorem on $f$, we get for $t\in[N,2N]$ the following

$\displaystyle f(n+a)-f(n)=af^{\prime}(t)\quad\text{and}\quad
af^{\prime}(t)=m+\delta_{3}.$

If $m\neq 0$, since $m\in\mathbb{Z}$, we have $|m|\geq 1$. From (5) we could
deduce

$\displaystyle ac_{1}\lambda_{1}\geq
a|f^{\prime}(t)|=|m+\delta_{3}|\geq|m|-|\delta_{3}|>1-\frac{1}{2}=\frac{1}{2},$

which gives us (6). If $m=0$, by (5) we have

$\displaystyle a\lambda_{1}\leq a|f^{\prime}(t)|=|\delta_{3}|<2\delta,$

which gives (7). ∎

For the next result, we will assume $0<\delta<\frac{1}{8}$. First we will
introduce the following lemma. [1, p. 383–385 Lemma 5.7]

######  Lemma 2.6 (Reduction principle).

Let $f:[N,2N]\longrightarrow\mathbb{R}$ be any map, $A$ be a real number
satisfying $1\leq A\leq N$ and, for all integers $a\in[1,A]$, we define on
$[N,2N-a]$ the function $\Delta_{a}f$ by

$\displaystyle\Delta_{a}f(x)=f(x+a)-f(x).$

Then

$\displaystyle\mathcal{R}(f,N,\delta)\leq\frac{N}{A}+\sum_{a\leq
A}\mathcal{R}(\Delta_{a}f,N,2\delta)+1.$

###### Proof.

For all $a\in\mathbb{N}$, define

$\displaystyle S(a)=\\{n\in[N,2N]\cap\mathbb{Z}:n\text{ and }n+a\text{ are
consecutive in }\mathcal{S}(f,N,\delta)\\}.$

As before, assume more than one point in the set $\mathcal{S}(f,N,\delta)$,
otherwise the statement is trivial. We observe that for any integer inside
$\mathcal{S}(f,N,\delta)$, except the largest one, has a successive element
and lies in only one subset $\mathcal{S}(a)$, so we could easily deduce the
following,

$\displaystyle\mathcal{R}(f,N,\delta)=\sum_{a=1}^{\infty}|\mathcal{S}|+1=\sum_{a\leq
A}|\mathcal{S}(a)|+\sum_{a>A}|\mathcal{S}(a)|+1.$ (8)

We write the set as $\mathcal{S}(f,N,\delta)=\\{n_{1}\leq n_{2}\leq\cdots\leq
n_{k}\\}$ and define $d_{j}$ for $j\in\\{1,\dots,k-1\\}$ as

$\displaystyle d_{1}=n_{2}-n_{1}\text{,
}d_{2}=n_{3}-n_{2}\text{,\ldots,}d_{k-1}=n_{k}-n_{k-1}.$

By definition we have $|\mathcal{S}(a)|$ counts the number of elements with
distance a, that is the number of indexes $j\in\\{1,\dots,k-1\\}$ such that
$d_{j}=a$, so clearly

$\displaystyle\sum_{a=1}^{\infty}a|\mathcal{S}(a)|=\sum_{j=1}^{k-1}d_{j}=\sum_{j=1}^{k-1}(n_{j+1}-n_{j})=n_{k}-n_{1}\leq
N.$

Therefore we can trivially bound the second term of (8) by the following,

$\displaystyle
N\geq\sum_{a=1}^{\infty}a|\mathcal{S}(a)|\geq\sum_{a>A}a|\mathcal{S}(a)|\geq
A\sum_{a>A}|\mathcal{S}(a)|\Rightarrow\sum_{a>A}|\mathcal{S}(a)|\leq\frac{N}{A}.$

Let $n\in\mathcal{S}(a)$, which means $n$ and $n+a$ are consecutive in
$\mathcal{S}(f,N,\delta)$, so that

$\displaystyle||\Delta_{a}f(n)||=||f(n+a)-f(n)||\leq||f(n+a)||+||f(n)||<2\delta.$

To justify the first inequality above to be true, simply take
$||(f(n+a)\text{ mod }1)-(f(n)\text{ mod }1)||$, it gives the same value as
$||f(n+a)-f(n)||$. So we have $n\in\mathcal{S}(\Delta_{a}f,N,2\delta)$, that
is

$\displaystyle|\mathcal{S}(a)|\leq\mathcal{R}(\Delta_{a}f,N,2\delta),$

which gives a bound for first term of (8) and the result. ∎

For the second derivative test, the idea is to use the mean value theorem to
get $|(\Delta_{a}f)^{\prime}(x)|\asymp a\lambda_{2}$, use the first derivative
test on $\Delta_{a}f$ and use the previous lemma to get back to $f$. This
gives the following theorem [1, p. 385–386 Theorem 5.4].

######  Theorem 2.7 (Second derivative test).

Let $f\in C^{2}[N,2N]$ such that there exist $\lambda_{2}>0$ and $c_{2}\geq 1$
such that, for all $x\in[N,2N]$, we have

$\displaystyle\lambda_{2}\leq|f^{\prime\prime}(x)|\leq c_{2}\lambda_{2},$ (9)

and

$\displaystyle N\lambda_{2}\geq c_{2}^{-1}.$ (10)

Then

$\displaystyle\mathcal{R}(f,N,\delta)\leq
6\\{(3c_{2})^{\frac{1}{3}}N\lambda_{2}^{\frac{1}{3}}+(12c_{2})^{\frac{1}{2}}N\delta^{\frac{1}{2}}+1\\},$
(11)

or to put it in a more practical way, if

$\displaystyle|f^{\prime\prime}(x)|\asymp\lambda_{2}\text{ and
}N\lambda_{2}\gg 1,$

then

$\displaystyle\mathcal{R}(f,N,\delta)\ll
N\lambda_{2}^{\frac{1}{3}}+N\delta^{\frac{1}{2}}+1.$

###### Proof.

As per usual, we first get rid of the trivial cases. If
$\lambda_{2}\geq(3c_{2})^{-1}$ or $\delta\geq(12c_{2})^{-1}$, then it would
result in the right hand side of the inequality (10) being $\geq N+1$, which
means the statement would be trivially true. So we could assume that

$\displaystyle 0<\lambda_{2}<(3c_{2})^{-1}\text{ and
}0<\delta<(12c_{2})^{-1}.$ (12)

Let $A\in\mathbb{R}$ such that $1\leq A\leq N$. For all $x\in[N,2N]$ and all
$a\in[1,A]\cap\mathbb{Z}$ such that $x+a\in[N,2N]$, applying the mean value
theorem on them, that

$\displaystyle(\Delta_{a}f)^{\prime}(x)=f^{\prime}(x+a)-f^{\prime}(x)=af^{\prime\prime}(t)$

for some $t\in[x,x+a]\subseteq[N,2N]$, with the condition from (9), we would
have for all $x\in[N,2N]$ and all $a\in[1,A]\cap\mathbb{Z}$ such that
$x+a\in[N,2N]$, we could easily find

$\displaystyle a\lambda_{2}\leq|(\Delta_{a}f)^{\prime}(x)|\leq
c_{2}a\lambda_{2}.$

By the first derivative test we get

$\displaystyle\mathcal{R}(\Delta_{a}f,N,2\delta)\leq
2c_{2}Na\lambda_{2}+8c_{2}N\delta+\frac{4\delta}{a\lambda_{2}}+1.$ (13)

Even though $\Delta_{a}f$ might not be defined on some points in $[N,2N]$, the
inequality still holds because the range where $\Delta_{a}f$ is defined is
contained in $[N,2N]$. We could simply extend the undefined part to be any
smooth function. As we are discussing an upper bound in (12), it still works,
since by the nature of the argument, we only care about counting the integer
points on the defined interval. Now we combine the above with Lemma 2.6. We
get the following,

$\displaystyle\mathcal{R}(f,N,\delta)\leq\frac{N}{A}+\sum_{a\leq
A}\Big{(}2c_{2}Na\lambda_{2}+8c_{2}N\delta+\frac{4\delta}{a\lambda_{2}}+1\Big{)}+1.$
(14)

By condition (10) and the fact that $a$ is a positive integer, we get

$\displaystyle 4c_{2}N\delta\geq 4\delta\lambda_{2}^{-1}\geq
4\delta(a\lambda_{2})^{-1}\text{ and }1\leq c_{2}Na\lambda_{2}.$

Replace terms on the right side of the inequality (14) using the above two
inequalities, we get

$\displaystyle\mathcal{R}(f,N,\delta)$
$\displaystyle\leq\frac{N}{A}+\sum_{a\leq
A}\Big{(}3c_{2}Na\lambda_{2}+12c_{2}N\delta\Big{)}+1$
$\displaystyle\leq\frac{N}{A}+3c_{2}NA^{2}\lambda_{2}+12c_{2}NA\delta+1.$ (15)

To improve our bound even further, we need to try to optimize the choice of
$A$ and see if there exists $A\in[1,N]$ such that the right hand side of the
above inequality could be as small as it can. The following lemma [19] does
exactly the thing we want, optimizing the choice of $H$ in a certain interval.
An explicit statement of the lemma can also be found in [1, p. 363 Lemma 5.6].

######  Lemma 2.8 (Srinivasan).

Let

$\displaystyle E(H)=\sum_{i=1}^{m}A_{i}H^{a_{i}}+\sum_{j=1}^{n}B_{j}H^{-bj},$

where m,n $\in$ $\mathbb{N}$ and $A_{i}$, $B_{j}$, $a_{i}$ and $b_{j}$ are
positive real numbers. Suppose that $0\leq H_{1}\leq H_{2}$. Then

$\displaystyle\min_{H_{1}\leq H\leq
H_{2}}E(H)\leq(m+n)\Big{\\{}\sum_{i=1}^{m}\sum_{j=1}^{n}(A_{i}^{b_{j}}B_{j}^{a_{i}})^{\frac{1}{a_{i}+b_{j}}}+\sum_{i=1}^{m}A_{i}H_{1}^{a_{i}}+\sum_{j=1}^{n}B_{j}H_{2}^{-b_{j}}\Big{\\}}.$

Now we let
$n=1,m=2,b_{1}=1,a_{1}=1,a_{2}=2,B_{1}=N,A_{1}=12c_{2}N\delta,A_{2}=3c_{2}N\lambda_{2},H=A$

$\displaystyle\min_{1\leq A\leq N}\Big{(}$ $\displaystyle
NA^{-1}+3c_{2}N\lambda_{2}A^{2}+12c_{2}NA\delta\Big{)}$ $\displaystyle\leq
3\Big{\\{}(A_{1}N^{a_{1}})^{\frac{1}{a_{1}+1}}+(A_{2}N^{a_{2}})^{\frac{1}{a_{2}+1}}+A_{1}H_{1}^{a_{1}}+A_{2}H_{1}^{a_{2}}+B_{1}H_{2}^{-b_{1}}\Big{\\}}$
$\displaystyle=3N\Big{\\{}(3c_{2}\lambda_{2})^{\frac{1}{3}}+3c_{2}\lambda_{2}+(12c_{2}\delta)^{\frac{1}{2}}+12c_{2}\delta\Big{\\}}+3.$
(16)

Now (12) implies that

$\displaystyle 0<3c_{2}\lambda_{2}<1\text{ and }0<12c_{2}\delta<1,$

which means $(3c_{2}\lambda_{2})^{\frac{1}{3}}>3c_{2}\lambda_{2}$ and
$(12c_{2}\delta)^{\frac{1}{2}}>12c_{2}\delta$, with all that said, bound in
(15) can be optimized as the following,

$\displaystyle\mathcal{R}(f,N,\delta)$ $\displaystyle\leq
3N\Big{\\{}(3c_{2}\lambda_{2})^{\frac{1}{3}}+3c_{2}\lambda_{2}+(12c_{2}\delta)^{\frac{1}{2}}+12c_{2}\delta\Big{\\}}+4$
$\displaystyle\leq
6\Big{\\{}(3c_{2}\lambda_{2})^{\frac{1}{3}}N+(12c_{2}\delta)^{\frac{1}{2}}N+1\Big{\\}},$

which is the result. ∎

The natural question to ask now is if the previous two results could be
generalized in some way. In order to do so, we should first consider a more
generalized version of the mean value theorem which put higher derivatives
into play. It is stated as follows [1, p.380–381 Theorem 5.2].

######  Theorem 2.9 (Divided differences).

Let $k$ be a positive integer, $x_{0}<x_{1}<\cdots<x_{k}$ be real numbers and
$f\in C^{k}[x_{0},x_{k}]$. Set $\mathcal{P}(x)=b_{k}x^{k}+\cdots+b_{0}$ the
unique polynomial of degree $\leq k$ such that $\mathcal{P}(x_{i})=f(x_{i})$
for $i=0,\dots,k$. Then there exists a real number $t\in[x_{0},x_{k}]$ such
that

$\displaystyle b_{k}=\frac{f^{(k)}(t)}{k!}.$

The proof of the theorem is rather straightforward. By letting
$F(x)=f(x)-\mathcal{P}(x)$, we can use induction to prove that for any
$F(x)\in C^{k}[x_{0},x_{k}]$ such that $F(x_{0})=F(x_{1})=\cdots=F(x_{k})$.
Then there exists a real number $t\in[x_{0},x_{k}]$ such that $F^{(k)}(t)=0$.
Notice that $\mathcal{P}^{(k)}(x)=k!b_{k}$.
The polynomial $\mathcal{P}$ mentioned above is a Lagrange polynomial. We can
see from (4) that $A\in\mathbb{Z}$ if $x_{j}\in\mathbb{Z}$ and
$f(x_{j})\in\mathbb{Z}$. When $k=1$, by (3), we can find
$b_{k}=\frac{f(x_{1})-f(x_{0})}{x_{1}-x_{0}}$, which shows that Theorem 2.9
generalizes the mean value theorem. With that in mind, now we can go back to
the generalization of the first and second derivative tests. The $k$th
derivative test [1, p. 387–372 Proposition 5.1] is stated as follows

######  Theorem 2.10 ($k$th derivative test).

Let $k\geq 1$ be an integer and $f\in C^{k}[N,2N]$ such that there exist
$\lambda_{k}>0$ and $c_{k}\geq 1$ such that, for all $x\in[N,2N]$, we have

$\displaystyle\lambda_{k}\leq|f^{(k)}(x)|\leq c_{k}\lambda_{k}.$ (17)

Assume also that

$\displaystyle(k+1)!\delta<\lambda_{k}.$ (18)

If $\alpha_{k}=2k(2c_{k})^{\frac{2}{k(k+1)}}$, then

$\displaystyle\mathcal{R}(f,N,\delta)\leq\alpha_{k}N\lambda_{k}^{\frac{2}{k(k+1)}}+4k.$

To state the theorem in a more practical sense, we can say if

$\displaystyle|f^{(k)}(x)|\asymp\lambda_{k}\text{ and }\delta\ll\lambda_{k},$

then

$\displaystyle\mathcal{R}(f,N,\delta)\ll N\lambda_{k}^{\frac{2}{k(k+1)}}+1.$

###### Proof.

As usual, we first get rid of the trivial case, if
$\lambda_{k}\geq\frac{1}{2}$, then

$\displaystyle\alpha_{k}N\lambda_{k}^{\frac{2}{k(k+1)}}+1\geq
N+1\geq\mathcal{R}(f,N,\delta).$

Since $k\geq 1$ and $c_{k}\geq 1$. So we can assume that
$\lambda_{k}<\frac{1}{2}$ and that the size of $\mathcal{S}(f,N,\delta)$ is
more than $4k$. The way we try to generalize the first derivative test here is
by taking $k+1$ consecutive points $n<n+a_{1}<n+a_{2}<\cdots<n+a_{k}$ in
$\mathcal{S}(f,N,\delta)$ and say the distance between the first and the last
elements $a_{k}$ satisfies

$\displaystyle a_{k}\geq 2k\alpha_{k}^{-1}\lambda_{k}^{-\frac{2}{k(k+1)}}.$
(19)

As we did in the proof of the first derivative test, we will assume (19) to be
true for now and will come back and prove it later. Let’s write the set in the
form $\mathcal{S}(f,N,\delta)=\\{n<n+a_{1}<\cdots<n+a_{k}<\cdots<n+a_{z}\\}$
where $z>4k$. Let $T$ be a subset of $\mathcal{S}(f,N,\delta)$ such that it
contains each $(k+1)$th elements of $\mathcal{S}(f,N,\delta)$, that is

$\displaystyle
T=\\{n+a_{mk+(m-1)}\in\mathcal{S}(f,N,\delta):m\in\mathbb{N}\setminus\\{0\\}\text{
and }mk+(m-1)\leq z\\}.$

We can see by (19), for any two elements in the set $T$, they differ by more
than $d_{k}=2k\alpha_{k}^{-1}\lambda_{k}^{-\frac{2}{k(k+1)}}$ and $k\geq 1$,
therefore we can deduce the following, which is essentially the result

$\displaystyle\mathcal{R}(f,N,\delta)\leq(k+1)(|T|+1)\leq
2k\Big{(}\frac{N}{d_{k}}+2\Big{)}.$

Now our job is to show that the inequality (19) is indeed true and then we are
done. We may abuse the notations a little bit and let
$n,n+a_{1},\dots,n+a_{k}$ be any $k+1$ consecutive elements in
$S(f,N,\delta)$. By definition, there exist integers $m_{0},\dots,m_{k}$ and
real numbers $\delta_{0},\dots,\delta_{k}$ such that $|\delta_{j}|<\delta$ for
all $j\in\\{0,\dots,k\\}$ and $f(n+a_{j})=m_{j}+\delta_{j}$ where $a_{0}=0$.
Using Theorem 2.9 and (3), let $\mathcal{P}(x)=b_{k}x^{k}+\cdots+b_{0}$ be the
Lagrange polynomial interpolating the points $(n+a_{j},m_{j}+\delta_{j})$. We
know there exist $t\in[n,n+a_{k}]$ such that

$\displaystyle b_{k}=\sum_{j=0}^{k}\frac{m_{j}+\delta_{j}}{\prod_{0\leq i\leq
k,i\neq j}(a_{j}-a_{i})}=\frac{f^{(k)}(t)}{k!};$ (20)

let $P=b^{\prime}_{k}X^{k}+\cdots+b^{\prime}_{0}$ be the polynomial
interpolating the points $(n+a_{j},m_{j})$, then we also have

$\displaystyle b^{\prime}_{k}=\sum_{j=0}^{k}\frac{m_{j}}{\prod_{0\leq i\leq
k,i\neq j}(a_{j}-a_{i})}=\frac{A_{k}}{D_{k}};$

where we can see $A_{k}\in\mathbb{Z}$ and $D_{k}=\prod_{0\leq i<j\leq
k}(a_{j}-a_{i})>0$, and we can get

$\displaystyle
b^{\prime}_{k}=b_{k}-\sum_{j=0}^{k}\frac{\delta_{j}}{\prod_{0\leq i\leq
k,i\neq j}(a_{j}-a_{i})};$

and then

$\displaystyle
k!A_{k}=k!D_{k}b^{\prime}_{k}=D_{k}f^{(k)}(t)-k!D_{k}\sum_{j=0}^{k}\frac{\delta_{j}}{\prod_{0\leq
i\leq k,i\neq j}(a_{j}-a_{i})}=x+y.$

Since $|\delta_{j}|<\delta$ and $|a_{j}-a_{i}|\geq 1$ for all $i\neq j$, we
have

$\displaystyle|y|<k!D_{k}\delta\sum_{j=0}^{k}\frac{1}{\prod_{0\leq i\leq
k,i\neq j}|a_{j}-a_{i}|}\leq(k+1)!D_{k}\delta.$

Now from (17), (18) and (20), the above becomes

$\displaystyle|y|<\lambda_{k}D_{k}\leq D_{k}|f^{(k)}(t)|=|x|.$

It is easy to see that $|x|>\frac{1}{2}$ since $x+y=k!A_{k}$ is an integer,
because $|x|>|y|$ which means $x+y\neq 0$ and $1\leq|x+y|\leq|x|+|y|<2|x|$.
Also we can see $a_{0}<a_{1}<\cdots<a_{k}$, so

$\displaystyle D_{k}=\prod_{0\leq i<j\leq k}(a_{j}-a_{i})\leq\prod_{0\leq
i<j\leq k}a_{j}\leq\prod_{0\leq i<j\leq k}a_{k}\leq a_{k}^{\frac{k(k+1)}{2}}.$

With (17), we get

$\displaystyle\frac{1}{2}<D_{k}|f^{(k)}(x)|\leq
a_{k}^{\frac{k(k+1)}{2}}c_{k}\lambda_{k}=\frac{\lambda_{k}}{2}((2k)^{-1}a_{k}\alpha_{k})^{\frac{k(k+1)}{2}}$

which implies (19), and concludes the proof. ∎

The $k$th derivative test stated above does generalize the first derivative
test, but we can see that many bounds we used in the proof could potentially
be improved, such as $|a_{j}-a_{i}|$ could be a larger number than $1$ in many
special cases, which would enable us to give a better upper bound for $|y|$,
that means the condition (18) could be less restrictive. Naturally, the quest
to establish a $k$th derivative test without the condition (18) arises. This
leads us to the result given by Huxley and Sargos which we have stated in
Theorem 2.1. To prove it is rather difficult, we would need several tools
first and then we will be in a the position to do so.

###  2.3 Preparatory Lemmas and Major Arcs

The aim of this section is to discuss the techniques and tools that we will be
using in the proof of Theorem 2.1, so we may assume some of the conditions,
such as $k\geq 3$, which are stated in the Theorem. The first tool we will
introduce is an easy enumeration principle [1, p. 374–375 Lemma 5.9].

######  Lemma 2.11.

Let $S$ be a finite set of integers, $S=\\{a_{1}<a_{2}\cdots<a_{n}\\}$ such
that $|a_{n}-a_{1}|\leq N$. If one can cover $S$ by pairwise distinct
intervals $\mathcal{I}$ and if $L(\mathcal{I})$ is the length of
$\mathcal{I}$, then

$\displaystyle|S|\leq
N\max_{\mathcal{I}}\Big{(}\frac{|S\cap\mathcal{I}|}{L(\mathcal{I})}\Big{)}+2\max_{\mathcal{I}}|S\cap\mathcal{I}|.$

###### Proof.

Let $\mathcal{I}_{1},\dots,\mathcal{I}_{J}$ be such a covering of $S$,
pairwise distinct here simply means if $h\neq j$, then
$\mathcal{I}_{h}\cap\mathcal{I}_{j}=\emptyset$ and if $2\leq j\leq J-1$, then
$\mathcal{I}_{j}\subseteq[a_{1},a_{n}]$, and what follows next is very easy to
see,

$\displaystyle|S|\leq\sum_{j=1}^{J}|S\cap\mathcal{I}_{j}|$
$\displaystyle=\sum_{j=2}^{J-1}\Big{\\{}L(\mathcal{I}_{j})\frac{|S\cap\mathcal{I}_{j}|}{L(\mathcal{I}_{j})}\Big{\\}}+|S\cap\mathcal{I}_{1}|+|S\cap\mathcal{I}_{J}|$
$\displaystyle\leq\max_{1\leq j\leq
J}\Big{(}\frac{|S\cap\mathcal{I}_{j}|}{L(\mathcal{I}_{j})}\Big{)}\sum_{j=2}^{J-1}L(\mathcal{I}_{j})+2\max_{1\leq
j\leq J}|S\cap\mathcal{I}_{j}|$ $\displaystyle\leq N\max_{1\leq j\leq
J}\Big{(}\frac{|S\cap\mathcal{I}_{j}|}{L(\mathcal{I}_{j})}\Big{)}+2\max_{1\leq
j\leq J}|S\cap\mathcal{I}_{j}|.$

∎

The next tool we will introduce is a certain class of inequalities which exist
to bound a derivatives of some function if we know the bound of its highest
order of derivative and they were the lowest. They are called the Landau-
Hadamard-Kolmogorov inequalities. It was first developed by E. Landau [21] in
1913 with rather restricted conditions, explicit statements of the following
three theorems can also be found in [1, p. 374].

######  Theorem 2.12 (E. Landau).

If $I$ is an interval with length $\geq 2$ and $f\in C^{2}(I)$ satisfies the
conditions $|f(x)|\leq 1$ and $|f^{\prime\prime}(x)|\leq 1$ on $I$, then
$|f^{\prime}(x)|\leq 2$ and the constant 2 is the best possible.

This was generalized by Hadamard [22], without the explicit restrictions on
the bound of $|f|$ and $|f^{\prime\prime}|$ .

######  Theorem 2.13 (Hadamard).

If $f\in C^{2}([a,a+L])$ and $a\in\mathbb{R}$, $L>0$, then

$\displaystyle\sup_{a\leq x\leq a+L}|f^{\prime}(x)|\leq\frac{2}{L}\sup_{a\leq
x\leq a+L}|f(x)|+\frac{L}{2}\sup_{a\leq x\leq a+L}|f^{\prime\prime}(x)|.$

As with the development of the derivative tests we have introduced, the next
natural step was to generalize it for higher order of derivatives [23].

######  Theorem 2.14 (L. Neder).

If $a\in\mathbb{R}$, $L>0$ and $f\in C^{k}[a,a+L]$, then, for all
$j\in\\{1,\dots,k-1\\}$, we have

$\displaystyle\sup_{a\leq x\leq
a+L}|f^{(j)}(x)|\leq\frac{(2k)^{2k}}{L^{j}}\sup_{a\leq x\leq
a+L}|f(x)|+L^{k-j}\sup_{a\leq x\leq a+L}|f^{(k)}(x)|.$ (21)

Theorem 2.14 stated above is sufficient enough for us to use in the proof of
Theorem 2.1. But what we will use is the following improved version due to
Gorny [5], the original source should also be in Bordellès [1, Lemma 5.10].

######  Lemma 2.15 (Gorny).

Let $k\geq 2$ be an integer, $a\in\mathbb{R}$, $L>0$ and $f\in C^{k}[a,a+L]$
such that, for all $x\in[a,a+L]$, we have

$\displaystyle|f(x)|\leq M_{0}\quad\text{and}\quad|f^{(k)}(x)|\leq M_{k}$

with $M_{0}<\infty$ and $M_{k}<\infty$. Then, for all $x\in[a,a+L]$ and
$j\in\\{1,\dots,k-1\\}$, we have

$\displaystyle|f^{(j)}(x)|<4(e^{2}k/j)^{j}M_{0}^{1-j/k}\big{\\{}max\big{(}M_{k},k!M_{0}L^{-k}\big{)}\big{\\}}^{j/k}.$

In practice, we will use this result in the following form

$\displaystyle|f^{(j)}(x)|<4e(ek/j)^{j}\big{\\{}k^{j+1}M_{0}L^{-j}+e^{j-1}M_{0}^{1-j/k}M_{k}^{j/k}\big{\\}}.$
(22)

The next technique [1, Lemma 5.11] will be used to calculate the implied
constant appeared in Theorem 2.1.

######  Lemma 2.16.

Let $k\geq 3$ be an integer and $a>e(k-1)$ be a real number. Then

$\displaystyle\sum_{j=1}^{k-1}\Big{(}\frac{a}{j}\Big{)}^{2j}\leq
e^{2}k\Big{(}\frac{a}{k}\Big{)}^{2k-2}.$

###### Proof.

By some brute force calculation, we can find that the derivative of
$\Big{(}\frac{e(k-1)}{x}\Big{)}^{2x}$ equals $0$ only when $x=k+1$, and it is
a local maximum. Since $a>e(k-1)$, we now can say that the function
$x\mapsto(a/x)^{2x}$ is increasing as soon as $1\leq x\leq k-1$ and so

$\displaystyle\sum_{j=1}^{k-1}\Big{(}\frac{a}{j}\Big{)}^{2j}\leq(k-1)\Big{(}\frac{a}{k-1}\Big{)}^{2k-2}$

and further more

$\displaystyle\exp\Big{\\{}\log\Big{(}\frac{k-1}{k}\Big{(}\frac{a}{k-1}\times\frac{k}{a}\Big{)}^{2k-2}\Big{)}\Big{\\}}=\exp\Big{\\{}(2k-1)\log\Big{(}1+\frac{1}{k-1}\Big{)}\Big{\\}}.$
(23)

Notice that if we let $\frac{1}{k-1}-\log(1+\frac{1}{k-1})=b$, we will find
$-b=\log\Big{(}\frac{1+\frac{1}{k-1}}{e^{\frac{1}{k-1}}}\Big{)}$, and we know
$1+x\leq e^{x}$ to be true by the fact that $1+x$ is tangent to $e^{x}$ at
$x=0$ and $e^{x}$ is convex. So $b\geq 0$, and to continue from (23), we have

$\displaystyle\exp\Big{\\{}(2k-1)\log\Big{(}1+\frac{1}{k-1}\Big{)}\Big{\\}}\leq\exp\Big{(}\frac{2k-3}{k-1}\Big{)}\leq
e^{2}.$

Rearrange things a bit, we will get the result. ∎

For the next technique, we will have to dedicate a few rather long pages of
explanation to cover the whole idea, first we will write down it’s definition
[1, Definition 5.3].

######  Definition 2.17.

(Major arc)

  1. 1.

A major arc associated to $f^{(k)}$ is a maximal set
$\mathcal{A}=\\{n_{1},\dots,n_{J}\\}$ of consecutive points of
$\mathcal{S}(f,N,\delta)$, where $J\geq k+1$ is an integer, such that, for all
$j\in\\{1,\dots,J\\}$, we have ($\lfloor x\rceil$ is the nearest integer to
$x$)

$\displaystyle\lfloor f(n_{j})\rceil=P(n_{j})$

where $P\in\mathbb{Q}[X]$ is the Lagrange polynomial of degree $<k$
interpolating the points $(n_{j},\lfloor f(n_{j})\rceil)$. The equation
$y=P(x)$ is called the equation of $\mathcal{A}$. We set $\mathcal{C}_{P}$ the
curve with equation $y=P(x)$.

  2. 2.

Let $q$ be the smallest positive integer such that
$P\in\frac{1}{q}\mathbb{Z}[X]$. Then $q$ is called the denominator of
$\mathcal{A}$.

Notice that the maximal set of points $\mathcal{A}$ depends on the choices of
the Lagrange polynomial and the major arc may not exist for certain such
choices. It might be easier to understand what exactly does the definition
mean by simply constructing a major arc. Select $k$ elements from
$\mathcal{S}(f,N,\delta)$. Apply the formula for Lagrange interpolation
polynomial $P$ on these points. Since the elements we are interpolating are
all integral points, we don’t have to worry about the condition
$P\in\mathbb{Q}[X]$. Let $\mathcal{B}$ be the set such that
$\mathcal{B}=\\{n\in\mathcal{S}(f,N,\delta):\lfloor f(n)\rceil=P(n)\\}$.
$\mathcal{A}$ is the set which contains the longest sequence of elements in
$\mathcal{B}$ that are consecutive in $\mathcal{S}(f,N,\delta)$. To
distinguish whether $\mathcal{A}$ is a major arc or not, we need to see if
$|\mathcal{A}|\geq k+1$.

To continue, we give the following notation

$\displaystyle\mathcal{C}_{\delta}=\Big{\\{}(x,y)\in[N,2N]\times\mathbb{R}:|y-f(x)|<\delta\Big{\\}}.$

One reasonable question to ask at this point would be what will it look like
if $\mathcal{C}_{\delta}$ and $\mathcal{C}_{P}$ are being plotted on the same
graph, and more specifically, what will their intersections be. The following
graph should give us a better idea.

Figure 1: $\mathcal{C}_{\delta}\cap\mathcal{C}_{P}$

As figure 1 has shown, the region of intersection between
$\mathcal{C}_{\delta}$ and $\mathcal{C}_{P}$ is being chopped into several
connected components. Now, we will state the lemma [1, Lemma 5.12] which gives
us a bound for the number of connected components of the set
$\mathcal{C}_{\delta}\cap\mathcal{C}_{P}$.

######  Lemma 2.18.

The set $\mathcal{C}_{\delta}\cap\mathcal{C}_{P}$ has at most $k$ connected
components.

###### Proof.

First, we expand the region where $f(x)$ is defined. Let $\tilde{f}\in
C^{k}(\mathbb{R})$ be a function defined as $\tilde{f}(x)=f(x)$ for
$x\in[N,2N]$,

$\displaystyle\tilde{f}^{(k)}=f^{(k)}(N)\text{ if }x\leq N\text{ and
}\tilde{f}^{(k)}(x)=f^{(k)}(2N)\text{ if }x\geq 2N,$

so that $|\tilde{f}^{(k)}(x)|\asymp\lambda_{k}$. Since $\lambda_{k}>0$, we can
see $\tilde{f}(x)$ is just some polynomial of degree $k$ in the interval
$(-\infty,N]\cup[2N,\infty)$. Now $P$ is a polynomial of degree $<k$ by
definition, so the behaviours of $\tilde{f}$ and $P$ at infinity are different
and the set $\tilde{\mathcal{C}_{\delta}}\cap\mathcal{C}_{P}$ is bounded.
Hence, at both ends of each connected component not reduced to a singleton (a
single point intersection), we would have $P(x)=\tilde{f}(x)\pm\delta$ (the
set $\tilde{\mathcal{C}_{\delta}}$ is the analogue of $\mathcal{C}_{\delta}$
for the function $\tilde{f}$).
What follows next is basically a consequence of divided differences, assume
there are $k+1$ connected components not reduced to a singleton. Then the
equation $P(x)=\tilde{f}(x)\pm\delta$ has at least $k+1$ solutions, say,
$\alpha_{0}<\cdots<\alpha_{k}$. Since the polynomials $P(X)$ and
$P(X)\pm\delta$ have the same leading coefficient, from (3) and the fact that
$P(X)$ has degree $<k$, for some $t_{1},t_{2}\in[\alpha_{0},\alpha_{k}]$ we
get

$\displaystyle 0$
$\displaystyle=\frac{P^{(k)}(t_{1})}{k!}=\sum_{j=0}^{k}\frac{P(\alpha_{j})}{\prod_{0\leq
i\leq k,i\neq
j}(\alpha_{j}-\alpha_{i})}=\sum_{j=0}^{k}\frac{P(\alpha_{j})\pm\delta}{\prod_{0\leq
i\leq k,i\neq j}(\alpha_{j}-\alpha_{i})}$
$\displaystyle=\sum_{j=0}^{k}\frac{\tilde{f}(\alpha_{j})}{\prod_{0\leq i\leq
k,i\neq j}(\alpha_{j}-\alpha_{i})}=\frac{\tilde{f}^{(k)}(t_{2})}{k!}\neq 0,$

which gives the contradiction. ∎

The above lemma gives a bound on the number of connected components and
enables us to discuss which connected component contains most integral points.
The following slight refinement of Definition 2.17 [1, Definition 5.4] would
make this clear. Personally, I find it to be more intuitive.

######  Definition 2.19.

Among the connected components of the set
$\mathcal{C}_{\delta}\cap\mathcal{C}_{P}$, choose the one having the largest
number of points $(n_{h+j},\lfloor f(n_{h+j})\rceil)$ for all
$j\in\\{1,\dots,l\\}$ with $l>k$. Then the set

$\displaystyle\bar{\mathcal{A}}=\\{n_{h+1},\dots,n_{h+l}\\}$

is called a proper major arc extracted from $\mathcal{A}$. The length of
$\bar{\mathcal{A}}$ is the number

$\displaystyle L=n_{h+l}-n_{h+1}.$

For convenience, we introduce the following numbers

$\displaystyle a_{k}=36e^{-2}k(2e^{3})^{k}c_{k}\quad\text{and}\quad
b_{k}=20e^{3}k^{2}c_{k}^{\frac{2}{k(k-1)}},$ (24)

so that $\beta_{k}=b_{k}+4k^{2}$, also $c_{k}$ comes from (1). Notice that
$a_{k}\geq 72e$ since $k,c_{k}\geq 1$.

With all these definitions in hand, now we could deduce a few basic properties
of the major arcs [1, Lemma 5.13].

######  Lemma 2.20.

Let $\mathcal{A}$ be a major arc associated to $f^{(k)}$ and
$\bar{\mathcal{A}}$ be the proper major arc taken from $\mathcal{A}$ with
denominator $q$, length $L$ and equation $y=P(x)$.

  1. 1.

We have

$\displaystyle L\leq
2k\Big{(}\frac{\delta}{\lambda_{k}}\Big{)}^{\frac{1}{k}}.$

  2. 2.

We have

$\displaystyle|\bar{\mathcal{A}}|\leq 2kLq^{-\frac{2}{k(k-1)}}.$

  3. 3.

If $q\leq(a_{k}\delta)^{-1}$, then the distance $d$ between each point of
$\mathcal{S}(f,N,\delta)\setminus\mathcal{A}$ and $\bar{A}$ satisfies

$\displaystyle d>L(a_{k}q\delta)^{-\frac{1}{k}}.$

where $a_{k}$ is defined in (24).

###### Proof.

  1. 1.

Set $\bar{A}=\\{n_{h},\dots,n_{h}+L\\}$ and define $g(x)=f(x)-P(x)$. Let
$\alpha_{j}=n_{h}+j\frac{L}{k}$ for $j\in\\{0,\dots,k\\}$. By using (3) and
the fact that $P(x)$ has degree $<k$ and by the assumption (1) that
$|f^{(k)}(x)|\asymp\lambda_{k}$, for some $t\in[\alpha_{0},\alpha_{k}]$, we
get

$\displaystyle\frac{f^{(k)}(t)}{k!}=\frac{g^{(k)}(t)}{k!}$
$\displaystyle=\sum_{j=0}^{k}\frac{g(\alpha_{j})}{\prod_{0\leq j\leq k,i\neq
j}(\alpha_{j}-\alpha_{i})}$
$\displaystyle=\Big{(}\frac{k}{L}\Big{)}^{k}\sum_{j=0}^{k}\frac{g(\alpha_{j})}{\prod_{0\leq
i\leq k,i\neq j}(j-i)}.$

We can see by the way we defined $g(x)$, $|g(\alpha_{j})|\leq\delta$, the
above equation can be rewritten as

$\displaystyle\frac{\lambda_{k}}{k!}$
$\displaystyle\leq\frac{f^{(k)}(t)}{k!}\leq\delta\Big{(}\frac{k}{L}\Big{)}^{k}\sum_{j=0}^{k}\frac{1}{\prod_{0\leq
i\leq k,i\neq
j}(j-i)}\leq\delta\Big{(}\frac{k}{L}\Big{)}^{k}\sum_{j=0}^{k}\frac{1}{(k-j)!j!}$
$\displaystyle=\frac{\delta}{k!}\Big{(}\frac{k}{L}\Big{)}^{k}\sum_{j=0}^{k}\binom{k}{j}=\frac{2^{k}\delta}{k!}\Big{(}\frac{k}{L}\Big{)}^{k}.$

A further note on the third inequality above, we can imagine the product
$\prod_{0\leq i\leq k,i\neq j}(j-i)$ as multiplying the differences between
$j$ and each element in $\\{1,\dots,k\\}\setminus j$, to avoid the product
being negative, we could simply separate the product to 2 parts, and get
$|\prod_{0\leq i\leq k,i\neq j}(j-i)|=j!(k-j)!$. Also it still might be worth
mentioning that $2^{k}=(1+1)^{k}=\sum_{j=0}^{k}\binom{k}{j}1^{k-j}1^{j}$,
which gives us the final part above. By rearranging the above equation, we
will obtain the required bound.

  2. 2.

Let $n_{1}<\cdots<n_{k}$ be $k$ points lying in $\bar{\mathcal{A}}$. Using the
formula given by the Lagrange interpolation polynomial that we have deduced in
(2) and (3), since the degree of Lagrange polynomial of the major arc is $<k$,
by the uniqueness of the Lagrange polynomial, we can express $P(x)$ as
following

$\displaystyle P(x)=\sum_{j=1}^{k}\Big{(}\prod_{i=1,i\neq
j}^{k}\frac{x-n_{i}}{n_{j}-n_{i}}\Big{)}\lfloor f(n_{i})\rceil$

and

$\displaystyle b_{k}=\sum_{j=1}^{k}\frac{\lfloor f(x_{j})\rceil}{\prod_{1\leq
i\leq k,i\neq j}(n_{j}-n_{i})}=\frac{A}{\prod_{1\leq i<j\leq
k}(n_{j}-n_{i})}.$

Where $b_{k}$ is the leading coefficient of $P(x)$ and A is an integer since
all the data points we are interpolating here are integral points. If we
expand (2), we can see that for each coefficient of $P(x)$, it can be written
in the form of having some integer as numerator and $\prod_{1\leq i<j\leq
k}(n_{j}-n_{i})$ as denominator, so $q$ must be something that is
$\leq\prod_{1\leq i<j\leq k}(n_{j}-n_{i})$ since it is the smallest positive
integer such that $P\in\frac{1}{q}\mathbb{Z}[x]$. Hence, we have

$\displaystyle q\leq\prod_{1\leq i<j\leq k}(n_{j}-n_{i})\leq\prod_{1\leq
i<j\leq k}(n_{k}-n_{1})=(n_{k}-n_{1})^{\frac{k(k-1)}{2}}.$

so that

$\displaystyle L\geq n_{k}-n_{1}\geq q^{\frac{2}{k(k-1)}}.$

Which implies that for any such $k$ points, we have $\frac{L}{n_{k}-n_{1}}\leq
Lq^{\frac{-2}{k(k-1)}}$. So it follows that there can only be at most
$Lq^{\frac{-2}{k(k-1)}}$ distinct intervals in $\bar{A}$ with each contains
$k$ distinct points. Thus

$\displaystyle|\bar{A}|\leq k(\frac{L}{n_{k}-n_{1}}+1)\leq
2kLq^{-\frac{2}{k(k-1)}}.$

  3. 3.

For the third part of the proof, let $n\in\mathcal{S}(f,N,\delta)\setminus A$
and $n_{0}\in\bar{A}$. Without the loss of generality, we can assume that
$n>n_{0}$ and let $m=\lfloor f(n)\rceil$. By the definition of major arc, we
have $m\neq P(n)$ since otherwise $m$ should be in the maximal set
$\mathcal{A}$. So we can say

$\displaystyle|P(n)-m|\geq\frac{1}{q}\geq\frac{1}{3q}+2\delta.$

Because $qP(n)-qm\neq 0$ and $qP(n),qm\in\mathbb{Z}$ by definition, so
$|q(P(n)-qm)|\geq 1$, also $q\leq(a_{k}\delta)^{-1}\leq(3\delta)^{-1}$ by
assumption. Define $g(x)=f(x)-P(x)$, by the triangle inequality we get

$\displaystyle|g(n)-g(n_{0})|$
$\displaystyle\geq|g(n)|-|g(n_{0})|\geq|g(n)|-\delta=|P(n)-f(n)|-\delta$
$\displaystyle\geq|P(n)-m|-|f(n)-m|-\delta\geq\frac{1}{3q}+2\delta-\delta-\delta$
$\displaystyle=\frac{1}{3q}.$ (25)

Since $f\in C^{k}[N,2N]$, by Taylor’s theorem with Lagrange reminder evaluated
at $n_{0}$, we get

$\displaystyle
g(x)=\sum_{j=0}^{k-1}g^{(j)}(n_{0})\frac{(x-n_{0})^{j}}{j!}+R_{k}(x)\quad\text{where}\quad
R_{k}(x)=\frac{g^{(k)}(t)}{k!}(x-n_{0})^{k}.$

for some $t\in[n_{0},n]$, thus

$\displaystyle
g(n)-g(n_{0})=\sum_{j=1}^{k-1}g^{(j)}(n_{0})\frac{d^{j}}{j!}+g^{(k)}(t)\frac{d^{k}}{k!}.$

Applying (1) and (22) on the function $g$ with $M_{0}=\delta$ and
$M_{k}=c_{k}\lambda_{k}$, we get

$\displaystyle|g(n)-g(n_{0})|<4e\delta\sum_{j=1}^{k-1}\Big{(}\frac{ke}{j}\Big{)}^{j}\frac{d^{j}}{j!}\Big{\\{}k^{j+1}L^{-j}+e^{j-1}\Big{(}\frac{c_{k}\lambda_{k}}{\delta}\Big{)}^{j/k}\Big{\\}}+c_{k}\lambda_{k}\frac{d^{k}}{k!}.$
(26)

From the first part of the proof, we know that
$\Big{(}\lambda_{k}/\delta\Big{)}^{1/k}\leq 2k/L$, along with the inequality
for $j\geq 1$, $j!>e(j/e)^{j}$ which can be proved by taking logarithms on
both side. With all we just mentioned in hand, (26) becomes

$\displaystyle|g(n)-g(n_{0})|<{}$ $\displaystyle
4e\delta\sum_{j=1}^{k-1}\Big{(}\frac{ke}{j}\Big{)}^{j}\frac{1}{j!}\\{k^{j+1}+c_{k}^{j/k}e^{-1}(2ek)^{j}\\}(dL^{-1})^{j}+\frac{(2k)^{k}c_{k}\delta
d^{k}}{k!L^{k}}$ $\displaystyle\leq{}$ $\displaystyle
4e\delta\sum_{j=1}^{k-1}\Big{(}\frac{ke}{j}\Big{)}^{j}e^{-1}\Big{(}\frac{e}{j}\Big{)}^{j}\\{k^{j+1}+c_{k}^{j/k}e^{-1}(2ek)^{j}\\}(dL^{-1})^{j}$
$\displaystyle+\frac{(2k)^{k}c_{k}\delta
d^{k}}{L^{k}}e^{-1}\Big{(}\frac{e}{k}\Big{)}^{k}.$

Since for $j\in\\{1,\dots,k-1\\}$,
$(dL^{-1})^{j}\leq\max\Big{(}dL^{-1},(dL^{-1})^{k-1}\Big{)}$. We can continue
to say

$\displaystyle|g(n)-g(n_{0})|<{}$ $\displaystyle
4\delta\Big{(}dL^{-1}+(dL^{-1})^{k-1}\Big{)}\sum_{j=1}^{k-1}\Big{(}\frac{ke}{j}\Big{)}^{2j}\\{k+c_{k}^{j/k}e^{-1}(2e)^{j}\\}$
$\displaystyle+(2e)^{k}e^{-1}c_{k}\delta(dL^{-1})^{k}$ $\displaystyle\leq{}$
$\displaystyle
4\delta(dL^{-1}+(dL^{-1})^{k-1})(k+c_{k}2^{k-1}e^{k-2})\sum_{j=1}^{k-1}\Big{(}\frac{ke}{j}\Big{)}^{2j}$
$\displaystyle+(2e)^{k}e^{-1}c_{k}\delta(dL^{-1})^{k}.$

Notice the fact that $c_{k}2^{k-1}e^{k-2}\geq 2^{k-1}e^{k-2}$ since $c_{k}\geq
1$, and by using induction for $k\in\mathbb{N}$ and $k\geq 3$, we can show
$2^{k-1}>k$, thus $c_{k}2^{k-1}e^{k-2}>k$. So (LABEL:27) will become

$\displaystyle|g(n)-g(n_{0})|<2$
${}^{k+2}e^{k-2}c_{k}\delta\Big{(}dL^{-1}+(dL^{-1})^{k-1}\Big{)}\sum_{j=1}^{k-1}\Big{(}\frac{ke}{j}\Big{)}^{2j}$
$\displaystyle+(2e)^{k}e^{-1}c_{k}\delta(dL^{-1})^{k}.$

Using the technique we have discussed before, Lemma 2.16, also remembering
that $a_{k}=36e^{-2}k(2e^{3})^{k}c_{k}$ from (24), we can get

$\displaystyle|g(n)-g(n_{0})|<{}$ $\displaystyle
4e^{-2}k(2e^{3})^{k}c_{k}\delta\Big{(}dL^{-1}+(dL^{-1})^{k-1}\Big{)}$
$\displaystyle+(2e)^{k}e^{-1}c_{k}\delta(dL^{-1})^{k}$ $\displaystyle={}$
$\displaystyle
9^{-1}a_{k}\delta\Big{(}dL^{-1}+(dL^{-1})^{k-1}\Big{)}+(2e)^{k}e^{-1}c_{k}\delta(dL^{-1})^{k}$
$\displaystyle\leq{}$ $\displaystyle
9^{-1}a_{k}\delta\Big{(}dL^{-1}+(dL^{-1})^{k-1}+(dL^{-1})^{k}\Big{)}.$

With the inequality we get from (25), we have

$\displaystyle
q^{-1}<3^{-1}a_{k}\delta\Big{(}dL^{-1}+(dL^{-1})^{k-1}+(dL^{-1})^{k}\Big{)}$
$\displaystyle
1<qa_{k}\delta\max\Big{(}dL^{-1},(dL^{-1})^{k-1},(dL^{-1})^{k}\Big{)}.$

which means

$\displaystyle
dL^{-1}>\min\Big{\\{}(a_{k}q\delta)^{-1},(a_{k}q\delta)^{-\frac{1}{k-1}},(a_{k}q\delta)^{-\frac{1}{k}}\Big{\\}}.$

Since by the assumption, we have $a_{k}\delta q\leq 1$, so

$\displaystyle\min\Big{\\{}(a_{k}q\delta)^{-1},(a_{k}q\delta)^{-\frac{1}{k-1}},(a_{k}q\delta)^{-\frac{1}{k}}\Big{\\}}=(a_{k}q\delta)^{-\frac{1}{k}}.$

Which implies the statement of the lemma. ∎

A reasonable question to ask right now is what is the total number of points
in $\mathcal{R}(f,N,\delta)$ that can be contained in some major arc
associated to $f^{(k)}$? Remember that by the definition, given different
Lagrange polynomials, there could be many major arcs associated to $f^{(k)}$.
We now are in the position to estimate such contribution of points coming from
major arcs. Proof of the lemma is changed from the original paper [11] and the
book [1, Lemma 5.14] due to the oversight we have mentioned in the
introduction, if reader is interested, have a look at the original proof which
can be found both in the paper and the book would be a very good idea.

######  Lemma 2.21.

Let $R_{0}$ be the contribution of points coming from the major arcs
associated to $f^{(k)}$, such that $R_{0}\subset\mathcal{R}(f,N,\delta)$. Then

  * •

If the set of points in each proper major arc with denominator
$\leq(a_{k}\delta)^{-1}$ can be covered with an interval of length
$L_{j}(a_{k}q_{j}\delta)^{-1/k}$ which is disjoint from all such covers for
other major arcs, where $L_{j}$ and $q_{j}$ are the length and denominator
associated with their proper major arcs:

$\displaystyle R_{0}\leq
b_{k}N\delta^{\frac{2}{k(k-1)}}+8k^{3}\Big{(}\frac{\delta}{\lambda_{k}}\Big{)}^{1/k}+10e^{3}k^{2}.$

  * •

Otherwise:

$\displaystyle
R_{0}\leq\frac{3}{2}b_{k}N\delta^{\frac{2}{k(k-1)}}+16k^{3}\Big{(}\frac{\delta}{\lambda_{k}}\Big{)}^{1/k}+10e^{3}k^{2}$

where $a_{k},b_{k}$ are defined in (24).

###### Proof.

Let $\mathcal{M}_{0}$ be the set of major arcs and $Q_{k}>0$ be the real
number defined by

$\displaystyle Q_{k}=(a_{k}\delta)^{-1}$

where $a_{k}$ is defined in (24). Write
$\mathcal{M}_{0}=\mathcal{M}_{1}\cup\mathcal{M}_{2}$ where $\mathcal{M}_{1}$
is the set of major arcs with denominator $>Q_{k}$ and
$\mathcal{M}_{2}=\mathcal{M}_{0}\setminus\mathcal{M}_{1}$. For
$i\in\\{1,2\\}$, let

$\displaystyle
S_{i}=\bigcup_{\mathcal{A}\in\mathcal{M}_{i}}\bar{\mathcal{A}}\quad\text{and}\quad
R_{i}=|S_{i}|.$

We can see that $R_{i}$ can be understood as the total number of points
contained in the proper major arcs inside $\mathcal{M}_{i}$. From Lemma 2.18,
we know that there are at most $k$ connected components. By definition, the
proper major arc is the component that intersects the most integral points, so
we can deduce $R_{0}\leq k(R_{1}+R_{2})$.

  * •

Estimate of $R_{1}$. This estimate is rendered trivial by the second part of
the result of Lemma 2.20. Choose a proper major arc in $\mathcal{M}_{1}$ with
$k$ consecutive points $n_{1},\dots,n_{k}$ such that $n_{k}-n_{1}$ is the
smallest. By the Lemma, we have $n_{k}-n_{1}\geq
q^{\frac{2}{k(k-1)}}>Q_{k}^{\frac{2}{k(k-1)}}$, so that

$\displaystyle R_{1}\leq k(NQ_{k}^{-\frac{2}{k(k-1)}}+1)<{}$ $\displaystyle
10e^{3}k\Big{(}N(c_{k}\delta)^{\frac{2}{k(k-1)}}+1\Big{)}$ $\displaystyle={}$
$\displaystyle b_{k}(2k)^{-1}N\delta^{\frac{2}{k(k-1)}}+10e^{3}k.$

  * •

Estimate of $R_{2}$. Since $q$ is a positive integer, we may assume that
$Q_{k}\geq 1$, otherwise $S_{2}=\emptyset$ which is just trivial. Let
$\bar{\mathcal{A}_{1}},\dots,\bar{\mathcal{A}}_{J}$ be the ordered sequence of
proper major arcs with denominator $q_{j}\leq Q_{k}$. For each proper major
arc $\bar{\mathcal{A}}_{J}$, we set $n_{j}$ and $L_{j}$ its first point and
length, and define

$\displaystyle d_{j}=L_{j}(a_{k}q_{j}\delta)^{-1/k}$

and $\mathcal{I}_{j}=[n_{j},n_{j}+d_{j}]$.

To continue, we first need to justify the fact that two proper major arcs with
their denominators $q_{j},q_{i}\leq Q_{k}$ do not intersect each other. Notice
that $\bar{\mathcal{A}}_{i}\nsubseteq\mathcal{A}_{j}$, this is indeed true by
the definition of the major arc and the uniqueness of the Lagrange
interpolation. Since a proper major arc must contain more than $k+1$ points,
the uniqueness of the Lagrange interpolation tells us there is only one such
polynomial with degree $<k$, if $\bar{\mathcal{A}}_{i}\subset\mathcal{A}_{j}$,
it will result in the two Lagrange interpolation polynomials associate to the
two major arcs equal being $P_{j}=P_{i}$. So there must exist a point $a$ such
that $a\in\bar{\mathcal{A}}_{i}$ and
$a\in\mathcal{S}(f,N,\delta)\setminus\mathcal{A}_{j}$, by Lemma 2.20 we have
$\operatorname{dist}(a,\bar{\mathcal{A}}_{j})>d_{j}$. Similarly, $\exists$
$b\in\bar{\mathcal{A}}_{j}$ such that
$\operatorname{dist}(b,\bar{\mathcal{A}}_{i})>d_{i}$. Now, let’s assume two
proper major arcs with their denominators $q_{j},q_{i}\leq Q_{k}$ intersect
each other. Without loss of generality, let’s assume that the first point of
one proper major arc intersects the last point of the other proper major arc.
As showing in the graph below.

Figure 2: Intersection of two proper major arcs

In the case of intersection, since $q_{i},q_{j}\leq Q_{k}$, we have

$\displaystyle d_{j}\geq
L_{j}(a_{k}Q_{k}\delta)^{-1/k}=L_{j}\quad\text{and}\quad d_{i}\geq
L_{i}(a_{k}Q_{k}\delta)^{-1/k}=L_{i}$

And this will give us a contradiction as follows

$\displaystyle L_{i}>d_{j}\geq L_{j}\quad\text{and}\quad L_{j}>d_{i}\geq
L_{i}$

So two proper major arcs in the setting we are in cannot have an intersection.

######  Case 1.

Distance between $n_{j}$ and $n_{j+1}$ $>d_{j}$.

We can see that $\mathcal{I}_{j}$ contains $\bar{\mathcal{A}_{j}}$ and does
not contain $\bar{\mathcal{A}}_{j+1}$, this is indeed true, since $q_{j}\leq
Q_{k}$, we have $d_{j}\geq L_{j}(a_{k}Q_{k}\delta)^{-1/k}=L_{j}$. Also, by
assumption, $\mathcal{I}_{j}\cap\bar{\mathcal{A}}_{j+1}=\emptyset$.

Therefore the intervals $\mathcal{I}_{j}$ are pairwise distinct. Using Lemma
2.11 with $S=S_{2}$, we get

$\displaystyle R_{2}\leq
N\max_{j}\frac{|\bar{\mathcal{A}}_{j}|}{d_{j}}+2\max_{j}|\bar{\mathcal{A}}_{j}|.$
(28)

Now by second part of Lemma 2.20 and the choice of $d_{j}$, we have

$\displaystyle\frac{|\bar{\mathcal{A}}_{j}|}{d_{j}}\leq
2kL_{j}q_{j}^{-\frac{2}{k(k-1)}}L_{j}^{-1}(a_{k}q_{j}\delta)^{1/k}=2k(a_{k}\delta)^{1/k}q_{j}^{\frac{k-3}{k(k-1)}}$

and since $q_{j}\leq Q_{k}=(a_{k}\delta)^{-1}$ and $k\geq 3$, we obtain

$\displaystyle\frac{|\bar{\mathcal{A}}_{j}|}{d_{j}}\leq
2k(a_{k}\delta)^{\frac{2}{k(k-1)}}<10e^{3}k(c_{k}\delta)^{\frac{2}{k(k-1)}}=b_{k}(2k)^{-1}\delta^{\frac{2}{k(k-1)}}$

for $j\in\\{1,\dots,J\\}$, and therefore by part 1 and 2 of Lemma 2.20

$\displaystyle R_{2}\leq
b_{k}(2k)^{-1}N\delta^{\frac{2}{k(k-1)}}+4k\max_{j}L_{j}\leq
b_{k}(2k)^{-1}N\delta^{\frac{2}{k(k-1)}}+8k^{2}\Big{(}\frac{\delta}{\lambda_{k}}\Big{)}^{1/k}.$

Combining both estimates and the fact that $R_{0}\leq k(R_{1}+R_{2})$, we get
the result.

######  Case 2.

Distance between $n_{j}$ and $n_{j+1}$ $\leq d_{j}$.

Here we can see that the intersection between
$\mathcal{I}_{j}\cap\bar{\mathcal{A}}_{j+1}\neq\emptyset$, the graph below
should give a better idea.

Figure 3: Proper major arcs

Since we have proved that proper major arcs are disjoint from each other. By
part three of Lemma 2.20, there exist a point in $\bar{\mathcal{A}}_{j+1}$
with distance $>d_{j}$ away from any point in $\bar{\mathcal{A}}_{j}$. We can
see that $\mathcal{I}_{j}$ must be disjoint from $\bar{\mathcal{A}}_{j+2}$.
Also $\bar{\mathcal{A}}_{j}\subset\mathcal{I}_{j}$ as in $Case$ 1\. Let

$\displaystyle S_{3}=\bigcup_{i\text{ is
odd}}\bar{\mathcal{A}}_{i}\quad\text{and}\quad S_{4}=\bigcup_{i\text{ is
even}}\bar{\mathcal{A}}_{i}\quad\text{and}\quad R_{j}=|S_{j}|,\quad
j\in\\{3,4\\}.$

We can see $S_{3}\cup S_{4}=S_{2}$ and $R_{2}=R_{3}+R_{4}$. By the same
argument as $Case$ 1, we have

$\displaystyle R_{3},R_{4}\leq
b_{k}(2k)^{-1}N\delta^{\frac{2}{k-1}}+8k^{2}\Big{(}\frac{\delta}{\lambda_{k}}\Big{)}^{1/k}.$

So

$\displaystyle R_{2}\leq
b_{k}k^{-1}N\delta^{\frac{2}{k(k-1)}}+16k^{2}\Big{(}\frac{\delta}{\lambda_{k}}\Big{)}^{1/k}.$

Combining both estimate, we get

$\displaystyle R_{0}\leq
k(R_{1}+R_{2})\leq\frac{3}{2}b_{k}N\delta^{\frac{2}{k(k-1)}}+16k^{3}\Big{(}\frac{\delta}{\lambda_{k}}\Big{)}^{1/k}+10e^{3}k^{2}.\quad\qed$

###  2.4 The Proof of the Theorem of Huxley and Sargos

From the end of the previous section, we get an estimation of the contribution
of points of $\mathcal{S}(f,N,\delta)$ which come from major arcs. The next
natural step to progress our proof of the theorem of Huxley and Sargos is to
estimate the contribution of those points which do not come from major arcs.
The next Lemma [1, Lemma 5.15] we will state provides such an estimate, and
its proof is similar to the proof of the $k$th derivative test. Also, again to
avoid the trivial case, we may assume $\mathcal{R}(f,N,\delta)\geq k+1$.

######  Lemma 2.22.

Let $N\leq n_{0}<\cdots<n_{k}\leq 2N$ be $k+1$ points of
$\mathcal{S}(f,N,\delta)$, which do not lie on the same algebraic curve of
degree $<k$. Then

$\displaystyle
n_{k}-n_{0}>\min\Big{(}(c_{k}\lambda_{k})^{-\frac{2}{k(k+1)}},2^{-1}\delta^{-\frac{2}{k(k-1)}}\Big{)}.$

###### Proof.

By definition, there exist integers $m_{0},\dots,m_{k}$ and real numbers
$\delta_{0},\dots,\delta_{k}$ such that

$\displaystyle f(n_{j})=m_{j}+\delta_{j}$

with $|\delta_{j}|<\delta$ for all $j\in\\{0,\dots,k\\}$. We define $D_{k}$ as
follows

$\displaystyle D_{k}=\prod_{0\leq h<i\leq k}(n_{i}-n_{h})>0.$

and let $P=b_{k}X^{k}+\cdots+b_{0}$ be the Lagrange polynomial interpolating
the points $(n_{j},m_{j})$. Then we have

$\displaystyle b_{k}=\sum_{j=0}^{k}\frac{m_{j}}{\prod_{0\leq i\leq k,i\neq
j}(n_{j}-n_{i})}=\frac{A_{k}}{D_{k}}$

where $A_{k}\in\mathbb{Z}$, since the points we are interpolating are integral
points. Reasoning exactly in the same way as in the proof of Theorem 2.10, we
get

$\displaystyle
k!A_{k}=D_{k}f^{(k)}(t)-k!D_{k}\sum_{j=0}^{k}\frac{\delta_{j}}{\prod_{0\leq
i\leq k,i\neq j}(n_{j}-n_{i})}.$

Since the points we are interpolating do not lie on the same algebraic curve
of degree $<k$, we have $b_{k}\neq 0$. Since $A_{k}$ is an integer, we have
$|A_{k}|\geq 1$, and using $|\delta_{j}|<\delta$ and condition (1) we get

$\displaystyle k!\leq k!|A_{k}|$ $\displaystyle<c_{k}\lambda_{k}D_{k}+k!\delta
D_{k}\sum_{j=0}^{k}\frac{1}{\prod_{0\leq i\leq k,i\neq j}|n_{j}-n_{i}|}$
$\displaystyle=c_{k}\lambda_{k}D_{k}+k!\delta\sum_{j=0}^{k}\prod_{\begin{subarray}{c}0\leq
h<i\leq k\\\ h\neq j,i\neq j\end{subarray}}(n_{i}-n_{h})$ $\displaystyle\leq
c_{k}\lambda_{k}(n_{k}-n_{0})^{\frac{k(k+1)}{2}}+(k+1)!\delta(n_{k}-n_{0})^{\frac{k(k-1)}{2}}.$

which suggests that either

$\displaystyle k!\leq
2c_{k}\lambda_{k}(n_{k}-n_{0})^{\frac{k(k+1)}{2}}\quad\text{or}\quad k!\leq
2(k+1)!\delta(n_{k}-n_{0})^{\frac{k(k-1)}{2}}$

and this implies

$\displaystyle
n_{k}-n_{0}>\min\Big{(}\Big{(}\frac{k!}{2}\Big{)}^{\frac{2}{k(k+1)}}(c_{k}\lambda_{k})^{-\frac{2}{k(k+1)}},(2k+2)^{-\frac{2}{k(k-1)}}\delta^{-\frac{2}{k(k-1)}}\Big{)}\quad\qed$

Finally, with all the techniques and results in hand, we are in the position
to give a conclusion to this chapter, which is the proof of the theorem of
Huxley and Sargos Theorem 2.1. Beside changes due to the oversight, the
general spirit of the proof stays true to the original. The original proof was
given both in the book by Bordellès [1, p. 383] and the paper by Huxley [11].

###### Proof.

Let $S_{0}$ be the set of points of $\mathcal{S}(f,N,\delta)$ coming from the
major arcs and $T_{0}=\mathcal{S}(f,N,\delta)\setminus S_{0}$. By Lemma 2.21,
we have

$\displaystyle|S_{0}|=R_{0}\leq
b_{k}N\delta^{\frac{2}{k(k-1)}}+8k^{3}\Big{(}\frac{\delta}{\lambda_{k}}\Big{)}^{1/k}+10e^{3}k^{2}$

or depending on the condition we discussed before

$\displaystyle|S_{0}|=R_{0}\leq\frac{3}{2}b_{k}N\delta^{\frac{2}{k(k-1)}}+16k^{3}\Big{(}\frac{\delta}{\lambda_{k}}\Big{)}^{1/k}+10e^{3}k^{2}$

where $b_{k}$ is given in (24). Now let $G=\\{n_{0},\dots,n_{k^{2}}\\}$ be a
set of $k^{2}+1$ consecutive ordered points of $T_{0}$, again here we assume
the size of $T_{0}$ is larger than $k^{2}+1$, otherwise the result is trivial.
Since $G$ is not contained in any major arc, so we can find an integer
$j\in\\{k,\dots,k^{2}\\}$ such that $j+1$ points $(n_{i},m_{i})$ do not lie on
the same algebraic curve of degree $<k$. By Lemma 2.22, we have

$\displaystyle n_{k^{2}}-n_{0}\geq n_{j}-n_{0}\geq
n_{k}-n_{0}>\min\Big{(}(c_{k}\lambda_{k})^{-\frac{2}{k(k+1)}},2^{-1}\delta^{-\frac{2}{k(k-1)}}\Big{)}$

which means

$\displaystyle|T_{0}|\leq
2k^{2}\Big{(}N(c_{k}\lambda_{k})^{\frac{2}{k(k+1)}}+2N\delta^{\frac{2}{k(k-1)}}+1\Big{)}$

and the proof is completed with the fact that
$\mathcal{R}(f,N,\delta)\leq|T_{0}|+|S_{0}|$. ∎

##  3 Optimality of The Methods

###  3.1 Integral Points Around Polynomials

In this chapter, we will discuss the optimality of Theorem 2.1, that is
whether the bound

$\displaystyle\mathcal{R}(f,N,\delta)\ll
N\lambda_{k}^{\frac{2}{k(k+1)}}+N\delta^{\frac{2}{k(k-1)}}+\big{(}\frac{\delta}{\lambda_{k}}\big{)}^{\frac{1}{k}}+1$
(29)

could be improved with some extra conditions or if the bound is false without
certain conditions. A good place to start will be putting the theorem to the
test where polynomials are concerned. First, let’s discuss some general
scenario where a better bound can be obtained.

######  Proposition 3.1.

Let $\delta\in[0,\frac{1}{4}]$, $N,k\in\mathbb{Z}_{\geq 1}$ and
$P=\alpha_{k}X^{k}+\dots+\alpha_{0}\in\mathbb{R}[x]$. If there exist
$a\in\mathbb{Z}$ and $q\in[1,N^{k}]\cap\mathbb{Z}$ such that the greatest
common divisor $(a,q)=1$ and $|\alpha_{k}-\frac{a}{q}|\leq\frac{1}{q^{2}}$,
then for all $\epsilon>0$

$\displaystyle\mathcal{R}(P,N,\delta)\ll
Nq^{-1/k}+N\delta^{\frac{2}{k(k+1)}}+N^{\epsilon}$

the term $N^{\epsilon}$ being replaced by $1$ if $k=1$.

If $\alpha_{k}\in(0,1]$, then we can take $a=1$ and
$q=\lfloor\alpha_{k}^{-1}\rfloor$. So if we further assume that
$\alpha_{k}\in[N^{-k},1]$, then we derive

$\displaystyle\mathcal{R}(P,N,\delta)\ll
N\alpha_{k}^{1/k}+N\delta^{\frac{2}{k(k+1)}}+N^{\epsilon}.$ (30)

If $\alpha_{k}>1$, then the bound (30) is trivial provided that
$\alpha_{k}\geq N^{-k}$. Now if $\alpha_{k}<N^{-k}$, then $N<\alpha^{-1/k}$,
and thus we can derive the following corollary.

######  Corollary 3.2.

Let $\delta\in[0,\frac{1}{4}]$, $N,k\in\mathbb{Z}_{\geq 1}$ and
$P=\alpha_{k}X^{k}+\alpha_{k-1}X^{k-1}+\dots+\alpha_{0}\in\mathbb{R}[x]$ with
$\alpha_{k}>0$. Then, for all $\epsilon>0$,

$\displaystyle\mathcal{R}(P,N,\delta)\ll
N\alpha_{k}^{1/k}+N\delta^{\frac{2}{k(k+1)}}+\alpha_{k}^{-1/k}+N^{\epsilon},$

the term $N^{\epsilon}$ being replaced by $1$ if $k=1$.

Next, we can see from the proof of Theorem 2.1 that the bound
$\mathcal{R}(f,N,\delta)\leq|T_{0}|+|S_{0}|$ has two parts. If the function
$f$ is already in the form of a Lagrange polynomial with rational coefficient,
then the contribution of the points in the set $\mathcal{S}(f,N,\delta)$ will
only come from major arcs, that is

$\displaystyle\mathcal{R}(f,N,\delta)\leq
b_{k}N\delta^{\frac{2}{k(k-1)}}+8k^{3}\Big{(}\frac{\delta}{\lambda_{k}}\Big{)}^{1/k}+10e^{3}k^{2}$

or

$\displaystyle\mathcal{R}(f,N,\delta)\leq\frac{3}{2}b_{k}N\delta^{\frac{2}{k(k-1)}}+16k^{3}\Big{(}\frac{\delta}{\lambda_{k}}\Big{)}^{1/k}+10e^{3}k^{2}.$

###  3.2 Further Refinements

The refinements of Theorem 2.1 have been made in several directions, first we
will see that the result can still hold for $k=2$ [2]. We will show the
following version which is stated explicitly in [1, Theorem 5.6].

######  Theorem 3.3 (Branton-Sargos).

Let $f\in C^{2}[N,2N]$ such that there exists $\lambda_{2}>0$ such that, for
all $x\in[N,2N]$, we have

$\displaystyle|f^{\prime\prime}(x)|\asymp\lambda_{2}.$

Then

$\displaystyle\mathcal{R}(f,N,\delta)\ll
N\lambda_{2}^{1/3}+N\delta+\Big{(}\frac{\delta}{\lambda_{2}}\Big{)}^{1/2}+1.$

If in addition there exists $\lambda_{1}>0$ such that
$|f^{\prime}(x)|\asymp\lambda_{1}$ for all $x\in[N,2N]$, then

$\displaystyle\mathcal{R}(f,N,\delta)\ll
N\lambda_{2}^{1/3}+N\delta+\lambda_{1}\Big{(}\frac{\delta}{\lambda_{2}}\Big{)}^{1/2}+\frac{\delta}{\lambda_{1}}+1.$

From Theorem 2.1, $N\lambda_{k}^{\frac{2}{k(k+1)}}$ is the main term of the
equality. It’s very difficult to improve on the main term. The others are the
secondary terms and the quantity $(\delta\lambda_{k}^{-1})^{1/k}$ is quasi-
optimal. So we turn our eyes on the term $N\delta^{\frac{2}{k(k-1)}}$, to see
whether it may be improved. This is done by generalizing the method used in
Theorem 3.3 and by using a $k$-dimensional version of the reduction principle
and a new divisibility relation on the divided differences discovered by
Filaseta and Trifonov. They proved the following result [1, Theorem 5.7].

######  Theorem 3.4.

Let $k\geq 3$ be an integer and $f\in C^{k}[N,2N]$ such that there exist
$\lambda_{k-1}>0$ and $\lambda_{k}>0$ such that, for all $x\in[N,2N]$, we have

$\displaystyle|f^{(k-1)}(x)|\asymp\lambda_{k-1},\quad|f^{(k)}(x)|\asymp\lambda_{k}\quad\text{and}\quad\lambda_{k-1}=N\lambda_{k}.$
(31)

Then the following upper bounds hold.

  * •

For all $k\geq 3$, we have

$\displaystyle\mathcal{R}(f,N,\delta)\ll
N\lambda_{k}^{\frac{2}{k(k+1)}}+N\delta^{\frac{2}{(k-1)(k-2)}}+N(\delta\lambda_{k-1})^{\frac{2}{k^{2}-k+2}}+\Big{(}\frac{\delta}{\lambda_{k-1}}\Big{)}^{\frac{1}{k-1}}+1.$

  * •

For $k=3$, we have

$\displaystyle\mathcal{R}(f,N,\delta)\ll
N\lambda_{3}^{1/6}+N\delta^{2/3}+N(\delta^{3}\lambda_{3})^{1/12}+\Big{(}\frac{\delta}{\lambda_{2}}\Big{)}^{1/2}+1.$

  * •

For all $k\geq 4$ and $\epsilon>0$, we have

$\displaystyle\mathcal{R}(f,N,\delta)\ll\Big{\\{}$ $\displaystyle
N\lambda_{k}^{\frac{2}{k(k+1)}}+N(\delta\lambda_{k-1})^{\frac{2}{k^{2}-k+2}}+N\delta^{\frac{4}{k^{2}-3k+6}}$
$\displaystyle+N(\delta^{2}N^{-1}\lambda_{k-1}^{-1})^{\frac{2}{k^{2}-3k+4}}\Big{\\}}N^{\epsilon}+\Big{(}\frac{\delta}{\lambda_{k-1}}\Big{)}^{\frac{1}{k-1}}+1.$

  * •

For all $k\geq 5$, we have

$\displaystyle\mathcal{R}(f,N,\delta)\ll
N\lambda_{k}^{\frac{2}{k(k+1)}}+N\delta^{\frac{2}{(k-1)(k-2)}}+\Big{(}\frac{\delta}{\lambda_{k-1}}\Big{)}^{\frac{1}{k-1}}+1.$

We can see easily that Theorem 2.1 implies the $k$th derivative test, because
the condition $\delta\ll\lambda_{k}$ means the main term dominates all the
others. The following result is an estimate analogous to the $k$th derivative
test but with a more flexible condition than (18) [1, Proposition 5.2].

######  Proposition 3.5.

Let $f\in C^{\infty}[N,2N]$ such that there exists $T\geq 1$ such that, for
all $x\in[N,2N]$ and all $j\in\mathbb{Z}_{\geq 0}$, we have

$\displaystyle|f^{(j)}(x)|\asymp\frac{T}{N^{j}},$ (32)

and

$\displaystyle N\delta\leq T\leq\delta^{-1}.$ (33)

Then for all $k\geq 1$, we have

$\displaystyle\mathcal{R}(f,N,\delta)\ll
T^{\frac{2}{k(k+1)}}N^{\frac{k-1}{k+1}}.$

Note that, using the notion of (32), for $k\geq 2$, Huxley and Sargos’s result
may be stated as follow

$\displaystyle\mathcal{R}(f,N,\delta)\ll
T^{\frac{2}{k(k+1)}}N^{\frac{k-1}{k+1}}+N\delta^{\frac{2}{k(k-1)}}+N(\delta
T^{-1})^{1/k},$ (34)

and the term $N(\delta T^{-1})^{1/k}$ is dominated by the term
$N\delta^{\frac{2}{k(k-1)}}$ for $k\geq 3$. So if Proposition 3.5 is true, it
tells us that the condition (33) is sufficient to remove both these two terms
mentioned.

###### Proof.

We will be using induction to prove the proposition. For $k=1$, by the first
derivative test we have

$\displaystyle\mathcal{R}(f,N,\delta)$ $\displaystyle\ll
N\lambda_{1}+N\delta+\frac{\delta}{\lambda_{1}}+1=N\frac{T}{N}+N\delta+\frac{\delta}{T/N}+1$
$\displaystyle=T+N\delta+\delta\frac{N}{T}+1\ll T\qquad\text{by (\ref{33})}.$

Now suppose the claim to be true for some $k\geq 1$, that is
$\mathcal{R}(f,N,\delta)\ll T^{\frac{2}{k(k+1)}}N^{\frac{k-1}{k+1}}$. Now by
Huxley and Sargos’s result (34), what we have for $k+1$ is

$\displaystyle\mathcal{R}(f,N,\delta)\ll
T^{\frac{2}{(k+1)(k+2)}}N^{\frac{k}{k+2}}+N\delta^{\frac{2}{k(k+1)}}+N(\delta
T^{-1})^{\frac{1}{k+1}}.$

Let

$\displaystyle
E=\max\Big{(}T^{\frac{2}{(k+1)(k+2)}}N^{\frac{k}{k+2}},N\delta^{\frac{2}{k(k+1)}},N(\delta
T^{-1})^{\frac{1}{k+1}}\Big{)}=\max(e_{1},e_{2},e_{3}).$

We will get

$\displaystyle\mathcal{R}(f,N,\delta)\ll\min\Big{(}E,T^{\frac{2}{k(k+1)}}N^{\frac{k-1}{k+1}}\Big{)}.$

The result follows if $E=e_{1}$. Now to discuss the cases where $E=e_{2}$ and
$E=e_{3}$ separately we will need the following obvious inequality. If
$x,y\geq 0$ and $0\leq a\leq 1$, then $\min(x,y)\leq x^{a}y^{1-a}$.

  * •

Case $E=e_{2}$, we choose $a=\frac{1}{k+2}$. By the inequality we have deduced
and (33)

$\displaystyle\min\Big{(}e_{2},T^{\frac{2}{k(k+1)}}N^{\frac{k-1}{k+1}}\Big{)}$
$\displaystyle\leq
T^{\frac{2}{(k+1)(k+2)}}N^{\frac{k}{k+2}}(T\delta)^{\frac{2}{k(k+1)(k+2)}}$
$\displaystyle\leq T^{\frac{2}{(k+1)(k+2)}}N^{\frac{k}{k+2}}.$

  * •

Case $E=e_{3}$, we choose $a=\frac{2}{k+2}$, similar as in the previous case,
we get

$\displaystyle\min\Big{(}e_{3},T^{\frac{2}{k(k+1)}}N^{\frac{k-1}{k+1}}\Big{)}$
$\displaystyle\leq T^{\frac{2}{(k+1)(k+2)}}N^{\frac{k}{k+2}}(N\delta
T^{-1})^{\frac{2}{(k+1)(k+2)}}$ $\displaystyle\leq
T^{\frac{2}{(k+1)(k+2)}}N^{\frac{k}{k+2}}.$

Which completes the proof. ∎

The main term in the case $k=2$ was improved by Huxley [8], Huxley and
Trifonov [24] and then Trifonov [20] again, who extended an earlier work by
Swinnerton Dyer. The following result is one of many versions of the theorem
which was proved [1, Theorem 5.8].

######  Theorem 3.6 (Huxley).

Let $f\in C^{3}[N,2N]$ such that there exist $C\geq 1$, $0<\lambda_{2}\leq
C^{-1}$ and $\lambda_{3}>0$ such that for all $x\in[N,2N]$, we have

$\displaystyle C^{-1}\lambda_{2}\leq|f^{\prime\prime}(x)|\leq
C\lambda_{2},\quad C^{-1}\lambda_{3}\leq|f^{\prime\prime\prime}(x)|\leq
C\lambda_{3}\quad\text{and}\quad\lambda_{2}=N\lambda_{3}.$ (35)

Then

$\displaystyle\mathcal{R}(f,N,\delta)\ll$
$\displaystyle\Big{\\{}N^{9/10}\lambda_{2}^{3/10}+N^{4/5}\lambda_{2}^{1/5}+N\lambda_{2}^{3/8}\delta^{1/8}+N^{7/8}\lambda_{2}^{1/4}\delta^{1/8}$
$\displaystyle+N^{6/7}(\lambda_{2}\delta)^{1/7}+N\lambda_{2}^{1/5}\delta^{2/5}\Big{\\}}(\log
N)^{2/5}+N\delta$ $\displaystyle+(\delta\lambda_{2}^{-1})^{1/2}+1.$

The implied constant depends only on $C$.

Finally for the sake of completion, we will show the following slight
improvement obtained due to Trifonov [20] and the explicit statement can also
be found in [1, Theorem 5.9].

######  Theorem 3.7 (Trifonov).

Let $f\in C^{3}[N,2N]$ such that there exist $C\geq 1$, $0<\lambda_{2}\leq 1$
and $\lambda_{3}>0$ such that for all $x\in[N,2N]$, we have

$\displaystyle C^{-1}\lambda_{2}\leq|f^{\prime\prime}(x)|\leq
C\lambda_{2},\quad C^{-1}\lambda_{3}\leq|f^{\prime\prime\prime}(x)|\leq
C\lambda_{3}\quad\text{and}\quad\lambda_{2}=N\lambda_{3}$ (36)

and

$\displaystyle N\lambda_{2}\geq 1\quad\text{and}\quad N\delta^{2}\leq C^{-1}$
(37)

Then for all $\epsilon>0$, we have

$\displaystyle\mathcal{R}(f,N,\delta)\ll$
$\displaystyle\Big{\\{}N^{43/54}\lambda_{2}^{4/27}+N^{4/5}\lambda_{2}^{4/25}+N^{9/10}\delta^{4/15}+N^{12/13}\delta^{4/13}$
$\displaystyle+N^{6/7}\lambda_{2}^{2/7}+N\lambda_{2}+N(\lambda_{2}\delta)^{1/4}\Big{\\}}N^{\epsilon}+\lambda_{2}(N\delta)^{5/2}.$

The implied constant depends only on $C$ and $\epsilon$.

The above two improvements were done on the main term of the inequality we get
in Theorem 2.1. As we can see in the case where $k=3$, the main term in the
Theorem 2.1 is $N\lambda^{1/6}$. The above main terms are all smaller than
that. Which will give a smaller upper bound for the number of integer points
we are trying to estimate when the main terms dominate.

###  3.3 Smooth Curves

Simply by using the first derivative test and letting $\delta\rightarrow 0$,
we get deduce a bound of the number of integer points lying on the arc of the
curve $y=f(x)$ with $N<x\leq 2N$, which is $\ll
N\lambda_{k}^{\frac{2}{k(k+1)}}+1$. Historically, this number was first
investigated by Jarník [25] who proved that a strictly convex arc $y=f(x)$
with length $L$ has at most $\leq\frac{3}{(2\pi)^{1/3}}L^{2/3}+O(L^{1/3})$
integer points on the arc of the curve, this is a nearly best possible result
under the sole condition of convexity.

However, Swinnerton Dyer [26] and Schmidt [27] proved independently that if
$f\in C^{3}[0,N]$ is such that $|f(x)|\leq N$ and
$f^{\prime\prime\prime}(x)\neq 0$ for all $x\in[0,N]$, then the number of
integer points on the arc $y=f(x)$ with $0\leq x\leq N$ is $\ll
N^{3/5+\epsilon}$. This result was then generalized by Bombieri and Pila [28]
as follows [1, Proposition 5.3].

######  Proposition 3.8 (Bombieri-Pila).

Let $N\geq 1$, $k\geq 4$ be integers and set $K=\binom{k+2}{2}$. Let
$\mathcal{I}$ be an interval with length $N$ and $f\in C^{k}(\mathcal{I})$
satisfying $|f^{\prime}(x)|\leq 1$, $f^{\prime\prime}(x)>0$ and such that the
number of solutions of the equation $f^{(K)}(x)=0$ is $\leq m$. Then there
exists a constant $c_{0}=c_{0}(k)>0$ such that the number of integer points on
the arc $y=f(x)$ with $x\in\mathcal{I}$ is

$\displaystyle\leq c_{0}(m+1)N^{1/2+3/(k+3)}$

The ideas of Bombieri and Pila have been extended by Huxley [7] to apply on
the problems involving counting the number of integer points which are very
close to regular curves, an explicit statement can also be found in [1,
Proposition 5.4]. The function is supposed to be $C^{5}$ and along with the
usual non-vanishing conditions of the derivatives on $[N,2N]$, the proof also
requires lower bounds of the following determinants:

$\displaystyle
D_{1}(f;x)=\begin{vmatrix}f^{\prime\prime\prime}(x)&3f^{\prime\prime}(x)\\\
f^{(4)}(x)&4f^{\prime\prime\prime}(x)\\\
\end{vmatrix}\begin{matrix}\vphantom{x}\\\ \vphantom{y}.\end{matrix}$
$\displaystyle
D_{2}(f;x)=\frac{1}{2f^{\prime\prime}(x)}\begin{vmatrix}f^{\prime\prime\prime}(x)&3f^{\prime\prime}(x)&0\\\
f^{(4)}(x)&4f^{\prime\prime\prime}(x)&6f^{\prime\prime}(x)^{2}\\\
f^{(5)}(x)&5f^{(4)}(x)&20f^{\prime\prime}(x)f^{\prime\prime\prime}(x)\\\
\end{vmatrix}\begin{matrix}\vphantom{x}\\\ \vphantom{y}\\\
\vphantom{z}.\end{matrix}$

######  Proposition 3.9 (Huxley).

Assume that $f\in C^{5}[N,2N]$ such that there exist real numbers $C,T\geq 1$
such that

$\displaystyle|f^{(j)}(x)|\leq
C^{j+1}j!\times\frac{T}{N^{j}}\quad(j=1,\cdots,5)$
$\displaystyle|f^{(j)}(x)|\geq\frac{j!}{C^{j+1}}\times\frac{T}{N^{j}}\quad(j=2,3)$
$\displaystyle|D_{1}(f;x)|\geq
144C^{-8}\times\frac{T^{2}}{N^{6}},\quad|D_{2}(f;x)|\geq
4320C^{-12}\times\frac{T^{3}}{N^{9}}.$

Let $0<\delta<\frac{1}{4}$ be a real number. Then we have

$\displaystyle\mathcal{R}(f,N,\delta)\ll(NT)^{4/15}+N(\delta^{11}T^{9})^{1/75}.$

The implied constant depends only on $C$.

The main term of this result is very good, since in the second derivative
test, the main term only yields $(NT)^{1/3}$ and Theorem 3.6 can only give
$(NT)^{3/10}$. A smaller main term will give a better upper bound for the
number of integer points when the main term dominates. On the other hand, the
secondary term of this result is too large, and thus useless in many
applications. But this may be improved subject to some additional non-
vanishing conditions of certain quite complicated determinants [1, p. 403].

##  4 Applications

###  4.1 Diophantine Inequality

One interesting application arises naturally from the methods we have been
discussing is to estimate the number of solutions of a given Diophantine
inequality. Consider the following Diophantine inequality

$\displaystyle|\alpha n^{2}+\beta m^{2}-z|\leq\delta.$

where $\alpha,\beta,z\in\mathbb{N}$ and $\delta$ small. The goal is to
estimate the number of non-trivial solutions as $(n,m)$ range over a closed
interval, The inequality can be then reformulated as a problem of finding
integer points near the planar curve $\mathcal{C}\subset\mathbb{R}^{2}$ given
by

$\displaystyle\alpha n^{2}+\beta m^{2}-z=0.$

Similar ideas have also been discussed by Damaris Schindler [17] where
Diophantine inequalities for generic ternary diagonal forms are in concern.
Fix some degree $k\geq 2$ and let $\alpha_{2},\alpha_{3}\in\mathbb{R}_{>0}$,
Let $\theta>0$ and consider the inequality

$\displaystyle|x_{1}^{k}-\alpha_{2}x_{2}^{k}-\alpha_{3}x_{3}^{k}|<\theta.$
(38)

The goal here is to understand when this inequality has a non-trivial solution
if the variables $x_{i}$ are allowed to range over a box of size $P$. With
some techniques rather complicated, we would eventually be able to reformulate
the inequality (38) as a problem of finding rational points near the planar
curve $\mathcal{C}\in\mathbb{R}^{2}$ given by
$1-\alpha_{2}y_{2}^{k}-\alpha_{3}y_{3}^{k}=0$. Finding solutions to (38) would
be translated into studying a counting function of the type with
$\delta=\frac{\theta}{P^{k-1}}$

$\displaystyle
N_{\mathcal{C}}(P,\delta)=\sharp\Big{\\{}\frac{p}{q}\in\mathbb{Q}^{2}:1\leq
q\leq
P,\operatorname{dist}\Big{(}\frac{p}{q},\mathcal{C}\Big{)}\ll\frac{\delta}{q}\Big{\\}}.$

###  4.2 The Squarefree Number Problem

Huxley and Sargos’s Theorem also can be applied on the squarefree number
problem. Without using the theorem, we could still get the basic result as
follows [1, Lemma 5.3].

######  Lemma 4.1.

Let $x,y$ satisfy $16\leq y<\frac{1}{4}\sqrt{x}$ and $2\sqrt{y}\leq A<B\leq
2\sqrt{x}$. Then

$\displaystyle\sum_{x<n\leq
x+y}\mu_{2}(n)=\frac{y}{\zeta(2)}+O\Big{(}(R_{1}+R_{2})\log x+A\Big{)},$

where $R_{1}=R_{1}(A,B)$ and $R_{2}=R_{2}(B)$ are defined by

$\displaystyle R_{1}=\underset{A<N\leq
B}{\max}\mathcal{R}\Big{(}\frac{x}{n^{2}},N,\frac{y}{N^{2}}\Big{)}\quad\text{and}\quad
R_{2}=\underset{N\leq
2x/B^{2}}{\max}\mathcal{R}\Big{(}\sqrt{\frac{x}{n}},N,\frac{y}{\sqrt{Nx}}\Big{)}.$

Now suppose first that $y\leq x^{4/9}$, if we use the above lemma with
$A=2x^{2/9}$ and $B=x^{1/3}$, by the restriction stated in the lemma, we have
$A>2y^{1/2}$ and hence

$\displaystyle\sum_{x<n\leq
x+y}\mu_{2}(n)=\frac{y}{\zeta(2)}+O\Big{(}R_{1}(2x^{2/9},x^{1/3})\log
x+R_{2}(x^{1/3})\log x+x^{2/9}\Big{)}.$

Notice that. The restriction on the second derivative test i.e. Theorem 2.7 is
satisfied by the function in its respective range of summation. So using
Theorem 2.7 we can get

$\displaystyle R_{2}\Big{(}x^{1/3}\Big{)}\ll\underset{N\leq
2x^{1/3}}{\max}\Big{(}(Nx)^{1/6}+y^{1/2}(N^{3}x^{-1})^{1/4}\Big{)}\ll
x^{2/9}+yx^{-2/9}.$

Furthermore, if we use the Theorem of Huxley and Sargos with $k=3$ for
$R_{1}(2x^{2/9},x^{1/3})$, we will have

$\displaystyle R_{1}(2x^{2/9,x^{1/3}})$
$\displaystyle\ll\underset{2x^{2/9}<N\leq
x^{1/3}}{\max}\Big{\\{}(Nx)^{1/6}+(Ny)^{1/3}+N(yx^{-1})^{1/3}\Big{\\}}$
$\displaystyle\ll x^{2/9}+x^{1/9}y^{1/3}.$

Thus, if $y\leq x^{1/3}$, we will have

$\displaystyle\sum_{x<n\leq
x+y}\mu_{2}(n)=\frac{y}{\zeta(2)}+O\Big{(}x^{2/9}\log x\Big{)}.$

Which means that there exists a constant $c_{0}>0$ such that if
$c_{0}x^{2/9}\log x\leq y<\frac{1}{4}\sqrt{x}$, the interval $[x,x+y]$
contains a squarefree number is since by the condition we already have $y\geq
16$, to guarantee that the RHS non-zero, we only need to make sure
$\frac{y}{\zeta(2)}$ is bigger than the approximated term $O(x^{2/9}\log x)$
for some such $c_{0}$.

## Acknowledgements

This manuscript is derived from my third-year bachelor’s dissertation at the
University of Warwick. I would like to express my sincere gratitude to Dr.
Simon L. Rydin Myerson for his invaluable advice and supervision throughout
the development of this essay. Additionally, I acknowledge the exceptional
work of Bordellès; without his beautifully translated and meticulously
organized textbook, Arithmetic Tales, this essay would not have been possible.

## References

  * Bordellès [2006] O Bordellès.  _Arithmetic Tales_.  Springer, 2006.
  * Branton and Sargos [1994] M Branton and P Sargos.  Points entiers au voisinage d’une courbure plane à très faible courbure.  _Bulletin des sciences mathématiques (Paris. 1885)_ , 118(1):15–28, 1994.
  * Filaseta and Trifonov [1992] Michael Filaseta and Ognian Trifonov.  On gaps between squarefree numbers ii.  _Journal of the London Mathematical Society_ , 2(2):215–221, 1992.
  * Filaseta and Trifonov [1996] Michael Filaseta and Ognian Trifonov.  The distribution of fractional parts with applications to gap results in number theory.  _Proceedings of the London Mathematical Society_ , 3(2):241–278, 1996.
  * Gorny [1939] Ayzyk Gorny.  Contribution à l’étude des fonctions dérivables d’une variable réelle.  _Acta Mathematica_ , 71(1):317–358, 1939.
  * Huxley and Sargos [2006] M.N Huxley and P Sargos.  Points entires au voisinage d’une courbe plane de classe $\mathcal{C}^{n}$, ii.  _Functiones et Approximatio Commentarii Mathematici_ , 35:91–115, 2006.
  * Huxley [2007] M.N Huxley.  The integer points in a plane curve.  _Functiones et Approximatio Commentarii Mathematici_ , 37(1):213–231, 2007.
  * Huxley [1996a] M.N Huxley.  _Area, lattice points, and exponential sums_ , volume 13.  Clarendon Press, 1996a.
  * Huxley [1996b] M.N Huxley.  The integer points close to a curve ii.  _Progress in Mathematics-Boston-_ , 139:487–516, 1996b.
  * Huxley [1999] M.N Huxley.  The integer points close to a curve iii.  _In: Gyory et al. (eds.) Number Theory in Progress_ , 2:911–940, 1999.
  * Huxley and Sargos [1995] M.N Huxley and P Sargos.  Points entiers au voisinage d’une courbe plane de classe $\mathcal{C}^{n}$.  _Acta Arithmetica_ , 69(4):359–366, 1995.
  * Konyagin [1999] S.V Konyagin.  Estimates of the least prime factor of a binomial coefficient.  _Mathematika_ , 46(1):41–55, 1999.
  * Lagrange [1882] Joseph Louis Lagrange.  _Oeuvres de Lagrange_ , volume 13.  Gauthier-Villars, 1882.
  * Letendre [2019] Patrick Letendre.  The number of integer points close to a polynomial.  _arXiv preprint arXiv:1901.10004_ , 2019.
  * Mandelbrojt [1952] Szolem Mandelbrojt.  Séries adhérentes régularisation des suites applications: leçons professées au Collège de France et au Rice Institute.  _Journal_ , 1952.
  * Matomäki and Teräväinen [2023] Kaisa Matomäki and Joni Teräväinen.  On the Möbius function in all short intervals.  _Journal of the European Mathematical Society (EMS Publishing)_ , 25(4), 2023.
  * Schindler [2020] Damaris Schindler.  Diophantine inequalities for generic ternary diagonal forms.  _International Mathematics Research Notices_ , 2020(11):3396–3416, 2020.
  * Shiu [1980] P Shiu.  On the number of square-full integers between successive squares.  _Mathematika_ , 27(2):171–178, 1980.
  * Srinivasan [1962] B.R Srinivasan.  On van der Corput’s and Nieland’s results on the Dirichlet’s divisor problem and the circle problem.  In _Proc Natl Inst Sci India, Part A_ , volume 28, pages 732–742, 1962.
  * Trifonov [2002] Ognian Trifonov.  Lattice points close to a smooth curve and squarefull numbers in short intervals.  _Journal of the London Mathematical Society_ , 65(2):303–319, 2002.
  * Landau [1913] E Landau.  Ungleichungen für zweimal differenzierbare Funktionen.  _Proc. London Math. Soc_ , 13:43–49, 1913.
  * A Kolmogorov [1949] A Kolmogorov.  On Inequalities Between the Upper Bounds of the Successive Derivatives of an Arbitrary Function on an Infinite Interval.  _Amer. Math. Soc. Transl._ , 1-2:233–243, 1949.
  * L Neder [1930] L Neder.  Abschätzungen für die Ableitungen einer reellen Funktion eines reellen Arguments.  _Mathematische Zeitschrift_ , 31:356–365, 1930.
  * huxley [1996] M.N Huxley and Ognian Trifonov.  The square-full numbers in an interval.  _Mathematical Proceedings of the Cambridge Philosophical Society_ , 199(2):201–208,  Cambridge University Press, 1996.
  * jarnik [1926] V.V Jarník.  Über die Gitterpunkte auf konvexen Kurven.  _Mathematische Zeitschrift_ , 24:500-518, 1926.
  * Swinnerton [1974] H.P.F Swinnerton-Dyer.  The number of lattice points on a convex curve.  _Number Theory_ , 6:128–135, 1974.
  * Schmidt [1985] W.M Schmidt.  Integer Points on Curves and Surfaces.  _Number Theory_ , 6:128–135, 1974.
  * bombieri [1989] E Bombieri and J Pila.  The number of integral points on arcs and ovals. 1989.