Naturālu skaitļu attēlošana ar kvadrātu summām

2005.gada 7.oktobra vēstule par 5 kvadrātu summām

2005.gada 18.oktobra vēstule par Ģirta grafiku

Ar Lagranža teorēmu saistītā teorija

2006.gada 14.februāra vēstule par KVi(n)

 

Skaitļu teorijā ir pierādīta šāda Ž. Lagranža (J. L. Lagrange) teorēma:

Teorēma. Ikvienu naturālu skaitli N var izteikt kā 4 naturālu skaitļu a, b, c, d kvadrātu summu: N=a2+b2+c2+d2.

Pierādījums. Jebkurā skaitļu teorijas mācību grāmatā. Sk arī Ar Lagranža teorēmu saistītā teorija.

Piemēri: 7=22+12+12+12, 15=32+22+12+12.

No šiem skaitļiem a, b, c, d daži var būt 0. Ir skaitļi, kurus var izteikt kā triju vai pat divu kvadrātu summas. Piemēri:

6=22+12+12, 13=32+22.

Un, protams, ir skaitļi, kuru izteikšanai pietiek ar vienu kvadrātu - tie ir naturālu skaitļu kvadāti: 1, 4, 9, 16, 25, 36, 49, ....

Uzdevums. Izveidojiet dator-programmu, kas saņem kā parametrus skaitļus N un K, un katram skaitlim 1, 2, 3, ..., N izdrukā visus tā pierakstus ne vairāk kā K kvadrātu summas izskatā. Piemēram, ja K=6, tad skaitlim 6 jāizdrukā šāda (vai līdzīga) rindiņa:

6 / 2 1 1 1 / 1 1 1 1 1 1

kas nozīmē, ka:

6=22+12+12=12+12+12+12+12+12

Saskaitāmos drukājiet dilstošā secībā. Uzdevuma beigas.

Ar šāda dator-eksperimenta palīdzību mēģināsim noskaidrot, piemēram, kas tie ir par skaitļiem:

a) kas paši nav kvadrāti, bet kurus var izteikt kā divu kvadrātu summu;

b) kurus nevar izteikt kā divu kvadrātu summu, bet var - kā triju kvadrātu summu.

Izvirzītās hipotēzes pamēģināsim pierādīt. (Šajā gadījumā gan hipotēzes, gan to pierādījumus var atrast skaitļu teorijas mācību grāmatās).

Bet īsti datoriska pieeja prasa izpētīt vēl ko vairāk. Dažus skaitļus var izteikt kā kvadrātu summas vairākos veidos, piemēram:

1=12, 2=12+12, 3=12+12+12

4=22=12+12+12+12

5=22+12

6=22+12+12

7=22+12+12+12

8=22+22

9=32=22+22+12

10=32+12=22+22+12+12

11==32+12+12

12=32+12+12+12=22+22+22

utt.

Kādas likumsakarības šai virzienā atklājas, aplūkojot Jūsu programmas izdruku? Potenciālie jautājumi:

a) Vai katram skaitlim ir tikai viena īsākā kvadrātu summa?

b) Cik liels (kā funkcija no N) ir skaitļa N dažādo attēlojumu skaits? Ne lielāks par kvadrātsakni no N?

c) Kas tie par skaitļiem, kuriem ir tikai viens attēlojums?

Utml.


17.oktobra vēstule par 5 kvadrātu summām

Jūsu piemērs ir pilnīgi korekts. Es nedaudz paplašināju savu cirvja programmu, pieliekot klāt piekto kvadrātu, un liekot atmest visas tās izteiksmes, kur divu, triju vai četru kvadrātu apakšsummas ir kvadrāti. Jūsu skaitlim 168 nereducējamas 5 kvadrātu summas ir pavisam 9 gab.

168 Varianti=12 (xxx 0 yyy 0 zzz 1 ttt 11)
7 7 6 5 3
9 6 5 5 1
9 7 5 3 2 - Jūsu variants
9 7 6 1 1
9 9 2 1 1
10 5 5 3 3
10 6 4 4 - četru kvadrātu summa
10 7 3 3 1
10 8 2 - triju kvadrātu summa
11 5 3 3 2
11 6 3 1 1
12 4 2 2 - - četru kvadrātu summa

