Erdős–Tetali-satsen

I additiv talteorin , ett område av matematik , är Erdős-Tetali-teorem en existenssats som gäller ekonomiska additivbaser av varje ordning. Mer specifikt sägs det att för varje fast heltal $h\geq 2$ finns det en delmängd av de naturliga talen ${\mathcal {B}}\subseteq \mathbb {N}$ tillfredsställande

$$r_{{\mathcal {B}},h}(n)\asymp \log n,$$

där $r_{{\mathcal {B}},h}(n)$ anger antalet sätt som ett naturligt tal n kan uttryckas som summan av h element i B .

Teoremet är uppkallat efter Paul Erdős och Prasad V. Tetali , som publicerade den 1990.

Motivering

Den ursprungliga motiveringen för detta resultat tillskrivs ett problem som S. Sidon ställde 1932 på ekonomiska grunder . En additiv bas ${\mathcal {B}}\subseteq \mathbb {N}$ kallas ekonomisk (eller ibland tunn ) när den är en additiv grund av ordningen h och

$r_{{\mathcal {B}},h}(n)\ll _{\varepsilon }n^{\varepsilon }$

för varje $\varepsilon >0$ . Med andra ord, dessa är additiva baser som använder så få tal som möjligt för att representera ett givet n , och ändå representerar varje naturligt tal. Besläktade begrepp inkluderar $B_{h}[g]$ -sekvenser och Erdős–Turán-förmodan om additivbaser .

Sidons fråga var om det finns en ekonomisk grund för order 2. Ett positivt svar gavs av P. Erdős 1956 och löste fallet h = 2 i satsen. Även om den allmänna versionen ansågs vara sann, förekom inga fullständiga bevis i litteraturen före tidningen av Erdős och Tetali.

Idéer i beviset

Beviset är ett exempel på den probabilistiska metoden och kan delas in i tre huvudsteg. Först börjar man med att definiera en slumpmässig sekvens $\omega \subseteq \mathbb {N}$ med

$\Pr(n\in \omega )=C\cdot n^{{\frac {1}{h} }-1}(\log n)^{\frac {1}{h}},$

där $C>0$ är någon stor reell konstant, $h\geq 2$ är ett fast heltal och n är tillräckligt stort så att formeln ovan är väldefinierad. En detaljerad diskussion om sannolikhetsutrymmet förknippat med denna typ av konstruktion kan hittas på Halberstam & Roth (1983). För det andra visar man då att det förväntade värdet av den slumpmässiga variabeln $r_{\omega ,h}(n)$ har ordningen log . Det är,

$\mathbb {E} (r_{\omega ,h}(n))\asymp \log n.$

Slutligen visar man att $r_{\omega ,h}(n)$ nästan säkert koncentreras kring sitt medelvärde. Mer explicit:

$\Pr {\big (}\exists c_{1},c_{2}>0~|~{\text{för alla stora }}n\in \mathbb {N} ,~c_{ 1}\mathbb {E} (r_{\omega ,h}(n))\leq r_{\omega ,h}(n)\leq c_{2}\mathbb {E} (r_{\omega ,h} (n)){\big )}=1$

Detta är det kritiska steget i bevisningen. Ursprungligen behandlades det med hjälp av Jansons ojämlikhet , en typ av koncentrationsojämlikhet för multivariata polynom. Tao & Vu (2006) presenterar detta bevis med en mer sofistikerad tvåsidig koncentrationsojämlikhet av V. Vu (2000), vilket förenklar detta steg relativt sett. Alon & Spencer (2016) klassificerar detta bevis som en instans av Poisson-paradigmet.

Förhållande till Erdős–Turán-förmodan om tillsatsbaser

Huvudartikel: Erdős–Turán gissningar om tillsatsbaser

Olöst problem i matematik :

Låt ${\textstyle h\geq 2}$ vara ett heltal. Om ${\textstyle {\mathcal {B}}\subseteq \mathbb {N} }$ är en oändlig mängd så att ${\textstyle r_{{\mathcal {B}},h }(n)>0}$ för varje n , betyder detta att:

$\limsup _{n\to \infty }{\frac {r_{{\mathcal {B}},h}(n)}{ \log n}}>0$ ?

(fler olösta problem i matematik)

Den ursprungliga Erdős–Turán gissningen om additiv baser säger, i sin mest allmänna form, att om ${\textstyle {\mathcal {B}}\subseteq \mathbb {N} }$ är en additiv grund av ordningen h då

$\limsup _{n\to \infty }r_{{\mathcal {B}},h}(n)=\infty ;$

det vill säga ${\textstyle r_{{\mathcal {B}},h}(n)}$ kan inte begränsas. I sin uppsats från 1956 frågade P. Erdős om det kunde vara så

