% 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 0<n<\omega\ra$ 
such that for all $n>0$
\[
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 i<n\ra$ for some $\sigma=\la s_i\colon i<n\ra\in R$.
First notice that 
\[
H_x\cup H_y= H_a.
\]
The inclusion $H_a\subset H_x\cup H_y$ is obvious, since
$\sum_{h\in H_a} q^a_h h= \sum_{h\in H_x} q^x_h h + \sum_{h\in H_y} q^y_h h$.
To see the other inclusion let $h\in H_x\cup H_y$. If 
$h\not\in H_x\cap H_y$, then clearly $h\in H_a$. So, assume that 
$h\in H_x\cap H_y$. Then, $h=h^x_i=h^y_j$ for some $i,j<n$ and
$e(h^x_i)|_{l_x}=e(h^y_j)|_{l_y}=e(h^x_j)|_{l_x}$.
Hence, $j=i$ by the choice of $l_x$. But then, 
$q^x_{h^x_i} h^x_i + q^y_{h^y_j} h^y_j= 2 q^x_{h^x_i} h$, i.e., $h\in H_a$,
as $2 q^x_{h^x_i}\neq 0$. 

Next notice that 
\begin{equation}\label{eqBaum1}
\text{if } h^x_i=h^y_i \text{ for } i\leq k \text{ then } x=y.
\end{equation}
To see it, it is enough to show that if
$h^x_i=h^y_i$ for $i\leq k$ then $h^x_i=h^y_i$ for all $i<n$.
If $n\leq k+1$ then there is nothing to prove.
So, assume that $n>k+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<n$. So, 
\[
w_{S^x_k}(h^x_{k+1})=w_{S^y_k}(h^y_{k+1})=
w_{S^x_k}(h^y_{k+1})
\]
and, since $w_{S^x_k}$ is one-to-one, $h^x_{k+1}=h^y_{k+1}$.
Continuing this by induction, we obtain $h^x_i=h^y_i$
for every $i<n$. This finishes the proof of (\ref{eqBaum1}).

Now, for fixed  
$\sigma=\la s_i\colon i<n\ra=
\la \la e_i,q_i,m_i\ra\in\{0,1\}^l\times\rationals\times\omega\colon i<n\ra$
and for every $i<n$ there are at most two
$h\in H_a$ such that $e(h)|_l= e_i$, one from each $H_x$ and $H_y$.
Thus, for $x+y=a$ and $f(x)=f(y)=\sigma$ 
each $h^x_i$ can be chosen in at most two ways. So, 
we have at most $2^{k+1}$ possible sequences $\la h^x_i\colon i\leq k\ra$.
Since, by (\ref{eqBaum1}), each such sequence determines $x$, we have 
at most $2^{k+1}$ numbers $x$ satisfying the equation.
So, the number of different pairs cannot exceed $2^k$.
This finishes the proof. \qed

\bigskip

To argue for the inequalities
$\omega_2\leq\hat{\sigma}(m)\leq
\min\left\{\omega_{k+2},\left(2^\omega\right)^+\right\}$ 
for $2^{k+1}\leq m<2^{k+2}$ and $k<\omega$
notice first that 
$\hat{\sigma}(m)\leq\hat{\sigma}(\omega)\leq
\left(2^\omega\right)^+$ 
follows from (\ref{eqPr1}) and Theorem \ref{VSetsPartSumOmegaBound}.
The inequalities
$\hat{\sigma}(m)\geq\omega_2$ and 
$\hat{\sigma}(m)\leq\omega_{k+2}$ 
follow from the next two theorems, respectively.

\thm{KomSh3}{ {\rm (Komj\'{a}th and Shelah in \cite[Thm 5]{KomSh})}
If $|V|\geq\omega_{k+2}$ for $k<\omega$ then 
there is no $\left(2^{k+2}-1\right)$ sum free
partition $\P$ of $V$. \qed
}


\thm{KomSh4}{ {\rm (Komj\'{a}th and Shelah in \cite[Thm 3]{KomSh})}
If $|V|\leq\omega_1$ then 
there is $2$ sum free partition $\P$ of $V$. \qed }

The proof of Theorem~\ref{KomSh4} can be also
easily obtained by a slight modification of the proof
of Theorem~\ref{KomSh2}.

The above inequalities gives us, in particular, the following equations.

\cor{cor:KomSh3}{ $\hat{\sigma}(2)=\hat{\sigma}(3)=\omega_2$. \qed }

\pr{problem1}{ Find the exact values of 
$\hat{\sigma}(n)$ for $3<n<\omega$.}

Note that it is consistent with ZFC
that $\hat{\sigma}(2^{k+1})=\omega_{k+2}=\left(2^\omega\right)^+$ 
for every $k<\omega$. It can be deduced from 
the next theorem in the same way as \cite[Thm~5]{KomSh}
was concluded
from \cite[Thm~4]{KomSh}.

\thm{KomSh333}{ {\rm (Komj\'{a}th and Shelah in \cite[Thm 1]{KomSh2})}
For $1\leq n<\omega$ it is 
consistent that $2^\omega=\omega_n$ and there is a 
function $F:[\omega_n]^{<\omega}\to \omega$ such that 
for every $A\in [\omega_n]^{<\omega}$ there are at most 
$2^n-1$ solutions of $A=H_0\cup H_1$ with $H_0\neq H_1$, 
$F(H_0)=F(H_1)$.
\qed
}



\section{$\!\!\!\!\!\!\!${\bf.} 
Sum and difference free partitions of subsets of $V$.}

This section is motivated by the following theorems
that deal with partitioning subsets of $V$ into
sum or difference free sets. We will try to 
examined their analogs for sum or difference free partitions.

\thm{th:SsumErd}{ {\rm (Erd\H{o}s \cite{Erd2})}
If $|V|\geq\omega_2$
then there exists $3$ sum free set
$S\in[V]^{\omega_2}$ which does not
admit a countable partition into
$2$ sum free sets. \qed }

\thm{th:SdiffKom1}{ {\rm (Komj\'{a}th \cite[Thms 3 and 4]{Kom1})}
\begin{description}
\item[(1)] If $S\in[V]^{\leq\omega_2}$ is
$\omega_2$ difference free then $S$ can be partitioned into 
countable many $2$ difference free sets.

\item[(2)] If $|V|\geq (2^\continuum)^+$ then there is 
$3$ difference free set $S\su V$ which cannot be partitioned into 
countable many $2$ difference free sets. \qed 
\end{description}
}

\thm{th:SdiffKom3}{ {\rm (Komj\'{a}th \cite[Thm 6]{Kom1})}
If $S\subset V$ is
$\omega_2$ difference free then $S$ can be partitioned into 
countable many $\omega$ difference free 
and $\omega$ sum free sets. \qed }

Theorem \ref{th:SsumErd} has the following corollary.

\cor{cor:SsumErd}{ The following conditions are equivalent.
\begin{description}
\item[(i)]   $|V|\geq\omega_2$.
\item[(ii)]  There exists $3$ sum free set $S\su V$ which does not 
             admit a countable partition into $2$ sum free sets. 
\item[(iii)] There exists $3$ sum free set $S\su V$ which does not 
             admit a countable $2$ sum free partition.
\item[(iv)]  $V$ does not admit a countable $2$ sum free partition.
\end{description}
}

\proof Implication (i)$\Impl$(ii) follows from Theorem \ref{th:SsumErd}.
(ii)$\Impl$(iii) and (iii)$\Impl$(iv) are obvious. 
Implication (iv)$\Impl$(i) follows from
Theorem \ref{KomSh4}. \qed

\bigskip

Since $\sigma(2)=\hat{\sigma}(2)=\omega_2$ 
Corollary~\ref{cor:SsumErd} suggests the following conjecture. 


\conj{con:SsumErd}{ Let $1<\kappa<\lambda$ be cardinal numbers.
\begin{description}
\item[(a)]   $|V|\geq\sigma(\kappa)$ if and only if 
             there exists $\lambda$ sum free set $S\su V$ which does not 
             admit a countable partition into $\kappa$ sum free sets. 
\item[(b)]   $|V|\geq\hat\sigma(\kappa)$ if and only if 
             there exists $\lambda$ sum free set $S\su V$ which does not 
             admit a countable $\kappa$ sum free partition. 
\end{description}
}

Notice that the implications from the right to the left are obvious.
The following part of the conjecture follows from the results of 
Section \ref{sec:FinSum}.

\thm{th:conj}{ For $k<\omega$ such that $2^\omega\geq\omega_{k+1}$ 
the following conditions are
equivalent:
\begin{description}
\item[(i)]   $|V|\geq\sigma(2^{k+1})=\omega_{k+2}$; 
\item[(ii)]  there exists 
             $\left(2^{k+1}+1\right)$ sum free set $S\su V$ which does not 
             admit a countable $2^{k+1}$ sum free partition. 
\end{description}
}

\proof Implication (ii)$\Impl$(i) follows by contra position from
Theorem~\ref{KomSh2}. 

To see (i)$\Impl$(ii) take a subspace $V_0$ of $V$ of cardinality 
$\omega_{k+2}$. Then, by Theorem \ref{KomSh2}, there exists 
a countable partition of $V_0$ into 
$\left(2^{k+1}+1\right)$ sum free sets. 
At least one of these sets must satisfy (ii) by 
Theorem \ref{KomSh1}.
\qed


\bigskip

The difference free analog of Corollary \ref{cor:SsumErd}
related to Theorem \ref{th:SdiffKom1}
reads as follows. 

\thm{th:SdiffPart}{ The following conditions are equivalent.
\begin{description}
\item[(i)]   $|V|\geq\omega_1$.
\item[(ii)]  There exists $3$ difference free set $S\su V$ which 
             does not admit a countable $2$ difference free partition.
\end{description}
}

\proof Implication (ii)$\Impl$(i) is obvious, since every
countable set can be partitioned into singletons.

To see the other implication, let $\{s,t\}\cup X$ be a linearly 
independent subset of $V$ of cardinality $\omega_1$ such that 
$s,t\not\in X$ and $s\neq t$. Define
\[
S=\{s-x\colon x\in X\}\cup\{x-t\colon x\in X\}.
\]

To see that $S$ is $3$ difference free take $a\neq 0$. 
Consider all possible solutions of $x-y=a$ with $x,y\in S$.
They must be in either of the form:
\begin{description}
\item{(1)}   $a=(s-x_1)-(y_1-t)=      -x_1-y_1+s+t$ for some $x_1,y_1\in X$;
\item{(2)}   $a=(y_2-t)-(s-x_2)=\ \ \, x_2+y_2-s-t$ for some $x_2,y_2\in X$;
\item{(3)}   $a=(s-x_3)-(s-y_3)=      -x_3+y_3    $ for some $x_3,y_3\in X$;
\item{(4)}   $a=(x_4-t)-(y_4-t)=\ \ \,\, x_4-y_4  $ for some $x_4,y_4\in X$.
\end{description}
By linear independence of $\{s,t\}\cup X$ 
if vector $a$ can be represented in form (1) or (2)
than it cannot be represented in any other form. Moreover, 
such $a$ can be obtained in at most two ways: 
by exchanging $x_i$ with $y_i$.
If $a$ is in the form (3) or (4) that its representation is unique
in each form. Thus, such $a$ can be represented in at most two ways:
one in form of (3) and one in form of (4). So, $S$ is 
$3$ difference free.

To see that there is no countable $3$ difference free partition of $S$ 
let $f\colon S\to\omega$. Define $F\colon X\to\omega\times\omega$
by $F(x)=\la f(s-x),f(x-t)\ra$ and let $X_0$ be an uncountable 
subset of $X$ on which $F$ is constant. Thus, for different $a,b\in X_0$
we have $f(s-a)=f(s-b)$ and $f(a-t)=f(b-t)$. However, 
\[
(a-t)-(b-t)=a-b=(s-b)-(s-a).
\]
Therefore equation $x-y=a-b$ has two different solutions 
$\la a-t,b-t\ra$ and $\la s-b,s-a\ra$ that agree with $f$. \qed

\pr{prob:SetsDiffFree}{ Find the conditions analogous to 
Theorems \ref{th:SdiffKom1} and \ref{th:SdiffPart}
for $(n+1)$ difference free subsets of $V$ without 
$n$ difference free partition, or a partition into
$n$ difference free sets. }


\begin{thebibliography}{22}

\bibitem{KCLL}
Krzysztof Ciesielski and Lee Larson, Uniformly antisymmetric functions,
{\sl Real Analysis Exchange 19} (1993/94), 226--235.

\bibitem{Erd1}
P. Erd\H{o}s, Measure Theoretic, Combinatorial and Number Theoretic
Problems Concerning Point Sets in Euclidean Space,
{\sl Real Analysis Exchange 4} (1978/79), 113--138.

\bibitem{Erd2}
P. Erd\H{o}s, Some applications of Ramsey's 
theorem to additive number theory,
{\sl European J. Combin. 1} (1980), 43--46.

\bibitem{EHMR}
P. Erd\H os, A. Hajnal, A. M\'at\'e, and R. Rado, 
{\sl Combinatorial Set Theory: Partition Relations for Cardinals},
Studies in Logic {\bf 106}, North-Holland, 1984.


\bibitem{Kom1}
P\'eter Komj\'{a}th, Vector sets with no repeted differences,
{\sl Colloquium Mathematicum 64} (1993), 129--134.

\bibitem{KomSh}
P. Komj\'{a}th and S. Shelah, On uniformly antisymmetric functions,
{\sl Real Analysis Exchange 19} (1993/94), 218--225.

\bibitem{KomSh2}
P. Komj\'{a}th and S. Shelah, Coloring finite subsets of uncountable sets,
{\sl Proc. Amer. Math. Soc.}, to appear.
\end{thebibliography}

\end{document}




