An elementary proof of the canonizing version of Gallai-Witt's theorem (Q1073794)

According to the classical theorem of \textit{B. L. van der Waerden} [Nieuw Arch. Wiskd. 15, 212-216 (1927; JFM 53.0073.12)], if \(N=\{0,1,2,...\}=C_ 1\cup...\cup C_ r\) then for some i, \(C_ i\) contains arbitrarily long arithmetic progressions. The finite form of van der Waerden's theorem (for two classes) asserts the following: For all \(k\in N\setminus \{0\}\), there exists a least n(k) so that if \(\{0,1,2,...,n(k)-1\}=C_ 1\cup C_ 2\) then some \(C_ i\) must contain a k-term arithmetic progression. A multi-dimensional version of van der Waerden's theorem is independently due to T. Gallai (see \textit{R. Radó} [Math. Z. 36, 424-480 (1933; Zbl 0006.14603)]) and to \textit{E. Witt} [Math. Nachr. 6, 261-262 (1951)]. It asserts that for every mapping \(\Delta\) :\(\{0,...,n-1\}^ t\to \{0,1\}\), where \(n\geq n(t,k)\) is sufficiently large, there exists a homothety \(h: N^ t\to N^ t\) \((h(x)=a+dx\), \(a\in N^ t\), \(d\in N\setminus \{0\})\) such that \(\Delta (h(b))=\Delta (h(c))\) for all \(b,c\in \{0,...,k-1\}^ t\). The following result of \textit{P. Erdős} and \textit{R. L. Graham} [Old and new problems and results in combinatorial number theory (Monographie 28, L'Enseignement Mathématique, Genève) (1980; Zbl 0434.10001)] is called the canonical version of van der Waerden's theorem. For every mapping \(\Delta\) :\(\{\) 0,...,n-1\(\}\) \(\to N\), where \(n\geq n_ 0(k)\) is sufficiently large, there exists a k-term arithmetic progression \(P\subseteq \{0,...,n-1\}\) such that \(\Delta_{| P}\) is either a constant mapping or a one-to-one mapping (i.e., there are two ''canonical types'' for \(\Delta_{| P}).\) A vector \(b\in Q^ t\) is called admissible for \(S\subseteq N^ t\) iff there exists a vector \(a\in Q^ t\) such that the affine line \(\{a+\lambda b| \lambda \in Q\}\) intersects S in at least two points. Let \({\mathcal A}(S)\) denote the set of linear subspaces of \(Q^ t\) possessing a basis of admissible vectors. Additionally the null-space \(\{\) \(0\}\) belongs to \({\mathcal A}(S)\). \textit{W. Deuber, R. L. Graham, H. J. Prömel} and \textit{B. Voigt} [J. Comb. Theory, Ser. A 34, 331-339 (1983; Zbl 0514.05002)] proved the following canonical version of the Gallai- Witt theorem. Let \(S\subseteq N^ t\) be a finite set. Then there exists a finite set \(T\subseteq N^ t\) such that for every mapping \(\Delta\) : \(T\to N\) there exists a homothety \(h: N^ t\to N^ t\) and a linear subspace \(U\in {\mathcal A}(S)\) with the property that \(\Delta (h(b))=\Delta (h(c))\) iff b-c\(\in U\), for every b,c\(\in S\). The original proof is based on \textit{H. Fürstenberg} and \textit{Y. Katznelson}'s [J. Anal. Math. 34, 275-291 (1978; Zbl 0426.28014)] deep density version of the Gallai-Witt theorem. In the paper under review, the autors give an elementary proof of the above canonical version of the Gallai-Witt theorem. The main tool of this proof is the following lemma. Let t, k be positive integers. Then there exists a positive integer \(n=n(t,k)\) such that for every mapping \(\Delta:\{0,...,n-1\}^ t\to N\) there exists a homothety \(h: N^ t\to N^ t\) such that for every line \(L\in {\mathcal A}(\{0,...,k-1\}^ t)\) the following is valid: if \(\Delta (h(y_ 0))=\Delta (h(y_ 1))\) for some \(y_ 0,y_ 1\in \{0,...,k-1\}^ t\) satisfying \(y_ 1-y_ 0\in L\), then \(\Delta (h(z_ 0))=\Delta (h(z_ 1))\) for every \(z_ 0,z_ 1\in \{0,...,k-1\}^ t\) satisfying \(z_ 1-z_ 0\in L\). A slight modification of the elementary proof also yields a canonization theorem due to \textit{J. H. Spencer} [J. Comb. Theory, Ser. A 34, 325-330 (1983; Zbl 0508.05048)] which characterizes the canonical partitions of finite subsets of \(R^ t\) with respect to the group of homotheties acting on \(R^ t\).