On the Ellenberg-Gijswijt sequence that is an upper bound for the size of Su\ n bsets of, F[4] , 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 3 2 n (x + x + x + 1) n then, for any d, the size of any subset of, F[4] , with no three-term arithmetical progressions is <= n 2 M[d/2, n] + 4 - M[d, n] Taking d to be , 2 n, it is easy to see that the above is bounded by a const\ ant time the sequence m 3 2 m A(m):=Coefficient of, x , in the polynomial , (x + x + x + 1) Thanks to the Almkvist-Zeilberger algorithm, the sequence A(m) satisfies the\ linear recurrence equation with polynomial coefficients of order, 3 2 -16 (13 m + 33) (m + 2) (m + 1) A(m) - 4 (m + 2) (26 m + 105 m + 96) A(m + 1) 3 2 + (-143 m - 935 m - 2000 m - 1392) A(m + 2) + 2 (13 m + 20) (2 m + 5) (m + 3) A(m + 3) = 0 and in Maple notation: -16*(13*m+33)*(m+2)*(m+1)*A(m)-4*(m+2)*(26*m^2+105*m+96)*A(m+1)+(-143*m^3-935*m ^2-2000*m-1392)*A(m+2)+2*(13*m+20)*(2*m+5)*(m+3)*A(m+3) = 0 The growth-constant is the cubic root of the largest root of the algebraic e\ quation in, M 3 2 4 M - 11 M - 8 M - 16 = 0 and in Maple notation 4*M^3-11*M^2-8*M-16 = 0 that happens to be equal to 1/2 1/3 (6371 + 624 78 ) 217 11 --------------------- + ------------------------ + -- 12 1/2 1/3 12 12 (6371 + 624 78 ) and in Maple notation 1/12*(6371+624*78^(1/2))^(1/3)+217/12/(6371+624*78^(1/2))^(1/3)+11/12 that equals 3.6107186132760393498 as you can see, this is less than, 4, . n so indeed the size of the largest such set it is exponentially less than, 4 The asymptotic expansion to order, 3, of the sequence A(m) is / (-m) m 1/2 (- m/3) 1/2 | %3 12 (%2 + 11 %1 + 217) (6371 + 624 78 ) (1/m) | | \ 1/2 2/3 1/2 1/2 2/3 1/2 13103 (6371 + 624 78 ) 78 513117 (6371 + 624 78 ) 78 --------------------------------- - ---------------------------------- %3 52 m %3 1/2 2/3 1/2 1/3 1/2 136422 (6371 + 624 78 ) 7595 (6371 + 624 78 ) 78 - ---------------------------- + -------------------------------- %3 %3 1/2 2/3 1/2 1/2 2/3 239453345 (6371 + 624 78 ) 78 22773021 (6371 + 624 78 ) - ------------------------------------- + ------------------------------ 2 208 m %3 43264 m %3 1/2 1/3 1/2 1/2 1/3 1306557 (6371 + 624 78 ) 78 1066338 (6371 + 624 78 ) - ----------------------------------- - ----------------------------- 52 m %3 %3 1/2 2/3 381985968 m 15909315 (6371 + 624 78 ) - ----------- + ------------------------------ %3 2 416 m %3 1/2 1/3 1/2 1/2 1/3 2272379515 (6371 + 624 78 ) 78 208245135 (6371 + 624 78 ) + -------------------------------------- + ------------------------------- 2 208 m %3 43264 m %3 1/2 1/3 \ 106515318 49336035 (6371 + 624 78 ) 634430097 5231823345| + --------- - ------------------------------ - --------- - ----------|/m %3 2 26 m %3 2 | 416 m %3 832 m %3 / 1/2 (1/3) %1 := (6371 + 624 78 ) 1/2 (2/3) %2 := (6371 + 624 78 ) 1/2 1/2 %3 := 13103 %2 78 - 136422 %2 + 7595 %1 78 - 1066338 %1 + 106515318 and in Maple notation (13103*(6371+624*78^(1/2))^(2/3)*78^(1/2)-136422*(6371+624*78^(1/2))^(2/3)+7595 *(6371+624*78^(1/2))^(1/3)*78^(1/2)-1066338*(6371+624*78^(1/2))^(1/3)+106515318 )*12^(-m)*((6371+624*78^(1/2))^(2/3)+11*(6371+624*78^(1/2))^(1/3)+217)^m*(6371+ 624*78^(1/2))^(-1/3*m)/m*(1/m)^(1/2)*(13103/(13103*(6371+624*78^(1/2))^(2/3)*78 ^(1/2)-136422*(6371+624*78^(1/2))^(2/3)+7595*(6371+624*78^(1/2))^(1/3)*78^(1/2) -1066338*(6371+624*78^(1/2))^(1/3)+106515318)*(6371+624*78^(1/2))^(2/3)*78^(1/2 )-513117/52/m/(13103*(6371+624*78^(1/2))^(2/3)*78^(1/2)-136422*(6371+624*78^(1/ 2))^(2/3)+7595*(6371+624*78^(1/2))^(1/3)*78^(1/2)-1066338*(6371+624*78^(1/2))^( 1/3)+106515318)*(6371+624*78^(1/2))^(2/3)*78^(1/2)-136422/(13103*(6371+624*78^( 1/2))^(2/3)*78^(1/2)-136422*(6371+624*78^(1/2))^(2/3)+7595*(6371+624*78^(1/2))^ (1/3)*78^(1/2)-1066338*(6371+624*78^(1/2))^(1/3)+106515318)*(6371+624*78^(1/2)) ^(2/3)+7595/(13103*(6371+624*78^(1/2))^(2/3)*78^(1/2)-136422*(6371+624*78^(1/2) )^(2/3)+7595*(6371+624*78^(1/2))^(1/3)*78^(1/2)-1066338*(6371+624*78^(1/2))^(1/ 3)+106515318)*(6371+624*78^(1/2))^(1/3)*78^(1/2)-239453345/43264/m^2/(13103*( 6371+624*78^(1/2))^(2/3)*78^(1/2)-136422*(6371+624*78^(1/2))^(2/3)+7595*(6371+ 624*78^(1/2))^(1/3)*78^(1/2)-1066338*(6371+624*78^(1/2))^(1/3)+106515318)*(6371 +624*78^(1/2))^(2/3)*78^(1/2)+22773021/208/m/(13103*(6371+624*78^(1/2))^(2/3)* 78^(1/2)-136422*(6371+624*78^(1/2))^(2/3)+7595*(6371+624*78^(1/2))^(1/3)*78^(1/ 2)-1066338*(6371+624*78^(1/2))^(1/3)+106515318)*(6371+624*78^(1/2))^(2/3)-\ 1306557/52/m/(13103*(6371+624*78^(1/2))^(2/3)*78^(1/2)-136422*(6371+624*78^(1/2 ))^(2/3)+7595*(6371+624*78^(1/2))^(1/3)*78^(1/2)-1066338*(6371+624*78^(1/2))^(1 /3)+106515318)*(6371+624*78^(1/2))^(1/3)*78^(1/2)-1066338/(13103*(6371+624*78^( 1/2))^(2/3)*78^(1/2)-136422*(6371+624*78^(1/2))^(2/3)+7595*(6371+624*78^(1/2))^ (1/3)*78^(1/2)-1066338*(6371+624*78^(1/2))^(1/3)+106515318)*(6371+624*78^(1/2)) ^(1/3)-381985968*m/(13103*(6371+624*78^(1/2))^(2/3)*78^(1/2)-136422*(6371+624* 78^(1/2))^(2/3)+7595*(6371+624*78^(1/2))^(1/3)*78^(1/2)-1066338*(6371+624*78^(1 /2))^(1/3)+106515318)+15909315/416/m^2/(13103*(6371+624*78^(1/2))^(2/3)*78^(1/2 )-136422*(6371+624*78^(1/2))^(2/3)+7595*(6371+624*78^(1/2))^(1/3)*78^(1/2)-\ 1066338*(6371+624*78^(1/2))^(1/3)+106515318)*(6371+624*78^(1/2))^(2/3)+ 2272379515/43264/m^2/(13103*(6371+624*78^(1/2))^(2/3)*78^(1/2)-136422*(6371+624 *78^(1/2))^(2/3)+7595*(6371+624*78^(1/2))^(1/3)*78^(1/2)-1066338*(6371+624*78^( 1/2))^(1/3)+106515318)*(6371+624*78^(1/2))^(1/3)*78^(1/2)+208245135/208/m/( 13103*(6371+624*78^(1/2))^(2/3)*78^(1/2)-136422*(6371+624*78^(1/2))^(2/3)+7595* (6371+624*78^(1/2))^(1/3)*78^(1/2)-1066338*(6371+624*78^(1/2))^(1/3)+106515318) *(6371+624*78^(1/2))^(1/3)+106515318/(13103*(6371+624*78^(1/2))^(2/3)*78^(1/2)-\ 136422*(6371+624*78^(1/2))^(2/3)+7595*(6371+624*78^(1/2))^(1/3)*78^(1/2)-\ 1066338*(6371+624*78^(1/2))^(1/3)+106515318)-49336035/416/m^2/(13103*(6371+624* 78^(1/2))^(2/3)*78^(1/2)-136422*(6371+624*78^(1/2))^(2/3)+7595*(6371+624*78^(1/ 2))^(1/3)*78^(1/2)-1066338*(6371+624*78^(1/2))^(1/3)+106515318)*(6371+624*78^(1 /2))^(1/3)-634430097/26/m/(13103*(6371+624*78^(1/2))^(2/3)*78^(1/2)-136422*( 6371+624*78^(1/2))^(2/3)+7595*(6371+624*78^(1/2))^(1/3)*78^(1/2)-1066338*(6371+ 624*78^(1/2))^(1/3)+106515318)-5231823345/832/m^2/(13103*(6371+624*78^(1/2))^(2 /3)*78^(1/2)-136422*(6371+624*78^(1/2))^(2/3)+7595*(6371+624*78^(1/2))^(1/3)*78 ^(1/2)-1066338*(6371+624*78^(1/2))^(1/3)+106515318)) and in floating-point 72934835.41*12.^(-1.*m)*988.7161671^m*11882.01878^(-.3333333333*m)/m*(1/m)^(1/2 )*(1.000000000+.687203880e-1/m-.541360111e-1/m^2-5.237359705*m) 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 [5, 15, 50, 167, 565, 1932, 6648, 22991, 79835, 278135, 971646, 3402284, 11937164, 41955320, 147685120, 520564975, 1837125575, 6490459869, 22953012990, 81244275327, 287806821765, 1020317525880, 3619677131000, 12849369803492, 45640580538740, 162203355428532, 576755471970248, 2051787197723192, 7302448448055720, 26000900528635952] The first, 30, terms of the above-mentioned sequence, A(m) are [1, 3, 10, 31, 101, 336, 1128, 3823, 13051, 44803, 154518, 534964, 1858156, 6472168, 22597760, 79067375, 277164295, 973184313, 3422117190, 12049586631, 42478745781, 149915252028, 529606271560, 1872653175556, 6627147599476, 23471065878276, 83186110269928, 295024653043480, 1046972450508456, 3717608331097936] Finally, just for fun,, A(1000), equals 4757248610528865268671452724894879142113105235546003372806217692651390169253\ 520016447835269028185919333156711010289272639365048663037808203587538892\ 764102094025491713725706644112254437733848184271418538892311811068902850\ 367510684597956223354279060350299760236268673671345211915517820414364175\ 875052732751812326576055559582299455109838242382759294144660443313637318\ 634893892759418945015009499386046512683630933300622304687581310391508085\ 794568764664684299901931416491179748149196847123591965632985507658772914\ 302708989824307879174949617597171661285879402848 --------------------------------------------------- This ends this article that took, 2.175, seconds to generate.