Saskaņā ar manas programmas datiem, mazākie skaitļi, kas ir nereducējamas 5 kvadrātu summas, ir:

16 Varianti=2 (xxx 1 yyy 0 zzz 0 ttt 1)
3 2 1 1 1
4

21 Varianti=3 (xxx 0 yyy 0 zzz 1 ttt 2)
3 2 2 2
3 3 1 1 1
4 2 1

23 Varianti=2 (xxx 0 yyy 0 zzz 0 ttt 2)
3 3 2 1
4 2 1 1 1

24 Varianti=2 (xxx 0 yyy 0 zzz 1 ttt 1)
3 3 2 1 1
4 2 2

Utt.

Bet kopējais secinājums - (ja mana programma darbojas korekti, tad) nereducējamas piecu kvadrātu summas ir ļoti bieži sastopamas, tāpēc laikam par tām nav jēgas daudz interesēties. Lai gan, piemēram, izskatās, ka 297 ir pēdējais skaitlis (pārbaudīju līdz 16500), kam neeksistē nevienas nereducējamas 5 kvadrātu summas:

297 Varianti=12 (xxx 0 yyy 0 zzz 6 ttt 6 uuu 0)
10 10 9 4
12 10 7 2
12 11 4 4
12 12 3
13 8 8
14 7 6 4
14 9 4 2
14 10 1
15 6 6
16 5 4
16 6 2 1
17 2 2

Liekas arī, ka pierādīt, ka visiem skaitļiem >297 eksistē vismaz viena nereducējama 5 kv summa, nemaz nebūtu tik viegli. Bet šis ir tas gadījums, kad rezultāts īpaši nozīmīgs neliekas.

Pilns rezultātu fails līdz 16500 (11MB), līdz 1650 (1MB).

KP


18.oktobra vēstule par Ģirta grafiku

Labrīt,

Vēlreiz apskatīju Ģirta programmas zīmēto grafiku funkcijai:

K(x) = "skaitļa x sadalījumu skaits <=4 kvadrātu summās".

(Lejuplādējiet graph.gif, 2 MB, IE tik lielu neprot parādīt.)

Ko varētu nozīmēt tās 3 zonas - tumšā, vidējā un gaišā? Zonu robežas dod mums divas (nezināmas dabas) funkcijas:

K1(x) (tumšās zonas augšējā mala),
K2(x) (vidējās zonas augšējā mala).

Lielākajai daļai skaitļu (zona ir ļoti tumša!), K(x)<=K1(x). Tad, vēl diezgan ievērojamai daļai, K1(x)<K(x)<=K2(x). Un tikai nelielai daļai, K(x)>K2(x).

Kādas dabas funkcijas ir K1 un K2? Man to abu grafiki liekas ieliekti (kā liekas kolēģiem?). Vienkāršākā hipotēze tad varētu būt pakāpes funkcija bx1+c, kur b, c - mazi pozitīvi reāli skaitļi.
Atgādināšu, ka funkcijas xd grafiks ir: izliekts, ja d<1; taisns, ja d=1; un ieliekts, ja d>1. Bet, varbūt, te ir jāmeklē pavisam cita formula.

Tas nu ir nopietns izaicinājums! Ja izdotos uzminēt kaut kādus tuvinājumus funkcijām K1, K2, plus vēl savākt statistiku par to, kāds procents skaitļu pieder katrai zonai, tad tur pilnīgi noteikti sanāktu vizmaz bakalaura darbs. Ja pēc tam vēl izdotos atrast "izskaidrojumu" šai parādībai, tad jau varētu mēģināt pieteikties referēt kādā konferencē.

Un izšķirošais solis bija Ģirta vienā ceturtdienas vakarā sagādātais grafiks...

KP

Pārdomas pēc kāda laika

