AREA E PUNTI INTERI

(1)

AREA E PUNTI INTERI

Leonardo Colzani

Dipartimento di Matematica, Universita degli Studi di Milano-Bicocca

SUNTO: 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%.

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. Consideri- amo 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,

r(n) =(x;y) 2 Z Z : x²+ y² = 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 d3(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

(2)

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 di punti a coordinate intere in un cerchio con centro nell'origine e raggiop

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 (d1(n) d3(n)), denotando con [x] il piu grande intero minore o uguale a x, si ricava

X

0kn

r(k) = 1 + 4 ([n=1] [n=3] + [n=5] [n=7] + :::) :

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 un cerchio con centro nell'origine e raggio p

n in quattro sottoinsiemi: A = f l'origine g, B = f i punti sugli assi, esclusa l'origine g, C = f i punti nel quadrato di lato 2p

n=2 iscritto nel cerchio, esclusi gli assi g, D = f i punti restanti g. Denotando con jEj il numero di punti in un insieme E, si ha

X

0kn

r(k) = jAj + jBj + jCj + jDj

= 1 + 4 [p

n] + 4hp n=2i₂

+ 8 X

pn=2<kpn

pn k² :

Malgrado l'aspetto, questa formula non e di dicile uso perche non uti- lizza che la parte intera delle radici quadrate. Per esempio, se n = 100, jAj = 1, jBj = 40, jCj = 196, jDj = 80,

n = (10)² (100)² (1000)² (10000)² X

0kn

r(k) = 317 31417 3141549 314159053

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,

(3)

X

0kn

r(k) n

2p

n (Gauss 1834-1837),

X

0kn

r(k) n

cn¹⁼³ (Sierpinski 1906),

X

0kn

r(k) n

cn^{1=3 "} (van der Corput 1923),

X

0kn

r(k) n

= (n¹⁼⁴) (Hardy, Landau 1915).

La stima dell'errore di Gauss ha una dimostrazione molto semplice. As- sociando 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 centri in x²+ y² n. Questi quadrati contengono il cerchio x² + y² p

n p

2=2₂

e sono contenuti in x² + y² pn p

2=2₂

. Quindi

p

n p

2=2₂

n < X

0kn

r(k) n < p n +p

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 (Erdos-Fuchs 1956):

Sia ff(n)g⁺¹_n=0 una funzione aritmetica a valori interi con f(0) f(1) 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 sup_x!+1x ¹⁼⁴jR(x)j > 0.

Nel problema del cerchio, f(n) = n² e = =4, quindi X

0knr(k) n cn¹⁼⁴ per inniti n e la congettura e che X

0knr(k) n cn^1=4+". Hardy, Kendal, e altri, hanno mostrato che 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.

(4)

Salendo di dimensione il problema non si complica ma si semplica. Invece delle somme di quadrati, si possono anche considerare delle forme quadratiche denite positive X

1i;jdai;jxixi.

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 pqr::: 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. Una approssimazione di questo numero e data dall'area sotto l'iperbole

Z _n

1

n

xdx = n log(n), quindi in media un numero n ha circa log(n) divisori. Di fatto Dirichlet ha dimostrato un risultato piu preciso. Scomponiamo la regione sotto l'iperbole nel quadrato di vertici (0; 0), (0;pn), (pn;pn), (pn; 0), nel trapezio curvilineo di vertici (0;p

n), (p n;p

n), (1; n), (0; n), e nel trapezio curvilineo di vertici (p n; 0), (n; 0), (n; 1), (p

n;p

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

(5)

Xn j=1

d(j) = [p

n]²+ 2 [X^pⁿ]

j=1

([n=j] [p n])

= 2 [X^pⁿ]

j=1

[n=j] [p

n]² = 2n [X^pⁿ]

j=1

1=j n + O (p n)

= 2nZ [^pⁿ]

1

dx

x n + 2n 0 B@

[X^pⁿ]

j=1

1 j

Z [^pⁿ]

1

dx x

1

CA + O (p n)

= n log(n) + n(2 1) + O (p n) :

Quindi, in media il numero dei divisori di n e uguale a log(n) + (2 1), dove = lim_n!+1Xn

j=1j ¹ Z _n

1 x ¹dx

= 0; 577215::: e la costante di Eulero-Mascheroni. Inoltre,

d(1) + d(2) + ::: + d(n)

n (log(n) + (2 1))

pcn:

Come per il problema del cerchio, questa stima dell'errore puo essere migliorata,

X

1kn

d(k) n log(n) (2 1)n

cn¹⁼² (Dirichlet 1849),

X

1kn

cn¹⁼³ (Voronoi 1903),

X

1kn

cn^{1=3 "} (van der Corput 1923),

X

1kn

= (n¹⁼⁴) (Hardy, Landau 1915).

La congettura e che X

1knd(k) n log(n) (2 1)n cn^1=4+" e 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:

(6)

\All'innito la somma dei fattori e uguale a ²=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

Xn k=1

(k) = Xn k=1

[n=k]X

j=1

j = Xn k=1

1 2

hn k

i hn k + 1i

n² 2

Xn k=1

1

k² ²n² 12 : Quindi, come enunciato da Gauss, si ha

n!+1lim X_n

k=1(k) Xn

k=1k = ² 6 :

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 ₁, ₂,..., _d, ed un numero naturale Q, esistono numeri interi p1, p2,..., pd, q, con 1 q Q, tali che jjq pjj Q ^1=d. In particolare jj pj=qj 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

(x1; x2; :::; xd; y) 2 R^d+1 : jjy xjj Q ^1=d; jyj Q :

Questo e un insieme convesso e simmetrico rispetto all'origine, di misura 2^d+1nello spazio R^d+1. Un tale insieme deve contenere dei punti interi distinti

(7)

dall'origine. Se questo convesso C non contiene punti interi diversi da zero, gli insiemifk + 2 ¹Cg_k2Zd+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.

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 coordinate intere sul bordo, allora A = I + B

2 1.

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):

(8)

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 deter- minato 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.

TEOREMA:

Se D e un dominio in R^dcon bordo @D liscio, la discrepanza tra il numero di punti interi N(rD) in dilatato rD ed il volume jDj r^d e dominata, a meno di un errore trascurabile quando r ! +1, dalla meta dell'area della supercie j@Dj r^{d 1},

N(rD) jDjr^d j@Dj2 r^{d 1}+ o r^{d 1} :

Poiche la discrepanza tra punti interi e volume e dovuta ai punti a dis- tanza minore di p

d=2 dal bordo, si puo ottenere facilmente una stima con la costante p

d. Ottenere la costante 1/2 e un poco piu complicato. Co- munque, 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.

(9)

PUNTI INTERI E SERIE DI FOURIER

Quanti punti interi stanno in un dominio D in R^d? 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 T^d= R^d=Z^d= [0; 1)^d,

X

k2Z^d

_{D t}(k) = X

j2Z^d

Z

T^d

X

k2Z^d

_{D s}(k) exp( 2ij s)ds

!

exp(2ij t)

= X

j2Z^d

X

k2Z^d

Z

T^d_D(k + s) exp( 2ij (k + s))ds

!

exp(2ij t)

= X

j2Z^d

Z

R^d_D(x) exp( 2ij x)dx

exp(2ij t)

= jDj + X

j2Z^d f0g

F_D(j) exp(2ij t):

Ff() = Z

R^df(x) exp( 2i x)dx e la trasformata di Fourier in R^d 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

T^d

X

k2Z^d

_D(k + t) jDj

!₂ dt

9=

;

1=2

= 8<

: X

j2Z^d f0g

jF_D(j)j² 9=

;

1=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 jj = 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:

(10)

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 1)=2} se s ! a+ e

