Een eigenschap van prime-congruent tot $ 7 \ pmod 8 $ uitgedrukt als sommen van vier vierkanten.

Deze vraag is gemotiveerd door vraag Opsommingen van representaties van een integer als een som van vierkanten  . Overweeg een priemgetal $ p $ congruent naar $ 7 $ modulo $ 8 $. Het kan dus worden geschreven op exact $ (p + 1)/2 $ manieren als een som van vierkanten van vier strikt positieve gehele getallen.

Een manier om te proberen alle oplossingen van $ p = a ^ 2 + b ^ 2 + c ^ 2 + d ^ 2 $ met $ (a, b, c, d) \ in \ mathbb N ^ 4 $ te genereren, is om te starten met een willekeurige oplossing (bijvoorbeeld verkregen door kristalbol kijken) $ (a, b, c, d) $, to herstel een van de parameters, zeg $ a $, en ontbind $ b ^ 2 + c ^ 2 + d ^ 2 $ anders als een som van drie vierkanten, indien mogelijk.

Dit werkt schijnbaar altijd. Anders vermeld, associeer met een prime $ p \ equiv 7 \ pmod 8 $ een grafiek met $ (p + 1)/2 $ hoekpunten geïndexeerd door alle verschillende decomposities $ p = a ^ 2 + b ^ 2 + c ^ 2 + d ^ 2 $ met $ a, b, c, d \ in \ mathbb N $ en teken een rand tussen twee hoekpunten $ (a, b, c, d), (a ', b', c ', d') $ if de kruising van $ \ lbrace a, b, c, d \ rbrace $ en $ \ lbrace a ', b', c ', d' \ rbrace $ is niet leeg. Is deze grafiek altijd verbonden? Zo ja, wat is meestal de diameter van deze grafiek?

10
Ja, ik heb alle primes van minder dan 500 gecontroleerd en de verbondenheid wordt veel gemakkelijker voor grotere prime-lenzen omdat alle coëfficiënten kleiner zijn dan $ \ sqrt p $. Als de grafiek niet is verbonden, dan bestaat er een partitie van $ \ lbrace 1, \ dots, \ lfloor \ sqrt {p} \ rfloor \ rbrace $ in twee disjuncte subsets $ A \ cup B $ met één aangesloten component met alleen coëfficiënten in $ A $ en alle andere componenten alleen coëfficiënten in $ B $. Aangezien het aantal hoekpunten veel groter is dan $ \ sqrt {p} $ is dit zeer onwaarschijnlijk.
toegevoegd de auteur Ashley Clark, de bron
Will Jagy, de grafieken met randen bij viervierlingen die twee gemeenschappelijke items delen, zijn waarschijnlijk vrij vaak niet verbonden, bijvoorbeeld. als er een viervoudige bestaat, zodat $ x ^ 2 + y ^ 2 $ een prime of tweemaal een prime is voor alle zes (of minder) keuzes van $ x, y $ bij een oplossing $ (a, b, c, d ) $. Zo'n viervoudige komt overeen met een geïsoleerde hoek in je grafiek.
toegevoegd de auteur Ashley Clark, de bron
Wadim, meer dan $ \ mathbb {Z} $ het aantal is $ 8 (p + 1) $, dus ik neem aan dat Roland gelijk heeft (aangezien deze prime-lenzen niet met minder dan 4 vierkanten kunnen worden gerepresenteerd, voor positieve oplossingen die we met 16 moeten delen) ...
toegevoegd de auteur terdon, de bron
Roland, merk op dat in de eerdere vraag $ (p + 1)/2 $ werd geteld over $ \ mathbb Z $, niet $ \ mathbb N $ zoals je nu hebt. Er zijn dus minder $ (p + 1)/2 $ hoekpunten! Heb je enig computationeel bewijs dat de grafiek is verbonden? (Ik betwijfel echt of het waar is, maar ik zal zelf geen programma uitvoeren.)
toegevoegd de auteur xecaps12, de bron
Bedankt, Vladimir! Mijn draadloze thuis is te traag om te controleren met het vorige antwoord. Maar toch: is er enig computationeel bewijs om de grafiek met elkaar te verbinden?
toegevoegd de auteur xecaps12, de bron
Roland, je heuristieken (en verificatie voor kleine $ p $) zijn voldoende bewijs. Ik ben overtuigd.
toegevoegd de auteur xecaps12, de bron
Je kunt ook proberen een rand te tekenen als de vierlingen twee ingangen gemeenschappelijk hebben, enige interpretatie vereist in het geval van herhaalde invoer, bijvoorbeeld als $ p \ equiv 1 \ pmod 3 $ we gegarandeerd $ p = u ^ 2 + 3 v ^ 2. $ Denk eraan dat elk oneven getal $ n $ wordt weergegeven als $ n = x ^ 2 + y ^ 2 + 2 z ^ 2. $
toegevoegd de auteur Will Jagy, de bron
Bedankt, Roland. Ik heb zojuist het probleem opgelost, omdat ik de jouwe erg leuk vond. Ik vertelde over het Hurwitz-probleem in mijn antwoord, het heeft een ingebouwde bosstructuur. Ik heb ook een langetermijnbelang in een aantal theoretische grafieken die ik heb bedacht (valenties moeten oneindig zijn), er is een eenvoudige test voor het plaatsen van een grens tussen twee geslachten van integraal positieve driedubbele vormen, en ik zou graag willen weten over verbondenheid . In mijn geval kunnen verbonden componenten overeenkomen met waarden van invarianten, ik ben er nog steeds niet zeker van. Het lijkt voldoende eenvoudig om hoekpunten bij elkaar te voegen zodat het geheel toch verbonden kan zijn.
toegevoegd de auteur Will Jagy, de bron