> Ja pareizi atceros, tad Jūsu programmas zīmētais grafiks attēlo funkciju
> f(N) = dažādo (līdz 4) kvadrātu summu skaits skaitlim N, ignorējot
> saskaitāmo secību. Grafiks parāda, ka ir 3 atšķirīgas skaitļu kategorijas:
> a) tumšās zona skaitļu ir visvairāk (tāpēc jau zona ir tika tumša), un tiem
> f(N) ir relatīvi mazāka vērtība nekā pārējiem skaitļiem, b) vidējās zonas
> skaitļu ir jau mazāk, un tiem f(N) ir relatīvi lielāka vērtība nekā tumšās
> zonas skaitļiem, bet mazāka nekā pavisam gaišās zonas skaitļiem, c) gaišās
> zonas skaitļu ir vismazāk, un tiem f(N) ir relatīvi vislielākā vērtība nekā
> pārējiem skaitļiem.
>
> Nākošais solis būtu mēģināt noskaidrot, kādas ir šīs atšķirības. Tā kā zonu
> robeža ir gandrīz taisna, tad varētu mēģināt rēķināt katram N attiecību
> f(N)/N, un tad sameklēt, kurām šīs attiecības vērtībām atbilst zonu
> robežas.
>
KP


Lagranža teorēma par kvadrātiem (gabals no teorijas)

No grāmatas:

[1] A. A. Buhštabs. Skaitļu teorija. Maskava, 1966, 384 lpp. (krievu val.)

1770. gadā franču matemātiķis Ž. L. Lagranžs pierādīja šādu teorēmu:

Teorēma (Lagranžs). Ikvienu naturālu skaitli (N) var sadalīt četru veselu skaitļu kvadrātu summā (N = c12+c22+c32+c42, kur daži no ci var būt nulles).

Piezīme. Kā var izlasīt tulkotāja piezīmē grāmatas G.Rademaher, O.Teplic "Cisla i figuri", 1966 beigās (244.lpp.), to, ka šāds likums varētu pastāvēt, ir pamanījis jau Diofants mūsu ēras III gadsimtā. Pjērs Fermā (XVII gadsimtā) kādā vēstulē ir devis šīs teorēmas pierādījuma uzmetumu (kārtējo!), bet "pa īstam" to pierādīja tikai Eilers un Lagranžs XVIII gadsimtā).

Lagranžs iesāka ar ļoti eleganto t.s. Eilera vienādību (ja neticat, pārbaudiet, sareizinot):

(a12+a22+a32+a42)(b12+b22+b32+b42) = c12+c22+c32+c42,

kur:

c1 = a1b1+a2b2+a3b3+a4b4,

c2 = a1b2-a2b1+a3b4-a4b3,

c3 = a1b3-a3b1+a4b2-a2b4,

c4 = a1b4-a4b1+a2b3-a3b2.

[Starp citu, "eksperimentālam" matemātiķim te uzreiz rodas jautājums: vai nevarētu uzrakstīt programmu, kas tādas elegantas vienādības ģenerē vairumā?]

No šīs vienādības seko, ka ja mēs protam sadalīt 4 kvadrātu summā divus skaitļus, tad varam sadalīt arī šo skaitļu reizinājumu. Tā kā katrs naturāls skaitlis ir pirmskaitļu reizinājums, tad Lagranža teorēma būtu pierādīta, ja mums izdotos pierādīt, ka ikvienu pirmskaitli var sadalīt 4 kvadrātu summā (vienīgais izņēmums - skaitlis 1 - arī ir tāda summa: 12+02+02+02). Tātad Lagranža teorēma viegli seko no šādas Lemmas 1:

Lemma 1 (Lagranžs). Ikvienu pirmskaitli var sadalīt četru veselu skaitļu kvadrātu summā.

Dalot naturālu skaitli N ar 4, mēs iegūstam vienu no četriem iespējamiem atlikumiem - 0, 1, 2, vai 3. Tāpēc var teikt, ka pastāv četru "izskatu" naturālie skaitļi - 4k, 4k+1, 4k+2 un 4k+3. Pirmskaitļi (izņemot skaitli 2) var būt tikai izskatos 4k+1 un 4k+3 (jo skaitļi 4k un 4k+2 dalās ar 2, t.i. vienīgais pirmskaitlis te ir skaitlis 2).

Pirmskaitļi izskatā 4k+1: 5, 13, 17, 29, 37, ...

Pirmskaitļi izskatā 4k+3: 3, 7, 11, 19, 23, 31, 43, ...

Izrādās, ka dalot tos kvadrātu summās, skaitļi izskatā 4k+1 un skaitļi izskatā 4k+3 "uzvedas" katrs savādāk.

