text:
# Untitled Document

1200

A Partition Theorem

Saharon Shelah

Institute of Math, The Hebrew University, Jerusalem Israel

Department of Math., Rutgers University, New Brunswick NJ USA

footnote Presented in the third Turan lecture of the author in Hungary, Feb 1998; Publ. Number 679. Done 1-2/98. Partially supported by the Partially supported by the United States Israel Binational Science Foundation.

Abstract

We deal with some relatives of the Hales Jewett theorem with primitive recursive bounds.

Anotated Content

0 Introduction

1 Basic Definitions

2 Proof of the Partition Theorem with a bound

3 : Higher Dimension Theorems

4 The Main Theorem

Key words: Ramsey theory, Hales Jewett theorem, finite combinatorics

Classification: Primary 05A99, Secondary 15A03

0: Introduction

We prove the following: there is a primitive recursive function $`f_{}^{}(,)`$ , in the three variables, such that: for every natural numbers $`t,n>0`$, and $`c`$, for any natural number $`kf_t^{}(n,c)`$ the following holds. Assume $`\mathrm{\Lambda }`$ is an alphabet with $`n>0`$ letters, $`M`$ is the family of non empty subsets of $`\{1,\mathrm{},k\}`$ with $`t`$ members and $`V`$ is the set of functions from $`M`$ to $`\mathrm{\Lambda }`$ and lastly $`d`$ is a $`c`$colouring of $`V`$ (i.e. a function with domain $`V`$ and range with at most $`c`$ members). Then there is a $`d`$monochromatic $`V`$line, which means that there are $`w\{1,\mathrm{},k\}`$, with at least $`t`$ members and function $`\rho `$ from $`\{uM:u`$ not a subset of $`w\}`$ to $`\mathrm{\Lambda }`$ such that letting $`L=\{\eta V:\eta `$ extend $`\rho `$ and for each $`s=1,\mathrm{},t`$ it is constant on $`\{uM:uw`$ has $`s`$ members $`\}\}`$, we have $`dL`$ is constant (for $`t=1`$ those are the Hales Jewett numbers).

A second theorem relates to the first just as the affine Ramsey theorem of Graham, Leob and Rothschild (which continue the n-parameter Ramsey theorem of Graham and Rothschild), relates to the Hales Jewett theorem. We also note an infinitary related theorem parallel to the Galvin Prikry theorem and the Carlson Sympson theorem.

Let us review history and background, not repeating \[GRS 80\]. In the late seventies, Furstenberg and Sarakozy independently prove that if $`𝐩(𝐱)`$ is a polynomial in $`Z[𝐱]`$ satisfying $`p(0)=0`$ and $`AN`$ is a set of positive density then for some $`a,bA`$ and $`nN`$ we have $`ab=𝐩(n)`$. Bergelson and Leibman \[BL96\] continuing Furstenberg \[Fu\] prove (this is a special of a density theorem like Szemeredi ): if $`r,k,t,m`$ are natural numbers, $`𝐩_{\mathrm{},s}(x)`$ for $`\mathrm{}=1,\mathrm{},k`$ and $`s=1,\mathrm{},t`$ are polynomials with rational coefficients, taking integer values at integers, and vectors $`\overline{v}_1,\mathrm{},\overline{v}_t{}_{}{}^{m}Z`$ and any $`r`$colouring of $`{}_{}{}^{m}Z`$ there are $`\overline{a}mZ`$ and $`nZ(n0)`$ such that the set $`S(\overline{a},n)=\{\overline{a}+\mathrm{\Sigma }_{j=1,t}𝐩_{i,j}(n)\overline{v}_j:i=1,\mathrm{},k\}`$ is monochromatic.

Bergelson and Leibman \[ BL 9x\] prove a theorem, set polynomial extension, which is, in different formulation, like the first theorem describe above but without a bound (i.e. the primitive recursiveness). Their method is infinitary so does not seem to give even the weak bound in 2.5 (one with triple induction), and certainly does not give primitive recursive bounds.

Naturally our proofs continue \[Sh 329\]. We thank the referee for telling us on \[BL 9x\] and other helpful comments.See a discussion of related problems in \[Sh 702\].

0.1 Notation:

(a) We use $`\mathrm{\Lambda }`$ for a finite alphabet, always non empty, members of which are denoted by $`\alpha ,\beta ,\gamma .`$

(b) We use $`M,N`$ to denote structures which serve as index sets, so we call them index models. We use $`\tau `$ to denote vocabularies, , (see Definition 1.1), $`F`$ to denote function symbols.

(c) We use $`n,m,k,\mathrm{},i,j,c,r,s,t`$ to denote natural numbers, but usually $`n`$ is the number of letters, i.e. the number of members in an alphabet; $`k`$ the dimension of the index models and $`c1`$ the number of colours.

(d) $`|X|`$ and also card$`(X)`$ denote the number of elements of the set $`X.`$

(e) We use $`\eta ,\nu ,\rho `$ to denote members of spaces, we use $`V,U`$ to denote spaces and $`a,b`$ to denote elements of $`M,N`$ and $`d`$ to denote colourings, $`p`$ to denote the ‘type‘ of a point in a line and p to denote type of a line or a space (see Definition 1.7(3)). We use $`L`$ to denote (combinatorial) lines, $`S`$ to denote (combinatorial) subspaces.

