% LaTeX2e \documentclass%[12pt] {article} \usepackage{amstex} \usepackage{amssymb} \def\goth{\frak} \newcommand{\res}{\upharpoonright} \newcommand{\propsub}{\subsetneqq} %\newcommand{\qed}{\nopagebreak\par\noindent\nopagebreak$\Box$\par} \def\rmiff{\mbox{ iff }} \def\rmand{\mbox{ and }} \def\dom{{\rm dom}} \def\proof{{\sc Proof. }} \def\reals{{\Bbb R}} \def\rationals{{\Bbb Q}} \def\A{{\cal H}} \def\D{{\cal D}} \def\E{{\cal E}} \def\F{{\cal F}} \def\G{{\cal G}} \def\P{{\cal P}} \def\cf{{\rm cf}} \def\qed{\hfill$\Box$} \def\proj{{{\rm pr}_x}} \def\continuum{{\goth c}} \def\poset{{\Bbb P}} \def\su{\subseteq} \def\eq{{\goth e}} \def\la{\langle} \def\ra{\rangle} \def\implies{\longrightarrow} %double implication \newcommand{\Impl}{\mbox{$\Rightarrow$}} %% Theorems, etc. \newtheorem{theorem}{Theorem}[section] \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{problem}{Problem}[section] \newtheorem{example}{Example}[section] \newtheorem{definition}{Definition} \newtheorem{conjecture}{Conjecture}[section] \newcommand{\thm}[2]{\begin{theorem}\label{#1}#2\end{theorem}} \newcommand{\cor}[2]{\begin{corollary}\label{#1}#2\end{corollary}} \newcommand{\prop}[2]{\begin{proposition}\label{#1}#2\end{proposition}} \newcommand{\lem}[2]{\begin{lemma}\label{#1}#2\end{lemma}} \newcommand{\pr}[2]{\begin{problem}\label{#1}#2\end{problem}} \newcommand{\ex}[2]{\begin{example}\label{#1}#2\end{example}} \newcommand{\defi}[2]{\begin{definition}\label{#1}#2\end{definition}} \newcommand{\conj}[2]{\begin{conjecture}\label{#1}#2\end{conjecture}} \pagestyle{myheadings} \title{Sum and difference free partitions of vector spaces% \thanks{ 1991 {\it Mathematics Subject classification}: 03E05; 04A20. \endgraf % The author would like to thank referee for an admirable job of pointing out numerous typos and making valuable suggestions.\endgraf % Work partially supported by the NATO Collaborative Research Grant CRG~950347. \endgraf % The author thanks Professor Dikran Dikranjan from the University of Udine, Italy, for his hospitality in June of 1995, while some of this research was carried out.}.} \author{} \date{} \markright{Sum and difference free partitions of vector spaces.} \begin{document} \maketitle {\small\noindent Krzysztof Ciesielski, Department of Mathematics, West Virginia University, Morgantown, WV 26506-6310 (kcies@@wvnvms.wvnet.edu)} %\vspace{.5in} \section{$\!\!\!\!\!\!\!${\bf.} Preliminaries.} In this paper $V$ will stand for a vector space over rationals $\rationals$ and $S$ for a subset of $V$. All the partitions $\P$ of a set $S\su V$ will be countable, i.e., $|\P|\leq\omega$. They will be often identified with coloring $f\colon S\to\omega$ of $S$, via $\P=\{f^{-1}(n)\colon n<\omega\}$. For a cardinal $\kappa>0$ and a partition $\P$ of $S\su V$ we say that {\em $\P$ is $\kappa$ sum free} if for every $a\in V$ the equation $x+y=a$ has less than $\kappa$ many solutions with $x$ and $y$ from the same element of the partition $\P$, i.e., such that $f(x)=f(y)$. We consider the solutions $\la x,y\ra$ and $\la y,x\ra$ identical and ignore the solution $\la x,y\ra=\la a/2,a/2\ra$. We say that a set $S$ is $\kappa$ sum free if $\P=\{S\}$ is $\kappa$ sum free. In particular, if a partition $\P$ of $S\su V$ is $\kappa$ sum free then $\P$ {\em partitions $S$ into $\kappa$ sum free sets}. Thus, a partition $\P=\{P_n\su S\colon n<\omega\}$ of a set $S\su V$ is $\kappa$ sum free if \[ (\forall a\in V) \left|\bigcup_{n<\omega}\{x,y\}\in[P_n]^2\colon x+y=a\}\right|<\kappa \] while $\P$ partitions $S$ into $\kappa$ free sets if \[ (\forall a\in V)(\forall n<\omega) \left|\{x,y\}\in[P_n]^2\colon x+y=a\}\right|<\kappa. \] Similarly, we say that a partition $\P$ of $S$ {\em is $\kappa$ difference free} if for every $a\in V$, $a\neq 0$, the equation $x-y=a$ has less than $\kappa$ many solutions $\la x,y\ra$, with $x$ and $y$ from the same element of the partition $\P$. A set $S$ is $\kappa$ difference free if $\P=\{S\}$ is $\kappa$ difference free. These notions lead in a natural way to the the following cardinal invariants, in which $\P$ is a countable partition. \begin{description} \item{} $\hat{\sigma}(\kappa)=\min\{|V|\colon \text{there is no $\kappa$ sum free partition $\P$ of $V$}\}$. \item{} $\sigma(\kappa)=\min\{|V|\colon \text{there is no partition $\P$ of $V$ into $\kappa$ sum free sets}\}$. \item{} $\hat{\delta}(\kappa)=\min\{|V|\colon \text{there is no $\kappa$ difference free partition $\P$ of $V$}\}$. \item{} $\delta(\kappa)=\min\{|V|\colon \text{there is no partition $\P$ of $V$ into $\kappa$ difference free sets}\}$. \end{description} Note that the above minima are taken over non-empty sets by (\ref{eqPr1}) and the facts that \begin{description} \item{(a)} if $\lambda\longrightarrow(\kappa+1)^2_\omega$ then $\sigma(\kappa)\leq\lambda$; \item{(b)} if $\binom{\lambda}{\lambda}\longrightarrow\binom{\kappa}{2}^{1,1}_\omega$ then $\delta(\kappa)\leq\lambda$. \end{description} (See \cite{EHMR} for the definitions and basic facts concerning the above partition relations.) The proofs of these implications are similar to the proofs of Theorems~\ref{VSetsPartSumOmegaBound} and \ref{VSetsPartDifOmegaBound}, respectively. Clearly, for every cardinal numbers $\lambda<\kappa$, \begin{equation}\label{eqPr1} \hat{\sigma}(\kappa)\leq\sigma(\kappa)\ \&\ \hat{\delta}(\kappa)\leq\delta(\kappa) \end{equation} and \begin{equation}\label{eqPr2} \hat{\sigma}(\lambda)\leq\hat\sigma(\kappa)\ \&\ {\sigma}(\lambda)\leq\sigma(\kappa)\ \&\ \hat{\delta}(\lambda)\leq\hat{\delta}(\kappa)\ \&\ {\delta}(\lambda)\leq{\delta}(\kappa). \end{equation} Note also that if $\kappa\geq\cf(\kappa)>\omega$ then $\hat{\sigma}(\kappa)=\sigma(\kappa)$ and $\hat{\delta}(\kappa)=\delta(\kappa)$. In our studies we will concentrate on these cardinals in the cases when $2\leq\kappa\leq\omega$. \section{$\!\!\!\!\!\!\!${\bf.} $\hat{\sigma}(\omega)=\sigma(\omega)=\left(2^\omega\right)^+$ and $\hat{\delta}(\omega)=\delta(\omega)=\omega_2$. } The equation $\sigma(\omega)=\left(2^\omega\right)^+$ has been proved by Komj\'{a}th in \cite[Thm 2]{Kom1} and the inequality $\hat{\sigma}(\omega)\geq\left(2^\omega\right)^+$ by Ciesielski and Larson in \cite[Thm 1.1]{KCLL}. More precisely, the equation $\hat{\sigma}(\omega)=\sigma(\omega)=\left(2^\omega\right)^+$ follows from the inequalities $\left(2^\omega\right)^+\leq \hat{\sigma}(\omega)\leq\sigma(\omega)\leq\left(2^\omega\right)^+$. The inequalities $\hat{\sigma}(\omega)\leq\sigma(\omega)$, $\left(2^\omega\right)^+\leq\hat{\sigma}(\omega)$ and $\sigma(\omega)\leq\left(2^\omega\right)^+$ follow from (\ref{eqPr1}) and the next two theorems, respectively. \thm{VPartSumOmega}{ {\rm (Ciesielski, Larson \cite[Thm 1.1]{KCLL})} If $|V|\leq 2^\omega$ then there is a countable $\omega$ sum free partition of $V$. \qed} \thm{VSetsPartSumOmegaBound}{ {\rm (Komj\'{a}th \cite[Thm 2(b)]{Kom1})} If $|V|> 2^\omega$ then $V$ is not a countable union of $\omega_1$ sum free sets. \qed} Next we will turn our attention to the equation $\hat{\delta}(\omega)=\delta(\omega)=\omega_2$. Once again, by (\ref{eqPr1}), it is enough to prove only two inequalities: $\hat{\delta}(\omega)\geq\omega_2$ and $\delta(\omega)\leq\omega_2$. They are proved in the next two theorems. Notice that the equation $\delta(\omega)=\omega_2$ has been proved by Komj\'{a}th in \cite[Thm 1]{Kom1}. \thm{VPartDifOmega}{ If $|V|\leq\omega_1$ then there is a countable $\omega$ difference free partition of $V$. } \proof Represent space $V$ as a union of continuous increasing sequence $\{V_\alpha\colon \alpha<\omega_1\}$ of countable subspaces. In particular, $V_\lambda=\bigcup_{\alpha<\lambda}V_\alpha$ for every limit ordinal $\lambda<\omega_1$. For convenience we will also assume that $V_0=\emptyset$. Thus, $\{V_{\alpha+1}\setminus V_\alpha\colon\alpha<\omega_1\}$ is a partition of $V$ into countable sets. For $\alpha<\omega_1$ let $\{p^\alpha_n\colon n<\omega\}$ be an enumeration of $V_{\alpha+1}\setminus V_\alpha$. A coloring function $f\colon V\to\omega$ generating the desired partition is constructed by defining, by induction on $\alpha<\omega_1$, its one-to-one restrictions $f|(V_{\alpha+1}\setminus V_\alpha)\colon V_{\alpha+1}\setminus V_\alpha\to\omega$ such that the following inductive condition holds \[ f(p^\alpha_n)\in\omega\setminus \{f(p)\colon p\in V_\alpha\ \&\ p = p^\alpha_n \pm p^\alpha_j\ \text{ for some }\ j\leq n\}. \] %We will show that the partition generated by $f$ is $\omega$ difference free. To show that the partition generated by $f$ is $\omega$ difference free choose an arbitrary $a=p^\alpha_n\neq 0$ and consider the pairs $\la x,y\ra$ satisfying $x-y=a$ and such that $f(x)=f(y)$. It is enough to show that $\{x,y\}\cap\{p^\alpha_j\colon j\leq n\}\neq\emptyset$. Let $x=p^\beta_m$ and $y=p^\gamma_k$. Then, $p^\beta_m - p^\gamma_k = p^\alpha_n$. Notice that $\delta=\max\{\alpha,\beta,\gamma\}$ must be equal to at least two of $\alpha$, $\beta$ and $\gamma$ since otherwise the number $p$ associated with the index $\delta$ would belong to $V_\delta$. Moreover, $\beta\neq\gamma$, since otherwise $f(p^\beta_m)=f(x)=f(y)=f(p^\beta_k)$, contradicting the fact that $f$ is one-to-one on $V_{\alpha+1}\setminus V_\alpha$. We are left with two cases. If $\alpha=\beta>\gamma$ then $p^\alpha_m - p^\alpha_n=x-a=y=p^\gamma_k\in V_\alpha$. So, $f(p^\alpha_m)=f(x)=f(y)=f(p^\alpha_m - p^\alpha_n)$ implies that $m\leq n$ and $y=p^\alpha_m\in\{p^\alpha_j\colon j\leq n\}$. If $\alpha=\gamma>\beta$ then $p^\alpha_k + p^\alpha_n=y+a=x=p^\beta_m\in V_\alpha$. So, $f(p^\alpha_k)=f(y)=f(x)=f(p^\alpha_k + p^\alpha_n)$ implies that $k\leq n$ and $x=p^\alpha_k\in\{p^\alpha_j\colon j\leq n\}$. \qed \thm{VSetsPartDifOmegaBound}{ If $|V|=\kappa\geq\omega_2$ and $\cf(\kappa)>\omega_1$ then $V$ is not a countable union of $\kappa$ difference free sets. } Proof. For $\kappa=\omega_2$ it has been proved by Komj\'{a}th in \cite[Thm 1(b)]{Kom1}. The proof of the general case is essentially identical and follows from the following partition theorem $\binom{\kappa}{\omega_1}\longrightarrow\binom{\kappa}{2}^{1,1}_\omega$ of Erd\H{o}s and Hajnal~\cite[p. 129]{Erd1}: %\begin{quote} if $f\colon\kappa\times\omega_1\to\omega$ then there are $\eta<\xi<\omega_1$ and $K\in[\kappa]^\kappa$ such that $f(\alpha,\eta)=f(\beta,\xi)$ for every $\alpha,\beta\in K$. \qed %\end{quote} \bigskip It is interesting how important is the assumption $\cf(\kappa)>\omega_1$ in the last theorem. It certainly cannot be completely removed, since for $|V|=\kappa$ with $\cf(\kappa)=\omega$ the space $V$ is a countable union of $\kappa$ difference free sets as $V$ can be partitioned into countably many sets each of size $<\kappa$. \pr{prob1}{ Let $|V|=\kappa>\cf(\kappa)=\omega_1$. Does it imply that $V$ is not a countable union of $\kappa$ difference free sets, or at least that there is no $\kappa$ difference free partition of $V$? } \pr{prob2}{ Let $|V|=\kappa>\cf(\kappa)=\omega$. Does it imply that there is no $\kappa$ difference free partition of $V$? } \section{$\!\!\!\!\!\!\!${\bf.} $\delta(n)=\omega_2$ and $\hat{\delta}(n)=\omega_1$ for $2\leq n<\omega$. } To see that $\delta(n)=\omega_2$ notice that the inequality $\delta(n)\leq\delta(\omega)\leq\omega_2$ follows from condition (\ref{eqPr2}) and Theorem \ref{VSetsPartDifOmegaBound}. The inequality $\delta(n)\geq\omega_2$ follows immediately from the following theorem of Erd\H{o}s and Kakutani \cite{Erd1}. (See also \cite[Thm 1(a)]{Kom1}.) \thm{VSetstDif2}{ If $|V|\leq\omega_1$ then $V$ is a union of countable many bases. \qed} To see that $\hat{\delta}(n)=\omega_1$ notice first that the inequality $\hat{\delta}(n)\geq\omega_1$ is obvious, since any countable $V$ can be partitioned into singletons, and such a partition is clearly $1$ difference free. The inequality $\hat{\delta}(n)\leq\omega_1$ follows from the next theorem. \thm{VPartDifFinBound}{ If $|V|\geq\omega_1$ then there is no $k$ difference free partition of $V$ for any $k<\omega$. } Proof. Let $f\colon V\to\omega$ be a coloring generating partition $\P$ . We will show that $\P$ is not $k$ difference free for any $k<\omega$. Take a linear base $H$ of $V$ over $\rationals$ and choose disjoint sets $A_0\in[H]^{\omega_1}$ and $B\in[H]^\omega$. Let $B=\{b_1,b_2,\ldots\}$. Define a sequence $\la A_n\in[A_0]^{\omega_1}\colon 00$ \[ f(a+b_n)=f(a'+b_n)\ \text{ for all }\ a,a'\in A_n, \] and that $A_{n+1}\su A_n$ for all $n<\omega$. A set $A_{n+1}$ can be chosen as one of the sets $\{a\in A_n\colon f(a+b_n)=i\}$ for $i<\omega$. Now, for $k<\omega$ pick different $a,a'\in A_k$. Then, $f(a+b_n)=f(a'+b_n)$ and $(a+b_n)-(a'+b_n)=a-a'$ for every $n\leq k$. So, the equation $x-y=a-a'$ has at least $k$ different solutions with $x$ and $y$ from the same element of the partition. \qed %\newpage \section{$\!\!\!\!\!\!\!${\bf.} $\omega_2\leq\hat{\sigma}(m)\leq \sigma(n)= \min\left\{\omega_{k+2},\left(2^\omega\right)^+\right\}$ \newline for $2^k< n \leq 2^{k+1}\leq m<2^{k+2}$ and $k<\omega$. }\label{sec:FinSum} The equation $\sigma(n)= \min\left\{\omega_{k+2},\left(2^\omega\right)^+\right\}$ will be proved by showing that for every $k<\omega$ the following inequalities hold: \[ \min\left\{\omega_{k+2},\left(2^\omega\right)^+\right\} \leq\sigma(2^k+1)\leq\sigma(2^{k+1})\leq \min\left\{\omega_{k+2},\left(2^\omega\right)^+\right\}. \] %and \[ \min\left\{\omega_k,\left(2^\omega\right)^+\right\} %\leq\hat{\sigma}(2^{k-1})\leq\hat{\sigma}(2^k-1)\leq %\min\left\{\omega_k,\left(2^\omega\right)^+\right\}. \] The inequalities \[ \sigma(2^k+1)\leq\sigma(2^{k+1}) \leq\sigma(\omega)\leq\left(2^\omega\right)^+ \] are the consequences of (\ref{eqPr2}) and Theorem~\ref{VSetsPartSumOmegaBound}. The two remaining inequalities: $\sigma(2^{k+1})\leq\omega_{k+2}$ and $\sigma(2^k+1)\geq\min\left\{\omega_{k+2},\left(2^\omega\right)^+\right\}$ follow respectively from the two following theorems. \thm{KomSh1}{ If $|V|\geq\omega_{k+2}$ for $k<\omega$ then there is no partition $\P$ of $V$ into $2^{k+1}$ sum free sets. } \proof The argument is included implicitly in the proof of \cite[Thm 5]{KomSh}. \qed \thm{KomSh2}{ If $|V|\leq\min\left\{\omega_{k+1},2^\omega\right\}$ for $k<\omega$ then there is a countable partition $\P$ of $V$ into $(2^k+1)$ sum free sets. } \proof %(1) for $k=0$ is proved by Komj\'{a}th and Shelah in \cite[Thm 3]{KomSh}. For $k=0$ it follows immediately from Theorem \ref{VSetstDif2}. The proof of general case, presented below, is essentially due to Baumgartner. (Private communication.) Let $|V|=\min\left\{\omega_{k+1},2^\omega\right\}$. Using induction on $k<\omega$, if necessary, we can assume that $|V|=\omega_{k+1}\leq 2^\omega$. We will construct a coloring $f\colon V\to R$ into a countable set $R$ which will generate the right partition. So, let $H$ be a linear base of $V$ over $\rationals$. Thus, for every $v\in V$ there exists the unique mapping $h \longmapsto q^v_h$ from a finite set $H_v\subset H$ into $\rationals\setminus\{0\}$ such that $v=\sum_{h\in H_v} q^v_h h$. Now, let $e\colon H\to \{0,1\}^\omega$ be a one-to-one mapping and for every $S\subset H$ choose a bijection $w_S\colon S\to |S|$. Thus, bijection $w_S$ establishes a well ordering $\leq_S$ of $S$ in order type $|S|$ by $h_1\leq_S h_2$ if and only if $w_S(h_1)\leq w_S(h_2)$. Moreover, choose $l_v<\omega$ such that $e(h_1)|_{l_v}\neq e(h_2)|_{l_v}$ for every different $h_1,h_2\in H_v$. We define $f(v)$ as a sequence $\la s^v_i\colon i<|H_v|\ra$ by induction on $i<|H_v|$ as follows. Let $h^v_0$ be the $\leq_H$-maximal element of $H_v$ and put $s^v_0=\la e(h^v_0)|_{l_v},q^v_{h^v_0},0\ra$. Moreover, let $S^v_0=\{h\in H\colon h<_H h^v_0\}$. Thus, $|S^v_0|\leq\omega_k$. Now, if $i+1<|H_v|$ is such that $s^v_i$ and $S^v_i$ are already defined, we define $s^v_{i+1}$ and $S^v_{i+1}$ as follows. Let $h^v_{i+1}$ be the $\leq_{S^v_i}$-maximal element of $H_v\setminus\{h^v_j\colon j\leq i\}$. If $|S^v_i|\leq\omega$ we put $s^v_{i+1}=\la e(h^v_{i+1})|_{l_v},q^v_{h_{i+1}},w_{S^v_i}(h^v_{i+1})\ra$ and $S^v_{i+1}=S^v_i$. If $|S^v_i|>\omega$ we put $s^v_{i+1}=\la e(h^v_{i+1})|_{l_v},q^v_{h^v_{i+1}},0\ra$ and $S^v_{i+1}=\{h\in S^v_i\colon h<_{S^v_i} h^v_{i+1}\}$. Thus, the range $R$ of $f$ is a subset of a countable set $\{0,1\}^{<\omega}\times\rationals\times\omega$. It is enough to show that $f$ has the desired properties. So, fix $a\in V$ and let $x,y\in V$ be different such that $x+y=a$ and $f(x)=f(y)$, i.e., $\la s^x_i\colon i<|H_x|\ra=\la s^y_i\colon i<|H_y|\ra =\la s_i\colon ik+1$. It is easy to see by our construction that $|S^x_i|>|S^x_{i+1}|$ provided $|S^x_i|>\omega$. This easily implies that $|S^x_k|\leq\omega$ and $S^x_i=S^y_i$ for every $i