Teorēma (L. Eilers, 1749). Ikvienu pirmskaitli izskatā p=4k+1 var sadalīt divu veselu skaitļu kvadrātu summā p=a2+b2 (pie tam - vienā vienīgā veidā, ja prasām, lai a>b>0).

Piemēram, 5=22+12, 13=32+22, 17=42+12, 29=52+22, 37=62+12, ...

Pirmskaitļi izskatā 4k+3 divu kvadrātu summā nedalās (daži nedalās pat triju kvadrātu summā). Piemēram, 3=12+12+12, 7=22+12+12+12, 11=32+12+12, 19=32+32+12, ...

Tomēr var pierādīt šādu vispārīgu Lemmu 2:

Lemma 2. Katram pirmskaitlim p>=2 eksistē veseli skaitļi m, a, b tādi, ka 1<=m<p/2 un mp=a2+b2+12. (T.i. katram pirmskaitlim p neliels tā daudzkārtnis mp ir sadalāms triju kvadrātu summā, pie tam viens no kvadrātiem ir 1.)

Ja esat studējuši skaitļu teorijas kursu, tad Lemmu 2 Jums nebūtu grūti pierādīt pašiem. Toties Lemmas 1 izvedums no Lemmas 2 jau ir grūtāks - mācību grāmatā tas aizņem pusotru lappusi.

Lemmas 2 pierādījums [1]. Ja p=2, tad 2=1+0+1, tātad atliek izpētīt gadījumu, kad p>2, t.i. kad p ir nepāra pirmskaitlis.

Vispirms ievērosim, ka ja mums ir jebkādi p+1 skaitļi, tad divi no tiem, dalot ar p, dos vienādus atlikumus. Šis ir visai iecienīts paņēmiens vienkāršu skaitļu teorijas teorēmu iegūšanai. Aplūkosim divas skaitļu kopas:

x2, kur 0<=x<=(p-1)/2, t.i. ir (p+1)/2 skaitļi,

-1-y2, kur 0<=y<=(p-1)/2, t.i. arī te ir (p+1)/2 skaitļi.

Kopā tātad mums te ir p+1 skaitlis, t.i. divi no tiem, dalot ar p, dos vienādus atlikumus. Ja viens no abiem skaitļiem būtu no pirmās kopas (t.i. x2), bet otrs - no otras (t.i. -1-y2), tad to starpība būtu x2+y2+1, un tai būtu jādalās ar p, t.i. x2+y2+1=mp kādam skaitlim m. Cik liels var būt m?

m = (x2+y2+1)/p <= 2*(p-1)2/4p <= (p2-2p+1)/2p < p/2.

Tātad lemma būs pierādīta, ja mums izdosies parādīt, ka gan pirmajā kopā, gan otrajā ik divi skaitļi, dalot ar p, dod dažādus atlikumus. Vai divu pirmās kopas skaitļu a2, b2 starpība var dalīties ar p? Ja var, tad

a2-b2=(a+b)(a-b),

tātad, a+b vai a-b dalās ar p. Bet a+b <=2*(p-1)/2 <p, un a-b tāpat. Bez tam, a-b>-p. Tātad vai nu a=b=0, vai a=b, kas nav iespējams.

Līdzīgi ir ar otro kopu, jo skaitļu -1-a2, -1-b2 starpība ir tas pats a2-b2.

Lemma 2 pierādīta.

Lemmas 1 pierādījums [1]. Interesanta ideja: pētīsim vismazāko m tādu, ka eksistē veseli skaitļi x, y, z, u tādi, ka mp=x2+y2+z2+u2. Saskaņā ar Lemmu 2, m<p/2, jo np=a2+b2+12+02 kādam 1<=n<p/2. Parādīsim, ka m=1.

Vispirms parādīsim, ka m ir nepārskaitlis. Pieņemsim no pretējā, ka m=2m', un parādīsim, ka tad arī m'p var uzrakstīt kā 4 kvadrātu summu (tā būs pretruna, jo m mums ir mazākais tāds skaitlis).

...

 

 

Sk. arī http://www.math.ohio-state.edu/~econrad/Jacobi/sumofsq/node7.html

Zinātniekiem ir izdevies vispārināt Eilera teorēmu, precīzi noskaidrojot to skaitļu klasi, kuri dalās divu kvadrātu summā.

