P. 157 of Theorem List - Metamath Proof Explorer

Theorem List for Metamath Proof Explorer - 15601-15700   *Has distinct variable group(s)

Type	Label	Description
Statement
Theorem	fldivp1 15601	The difference between the floors of adjacent fractions is either 1 or 0. (Contributed by Mario Carneiro, 8-Mar-2014.)
|- ( ( M e. ZZ /\ N e. NN ) -> ( ( |_ ` ( ( M + 1 ) / N ) ) - ( |_ ` ( M / N ) ) ) = if ( N || ( M + 1 ) , 1 , 0 ) )
Theorem	pcfaclem 15602	Lemma for pcfac 15603. (Contributed by Mario Carneiro, 20-May-2014.)
|- ( ( N e. NN0 /\ M e. ( ZZ>= ` N ) /\ P e. Prime ) -> ( |_ ` ( N / ( P ^ M ) ) ) = 0 )
Theorem	pcfac 15603*	Calculate the prime count of a factorial. (Contributed by Mario Carneiro, 11-Mar-2014.) (Revised by Mario Carneiro, 21-May-2014.)
|- ( ( N e. NN0 /\ M e. ( ZZ>= ` N ) /\ P e. Prime ) -> ( P pCnt ( ! ` N ) ) = sum_ k e. ( 1 ... M ) ( |_ ` ( N / ( P ^ k ) ) ) )
Theorem	pcbc 15604*	Calculate the prime count of a binomial coefficient. (Contributed by Mario Carneiro, 11-Mar-2014.) (Revised by Mario Carneiro, 21-May-2014.)
|- ( ( N e. NN /\ K e. ( 0 ... N ) /\ P e. Prime ) -> ( P pCnt ( N _C K ) ) = sum_ k e. ( 1 ... N ) ( ( |_ ` ( N / ( P ^ k ) ) ) - ( ( |_ ` ( ( N - K ) / ( P ^ k ) ) ) + ( |_ ` ( K / ( P ^ k ) ) ) ) ) )
Theorem	qexpz 15605	If a power of a rational number is an integer, then the number is an integer. In other words, all n-th roots are irrational unless they are integers (so that the original number is an n-th power). (Contributed by Mario Carneiro, 10-Aug-2015.)
|- ( ( A e. QQ /\ N e. NN /\ ( A ^ N ) e. ZZ ) -> A e. ZZ )
Theorem	expnprm 15606	A second or higher power of a rational number is not a prime number. Or by contraposition, the n-th root of a prime number is irrational. Suggested by Norm Megill. (Contributed by Mario Carneiro, 10-Aug-2015.)
|- ( ( A e. QQ /\ N e. ( ZZ>= ` 2 ) ) -> -. ( A ^ N ) e. Prime )
Theorem	oddprmdvds 15607*	Every positive integer which is not a power of two is divisible by an odd prime number. (Contributed by AV, 6-Aug-2021.)
|- ( ( K e. NN /\ -. E. n e. NN0 K = ( 2 ^ n ) ) -> E. p e. ( Prime \ { 2 } ) p || K )
6.2.8  Pocklington's theorem
Theorem	prmpwdvds 15608	A relation involving divisibility by a prime power. (Contributed by Mario Carneiro, 2-Mar-2014.)
|- ( ( ( K e. ZZ /\ D e. ZZ ) /\ ( P e. Prime /\ N e. NN ) /\ ( D || ( K x. ( P ^ N ) ) /\ -. D || ( K x. ( P ^ ( N - 1 ) ) ) ) ) -> ( P ^ N ) || D )
Theorem	pockthlem 15609	Lemma for pockthg 15610. (Contributed by Mario Carneiro, 2-Mar-2014.)
|- ( ph -> A e. NN )   &    |- ( ph -> B e. NN )   &    |- ( ph -> B < A )   &    |- ( ph -> N = ( ( A x. B ) + 1 ) )   &    |- ( ph -> P e. Prime )   &    |- ( ph -> P || N )   &    |- ( ph -> Q e. Prime )   &    |- ( ph -> ( Q pCnt A ) e. NN )   &    |- ( ph -> C e. ZZ )   &    |- ( ph -> ( ( C ^ ( N - 1 ) ) mod N ) = 1 )   &    |- ( ph -> ( ( ( C ^ ( ( N - 1 ) / Q ) ) - 1 ) gcd N ) = 1 )   =>    |- ( ph -> ( Q pCnt A ) <_ ( Q pCnt ( P - 1 ) ) )
Theorem	pockthg 15610*	The generalized Pocklington's theorem. If N - 1 = A x. B where B < A, then N is prime if and only if for every prime factor p of A, there is an x such that x ^ ( N - 1 ) = 1 ( mod N ) and gcd ( x ^ ( ( N - 1 ) / p ) - 1 , N ) = 1. (Contributed by Mario Carneiro, 2-Mar-2014.)
|- ( ph -> A e. NN )   &    |- ( ph -> B e. NN )   &    |- ( ph -> B < A )   &    |- ( ph -> N = ( ( A x. B ) + 1 ) )   &    |- ( ph -> A. p e. Prime ( p || A -> E. x e. ZZ ( ( ( x ^ ( N - 1 ) ) mod N ) = 1 /\ ( ( ( x ^ ( ( N - 1 ) / p ) ) - 1 ) gcd N ) = 1 ) ) )   =>    |- ( ph -> N e. Prime )
Theorem	pockthi 15611	Pocklington's theorem, which gives a sufficient criterion for a number N to be prime. This is the preferred method for verifying large primes, being much more efficient to compute than trial division. This form has been optimized for application to specific large primes; see pockthg 15610 for a more general closed-form version. (Contributed by Mario Carneiro, 2-Mar-2014.)
|- P e. Prime   &    |- G e. NN   &    |- M = ( G x. P )   &    |- N = ( M + 1 )   &    |- D e. NN   &    |- E e. NN   &    |- A e. NN   &    |- M = ( D x. ( P ^ E ) )   &    |- D < ( P ^ E )   &    |- ( ( A ^ M ) mod N ) = ( 1 mod N )   &    |- ( ( ( A ^ G ) - 1 ) gcd N ) = 1   =>    |- N e. Prime
6.2.9  Infinite primes theorem
Theorem	unbenlem 15612*	Lemma for unben 15613. (Contributed by NM, 5-May-2005.) (Revised by Mario Carneiro, 15-Sep-2013.)
|- G = ( rec ( ( x e. _V |-> ( x + 1 ) ) , 1 ) |` om )   =>    |- ( ( A C_ NN /\ A. m e. NN E. n e. A m < n ) -> A ~~ om )
Theorem	unben 15613*	An unbounded set of positive integers is infinite. (Contributed by NM, 5-May-2005.) (Revised by Mario Carneiro, 15-Sep-2013.)
|- ( ( A C_ NN /\ A. m e. NN E. n e. A m < n ) -> A ~~ NN )
Theorem	infpnlem1 15614*	Lemma for infpn 15616. The smallest divisor (greater than 1) M of N ! + 1 is a prime greater than N. (Contributed by NM, 5-May-2005.)
|- K = ( ( ! ` N ) + 1 )   =>    |- ( ( N e. NN /\ M e. NN ) -> ( ( ( 1 < M /\ ( K / M ) e. NN ) /\ A. j e. NN ( ( 1 < j /\ ( K / j ) e. NN ) -> M <_ j ) ) -> ( N < M /\ A. j e. NN ( ( M / j ) e. NN -> ( j = 1 \/ j = M ) ) ) ) )
Theorem	infpnlem2 15615*	Lemma for infpn 15616. For any positive integer N, there exists a prime number j greater than N. (Contributed by NM, 5-May-2005.)
|- K = ( ( ! ` N ) + 1 )   =>    |- ( N e. NN -> E. j e. NN ( N < j /\ A. k e. NN ( ( j / k ) e. NN -> ( k = 1 \/ k = j ) ) ) )
Theorem	infpn 15616*	There exist infinitely many prime numbers: for any positive integer N, there exists a prime number j greater than N. (See infpn2 15617 for the equinumerosity version.) (Contributed by NM, 1-Jun-2006.)
|- ( N e. NN -> E. j e. NN ( N < j /\ A. k e. NN ( ( j / k ) e. NN -> ( k = 1 \/ k = j ) ) ) )
Theorem	infpn2 15617*	There exist infinitely many prime numbers: the set of all primes S is unbounded by infpn 15616, so by unben 15613 it is infinite. This is Metamath 100 proof #11. (Contributed by NM, 5-May-2005.)
|- S = { n e. NN | ( 1 < n /\ A. m e. NN ( ( n / m ) e. NN -> ( m = 1 \/ m = n ) ) ) }   =>    |- S ~~ NN
Theorem	prmunb 15618*	The primes are unbounded. (Contributed by Paul Chapman, 28-Nov-2012.)
|- ( N e. NN -> E. p e. Prime N < p )
Theorem	prminf 15619	There are an infinite number of primes. Theorem 1.7 in [ApostolNT] p. 16. (Contributed by Paul Chapman, 28-Nov-2012.)
|- Prime ~~ NN
6.2.10  Sum of prime reciprocals
Theorem	prmreclem1 15620*	Lemma for prmrec 15626. Properties of the "square part" function, which extracts the m of the decomposition N = r m ^ 2, with m maximal and r squarefree. (Contributed by Mario Carneiro, 5-Aug-2014.)
|- Q = ( n e. NN |-> sup ( { r e. NN | ( r ^ 2 ) || n } , RR , < ) )   =>    |- ( N e. NN -> ( ( Q ` N ) e. NN /\ ( ( Q ` N ) ^ 2 ) || N /\ ( K e. ( ZZ>= ` 2 ) -> -. ( K ^ 2 ) || ( N / ( ( Q ` N ) ^ 2 ) ) ) ) )
Theorem	prmreclem2 15621*	Lemma for prmrec 15626. There are at most 2 ^ K squarefree numbers which divide no primes larger than K. (We could strengthen this to 2 ^ # ( Prime i^i ( 1 ... K ) ) but there's no reason to.) We establish the inequality by showing that the prime counts of the number up to K completely determine it because all higher prime counts are zero, and they are all at most 1 because no square divides the number, so there are at most 2 ^ K possibilities. (Contributed by Mario Carneiro, 5-Aug-2014.)
|- F = ( n e. NN |-> if ( n e. Prime , ( 1 / n ) , 0 ) )   &    |- ( ph -> K e. NN )   &    |- ( ph -> N e. NN )   &    |- M = { n e. ( 1 ... N ) | A. p e. ( Prime \ ( 1 ... K ) ) -. p || n }   &    |- Q = ( n e. NN |-> sup ( { r e. NN | ( r ^ 2 ) || n } , RR , < ) )   =>    |- ( ph -> ( # ` { x e. M | ( Q ` x ) = 1 } ) <_ ( 2 ^ K ) )
Theorem	prmreclem3 15622*	Lemma for prmrec 15626. The main inequality established here is # M <_ # { x e. M | ( Q ` x ) = 1 } x. sqr N, where { x e. M | ( Q ` x ) = 1 } is the set of squarefree numbers in M. This is demonstrated by the map y |-> <. y / ( Q ` y ) ^ 2 , ( Q ` y ) >. where Q ` y is the largest number whose square divides y. (Contributed by Mario Carneiro, 5-Aug-2014.)
|- F = ( n e. NN |-> if ( n e. Prime , ( 1 / n ) , 0 ) )   &    |- ( ph -> K e. NN )   &    |- ( ph -> N e. NN )   &    |- M = { n e. ( 1 ... N ) | A. p e. ( Prime \ ( 1 ... K ) ) -. p || n }   &    |- Q = ( n e. NN |-> sup ( { r e. NN | ( r ^ 2 ) || n } , RR , < ) )   =>    |- ( ph -> ( # ` M ) <_ ( ( 2 ^ K ) x. ( sqr ` N ) ) )
Theorem	prmreclem4 15623*	Lemma for prmrec 15626. Show by induction that the indexed (nondisjoint) union W ` k is at most the size of the prime reciprocal series. The key counting lemma is hashdvds 15480, to show that the number of numbers in 1 ... N that divide k is at most N / k. (Contributed by Mario Carneiro, 6-Aug-2014.)
|- F = ( n e. NN |-> if ( n e. Prime , ( 1 / n ) , 0 ) )   &    |- ( ph -> K e. NN )   &    |- ( ph -> N e. NN )   &    |- M = { n e. ( 1 ... N ) | A. p e. ( Prime \ ( 1 ... K ) ) -. p || n }   &    |- ( ph -> seq 1 ( + , F ) e. dom ~~> )   &    |- ( ph -> sum_ k e. ( ZZ>= ` ( K + 1 ) ) if ( k e. Prime , ( 1 / k ) , 0 ) < ( 1 / 2 ) )   &    |- W = ( p e. NN |-> { n e. ( 1 ... N ) | ( p e. Prime /\ p || n ) } )   =>    |- ( ph -> ( N e. ( ZZ>= ` K ) -> ( # ` U_ k e. ( ( K + 1 ) ... N ) ( W ` k ) ) <_ ( N x. sum_ k e. ( ( K + 1 ) ... N ) if ( k e. Prime , ( 1 / k ) , 0 ) ) ) )
Theorem	prmreclem5 15624*	Lemma for prmrec 15626. Here we show the inequality N / 2 < # M by decomposing the set ( 1 ... N ) into the disjoint union of the set M of those numbers that are not divisible by any "large" primes (above K) and the indexed union over K < k of the numbers W ` k that divide the prime k. By prmreclem4 15623 the second of these has size less than N times the prime reciprocal series, which is less than 1 / 2 by assumption, we find that the complementary part M must be at least N / 2 large. (Contributed by Mario Carneiro, 6-Aug-2014.)
|- F = ( n e. NN |-> if ( n e. Prime , ( 1 / n ) , 0 ) )   &    |- ( ph -> K e. NN )   &    |- ( ph -> N e. NN )   &    |- M = { n e. ( 1 ... N ) | A. p e. ( Prime \ ( 1 ... K ) ) -. p || n }   &    |- ( ph -> seq 1 ( + , F ) e. dom ~~> )   &    |- ( ph -> sum_ k e. ( ZZ>= ` ( K + 1 ) ) if ( k e. Prime , ( 1 / k ) , 0 ) < ( 1 / 2 ) )   &    |- W = ( p e. NN |-> { n e. ( 1 ... N ) | ( p e. Prime /\ p || n ) } )   =>    |- ( ph -> ( N / 2 ) < ( ( 2 ^ K ) x. ( sqr ` N ) ) )
Theorem	prmreclem6 15625*	Lemma for prmrec 15626. If the series F was convergent, there would be some k such that the sum starting from k + 1 sums to less than 1 / 2; this is a sufficient hypothesis for prmreclem5 15624 to produce the contradictory bound N / 2 < ( 2 ^ k ) sqr N, which is false for N = 2 ^ ( 2 k + 2 ). (Contributed by Mario Carneiro, 6-Aug-2014.)
|- F = ( n e. NN |-> if ( n e. Prime , ( 1 / n ) , 0 ) )   =>    |- -. seq 1 ( + , F ) e. dom ~~>
Theorem	prmrec 15626*	The sum of the reciprocals of the primes diverges. Theorem 1.13 in [ApostolNT] p. 18. This is the "second" proof at http://en.wikipedia.org/wiki/Prime_harmonic_series, attributed to Paul Erdős. This is Metamath 100 proof #81. (Contributed by Mario Carneiro, 6-Aug-2014.)
|- F = ( n e. NN |-> sum_ k e. ( Prime i^i ( 1 ... n ) ) ( 1 / k ) )   =>    |- -. F e. dom ~~>
6.2.11  Fundamental theorem of arithmetic
Theorem	1arithlem1 15627*	Lemma for 1arith 15631. (Contributed by Mario Carneiro, 30-May-2014.)
|- M = ( n e. NN |-> ( p e. Prime |-> ( p pCnt n ) ) )   =>    |- ( N e. NN -> ( M ` N ) = ( p e. Prime |-> ( p pCnt N ) ) )
Theorem	1arithlem2 15628*	Lemma for 1arith 15631. (Contributed by Mario Carneiro, 30-May-2014.)
|- M = ( n e. NN |-> ( p e. Prime |-> ( p pCnt n ) ) )   =>    |- ( ( N e. NN /\ P e. Prime ) -> ( ( M ` N ) ` P ) = ( P pCnt N ) )
Theorem	1arithlem3 15629*	Lemma for 1arith 15631. (Contributed by Mario Carneiro, 30-May-2014.)
|- M = ( n e. NN |-> ( p e. Prime |-> ( p pCnt n ) ) )   =>    |- ( N e. NN -> ( M ` N ) : Prime --> NN0 )
Theorem	1arithlem4 15630*	Lemma for 1arith 15631. (Contributed by Mario Carneiro, 30-May-2014.)
|- M = ( n e. NN |-> ( p e. Prime |-> ( p pCnt n ) ) )   &    |- G = ( y e. NN |-> if ( y e. Prime , ( y ^ ( F ` y ) ) , 1 ) )   &    |- ( ph -> F : Prime --> NN0 )   &    |- ( ph -> N e. NN )   &    |- ( ( ph /\ ( q e. Prime /\ N <_ q ) ) -> ( F ` q ) = 0 )   =>    |- ( ph -> E. x e. NN F = ( M ` x ) )
Theorem	1arith 15631*	Fundamental theorem of arithmetic, where a prime factorization is represented as a sequence of prime exponents, for which only finitely many primes have nonzero exponent. The function M maps the set of positive integers one-to-one onto the set of prime factorizations R. (Contributed by Paul Chapman, 17-Nov-2012.) (Proof shortened by Mario Carneiro, 30-May-2014.)
|- M = ( n e. NN |-> ( p e. Prime |-> ( p pCnt n ) ) )   &    |- R = { e e. ( NN0 ^m Prime ) | ( `' e " NN ) e. Fin }   =>    |- M : NN -1-1-onto-> R
Theorem	1arith2 15632*	Fundamental theorem of arithmetic, where a prime factorization is represented as a finite monotonic 1-based sequence of primes. Every positive integer has a unique prime factorization. Theorem 1.10 in [ApostolNT] p. 17. This is Metamath 100 proof #80. (Contributed by Paul Chapman, 17-Nov-2012.) (Revised by Mario Carneiro, 30-May-2014.)
|- M = ( n e. NN |-> ( p e. Prime |-> ( p pCnt n ) ) )   &    |- R = { e e. ( NN0 ^m Prime ) | ( `' e " NN ) e. Fin }   =>    |- A. z e. NN E! g e. R ( M ` z ) = g
6.2.12  Lagrange's four-square theorem
Syntax	cgz 15633	Extend class notation with the set of gaussian integers.
class ZZ[_i]
Definition	df-gz 15634	Define the set of gaussian integers, which are complex numbers whose real and imaginary parts are integers. (Note that the [ _i ] is actually part of the symbol token and has no independent meaning.) (Contributed by Mario Carneiro, 14-Jul-2014.)
|- ZZ[_i] = { x e. CC | ( ( Re ` x ) e. ZZ /\ ( Im ` x ) e. ZZ ) }
Theorem	elgz 15635	Elementhood in the gaussian integers. (Contributed by Mario Carneiro, 14-Jul-2014.)
|- ( A e. ZZ[_i] <-> ( A e. CC /\ ( Re ` A ) e. ZZ /\ ( Im ` A ) e. ZZ ) )
Theorem	gzcn 15636	A gaussian integer is a complex number. (Contributed by Mario Carneiro, 14-Jul-2014.)
|- ( A e. ZZ[_i] -> A e. CC )
Theorem	zgz 15637	An integer is a gaussian integer. (Contributed by Mario Carneiro, 14-Jul-2014.)
|- ( A e. ZZ -> A e. ZZ[_i] )
Theorem	igz 15638	_i is a gaussian integer. (Contributed by Mario Carneiro, 14-Jul-2014.)
|- _i e. ZZ[_i]
Theorem	gznegcl 15639	The gaussian integers are closed under negation. (Contributed by Mario Carneiro, 14-Jul-2014.)
|- ( A e. ZZ[_i] -> -u A e. ZZ[_i] )
Theorem	gzcjcl 15640	The gaussian integers are closed under conjugation. (Contributed by Mario Carneiro, 14-Jul-2014.)
|- ( A e. ZZ[_i] -> ( * ` A ) e. ZZ[_i] )
Theorem	gzaddcl 15641	The gaussian integers are closed under addition. (Contributed by Mario Carneiro, 14-Jul-2014.)
|- ( ( A e. ZZ[_i] /\ B e. ZZ[_i] ) -> ( A + B ) e. ZZ[_i] )
Theorem	gzmulcl 15642	The gaussian integers are closed under multiplication. (Contributed by Mario Carneiro, 14-Jul-2014.)
|- ( ( A e. ZZ[_i] /\ B e. ZZ[_i] ) -> ( A x. B ) e. ZZ[_i] )
Theorem	gzreim 15643	Construct a gaussian integer from real and imaginary parts. (Contributed by Mario Carneiro, 16-Jul-2014.)
|- ( ( A e. ZZ /\ B e. ZZ ) -> ( A + ( _i x. B ) ) e. ZZ[_i] )
Theorem	gzsubcl 15644	The gaussian integers are closed under subtraction. (Contributed by Mario Carneiro, 14-Jul-2014.)
|- ( ( A e. ZZ[_i] /\ B e. ZZ[_i] ) -> ( A - B ) e. ZZ[_i] )
Theorem	gzabssqcl 15645	The squared norm of a gaussian integer is an integer. (Contributed by Mario Carneiro, 16-Jul-2014.)
|- ( A e. ZZ[_i] -> ( ( abs ` A ) ^ 2 ) e. NN0 )
Theorem	4sqlem5 15646	Lemma for 4sq 15668. (Contributed by Mario Carneiro, 15-Jul-2014.)
|- ( ph -> A e. ZZ )   &    |- ( ph -> M e. NN )   &    |- B = ( ( ( A + ( M / 2 ) ) mod M ) - ( M / 2 ) )   =>    |- ( ph -> ( B e. ZZ /\ ( ( A - B ) / M ) e. ZZ ) )
Theorem	4sqlem6 15647	Lemma for 4sq 15668. (Contributed by Mario Carneiro, 15-Jul-2014.)
|- ( ph -> A e. ZZ )   &    |- ( ph -> M e. NN )   &    |- B = ( ( ( A + ( M / 2 ) ) mod M ) - ( M / 2 ) )   =>    |- ( ph -> ( -u ( M / 2 ) <_ B /\ B < ( M / 2 ) ) )
Theorem	4sqlem7 15648	Lemma for 4sq 15668. (Contributed by Mario Carneiro, 15-Jul-2014.)
|- ( ph -> A e. ZZ )   &    |- ( ph -> M e. NN )   &    |- B = ( ( ( A + ( M / 2 ) ) mod M ) - ( M / 2 ) )   =>    |- ( ph -> ( B ^ 2 ) <_ ( ( ( M ^ 2 ) / 2 ) / 2 ) )
Theorem	4sqlem8 15649	Lemma for 4sq 15668. (Contributed by Mario Carneiro, 15-Jul-2014.)
|- ( ph -> A e. ZZ )   &    |- ( ph -> M e. NN )   &    |- B = ( ( ( A + ( M / 2 ) ) mod M ) - ( M / 2 ) )   =>    |- ( ph -> M || ( ( A ^ 2 ) - ( B ^ 2 ) ) )
Theorem	4sqlem9 15650	Lemma for 4sq 15668. (Contributed by Mario Carneiro, 15-Jul-2014.)
|- ( ph -> A e. ZZ )   &    |- ( ph -> M e. NN )   &    |- B = ( ( ( A + ( M / 2 ) ) mod M ) - ( M / 2 ) )   &    |- ( ( ph /\ ps ) -> ( B ^ 2 ) = 0 )   =>    |- ( ( ph /\ ps ) -> ( M ^ 2 ) || ( A ^ 2 ) )
Theorem	4sqlem10 15651	Lemma for 4sq 15668. (Contributed by Mario Carneiro, 16-Jul-2014.)
|- ( ph -> A e. ZZ )   &    |- ( ph -> M e. NN )   &    |- B = ( ( ( A + ( M / 2 ) ) mod M ) - ( M / 2 ) )   &    |- ( ( ph /\ ps ) -> ( ( ( ( M ^ 2 ) / 2 ) / 2 ) - ( B ^ 2 ) ) = 0 )   =>    |- ( ( ph /\ ps ) -> ( M ^ 2 ) || ( ( A ^ 2 ) - ( ( ( M ^ 2 ) / 2 ) / 2 ) ) )
Theorem	4sqlem1 15652*	Lemma for 4sq 15668. The set S is the set of all numbers that are expressible as a sum of four squares. Our goal is to show that S = NN0; here we show one subset direction. (Contributed by Mario Carneiro, 14-Jul-2014.)
|- S = { n | E. x e. ZZ E. y e. ZZ E. z e. ZZ E. w e. ZZ n = ( ( ( x ^ 2 ) + ( y ^ 2 ) ) + ( ( z ^ 2 ) + ( w ^ 2 ) ) ) }   =>    |- S C_ NN0
Theorem	4sqlem2 15653*	Lemma for 4sq 15668. Change bound variables in S. (Contributed by Mario Carneiro, 14-Jul-2014.)
|- S = { n | E. x e. ZZ E. y e. ZZ E. z e. ZZ E. w e. ZZ n = ( ( ( x ^ 2 ) + ( y ^ 2 ) ) + ( ( z ^ 2 ) + ( w ^ 2 ) ) ) }   =>    |- ( A e. S <-> E. a e. ZZ E. b e. ZZ E. c e. ZZ E. d e. ZZ A = ( ( ( a ^ 2 ) + ( b ^ 2 ) ) + ( ( c ^ 2 ) + ( d ^ 2 ) ) ) )
Theorem	4sqlem3 15654*	Lemma for 4sq 15668. Sufficient condition to be in S. (Contributed by Mario Carneiro, 14-Jul-2014.)
|- S = { n | E. x e. ZZ E. y e. ZZ E. z e. ZZ E. w e. ZZ n = ( ( ( x ^ 2 ) + ( y ^ 2 ) ) + ( ( z ^ 2 ) + ( w ^ 2 ) ) ) }   =>    |- ( ( ( A e. ZZ /\ B e. ZZ ) /\ ( C e. ZZ /\ D e. ZZ ) ) -> ( ( ( A ^ 2 ) + ( B ^ 2 ) ) + ( ( C ^ 2 ) + ( D ^ 2 ) ) ) e. S )
Theorem	4sqlem4a 15655*	Lemma for 4sqlem4 15656. (Contributed by Mario Carneiro, 14-Jul-2014.)
|- S = { n | E. x e. ZZ E. y e. ZZ E. z e. ZZ E. w e. ZZ n = ( ( ( x ^ 2 ) + ( y ^ 2 ) ) + ( ( z ^ 2 ) + ( w ^ 2 ) ) ) }   =>    |- ( ( A e. ZZ[_i] /\ B e. ZZ[_i] ) -> ( ( ( abs ` A ) ^ 2 ) + ( ( abs ` B ) ^ 2 ) ) e. S )
Theorem	4sqlem4 15656*	Lemma for 4sq 15668. We can express the four-square property more compactly in terms of gaussian integers, because the norms of gaussian integers are exactly sums of two squares. (Contributed by Mario Carneiro, 14-Jul-2014.)
|- S = { n | E. x e. ZZ E. y e. ZZ E. z e. ZZ E. w e. ZZ n = ( ( ( x ^ 2 ) + ( y ^ 2 ) ) + ( ( z ^ 2 ) + ( w ^ 2 ) ) ) }   =>    |- ( A e. S <-> E. u e. ZZ[_i] E. v e. ZZ[_i] A = ( ( ( abs ` u ) ^ 2 ) + ( ( abs ` v ) ^ 2 ) ) )
Theorem	mul4sqlem 15657*	Lemma for mul4sq 15658: algebraic manipulations. The extra assumptions involving M are for a part of 4sqlem17 15665 which needs to know not just that the product is a sum of squares, but also that it preserves divisibility by M. (Contributed by Mario Carneiro, 14-Jul-2014.)
|- S = { n | E. x e. ZZ E. y e. ZZ E. z e. ZZ E. w e. ZZ n = ( ( ( x ^ 2 ) + ( y ^ 2 ) ) + ( ( z ^ 2 ) + ( w ^ 2 ) ) ) }   &    |- ( ph -> A e. ZZ[_i] )   &    |- ( ph -> B e. ZZ[_i] )   &    |- ( ph -> C e. ZZ[_i] )   &    |- ( ph -> D e. ZZ[_i] )   &    |- X = ( ( ( abs ` A ) ^ 2 ) + ( ( abs ` B ) ^ 2 ) )   &    |- Y = ( ( ( abs ` C ) ^ 2 ) + ( ( abs ` D ) ^ 2 ) )   &    |- ( ph -> M e. NN )   &    |- ( ph -> ( ( A - C ) / M ) e. ZZ[_i] )   &    |- ( ph -> ( ( B - D ) / M ) e. ZZ[_i] )   &    |- ( ph -> ( X / M ) e. NN0 )   =>    |- ( ph -> ( ( X / M ) x. ( Y / M ) ) e. S )
Theorem	mul4sq 15658*	Euler's four-square identity: The product of two sums of four squares is also a sum of four squares. This is usually quoted as an explicit formula involving eight real variables; we save some time by working with complex numbers (gaussian integers) instead, so that we only have to work with four variables, and also hiding the actual formula for the product in the proof of mul4sqlem 15657. (For the curious, the explicit formula that is used is ( | a | ^ 2 + | b | ^ 2 ) ( | c | ^ 2 + | d | ^ 2 ) = | a * x. c + b x. d * | ^ 2 + | a * x. d - b x. c * | ^ 2.) (Contributed by Mario Carneiro, 14-Jul-2014.)
|- S = { n | E. x e. ZZ E. y e. ZZ E. z e. ZZ E. w e. ZZ n = ( ( ( x ^ 2 ) + ( y ^ 2 ) ) + ( ( z ^ 2 ) + ( w ^ 2 ) ) ) }   =>    |- ( ( A e. S /\ B e. S ) -> ( A x. B ) e. S )
Theorem	4sqlem11 15659*	Lemma for 4sq 15668. Use the pigeonhole principle to show that the sets { m ^ 2 | m e. ( 0 ... N ) } and { -u 1 - n ^ 2 | n e. ( 0 ... N ) } have a common element, mod P. (Contributed by Mario Carneiro, 15-Jul-2014.)
|- S = { n | E. x e. ZZ E. y e. ZZ E. z e. ZZ E. w e. ZZ n = ( ( ( x ^ 2 ) + ( y ^ 2 ) ) + ( ( z ^ 2 ) + ( w ^ 2 ) ) ) }   &    |- ( ph -> N e. NN )   &    |- ( ph -> P = ( ( 2 x. N ) + 1 ) )   &    |- ( ph -> P e. Prime )   &    |- A = { u | E. m e. ( 0 ... N ) u = ( ( m ^ 2 ) mod P ) }   &    |- F = ( v e. A |-> ( ( P - 1 ) - v ) )   =>    |- ( ph -> ( A i^i ran F ) =/= (/) )
Theorem	4sqlem12 15660*	Lemma for 4sq 15668. For any odd prime P, there is a k < P such that k P - 1 is a sum of two squares. (Contributed by Mario Carneiro, 15-Jul-2014.)
|- S = { n | E. x e. ZZ E. y e. ZZ E. z e. ZZ E. w e. ZZ n = ( ( ( x ^ 2 ) + ( y ^ 2 ) ) + ( ( z ^ 2 ) + ( w ^ 2 ) ) ) }   &    |- ( ph -> N e. NN )   &    |- ( ph -> P = ( ( 2 x. N ) + 1 ) )   &    |- ( ph -> P e. Prime )   &    |- A = { u | E. m e. ( 0 ... N ) u = ( ( m ^ 2 ) mod P ) }   &    |- F = ( v e. A |-> ( ( P - 1 ) - v ) )   =>    |- ( ph -> E. k e. ( 1 ... ( P - 1 ) ) E. u e. ZZ[_i] ( ( ( abs ` u ) ^ 2 ) + 1 ) = ( k x. P ) )
Theorem	4sqlem13 15661*	Lemma for 4sq 15668. (Contributed by Mario Carneiro, 16-Jul-2014.) (Revised by AV, 14-Sep-2020.)
|- S = { n | E. x e. ZZ E. y e. ZZ E. z e. ZZ E. w e. ZZ n = ( ( ( x ^ 2 ) + ( y ^ 2 ) ) + ( ( z ^ 2 ) + ( w ^ 2 ) ) ) }   &    |- ( ph -> N e. NN )   &    |- ( ph -> P = ( ( 2 x. N ) + 1 ) )   &    |- ( ph -> P e. Prime )   &    |- ( ph -> ( 0 ... ( 2 x. N ) ) C_ S )   &    |- T = { i e. NN | ( i x. P ) e. S }   &    |- M = inf ( T , RR , < )   =>    |- ( ph -> ( T =/= (/) /\ M < P ) )
Theorem	4sqlem14 15662*	Lemma for 4sq 15668. (Contributed by Mario Carneiro, 16-Jul-2014.) (Revised by AV, 14-Sep-2020.)
|- S = { n | E. x e. ZZ E. y e. ZZ E. z e. ZZ E. w e. ZZ n = ( ( ( x ^ 2 ) + ( y ^ 2 ) ) + ( ( z ^ 2 ) + ( w ^ 2 ) ) ) }   &    |- ( ph -> N e. NN )   &    |- ( ph -> P = ( ( 2 x. N ) + 1 ) )   &    |- ( ph -> P e. Prime )   &    |- ( ph -> ( 0 ... ( 2 x. N ) ) C_ S )   &    |- T = { i e. NN | ( i x. P ) e. S }   &    |- M = inf ( T , RR , < )   &    |- ( ph -> M e. ( ZZ>= ` 2 ) )   &    |- ( ph -> A e. ZZ )   &    |- ( ph -> B e. ZZ )   &    |- ( ph -> C e. ZZ )   &    |- ( ph -> D e. ZZ )   &    |- E = ( ( ( A + ( M / 2 ) ) mod M ) - ( M / 2 ) )   &    |- F = ( ( ( B + ( M / 2 ) ) mod M ) - ( M / 2 ) )   &    |- G = ( ( ( C + ( M / 2 ) ) mod M ) - ( M / 2 ) )   &    |- H = ( ( ( D + ( M / 2 ) ) mod M ) - ( M / 2 ) )   &    |- R = ( ( ( ( E ^ 2 ) + ( F ^ 2 ) ) + ( ( G ^ 2 ) + ( H ^ 2 ) ) ) / M )   &    |- ( ph -> ( M x. P ) = ( ( ( A ^ 2 ) + ( B ^ 2 ) ) + ( ( C ^ 2 ) + ( D ^ 2 ) ) ) )   =>    |- ( ph -> R e. NN0 )
Theorem	4sqlem15 15663*	Lemma for 4sq 15668. (Contributed by Mario Carneiro, 16-Jul-2014.) (Revised by AV, 14-Sep-2020.)
|- S = { n | E. x e. ZZ E. y e. ZZ E. z e. ZZ E. w e. ZZ n = ( ( ( x ^ 2 ) + ( y ^ 2 ) ) + ( ( z ^ 2 ) + ( w ^ 2 ) ) ) }   &    |- ( ph -> N e. NN )   &    |- ( ph -> P = ( ( 2 x. N ) + 1 ) )   &    |- ( ph -> P e. Prime )   &    |- ( ph -> ( 0 ... ( 2 x. N ) ) C_ S )   &    |- T = { i e. NN | ( i x. P ) e. S }   &    |- M = inf ( T , RR , < )   &    |- ( ph -> M e. ( ZZ>= ` 2 ) )   &    |- ( ph -> A e. ZZ )   &    |- ( ph -> B e. ZZ )   &    |- ( ph -> C e. ZZ )   &    |- ( ph -> D e. ZZ )   &    |- E = ( ( ( A + ( M / 2 ) ) mod M ) - ( M / 2 ) )   &    |- F = ( ( ( B + ( M / 2 ) ) mod M ) - ( M / 2 ) )   &    |- G = ( ( ( C + ( M / 2 ) ) mod M ) - ( M / 2 ) )   &    |- H = ( ( ( D + ( M / 2 ) ) mod M ) - ( M / 2 ) )   &    |- R = ( ( ( ( E ^ 2 ) + ( F ^ 2 ) ) + ( ( G ^ 2 ) + ( H ^ 2 ) ) ) / M )   &    |- ( ph -> ( M x. P ) = ( ( ( A ^ 2 ) + ( B ^ 2 ) ) + ( ( C ^ 2 ) + ( D ^ 2 ) ) ) )   =>    |- ( ( ph /\ R = M ) -> ( ( ( ( ( ( M ^ 2 ) / 2 ) / 2 ) - ( E ^ 2 ) ) = 0 /\ ( ( ( ( M ^ 2 ) / 2 ) / 2 ) - ( F ^ 2 ) ) = 0 ) /\ ( ( ( ( ( M ^ 2 ) / 2 ) / 2 ) - ( G ^ 2 ) ) = 0 /\ ( ( ( ( M ^ 2 ) / 2 ) / 2 ) - ( H ^ 2 ) ) = 0 ) ) )
Theorem	4sqlem16 15664*	Lemma for 4sq 15668. (Contributed by Mario Carneiro, 16-Jul-2014.) (Revised by AV, 14-Sep-2020.)
|- S = { n | E. x e. ZZ E. y e. ZZ E. z e. ZZ E. w e. ZZ n = ( ( ( x ^ 2 ) + ( y ^ 2 ) ) + ( ( z ^ 2 ) + ( w ^ 2 ) ) ) }   &    |- ( ph -> N e. NN )   &    |- ( ph -> P = ( ( 2 x. N ) + 1 ) )   &    |- ( ph -> P e. Prime )   &    |- ( ph -> ( 0 ... ( 2 x. N ) ) C_ S )   &    |- T = { i e. NN | ( i x. P ) e. S }   &    |- M = inf ( T , RR , < )   &    |- ( ph -> M e. ( ZZ>= ` 2 ) )   &    |- ( ph -> A e. ZZ )   &    |- ( ph -> B e. ZZ )   &    |- ( ph -> C e. ZZ )   &    |- ( ph -> D e. ZZ )   &    |- E = ( ( ( A + ( M / 2 ) ) mod M ) - ( M / 2 ) )   &    |- F = ( ( ( B + ( M / 2 ) ) mod M ) - ( M / 2 ) )   &    |- G = ( ( ( C + ( M / 2 ) ) mod M ) - ( M / 2 ) )   &    |- H = ( ( ( D + ( M / 2 ) ) mod M ) - ( M / 2 ) )   &    |- R = ( ( ( ( E ^ 2 ) + ( F ^ 2 ) ) + ( ( G ^ 2 ) + ( H ^ 2 ) ) ) / M )   &    |- ( ph -> ( M x. P ) = ( ( ( A ^ 2 ) + ( B ^ 2 ) ) + ( ( C ^ 2 ) + ( D ^ 2 ) ) ) )   =>    |- ( ph -> ( R <_ M /\ ( ( R = 0 \/ R = M ) -> ( M ^ 2 ) || ( M x. P ) ) ) )
Theorem	4sqlem17 15665*	Lemma for 4sq 15668. (Contributed by Mario Carneiro, 16-Jul-2014.) (Revised by AV, 14-Sep-2020.)
|- S = { n | E. x e. ZZ E. y e. ZZ E. z e. ZZ E. w e. ZZ n = ( ( ( x ^ 2 ) + ( y ^ 2 ) ) + ( ( z ^ 2 ) + ( w ^ 2 ) ) ) }   &    |- ( ph -> N e. NN )   &    |- ( ph -> P = ( ( 2 x. N ) + 1 ) )   &    |- ( ph -> P e. Prime )   &    |- ( ph -> ( 0 ... ( 2 x. N ) ) C_ S )   &    |- T = { i e. NN | ( i x. P ) e. S }   &    |- M = inf ( T , RR , < )   &    |- ( ph -> M e. ( ZZ>= ` 2 ) )   &    |- ( ph -> A e. ZZ )   &    |- ( ph -> B e. ZZ )   &    |- ( ph -> C e. ZZ )   &    |- ( ph -> D e. ZZ )   &    |- E = ( ( ( A + ( M / 2 ) ) mod M ) - ( M / 2 ) )   &    |- F = ( ( ( B + ( M / 2 ) ) mod M ) - ( M / 2 ) )   &    |- G = ( ( ( C + ( M / 2 ) ) mod M ) - ( M / 2 ) )   &    |- H = ( ( ( D + ( M / 2 ) ) mod M ) - ( M / 2 ) )   &    |- R = ( ( ( ( E ^ 2 ) + ( F ^ 2 ) ) + ( ( G ^ 2 ) + ( H ^ 2 ) ) ) / M )   &    |- ( ph -> ( M x. P ) = ( ( ( A ^ 2 ) + ( B ^ 2 ) ) + ( ( C ^ 2 ) + ( D ^ 2 ) ) ) )   =>    |- -. ph
Theorem	4sqlem18 15666*	Lemma for 4sq 15668. Inductive step, odd prime case. (Contributed by Mario Carneiro, 16-Jul-2014.) (Revised by AV, 14-Sep-2020.)
|- S = { n | E. x e. ZZ E. y e. ZZ E. z e. ZZ E. w e. ZZ n = ( ( ( x ^ 2 ) + ( y ^ 2 ) ) + ( ( z ^ 2 ) + ( w ^ 2 ) ) ) }   &    |- ( ph -> N e. NN )   &    |- ( ph -> P = ( ( 2 x. N ) + 1 ) )   &    |- ( ph -> P e. Prime )   &    |- ( ph -> ( 0 ... ( 2 x. N ) ) C_ S )   &    |- T = { i e. NN | ( i x. P ) e. S }   &    |- M = inf ( T , RR , < )   =>    |- ( ph -> P e. S )
Theorem	4sqlem19 15667*	Lemma for 4sq 15668. The proof is by strong induction - we show that if all the integers less than k are in S, then k is as well. In this part of the proof we do the induction argument and dispense with all the cases except the odd prime case, which is sent to 4sqlem18 15666. If k is 0 , 1 , 2, we show k e. S directly; otherwise if k is composite, k is the product of two numbers less than it (and hence in S by assumption), so by mul4sq 15658 k e. S. (Contributed by Mario Carneiro, 14-Jul-2014.) (Revised by Mario Carneiro, 20-Jun-2015.)
|- S = { n | E. x e. ZZ E. y e. ZZ E. z e. ZZ E. w e. ZZ n = ( ( ( x ^ 2 ) + ( y ^ 2 ) ) + ( ( z ^ 2 ) + ( w ^ 2 ) ) ) }   =>    |- NN0 = S
Theorem	4sq 15668*	Lagrange's four-square theorem, or Bachet's conjecture: every nonnegative integer is expressible as a sum of four squares. This is Metamath 100 proof #19. (Contributed by Mario Carneiro, 16-Jul-2014.)
|- ( A e. NN0 <-> E. a e. ZZ E. b e. ZZ E. c e. ZZ E. d e. ZZ A = ( ( ( a ^ 2 ) + ( b ^ 2 ) ) + ( ( c ^ 2 ) + ( d ^ 2 ) ) ) )
6.2.13  Van der Waerden's theorem
Syntax	cvdwa 15669	The arithmetic progression function.
class AP
Syntax	cvdwm 15670	The monochromatic arithmetic progression predicate.
class MonoAP
Syntax	cvdwp 15671	The polychromatic arithmetic progression predicate.
class PolyAP
Definition	df-vdwap 15672*	Define the arithmetic progression function, which takes as input a length k, a start point a, and a step d and outputs the set of points in this progression. (Contributed by Mario Carneiro, 18-Aug-2014.)
|- AP = ( k e. NN0 |-> ( a e. NN , d e. NN |-> ran ( m e. ( 0 ... ( k - 1 ) ) |-> ( a + ( m x. d ) ) ) ) )
Definition	df-vdwmc 15673*	Define the "contains a monochromatic AP" predicate. (Contributed by Mario Carneiro, 18-Aug-2014.)
|- MonoAP = { <. k , f >. | E. c ( ran (AP ` k ) i^i ~P ( `' f " { c } ) ) =/= (/) }
Definition	df-vdwpc 15674*	Define the "contains a polychromatic collection of APs" predicate. See vdwpc 15684 for more information. (Contributed by Mario Carneiro, 18-Aug-2014.)
|- PolyAP = { <. <. m , k >. , f >. | E. a e. NN E. d e. ( NN ^m ( 1 ... m ) ) ( A. i e. ( 1 ... m ) ( ( a + ( d ` i ) ) (AP ` k ) ( d ` i ) ) C_ ( `' f " { ( f ` ( a + ( d ` i ) ) ) } ) /\ ( # ` ran ( i e. ( 1 ... m ) |-> ( f ` ( a + ( d ` i ) ) ) ) ) = m ) }
Theorem	vdwapfval 15675*	Define the arithmetic progression function, which takes as input a length k, a start point a, and a step d and outputs the set of points in this progression. (Contributed by Mario Carneiro, 18-Aug-2014.)
|- ( K e. NN0 -> (AP ` K ) = ( a e. NN , d e. NN |-> ran ( m e. ( 0 ... ( K - 1 ) ) |-> ( a + ( m x. d ) ) ) ) )
Theorem	vdwapf 15676	The arithmetic progression function is a function. (Contributed by Mario Carneiro, 18-Aug-2014.)
|- ( K e. NN0 -> (AP ` K ) : ( NN X. NN ) --> ~P NN )
Theorem	vdwapval 15677*	Value of the arithmetic progression function. (Contributed by Mario Carneiro, 18-Aug-2014.)
|- ( ( K e. NN0 /\ A e. NN /\ D e. NN ) -> ( X e. ( A (AP ` K ) D ) <-> E. m e. ( 0 ... ( K - 1 ) ) X = ( A + ( m x. D ) ) ) )
Theorem	vdwapun 15678	Remove the first element of an arithmetic progression. (Contributed by Mario Carneiro, 11-Sep-2014.)
|- ( ( K e. NN0 /\ A e. NN /\ D e. NN ) -> ( A (AP ` ( K + 1 ) ) D ) = ( { A } u. ( ( A + D ) (AP ` K ) D ) ) )
Theorem	vdwapid1 15679	The first element of an arithmetic progression. (Contributed by Mario Carneiro, 12-Sep-2014.)
|- ( ( K e. NN /\ A e. NN /\ D e. NN ) -> A e. ( A (AP ` K ) D ) )
Theorem	vdwap0 15680	Value of a length-1 arithmetic progression. (Contributed by Mario Carneiro, 18-Aug-2014.)
|- ( ( A e. NN /\ D e. NN ) -> ( A (AP ` 0 ) D ) = (/) )
Theorem	vdwap1 15681	Value of a length-1 arithmetic progression. (Contributed by Mario Carneiro, 18-Aug-2014.)
|- ( ( A e. NN /\ D e. NN ) -> ( A (AP ` 1 ) D ) = { A } )
Theorem	vdwmc 15682*	The predicate " The <. R , N >.-coloring F contains a monochromatic AP of length K". (Contributed by Mario Carneiro, 18-Aug-2014.)
|- X e. _V   &    |- ( ph -> K e. NN0 )   &    |- ( ph -> F : X --> R )   =>    |- ( ph -> ( K MonoAP F <-> E. c E. a e. NN E. d e. NN ( a (AP ` K ) d ) C_ ( `' F " { c } ) ) )
Theorem	vdwmc2 15683*	Expand out the definition of an arithmetic progression. (Contributed by Mario Carneiro, 18-Aug-2014.)
|- X e. _V   &    |- ( ph -> K e. NN0 )   &    |- ( ph -> F : X --> R )   &    |- ( ph -> A e. X )   =>    |- ( ph -> ( K MonoAP F <-> E. c e. R E. a e. NN E. d e. NN A. m e. ( 0 ... ( K - 1 ) ) ( a + ( m x. d ) ) e. ( `' F " { c } ) ) )
Theorem	vdwpc 15684*	The predicate " The coloring F contains a polychromatic M-tuple of AP's of length K". A polychromatic M-tuple of AP's is a set of AP's with the same base point but different step lengths, such that each individual AP is monochromatic, but the AP's all have mutually distinct colors. (The common basepoint is not required to have the same color as any of the AP's.) (Contributed by Mario Carneiro, 18-Aug-2014.)
|- X e. _V   &    |- ( ph -> K e. NN0 )   &    |- ( ph -> F : X --> R )   &    |- ( ph -> M e. NN )   &    |- J = ( 1 ... M )   =>    |- ( ph -> ( <. M , K >. PolyAP F <-> E. a e. NN E. d e. ( NN ^m J ) ( A. i e. J ( ( a + ( d ` i ) ) (AP ` K ) ( d ` i ) ) C_ ( `' F " { ( F ` ( a + ( d ` i ) ) ) } ) /\ ( # ` ran ( i e. J |-> ( F ` ( a + ( d ` i ) ) ) ) ) = M ) ) )
Theorem	vdwlem1 15685*	Lemma for vdw 15698. (Contributed by Mario Carneiro, 12-Sep-2014.)
|- ( ph -> R e. Fin )   &    |- ( ph -> K e. NN )   &    |- ( ph -> W e. NN )   &    |- ( ph -> F : ( 1 ... W ) --> R )   &    |- ( ph -> A e. NN )   &    |- ( ph -> M e. NN )   &    |- ( ph -> D : ( 1 ... M ) --> NN )   &    |- ( ph -> A. i e. ( 1 ... M ) ( ( A + ( D ` i ) ) (AP ` K ) ( D ` i ) ) C_ ( `' F " { ( F ` ( A + ( D ` i ) ) ) } ) )   &    |- ( ph -> I e. ( 1 ... M ) )   &    |- ( ph -> ( F ` A ) = ( F ` ( A + ( D ` I ) ) ) )   =>    |- ( ph -> ( K + 1 ) MonoAP F )
Theorem	vdwlem2 15686*	Lemma for vdw 15698. (Contributed by Mario Carneiro, 12-Sep-2014.)
|- ( ph -> R e. Fin )   &    |- ( ph -> K e. NN0 )   &    |- ( ph -> W e. NN )   &    |- ( ph -> N e. NN )   &    |- ( ph -> F : ( 1 ... M ) --> R )   &    |- ( ph -> M e. ( ZZ>= ` ( W + N ) ) )   &    |- G = ( x e. ( 1 ... W ) |-> ( F ` ( x + N ) ) )   =>    |- ( ph -> ( K MonoAP G -> K MonoAP F ) )
Theorem	vdwlem3 15687	Lemma for vdw 15698. (Contributed by Mario Carneiro, 13-Sep-2014.)
|- ( ph -> V e. NN )   &    |- ( ph -> W e. NN )   &    |- ( ph -> A e. ( 1 ... V ) )   &    |- ( ph -> B e. ( 1 ... W ) )   =>    |- ( ph -> ( B + ( W x. ( ( A - 1 ) + V ) ) ) e. ( 1 ... ( W x. ( 2 x. V ) ) ) )
Theorem	vdwlem4 15688*	Lemma for vdw 15698. (Contributed by Mario Carneiro, 12-Sep-2014.)
|- ( ph -> V e. NN )   &    |- ( ph -> W e. NN )   &    |- ( ph -> R e. Fin )   &    |- ( ph -> H : ( 1 ... ( W x. ( 2 x. V ) ) ) --> R )   &    |- F = ( x e. ( 1 ... V ) |-> ( y e. ( 1 ... W ) |-> ( H ` ( y + ( W x. ( ( x - 1 ) + V ) ) ) ) ) )   =>    |- ( ph -> F : ( 1 ... V ) --> ( R ^m ( 1 ... W ) ) )
Theorem	vdwlem5 15689*	Lemma for vdw 15698. (Contributed by Mario Carneiro, 12-Sep-2014.)
|- ( ph -> V e. NN )   &    |- ( ph -> W e. NN )   &    |- ( ph -> R e. Fin )   &    |- ( ph -> H : ( 1 ... ( W x. ( 2 x. V ) ) ) --> R )   &    |- F = ( x e. ( 1 ... V ) |-> ( y e. ( 1 ... W ) |-> ( H ` ( y + ( W x. ( ( x - 1 ) + V ) ) ) ) ) )   &    |- ( ph -> M e. NN )   &    |- ( ph -> G : ( 1 ... W ) --> R )   &    |- ( ph -> K e. ( ZZ>= ` 2 ) )   &    |- ( ph -> A e. NN )   &    |- ( ph -> D e. NN )   &    |- ( ph -> ( A (AP ` K ) D ) C_ ( `' F " { G } ) )   &    |- ( ph -> B e. NN )   &    |- ( ph -> E : ( 1 ... M ) --> NN )   &    |- ( ph -> A. i e. ( 1 ... M ) ( ( B + ( E ` i ) ) (AP ` K ) ( E ` i ) ) C_ ( `' G " { ( G ` ( B + ( E ` i ) ) ) } ) )   &    |- J = ( i e. ( 1 ... M ) |-> ( G ` ( B + ( E ` i ) ) ) )   &    |- ( ph -> ( # ` ran J ) = M )   &    |- T = ( B + ( W x. ( ( A + ( V - D ) ) - 1 ) ) )   &    |- P = ( j e. ( 1 ... ( M + 1 ) ) |-> ( if ( j = ( M + 1 ) , 0 , ( E ` j ) ) + ( W x. D ) ) )   =>    |- ( ph -> T e. NN )
Theorem	vdwlem6 15690*	Lemma for vdw 15698. (Contributed by Mario Carneiro, 13-Sep-2014.)
|- ( ph -> V e. NN )   &    |- ( ph -> W e. NN )   &    |- ( ph -> R e. Fin )   &    |- ( ph -> H : ( 1 ... ( W x. ( 2 x. V ) ) ) --> R )   &    |- F = ( x e. ( 1 ... V ) |-> ( y e. ( 1 ... W ) |-> ( H ` ( y + ( W x. ( ( x - 1 ) + V ) ) ) ) ) )   &    |- ( ph -> M e. NN )   &    |- ( ph -> G : ( 1 ... W ) --> R )   &    |- ( ph -> K e. ( ZZ>= ` 2 ) )   &    |- ( ph -> A e. NN )   &    |- ( ph -> D e. NN )   &    |- ( ph -> ( A (AP ` K ) D ) C_ ( `' F " { G } ) )   &    |- ( ph -> B e. NN )   &    |- ( ph -> E : ( 1 ... M ) --> NN )   &    |- ( ph -> A. i e. ( 1 ... M ) ( ( B + ( E ` i ) ) (AP ` K ) ( E ` i ) ) C_ ( `' G " { ( G ` ( B + ( E ` i ) ) ) } ) )   &    |- J = ( i e. ( 1 ... M ) |-> ( G ` ( B + ( E ` i ) ) ) )   &    |- ( ph -> ( # ` ran J ) = M )   &    |- T = ( B + ( W x. ( ( A + ( V - D ) ) - 1 ) ) )   &    |- P = ( j e. ( 1 ... ( M + 1 ) ) |-> ( if ( j = ( M + 1 ) , 0 , ( E ` j ) ) + ( W x. D ) ) )   =>    |- ( ph -> ( <. ( M + 1 ) , K >. PolyAP H \/ ( K + 1 ) MonoAP G ) )
Theorem	vdwlem7 15691*	Lemma for vdw 15698. (Contributed by Mario Carneiro, 12-Sep-2014.)
|- ( ph -> V e. NN )   &    |- ( ph -> W e. NN )   &    |- ( ph -> R e. Fin )   &    |- ( ph -> H : ( 1 ... ( W x. ( 2 x. V ) ) ) --> R )   &    |- F = ( x e. ( 1 ... V ) |-> ( y e. ( 1 ... W ) |-> ( H ` ( y + ( W x. ( ( x - 1 ) + V ) ) ) ) ) )   &    |- ( ph -> M e. NN )   &    |- ( ph -> G : ( 1 ... W ) --> R )   &    |- ( ph -> K e. ( ZZ>= ` 2 ) )   &    |- ( ph -> A e. NN )   &    |- ( ph -> D e. NN )   &    |- ( ph -> ( A (AP ` K ) D ) C_ ( `' F " { G } ) )   =>    |- ( ph -> ( <. M , K >. PolyAP G -> ( <. ( M + 1 ) , K >. PolyAP H \/ ( K + 1 ) MonoAP G ) ) )
Theorem	vdwlem8 15692*	Lemma for vdw 15698. (Contributed by Mario Carneiro, 18-Aug-2014.)
|- ( ph -> R e. Fin )   &    |- ( ph -> K e. ( ZZ>= ` 2 ) )   &    |- ( ph -> W e. NN )   &    |- ( ph -> F : ( 1 ... ( 2 x. W ) ) --> R )   &    |- C e. _V   &    |- ( ph -> A e. NN )   &    |- ( ph -> D e. NN )   &    |- ( ph -> ( A (AP ` K ) D ) C_ ( `' G " { C } ) )   &    |- G = ( x e. ( 1 ... W ) |-> ( F ` ( x + W ) ) )   =>    |- ( ph -> <. 1 , K >. PolyAP F )
Theorem	vdwlem9 15693*	Lemma for vdw 15698. (Contributed by Mario Carneiro, 12-Sep-2014.)
|- ( ph -> R e. Fin )   &    |- ( ph -> K e. ( ZZ>= ` 2 ) )   &    |- ( ph -> A. s e. Fin E. n e. NN A. f e. ( s ^m ( 1 ... n ) ) K MonoAP f )   &    |- ( ph -> M e. NN )   &    |- ( ph -> W e. NN )   &    |- ( ph -> A. g e. ( R ^m ( 1 ... W ) ) ( <. M , K >. PolyAP g \/ ( K + 1 ) MonoAP g ) )   &    |- ( ph -> V e. NN )   &    |- ( ph -> A. f e. ( ( R ^m ( 1 ... W ) ) ^m ( 1 ... V ) ) K MonoAP f )   &    |- ( ph -> H : ( 1 ... ( W x. ( 2 x. V ) ) ) --> R )   &    |- F = ( x e. ( 1 ... V ) |-> ( y e. ( 1 ... W ) |-> ( H ` ( y + ( W x. ( ( x - 1 ) + V ) ) ) ) ) )   =>    |- ( ph -> ( <. ( M + 1 ) , K >. PolyAP H \/ ( K + 1 ) MonoAP H ) )
Theorem	vdwlem10 15694*	Lemma for vdw 15698. Set up secondary induction on M. (Contributed by Mario Carneiro, 18-Aug-2014.)
|- ( ph -> R e. Fin )   &    |- ( ph -> K e. ( ZZ>= ` 2 ) )   &    |- ( ph -> A. s e. Fin E. n e. NN A. f e. ( s ^m ( 1 ... n ) ) K MonoAP f )   &    |- ( ph -> M e. NN )   =>    |- ( ph -> E. n e. NN A. f e. ( R ^m ( 1 ... n ) ) ( <. M , K >. PolyAP f \/ ( K + 1 ) MonoAP f ) )
Theorem	vdwlem11 15695*	Lemma for vdw 15698. (Contributed by Mario Carneiro, 18-Aug-2014.)
|- ( ph -> R e. Fin )   &    |- ( ph -> K e. ( ZZ>= ` 2 ) )   &    |- ( ph -> A. s e. Fin E. n e. NN A. f e. ( s ^m ( 1 ... n ) ) K MonoAP f )   =>    |- ( ph -> E. n e. NN A. f e. ( R ^m ( 1 ... n ) ) ( K + 1 ) MonoAP f )
Theorem	vdwlem12 15696	Lemma for vdw 15698. K = 2 base case of induction. (Contributed by Mario Carneiro, 18-Aug-2014.)
|- ( ph -> R e. Fin )   &    |- ( ph -> F : ( 1 ... ( ( # ` R ) + 1 ) ) --> R )   &    |- ( ph -> -. 2 MonoAP F )   =>    |- -. ph
Theorem	vdwlem13 15697*	Lemma for vdw 15698. Main induction on K; K = 0, K = 1 base cases. (Contributed by Mario Carneiro, 18-Aug-2014.)
|- ( ph -> R e. Fin )   &    |- ( ph -> K e. NN0 )   =>    |- ( ph -> E. n e. NN A. f e. ( R ^m ( 1 ... n ) ) K MonoAP f )
Theorem	vdw 15698*	Van der Waerden's theorem. For any finite coloring R and integer K, there is an N such that every coloring function from 1 ... N to R contains a monochromatic arithmetic progression (which written out in full means that there is a color c and base, increment values a , d such that all the numbers a , a + d , ... , a + ( k - 1 ) d lie in the preimage of { c }, i.e. they are all in 1 ... N and f evaluated at each one yields c). (Contributed by Mario Carneiro, 13-Sep-2014.)
|- ( ( R e. Fin /\ K e. NN0 ) -> E. n e. NN A. f e. ( R ^m ( 1 ... n ) ) E. c e. R E. a e. NN E. d e. NN A. m e. ( 0 ... ( K - 1 ) ) ( a + ( m x. d ) ) e. ( `' f " { c } ) )
Theorem	vdwnnlem1 15699*	Corollary of vdw 15698, and lemma for vdwnn 15702. If F is a coloring of the integers, then there are arbitrarily long monochromatic APs in F. (Contributed by Mario Carneiro, 13-Sep-2014.)
|- ( ( R e. Fin /\ F : NN --> R /\ K e. NN0 ) -> E. c e. R E. a e. NN E. d e. NN A. m e. ( 0 ... ( K - 1 ) ) ( a + ( m x. d ) ) e. ( `' F " { c } ) )
Theorem	vdwnnlem2 15700*	Lemma for vdwnn 15702. The set of all "bad" k for the theorem is upwards-closed, because a long AP implies a short AP. (Contributed by Mario Carneiro, 13-Sep-2014.)
|- ( ph -> R e. Fin )   &    |- ( ph -> F : NN --> R )   &    |- S = { k e. NN | -. E. a e. NN E. d e. NN A. m e. ( 0 ... ( k - 1 ) ) ( a + ( m x. d ) ) e. ( `' F " { c } ) }   =>    |- ( ( ph /\ B e. ( ZZ>= ` A ) ) -> ( A e. S -> B e. S ) )