On the Ellenberg-Gijswijt sequence that is an upper bound for the size of Su\ n bsets of, F[3] , with No Three-Term Arithemtical Progressions By Shalosh B. Ekhad In the brilliant paper "On large subsets of F_q^n with no Three-Term Arithmetic Progressions" by Jordan S. Ellenberg and Dion Gijswijt arxiv: 1605.09223v1 the authors prove that if M[d,n] is the sum of the coefficients from x^0 to \ x^d of the polynomial 2 n (x + x + 1) n then, for any d, the size of any subset of, F[3] , with no three-term arithmetical progressions is <= n 2 M[d/2, n] + 3 - M[d, n] 4 n Taking d to be , ---, and replacing n by 3m, it is easy to see that the abov\ 3 e is bounded by a constant time the sequence (2 m) 2 (3 m) A(m):=Coefficient of, x , in the polynomial , (x + x + 1) Thanks to the Almkvist-Zeilberger algorithm, the sequence A(m) satisfies the\ linear recurrence equation with polynomial coefficients of order, 2 243 (3 m + 5) (3 m + 2) (11 m + 20) (3 m + 4) (3 m + 1) (m + 1) A(m) - 18 3 2 (3 m + 5) (2 m + 1) (3 m + 4) (759 m + 2898 m + 3505 m + 1350) A(m + 1) + 16 (4 m + 5) (2 m + 3) (2 m + 1) (11 m + 9) (4 m + 7) (m + 2) A(m + 2) = 0 and in Maple notation: 243*(3*m+5)*(3*m+2)*(11*m+20)*(3*m+4)*(3*m+1)*(m+1)*A(m)-18*(3*m+5)*(2*m+1)*(3* m+4)*(759*m^3+2898*m^2+3505*m+1350)*A(m+1)+16*(4*m+5)*(2*m+3)*(2*m+1)*(11*m+9)* (4*m+7)*(m+2)*A(m+2) = 0 The growth-constant is the cubic root of the largest root of the algebraic e\ quation in, M 2 1024 M - 22356 M + 19683 = 0 and in Maple notation 1024*M^2-22356*M+19683 = 0 that happens to be equal to / 1/2\(1/3) |5589 891 33 | |---- + ---------| \512 512 / and in Maple notation (5589/512+891/512*33^(1/2))^(1/3) that equals 2.7551046130236330002 as you can see, this is less than, 3, . n so indeed the size of the largest such set it is exponentially less than, 3 The asymptotic expansion to order, 3, of the sequence A(m) is / 1/2\m / 1/2 1/2 |5589 891 33 | 1/2 | 141 33 (-3289 + 141 33 ) |---- + ---------| (1/m) |----------------- \512 512 / | 1/2 \-3289 + 141 33 1/2 34848 m 50917 33 3289 + ----------------- - -------------------------- - ----------------- 1/2 1/2 1/2 -3289 + 141 33 1056 m (-3289 + 141 33 ) -3289 + 141 33 1/2 3167435 33 77573 + ------------------------------ + ------------------------- 2 1/2 1/2 1672704 m (-3289 + 141 33 ) 288 m (-3289 + 141 33 ) \ 23293015 | + ------------------------------|/m 2 1/2 | 1368576 m (-3289 + 141 33 )/ and in Maple notation (-3289+141*33^(1/2))*(5589/512+891/512*33^(1/2))^m/m*(1/m)^(1/2)*(141/(-3289+ 141*33^(1/2))*33^(1/2)+34848*m/(-3289+141*33^(1/2))-50917/1056/m/(-3289+141*33^ (1/2))*33^(1/2)-3289/(-3289+141*33^(1/2))+3167435/1672704/m^2/(-3289+141*33^(1/ 2))*33^(1/2)+77573/288/m/(-3289+141*33^(1/2))+23293015/1368576/m^2/(-3289+141* 33^(1/2))) and in floating-point -2479.016667*20.91290101^m/m*(1/m)^(1/2)*(.9999999998-14.05718665*m+.30794694e-\ 2/m-.1125357686e-1/m^2) 1 Note that we even gained a factor of, ---- 1/2 n hence be have an improvement on Ellenberg-Gijswijt! For the sake our beloved OEIS, the first, 30, terms of the upper bound discussed at the beginning are (recall that we doing only n multiple of 3) [24, 414, 7629, 144846, 2799369, 54752283, 1080189015, 21451329486, 428215108452, 8584133217309, 172680811840143, 3483912569041251, 70466262482921823, 1428365834899683849, 29008380421482185529, 590114411488187489358, 12022561330005862713762, 245266390080480566237364, 5009585602954317350964858, 102432794755596084397430541, 2096559388061824512274802052, 42950602967175028719987870429, 880628934329870431079635074855, 18069649936370124321661161136947, 371034605472102661510648791525969, 7623678240448054059728048583324933, 156740101823565859758912644551445697, 3224357100399338409459993517428919425, 66364738897341779619260777766638882433, 1366621496429027248950682865721775882263] The first, 30, terms of the above-mentioned sequence, A(m) are [6, 90, 1554, 28314, 531531, 10171746, 197278710, 3864164634, 76265209410, 1514286194715, 30214037148840, 605291164452450, 12167372258235954, 245295416233065078, 4957582903412717754, 100415154461309072154, 2037807598445421087600, 41425434023770734693210, 843395941696973151430944, 17194486471905464578461339, 350980245625944872580414639, 7172364801498809426622861480, 146718655347358196215913715048, 3004097799554011107165885764706, 61562410565081026074368486374656, 1262585802844145323934147807558586, 25913382860618141894105783918270640, 532209030482261902123111588546317174, 10937414915281270912908404611777066434, 224906985257164615306455049149774541146] Finally, just for fun,, A(1000), equals 2474099474915100861758310825447354168990510343926130313140940221244451693388\ 882501953705850985266442195087673910773099903243358955610177670373279636\ 609278491930623625667365607544619939685839444379358149943073999633973695\ 222597339966928719403293249313508968134349539004999702686188738898865395\ 837375872366940499903726139246690553775378124079565128088768592398564238\ 451818392697331044102527039916415094645727295867678000277887807688904624\ 294025508371690007060892245705390401313049959812555859550568778381660253\ 564301961847606082970535593172604748513822384455912242824567830867320844\ 628872926122638363545575071570094572025183449174622000599632951309631833\ 598062249039303804397449902951051576825010116295318281168844862260191661\ 648817430826445745315332926405716561981492628150243012163492897286335445\ 445668918928098274973576034577507026930775443659003267879460495955656932\ 322630093566524848341595743332161756594583160360362545717932714329797335\ 475059388882436892092316299280096150981272963463073830732670030071141913\ 240543327194164650735647911644674019094704963678914927975890619811891697\ 188110204282142691815079676934389321079389231152297114007241694024576715\ 956382590404301062522011393301975023098535335458795032112893978293922410\ 737137379620478915997608469081413265028003937757802124636309429753480670\ 5597709065574398434 --------------------------------------------------- This ends this article that took, 0.650, seconds to generate.