Erdős – Fuchsova věta - Erdős–Fuchs theorem

v matematika, v oblasti teorie aditivních čísel, Erdős – Fuchsova věta je prohlášení o počtu způsobů, jakými lze čísla reprezentovat jako součet prvků daného aditivní základ, s uvedením, že průměrné pořadí tohoto čísla nemůže být příliš blízko tomu, aby bylo a lineární funkce.

Věta je pojmenována po Paul Erdős a Wolfgang Heinrich Johannes Fuchs, který ji publikoval v roce 1956.

Prohlášení

Nechat ${displaystyle {mathcal {A}} subseteq mathbb {N}}$ být nekonečnou podmnožinou přirozená čísla a ${displaystyle r _ {{mathcal {A}}, h} (n)}$ své reprezentační funkce, což označuje počet způsobů, jak přirozené číslo ${displaystyle n}$ lze vyjádřit jako součet ${displaystyle h}$ prvky ${displaystyle {mathcal {A}}}$ (s přihlédnutím k objednávce). Poté zvážíme funkce akumulace

který počítá (také s ohledem na pořadí) počet řešení ${displaystyle k_ {1} + cdots + k_ {h} leqslant x}$, kde ${displaystyle k_ {1}, ldots, k_ {h} v {mathcal {A}}}$. Věta pak říká, že pro jakýkoli daný ${displaystyle c> 0}$vztahnemůže být spokojený; to znamená, že existuje Ne ${displaystyle {mathcal {A}} subseteq mathbb {N}}$ splňující výše uvedený odhad.

Věty typu Erdős – Fuchs

Erdős – Fuchsova věta má zajímavou historii precedentů a zobecnění. V roce 1915 to již bylo známo G. H. Hardy^[1] že v případě sekvence ${displaystyle {mathcal {Q}}: = {0,1,4,9, ldots}}$ z perfektní čtverce jeden má

Tento odhad je o něco lepší než ten, který popsali Erdős – Fuchs, ale za cenu mírné ztráty přesnosti dosáhli P. Erdős a W. H. J. Fuchs ve svém výsledku úplné obecnosti (alespoň pro tento případ ${displaystyle h = 2}$). Dalším důvodem, proč je tento výsledek tak oslavovaný, může být skutečnost, že v roce 1941 P. Erdős a P. Turán^[2] domníval se, že s výhradou stejných hypotéz jako v uvedené větě, vztahnemohl držet. Tato skutečnost zůstala neprokázaná až do roku 1956, kdy Erdős a Fuchs získali svou větu, která je ještě silnější než dříve předpokládaný odhad.

Vylepšené verze pro h = 2

Tato věta byla rozšířena v mnoha různých směrech. V roce 1980 A. Sárközy^[3] považovány za dvě sekvence, které jsou v určitém smyslu „blízké“. Dokázal následující:

