%A revision, 30 March 2000
%Submission to INTEGERS, 10 November 1999
%LaTeX 2e,  16 pages

\documentclass[11pt]{article}

\usepackage{amssymb} %for Bbb

% Format
\textwidth= 6.25in
\textheight= 9.0in
\topmargin =10pt 
\evensidemargin=10pt
\oddsidemargin=10pt
\headsep=25pt
\parskip=10pt 
\font\smallit=cmti10
\font\smallrm=cmr9
\font\smalltt=cmtt10

% Sectioning
%The below commands produce section titles as in the current INTEGERS style;
%this solution is better because it supports automatic references to 
%section numbers.
\makeatletter
\def\section{\@startsection {section}{1}{\z@}{3.5ex plus1ex minus
    .2ex}{2.3ex plus.2ex}{\reset@font\normalsize\bf}}
\def\subsection{\@startsection{subsection}{2}{\z@}{3.25ex plus1ex
    minus.2ex}{1.5ex plus.2ex}{\reset@font\normalsize\bf}}
\def\postsection{. \mbox{}}
\def\postsubsection{\mbox{} \mbox{}}
\def\@seccntformat#1{\csname the#1\endcsname\csname post#1\endcsname}
\makeatother

% Theorem-like environments
%In the below environments I prefer type style sl
\newtheorem{thm}{Theorem}[section]
\newtheorem{lem}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newenvironment{theorem}{\begin{thm}\begin{slshape}}{\end{slshape}\end{thm}}
\newenvironment{lemma}{\begin{lem}\begin{slshape}}{\end{slshape}\end{lem}}
\newenvironment{proposition}{\begin{prop}\begin{slshape}}{\end{slshape}\end{prop}}
%
%In the below environments I prefer type style rm
%
\newtheorem{rem}[thm]{Remark}
\newenvironment{remark}{\begin{rem}\em}{\end{rem}}
\newtheorem{que}[thm]{Question}
\newenvironment{question}{\begin{que}\em}{\end{que}}

% Proofs
\newcommand{\qed}{$\;\;\;\Box$}
\newenvironment{proof}{\par\smallbreak{\sl Proof.~}}
{\unskip\nobreak\hfill \qed \par\medbreak}

