area e punti interi - Dipartimento di Matematica e Applicazioni

AREA E PUNTI INTERI
Leonardo Colzani
Dipartimento di Matematica, Universita degli Studi di Milano-Bicocca
Un punto intero nel piano cartesiano e un punto a coordinate
intere. Ogni punto intero e centro di un quadrato di area uno e questi quadrati
piastrellano il piano. Per stimare l'area di una regione piana, invece dei
quadrati, si possono contare i punti a coordinate intere contenuti nella regione
ed in questo modo si ottiene una approssimazione dell'area. Per esempio, un
cerchio con centro intero e raggio 10 contiene 317 punti interi, mentre l'area
e approssimativamente 314. L'errore relativo (317-314)/314 e dell'ordine del
1%.
SUNTO:
IL PROBLEMA DEL CERCHIO DI GAUSS
Parecchi problemi in teoria dei numeri conducono alla stima del numero
di punti interi contenuti in una regione del piano o dello spazio. Consideriamo per esempio un classico problema studiato da Fermat, Eulero, Lagrange,
Gauss, Jacobi, ed altri. E possibile decomporre un dato numero intero nella
somma di due quadrati? Un certo numero puo non essere rappresentabile
come somma di due quadrati mentre un altro puo avere parecchie rappresentazioni. Per esempio, 25 = 0 + 5 = 3 + 4 e 26 = 1 + 5 , ma 27 non
e somma di due quadrati, 83 e 84 non sono somme di due quadrati, mentre
85 = 2 + 9 = 6 + 7 . Denotiamo con r(n) il numero delle decomposizioni
di n nella somma di due quadrati,
2
2
2
2
2
2
2
2
2
2
r(n) = (x; y) 2 Z Z : x2 + y2 = n :
Si puo mostrare che un numero e somma di quadrati se e solo se nella
sua scomposizione in fattori primi ogni primo della forma 4n + 3 compare un
numero pari di volte. Piu precisamente r(n) = 4 (d (n) d (n)), dove d (n)
e d (n) sono i numeri dei divisori di n della forma 4n + 1 e 4n + 3. Questa
funzione aritmetica dipende quindi dalla scomposizione in fattori primi ed e
piuttosto irregolare, ma l'irregolarita viene mitigata considerandone il valor
1
3
1
3
1
medio. La somma r(1) + r(2) + ::: + r(n) e il numero di soluzioni intere della
disequazione x + y n ed e uguale al numero
p di punti a coordinate intere in
un cerchio con centro nell'origine e raggio n. Il numero di punti interi in un
cerchio e approssimativamente uguale all'area del cerchio, quindi un numero
ha in media rappresentazioni come somma di quadrati. Dalla formula
r(n) = 4 (d (n) d (n)), denotando con [x] il piu grande intero minore o
uguale a x, si ricava
2
1
2
3
X
k n
r(k) = 1 + 4 ([n=1] [n=3] + [n=5] [n=7] + :::) :
0
Al limite per n ! +1 si riconosce la serie di Leibniz 1 1=3 + 1=5
1=7 + ::: = =4.
E anche possibile calcolare esplicitamente r(1) + r(2) + ::: + r(n) con un
semplice metodo dovuto a Gauss. Dividiamo
i punti a coordinate intere in
p
un cerchio con centro nell'origine e raggio n in quattro sottoinsiemi: A =
f l'origine g, B = pf i punti sugli assi, esclusa l'origine g, C = f i punti nel
quadrato di lato 2 n=2 iscritto nel cerchio, esclusi gli assi g, D = f i punti
restanti g. Denotando con jE j il numero di punti in un insieme E , si ha
X
r(k) = jAj + jB j + jC j + jDj
k n h
p
p
0
= 1 + 4 [ n] + 4
i2
n=2 + 8
X
pn= <kpn
p
n k2 :
2
Malgrado l'aspetto, questa formula non e di dicile uso perche non utilizza che la parte intera delle radici quadrate. Per esempio, se n = 100,
jAj = 1, jB j = 40, jC j = 196, jDj = 80,
n=
r(k) =
X
k n
(10)
317
2
(100)
31417
2
(1000)
3141549
2
(10000)
314159053
2
0
In questo modo si ottengono gia buone stime di e tra l'altro il metodo
utilizzato e assolutamente elementare. Quello che non e elementare e stimare
l'errore,
2
X
r(k)
0kn
X
r(k)
0
k
n
X
r(k)
0kn
X
r (k )
0 k n
n
n
n
n =
2 p n
(Gauss 1834-1837),
cn =
(Sierpinski 1906),
1 3
cn =
1 3
"
(van der Corput 1923),
(n = ) (Hardy, Landau 1915).
1 4
La stima dell'errore di Gauss ha una dimostrazione molto semplice. Associando ad ogni punto intero il quadrato con centro nel punto e lati di
lunghezza uno paralleli agli assi. r(1) + r(2) + ::: + r(n) risulta essere uguale
all'area di tutti i quadrati con pcentripin x + y n. Questi quadrati contengonopil cerchio
x +y n
2=2 e sono contenuti in x + y pn 2=2 . Quindi
2
2
2
2
2
2
2
2
p p
n
2=2
2
X
n <
0
k n
p p
r(k) n < n + 2=2
2
n:
Le altre stime sono piu dicili. In particolare, la stima di Hardy e Landau
e un caso particolare del seguente teorema, che secondo Erdos sopravvivra
agli scopritori per qualche centinaio di anni.
TEOREMA (Erd
os-Fuchs 1956):
1 una funzione aritmetica a valori interi con f (0) f (1) Sia ff (n)g+n=0
f (2) ::: e N (x) il numero di soluzioni di f (m)+ f (n) x. Se per una certa
costante si ha N (x) = x + R(x), allora lim supx!+1 x 1=4 jR(x)j > 0.
2
XNel problema del cerchio, f (n) = n e = =4, quindi
r
(
k
)
n
e che
cn1=4 per inniti n e la congettura 0k n
X
k n
0
r(k)
n
cn = ". Hardy, Kendal, e altri, hanno mostrato che
1 4+
questa congettura e vericata in media.
Accanto al problema del cerchio esiste il problema della sfera, cioe contare le decomposizioni di un numero nella somma di tre o quattro quadrati.
3
Salendo di dimensione il problema non si complica ma si semplica. Invece
delle somme di quadrati,
si possono anche considerare delle forme quadratiche
X
denite positive
a xx.
i;j d i;j i i
1
IL PROBLEMA DEI DIVISORI DI DIRICHLET
Il problema del cerchio di Gauss studia in quanti modi si puo decomporre
un numero in una somma di due quadrati. Il problema dei divisori di Dirichlet
studia in quanti modi si puo decomporre un numero in un prodotto di due
numeri, cioe quanti divisori interi ha un dato numero intero? Per esempio,
se n e primo i divisori sono solo due, 1 e n, e se n ha una scomposizione
in fattori primi pq r ::: allora i divisori sono ( + 1)( + 1)( + 1):::. La
funzione aritmetica che conta i divisori di un numero dipende quindi dalla
scomposizione in fattori primi ed e abbastanza irregolare. Riformuliamo
allora la domanda chiedendoci quanti sono in media i divisori di un numero
intero. Indichiamo con d(k) il numero dei divisori di k,
d(n) = jf(x; y) 2 N N : x y = ngj :
Questo numero e uguale al numero dei punti (x; y) a coordinate intere e
positive sull'iperbole xy = n e la somma d(1)+ d(2)+ ::: + d(n) e uguale al numero dei punti interi (x; y) con 0 < y n=x
Z n . Una approssimazione di questo
numero e data dall'area sotto l'iperbole nx dx = n log(n), quindi in media
un numero n ha circa log(n) divisori. Di fatto Dirichlet ha dimostrato un
risultato piu preciso.p Scomponiamo
la regione sotto l'iperbole nel quadrato
p
p
p
di vertici
(0
; 0),p (0; n), ( n; n), ( n; 0), nel trapezio curvilineo dipvertici
p
p
(0; n), ( n; pn),p(1; n), (0; n), e nel trapezio curvilineo di vertici ( n; 0),
(n; 0), (n; 1), ( n; n). Siccome il numero di punti interi nei due trapezi e
lo stesso, il numero di punti sotto l'iperbole 0 < y n=x e
1
4
n
X
j =1
=2
pn
[X
]
j =1
p
[Xn]
p
p
d(j ) = [ n] + 2
([n=j ] [ n])
2
p
[n=j ] [ n] = 2n
pn
[ ] dx
= 2n
x
Z
1
j =1
2
pn
[X
]
p
1=j n + O ( n)
0 p j =1
[ n] Z
BX 1
n + 2n @
j
j =1
1
[pn] dx C
1
x
pn)
A+O(
p
= n log(n) + n(2 1) + O ( n) :
Quindi, in mediail numero deiZdivisori
din e uguale a log(n) + (2 1),
n
Xn
j
x dx = 0; 577215::: e la costante di
dove = limn! 1
j
Eulero-Mascheroni. Inoltre,
d(1) + d(2) + ::: + d(n)
(log(n) + (2 1)) pc :
1
+
=1
1
1
n
n
Come per il problema del cerchio, questa stima dell'errore puo essere
migliorata,
X
d(k)
1kn
X
d(k)
1
k
n
X
d(k)
1 k n
X
d(k)
1 k n
n log(n) (2
n log(n) (2
n log(n) (2
n log(n) (2
X
1)n
1)n
1)n
1)n =
cn =
(Dirichlet 1849),
cn =
(Voronoi 1903),
1 2
1 3
cn =
1 3
"
(van der Corput 1923),
(n = ) (Hardy, Landau 1915).
1 4
1)n
La congettura e che
d(k) n log(n) (2
cn = " e
k n
questa congettura e vericata in media.
Concludiamo questo cenno al problema dei divisori dando un'occhiata
ai diari di Gauss che in data 20 Giugno 1796 contengono l'aermazione:
1
5
1 4+
\All'innito la somma dei fattori e uguale a 2 =6 per la somma dei numeri".
Indichiamo con (k) la somma dei divisori di k. I divisori di k sono tanti
quanti i punti (x; y) a coordinate intere e positive sull'iperbole xy = k e la
somma dei divisori dei numeri positivi minori o uguali ad n e
n
X
k=1
(k) =
n=k]
n [X
X
k=1 j =1
j=
n
X
1 hni hn
k=1
i
2 k k +1 n
1
n2 X
2 k=1 k2
12n :
2
2
Quindi, come enunciato da Gauss, si ha
Xn
lim
n! 1
+
k=1
X
n
(k )
k=1
k
= 6 :
2
APPROSSIMAZIONI DI IRRAZIONALI CON RAZIONALI
Abbiamo visto dei problemi in teoria dei numeri che conducono alla stima
del numero di punti interi contenuti in una regione del piano o dello spazio.
Ne presentiamo un'altro che e un po' diverso dai precedenti perche, invece
di tanti punti interi, questa volta se ne cerca uno solo. Il problema e il
seguente: Se si vogliono approssimare dei numeri reali con numeri razionali
con un comune denominatore il piu piccolo possibile, quanto possono essere
buone le approssimazioni?
TEOREMA (Lagrange-Dirichlet-Minkowski):
Dati dei numeri reali 1 , 2 ,..., d , ed un numero naturale Q, esistono
numeri interi p1 , p2 ,..., pd , q, con 1 q Q, tali che jj q pj j Q 1=d .
In particolare jj pj =q j q (d+1)=d .
Lagrange ha dimostrato il teorema quando d = 1 utilizzando le frazioni
continue. Dirichlet ha dimostrato il teorema utilizzando il principio che se
ci sono piu oggetti che scatole, c'e una scatola con almeno due oggetti.
Minkowski ha riottenuto il risultato utilizzando la geometria dei numeri.
Consideriamo il parallelogrammo
(x ; x ; :::; xd; y) 2 Rd : jj y xj j Q =d; jyj Q :
Questo e un insieme convesso e simmetrico rispetto all'origine, di misura
d
2 nello spazio Rd . Un tale insieme deve contenere dei punti interi distinti
1
+1
+1
2
1
+1
6
dall'origine. Se questo convesso C non contiene punti interi diversi da zero,
gli insiemifk + 2 C gk2Zd+1 hanno misura uno e sono disgiunti. Se gli insiemi
sono disgiunti non coprono tutto lo spazio, ma se hanno misura uno coprono
il 100% dello spazio.
1
AREA E PUNTI INTERI
Abbiamo visto che per stimare il numero di punti a coordinate intere
contenuti in una regione, si puo calcolare l'area della regione. Viceversa, per
stimare l'area si possono contare i punti interi. In generale si ottengono solo
delle approssimazioni, ma se la regione e un poligono semplicemente connesso
con vertici interi, esiste una precisa relazione tra area e punti interi.
TEOREMA (Pick 1899):
Se A e l'area di un poligono semplice con vertici a coordinate intere,
I il numero di punti a coordinate intere interni e B il numero di punti a
B
coordinate intere sul bordo, allora A = I +
1.
2
L'idea della dimostrazione e che sia l'area A che la quantita I + B=2 1
sono funzioni additive dei poligoni. Decomponendo un poligono P a vertici
interi nell'unione di due poligoni Q e R a vertici interi senza punti interni
in comune, se la formula A = I + B=2 1 vale sia per Q che per R, allora
vale anche per P = Q [ R. In particolare, se la formula vale per ogni
triangolo elementare con tre vertici interi e senza punti interi interni, allora
vale anche per ogni poligono semplice con vertici interi. Due copie di un
triangolo elementare formano un parallelogrammo elementare con quattro
vertici interi senza punti interi interni, con I = 0 e B = 4. Le traslazioni
intere di questo parallelogrammo piastrellano il piano con tante piastrelle
quanti sono i punti interi, quindi A = 1. La formula e vericata per questo
parallelogrammo, quindi anche per un triangolo elementare ed anche per ogni
gura che puo essere decomposta in triangoli elementari.
Per un dominio piano qualsiasi non ci si puo aspettare una relazione
precisa tra area e punti interi interni, ma solo una relazione approssimata.
Osserviamo che nel teorema di Pick A I = B=2 1 < L, con L il perimetro
del poligono. E' questa relazione che e possibile generalizzare dai poligoni ad
altri domini semplicemente connessi.
TEOREMA (Jarnik-Nosarzewska-Steinhaus 1948):
7
Se e una curva piana, chiusa, semplice, retticabile di lunghezza L 1,
se A e l'area racchiusa dalla curva e N il numero di punti a coordinate intere
interni alla curva, allora jN Aj < L. Inoltre, se il dominio racchiuso dalla
curva e convesso, si ha L=2 < N A L=2 + 1 e l'uguaglianza vale solo
per rettangoli con vertici interi e lati paralleli agli assi.
L'idea della dimostrazione e di associare ad ogni punto intero il quadrato
con centro nel punto e lati di lunghezza uno paralleli agli assi. Un quadrato
interno alla curva da un contributo +1 sia all'area che al numero di punti
interi, quindi non contribuisce all'errore N A. Similmente, un quadrato
esterno alla curva da un contributo 0 sia all'area che al numero di punti
interi e non contribuisce all'errore. Gli unici quadrati che contribuiscono
all'errore sono quelli che intersecano la curva ed il contributo di uno di questi
quadrati e minore della lunghezza di quella parte della curva contenuta nel
quadrato. Il risultato per regioni convesse e un poco piu complicato.
Esistono delle generalizzazioni di questi teoremi a domini in dimensione
maggiore di due, ma non sono semplici ed immediate. Per esempio, in R i
tetraedri con vertici (0; 0; 0), (1; 0; 0), (0; 1; 0), (1; 1; n), hanno quattro punti
interi sul bordo e nessun punto intero interno. Il volume n=6 non e determinato dal numero di punti interi. Analogamente, un cilindro molto lungo
puo contenere molti punti interi ma avere volume e area piccoli. Quindi non
e immediato controllare la dierenza tra volume e punti interi con l'area.
Per evitare controesempi patologici ed ottenere risultati positivi si possono
considerare dilatazioni di domini dati.
3
TEOREMA:
Se D e un dominio in Rd con bordo @D liscio, la discrepanza tra il numero
di punti interi N (rD) in dilatato rD ed il volume jDj rd e dominata, a
meno di un errore trascurabile quando r ! +1, dalla meta dell'area della
supercie j@Dj rd 1 ,
N (rD)
j rd + o rd
jDj rd j@D
2
1
1
:
Poiche la discrepanza
tra punti interi e volume e dovuta ai punti a disp
tanza minorep di d=2 dal bordo, si puo ottenere facilmente una stima con
la costante d. Ottenere la costante 1/2 e un poco piu complicato. Comunque, l'esempio di un parallelogrammo centrato in un punto intero e con
lati di lunghezza intera e paralleli agli assi, mostra che questa costante e la
migliore possibile.
8
PUNTI INTERI E SERIE DI FOURIER
Quanti punti interi stanno in un dominio D in Rd? Per complicare un
poco la domanda chiediamoci quanti punti interi stanno in un traslato D
t. Questo numero e una funzione periodica nella variabile t che possiamo
sviluppare in serie di Fourier sul toro Td = Rd=Zd = [0; 1)d,
X
k2Z
d
D t (k) =
=
X
j 2Z
XZ
X
j 2Z
d
Td
=
F f ( ) =
j 2Zd
Z
R
d
!
X
D s (k) exp( 2ij s)ds exp(2ij t)
Td k2Zd
d
k2Z Z
X
d
Z
!
D (k + s) exp( 2ij (k + s))ds exp(2ij t)
Rd
D (x) exp( 2ij x)dx exp(2ij t)
= jDj +
X
j 2Z
f0g
d
F D (j ) exp(2ij t):
f (x) exp( 2i x)dx e la trasformata di Fourier in Rd ed
il conto sopra non e nient'altro che la formula di sommazione di Poisson.
Gli esponenziali exp(2ij t) hanno media nulla sul toro, quindi integrando
sopravvive solo il termine jDj. Le traslate D t contengono in media tanti
punti interi quanto la misura del dominio jDj e l'errore quadratico medio e,
per l'uguaglianza di Parseval,
8
<Z
:
Td
X
k2Zd
D (k + t)
!2
91=2
=
8
< X
jDj dt; = :
j 2Zd
f0g
91=2
=
jF D (j )j ; :
2
La stima della varianza nel numero dei punti interi in un dominio conduce
quindi a studiare la trasformata di Fourier di una funzione caratteristica.
Ponendo = # con j j = e j#j = 1 e scomponendo l'integrale su D lungo
le sezioni fx 2 D; # x = tg, si ottiene
Z
D
exp( 2i x)dx =
Z
R
jfx 2 D; # x = sgj exp( 2is)ds:
9
Se l'insieme D ha un bordo liscio con curvatura positiva, la misura delle
sezioni e diversa da zero solo su un intervallo a < s < b, e concava in
questo intervallo e singolare agli estremi, A(s a) d = se s ! a+ e
B (b s) d = se s ! b . Le costanti A e B sono funzioni della curvatura
nei punti con normale #. Integrando per parti si verica facilmente che sono
gli estremi a e b con le costanti A e B i responsabili del decadimento della
trasformata di Fourier. In particolare si ha
(
(
1) 2
1) 2
Z
F D (#) = jfx 2 D; # x = sgj exp( 2is)ds d
=
( +1) 2
:
R
Per esempio, la trasformata di Fourier di una sfera con centro nell'origine
e raggio r e una funzione di Bessel,
F fjxjrg( ) = rd jr j d= Jd= (2 jr j)
r d = j j d = cos(2r j j (d + 1)=4):
2
1 (
1) 2
2
( +1) 2
Da queste stime asintotiche si ricava il seguente risultato.
TEOREMA (Kendall 1948):
8
<Z
:
Td
X
k2Zd
fjxjrg (k + t)
!2
91=2
=
jfjxj rgj dt; r d
(
=
1) 2
:
Piu in generale, dilatando di un fattore r un dominio convesso con bordo
di curvatura positiva, si ha F rD ( ) = rd F D (r ), e
8
<Z
:
Td
X
k2Z
d
rD (k + t)
!2
91=2
=
8
< X
jrDj dt; = :
j 2Z
d
f0g
91=2
d
=
r (rj )
D
;
F
cr d
(
La trasformata di Fourier di funzioni caratteristiche di domini convessi
con curvatura positiva decade allo stesso modo lungo tutte le direzioni. Per
domini generici la situazione e dierente. Lungo le direzioni delle normali
nei punti del bordo con curvatura nulla il decadimento della trasformata di
Fourier F D ( ) puo essere peggiore di j j d = . L'esempio di un cubo e
caratteristico:
( +1) 2
10
=
1) 2
:
Z=
1 2
=
1 2
Z=
1 2
:::
exp ( 2i( x + ::: + dxd)) dx :::dxd =
1
1
1
=
1 2
d
Y
sin( j )
j =1
j
:
In generale, per un poliedro jF P ( )j j j se ! 1 lungo le direzioni
ortogonali alle facce, mentre jF P ( )j j j d lungo direzioni non ortogonali.
Il cattivo decadimento della trasformata di Fourier lungo certe direzioni non
e dovuto agli spigoli, ma alle facce. Questo comportamento della trasformata
di Fourier inuenza il comportamento dell'errore nella stima del numero di
punti interi in un dilatato di un poliedro. Se il poliedro ha una faccia con
inclinazione razionale le stime dell'errore sono dell'ordine di rd , mentre
se tutte le facce del poliedro hanno inclinazioni irrazionali possono valere
stime considerevolmente migliori. In particolare, Hardy e Littlewood hanno
mostrato che per certi triangoli nel piano l'errore puo essere controllato da
log(r). Per poliedri l'errore puo essere controllato in media da logd (r).
Prima di dare un enunciato preciso, diamo una idea di questo fatto. Per il
teorema di Pick, in un poligono con vertici interi l'area dierisce dal numero
di punti interi interni per circa la meta del numero di punti interi sul bordo.
Un poligono con vertici interi ha lati con inclinazioni razionali ed e possibile
avere sul bordo un numero di punti interi paragonabile al perimetro, ma
per delle inclinazioni razionali con denominatore grande su questi lati non
ci sono molti punti interi. Quindi "in generale" sul bordo del poligono non
ci sono molti punti interi ed il numero di punti interi interni e una buona
approssimazione dell'area.
1
1
1
TEOREMA:
Sia P un poliedro in Rd , sia r > 0, 2 SO(d), t 2 Rd , e sia rP + t un
dilatato, ruotato, traslato di P . Denotiamo con D(r; ; t) la discrepanza tra
il numero di punti interi in rP + t ed il volume jrP + tP j,
D(r; ; t) =
X
k2Zd
rP +t (k)
Allora
11
jP j r d
Z
Z
jD(r; ; t)j dtd
p
SO(d) ZT
d
Z
1=p
c(2 + r) d
(
=p) ;
1)(1 1
se 1 < p +1;
j
D(r; ; t)j dtd c logd (2 + r); se p = 1;
Td
SO d
sup 2 SO(d); t 2 Td : jD(r; ; t)j > c logd (2 + r):
( )
1
>0
Interpretazione probabilistica:
Se si getta a caso un poliedro rP + t nello spazio Rd , la dierenza tra
il volume ed il numero di punti interi puo essere dell'ordine della misura
del bordo, crd 1 , ma la probabilita per questa dierenza di essere molto piu
grande di logd 1 (2 + r) e molto piccola:
2 SO(d); t 2 Td : jD(r; ; t)j > " logd (2 + r) c":
1
1
Concludiamo con un cenno a possibili generalizzazioni. Abbiamo visto
che la discrepanza tra il numero di punti interi ed il volume e dominata
dall'area della supercie. Se il dominio e posizionato a caso nello spazio, la
media quadratica della discrepanza e la radice quadrata dell'area. Queste
stime valgono per domini con un bordo piuttosto regolare, in particolare
hanno senso solo se il bordo ha misura superciale nita. Che cosa accade per
domini con bordo frattale? Forse entra in gioco un qualche tipo di dimensione
frazionaria del bordo.
12