2 antwoord

Te lang voor een opmerking. Je probleem herinnert me hieraan. Als er iets direct nuttigs opkomt voor uw probleem, zal ik u dit natuurlijk laten weten.

Staat u mij toe uw aandacht te vestigen op de fascinerende vergelijking van Markov-Hurwitz Diophantine $$ x_1 ^ 2 + x_2 ^ 2 + \ cdots + x_n ^ 2 = a \; x_1 x_2 \ ldots x_n $$ in positieve gehele getallen, met $$ 1 \ leq a \ leq n $$ zoals getoond door Hurwitz (1907).

See my answer to Numbers characterized by extremal properties especially the Markov tree, Markov (1880) http://en.wikipedia.org/wiki/Markov_number

Als $ x_1 $ bijvoorbeeld behoorlijk groot is, kan het worden vervangen door $ a x_2 x_3 \ ldots x_n - x_1 $ om een ​​andere oplossing met kleinere waarden te geven. Dit proces kan herhaald worden totdat er een "fundamentele oplossing" komt die aan een bepaalde ongelijkheid voldoet: zo besteld dat $ x_1 $ inderdaad de grootste is, een fundamentele oplossing heeft $$ 2 x_1 \ leq a x_2 x_3 \ ldots x_n. $$

Dus een fundamentele oplossing is de wortel van een boom van oplossingen voor vast paar $ (n, a). $ De eerste keer dat een paar $ (n, a) $ een losgemaakt bos vereist is $ (n = 14, a = 1 ) $ één boom met (aflopend volgorde) root $ (6,4,3,1,1, \ ldots) $ en een andere boom met bestelde root $ (3,3,2,2,1,1, \ ldots). $

Zoveel dingen ... mijn vermoeden dat, voor een fundamentele oplossing in niet-afnemende volgorde, $ 5 x_1 ^ 2 \ leq 9 (n + 6). $ Eindelijk de rechterkant $ a \; x_1 x_2 \ ldots x_n $ kan worden vervangen door elk van die symmetrische polynomen waarvan alle exponenten maximaal één zijn, omdat we nog steeds bomen krijgen.

2
toegevoegd

Ik zal niet ingaan op de kwestie van de verbondenheid van de grafiek, maar (ervan uitgaande dat het verbonden is!) Kan ik misschien wat intuïtie bieden over het probleem van de grafiekdiameter. Je zou probabilistische methoden kunnen gebruiken om een ​​goede band te krijgen. U kent het aantal hoekpunten (p + 1)/2 al. U moet de kans op randconnectiviteit berekenen.

Als $ R_3 (n) $ het aantal manieren is waarop 'n' kan worden weergegeven als de som van 3 vierkanten, moet de graad van een hoekpunt na het doorlopen van alle vier de coëfficiënten $ zijn [Sum_ {i = 1} ^   {4} (R_3 (p- coeff_i) - 1) ] $.

Het aantal totale randen in de grafiek wordt bovenaan begrensd door $ [Sum_ {i = 1} ^   {\ sqrt {p}} (R_3 (i) (R_3 (i) - 1))/2 ] $

Ik kan de verdeling van deze som-van-vierkanten-grafiek niet visualiseren, maar je kunt de methoden aanpassen die zijn toegepast in http://www1.cs.columbia.edu/~coms6998/Notes/lecture3.pdf

Zie ook

  1. Fan Chung's summary on graph diameter http://math.ucsd.edu/~fan/research/diad.pdf
  2. Béla Bollobás. The Diameter of Random Graphs. Transactions of the American Mathematical Society, Vol. 267, No. 1 (Sep., 1981), pp. 41-52 Published by: American Mathematical Society Stable URL: http://www.jstor.org/stable/1998567
  3. Edgar Palmer's book Graphical Evolution
0
toegevoegd