Teorēma. Skaitlis N sadalās divu kvadrātu summā N=a2+b2 tad un tikai tad, ja tas ir vesela skaitļa kvadrāta reizinājums ar skaitli, kas ir viena vai vairāku tādu skaitļu reizinājums, kas pieder kopai {1, 2}U{visi pirmskaitļi izskatā 4k+1}.

Šīs teorēmas pierādījuma viena puse ("no labās puses uz kreiso") viegli seko no augšminētās Eilera teorēmas, izmantojot šādu viegli pārbaudāmu identitāti:

(a12+a22)(b12+b22) = c12+c22,

kur:

c1 = a1b1+a2b2,

c2 = a1b2-a2b1.

Tiešām, 1=12+02, 2=12+12, un ikviens pirmskaitlis izskatā 4k+1 sadalās divu kvadrātu summā. Tātad arī jebkurš šādu skaitļu reizinājums dalās divu kvadrātu summā. Un ja n=a2+b2, tad pareizinot n ar m2, iegūstam skaitli N=m2n=(ma)2+(mb)2. Q.E.D.

Pierādījuma otra puse ("no kreisās puses uz labo") ir daudz sarežģītāka.

Šī teorēma dod mums vienkāršu metodi, kas ģenerē visus skaitļu s, kas dalās divu kvadrātu summā.

a) Ņemam skaitļus 1, 2 un pirmskaitļus izskatā 4k+1: 5, 13, 17, 29, 37, 41, ...

b) Veidojam visus iespējamos šo skaitļu reizinājumus pa vienam, pa diviem, pa trim utt.: 1, 2, 5, 2*5=10, 13, 2*13=26, 29, 2*17=34, 37, 5*13=65, ...

c) Reizinām iegūtos skaitļus ar patvaļīgiem kvadrātiem: n2, 2n2, 4n2, 5n2, 10n2, 13n2, 25n2, 26n2, 29n2, 34n2, 37n2, ...

Tādā veidā iegūstam visus skaitļus, kas dalās divu kvadrātu summā: 2, 4, 5, 8, 9, 10, 13, 16, 18, 20, 25, 26, 29, 32, 34, 36, 37, 40, 41, 45, 49, 50, 52, ...

Šī virkne, protams, sakrīt ar to, ko mēs varētu iegūt no saviem eksperimentiem līdz 6000 (3MB) vai līdz 65500 (15 MB).

Diemžēl, manās skaitļu teorijas grāmatās man neizdevās atrast teorēmas, kas ļautu raksturot skaitļus, kuri dalās triju kvadrātu summās. Vai no mūsu eksperimentiem mēs spētu izvirzīt kādu hipotēzi šajā jautājumā?


Hipotēze (aplūkojot datus līdz skaitlim 6000)?

Ja skaitli var sadalīt <=4 kvadrātu summā tikai vienā veidā, tad to var sadalīt <=3 kvadrātu summā. Kas tie ir par skaitļiem? Hipotēze: tādu skaitļu ir bezgalīgi daudz.


14.februāra vēstule par KVi(n)

Ienāca prātā vēl viena problēma no kvadrātu summu pasaules.

Cik liels naturālo skaitļu "procents" ir sadalāmi ne vairāk kā divu, vai ne vairāk kā triju kvadrātu summā?

Ar vienu kvadrātu ir tā: starp skaitļiem no 1 līdz n kvadrātu skaits ir sqrt(n) veselā daļa. Tiešām, x*x<=n tad un tikai tad, ja x<=sqrt(n).

Tātad KV1(n) = sqrt(n) + O(1), t.i kvadrātu skaits līdz n ir aptuveni kvadrātsakne no n.

Ar KVi(n) apzīmēsim to skaitļu skaitu no 1 līdz n, kuri sadalāmi ne vairāk kā i kvadrātu summā.

Kādas funkcijas sanāktu, ja mēs mēģinātu papētīt KV2(n) un KV3(n)? Protams, ir skaidrs, ka KV4(n)=n. Bet KV2 un KV3 pētīšana būtu jāiesāk ar eksperimentiem, izrēķinot KV2(n) un KV3(n) pietiekami lieliem n. Tad varētu salīdzināt tās, piemēram, ar to pašu kvadrātsakni no n. Interesanti, kas tur varētu sanākt?

KP