% Abbreviations
\newcommand{\refeq}[1]{(\ref{#1})}
\newcommand{\bbb}[1]{\mathbb{#1}}
\newcommand{\bbbz}{ {\bbb Z} }
\newcommand{\bbbn}{ {\bbb N} }
\newcommand{\calP}{\mathcal{P}}
\newcommand{\setdef}[2]{\left\{ \hspace{0.5mm} #1 :
\hspace{0.5mm} #2 \right\}}
\newcommand{\function}[2]{:#1 \rightarrow #2}
\newcommand{\binomial}[2]{\left(                     %binomial coefficient
  \begin{array}{@{}c@{}} #1\\[-.5ex]#2 \end{array}   %better than \choose
  \right)}                                           %in displayed formulas
\newcommand{\of}[1]{\left( #1 \right)}
\newcommand{\gs}{\sigma}
\newcommand{\mod}[1]{\,(\bmod\, #1)}
\newcommand{\PP}[1]{ {\bbb P} \left[ #1 \right] }
\newcommand{\EE}[1]{ {\bbb E} \left[ #1 \right] }
\newcommand{\nonabel}{{non-abel}}



\begin{document} 

\begin{center}
{\bf 
%RAMSEYAN VARIATIONS ON SYMMETRIC SUBSEQUENCES
SYMMETRIC SUBSETS OF LATTICE PATHS 
}
\vskip 20pt
{\bf Oleg Verbitsky\footnote{On leave from the Department of 
Mechanics \& Mathematics, Lviv University, Ukraine.
Research supported in part by a Lise Meitner Fellowship of the Austrian
Science Foundation (FWF) and by grant INTAS-96-0753.}}\\
{\smallit Institute of Information Systems, Vienna University of Technology,
Favoritenstra\ss e 9, 1090 Wien, Austria}\\
{\tt oleg@dbai.tuwien.ac.at}
\end{center}
\vskip 30pt 
\centerline{\smallit Received: 11/10/99, Revised: 3/30/00, Accepted: 
4/13/00, Published: 5/19/00}
\vskip 30pt
\centerline{\bf Abstract}

\noindent
Let $[n]=\{0,1,\ldots,n\}.$ A subset $S$ of $[n]$ is symmetric if $S=g-S$ for a 
natural number $g$. We show that, for every $f\function{[n]}{[2n]}$ with the 
restriction $1 \le f(i+1)-f(i) \le 2$ for all $i < n$, there is some 
$S \subset [n]$ such that $|S| \ge 2\ln n - O(1)$, with the property that 
both $S$ and $f(S)$ are symmetric. We prove this result by finding a lower bound
for the length of a symmetric pattern whose abelian occurrences are encountered
in all binary words of length $n$. We also show that if $M$ is such that for 
every $f:[n] \rightarrow [2n]$ as above, there is at least one $S \subset [n]$
with $|S| \ge M$ and both $S$ and $f(S)$ symmetric, then $M \le (7+o(1))\sqrt n$. 
This result is based on the construction of appropriate Sidon $B_2$-sequences.
In another interpretation, our results can be formulated as lower and upper
bounds for $M$ such that every path of length $n$ along basis vectors of
a two-dimensional lattice contains an $M$-point centrally symmetric set.

\pagestyle{myheadings}
\markright{\smalltt INTEGERS:
\smallrm ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 0
(2000), \#A05 \hfil}

\thispagestyle{empty} 
\baselineskip=15pt 


\section{Introduction}

Let $[n]=\{0,1,2,\ldots,n\}$, with $0$ included for our convenience. 
We consider injective order-preserving
transformations $f\function{[n]}{[2n]}$ with restriction
$f(i+1)-f(i)\le 2$ for all $i<n$. We wonder to which extent
such transformations can violate the regular structure of $[n]$.
Namely, suppose that $\calP$ is a regularity property of a set of
integers, say, one of being an arithmetic progression. We then wish
to know the maximum $M=M(n)$ such that, for every $f$ as above,
at least one set $S\subseteq[n]$ with $|S|\ge M$ has property $\calP$
and its image $f(S)$ still has the same property.

In the case of arithmetic progressions,
it is easy to observe an equivalent reformulation of the question.
Let $V=\{v_0,\ldots,v_n\}$ be a sequence of points in the grid $\bbbz^2$
with each difference $v_{i+1}-v_i$ being either $a=(1,1)$ or $b=(1,2)$.
Now the question is what is the maximum $M$ such that every $V$
contains an $M$-term arithmetic progression of vectors.
To see the equivalence of the two problems, it suffices to view a set $V$
as the graph of a map $f$. Clearly, $f$ preserves an arithmetic
progression $S\subseteq[n]$ iff $\setdef{(x,f(x))}{x\in S}$ is an
arithmetic progression in $V$. Notice that the specification of differences
$a$ and $b$ is actually irrelevant --- those could be any other pair
of non-collinear vectors as well, say, $a=(1,0)$ and $b=(0,1)$.

As the choice of the initial point $v_0$ does not affect anything,
a set $V$ is characterized by the sequence of differences
$v_1-v_0,\ldots,v_n-v_{n-1}$, which can be regarded as a word $w(V)$ of
length $n$ over alphabet $\{a,b\}$. In this way we arrive at yet another
reformulation of the problem under consideration. We call an arbitrary
sequence of variables a {\em pattern}. 
An {\em abelian occurrence\/} of a pattern in a word is 
a subword obtainable from the pattern by substituting nonempty
words in place of variables so that words replacing the same
variable may differ only in order of letters (see 
Section \ref{s:prel} for more details).
It is not hard to observe a one-to-one correspondence between $(m+1)$-term
arithmetic progressions in $V$ and abelian occurrences
of the pattern $x^m$ in $w(V)$. Thus, the value of $M(n)$
is the maximum number $M$ such that every word of length $n$
over the binary alphabet has an abelian occurrence of $x^{M-1}$.

Dekking \cite{Dek} constructs
an infinite word in the binary alphabet without abelian occurrences
of $x^4$. It immediately follows \cite[theorem~6.13]{PSa} that
$M(n)\le 4$, i.e.\ 5-term arithmetic
progressions can all be destroyed by some
transformation $f$. 

This motivates an extension of property $\calP$.
A set $S\subseteq\bbbz^k$ such that $S=g-S$ for a lattice
point $g\in\bbbz^k$
is called {\em symmetric} (with respect to the center at rational
point $\frac12g$). 
From now on the property $\calP$ extended to being symmetric
will be our main concern.
Given $V\subseteq\bbbz^k$, let $MS(V)$ denote
the maximum cardinality of a symmetric subset of $V$.

A pattern is {\em symmetric\/} if it reads the same backward as forward, 
like $xyx$.
With notation introduced above, we again have a
one-to-one correspondence between sets $S\subseteq[n]$ whose
symmetry is preserved by $f$, symmetric subsets of the graph $V$
of $f$, and abelian occurrences of symmetric patterns in the word $w(V)$.
Correspondingly, we have the following equivalences whose proof
is given in more detail in Section~\ref{s:prel}.

\begin{lemma}\label{lem:equiv}
The statements below are equivalent.
\begin{enumerate}
\item
$M(n)=\min_{f\function{[n]}{[2n]}}\max_{S\subseteq[n]}
\setdef{|S|}{\mbox{both $S$ and $f(S)$ are symmetric}}$,
where the minimum is taken over all $f$
with 
\begin{equation}\label{eq:1f2}
1\le f(i+1)-f(i)\le 2\mathrm{\ \ for\ \ }i<n.
\end{equation}
\item
$M(n)$ is the minimum of $MS(V)$ over all
subsets $V=\{v_0,v_1,\ldots,v_n\}$ of $\bbbz^2$ with each $v_{i+1}-v_i$ 
equal to either $a$ or $b$, where $a$ and $b$ are arbitrarily fixed
non-collinear vectors.
\item
$M(n)$ is the maximum $M$ such that every word of length $n$
over the binary alphabet has abelian occurrence of a symmetric
pattern of length at least $M-1$.
\end{enumerate}
\end{lemma}

In contrast to the case of arithmetic progressions, 
$M(n)$ now grows with $n$, that is, no $f$ is able
to destroy symmetric subsets so well as  arithmetic progressions. 
To show this, consider an infinite sequence of symmetric patterns
\begin{equation}\label{eq:patterns}
\hspace{-3cm}
\begin{array}{ccl}
P_1 &=& x, \\
P_2 &=& xyx,\\
P_3 &=& xyxzxyx,\\
P_4 &=& xyxzxyxuxyxzxyx,\\
\vdots
\end{array}
\end{equation}
where $P_{i+1}$ is the result of inserting a new variable
between two copies of $P_i$. In combinatorics of words, members
of this sequence are called {\em sesquipowers\/} or {\em Zimin's patterns}.
Coudrain and Sch\"utzenberger \cite{CSc} proved that each $P_i$
must occur in all long enough words over a finite alphabet.
Here we mean literal rather than abelian occurrence, i.e.\ the same variable
is substituted everywhere by the same word.
The unavoidability of sesquipowers immediately implies that
$M(n)$ goes to the infinity with $n$ increasing. However, this argument
gives a very small lower bound for $M(n)$, actually, a kind of
the inverse tower function (see Lemma \ref{lem:tower}).

In Section \ref{s:lower} we prove a better lower bound 
$M(n)=\Omega(\ln n)$ 
based on estimation of how long symmetric 
pattern is represented by an abelian
occurrence in every binary word of length $n$.
Similarly to the $O$-notation, we write $\Omega(h(n))$ to 
refer to a function of $n$ that everywhere exceeds $c\cdot h(n)$ 
for a positive constant $c$.

In Section \ref{s:upper} we prove upper bound $M(n)=O(\sqrt n)$.
As the main technical tool we use $B_2$-sequences introduced
by Sidon and investigated by many authors (see \cite[section 4.1]{PSa}
for survey and references).
A set $X$ of integers is called a {\em $B_2$-sequence\/}
if for any integer $g$ the equation $x+y=g$ has at most one
solution in $X$ with $x\le y$. In other words, a $B_2$-sequence $X$ is 
a highly asymmetric set characterized by $MS(X)\le2$.
There are several constructions \cite{Sin,Bos,ETu,Erd,Cho,BCh,Kru} 
of dense $B_2$-sequences in $[n]$.
We employ a fairly simple and explicit construction of \cite{Kru},
making use of an additional uniformity property of it.

We conclude the paper with discussion of open problems in 
Section \ref{s:higher}.


\paragraph{Related work.}
The van der Waerden theorem can be restated so that every infinite
subsequence $v_0,v_1,\ldots$ of $\bbbn$ with $v_{i+1}-v_i=O(1)$ 
contains arbitrarily long arithmetic progressions (see \cite{Bro}). 
As Dekking's result shows, a similar statement in $\bbbz^2$ is
false. However, Ramsey and Gerver \cite{RGe} prove that every
infinite sequence $v_0,v_1,\ldots$ in $\bbbz^2$ with bounded
distances $||v_{i+1}-v_{i}||$ between any two successive points 
contains arbitrarily
large subsets of collinear points. Pomerance \cite{Pom} shows
this holds true even under the weaker assumption that
\begin{equation}\label{eq:dens}
\liminf_{n\to\infty}\frac1n\sum_{i=1}^n||v_{i+1}-v_i||<\infty.
\end{equation}
These results can be viewed as two-dimensional
analogs of the van der Waerden theorem and its density version of Szemer\'edi,
with collinear subsets instead of arithmetic progressions. 
In this respect our result on behavior of $M(n)$, in view of item 2
of Lemma \ref{lem:equiv}, can serve as yet another two-dimensional analog of
van der Waerden's theorem, with arithmetic progressions replaced by 
symmetric subsets.
The multi-dimensional analog of Szemer\'edi's theorem is also true
as shown by Banakh \cite{BKV}, who observed that condition \refeq{eq:dens}
guarantees the existence of arbitrarily long symmetric subsequences
in an infinite sequence $v_0,v_1,\ldots$ of points in $\bbbz^k$, $k\ge1$.
It should be noted that in the case of $k=2$ the latter result
strengthes the claim that $M(n)\to\infty$ but provides no satisfactory
lower bound for $M(n)$.

Banakh and Protasov \cite{Ban,BPr} prove that the minimal number of 
colors required for coloring the $n$-dimensional integer grid $\bbbz^n$
avoiding infinite symmetric monochromatic subsets is $n+1$.
Unavoidable symmetries in words are investigated by Fouch\'e~\cite{Fou}.


\section{Preliminaries}\label{s:prel}

In this section we prove Lemma \ref{lem:equiv} and then show that
$M(n)\to\infty$ as $n\to\infty$.
Recall that throughout the paper $MS(V)$ denotes the cardinality of the
largest symmetric subset of $V$.

The proof of the equivalence of statements 1 and 2 of Lemma \ref{lem:equiv}
in the case that
\begin{equation}\label{eq:ab}
a=(1,1),\quad b=(1,2)
\end{equation}
follows arguments outlined in the introduction for arithmetic
progressions. With a function $f$ we associate its graph
$V=\{v_0,\ldots,v_n\}$, where $v_i=(i,f(i))$.
The bounds \refeq{eq:1f2} imply that $v_{i+1}-v_i\in\{a,b\}$.
Vice versa, any set $V=\{v_0,\ldots,v_n\}$ in $\bbbz^2$ with
the latter condition can be viewed as the graph of a function $f$
of the prescribed kind. A set $S\subseteq[n]$ and its image $f(S)$
are both symmetric iff $S'=\setdef{(i,f(i))}{i\in S}$
is a symmetric subset of $V$. 
This completes the proof in the case \refeq{eq:ab}.

The case of arbitrary non-collinear $a$ and $b$ reduces to the 
case \refeq{eq:ab}. Really, consider two sets $V=\{v_0,\ldots,v_n\}$
and $V'=\{v'_0,\ldots,v'_n\}$ in $\bbbz^2$ with all
$v_{i+1}-v_i\in\{(1,1),(1,2)\}$ and $v'_{i+1}-v'_i\in\{a,b\}$, where
$a$ and $b$ are non-collinear. Let $\phi$ be the affine transformation
of $\bbbz^2$ into itself that takes $v_0$ to $v'_0$,
$(1,1)$ to $a$, and $(1,2)$ to $b$. Then $\phi$ establishes
a one-to-one correspondence between $V$ and $V'$ that matches
symmetric subsets in $V$ and symmetric subsets in $V'$.
It follows that $MS(V)=MS(V')$, thereby proving the equivalence
of statements 1 and 2.

Before proving the equivalence of statements 2 and 3, let us
recall the relevant notions of the formal language theory.
A {\em pattern\/} is a word over the alphabet of variables
$\{x_1,x_2,\ldots\}$. Pattern $x_{i_1}x_{i_2}\ldots x_{i_l}$
is {\em symmetric\/} if $i_j=i_{l+1-j}$ for all $j\le l$.
Let $A=\{a_1,\ldots,a_m\}$ be a finite alphabet. The number
of occurrences of letter $a_i$ in a word $w$ over $A$ is denoted by
$|w|_{a_i}$. A {\em commutative index\/} of $w$ is the tuple
$\langle|w|_{a_1},\ldots,|w|_{a_m}\rangle$.
A subword $u$ of a word $w$ is an {\em occurrence\/}
of a pattern $P=x_{i_1}\ldots x_{i_l}$ if $u$ can be obtained
from $P$ by substituting nonempty words in place of each variable,
where the same variable is everywhere replaced with the same word.
If the same variable may be replaced by (possibly distinct) words 
with the same commutative index, $u$ is called an 
{\em abelian occurrence\/} of $P$.

{\em Example.} In word $a_1a_1a_2a_1a_2a_1a_3$, subwords
$a_1a_1$, $a_1a_2a_1a_2$, and $a_2a_1a_2a_1$ are occurrences
of pattern $x_1x_1$. In addition, $a_1a_1a_2a_1a_2a_1$ is an abelian
occurrence of the same pattern.

Given a sequence of vectors $V=\{v_0,v_1,\ldots,v_n\}$ in
$\bbbz^k$ with all $v_i-v_{i-1}$ in a finite set 
$A\subset\bbbz^k$, we associate with $V$ the sequence $w(V)$
of differences $v_1-v_0,v_2-v_1,\ldots,v_k-v_{k-1}$ which will
be viewed as a word of length $n$ over alphabet $A$.

\begin{lemma}\label{lem:aux}
\mbox{}

\begin{enumerate}
\item
If $w(V)$ has an abelian occurrence of a symmetric pattern of
length $l$, then $MS(V)\ge l+1$.
\item
Conversely, suppose that $A$ is a linearly independent set
of vectors. Then $w(V)$ has an abelian occurrence of a symmetric
pattern of length at least $MS(V)-1$.
\end{enumerate}
\end{lemma}


\begin{proof}
1.
Recall that word $w(V)$ is a sequence of vectors $v_1-v_0,\ldots,v_n-v_{n-1}$.
Given a subword $u=v_{i+1}-v_i\ldots v_j-v_{j-1}$, $i<j$, we call $v_i$
the initial point and $v_j$ the terminal point of $u$. Let $u=u_1\ldots u_l$
be an abelian occurrence of a symmetric pattern $P$ of length $l$,
where $u_s$ is substituted in place of $s$-th variable of $P$.
Let $v_{i_{s-1}}$ and $v_{i_s}$ be the initial and terminal points
of $u_s$. Then the set $\{v_{i_0},\ldots,v_{i_l}\}$ is symmetric.
This can be shown by easy induction. Really, assume that 
$v_{i_1}$ and $v_{i_{l-1}}$ are symmetric with respect to the center
$\frac12g$, that is, $v_{i_1}+v_{i_{l-1}}=g$. 
As $u_1$ and $u_l$ differ only in order of their letters,
we have $v_{i_1}-v_{i_0}=v_{i_l}-v_{i_{l-1}}$. Consequently,
$v_{i_0}$ and $v_{i_l}$ are symmetric with respect to $\frac12g$ too.

2.
Let $l=MS(V)$ and $v_{i_0},\ldots,v_{i_l}$ be a symmetric subsequence
of $V$. Denote a subword of $w(V)$ whose initial and terminal points
are $v_{i_{s-1}}$ and $v_{i_s}$ by $u_s$. Then $u=u_i\ldots u_l$
is an abelian occurrence of a symmetric pattern of length $l$.
It suffices to show that commutative indices of words $u_s$ and
$u_{l+1-s}$ are the same. Those are uniquely determined by
expansions of vectors $v_{i_s}-v_{i_{s-1}}$ and $v_{i_{l+1-s}}-v_{i_{l-s}}$ 
in basis $A$. It remains to notice that the last two vectors are
equal by symmetricalness of $\{v_{i_0},\ldots,v_{i_l}\}$.
\end{proof}

The equivalence of statements 2 and 3 of Lemma \ref{lem:equiv} now
follows directly from Lemma \ref{lem:aux}. The proof of Lemma \ref{lem:equiv}
is complete.

\begin{proposition}\label{prop:toinf}
$M(n)\to\infty$ as $n\to\infty$.
\end{proposition}

At this point we prefer the statement 3 of Lemma \ref{lem:equiv}.
Let $L^{\nonabel}(n)$ be the maximal $l$ such that 
every word of length $n$ over the binary alphabet has an
occurrence of a symmetric
pattern of length at least $l$. As $M(n)>L^{\nonabel}(n)$, 
it suffices to show that
$L^{\nonabel}(n)\to\infty$ for $n\to\infty$. The latter follows from
a result of Coudrain and Sch\"utzenberger \cite{CSc} which we state
below in a form convenient for our purposes.

\begin{lemma}\textbf{\textrm{(\cite{CSc})}}\label{lem:tower}
If $L^{\nonabel}(n)\ge l$, then $L^{\nonabel}((n+1)(2^n+1))\ge 2l+1$.
\end{lemma}

\begin{proof}
Assume that every binary word of length $n$ has occurrence of a symmetric
pattern $P$ of length $l$. Any binary word of length $(n+1)(2^n+1)$
contains two identical subwords of length $n$ separated by a nonempty word.
Thus, there is an occurrence of the symmetric pattern $PxP$, where $x$
is a new variable absent in $P$.
\end{proof}

Notice that the above argument ensures that each pattern $P_i$
of the sequence \refeq{eq:patterns} occurs in any long enough binary word.



\section{Lower Bound}\label{s:lower}

The proof of Proposition \ref{prop:toinf} based on Lemma \ref{lem:tower}
gives us an extremely small lower bound for $M(n)$ that is even smaller
than the inverse tower function. In this section we improve it to
$M(n)\ge 2\ln n-O(1)$. We first prove an auxiliary fact.
Notice that whenever below we refer to the number of subwords of
a word, we distinguish all occurrences of a subword, that is,
a subword is counted each time it occurs in the word.

\begin{lemma}\label{lem:xyx}
Given a word $w$, let $\nu(w)$ denote the number of pairs 
$\{u_1,u_2\}$, where $u_1$ and $u_2$ are disjoint subwords of $w$
with the same commutative index.
Let $N(n)$ be the minimum of $\nu(w)$ over all binary words $w$
of length $n$. Then
$$
N(n)\ge(\ln n-O(1))n^2/4.
$$  
\end{lemma}

\begin{proof}
Consider a binary word $w$ of length $n$ and estimate the value
$\nu(w)$ from below. Expand $\nu(w)$ to the sum $\sum_t\nu_t(w)$,
where the $t$-th term counts pairs of subwords with length $t$.
Let $\gs_t(i)$ denote the number of subwords of $w$ with length $t$
and commutative index $\langle i,t-i\rangle$. As the total number
of subwords of length $t$ is equal to $n+1-t$, notice the equality
$\gs_t(0)+\gs_t(1)+\ldots+\gs_t(t)=n+1-t$. 
As a subword of length $t$ can overlap with at most $2t-1$
subwords of the same length, we have
$$
\nu_t(w)\ge\frac12\sum_{i=0}^t\gs_t(i)(\gs_t(i)-(2t-1)).
$$
Taking into account that 
$$
\sum_{i=0}^t\gs_t(i)^2\ge(t+1)\of{\frac{\sum_{i=0}^t\gs_t(i)}{t+1}}^2,
$$
we conclude that
\begin{eqnarray*}
\nu_t(w)&\ge&\frac12\of{(t+1)\of{\frac{n+1-t}{t+1}}^2-(2t-1)(n+1-t)}\\
&=&\frac{(n+2)^2}{2(t+1)}-(t+\frac12)(n+1)+t^2-\frac12.
\end{eqnarray*}
Let us sum these inequalities over $t$ from $1$ to $s$,
dropping the last term $t^2-\frac12$ in the right hand side
(anyway it would give us no gain). Summing the first term
in the right hand side, we take into account that $\sum_{t=1}^s1/t-\ln s$
approaches Euler's constant as $s$ increases.
Therefore,
$$
\sum_{t=1}^s\nu_t(w)\ge\frac12(\ln s-O(1))(n+2)^2-\frac{s(s+2)}2 (n+1).
$$
Setting $s=\lceil\sqrt n\,\rceil$, we obtain the proclaimed bound
for $\nu(w)$ and hence for $N(n)$.  
\end{proof}

\begin{theorem}\label{thm:lower}
$M(n)\ge 2\ln n-O(1)$.
\end{theorem}

\begin{proof}
We adhere to the statement 2 of Lemma \ref{lem:equiv}.
Let $V=\{v_0,v_1,\ldots,v_n\}$ be a set of points in $\bbbz^2$
with $v_{i+1}-v_i\in\{a,b\}$.
Denote $G=\setdef{\frac12(v_i+v_j)}{0\le i\le j\le n}$, the set
of all potential centers of symmetry. 
Let $m_g$ denote the ``multiplicity'' of an element $g$ in $G$, that is,
the number of pairs $(i,j)$ such that $g=\frac12(v_i+v_j)$ and $i\le j$.
Clearly,
$$
\sum_{g\in G}m_g=(n+1)(n+2)/2.
$$
Furthermore, let $N$ denote the total number of quadruples
\begin{equation}\label{eq:quadr}
\mbox{$(v_l,v_i,v_j,v_k)$ with $l<i\le j<k$ and $v_i-v_l=v_k-v_j$.}
\end{equation}
Clearly,
$$
N\le\sum_{g\in G}{m_g\choose 2}
$$
(actually, the linear independence of $a$ and $b$ implies the equality here).
It follows that
\begin{equation}\label{eq:Nless}
N<\frac12\sum_{g\in G}m_g^2\le\frac12\of{\max_{g\in G}m_g}\sum_{g\in G}m_g=
\frac14n^2\of{1+O(\frac1n)}\max_{g\in G}m_g.
\end{equation}

Recall that with the set $V$ we associate a word
$w(V)$ over alphabet $\{a,b\}$. It is easy to observe a one-to-one
correspondence between quadruples \refeq{eq:quadr} in $V$ and
pairs of disjoint subwords $u_1$ and $u_2$ with the same
commutative index in $w(V)$. By Lemma \ref{lem:xyx}
we have 
$$
N\ge(\ln n-O(1))n^2/4.
$$
Together with \refeq{eq:Nless}, this gives
$$
\max_{g\in G}m_g\ge\ln n-O(1).
$$
It remains to observe that, for every center $g\in G$, the set $V$ contains a 
subset that is symmetric with respect to $g$ and has at least $2m_g-1$ elements.
\end{proof}



\section{Upper Bound}\label{s:upper}

In this section we prove an upper bound for $M(n)$.

\begin{theorem}\label{thm:upper}
$M(n)\le (7+o(1))\sqrt n$.
\end{theorem}

We use a two-dimensional geometric interpretation of $M(n)$
given by statement 2 of Lemma \ref{lem:equiv}.
We will construct a set $V=\{v_0,v_1,\ldots,v_n\}$ of points in $\bbbz^2$
such that each difference $v_{i+1}-v_i$ is either $(1,0)$ or $(0,1)$
and $MS(V)\le(7+o(1))\sqrt n$.

Our construction will be completely determined by two sets of
integers $X=\{x_1,\ldots,x_q\}$ and $Y=\{y_1,\ldots,y_q\}$
listed in the ascending order. Given $X$ and $Y$, consider a sequence
of points in $\bbbz^2$
\begin{equation}\label{eq:corners}
(x_1,y_1),\ (x_2,y_1),\ (x_2,y_2),\ (x_3,y_2),\ (x_3,y_3),\ \ldots,\ (x_q,y_q)
\end{equation}
We define $V$ by $V=V_1\cup V_2$, where
$$
V_1=\bigcup_{i=1}^q\setdef{(x_i,y)}{y_{i-1}<y\le y_i}
\mbox{ and }
V_2=\bigcup_{i=1}^{q-1}\setdef{(x,y_i)}{x_{i}<x\le x_{i+1}}
$$
(we set $y_0=y_1-1$ for convenience).
Thus, \refeq{eq:corners} are ``corner'' points of $V$, at which
difference $v_{i+1}-v_i$ changes its value from $(1,0)$ to $(0,1)$
or vice versa. Clearly, $V$ consists of $x_q+y_q+1-x_1-y_1$ points.

Given a set $Z=\{z_1,\ldots,z_q\}$ of integers listed in the ascending
order, define $D(Z)=\max_{1\le i<q}(z_{i+1}-z_i)$.

\begin{lemma}\label{lem:vxy}
Suppose that $V$ has been constructed based on $q$-element sets $X$ and $Y$
as described above. Then
\begin{equation}\label{eq:vxy}
MS(V)< MS(X)D(Y)+MS(Y)D(X)+2q.
\end{equation}
\end{lemma}

\begin{proof}
Let $S$ be the maximum subset of $V$ symmetric with respect to
center $\frac12g$, i.e.\ $S=V\cap(g-V)$. Clearly,
$$
S=(V_1\cap g-V_1)\cup(V_2\cap g-V_2)\cup(V_1\cap g-V_2)\cup(V_2\cap g-V_1).
$$
Let us estimate the cardinality of each member of the union.

$V_1\cap g-V_1$ is a symmetric subset of $V_1$. As the projection
of $V_1\cap g-V_1$ onto the first coordinate is symmetric too,
the cardinality of this projection does not exceed $MS(X)$.
As any cut of $V_1$ by vertical line (i.e.\ along the second coordinate)
containes at most $D(Y)$ points, we have 
$|V_1\cap g-V_1|\le MS(X)D(Y)$. Similarly, $|V_2\cap g-V_2|\le MS(Y)D(X)$.

Observe now that all points of $V_1$ differ in the second coordinate and have
only $q$ values for the first coordinate, while all points of $V_2$ differ 
in the first coordinate and have
only $q$ values for the second coordinate. As a consequence,
both $V_1\cap g-V_2$ and $V_2\cap g-V_1$ have less than $q$ points.
The bound \refeq{eq:vxy} follows.
\end{proof}

We now need to choose $X$ and $Y$ so as to make the right hand side
of \refeq{eq:vxy} as small as possible. The idea is to use a 
$B_2$-sequence $X=Y$, which gives us the best possible
$MS(X)=MS(Y)=2$. It easily follows from \cite{ETu} that
$D(X)\ge q(1-o(1))$ for any $B_2$-sequence $X=\{x_1,\ldots,x_q\}$.
We use a construction of \cite{Kru} that provides us with
$D(X)\le(3+o(1))q$.

\begin{lemma}\textbf{\textrm{(Kr\"uckeberg \cite{Kru})}}\label{lem:kru}
For any prime $q$ there is a sequence of integers $X=\{x_1,\ldots,x_q\}$
with $MS(X)=2$ and $D(X)<3q$. Moreover, $x_1=0$ and $x_q=2q^2-2q-1$.
\end{lemma}

We include the proof of this lemma given in \cite{Kru}, because
it contains a simple explicit construction of the needed $B_2$-sequences,
thereby making our construction of $V$ explicit too.

\begin{proof}
Set $x_{i+1}=2qi-(i^2\bmod q)$ for $0\le i<q$, where expression
$i^2\bmod q$ stands for the least non-negative residue of $i^2$ modulo $q$.
Obviously, $q<x_{i+1}-x_i<3q$. To show that $X$ is a $B_2$-sequence,
assume that $x_i+x_j=x_{i'}+x_{j'}$, $i\le j$, $i'\le j'$.
It is easy to derive from this that
$$
\left\{
\begin{array}{rcll}
i+j&=&i'+j'&\mod{q}\\
i^2+j^2&=&(i')^2+(j')^2&\mod{q}
\end{array}
\right.
$$
Since in the field $\mathbb{F}_q$ a system of kind
$$
\left\{
\begin{array}{ccl}
i+j&=&a\\
i^2+j^2&=&b
\end{array}
\right.
$$
can have only a unique solution $i,\,j$ with $i\le j$, we
conclude that $i=i'$ and $j=j'$.
\end{proof}

Let us summarize our construction of the set $V=\{v_0,v_1,\ldots,v_n\}$.
Let $q$ be the prime next to $(\sqrt{n+3}+1)/2$ and $X$ be the $B_2$-set
given by Lemma \ref{lem:kru}. Applying the construction described
in the beginning of the section with $Y=X$, we obtain a set
$V'=\{v_0,v_1,\ldots,v_n,\ldots\}$ of $4q^2-4q-1\ge n+1$ points
in $\bbbz^2$. Leaving aside some last elements of $V'$, we get
the set $V$. By Lemma \ref{lem:vxy}, $MS(V)\le MS(V')<14q$.
Since the prime next to $m$ does not exceed $m+O(m^\alpha)$, 
where $0<\alpha<1$ (\cite{Hoh}, see also \cite[pp.~225, 256]{BSh} for 
references on the best current values of
$\alpha$), we have $MS(V)\le(7+o(1))\sqrt n$.
The proof of Theorem \ref{thm:upper} is complete.


\begin{remark}\label{rem:opt}
The choice of Kr\"uckeberg's $B_2$-sequence is essentially
best possible, because the right hand side of \refeq{eq:vxy}
cannot be smaller than $\sqrt{2n}$, whatever sets $X$ and $Y$ are.
Let us prove this fact. First, observe relation
\begin{equation}\label{eq:msd}
MS(X)\ge q/D(X).
\end{equation}
for a set of integers $X=\{x_1,\ldots,x_q\}$. 
This is a consequence of inclusion
$X\subseteq\bigcup_{g=0}^{D(X)-1}(g+x_1+x_q-X)$ which implies
$|X\cap(g-X)|\ge q/D(X)$ for some $g$.
By~\refeq{eq:msd} 
$$
MS(X)D(Y)+MS(Y)D(X)\ge2(MS(X)D(Y)MS(Y)D(X))^{1/2}\ge2q
$$
and therefore the right hand side of \refeq{eq:vxy} is at least $4q$.

Further, observe that $MS(V)>\max\{D(X),D(Y)\}$. Using this, we have
$n=|V|-1\le q(D(X)+D(Y))<2q\,MS(V)$. Therefore, the right hand side
of \refeq{eq:vxy} exceeds $2n/MS(V)$. It remains to notice that one
of the values $MS(V)$ and $2n/MS(V)$ is at least $\sqrt{2n}$.
\end{remark}


\begin{remark}
Consider a random set ${\mathbf V}=\{v_0,v_1,\ldots,v_n\}$ in $\bbbz^2$
with $v_{i+1}-v_i\in\{a,b\}$ for non-collinear $a$ and $b$.
We mean that the underlying word $w({\mathbf V})$ is uniformly distributed
on $\{a,b\}^n$. The mean value of $MS({\mathbf V})$ could serve as an
upper bound for $M(n)$. Unfortunately, this probabilistic argument
cannot give anything better that the constructive bound of 
Theorem \ref{thm:upper} by the following reason.

Just for simplicity assume that $n=2m$ is even. Let $\mathbf s$ denote
the cardinality of the maximum subset of $\mathbf V$ symmetric with
respect to the center at the medium point $v_m$. Consider now
two independent sequences $\xi_1,\ldots,\xi_m$ and $\zeta_1,\ldots,\zeta_m$ 
of unbiased Bernoulli trials, that is, all $\xi_i$ and $\zeta_j$ are
mutually independent random variables that take on equiprobable values
$0$ and $1$. Denote the number of $k$ such that
$\sum_{i=1}^k\xi_i=\sum_{i=1}^k\zeta_i$ by $\mathbf t$.
In coding $a=0$ and $b=1$, it becomes clear that ${\mathbf s}=2{\mathbf t}+1$.
Estimate the expectation of $\mathbf t$ from below.

Let $p_k=\PP{\sum_{i=1}^k\xi_i=\sum_{i=1}^k\zeta_i}$.
By linearity of mathematical expectation, $\EE{\mathbf t}=\sum_{k=1}^mp_k$.
Using Chernoff's bound, we have 
\begin{eqnarray*}
&&
p_k=\sum_{l=0}^k\PP{\sum_{i=1}^k\xi_i=l}^2>
\sum_{k/2-\sqrt k\le l\le k/2+\sqrt k}\PP{\sum_{i=1}^k\xi_i=l}^2\ge\\
&&(2\sqrt k-1)
\of{\frac{\PP{k/2-\sqrt k\le\sum_{i=1}^k\xi_i\le k/2+\sqrt k}}{2\sqrt k+1}}^2
\ge\frac{(1-2\exp(-2))^2}{2\sqrt k+7}.
\end{eqnarray*}
Therefore, $\EE{\mathbf t}=\Omega\of{\sum_{k=1}^m1/\sqrt k}=\Omega(\sqrt m)$.
As $\EE{\mathbf s}=2\EE{\mathbf t}+1$, we conclude that the mean value
of $MS({\mathbf V})$ is $\Omega(\sqrt n)$.
\end{remark}


In conclusion we discuss one more aspect of the upper bound proven
in this section. Given $n$, we have constructed a set $\{v_0,v_1,\ldots,v_n\}$
with 
\begin{equation}\label{eq:inf}
MS(\{v_0,v_1,\ldots,v_n\})=O(\sqrt n).
\end{equation}

\begin{question}\label{que:inf}
Is it possible to construct an infinite set $\{v_0,v_1,v_2\ldots\}$
such that \refeq{eq:inf} is true for all $n$?
\end{question}

We could achieve this goal with the same construction, if we had an
infinite $B_2$-sequence $X=\{x_1,x_2,\ldots\}$ with 
$D(\{x_1,\ldots,x_q\})=O(q)$ for all $q$. However, the latter condition
implies $|X\cap[m]|=\Omega(\sqrt m)$ for all $m$, whereas
no $B_2$-sequence satisfies this condition by a result of Erd\H{o}s.
Erd\H{o}s proves that there is a constant $c$
such that for any infinite $B_2$-sequence $X$ the inequality
$|X\cap[m]|\le c\sqrt{m/\ln m}$ is true for infinitely many $m$
(see \cite{Erd2}).
The best known construction of \cite{AKS} gives 
$|X\cap[m]|=\Omega\of{(m\ln m)^{1/3}}$. Nevertheless, we
are able at least to approach \refeq{eq:inf}
with an infinite $V$.

\begin{proposition}\label{thm:inf}
There is an infinite sequence $V=\{v_0,v_1,v_2,\ldots\}$
with each difference $v_{i+1}-v_i$ either $(1,0)$ or $(0,1)$
and such that
\begin{equation}\label{eq:squares}
MS(\{v_0,v_1,\ldots,v_n\})=n^{1/2+O(1/\ln\ln n)}
\end{equation}
for all $n$.
\end{proposition}

\begin{proof}
We apply the straightforward infinite version of the construction
described in the beginning of this section with $X=Y=\{1,4,9,16,\ldots\}$,
the set of integer squares. By Lemma \ref{lem:vxy}, for any integer $q$
and $n=2q^2-2$
$$
MS(\{v_0,v_1,\ldots,v_n\})<2MS(\{1,4,\ldots,q^2\})D(\{1,4,\ldots,q^2\})+2q.
$$
We obviously have $D(\{1,4,\ldots,q^2\})=2q-1$ and, by Lemma \ref{lem:squares}
below, 
$$
MS(\{1,4,\ldots,q^2\})=q^{O(1/\ln\ln q)}.
$$
This proves \refeq{eq:squares} for all $n=2q^2-2$.
Equality \refeq{eq:squares} is true for any other $n$ as well,
because the next to $n$ number of kind $2q^2-2$ does not
exceed $n+\sqrt{(n+2)/2}+1=n(1+o(1))$.
\end{proof}


The following lemma in other terms estimates the number of
representations of an integer as a sum of two squares.
Though this estimate easily follows from the well-known number-theoretic
facts, we give a proof for the sake of completeness.

\begin{lemma}\label{lem:squares}
$MS(\{1,4,\ldots,q^2\})=q^{O(1/\ln\ln q)}$.
\end{lemma}

\begin{proof}
It is easy to see that the maximum subset of $\{1,4,\ldots,q^2\}$
symmetric with respect to $\frac12g$ has as many elements as the number
of solutions of equation $z_1+z_2=g$ in $\{1,4,\ldots,q^2\}$. 
The Jacobi theorem (see e.g.\ \cite[theorem 65]{Dic})
says that if $g=2^km$ with odd $m$, then the total number of integer
solutions of the equation $x^2+y^2=g$ is equal to $4E$, where $E$ is
the excess of the number of divisors $t\equiv 1\mod 4$ of $m$
over the number of divisors $t\equiv 3\mod 4$ of $m$.
We use the bound
$E\le d(m)$, where
$d(m)$ denotes the total number of positive divisors of $m$. 
It is known that $d(m)=m^{O(1/\ln\ln m)}$ (\cite{Wig}, see also
\cite{NRo} for the best currently known constant in the exponent).
As $m\le g$ and it makes sense to consider only $g<2q^2$, we have
$d(m)=q^{O(1/\ln\ln q)}$. Summarizing,
we obtain $MS(\{1,4,\ldots,q^2\})\le 4E\le 4d(m)=q^{O(1/\ln\ln q)}$.
\end{proof}


\section{Concluding Remarks And Open Problems}\label{s:higher}


\subsection{The Main Problem}

The main problem
left open is to make closer the exponential gap between our bounds
$$
2\ln n-O(1)\le M(n)\le (7+o(1))\sqrt n.
$$
Remark \ref{rem:opt} shows that our method for upper bounding $M(n)$
cannot do it better. As for possibilities to improve our lower
bound, it is a question if one can improve the intermediate lower
bound of Lemma~\ref{lem:xyx}.


\subsection{An Observation}

It turns out that if we impose some (strong at first sight) restrictions
on the structure of $V\subseteq\bbbz^2$, then the minimal possible
value of $MS(V)$ will not change much. We first prove the
following auxiliary fact.

\begin{lemma}\label{lem:stab}
Let $V$, $U$, and $A$ be finite subsets of $\bbbz^k$.
Suppose that for any $u\in U$ there is $v\in V$ with
$u-v\in A$. Then
$
MS(V)\ge MS(U)/|A|^2.
$
\end{lemma}

\begin{proof}
Fix a correspondence $\phi\function{U}{V}$ such that
$u-\phi(u)\in A$ for all $u$.
Let $S$ be a symmetric subset of $U$ containing
$MS(U)$ elements. Among all $MS(U)$ ordered pairs $(u_1,u_2)$
of symmetric points of $S$, let us consider those for which
the pair $(u_1-\phi(u_1),u_2-\phi(u_2))$ is the same. 
We can pick up at least $MS(U)/|A|^2$ such pairs.
The corresponding pairs $(\phi(u_1),\phi(u_2))$ are clearly
pairwise distinct and, moreover, have a common center
$g+\frac12(\phi(u_1)-u_1)+\frac12(\phi(u_2)-u_2)$, where $g$
is the center of symmetry of $S$. Therefore, they form
a symmetric subset of $V$ with at least $MS(U)/|A|^2$ elements.
\end{proof}

As before, let $a$ and $b$ be arbitrary but fixed non-collinear
vectors in $\bbbz^2$.
Define $M'(n)$ to be the minimum of $MS(U)$ over all subsets
$U=\{u_0,v_1,\ldots,u_n\}$ of $\bbbz^2$ with each difference
$u_{i+1}-u_i$ in $\{a,b\}$ and such that the underlying
word $w(U)$ does not contain subwords $aa$ and $bbb$.

\begin{proposition}\label{prop:mvar}
$\frac19 M'(2n-1)\le M(n)\le M'(n)$.
\end{proposition}

\begin{proof}
The second inequality is trivial. To prove the first one,
consider a set $V=\{v_0,v_1,\ldots,v_n\}$
of points of $\bbbz^2$ with each $v_{i+1}-v_i$ either $(1,1)$ or $(1,2)$. 
Extend $V$
to $U=\{u_0,u_1,\ldots\}$ inserting a new point $v_i+(1,0)$ between 
$v_i$ and $v_{i+1}$ with $v_{i+1}-v_i=(1,1)$ and two new points $v_i+(1,0)$ 
and $v_{i+1}-(0,1)$ between $v_i$ and $v_{i+1}$ with $v_{i+1}-v_i=(1,2)$.
Notice that for any $u_j$ there is $v_i$ with 
$u_j-v_i\in\{(0,0),(1,0),(0,-1)\}$. By Lemma \ref{lem:stab},
$MS(V)\ge MS(U)/9$. In its turn $MS(U)\ge M'(2n-1)$, because
difference between any two successive points
of $U$ is either $a=(1,0)$ or $b=(0,1)$, and word $w(U)$ is free
of subwords $a^2$ and $b^3$ and has length at least $2n-1$. 
The proposition follows.
\end{proof}

Similarly with item 3 of Lemma \ref{lem:equiv}, $M'(n)$ could be
alternatively defined as the maximum $m$ such that every binary word
of length $n$ without squares of one letter and cubes of another letter
has abelian occurrence of a symmetric pattern of length at least $m-1$.
Proposition \ref{prop:mvar} shows that the function $M(n)$ and
its restricted version $M'(n)$ have the same order of magnitude.

\begin{question}
Can prohibition of $a^2$ and $b^3$ help? Is estimating $M'(n)$
somehow easier than estimating $M(n)$?
\end{question}


\subsection{Higher Dimensions}

The function $M(n)$, if considered from the geometric point of view
in accordance with item 2 of Lemma \ref{lem:equiv}, admits a natural
generalization. Given $A\subset\bbbz^k$, define
$$
M_{k,A}(n)=\min\setdef{MS(\{v_0,v_1,\ldots,v_n\})}{v_i\in\bbbz^k,\ v_{i+1}-v_i
\in A}.
$$
\begin{remark}
We assume that $V=\{v_0,v_1,\ldots,v_n\}$ is an $(n+1)$-element set, or
a sequence without self-crossing. Nevertheless, if we allow
self-crossing and consider $V$ to be {\em multiset}, then
everything that is claimed below holds true under the suitable
definition of a {\em symmetric multisubset}.
\end{remark}

If $A\subset \bbbz^k$ is a linearly independent system of $k$ vectors, 
then $M_{k,A}(n)$ does not depend 
on the particular choice of $A$. In this case we will drop subscript
$A$ and write simply $M_k(n)$. In this notation $M(n)=M_2(n)$.

Define also $L_k(n)$ to be the maximal $l$ such that every
word of length $n$ over $k$ letter alphabet has an abelian
occurrence of a symmetric pattern of length at least $l$.
The proof of Lemma \ref{lem:equiv} can be directly extended to
show that
\begin{eqnarray}
M_k(n)&=&L_k(n)+1,\nonumber\\
M_{k,A}(n)&\ge&L_{|A|}(n)+1=M_{|A|}(n).\label{eq:jump}
\end{eqnarray}


Let us focus on the case of difference set
$A_c=\setdef{v}{0<\|v\|\le c}$, where
the norm $\|\cdot\|$ on $\bbbz^k$ is defined by
$\|(z_1,\ldots,z_k)\|=\sum_{i=1}^k|z_i|$.
As long as we are concerned with
asymptotics in $n$ and consider parameters $k$ and $c$ fixed,
we may restrict our attention to the difference set $A_1$,
consisting of $k$ unit vectors of the standard basis and $k$ more
opposite vectors. We will not loose much, because
$$
\frac{M_{k,A_1}(n)}{(2c+1)^{2k}}\le M_{k,A_c}(n)\le M_{k,A_1}(n).
$$
The first inequality follows from Lemma \ref{lem:stab}
(given a set $V=\{v_0,v_1,\ldots,v_n\}$ with difference set $A_c$,
we extend it to a set $U$ with difference set $A_1$ inserting
intermediate points between $v_i$ and $v_{i+1}$ whenever $\|v_{i+1}-v_i\|>1$,
and then relate $MS(V)$ with $MS(U)$).
To facilitate notation, denote $M_k^\pm(n)=M_{k,A_1}(n)$. Notice relations
$$
M_{2k}(n)\le M_k^\pm(n)\le M_k(n),
$$
where the first inequality is true by \refeq{eq:jump}.

If $k>2$, all that we can say is
that 
\begin{equation}\label{eq:mktoinf}
M_k(n)\to\infty\mbox{\ \ as\ \ }n\to\infty.
\end{equation}
This fact is a consequence of inequalities $M_k(n)>L_k(n)>L^{\nonabel}_k(n)$,
where $L^{\nonabel}_k(n)$ generalizes the function $L^{\nonabel}(n)$
introduced in Section \ref{s:prel} to the $k$-letter alphabet.
Similarly with Lemma \ref{lem:tower}, if $L^{\nonabel}_k(n)\ge l$, 
then $L^{\nonabel}_k((n+1)(k^n+1))\ge 2l+1$. This results in a lower
bound for $M_k(n)$ that tends to the infinity but more slowly than
the inverse tower function.

\begin{question}
Prove better (than the inverse tower function) lower bounds
for $M_3(n)$ and $M_2^\pm(n)$.
\end{question}

\begin{question}
For $k>2$ prove a better (than $O(\sqrt n)$) upper bound for $M_k(n)$.
\end{question}

\begin{question}
Try to prove a better (than $O(\sqrt n)$) upper bound for $M_2^\pm(n)$.
\end{question}

\subsection{Odd Vs.\ Even Cardinality}
Dekking \cite{Dek} proves that in the binary alphabet there is an
infinite word without abelian occurences of pattern $x^4$
and that in the ternary alphabet there is an infinite word
without abelian occurences of pattern $x^3$.
Ker\H{a}nen \cite{Ker} reports a (computer aided) proof that in the 4-letter
alphabet there is an
infinite word free of abelian occurences of pattern $x^2$.
The latter result implies
that there is an infinite sequence of points in $\bbbz^4$
with differences between consequtive points only $(1,0,0,0)$,
$(0,1,0,0)$, $(0,0,1,0)$, and $(0,0,0,1)$ and without
symmetric subsets of odd cardinality
(excepting singletons). At the same time by \refeq{eq:mktoinf} it must contain
arbitrarily long symmetric subsets of even cardinality.



\section*{\normalsize Acknowledgments.}

I am grateful to Taras Banakh, whose proof of
Proposition~\ref{prop:toinf} in geometric terms inspired this work,
and to Oleg Pikhurko, whose observation improved the original proof of
Theorem~\ref{thm:lower} and led to a better lower bound for $M(n)$.
I thank an anonymous referee for several corrections and useful
expository suggestions.



\begin{thebibliography}{10}

\bibitem{AKS}
M.~Ajtai, J.~Koml\'os and E.~Szemer\'edi.
\newblock
A dense infinite Sidon sequence.
\newblock
{\em European J.\ Combin.}, 2:1--11, 1981.

\bibitem{BSh}
E.~Bach and J.~Shallit.
\newblock
{\em Algorithmic number theory}.
\newblock
Vol.~1, MIT Press, Cambridge, 1996.

\bibitem{Ban}
T.~Banakh. 
\newblock
On asymmetric colorings of Abelian groups.
\newblock
In: {\em Paul Erd\H{o}s and his Mathematics.
Research Communications
of the conference held in the memory of Paul Erd\H{o}s}, July 4--11, 1999,
Budapest, Janos Bolyai Mathematical Society, 30--32.

\bibitem{BPr}
T.~O.~Banakh and I.~V.~Protasov.
\newblock
Asymmetric partitions of Abelian groups (in Russian).
\newblock
{\em Mat.\ Zametki}, 66(1):10--19, 1999.

\bibitem{BKV}
T.~Banakh, I.~Kmit, and O.~Verbitsky. 
\newblock
On asymmetric colorings of integer grids.
\newblock
September 1999, accepted for publication in {\em Ars Combinatoria}.

\bibitem{Bos}
R.~C.~Bose.
\newblock
An affine analogue of Singer's theorem.
\newblock
{\em J.~Indian Math.\ Soc.} (new series), 6:1--15, 1942. 

\bibitem{BCh}
R.~C.~Bose and S.~Chowla.
\newblock
Theorems in the additive theory of numbers.
\newblock
{\em Comment.\ Math.\ Helv.}, 37:141--147, 1962. 

\bibitem{Bro}
T.~C.~Brown.
\newblock
Variations on van der Waerden's and Ramsey's theorems.
\newblock
{\em Am.\ Math.\ Mon.}, 82:993--995, 1975.

\bibitem{Cho}
S.~Chowla.
\newblock
Solution of a problem of Erd\H{o}s and Turan in additive number theory.
\newblock
{\em Proc.\ Natl.\ Acad.\ Sci.\ India}, 14:1--2, 1944.

\bibitem{CSc}
M.~Coudrain and M.~P.~Sch\"utzenberger.
\newblock
Une condition de finitude des monoides finiment engendres.
\newblock
{\em C.\ R.\ Acad.\ Sci., Paris, Ser.~A}, 262:1149--1151, 1966. 

\bibitem{Dek}
F.~M. Dekking.
\newblock Strongly non-repetitive sequences and progression-free sets.
\newblock {\em J.~Combin.\ Theory}, 27:181--185, 1979.

\bibitem{Dic}
L.~E.~Dickson.
\newblock
{\em Introduction to the theory of numbers.}
\newblock
Dover Publ., New York, 1957.

\bibitem{ETu}
P.~Erd\H{o}s and P.~Turan.
\newblock
On a problem of Sidon in additive number theory, and on some related
problems.
\newblock
{\em J.~London Math.\ Soc.}, 16:212--215, 1941. 

\bibitem{Erd}
P.~Erd\H{o}s.
\newblock
On a problem of Sidon in additive number theory and on some related
problems. Addendum. 
\newblock
{\em J.~London Math.\ Soc.}, 19:208, 1944.

\bibitem{Erd2}
P.~Erd\H{o}s,
\newblock
message to A.~St\"ohr, 
\newblock
published in: A.~St\"ohr,
Gel\"oste und ungel\"oste Fragen \"uber Basen der nat\"urlichen Zahlenreihe. 
II. {\em J.~Reine Angew.\ Math.}, 194:132--133, 1955.

\bibitem{Fou}
W.~L.~Fouch\'e.
\newblock
Unavoidable regularities and factor permutations of words.
\newblock
{\em Proc.\ Royal Soc.\ Edinb.}, 125A(3):519--524, 1995.

\bibitem{Ker}
V.~Ker\H{a}nen.
\newblock
Abelian squares are avoidable on 4 letters.
\newblock
In: {\em Proc.\ of ICALP'92}, LNCS vol.~623, Springer, 41--52, 1992.

\bibitem{Hoh}
G.~Hoheisel.
\newblock
Primzahlprobleme in der Analysis.
\newblock
{\em Sitzungsberichte der Preussischen Akademie der Wissenschaften},
573:580--588, 1930.

\bibitem{Kru}
F.~Kr\"uckeberg.
\newblock $B_2$-Folgen und verwandte Zahlenfolgen.
\newblock {\em J.~Reine Angew.\ Math.}, 206:53--60, 1961.

\bibitem{NRo}
J.-L.~Nicolas and G.~Robin.
\newblock
Majorations explicites pour le nombre de diviseurs de $N$.
\newblock
{\em Canad.\ Math.\ Bull.}, 26:485--492, 1983.

\bibitem{PSa}
C.~Pomerance and A.~S\'ark\"ozy.
\newblock Combinatorial number theory.
\newblock In {\em Handbook of Combinatorics}, chapter~20, pages 967--1018.
  Elsevier Publ., 1995.

\bibitem{Pom}
C.~Pomerance.
\newblock
Collinear subsets of lattice point sequences --- an analog of Szemer\'edi's
theorem.
\newblock
{\em J.\ Combin.\ Theory A}, 28:140--149, 1980.

\bibitem{RGe}
L.~T.~Ramsey and J.~L.~Gerver.
\newblock
On certain sequences of lattice points.
\newblock
{\em Pacific J.~Math}, 83:357--363, 1979.

\bibitem{Sin}
J.~Singer.
\newblock
A theorem in finite projective geometry and some applications to number theory.
\newblock
{\em Trans.\ Am.\ Math.\ Soc.}, 43:377--385, 1938. 

\bibitem{Wig}
S.~Wigert.
\newblock
Sur l'odre de grandeur du nombre des diviseurs d'un entier.
\newblock
{\em Arkiv f\"or Matematik, Astronomi och Fisik}, 3(18):1--9, 1906--1907.

\end{thebibliography}

\end{document}