A Ramsey Treatment of Symmetry

T. Banakh^{∗} O. Verbitsky^{∗} ^{†} Ya. Vorobets

Department of Mechanics and Mathematics Lviv University, 79000 Lviv, Ukraine

                     E-mail: tbanakh@franko.lviv.ua

Submitted: November 8, 1999; Accepted: August 15, 2000.

But seldom is asymmetry merely the absence of symmetry. Hermann Weyl, “Symmetry”

Abstract

Given a space Ω endowed with symmetry, we define ms(Ω, r) to be the maximum of m such that for any r-coloring of Ω there exists a monochromatic symmetric set of size at least m. We consider a wide range of spaces Ω including the discrete and continuous segments {1, …, 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, …, 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(Ω, 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.

MR Subject Number: 05D10

∗Research supported in part by grant INTAS-96-0753.

†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).

§ 0 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 Ω be a space with measure μ. Suppose that Ω is endowed with a family S of transformations s : Ω → Ω called symmetries. A set B ⊆ Ω is symmetric if s(B) = B for a symmetry s ∈ S. An r-coloring of Ω is a map χ : Ω → {1, 2, …, r}, where each color class χ^{−1}(i) for i ≤ r is assumed measurable. A set included into a color class is called monochromatic. In this framework, we address the value

ms(Ω, S, r) = inf_{χ} sup {μ(B) : B is a monochromatic symmetric subset of Ω} ,

where the infimum is taken over all r-colorings of Ω. Our analysis covers the following spaces with symmetry. § 1–2 Segments. S consists of central symmetries.

1 Discrete segment {1, 2, …, n}. μ is the cardinality of a set.

2 Continuous segment [0, 1]. μ is the Lebesgue measure. § 3 Abelian groups. S consists of “central” symmetries s_{g}(x) = g − x.

3.1 Cyclic group ℤ_{n}. μ is the cardinality of a set. Equivalently: the vertex set of the regular n-gon with axial symmetry. 3.2 Group ℝ/ℤ. μ is the Lebesgue measure. Equivalently: the circle with axial symmetry. 3.3 Arbitrary compact Abelian groups. μ is the Haar measure. A generalization of the preceding two cases.

§ 4 Geometric figures. S consists of non-identical isometries of Ω (including all central, axial, and rotational symmetries). μ is the Lebesgue measure.

4.1 Figures of revolution: disc, sphere etc.

4.2 Figures with finite S: regular polygons, ellipses and rectangles, their multidimensional analogs.

§ 5 analyses the cases when the value ms(Ω, S, r) is attainable with a certain coloring χ. § 6 suggests another view of the subject with focusing on the cardinality of monochromatic symmetric subsets irrespective of the measure-theoretic aspects. § 7 contains a list of open problems.

Techniques used for discrete spaces include a reduction to continuous optimization (Section 2.2), the probabilistic method (Proposition 2.6), elements of harmonic analysis (Proposition 3.4), an application of the Borsuk-Ulam antipodal theorem (Theorem 6.1). Continuous spaces are often approached by their discrete analogs (e.g. the segment and the circle are limit cases of the spaces {1, 2, …, n} and ℤ_{n}, respectively). In Section 4.1 combinatorial methods are combined with some Riemannian geometry and measure theory.

Throughout the paper [n] = {1, 2, …, n}. In addition to the standard o- and Onotation, we write Ω(h(n)) to refer to a function of n that everywhere exceeds c·h(n), for c a positive constant. The notation Θ(h(n)) stands for a function that is simultaneously O(h(n)) and Ω(h(n)). The relation f(n) ∼ 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 [1, 2, 3, 4, 5, 19, 20, 22] unless other sources are specified.

§ 1 Discrete segment [n]

1.1 Warm-up

A set B ⊆ ℤ such that B = g − B for an integer g is called symmetric (with respect to the center at rational point \frac{1}{2}g). Given a set of integers A, let MS(A) denote the maximum cardinality of a symmetric subset B ⊆ A. In the case that A ⊆ [n], notice the lower bound

MS(A) > \frac{|A|^{2}}{2n} .  (1)

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 \frac{1}{2}g is A ∩ (g − A). The cardinality of A ∩ (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.

Example 1.1 Primes – much symmetry. Let P_{≤n} denote the set of all primes in [n]. The prime number theorem says that |P_{≤n}| ∼ n/ log n. It follows by (1) that MS(P_{≤n}) = Ω(n/ log^{2} n). This simple estimate turns out to be not so far from the true value Θ(\frac{n log log n}{log^{2} n}) due to Schnirelmann [21] and Prachar [18].

Example 1.2 Squares – little symmetry. Let S_{≤n} denote the set of all squares in [n]. The Jacobi theorem says that if g = 2^{k}m 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 ≡ 1 (mod 4) of m over the number of its divisors t ≡ 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 [16]). Therefore, MS(S_{≤n}) = n^{O(1/ log log n)}.

Example 1.3 (Krückeberg [12]) A Sidon set – no symmetry. Given a prime p, define the set A_{p} = {a_{1}, …, a_{p}} by a_{i+1} = 2pi − (i^{2} mod p) + 1 for 0 ≤ i < p. This set turns out to be highly asymmetric, namely, MS(A_{p}) = 2. Really, assume that a_{i} + a_{j} = a_{i′} + a_{j′} with i ≤ j and i′ ≤ j′. From this it is easy to derive that

\{ \begin{matrix}i + j & = & i′ + j′ & (mod p) \\ i^{2} + j^{2} & = & (i′)^{2} + (j′)^{2} & (mod p) \end{matrix}

Since in the field 𝔽_{p} a system of the kind

\{ \begin{matrix}i + j & = & a \\ i^{2} + j^{2} & = & b \end{matrix}

can have only a unique solution i, j with i ≤ j, we conclude that i = i′ and j = j′, which proves the claim.

Sets A with MS(A) = 2, known as Sidon’s sets or B_{2}-sequences, were investigated by many authors (see [17, section 4.1] for survey and references). For a Sidon set A ⊆ [n] the estimate (1) implies |A| < 2\sqrt{n}. The stronger upper bound |A| ≤ \sqrt{n}(1+o(1)) is due to Erdős and Turán. Thus, the set A_{p} with the biggest p ≤ n, for which |A_{p}| = \sqrt{n}(1−o(1)), is nearly as dense in [n] as possible.

1.2 Ramsey setting

Given positive integers n and r, consider the value

MS(n, r) = min_{χ:[n]→[r]} max_{i≤r} MS(χ^{−1}(i)).  (2)

In other words, MS(n, r) is the maximum integer such that for any r-coloring χ of [n] there is a monochromatic symmetric subset B ⊆ [n] with |B| ≥ MS(n, r).

For comparison let us define M(n, r) in the same way with the only change that B is now an arithmetic progression. Clearly, M(n, r) ≤ MS(n, r). In this notation the van der Waerden theorem (see [11, 15]) says that M(n, r) → ∞ as n → ∞ for any fixed r, while the Berlekamp bound [6] reads to M(n, r) = O(log n). The function MS(n, r) proves to grow much faster.

Proposition 1.4 For every r, the sequence MS(n, r)/n converges as n increases, and its limit is at least 1/(2r^{2}).

Proof. Observe relations

MS(k + j, r) ≤ MS(k, r) + 2j,  (3)
MS(l · n, r) ≤ l · MS(n, r).  (4)

The first of them is obvious. To check the second, it suffices, given a coloring χ : [n] → [r], to consider the coloring χ′ : [ln] → [r] such that χ′(x) = χ(⌈x/l⌉).

Let j = m mod n. By (3) and (4) we have

\frac{MS(m, r)}{m} ≤ \frac{MS(m − j, r) + 2j}{m} ≤ \frac{MS(n, r)}{n} + \frac{2j}{m} .

Letting m go to the infinity while keeping n fixed, we obtain

lim sup_{m→∞} \frac{MS(m, r)}{m} ≤ \frac{MS(n, r)}{n} for any n.  (5)

Hence the upper and lower limits of MS(n, r)/n coincide, which implies the convergence. The estimate lim_{n→∞} MS(n, r)/n ≥ 1/(2r^{2}) follows from (1). □

Notice that relation (5) has an important consequence.

Corollary 1.5 lim_{n→∞} MS(n, r)/n exceeds no particular value MS(n, r)/n.

This fact suggests a way for computing upper bounds on lim_{n→∞} MS(n, r)/n as tight as desired. Unfortunately, computing MS(n, r)/n seems not to be a feasible task for big n. Nonetheless, in Section 2.2 we achieve some speed-up in approaching the value lim_{n→∞} MS(n, r)/n.

1.3 General framework and the limit case of [n]

The following definition gives the background for all further considerations. In particular, it will allow us to characterize the limit of MS(n, r)/n.

Definition 1.6

• Let U be a space with measure μ.

• The space U is assumed to be endowed with a family S of one-to-one maps of U onto itself, that are measurable and preserve the measure. These maps will be called admissible symmetries.

• A set B ⊆ U is called symmetric if s(B) = B for some symmetry s ∈ S.

• Given A ⊆ U, define

ms(A) = sup {μ(B) : B is a symmetric measurable subset of A} .

• We consider a set Ω ⊆ U with μ(Ω) = 1, i.e. (Ω, μ) is a probability space.

• Let r ≥ 2. An r-coloring of Ω is a map χ : Ω → [r] such that each color class χ^{−1}(i) for i ≤ r is measurable. A subset of Ω is called monochromatic if it is included into a color class.

• Define

ms(Ω, r) = inf_{χ} max_{i≤r} ms(χ^{−1}(i)),

where the infimum is taken over all colorings of Ω.

To avoid any ambiguity in the presence of several families of admissible symmetries, we will sometimes use more definite notation ms(Ω, S, r). The notation ms should be recognized as an abbreviation of “the maximal measure of a monochromatic symmetric subset”.

For example, consider Ω = [n] in U = ℤ. Let μ(x) = 1/n for every x ∈ U. Let S consist of central symmetries s(x) = g − x with center at point g/2 for arbitrary integer g. Obviously, ms([n], r) = MS(n, r)/n.

Let Ω = [0, 1] now be the unitary segment. Considering the universe U = ℝ with the Lebesgue measure and central symmetries with center at any real point, we obtain the definition of the value ms([0, 1], r). Proposition 1.4 can be made more precise.

Theorem 1.7 lim_{n→∞} ms([n], r) = ms([0, 1], r). □

Estimation of ms([0, 1], r) will be our concern in the next section.

§ 2 Continuous segment [0, 1]

In this section we estimate ms([0, 1], r) for r = 2 and describe the asymptotic behavior of this value for r → ∞.

Theorem 2.1

(1) \frac{1}{4 + \sqrt{6}} ≤ ms([0, 1], 2) ≤ \frac{5}{24}.

(2) ms([0, 1], r) ∼ \frac{c}{r^{2}} for a constant \frac{1}{2} ≤ c ≤ \frac{5}{6}.

2.1 Lower bound on ms([0, 1], 2)

We prove the lower bound in Theorem 2.1 (1) by the double-counting argument. Given ϵ > 0, 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) + ϵ. Consider Cartesian squares A_{1}^{2} and A_{2}^{2} in a plane. Obviously,

μ^{2}(A_{1}^{2} ∪ A_{2}^{2}) = μ(A_{1})^{2} + (1 − μ(A_{1}))^{2} ≥ 1/2.  (6)

We now have to bound the left hand side of (6) from above. Define S(a, b) = {(x, y) ∈ [0, 1]^{2} : a ≤ x + y ≤ b}. Let 0 < t < 1 be a parameter whose value will be chosen later. We split the square [0, 1]^{2} into three parts S(0, t), S(t, 2−t), and S(2−t, 2), and estimate the area of intersection of A_{1}^{2} ∪ A_{2}^{2} with each part separately.

Consider first the intersection with the strip S(t, 2 − t). From

μ ((A_{1}^{2} ∪ A_{2}^{2}) ∩ S(g, g)) = \sqrt{2} (μ(A_{1} ∩ (g − A_{1})) + μ(A_{2} ∩ (g − A_{2})))
≤ 2\sqrt{2} (ms([0, 1], 2) + ϵ)

we infer that

μ^{2} ((A_{1}^{2} ∪ A_{2}^{2}) ∩ S(t, 2 − t)) ≤ 4(1 − t)(ms([0, 1], r) + ϵ).  (7)

To estimate the intersection with the triangle S(0, t), we use two lemmas.

Lemma 2.2 If B ⊆ [0, t], then μ(B) ≤ (t + ms(B))/2.

Proof. Consider the partition of B into three parts B′ = B ∩ (t − B), B′′ = (B \ B′) ∩ [0, t/2], and B′′′ = (B \ B′) ∩ [t/2, t]. Since sets B′ ∩ [0, t/2], B′′, and t − B′′′ do not intersect, we have μ(B′)/2 + μ(B′′) + μ(B′′′) ≤ t/2. As μ(B′) ≤ ms(B), we obtain μ(B) = μ(B′)/2 + μ(B′)/2 + μ(B′′) + μ(B′′′) ≤ ms(B)/2 + t/2. □

For B_{i} = A_{i} ∩ [0, t], Lemma 2.2 implies that μ(B_{i}) ≤ (t + ms([0, 1], 2) + ϵ)/2.

Lemma 2.3 Given a partition [0, t] = B_{1} ∪ B_{2}, suppose that max{μ(B_{1}), μ(B_{2})} ≤ s, where

s ≥ \frac{2}{3} t.  (8)

Then

μ ((B_{1}^{2} ∪ B_{2}^{2}) ∩ S(0, t)) ≤ s^{2} − (2s − t)/2.

An equivalent reformulation of the lemma is that the area of (B_{1}^{2} ∪ B_{2}^{2}) ∩ S(0, t) attains its maximum at the partition B_{1} = [0, s], B_{2} = [s, t]. This fact is not so obvious as it appears at first sight, say, it is not true if the condition (8) is violated. The proof is omitted in this exposition (see [5, lemma 6.12] for details).

Assuming that ms([0, 1], 2) < 1/3 (otherwise nothing to prove), we set

t = 3ms([0, 1], 2).

Apply Lemma 2.3 to the partition of [0, t] into B_{i} = A_{i} ∩ [0, t], i = 1, 2, with s = (t + ms([0, 1], 2) + ϵ)/2 = 2ms([0, 1], 2) + ϵ/2. As the condition (8) is fulfilled, we obtain

μ^{2} ((A_{1}^{2} ∪ A_{2}^{2}) ∩ S(0, t)) = μ^{2} ((B_{1}^{2} ∪ B_{2}^{2}) ∩ S(0, t)) ≤ \frac{7}{2} ms([0, 1], 2)^{2} + O(ϵ). (9)

The same bound holds true for the intersection (A_{1}^{2} ∪ A_{2}^{2}) ∩ S(2 − t, 2). Summing it up with (9) and (7), we obtain an upper bound on μ^{2}(A_{1}^{2} ∪ A_{2}^{2}) which after comparison with the lower bound (6) implies

10 ms([0, 1], 2)^{2} − 8 ms([0, 1], 2) + 1 ≤ O(ϵ).

As ϵ can be here arbitrarily small, the bound ms([0, 1], 2) ≥ 1/(4 + \sqrt{6}) follows.

2.2 Blurred colorings

For the remaining claims of Theorem 2.1 we need to involve some machinery. The idea is to move from our problem to its (hopefully) more tractable continuous version. For this purpose we modify the notion of coloring, allowing a point x ∈ Ω be colored by several colors mixed in arbitrary proportion. The fraction of each color at x is a non-negative real number, and the sum of all color fractions should equal 1. A similar concept of the fractional coloring of a graph is well known in combinatorics and discrete optimization. However our approach is different in some important aspects; in particular, our problem seems to fall out from the scope of linear or even convex programming. This justifies our choice of other term blurred coloring.

Definition 2.4

• Let a space U with measure μ, a set Ω ⊆ U, and a family of symmetries S satisfy the conditions of Definition 1.6. Assume in addition that every symmetry s ∈ S is involutive, i.e. s = s^{−1}.

• A blurred r-coloring of Ω is an arbitrary set of measurable functions {β_{i} : U → [0, 1]}_{i=1}^{r} such that ∑_{i=1}^{r} β_{i} = χ_{Ω}, where χ_{Ω} denotes the characteristic function of Ω.

• Given a measurable function f : U → ℝ, we define a map f ⋆ f : S → ℝ by

f ⋆ f(s) = ∫_{U} f(x)f(s(x)) dμ(x).

We use the notation ∥ · ∥ for the uniform norm on the set of functions from S to ℝ, i.e. ∥F ∥ = sup_{s∈S} |F (s)| for a function F : S → ℝ.

• An analog of the maximum measure of a monochromatic symmetric subset under a blurred coloring β = {β_{i}}_{i=1}^{r} is defined by

bms(Ω, r; β) = max_{i≤r} ∥β_{i} ⋆ β_{i}∥.

We set

bms(Ω, r) = inf_{β} bms(Ω, r; β),

where the infimum is taken over all blurred r-colorings of Ω.

Proposition 2.5 For every space Ω with involutive symmetries we have bms(Ω, r) ≤ ms(Ω, r) .

Proof-sketch. It suffices to observe that the notion of a blurred coloring generalizes the notion of a coloring that has been considered so far. An ordinary “distinct” coloring χ of Ω can be viewed as a blurred coloring β = {β_{i} : U → [0, 1]}_{i=1}^{r} taking on only two values 0 and 1 in the segment [0, 1] so that β_{i}(x) = 1 whenever χ(x) = i and β_{i}(x) = 0 otherwise. □

In a rather typical situation the values ms(Ω, r) and bms(Ω, r) turn out to be close to each other. To be more precise, suppose that Ω is a finite subset of the universe U, every finite set A ⊆ U has measure μ(A) = |A|/|Ω|, and the family of symmetries S consists of involutions. Given a symmetry s ∈ S, let Fix(s) = {x ∈ Ω : s(x) = x}.

Proposition 2.6 Let n = |Ω| and m = max_{s∈S} |Fix(s)|. Then

ms(Ω, r) ≤ bms(Ω, r) + \frac{m}{n} + (\frac{4 ln(r|S|)}{n − m})^{1/2} .  (10)

Proof-sketch. Since Ω is finite, bms(Ω, r) = bms(Ω, r; β) for some blurred coloring β = {β_{i}}_{i=1}^{r}. Define a random distinct coloring χ so that each point x ∈ Ω receives color i with probability β_{i}(x), independently of other points. With nonzero probability, every χ-monochromatic symmetric subset of Ω has measure no more than the right hand side of (10). □

2.3 Upper bound on ms([0, 1], 2)

Recall that by Corollary 1.5 the values ms([n], r) approximate ms([0, 1], r) from above. Let us show that the values bms([n], r) do the same as well (and likely even better).

Applying Propositions 2.5 and 2.6 to the discrete space [n], we obtain

bms([n], r) ≤ ms([n], r) ≤ bms([n], r) + o(1)  (11)

for a fixed r and n increasing. By Theorem 1.7 this implies that

bms([n], r) → ms([0, 1], r) as n → ∞.  (12)

Similarly to relations (3) and (4), one can prove their counterparts

bms([k + j], r) ≤ bms([k], r)\frac{k}{k+j} + \frac{2j}{k+j}
bms([ln], r) ≤ bms([n], r).

In the same vein as in Section 1.2, we derive from here that

lim_{m→∞} bms([m], r) ≤ bms([n], r)

for all n. By (12) we get

ms([0, 1], r) ≤ bms([n], r)  (13)

for all n. We gain from (13) even with small n. To prove the desired bound ms([0, 1], r) ≤ 5/24 we just set n = 4 and apply the following fact.

Lemma 2.7 bms([4], 2) ≤ 5/24.

Proof. Consider the blurred coloring β = {β_{1}, 1 − β_{1}} with

β_{1}(1) = \frac{1}{2}, β_{1}(2) = \frac{1}{2} − \frac{1}{2\sqrt{3}}, β_{1}(3) = \frac{1}{2} + \frac{1}{2\sqrt{3}}, β_{1}(4) = \frac{1}{2}.

Straightforward computation shows that bms([4], 2; β) = 5/24. □

2.4 Asymptotics of ms([0, 1], r) for r → ∞

In this section we prove the second statement of Theorem 2.1. We again prefer to deal with blurred colorings. In the case of the segment this is reasonable because

bms([0, 1], r) = ms([0, 1], r).  (14)

This equality is true because, simultaneously with (12), bms([n], r) → bms([0, 1], r) as n → ∞. The latter convergence is an analog of Theorem 1.7 and is provable by essentially the same argument (see [5] for details).

Our next goal is to check the inequality

lim sup_{r→∞} bms([0, 1], r)r^{2} ≤ bms([0, 1], k)k^{2}  (15)

for any fixed k. Given ϵ > 0, let β = {β_{i}}_{i=0}^{k−1} be a blurred k-coloring of [0, 1] with bms([0, 1], k; β) < bms([0, 1], k) + ϵ. Assume r = kt and define a blurred r-coloring χ = \{χ_{i}\}_{i=0}^{r−1} by χ_{i}(x) = \frac{1}{t}β_{i mod k}(x) for all x ∈ [0, 1]. Then

bms([0, 1], r) ≤ bms([0, 1], r; χ) = max_{0≤i<r} ∥χ_{i} ⋆ χ_{i}∥ =

max_{0≤i<k} \frac{1}{t^{2}} ∥β_{i} ⋆ β_{i}∥ = \frac{1}{t^{2}} bms([0, 1], k; β) < \frac{1}{t^{2}} bms([0, 1], k) + ϵ.

As ϵ can be arbitrarily small, we obtain relation bms([0, 1], r) ≤ \frac{k^{2}}{r^{2}} bms([0, 1], k) for r multiple of k. For arbitrary r, letting j = r mod k we obtain

bms([0, 1], r) ≤ bms([0, 1], r − j) ≤ \frac{k^{2}}{r^{2}} bms([0, 1], k) (\frac{r}{r − j} )^{2} ,

and inequality (15) follows.

From (15) we conclude that the upper and lower limits of bms([0, 1], r)r^{2} for r → ∞ coincide, and hence there exists lim_{r→∞} bms([0, 1], r)r^{2} = c. By equality (14) we obtain ms([0, 1], r) ∼ \frac{c}{r^{2}} .

The bound c ≥ 1/2 follows from the relation ms([0, 1], r) ≥ 1/(2r^{2}) (see Proposition 1.4 and Theorem 1.7). To prove the bound c ≤ 5/6 it suffices to put k = 2 in (15) and use inequalities bms([0, 1], 2) ≤ bms([4], 2) ≤ 5/24.

§ 3 Abelian groups

The notion of symmetry in ℤ or ℝ can be naturally extended to any Abelian group. More precisely, two families of symmetries look reasonable for an Abelian group G.

S – the family of “central” symmetries s : G → G of kind s(x) = 2g − x for some g ∈ G; S_{+} – the extended family of symmetries s : G → G of kind s(x) = g−x for some g ∈ G.

Given a finite group G, we consider the counting measure μ, i.e. μ(A) = |A|/|G| for any A ⊆ G. Given the group ℝ/ℤ, which can be viewed equivalently as the unitary circle in the complex plane, we consider the Lebesgue measure. Both cases are covered by the most general setting where we consider the Haar measure on a compact Abelian group G.

Therewith every compact Abelian group G can be regarded as a space with symmetry. To shorten notation, we set ms(G, r) = ms(G, S, r) and ms_{+}(G, r) = ms(G, S_{+}, r). As S ⊆ S_{+}, it holds ms(G, r) ≤ ms_{+}(G, r).

3.1 Cyclic group ℤ_{n}

Consideration of ℤ_{n} has a distinct geometric sense, since ℤ_{n} can be viewed as the vertex set of the rectangular n-gon. Then S consists of reflections in those axes that pass through a vertex, while S_{+} consists of all axial symmetries. Another reason why ℤ_{n} deserves a detailed treatment is that this is the model case for a wide variety of compact Abelian groups.

Notice that if n is odd, then S = S_{+} and hence ms(ℤ_{n}, r) = ms_{+}(ℤ_{n}, r). In this section we prove the following result.

Theorem 3.1 For a fixed number of colors r and n increasing we have

1/r^{2} ≤ ms(ℤ_{n}, r) ≤ ms_{+}(ℤ_{n}, r) ≤ 1/r^{2} + o(1).  (16)

Moreover, it holds the strict inequality

ms_{+}(ℤ_{n}, r) > 1/r^{2}.  (17)

Lower bounds. Recall that μ(A) = |A|/n is the density of a set A ⊆ ℤ_{n}. Let χ_{A} : ℤ_{n} → {0, 1} denote the characteristic function of A. Define

f(g) = μ (A ∩ (g − A)) = \frac{1}{n} ∑_{x∈ℤ_{n}} χ_{A}(x)χ_{A}(g − x)  (18)

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 3.1 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_{+}(ℤ_{n}, r) ≥ 1/r^{2} immediately follows from the statement below.

Proposition 3.2 Every set A ⊆ ℤ_{n} contains an S_{+}-symmetric subset of density at least μ(A)^{2}.

Proof. We apply the standard averaging argument. Using (18), we have

\frac{1}{n} ∑_{g∈ℤ_{n}} f(g) = \frac{1}{n} ∑_{x∈ℤ_{n}} χ_{A}(x)\frac{1}{n} ∑_{g∈ℤ_{n}} χ_{A}(g − x) = μ(A)^{2}.  (19)

Therefore, f(g) ≥ μ(A)^{2} for at least one g. □

The next two statements strengthen Proposition 3.2 in two different directions. The first of them implies the bound ms(ℤ_{n}, r) ≥ 1/r^{2} in Theorem 3.1.

Proposition 3.3 Every set A ⊆ ℤ_{n} contains an S-symmetric subset of density at least μ(A)^{2}.

Proof. For odd n the statement coincides with Proposition 3.2. Suppose that n = 2m. Let A_{0} and A_{1} be two parts of A consisting of even and odd numbers respectively. Averaging (18) on even arguments of f, we obtain

\frac{1}{m} ∑_{g∈ℤ_{m}} f(2g) = \frac{1}{n} ∑_{x∈ℤ_{n}} χ_{A}(x)\frac{1}{m} ∑_{g∈ℤ_{m}} χ_{A}(2g − x) =

\frac{1}{n} ∑_{x even} χ_{A_{0}}(x)\frac{1}{m} ∑_{x even} χ_{A_{0}}(x) + \frac{1}{n} ∑_{x odd} χ_{A_{1}}(x)\frac{1}{m} ∑_{x odd} χ_{A_{1}}(x) =

2μ(A_{0})^{2} + 2μ(A_{1})^{2} ≥ (μ(A_{0}) + μ(A_{1}))^{2} = μ(A)^{2}.

Therefore, f(2g) ≥ μ(A)^{2} for at least one g. □

It remains to prove the bound ms_{+}(ℤ_{n}, r) > 1/r^{2} in Theorem 3.1.

Proposition 3.4 Let A be a proper nonempty subset of ℤ_{n}. Then A contains an S_{+}- symmetric subset of density strictly more than μ(A)^{2}.

Proof. Assume, to the contrary, that f(g) ≤ μ(A)^{2} for all g. By (19) this implies f(g) ≡ μ(A)^{2}, where ≡ means equality everywhere on ℤ_{n}.

Let ϕ_{i} : ℤ_{n} → ℂ, for 0 ≤ i < n, be all characters of ℤ_{n}, that is, all homomorphisms from ℤ_{n} to ℂ. The system {ϕ_{i}}_{i=0}^{n−1} is an orthonormal basis of the Hilbert space L_{2}(ℤ_{n}) = ℂ^{ℤ_{n}} ≃ ℂ^{n}. This is a general property of characters of a compact Abelian group (see e.g. [13, § 38]), which in the case of ℤ_{n} reduces to the non-singularity of the Vandermonde matrix. We will suppose that ϕ_{0} ≡ 1.

Relation (18) shows that the function f is representable as the convolution χ_{A} ⋆ χ_{A}. Assuming the expansion χ_{A} = ∑_{i=0}^{n−1} c_{i}ϕ_{i} in the basis {ϕ_{i}}_{i=0}^{n−1}, we obtain f = ∑_{i=0}^{n−1} c_{i}^{2}ϕ_{i}. Comparing this with f ≡ μ(A)^{2}, from the uniqueness of expansion we conclude that c_{0}^{2} = μ(A)^{2}, while all the other coefficients c_{i} are zero. Thus, χ_{A} ≡ μ(A) and A must be either ∅ or ℤ_{n}, a contradiction. □

The upper bound in Theorem 3.1 is a direct consequence of Proposition 2.6 that in the case Ω = ℤ_{n} reads as follows.

Proposition 3.5 ms_{+}(ℤ_{n}, r) ≤ 1/r^{2} + O(\sqrt{log(rn)/n}).

Indeed, in notation of Proposition 2.6 we have m ≤ 2. Moreover, for any space Ω we have bms(Ω, r) ≤ 1/r^{2} as follows from consideration of the blurred coloring {β_{i}}_{i=1}^{r} with each β_{i} = 1/r everywhere on Ω.

3.2 Circle ℝ/ℤ

The group ℝ/ℤ is of especial interest because it can be alternatively viewed as the circle with axial symmetry. Of course, S = S_{+}.

Theorem 3.6 ms(ℝ/ℤ, r) = 1/r^{2}.

The proof of Theorem 3.6 borrows much from our analysis of ℤ_{n}. Similarly to ℤ_{n}, the following properties are true for Ω = ℝ/ℤ.

(L) Every measurable set A ⊆ Ω contains a symmetric subset B ⊆ A of measure μ(B) ≥ μ(A)^{2}.

(SL) Every measurable set A ⊂ Ω of measure 0 < μ(A) < 1 contains a symmetric subset B ⊆ A of measure μ(B) > μ(A)^{2}.

(U) ms(Ω, r) ≤ 1/r^{2}.

The proof of (L) is the same as that of Proposition 3.2, with integration instead of summation. As a consequence, ms(ℝ/ℤ, r) ≥ 1/r^{2}. Property (SL), the remarkable strengthening of (L), can be proved with using the Fourier expansion similarly to Proposition 3.4. Property (U) is provable by reduction to Proposition 3.5 on account of the following fact.

Proposition 3.7 Let H be a finite subgroup of a compact Abelian group G. Then ms_{+}(G, r) ≤ ms_{+}(H, r). □

We therefore have ms(ℝ/ℤ, r) ≤ ms_{+}(ℤ_{n}, r) ≤ \frac{1}{r^{2}} + O(\sqrt{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.

3.3 Arbitrary compact Abelian groups

Recall that we consider a compact Abelian group G along with its Haar measure μ. The topology of G is assumed Hausdorff, and μ is assumed to be a complete probability measure. This setting includes the groups ℤ_{n} with the counting measure and ℝ/ℤ with the Lebesgue measure as particular cases.

Theorem 3.8 Let [G]_{2} denote the subgroup of a group G consisting of the elements of order 2. Then ms(G, r) = ms_{+}(G, r) = 1/r^{2} provided μ([G]_{2}) = 0.

The lower bound ms(G, r) ≥ 1/r^{2} follows from Property (L) above that is true for every compact Abelian group Ω = G with respect to the family of symmetries S. Moreover, Property (SL) is true with respect to the extended family of symmetries S_{+}. To establish Property (U) with respect to S_{+}, the following relation is useful.

Proposition 3.9 Let H be a closed subgroup of a compact Abelian group G. Then ms_{+}(G, r) ≤ ms_{+}(G/H, r). □

Proving (U), we distinguish two cases. If there exists a homomorphism from G onto ℝ/ℤ, then (U) follows from Proposition 3.9 and Theorem 3.6. Otherwise, the structural theory of compact Abelian groups (see e.g. [14]) 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} ≃ D_{n} and μ(H_{n}) → 0. By Proposition 3.9, ms_{+}(G, r) ≤ ms_{+}(D_{n}, r). It remains to prove the upper bound ms_{+}(D_{n}, r) = 1/r^{2} + o(1), what can be done by the probabilistic method similarly to Proposition 3.5. 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 ℤ_{p^{n}}.

§ 4 Geometric figures

This section is devoted to symmetric geometric figures in Euclidean space ℝ^{k}. The general reference books on the topic are [8, 23]. 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 Ω is considered with the Lebesgue measure μ on Ω normed so that μ(Ω) = 1. The family of admissible symmetries consists of all non-identical isometries of ℝ^{k} leaving Ω invariant. We therewith have defined the value ms(Ω, r).

4.1 Figures of revolution

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 3.2.

Theorem 4.1

(1) The spaces Ω = S^{k−1} and Ω = V^{k} for any k ≥ 2 have Properties (L) and (U). Consequently, ms(Ω, r) = 1/r^{2}.

(2) The sphere S^{k} for k ≥ 1 and the ball V^{k} for k ≥ 3 have Property (SL).

(3) 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}.

Theorem 4.1 strengthens Property (U) shown in Section 3.2 for the circle S^{1}, as now this property is stated not only for bilateral but also for rotatory symmetry. In general, Theorem 4.1 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 ⊆ Ω only smaller. Property (L) follows from the argument common for all figures of revolution. From the measure-theoretic point of view any figure of revolution Ω is representable as the product Ω = S^{1} × Ω_{1} of the circle and some probability space Ω_{1}. Correspondingly, Ω has the product-measure μ = μ_{0} × μ_{1}, where μ_{0} denotes the probability Lebesgue measure on S^{1}, and μ_{1} is the measure on Ω_{1}. Identifying the circle S^{1} with the group ℝ/ℤ, for each g ∈ S^{1} we consider symmetry s_{g}(x, x_{1}) = (g − x, x_{1}), where x ∈ S^{1} and x_{1} ∈ Ω_{1}. Notice that any such symmetry is reflection in a hyperplane.

Proposition 4.2 Every measurable set A ⊆ S^{1} × Ω_{1} contains a symmetric subset B ⊆ A of measure μ(B) ≥ μ(A)^{2}.

Proof. Let B_{g} = A ∩ s_{g}(A) be the maximum subset of A symmetric with respect to a symmetry s_{g}. Denote A_{x_{1}} = {x ∈ S^{1} : (x, x_{1}) ∈ A}, a section of the set A. Representing μ(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 ∫_{S^{1}} μ(B_{g}) dμ_{0}(g) = ∫_{Ω_{1}} μ_{0}(A_{x_{1}})^{2} dμ_{1}(x_{1}). Applying the Cauchy-Schwartz inequality, we obtain

∫_{S^{1}} μ(B_{g}) dμ_{0}(g) = ∫_{Ω_{1}} μ_{0}(A_{x_{1}})^{2} dμ_{1}(x_{1}) ≥ (∫_{Ω_{1}} μ_{0}(A_{x_{1}}) dμ_{1}(x_{1}))^{2} = μ(A)^{2}. (20)

There must exist g ∈ S^{1} such that μ(B_{g}) ≥ μ(A)^{2}. □

Property (U). In fact, we are able to prove the bound ms(Ω, r) ≤ 1/r^{2} in a very general form, namely, for Ω being any compact subset of a connected Riemannian manifold. The basic idea is the same as in the proof of Proposition 3.5 where we, in essence, show that large monochromatic symmetric subsets in ℤ_{n} are avoidable by coloring ℤ_{n} at random. In a similar vein, we partition Ω 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} + ϵ, for a small ϵ > 0. The obvious bottleneck in this scenario is that most often the family S of symmetries is infinite. Nonetheless, we manage to approximate S by its finite subset in the metric ρ(s_{1}, s_{2}) = sup_{x∈Ω} dist(s_{1}(x), s_{2}(x)), where dist denotes the distance between two points in ℝ^{k}. The complete proof contains some subtleties and is given in [5]. Property (SL) was already stated in Section 3.2 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 4.1 only for the sphere S^{2}.

Proposition 4.3 Every subset A ⊂ S^{2} of measure 0 < μ(A) < 1 contains a symmetric subset B of measure μ(B) > μ(A)^{2}.

Proof. Let D_{δ}(x) be the spherical disc of radius δ with center at the point x ∈ S^{2}. By the Lebesgue theorem on density [10, theorem 2.9.11], for almost all x we have lim_{δ→0} \frac{μ(A∩D_{δ}(x))}{μ(D_{δ}(x))} = χ_{A}(x), where χ_{A} is the characteristic function of A. Therefore, A contains a point N with

lim_{δ→0} \frac{μ(A ∩ D_{δ}(N))}{μ(D_{δ}(N))} = 1.  (21)

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} = ℝ/ℤ with the probability Lebesgue measure μ_{0}. For the appropriate choice of probability measure μ_{1} on I, the sphere can be identified in the measure-theoretic sense with the product S^{2} = S^{1} × I. For every g ∈ 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 ∩ s_{g}(A) and prove by reductio ad absurdum that for some g ∈ S^{1} the strong inequality μ(B_{g}) > μ(A)^{2} is true. Recall the relation (20) in the proof of Proposition 4.2. It follows that if μ(B_{g}) ≤ μ(A)^{2} for all g, then

∫_{I} μ_{0}(A_{x_{1}})^{2} dμ_{1}(x_{1}) = (∫_{I} μ_{0}(A_{x_{1}}) dμ_{1}(x_{1}))^{2} = μ(A)^{2}.

The latter implies μ_{0}(A_{x_{1}}) ≡ μ(A) almost everywhere on I. Therefore, for every measurable set D ⊂ S^{2} of kind D = S^{1} × I_{1} with I_{1} ⊂ I we have

μ(A ∩ D) = ∫_{I_{1}} μ_{0}(A_{x_{1}}) dμ_{1}(x_{1}) = μ(A) · μ(D).

Applying this equality to D = D_{δ}(N), we have \frac{μ(A∩D_{δ}(N))}{μ(D_{δ}(N))} = μ(A) for all δ > 0. By (21) we get μ(A) = 1, a contradiction. □

Violation of (SL). In the rest of this section we prove the claim 3 of Theorem 4.1 showing that the disc V^{2} is an exception for which Property (SL) is false.

Proposition 4.4 For any 0 ≤ α ≤ 1/2 there is a set A ⊂ V^{2} of measure μ(A) = α without symmetric subsets whose measure exceeds α^{2}.

Proof. Instead of the disc V^{2}, it will be technically more convenient for us to deal with the space V = S^{1} × S^{1} supplied with the product measure μ_{0} × μ_{0}, where μ_{0} is the Lebesgue measure on the circle S^{1} = ℝ/ℤ. For this purpose we establish f : 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} ∈ (0, 1] and x_{2} ∈ (0, 1], whereas for the disc V^{2} we use polar coordinates (ρ, ϕ) with ρ ∈ [0, π^{−1/2}] and ϕ ∈ (0, 2π]. We set f(x_{1}, x_{2}) = (ρ, ϕ) iff x_{1} = ϕ/(2π) and x_{2} = πρ^{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] × (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 ⊆ 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 ⊆ 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π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 ϕ = π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 ⊂ V of measure α but without s′-symmetric subsets of measure more than α^{2}. To do so, we fix an arbitrary set H ⊂ S^{1} of measure μ_{0}(H) = α so that H is completely contained in some semicircle. Then we define A = {(x_{1}, x_{2}) : x_{1} + x_{2} ∈ 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

μ(A ∩ s′(A)) = ∫_{S^{1}} μ_{0} ({x_{1} ∈ S^{1} : x_{1} + x_{2}, g − x_{1} + x_{2} ∈ H}) dμ_{0}(x_{2})
= ∫_{S^{1}} μ_{0}(H ∩ (g + 2x_{2} − H)) dμ_{0}(x_{2}) = μ_{0}(H)^{2} = α^{2}.

The proposition follows. □

Figure 1: Construction of a bicoloring of the disc without monochromatic symmetric sets of measure more than 1/4.

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} ∪ … ∪ A_{r}, where

A_{i} = \{(x_{1}, x_{2}) : \frac{i − 1}{r} < x_{1} + x_{2} ≤ \frac{i}{r} or \frac{i − 1}{r} < x_{1} + x_{2} − 1 ≤ \frac{i}{r}\} .

For r = 2 this coloring is shown in Figure 1.

4.2 Figures with finite number of symmetries

Let G denote the group of all isometries of Euclidean space leaving a figure Ω invariant. Recall that for Ω we consider the family of symmetries S = G \ {id}, excluding the identity. Suppose now that G is finite. In this case, which includes regular polygons, rectangles, ellipses, and their multi-dimensional analogs, the previous techniques do not apply, and we need a completely different approach.

The first thing to be understood is that the exact geometric shape of Ω is not so relevant, as the value ms(Ω, r) eventually depends only on the group G. For instance, ms(Ω, r) is the same for the rectangle and the ellipse (independently of whether contours or areas are meant), for the parallelopiped and the ellipsoid etc.

To be more accurate, we assume that Ω contains a measurable subset I (a fundamental domain in the sense of [8]) such that all sI for s ∈ G are pairwise disjoint and μ(⋃_{s∈G} sI) = 1. In other words, {sI}_{s∈G} is a partition of Ω into N = |G| congruent pieces (points whose orbit under action of G is shorter than N are excluded from consideration, and their measure is assumed to be zero).

The group G itself can be regarded as a space with symmetries σ_{s} : G → G, for each s ∈ G defined by σ_{s}(g) = sg. Denote R = r^{N}. Let ϕ_{1}, …, ϕ_{R} : G → [r] be all possible r-colorings of G. Introduce notation M_{s,i}^{j} to denote the cardinality of the maximum σ_{s}-symmetric subset of G having color i under the coloring ϕ_{j}. Formally, M_{s,i}^{j} = | ⋂_{t=1}^{N} s^{t}ϕ_{j}^{−1}(i)|. In the natural way we will identify the orbit Gx = {s(x)}_{s∈G} of a point x ∈ I with the group G itself. Given an r-coloring χ of Ω, let I_{j} consist of those x ∈ I that χ induces the coloring ϕ_{j} on Gx. Set p_{j} = μ(I_{j}).

It is not hard to see that the maximum s-symmetric subset of Ω that receives color i under the coloring χ has measure ∑_{j=1}^{R} p_{j}M_{s,i}^{j}. Therefore

ms(Ω, r) = min_{(p_{j})} max_{\begin{matrix}s∈G\\{id\} \\ i≤r \end{matrix}} ∑_{j=1}^{R} p_{j}M_{s,i}^{j}  (22)

where the minimum is taken over all vectors (p_{1}, …, p_{R}) with 0 ≤ p_{j} ≤ 1/N and ∑_{j=1}^{R} p_{j} = 1/N. This equality, in particular, implies that ms(Ω, r) depends only on the group G of all isometries of Ω.

In fact, relation (22) shows that any geometric figure with finite symmetry group G is equivalent to the space Ω = G × [0, 1] with the uniform probability measure and slice-wise symmetries σ̂_{s} : Ω → Ω, for each s ∈ G \ {id} defined by σ̂_{s}(g, x) = (sg, x). For example, the regular n-gon in a plane can be identified with space D_{2n} ×[0, 1], where D_{2n} is the dihedral group; and the k-dimensional parallelopiped (as well as ellipsoid) can be identified with space ℤ_{2}^{k} × [0, 1].

Theorem 4.5

(1) Let p be the smallest prime divisor of n. Then for the regular n-gon Γ_{n} we have

ms(Γ_{n}, r) = \{ \begin{matrix}\frac{p−1}{p^{2}+2p−2} & if r = 2, \\ \frac{1}{3p^{2}+6} & if r = 3, \\ 0 & if r ≥ 4. \end{matrix}

(2) For the k-dimensional parallelopiped Π_{k} we have

ms(Π_{k}, r) = \frac{2^{k} − r}{r^{2}(2^{k} − 1)},

whenever r = 2^{l} for some 0 ≤ l < k. □

The proof of Theorem 4.5 has not been published yet and will appear elsewhere.

§ 5 Extremal colorings

Given an r-coloring χ of a space Ω with symmetry, let ms(Ω, r; χ) denote the supremum of μ(A) over all χ-monochromatic symmetric sets A ⊆ Ω. We call χ extremal if ms(Ω, r; χ) = ms(Ω, r). Similarly, a blurred r-coloring β is extremal if bms(Ω, r; β) = bms(Ω, r) (see Definition 2.4).

Obviously, no extremal colorings exist whenever both of Properties (U) and (SL) are met, in particular, for a wide variety of compact Abelian groups (see Section 3.3), for spheres of all dimensions, and for balls starting from dimension 3 (see Theorem 4.1). By Theorem 4.1 (3), an extremal coloring does exist for the 2-dimensional disc. We do not know what is the case for the space Ω = [0, 1].

Whenever bms(Ω, r) = 1/r^{2}, there exists the obvious extremal blurred coloring β = {β_{i}}_{i=1}^{r} with each β_{i} = 1/r everywhere on Ω. In particular, this is the case for the aforementioned spaces without extremal “distinct” colorings. For the segment [0, 1] the answer is not so obvious. The proof of the following result can be found in [5, theorem 7.2].

Theorem 5.1 There exists an extremal blurred r-coloring of [0, 1]. □

One could expect that extremal colorings, if exist, have some regular properties. Observe that color classes of the extremal coloring of the disc constructed in Section 4.1 are congruent (see Figure 1). In particular, if there is a symmetric set of one color with measure α, then there must be a symmetric set of any other color with the same measure. The latter property is actually fulfilled for all extremal colorings of the disc. This can be inferred from relation (20) in the proof of Proposition 4.2. It turns out that an analog of this property for blurred colorings is true for all spaces with symmetry. More precisely, if β = {β_{i}}_{i=1}^{r} is an extremal blurred r-coloring of a space Ω, i.e. bms(Ω, r) = ∥β_{i} ⋆ β_{i}∥ for some i ≤ r, then the same equality holds true for all i ≤ r.

§ 6 Infinitary issues

In this section we reconsider our original problem from another perspective. Modifying the setting of Definition 1.6 in a quantitative aspect, we become concerned with the cardinality of a monochromatic symmetric subset rather than with its measure. Given a space Ω with symmetry and a cardinal number κ, the proper question to ask now is what minimum (cardinal) number r of colors suffices to color Ω so that there were no monochromatic symmetric subsets of cardinality κ.

As first example, consider an Abelian group G with symmetries s_{g}(x) = g − x. Define ν(G) to be the minimal r such that there exists an r-coloring of G without infinite monochromatic symmetric subsets. The following result is proved in [3].

Theorem 6.1 ν(ℤ^{k}) = k + 1.

Proof. To show that ν(ℤ^{k}) ≤ k + 1, define a (k + 1)-coloring of ℤ^{k} with color classes A_{1}, …, A_{k+1} as follows. Consider a k-dimensional simplex S (a segment in ℝ, a triangle in ℝ^{2}, a tetrahedron in ℝ^{3} and so on). Fix a point p inside S. For a point z ∈ ℝ^{k}, let R(z) be the ray extending from p and passing through z. Let A_{i} consist of those lattice points z that R(z) intersects i-th face of S. Clearly, no A_{i} contains an infinite symmetric subset.

Now we need to prove that in any k-coloring of ℤ^{k} one can find an infinite monochromatic symmetric set. The one-dimensional case is trivial, and the two-dimensional case is still not so hard. We outline the proof for the first non-trivial case of k = 3 that can be easily extended to higher dimensions.

Suppose the contrary and consider a 3-coloring of ℤ^{3} without infinite monochromatic symmetric sets. Let C = {−1, 0, 1}^{3} be a discrete cube and K = [−m, m]^{3} a continuous cube in ℝ^{3}. It follows from our assumption that if m is large enough, then the boundary ∂K of K contains no two lattice points of the same color and symmetric with respect to a center in C. Fix such a cube K for some even m. Triangulate ∂K into isosceles rightangled triangles with vertices in all those lattice points of ∂K whose three coordinates are even. For convenience we choose this triangulation symmetric with respect to the origin (0, 0, 0).

Fix now a triangle T in ℝ^{2} and assign each of three colors to one of the vertices of T. Define a mapping h : ∂K → T by the following two conditions.

(1) h takes each lattice point of ∂K with all three coordinates even (i.e. each vertex of the triangulation) into the vertex of T with the same color.

(2) The mapping h is linear on each element of the triangulation. In other words, for every triangle T′ in the triangulation of ∂K, there is a linear transformation from ℝ^{3} to ℝ^{2} that induces h : T′ → T.

Clearly, h is uniquely determined by these two conditions and is continuous. Apply to h the Borsuk-Ulam antipodality theorem (see e.g. [7, theorem 13.6]). It follows that there exists a pair {x, −x} of antipodal points on ∂K with h(x) = h(−x). Let a, b, c ∈ ∂K be vertices of the triangle containing the point x (if x lies on the border between two or more triangles, we merely choose one of them). The triangle with vertices −a, −b, −c contains the point −x. By the linearity of h, images h(x) and h(−x) belong to the convex hulls of sets {h(a), h(b), h(c)} and {h(−a), h(−b), h(−c)} respectively. Consequently, the two convex hulls have nonempty intersection.

On the other hand, any point in {a, b, c} is symmetric to any point in {−a, −b, −c} with respect to a center in C. By our assumption, colors of {a, b, c} and colors of {−a, −b, −c} do not intersect and, hence, {h(a), h(b), h(c)} and {h(−a), h(−b), h(−c)} are disjoint sets of vertices of the triangle T. Therefore, convex hulls of these two sets are disjoint too, a contradiction. □

In [3] the cardinal ν(G) is computed for any Abelian group G. Other relevant questions are discussed in [1, 2]. The following statement has been recently proven by Igor Protasov and the first author [4] based on a version of the Erdős-Rado partition theorem.

Theorem 6.2 Assume that the generalized continuum hypothesis is true. Let G be an infinite Abelian group whose order exceeds a cardinal number κ. Then, for any coloring of G in finite number r of colors, G contains a monochromatic symmetric subset of cardinality at least κ. □

According to an earlier result of Protasov [20], for r ≤ 3 the theorem can be proved without the generalized continuum hypothesis. If κ is equal to the order of G, the statement is not true.

§ 7 Open problems

1. Improve our bounds on ms([0, 1], 2). In particular, a better upper bound can be attained just at cost of more calculation, namely, by more careful estimating particular values bms([n], 2) for n ≥ 4.

2. Does there exist an extremal blurred bicoloring {β_{1}, β_{2}} of [n] such that β_{1}(x) = β_{2}(n + 1 − x) for all x ∈ [n]? If so, this would facilitate computation of particular values bms([n], 2).

3. Improve our bounds on the constant c in Theorem 2.1 (2). In particular, can it be separated from 1/2?

4. How fast does the sequence ms([n], r) converge? In particular, is the bound |ms([n], r) − ms([0, 1], r)| = O(1/n^{α}) true for a positive α? How faster is convergence of bms([n], r)?

5. Does there exist an extremal coloring of the segment [0, 1]? In particular, is the equality ms([0, 1], r) = ms([n], r) possible for some n? Recall that the value ms([0, 1], r) = bms([0, 1], r) is achievable by a measurable blurred coloring of the segment. Is it achievable by a piecewise-continuous blurred coloring?

6. For a space Ω with symmetry and a real σ define

dms(Ω, σ) = inf {ms(A) : A ⊆ Ω, μ(A) ≥ σ} .

Clearly, ms(Ω, r) ≥ dms(Ω, 1/r). If Ω has Property (L), then dms(Ω, σ) ≥ σ^{2}. Thus, whenever Ω has both of Properties (L) and (U), we have the equality ms(Ω, r) = dms(Ω, 1/r). Is this equality true for Ω = [0, 1]?

7. (P. Erdős, A. Sárközy, V. T. Sós [9]) Given an r-coloring χ : [n] → [r], let S(g) denote the sum of the cardinalities of all monochromatic sets symmetric with respect to \frac{1}{2}g, i.e., S(g) = ∑_{i=1}^{r} |χ^{−1}(i) ∩ (g − χ^{−1}(i))|. Does there exist a positive constant c(r) such that, for every r-coloring of [n], the bound S(g) ≥ c(r)g is true for almost all even integers g not exceeding n? A statement of such a kind is proven in [9] with the bound S(g) ≥ 2. This cannot be extended to odd integers g, because if χ colors all even numbers in [n] and all odd numbers in [n] in two different colors, then S(g) = 0 for every odd g.

8. The notion of symmetry can be extended also over any non-Abelian group G. Namely, the symmetry s_{g} : G → G with respect to an element g can be defined by s_{g}(x) = gx^{−1}g. As every compact topological group has the unique probability Haar measure, for any group G of this class it makes sense to consider the value ms(G, r). For instance, consider the group SO(3) of orientation-preserving rotations of the 3dimensional space. What is ms(SO(3), 2) equal to? We can suggest the bounds 1/16 ≤ ms(SO(3), 2) ≤ 1/4.

9. Let P be the family of all orientation-preserving involutive symmetries of the sphere S^{2}, i.e. all its axial symmetries. What is ms(S^{2}, P, r) equal to? How far from the true value is the upper bound 1/r^{2}? Notice that P contains the group ℤ_{2}^{2}, which is generated by rotations of 180^{∘} around three pairwise perpendicular axes. It follows that ms(S^{2}, P, r) ≥ ms(ℤ_{2}^{2} ×[0, 1], r), where the space ℤ_{2}^{2} ×[0, 1] is considered with slice-wise symmetries as in Section 4.2. Applying Theorem 4.5 (2) for k = 2, we obtain the lower bound ms(S^{2}, P, 2) ≥ 1/6.

10. Compute ms(Ω, r) for convex regular polyhedra in ℝ^{k}. This research program is of great interest even if restricted to particular directions. For example, it would be desirable to know ms(Δ_{k}, r) for the regular k-dimensional simplex Δ_{k}. Equivalently one can consider the space S_{k} ×[0, 1], where S_{k} is the symmetric group of degree k. Another interesting direction is to compute ms(Ω, r) for all five Platonic solids in ℝ^{3}.

11. (R. I. Grigorchuk) Let F_{2} be a free group of rank 2. Compute ν(F_{2}) for the symmetries as in Problem 8.

12. Call a subset E of an Abelian group G essential if for every coloring of G in less than ν(G) colors the group G contains an infinite subset A symmetric with respect to a point g in E (i.e. A = 2g − A). For example, the proof of Theorem 6.1 shows that the 27-element cube {−1, 0, 1}^{3} is an essential set in ℤ^{3}. Let ρ(G) denote the minimum cardinality of an essential set in G. The problem is to compute or to estimate ρ(ℤ^{k}). We know the bounds k(k + 1)/2 ≤ ρ(ℤ^{k}) < 2^{k}, where the lower bound is the precise value for k = 1, 2, 3 (see [2]).

13. Is Theorem 6.2 provable in ZFC? In particular, can one prove without additional set-theoretic assumptions that for every 4-coloring of ℝ and for every cardinal number κ < 𝔠 there exists a monochromatic symmetric set A ⊂ ℝ of cardinality at least κ?

14. Let M(n) be the maximum M such that every sequence v_{0}, v_{1}, …, v_{n} of points in ℤ^{2} with each difference v_{i+1}−v_{i} being either (0, 1) or (1, 0) contains an M-point centrally symmetric subset. What is asymptotics of M(n)? We only know that 2 log n − O(1) ≤ M(n) ≤ (7 + o(1))\sqrt{n} (see [22]).

Acknowledgments

We appreciate the contribution of Igor Protasov, whose results and questions gave us an inspiration for this research. The second author is greatly indebted to the Department of Information Systems at Vienna University of Technology for hospitality during his work on this survey.

References

[1] T. Banakh. On asymmetric colorings of Abelian groups. In: Paul Erdős and his Mathematics. Research Communications of the conference held in the memory of Paul Erdős, July 4–11, 1999, Budapest, Janos Bolyai Mathematical Society, 30–32.

[2] T. Banakh. On a cardinal group invariant related to partitions of Abelian groups (in Russian). Mat. Zametki, 64(3):341–350, 1998. English translation in Math. Notes, 64(3):295–302, 1998.

[3] T. Banakh and I. Protasov. Asymmetric partitions of Abelian groups (in Russian). Mat. Zametki, 66(1):10–19, 1999. English translation in Math. Notes, 66(1):8–15, 1999.

[4] T. Banakh and I. Protasov. Symmetry and colorings: some results and open problems. Voprosy Algebry, 2000, to apppear.

[5] T. Banakh, Ya. Vorobets, and O. Verbitsky. Ramsey-type problems for spaces with symmetry (in Russian). Izvestiya Ross. Akad. Nauk, Ser. Mat. (Russian Academy of Sciences. Izvestiya. Mathematics), 2000, to appear.

[6] E. R. Berlekamp. A construction of partitions which avoid long arithmetic progressions. Canad. Math. Bull., 11:409–414, 1968.

[7] A. Björner. Topological methods. In Handbook of Combinatorics, chapter 34, pages 1819–1872. Elsevier Publ., 1995.

[8] H. S. M. Coxeter. Introduction to geometry. 2nd ed., New York etc.: John Wiley and Sons, 1969.

[9] P. Erdős, A. Sárközy, V. T. Sós. On a conjecture of Roth and some related problems I. In Irregularities of partitions, Pap. Meet., Fertod/Hung. 1986. Algorithms and Combinatorics 8, pages 47–59, 1989.

[10] H. Federer. Geometric measure theory. Berlin-Heidelberg-New York: Springer-Verlag, 1969.

[11] R. L. Graham, B. L. Rothschild, and J. H. Spencer. Ramsey theory. 2nd ed., Wiley-Interscience Series in Discrete Mathematics and Optimization. New York etc.: John Wiley & Sons, 1990.

[12] F. Krückeberg. B_{2}-Folgen und verwandte Zahlenfolgen. J. Reine Angew. Math., 206:53–60, 1961.

[13] L. H. Loomis. An introduction to abstract harmonic analysis. Toronto-New York-London: D. Van Nostrand Company, 1953.

[14] S. A. Morris. Pontryagin duality and the structure of locally compact Abelian groups. London Mathematical Society Lecture Note Series 29. Cambridge University Press, 1977.

[15] J. Nešetřil. Ramsey theory. In Handbook of Combinatorics, chapter 25, pages 1331–1403. Elsevier Publ., 1995.

[16] J.-L. Nicolas and G. Robin. Majorations explicites pour le nombre de diviseurs de N. Canad. Math. Bull., 26:485–492, 1983.

[17] C. Pomerance and A. Sárközy. Combinatorial number theory. In Handbook of Combinatorics, chapter 20, pages 967–1018. Elsevier Publ., 1995.

[18] K. Prachar. On integers having many representations as a sum of two primes. J. London Math. Soc., 29:347–350, 1954.

[19] I. Protasov. Asymmetrically decomposable Abelian groups (in Russian). Mat. Zametki, 59(3):468–471, 1996. English translation in Math. Notes, 59(3):336–338, 1996.

[20] I. Protasov. Monochromatic symmetric subsets in the colorings of Abelian groups. Dopovidi Natsionalnoï Akademiï Nauk Ukraïny, 11:54–57, 1999.

[21] L. G. Schnirelmann. Über additive Eigenschaften von Zahlen. Math. Ann., 107:649– 690, 1933.

[22] O. Verbitsky. Symmetric subsets of lattice paths. INTEGERS: an Electronic Journal of Combinatorial Number Theory, Vol. 0, A05, 16 pages, 2000.

[23] H. Weyl. Symmetry. Reprint of the 1952 original. Princeton Science Library. Princeton, NJ: Princeton University Press, 1989.