1149:. If the digits of each number are thought of as coordinates of a vector, this constraint describes a sphere in the resulting vector space, and by convexity the average of two distinct values on this sphere will be interior to the sphere rather than on it. Therefore, if two elements of Behrend's set are the endpoints of an arithmetic progression, the middle value of the progression (their average) will not be in the set. Thus, the resulting set is progression-free.
31:
1526:
1519:
1512:
1505:
1498:
1492:
1196:
proved that there is a single infinite Salem–Spencer sequence achieving the same asymptotic density on every prefix as
Behrend's construction. By considering the convex hull of points inside a sphere, rather than the set of points on a sphere, it is possible to improve the construction by a factor of
1702:
chessboard so that all squares of the board are attacked. The set of diagonal squares that remain unoccupied must form a Salem–Spencer set, in which all values have the same parity (all odd or all even). The smallest possible set of queens is the complement of the largest Salem–Spencer subset of the
620:. Therefore, although the sets constructed by Salem, Spencer, and Behrend have sizes that are nearly linear, it is not possible to improve them and find sets whose size is actually linear. This result became a special case of
58:. They have also been called non-averaging sets, but this term has also been used to denote a set of integers none of which can be obtained as the average of any subset of the other numbers. Salem-Spencer sets are named after
717:
787:
409:
558:
885:
2557:
1782:
1225:
618:
1736:
1396:
and problem-specific heuristics to bound the size that can be achieved in any branch of the search tree. One heuristic that they found to be particularly effective was the
1340:
474:
34:
For the set {1, 2, 4, 5, 10, 11, 13, 14}, all midpoints of two elements (the 28 yellow points) land outside the set, so no three elements can form an arithmetic progression
813:
500:
114:
957:
923:
1700:
1625:
Five queens on the main diagonal of a chessboard, attacking all other squares. The vacant squares on the diagonal are in rows 1, 3, and 7, an all-odd Salem–Spencer set.
1366:
2228:
2169:
2053:
1081:
1127:
292:
1441:
1418:
1386:
1297:
1273:
1253:
1190:
1170:
1147:
1101:
1049:
1029:
1009:
989:
433:
339:
319:
194:
174:
154:
134:
1011:
are the first and second members of an arithmetic progression, the third member must have the digit two at the position of the least significant digit where
568:
296:
2484:
2305:
2123:
1990:
268:
239:
207:
1051:
differ. The illustration shows a set of this form, for the three-digit ternary numbers (shifted by one to make the smallest element 1 instead of 0).
1877:
2605:
1129:(so that addition of these numbers has no carries), with the extra constraint that the sum of the squares of the digits is some chosen value
1650:
1738:. This Salem-Spencer subset can be found by doubling and subtracting one from the values in a Salem–Spencer subset of all the numbers in
3069:
Proceedings of the
Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019
1642:
1658:
816:
624:
on the density of sets of integers that avoid longer arithmetic progressions. To distinguish Roth's bound on Salem–Spencer sets from
2383:
887:
was found by computers scientist Kelley and Meka and shortly after an exposition in more familiar mathematical terms was given by
643:
2008:; Lev, V.; Rauzy, G.; Sándor, C.; Sárközy, A. (1999), "Greedy algorithm, arithmetic progressions, subset sums and divisibility",
2983:
Theory of
Cryptography: 9th Theory of Cryptography Conference, TCC 2012, Taormina, Sicily, Italy, March 19–21, 2012, Proceedings
2643:
3165:
3109:
2941:
2731:
Bloom, Thomas F.; Sisask, Olof (2023-09-05). "An improvement to the Kelley-Meka bounds on three-term arithmetic progressions".
1808:
722:
1631:
2010:
2710:
Bloom, Thomas F.; Sisask, Olof (2023-02-14). "The Kelley--Meka bounds for sets free of three-term arithmetic progressions".
2757:
2425:
2344:
1673:
967:
A simple construction for a Salem–Spencer set (of size considerably smaller than
Behrend's bound) is to choose the
2803:
1641:
Salem–Spencer sets have also been used in theoretical computer science. They have been used in the design of the
640:. After several additional improvements to Roth's theorem, the size of a Salem–Spencer set has been proven to be
629:
435:, so the sets found by Salem and Spencer have a size that is nearly linear. This bound disproved a conjecture of
344:
1307:
Gasarch, Glenn, and
Kruskal have performed a comparison of different computational methods for large subsets of
621:
288:
2869:(1961), "XXIV: Sets of integers containing not more than a given number of terms in arithmetical progression",
1669:
509:
39:
3150:
822:
2558:"To cheer you up in difficult times 7: Bloom and Sisask just broke the logarithm barrier for Roth's theorem!"
971:
that use only the digits 0 and 1, not 2. Such a set must be progression-free, because if two of its elements
2866:
3063:; Hermelin, Danny; Shabtay, Dvir (2019), "SETH-based lower bounds for subset sum and bicriteria path", in
2914:, Colloq. Math. Soc. János Bolyai, vol. 18, Amsterdam and New York: North-Holland, pp. 939–945,
1342:
with no arithmetic progression. Using these methods they found the exact size of the largest such set for
968:
47:
1941:
2430:
1646:
251:
1741:
1200:
574:
2178:
2062:
1635:
66:, who showed in 1942 that Salem–Spencer sets can have nearly-linear size. However a later theorem of
2254:
Bloom, Thomas; Sisask, Olaf (2019), "Logarithmic bounds for Roth's theorem via almost-periodicity",
2815:
2811:
1706:
1310:
446:
792:
479:
81:
3090:
3072:
3042:
3016:
3007:
2886:
2849:
2823:
2766:
2732:
2711:
2674:
2622:
2583:
2541:
2519:
2493:
2482:
Bloom, T. F. (2016), "A quantitative improvement for Roth's theorem on arithmetic progressions",
2465:
2439:
2408:
2283:
2265:
2167:(December 1946), "On sets of integers which contain no three terms in arithmetical progression",
2051:(December 1942), "On Sets of Integers Which Contain No Three Terms in Arithmetical Progression",
1835:
1662:
1393:
928:
2907:
2580:
2023 IEEE 64th Annual
Symposium on Foundations of Computer Science (FOCS)-Conference Proceedings
2339:
1192:
as the most frequently-occurring sum of squares of digits, Behrend achieves his bound. In 1953,
894:
1911:
Abbott, H. L. (1976), "On a conjecture of Erdős and Straus on non-averaging sets of integers",
1679:
1345:
2692:
2601:
2300:
2256:
2206:
2090:
2048:
625:
63:
3118:
3082:
3026:
2986:
2979:"Progression-free sets and sublinear pairing-based non-interactive zero-knowledge arguments"
2950:
2878:
2871:
Proceedings of the Royal
Society of Edinburgh, Section A: Mathematical and Physical Sciences
2833:
2820:
Additive number theory: Festschrift in honor of the sixtieth birthday of Melvyn B. Nathanson
2776:
2684:
2593:
2503:
2449:
2392:
2353:
2314:
2275:
2196:
2186:
2132:
2080:
2070:
2044:
2019:
1953:
1886:
1817:
1389:
633:
226:
225:
This example is shifted by adding one to the elements of an infinite Salem–Spencer set, the
59:
3130:
3038:
2964:
2919:
2845:
2790:
2515:
2461:
2404:
2365:
2326:
2241:
2144:
2031:
1967:
1920:
1898:
1831:
3126:
3064:
3034:
2960:
2936:
2932:
2915:
2841:
2786:
2511:
2457:
2400:
2361:
2322:
2237:
2140:
2027:
1963:
1916:
1915:, Congressus Numerantium, vol. XV, Winnipeg, Manitoba: Utilitas Math., pp. 1–4,
1913:
Proceedings of the Fifth
British Combinatorial Conference (Univ. Aberdeen, Aberdeen, 1975)
1894:
1857:
1827:
1057:
2111:
1106:
440:
3107:
Cockayne, E. J.; Hedetniemi, S. T. (1986), "On the diagonal queens domination problem",
2182:
2066:
1423:
3060:
2201:
2085:
1403:
1371:
1282:
1258:
1238:
1175:
1155:
1132:
1086:
1034:
1014:
994:
974:
418:
412:
324:
304:
276:
255:
247:
179:
159:
139:
119:
2955:
2023:
3159:
3122:
3046:
2903:
2890:
2378:
2287:
2164:
2107:
2005:
1861:
1839:
1654:
503:
436:
254:
first infinite Salem–Spencer set. Another infinite Salem–Spencer set is given by the
3094:
2853:
2523:
2469:
888:
2412:
1865:
30:
3005:
Abboud, Amir; Bodwin, Greg (2017), "The 4/3 additive spanner exponent is tight",
2991:
2985:, Lecture Notes in Computer Science, vol. 7194, Springer, pp. 169–189,
2597:
2575:
2453:
301:
In 1942, Salem and
Spencer published a proof that the integers in the range from
17:
2837:
1980:
1083:. His set consists of the numbers whose digits are restricted to the range from
891:
and Sisask who have since also improved the exponent of the Kelly-Meka bound to
2318:
2136:
1890:
293:
Erdős conjecture on arithmetic progressions § Progress and related results
3086:
2882:
2807:
2781:
2621:
Kelley, Zander; Meka, Raghu (2023-02-10). "Strong Bounds for 3-Progressions".
2223:
2115:
564:
67:
2696:
2538:
Breaking the logarithmic barrier in Roth's theorem on arithmetic progressions
3146:
2755:
Elkin, Michael (2011), "An improved construction of progression-free sets",
2663:"The Kelley–Meka bounds for sets free of three-term arithmetic progressions"
2553:
1803:
1193:
2210:
2191:
2094:
2075:
1822:
1275:
elements form an arithmetic progression if and only if they are all equal.
2688:
2507:
2396:
2662:
1227:. However, this does not affect the size bound in the form stated above.
232:
0, 1, 3, 4, 9, 10, 12, 13, 27, 28, 30, 31, 36, 37, 39, 40, ... (sequence
2912:
Combinatorics (Proc. Fifth
Hungarian Colloq., Keszthely, 1976), Vol. II
2357:
1634:, Salem–Spencer sets have been used to construct dense graphs in which
1235:
The notion of Salem–Spencer sets (3-AP-free set) can be generalized to
2910:(1978), "Triple systems with no six points carrying three triangles",
2810:(2010), "A note on Elkin's improvement of Behrend's construction", in
819:
computed) was announced in 2020 in a preprint. In 2023 a new bound of
2279:
2270:
3030:
1368:. Their results include several new bounds for different values of
3077:
3021:
2737:
2716:
2679:
2627:
2588:
2546:
1054:
Behrend's construction uses a similar idea, for a larger odd radix
3071:, Society for Industrial and Applied Mathematics, pp. 41–57,
2978:
2828:
2771:
2498:
2444:
1958:
29:
297:
Roth's theorem on arithmetic progressions § Improving Bounds
200:
1, 2, 4, 5, 9, 11, 13, 14, 20, 24, 26, 30, 32, 36, ... (sequence
1676:
of placing as few queens as possible on the main diagonal of an
214:
For instance, among the numbers from 1 to 14, the eight numbers
2342:(1990), "Integer sets containing no arithmetic progressions",
2303:(1987), "Integer sets containing no arithmetic progressions",
1653:. Recently, they have been used to show size lower bounds for
261:
0, 1, 8, 27, 64, 125, 216, 343, 512, 729, 1000, ... (sequence
2939:(1990), "Matrix multiplication via arithmetic progressions",
712:{\displaystyle O{\bigl (}n(\log \log n)^{4}/\log n{\bigr )}}
1984:
263:
234:
202:
571:
establishing that the size of a Salem-Spencer set must be
1400:, in which two shifted copies of a Salem–Spencer set for
782:{\displaystyle O{\bigl (}n/(\log n)^{1+\delta }{\bigr )}}
1942:"Sequences containing no 3-term arithmetic progressions"
502:. The construction of Salem and Spencer was improved by
2644:"Surprise Computer Science Proof Stuns Mathematicians"
1744:
1709:
1682:
1426:
1420:
are placed in the first and last thirds of a set for
1406:
1374:
1348:
1313:
1285:
1261:
1241:
1203:
1178:
1158:
1135:
1109:
1089:
1060:
1037:
1017:
997:
977:
931:
897:
825:
795:
725:
646:
577:
512:
482:
449:
421:
347:
327:
307:
182:
162:
142:
122:
84:
250:, use only the digits 0 and 1. This sequence is the
279:that no three cubes are in arithmetic progression.
1776:
1730:
1694:
1435:
1412:
1380:
1360:
1334:
1291:
1267:
1247:
1219:
1184:
1164:
1141:
1121:
1095:
1075:
1043:
1023:
1003:
983:
951:
917:
879:
807:
781:
711:
612:
552:
494:
468:
427:
403:
333:
313:
188:
168:
148:
128:
108:
2381:(1999), "On triples in arithmetic progression",
1452:
70:shows that the size is always less than linear.
2170:Proceedings of the National Academy of Sciences
2054:Proceedings of the National Academy of Sciences
289:Szemerédi's theorem § Quantitative bounds
46:is a set of numbers no three of which form an
2661:Bloom, Thomas F.; Sisask, Olof (2023-12-31).
2428:(2011), "On Roth's theorem on progressions",
1806:(1953), "On non-averaging sets of integers",
774:
731:
704:
652:
443:that the size of such a set could be at most
8:
2226:(1952), "Sur quelques ensembles d'entiers",
1768:
1745:
1725:
1710:
1329:
1314:
404:{\displaystyle n/e^{O(\log n/\log \log n)}}
222:form the unique largest Salem-Spencer set.
2574:Kelley, Zander; Meka, Raghu (2023-11-06).
2485:Journal of the London Mathematical Society
2306:Journal of the London Mathematical Society
2124:Journal of the London Mathematical Society
415:, and grows more slowly than any power of
411:. The denominator of this expression uses
3076:
3020:
2990:
2954:
2827:
2780:
2770:
2736:
2715:
2678:
2626:
2587:
2545:
2497:
2443:
2269:
2229:Comptes rendus de l'Académie des Sciences
2200:
2190:
2084:
2074:
1991:On-Line Encyclopedia of Integer Sequences
1957:
1866:"Finding large 3-free sets. I. The small
1821:
1760:
1743:
1708:
1681:
1425:
1405:
1373:
1347:
1312:
1284:
1260:
1240:
1204:
1202:
1177:
1157:
1134:
1108:
1088:
1059:
1036:
1016:
996:
976:
941:
930:
907:
896:
861:
857:
824:
794:
773:
772:
760:
739:
730:
729:
724:
703:
702:
688:
682:
651:
650:
645:
638:Roth's theorem on arithmetic progressions
587:
576:
553:{\displaystyle n/e^{O({\sqrt {\log n}})}}
532:
525:
516:
511:
481:
454:
448:
420:
376:
360:
351:
346:
326:
306:
181:
161:
141:
121:
83:
2822:, New York: Springer, pp. 141–144,
880:{\displaystyle \exp(-c(\log N)^{1/12})N}
1878:Journal of Computer and System Sciences
1792:
1649:, and in the construction of efficient
341:have large Salem–Spencer sets, of size
2750:
2748:
1636:each edge belongs to a unique triangle
1525:
1518:
1511:
1504:
1497:
1276:
2159:
2157:
2155:
2153:
1935:
1933:
1931:
1929:
1852:
1850:
1848:
1798:
1796:
1651:non-interactive zero-knowledge proofs
1488:
50:. Salem–Spencer sets are also called
38:In mathematics, and in particular in
7:
2536:Bloom, Thomas; Sisask, Olaf (2020),
1946:Electronic Journal of Combinatorics
246:of numbers that, when written as a
2576:"Strong Bounds for 3-Progressions"
1668:These sets can also be applied in
1659:strong exponential time hypothesis
25:
2384:Geometric and Functional Analysis
1777:{\displaystyle \{1,\dots n/2\}.}
1524:
1517:
1510:
1503:
1496:
1490:
1220:{\displaystyle {\sqrt {\log n}}}
613:{\displaystyle O(n/\log \log n)}
506:in 1946, who found sets of size
3110:Journal of Combinatorial Theory
2942:Journal of Symbolic Computation
2116:"On some sequences of integers"
1809:Canadian Journal of Mathematics
196:-element Salem-Spencer set are
27:Progression-free set of numbers
1643:Coppersmith–Winograd algorithm
871:
854:
841:
832:
757:
744:
679:
660:
636:, this result has been called
607:
581:
545:
529:
396:
364:
1:
2956:10.1016/S0747-7171(08)80013-2
2758:Israel Journal of Mathematics
2024:10.1016/S0012-365X(98)00385-9
1731:{\displaystyle \{1,\dots n\}}
1335:{\displaystyle \{1,\dots n\}}
469:{\displaystyle n^{1-\delta }}
3123:10.1016/0097-3165(86)90012-9
2992:10.1007/978-3-642-28914-9_10
2642:Sloman, Leila (2023-03-21).
2598:10.1109/FOCS57990.2023.00059
2454:10.4007/annals.2011.174.1.20
1940:Dybizbański, Janusz (2012),
1279:gave constructions of large
808:{\displaystyle \delta >0}
495:{\displaystyle \delta >0}
218:{1, 2, 4, 5, 10, 11, 13, 14}
109:{\displaystyle k=1,2,\dots }
2981:, in Cramer, Ronald (ed.),
2838:10.1007/978-0-387-68361-4_9
952:{\displaystyle \beta =5/41}
136:such that the numbers from
3182:
2345:Acta Mathematica Hungarica
1981:Sloane, N. J. A.
1891:10.1016/j.jcss.2007.06.002
1674:mathematical chess problem
918:{\displaystyle \beta =1/9}
719:. An even better bound of
286:
3087:10.1137/1.9781611975482.3
2883:10.1017/S0080454100017726
2782:10.1007/s11856-011-0061-1
1695:{\displaystyle n\times n}
1361:{\displaystyle n\leq 187}
1152:With a careful choice of
630:Diophantine approximation
3147:Nonaveraging sets search
2319:10.1112/jlms/s2-35.3.385
2137:10.1112/jlms/s1-11.4.261
1670:recreational mathematics
1255:-AP-free sets, in which
40:arithmetic combinatorics
2977:Lipmaa, Helger (2012),
2667:Essential Number Theory
1985:"Sequence A005836"
1632:Ruzsa–Szemerédi problem
1630:In connection with the
116:the smallest values of
3166:Additive combinatorics
2562:Combinatorics and more
2192:10.1073/pnas.32.12.331
2076:10.1073/pnas.28.12.561
1823:10.4153/cjm-1953-027-0
1778:
1732:
1696:
1661:based hardness of the
1437:
1414:
1382:
1362:
1336:
1293:
1269:
1249:
1221:
1186:
1166:
1143:
1123:
1097:
1077:
1045:
1025:
1005:
985:
953:
919:
881:
809:
783:
713:
614:
554:
496:
470:
429:
405:
335:
315:
190:
170:
150:
130:
110:
48:arithmetic progression
35:
3151:University of Wrocław
2689:10.2140/ent.2023.2.15
2431:Annals of Mathematics
2397:10.1007/s000390050105
1779:
1733:
1697:
1647:matrix multiplication
1438:
1415:
1383:
1363:
1337:
1303:Computational results
1294:
1270:
1250:
1222:
1187:
1167:
1144:
1124:
1098:
1078:
1046:
1026:
1006:
986:
954:
920:
882:
810:
784:
714:
615:
555:
497:
471:
430:
406:
336:
316:
191:
171:
151:
131:
111:
56:progression-free sets
33:
3149:, Jarek Wroblewski,
2011:Discrete Mathematics
1742:
1707:
1680:
1424:
1404:
1392:algorithms that use
1372:
1346:
1311:
1283:
1259:
1239:
1201:
1176:
1156:
1133:
1107:
1087:
1076:{\displaystyle 2d-1}
1058:
1035:
1015:
995:
975:
929:
895:
823:
793:
723:
644:
575:
510:
480:
447:
419:
345:
325:
305:
180:
160:
140:
120:
82:
3015:(4): A28:1–A28:20,
2816:Chudnovsky, Gregory
2508:10.1112/jlms/jdw010
2183:1946PNAS...32..331B
2067:1942PNAS...28..561S
1122:{\displaystyle d-1}
622:Szemerédi's theorem
275:It is a theorem of
52:3-AP-free sequences
3008:Journal of the ACM
2358:10.1007/BF01903717
2301:Heath-Brown, D. R.
1952:(2): P15:1–P15:5,
1774:
1728:
1692:
1663:subset sum problem
1436:{\displaystyle 3n}
1433:
1410:
1394:linear programming
1378:
1358:
1332:
1289:
1265:
1245:
1217:
1182:
1172:, and a choice of
1162:
1139:
1119:
1093:
1073:
1041:
1021:
1001:
981:
949:
915:
877:
815:that has not been
805:
779:
709:
610:
550:
492:
466:
425:
401:
331:
311:
186:
166:
146:
126:
106:
36:
2812:Chudnovsky, David
2607:979-8-3503-1894-4
2582:. IEEE: 933–973.
2488:, Second Series,
2434:, Second Series,
2309:, Second Series,
2257:Discrete Analysis
1994:, OEIS Foundation
1862:Kruskal, Clyde P.
1623:
1622:
1413:{\displaystyle n}
1381:{\displaystyle n}
1292:{\displaystyle k}
1268:{\displaystyle k}
1248:{\displaystyle k}
1215:
1185:{\displaystyle k}
1165:{\displaystyle d}
1142:{\displaystyle k}
1096:{\displaystyle 0}
1044:{\displaystyle y}
1024:{\displaystyle x}
1004:{\displaystyle y}
984:{\displaystyle x}
959:) in a preprint.
925:(and conjectured
634:algebraic numbers
543:
428:{\displaystyle n}
334:{\displaystyle n}
314:{\displaystyle 1}
252:lexicographically
189:{\displaystyle k}
169:{\displaystyle n}
149:{\displaystyle 1}
129:{\displaystyle n}
64:Donald C. Spencer
44:Salem-Spencer set
18:Salem-Spencer set
16:(Redirected from
3173:
3134:
3133:
3104:
3098:
3097:
3080:
3065:Chan, Timothy M.
3056:
3050:
3049:
3024:
3002:
2996:
2995:
2994:
2974:
2968:
2967:
2958:
2937:Winograd, Shmuel
2933:Coppersmith, Don
2929:
2923:
2922:
2900:
2894:
2893:
2863:
2857:
2856:
2831:
2800:
2794:
2793:
2784:
2774:
2752:
2743:
2742:
2740:
2728:
2722:
2721:
2719:
2707:
2701:
2700:
2682:
2658:
2652:
2651:
2639:
2633:
2632:
2630:
2618:
2612:
2611:
2591:
2571:
2565:
2564:
2556:(July 8, 2020),
2550:
2549:
2533:
2527:
2526:
2501:
2479:
2473:
2472:
2447:
2422:
2416:
2415:
2375:
2369:
2368:
2352:(1–2): 155–158,
2336:
2330:
2329:
2297:
2291:
2290:
2280:10.19086/da.7884
2273:
2251:
2245:
2244:
2220:
2214:
2213:
2204:
2194:
2161:
2148:
2147:
2120:
2104:
2098:
2097:
2088:
2078:
2041:
2035:
2034:
2018:(1–3): 119–135,
2002:
1996:
1995:
1977:
1971:
1970:
1961:
1937:
1924:
1923:
1908:
1902:
1901:
1874:
1869:
1860:; Glenn, James;
1858:Gasarch, William
1854:
1843:
1842:
1825:
1800:
1783:
1781:
1780:
1775:
1764:
1737:
1735:
1734:
1729:
1701:
1699:
1698:
1693:
1528:
1527:
1521:
1520:
1514:
1513:
1507:
1506:
1500:
1499:
1494:
1493:
1453:
1442:
1440:
1439:
1434:
1419:
1417:
1416:
1411:
1390:branch-and-bound
1387:
1385:
1384:
1379:
1367:
1365:
1364:
1359:
1341:
1339:
1338:
1333:
1298:
1296:
1295:
1290:
1274:
1272:
1271:
1266:
1254:
1252:
1251:
1246:
1226:
1224:
1223:
1218:
1216:
1205:
1191:
1189:
1188:
1183:
1171:
1169:
1168:
1163:
1148:
1146:
1145:
1140:
1128:
1126:
1125:
1120:
1102:
1100:
1099:
1094:
1082:
1080:
1079:
1074:
1050:
1048:
1047:
1042:
1030:
1028:
1027:
1022:
1010:
1008:
1007:
1002:
990:
988:
987:
982:
958:
956:
955:
950:
945:
924:
922:
921:
916:
911:
886:
884:
883:
878:
870:
869:
865:
814:
812:
811:
806:
788:
786:
785:
780:
778:
777:
771:
770:
743:
735:
734:
718:
716:
715:
710:
708:
707:
692:
687:
686:
656:
655:
619:
617:
616:
611:
591:
559:
557:
556:
551:
549:
548:
544:
533:
520:
501:
499:
498:
493:
475:
473:
472:
467:
465:
464:
434:
432:
431:
426:
410:
408:
407:
402:
400:
399:
380:
355:
340:
338:
337:
332:
320:
318:
317:
312:
266:
237:
227:Stanley sequence
205:
195:
193:
192:
187:
175:
173:
172:
167:
155:
153:
152:
147:
135:
133:
132:
127:
115:
113:
112:
107:
21:
3181:
3180:
3176:
3175:
3174:
3172:
3171:
3170:
3156:
3155:
3143:
3138:
3137:
3106:
3105:
3101:
3061:Bringmann, Karl
3058:
3057:
3053:
3031:10.1145/3088511
3004:
3003:
2999:
2976:
2975:
2971:
2931:
2930:
2926:
2902:
2901:
2897:
2865:
2864:
2860:
2802:
2801:
2797:
2754:
2753:
2746:
2730:
2729:
2725:
2709:
2708:
2704:
2660:
2659:
2655:
2648:Quanta Magazine
2641:
2640:
2636:
2620:
2619:
2615:
2608:
2573:
2572:
2568:
2552:
2535:
2534:
2530:
2481:
2480:
2476:
2424:
2423:
2419:
2377:
2376:
2372:
2338:
2337:
2333:
2299:
2298:
2294:
2253:
2252:
2248:
2222:
2221:
2217:
2177:(12): 331–332,
2163:
2162:
2151:
2118:
2106:
2105:
2101:
2061:(12): 561–563,
2043:
2042:
2038:
2004:
2003:
1999:
1979:
1978:
1974:
1939:
1938:
1927:
1910:
1909:
1905:
1872:
1867:
1856:
1855:
1846:
1802:
1801:
1794:
1789:
1740:
1739:
1705:
1704:
1703:odd numbers in
1678:
1677:
1628:
1627:
1626:
1530:
1529:
1522:
1515:
1508:
1501:
1491:
1449:
1422:
1421:
1402:
1401:
1370:
1369:
1344:
1343:
1309:
1308:
1305:
1299:-AP-free sets.
1281:
1280:
1257:
1256:
1237:
1236:
1233:
1199:
1198:
1174:
1173:
1154:
1153:
1131:
1130:
1105:
1104:
1085:
1084:
1056:
1055:
1033:
1032:
1013:
1012:
993:
992:
973:
972:
969:ternary numbers
965:
927:
926:
893:
892:
853:
821:
820:
791:
790:
756:
721:
720:
678:
642:
641:
573:
572:
521:
508:
507:
478:
477:
450:
445:
444:
417:
416:
356:
343:
342:
323:
322:
303:
302:
299:
285:
262:
233:
201:
178:
177:
158:
157:
138:
137:
118:
117:
80:
79:
76:
28:
23:
22:
15:
12:
11:
5:
3179:
3177:
3169:
3168:
3158:
3157:
3154:
3153:
3142:
3141:External links
3139:
3136:
3135:
3117:(1): 137–139,
3099:
3059:Abboud, Amir;
3051:
2997:
2969:
2949:(3): 251–280,
2924:
2895:
2877:(4): 332–344,
2858:
2795:
2744:
2723:
2702:
2653:
2634:
2613:
2606:
2566:
2528:
2492:(3): 643–663,
2474:
2438:(1): 619–636,
2417:
2391:(5): 968–984,
2370:
2331:
2313:(3): 385–394,
2292:
2246:
2215:
2165:Behrend, F. A.
2149:
2131:(4): 261–264,
2099:
2049:Spencer, D. C.
2036:
1997:
1972:
1925:
1903:
1885:(4): 628–655,
1844:
1791:
1790:
1788:
1785:
1773:
1770:
1767:
1763:
1759:
1756:
1753:
1750:
1747:
1727:
1724:
1721:
1718:
1715:
1712:
1691:
1688:
1685:
1655:graph spanners
1624:
1621:
1620:
1618:
1615:
1612:
1609:
1606:
1603:
1600:
1597:
1594:
1591:
1590:
1587:
1583:
1582:
1579:
1575:
1574:
1571:
1567:
1566:
1563:
1559:
1558:
1555:
1551:
1550:
1547:
1543:
1542:
1539:
1535:
1534:
1531:
1523:
1516:
1509:
1502:
1495:
1489:
1487:
1483:
1482:
1480:
1477:
1474:
1471:
1468:
1465:
1462:
1459:
1456:
1451:
1450:
1448:
1445:
1432:
1429:
1409:
1377:
1357:
1354:
1351:
1331:
1328:
1325:
1322:
1319:
1316:
1304:
1301:
1288:
1264:
1244:
1232:
1231:Generalization
1229:
1214:
1211:
1208:
1181:
1161:
1138:
1118:
1115:
1112:
1092:
1072:
1069:
1066:
1063:
1040:
1020:
1000:
980:
964:
961:
948:
944:
940:
937:
934:
914:
910:
906:
903:
900:
876:
873:
868:
864:
860:
856:
852:
849:
846:
843:
840:
837:
834:
831:
828:
804:
801:
798:
776:
769:
766:
763:
759:
755:
752:
749:
746:
742:
738:
733:
728:
706:
701:
698:
695:
691:
685:
681:
677:
674:
671:
668:
665:
662:
659:
654:
649:
626:Roth's theorem
609:
606:
603:
600:
597:
594:
590:
586:
583:
580:
569:Roth's theorem
547:
542:
539:
536:
531:
528:
524:
519:
515:
491:
488:
485:
463:
460:
457:
453:
424:
413:big O notation
398:
395:
392:
389:
386:
383:
379:
375:
372:
369:
366:
363:
359:
354:
350:
330:
310:
284:
281:
277:Leonhard Euler
273:
272:
248:ternary number
244:
243:
220:
219:
212:
211:
185:
165:
145:
125:
105:
102:
99:
96:
93:
90:
87:
75:
72:
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
3178:
3167:
3164:
3163:
3161:
3152:
3148:
3145:
3144:
3140:
3132:
3128:
3124:
3120:
3116:
3112:
3111:
3103:
3100:
3096:
3092:
3088:
3084:
3079:
3074:
3070:
3066:
3062:
3055:
3052:
3048:
3044:
3040:
3036:
3032:
3028:
3023:
3018:
3014:
3010:
3009:
3001:
2998:
2993:
2988:
2984:
2980:
2973:
2970:
2966:
2962:
2957:
2952:
2948:
2944:
2943:
2938:
2934:
2928:
2925:
2921:
2917:
2913:
2909:
2908:Szemerédi, E.
2905:
2899:
2896:
2892:
2888:
2884:
2880:
2876:
2872:
2868:
2867:Rankin, R. A.
2862:
2859:
2855:
2851:
2847:
2843:
2839:
2835:
2830:
2825:
2821:
2817:
2813:
2809:
2805:
2799:
2796:
2792:
2788:
2783:
2778:
2773:
2768:
2764:
2760:
2759:
2751:
2749:
2745:
2739:
2734:
2727:
2724:
2718:
2713:
2706:
2703:
2698:
2694:
2690:
2686:
2681:
2676:
2672:
2668:
2664:
2657:
2654:
2649:
2645:
2638:
2635:
2629:
2624:
2617:
2614:
2609:
2603:
2599:
2595:
2590:
2585:
2581:
2577:
2570:
2567:
2563:
2559:
2555:
2548:
2543:
2539:
2532:
2529:
2525:
2521:
2517:
2513:
2509:
2505:
2500:
2495:
2491:
2487:
2486:
2478:
2475:
2471:
2467:
2463:
2459:
2455:
2451:
2446:
2441:
2437:
2433:
2432:
2427:
2421:
2418:
2414:
2410:
2406:
2402:
2398:
2394:
2390:
2386:
2385:
2380:
2374:
2371:
2367:
2363:
2359:
2355:
2351:
2347:
2346:
2341:
2340:Szemerédi, E.
2335:
2332:
2328:
2324:
2320:
2316:
2312:
2308:
2307:
2302:
2296:
2293:
2289:
2285:
2281:
2277:
2272:
2267:
2263:
2259:
2258:
2250:
2247:
2243:
2239:
2235:
2231:
2230:
2225:
2219:
2216:
2212:
2208:
2203:
2198:
2193:
2188:
2184:
2180:
2176:
2172:
2171:
2166:
2160:
2158:
2156:
2154:
2150:
2146:
2142:
2138:
2134:
2130:
2126:
2125:
2117:
2113:
2109:
2103:
2100:
2096:
2092:
2087:
2082:
2077:
2072:
2068:
2064:
2060:
2056:
2055:
2050:
2046:
2040:
2037:
2033:
2029:
2025:
2021:
2017:
2013:
2012:
2007:
2001:
1998:
1993:
1992:
1986:
1982:
1976:
1973:
1969:
1965:
1960:
1959:10.37236/2061
1955:
1951:
1947:
1943:
1936:
1934:
1932:
1930:
1926:
1922:
1918:
1914:
1907:
1904:
1900:
1896:
1892:
1888:
1884:
1880:
1879:
1871:
1863:
1859:
1853:
1851:
1849:
1845:
1841:
1837:
1833:
1829:
1824:
1819:
1815:
1811:
1810:
1805:
1799:
1797:
1793:
1786:
1784:
1771:
1765:
1761:
1757:
1754:
1751:
1748:
1722:
1719:
1716:
1713:
1689:
1686:
1683:
1675:
1671:
1666:
1664:
1660:
1656:
1652:
1648:
1644:
1639:
1637:
1633:
1619:
1616:
1613:
1610:
1607:
1604:
1601:
1598:
1595:
1593:
1592:
1588:
1585:
1584:
1580:
1577:
1576:
1572:
1569:
1568:
1564:
1561:
1560:
1556:
1553:
1552:
1548:
1545:
1544:
1540:
1537:
1536:
1532:
1485:
1484:
1481:
1478:
1475:
1472:
1469:
1466:
1463:
1460:
1457:
1455:
1454:
1446:
1444:
1430:
1427:
1407:
1399:
1398:thirds method
1395:
1391:
1375:
1355:
1352:
1349:
1326:
1323:
1320:
1317:
1302:
1300:
1286:
1278:
1277:Rankin (1961)
1262:
1242:
1230:
1228:
1212:
1209:
1206:
1195:
1179:
1159:
1150:
1136:
1116:
1113:
1110:
1090:
1070:
1067:
1064:
1061:
1052:
1038:
1018:
998:
978:
970:
962:
960:
946:
942:
938:
935:
932:
912:
908:
904:
901:
898:
890:
874:
866:
862:
858:
850:
847:
844:
838:
835:
829:
826:
818:
802:
799:
796:
767:
764:
761:
753:
750:
747:
740:
736:
726:
699:
696:
693:
689:
683:
675:
672:
669:
666:
663:
657:
647:
639:
635:
631:
627:
623:
604:
601:
598:
595:
592:
588:
584:
578:
570:
566:
561:
540:
537:
534:
526:
522:
517:
513:
505:
504:Felix Behrend
489:
486:
483:
461:
458:
455:
451:
442:
438:
422:
414:
393:
390:
387:
384:
381:
377:
373:
370:
367:
361:
357:
352:
348:
328:
308:
298:
294:
290:
282:
280:
278:
270:
265:
260:
259:
258:
257:
253:
249:
241:
236:
231:
230:
229:
228:
223:
217:
216:
215:
209:
204:
199:
198:
197:
183:
163:
143:
123:
103:
100:
97:
94:
91:
88:
85:
73:
71:
69:
65:
61:
60:Raphaël Salem
57:
53:
49:
45:
41:
32:
19:
3114:
3113:, Series A,
3108:
3102:
3068:
3054:
3012:
3006:
3000:
2982:
2972:
2946:
2940:
2927:
2911:
2904:Ruzsa, I. Z.
2898:
2874:
2870:
2861:
2819:
2798:
2762:
2756:
2726:
2705:
2673:(1): 15–44.
2670:
2666:
2656:
2647:
2637:
2616:
2579:
2569:
2561:
2537:
2531:
2489:
2483:
2477:
2435:
2429:
2426:Sanders, Tom
2420:
2388:
2382:
2379:Bourgain, J.
2373:
2349:
2343:
2334:
2310:
2304:
2295:
2271:1810.12791v2
2261:
2255:
2249:
2233:
2227:
2218:
2174:
2168:
2128:
2122:
2102:
2058:
2052:
2039:
2015:
2009:
2000:
1988:
1975:
1949:
1945:
1912:
1906:
1882:
1876:
1813:
1807:
1667:
1640:
1629:
1447:Applications
1397:
1306:
1234:
1151:
1053:
966:
963:Construction
637:
562:
300:
274:
245:
224:
221:
213:
77:
55:
51:
43:
37:
2808:Wolf, Julia
2551:; see also
2236:: 388–390,
2224:Roth, Klaus
2112:Turán, Paul
2108:Erdős, Paul
1816:: 245–252,
1388:, found by
3078:1704.04546
3022:1511.00700
2804:Green, Ben
2765:: 93–128,
2738:2309.02353
2717:2302.07211
2680:2302.07211
2628:2302.05537
2589:2302.05537
2554:Kalai, Gil
2547:2007.03528
1804:Moser, Leo
1787:References
1657:, and the
817:explicitly
789:(for some
565:Klaus Roth
437:Paul Erdős
287:See also:
68:Klaus Roth
3047:209870748
2891:122037820
2829:0810.0732
2772:0801.4310
2697:2834-4634
2499:1405.5800
2445:1011.0104
2288:119583263
2045:Salem, R.
2006:Erdős, P.
1840:124488483
1755:…
1720:…
1687:×
1645:for fast
1353:≤
1324:…
1210:
1194:Leo Moser
1114:−
1068:−
933:β
899:β
848:
836:−
830:
797:δ
768:δ
751:
697:
673:
667:
602:
596:
563:In 1952,
538:
484:δ
476:for some
462:δ
459:−
441:Pál Turán
391:
385:
371:
104:…
3160:Category
3095:15802062
2854:10475217
2818:(eds.),
2524:27536138
2470:53331882
2211:16578230
2114:(1936),
2095:16588588
1864:(2008),
74:Examples
3131:0843468
3067:(ed.),
3039:3702458
2965:1056627
2920:0519318
2846:2744752
2791:2823971
2516:3509957
2462:2811612
2405:1726234
2366:1100788
2327:0889362
2242:0046374
2202:1078964
2179:Bibcode
2145:1574918
2086:1078539
2063:Bibcode
2032:1692285
1983:(ed.),
1968:2928630
1921:0406967
1899:2417032
1832:0053140
567:proved
267:in the
264:A000578
238:in the
235:A005836
206:in the
203:A065825
176:have a
3129:
3093:
3045:
3037:
2963:
2918:
2889:
2852:
2844:
2789:
2695:
2604:
2522:
2514:
2468:
2460:
2413:392820
2411:
2403:
2364:
2325:
2286:
2240:
2209:
2199:
2143:
2093:
2083:
2030:
1966:
1919:
1897:
1838:
1830:
295:, and
3091:S2CID
3073:arXiv
3043:S2CID
3017:arXiv
2887:S2CID
2850:S2CID
2824:arXiv
2767:arXiv
2733:arXiv
2712:arXiv
2675:arXiv
2623:arXiv
2584:arXiv
2542:arXiv
2520:S2CID
2494:arXiv
2466:S2CID
2440:arXiv
2409:S2CID
2284:S2CID
2266:arXiv
2264:(4),
2119:(PDF)
1873:(PDF)
1870:case"
1836:S2CID
1672:to a
889:Bloom
256:cubes
2693:ISSN
2602:ISBN
2262:2019
2207:PMID
2091:PMID
1989:The
1031:and
991:and
800:>
487:>
439:and
283:Size
269:OEIS
240:OEIS
208:OEIS
78:For
62:and
42:, a
3119:doi
3083:doi
3027:doi
2987:doi
2951:doi
2879:doi
2834:doi
2777:doi
2763:184
2685:doi
2594:doi
2504:doi
2450:doi
2436:174
2393:doi
2354:doi
2315:doi
2276:doi
2234:234
2197:PMC
2187:doi
2133:doi
2081:PMC
2071:doi
2020:doi
2016:200
1954:doi
1887:doi
1818:doi
1638:.
1356:187
1207:log
1103:to
845:log
827:exp
748:log
694:log
670:log
664:log
632:of
628:on
599:log
593:log
535:log
388:log
382:log
368:log
321:to
156:to
54:or
3162::
3127:MR
3125:,
3115:42
3089:,
3081:,
3041:,
3035:MR
3033:,
3025:,
3013:64
3011:,
2961:MR
2959:,
2945:,
2935:;
2916:MR
2906:;
2885:,
2875:65
2873:,
2848:,
2842:MR
2840:,
2832:,
2814:;
2806:;
2787:MR
2785:,
2775:,
2761:,
2747:^
2691:.
2683:.
2669:.
2665:.
2646:.
2600:.
2592:.
2578:.
2560:,
2540:,
2518:,
2512:MR
2510:,
2502:,
2490:93
2464:,
2458:MR
2456:,
2448:,
2407:,
2401:MR
2399:,
2387:,
2362:MR
2360:,
2350:56
2348:,
2323:MR
2321:,
2311:35
2282:,
2274:,
2260:,
2238:MR
2232:,
2205:,
2195:,
2185:,
2175:32
2173:,
2152:^
2141:MR
2139:,
2129:11
2127:,
2121:,
2110:;
2089:,
2079:,
2069:,
2059:28
2057:,
2047:;
2028:MR
2026:,
2014:,
1987:,
1964:MR
1962:,
1950:19
1948:,
1944:,
1928:^
1917:MR
1895:MR
1893:,
1883:74
1881:,
1875:,
1847:^
1834:,
1828:MR
1826:,
1812:,
1795:^
1665:.
1443:.
947:41
867:12
560:.
291:,
3121::
3085::
3075::
3029::
3019::
2989::
2953::
2947:9
2881::
2836::
2826::
2779::
2769::
2741:.
2735::
2720:.
2714::
2699:.
2687::
2677::
2671:2
2650:.
2631:.
2625::
2610:.
2596::
2586::
2544::
2506::
2496::
2452::
2442::
2395::
2389:9
2356::
2317::
2278::
2268::
2189::
2181::
2135::
2073::
2065::
2022::
1956::
1889::
1868:n
1820::
1814:5
1772:.
1769:}
1766:2
1762:/
1758:n
1752:,
1749:1
1746:{
1726:}
1723:n
1717:,
1714:1
1711:{
1690:n
1684:n
1617:h
1614:g
1611:f
1608:e
1605:d
1602:c
1599:b
1596:a
1589:1
1586:1
1581:2
1578:2
1573:3
1570:3
1565:4
1562:4
1557:5
1554:5
1549:6
1546:6
1541:7
1538:7
1533:8
1486:8
1479:h
1476:g
1473:f
1470:e
1467:d
1464:c
1461:b
1458:a
1431:n
1428:3
1408:n
1376:n
1350:n
1330:}
1327:n
1321:,
1318:1
1315:{
1287:k
1263:k
1243:k
1213:n
1180:k
1160:d
1137:k
1117:1
1111:d
1091:0
1071:1
1065:d
1062:2
1039:y
1019:x
999:y
979:x
943:/
939:5
936:=
913:9
909:/
905:1
902:=
875:N
872:)
863:/
859:1
855:)
851:N
842:(
839:c
833:(
803:0
775:)
765:+
762:1
758:)
754:n
745:(
741:/
737:n
732:(
727:O
705:)
700:n
690:/
684:4
680:)
676:n
661:(
658:n
653:(
648:O
608:)
605:n
589:/
585:n
582:(
579:O
546:)
541:n
530:(
527:O
523:e
518:/
514:n
490:0
456:1
452:n
423:n
397:)
394:n
378:/
374:n
365:(
362:O
358:e
353:/
349:n
329:n
309:1
271:)
242:)
210:)
184:k
164:n
144:1
124:n
101:,
98:2
95:,
92:1
89:=
86:k
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
