% LaTeX2e
% 25 pages
% the paper contains a figure for which three graphic files
%`square.bmp', `cylinder.bmp', and `disk.bmp' are needed
%
\documentclass[12pt]{article}
\usepackage{latexsym}
\usepackage{amssymb}
\usepackage{graphics}
%
\hfuzz=3pt
%
% Page format
\oddsidemargin 2mm
\evensidemargin 2mm
\topmargin 14mm
% text height = 217mm
\makeatletter
\newlength{\temp}
\newlength{\templ}
\newlength{\templl}
\setlength{\temp}{-\topskip}
\setlength{\templ}{217mm}
\addtolength{\templ}{\temp}
\setlength{\templl}{\baselineskip}
\divide\templ\templl
\@tempcnta=\templ
\setlength\textheight{\@tempcnta\baselineskip}
\addtolength{\textheight}{\topskip}
\makeatother
%
\textwidth 157mm
\flushbottom %all pages of equal height
%
\newcommand{\subtitle}[1]{\par\smallskip\par\noindent\textbf{#1}}
% Theorem-like environments
%
\newtheorem{thm}{Theorem}[section]
\newtheorem{lem}[thm]{Lemma}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{dfn}[thm]{Definition}
%
%In the below thm-environments I prefer sl
%
\newenvironment{theorem}{\begin{thm}\begin{slshape}}{\end{slshape}\end{thm}}
\newenvironment{lemma}{\begin{lem}\begin{slshape}}{\end{slshape}\end{lem}}
\newenvironment{corollary}{\begin{cor}\begin{slshape}}{\end{slshape}\end{cor}}
\newenvironment{proposition}{\begin{prop}\begin{slshape}}%
{\end{slshape}\end{prop}}
\newenvironment{definition}{\begin{dfn}\begin{slshape}}{\end{slshape}\end{dfn}}
%
%In the below thm-environments I prefer rm
%
\newtheorem{rem}[thm]{Remark}
\newenvironment{remark}{\begin{rem}\em}{\end{rem}}
\newtheorem{inst}[thm]{Example}
\newenvironment{example}{\begin{inst}\em}{\end{inst}}
%
% Proofs
\newcommand{\qed}{$\;\;\;\Box$}
\newenvironment{proof}{\par\smallbreak\noindent{\textsl{Proof.}~}}
{\unskip\nobreak\qed \par\medbreak}
\newenvironment{sketch}{\par\smallbreak\noindent{\textsl{Proof-sketch.}~}}
{\unskip\nobreak\qed \par\medbreak}
\newcommand{\noproof}{\qed}
%
%
%style changes
%
\def\labelenumi{{\rm(\theenumi)}} %()-enumeration
%
%\S in Sections
\makeatletter
\def\section{\@startsection {section}{1}{\z@}{3.5ex plus1ex minus
.2ex}{2.3ex plus.2ex}{\reset@font\Large\bf\S~}}
\makeatother
%
\newcommand{\hide}[1]{}
\newcommand{\spaceclass}[3]{\par\noindent\textbf{\S~#3~#1.} #2
\par\hangindent=\parindent\hangafter=1}
\newcommand{\spaces}[3]{\textbf{\ref{#3}~#1.} #2}
\newcommand{\spacess}[3]{%\par\noindent
\textbf{\ref{#3}~#1:} #2}
\newcounter{op}%[section]
\newcommand{\oproblem}{\refstepcounter{op}\par\textbf{\theop.}~}
% Abbreviations
\newcommand{\lle}{{\scriptscriptstyle{\le}}}
\newcommand{\setdef}[2]{\left\{ \hspace{0.5mm} #1 :
\hspace{0.5mm} #2 \right\}}
\newcommand{\of}[1]{\left( #1 \right)}
\newcommand{\function}[2]{:#1 \rightarrow #2}
\newcommand{\mod}[1]{\,(\bmod\, #1)}
\newcommand{\fracc}[2]{#1/#2}
\newcommand{\twothird}{{\textstyle\frac23}}
\newcommand{\refeq}[1]{(\ref{eq:#1})}
\newcommand{\zz}{\mathbb{Z}}
\newcommand{\nn}{\mathbb{N}}
\newcommand{\rr}{\mathbb{R}}
\newcommand{\cc}{\mathbb{C}}
\newcommand{\bbbf}{\mathbb{F}}
\newcommand{\zn}{{\zz_n}}
\newcommand{\zm}{\zz_m}
\newcommand{\om}{\Omega}
\newcommand{\sym}{\mathcal{S}}
\newcommand{\uu}{\mathcal{U}}
\newcommand{\ms}{ms}
\newcommand{\fms}{bms}
\newcommand{\dms}{dms}
\newcommand{\MS}{MS}
\newcommand{\M}{M}
\title{
A Ramsey Treatment of Symmetry\\}
\newcounter{thesame}
\setcounter{thesame}{1}
\author{
T.~Banakh\thanks{Research supported in part by grant INTAS-96-0753.}
\quad
O.~Verbitsky$^\fnsymbol{thesame}\,\mbox{}$\thanks{
Part of this work was done while visiting the Institute of
Information Systems, Vienna University of Technology,
supported by a Lise Meitner Fellowship of the Austrian
Science Foundation (FWF).}
\quad
Ya.~Vorobets\\[4mm]
\normalsize
Department of Mechanics and Mathematics\\
\normalsize
Lviv University, 79000 Lviv, Ukraine\\
\normalsize
E-mail: {\tt tbanakh@franko.lviv.ua}\\[6mm]
\normalsize
Submitted: November 8, 1999; Accepted: August 15, 2000.
}
\date{}
\pagestyle{myheadings}
\markright{\sc the electronic journal of combinatorics
\textbf{7} (2000), \#R52\hfill}
\begin{document}
\thispagestyle{empty}
\maketitle
\bigskip
\begin{flushright}
\em
But seldom is asymmetry merely the absence of symmetry.\\
Hermann Weyl, ``Symmetry''
\end{flushright}
\bigskip
\begin{center}
\textbf{Abstract}
\end{center}
Given a space $\Omega$ endowed with symmetry, we define $ms(\Omega, r)$
to be the maximum of $m$ such that for any $r$-coloring of $\Omega$
there exists a monochromatic symmetric set of size at least $m$.
We consider a wide range of spaces $\Omega$ including the discrete and
continuous segments $\{1, \ldots, n\}$ and $[0,1]$ with central symmetry,
geometric figures with the usual symmetries of Euclidean space,
and Abelian groups with a natural notion of central symmetry.
We observe that $ms(\{1, \ldots, n\}, r)$ and $ms([0,1], r)$
are closely related, prove lower and upper bounds for $ms([0,1], 2)$,
and find asymptotics of $ms([0,1], r)$ for $r$ increasing.
The exact value of $ms(\Omega, r)$ is determined for figures
of revolution, regular polygons, and multi-dimensional parallelopipeds.
We also discuss problems of a slightly different flavor and,
in particular, prove that the minimal $r$ such that there exists
an $r$-coloring of the $k$-dimensional integer grid without infinite
monochromatic symmetric subsets is $k+1$.
\bigskip
{\em MR Subject Number: 05D10}
\newpage
\setcounter{section}{-1}
\section{Introduction}
The aim of this work is, given a space with symmetry, to compute or
to estimate the maximum size of a monochromatic symmetric set that exists
for any $r$-coloring of the space.
More precisely, let $\om$ be a space with measure $\mu$.
Suppose that $\om$ is endowed with a family $\sym$ of transformations
$s\function\om\om$ called \emph{symmetries}.
A set $B\subseteq\om$ is \emph{symmetric} if $s(B)=B$ for
a symmetry $s\in\sym$. An \emph{$r$-coloring} of $\om$ is a map
$\chi\function\om{\{1,2,\ldots,r\}}$, where each \emph{color class}
$\chi^{-1}(i)$ for $i\le r$ is assumed measurable.
A set included into a color class is called \emph{monochromatic}.
In this framework, we address the value
$$
\ms(\om,\sym,r)=\inf_\chi\sup\setdef{\mu(B)}{B\mathrm{\ is\ a\ monochromatic\
symmetric\ subset\ of\ }\om},
$$
where the infimum is taken over all $r$-colorings of $\om$.
Our analysis covers the following spaces with symmetry.
\spaceclass{Segments}
{$\sym$ consists of central symmetries.}
{\ref{s:n}--\ref{s:01}}
\spaces{Discrete segment $\{1,2,\ldots,n\}$}
{$\mu$ is the cardinality of a set.\\}
{s:n}
\spaces{Continuous segment $[0,1]$}
{$\mu$ is the Lebesgue measure.}
{s:01}
\spaceclass{Abelian groups}
{$\sym$ consists of ``central'' symmetries $s_g(x)=g-x$.}
{\ref{s:groups}}
\spaces{Cyclic group $\zn$}
{$\mu$ is the cardinality of a set.
Equivalently: the vertex set of
the regular $n$-gon with axial symmetry.\\}
{ss:zn}
\spaces{Group $\rr/\zz$}
{$\mu$ is the Lebesgue measure. Equivalently: the circle with
axial symmetry.\\}
{ss:circle}
\spaces{Arbitrary compact Abelian groups}
{$\mu$ is the Haar measure. A generalization of the preceding two cases.}
{ss:cag}
\spaceclass{Geometric figures}
{$\sym$ consists of non-identical isometries of $\om$ (including all central,
axial, and rotational symmetries). $\mu$ is the Lebesgue measure.}
{\ref{s:geom}}
\spacess{Figures of revolution}
{disc, sphere etc.\\}
{ss:revol}
\spacess{Figures with finite $\sym$}
{regular polygons, ellipses and rectangles, their
multi-dimensional analogs.}
{ss:finsym}
\noindent
\textbf{\S~\ref{s:extr}} analyses the cases when the value $\ms(\om,\sym,r)$
is attainable with a certain coloring~$\chi$. \textbf{\S~\ref{s:inf}}
suggests another view of the subject with focusing on the \emph{cardinality}
of monochromatic symmetric subsets irrespective of the measure-theoretic
aspects. \textbf{\S~\ref{s:open}} contains a list of open problems.
Techniques used for discrete spaces include a
reduction to continuous optimization (Section \ref{ss:blurred}),
the probabilistic method (Proposition \ref{prop:msfms}),
elements of harmonic analysis (Proposition \ref{prop:znsl}),
an application of the Borsuk-Ulam antipodal theorem (Theorem \ref{thm:bp}).
Continuous spaces are often approached by their discrete
analogs (e.g.\ the segment and the circle are limit cases
of the spaces $\{1,2,\ldots,n\}$ and $\zn$, respectively).
In Section \ref{ss:revol} combinatorial methods are combined with
some Riemannian geometry and measure theory.
Throughout the paper $[n]=\{1,2,\ldots,n\}$.
In addition to the standard $o$- and $O$-notation,
we write $\Omega(h(n))$ to
refer to a function of $n$ that everywhere exceeds $c\cdot h(n)$, for $c$
a positive constant. The notation $\Theta(h(n))$ stands for a function
that is simultaneously $O(h(n))$ and $\Omega(h(n))$.
The relation $f(n)\sim h(n)$ means that $f(n)=h(n)(1+o(1))$.
All proofs that in this exposition are omitted or only sketched
can be found in full detail in \cite{Ban1,Ban2,BPr,BPr2,BVV,Pro,Pro2,Ver}
unless other sources are specified.
\section{Discrete segment $[n]$}\label{s:n}
\subsection{Warm-up}
A set $B\subseteq\zz$ such that $B=g-B$ for an integer $g$
is called {\em symmetric} (with respect to the center at rational
point $\frac12g$). Given a set of integers $A$, let $\MS(A)$ denote
the maximum cardinality of a symmetric subset $B\subseteq A$.
In the case that $A\subseteq[n]$, notice the lower bound
\begin{equation}\label{eq:msa}
\MS(A)>\frac{|A|^2}{2n}.
\end{equation}
Indeed, since there are $|A|^2$ ordered pairs $(a,a')$ of
elements of $A$ and at most $2n-1$ centers $(a+a')/2$, at least
$|A|^2/(2n-1)$ pairs have a common center $g$.
Clearly, the maximum subset of $A$ symmetric with respect to $\frac12g$
is $A\cap(g-A)$. The cardinality of $A\cap(g-A)$ is equal to
the number of representations of $g$ as a sum $a+a'$ with both $a$ and
$a'$ in $A$. This gives us some links to number theory.
\begin{example}
\textbf{Primes -- much symmetry.}\\
Let $P_{{\lle}n}$ denote the set of all primes in $[n]$.
The prime number theorem says that $|P_{{\lle}n}|\sim n/\log n$.
It follows by \refeq{msa} that
$\MS(P_{{\lle}n})=\Omega(n/\log^2n)$. This simple estimate turns out
to be not so far from the true value
$\Theta(\frac{n\log\log n}{\log^2n})$ due to Schnirelmann \cite{Sch} and
Prachar~\cite{Pra}.
\end{example}
\begin{example}
\textbf{Squares -- little symmetry.}\\
Let $S_{{\lle}n}$ denote the set of all squares in $[n]$.
The Jacobi theorem
says that if $g=2^km$ with odd $m$, then the number of
representations $g=x^2+y^2$ with integer $x$ and $y$ is equal to $4E$,
where $E$ denotes
the excess of the number of divisors $t\equiv 1\mod 4$ of $m$
over the number of its divisors $t\equiv 3\mod 4$. The value $E$
does not exceed the number $d(m)$ of all positive divisors of $m$.
It is known that $d(m)=m^{O(1/\ln\ln m)}$ (Wigert, see also \cite{NRo}).
Therefore, $\MS(S_{{\lle}n})=n^{O(1/\log\log n)}$.
\end{example}
\begin{example}
\textbf{(Kr\"uckeberg \cite{Kru}) A Sidon set -- no symmetry.}\\
Given a prime $p$, define the set $A_p=\{a_1,\ldots,a_p\}$ by
$a_{i+1}=2pi-(i^2\bmod p)+1$ for $0\le i0$, fix a coloring
of $[0,1]$ with color classes $A_1$ and $A_2$ such that both
$\ms(A_i)$ do not exceed $\ms([0,1],2)+\epsilon$.
Consider Cartesian squares $A_1^2$ and $A_2^2$ in a plane. Obviously,
\begin{equation}\label{eq:cart}
\mu^2(A_1^2\cup A_2^2)=\mu(A_1)^2+(1-\mu(A_1))^2\ge 1/2.
\end{equation}
We now have to bound the left hand side of \refeq{cart} from above.
Define $S(a,b)=\setdef{(x,y)\in[0,1]^2}{a\le x+y\le b}$.
Let $00$, let
$\beta=\{\beta_i\}_{i=0}^{k-1}$ be a blurred $k$-coloring of $[0,1]$
with $\fms([0,1],k;\beta)<\fms([0,1],k)+\epsilon$.
Assume $r=kt$ and define a blurred $r$-coloring $\chi=\{\chi_i\}_{i=0}^{r-1}$
by $\chi_i(x)=\frac1t\beta_{i\bmod k}(x)$ for all $x\in[0,1]$. Then
\begin{eqnarray*}
\displaystyle
\fms([0,1],r)\le\fms([0,1],r;\chi)=\max_{0\le i1/r^2.
\end{equation}
\end{theorem}
\subtitle{Lower bounds.}
Recall that $\mu(A)=|A|/n$ is the density of a set $A\subseteq\zn$.
Let $\chi_A\function\zn{\{0,1\}}$ denote the characteristic function
of $A$. Define
\begin{equation}\label{eq:f}
f(g)=\mu\of{A\cap(g-A)}=\frac1n\sum_{x\in\zn}\chi_A(x)\chi_A(g-x)
\end{equation}
to be the density of the maximum subset of $A$ symmetric with
respect to symmetry $s(x)=g-x$.
The proof of lower bounds in Theorem \ref{thm:zn} is based on the
simple observation that at least one of $r$ color classes must have
density at least $1/r$.
The weakest bound $\ms_+(\zn,r)\ge1/r^2$
immediately follows from the statement below.
\begin{proposition}\label{prop:weakl}
Every set $A\subseteq\zn$ contains an $\sym_+$-symmetric subset
of density at least $\mu(A)^2$.
\end{proposition}
\begin{proof}
We apply the standard averaging argument. Using \refeq{f}, we have
\begin{equation}\label{eq:fg}
\frac1n\sum_{g\in\zn}f(g)=\frac1n\sum_{x\in\zn}\chi_A(x)
\frac1n\sum_{g\in\zn}\chi_A(g-x)=\mu(A)^2.
\end{equation}
Therefore, $f(g)\ge\mu(A)^2$ for at least one $g$.
\end{proof}
The next two statements strengthen Proposition \ref{prop:weakl}
in two different directions. The first of them implies the bound
$\ms(\zn,r)\ge1/r^2$ in Theorem \ref{thm:zn}.
\begin{proposition}\label{prop:znl}
Every set $A\subseteq\zn$ contains an $\sym$-symmetric subset
of density at least $\mu(A)^2$.
\end{proposition}
\begin{proof}
For odd $n$ the statement coincides with Proposition \ref{prop:weakl}.
Suppose that $n=2m$. Let $A_0$ and $A_1$ be two parts of $A$ consisting
of even and odd numbers respectively.
Averaging \refeq{f} on even arguments of $f$, we obtain
\begin{eqnarray*}
\frac1m\sum_{g\in\zm}f(2g)=\frac1n\sum_{x\in\zn}\chi_A(x)
\frac1m\sum_{g\in\zm}\chi_A(2g-x)=\\
\frac1n\sum_{x\mathrm{\ even}}\chi_{A_0}(x)
\frac1m\sum_{x\mathrm{\ even}}\chi_{A_0}(x)+
\frac1n\sum_{x\mathrm{\ odd}}\chi_{A_1}(x)
\frac1m\sum_{x\mathrm{\ odd}}\chi_{A_1}(x)=\\
2\mu(A_0)^2+2\mu(A_1)^2\ge
\of{\mu(A_0)+\mu(A_1)}^2=\mu(A)^2.
\end{eqnarray*}
Therefore, $f(2g)\ge\mu(A)^2$ for at least one $g$.
\end{proof}
It remains to prove the bound $\ms_+(\zn,r)>1/r^2$ in Theorem \ref{thm:zn}.
\begin{proposition}\label{prop:znsl}
Let $A$ be a proper nonempty subset of $\zn$. Then $A$ contains
an $\sym_+$-symmetric subset of density strictly more than $\mu(A)^2$.
\end{proposition}
\begin{proof}
Assume, to the contrary, that $f(g)\le\mu(A)^2$ for all $g$.
By \refeq{fg} this implies $f(g)\equiv\mu(A)^2$, where
${\equiv}$ means equality everywhere on $\zn$.
Let $\phi_i\function\zn\cc$, for $0\le i0$, estimate the probability that
\begin{equation}\label{eq:bis}
|B_{i,s}|>\frac n{r^2}+\delta n+3.
\end{equation}
Inequality \refeq{bis} implies $\sum_{j=1}^mX_j>(\frac1{r^2}+\delta)m$.
This allows us apply the Chernoff bound and estimate the probability
of \refeq{bis} from above by $\exp(-2\delta^2m)$. Hence the event \refeq{bis}
occurs for some $i$ and $s$ with probability less than $rn\exp(-2\delta^2m)$.
For $\delta=\sqrt\frac{\log(rn)}{n-2}$ the latter probability is strictly
less than $1$, completing the proof.
\end{proof}
}
\subsection{Circle $\rr/\zz$}\label{ss:circle}
The group $\rr/\zz$ is of especial interest because it can be
alternatively viewed as the circle with axial symmetry.
Of course, $\sym=\sym_+$.
\begin{theorem}\label{thm:circle}
$\ms(\rr/\zz,r)=1/r^2$.
\end{theorem}
The proof of Theorem \ref{thm:circle} borrows much from our analysis
of $\zn$. Similarly to $\zn$, the following properties are true
for $\om=\rr/\zz$.
\begin{description}
\item[(L)]
Every measurable set $A\subseteq\om$ contains a symmetric subset
$B\subseteq A$ of measure $\mu(B)\ge\mu(A)^2$.
\item[(SL)]
Every measurable set $A\subset\om$ of measure $0<\mu(A)<1$ contains a
symmetric subset $B\subseteq A$ of measure $\mu(B)>\mu(A)^2$.
\item[(U)]
$\ms(\om,r)\le 1/r^2$.
\end{description}
The proof of (L) is the same as that of Proposition \ref{prop:weakl},
with integration instead of summation.
As a consequence, $\ms(\rr/\zz,r)\ge 1/r^2$.
Property (SL), the remarkable strengthening of (L),
can be proved with using the Fourier expansion similarly to
Proposition \ref{prop:znsl}.
Property (U) is provable by reduction to Proposition \ref{prop:znu}
on account of the following fact.
\begin{proposition}\label{prop:subgr}
Let $H$ be a finite subgroup of a compact Abelian group $G$.
Then $\ms_+(G,r)\le\ms_+(H,r)$.\noproof
\end{proposition}
We therefore have
$\ms(\rr/\zz,r)\le\ms_+(\zn,r)\le \frac1{r^2}+O(\sqrt{\fracc{\log(rn)}{n}})$
for all $n$, which immediately implies (U).
We will refer to Properties (L), (SL), and (U) in the rest of the survey
as they are common for many spaces with symmetry.
\subsection{Arbitrary compact Abelian groups}\label{ss:cag}
Recall that we consider a compact Abelian group $G$ along with
its Haar measure $\mu$. The topology of $G$ is assumed Hausdorff,
and $\mu$ is assumed to be a complete probability measure.
This setting includes the groups
$\zn$ with the counting measure and $\rr/\zz$ with the Lebesgue measure
as particular cases.
\begin{theorem}
Let $[G]_2$ denote the subgroup of a group $G$ consisting of
the elements of order 2. Then $\ms(G,r)=\ms_+(G,r)=\fracc1{r^2}$
provided $\mu([G]_2)=0$.
\end{theorem}
The lower bound $\ms(G,r)\ge1/r^2$ follows from Property (L) above
that is true for every compact Abelian group $\om=G$ with respect to
the family of symmetries $\sym$.
Moreover, Property (SL) is true with respect to the extended
family of symmetries $\sym_+$.
To establish Property (U) with respect to $\sym_+$, the following
relation is useful.
\begin{proposition}\label{prop:factor}
Let $H$ be a closed subgroup of a compact Abelian group $G$.
Then $\ms_+(G,r)\le\ms_+(G/H,r)$.\noproof
\end{proposition}
Proving (U), we distinguish two cases. If there exists a homomorphism
from $G$ onto $\rr/\zz$, then (U) follows from Proposition \ref{prop:factor}
and Theorem \ref{thm:circle}. Otherwise, the structural theory
of compact Abelian groups (see e.g.\ \cite{Mor}) implies that $G$
can be approximated by a sequence of finite Abelian groups $\{D_n\}$
in the sense that $G$ has closed subgroups $H_n$ with $G/H_n\simeq D_n$
and $\mu(H_n)\to0$. By Proposition \ref{prop:factor},
$\ms_+(G,r)\le\ms_+(D_n,r)$. It remains to prove the upper bound
$\ms_+(D_n,r)=\fracc1{r^2}+o(1)$, what can be done by the probabilistic
method similarly to Proposition~\ref{prop:znu}. As an example of
this scenario one can suggest the group $Z(p)$ of integer $p$-adic numbers,
which is approximated in the above sense by the cyclic groups $\zz_{p^n}$.
\section{Geometric figures}\label{s:geom}
This section is devoted to symmetric geometric figures in
Euclidean space $\rr^k$.
The general reference books on the topic are \cite{Cox,Wey}.
We consider two classes of figures that require completely
different approaches. One class consists of surfaces and bodies
of revolution. Another class includes plane figures like regular polygons,
ellipses and rectangles (equivalent as spaces with symmetry), and
their multi-dimensional analogs. The crucial feature of this class is that
its members have only finitely many symmetries.
Every figure $\om$ is considered with the Lebesgue measure $\mu$
on $\om$ normed so that $\mu(\om)=1$. The family of admissible
symmetries consists of all non-identical isometries of
$\rr^k$ leaving $\om$ invariant.
We therewith have defined the value $\ms(\om,r)$.
\subsection{Figures of revolution}\label{ss:revol}
Though our results apply to a wide range of figures of revolution
including cylinder, cone, torus etc., we will focus on
the ball $V^k$ and the sphere $S^{k-1}$ in Euclidean
space of dimension $k$. We adopt formulations
of Properties (L), (SL), and (U) from Section \ref{ss:circle}.
\begin{theorem}\label{thm:revol}
\mbox{}
\begin{enumerate}
\item
The spaces $\om=S^{k-1}$ and $\om=V^k$ for any $k\ge2$ have Properties
(L) and (U). Consequently, $\ms(\om,r)=1/r^2$.
\item
The sphere $S^k$ for $k\ge1$ and the ball $V^k$ for $k\ge3$
have Property (SL).
\item
The disc $V^2$ does not have Property (SL). Moreover,
there is an $r$-coloring of $V^2$ without monochromatic symmetric
subsets of measure more than $1/r^2$.
\end{enumerate}
\end{theorem}
Theorem \ref{thm:revol} strengthens Property (U) shown in
Section \ref{ss:circle} for the circle $S^1$, as now this property
is stated not only for bilateral but also for rotatory symmetry.
In general, Theorem \ref{thm:revol} states the upper bounds (i.e.\
Property (U) and negation of (SL)) for the fairly rich family
of all non-identical isometries of a figure. On the other hand,
the lower bounds (L) and (SL) will be actually proved for much more limited
family of symmetries consisting of reflections in hyperplanes.
This makes our results stronger, as decrease of admissible symmetries
can make the value $\ms(A)$ for $A\subseteq\om$ only smaller.
\subtitle{Property (L)} follows from the argument
common for all figures of revolution.
{}From the measure-theoretic point of view any figure of revolution $\om$
is representable as the product $\om=S^1\times\om_1$ of the circle
and some probability space $\om_1$. Correspondingly, $\om$ has the
product-measure $\mu=\mu_0\times\mu_1$, where $\mu_0$ denotes the
probability Lebesgue measure on $S^1$, and $\mu_1$ is the measure on $\om_1$.
Identifying the circle $S^1$ with the group $\rr/\zz$, for each $g\in S^1$
we consider symmetry $s_g(x,x_1)=(g-x,x_1)$, where $x\in S^1$ and
$x_1\in\om_1$. Notice that any such symmetry is reflection in a hyperplane.
\begin{proposition}\label{prop:geoml}
Every measurable set $A\subseteq S^1\times\om_1$ contains a symmetric subset
$B\subseteq A$ of measure $\mu(B)\ge\mu(A)^2$.
\end{proposition}
\begin{proof}
Let $B_g=A\cap s_g(A)$ be the maximum subset of $A$
symmetric with respect to a symmetry $s_g$. Denote
$A_{x_1}=\setdef{x\in S^1}{(x,x_1)\in A}$, a section of the set $A$.
Representing $\mu(B_g)$ as the integral of the characteristic function
of the set $B_g$, averaging it on $g$ and changing the order of integration,
we come to the equality
$\int_{S^1}\mu(B_g)\,d\mu_0(g)=\int_{\om_1}\mu_0(A_{x_1})^2\,d\mu_1(x_1)$.
Applying the Cauchy-Schwartz inequality, we obtain
\begin{equation}\label{eq:bgmua}
\int_{S^1}\mu(B_g)\,d\mu_0(g)=\int_{\om_1}\mu_0(A_{x_1})^2\,d\mu_1(x_1)\ge
\of{\int_{\om_1}\mu_0(A_{x_1})\,d\mu_1(x_1)}^2=\mu(A)^2.
\end{equation}
There must exist $g\in S^1$ such that $\mu(B_g)\ge\mu(A)^2$.
\end{proof}
\subtitle{Property (U).}
In fact, we are able to prove the bound $\ms(\om,r)\le1/r^2$ in a very
general form,
namely, for $\om$ being any compact subset of a connected Riemannian manifold.
The basic idea is the same as in the proof of Proposition \ref{prop:znu}
where we, in essence, show that large monochromatic symmetric subsets
in $\zn$ are avoidable by coloring $\zn$ at random. In a similar vein,
we partition $\om$ into small measurable pieces and color it piecewise
at random. Then we show that with nonzero probability there is no
monochromatic symmetric set whose measure exceeds $1/r^2+\epsilon$,
for a small $\epsilon>0$.
The obvious bottleneck in this scenario is that most often the family $\sym$ of
symmetries is infinite. Nonetheless, we manage to approximate $\sym$
by its finite subset in the metric
$\rho(s_1,s_2)=\sup_{x\in\om}\mathit{dist}(s_1(x),s_2(x))$,
where $\mathit{dist}$ denotes the distance between two points in $\rr^k$.
The complete proof contains some subtleties and is given in \cite{BVV}.
\subtitle{Property (SL)} was already stated in Section \ref{ss:circle}
for the circle $S^1$. For spheres and balls in higher dimensions
we use a different argument.
To facilitate the exposition, we prove the claim 2
of Theorem \ref{thm:revol} only for the sphere $S^2$.
\begin{proposition}
Every subset $A\subset S^2$ of measure $0<\mu(A)<1$
contains a symmetric subset $B$ of measure $\mu(B)>\mu(A)^2$.
\end{proposition}
\begin{proof}
Let $D_\delta(x)$ be the spherical disc of radius $\delta$
with center at the point $x\in S^2$. By the Lebesgue
theorem on density \cite[theorem 2.9.11]{Fed}, for almost all $x$ we have
$\lim_{\delta\to0}\frac{\mu(A\cap D_\delta(x))}{\mu(D_\delta(x))}=\chi_A(x)$,
where $\chi_A$ is the characteristic function of $A$.
Therefore, $A$ contains a point $N$ with
\begin{equation}\label{eq:lim}
\lim_{\delta\to0}\frac{\mu(A\cap D_\delta(N))}{\mu(D_\delta(N))}=1.
\end{equation}
Choose spherical coordinates $(x,x_1)$ on $S^2$, putting the north pole
at the point $N$. Norm the coordinates so that the longitude $x$
lies on the circle $S^1$ and the latitude $x_1$ lies in the segment
$I=[-1,1]$. We adhere to our previous convention that $S^1=\rr/\zz$
with the probability Lebesgue measure $\mu_0$.
For the appropriate choice of probability measure $\mu_1$
on $I$, the sphere can be identified in the measure-theoretic sense
with the product $S^2=S^1\times I$.
For every $g\in S^1$ we consider symmetry $s_g(x,x_1)=(g-x,x_1)$,
which is reflection in a plane.
Consider a symmetric set $B_g=A\cap s_g(A)$ and prove by reductio ad absurdum
that for some $g\in S^1$
the strong inequality $\mu(B_g)>\mu(A)^2$ is true.
Recall the relation \refeq{bgmua} in the proof of Proposition \ref{prop:geoml}.
It follows that if $\mu(B_g)\le\mu(A)^2$ for all $g$, then
$$
\int_{I}\mu_0(A_{x_1})^2\,d\mu_1(x_1)=
\of{\int_{I}\mu_0(A_{x_1})\,d\mu_1(x_1)}^2=\mu(A)^2.
$$
The latter implies $\mu_0(A_{x_1})\equiv\mu(A)$ almost everywhere on $I$.
Therefore, for every measurable set $D\subset S^2$ of kind $D=S^1\times I_1$
with $I_1\subset I$ we have
$$
\mu(A\cap D)=\int_{I_1}\mu_0(A_{x_1})\,d\mu_1(x_1)=\mu(A)\cdot\mu(D).
$$
Applying this equality to $D=D_\delta(N)$, we have
$\frac{\mu(A\cap D_\delta(N))}{\mu(D_\delta(N))}=\mu(A)$
for all $\delta>0$. By \refeq{lim} we get $\mu(A)=1$, a contradiction.
\end{proof}
\subtitle{Violation of (SL).} In the rest of this section we prove
the claim 3 of Theorem \ref{thm:revol} showing that
the disc $V^2$ is an exception for which Property (SL) is false.
\begin{proposition}
For any $0\le\alpha\le1/2$ there is a set $A\subset V^2$ of measure
$\mu(A)=\alpha$ without symmetric subsets whose measure exceeds $\alpha^2$.
\end{proposition}
\begin{proof}
Instead of the disc $V^2$, it will be technically more convenient for us
to deal with the space $V=S^1\times S^1$ supplied with the product measure
$\mu_0\times\mu_0$, where $\mu_0$ is the Lebesgue measure on the circle
$S^1=\rr/\zz$. For this purpose we establish $f\function V{V^2}$,
a one-to-one mapping from $V$ onto the disc $V^2$ with the center
pricked out, that will preserve measure and symmetry.
We describe a point in the
space $V$ by a pair of coordinates $(x_1,x_2)$ with $x_1\in(0,1]$ and
$x_2\in(0,1]$, whereas for the disc $V^2$ we use polar coordinates
$(\rho,\phi)$ with $\rho\in[0,\pi^{-1/2}]$ and $\phi\in(0,2\pi]$.
We set $f(x_1,x_2)=(\rho,\phi)$ iff
$x_1=\phi/(2\pi)$ and $x_2=\pi\rho^2$.
To explain the geometric sense of the correspondence $f$, let us identify
$S^1$ with $(0,1]$ and regard the square $V=(0,1]\times(0,1]$
as the development of a cylinder on a plane. Then a longitudinal section of
the cylinder is carried by $f$ onto a radius of the disc. A cross section
is carried onto a concentric circle so that the area below the section
is equal to the area within the circle. It follows that a set $X\subseteq V^2$
is measurable iff so is $f^{-1}(X)$, and both have the same measure.
The correspondence $f$ preserves symmetry in the following sense.
For every admissible symmetry $s$ of the disc $V^2$ there is a
transformation $s'$ of the space $V$ such that the equality $s(X)=X$
for $X\subseteq V^2$ is equivalent with the equality $s'(f^{-1}(X))=f^{-1}(X)$.
Every admissible symmetry of the disc is either a rotation around
the center or a reflection in a diameter. If $s$ is the rotation by
angle $2\pi g$, then $s'$ is definable by $s'(x_1,x_2)=(g+x_1,x_2)$
(for the cylinder this is a rotation around its vertical axis).
If $s$ is the reflection in the diameter $\phi=\pi g$, then
$s'(x_1,x_2)=(g-x_1,x_2)$ (for the cylinder this is reflection in one of
its vertical planes of symmetry).
Thus, it suffices to find a set $A\subset V$ of measure $\alpha$
but without $s'$-symmetric subsets of measure more than $\alpha^2$.
To do so, we fix an arbitrary set $H\subset S^1$ of measure $\mu_0(H)=\alpha$
so that $H$ is completely contained in some semicircle. Then we
define $A=\setdef{(x_1,x_2)}{x_1+x_2\in H}$.
It is not hard to see that $A$ has no subset symmetric with respect to
any symmetry $s'(x_1,x_2)=(g+x_1,x_2)$. Compute the measure
of the maximum subset of $A$ symmetric with respect to
a symmetry $s'(x_1,x_2)=(g-x_1,x_2)$. We have
\begin{eqnarray*}
\mu(A\cap s'(A))=\int_{S^1}\mu_0\of{\setdef{x_1\in S^1}%
{x_1+x_2,\,g-x_1+x_2\in H}}\,d\mu_0(x_2)\\
=\int_{S^1}\mu_0(H\cap(g+2x_2-H))\,d\mu_0(x_2)=\mu_0(H)^2=\alpha^2.
\end{eqnarray*}
The proposition follows.
\end{proof}
The above argument can be easily extended to construct
an $r$-coloring of the disc
without monochromatic symmetric subsets of measure more than $1/r^2$.
It suffices to apply the transformation $f$ to the partition
$V=A_1\cup\ldots\cup A_r$, where
$$
A_i=\setdef{(x_1,x_2)}{\frac{i-1}r