WEAKLY MIXING SETS OF INTEGERS AND POLYNOMIAL EQUATIONS JAKUBKONIECZNY Abstract. We investigate polynomial patterns which can be guaranteed to 6 appear in weakly mixing sets introduced by introduced by Furstenberg and 1 studiedby Fish. In particular,we provethat ifAisa weaklymixingsetand 0 p(x)∈Z[x]apolynomial ofodd degreewithpositiveleadingcoefficient, then 2 all sufficiently large integers N can be represented as N = n1+n2, where n p(n1)+m, p(n2)+m∈Aforsomem∈A. a J 1 3 1. Introduction ] T Itis a fundamentalquestionin additive combinatoricsto determine whichtypes N of structure are guaranteed to appear in a given set of the integers. We begin . h with citing the celebrated theorem of Szemer´edi [12], whose ergodic theory proof t a ofFurstenberg[7]pavedthe wayto applicationsof ergodictheoryin combinatorial m [ number theory. 1 Theorem 1.1(Szemer´edi). LetA⊂N beasetwithpositive upper Banach density. v 3 Then,foranyk ∈N,thereexistn,m∈Nsuchthatn, n+m, n+2m,...n+km∈A. 4 3 Phraseddifferently,the theoremassertsthatanysetofpositivedensity contains 0 0 arithmeticprogressionsofarbitrarylength. Manygeneralisationsexistofthistheo- . 2 remexist. AtheoremofSa´rk¨ozy[11](seealso[7],[8])assertsthatinsetsofpositive 0 6 Banachdensityonecanfindpatternssuchasn,n+m2. Inapproximatelythesame 1 : time, but differentdirection, a resultof FurstenbergandKatznelson[9]pertains to v i configurations in higher dimensions, showing that a set A⊂Nr of positive Banach X density contains the configuration n+mF, where F ⊂Zr is any finite set. r a Returning to the polynomial in a single dimension, Bergelson and Leibman [2] were able to improve Sa´rk¨ozy’s theorem to several polynomials vanishing at 0. This result was ultimately improved by these authors and Lesigne [3] to deal with intersective families of polynomials. A sequence p (x)∈Z[x], i∈[r] is intersective i if for any integer k there exists n ∈N such that k |p (n ) for all i∈[r]. k i k Theorem 1.2 (Bergelson, Leibman, Lesigne). Let A ⊂ N be a set with positive Banach density, and let p ∈ Z[x] be an intersective family of polynomials with i p (n)→∞as n→∞. Then, thereexistsn,m∈N suchthat m,m+p (n),...,m+ i 1 p (n)∈A. r 1 2 J.KONIECZNY Note that the conclusion of the above theorem fails if p are not intersective. i Moreover, the offending set A can be very structured: indeed, an (infinite) arith- metic progressionwill do. On the other hand, one expects that more can be proved if A is forced to be unstructured. In the extreme case, when A is a random set, constructed by declaring n ∈ A with a certain probability p > 0, independently for all n, then with probability 1, A will contain many occurrences of the pattern, say, m,m+ p (n),m + p (n),...,m + p (n) for any polynomials (or, for that matter, any 1 2 r functions p ,p ,...,p ). Thus, it is of interest to see which notions of pseudo- 1 2 r randomness guarantee existence of various patterns. The class of weakly-mixing sets was proposed by Furstenberg and investigated by Fish [5], [6]. Roughly speaking, a weakly mixing set is a set of return times of a generic point to anopen neighbourhoodofits originin a weakly-mixingmeasure preserving system XA. While the precise definitions will be givenin due course, at this point we remark that weakly mixing sets include normal sets, i.e. those sets for which any pattern of 0’s and 1’s appears in the characteristic sequence of the set with the same frequency as for a genuinely random set. In [5], Fish characterised all the linear patterns which are guaranteed to ap- pear in a weakly mixing set. We give a special (yet representative) case of this characterisation. Theorem 1.3 (Fish [5]). Let A be a weakly mixing set. Suppose that a ,b ∈ N i i a a and c ∈ Z for i ∈ [r] are such that for all i 6= j we have det i j 6= 0. Then, i b b i j (cid:20) (cid:21) there exist n,m∈N such that a n+b m+c ∈A for all i∈[r]. i i i Forexample,asetAwillcontainthepatternn,m,n+m,n+2m,2n+m,which is not guaranteed to appear on the grounds of density alone. However, unlike in the case of the normal set, a weakly-mixing set is not guaranteed to contain two consecutive elements n,n+1. When it comes to polynomial patterns, one has a result of a somewhat different flavour,which bears resemblance to Theorem 1.2. Theorem 1.4 (Fish [6]). Let A ⊂ N be a weakly-mixing set, and let B ⊂ N be a set of positive density. Let p (x) ∈ Z[x] for i ∈ [r] be polynomials of equal degree, i such that for all i 6= j we have deg(p −p ) > 0, and p (n) → ∞ as n → ∞. i j i Then, for all n ∈ N except 1 for a set of density 0, there exist m ∈ B such that p (n)−m,p (n)−m,...,p (n)−m∈A. 1 2 r 1Hereandelsewhere,whenastatement issaidtoholdfor“allN except forasetof0density ”, we mean that there exists a set S ⊂ N with density 1 such that the statement holds for all N ∈S. Themeaningofthephrase“allbutfinitelymany”isanalogous. WEAKLY MIXING SETS AND POLYNOMIAL EQUATIONS 3 Inapreviouspaper,the authorinvestigatedthe questionofwhethercertainsets of polynomial recurrence are bases of positive integers. A representative instance is the following question. Question 1.5. Fix α ∈ R\Q and a polynomial p(x) ∈ Z[x] with p(n) → ∞ as n → ∞. For ε > 0, let A be the Bohr set {n∈N | nαmod1∈(−ε,ε)}. Is it the case that for all ε > 0, the set {n∈N | p(n)∈A} is a basis of order 2 for the positive integers? Here, a set B ⊂ N is a basis of order 2 if there exist N = N (B) such that for 0 0 N ≥ N , there are n ,n ∈ B with N = n +n . Hence, we are asking if, for 0 1 2 1 2 sufficiently large N, there is a solution to N =n +n with p(n )∈A, p(n )∈A. 1 2 1 2 The answer to Question 1.5 is (trivially) negative in the case when degp = 1. Somewhat surprisingly, the answer remains negative when degp = 2 for generic choice of α. Finally, when degp ≥ 3, the answer is positive, again for a generic choice of α. For exact statements, we refer to [10]. This paper arose from an attempt to see what happens at the other extreme, where instead of being structured, the set A is weakly-mixing. Whendegp=1,thenitisnotasignificantlossofgeneralityassumethatp(x)= x. The questionthen becomes: Is anyweakly-mixingsetA a basisoforder2? The answer to this is negative, but A is almost a basis of order 2, in the sense A+A has density 1 (see [5]). In the case whendegp≥2, one cannotexpect to guarantee that a weakly-mixing set A contains any elements from {p(n) | n∈N}. Indeed, if A is weakly-mixing,then so is A\Z for any Z of density 0, and thus in particular A\{p(n) | n∈N} is weakly mixing. However, we are able to prove the following. Theorem 1.6. Let A ⊂ N be a weakly-mixing set, and let p(x) ∈ Z[x] be a poly- nomial with p(n) → ∞ as n → ∞. Then, all N except for a set of 0 density can be represented as N =n +n , where n ,n ∈N are such that p(n )+m∈A and 1 2 1 2 1 p(n )+m∈A for some m∈A. Moreover, if degp is odd then the conclusion holds 2 for all but finitely many N. The above theorem is a direct consequence of two more technical results, which may be of independent interest. To formulate them, we need to introduce some terminology. For a polynomial p, we denote by degp and lcp the degree and leading coefficient of p, respectively. We shall say that a sequence of polynomials p(N)(x)∈Z[x]fori∈[r], N ∈N,isuniformlyadmissible ifthefollowingconditions i hold: (N) (N) (N) (1) for each i and N, degp > 0, lcp > 0, and moreover degp and i i i lcp(N) are independent of N, i 4 J.KONIECZNY (2) for each i 6= j, deg(p(N) −p(N)) > 0, and moreover deg(p(N) −p(N)) and i j i j (N) (N) lc(p −p ) are independent of N. i j Forinstance,thepairp(N)(n)=n3, p(N)(n)=(N−n)3 isuniformlyadmissible, 1 2 but the pair p(N)(n) = n2, p(N)(n) = (N −n)2 is not. More generally, p(N)(n) = 1 2 1 n3, p(N)(n)= an3+b(N)n2+c(N)n+d(N) will be uniformly admissible as long 2 as a6=0,1 or a=1 and b(N)=b is independent of N. Theorem1.7. LetA⊂Nbeaweakly-mixingset,andletB⊂Nbeasetofpositive density. Let p(N)(x) ∈ Z[x] for i ∈[r],N ∈ N, be a family of polynomials which is i uniformly admissible. Then, there exists N such that for any N > N , there are 0 0 n≤N, m∈B such that p(N)(n)+m,...,p(N)(n)+m∈A. 1 r Rather than fully general families of polynomials, we have are interested specif- ically in those which are themselves givenby polynomialformulas. In other words, we will consider a sequence p(N)(x) ∈Z[x,N], i∈[r]. Such sequence is admissible i if the following holds: (1) for each i, deg p(N)(x)>0, and p(N)(x)≥0 for x∈[0,N], x i i (2) for each i6=j, deg (p(N)(x)−p(N)(x))>0. x i j For instance, the pair p(N)(n) = nk, p(N)(n) = (N −n)k is admissible for each 1 2 k ∈Z. Theorem1.8. LetA⊂Nbeaweakly-mixingset,andletB⊂Nbeasetofpositive density. Let p(N)(x) ∈ Z[x,N] for i ∈ [r] be a polynomial family of polynomials, i whichis admissible. Then,thereexistsasetS ⊂Nwithdensityd(S)=1,suchthat for all N ∈S, thereare n≤N, m∈Bsuchthat p(N)(n)+m,...,p(N)(n)+m∈A. 1 r This paper is organisedas follows. In Section 2 we give basic definitions, specif- ically we define the weakly-mixing sets. In Section 3 we reduce Theorem 1.7 to a uniform convergence statement in ergodic theory, and prove a special case of it. In Section 4 we introduce the PET induction and finish the proof of Theorem 1.7. In Section 5 we again reduce Theorem 1.8 to a statement about certain ergodic averages,and then prove this statement. This paperdrawsheavilyonthe workofBergelson[1]andFish[5], [6]. Many of the ideas we use can be traced back to their, or earlier, work. Acknowledgements. TheauthorthanksVitalyBergelsonforusefulcommentson Theorem3.2,andBenGreenforadviceandsupportduringtheworkonthisproject. ThanksgoalsotoSeanEberhard,FreddieManners,RudiMrazovi´c,PrzemekMazur and Aled Walker for many informal discussions. WEAKLY MIXING SETS AND POLYNOMIAL EQUATIONS 5 2. Definitions, convenitions and basics Throughout the paper, we denote the characteristic function of a set X by 1 . X We use the convention N = {1,2,3,...}, and write [N] = {1,2,...,N}. To sim- plify notation, we use the symbol E borrowedfrom probability to denote averages: E f(x)= 1 f(x). x∈X |X| x∈X ForasetofintPegersA⊂Nwedefineitdensityasd(A)=limN→∞En∈[N]1A(n), provided that the limit exists, which will usually be the case in this paper. We shall use standard asymptotic notation. We write X = O(Y) or X ≪ Y if X ≤CY foranabsolute constantC >0. IfC is allowedto dependonaparameter M, we write X =O (Y). In presence of a variable n, we write X =o (Y) (or M n→∞ simply X =o(Y) if no confusion is possible) if X/Y →0 as n→∞. If the rate of convergence is allowed to depend on M, we write X =o (Y). M;n→∞ A measure preserving system X = (X,B,µ,T) consists of a compact metriz- able space X, together with a probability measure µ on a σ-algebra B, and a B- measurable transformation T: X →X, such that µ(T−1E)= µ(E) for all E ∈B. The transformation T acts on function on X by composition: (Tf)(x)=f(Tx). Recall that a m.p.s. X is ergodic if for any A,B ∈ B we have that E µ(A∩ n≤N T−nB)−−−−→µ(A∩B), and similarly X is weakly mixing if we have the stronger N→∞ condition E |µ(A∩T−nB)−µ(A)µ(B)| −−−−→ 0. A point x ∈ X is generic n≤N N→∞ if for any f ∈ C(X) one has E Tnf(x) → fdµ. It is a consequence of the n≤N ergodic theorem that µ-almost all points are genReric. It will be convenient to view a set A ⊂ N of positive upper density as arising from dynamics. Let Ω := {0,1}N denote the shift space, taken with the natural product topology and the Borel σ-algebra. On Ω, we may define the shift map given by (Sx)(i) := x(i+1). To A ⊂ N we can always associate its characteristic function 1A ∈Ω, which gives rise the the subshift XA :=cl{Sn1A | n∈N}, which is evidently a closed and S-invariant subspace of Ω. ThesetAwithpositiveupperdensityisergodic ifandonlyifthepoint1A ∈XA isgenericforsomeergodicS-invariantprobabilitymeasureµA (whichisnecessarily unique). WestressthatanergodicsetAisinparticularrequiredtohavepositiveup- perdensity,anditisaneasyconsequenceofthe ergodictheoremthatAinfacthas a density. We denote the resulting measure preserving system (XA,S,B(X),µA) byXA. Finally,thesetAisweakly-mixing ifandonlyifitisergodicandthesystem XA is weakly-mixing. Anotherpossibledefinitionofaweakly-mixingsetrequiresmerelythatAshould take the form A = {n∈N | f(Tnx )=1} where X = (X,T,B,µ) is a weakly 0 mixing system, f ∈L∞(µ) takes values 0 and 1, and x is f-generic. Here, a point 0 6 J.KONIECZNY is f-generic if for any g in the algebra generated by f,Tf,T2f,..., we have the convergence of the averages: E g(Tnx )−−−−→ gdµ. n≤N 0 N→∞ ZX We claim that the two definitions are equivalent. Indeed, suppose that a set A = {n∈N | f(Tnx )=1} is as in the latter definition. Define the measurable 0 mapF: X →Ωgivenbyx7→(f(Tnx))n∈N. ItisclearthatF◦T =S◦F,andhence the pushforwardν :=F µ is a S-invariantmeasureonΩ. Since Y=(Ω,S,B(Ω),ν) ∗ is a factor of X, it is easy to check that Y is weakly mixing. Note also that 1A =F(x0). We need to check that 1A is generic for thus defined ν. It will suffice to verify that for any cylinder U = {x∈Ω | x(1)=ǫ ,...,x(r)=ǫ } it is the case that 1 r En≤N1U(Sn1A) → ν(U). But this is an easy consequence of f-genericity of x0. Indeed, let f (x)=f(x) if ǫ =1 and f (x)=1−f(x) if ǫ =0; then i i i i En≤N1U(Sn1A)=En≤N fi(Tn+ix0)−−−−→ Tnfi =ν(U). i≤r N→∞ ZXi≤r Y Y 3. Uniform ergodic theorem We will now explain how Theorem 1.7 can be derived from a result in ergodic theory, concerning convergence of certain averages. Because the set A is already related to a m.p.s. XA = (XA,S,µA), it comes as no surprise that we will be interested in averagesof functions for this system. Fixafamilyofpolynomialsp(N),i∈[r]asinTheorem1.7or1.8,andassumefor i simplicity that B = A. For large integers M,N, let N(N,M) denote the number of solutions to (3.1) p(N)(n)+m∈A, ..., p(N)(n)+m∈A, m∈A 1 r withn∈[N], m∈[M]. Letalsof0 ∈C(XA)bethefunctiongivenbyf0(x)=x(1). We may then approximate, at least heuristically: r 1 NMN(N,M)=Em≤MEn≤N1A(m) 1A(p(iN)(n)+m) i=1 Y r =Em≤MEn≤Nf0(Sm) Sp(iN)(n)+mf0(1A) i=1 Y r r+1 (≈1) f0·En≤N Sp(iN)(n)f0 dµA (≈2) f0(x) dµA =d(A)r+1 ZXA i=1 (cid:18)ZXA (cid:19) Y The approximation labelled (1) is simply the ergodic theorem, and is valid as long as M is sufficiently large, with N fixed. The key difficulty lies in making preciseandjustifying step(2),whichwillinvolveunderstandingthe convergenceof averagessuch as the one under the integral. WEAKLY MIXING SETS AND POLYNOMIAL EQUATIONS 7 Study of similar averages was pioneered by Bergelson in [1], but without the dependenceofthepolynomialsonN. Weshallcallasequenceofr ≥1polynomials (p )r admissible if for any i 6= j we have deg(p −p ) > 0, and p (n) → ∞ as i i=1 i j i n→∞. Theorem 3.1 (Bergelson [1]). Suppose that a m.p.s X = (X,T,B,µ) is weakly mixing. Let (p )r be an admissible sequence of polynomials. Let f ∈ L∞(µ). i i=1 i Then: r r (3.2) E Tpi(n)f −−L−2−→ f dµ. n≤N i i N→∞ i=1 i=1Z Y Y Here, we need a slight variationof the above theorem, alreadymentioned in the introduction. Refiningthenotionofadmissibility,weshallcallafamilyofsequences of polynomials (p(t))r uniformly admissible if for any i 6= j: deg(p(t)−p(t)) ≥ 0 i i=1 i j and if the leading term and degree of p(t)−p(t) are independent of t. (Here, t runs i j oversomeunspecifiedindexsetI.) Forexample,thefamily(x2+a(t),x2+x+a(t)) 1 2 isuniformlyadmissible,but(x2+b(t)x+a(t),x2+x+a(t))is,ingeneral,not(unless 1 1 2 b(t) is independent of t). 1 Theorem 3.2. Suppose that a m.p.s X = (X,T,B,µ) is weakly mixing. Let (p(t))r be an admissible family of sequences of polynomials, indexed by t ∈ I. i i=1 Let f ∈L∞(µ). Then: i r r (3.3) En≤N Tp(it)(n)fi −−L−2−→ fidµ, uniformly in t. N→∞ i=1 i=1Z Y Y Before embarking upon the proof of the above theorem, we explain how it com- pletes the proof of the first of our main results. Proof of Theorem 1.6 assuming Theorem 3.2. Suppose, for the sake of contradic- tion, that the system (3.4) p(N)(n)+m∈A, ..., p(N)(n)+m∈A, m∈B, 1 r has no solution, and consider the quantity r L(N)= lim Em≤MEn≤N1B(m) 1A(m+p(iN)(n))−d(A)r (cid:12)M→∞ !(cid:12) (cid:12) iY=1 (cid:12) (cid:12) (cid:12) which can be co(cid:12)nstrued as the (normalised) deviation of the number solu(cid:12)tions to (cid:12) (cid:12) (3.4) from the expected value of d(B)d(A)rMN. On one hand, since (3.4) lacks solutions, we have L(N) = d(B)d(A)r, and in particular the limit actually exists. Ontheotherhand,wemayapproximate,withthe useofCauchy-Schwartzandthe 8 J.KONIECZNY ergodic theorem: r 2 1/2 L(N)≤Mli→m∞Em≤M En≤N 1A(m+p(iN)(n))−d(A)r!  i=1 Y  r 2 1/2  r = En≤N Sp(iN)(n)f0−d(A)r dµA = En≤N Sp(iN)(n)f0−d(A)r ZXA Yi=1 !  (cid:13)(cid:13) iY=1 (cid:13)(cid:13)L2(µ) (cid:13) (cid:13) An application of Theorem 3.2 gives, in particular: (cid:13) (cid:13) (cid:13) (cid:13) r En≤N Sp(iN)(n)f0 −−L−2−→d(A)r. N→∞ i=1 Y Thus, if N is large enough, then we conclude that L(N)<d(B)d(A)r, which is the sought for contradiction. (cid:3) Remark 3.3. Inthe caseA=B,a similarreasoninggivesthe asymptoticformula forthethenumberofsolutionsN(N,M)mentionedatthebeginningofthissection: N(N,M)=d(B)d(A)rMN(1+o (1)+o (1)). N→∞ N;M→∞ The remainder of this section is devoted to proving Theorem 3.2. In our argu- ment, we follow the approach of Bergelson rather closely, taking care to account for uniformity of convergence. We will need an uniform version of van der Corput Lemma, which is a slight variation on the usual statement. We include the proof, which is rather standard, in the appendix, for the convenience of the reader. Lemma 3.4 (Uniform van der Corput). Suppose that (u(t)) is a sequence of vec- n n tors in a Hilbert space H with u(t) ≤ 1, indexed by t ∈ I. Suppose further that n for s(t) ∈R we have: (cid:13) (cid:13) h >0 (cid:13) (cid:13) (cid:13) (cid:13) (3.5) E u(t), u(t) ≤s(t)+o (1) n≤N n n+h h N→∞ (cid:12) D E(cid:12) where the error term i(cid:12)s uniform in t. Sup(cid:12)pose further that: (cid:12) (cid:12) (3.6) E s(t) −−−−→0, uniformly in t. h≤H h H→∞ Then we have: (3.7) E u(t) −−−−→0, uniformly in t. n≤N n N→∞ Proof of Theorem 3.2, linear case. We will now deal with the case of Theorem 3.2 when degp(t) = 1 for all i. For the sake of readability, we will keep dependence i on t implicit, writing p instead of p(t). In this case, p are necessarily of the form i i i p (x)=a n+b(t), where a does not depend on t. i i i i We may assume without loss of generality that for each i, we have f dµ = 0 i . Indeed, if this is not the case, we may simply replace the original fuRnctions by f˜ :=f − f dµ. Likewise, we may assume kfk ≤1, else we may rescale. i i i ∞ R WEAKLY MIXING SETS AND POLYNOMIAL EQUATIONS 9 The case r = 1 when there is only one polynomial is simple. Indeed, we then have: En≤NTp1(n)f1 =Tb(it)(En≤NTa1nf1). The average in the brackets does not depend on t, and converges to 0 in L2 which follows e.g. from Theorem 3.1. Since Tb(it) preserves the L2 norm, we have: E Tp1(n)f −−L−2−→0, uniformly in t. n≤N 1 N→∞ For r ≥ 2 we proceed by induction using van der Corput Lemma. Let us write un := ri=1Tpi(n)fi. We have: r Q E hu , u i= Tain+bi f ·Taihf dµ n≤N n n+h i i Z i=1 Y (cid:0) (cid:1) r−1 = f˜ ·E Ta˜in+˜bif˜ dµ r,h n≤N i,h Z i=1 Y where we define: a˜ :=a −a , ˜b :=b −b , f˜ =f ·Taihf . i i r i i r i,h i i Thesequenceofpolynomialsp˜(x)=a˜ x+˜b fori∈[r−1]isuniformlyadmissible, i i i since p˜ −p˜ =p −p . Hence, we caninvokethe inductive assumptionto conclude i j i j that: r−1 r−1 E Ta˜in+˜bif˜ = f˜ dµ+o (1), n≤N i,h i,h h;N→∞ i=1 i=1Z Y Y with the error term independent of t. Letting s = r f˜ dµ we have: h i=1 i,h (cid:12) (cid:12) |E hu , u i|≤s +o (cid:12)Q (1R). (cid:12) n≤N n n+h h h;N(cid:12)→∞ (cid:12) By a standard argument, we have E s → 0 as H → ∞, and convergence is h≤H h automatically uniform in t, since s does not depend on t. We are now in position h to apply Lemma 3.4 to conclude that E u →0 in L2 as N →∞, uniformly in n≤N n t. This finishes the inductive step, and thus the proof in the case degp =1. i (cid:3) 4. PET induction ToprovethegeneralcaseofTheorem3.2wewillusePETinduction. Becausethe idea will reemerge in the proof of Theorem 5.1, we will introduce the key concepts in separation from the proof of this particular result. Definition 4.1 (Characteristicvector). Letp=(p )r be the a sequence ofpoly- i i=1 nomials (not necessarily admissible). For k ∈N, let F be the set of those p with k i degp = k. We define the characteristic vector of p, which we denote by χ(p), by i declaring χ(p) to be equal to the number of different leading coefficients lc(p) for k p∈F . k 10 J.KONIECZNY It does not matter much if we define characteristic vectors to have entries for all k or just for k ≤max degp . For the sake of simplicity, we assume the former. i i We make the set of possible characteristic vectors (i.e. Z -valued sequences) into ≥0 an ordered set by introducing reverse-lexicographical order. Recall that χ > χ′ if for the largest k with χ 6= χ′ we have χ > χ′. It is well known fact that ZN k k k k ≥0 is well-ordederby the reverselexicographicalorder. Thus,any decreasingsequence χ>χ′ >χ′′ >... has to be finite. For the inductive step, we shall need the following operation. Let p = (p )r i i=1 be the an admissible sequence of polynomials. We may, without loss of generality, assume that degp ≥degp ≥···≥degp . We then define the sequence p˜ to the 1 2 r h concatenation of two sequences: (4.1) p˜ (x):=p (x)−p (x), i∈[r−1] 1,h,i i r (4.2) p˜ (x):=p (x+h)−p (x), i∈[r] 2,h,i i r The following statements give a base for the PET induction. We cite it here merely as a list of facts. For proofs, which are not difficult, we refer the reader to [1] Fact 4.2. Let p be an admissible sequence of polynomials. (1) If χ(p) =0, then p˜ is admissible for all but finitely many h. 1 h (2) The characteristic vector χ(p˜ ) takes the same value for all but finitely h many values of h. (3) We have χ(p˜ )<χ(p). h Essentially the same statement if true with admissible sequences replaced by a uniformly admissible families of sequences of polynomials. Lemma 4.3. Let p(t) be an uniformly admissible sequence of polynomials. (1) The characteristic vector χ(p(t)) does not depend on t. (2) For all but finitely many h, the leading terms of p˜(t) and p˜(t) −p˜(t) do not h,k h,k h,l depend on t. (3) For all but finitely many h, χ(p˜(t)) does not depend on h and t, and we h have χ(p˜(t))<χ(p(t)). h (4) If χ(p(t)) ≤1 then for all but finitely many h, p(t) is uniformly admissible. 1 h (5) Ifχ(p(t)) ≥2 thefor all butfinitely manyh, wehave for any (σ,i)6=(ρ,j) 1 that deg(p˜(t) −p˜(t) )≥1, except when i=j and degp(t) =1. h,σ,i h,ρ,j i Proof. The item 1 is clear, since χ(p(t)) depends only on leading terms of polyno- mials in p(t), and these are independent of t.