Erdős–Anning theorem
એર્ડોસ-એન્નિંગ પ્રમેય જણાવે છે કે સમતલમાં અનંત સંખ્યામાં બિંદુઓ પરસ્પર પૂર્ણાંક અંતર ત્યારે જ મેળવી શકે છે જ્યારે તમામ બિંદુઓ એક સીધી રેખા પર હોય. તેનું નામ પોલ એર્દોસ અને નોર્મન એચ. એન્નિંગના નામ પરથી રાખવામાં આવ્યું છે, જેમણે 1945માં તેનો પુરાવો પ્રકાશિત કર્યો હતો. તર્કસંગતતા વિરુદ્ધ અખંડિતતા જો કે પૂર્ણાંક અંતર ધરાવતા બિંદુઓનો કોઈ અનંત બિન-સમરેખીય સમૂહ હોઈ શકતો નથી, તેમ છતાં એવા બિંદુઓના અનંત બિન-સમરેખીય સમૂહ હોય છે જેમના અંતર તર્કસંગત સંખ્યાઓ હોય છે. દાખલા તરીકે, 3-4-5 જમણા ત્રિકોણમાં તીક્ષ્ણ ખૂણા દ્વારા વારંવાર ફરતા એકમ વર્તુળ પરના બિંદુઓના ઉપગણમાં આ ગુણધર્મ હોય છે. તે વર્તુળમાં ગાઢ સમૂહ બનાવે છે. (હજુ પણ વણઉકેલાયેલી) એર્દોસ-ઉલામ સમસ્યા પૂછે છે કે શું એકબીજાથી તર્કસંગત અંતર પર બિંદુઓનો સમૂહ અસ્તિત્વમાં હોઈ શકે છે જે સમગ્ર યુક્લિડિયન સમતલ માટે ગાઢ સમૂહ બનાવે છે. એર્ડોસના જણાવ્યા અનુસાર, સ્ટેનિસ્લો ઉલામ એર્ડોસ-એનિંગ પ્રમેય વિશે એર્ડોસ પાસેથી સાંભળ્યા પછી આ પ્રશ્ન પૂછવા માટે પ્રેરિત થયા હતા. એકબીજાથી તર્કસંગત અંતર પર બિંદુઓના કોઈપણ મર્યાદિત સમૂહ S માટે, એકબીજાથી પૂર્ણાંક અંતર પર બિંદુઓનો સમાન સમૂહ શોધવો શક્ય છે, S માં અંતરના ઓછામાં ઓછા સામાન્ય છેદના પરિબળ દ્વારા S ને વિસ્તૃત કરીને. આ રીતે એકમ વર્તુળની રચનાના મર્યાદિત ઉપગણને વિસ્તૃત કરીને, એકબીજાથી પૂર્ણાંક અંતર સાથે બિન-સમરેખીય બિંદુઓના મનસ્વી રીતે મોટા મર્યાદિત સમૂહ બનાવી શકાય છે. જો કે, S માં વધુ બિંદુઓનો સમાવેશ કરવાથી વિસ્તરણ પરિબળમાં વધારો થઈ શકે છે, તેથી આ રચના તર્કસંગત અંતર પર બિંદુઓના અનંત સમૂહને પૂર્ણાંક અંતર પર બિંદુઓના અનંત સમૂહમાં રૂપાંતરિત કરવાની મંજૂરી આપતી નથી. પુરાવા એર્ડોસ-એનિંગ પ્રમેયના મૂળ પ્રકાશનના થોડા સમય પછી, એર્ડોસે નીચેના સરળ પુરાવા પૂરા પાડ્યા. સાબિતીમાં વળાંકની પ્રણાલી શોધવાનો સમાવેશ થાય છે જેથી સમૂહનો દરેક બિંદુ બે વળાંકના પાર પર રહે. પૂર્ણાંક અંતર સાથેના બિંદુઓના સમૂહને જોતાં, બધા એક રેખા પર નહીં, મનસ્વી રીતે ત્રણ બિંદુઓ દ્વારા રચાયેલ ત્રિકોણ પસંદ કરો. ચાલો યુક્લિડિયન અંતર કાર્યને દર્શાવીએ. કોઈપણ આપેલ બિંદુ માટે, ત્રિકોણ અસમાનતા દ્વારા પૂર્ણાંક મહત્તમ હોય છે. આમ, સાથે સ્વરૂપના સમીકરણો દ્વારા વ્યાખ્યાયિત હાયપરબોલાઓમાંથી એક આવેલું છે. સપ્રમાણ દલીલ દ્વારા, સ્વરૂપના સમીકરણો દ્વારા વ્યાખ્યાયિત હાયપરબોલાઓમાંથી એક પર પણ હોવું જોઈએ. બે હાયપરબોલા ધરાવતા એકબીજા સાથે મેળ ખાતા નથી, તેથી તે એક બિંદુ હોવું જોઈએ જ્યાં તેઓ એકબીજાને છેદે છે. બેઝઆઉટના પ્રમેય અનુસાર, દરેક પસંદગી માટે અને વધુમાં વધુ ચાર આંતરછેદ બિંદુઓની પસંદગીઓ છે. કારણ કે આપેલ દરેક બિંદુ આ આંતરછેદ બિંદુઓમાંથી એક હોવું આવશ્યક છે, આપેલ બિંદુઓના સમૂહમાં મોટાભાગના બિંદુઓ પર મર્યાદિત સંખ્યા હોવી આવશ્યક છે. એ જ પુરાવો દર્શાવે છે કે, જ્યારે પૂર્ણાંક અંતર ધરાવતા બિંદુઓના સમૂહનો વ્યાસ હોય, ત્યારે મોટાભાગના બિંદુઓ હોય છે. સમાન સાબિતીનો ઉપયોગ કરીને પરંતુ હાયપરબોલા પરિવારોને વ્યાખ્યાયિત કરવા માટે ઉપયોગમાં લેવાતા બિંદુઓની જોડીની વધુ સાવચેતીપૂર્વક પસંદગી સાથે આ બાઉન્ડ ઓનની દ્વિઘાત અવલંબનમાં સુધારો કરી શકાય છેઃ પૂર્ણાંક અંતર અને વ્યાસ સાથે સેટ કરેલ દરેક બિંદુ કદ ધરાવે છે. જો કે, બિંદુઓ વચ્ચેના લઘુતમ અંતર દ્વારા બદલવું શક્ય નથીઃ પૂર્ણાંક અંતર અને લઘુતમ અંતર બે સાથે મનસ્વી રીતે મોટા બિન-સમરેખીય બિંદુ સમૂહો અસ્તિત્વ ધરાવે છે. અવિભાજ્ય અંતર સાથેના મહત્તમ બિંદુ સમૂહો પ્રમેય જણાવવાની વૈકલ્પિક રીત એ છે કે પૂર્ણાંક અંતરવાળા સમતલમાં બિંદુઓના બિન-સમરેખીય સમૂહને માત્ર મર્યાદિત રીતે ઘણા વધારાના બિંદુઓ ઉમેરીને વિસ્તૃત કરી શકાય છે, તે પહેલાં કોઈ વધુ બિંદુઓ ઉમેરી શકાતા નથી. પૂર્ણાંક કોઓર્ડિનેટ્સ અને પૂર્ણાંક અંતર બંને સાથેના બિંદુઓનો સમૂહ, જેમાં બંને ગુણધર્મોને જાળવી રાખીને વધુ ઉમેરી શકાતું નથી, તે એર્ડોસ-ડાયોફેન્ટાઇન આલેખ બનાવે છે. પૂર્ણાંક અંતર સાથે પૂર્ણાંક બિંદુઓનો આપેલ સમૂહ એર્ડોસ-ડાયોફેન્ટાઇન આલેખ બનાવે છે કે કેમ તે તપાસવા માટે એર્ડોસ-એનિંગ પ્રમેયના પુરાવાનો ઉપયોગ અલ્ગોરિધમમાં થઈ શકે છેઃ ફક્ત સાબિતીમાં ઉપયોગમાં લેવાતા હાયપરબોલા ના તમામ ક્રોસિંગ બિંદુઓ શોધો, અને તપાસો કે પરિણામી બિંદુઓમાંથી કોઈપણમાં આપેલ સમૂહથી પૂર્ણાંક કોઓર્ડિનેટ્સ અને પૂર્ણાંક અંતર પણ છે કે કેમ. સંદર્ભો સમતલ ભૂમિતિના અંકગણિત સમસ્યાઓ અલગ ગણિતમાં પ્રમેયો પુરાવા ધરાવતા લેખો અલગ ભૂમિતિમાં પ્રમેયો એન્નિંગ પ્રમેય