Número de van der Waerden

El teorema de Van der Waerden establix que per a qualssevol sancers positius r i k existix un sancer positiu N tal que si els sancers $1, 2, ..., N$ són coloreats, cada u en un de r distints colors, llavors hi ha a lo manco k números en progressió aritmètica tots d'un mateix color. El número més chicotet per a N és el número de van der Waerden $W (r, k)$ .

Taules de números de van der Waerden

Existixen dos casos en els que el número de van der Waerden $W (r, k)$ és senzill de calcular: primer, quan el número de colors r és igual a 1, un té $W (1, k) = k$ per a qualsevol sancer k, ya que un sol color produïx el coloreat trivial $R R R R \dots R R R$ (per a l'únic color denotat en R). Segon, quan la llongitut k de la progressió aritmètica forçada és 2, un té $W (r, 2) = r + 1$ ya que és possible construir un coloreat que evite les progressions aritmètiques de llongitut 2 usant cada color fins a un màxim d'una volta, pero usar qualsevol color dos voltes crearà una progressió aritmètica de llongitut 2. Per eixemple, per a $r = 3$ , el coloreat més llarc que evita una progressió de llongitut 2 és $R G B$ . Només existixen atres sèt números de van der Waerden els valors dels quals es coneixen exactament. El quadro reproduït avall reporta els valors exactes i llímits per a valors de $W (r, k)$ ; estos vénen del treball de Rabung and Lotts, llevat a on es mencione lo contrari.^[1]

k	2 colors	3 colors	4 colors	5 colors	6 colors
3	9	27	76	>170	>223
4	35	293	>1,048	>2,254	>9,778
5	178	>2,173	>17,705	>98,740	>98,748
6	1,132	>11,191	>91,331	>540,025	>816,981
7	>3,703	>48,811	>420,217	>1,381,687	>7,465,909
8	>11,495	>238,400	>2,388,317	>10,743,258	>57,445,718
9	>41,265	>932,745	>10,898,729	>79,706,009	>458,062,329^[2]
10	>103,474	>4,173,724	>76,049,218	>542,694,970^[2]	>2,615,305,384^[2]
11	>193,941	>18,603,731	>305,513,57^[2]	>2,967,283,511^[2]	>3,004,668,671^[2]

Els número de van der Waerden en $r \geq 2$ tenen un llímit superior dau per

W (r, k) \leq 2^{2^{r^{2^{2^{k + 9}}}}}

segons la prova de Gowers.^[3]

Per a un Número primo $p$ , el número de van der Waerden de dos colors té un llímit inferior dau per

p \cdot 2^{p} \leq W (2, p + 1),

segons la prova de Berlekamp.^[4]

També és possible denotar $w (r; k_{1}, k_{2}, \dots, k_{r})$ per a referir-se al menor número $w$ tal que qualsevol coloració dels sancers $1, 2, \dots, w$ en $r$ colors conté una progressió de llongitut $k_{i}$ de color $i$ per a alguna $i$ . Dits números es diuen números de van der Waerden fòra de la diagonal (en inglés: off-diagonal van der Waerden numbers. Per lo tant $W (r, k) = w (r; k, k, \dots, k)$ .

A continuació es presenta una llista d'alguns números de van der Waerden coneguts:

Números de van der Waerden coneguts
w(r;k₁, k₂, …, k_r)	Valor	Referència
w(2; 3,3)	9	Chvátal
w(2; 3,4)	18	Chvátal
w(2; 3,5)	22	Chvátal
w(2; 3,6)	32	Chvátal
w(2; 3,7)	46	Chvátal
w(2; 3,8)	58	Beeler and O'Neil
w(2; 3,9)	77	Beeler and O'Neil
w(2; 3,10)	97	Beeler and O'Neil
w(2; 3,11)	114	Landman, Robertson, and Culver
w(2; 3,12)	135	Landman, Robertson, i Culver
w(2; 3,13)	160	Landman, Robertson, i Culver
w(2; 3,14)	186	Kouril
w(2; 3,15)	218	Kouril
w(2; 3,16)	238	Kouril
w(2; 3,17)	279	Ahmed
w(2; 3,18)	312	Ahmed
w(2; 3,19)	349	Ahmed, Kullmann, i Snevily
w(2; 4,4)	35	Chvátal
w(2; 4,5)	55	Chvátal
w(2; 4,6)	73	Beeler i O'Neil
w(2; 4,7)	109	Beeler
w(2; 4,8)	146	Kouril
w(2; 4,9)	309	Ahmed
w(2; 5,5)	178	Stevens i Shantaram
w(2; 5,6)	206	Kouril
w(2; 5,7)	260	Ahmed
w(2; 6,6)	1132	Kouril i Paul
w(3; 2, 3, 3)	14	Brown
w(3; 2, 3, 4)	21	Brown
w(3; 2, 3, 5)	32	Brown
w(3; 2, 3, 6)	40	Brown
w(3; 2, 3, 7)	55	Landman, Robertson, i Culver
w(3; 2, 3, 8)	72	Kouril
w(3; 2, 3, 9)	90	Ahmed
w(3; 2, 3, 10)	108	Ahmed
w(3; 2, 3, 11)	129	Ahmed
w(3; 2, 3, 12)	150	Ahmed
w(3; 2, 3, 13)	171	Ahmed
w(3; 2, 3, 14)	202	Kouril
w(3; 2, 4, 4)	40	Brown
w(3; 2, 4, 5)	71	Brown
w(3; 2, 4, 6)	83	Landman, Robertson, i Culver
w(3; 2, 4, 7)	119	Kouril
w(3; 2, 4, 8)	157	Kouril
w(3; 2, 5, 5)	180	Ahmed
w(3; 2, 5, 6)	246	Kouril
w(3; 3, 3, 3)	27	Chvátal
w(3; 3, 3, 4)	51	Beeler i O'Neil
w(3; 3, 3, 5)	80	Landman, Robertson, i Culver
w(3; 3, 3, 6)	107	Ahmed
w(3; 3, 4, 4)	89	Landman, Robertson, i Culver
w(3; 4, 4, 4)	293	Kouril
w(4; 2, 2, 3, 3)	17	Brown
w(4; 2, 2, 3, 4)	25	Brown
w(4; 2, 2, 3, 5)	43	Brown
w(4; 2, 2, 3, 6)	48	Landman, Robertson, i Culver
w(4; 2, 2, 3, 7)	65	Landman, Robertson, i Culver
w(4; 2, 2, 3, 8)	83	Ahmed
w(4; 2, 2, 3, 9)	99	Ahmed
w(4; 2, 2, 3, 10)	119	Ahmed
w(4; 2, 2, 3, 11)	141	Schweitzer
w(4; 2, 2, 4, 4)	53	Brown
w(4; 2, 2, 4, 5)	75	Ahmed
w(4; 2, 2, 4, 6)	93	Ahmed
w(4; 2, 2, 4, 7)	143	Kouril
w(4; 2, 3, 3, 3)	40	Brown
w(4; 2, 3, 3, 4)	60	Landman, Robertson, i Culver
w(4; 2, 3, 3, 5)	86	Ahmed
w(4; 3, 3, 3, 3)	76	Beeler i O'Neil
w(5; 2, 2, 2, 3, 3)	20	Landman, Robertson, i Culver
w(5; 2, 2, 2, 3, 4)	29	Ahmed
w(5; 2, 2, 2, 3, 5)	44	Ahmed
w(5; 2, 2, 2, 3, 6)	56	Ahmed
w(5; 2, 2, 2, 3, 7)	72	Ahmed
w(5; 2, 2, 2, 3, 8)	88	Ahmed
w(5; 2, 2, 2, 3, 9)	107	Kouril
w(5; 2, 2, 2, 4, 4)	54	Ahmed
w(5; 2, 2, 2, 4, 5)	79	Ahmed
w(5; 2, 2, 2, 4, 6)	101	Kouril
w(5; 2, 2, 3, 3, 3)	41	Landman, Robertson, i Culver
w(5; 2, 2, 3, 3, 4)	63	Ahmed
w(6; 2, 2, 2, 2, 3, 3)	21	Ahmed
w(6; 2, 2, 2, 2, 3, 4)	33	Ahmed
w(6; 2, 2, 2, 2, 3, 5)	50	Ahmed
w(6; 2, 2, 2, 2, 3, 6)	60	Ahmed
w(6; 2, 2, 2, 2, 4, 4)	56	Ahmed
w(6; 2, 2, 2, 3, 3, 3)	42	Ahmed
w(7; 2, 2, 2, 2, 2, 3, 3)	24	Ahmed
w(7; 2, 2, 2, 2, 2, 3, 4)	36	Ahmed
w(7; 2, 2, 2, 2, 2, 3, 5)	55	Ahmed
w(7; 2, 2, 2, 2, 2, 3, 6)	65	Ahmed
w(7; 2, 2, 2, 2, 2, 4, 4)	66	Ahmed
w(7; 2, 2, 2, 2, 3, 3, 3)	45	Ahmed
w(8; 2, 2, 2, 2, 2, 2, 3, 3)	25	Ahmed
w(8; 2, 2, 2, 2, 2, 2, 3, 4)	40	Ahmed
w(8; 2, 2, 2, 2, 2, 2, 3, 5)	61	Ahmed
w(8; 2, 2, 2, 2, 2, 2, 3, 6)	71	Ahmed
w(8; 2, 2, 2, 2, 2, 2, 4, 4)	67	Ahmed
w(8; 2, 2, 2, 2, 2, 3, 3, 3)	49	Ahmed
w(9; 2, 2, 2, 2, 2, 2, 2, 3, 3)	28	Ahmed
w(9; 2, 2, 2, 2, 2, 2, 2, 3, 4)	42	Ahmed
w(9; 2, 2, 2, 2, 2, 2, 2, 3, 5)	65	Ahmed
w(9; 2, 2, 2, 2, 2, 2, 3, 3, 3)	52	Ahmed
w(10; 2, 2, 2, 2, 2, 2, 2, 2, 3, 3)	31	Ahmed
w(10; 2, 2, 2, 2, 2, 2, 2, 2, 3, 4)	45	Ahmed
w(10; 2, 2, 2, 2, 2, 2, 2, 2, 3, 5)	70	Ahmed
w(11; 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3)	33	Ahmed
w(11; 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 4)	48	Ahmed
w(12; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3)	35	Ahmed
w(12; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 4)	52	Ahmed
w(13; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3)	37	Ahmed
w(13; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 4)	55	Ahmed
w(14; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3)	39	Ahmed
w(15; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3)	42	Ahmed
w(16; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3)	44	Ahmed
w(17; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3)	46	Ahmed
w(18; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3)	48	Ahmed
w(19; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3)	50	Ahmed
w(20; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3)	51	Ahmed

Els números de van der Waerden són primitiu recursivos, segons la prova de Shelah;^[5] en la que va provar que estan (quan més) en el quint nivell $ℰ^{5}$ de la jerarquia de Grzegorczyk.

Llectures adicionals

Herwig, P. R. (2007). “A New Method to Construct Lower Bounds for Van der Waerden Numbers”. The Electronic Journal of Combinatorics 14 (1).

Vore també

Referències

↑ (2012).«Improving the use of cyclic zippers in finding lower bounds for van der Waerden numbers».Electron. J. Combin..19(2)
↑ ^2,0 ^2,1 ^2,2 ^2,3 ^2,4 ^2,5 «Daniel Monroe, Van Der Waerden Numbers». Archivat des d'el original, el 16 de setembre de 2015. Consultat el 19 de setembre de 2015.
↑ Gowers, Timothy (2001). “A new proof of Szemerédi's theorem”. Geom. Funct. Anal. 11 (3): 465–588. doi:10.1007/s00039-001-0332-9.
↑ Berlekamp, E. (1968). “A construction for partitions which avoid long arithmetic progressions”. Canadian Mathematical Bulletin 11: 409–414. doi:10.4153/CMB-1968-047-7.
↑ Shelah, Saharon (1988). “Primitive recursive bounds for van der Waerden numbers”. J. Amer. Math. Soc. 1 (3): 683–697. doi:10.2307/1990952.

Referències

Este artícul conté una traducció derivada de «Número de van der Waerden» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.

[1] (2012).«Improving the use of cyclic zippers in finding lower bounds for van der Waerden numbers».Electron. J. Combin..19(2)

[:0-2] 2,0 ^2,1 ^2,2 ^2,3 ^2,4 ^2,5 «Daniel Monroe, Van Der Waerden Numbers». Archivat des d'el original, el 16 de setembre de 2015. Consultat el 19 de setembre de 2015.

[3] Gowers, Timothy (2001). “A new proof of Szemerédi's theorem”. Geom. Funct. Anal. 11 (3): 465–588. doi:10.1007/s00039-001-0332-9.

[4] Berlekamp, E. (1968). “A construction for partitions which avoid long arithmetic progressions”. Canadian Mathematical Bulletin 11: 409–414. doi:10.4153/CMB-1968-047-7.

[5] Shelah, Saharon (1988). “Primitive recursive bounds for van der Waerden numbers”. J. Amer. Math. Soc. 1 (3): 683–697. doi:10.2307/1990952.

[1]

[2]

[3]

[4]

[5]