# MATILDA: Inclusive Data Science Pipelines Design through
Computational Creativity

Genoveva Vargas-Solar, Santiago Negrete-Yankelevich, Javier A. Espinosa-
Oviedo,
Khalid Belhajjame, José-Luis Zechinelli-Martini
Fundación Universidad de las Américas, Puebla
Universidad Autónoma Metropolitana (Cuajimalpa)
CNRS, Univ Lyon, INSA Lyon, UCBL, LIRIS, UMR5205,69622 Villeurbanne, France
Université Paris Dauphine

###### Abstract

We argue for the need of a new generation of data science solutions that can
democratize recent advances in data engineering and artificial intelligence
for non-technical users from various disciplines, enabling them to unlock the
full potential of these solutions. To do so, we adopt an approach whereby
computational creativity and conversational computing are combined to guide
non-specialists intuitively to explore and extract knowledge from data
collections. The paper introduces MATILDA, a creativity-based data science
design platform, showing how it can support the design process of data science
pipelines guided by human and computational creativity.

## Introduction

Exploiting large amounts of data collected in various domains through data
science methods presents unprecedented economic and societal opportunities.
Data science methods are primarily dominated by AI-savvy users with profound
expertise in mathematical, statistical, numerical, and artificial intelligence
models. However, these methods respond to research questions and challenges
from other disciplines, with consumers with different expertise and little
knowledge of data science methods. Methods must go beyond the expertise of
data scientists towards non-technical users with diverse expertise for them to
be actionable. That is, engineering, humanities, social sciences, and any
discipline requiring experiments on data to answer research questions. This
new way of exploiting data calls for a new generation of data science
solutions that harness and democratise recent advances in data engineering and
AI for the benefit of users from non-technical disciplines, insulating them
from technical complexity while enabling them to unlock the full power that
these solutions can offer to meet the data analysis needs of their field.

