Blichfeldts sats

Blichfeldts sats, i form av att varje plan uppsättning av area $A$ (här en ellips med area $\pi$ ) innehåller minst $\lceil A\rceil$ punkter ( här är $\lceil \pi \rceil =4$ punkter), vars alla koordinater skiljer sig från varandra med heltal. Satsen bevisas genom att klippa uppsättningen av kvadrater av heltalsrutnätet (överst), översätta varje del med en heltalstranslationsvektor till en enhetskvadrat, hitta en punkt i den enhetskvadraten som täcks av många bitar (mitten), och använda förbilderna av denna punkt som de önskade punkterna (nederst).

Blichfeldts sats är en matematisk sats i siffrors geometri , som säger att närhelst en avgränsad mängd i det euklidiska planet har area ${\displaystyle A} ,$ kan den översättas så att den innehåller åtminstone $\lceil A \rceil$ punkter i heltalsgittret . På motsvarande sätt innehåller varje avgränsad uppsättning område $A$ en uppsättning $\lceil A\rceil$ punkter vars koordinater alla skiljer sig med heltal.

Denna teorem kan generaliseras till andra gitter och till högre dimensioner, och kan tolkas som en kontinuerlig version av duvhålsprincipen . Den är uppkallad efter den dansk-amerikanske matematikern Hans Frederick Blichfeldt, som publicerade den 1914. Vissa källor kallar den Blichfeldts princip eller Blichfeldts lemma .

Uttalande och bevis

Satsen kan enklast anges för punkter i det euklidiska planet, och för heltalsgittret i planet. För denna version av satsen, låt $S$ vara valfri mätbar mängd , låt $A$ beteckna dess area och runda av detta tal uppåt till nästa heltalsvärde, $n =\lceil A\rceil$ . Sedan säger Blichfeldts teorem att $S$ kan översättas så att dess översatta kopia innehåller minst $n$ punkter med heltalskoordinater.

Grundidén med beviset är att skära $S$ i bitar enligt kvadraterna av heltalsgittret, och att översätta var och en av dessa bitar med ett heltalsmängd så att den ligger inom enhetskvadraten med ursprunget som dess nedre högra hörnet. Denna översättning kan göra att vissa bitar av enhetskvadraten täcks mer än en gång, men om den kombinerade arean av de översatta bitarna räknas med multiplicitet förblir den oförändrad, lika med $A$ . Å andra sidan, om hela enhetskvadraten täcktes med multiplicitet $n-1$ skulle dess area vara $n-1$ , mindre än $A$ . Därför måste någon punkt $p$ i enhetskvadraten täckas med multiplicitet åtminstone $n$ . En översättning som tar $p$ till ursprunget kommer också att ta alla de $n$ punkterna i $S$ som täckte $p$ till heltalspunkter, vilket är vad som krävdes .

Mer allmänt gäller satsen $d$ -dimensionella mängder $S$ , med $d$ -dimensionell volym $A$ och en godtycklig $d$ -dimensionellt gitter $\Lambda$ (en uppsättning punkter i $d$ -dimensionellt utrymme som inte alla ligger i något lägre dimensionellt delrum, är separerade från varandra med något minimiavstånd och kan kombineras genom att addera eller subtrahera deras koordinater för att producera andra punkter i samma uppsättning). Precis som heltalsgittret delar upp planet i kvadrater, delar ett godtyckligt gitter upp sitt utrymme i fundamentala områden (kallade parallellotoper ) med egenskapen att vilken som helst av dessa regioner kan översättas till vilken som helst av dem genom att lägga till koordinaterna för en unik gitterpunkt . Om $L$ är den $d$ -dimensionella volymen av en av parallellotoper, så anger Blichfeldts sats att $S$ kan översättas till att inkludera åtminstone $\ lceil A/L\rceil$ punkter av $\Lambda$ . Beviset är som tidigare: skär upp $S$ med parallellotoper, översätt bitarna med translationsvektorer i $\lambda$ till en enda parallellotop utan att ändra den totala volymen (räknat med multiplicitet), observera att det måste vara en punkt $p$ av multiplicitet åtminstone $\lceil A/L\rceil$ , och använd en översättning som tar $p$ till origo.

Istället för att be om en översättning för vilken det finns $n$ gitterpunkter, säger en ekvivalent form av satsen att $S$ själv innehåller en uppsättning av $n$ punkter, vars alla parvis skillnader hör till gallret. En förstärkt version av satsen gäller för kompakta mängder , och anger att de kan översättas till att innehålla åtminstone $\lfloor A+1\rfloor$ punkter i gittret. Detta antal punkter skiljer sig från $\lceil A\rceil$ endast när $A$ är ett heltal, för vilket det är ett större.

Ansökningar

Minkowskis teorem

Minkowskis teorem , bevisat tidigare än Blichfeldts arbete av Hermann Minkowski , säger att varje konvex mängd i planet som är centralt symmetrisk runt ursprunget, med area större än fyra (eller en kompakt symmetrisk mängd med area lika med fyra) innehåller en heltalspunkt som inte är noll . Mer allmänt, för ett $d$ -dimensionellt gitter $\Lambda$ vars fundamentala parallellotoper har volym ${\displaystyle L} ,$ vilken uppsättning som helst centralt symmetrisk runt origo med volym större än $2^{d}L$ innehåller en gitterpunkt som inte är noll.