• Teorém (Sárközy, 1980). Li ${displaystyle {mathcal {A}} = {a_ {1}$ a ${displaystyle {mathcal {B}} = {b_ {1}$ jsou dvě nekonečné podmnožiny přirozených čísel s ${displaystyle a_ {i} -b_ {i} = o {ig (} a_ {i} ^ {1/2} log (a_ {i}) ^ {- 1} {ig)}}$, pak ${displaystyle | {(i, j): a_ {i} + b_ {j} leqslant n} | = cn + o {ig (} n ^ {1/4} log (n) ^ {- 1/2} { ig)}}$ nemůže držet žádnou konstantu ${displaystyle c> 0}$.

V roce 1990 H. L. Montgomery a R. C. Vaughan^[4] byli schopni odstranit záznam z pravé strany původního prohlášení Erdőse – Fuchse, což ukazuje

nemůže držet. V roce 2004 G. Horváth^[5] rozšířil oba tyto výsledky a prokázal následující:

• Teorém (Horváth, 2004). Li ${displaystyle {mathcal {A}} = {a_ {1}$ a ${displaystyle {mathcal {B}} = {b_ {1}$ jsou nekonečné podmnožiny přirozených čísel s ${displaystyle a_ {i} -b_ {i} = o {ig (} a_ {i} ^ {1/2} {ig)}}$ a ${displaystyle | {mathcal {A}} cap [0, n] | - | {mathcal {B}} cap [0, n] | = O (1)}$, pak ${displaystyle | {(i, j): a_ {i} + b_ {j} leqslant n} | = cn + o {ig (} n ^ {1/4} {ig)}}$ nemůže držet žádnou konstantu ${displaystyle c> 0}$.

Obecný případ (h ≥ 2)

Přirozené zobecnění na Erdős – Fuchsovu větu, jmenovitě pro ${displaystyle hgeqslant 3}$, je známo, že má stejnou sílu jako Montgomery – Vaughanova verze. Ve skutečnosti M. Tang^[6] v roce 2009 ukázal, že za stejných podmínek jako v původním prohlášení Erdőse – Fuchse pro všechny ${displaystyle hgeqslant 2}$ vztah

nemůže držet. Jiným směrem, v roce 2002, G. Horváth^[7] dal přesnou generalizaci výsledku Sárközy z roku 1980, což ukázal

• Teorém (Horváth, 2002) Li ${displaystyle {mathcal {A}} ^ {(j)} = {a_ {1} ^ {(j)}$ (${displaystyle j = 1, ldots, k}$) jsou ${displaystyle k}$ (alespoň dvě) nekonečné podmnožiny přirozených čísel a platí následující odhady:

1. ${displaystyle a_ {i} ^ {(1)} - a_ {i} ^ {(2)} = o {ig (} (a_ {i} ^ {(1)}) ^ {1/2} log (a_ {i} ^ {(1)}) ^ {- k / 2} {ig)}}$
2. ${displaystyle | {mathcal {A}} ^ {(j)} cap [0, n] | = Theta {ig (} | {mathcal {A}} ^ {(1)} cap [0, n] | {ig )}}$ (pro ${displaystyle j = 3, ldots, k}$)

pak vztah:

${displaystyle | {(i_ {1}, ldots, i_ {k}): a_ {i_ {1}} ^ {(1)} + ldots + a_ {i_ {k}} ^ {(k)} leqslant n, ~ a_ {i_ {j}} ^ {(j)} v {mathcal {A}} ^ {(j)} (j = 1, ldots, k)} | = cn + o {ig (} n ^ {1 / 4} log (n) ^ {1-3k / 4} {ig)}}$

nemůže držet žádnou konstantu ${displaystyle c> 0}$.

Nelineární aproximace

Ještě dalším směrem, ve kterém lze Erdős-Fuchsovu větu vylepšit, je uvažování o aproximacích ${displaystyle s _ {{mathcal {A}}, h} (n)}$ jiný než ${displaystyle cn}$ pro některé ${displaystyle c> 0}$. V roce 1963 P. T. Bateman E. E. Kohlbecker a J. P. Tull^[8] se ukázal jako mírně silnější verze následujících:

• Teorém (Bateman – Kohlbecker – Tull, 1963). Nechat ${displaystyle L (x)}$ být pomalu se měnící funkce což je buď konvexní nebo konkávní od nějakého bodu kupředu. Potom za stejných podmínek jako v původní Erdős – Fuchsově teorém nemůžeme mít ${displaystyle s _ {{mathcal {A}}, 2} (n) = nL (n) + o {ig (} n ^ {1/4} log (n) ^ {- 1/2} L (n) ^ {alpha} {ig)}}$, kde ${displaystyle alpha = 3/4}$ -li ${displaystyle L (x)}$ je ohraničený a ${displaystyle 1/4}$ v opačném případě.

Na konci příspěvku je rovněž poznamenáno, že je možné rozšířit jejich metodu o získání výsledků s ohledem na výsledky ${displaystyle n ^ {gamma}}$ s ${displaystyle gamma eq 1}$, ale tyto výsledky nejsou považovány za dostatečně konečné.

Viz také

• Erdős – Tetaliho věta: Pro všechny ${displaystyle hgeq 2}$, existuje sada ${displaystyle {mathcal {A}} subseteq mathbb {N}}$ který uspokojuje ${displaystyle r _ {{mathcal {A}}, h} (n) = Theta (log (n))}$. (Existence ekonomických základen)
• Erdős – Turán dohad o aditivních základech: Pokud ${displaystyle {mathcal {A}} subseteq mathbb {N}}$ je tedy aditivní základ objednávky 2 ${displaystyle r _ {{mathcal {A}}, 2} (n) eq O (1)}$. (Báze nemohou být také hospodárný)

Reference

• Erdős, P.; Fuchs, W. H. J. (1956). „K problému teorie aditivních čísel“. J. London Math. Soc. 31 (1): 67–73. doi:10.1112 / jlms / s1-31.1.67. hdl:2027 / mdp. 39015095244037.
• Newman, D. J. (1998). Teorie analytických čísel. GTM. 177. New York: Springer. 31–38. ISBN  0-387-98308-2.
• Halberstam, H.; Roth, K.F. (1983) [1966]. Sekvence (2. vyd.). Berlín, New York: Springer-Verlag. ISBN  978-0-387-90801-4. PAN  0210679.

^ Hardy, G. H. (1915). "Na výraz čísla jako součet dvou čtverců". Kvart. J. Math. 46: 263–83.

^ Erdős, P .; Turán, P. (1941). „K problému Sidona v teorii aditivních čísel a některých souvisejících problémech“. J. London Math. Soc. 16: 212–5.

^ Sárközy, A. (1980). „K teorému Erdőse a Fuchse“. Acta Arith. 37: 333–338.

^ Montgomery, H.L .; Vaughan, R. C. (1990). „Na Erdős – Fuchsovu větu“. Pocta Paulovi Erdősovi. Cambridge Univ. Tisk: 331–338.

^ Horváth, G. (2004). "Vylepšení rozšíření věty o Erdős a Fuchs". Acta Math. Visel. 104: 27–37.

^ Tang, Min (2009). „O zevšeobecnění věty o Erdősovi a Fuchsovi“. Diskrétní matematika. 309: 6288–6293.

^ Horváth, G. (2002). „K teorému Erdőse a Fuchse“. Acta Arith. 103 (4): 321–328.

^ Bateman, P. T .; Kohlbecker, E. E .; Tull, J. P. (1963). „K teorému Erdőse a Fuchse v aditivní teorii čísel“. Proc. Dopoledne. Matematika. Soc. 14: 278–84.