The interaction and conversation of experts from various fields to address
transdisciplinary problems call for creativity111Creativity is defined as the
tendency to generate or recognise ideas, alternatives, or possibilities that
may be useful in solving problems, communicating with others, and entertaining
ourselves and others (https://en.wikipedia.org/wiki/Creativity). in designing
data science solutions from different perspectives, namely, algorithmic, data,
information technologies and trans-discipline non-data science users. Thus,
there is a need for creativity-based solutions that can democratise data
science that can guide non-specialists intuitively to explore data collections
and extract knowledge from them.

The approach we investigate in this paper to address the above issues combines
two strands, namely computational creativity, to allow users to explore
uncharted territory when designing their data analysis, and conversational
computing, to provide users with abstractions to steer and configure the data
analysis without having to delve into low technical details.

Accordingly, the remainder of the paper is organised as follows. The following
section gives a general overview of approaches contributing to model creative-
based processes and friendly design data science pipelines. It discusses how
both areas can provide novel ways of designing data science-driven solutions.
The section after that describes the challenges of modelling creative-driven
data science design processes. It gives the general lines of an approach that
can enhance and envision a new way of addressing analytics problems using data
and artificial intelligence models. The following section after that
introduces a creativity-based data science design platform. It describes the
general architecture and functions and shows how it can support the design
process of data science pipelines guided by human and computational
creativity. The final section concludes the paper and discusses future work.

## Related work

Addressing the creative design of data science pipelines to make them
inclusive for non-experts requires drawing from methods and results from three
areas: creative models, friendly data science and provenance. This section
gives an overview of the relevant results that provide a scientific background
to the project and help to contextualize our objectives.

Creativity-driven systems Artificial intelligence (AI) offers opportunities to
reify and transform how we think about human cognitive capabilities. In this
context, computational creativity (CC)222Computational creativity is the study
of building software that exhibits behaviour that would be deemed creative in
humans. Such creative software can be used for autonomous creative tasks, such
as inventing mathematical theories, writing poems, painting pictures, and
composing music (https://computationalcreativity.net, aims at studying human
creativity and building systems that perform in such a way as to be considered
creative. Concerning creativity, whether this cognitive capability is
individual or collective. CC has moved from the classic individualistic and
cognitive model of creativity (?) to a social and collective creativity model
(?; ?; ?; ?; ?; ?).

Collective-creativity models are concerned with understanding the roles and
tasks that different agents (both human and non-human) play in a process that
requires creativity and how creativity can be measured in this context (?; ?).
Co-creativity is an excellent approach to establishing efficient, context-
aware interactive systems and setting long-term programmes where solutions to
problems requiring human and machine collaboration can be studied.

CC has been widely applied in art with systems that promote “artificial”
creation. “The painting fool” is a system developed by Simon Colton that draws
portraits taking into account emotional information obtained from the subjects
being painted through a camera (?). Negrete-Yankelevich and Morales-Zaragoza
(?) propose a model to develop and assess creativity in computational agents
embedded in mixed teams. The Apprentice Framework model establishes a series
of roles (or levels of responsibility) agents can play within the group over
time with the possibility of ascent through the ladder as the system is
developed, acquiring thus more responsibility in the creative process. The
model also helps identify aspects of the product being produced, at which
point the agent is supposed to be creative. By keeping track of both
responsibilities and aspects, it is possible to plan and assess the
development of the system. Negrete-Yankelevich and Morales-Zaragoza (?)
propose a framework to create animatics. These animated storyboards constitute
an essential artefact in producing animations by a team of expert animators
that made an award-winning series of one-minute shorts for Mexican TV called
Imaginantes (Televisa, “Imaginantes* - YouTube.”). The system’s creativity is
measured by how well the overall creativity of the team is affected by the
system’s performance.

Developing friendly data science solutions.  Friendly data science systems
must provide intuitive and interactive access to data processing operations in
an agile and visual step-by-step manner (?). They should help a user to derive
conclusions about the data collection content and identify the potential
questions that data can help answer. Through conversational loops and
feedback, a friendly exploration and analysis system must calibrate the tasks
according to the data’s characteristics and the user’s expertise and
expectations. Through metadata collection and user profiling, an exploration
and analysis conversation loop should propose actions, insight, and results’
display (and visualisations) that assist the user in completing a given goal.

Discussion. We believe the collective CC can reproduce the collaborative
transdisciplinary conditions in which data science solutions are developed. It
can drive the proposal of data science solutions combining data, algorithms,
and computing resources to model complex systems and contribute to answering
research questions to understand and predict them. While computational
creativity and conversational techniques have proven effective, they have not
been explored with the design of exploratory data analysis pipelines.
Moreover, the two approaches are somewhat opposed because conversational
techniques tend to rely on known territories (i.e. previously explored data
manipulation and analysis actions). In contrast, computational creativity
allows for exploring unknown territories (data manipulation and analysis),
which may, in some cases, prove more effective.

Our work addresses two challenges. On the one hand, adapt and leverage both
techniques to design an efficient and exploratory data analysis pipeline. On
the other hand, strike the right balance when creating data analysis pipelines
between ’known’ prior data exploration and analysis actions and ’unknown’
creative actions.

## Creative process for designing data science driven solutions

Data science pipelines combining machine learning and deep learning are the
new query types with specific needs regarding how data must be structured and
managed. The “one all-fits-all” data structure and associated management
functions approach are no longer adapted for data science queries. Indeed,
every query has a specific objective (modelling, prediction), and its design
entirely depends on the input dataset and an initial research question (RQ).
The data science query is not based on an explicit knowledge of the data. It
includes tasks devoted to mathematically understanding the data; then, the
partial results of those tasks determine the design of other studies devoted
to the computation of a model representing some hidden knowledge. Given
statistical and machine learning methods and a target objective, data
scientists rely on libraries that provide methods that they combine to define
a data science pipeline. The results obtained by this pipeline are never
definite, and they are always, to some degree, close to the target.

To illustrate the design process of a DS pipeline, consider the following
scenario. Consider a trendy decision-making group willing to adopt a data-
driven approach for designing public policies to enhance citizens’ lives in
urban spaces and reduce energy and economic costs. Public policies are
intended to modify built environments to improve them from financial and well-
being perspectives. Decision-makers know that from the urbanism perspective,
small changes in the built environment can alter how people use the space. For
instance, increasing pedestrian areas in a city downtown close to restaurant
zones reduce CO2 footprint. Still, it impacts the influx of restaurant
customers in the area and lowers real estate prices. Customers can suddenly
start preferring restaurants close to parking slots. People living in the area
can have problems accessing it and park their cars close to home. The research
question is to which extent public policies can impact the quality of life of
different categories of citizens willing to evolve in a given urban area?.
Decision makers now call for data scientists’ creativity to provide studies
and mathematical evidence of the kind of urban changes to be considered in
public policies.

Designing a data science pipeline. Datasets and research questions drive DS
pipelines’ design. Through a simplified creative scenario using the main
phases of a DS pipeline: (1) collect or search for datasets that can be used
for answering a research question, and then (2) prepare them (explore, clean,
engineer) to feed one or several Artificial Intelligence (AI) models. (3)
Models are trained and tested with dataset fragments. These tasks are
calibrated recurrently until specific performance scores are reached. (4)
Results are constantly assessed and eventually considered good enough to be
interpreted by experts and conclude on answering the initial research question
to some extent.

Sketching a creative process, the elements to consider are: What data is
needed to answer the research question and develop a strategy to collect them?
How to transform the initial research question into a quantitative statement
that can be addressed by mathematical or AI models? Which models’ families can
be pertinent for answering the question? How to design a series of tasks where
data are processed? How to connect the results format with the research
question statement? How to determine whether results converge? How to decide
whether results are fair enough for considering an answer?

In the example, data scientists can decide to film civilians in the target
urban spaces to collect their behavioural patterns on how they occupy and
evolve along those spaces before and after implementing public spaces. Extract
behavioural patterns that imply designing a DS pipeline for processing videos
and detecting civilians, for example, using perceptrons (?) and behaviour
patterns within a series of scenes. The patterns can then be classified
according to properties that detect changes before and after implementing some
change. Other possibilities would be to run other data collection techniques
like questionnaires to describe urban civilians’ behaviour through
quantitative variables that can be correlated for detecting changes produced
after applying public policies. The possibilities are numerous, and they rely
on data scientists’ expertise, on the facilities or not for collecting certain
types of data (e.g., video vs questionnaires) and their knowledge of specific
AI models’ families.

Discussion Data Science and Machine Learning Environments provide all the
necessary AI models. They are supported by enactment stacks that deal with the
storage, fragmentation, indexing and distribution of the data required and
produced by the tasks composing a pipeline. What are the rules and strategies
to combine different components that can transform input data into models and
predictions that provide quantitative elements to answer initial research
questions?

Generative artificial intelligence 333According to the Bing chat-GPT and
validated by this paper’s authors: Generative AI refers to a category of
artificial intelligence (AI) algorithms that generate new outputs based on the
data they have been trained on (www.weforum.org/agenda/2023/02/generative-ai-
explain-algorithms-work/). has started to be consolidated into solutions that
give the illusion of creation through interactive and conversational
approaches 444Microsoft Deepspeed
https://github.com/microsoft/DeepSpeed/tree/master/blogs/deepspeed-chat.
Systems like chat-GPT, in its various versions, mimic conversational and
question-answering experiences intended to perform target tasks or produce
“new” content based on existing evidence. The principle of this system is
synthesising the creation process as an exercise of wrapping together
“content” with specific characteristics and considering some constraints to
produce artefacts that look, to some extent, novel.

In the case of DS pipelines, the first challenge is to model the creation
process behind them. How does someone (a domain expert) states a research
question such that a data-driven quantitative study can be run? How are data
collected and selected to answer such questions? Which comes first, data or
questions? How to conclude that given datasets representing observations of an
object of study are representative enough to produce a model or predict the
behaviour of that object? How is the human integrated into the loop and
intervenes in the design milestones of a DS pipeline?

Challenges and Open Issues. A computational-creativity based methodology for
designing DS pipelines should consider at least the following scientific
challenges and associated open problems:
\- Modelling hybrid (human and nonhuman) creativity-driven data science
pipelines’ design: propose a computational creativity model to represent end-
to-end pipeline design. The creativity model can integrate design patterns
like the ones presented in (?) (design, mutant shopping, chorus line,
simulation and approximating feedback, entertaining evaluations and no blank
canvas). Depending on the tasks to be designed within a DS pipeline, different
creativity patterns can best be adapted to address the task.
\- Define the interaction among humans designing a DS pipeline and artificial
system(s) that can take on tasks and propose results. Model the input/out
required to feed and expect to/from the system and the type of feedback to be
given by humans.
\- Intervene the process with an agent by selecting a relevant subprocess
where creativity would contribute significantly to the overall solution and
assess how it works. Then try other similar subprocesses and verify again.
This bottom-up approach would establish a practice to turn the overall process
into a friendly one in a stepwise fashion.
\- Collecting provenance and data from DS pipelines design tasks: implement
processes for data curation, annotation, identification, and quality control
in research.
\- Proposing an ad-hoc computational creativity tool for making DS science
pipelines’ design friendly for non-data scientists.

## Towards a Human in the loop creative platform for designing data science
pipelines

Figure 1: Matilda platform creation pipeline.

Figure 1 shows the general architecture of the MATILDA platform that assists
people with different expertise to follow a creative process for designing DS
pipelines given datasets and target research questions. The platform relies on
a step-by-step conversational approach based on our previous work (?) and
provides interaction entry points to allow humans feedback, validate and guide
the creative process. For each phase of a DS pipeline (data exploration and
preparation, fragmentation, training, testing and assessing), the platform
suggests possible scenarios that are adopted or not.

Our DS creativity platform allows us to study how overall creativity is
affected if computer systems take over different roles within the design of
data science pipelines. The platform provides a collaborative environment that
integrates an artificial actor within in the creative production process of DS
pipelines by data scientists.

## Conclusions and Future Work

The research and development market associated with data science is fuelling
the economies of countries in the world. Almost all sectors in the global
economies see data science as a promising alternative to develop original
solutions to critical societal problems and promote data-driven decision-
making processes that can create know-how and value. Yet, despite the
availability of datasets and technology for transforming any phenomenon
produced in reality into digital data and the variety of algorithms
(Mathematical and artificial intelligence models), the design of data science
solutions remains artisanal. The impact on person-hours and economic
investment is not anecdotic. The time has come to propose methodologies that
can formalise the design of data science solutions and model the “know-how”
developed by data scientists during the creation process. Besides, data
science addresses trans-disciplinary challenges. It is critical to bridge the
gap between technical vocabulary, tasks, and the vocabulary of other
disciplines and users with different expertise. This strategy will ensure the
usability and acceptability of solutions (i.e. pipelines). In summary, data
science must become inclusive and accessible to all. Our work addresses this
challenge by aiming to adopt computational creativity methods to model the
data science design process(es) that combine human and nonhuman creativity.

The platform MATILDA proposed in this paper is based on the original
methodologies that we propose. It contributes to creating data science
pipelines according to the expectations of knowledge discovery. It is
interesting for answering target research questions, the input data’s
characteristics and the data scientists’ models. Creativity-based
methodologies applied to data science will make it accessible and inclusive to
address increasingly complex problems humanity faces.

## References

  * [Bethaz et al. 2021] Bethaz, P.; Belhajjame, K.; Vargas-Solar, G.; and Cerquitelli, T.  2021\.  Ds4all: All you need for democratizing data exploration and analysis.  In 2021 IEEE International Conference on Big Data (Big Data), 4235–4242.  IEEE.
  * [Boden and others 2004] Boden, M. A., et al.  2004\.  The creative mind: Myths and mechanisms.  Psychology Press.
  * [Colton, Charnley, and Pease 2011] Colton, S.; Charnley, J. W.; and Pease, A.  2011\.  Computational creativity theory: The face and idea descriptive models.  In ICCC, 90–95.  Mexico City.
  * [Cruz-Esquivel and Guzman-Zavaleta 2022] Cruz-Esquivel, E., and Guzman-Zavaleta, Z. J.  2022\.  An examination on autoencoder designs for anomaly detection in video surveillance.  IEEE Access 10:6208–6217.
  * [Glines, Griffith, and Bodily 2021] Glines, P.; Griffith, I.; and Bodily, P. M.  2021\.  Software design patterns of computational creativity: A systematic mapping study.  In ICCC, 218–221.
  * [Goel and de Silva Garza 2010] Goel, A. K., and de Silva Garza, A. G.  2010\.  Special issue on artificial intelligence in design.  Journal of Computing and Information Science in Engineering 10(3).
  * [Gu and Amini Behbahani 2021] Gu, N., and Amini Behbahani, P.  2021\.  A critical review of computational creativity in built environment design.  Buildings 11(1):29.
  * [Kantosalo and Riihiaho 2019] Kantosalo, A., and Riihiaho, S.  2019\.  Experience evaluations for human–computer co-creative processes–planning and conducting an evaluation in practice.  Connection Science 31(1):60–81.
  * [Kantosalo, Toivanen, and Toivonen 2015] Kantosalo, A. A.; Toivanen, J. M.; and Toivonen, H. T. T.  2015\.  Interaction evaluation for human-computer co-creativity: A case study.  In Proceedings of the sixth international conference on computational creativity.  Brigham Young University.
  * [Maher 2010] Maher, M. L.  2010\.  Evaluating creativity in humans, computers, and collectively intelligent systems.  In Proceedings of the 1st DESIRE Network Conference on Creativity and Innovation in Design, 22–28.
  * [Maher 2012] Maher, M. L.  2012\.  Computational and collective creativity: Who’s being creative?  In ICCC, 67–71.
  * [Negrete-Yankelevich and Morales-Zaragoza 2013] Negrete-Yankelevich, S., and Morales-Zaragoza, N.  2013\.  e-motion: a system for the development of creative animatics.  Proceedings of the Fourth International Conference on Computational Creativity.
  * [Negrete-Yankelevich and Morales-Zaragoza 2014] Negrete-Yankelevich, S., and Morales-Zaragoza, N.  2014\.  The apprentice framework: planning and assessing creativity.  Proceedings of the Fifth International Conference on Computational Creativity.
  * [Sawyer 2011] Sawyer, R. K.  2011\.  Explaining creativity: The science of human innovation.  Oxford university press.


# Monochromatic non-commuting products

Matt Bowen  Mathematical Institute, Radcliffe Observatory Quarter, Woodstock
Road, Oxford OX2 6GG, England<EMAIL_ADDRESS>
(Date: April 2024)

###### Abstract.

We show that a finite coloring of an amenable group contains ‘many’
monochromatic sets of the form $\\{x,y,xy,yx\\},$ and natural extensions with
more variables. This gives the first combinatorial proof and extensions of
Bergelson and McCutcheon’s non-commutative Schur theorem. Our main new tool is
the introduction of what we call ‘quasirandom colorings,’ a condition that is
automatically satisfied by colorings of quasirandom groups, and a reduction to
this case.

The author is supported by Ben Green’s Simons Investigator Grant number 376201

##  1\. Introduction

In this paper we will be concerned with the following conjectures of Bergelson
and McCutcheon. In the following and throughout, a group is sufficiently non-
commutative if the centralizer subgroup of every element has infinite index.

######  Conjecture 1.1 ([BR09], Conjecture 2.3).

Suppose that a sufficiently non-commutative group is finitely colored. There
is a monochromatic set of the form $\\{x,y,xy,yx\\}$ with $xy\neq yx.$

######  Question 1.2 ([BM98], the paragraph before Theorem 3.4).

Suppose that a sufficiently non-commutative group is finitely colored. Is
there a sequence $x_{1},...,x_{k}$ with all possible products (in any order)
monochromatic and distinct?

While the above conjectures are still quite open for general groups (and the
free group on two generators in particular), a number of special cases have
been closely analyzed and resolved. Namely, Bergelson and McCutcheon [BM98,
BM07] were able to prove Conjecture 1.1 for colorings of infinite amenable
groups. For finite groups (which are always amenable), Sanders [San19] later
proved an analogous result, extending work of Bergelson and Tao [BT14], who
had proven a stronger density result in the more restrictive setting of finite
quasirandom groups. Similar results to Bergelson and Tao’s with good
quantitative bounds were also obtained by Austin [Aus15] and Tserunyan
[Tse23]. For Question 1.2, there appear to be no special cases where even the
$k=3$ case is fully known, with the main progress so far due to Bergelson,
Christopherson, Donaldson, and Zorin-Kranich, who proved a density version of
a weaker form the conjecture for infinite amenable quasirandom groups
[BCRZK16].

A peculiar aspect shared by all of the previously mentioned papers is that
they deduce their coloring results from a ‘non-commutative Roth theorem,’
i.e., a density results which controls the pattern $\\{x,xy,yx\\}.$ Moreover,
it appears that there was no previously known direct ‘coloring’ proof of any
special case of Conjecture 1.1. This is in contrast with most classical
results in Ramsey theory, where coloring results are typically much easier
than and known well in advance of their density counterparts. It has also
served as a major bottleneck in extending progress on Conjecture 1.1 and
Question 1.2 beyond the $k=2$ case (where non-commutative measure recurrence
results seem to quickly become elusive) and the setting of amenable groups
(where density stops being a viable tool altogether).

In this paper we give a direct coloring proof of the amenable case of
Conjecture 1.1 which extends to handle some of the previously unknown sub-
cases of Question 1.2.

######  Theorem 1.3.

Suppose that $G$ is an amenable group with $G$-invariant finitely additive
probability measure $\mu.$ In any $r$-coloring of $G$ we have

$\mu(\\{y:\mu(\\{x:\\{x,y,xy,yx\\}\textnormal{ is monochromatic}\\})>0\\})>0.$

More generally, for any $k$ we can find many monochromatic sets of the form

$\\{x_{i}\cdot x_{i+1}\cdot...\cdot x_{j},\overrightarrow{\prod_{a\in
I}}x_{a}\cdot x_{0}\cdot x_{1}\cdot...\cdot x_{j}:i\leq
j\in\\{0,...,k\\},I\subset\\{j+1,...,k\\}\\}.$

Note that one wishes to find a monochromatic set of size $15$ in the $k=3$
case of Question 1.2, corresponding to all products in any order of terms
$x,y,z.$ In this case, the second part of Theorem 1.3 finds a monochromatic
set of size $10,$ with the missing terms being $xz,zy,xzy,yxz,zyx.$

Up to keeping track of extra parameters, one can also obtain lower bounds on
the size of the sets in Theorem 1.3. The bounds this would give are fairly
poor and most likely far from optimal, so we will omit the details for ease of
exposition.

Using a more basic form of the same idea, we also make the following progress
on the non-amenable case of Conjecture 1.1.

######  Proposition 1.4.

In any finite coloring of a group we have

$\\{y:\\{x:\\{x,xy,yx\\}\textnormal{ is monochromatic}\\}\textnormal{ is
piecewise syndetic}\\}$

is piecewise syndetic.

A similar result was proven by Bergelson and Hindman in [BH92] using
idempotent ultrafilters. The argument we give here appears to be the first
combinatorial proof of this fact and primarily relies on a ‘piecewise syndetic
pigeonhole principle’ (see Proposition 5.3) which says that any piecewise
syndetic subset of an arbitrary group contains ‘many’ sets of the form
$\\{x,xy\\}.$ Unfortunately the notion of ‘many’ that appears here is less
robust than appears in the ‘density pigeonhole principle’ which applies to
amenable groups (see Lemma 2.1), and this is the main obstacle in extending
our argument to control the color of $y$ as well.

###  1.1. Techniques

The basic idea behind the proof of Theorem 1.3 was inspired by the author and
Sabok’s recent work [Bow22b, BS22] on finding monochromatic sets of the form
$\\{x,y,xy,x+y\\}$ in colorings of $\mathbb{N}$ and $\mathbb{Q},$ although the
execution of the idea is quite different in the present paper. The starting
point of these results is that it is fairly easy, using standard dynamical
color focusing arguments, to prove a weaker result controlling the color of
all terms excluding $y.$ From here one then argues that if the coloring is
‘sufficiently random’ then this color focusing argument can be upgraded to
also control the color of $y.$ Otherwise, the coloring must be fairly
structured and the desired conclusion can be deduced by exploiting this
structure.

The primary difference between the arguments in the present paper and those in
[Bow22b, BS22] comes from which definition of ‘sufficiently random’ is useful.
In [Bow22b, BS22] the useful structure vs randomness dichotomy came from the
dichotomy between thick and syndetic sets. While the thick case of the
arguments from those papers is applicable to the present problem, it seems
that syndeticity is a much less useful condition in the non commutative
setting.

Instead, the notion of randomness that we develop in the present paper is
related to the properties of colorings of what are known as quasirandom groups
in the finite setting [Gow08] and weak mixing [BF09] or minimally almost
periodic [Neu34] groups in the infinite setting. Gowers in the finite setting
[Gow08] and Bergelson and Furstenburg in the infinite setting [BF09] showed
that, when amenable, such groups behave psudorandomly in the sense that that
all of their large subsets contain roughly the expected number of finite
product sets of a given length, and moreover, that it is easy to ‘switch’
between any large sets via multiplication in the sense that if $A,B\subset G$
then there are roughly the expected number of $a\in A$ and $b\in B$ with
$ab\in A.$

Inspired by this, we will call a coloring of an arbitrary amenable group
quasirandom if every color class has roughly the expected number of finite
product sets of each length (see Section 3 for precise definitions) and deduce
that in such colorings it is very easy to switch between color classes via
multiplication in a sense similar to before. It turns out this latter property
is precisely what is needed to upgrade the color focusing proof that deals
with the configuration $\\{x,xy,yx\\}$ to also control the color of the $y$
term. This is explained in Section 4.1, where we prove Theorem 1.3 for
quasirandom colorings of amenable groups (and, consequently, arbitrary
colorings of amenable quasirandom groups).

From here we then need to reduce the proof of Theorem 1.3 to the case that the
coloring is quasirandom. This is done in Section 4.2, where we show that in an
arbitrary coloring $c$ of an amenable group $G$ there is a $D\subset G$ such
that $c$ is a quasirandom coloring of $G\setminus D$ and $G\setminus D$ is
invariant enough under multiplication to run the proof from Section 4.1.

##  2\. Notation and preliminaries

Throughout the paper, by $FP(x_{0},...,x_{k})$ we mean the set of all non-
repeating finite products of $x_{0},...,x_{k},$ with products written from
left to right in the order of the given indices. For example,
$FP(x_{0},x_{1})=\\{x_{0},x_{1},x_{0}x_{1}\\},$ while
$FP(x_{1},x_{0})=\\{x_{1},x_{0},x_{1}x_{0}\\}.$

If $S=\\{s_{1},...,s_{n}\\},$ by $FP(S)$ we mean $FP(s_{1},...,s_{n}).$ We
will only use this notation in cases where the identity of the elements
$s_{1},...,s_{n}$ is not important, and typically not specify anything about
$S$ besides its size.

By an $IP_{n}$ set we mean a set of the form $FP(S)$ for some $S\subset G$
with $|S|=n$. Recall that the finite unions theorem implies that for any
$r,n\in\mathbb{N}$ there is a $n^{\prime}\in\mathbb{N}$ such that any
$r$-coloring of an $IP_{n^{\prime}}$ set contains a monochromatic $IP_{n}$
subset.

We will also use left and right versions of the $\prod$ notation. Namely, if
$F\subset\\{1,...,n\\}$ then by $\overrightarrow{\prod}_{i\in F}x_{i}$ we mean
$x_{i_{1}}\cdot...\cdot x_{i_{|F|}},$ where $i_{1}<i_{2}<...<i_{|F|},$ and the
reverse for $\overleftarrow{\prod}.$

###  2.1. Amenability and recurrence

Throughout this paper, we say a group is amenable if it admits a finitely
additive propability measure $\mu$ that is $G$-invariant, i.e.,
$\mu(A)=\mu(gA)=\mu(Ag)$ for all $A\subset G$ and $g\in G.$ Our arguments will
in fact work for amenable semigroups, although we do not emphasize this. If
one prefers to avoid the use of such measures (whose existence in infinite
groups can depend on the axiom of choice), then up to passing to appropriate
Følner sub-sequences at various points of the argument one could replace the
use of the measures $\mu$ with densities along two sided Følner sequences.

The following ‘density pigeonhole principle’ will be the primary tool that
allows our proof to work for amenable groups and is just an elementary variant
of the Poincare recurrence theorem. A weaker analogue holds when replacing the
positive measure set with a piecewise syndetic set in a non-amenable group,
but that weaker variant is only enough to find monochromatic sets of the form
$\\{x,xy,yx\\},$ see Proposition 5.3.

######  Lemma 2.1.

Suppose that $\mu(A)>\varepsilon$ and $(y_{0},...,y_{k})$ is a sequence with
$k$ large enough depending on $\mu(A)$. There are $i<j$ such that
$y=y_{i}\cdot y_{i+1}\cdot...\cdot y_{j}$ satisfies $\mu(A\cap
Ay^{-1})>\varepsilon^{2}/2.$ Similarly, there are $i^{\prime}<j^{\prime}$ such
that $y^{\prime}=y_{i^{\prime}}\cdot...\cdot y_{j^{\prime}}$ satisfies
$\mu(y^{-1}A\cap A)>\varepsilon^{2}/2.$

This lemma is well known, and its proof can be found in Bergelson’s survey
article [Ber00] as Proposition 2.2. We repeat it here for convenience.

###### Proof.

We will only prove the version with right multiplication, as the version with
left multiplication follows from the analagous argument. Let $A_{0}=A$ and
$A_{i}=A\cdot(y_{0}\cdot...\cdot y_{i-1})^{-1}$ for $0<i\leq k+1$. So long as
$k$ is large enough, there are $i<j\leq k$ with $\mu(A_{i}\cap
A_{j})>\varepsilon^{2}/2.$ Note for $a\in A_{i}\cap A_{j},$ we have $a\cdot
y_{0}\cdot...\cdot y_{i-1}\in A$ and $a\cdot y_{0}\cdot...\cdot y_{j-1}\in A,$
and so for $y=y_{i}\cdot...\cdot y_{j-1}$ we have $\mu(A\cap
Ay^{-1})>\varepsilon^{2}/2.$ ∎

We will also need the following iterated version of the above fact, which
follows immediately from repeated applications of Lemma 2.1. The $r=1$ case is
also recorded in [Ber00] as Proposition 2.5.

######  Lemma 2.2.

Suppose that $\mu(A)>\varepsilon$ and that $k\in\mathbb{N}.$ There is a
$k^{\prime}\in\mathbb{N}$ depending only on $k$ and $\varepsilon$ such that if
$S_{1}^{\prime},...,S_{r}^{\prime}\subset G$ with
$|S_{i}^{\prime}|>k^{\prime},$ there are $S_{1}\subset
FP(S_{1}^{\prime}),...,S_{r}\subset FP(S_{r}^{\prime})$ such with $|S_{i}|=k$
and a set $B\subset A$ with $\mu(B)>(\varepsilon^{2}/2)^{rk}$ such that
$s_{i}B\subset A$ for any $s_{i}\in FP(S_{i}).$

###  2.2. ‘Many’ tuples

In order for our inductive arguments to go through we will often need to find
‘many’ tuples with a given property. We introduce the following notation to
make this precise.

######  Definition 2.3.

Given a property $P:G^{k}\rightarrow\\{0,1\\}$ we say that there are many
tuples $(x_{1},...,x_{k})\in G^{k}$ satisfying $P$ if

$\mu(\\{x_{1}\in G:\mu(\\{x_{2}\in G:...:\mu(\\{x_{k}\in
G:P(x_{1},...,x_{k})=1\\})>0\\}....\\})>0\\})>0.$

If there are many tuples $(x_{1},...,x_{k})$ with property $P,$ we say that
$(x_{1},...,x_{i})$ is a valid choice for $P$ if there are many
$(x_{i+1},...,x_{k})$ with $P(x_{1},...,x_{k})=1.$

If there are many tuples $(x_{1},...,x_{k})$ with property $P$ and
$(x_{1},...,x_{i})$ is a valid choice for $P$, we write

$X_{i+1}(x_{1},...,x_{i})=\\{x_{i+1}\in G:(x_{1},...,x_{i+1})\textnormal{ is a
valid choice for }P\\}.$

For example, we will say that a set $A$ contains many sets of the form
$\\{x_{0},x_{1},x_{0}x_{1}\\}$ if $\mu(\\{x_{0}\in G:\mu(\\{x_{1}\in
G:x_{0},x_{1},x_{0}x_{1}\in A\\})>0\\})>0.$ In this case, $x_{0}$ is a valid
choice with this property if $\mu(\\{x_{1}:x_{0},x_{1},x_{0}x_{1}\in A\\})>0,$
and given a valid choice of $x_{0}$ we have
$X_{1}(x_{0})=\\{x_{1}:x_{0},x_{1},x_{0}x_{1}\in A\\}.$

###  2.3. Finite product Trees

In this subsection we introduce finite product trees, which will be the main
objects along which we induct throughout the paper. The picture to have in
mind is of a rooted tree whose vertices are labeled by elements of $G,$ and
where paths through the tree correspond to multiplying by the label of each
each vertex along the path.

A finite product tree $T$ of height $m$ consists of a root $v\in G$ together
with a sequence of children
$T(v_{0}),T(v_{0},v_{1}),...,T(v_{0},...,v_{m-1})\subset G,$ where $v_{i}\in
T(v_{0},...,v_{i-1}).$ If $|T(v_{0},...,v_{i})|=n$ for all $i<m$ then we say
that $T$ has branching $n.$

A path in $T$ consists of a vertex $v_{i}\in T$ together with a consecutive
sequence (starting from $i$) of $v_{j}\in T(v_{i},...,v_{j-1})$. We denote by
$P(T)$ the set of all paths through $T$ that start from the root $v_{0},$ and
identify a path $v_{0},...,v_{n}\in P(T)$ with the element $v_{0}\cdot...\cdot
v_{n}\in G$.

We can concatenate a path $v_{i},...,v_{j}\in T,$ forming a new tree
$T^{\prime},$ by replacing the sequences $v_{i},...,v_{j}$ with a single
vertex $v^{\prime}=v_{i}\cdot...\cdot v_{j}.$ The children of $v^{\prime}\in
T^{\prime}$ are the children $T(v_{0},...,v_{i},...,v_{j})\subset T.$

A subtree of $T$ is any finite product tree that can be obtained from $T$ by
removing or concatenating paths.

The following is a technical lemma which we will need in Section 4.2. The
point is that if we finitely color the paths in a finite product tree so that
almost all paths have color $0,$ then it is easy to pass to a well behaved
subtree all of whose paths are monochromatic in color $0.$ The only difficulty
in the proof is the required notation.

######  Lemma 2.4.

Suppose that $T$ is a finite product tree of height at least
$((r+1)(k+1)|T(v_{0})|+1)m$ and branching $n$ such that
$T(v_{0},v_{1},...,v_{i})$ does not depend on $v_{1}.$ Suppose that
$c:\bigcup_{P\in P(T)}P\rightarrow\\{0,...,r\\}$ is a coloring such that:

  1. (1)

$c(v_{0})=0.$

  2. (2)

If there are paths $P_{0}=v_{0},...,v_{i_{1}},$
$P_{1}=v_{i_{1}+1},...,v_{i_{2}},...$ $P_{k}=v_{i_{k}+1},...,v_{i_{k+1}}$ with
$c(P_{0},...,P_{i})=a\neq 0$ for all $i\leq k,$ then for all paths
$P^{\prime}=v_{i_{k+1}+1},...,v_{j}$ we have
$c(P_{0},...,P_{k},P^{\prime})\neq a.$

Then there are $v_{2},...,v_{i}$ with $v_{j}\in T(v_{0},v_{1},...,v_{j-1})$
such that all paths in the subtree obtained by concatenating the paths
$v_{1},v_{2}...,v_{i}$ for all $v_{1}\in T(v_{0})$ and truncating this tree at
height $m$ are monochromatic in color $0.$

###### Proof.

Consider the following procedure. For fixed $v_{2},...,v_{i-1}$ either all
paths of the form $v_{0},v_{1},...,v_{i-1},v_{i}$ for $v_{1}\in T(v_{0})$ and
$v_{i}\in T(v_{0},v_{1},...,v_{i-1})$ receive color $0,$ or there is some
$v_{1}\in T(v_{0})$ and $T_{i}\in T(v_{0},v_{1},...,v_{i-1})$ such that
$c(v_{0},v_{1},...,v_{i-1},v_{i})\neq 0.$ If the former case occurs $m$ times
in a row then we are done. If the latter case occurs let us say that we made
progress. In this case we pass to the subtree obtained from concatenating all
paths $\overline{v_{1}},v_{2},...,v_{i}$ for all $\overline{v_{1}}\in
T(v_{0}).$ Note that we can only make progress in this way
$(r+1)(k+1)|T(v_{0})|$ times without violating condition (3) of the coloring,
and so after a total of $((r+1)(k+1)|T(v_{0})|+1)m$ iterations we have built
the desired monochromatic subtree. ∎

##  3\. Quasirandom colorings

In this section we introduce quasirandom colorings and describe some of their
basic properties. In the next definition and throughout one should refer to
Section 2.2 for our definition of the term ‘many.’

######  Definition 3.1.

Given an amenable group $(G,\mu)$ we say that $A\subset G$ is a large
$\overleftarrow{IP_{0}}$ set if for any $k\in\mathbb{N}$ there are many
sequences $(x_{0},...,x_{k})$ with $FP(x_{k},...,x_{0})\subset A.$

We say that a coloring of $G$ is quasirandom if every positive measure color
class is a large $\overleftarrow{IP_{0}}$ set.

######  Remark 3.2.

It is a consequence of [BF09] Theorem 1 that any finite coloring of a weak
mixing group is quasirandom. Up to introducing appropriate bounds, it follows
from [Gow08] Theorem 5.3 that any finite coloring of a $D$-quasirandom group
is approximately quasirandom.

An easy consequence of the existence of idempotent ultrafilters is that any
finite coloring of an amenable group contains a large $\overleftarrow{IP_{0}}$
color class. Namely, if we consider the semigroup $(G,*),$ where $a*b=ba\in G$
and $p$ is an idempotent ultrafilter in the left ideal of $(\beta G,*)$
consisting of the ultrafilters $q$ with $\mu(A)>0$ for all $A\in q,$ then
every element of $p$ is a large $\overleftarrow{IP_{0}}$ set. In particular,
every finite coloring of $G$ contains a color which is a large
$\overleftarrow{IP_{0}}$ set. Our next lemma is an elementary variant of this
fact, which, up to some setup, follows from the finite sums theorem.

######  Lemma 3.3.

Large $\overleftarrow{IP_{0}}$ sets are partition regular, i.e., if
$A=A_{1}\cup...\cup A_{r}$ and $A$ is a large $\overleftarrow{IP_{0}}$ set,
then some $A_{i}$ is a large $\overleftarrow{IP_{0}}$ set.

###### Proof.

Fix $k^{\prime}$ and let $k$ be large enough such that any $r$-coloring of an
$IP_{k}$ set contains an $IP_{k^{\prime}}$ set. By assumption, $A$ contains
many tuples $(x_{0},...,x_{k})$ with $FP(x_{k},...,x_{0})\in A.$

For a fixed valid choice of $x_{0},...,x_{k-1},$ consider
$X_{k}=X_{k}(x_{0},...,x_{k-1}).$ This satisfies $\mu(X_{k})>0$ by assumption.
Consider the auxiliary coloring $c:X^{k}\rightarrow[r^{k}]$ given by the
string listing the colors of elements of $FP(x_{k},...,x_{0})$. By the
pigeonhole principle there is an $X_{k}^{\prime}\subset X_{k}$ with
$\mu(X_{k}^{\prime})>\mu(X_{k})/r^{2^{k}}$ that is monochromatic with respect
to $c,$ and so replacing $X_{k}(x_{0},...,x_{k-1})$ with $X_{k}^{\prime}$
gives many tuples $(x_{0},...,x_{k})$ with $FP(x_{k},...,x_{0})\subset A$ and
so that for each $F\subset\\{0,..,k-1\\}$ and valid choice of
$x_{0},...,x_{k-1}$ the color of $x_{k}\overleftarrow{\prod}_{i\in F}x_{i}$
depends only on $F$ and not on the choice of $x_{k}\in X_{k}^{\prime}.$

Now consider a fixed valid choice of $x_{0},...,x_{k-2},$ and consider the
auxiliary $r^{2^{k}}$ coloring of $X_{k-1}(x_{0},...,x_{k-2})$ based on the
value of $c(x_{k})$ for some (and by the previous paragraph, any) $x_{k}\in
X_{k}(x_{0},...,x_{k-1})$. By the pigeonhole principle we can find
$X_{k-1}^{\prime}\subset X_{k-1}(x_{0},...,x_{k-2})$ with
$\mu(X_{k-1}^{\prime})\geq\mu(X_{k-1}(x_{0},...,x_{k-1}))/r^{2{{}^{k}}}$ such
that replacing $X_{k-1}(x_{0},...,x_{k-2})$ with $X_{k-1}^{\prime}$ gives many
tuples $(x_{0},...,x_{k})$ with $FP(x_{k},...,x_{0})\subset A$ and so that for
each $F\subset\\{0,..,k\\}$ and valid choice of $x_{0},...,x_{k-2}$ the color
of $\overleftarrow{\prod}_{i\in F}x_{i}$ depends only on $F$ and not on the
choice of $x_{k-1}\in X_{k-1}^{\prime}$ or $x_{k}\in X_{k}(x_{0},..,x_{k-1}).$

Continuing in this way, we find many tuples $(x_{0},...,x_{k})$ such that
$FP(x_{k},...,x_{0})\in A$ and for each $F\subseteq\\{0,...,k\\}$ and valid
choice of $x_{0},...,x_{k},$ the color of $\overleftarrow{\prod}_{i\in
F}x_{i}$ depends only on $F$ and not the choice of $x_{0},...,x_{k}.$ Finally,
applying the finite sums theorem, we find some $i$ and many choices of
$(x^{\prime}_{0},...,x^{\prime}_{k^{\prime}})$ such that
$FP(x^{\prime}_{k^{\prime}},...,x^{\prime}_{0})\in A_{i}.$

Repeating this for each $k^{\prime}\in\mathbb{N}$ gives the desired large
$\overleftarrow{IP_{0}}$ color class. ∎

###  3.1. Mixing in quasirandom colorings

In this subsection we show that it is easy to ‘switch’ between any desired
color classes in a quasirandom coloring, in the sense that if $C_{1},C_{2}$
are two positive measure color classes, then there are many $c_{1}\in C_{1}$
and $c_{2}\in C_{2}$ with $c_{1}c_{2}\in C_{1}$. This is a qualitative
analogue of the mixing property for quasirandom groups (see [Gow08] Theorem
5.3 and [BF09] Theorem 2.3), which implies that one can switch between any
finite collection of large sets via multiplication in that setting.

To be more precise, we will need the following definition. Refer to Subsection
2.3 for our notation involving trees.

######  Definition 3.4.

Given sets $A,R_{1},...,R_{r}\subset G,$ a color switching tree of height $m$
and branching $2^{n}r$ is a finite product tree $T$ with root $a\in A$ such
that:

  1. (1)

for each $v\in T$ of height less than $m,$ there are sets
$S_{1}(v),...,S_{r}(v)$ with $|S_{i}|=n$ and $FP(S_{i}(v))\in R_{i}.$ The
children of $v$ are precisely the elements of $FP(S_{i}(v))$ for each $i.$

  2. (2)

For any path $v_{i},...,v_{j}\in T,$ the color of $v_{i}\cdot...\cdot v_{j}$
depends only on $v_{i}.$

A rootless color switching tree is the same as above, but with the set
$A=\\{1\\}$ and with Item (2) above only applying when the path does not start
from the root.

For example, a color switching tree of height one and branching $2^{n}r$
consists of an element $a\in A$ and sets $FP(S_{1}),...,FP(S_{r})\subset G$
with $|S_{i}|=n$ and such that $FP(S_{i})\subset R_{i}$ and $a\cdot
FP(S_{i})\in A$ for all $i\in[r].$ A rootless color switching tree is just the
sets $FP(S_{i})$ as before, with no set $A$ and element $a\in A$ specified. If
$\mu(A)>0$ and each $R_{i}$ is a large $\overleftarrow{IP_{0}}$ set, then such
height one trees exist by Lemma 2.2. The following lemmas are simply the
result of iterating this fact $m$ times, where the only trick is that, since
each $R_{i}$ is a large $\overleftarrow{IP_{0}}$ set, we can find an $IP_{n}$
set in $R_{i}$ all of whose elements start a color switching tree of height
$m-1$ and arbitrarily high branching.

######  Lemma 3.5.

Suppose that $A,R_{1},...,R_{r}\subset G$ with $\mu(A)>0,$ and for any
$m,n^{\prime}\in\mathbb{N}$ there are elements of $R_{1},...,R_{r}$ which form
a rootless color switching tree of height $m$ and branching $2^{n^{\prime}}r$.
Then for any $m,n\in\mathbb{N}$ the set of $a\in A$ that form the root of a
color switching tree of height $m$ and branching $2^{n}r$ has positive
measure. Moreover, this measure is bounded from below by a function depending
only on $\mu(A),m$ and $n$.

###### Proof.

We proceed by induction on the height of the tree $m$. For $m=1,$ consider
$S_{1},...,S_{r}$ with $|S_{i}|=n^{\prime}$ and $FP(S_{i})\in R_{i}.$ So long
as $n^{\prime}$ is large enough with respect to $\mu(A),$ we can apply Lemma
2.2, obtaining the desired $IP_{n}$ sets and positive measure subset of $A.$

Now suppose that we have proven the Lemma for trees of height $m-1$ and any
branching and next wish to prove it for trees of height $m.$ Fix $n^{\prime}$
large enough depending on $m$ and $\mu(A).$ By assumption, there is a rootless
color switching tree $T$ of height $m$ and branching $2^{n^{\prime}}r.$ Let
$S_{i}=S_{i}(\emptyset)$ be the sequences corresponding to the children of
$\emptyset$ in $T.$ Note, by definition, that each element $f\in FP(S_{i})$ is
the root of a color switching tree $T(f)$ of height $m-1.$ As in the base
case, applying Lemma 2.2 to $A$ and the set $S_{i}$ produces a set
$A_{i}^{\prime}\subset A$ of measure bounded from below and an $IP_{n}$ set
$S_{i}^{\prime}\subset FP(S_{i})$ such that $A_{i}^{\prime}\cdot f\subset A$
for each $f\in S_{i}^{\prime}.$ For each such $f\in S_{i}^{\prime}$,
iteratively applying the inductive hypothesis to the sets $A_{i}^{\prime}\cdot
f\subset A$ and the rootless tree corresponding to the descendants of $f,$ we
obtain $A_{i}\subset A$ with measure bounded from below and a subtree
$T^{\prime}(f)\subset T(f)$ of height $m-1$ and branching $2^{n}r$ such that
$A_{i}\cdot t\subset A$ for each $t\in P(T(f))$. Iteratively running this
procedure for each $i\in[r],$ we find sets $A\supset A_{1}\supset...\supset
A_{r}$ of measure bounded from below such that each element of $A_{r}$ forms
the root for a color switching tree of height $m$ and branching $2^{n}r.$ ∎

######  Lemma 3.6.

Suppose that $A,R_{1},...,R_{r}\subset G$ with $\mu(A)>0$ and each $R_{i}$ a
large $\overleftarrow{IP_{0}}$ set. For any $m,n\in\mathbb{N}$, the set of
elements of $A$ that form the root for a color switching tree of height $m$
and branching $2^{n}r$ has positive measure.

###### Proof.

We proceed by induction on the height of the tree. For trees of height one,
consider $S_{1},...,S_{r}$ with $|S_{i}|=n^{\prime}$ and $FP(S_{i})\in R_{i}.$
So long as $n^{\prime}$ is large enough with respect to $\mu(A),$ we can apply
Lemma 2.2 to $A$ and the sets $S_{i}$, obtaining the desired $IP_{n}$ sets and
positive measure subset of $A.$

Now suppose that we have proven the Lemma for trees of height $m$ and any
desired branching. Consider $A\subset G$ with positive measure and choose
$n^{\prime}$ large enough depending on $\mu(A)$. In order to prove Lemma 3.6
for height $m+1$ and branching $2^{n}r$, by Lemma 3.5 it suffices to build a
rootless color switching tree of height $m+1$ and branching $2^{n^{\prime}}r$
using elements of the $R_{i}.$ Note that this is equivalent to showing that,
for each $i,$ there is an $IP_{n^{\prime}}$ subset of $R_{i}$ all of whose
members are the root for a color switching tree of height $m$ and branching
$2^{n^{\prime}}r.$

Restating our previous observation, it suffices to prove the following:

######  Claim 3.7.

Suppose that $R_{1},...,R_{r}$ are large $\overleftarrow{IP_{0}}$ sets, and
suppose that we have proven Lemma 3.6 for trees of height $m$ and any
branching. For each $i\in[r]$ and $n^{\prime}\in\mathbb{N},$ there is an
$IP_{n^{\prime}}$ set in $R_{i}$ all of whose members are the root for a color
switching tree of height $m$ and branching $2^{n^{\prime}}r.$

###### Proof.

For fixed $i\in[r]$ and $n^{\prime}\in\mathbb{N},$ the definition of being a
large $\overleftarrow{IP_{0}}$ set ensures that there are many tuples
$(x_{0},...,x_{n^{\prime}})$ with $FP(x_{n^{\prime}},...,x_{0})\in R_{i}.$ For
a valid choice of $(x_{0},...,x_{n^{\prime}-1}),$ consider
$X_{n^{\prime}}(x_{0},...,x_{n^{\prime}-1}).$ This has positive measure by
definition, and so the inductive hypothesis of Lemma 3.6 gives a positive
measure subset of $X_{n^{\prime}}(x_{0},...,x_{n^{\prime}-1})$ whose elements
are all roots for color switching trees of height $m$ and branching
$2^{n^{\prime}}r$. Replacing $X_{n^{\prime}}(x_{0},...,x_{n^{\prime}-1})$ with
this subset and repeating this procedure for each set

$A=X_{n^{\prime}}(x_{0},...,x_{n^{\prime}-1})\cdot f$

for $f\in FP(x_{n^{\prime}-1},...,x_{0})$ produces, for a given
$(x_{n^{\prime}-1},...,x_{0}),$ an $x_{n^{\prime}}$ such that $x_{n}\cdot f$
is the root of a color switching tree of height $m$ and branching
$2^{n^{\prime}}r$ for each $f\in FP(x_{n^{\prime}-1},...,x_{0}).$ Repeating
this entire process for each valid choice of $(x_{0},...,x_{i})$ for
$i<n^{\prime}$ produces a sequence $(x,...,x_{n^{\prime}})$ such that each
element of $FP(x_{n^{\prime}},...,x_{0})\subset R_{i}$ is the root of a color
switching tree of height $m$ and branching $2^{n^{\prime}}r.$ ∎

∎

##  4\. Proof of Theorem Theorem 1.3

###  4.1. The quasirandom case

In this subsection we prove theorem 1.3 for quasirandom colorings (and,
consequently, for all colorings of quasirandom amenable groups). The idea of
the proof is similar to the ‘locally balanced’ case of the proof of the main
result from [Bow22b] and the ‘thick’ case of the proof of the main result from
[BS22], with the additional ease over the $+,\cdot$ results coming from the
fact that the left and right actions of $G$ on $(G,\mu)$ commute. Most of the
work in the proof of Theorem 1.3 will come in the next subsection, where we
reduce the problem to the quasirandom case studied here.

######  Lemma 4.1.

Suppose that $G=C_{0}\cup...\cup C_{r},$ where each $C_{i}$ is a large
$\overleftarrow{IP_{0}}$ set. For any $k\in\mathbb{N}$ there are many
monochromatic sets of the form

$\\{x_{i}\cdot x_{i+1}\cdot...\cdot x_{j},\overrightarrow{\prod_{a\in
I}}x_{a}\cdot x_{0}\cdot x_{1}\cdot...\cdot x_{j}:i\leq
j\in\\{0,...,k\\},I\subset\\{j+1,...,k\\}\\}.$

###### Proof.

Before we begin, we note that the case $k=2,$ where one only desires
monochromatic $\\{x,y,xy,yx\\},$ already has all of the needed ideas for the
proof of the general result. The only difference is that one applies the
pigeonhole principle at the last step to find a monochromatic sequence of
length $k$ rather than length $2.$

Without loss of generality we may assume that $\mu(C_{0})\geq\frac{1}{r-1}.$
Apply Claim 3.7 with large $\overleftarrow{IP_{0}}$ sets $R_{i}=C_{i}$ and
with $m=r+1,$ and $n$ large enough depending on $r$ to construct a rootless
color switching tree $T$ of height $k(r+1)$ and branching $2^{n}(r+1).$

We inductively define sequences $C_{0}=A_{0}\supset A_{1}\supset...\supset
A_{k(r+1)}$ and $y_{-1},y_{0},...,y_{k(r+1)}\in G$ and a function
$f:\\{-1,0,...,k(r+1)\\}\rightarrow\\{0,...,r\\}$ such that:

  1. (1)

$\mu(A_{i+1})>\frac{\mu(A_{i})^{2}}{2(r+1)}.$

  2. (2)

$y_{i}A_{i+1}\subset A_{i}.$

  3. (3)

$A_{i+1}y_{0}\cdot...\cdot y_{i}\subset C_{f(i+1)}.$

  4. (4)

$f(-1)=0$ and $y_{-1}=1.$

  5. (5)

$y_{i+1}\in T(y_{0},...,y_{i})\cap C_{f(i)}.$

To see that this gives the desired result, note by the pigeonhole principle
that there are $a_{0}<...<a_{k}\in\\{-1,...,k(r+1)\\}$ with
$f(a_{i})=f(a_{j})=f$ for all $i,j\in\\{0,...,k\\}.$ Letting
$x_{i}=y_{a_{i}+1}\cdot...\cdot y_{a_{i+1}}$ for $i>0$ and
$X=A_{k(r+1)}y_{-1}\cdot...\cdot y_{a_{0}},$ we see that $X\subset C_{f}$ by
Item (2), $x_{a}\cdot...\cdot x_{b}\in C_{f}$ for all $1\leq a\leq b\leq k$ by
Item (5) and the definition of $T,$ and that $\overrightarrow{\prod}_{i\in
F}x_{i}\cdot X\cdot x_{1}\cdot...\cdot x_{i}\subset
C_{f(a_{i+1})}=C_{f(a_{1})}=C_{f}\in C_{f}$ for all $F\subset\\{1,...,k\\}$ by
Items (2) and (3). Moreover, by Item (1) we know $\mu(X)>0,$ and so for a
given $T$ we find a single $y$ and many valid choices of $x_{0}\in X$, and
since Lemma 3.6 gives us many choices of $T$ we have many choices of
$x_{1},...,x_{k}$ as desired.

Therefore, it suffices to construct the sequences $A_{i}$ and $y_{i}$ and a
function $f$ satisfying Items (1)-(5). Towards this, suppose that we have
defined $A_{0}\supset...\supset A_{i}$ and $y_{-1},...,y_{i-1}$ and the
partial function $f:\\{-1,...,i\\}\rightarrow\\{0,...,r\\}$ as desired. To
continue, we apply Lemma 2.2 with $A=A_{i}$ and $S=T(y_{-1}\cdot...\cdot
y_{i-1})\cap C_{f(i)}$ to find $A_{i+1}^{\prime}\subset A_{i}$ and $y_{i}\in
S$ such that $y_{i}A_{i+1}^{\prime}\subset A_{i}.$ Finally, by the pigeonhole
principle there is some color $j$ such that

$\mu(\\{x\in A_{i+1}^{\prime}:xy_{0}\cdot...\cdot y_{i}\in
C_{j}\\})\geq\frac{\mu(A_{i+1})}{r+1}>\frac{\mu(A_{i})^{2}}{2(r+1)}.$

Letting $A_{i+1}$ be this subset of $A_{i+1}^{\prime}$ and $f(i+1)=j$ is as
desired.

∎

###  4.2. Reduction to the quasirandom case

In this subsection we prove our main result. In the previous section we saw
that Theorem 1.3 holds for quasirandom colorings, and so our goal in this
section is to show that, in an arbitrary coloring, one can always pass to an
‘invariant enough’ subset of $G$ where the coloring appears quasirandom and we
can run the proof from Section 4.1 on this subset.

To explain the idea, let’s imagine that we’re in a simple special case where
we have a coloring $G=C_{0}\cup C_{1}\cup...\cup C_{r},$ where $C_{i}$ for
$i>0$ is a large $\overleftarrow{IP_{0}}$ set and $C_{0}$ is a positive
measure set with no subsets of the form $\\{x,y,xy\\}.$ In this case, we can
apply Lemma 3.6 with $A=C_{0}$ and $R_{i}=C_{i}$ for $i>0$ to find an as large
as desired color switching tree $T$ with root $v_{0}\in C_{0}.$ By definition,
this tells us that for any rooted path $v_{0},...,v_{k}\in T$ we have
$y=v_{0}\cdot...\cdot v_{k}\in C_{0},$ and so we know $C_{0}y\cap
C_{0}=\emptyset,$ as otherwise we could find a set of the form
$\\{x,y,xy\\}\subset C_{0}.$ In particular, we can now run the proof from
Section 4.1 starting with $A_{0}=C_{0}v_{0}$ and the using the rootless color
switching tree $T\setminus\\{v_{0}\\},$ finding the desired configuration in
$G\setminus C_{0}.$

The approach we take in the following is essentially as above, but we must
deal with the added complications that arise from only being able to assume
that $C_{0}$ does not have many sets of the form $FP(x_{k},...,x_{0})$ for
each $k.$

######  Lemma 4.2.

Suppose that $G=C_{0}\cup...\cup C_{r}$ where $C_{i}$ is a large
$\overleftarrow{IP_{0}}$ set for $i>0$. Either $C_{0}$ is also a large
$\overleftarrow{IP_{0}}$ set or some $C_{i}$ for $i>0$ contains many sets of
the form

$\\{x_{i}\cdot x_{i+1}\cdot...\cdot x_{j},\overrightarrow{\prod_{a\in
I}}x_{a}\cdot x_{0}\cdot x_{1}\cdot...\cdot x_{j}:i\leq
j\in\\{0,...,k\\},I\subset\\{j+1,...,k\\}\\}.$

Before proving this lemma, let us first note that together with Lemma 4.1 it
immediately implies Theorem 1.3.

###### Proof of Theorem 1.3.

If every color class is a large $\overleftarrow{IP_{0}}$ set then we are done
by Lemma 4.1. Otherwise, we may assume that we are given a coloring
$G=C_{0}^{\prime}\cup...\cup C_{i}^{\prime}\cup C_{i+1}^{\prime}\cup...\cup
C_{r^{\prime}}^{\prime},$ where $C_{j}^{\prime}$ is a large
$\overleftarrow{IP_{0}}$ set if and only if $j>i\geq 0.$ By Lemma 3.3 we may
assume that $i<r^{\prime}$ and that $C_{0}^{\prime}\cup...\cup C_{i}^{\prime}$
is not a large $\overleftarrow{IP_{0}}$ set. Applying Lemma 4.2 with the
coloring $G=C_{0}\cup C_{1}\cup...\cup C_{r},$ where
$C_{0}=C_{0}^{\prime}\cup...\cup C_{i}^{\prime}$ and $C_{j}=C_{i+j}^{\prime}$
for $j>0$ gives the needed configuration in a set $C_{j}$ for $j>0$. ∎

###### Proof of Lemma 4.2.

Assume that no $C_{i}$ contains many sets of the form

$\\{x_{i}\cdot x_{i+1}\cdot...\cdot x_{j},\overrightarrow{\prod_{a\in
I}}x_{a}\cdot x_{0}\cdot x_{1}\cdot...\cdot x_{j}:i\leq
j\in\\{0,...,k\\},I\subset\\{j+1,...,k\\}\\}$

for $i>0.$ We will use this property to find many sequences
$(x_{0},...,x_{k})$ with $FP(x_{n},...,x_{0})\subset C_{0}$ for each $k.$ In
fact, for each $k,m,n\in\mathbb{N}$ we will construct (many choices of)
$(x_{0},...,x_{k})$ such that each $x_{i}$ is the root of a color switching
tree $T_{i}$ of height $m$ and branching $2^{n}r$ and
$FP(x_{k}a_{k},...,x_{0}a_{0})\in C_{0}$ for all $a_{i}\in P(T_{i}).$

In the base case, we simply apply Lemma 3.6 to the set $C_{0}$ to find a
rootless color switching tree $T$ and a positive measure subset of $C_{0}$ all
of whose elements can be a root of $T.$

In the inductive step, we will use the following:

######  Claim 4.3.

Let $C^{\prime}\subset C_{0}$ have positive measure. For all
$m,n\in\mathbb{N}$ and finite sets $F\subset C_{0},$ there are
$m^{\prime},n^{\prime}\in\mathbb{N}$ such that if $T^{\prime}$ is a rootless
color switching tree of height $m^{\prime}$ and branching $2^{n^{\prime}}r$
such that $F\cdot P(T^{\prime})\subset C_{0},$ then there is a positive
measure subset $C\subset C^{\prime}$ and a color switching subtree $T\subset
T^{\prime}$ of height $m$ and branching $2^{n}r$ such that $C\cdot F\cdot
P(T)\subset C_{0}.$ Moreover, $\mu(C),m^{\prime},$ and $n^{\prime}$ depend
only on $\mu(C^{\prime}),m,,n$ and $|F|.$

Before proving Claim 4.3, let us first use it to complete the proof of Lemma
4.2.

Suppose that we have already found many choices of $(x_{0},...,x_{k})$ such
that each $x_{i}$ is the root of a color switching tree $T_{i}^{\prime}$ of
height $m^{\prime}$ and branching $2^{n^{\prime}}r$ and
$FP(x_{k}a_{k},...,x_{0}a_{0})\in C_{0}$ for all $a_{i}\in P(T_{i}^{\prime}).$
Given a valid choice of such $(x_{0},...,x_{k})$ and $T_{i}^{\prime}$ we will
construct a positive measure set $X_{k+1},$ a rootless color switching tree
$T_{k+1}$ of height $m$ and branching $2^{n}r,$ and subtrees $T_{i}\subset
T_{i}^{\prime}$ of height $m$ and branching $2^{n}r$ such that each element of
$X_{k+1}$ can be a root for $T_{k+1}$ and
$FP(x_{k+1}a_{k+1},...,x_{0}a_{0})\in C_{0}$ for all $a_{i}\in P(T_{i})$ and
$x_{k+1}\in X_{k+1}.$ Repeating this for each $k\in\mathbb{N}$ demonstrates
that $C_{0}$ is a large $\overleftarrow{IP_{0}}$ set.

This construction can be achieved by iterating Claim 4.3. To see this, we
first start with $X=C_{0}$ and apply Claim 4.3 with $C^{\prime}=X,$
$F=\\{x_{k}\\}$, and $T^{\prime}=T_{k}$ to find a positive measure set
$X_{1}\subset X$ and $T_{k}\subset T_{k}^{\prime}$ as desired. We then repeat
this, applying Claim 4.3 with $C^{\prime}=X_{1}$,
$F=\\{x_{k}a_{k}x_{k-1}:a_{k}\in T_{k}\\}\cup\\{x_{k-1}\\}$, and
$T^{\prime}=T_{k-1}^{\prime}$ to find the needed positive measure set
$X_{2}\subset X_{1}$ and $T_{k-1}\subset T_{k-1}^{\prime}.$ Continuing in this
way gives subtrees $T_{i}\subset T_{i}^{\prime}$ for $i\leq k$ and a positive
measure set $X_{k+1}^{\prime}$ such that $FP(x_{k+1}a_{k+1},...,x_{0}a_{0})\in
C_{0}$ for all $a_{i}\in T_{i}$ and $x_{k+1}\in X_{k+1}.$ To obtain the set
$X_{k+1}\subset X_{k+1}^{\prime}$ and $T_{k+1},$ we now apply Lemma 3.6 to the
set $X_{k+1}^{\prime}$.

∎

The proof of Claim 4.3 follows from running the proof of Lemma 4.1
simultaneously for the sets $C^{\prime}f$ for each $f\in F.$ This can be
accomplished by using a ‘color focusing tree,’ a variant of the typical color
focusing technique introduced in [Bow22a] which takes advantage of the fact
that one has many choices for each next step size in a typical coloring
focusing argument. The hypothesis of Lemma 4.2 ensures that each branch of the
color focusing tree that we construct will terminate in color $C_{0}.$

######  Claim 4.4.

There is a tree $\mathbf{T}$ whose vertices are positive measure subsets of
$G$ and whose edges are labeled by vertices of a rootless color switching
subtree $T^{\prime\prime}\subset T^{\prime}$ such that:

  1. (1)

The root of $\mathbf{T}$ is a set $A\subset C^{\prime}.$

  2. (2)

Vertices in $\mathbf{T}$ are monochromatic and are the sets of the form $Aft$
for $f\in F\cup\\{1\\}$ and $t\in P(T^{\prime\prime}).$

  3. (3)

For any rooted path $1,v_{1},...,v_{n}\in T^{\prime\prime},$ any $f\in F,$ and
any $i\leq j\leq m,$ the set $v_{j}\cdot...\cdot v_{n}\cdot Af\cdot
v_{1}\cdot...v_{i-1}$ is monochromatic of the same color as $Af\cdot
v_{1}\cdot...\cdot v_{i-1}.$

Before proving Claim 4.4, we will first use it to deduce Claim 4.3

###### Proof of Claim 4.3.

Given the data in Claim 4.4, note that if there is a path
$v_{0},...,v_{i},...,v_{j}$ in $T^{\prime\prime}$ and $f\in F$ such that the
colors of the term $v_{i}\cdot...\cdot v_{j}$ and sets $A\cdot f\cdot
v_{0}\cdot...\cdot v_{i}$ and $A\cdot f\cdot v_{0}\cdot...\cdot v_{j}$ agree
and are not $C_{0}$, then Item (3) ensures that for any $x\in Af\cdot
v_{0}\cdot...\cdot v_{i-1}$ and $y=v_{i}\cdot...\cdot v_{j}$ the set
$\\{x,y,xy,yx\\}$ is monochromatic. The same is true for more variables if we
instead find a sequence $v_{0},...,v_{a_{1}},...,v_{a_{k}}$ with this
property, which would contradict the hypothesis of Lemma 4.2. This is exactly
what we need to apply Lemma 2.4, which gives us the needed subtree $T\subset
T^{\prime\prime}$ and set $C=A.$

∎

###### Proof of Claim 4.4.

We will iteratively find $C^{\prime}\supset A_{0}\supset
A_{1}\supset...\supset A_{i}$ and $T_{0}=T^{\prime\prime}\supset
T_{1}\supset...\supset T_{i}$ such that $A_{i}$ and $T_{i}$ satisfy Properties
(1)-(3) of Claim 4.4 for rooted paths $1,...,v_{i-1}$ of length $i$, and
terminate with $A=A_{m^{\prime}}$ and $T^{\prime\prime}=T_{m^{\prime}}$. This
is accomplished by iteratively applying the pigeonhole principle and Lemma
2.2, with the only difficulty being the need to keep track of notation.

To begin, first note by the pigeonhole principle that there is $A_{0}\subset
C^{\prime}$ with $\mu(A_{0})\geq\mu(C^{\prime})/(r+1)^{|F|}$ such that each
set $A_{0}f$ is monochromatic for $f\in F.$

Now, suppose we have found $A_{0}\supset A_{1}\supset...\supset A_{i}$ and
$T_{0}=T^{\prime\prime}\supset T_{1}\supset...\supset T_{i}$ with the desired
properties. To find $A_{i+1}$ and $T_{i+1},$ consider a rooted path
$1,v_{1},...,v_{i}\in T_{i}$ and $f\in F.$ Applying Lemma 2.2 with $A_{i},$
and the children $T_{i}(v_{1},...,v_{i})$ we find $A_{i}^{\prime}\subset
A_{i}$ of measure bounded from below and $T_{i+1,v_{1},...,v_{i}}\subset
T_{i}$ such that Property (3) of Claim 4.4 is satisfied for all $f\in F$ and
paths of the form $v_{1},...,v_{i},v_{i+1},$ where $v_{1},...,v_{i}$ is the
previously specified sequence and $v_{i+1}\in
T_{i+1,v_{1},...,v_{i}}(v_{1},...,v_{i}).$ Applying the pigeonhole principle,
we find $A_{i,v_{1},...,v_{i}}\subset A_{i}^{\prime}$ such that
$\mu(A_{i,v_{1},...,v_{i}})\geq\mu(A_{i}^{\prime})/(r+1)^{m}$ and the sets
$A_{i,v_{1},...,v_{i}}fv_{1}\cdot...\cdot v_{i+1}$ are monochromatic for the
specified choice of $v_{1},...,v_{i}$ and any choice of $v_{i+1}\in
T_{i+1,f,v_{1},...,v_{i}}(v_{1},...,v_{i})$ and $f\in F,$ ensuring that we
satisfy property (2) of Claim 4.4 at this stage of the construction.
Iteratively repeating this process for each path $v_{1},...,v_{i}\in T_{i}$
gives the desired set $A_{i+1}=\bigcap A_{i,v_{1},...,v_{i}}$ and subtree
$T_{i+1}=\bigcap T_{i+1,v_{1},...,v_{i}}.$ ∎

##  5\. The pattern $\\{x,xy,yx\\}$ in non-amenable groups

In this section we prove Proposition 1.4. The idea is essentially the same as
in the proof of Lemma 4.1, but we use a weaker pigeonhole principle and do not
need to keep track of the color of $y.$

Before beginning, we recall a couple needed definitions.

######  Definition 5.1.

In a group $G:$

  * •

A set $T\subset F_{2}$ is (right) thick if for any finite $F\subset G$ there
is a $t\in T$ with $Ft\subset T.$

  * •

A set $S\subset F_{2}$ is (left) syndetic if there is a finite set $F\subset
G$ such that $F^{-1}S=G.$

  * •

A set $A\subset G$ is piecewise syndetic if it is the intersection of a thick
set and a syndetic set.

We will also use the following basic facts about these notions of size. Their
proofs all follow quickly from the definitions and can be found in [BHM98]
section 2.

######  Proposition 5.2.

Let $G$ be a group, $A\subset G$ a piecewise syndetic set and $S\subset G$ a
syndetic set. For all $g\in G:$

  1. (1)

$gA$ and $Ag$ are piecewise syndetic.

  2. (2)

$gS$ and $Sg$ are syndetic.

  3. (3)

If $A=C_{0}\cup...\cup C_{r},$ then some $C_{i}$ is piecewise syndetic.

We will also need the following variant of the pigeonhole principle.

######  Proposition 5.3.

If $A\subset G$ is piecewise syndetic, then $\\{g:g^{-1}A\cap A\textnormal{ is
piecewise syndetic}\\}$ is syndetic.

This fact has a standard ultrafilter proof (which follows from combining
[HS11] Theorems 4.39 and 4.40, for example) but we were unable to find a
reference containing a combinatorial proof. We give one below:

###### Proof of Proposition 5.3.

This will follow from the following auxiliary claim about thick sets.

######  Claim 5.4.

If $T$ is thick, then for all $g\in G$ so is the set $g^{-1}T\cap T.$

###### Proof.

Consider a finite subset $F\subset G$ and, using the fact that $T$ is thick,
find a $t\in G$ such that $(g^{-1}F\cup F)t\subset T.$ This implies that
$Ft\subset g^{-1}T\cap T$ as desired. ∎

Now to prove the Proposition, consider a piecewise syndetic set $A=S\cap T,$
where $S$ is syndetic and $T$ is thick. Since $S$ is syndetic, there is a
finite set $F\subset G$ such that $T\subset F^{-1}A.$ By our previous claim we
know $T(g)=g^{-1}T\cap T$ is thick, and so $A\cap T(g)=S\cap T\cap T(g)=S\cap
T(g)$ is piecewise syndetic. Moreover, for all $x\in A\cap T(g)$ there is an
$f\in F$ such that $fgx\in A.$ Coloring elements of $T(g)$ based on their
corresponding $f$ and applying Proposition 5.2 (1) and (3), we see that
$(fg)^{-1}A\cap A$ is piecewise syndetic. As this holds for all $g\in G,$ we
see that $F^{-1}\\{g:g^{-1}A\cap A\textnormal{ is piecewise syndetic}\\}=G,$
i.e. the set is syndetic. ∎

Proposition 1.4 now follows from a standard dynamical color focusing argument:

###### Proof.

Without loss of generality, assume that $C_{0}$ is piecewise syndetic. We
inductively build sequences of sets $A_{0}=C_{0}\supset A_{1}\supset...\supset
A_{r+1}$ and $S_{0},...,S_{r}\subset G,$ a sequence $y_{0},...,y_{r+1}\in G,$
and a function $f:\\{-1,0,...,r+1\\}\rightarrow\\{0,...,r\\}$ such that:

  1. (1)

$A_{i}$ is piecewise syndetic.

  2. (2)

$y_{i}\in S_{i}$ and $S_{i}$ is syndetic.

  3. (3)

$y_{i}A_{i+1}\subset A_{i}$ for each $i\geq 0.$

  4. (4)

$f(-1)=0$

  5. (5)

$A_{i+1}y_{0}\cdot...\cdot y_{i}$ is monochromatic of color $f(i)$ for each
$i\geq 0.$

To build such a sequence and use it to complete the proof, suppose that we
have already found $A_{i},$ $y_{0},...,y_{i-1},$ and a partial function $f$ as
desired. Note by Proposition 5.3 that there is a syndetic set $S_{i}$ such
that $A^{\prime}_{i}(y)=y^{-1}A_{i}\cap A_{i}$ is piecewise syndetic for each
$y\in S_{i}.$ Moreover, coloring $a\in A^{\prime}_{i}(y)$ based on the color
of $ay_{0}\cdot...\cdot y_{i-1}y$ and applying Proposition 5.2 (3), for each
$y$ we find a piecewise syndetic subset $A_{i}(y)\subset A^{\prime}_{i}(y)$
such that $A_{i}(y)y_{0}\cdot...\cdot y_{i-1}y$ is monochromatic. Now color
$y\in S_{i}$ based on the color of $A_{i}(y)$ and apply Proposition 5.2 (3)
again to find a piecewise syndetic set $S\subset S_{i}$ such that the colors
of the sets $A_{i}(y)$ agree for all $y\in S.$ Let $f(i)$ be this color. If
$f(i)=f(j)$ for some $j<i,$ then we complete the proof by considering the set
of $y\in y_{j+1}\cdot...\cdot y_{i-1}S$ and the set of $x\in
y_{0}\cdot...\cdot y_{j}A_{i}(y),$ both of which are piecewise syndetic by
Proposition 5.2 (1). Otherwise, we choose $y_{i}\in S$ arbitrarily and set
$A_{i+1}=A_{i}(y_{i})$ to continue with our construction. As we must
eventually have $f(i)=f(j)$ for some $j<i$ by the pigeonhole principle, this
process returns the desired configuration after at most $r+1$ steps.

∎

##  6\. Questions

We end with two related questions.

The first is a coloring variant of [KMRR22] Question 8.7, which asked if every
positive density set in an amenable group contains a subset of the form
$AB\cup BA$ with $A,B$ infinite.

######  Question 6.1.

Suppose that a sufficiently non commutative group is finitely colored. Are
there infinite sets $A,B$ such that $AB\cup BA$ is monochromatic and $ab\neq
ba$ for all $a\in A$ and $b\in B$? What if we also assume that the group is
amenable?

A weaker form of the above result where $A$ is required to be infinite but $B$
is only required to have size at least $k$ for any fixed $k$ follows from the
pigeonhole principle. The proof of Proposition 1.4 also gives a somewhat
stronger result, ensuring that $A\cup AB\cup BA$ is monochromatic.

Our second question concerns left vs right recurrence in amenable groups and
requires the following definition.

######  Definition 6.2.

Let $G$ be an amenable group with invariant measure $\mu.$ We say that
$S\subset G:$

  * •

is a set of weak left recurrence if $\\{s\in S:s^{-1}A\cap
A\neq\emptyset\\}\neq\emptyset$ for all $A$ with $\mu(A)>0.$

  * •

is a set of left recurrence if $\\{s\in S:\mu(s^{-1}A\cap
A)>0\\}\neq\emptyset$ for all $A$ with $\mu(A)>0.$

  * •

is a set of nice left recurrence if $\\{s\in S:\mu(s^{-1}A\cap
A)>\mu(A)-\delta\\}\neq\emptyset$ for all $A$ with $\mu(A)>0$ and all
$\delta>0.$

In all of the above items we say that $S$ is a large set of (weak/nice)
recurrence if the set of such $s$ has positive measure rather than just being
non-empty. We also define right versions of these notions analogously.

A crucial fact used during the proof of Theorem 1.3 was that left $IP_{0}$
sets and right $IP_{0}$ sets coincide, and, in particular via Lemma 2.1, are
both left and right sets of nice recurrence.

######  Question 6.3.

When do the left and right notions from Definition 6.2 coincide?

## References

  * [Aus15] Tim Austin, _Quantitative equidistribution for certain quadruples in quasi-random groups_ , Combinatorics, Probability and Computing 24 (2015), no. 2, 376–381.
  * [BCRZK16] Vitaly Bergelson, JC Christopherson, Donald Robertson, and Pavel Zorin-Kranich, _Finite products sets and minimally almost periodic groups_ , Journal of Functional Analysis 270 (2016), no. 6, 2126–2167.
  * [Ber00] Vitaly Bergelson, _The multifarious poincaré recurrence theorem_ , Descriptive set theory and dynamical systems 1 (2000), 31–57.
  * [BF09] Vitaly Bergelson and Hillel Furstenberg, _Wm groups and ramsey theory_ , Topology and its Applications 156 (2009), no. 16, 2572–2580.
  * [BH92] Vitaly Bergelson and Neil Hindman, _Some topological semicommutative van der waerden type theorems and their combinatorial consequences_ , Journal of the London Mathematical Society 2 (1992), no. 3, 385–403.
  * [BHM98] Vitaly Bergelson, Neil Hindman, and Randall McCutcheon, _Notions of size and combinatorial properties of quotient sets in semigroups_ , Topology Proceedings, vol. 23, 1998, pp. 23–60.
  * [BM98] V Bergelson and R McCutcheon, _Recurrence for semigroup actions and_ , Topological Dynamics and Applications: A Volume in Honor of Robert Ellis: Proceedings of a Conference in Honor of the Retirement of Robert Ellis, April 5-6, 1995, University of Minnesota, vol. 215, American Mathematical Soc., 1998, p. 205.
  * [BM07] Vitaly Bergelson and Randall McCutcheon, _Central sets and a non-commutative roth theorem_ , American journal of mathematics 129 (2007), no. 5, 1251–1275.
  * [Bow22a] Matt Bowen, _Composite ramsey theorems via trees_ , arXiv preprint arXiv:2210.14311 (2022).
  * [Bow22b] by same author, _Monochromatic products and sums in $2$-colorings of $\mathbb{N}$_, arXiv preprint arXiv:2205.12921 (2022).
  * [BR09] Vitaly Bergelson and Bruce Rothschild, _A selection of open problems_ , Topology and its Applications 156 (2009), no. 16, 2674–2681.
  * [BS22] Matt Bowen and Marcin Sabok, _Monochromatic products and sums in $\mathbb{Q}$_, arXiv preprint arXiv:2210.12290 (2022).
  * [BT14] Vitaly Bergelson and Terence Tao, _Multiple recurrence in quasirandom groups_ , Geometric and Functional Analysis 24 (2014), 1–48.
  * [Gow08] William T Gowers, _Quasirandom groups_ , Combinatorics, Probability and Computing 17 (2008), no. 3, 363–387.
  * [HS11] Neil Hindman and Dona Strauss, _Algebra in the stone-ˇcech compactification_ , Algebra in the Stone-Cech Compactification, de Gruyter, 2011.
  * [KMRR22] Bryna Kra, Joel Moreira, Florian K Richter, and Donald Robertson, _Infinite sumsets in sets with positive density_ , arXiv preprint arXiv:2206.01786 (2022).
  * [Neu34] JV Neumann, _Almost periodic functions in a group. i_ , Transactions of the American Mathematical Society 36 (1934), no. 3, 445–492.
  * [San19] Tom Sanders, _Schur’s colouring theorem for noncommuting pairs_ , Bulletin of the Australian Mathematical Society 100 (2019), no. 3, 446–452.
  * [Tse23] Anush Tserunyan, _Mixing and double recurrence in probability groups_ , Fundamenta Mathematicae 260 (2023), 77–98.