$\limsup _{n\to \infty }{\frac {r_{{\mathcal {B}},2}(n)}{ \log n}}>0$

närhelst ${\mathcal {B}}\subseteq \mathbb {N}$ är en additiv grund för ordning 2. Med andra ord, detta säger att ${\textstyle r_{ {\mathcal {B}},2}(n)}$ är inte bara obegränsad, utan att ingen funktion mindre än log kan dominera ${\textstyle r_{{\mathcal {B}},2} (n)}$ . Frågan sträcker sig naturligtvis till $h\geq 3$ , vilket gör den till en starkare form av Erdős–Turán-förmodan på additiv bas. På sätt och vis är det som förmodas att det inte finns några tillsatsbaser som är väsentligt mer ekonomiska än de som garanteras existera av Erdős-Tetali-satsen.

Ytterligare utvecklingar

Beräkningsbara ekonomiska baser

Alla kända bevis för Erdős-Tetali-satsen är, till följd av det oändliga sannolikhetsutrymmets natur, icke-konstruktiva bevis . Kolountzakis (1995) visade dock att det finns en rekursiv mängd ${\mathcal {R}}\subseteq \mathbb {N}$ som uppfyller $r_ {{\mathcal {R}},2}(n)\asymp \log n$ så att ${\mathcal {R}}\cap \{0,1, \ldots ,n\}$ tar polynomtid i n att beräknas. Frågan för $h\geq 3$ förblir öppen.

Ekonomiska subbaser

Givet en godtycklig additiv bas ${\displaystyle {\mathcal {A}}\subseteq \mathbb {N} } ,$ kan man fråga sig om det finns ${\mathcal {B}}\subseteq {\ mathcal {A}}$ så att ${\mathcal {B}}$ är en ekonomisk grund. V. Vu (2000) visade att detta är fallet för Waring-baser ${\displaystyle \mathbb {N} ^{\wedge }k:=\{0 ^{k},1^{k},2^{k},\ldots \}} ,$ där det för varje fast k finns ekonomiska subbaser av $\mathbb {N} ^{\wedge }k$ av ordningen $s$ för varje $s\geq s_{k}$ , för någon stor beräkningsbar konstant $s_{k}$ .

Andra tillväxttakt än stock

En annan möjlig fråga är om liknande resultat gäller för andra funktioner än logg. Det vill säga att fixera ett heltal $h\geq 2$ , för vilka funktioner f kan vi hitta en delmängd av de naturliga talen ${\mathcal {B}}\subseteq \mathbb {N }$ uppfyller $r_{{\mathcal {B}},h}(n)\asymp f(n)$ ? Det följer av ett resultat av C. Táfula (2019) att om f är en lokalt integrerbar , positiv reell funktion som uppfyller

• ${\frac {1}{x}}\int _{1}^{x}f(t)\,\mathrm {d} t\asymp f(x)$ , och
• $\log x\ll f(x)\ll x^{\frac {1}{h-1}}( \log x)^{-\varepsilon }$ för vissa $\varepsilon >0$ ,

då finns det en additiv bas ${\mathcal {B}}\subseteq \mathbb {N}$ av ordningen h som uppfyller $r_{{ \mathcal {B}},h}(n)\asymp f(n)$ . Det minimala fallet f ( x ) = log x återvinner Erdős–Tetalis sats.

Se även

• Erdős–Fuchs teorem : För alla icke-noll ${\displaystyle C\in \mathbb {R} } ,$ finns det ingen mängd ${\mathcal {B}}\subseteq \mathbb {N}$ som uppfyller $\textstyle {\sum _{n\leq x}r_ {{\mathcal {B}},2}(n)=Cx+o\left(x^{1/4}\log(x)^{-1/2}\höger)}$ .
• Erdős–Turán gissningar på additiva baser : Om ${\mathcal {B}}\subseteq \mathbb {N}$ är en additiv grund av ordning 2, då $r_{{\mathcal {B}},2}(n)\neq O(1)$ .
• Warings problem , problemet med att representera tal som summor av k -potenser, för fast $k\geq 2$ .

• Erdős, P. ; Tetali, P. (1990). "Representationer av heltal som summan av k termer". Slumpmässiga strukturer och algoritmer. 1 (3): 245–261. doi : 10.1002/rsa.3240010302 .
•     Halberstam, H. ; Roth, KF (1983). Sekvenser . Springer New York. ISBN 978-1-4613-8227-0 . OCLC 840282845 .
•     Alon, N .; Spencer, J. (2016). Den probabilistiska metoden (4:e upplagan). Wiley. ISBN 978-1-1190-6195-3 . OCLC 910535517 .
•     Tao, T .; Vu, V. (2006). Additiv kombinatorik . Cambridge University Press. ISBN 0521853869 . OCLC 71262684 .