B(b s)^{(d 1)=2} 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

F_D(#) = Z

R

jfx 2 D; # x = sgj exp( 2is)ds ^(d+1)=2:

Per esempio, la trasformata di Fourier di una sfera con centro nell'origine e raggio r e una funzione di Bessel,

F_fjxjrg() = r^djrj ^d=2Jd=2(2 jrj)

¹r^{(d 1)=2}jj ^(d+1)=2cos(2r jj (d + 1)=4):

Da queste stime asintotiche si ricava il seguente risultato.

TEOREMA (Kendall 1948):

8<

: Z

T^d

X

k2Z^d

_fjxjrg(k + t) jfjxj rgj

!₂ dt

9=

;

1=2

r^{(d 1)=2}:

Piu in generale, dilatando di un fattore r un dominio convesso con bordo di curvatura positiva, si ha F _rD() = r^dF _D(r), e

8<

: Z

T^d

X

k2Z^d

_rD(k + t) jrDj

!₂ dt

9=

;

1=2

= 8<

: X

j2Z^d f0g

r^dF_D(rj)9

=

;

1=2

cr^{(d 1)=2}:

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 jj ^(d+1)=2. L'esempio di un cubo e caratteristico:

(11)

1=2Z

1=2

:::

1=2Z

1=2

exp ( 2i(₁x₁+ ::: + _dx_d)) dx₁:::dx_d= Yd j=1

sin(_j)

_j :

In generale, per un poliedro jF_P()j jj ¹ se ! 1 lungo le direzioni ortogonali alle facce, mentre jF_P()j jj ^dlungo 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 in uenza 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 r^{d 1}, 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 log^{d 1}(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.

TEOREMA:

Sia P un poliedro in R^d, sia r > 0, 2 SO(d), t 2 R^d, 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

k2Z^d

_{rP +t}(k) jP j r^d

Allora

(12)

Z

SO(d)

Z

T^djD(r; ; t)j^pdtd

_1=p

c(2 + r)(d 1)(1 1=p); se 1 < p +1;

Z

SO(d)

Z

T^djD(r; ; t)j dtd c log^d(2 + r); se p = 1;

sup>0 2 SO(d);t 2 T^d: jD(r; ; t)j > clog^{d 1}(2 + r):

Interpretazione probabilistica:

Se si getta a caso un poliedro rP + t nello spazio R^d, la dierenza tra il volume ed il numero di punti interi puo essere dell'ordine della misura del bordo, cr^{d 1}, ma la probabilita per questa dierenza di essere molto piu grande di log^{d 1}(2 + r) e molto piccola:

2 SO(d);t 2 T^d : jD(r; ; t)j > " ¹log^{d 1}(2 + r) c":

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.