Även om Minkowskis ursprungliga bevis var annorlunda, kan Blichfeldts teorem användas i ett enkelt bevis för Minkowskis teorem. Låt $X$ vara vilken centralt symmetrisk mängd som helst med volym större än $2^{d}L$ (uppfyller villkoren för Minkowskis teorem), och skala ner den med en faktor två för att få en ställ in ${\tfrac {1}{2}}X$ av volym större än $L$ . Enligt Blichfeldts sats har ${\displaystyle {\tfrac {1}{2}}X} två punkter$$p$ och $q$ vars koordinatmässiga skillnad tillhör $L$ . Omvänd krympningsoperationen, $2p$ och $2q$ tillhör $X$ . Genom symmetri ${\displaystyle -2q} också$ tillhör $X$ , och genom konvexitet hör mittpunkten av $2p$ och $-2q$ till $X$ . Men denna mittpunkt är $pq$ , en punkt som inte är noll för $L$ .

Andra applikationer

Ett exempel på den ökade kraften hos Blichfeldts sats över Minkowskis sats för att hitta gitterpunkter i icke-konvexa mängder. Den (stängda) gula uppsättningen $Y$ till vänster har area 1, så den kan översättas till att täcka två punkter av vilket gitter som helst vars fundamentala område har volym 1, till exempel det röda gittret. Därför innehåller den blå uppsättningen $X=YY$ till vänster, uppsättningen av skillnader mellan par av punkter i ${\displaystyle Y},$ när den är centrerad på origo, en gitterpunkt som inte är noll. Däremot har den blå rektangeln $K$ till höger, den största konvexa delmängden av ${\displaystyle X} ,$ arean för liten för Minkowskis teorem för att garantera att den innehåller en gitterpunkt som inte är noll, och den gula rektangeln ${\tfrac {1}{2}}K$ inom den är för liten för att Blichfeldts sats ska hitta två punkter i den.

Många tillämpningar av Blichfeldts teorem, som tillämpningen på Minkowskis teorem, innebär att hitta en gitterpunkt som inte är noll i en tillräckligt stor mängd, men en som inte är konvex. För beviset för Minkowskis sats är nyckelrelationen mellan mängderna $X$ och ${\tfrac {1}{2}}X$ som gör att beviset fungerar att alla skillnader i par av punkter i ${\tfrac {1}{2}}X$ tillhör $X$ . Men för en uppsättning $X$ som inte är konvex, kan ${\tfrac {1}{2}}X$ ha punkterpar vars skillnad inte tillhör $X$ , vilket gör den oanvändbar i den här tekniken. Man skulle istället kunna hitta den största centralt symmetriska konvexa delmängden ${\displaystyle K\delmängd X} ,$ och sedan tillämpa Minkowskis sats på ${\displaystyle K} ,$ eller på motsvarande sätt tillämpa Blichfeldts sats på ${\tfrac {1}{2}}K$ . Men i många fall har en given icke-konvex uppsättning $X$ en delmängd $Y\subset X$ som är större än ${\tfrac {1}{2} }K$ , vars parvisa skillnader tillhör $X$ . När så är fallet leder den större storleken på $Y$ i förhållande till ${\tfrac {1}{2}}K$ till snävare gränser för hur stor $X$ behöver för att vara säker på att innehålla en gitterpunkt.

För en centralt symmetrisk stjärndomän är det möjligt att använda variationskalkylen för att hitta den största mängden $X'$ vars parvisa skillnader tillhör $X$ . Tillämpningar av denna metod inkluderar simultan Diophantine approximation , problemet med att approximera en given uppsättning irrationella tal med rationella tal som alla har samma nämnare.

Generaliseringar

Analoger av Blichfeldts teorem har bevisats för andra uppsättningar av punkter än gitter, vilket visar att tillräckligt stora regioner innehåller många punkter från dessa uppsättningar. Dessa inkluderar en sats för fuchsiska grupper , gitterliknande delmängder av $2\times 2$ matriser och för uppsättningarna av hörn av arkimediska plattsättningar .

Andra generaliseringar tillåter mängden $S$ att vara en mätbar funktion , som bevisar att dess summa över någon uppsättning av översatta gitterpunkter är minst lika stor som dess integral, eller ersätt den enda uppsättningen $S$ med en familj av uppsättningar.

Beräkningskomplexitet

Ett beräkningsproblem relaterat till Blichfeldts teorem har visat sig vara komplett för PPP-komplexitetsklassen och därför osannolikt att vara lösbart i polynomtid. Problemet tar som indata en uppsättning heltalsvektorer som utgör grunden för ett $d$ -dimensionellt gitter $\Lambda$ , och en uppsättning $S$ av heltalsvektorer, implicit representerade av en boolesk krets för att testa om en given vektor tillhör $S$ . Det krävs att kardinaliteten för $S$ , dividerat med volymen av den fundamentala parallellotopen av ${\displaystyle \Lambda } ,$ är minst en, från vilken en diskret version av Blichfeldts sats antyder att $S$ inkluderar ett par punkter vars skillnad tillhör $\Lambda$ . Uppgiften är att hitta antingen ett sådant par, eller en punkt av $S$ som själv tillhör $\Lambda$ . Beräkningshårdheten för denna uppgift motiverar konstruktionen av en kandidat för en kollisionssäker kryptografisk hashfunktion .

Se även

• Punktplanimeter , en anordning för att uppskatta arean av en form genom att räkna gitterpunkterna som den innehåller
• Picks teorem , ett mer exakt förhållande mellan area och gitterpunkter täckta av en polygon med gitterpunktshörn

externa länkar

• Weisstein, Eric W. , "Blichfeldt's Theorem" , MathWorld