(f) $`A`$ bar on a symbol, say $`\overline{x}`$ denote a finite sequence of such objects, of length lg$`(\overline{x})`$ the ???$`i`$th object being $`x_i`$ (and of $`\overline{x}_m`$ or $`\overline{x}^m`$ it is $`x_i^m).`$

0.2 DEFINITION: (1) For $`m1`$, let $`E`$m be the minimal class of functions from natural numbers to natural numbers (with any number of places) closed under composition, which for $`m=1`$ contains $`0,1,x+1`$ and the projection functions, and for $`m>1`$ contains any function which we get by inductive definition on functions from $`E`$m-1 (see \[Ro84\], so $`E`$3 is the family of polynomials, $`E`$4 contains the tower function and $`E`$5 contains the waw function and $`_{m1}E_m`$ is the family of primitive recursive functions, and the ‘simplest‘ function not there is the Akerman function.) We allow an object like $`\overline{\mathrm{\Lambda }}`$ to be one of the arguments meaning a natural number coding of it (in the cases used this does not matter). Abusing notation, we may say $`f`$ is in $`E`$n instead of $`f`$ is bounded by a function from $`E`$n, also writing $`f_{\overline{\mathrm{\Lambda }}}(,\mathrm{})`$ we count $`\overline{\mathrm{\Lambda }}`$ as one of the arguments.

(2) We can define the Akerman function $`A_n(m)`$ by double induction (in as sense it is the simplest, smallest function which is not primitive recursive).

0.3 DEFINITION: (1) Let RAM$`(t,\mathrm{},c)`$ be the Ramsey number, i.e. the first $`k`$ such that $`k(t)_c^{\mathrm{}}`$ which mean that if $`A`$ is a set with $`k`$ elements, and $`d`$ is a $`c`$colouring of $`[A]^{\mathrm{}}=^{df}\{B:B`$ is a subset of $`A`$ with $`\mathrm{}`$ elements$`\}`$, that is a function with this domain and range of cardinality $`c`$, then for some $`A_1[A]^t`$ we have $`d[A_1]^{\mathrm{}}`$ is constant.

(2) Let HJ$`(n,m,c)`$ be the Hales Jewett number for getting a monochromatic subspace of dimension $`m`$, when the colouring has $`c`$ colours and for an alphabet with $`n`$ members (this is, by our subsequent definitions, $`f^1(\overline{\mathrm{\Lambda }},m,c)`$ when $`\tau (\overline{\mathrm{\Lambda }})=\{`$id$`\}`$, and $`\mathrm{\Lambda }_{\mathrm{id}}`$ has $`n`$ members, see Definition 1.9).

Section 1 : Basic definitions

We can look at Hales Jewett theorem in geometric terms: $`R`$ is replaced by $`\mathrm{\Lambda }`$; a finite alphabet, the $`k`$dimensional euclidean space $`R^k`$ is replaced by $`{}_{}{}^{[1,k]}\mathrm{\Lambda }`$ (or $`{}_{}{}^{[0,k)}\mathrm{\Lambda }`$), essentially the set of sequences of length $`k`$ of members of the alphabet $`\mathrm{\Lambda }`$; a subspace is replaced by the set of solutions $`(x_1,\mathrm{},x_k){}_{}{}^{[1,k]}\mathrm{\Lambda }`$ of a family of linear equations, which here means just $`x_i=\alpha `$ (where $`\alpha \mathrm{\Lambda },1ik)`$ or $`x_i=x_j`$. Here the basic set $`[1,k]`$ is replaced by a structure $`M`$, a $`\tau `$fim. Such basic definitions are given in this section.

We define a ‘space over an index model of dimension $`k`$, over an alphabet $`\mathrm{\Lambda }`$ of size $`n\mathrm{`}`$, lines and more. We then define the function $`f^1`$, such that for every $`n`$, if $`k`$ is $`f_\tau ^1(n,c)`$ then for every colouring of the space by $`c`$ colours, there is a monochromatic line (in the appropriate interpretation.) Of course the use of id as a special function symbol is not really needed, also we can waive the linear order on $`P^M`$, and the set of automorphisms of the resulting structure are natural for our purpose, but not for the structures from 1.10(3); but at present those decisions does not matter.

1.1 DEFINITION: (1) We call $`M`$ a full index model \[fim or $`\tau `$fim or fim for $`\tau ]`$ if:

(a) the vocabulary $`\tau =\tau _M=\tau (M)`$ of $`M`$ includes a unary predicates $`P`$, a binary predicate $`<`$, and finitely many function symbols $`F`$, $`F`$ being arity$`(F)`$place and no other symbols (so $`F`$ vary over such function symbols). We may write arity$`{}_{}{}^{\tau }(F)`$ for arity$`(F).`$ We usually treat $`\tau `$ as the set of function symbols in $`\tau .`$

(b) the universe of $`M`$ is finite (non empty of course).

$`(c)<^M`$ is a linear order of $`P^M`$, so $`x<^My`$ implies $`x,yP^M.`$

$`(d)F^M`$ is a partial function such that if $`F^M(a_1,\mathrm{},a_r)`$ is well defined (so $`r=`$ arity$`(F))`$ then $`a_1,\mathrm{},a_rP^M`$ and the function is symmetric, i.e. does not depend on the order of the arguments, so if not said otherwise we assume $`a_1^Ma_2^M\mathrm{}^Ma_r.`$

(e) if $`F_1^M(a_1,\mathrm{},a_r)=F_2^M(b_1,\mathrm{},b_t)`$ then $`F_1=F_2`$ (hence $`r=t)`$ and $`a_{\mathrm{}}=b_{\mathrm{}}`$ for $`\mathrm{}=1,\mathrm{},t`$ (under the convention from clause $`(d))`$ and every $`bMP^M`$ has this form. So we let base$`{}_{M}{}^{}(b)=^{df}\{a_1,\mathrm{},a_r\}`$ and let base$`{}_{\mathrm{}}{}^{}(b)=`$ base$`{}_{M,\mathrm{}}{}^{}=_{}^{df}a_{\mathrm{}}`$ where $`b=F^M(a_1,\mathrm{},a_r)`$ (and $`a_1^Ma_2^M\mathrm{}^Ma_r`$ of course) and $`F_{M,b}=^{df}F;`$ those are well defined by the demand above.

$`(f)`$ $`P^M`$ is non empty and we call its cardinality dim$`(M)`$, the dimension of $`M.`$

(g) idM is the identity function on $`P^M`$, so id is a unary function symbol of $`\tau `$.

(h) each $`F^M(a_1,\mathrm{},a_{\mathrm{arity}(F)})`$ is well defined iff $`a_1,\mathrm{},a_{\mathrm{arity}(F)}`$ are from $`P^M`$ ( and the value does not depend on the order, of course)

(2) For $`\tau `$ as in part (1), let arity$`(\tau )`$ be Max$`\{`$arity$`(F):F\tau \}`$, so it is at least 1 and let $`\overline{m}[\tau ]=^{df}m_t^\tau :t=1,\mathrm{}`$,arity$`(\tau )`$ where $`m_t^\tau `$ is the number of $`F\tau `$ with arity $`t;`$ and we call $`\overline{m}^\tau `$ the signature of $`\tau `$, of course when saying “the signature of $`M`$” we mean “of $`\tau (M)`$”.

(3) For $`M`$ a fim we call $`BM`$ closed in $`M`$ (or $`M`$closed ) if for $`b=F^M(a_1,\mathrm{},a_s)`$ we have $`bB`$ iff $`a_1,\mathrm{},a_sM.`$ Let the closure of $`A`$ in $`B`$ or cl$`{}_{M}{}^{}(A)`$ for $`AM`$, be the minimal $`M`$closed set $`B`$ $`M`$ which include $`A`$. A close (non empty) subset of $`M`$ is actually a submodel. We do not strictly distinguish between a closed subset $`B`$ of $`M`$ and the model $`MB`$ (which are fims with the same vocabulary).

(4) For $`\tau `$index models $`M,N`$ let PHom$`(M,N)`$ be the set of functions $`f`$ from $`P^M`$ into $`P^N`$ such that $`x^Myf(x)^Nf(y).`$ Let Hom$`(M,N)`$ be the set of functions $`f`$ from $`M`$ into $`N`$ such that $`fP^M`$ PHom$`(M,N)`$ and $`b=F^M(a_1,\mathrm{},a_t)`$ implies $`f(b)=F^N(f(a_1),\mathrm{},f(a_t)).`$ Let PHm$`(M,N)`$ be the set of functions $`f`$ from $`P^M`$ into $`P^N`$, and let Hm$`(M,N)`$ be the set of functions $`f`$ from $`M`$ into $`N`$ such that $`fP^MPHm(M,N)`$ and $`b=F^M(a_1,\mathrm{},a_t)`$ implies $`f(b)=F^N(f(a_1),\mathrm{},f(a_t))`$.

(5) Let Sort$`{}_{}{}^{M}(F)`$ be the range of $`F^M.`$

1.2 Fact: (1) For any $`f`$ PHom$`(M,N)`$ there is a unique $`\widehat{f}`$ Hom$`(M,N)`$ which extend $`f.`$

(2) For any $`f`$ PHm$`(M,N)`$ there is a unique $`\widehat{f}`$ Hm$`(M,N)`$ which extend $`f.`$

1.3 CLAIM/DEFINITION: (1) For any fim $`M`$ there is a polynomial p$`(x)`$, with rational coefficients but positive integers as values for $`x`$ a positive integer (really sum of binomial coefficients binom$`(x,m_1,\mathrm{},m_n)`$ for $`m_i=1,\mathrm{}`$, arity$`(\tau ))`$ such that for $`uP^M`$, the set cl$`{}_{M}{}^{}(u)`$ has exactly p$`(|u|)`$ members. Now p$`(x)`$ depend on the signature of $`\tau `$ only and so we shall denote it by p$`{}_{\tau }{}^{}(x)`$ or p$`{}_{M}{}^{}(x).`$ Note that p$`{}_{\tau }{}^{}(0)=0.`$

1.4 DEFINITION: (1) We say that $`\tau `$ is canonical vocabulary for $`t`$ (or $`t`$canonical) and write $`\tau =\tau _t`$ if $`\tau =\{F_1,\mathrm{},F_t,P,<\}`$ where arity$`(F_s)`$ is $`s.`$

(2) We say that $`M`$ is a $`(J,t)`$canonical fim if:

$`(a)`$ $`J`$ is a finite linear order

$`(b)`$ $`M`$ is a fim with the $`t`$canonical vocabulary

$`(c)`$ $`(P^M,<^M)`$ is $`J`$

$`(d)`$ $`F_1^M`$ is the identity on $`P^M`$

$`(e)`$ for $`r=2,\mathrm{},t`$ the function $`F_r^M`$ is $`F_r^M(a_1,\mathrm{},a_r)=^{df}\{a_1,\mathrm{},a_r\}.`$

1.5 DEFINITION: (1) Let $`M`$ be a fim with vocabulary $`\tau =\tau _M`$ and let $`\{A_1,A_2\}`$ be a partition of $`P^M`$ to convex sets such that $`A_1<^MA_2`$ which means that $`(a_1A_1)(a_2A_2)[a_1<^Ma_2]`$. We define a vocabulary $`\tau _{M,A_1,A_2}.`$ It contains, in addition to the symbols $`P`$, $`<`$, for each function symbol $`F`$ of $`\tau `$ and a $`^M`$increasing sequence $`\overline{a}_1`$ from $`A_1`$ and a $`^M`$increasing sequence $`\overline{a}_2`$ from $`A_2`$ such that lg$`(\overline{a}_1)+`$lg$`(\overline{a}_2)<`$ arity$`{}_{}{}^{\tau }(F)`$ a function symbol called $`F_{\overline{a}_1,\overline{a}_2}`$ with arity arity$`{}_{}{}^{\tau }(F)`$ lg$`(\overline{a}_1)`$ lg$`(\overline{a}_2).`$

We identify $`F\tau `$ with $`F_,`$ and so consider $`\tau _{M,\overline{a}_1,\overline{a}_2}`$ an extension of $`\tau .`$

(2) Let $`\overline{m}=\overline{m}[\tau ,k_0,k_1]`$ be $`\overline{m}[\tau _{M,A_0,A_1}]`$, the signature of $`\tau _{M,A_0,A_2}`$ whenever $`M`$ is a $`\tau `$fim of dimension $`k_0+k_1`$ and $`A_0`$ is the set of $`k_0`$ first members of $`P^M`$ and $`A_1`$ is the set of $`k_1`$ last members of $`P^M.`$

(3) Let $`M_k^\tau `$ be a fim of vocabulary $`\tau `$ and dimension $`k`$, say $`P^M=\{1,\mathrm{},k\}.`$ Let $`\tau ^{[k,\mathrm{}]}`$ be $`\tau _{M_{k+\mathrm{}}^\tau ,A_0,A_1}`$ where $`A_0`$ is the set of the first $`k`$ members of $`P^M`$ and $`A_1`$ is the set of the last $`\mathrm{}`$ members of $`P^M.`$

1.6 DEFINITION: (1) Let $`\overline{\mathrm{\Lambda }}`$ denote a sequence $`\mathrm{\Lambda }_F:F\tau `$ where $`\mathrm{\Lambda }_F`$ is a finite alphabeth, and we let $`\tau [\overline{\mathrm{\Lambda }}]=\tau `$, as $`\overline{\mathrm{\Lambda }}`$ determine $`\tau .`$ We call $`\overline{\mathrm{\Lambda }}`$ an alphabet sequence (for $`\tau )`$ or a $`\tau `$alphabet sequence. We may write $`(\tau ,\mathrm{\Lambda })`$ instead $`\overline{\mathrm{\Lambda }}`$ if $`\tau =\tau [\overline{\mathrm{\Lambda }}]`$ and $`\mathrm{\Lambda }_F=\mathrm{\Lambda }`$ for every $`F\tau .`$

(2) We say $`p`$ is a $`\overline{\mathrm{\Lambda }}`$-type if $`p`$ is a function with domain $`\tau `$ such that $`p(F)\mathrm{\Lambda }_F`$; let p, q denote non empty sets of $`\overline{\mathrm{\Lambda }}`$-types; we identify them with their characteristic functions that they define, so we assume that from p we can reconstruct $`\overline{\mathrm{\Lambda }}`$ hence $`\tau [\overline{\mathrm{\Lambda }}].`$ Let p$`_{\overline{\mathrm{\Lambda }}}`$ be the set of $`\overline{\mathrm{\Lambda }}`$-types. We may write $`\mathrm{\Lambda }`$ instead $`\overline{\mathrm{\Lambda }}`$ is $`\mathrm{\Lambda }_F=\mathrm{\Lambda }`$ for every $`F\tau `$ and then let pτ,Λ be the set of constant $`(\tau ,\mathrm{\Lambda })`$types.

1.7 DEFINITION: (1) For $`\overline{\mathrm{\Lambda }}`$ a $`\tau `$alphabet sequence, let $`V=`$ Space$`{}_{\overline{\mathrm{\Lambda }}}{}^{}(M)`$ be defined as follows:

its set of elements is the set of functions $`\eta `$ with domain $`M`$, such that $`b`$ Sort$`{}_{}{}^{M}(F)\eta (b)\mathrm{\Lambda }_F;`$ we assume that from $`V`$ we can reconstruct $`M`$ and $`\mathrm{\Lambda }.`$

(2) We say $`d`$ is a $`C`$colouring of $`V`$, if $`d`$ is a function form $`V`$ into $`C`$, we say $`c`$colouring if $`C`$ has $`c`$ members and the default value of $`C`$ is \[0,$`c)=\{0,1,\mathrm{},c1\}.`$

(3) We say $`L`$ is a $`V`$line or a line of $`V`$ if for q $`=𝔭_{\overline{\mathrm{\Lambda }}}`$ we have : $`L`$ is a $`(V,𝔮)`$line or a q -line of $`V;`$ this is defined for q a (non empty) subset of p$`_{\overline{\mathrm{\Lambda }}}`$ and it means:

$`L`$ is a subset of $`V`$ such that for some subset supp$`(L)=`$ supp$`{}_{M}{}^{}(L)`$ of $`M`$ we have:

(a) supp$`(L)P^M`$ is non empty and we call it supp$`{}_{}{}^{P}(L)`$

(b) supp$`(L)`$ is the $`M`$th closure of supp$`{}_{}{}^{P}(L)`$

(c) for any $`\eta ,\nu L`$ we have $`\eta (M`$ supp$`{}_{M}{}^{}(L))=\nu (M`$ supp$`{}_{M}{}^{}(L))`$

(d) for any $`\eta L`$ for some $`p𝔮`$ we have : if $`b`$ supp$`{}_{M}{}^{}((L)`$ then $`\eta (b)=p(F_{M,b})`$

(e) For any $`p𝔮`$ there is $`\eta L`$ as in clause $`(d).`$

(5) For $`L`$ as above and $`p𝔭`$ let pt$`{}_{L}{}^{}(p)`$ be the unique $`\nu L`$ such that for every $`a`$ $``$ supp$`{}_{M}{}^{}(L)`$ we have $`\nu (a)=p(F_{M,b}).`$ For q$`{}_{}{}^{}𝔮`$, the q$`{}_{}{}^{}`$ subline of a q-line $`L`$ is $`\{`$pt$`{}_{L}{}^{}(p):p𝔮^{}\}.`$

(6) For a colouring $`d`$ of $`V`$, we say a $`V`$line (or $`(V,𝔮)`$line) $`L`$ is $`d`$monochromatic if $`d`$ is constant on $`L.`$

(7) When we are given $`M,\tau ,\overline{\mathrm{\Lambda }},V`$ as in part (4) and in addition we are given $`m`$, we define when $`S`$ is an $`m`$dimensional $`V`$subspace , or $`m`$dimensional subspace for $`V.`$ It means that for some sequence $`M_{\mathrm{}}:\mathrm{}<m`$ we have

(a) each $`M_{\mathrm{}}`$ is a submodel of $`M`$,

(b) if $`\mathrm{}_1<\mathrm{}_2<m`$ then $`M_\mathrm{}_1,M_\mathrm{}_2`$ are disjoint,

(c) for some $`\rho `$, a function with domain ($`M`$ cl$`(\{M_{\mathrm{}}:\mathrm{}<m)\}))`$ such that $`\rho (b)\mathrm{\Lambda }_{F_{M,b}}`$ for every $`b`$ Dom$`(\rho )`$, and some $`m`$dimensional $`\tau `$fim $`K`$ say $`K=M_{[0,m)}^\tau `$ and letting $`N`$ be the submodel of $`M`$ with universe cl$`{}_{M}{}^{}(_{\mathrm{}<m}M_{\mathrm{}})`$ there is  $`f`$ Hm$`(N,K)`$ which is onto $`K`$ such that $`fP^M_{\mathrm{}}`$ is constant for each $`\mathrm{}`$ and: $`\nu S`$ iff $`\nu `$ extend $`\rho `$ and for some $`\varrho `$ Space$`{}_{\overline{\mathrm{\Lambda }}}{}^{}(K)`$ we have $`bN\nu (b)=\varrho (\widehat{f}(b))`$

(8) We call $`S`$ convex if

(a) for $`\mathrm{}_1<\mathrm{}_2<m`$ and $`a_1M_\mathrm{}_1`$ and $`a_2M_\mathrm{}_2`$ we have $`a_1<^Ma_2`$ and

(b) $`f`$ Hom$`(N,K)`$.

(9) For $`S`$ as above and (see Definition 1.5(3)) $`\varrho `$ Space$`{}_{\mathrm{\Lambda }}{}^{}(M_{[0,m)}^\tau )`$ we define pt$`{}_{S}{}^{}(\varrho )`$ as the unique $`\nu S`$ as above in part (8).

We may define now a natural function, which is our main concern here :

1.8 DEFINITION: (1) Let $`f^1(𝔭,c)`$ where p $``$ p$`_{\overline{\mathrm{\Lambda }}}`$ ( and $`\overline{\mathrm{\Lambda }}`$ an alphabet sequence) be the minimal $`k`$ such that for any $`\tau _{\overline{\mathrm{\Lambda }}}`$fim $`M`$ of dimension $`k`$, we have:

for any $`c`$colouring $`d`$ of $`V=`$ Space$`{}_{\overline{\mathrm{\Lambda }}}{}^{}(M)`$ there is a p-line $`L`$ of $`V`$ which is $`d`$monochromatic, i.e. such that $`p,q𝔭`$ implies that pt$`{}_{L}{}^{}(p)`$ , pt$`{}_{L}{}^{}(q)`$ have the same colour (by $`d).`$

If $`k`$ does not exist we may say it is $`\omega `$ or is $`\mathrm{}.`$ We may write $`f_\tau ^1(𝔭,c)`$ or $`f^1(𝔭,c;\tau )`$ to stress the role of $`\tau `$.

(2) If p $`=𝔭_{\overline{\mathrm{\Lambda }}}`$ we may write $`f^1(\overline{\mathrm{\Lambda }},c).`$ If $`\mathrm{\Lambda }_F=\mathrm{\Lambda }`$ for every $`F\tau =\tau [\overline{\mathrm{\Lambda }}]`$ then we may write $`f_\tau ^1(\mathrm{\Lambda },c);`$ in this case we can replace $`\mathrm{\Lambda }`$ by $`|\mathrm{\Lambda }|.`$ Clearly only $`\overline{m}^\tau `$ is important so we may write only it. Also we may write $`f_\tau ^1(\overline{n},c)`$ for $`f_\tau ^1(\overline{\mathrm{\Lambda }},c)`$ whenever $`\overline{n}=n_F:F\tau `$ and $`|\mathrm{\Lambda }_F|=n_F.`$

We can of course use the multidimensional versions of those definitions

1.9 DEFINITION: Let $`f^1(\overline{\mathrm{\Lambda }},m,c)`$ be the minimal $`k`$ such that for any $`\tau `$fim $`M`$ of dimension $`k`$ we have: for any $`c`$colouring $`d`$ of Space$`{}_{\overline{\mathrm{\Lambda }}}{}^{}(M)`$ there is a convex subspace $`S`$ of $`V`$ of dimension $`m`$ which is $`d`$monochromatic, i.e. such that all the points in $`S`$ have the same colour (by $`d)`$, if $`k`$ does not exist we say it is $`\omega `$ or is $`\mathrm{}.`$ We may write $`f_\tau ^1(\overline{\mathrm{\Lambda }},m,c)`$ or $`f_\tau ^1(\mathrm{\Lambda },m,c)`$ etc. as before. Clearly only $`\overline{m}^\tau `$ is important (rather than $`\tau `$), so we may write only it. We may replace $`\mathrm{\Lambda }`$ by $`|\mathrm{\Lambda }|.`$ We may replace $`\overline{\mathrm{\Lambda }}`$ by $`n_F:F\tau `$ when $`n_F=|\mathrm{\Lambda }_F|.`$

At present, it does not really matter if we omit the demand convex above.

The function has some obvious monotonicity properties, we mention those we shall actually use.

1.10 Claim: (1) For $`\mathrm{}=1,2`$ assume $`\overline{\mathrm{\Lambda }}`$ is an alphabet sequence for the vocabulary $`\tau ^{\mathrm{}}`$ and arity$`(\tau ^1)`$ arity$`(\tau ^2)`$ and for each $`m=1,\mathrm{}`$, arity$`(\tau ^1)`$ we have

$`\mathrm{\Pi }\{|\mathrm{\Lambda }_F^1|:F\tau ^1`$ has arity $`m\}`$ $`\mathrm{\Pi }\{|\mathrm{\Lambda }_F^2|:F\tau ^2`$ has arity $`m\}.`$

Then $`f^1(\overline{\mathrm{\Lambda }}^1,c)f^1(\overline{\mathrm{\Lambda }}^2,c).`$

(2) For $`\mathrm{}=1,2`$ assume $`\overline{\mathrm{\Lambda }}`$ is an alphabet sequence for the vocabulary $`\tau ^{\mathrm{}}`$ and $`\tau ^1\tau ^2`$ and $`\overline{\mathrm{\Lambda }}`$$`{}_{}{}^{1}=\overline{\mathrm{\Lambda }}^2\tau ^1`$ and $`F\tau ^2\tau ^1|\mathrm{\Lambda }_F^2|=1.`$

Then $`f^1(\overline{\mathrm{\Lambda }}^1,c)=f^1(\overline{\mathrm{\Lambda }}^2,c).`$

Proof: Straightforward.

$`\text{}_{1.10}`$

1.11 DEFINITION: We define, for $`\mathrm{}=1,2,3`$ what is a fim, we just replace in Def.$`1.1`$ clauses $`(d),(e)`$ by

$`(d)_{\mathrm{}}`$ $`F^M`$ is a partial function such that if $`F^M(a_1,\mathrm{},a_r)`$ is well defined (so $`r=`$ arity$`(F))`$ then $`a_1,\mathrm{},a_mP^M`$ and $`\mathrm{}=1`$ implies the function is symmetric, i.e. does not depend on the order of the variables, so if not said otherwise we assume $`a_1^Ma_2^M\mathrm{}^Ma_r.`$

$`(e)_{\mathrm{}}`$ if $`F_1^M(a_1,\mathrm{},a_r)=F_2^M(b_1,\mathrm{},b_t)`$ and $`\mathrm{}\{1,2\}`$ then $`F_1=F_2`$ (hence $`r=t)`$ and $`\mathrm{}=2_{s=1,\mathrm{},r}a_s=b_s`$

and

$`\mathrm{}=1_{s=1,\mathrm{},r1}a_s^Ma_{s+1}`$ $`_{s=1,\mathrm{},r1}b_s^Mb_{s+1}`$ $`_{s=1,\mathrm{},r}a_s=b_s.`$ So we let base$`{}_{M}{}^{}(b)=^{df}\{a_1,\mathrm{},a_r\}`$ and when $`\mathrm{}=1,2`$ let base$`{}_{s}{}^{}(b)=`$ base$`{}_{M,s}{}^{}(b)=^{df}a_s`$ where $`b=F^M(a_1,\mathrm{},a_r)`$ (and if $`\mathrm{}=1`$ then $`a_1^Ma_2^M\mathrm{}^Ma_r`$ , of course) and $`F_{M,b}=^{df}F;`$ those are well defined by the demand above.

$`(e)_{\mathrm{}}^{^{}}`$ if $`\mathrm{}\{1,2,3\}`$ and $`bMP^M`$ then for some $`F\tau `$ and $`a_1,\mathrm{},a_{arity[F]}P^M`$ we have $`b=F^M(a_1,\mathrm{},a_{arity[F]})`$. So $`\mathrm{}=1`$ is the old notion and for $`\mathrm{}=3`$ we require very little. We define $`f_\lambda ^{\mathrm{}}(\overline{\mathrm{\Lambda }},c)`$ as in Definition 1.9 for fim (so again $`\mathrm{}=1`$ is our standard case.)

1.12 Claim: Let $`\tau `$ be a vocabulary and $`\tau _{}=\{G_{F,\pi }:`$ $`F\tau `$ and $`\pi `$ is a permutation of $`\{1,\mathrm{}`$,arity$`(F)\}\}`$

with arity$`(G_{F,\pi })=`$ arity$`(F).`$

Then

$`(\alpha )`$ If $`\overline{\mathrm{\Lambda }}`$ is a $`\tau `$alphabet sequence and $`\overline{\mathrm{\Lambda }}`$$`{}_{}{}^{}=\mathrm{\Lambda }_G^{}:G\tau _{}`$ where $`\mathrm{\Lambda }_{G_{F,\pi }}^{}=\mathrm{\Lambda }_F`$ then $`f^2`$$`{}_{\tau }{}^{}(\overline{\mathrm{\Lambda }},c)f_\tau _{}^1(\overline{\mathrm{\Lambda }}^{},c)`$

$`(\beta )`$ For $`\overline{\mathrm{\Lambda }}`$ a $`\tau `$alphabet sequence we have: $`f_\tau ^3(\overline{\mathrm{\Lambda }},c)`$ is at most RAM$`(f_\tau ^2(\overline{\mathrm{\Lambda }}^{},c)`$, arity$`(\tau ),c^{})`$ where e.g. $`c^{}`$ depend on $`\tau `$ only (and RAM stand for Ramsey number).

$`(\gamma )f_\tau ^1(\overline{\mathrm{\Lambda }},c)f_\tau ^2(\overline{\mathrm{\Lambda }},c)`$

$`(\delta )f_\tau ^2(\overline{\mathrm{\Lambda }},c)f_\tau ^3(\overline{\mathrm{\Lambda }},c)`$

Proof: Straightforward.

$`\text{}_{1.12}`$

Section 2 : Proof of the partition Theorem with a bound

Except Def 2.1,2.2 this section is for the reader convenience only, as it give a proof of a weaker version of the first theorem (with a bound which we get by triple induction). Later in 4.1-4.10 we give a complete proof with the primitive recursive bound, formally not depending on the proofs here. The strategy is to make the $`bM`$ with $`|\mathrm{base}_M(b)|`$ maximal immaterial. We first define some help functions.

2.1 DEFINITION: (1) We call a vocabulary $`\tau `$ monic if there is a unique function symbol of maximal arity, we then denote it by $`F_\tau ^{\mathrm{max}}.`$

(2) For a $`P^M`$ let $`M_a`$ be cl$`{}_{M}{}^{}(\{P^M\{a\})`$

(3) For $`V=`$ Space$`{}_{\overline{\mathrm{\Lambda }}}{}^{}(M)`$ and $`N`$ a closed subset of $`M`$ and $`H\tau `$, we say that a colouring $`d`$ of $`V`$ is $`(N,\alpha ,H)`$invariant if : $`\alpha \mathrm{\Lambda }_H`$, and the following holds, for any $`aP^N:`$

(\*) if $`\nu ,\eta V`$ and $`\nu M_a=\eta M_a`$ and $`\left[bM\mathrm{base}(b)=\{a\}F_{M,b}=H\nu (b)=\alpha =\eta (b)\right]`$ then $`d(\nu )=d(\eta ).`$

(4) In part (3) we write $`(\mathrm{},\alpha ,H)`$monochromatic if above $`N`$ is such that $`P^N`$ is the set of the last $`\mathrm{}`$ members of $`P^M.`$ We write $`(M,\alpha ,H)`$monochromatic if in part (3) we have $`M=N`$.

(5) In parts (3) and (4) we may omit $`H`$ when $`\tau `$ is monic and $`H=F_\tau ^{\mathrm{max}}.`$ Replacing $`\alpha `$ by $`\mathrm{\Lambda }^{}`$ mean that $`\mathrm{\Lambda }^{}`$ is a subset of $`\mathrm{\Lambda }_H`$ and the demand holds for every $`\alpha \mathrm{\Lambda }^{}.`$

2.2 DEFINITION: Let $`f^0`$ be defined as follows. First, $`f_{\overline{\mathrm{\Lambda }}}^0(n,\mathrm{},c)=`$ $`f_{\tau ,\overline{\mathrm{\Lambda }}}^0(n,\mathrm{},c)`$ is defined iff $`\tau `$ is monic with $`H=F_\tau ^{\mathrm{max}}`$ and $`\overline{\mathrm{\Lambda }}`$ an alphabet sequence for $`\tau `$ and $`n|\mathrm{\Lambda }_H|`$ and $`n<|\mathrm{\Lambda }_H|(n=|\mathrm{\Lambda }_H|\mathrm{}=0)`$. Second, $`f_{\overline{\mathrm{\Lambda }}}^0(n,\mathrm{},c)`$ is the first $`k`$ (natural number, if not defined we can understand it as $`\mathrm{}`$ or $`\omega `$ or ‘does not exist‘ ) such that (\*)k below holds,

where:

(\*)k If clauses (a)-(f) below hold then there is a $`d`$monochromatic line of $`V`$, where :

(a) $`M`$ is a fim of vocabulary $`\tau `$

(b) the dimension of $`M`$ is $`k`$

(c) $`V=`$ Space$`{}_{\overline{\mathrm{\Lambda }}}{}^{}(M)`$

(d) $`\mathrm{\Lambda }^{}`$ is a subset of $`\mathrm{\Lambda }_H`$ with exactly $`n`$ members

(e) $`d`$ is an $`(M,\mathrm{\Lambda }^{},H)`$invariant colouring of $`V`$

(f) if $`\mathrm{}0`$, then there is an $`\alpha `$ such that $`\alpha \mathrm{\Lambda }_H\mathrm{\Lambda }^{}`$ and $`d`$ is $`(\mathrm{},\alpha ,H)`$invariant.

Immediate connections are:

2.3 Observation: (1) The function $`f_{\tau ,\overline{\mathrm{\Lambda }}}^0(n,\mathrm{},c)`$ increases with $`c`$ and decreases with $`\mathrm{}`$ and $`n.`$

(2) The function $`f_{\tau ,\overline{\mathrm{\Lambda }}}^0(n,\mathrm{},c)`$ depends just on $`n,\mathrm{},c`$ and the set $`\{`$(arity$`(F),|\mathrm{\Lambda }_F|):F\tau \}`$ (possibly with multiple membership), so we may replace $`\tau `$ by its $`\overline{m}^\tau `$ (similarly for other such functions).

(3) In definitions 1.8,1.9,2.2 the demand holds for any larger $`k.`$

(4) $`f_{\overline{\mathrm{\Lambda }}}^0(0,0,c)=f^1(\overline{\mathrm{\Lambda }},c).`$

(5) If $`\tau `$ is monic and $`H=F_\tau ^{\mathrm{max}}`$ and $`\tau ^{}=\tau \{H\}`$ then $`f_{\overline{\mathrm{\Lambda }}}^0(|\mathrm{\Lambda }_H|,0,c)=f^1(\overline{\mathrm{\Lambda }}\tau ^{},c).`$

(6) If $`\mathrm{}^{}=f_{\overline{\mathrm{\Lambda }}}^0(n+1,0,c)`$ then $`f_{\overline{\mathrm{\Lambda }}}^0(n,\mathrm{}^{},c)=\mathrm{}^{}.`$

Proof: Trivial.

2.4 MAIN Claim: Assume

(a) $`\overline{\mathrm{\Lambda }}`$ is an alphabet sequence for a vocabulary $`\tau =\tau [\overline{\mathrm{\Lambda }}]`$, and $`n<|\mathrm{\Lambda }_H|`$

(b) $`\tau `$ is a monic vocabulary with $`H=F_\tau ^{\mathrm{max}}`$

(c) $`k_0f_{\overline{\mathrm{\Lambda }}}^0(n,\mathrm{}+1,c)`$ and $`k_0>\mathrm{}`$

(d) $`K`$ is a $`\tau `$fim of dimension $`k_01`$ with $`A_2`$ the last $`\mathrm{}`$ elements and $`A_1`$ the first $`(k_0\mathrm{}1)`$elements (this $`K`$ serve just for notation)

(e) $`\tau ^{}`$ is the vocabulary $`(\tau _{K,A_1,A_2})\{H\}`$ see Definition 1.5(3); so

(i) arity$`(\tau ^{})<`$ arity$`(\tau ))`$,

(ii) proj is the following function from $`\tau ^{}`$ to $`\tau :`$ it map $`F_{K,\overline{a}_1,\overline{a}_2}`$ to $`F`$ so proj$`\tau `$ is the identity, and

(iii) $`\overline{\mathrm{\Lambda }}^{}=^{df}\mathrm{\Lambda }_F^{}:F\tau ^{}`$ where $`\mathrm{\Lambda }_F^{}=\mathrm{\Lambda }_{\mathrm{proj}(F)}`$.

(f) $`c^{}=^{df}c^{\mathrm{card}(\mathrm{Space}_{\overline{\mathrm{\Lambda }}}(K))}.`$

Then

$`f_{\overline{\mathrm{\Lambda }}}^0(n,\mathrm{},c)k_0+`$ $`f^1(\overline{\mathrm{\Lambda }}^{},c^{})1`$

Proof: Let $`k_1=f^1(\overline{\mathrm{\Lambda }}^{},c^{})`$ and let $`k=k_0+k_11`$, so it suffice to prove that $`kf_{\overline{\mathrm{\Lambda }}}^0(n,\mathrm{},c).`$ For this it is enough to check (\*)k from Definition 2.1(1), so let $`\mathrm{\Lambda }^{}`$ be a subset of $`\mathrm{\Lambda }_H`$ with $`n`$ elements and $`\alpha ^{}\mathrm{\Lambda }_H\mathrm{\Lambda }^{}`$, also let $`M`$ be a fim of vocabulary $`\tau `$ and dimension $`k`$ (i.e. $`P^M`$ is with $`k`$ members), $`V=`$ Space$`{}_{\overline{\mathrm{\Lambda }}}{}^{}(M)`$, and $`d`$ an $`(\mathrm{},\alpha ^{},H)`$invariant and $`(M,\mathrm{\Lambda }^{},H)`$invariant $`C`$colouring of $`V`$ such that $`C`$ has $`c`$ members. So we just have to prove that the conclusion of Definition 2.2 holds, which means there is a $`d`$monochromatic line of $`V`$.

Let $`w_1=^{df}\{a:aP^M`$ and the number of $`b<^M`$ $`a`$ is $`k_0\mathrm{}1`$ but is $`<k_0\mathrm{}1+k_1\}`$ hence in $`w_1`$ there are $`k_1`$ members, and let $`w_0`$ be the set of first $`k_0\mathrm{}1`$ members of $`P^M`$ by $`<^M`$, and lastly let $`w_2`$ be the set of the $`\mathrm{}`$ last members of $`M`$ by $`<^M.`$ So $`w_0,w_1,w_2`$ form a convex partition of $`P^M.`$

Now we let $`K`$ be $`M`$ restricted to cl$`{}_{M}{}^{}(w_0w_2)`$, (note that this gives no contradiction to the assumption on $`K`$ i.e. clause (d) of the assumptions, as concerning $`K`$ there, only its vocabulary and dimension are important and they fit). Let $`K^+`$ be a fim with vocabulary $`\tau `$ and dimension $`k_0`$, let $`g_0`$ PHom$`(M,K^+)`$ be the following function from $`P^M`$ onto $`P^{K^+}:`$ it maps all the members of $`w_1`$ to one member of $`P^{K^+}`$ which we call $`b^{}`$, it is a one to one order preserving function from $`w_2`$ onto $`\{bP^{K^+}:b^{}<^{K^+}b\}`$ and it is a one to one order preserving function from $`w_0`$ onto $`\{bP^{K^+}:b<^{K^+}b^{}\}.`$ Let $`g`$ Hom$`(M,K^+)`$ be the unique extension of $`g_0;`$ without loss of generality $`g_0`$ is the identity on $`w_0`$ and on $`w_2`$ hence without loss of generality $`g`$ is the identity on $`K`$, it exist by 1.2.

Next recall that the vocabulary $`\tau ^{}=\tau _{K,w_o,w_2}\{H\}`$ is a well defined vocabulary ( see Definition 1.5(1) and remember that $`\tau \tau _{K,w_0,w_2}`$ so $`H\tau _{K,w_0,w_2}`$). Next we shall define a $`\tau ^{}`$model $`N.`$ Its universe is $`MKA^{}`$ where $`A^{}=^{df}\{bM:`$ base$`{}_{M}{}^{}(b)w_1`$ and $`F_{M,b}=H\}`$, we let $`P^N`$ be $`w_1`$ and $`<^N`$ be $`<^MP^N.`$ Now we have to define each function $`F_{K,\overline{a}_1,\overline{a}_2}^N`$, say of arity $`r`$, where $`F\tau ,\overline{a}_1`$ a non decreasing sequence form $`w_0`$ and $`\overline{a}_2`$ a non decreasing sequence from $`w_2`$, and lg$`(\overline{a}_1)+`$ lg$`(\overline{a}_2)<`$ arity(F) and arity$`(F_{K,\overline{a}_1,\overline{a}_2})`$ $`<`$ arity$`(\tau ).`$ Note that the last condition is equivalent to : if $`F=H`$ then at least one of the sequences $`\overline{a}_1,\overline{a}_2`$ is not empty.

For $`b_1^N\mathrm{}^Nb_rP^N`$ we let $`F_{\overline{a}_1,\overline{a}_2}^N(b_1,\mathrm{},b_t)`$ be equal to

$`b=F^M(\overline{a}_1,b_1,\mathrm{},b_t,\overline{a}_2)`$ $`=F^M(a_1^1,a_2^1,\mathrm{},a_{\mathrm{lg}(\overline{a}_1)}^1`$, $`b_1,\mathrm{},b_t,a_1^2,\mathrm{},a_{\mathrm{lg}(\overline{a}_2)}^2).`$

It is easy to check that the number of arguments is right and also the sequence they form is $`^M`$increasing, so this is well defined and belongs to $`M`$, but still we have to check that it belongs to $`N.`$ First note that it does not belong to $`K`$, as if $`bK`$ then base$`{}_{\mathrm{lg}(\overline{a}_1)+1}{}^{}(b)K`$ and it is just $`b_1`$ which belongs to $`w_1`$, contradiction. Second note that it does not belongs to $`A^{}`$, this holds as we have substructed $`H`$ when we have defined $`\tau ^{}.`$ Lastly it is also trivial to note that every member of $`N`$ has this form. It is easy to check that $`N`$ is really a $`\tau ^{}`$fim.

We next let $`V^{}=`$ Space$`{}_{\overline{\mathrm{\Lambda }}^{}}{}^{}(N)`$ and let $`C^{}=\{g:g`$ is a function from Space$`{}_{\overline{\mathrm{\Lambda }}}{}^{}(K)`$ to $`C\}`$ and define a $`C^{}`$-colouring $`d^{}`$ of $`V^{}.`$ For $`\eta V^{}`$ let $`d^{}(\eta )`$ be the following function from Space$`{}_{\overline{\mathrm{\Lambda }}}{}^{}(K)`$ to $`C`$, letting $`\varrho `$ be the function with domain $`A^{}`$ which is constantly $`\alpha ^{}:`$ for $`\nu K`$ we let $`\left(d^{}(\eta )\right)(\nu )=d(\eta \nu \varrho ).`$

Clearly the function $`d^{}(\eta )`$ is a $`C^{}`$colouring of Space$`{}_{\overline{\mathrm{\Lambda }}}{}^{}(K)`$. How many such functions there are? The domain has clearly card(Space$`{}_{\overline{\mathrm{\Lambda }}}{}^{}(K))`$ members, (we can get slightly less if $`\mathrm{}>0`$, but with no real influence). The range has at most $`c`$ members, so the number of such functions is at most $`c^{\mathrm{card}(\mathrm{Space}_{\overline{\mathrm{\Lambda }}}(K))}`$, a number which we have called $`c^{}`$.

So $`d^{}`$ is a $`c^{}`$colouring.

Now as we have chosen $`k_1=f^1(\overline{\mathrm{\Lambda }}^{},c^{})`$ we can apply Definition 2.2 to $`V^{}=`$ Space$`{}_{\overline{\mathrm{\Lambda }}^{}}{}^{}(N)`$ and $`d^{};`$ so we can find a $`d^{}`$monochromatic $`V^{}`$line and we call it $`L^{}.`$ Let $`h`$ be the function from $`U=^{df}`$ Space$`{}_{\overline{\mathrm{\Lambda }}}{}^{}(K^+)`$ to $`V`$ defined as follows:

(\*) $`h(\rho )=\nu `$ iff :

(a) $`\nu V,\rho U`$,

(b) $`\nu K=\rho K`$

(c) if $`bN`$ supp$`{}_{N}{}^{}(L^{})`$ (see Def 1.7(3)) then $`\nu (b)=\eta (b)`$ for every $`\eta L^{}.`$

(d) if a $`A^{}`$ clM( supp$`{}_{N}{}^{}(L^{}))`$ then $`\rho (a)=\alpha ^{}.`$

(e) if a $``$ supp$`{}_{N}{}^{}(L^{})`$, (so a $`N`$, $`F_{N,a}=F_{K,\overline{a}_1,\overline{a}_2}`$, base$`{}_{N}{}^{}(a)`$ supp$`{}_{N}{}^{P}(L^{}))`$, and $`bK^+`$, $`F_{K^+,b}=F,b=F(\overline{a}_1,b^{},\mathrm{},b^{},\overline{a}_2)`$ (with the number of cases of $`b^{}`$ being arity( $`F_{K,\overline{a}_1,\overline{a}_2}))`$ then $`\rho (b)=\nu (a).`$

(f) if $`aA^{}`$clM(sup$`{}_{N}{}^{}(L^{}))`$ and $`b`$ $`K^+`$ is $`H(b^{},\mathrm{},b^{})`$ then $`\rho (b)=\nu (a).`$

Let the range of $`h`$ be called $`S.`$ Now clearly

$`_1`$ $`(\alpha )`$ $`h`$ is a one to one function from $`U`$ to $`SV.`$

$`(\beta )`$ $`S`$ has $`|`$Space$`{}_{\overline{\mathrm{\Lambda }}}{}^{}(K^+)|`$ members

$`(\gamma )`$ $`S`$ is a subspace of $`V`$ of dimension $`k_0`$, such that $`h(\rho )=`$ pt$`{}_{S}{}^{}(\rho )`$, see 1.7(7).

Now clearly

$`_2`$ there is a $`C`$colouring $`d^{}`$ of $`U`$ such that:

$`d^{}(\nu )=d(h(\nu ))`$ for $`\nu U.`$

and

$`_3`$ (a) $`d^{}`$ is $`(K^+,\mathrm{\Lambda }^{})`$invariant

(b) $`d^{}`$ is $`(\mathrm{}+1,\alpha ^{},H))`$invariant

\[WHY? Reflect\]

Applying the definition of $`k_0f_{\tau ,\overline{\mathrm{\Lambda }}}^0(n,\mathrm{}+1,c)`$ , that is Definition 2.2 to $`\overline{\mathrm{\Lambda }}`$, $`\alpha ^{},U,d^{}`$ we can conclude that there is a $`d^{}`$monochromatic $`U`$line $`L^{}.`$ Let $`L=^{df}\{h(\rho ):\rho L^{}\}.`$ It is easy to check that $`L`$ is as required.

$`\text{}_{2.4}`$

As a warm up for the later bounds we prove:

2.5 Theorem: (1) The function $`f_\tau ^1(\overline{\mathrm{\Lambda }},c)`$ is well defined, i.e. always get value, a natural number.

Moreover has a bound which we have got by triple induction.

(2) Similarly the function $`f^0.`$

Proof: (1) The proof follows by induction, the main induction is on $`t=`$ arity$`(\tau _{\overline{\mathrm{\Lambda }}}).`$ Now by observation 1.10(1) without loss of generality $`\tau `$ is monic, i.e. has a unique function symbol of arity $`t`$, called $`H=^{df}F_\tau ^{\mathrm{max}}.`$ Fixing $`t`$, we prove by induction on $`s=|\mathrm{\Lambda }_H|.`$

CASE 0: $`t=1`$

This is Hales-Jewett theorem (on a bound see \[Sh:329\] and \[GRS80\])

CASE 1: $`t>1,s=1`$

By claim 1.10(2) we can decrease $`t.`$

CASE 2: $`t>1,s2`$

We note that $`f^1(\overline{\mathrm{\Lambda }},c)=f_{\overline{\mathrm{\Lambda }}}^0(0,0,c)`$ by 2.3(4) so it is enough to bound the later one. But by 2.3(5) we know $`f_{\overline{\mathrm{\Lambda }}}^0(|\mathrm{\Lambda }_H|,0,c)=f^1(\overline{\mathrm{\Lambda }}\tau ^{},c)`$ where $`\tau ^{}=^{df}\tau \{H\}`$, but for the later one we have a bound by the induction hypothesis on $`t`$ as arity$`(\tau ^{})t`$, so we have a bound on $`f_{\overline{\mathrm{\Lambda }}}^0(|\mathrm{\Lambda }_H|,0,c).`$ By the last two sentences together, it is enough to find a bound to $`f_{\overline{\mathrm{\Lambda }}}^0(n,0,c)`$ by downward induction on $`n|\mathrm{\Lambda }_H|`$, and we have the starting case : $`n=|\mathrm{\Lambda }_H|`$ and the case $`n=0`$ gives the desired conclusion. So assume we know for $`n+1`$ and we shall do it for $`n.`$ Let $`\mathrm{}^{}=^{df}f_{\overline{\mathrm{\Lambda }}}^0(n+1,0,c)`$, so we know that $`\mathrm{}^{}=f_{\overline{\mathrm{\Lambda }}}^0(n,\mathrm{}^{},c)`$ by 2.3(6), so we by downward induction on $`\mathrm{}\mathrm{}^{}`$ give a bound to $`f_{\overline{\mathrm{\Lambda }}}^0(n,\mathrm{},c).`$ So we are left with bounding $`f_{\overline{\mathrm{\Lambda }}}^0(n,\mathrm{},c)`$ given bound for $`f_{\overline{\mathrm{\Lambda }}}^0(n,\mathrm{}+1,c)`$ ( and also $`f_\tau _{}^1(\overline{\mathrm{\Lambda }}^{},c^{})`$ whenever arity$`(\tau _{})<t).`$ For this 2.4 was designed, it says

$`f_{\overline{\mathrm{\Lambda }}}^0(n,\mathrm{},c)f_{\overline{\mathrm{\Lambda }}}^0(n,\mathrm{}+1,c)+f_\tau ^{}^1(\overline{\mathrm{\Lambda }}^{},c)+1`$

where $`\tau ^{},\overline{\mathrm{\Lambda }}^{}`$ were defined there and arity$`(\tau ^{})<`$ arity$`(\tau )`$, (well, we have to assume that $`\mathrm{}<f_{\overline{\mathrm{\Lambda }}}^0(n,\mathrm{}+1,c)`$, but otherwise use $`\mathrm{}+1+f_\tau ^{}^1(\overline{\mathrm{\Lambda }}^{},c)+1`$

$`\text{}_{2.5}`$

Section 3 : Higher Dimension Theorems

Concerning the multidimensional case (see Def 1.9):

3.1 Conclusion: (1) For any $`\overline{\mathrm{\Lambda }}`$, $`m`$ and $`c`$, we have $`f^1(\overline{\mathrm{\Lambda }},m,c)`$ is well defined (with bound as in the proof, actually using one further induction using only $`f_{\tau _i}^1(\overline{\mathrm{\Lambda }},c)`$ for suitable $`\tau _i`$-s in teh $`i`$step.)

(2) We can naturally defined $`\tau `$fim of dimension $`\mathrm{}_0`$ and convex subspaces, and prove that for any $`\tau `$fim $`M`$ of dimension $`\mathrm{}_0`$ and alphabet sequence $`\overline{\mathrm{\Lambda }}`$, if Space$`{}_{M}{}^{}(\overline{\mathrm{\Lambda }})`$ is the union of finitely many Borel subsets, then some convex subspace $`S`$ of dimension $`\mathrm{}_0`$ is included in one of those Borel subsets.

Proof: (1) For simplicity (and without loss of generality by 1.10(1)) we have $`\overline{\mathrm{\Lambda }}`$ is constantly $`\mathrm{\Lambda }`$, so each $`\mathrm{\Lambda }_F`$ is $`\mathrm{\Lambda }`$, a fixed alphabet. We choose by induction on $`i=0,\mathrm{},m`$ the objects $`M_i,\tau _i,k_i`$ and $`c_i`$ such that

(a) $`k_0=0`$ and $`k_i<k_{i+1}`$

(b) $`M_i`$ is a fim for $`\tau `$ of dimension $`k_i`$ (we allow empty fim, if you do not like it start with $`k_0=1`$)

(c) $`M_{i+1}`$ is an end extension of $`M_i`$

(d) $`\tau _i=\tau _{M_i,P^{M_i},\mathrm{}}`$ (see Definition 1.5(1) )

(e) $`c_0`$ is $`c`$ and $`c_{i+1}`$ is $`c^{|\mathrm{Space}_\mathrm{\Lambda }(k_i+mi)|}`$

(f) $`k_{i+1}=k_i+f_{\tau _i}^1(\mathrm{\Lambda },c_i).`$

There is no problem to carry the definition and we can prove that $`k_mf_\tau ^1(\mathrm{\Lambda },m,c).`$

The proof is straight.

2) Such theorems are closed relatives to theorems on appropriate forcing notions, as anyhow it is a set theoretical theorem we use such approach. Specifically we use the general treatment of creature forcing of \[RoSh 470\]. For any finite non empty $`u\omega `$ let $`M_u^\tau `$ be a $`\tau `$model with $`(P^{M_u^\tau },^{M_u^\tau })=(u,)`$, and without loss of generality $`u_1u_2M_{u_1}^\tau M_{u_2}^\tau `$. So for infinite $`u\omega `$ we have $`M_u^\tau =\{M_{u_1}^\tau :u_1u`$ finite $`\}`$ is well defined.

A $`\overline{\mathrm{\Lambda }}`$-creature $`𝔠`$ consist of a convex subspace $`S^𝔠=S[𝔠]`$ of some $`M_u^\tau `$ for some finite non empty $`u=u[𝔠]`$ of the form $`[n,m]=[n_𝔠,m_𝔠]`$ .

Fot creatures $`𝔠_1,\mathrm{},𝔠_k`$ we let $`\mathrm{\Sigma }(𝔠_1,\mathrm{},𝔠_k)`$ be well defined iff $`m_𝔠_{\mathrm{}}=n_{𝔠_{\mathrm{}+1}}`$ for $`\mathrm{}[1,k)`$ and it is the set of $`\overline{\mathrm{\Lambda }}`$creatures $`𝔠`$ such that $`n_𝔠=n_{𝔠_1},m_𝔠=m_{𝔠_k}`$ and $`\eta S^𝔠\mathrm{}[1,k)\eta u[𝔠_{\mathrm{}}]S^𝔠_{\mathrm{}}`$.

So the forcing notion $`Q`$ is well defined by \[RoSh 470\] for the case the lim-sup of the norms is infinity”. So a condition $`p`$ has the form $`\eta ,𝔠_1,𝔠_2,\mathrm{}=\eta ^p,𝔠_1^p,𝔠_2^p,\mathrm{}`$ where for $`t=1,2,\mathrm{}`$, $`𝔠_t^p`$ is a $`\overline{\mathrm{\Lambda }}`$creature , $`m_{𝔠_{t+1}^p}=n_{𝔠_t^p}`$. Let $`B=^{df}\mathrm{Space}_{\overline{\mathrm{\Lambda }}}(M_\omega ^\tau )=\{\rho :\rho \text{ is a function with domain }M_\omega ^\tau \text{ satisfying }f(b)\mathrm{\Lambda }_{F(b)}\}`$ where $`F(b)=F_{M_\omega ^\tau ,b}`$. We say that $`\rho B`$ obeys $`pQ`$ if $`\eta ^p\rho `$ and for $`t=1,2,\mathrm{}`$ we have $`\rho u^{𝔠_t^p}S^{𝔠_t^p}`$. It is proved there that such forcing notions has many good properties. In particular letting cont$`(p)=\{\rho :\rho B\text{ obeys }p\}`$ is a function with domain and defining the $`Q`$-name $`\widehat{f}=\{f^p:p\widehat{G}_Q\}`$. Now note that

(a) $`p_Q\text{}\widehat{f}`$ cont$`(p)`$

(b) if $`N((\chi ),)`$ is countable, the definition of those countably many Borel sets belongs to $`N`$, and $`pQN`$, then we can find $`q`$ such that

(i) $`pq`$

(ii) every $`f\mathrm{cont}(q)`$ is a generic for $`Q`$ over $`N`$

(iii) for some $`p^{},n^{}`$ we have $`pp^{}NQ,p^{}q`$ and $`p^{}_Q\text{}\widehat{f}A_n^{}\text{}`$

Together we conclude that $`\mathrm{cont}(q)A_n^{}`$ and we are done.

$`\text{}_{3.1}`$

We turn to relating the old results from Bergelson Leibman \[BL96\]

3.2 Conclusion: (1) Assume that

(a) $`\tau `$ is a $`t`$canonical vocabulary (see 1.4)

(b) $`k=f_\tau ^1(\mathrm{\Lambda },c)`$, $`\mathrm{\Lambda }`$ a (finite) alphabet

(c) $`R`$ is a ring, and $`r_1,\mathrm{},r_kR`$

(d) for $`\alpha \mathrm{\Lambda },𝐩_\alpha (x)`$ is a polynomial over $`R`$ (i.e. with parameters in $`R`$).

(e) $`d`$ is a $`c`$colouring of $`R`$ ( actually enough to consider a finite subset, the range of $`g`$ in the proof below)

Then we can find $`y,z`$ and $`w\{1,\mathrm{},k\}`$ such that

$`(\alpha )`$ $`yR`$ and $`z=\mathrm{\Sigma }_\mathrm{}wr_{\mathrm{}}R`$

$`(\beta )`$ the set $`\{y+𝐩_\alpha (z):\alpha \mathrm{\Lambda }\}`$ is $`d`$monochromatic

(2) Assume that

(a) $`\tau `$ is a vocabulary of arity $`t`$, such that for each $`s=1,\mathrm{},t`$ in $`\tau `$ there are exactly $`m^{}`$ function symbols of arity $`s`$

(b) $`k=f_\tau ^1(\mathrm{\Lambda },c)`$, $`\mathrm{\Lambda }`$ a (finite) alphabet

(c) $`R`$ is a ring, and $`r_1,\mathrm{},r_kR`$

(d) for $`\alpha \mathrm{\Lambda }`$ and $`m<m^{},𝐩_{\alpha ,m}(x)`$ is a polynomial over $`R`$ (i.e. with coefficients in $`R`$).

(e) $`d`$ is a $`c`$colouring of $`R^m^{}=\{y_m:m<m^{}:y_0,\mathrm{},y_{m^{}1}R\}`$ (actually enough to consider a finite subset, the range of $`g`$ in the proof below).

Then we can find $`y,z`$ and $`w\{1,\mathrm{},k\}`$ such that

$`(\alpha )`$ $`yR`$ and $`z=\mathrm{\Sigma }_\mathrm{}wr_{\mathrm{}}R`$

$`(\beta )`$ the set $`\{y+𝐩_{\alpha ,m}(z):m<m^{}:\alpha \mathrm{\Lambda }\}`$ is $`d`$monochromatic

Proof: (1) Let $`M`$ be a fim for $`\tau `$ of dimension $`k`$ and let $`h`$ be a one to one order preserving function from $`P^M`$ to $`\{1,\mathrm{},k\}.`$ We define a function $`g`$ from $`V=`$ Space$`{}_{\mathrm{\Lambda }}{}^{}(M)`$ to $`R.`$ For $`\eta V`$ we let $`g(\eta )=\mathrm{\Sigma }_{bM}g_b(\eta (b))`$ where $`g_b`$ is the following function from $`\mathrm{\Lambda }`$ to $`R`$. For $`b=F(b_1,\mathrm{},b_t)M`$ and $`\alpha \mathrm{\Lambda }`$ we let $`g_b(\alpha )`$ be zero if $`b_1,b_2,\mathrm{},b_t`$ is with repetitions and otherwise we consider $`𝐩_\alpha (\mathrm{\Sigma }_{i=1,t}r_{h(b_i)})`$, expand it as sum of monoms in $`r_1,\mathrm{},r_k`$ , and let $`g_b(\alpha )`$ be the sum of those monoms for which $`\{r_j:j\{1,\mathrm{},k\}`$ and $`r_j`$ appear in the monom $`\}`$ $`=`$ $`\{h(b_1),\mathrm{},h(b_t)\}`$. Now we define a $`c`$colouring $`d^{}`$ of $`V`$ by $`d^{}(\eta )=d(g(\eta )).`$ Let $`L`$ be a $`d^{}`$monochromatic line of $`V`$ , let supp$`{}_{M}{}^{}(L)=N.`$ Now let $`y=^{df}\mathrm{\Sigma }_{bMN}g_b`$(pt$`{}_{L}{}^{}(\alpha ))`$, note that all the $`\alpha \mathrm{\Lambda }`$ gives the same value. Let $`w=^{df}\{h(b):b`$ supp$`{}_{M}{}^{P}(L)\}`$, recalling Def 1.7(5) and so $`z=\mathrm{\Sigma }_\mathrm{}wr_{\mathrm{}}`$, now check.

Note that algebraically it is more natural to defined $`g`$ differently, working by the rank of the monom rather that by the set of variables appearing.

(2) Similarly, left to the reader.

$`\text{}_{3.2}`$

3.3 Discussion: It is natural to ask:

(1) Can we generalize the Graham Rothschild theorem? (see \[GR 71\], \[GRS 80\])

(2) Can we get here primitive recursive bounds?

(3) Can we prove the density version of the theorem (2.11)?

Below we answer positively questions (1),(2), we believe that the answer to question (3) is positive too but probably it require methods of dynamical systems, see the book Furstenberg \[Fu81\].

3.4 DEFINITION: We define $`f^4(\overline{\mathrm{\Lambda }},t,\mathrm{},c)=f_\tau ^4(\overline{\mathrm{\Lambda }},t,\mathrm{},c)`$ where 0 $`\mathrm{}<t`$ as follows. It is the minimal $`k`$ such that: if $`M`$ is fim for $`\tau ,V=`$ Space$`{}_{\overline{\mathrm{\Lambda }}}{}^{}(M)`$ and $`d`$ is a $`c`$colouring of $`\{S:S`$ is an $`\mathrm{}`$subspace of $`V\}`$ then for some subspace $`U`$ of $`V`$ of dimension $`t`$, all the $`\mathrm{}`$subspaces of $`U`$ (equivalently, $`\mathrm{}`$subspaces of $`V`$ which are contained in $`U`$) have the same colour by $`d.`$

3.5 Theorem : (1) For any $`\overline{\mathrm{\Lambda }}`$, $`t,\mathrm{},c`$ as in Definition 3.3, the function $`f^4(\overline{\mathrm{\Lambda }},t,\mathrm{},c)`$ is well defined, i.e. is finite.

(2) Let $`m=`$ RAM$`(t,\mathrm{},c)`$, see Definition 0.3(1), where $`\tau `$ is a vocabulary and $`\overline{\mathrm{\Lambda }}`$ is a $`\tau `$alphabet sequence, and define $`k_i`$ for $`i=0,\mathrm{},m`$ by induction on $`i`$ as follows (on $`\tau ^{[k,r]}`$ see 1.5(3)):

$`k_0=0,\overline{\mathrm{\Lambda }}^0=\overline{\mathrm{\Lambda }}`$ and $`k_{i+1}=k_i+f_{\tau _i}^1(\overline{\mathrm{\Lambda }}^i,c_i)`$ where $`\tau _i=^{df}\tau ^{[k_i,mi]}`$ and $`\overline{\mathrm{\Lambda }}^i`$ is a $`\tau ^{[k,mi]}`$alphabet sequence, and $`\mathrm{\Lambda }_{F_{M_{k_i+mi}^\tau ,\overline{a}_1,\overline{a}_2}}^i`$ has $`|\mathrm{\Lambda }_F^i|+\mathrm{}+|M_{k_i+mi}^\tau |`$ members and $`c_i=c^{\mathrm{card}(\mathrm{Space}_{\overline{\mathrm{\Lambda }}^i}(M_{k_i+mi}^\tau ))}.`$

Then $`f_\tau ^4(\mathrm{\Lambda },t,\mathrm{},c)k_m.`$

Proof:(1) Follows from (2).

(2) Let $`N=M_{\mathrm{}}^\tau `$ (see notation in 1.5(3), recall that $`\mathrm{}`$ is the dimension of the subspaces we are colouring) and let $`\{\gamma _a:aN\}`$ list a set disjoint to $`\mathrm{\Lambda }`$ without repetitions.

We choose for $`i=0,\mathrm{},m`$ the objects $`k_i,\tau _i,\overline{\mathrm{\Lambda }}^i`$ (consistently with what is said in the statement of the theorem) and $`M_i,M_i^+`$, by induction on $`i`$ as follows:

$`_1`$ (a) $`k_0=0`$ and $`k_i<k_{i+1}`$

(b) $`M_i`$ is a fim for $`\tau `$ of dimension $`k_i`$ (we allow empty fim, the space is the a singleton, if you do not like it start with 1)

(c) $`M_{i+1}`$ an end extension of $`M_i`$ and $`M_i^+`$ is an end extension of $`M_i`$ (so both have vocabulary $`\tau )`$ and has dimension $`k_i+mi`$

(d) $`\tau _i=\tau _{M_i^+,P^{M_i},P^{M_i^+}P^{M_i}}`$ (see Definition 1.5(3) )

(e) $`\overline{\mathrm{\Lambda }}^0=\overline{\mathrm{\Lambda }}`$ and $`\mathrm{\Lambda }_{F_{\overline{a}_1,\overline{a}_2}}^i`$ is the disjoint union of $`\mathrm{\Lambda }_F,\mathrm{\Lambda }_F^{}=^{df}\{\gamma _b:bN`$ and $`F_{N,b}=F\}`$ and $`\{\beta _b:bM_i^+`$ such that $`F_{M_i^+,b}=F\}`$ (and no two letter are incidentally equal, of course).

(f) $`c_0`$ is $`c`$ and $`c_{i+1}`$ is $`c^{\mathrm{card}(\mathrm{Space}_{\overline{\mathrm{\Lambda }}_i}(M_{k_i+mi}^\tau ))}`$

(g) $`k_{i+1}=k_i+f_{\tau _i}^1(\overline{\mathrm{\Lambda }}^i,c_i).`$

Let $`k=k_m,M=M_k`$ and let $`V_i=`$ Space$`{}_{\overline{\mathrm{\Lambda }}}{}^{}(M_i^\tau )`$ and $`V=V_m.`$ We shall regard an $`\mathrm{}`$subspace $`\mathrm{\Phi }`$ of $`V`$ as a function from $`M`$ to $`\mathrm{\Lambda }^{}=\{\gamma _b:bN\}\mathrm{\Lambda }`$, such that (and where):

$`_2`$ (a) $`\mathrm{\Lambda }=_{F\tau }\mathrm{\Lambda }_F`$,

(b) $`\mathrm{\Phi }(b)\mathrm{\Lambda }_{F_{M,b}}^{}\mathrm{\Lambda }_{F_{M,b}}`$, see clause (e) of $`_1`$

(c) if $`bM,\alpha \mathrm{\Lambda }`$ and $`(\nu )[\nu \mathrm{\Phi }\nu (b)=\alpha ]`$ then $`\mathrm{\Phi }(b)=\alpha `$

(d) if $`bM,aN`$ and for every $`\rho `$ Space$`{}_{\overline{\mathrm{\Lambda }}}{}^{}(N)`$ we have (pt$`{}_{\mathrm{\Phi }}{}^{}(\rho ))(b)=\rho (a)`$ then $`\mathrm{\Phi }(b)=\gamma _a.`$

(Reflect on the meaning of $`\mathrm{}`$subspace of $`M`$, i.e. Definition 1.7(7) and it should be clear.) Let $`d`$ be a $`c`$colouring of the set of $`\mathrm{}`$subspaces of $`V.`$ We shall define by downward induction on $`i<m`$ a (non empty) subset $`A_i`$ of $`P^{M_{i+1}}`$ disjoint to $`M_i`$ and a function $`\varrho _i`$ from $`B_i=^{df}M`$ cl$`{}_{M}{}^{}(M_i_{j=i,\mathrm{},m1}A_j)_{j=i+1,\mathrm{},m1}B_j`$ into $`\mathrm{\Lambda }\{\beta _a:aM_i^+\}.`$ We let $`𝐑_i`$ denote the family of $`\mathrm{}`$subspaces $`\mathrm{\Phi }`$ of $`V`$ which satisfies:

(\*)1 (a) if $`j`$ satisfies $`ij<m`$ and $`bB_j`$ and $`\varrho _j(b)\mathrm{\Lambda }`$ then $`\mathrm{\Phi }(b)=\varrho _j(b)`$

(b) if $`j`$ satisfies $`ij<m`$ and $`bB_j`$ and $`\varrho _j(b)=\beta _a`$ where a $`M_j`$ then $`\mathrm{\Phi }(b)=\mathrm{\Phi }(a)`$

(c) if $`b_1,b_2`$ satisfies the following then $`\mathrm{\Phi }(b_1)=\mathrm{\Phi }(b_2)`$ where the demand is:

(i) $`b_1,b_2`$ cl$`{}_{M}{}^{}(M_i_{j=i,\mathrm{},m1}A_j)`$ and

(ii) $`F_{M,b_1}=F_{M,b_2}`$ and for every $`r\{1,\mathrm{}`$, arity($`F_{M,b_1})`$ $`\}`$ we have: base$`{}_{M,r}{}^{}(b_1)=`$ base$`{}_{M,r}{}^{}(b_2)`$ or they both belongs to the same $`A_j`$ for some $`j\{i,\mathrm{},m1\}`$.

Now $`A_i,B_i,\varrho _i`$ will be chosen such that the following condition holds

(\*)2 If $`\mathrm{\Phi },\mathrm{\Psi }𝐑_i`$ satisfy the clauses (a),(b) below then $`d(\mathrm{\Phi })=d(\mathrm{\Psi })`$ where

(a) $`\mathrm{\Phi }`$ cl$`{}_{M}{}^{}(M_i_{j=i+1,\mathrm{},m1}A_j)=`$ $`\mathrm{\Psi }`$ cl$`{}_{M}{}^{}(M_i_{j=i+1,\mathrm{},m1}A_j)`$

(b) if $`bN`$ and $`\gamma _b`$ Rang$`(\mathrm{\Phi }M_{i+1})`$ then $`\gamma _b`$ Rang$`(\mathrm{\Phi }M_i)`$.

Suppose now that we have carried this induction, and we shall show that this suffice. Let $`S`$ be the following subset of $`V`$:

(\*)3 $`\eta S`$ iff

(a) if $`i<m`$ and $`bB_i`$ and $`\varrho _i(b)\mathrm{\Lambda }`$ then $`\eta (b)=\varrho _i(b)`$

(b) if $`i<m`$ and $`bB_i`$ and $`\varrho _i(b)=\beta _a`$ and $`aM_i`$ then $`\eta (b)=\eta (a)`$.

Clearly $`S`$ is an $`m`$subspace of $`V`$, and we may by (\*)2 above show that:

(\*)4 if $`\mathrm{\Phi }`$ is an $`\mathrm{}`$subspace of $`S`$, then $`d(\mathrm{\Phi })`$ can be computed from $`J[\mathrm{\Phi }]=^{df}\{`$ Min $`\{i:\mathrm{\Phi }A_i`$ is constantly the $`r`$th member of $`P^N\}:r<\mathrm{}\}.`$

So for some function $`e`$, with domain the family of subsets of $`\{0,\mathrm{},m1\}`$ with $`\mathrm{}`$ elements, we have : if $`\mathrm{\Phi }`$ is an $`\mathrm{}`$subspace of $`S`$ then $`d(\mathrm{\Phi })=e(J[\mathrm{\Phi }])`$. Clearly the set $`\mathrm{Rang}(e)`$ has $`|\mathrm{Rang}(\mathrm{d})|`$ elements.

By Ramsey theorem and the choice of $`m`$, there is a subset $`w`$ of $`\{0,\mathrm{},m1\}`$ with $`t`$ members such that the function $`e`$ is constant on the family of subsets of $`w`$ with $`\mathrm{}`$ elements. Let $`U`$ be a subspace of $`S`$ of dimension $`t`$ such that if $`bM`$, base$`(b)`$ not a subset of $`_{iw}A_i`$ then $`\nu (b):bU`$ is constant (and the constant value belongs to $`\mathrm{\Lambda }_{M,b}`$.

Clearly $`U`$ is as required. The construction, i.e. the inductive choice of $`A_i,\varrho _i`$ is straight.

$`\text{}_{3.5}`$

Section 4: The main Theorem

Now we turn to the obtainment of primitive recursive bounds. The idea is that we decrease the dependency from below, dealing with the unary functions each time (rather than dealing with $`H\tau `$ of maximal arity).

In the definition below, we shall use the case $`r=1.`$

4.1 DEFINITION: (1) Recall that for $`a`$ $`P^M`$ we let $`M_a`$ be cl$`{}_{M}{}^{}(\{P^M\{a\})`$, that is $`M`$ restricted to this set.

(2) For $`V=`$ Space$`{}_{\overline{\mathrm{\Lambda }}}{}^{}(M)`$ and $`N`$ a closed subset of $`M`$ we say that a colouring $`d`$ of $`V`$ is $`(N,r)`$base-invariant if the following holds, for any $`a`$ $`P^N:`$

(\*) if $`\nu ,\eta V`$ and $`\nu M_a=\eta M_a`$ and $`[bMr<|\{i:i=1,\mathrm{}`$, arity$`(F_{M,b})`$ and base$`{}_{M,i}{}^{}(b)=a\}|\nu (b)=\eta (b)]`$ then $`d(\nu )=d(\eta ).`$

(3) We write $`(\mathrm{},r)`$base-invariant if above $`N`$ is such that $`P^N`$ is the set of the last $`\mathrm{}`$ members of $`P^M.`$

4.2 DEFINITION: Let $`f^6`$ be defined as follows. First, $`f_{\overline{\mathrm{\Lambda }}}^6(\mathrm{},c)=`$ $`f^6(\overline{\mathrm{\Lambda }},\mathrm{},c)=f_\tau ^6(\overline{\mathrm{\Lambda }},\mathrm{},c)`$ is defined iff $`\overline{\mathrm{\Lambda }}`$ is an alphabet sequence for a vocabulary $`\tau `$. Second, let $`f_{\overline{\mathrm{\Lambda }}}^6(\mathrm{},c)`$ be the first $`k`$ (natural number, if not defined we can understand it as $`\mathrm{}`$ or $`\omega `$ or ‘does not exist‘ ) such that (\*)k below holds, where:

(\*)k If clauses (a)-(d) below hold then there is a $`d`$monochromatic line of $`V`$, where :

(a) $`M`$ is a fim of vocabulary $`\tau `$

(b) the dimension of $`M`$ is $`k`$

(c) $`V=`$ Space$`{}_{\overline{\mathrm{\Lambda }}}{}^{}(M)`$

(d) $`d`$ is an $`(\mathrm{},1)`$base-invariant colouring of $`V`$.

Immediate connections are:

4.3 Observation: (1) The function $`f_{\overline{\mathrm{\Lambda }}}^6(\mathrm{},c)`$ increases with $`c`$ and decreases with $`\mathrm{}.`$

(2) We have $`f_{\tau _1}^6(\overline{\mathrm{\Lambda }}^1,\mathrm{}_1,c_1)`$ $`f_{\tau _2}^6(\overline{\mathrm{\Lambda }}^2`$, $`\mathrm{}_2,c_2)`$ if:

(a) $`c_1c_2,\mathrm{}_1\mathrm{}_2`$, and

(b) $`s`$ arity$`(\tau _1)\mathrm{\Pi }\{|\mathrm{\Lambda }_F^1|:F\tau _1`$, arity$`(F)=s\}`$ $`\mathrm{\Pi }\{|\mathrm{\Lambda }_F^2|:F\tau _2`$, arity$`(F)=s\}`$ and

(c) arity$`(\tau _1)<s`$ arity $`(\tau _2)F\tau _2`$ arity$`(F)=s`$ $`|\mathrm{\Lambda }_F^2|=1`$

(3) In definition 4.2 the demand holds for any larger $`k.`$

(4) $`f_{\overline{\mathrm{\Lambda }}}^6(0,c)=f^1(\overline{\mathrm{\Lambda }},c).`$

Proof: Trivial.

4.4 Claim: Assume

(a) $`\tau `$ is a vocabulary of arity $`>1`$ and $`\overline{\mathrm{\Lambda }}`$ is a $`\tau `$alphabet sequence

$`(b)`$ $`\tau ^{}`$ is the following vocabulary: $`\{G_{F,e}:F\tau `$, arity$`(F)>1`$ and $`e`$ is a convex equivalence relation on $`\{1,\mathrm{}`$, arity$`(F)\}`$ such that each $`e`$equivalence class has at least two elements $`\}`$

with arity$`(G_{F,e})=`$ the number of $`e`$equivalence classes and for some $`H\tau `$ of maximal arity, letting $`e=^{df}\{(i,j):i,j[1`$,arity$`(H)]\}`$ we identify $`G_{H,e}`$ with id

$`(c)`$ $`\overline{\mathrm{\Lambda }}^{}`$ is the following $`\tau ^{}`$alphabet sequence: $`\mathrm{\Lambda }_{G_{F,e}}^{}=\mathrm{\Lambda }_F.`$

$`(d)`$ $`\mathrm{}^{}=f_\tau ^{}^1(\overline{\mathrm{\Lambda }}^{},c)`$.

Then $`f_{\overline{\mathrm{\Lambda }}}^6(\mathrm{}^{},c)\mathrm{}^{}`$.

Proof: Let $`M`$ be a fim of vocabulary $`\tau `$ and dimension $`\mathrm{}^{}`$ and $`V=`$ Space$`{}_{\overline{\mathrm{\Lambda }}}{}^{}(M)`$ and $`d`$ is a $`c`$colouring of $`V`$ which is $`(\mathrm{}^{},1)`$base-invariant; it suffice to find a monochromatic $`V`$line $`L..`$

Let $`M^{}`$ be a fim of vocabulary $`\tau ^{}`$ and dimension $`\mathrm{}^{}`$ and $`V^{}=`$ Space$`{}_{\overline{\mathrm{\Lambda }}^{}}{}^{}(M^{}).`$ Let $`g_0`$ be an isomorphism from $`(P^M,<^M)`$ onto $`(P^M^{},<^M^{}).`$ We define a partial function $`g`$ from $`M`$ into $`M^{}`$ as follows; if $`b=F^M(b_1,\mathrm{},b_t)`$ so $`t=`$ arity$`{}_{\tau }{}^{}(F)`$ and $`b_1^Mb_2^M\mathrm{}^Mb_t`$ and $`e=\{(i,j):b_i=b_j\}`$ and $`G_{F,e}`$ $`\tau ^{}`$ is well defined (i.e. every $`e`$equivalence class has at least two elements) and the $`e`$equivalence classes are \[$`s_i,s_{i+1})`$ for $`i=1,\mathrm{}`$,arity$`(G_{F,e})1`$ and 1$`=s_1<s_2<\mathrm{}`$ $`<s_{\mathrm{arity}(G_{F,e})}=t+1`$ then $`g(b)=G_{F,e}^M^{}(g_0(b_{s_1}),\mathrm{}`$, $`g_0(b_{s_{\mathrm{arity}(G_{F,e})1}})).`$

Note:

$`()_1`$ $`g`$ is really a partial function from $`M`$ to $`M^{}`$

$`()_2`$ if $`\eta ,\nu V`$ and $`\eta \mathrm{Dom}(g)=\nu \mathrm{Dom}(g)`$ then $`d(\eta )=d(\nu )`$

\[Why? By the transitivity of equality, it is enough to consider the case that for some $`a^{}M\mathrm{Dom}(g)`$ we have $`\{a^{}\}=\{aM:\eta (a)\nu (a)\}`$. Now by the definition of $`g`$ for some $`aP^M`$ we have $`(!i)[\mathrm{base}_{M,i}(b)=a]`$. Now read the Definition 4.1(2),(3) of the base invariant\]

(\*)3 we can define a $`c`$colouring $`d^{}`$ of $`V^{}`$ such that $`\eta V,\nu V^{}`$, and $`[b`$ Dom$`(g)\eta (b)=\nu (g(b))]`$ then $`d(\eta )=d^{}(\nu )`$

\[why? by (\*)$`{}_{2}{}^{}]`$

(\*)4 for any $`V^{}`$line $`L^{}`$ there is a $`V`$line $`L`$ such that for every $`\eta L`$ for some $`\nu L^{}`$ we have $`d(\eta )=d^{}(\nu )`$

\[Why? Reflect. In details, let $`w^{}=`$ supp$`{}_{}{}^{P}(L^{})`$ and $`N^{}=`$ supp$`(L^{})`$ and $`\nu ^{}`$ is the function with domain $`M^{}N^{}`$ such that for every $`b`$ from this set and $`\nu L^{}`$ we have $`\nu (b)=\nu ^{}(b).`$ Let $`w=^{df}\{bP^M:g_0(b)w^{}\}`$ and let $`N=^{df}`$ cl$`{}_{M}{}^{}(w)`$ and choose a function $`\eta ^{}`$ with domain $`MN`$ such that for every $`bMN`$ we have $`\eta ^{}(b)=\nu ^{}(g(b))`$ if $`b\mathrm{Dom}(g)`$ and is any member of $`\mathrm{\Lambda }_{F_{M,b}}`$ otherwise. Let $`L`$ be the $`V`$line such that supp$`(L)=N`$ and for every $`\eta L`$ we have $`\eta `$ extend $`\eta ^{}.`$ Clearly $`L`$ is a $`V`$line and let $`\eta L`$ and we should check the desired conclusion. So there is $`p𝔭_{\overline{\mathrm{\Lambda }}}`$ such that $`\eta =`$ pt$`{}_{L}{}^{}(p);`$ now we define $`q𝔭_{\overline{\mathrm{\Lambda }}^{}}`$ as follows: $`q(G_{F,e})=p(F)`$, the later belongs to $`\mathrm{\Lambda }_F`$ which is equal to $`\mathrm{\Lambda }_{G_{F,e}}^{}.`$ Let $`\nu =`$pt$`{}_{L^{}}{}^{}(q)`$ and we should just check that $`\eta ,\nu `$ are as in (\*)3 above so we are done.\]

By the assumption $`\mathrm{}^{}=f^1(\overline{\mathrm{\Lambda }}^{},c))`$ (see clause $`(d)`$ in the assumption), hence there is a $`d^{}`$monochromatic $`V^{}`$line $`L^{}.`$ Apply (\*)4 to it, so there is a $`d`$monochromatic $`V`$line and so we are done.

$`\text{}_{4.4}`$

4.5 DEFINITION: (1) Assume the following:

(i) $`\overline{\mathrm{\Lambda }}`$ is an alphabet sequence for the vocabulary $`\tau `$

(ii) $`P\{(p,q):p,q`$ are $`\overline{\mathrm{\Lambda }}`$-types $`\}`$, see Def 1.6

(iii) $`m,c>0`$.

We define $`f_{\overline{\mathrm{\Lambda }}}^7(P,m,c)`$ as the first $`k`$ (if there is no such $`k`$ it is $`\omega `$ or $`\mathrm{}`$ or undefined) such that (\*)k stated below holds, where

(\*)k if clauses (a)-(e) below hold then there is a subspace $`S`$ of $`V`$ of dimension $`m`$, satisfying:

if $`L`$ is a $`V`$line $`S`$, and $`(p,q)P`$ then $`d`$(pt$`{}_{L}{}^{}(p))=d`$(pt$`{}_{L}{}^{}(q))`$

where

(a) $`M`$ is a fim of vocabulary $`\tau `$

(b) $`M`$ has dimension $`k`$

(c) $`V=`$ Space$`{}_{\overline{\mathrm{\Lambda }}}{}^{}(M)`$

(d) $`P`$ is a subset of $`\{(p,q):p,q𝔭_{\overline{\mathrm{\Lambda }}}`$ and $`[F\tau `$ arity$`(F)>1p(F)=q(F)]\}`$

(e) $`d`$ is a $`c`$colouring of $`V`$

(2) Let $`P`$$`{}_{\overline{\mathrm{\Lambda }}}{}^{}=`$ $`\{(p,q):p,q𝔭_{\overline{\mathrm{\Lambda }}}`$ and $`[F\tau `$ arity$`(F)>1p(F)=q(F)]\}`$

4.6 MAIN Claim: Assume

(a) $`\overline{\mathrm{\Lambda }}`$ is an alphabet sequence for a vocabulary $`\tau =\tau [\overline{\mathrm{\Lambda }}].`$

(b) $`k_0f_{\overline{\mathrm{\Lambda }}}^6(\mathrm{}+1,c)`$ and $`k_0>\mathrm{}.`$

(c) $`K`$ is a $`\tau `$fim of dimension $`k_01`$ with $`A_2`$ the last $`\mathrm{}`$ elements and $`A_1`$ the first $`(k_0\mathrm{}1)`$elements (this $`K`$ surve just for notation).

(d) $`\tau ^{}`$ is the vocabulary $`\tau _{K,A_1,A_2}`$, see Definition 1.5(1) and proj is the following function from $`\tau ^{}`$ to $`\tau :`$ it map $`F_{K,\overline{a}_1,\overline{a}_2}`$ to $`F`$ and $`\overline{\mathrm{\Lambda }}`$$`{}_{}{}^{}=_{}^{df}\mathrm{\Lambda }_F^{}:F\tau ^{}`$ where $`\mathrm{\Lambda }_F^{}=\mathrm{\Lambda }_{\mathrm{proj}(F)}`$, so proj $`\tau `$ is the identity.

(e) $`c^{}=^{df}c^{\mathrm{card}(\mathrm{Space}_{\overline{\mathrm{\Lambda }}}(K))}.`$

Then

$`f_{\overline{\mathrm{\Lambda }}}^6(\mathrm{},c)k_0+`$ $`f_{\overline{\mathrm{\Lambda }}^{}}^7(P_{\overline{\mathrm{\Lambda }}^{}},1,c^{})1`$

REMARK: This is similar to the proof of 2.4, but for completeness we do it in full.

Proof: Let $`k_1=f_{\overline{\mathrm{\Lambda }}^{}}^7(1,P_{\overline{\mathrm{\Lambda }}^{}},c^{})`$ and let $`k=k_0+k_11`$, so it suffice to prove that $`kf_{\overline{\mathrm{\Lambda }}}^0(n,\mathrm{},c).`$ For this it is enough to check (\*)k from Definition 4.2, also let $`M`$ be a fim of vocabulary $`\tau `$ and dimension $`k`$ (that is $`P^M`$ is with $`k`$ members), $`V=`$ Space$`{}_{\overline{\mathrm{\Lambda }}}{}^{}(M)`$, and $`d`$ an $`(\mathrm{},1)`$base-invariant $`C`$colouring of $`V`$ such that $`C`$ has $`c`$ members. So we just have to prove that the conclusion of Definition 4.2 holds, that is there is a monochromatic $`V`$line.

Let $`w_1=^{df}\{a:aP^M`$ and the number of $`b<^M`$ a is $`k_0\mathrm{}1`$ but is $`<k_0\mathrm{}1+k_1\}`$ hence in $`w_1`$ there are $`k_1`$ members, and let $`w_0`$ be the set of first $`k_0\mathrm{}1`$ members of $`P^M`$ by $`<^M`$, lastly let $`w_2`$ be the set of the $`\mathrm{}`$ last members of $`M`$ by $`<^M.`$ So $`w_0,w_1,w_2`$ form a convex partition of $`P^M.`$

Now we let $`K`$ be $`M`$ restricted to cl$`{}_{M}{}^{}(w_0w_2)`$, (note that this gives no contradiction to the assumption on $`K`$, as concerning $`K`$ there, only its vocabulary and dimension are important and they fit). Let $`K^+`$ be a fim with vocabulary $`\tau `$ and dimension $`k_0`$, let $`g_0`$ PHom$`(M,K^+)`$ be the following function from $`P^M`$ onto $`P^{K^+}:`$ it maps all the members of $`w_1`$ to one member of $`P^{K^+}`$ which we call $`b^{}`$, it is a one to one order preserving function from $`w_2`$ onto $`\{bP^{K^+}:b^{}<^{K^+}b\}`$ and it is a one to one order preserving function from $`w_0`$ onto $`\{bP^{K^+}:b<^{K^+}b^{}\}.`$ Let $`g`$ Hom$`(M,K^+)`$ be the unique extension of $`g_0;`$ without loss of generality $`g_0`$ is the identity on $`w_0`$ and on $`w_2`$ hence without loss of generality $`g`$ is the identity on $`K`$, it exist by 1.2.

Next recall that the vocabulary $`\tau ^{}=\tau _{K,w_o,w_2}`$ is a well defined vocabulary (see Definition 1.5(1)). Next we shall define a $`\tau ^{}`$fim $`N.`$ Its universe is $`MK;`$ we let $`P^N`$ be $`w_1`$ and $`<^N`$ be $`<^MP^N.`$ Now we have to define the function $`F_{K,\overline{a}_1,\overline{a}_2}^N`$, say of arity $`r`$, where $`F\tau ,\overline{a}_1`$ a non decreasing sequence from $`w_0`$ and $`\overline{a}_2`$ a non decreasing sequence from $`w_2`$, and lg($`\overline{a}_1)+`$ lg$`(\overline{a}_2)<`$ arity$`(F)`$. So $`r=\mathrm{arity}(F)\mathrm{lg}(\overline{a}_1)\mathrm{lg}(a_2)`$.

For $`b_1^N\mathrm{}^Nb_rP^N`$ we let $`F_{\overline{a}_1,\overline{a}_2}^N(b_1,\mathrm{},b_r)`$ be equal to

$`b=F^M(\overline{a}_1,b_1,\mathrm{},b_r,\overline{a}_2)`$ $`=F^M(a_1^1,a_2^1,\mathrm{},a_{\mathrm{lg}(\overline{a}_1)}^1`$, $`b_1,\mathrm{},b_r,a_1^2,\mathrm{},a_{\mathrm{lg}(\overline{a}_2)}^2).`$

It is easy to check that the number of arguments is right and also the sequence they form is $`^M`$increasing, so this is well defined and belongs to $`M`$, but still we have to check that it belongs to $`N.`$ But $`N=MK`$ and if $`bK`$ then base$`{}_{\mathrm{lg}(\overline{a}_1)+1}{}^{}(b)K`$ and it is just $`b_1`$ which belongs to $`w_1`$, contradiction. Lastly it is also trivial to note that every member of $`N`$ has this form. It is easy to check that $`N`$ is really a $`\tau ^{}`$fim.

We next let $`V^{}=`$ Space$`{}_{\overline{\mathrm{\Lambda }}^{}}{}^{}(N)`$ let $`C^{}=\{g:g`$ is a function from $`\mathrm{Space}_{\overline{\mathrm{\Lambda }}}(K)`$ to $`C\}`$ and define a $`C^{}`$ colouring $`d^{}`$ of $`V^{}.`$ For $`\eta V^{}`$ let $`d^{}(\eta )`$ be the following function from Space$`{}_{\overline{\mathrm{\Lambda }}}{}^{}(K)`$ to $`C:`$ for $`\nu K`$ we let $`\left(d^{}(\eta )\right)(\nu )=d(\eta \nu ).`$

Clearly the function $`d^{}(\eta )`$ is a $`C^{}`$colouring of $`K.`$ How many such functions, that is members of $`C^{}`$ there are? The domain has clearly card(Space$`{}_{\overline{\mathrm{\Lambda }}}{}^{}(K))`$ members, (we can get slightly less if $`\mathrm{}>0`$, but with no real influence). The range has at most $`c`$ members, so the number of such functions is at most $`c^{\mathrm{card}(\mathrm{Space}_{\overline{\mathrm{\Lambda }}}(K))}`$, a number which we have called $`c^{}`$ in the claim’s statement.

Hence $`d^{}`$ is a $`c^{}`$colouring.

So as we have chosen $`k_1=`$ $`f_{\overline{\mathrm{\Lambda }}^{}}^7(P_{\overline{\mathrm{\Lambda }}^{}},1,c^{})`$ we can apply Definition 4.5 to $`V^{}=`$ Space$`{}_{\overline{\mathrm{\Lambda }}^{}}{}^{}(N)`$ and $`d^{};`$ so we can find a $`d^{}`$monochromatic $`V^{}`$line $`L^{}.`$ Let $`h`$ be the function from $`U=^{df}`$ Space$`{}_{\overline{\mathrm{\Lambda }}}{}^{}(K^+)`$ to $`V`$ defined as follows:

(\*) $`h(\rho )=\nu `$ iff :

(a) $`\nu V,\rho U`$,

(b) $`\nu K=\rho K`$

(c) if $`bN`$ supp$`{}_{N}{}^{}(L^{})`$ then $`\nu (b)=\eta (b)`$ for every $`\eta L^{}.`$

(d) if a $``$ supp$`{}_{N}{}^{}(L^{})`$, (so a $`N`$, $`F_{N,a}=F_{K,\overline{a}_1,\overline{a}_2}`$, base$`{}_{N}{}^{}(a)`$ supp$`{}_{N}{}^{P}(L^{}))`$, and $`bK^+`$, $`F_{K^+,b}=F,b=F(\overline{a}_1,b^{},\mathrm{},b^{},\overline{a}_2)`$ (with the number of cases of $`b^{}`$ being arity$`(F_{K,\overline{a}_1,\overline{a}_2}))`$ then $`\rho (b)=\nu (a).`$

Let the range of $`h`$ be called $`S.`$ Now clearly

$`_1(\alpha )h`$ is a one to one function from $`U`$ to $`SV.`$

$`(\beta )`$ $`S`$ has $`|`$Space$`{}_{\overline{\mathrm{\Lambda }}}{}^{}(K^+)|`$ members

$`(\gamma )`$ $`S`$ is a subspace of $`V`$ of dimension $`k_0,h(\rho )=`$ pt$`{}_{S}{}^{}(\rho )`$, see Definition 1.7(7).

Now clearly

$`_2`$ there is a $`C`$colouring $`d^{}`$ of $`U`$ such that:

$`d^{}(\nu )=d(h(\nu ))`$ for $`\nu U.`$

and

$`_3`$ $`d^{}`$ is $`(\mathrm{}+1,1)`$base -invariant

\[WHY? Reflect\]

Applying the definition of $`k_0=f_{\overline{\mathrm{\Lambda }}}^6(\mathrm{}+1,c)`$ , that is Definition 4.2 to $`\overline{\mathrm{\Lambda }},U,d^{}`$ we can conclude that there is a $`d^{}`$monochromatic $`U`$line $`L^{}.`$ Let $`L=^{df}\{h(\rho ):\rho L^{}\}.`$ It is easy to check that $`L`$ is as required.

$`\text{}_{4.6}`$

4.7 Claim: (1) Assume that $`\overline{\mathrm{\Lambda }}`$ is a $`\tau `$alphabet sequence , and $`p^{}𝔭_{\overline{\mathrm{\Lambda }}}`$ and $`P`$$`{}_{}{}^{+}=`$ $`P`$ $`\{(p^{},q):q𝔭_{\overline{\mathrm{\Lambda }}}`$ and

$`[F\tau `$ $``$ arity $`(F)>1q(F)=p^{}(F)\}`$ $`P`$$`_{\overline{\mathrm{\Lambda }}}`$ (see Definition 4.5) and $`n=\mathrm{\Pi }_{F\tau ,\mathrm{arity}(F)=1}|\mathrm{\Lambda }_F|.`$ Then

$`f_{\overline{\mathrm{\Lambda }}}^7(P^+,m,c)`$ HJ$`(n,f_{\overline{\mathrm{\Lambda }}}^7(P,m,c),c)`$

(on HJ see 0.3(2)).

(2) $`f^7(\overline{\mathrm{\Lambda }},P_{\overline{\mathrm{\Lambda }}},m,c)`$ is in $`E`$$`_6.`$

Proof: (1) Straight. Let $`M`$ be a $`\tau `$fim of dimension $`k=^{df}`$ HJ$`(n,f_{\overline{\mathrm{\Lambda }}}^7(P,m,c),c)`$ and let $`V=`$ Space$`{}_{\overline{\mathrm{\Lambda }}}{}^{}(M)`$ and let $`d`$ be a $`c`$colouring of $`V.`$ Let $`\tau ^{}=\{F\tau :`$arity$`(F)=1\}`$ and let $`M^{}`$ be a $`\tau ^{}`$fim of dimension $`k`$, without loss of generality $`M^{}`$ is $`M`$ restricted to $`\tau ^{}`$ and the universe of $`M^{}.`$ Let $`\overline{\mathrm{\Lambda }}`$$`{}_{}{}^{}=\overline{\mathrm{\Lambda }}\tau ^{}`$ and let $`V^{}=`$ Space$`{}_{\overline{\mathrm{\Lambda }}^{}}{}^{}(M^{})`$ and let $`h`$ be the function from $`V^{}`$ to $`V`$ defined as follows: let $`\eta V^{}`$, for $`bM`$ let $`(h(\eta ))(b)`$ be $`\eta (b)`$ is $`bM^{}`$ and be $`p^{}(F_{M,b})`$ if $`bMM^{}.`$ So $`h`$ is a function as required and we define a $`c`$colouring $`d^{}`$ of $`V^{}`$ by $`d^{}(\nu )=d(h(\nu ))`$ for $`\nu V^{}.`$

Now we apply the definition of $`k=`$ HJ$`(n,f_{\overline{\mathrm{\Lambda }}}^7(P,m,c),c)`$ to the space $`V^{}`$ and the colouring $`d^{}`$ and we get a subspace $`S^{}`$ of $`V^{}`$ on which $`d^{}`$ is constant and has dimension $`f_{\overline{\mathrm{\Lambda }}}^7(P,m,c).`$ There is a unique subspace $`S^{}`$ of $`V`$ of dimension $`f_{\overline{\mathrm{\Lambda }}}^7(P,m,c)`$ such that $`\eta S^{}\eta M^{}S^{}.`$ Clearly:

$`()_1`$ if $`L`$ is a $`V`$line which is $`S`$ and $`(p,q)P^+P`$ then $`pt_L(p)=d(pt_L(q))`$

Now, letting $`k^{}=f_{\overline{\mathrm{\Lambda }}}^7(P,m,c)`$ and $`d^{}=dS^{}`$, we can apply the definition of $`f_{\overline{\mathrm{\Lambda }}}^7(P,m,c)`$ and get a subspace $`S`$ of $`S^{}`$ of dimension $`m`$ such that

$`()_2`$ if $`L`$ is a $`V`$line which is included in $`S`$ and $`(p,q)P`$ then $`d^{}(pt_L(p))=d^{}(pt_L(q))`$ which means that $`d(pt_L(p))=d(pt_L(q))`$

By $`()_1+()_2`$, clearly $`S`$ is as required.

(2) Let $`\{p_i^{}:i<i()\}`$ be maximal subset of $`P`$$`_{\overline{\mathrm{\Lambda }}}`$ such that $`i<j<i()p_i^{}\{F\tau :`$ arity$`(F)>1\}`$ $`p_j^{}\{F\tau :`$ arity$`(F)>1\}`$ and let $`P`$$`{}_{j}{}^{}=\{(p_i^{},q):i<j`$ and $`q𝔭_{\overline{\mathrm{\Lambda }}}`$ and $`q\{F\tau :`$ arity$`(F)>1\}=`$ $`p_i^{}\{F\tau :`$ arity$`(F)>1\}\}.`$ By part (1) we have a recursion formula (we use 1.10 freely):

$`f_{\overline{\mathrm{\Lambda }}}^7(P_{i+1},m,c)`$ HJ$`(|\mathrm{\Pi }_{F\tau ,\mathrm{arity}(F)=1}|\mathrm{\Lambda }_F|,f_{\overline{\mathrm{\Lambda }}}^7(P_i,m,c),c)`$

As HJ belongs to $`E`$5 ( by \[Sh 329, 1.8(2),p.691), we are done.

$`\text{}_{4.7}`$

4.8 DEFINITION: Let $`f^{6,}(\overline{\mathrm{\Lambda }},\mathrm{},t,c)`$ is defined by induction on $`\mathrm{}`$ as follows:

$`f^{6,}(\overline{\mathrm{\Lambda }},0,t,c)=t`$

$`f^{6,}(\overline{\mathrm{\Lambda }},\mathrm{}+1,t,c)`$ is equal to $`k_0+f_{\overline{\mathrm{\Lambda }}[k_0]}^7(P_{\overline{\mathrm{\Lambda }}[k_0]},1,c^{\mathrm{card}(\mathrm{Space}_{\overline{\mathrm{\Lambda }}}(M_{k_0}^\tau )})1`$

where $`k_0=\mathrm{Max}\{,\mathrm{}+1,f^{6,}(\overline{\mathrm{\Lambda }},\mathrm{},t,c)`$ and $`\overline{\mathrm{\Lambda }}`$$`[k_0]`$ is defined from $`\overline{\mathrm{\Lambda }}`$ as in the main claim 4.6.

4.9 Claim: $`f^{6,}`$ beongs to $`E`$7

Proof: Straight.

4.10 Theorem: (1) The function $`f^1(\overline{\mathrm{\Lambda }},c)`$ is well defined, i.e. always get value, a natural number and is primitive recursive, in fact belongs to $`E`$$`_8.`$

(2) Similarly the function $`f^6(\overline{\mathrm{\Lambda }},\mathrm{},c).`$

(3) $`f^4`$ is primitive recursive, in fact belongs to $`E`$$`_9.`$

Proof: (1),(2) Let $`\tau =\tau [\overline{\mathrm{\Lambda }}].`$ The proof follows by induction, the main induction is on $`t=`$ arity$`(\tau _{\overline{\mathrm{\Lambda }}})`$ (or, if you prefer $`\mathrm{\Pi }_{F\tau [\overline{\mathrm{\Lambda }}]}(|\mathrm{\Lambda }_F|+1)).`$

CASE 0: arity$`(\tau )=1`$

This is Hales-Jewett theorem (on a bound see \[Sh:329\] or \[GRS80\])

CASE 1: arity$`(\tau )>1`$

Let $`\tau ^{},\overline{\mathrm{\Lambda }}^{}`$ be as in claim 4.4, so arity$`(\tau ^{})`$ $``$ arity$`(\tau )/2`$ and $`|\tau ^{}||\tau |\times 2^{\mathrm{arity}(\tau )}.`$

Let $`\mathrm{}^{}=f^1(\overline{\mathrm{\Lambda }}^{},c)`$ so (by 4.4) clearly $`f_{\overline{\mathrm{\Lambda }}}^6(\mathrm{}^{},c)\mathrm{}^{}`$ hence (by Definition 4.8) clearly $`f^{6,}(\overline{\mathrm{\Lambda }},0,\mathrm{}^{},c)=\mathrm{}^{}=f^1(\overline{\mathrm{\Lambda }}^{},c)`$ ; together we get $`f_{\overline{\mathrm{\Lambda }}}^6(\mathrm{}^{},c)f^{6,}(\overline{\mathrm{\Lambda }},0,\mathrm{}^{},c)`$. Hence (by 4.6 $`+`$ Definition 4.8, we shall prove by induction on $`\mathrm{}\mathrm{}^{})`$ that $`f_{\overline{\mathrm{\Lambda }}}^6(\mathrm{}^{}\mathrm{},c)f^{6,}(\overline{\mathrm{\Lambda }},\mathrm{},\mathrm{}^{},c)`$; for $`\mathrm{}=0`$ this holds by the previous sentnece; for the induction step, i.e. the proof for $`\mathrm{}+1`$ we apply Theorem 4.6 with $`\mathrm{}^{}\mathrm{},\mathrm{}^{}(\mathrm{}+1)`$ here standing for $`\mathrm{}+1,\mathrm{}`$ there and letting $`k_0=\mathrm{Max}\{\mathrm{}^{}\mathrm{},f_{\overline{\mathrm{\Lambda }}}^6(\mathrm{}^{},c)\}`$ and $`\tau ^{},\overline{\mathrm{\Lambda }}^{},c^{}`$ defined as there, and we get that $`f_{\overline{\mathrm{\Lambda }}}^6(\mathrm{}^{}(\mathrm{}+1),c)k_0+f_{\overline{\mathrm{\Lambda }}^{}}^7(P_{\overline{\mathrm{\Lambda }}^{}},1,c^{})1\mathrm{Max}\{\mathrm{}^{}\mathrm{},f_{\overline{\mathrm{\Lambda }}}^6(\mathrm{}^{},c)\}+f_{\overline{\mathrm{\Lambda }}^{}}^7(P_{\overline{\mathrm{\Lambda }}^{}},1,c^{})1`$

but the last expression is exactly $`f^{6,}(\overline{\mathrm{\Lambda }},\mathrm{}+1,\mathrm{}^{},c)`$

So (using $`\mathrm{}=\mathrm{}^{})`$ clearly $`f_{\overline{\mathrm{\Lambda }}}^6(0,c)f^{6,}(\overline{\mathrm{\Lambda }},\mathrm{}^{},\mathrm{}^{},c).`$

Now

$`f^1(\overline{\mathrm{\Lambda }},c)=f_{\overline{\mathrm{\Lambda }}}^6(0,c)`$ $`f^{6,}(\overline{\mathrm{\Lambda }},\mathrm{}^{},\mathrm{}^{},c)`$ $`f^{6,}(\overline{\mathrm{\Lambda }},f^1(\overline{\mathrm{\Lambda }}^{},c),\phi ^1(\overline{\mathrm{\Lambda }}^{},c),c).`$

As $`f^{6,}`$ is from $`E_7`$ by 3.14, this clearly give the desired conclusion.

(3) Should be clear from the proof of 3.5 and the previous parts.

$`\text{}_{4.10}`$

REFERENCE

\[BL96\] V. Bergelson and A. Leibman, Polynomial extensions of van der Waerder’$`s`$ and Szemeredi theorems, JAMS 9(1996)725-753

\[BL 9x\] V. Bergelson and A. Leibman, Set polynomial and polynomial extensions of the Hales Jewett theorem, to appear

\[Fu81\] H. Furstenberg, Recurrence in Ergodic Theory and Combinatorial Number Theory, Princeton University Press 1981

\[GR71\] R.L. Graham, B.L. Rothschild, Ramsey’s theorem for $`n`$parameter sets, TAMS 159(1971)257-292

\[GRS80\] R.L. Graham, B.L. Rothschild and H.J. Spencer, Ramsey Theory Wiley-Interscience Ser. in Discrete Math. New York 1980

\[Ro84\] H.E. Rose, Subrecursion: functions and heirarchies, Oxford Logic Guide 9, Oxford University Press, Oxford 1984

\[Sh:329\] Shelah, Saharon, Primitive recursive bounds for van der Waerden numbers, Journal of the American Mathematical Society, 1 (1988) 683–697