Annales de l’institut Fourier (AIF)

Brandt, D.

Hausmann, Jean-Claude

Théorie de jauge et symétries des fibrés

Berend, Daniel

Harmse, J. E.

Gaps between consecutive divisors of factorials

Haran, Shai

Quantizations and symbolic calculus over the $p$-adic numbers

Schwartz, Laurent

Les travaux de Bernard Malgrange (première partie)

Kawazumi, Nariya

On the complex analytic Gel'fand-Fuks cohomology of open Riemann surfaces

Hörmander, Lars

Remarks on Holmgren's uniqueness theorem

Sabbah, Claude

Équations différentielles à points singuliers irréguliers en dimension 2

Skriganov, Maxim

ANNALES DE L’INSTITUT FOURIER
MAXIM SKRIGANOV
On integer points in polygons
Annales de l’institut Fourier, tome 43, no 2 (1993), p. 313-323
<http://www.numdam.org/item?id=AIF_1993__43_2_313_0>
© Annales de l’institut Fourier, 1993, tous droits réservés.
L’accès aux archives de la revue « Annales de l’institut Fourier »
(http://annalif.ujf-grenoble.fr/) implique l’accord avec les conditions gé-
nérales d’utilisation (http://www.numdam.org/conditions). Toute utilisa-
tion commerciale ou impression systématique est constitutive d’une in-
fraction pénale. Toute copie ou impression de ce fichier doit conte-
nir la présente mention de copyright.
Article numérisé dans le cadre du programme
Numérisation de documents anciens mathématiques
http://www.numdam.org/
Ann. Inst. Fourier, Grenoble
43, 2 (1993), 313-323
ON INTEGER POINTS IN POLYGONS
by Maxim SKRIGANOV
1. The results.
Let P C R2 be a compact region, Z2 C H2 be the integer point lattice
and
n(P) = card P H Z2
be the number of integer points lying in P. We set by definition
n(P) =areaP+r(P).
Let P + X be the translation of P by a vector X € IR2 and ^P be the
dilatation of P by a factor t > 0. We set
fi(P)=max|r(P+X)|.
./c eH
The classical lattice point problem deals with behavior of the error
R(tP) as t —> oo. In the present paper we shall study this problem under
the assumption that P is a polygon with finitely many sides. At first sight,
the problem under this assumption seems trivial. Indeed, the trivial bound
R(tP) <^ t is, obviously, best possible here if at least one of the normals
to the sides of P is proportional to a vector of Z2. However, in the present
paper we wish to examine the opposite situation.
Key words : Lattice point problem - Diophantine approximation.
A.M.S. Classification : 11K38 - 11H06 - 11P21.
314 MAXIM SKRIGANOV
We shall use the following definitions. The polygon P is said to be
irrational if the normals to its sides are proportional to the vectors with
coordinates (1, o^-), j = 1, . . . , h (h is the number of sides of P) and all of
the slopes a i , . . . , o^ are irrational numbers. If all of the slopes ai , . . . , OH
are irrational algebraic numbers the polygon P is said to be algebraic.
We shall use the notation PA for the polygon with a given set of slopes
A = (ai,.. . ,a/J.
It turns out that for irrational polygons the error term can be loga-
rithmically small. Thus the asymptotic behavior of the error is extremely
unstable with respect to small variations of the polygon. The phenomenon
of such amazingly instability as well as the possibility of logarithmically
small errors in the lattice point problem were first studied in the author's
papers [Sl], [S2].(*)
We wish to state one of our results from [S2]. Let a=[ao; ai, 03,03,- • •],
Oj; € Z, be the continued fraction expansion of an irrational a with partial
quotients dj ^ 1, j > 1 (cf. [L] and [P] for all details concerning continued
fractions). We introduce the following arithmetic function
<^(P) = ̂  Oj
1<J<P
for real p > 1.
THEOREM 1 (cf. [S2], Th. 6.1). — For any irrational polygon PA
one has the bound
h
R(tPA)^Y,qa^nt).
j=i
Using this theorem one can easily give a lot of examples of polygons
with extremely small errors. For this purpose it is sufficient to choose
natural partial quotients as we like, since the corresponding continued
fraction always converges. We mention here only two examples.
Example 1. — Let the partial quotients of all of the slopes A =
(ai,.. . ,a/J be bounded by a constant, say, all of the slopes A =
(ai,.. . ,a/i) be quadratic irrationalities. Then for the corresponding ir-
rational polygon PA one has the bound
R(tPA) < in t.
(*) In connection with this, the following works should be also mentioned : the well
known memoir [HL] by Hardy and Littlewood which is rather closed to the matter of
our study and the paper [R2] by Randol where a logarithmic bound was given for the
mean value of the error over all rotations of the polygon.
ON INTEGER POINTS IN POLYGONS 315
Example 2. — The famous Euler's formula (cf. [L], Chap. 5, Sect. 1
and [P], §64) gives the following continued fraction expansion
1 e2^ - 1
tanh ̂  = ̂  ^ == [0; fc, 3k, 5fc, 7A;, 9A;,. • . ]
where e is the base of natural logarithms and k = 1,2, - • •. Now, let all of
the slopes A = (o;i,... ,o^) be transcendental numbers of the indicated
form. Then one has the bound
R(tPA) < ^n2 t.
It is well known that for almost all a € R1 the arithmetic function
qa(p) satisfies the estimate Qa(p) < p<p(£n p) as p —> oo, where ^p(t}, t > 0,
is an arbitrary nondecreasing positive function such that the series
oo
\^-L
^ ̂ ')
converges (cf. [Kh], p. 123). Taking this statement into account we derive
from Theorem 1 the following "metrical" result.
THEOREM 2. — Let the number h of sides of polygons PA be fixed.
Then for almost all slopes A = (a i , . . . , a/J G IR'1 one has the bound
R(tPA) < in t • ip(2£n Hn t),
where the function (^(') is indicated above.
In particular (if we take (p(t) = ^1+£), for almost all slopes A =
(ai , . . . , Oh) C IR^ one has the bound
R(tPA) < in t • (in in t)1^
with arbitrarily small e > 0.
Theorem 2 shows that the appearance of logarithmically small errors
on the set of all polygons is quite typical.
Continued fractions that had been used in Theorem 1 are not always
convenient, say, for general algebraic polygons, since, nothing is known
about the growth properties of the partial quotients for algebraic irrational-
ities of degree > 2. In the present paper we wish to evaluate the error for
a polygon PA directly in the terms of diophantine properties of its slopes
A = (Q:i , . . . ,Q^).
To state our results we recall some definitions (cf. [KN], Chap. 2,
Sect. 3). For a real number t, let (t) denote the distance from t to the
nearest integer, namely,
{t) = min \t - n\ = min[{^}, 1 - {t}},
n6Z
316 MAXIM SKRIGANOV
where {t} is the fractional part of t. Let ^(^), t > 0, be a nondecreasing
positive function. The irrational a is said to be of type < ^ if the inequality
q{aq} > w
holds for all positive integers q. This definition was given by Lang (cf. [L],
Chap. 2, Sect. 1).
The irrational polygon PA is said to be of type < ^ if all of its slopes
A = (ai , . . . , a/i) are of type < ^.
THEOREM 3. — For any irrational polygon PA of type < ̂  one
has the bound
R(tPA)^tp-e^^(p)£n2 p,
where 0 < 0 < 1 is arbitrarily fixed and p >_ 1 is an arbitrary parameter;
moreover the constant implied by <^ is independent of p.
The proof of this theorem will be given in the next section. Note
that the bound of Theorem 3 can be slightly improved, namely, the factor
in2 p can be replaced by in p. However, this improvement requires more
complicated techniques and is not given here.
The famous theorem of Thue-Siegel-Roth says that every irrational
algebraic number a is of type < ^, where ^e(t) = Get6 with arbitrarily
small e > 0 and a suitable c^ = Cg(a) > 0 (cf. [Sch]). Taking this statement
into account and choosing p° = t we derive from Theorem 3 the following
result.
THEOREM 4. — For any algebraic polygon P one has the bound
R(tP) < ̂
with arbitrarily small e > 0.
Note that the upper bounds given in Theorems 1-4 are rather sharp.
For example, one can prove that for every parallelogram II the following
omega-theorem
R(tH) = ^{£n t)
holds.
Perhaps, it is worth to mention also the following simple corollary of
Theorem 3.
ON INTEGER POINTS IN POLYGONS 317
THEOREM 5. — For any irrational polygon P one has the bound
R(tP) = o(t).
Indeed, any irrational polygon P is of type < ^p, with certain ^p(t).
Choosing the parameter p = p(t) in Theorem 3 such that p —> oo as t —> oo,
but at the same time ^p(p)£n2 p = o(t), we complete the proof. The bound
of Theorem 5 cannot be improved on the set of all irrational polygons
(cf. [HL]).
The reader can ask the question : are there regions besides polygons
with logarithmically small errors terms in the lattice point problem? We
conjecture that the answer is negative and the set of polygons is the only
class of regions with logarithmically small errors. I checked this conjecture
only for regions bounded by finitely many pieces of analytic curves. For
general regions this problem requires, probably, more deep analysis of the
Fourier transform of the characteristic functions of planar sets in the spirit
of works by Randol [R2] and Colin de Verdiere [CV]. The author hopes to
touch this task on a suitable occasion.
The foregoing results give rather complete picture of the behavior of
the errors terms for polygons in the plane. These results form a part of
much more complete theory of anomaly small errors in the lattice point
problem that can be developed in arbitrary dimensions and that will be
given in consequent author's papers (see [S3] and [S4]).
It gives me pleasure to express my sincere appreciation to professor
Colin de Verdiere for his hospitality in Institut Fourier where this paper
had been written and given as a lecture.
2. Proof of Theorem 3.
In proving we shall need the following ingredients.
i. General bounds for the number of integer points in com-
pact regions (cf. [CV], [Rl], here we follow [S2], Sect. 3).
We recall the definition : given a compact region P and a number T,
0 < T < 1; we say that the compact regions P^ form a r- approximation of
P if P^T C P C P^ and the points of the boundaries QP^ are at a distance
> T from the boundary OP.
318 MAXIM SKRIGANOV
Let \(P,X), X C IR2, denote the characteristic function of a region
P and let
XCP, Y) = ( [ exp(27rzy . X)dX , z = ̂ ^1,
v
be the Fourier transform of \f(P,X\ We use the notation Y ' X for the
inner product of the vectors Y and X, and the notation |X| for the norm.
Fix a non-negative function G(X), X e R2, of the class C°° with the
support inside the disk \X\ < 1, and assume that f G(X)dX = 1. We set
Gr{X) = r^G^^X), 0 < r < 1. Taking into account that the Fourier
transform Gr(Y) = G(rY) we obtain the estimates
(2.1) \G^Y)\ < CaW)^ , \G^Y)\ < 1
with any B > 1 and some Cp > 0.
LEMMA 1. — Let a compact region P cH2 be given. Then for any
r-approximation P^ ofP one has the bound for the error R(P)
R(P) < areaP^ -areaP,-+ ^/ (^(P^^l + |x(P.-,7)l)lG(r7)|,
7CZ2
where the prime over ̂  means that the summand with 7 = 0 is omitted.
Proof of Lemma 1 is identical with the proof of Lemma 3.3 in [S2].
ii. The Fourier transform of the characteristic function of a
polygon (here we follow [S4]).
Let P be a convex polygon with counterclockwise oriented boundary
9P=^S^
j=i
where Sj = [A^Aj+i] are oriented sides joining the vertices Aj and A^+i;
moreover A^i = Ai.
Let Nj be normals to Sj and Lj be the unit vectors in the direction
ofSj.
LEMMA 2. — In the above notation one has the following estimates
for the Fourier transform of the characteristic function \{P, Y) of the
polygon P
\W Y) | < ̂ ^ perimeter P,
|yfp y)| < 1 V l^^'lIW^I^ 27r2|y|22^|y-Zj-i i j^ i j i
ON INTEGER POINTS IN POLYGONS 319
Proof. — The statements of Lemma 2 are direct corollaries of the
following explicit formulas for ^(P, V). Let A be the Laplacian in variables
r\
X e R2 and - _ _ be the normal derivative at a given point X e 9P. One
has
-^Y^P.Y) = ( ( Aexp(27nr • X)dX.
p
Integration by parts gives
-^\Y\2^ Y)= [ —— exp{2mY . X)dXJQP ol\
h n r\
^E/ Q^exp(2mY-X)dX
j==l v Sj
h
== V 27rzy • Nj \ exp(27rzy • X)dX.
j=i t/^
Now, first estimate of lemma follows from this formula at once. For
the second estimate we have to calculate in this formula the integrals over
the segments 6j. As a result
^ri^P, Y) = ̂  y-^ [exp(27rzy . A,+i) - exp(27rzy • A,)1.
j=i Y ' Lj L j
This completes the proof.
iii. Some results from diophantine approximations (cf. [HL],
[L], [Sch], here we follow [KN] and [L]).
Let a be an irrational number. We introduce the arithmetic function
UP)- E -73-̂wp^
for real p > 1.
LEMMA 3. — Let a be of type < ̂ . Then one has the estimate
UP) « ̂ Wn2 p.
For the proof of Lemma 3 we refer to [KN], Chap. 3, Sect. 3,
Lemma 3.3. Note that the bounds for such sums were first given in [HL] in
terms of continued fractions and in [L], Chap. 3, Sect. 2, in terms of the
type of a.
320 MAXIM SKRIGANOV
We introduce another arithmetic function
_ / ,\ v^ 1 v-^ 1•w- £ - Eo'.
K^P^l^^'^l
for irrational a and real p > 1.
LEMMA 4. — Let a be of type < ̂ . Then one has the estimate
^a(p) < ̂ (2p)fc2 p.
Proof. — Let us estimate the inner sum in the definition of cr^(p).
If the number aq is outside of the interval [1/2; p + 1/2], then we have the
bound
E ]^< E T^«^p<—+^p.
l<P<<o '" " l<t<p 2 ' " V0^/
Let aq be inside the interval [1/2; p + 1/2] and let aq = {aq) + po
where po € Z H [1, p]. then we have the bound
E<,\p^rW)+^\p^^W}+\E^<<^+£np•PT^PO ~
Using these bounds we find that
aa^ « E .7—}+ ̂ p E ^« ̂ (^) + ̂ n2 p-
i<g<p x '/ i^9<p '
The reference to Lemma 3 completes the proof.
Now we are in position to prove Theorem 3. Let PA be an irrational
polygon of type < ^. Without loss of generality we can assume that PA
is convex. Really, extending the sides of a given polygon PA we obtain a
fragmentation of PA into a collection of disjoint convex polygons with the
same set A of slopes, and it remains to prove Theorem 3 for each of these
fragments.
The convex polygon iP^ can be given by the inequalities
t P A = { X e R 2 : X ' N , < b ^ .7= I, . . . , / ,}
where 61, . . . , & / , are some constant independent of t. We choose the follow-
ing r-approximations for tP^
P^ (t) = {x e n2: x • N, < b,t ± T, j = i , . . . . . /Q,
ON INTEGER POINTS IN POLYGONS 321
0 < r < l , ^ ^ l ; moreover
areaP^t) = t2 area? =L rt perimeter P + 0(r2),
perimeter P,̂ ) = t perimeter P + 0(r).
Note that the normals T V i , . . . , Nh to the sides and the unit vectors
L i , . . . , Lh in the directions of the sides are the same for all polygons iP^i
P^~ (t) and they are of the form
Nj =Cj(l,aj),Lj =cj(-aj,l),c]= ——^j=l^.^h.
-a,
From Lemma 1 we derive the following bound
R(tP) ̂  2^ perimeter P+0(T2)+ ^/ (\^{P^(t)^)\
7GZ2
(2.2) x ^
+|x(P.-(Ml)lG(T7)|.
Further we shall assume that r = p~°\ where p > 1 is large parameter and
D_1
0 = ———, moreover B is taken from (2.1). Let Kp C H2 be the square
-o+l
Kp = {X = {x,y) € R2 : x\ < p, \y\ < p}
and Qp = H2 \ Kp be its complement. In the bound (2.2) we divide the
sum over 7 € Z2 into a sum over 7 € Z2 D Qp and a sum over 7 e Z2 H K p .
In the first sum over 7 € Z2 H Qp we replace ^(P^^V)! and |G(ry)|
by first bounds from Lemma 2 and from the formula (2.1), respectively.
In the second sum over 7 G Z2 D Kp we use similarly second bounds from
Lemma 2 and from the formula (2.1). As a result we obtain the inequality
(2.3) R(tP) < 2rt perimeter P + 0(1) + Pi + V^
here
,|-B-1Pi = CB (perimeter P^r-5 ^ H-
7r 7CZ2nQp
-t /^' I Tt T 1 ^•n y^ / 1 ^\7-Nj 1 ̂
^ = 2 . 27r^^|7-T7=2^^^(^
^^J^nK^ 1 " i=l ' ' • 7 1 i=l——— Z»7 / ——— / ' -L/1 ^i/l ———7(=z2n p j i 1 ' • j i
where we introduced the arithmetic function
(9 A} H (n\- V^7 1 lg+^1( ' ^"-i.î ?^^^-
Recall that the prime over the sums means that the summand with
7 = (^P) = (0)0) ls omitted.
322 MAXIM SKRIGANOV
The bound for Pi is very simple, indeed,
PI ^tr-13?1-13 =tp~°,
since
^ H-5-1^1-5.
7€Z2nQp
Grouping in the sum (2.4) separately terms with q = 0, p 7^ 0 with
g 7^ 0, p = 0 and with q ̂  0, p 7^ 0, and using the inequality
1<? + o^Pl . 1^ , i > 1
T-^^^M
we can evaluate the sum (2.4) as follows
n.w^w E ̂  E \
1<P<P ' '1^(?<P -
+(2+H)l<E<p^^::^+hTa,1)
< ̂ n p + cr^(p) + (7-a(p) < ̂ (2p)^n2 p,
where, at the last step, Lemma 4 had been used; note also that the numbers
a and —a are of the same type. Therefore
?2 < ̂ (2p)£n2 p.
Substituting the above bounds for 'DI and V'z into the inequality (2.3)
we complete the proof of Theorem 3.
BIBLIOGRAPHY
[CV] Y. COLIN DE VERDIERE, Nombre de points entiers dans une famille homothetique
de domaines de IR71, Ann. Sci. Ecole Norm. Sup., 4e serie, 10 (1977), 559-576.
[HL] G. H. HARDY, J.E. LITTLEWOOD, Some problems of Diophantine approximation :
the lattice points of a right-angled triangle, part I, Proc. London Math. Soc.
(2), 20 (1922), 15-36; part II, Abh. Math. Sem. Hamburg, 1 (1922), 212-249.
[Kh] A. KHINCHIN, Einige Satze liber Kettenbriiche, mit Anwendungen auf die Theorie
der Diophantischen Approximationen, Math. Ann., 92 (1924), 115-125.
[KN] I. KUIPERS, H. NIEDERREITER, Uniform distribution of sequences, Wiley, New-
York-London, 1974.
[L] S. LANG, Introduction to diophantine approximations, Addison-Wesley, Mass.,
1966.
[P] 0. PERRON, Die Lehre von den Kettenbriichen, 3 Aufl., Teubner, Stuttgart, 1954.
ON INTEGER POINTS IN POLYGONS 323
[Rl] B. RANDOL, A lattice point problem I, Trans. A.M.S., 121 (1966), 257-268; II,
Trans. A.M.S., 125 (1966), 101-113.
[R2] B. RANDOL, On the Fourier transform of the indicator function of a planar set,
Trans. A.M.S., 139 (1969), 271-278.
[Sch] W.M. SCHMIDT, Diophantine approximation, Lecture Notes in Math., 785,
Springer-Ver lag, Berlin, New York, 1980.
[Sl] M.M. SKRIGANOV, On lattices in algebraic number fields, Dokl. Akad. Nauk SSSR,
306 (1989), 553-555, Soviet Math. Dokl., 39 (1989), 538-540.
[S2] M.M. SKRIGANOV, Lattices in algebraic number fields and uniform distributions
modulo 1, LOMI Preprint 12-88, Leningrad, (1988), Algebra and analysis, 1,
N2 (1989), 207-228, Leningrad Math. J., 1, N2 (1990), 535-558.
[S3] M.M. SKRIGANOV, Construction of uniform distributions in terms of geometry of
numbers, Prepublication de ITnstitut Fourier, n° 200, Grenoble, 1992.
[S4] M.M. SKRIGANOV, Anomaly small errors in the lattice point problem, (in prepa-
ration).
Manuscrit recu Ie 7 mai 1992.
Maxim SKRIGANOV,
Steklov Inst. of Math.
SPB-Branch
Fontanka 27
191011 St. Petersburg (Russia).
Email : skrig@lomi.spb.su


Not a member yet

Théorie de jauge et symétries des fibrés

Gaps between consecutive divisors of factorials

Quantizations and symbolic calculus over the $p$ -adic numbers

Les travaux de Bernard Malgrange (première partie)

On the complex analytic Gel'fand-Fuks cohomology of open Riemann surfaces

Remarks on Holmgren's uniqueness theorem

Équations différentielles à points singuliers irréguliers en dimension 2

On integer points in polygons

Exemples d'applications holomorphes d'indice un

Constructive invariant theory for tori

3,503

3,732