%%%% THIS FILE IS AUTOMATICALLY GENERATED
%%%% DO NOT EDIT THIS FILE DIRECTLY,
%%%% ONLY EDIT THE SOURCE, tom-3/document.tex.
%%%%
%% Standard package list
\documentclass[letterpaper]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[english]{babel}
\usepackage[top=3cm, bottom=3cm, left=3.5cm, right=3.5cm]{geometry}
\usepackage[onehalfspacing]{setspace}
\usepackage{amsmath,amssymb,amsthm,wasysym}
\usepackage{nicefrac,booktabs}
\usepackage{mathptmx}
\usepackage{cite}
\usepackage[colorlinks=true]{hyperref}

%% Various helpers for Tom's papers
\newcommand{\gs}{\textnormal{gs}}
\newcommand{\ord}{\textnormal{ord}}
\newcommand{\Exp}{\textnormal{Exp}}
\newcommand{\Log}{\textnormal{Log}}
\newcommand{\lcm}{\textnormal{lcm}}
\newcommand{\range}{\textnormal{range}}
\newcommand{\NR}{\textnormal{NR}}
\newcommand{\Mod}[1]{\left(\textnormal{mod}~#1\right)}

\newcommand{\ap}[2]{\left\langle #1;#2 \right\rangle}
\newcommand{\summ}[1]{\sum_{k=1}^m{#1}}
\newcommand{\bt}[1]{{{#1}\mathbb{N}}}
\newcommand{\fp}[1]{{\left\lbrace{#1}\right\rbrace}}
\newcommand{\intv}[1]{{\left[1,{#1}\right]}}


%% Lifted from http://stackoverflow.com/questions/2767389/referencing-a-theorem-like-environment-by-its-name
%% This lets me do things like "Theorem A" and have the references work properly.
\makeatletter
\let\@old@begintheorem=\@begintheorem
\def\@begintheorem#1#2[#3]{%
  \gdef\@thm@name{#3}%
  \@old@begintheorem{#1}{#2}[#3]%
}
\def\namedthmlabel#1{\begingroup
   \edef\@currentlabel{\@thm@name}%
   \label{#1}\endgroup
}
\makeatother
% end lift

\newtheoremstyle{namedthrm}
  {}{}{}{}{}{}{ }  % This last space needs to be there
  {\bf\thmname{#1} \thmnote{#3}.}
%% End reference hack


%% Document start
\date{}
\begin{document}

%% Content start


\theoremstyle{plain}% default
\newtheorem{thm}{Theorem}[section]
\newtheorem{lem}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem*{cor}{Corollary}

\theoremstyle{definition}
\newtheorem{defn}{Definition}[section]
\newtheorem{conj}{Conjecture}[section]
\newtheorem{exmp}{Example}[section]
\theoremstyle{remark}
\newtheorem*{rem}{Remark}
\newtheorem*{note}{Note}
\newtheorem{case}{Case}

\title{Chaotic orderings of the rationals and reals}
\author{Hayri Ardal, Tom Brown, and Veselin Jungi\'{c}\footnote{Department of Mathematics,
¶¡ÏãÔ°AV, Burnaby, BC, Canada, V5A 1S6. \texttt{hardal@sfu.ca}, \texttt{tbrown@sfu.ca},
\texttt{vjungic@sfu.ca}.}}
\maketitle
\begin{center}{\small {\bf Citation data:} Hayri Ardal, Tom Brown, and Veselin Jungi\'c, \emph{Chaotic orderings of the
  rationals and reals}, Amer. Math. Monthly \textbf{118} (2011), 921--925.}\bigskip\end{center}

\begin{abstract}
In this note we prove that there is a linear ordering of the set of real numbers for which there is no monotonic 3-term arithmetic progression. This answers the question (asked by Erd\H{o}s and Graham) of whether or not every linear ordering of the reals must have a monotonic $k$-term arithmetic progression for every $k$.
\end{abstract}

% Introduction

\section{Introduction.}

Over the last few years there has been an increasing interest in combinatorial properties of linear orderings, also called infinite permutations, of various sets of real numbers. See for example \cite{avgust+frid+kamae+samilov2011,fon-der-flaass+frid2007,makarov2009,makarov2010}.

In this note, answering a question of Erd\H{o}s and Graham \cite[pp.~21--22]{erdos+graham1980}, we show that there is a linear ordering $\ll$ of the set $\mathbb{R}$ of real numbers which has no monotonic 3-term arithmetic progression (AP). This means that there do not exist distinct real numbers $x$ and $y$ such that $x$ $\ll$ $\frac{1}{2}(x+y)$ $\ll y$. We call such an ordering {\it chaotic}. In general, for any set $X\subseteq \mathbb{R}$, a linear ordering $\ll$ of $X$ is {\it chaotic} if there do not exist distinct $x,y,z\in X$ such that $y=\frac{1}{2}(x+z)$ and $x\ll y \ll z$.

Symbols such as ``$<$" or ``$\ge$" always refer to the usual order relation on $\mathbb{R}$.

Our methods show that for every $k\ge2$ there is a linear ordering of $\mathbb{R}$ for which there are monotonic $k$-term AP's, but no monotonic $(k+1)$-term AP. A {\it monotonic $k$-term AP} in $\mathbb{R}$ (monotonic with respect to an ordering $\ll$) is a set $\{a_i$ : $0\le i\le k-1\}$ with $a_i =a_0 +id$, $0\le i\le k-1$, $d\ne 0$, such that $a_0\ll a_1\ll \cdots \ll a_{k-1}$.


It has long been known that there are chaotic linear orderings of $\{1,2,\dots,n\}$ for every positive integer $n$ \cite{entringer+jackson1975,lyndon1975,odda1975,simmons1975,thomas1975}, but that for any arrangement of the positive integers into a sequence $a_{1},a_{2},\dots$, or even a doubly-infinite sequence $\dots ,a_{-2},a_{-1},a_{0},a_{1},a_{2},\dots$, there {\it does} exist a monotonic 3-term AP, that is, there are $i<j<k$ such that $a_{j}=\frac{1}{2}(a_{i}+a_{k})$ \cite{davis+entringer+graham+simmons1977}. It is a well-known open question whether every sequence $a_{1},a_{2},\dots$ which contains each positive integer exactly once must contain a monotonic 4-term AP. It is known that such a sequence need not contain a monotonic 5-term AP \cite{davis+entringer+graham+simmons1977}.

We start by constructing an explicit chaotic linear ordering of $\mathbb{Z}$, the set of integers. (Our method is similar to that of T. Odda \cite{odda1975}.) This ordering of $\mathbb{Z}$ has $0$ as its smallest element and $-1$ as its largest element. We then use K\"{o}nig's infinity lemma to obtain a chaotic linear ordering of $\mathbb{Q}$, the set of rational numbers. Finally, we use the axiom of choice (in the form ``every vector space has a basis") to obtain a chaotic linear ordering of $\mathbb{R}$. It would be of interest to know whether such an ordering can be constructed without using the axiom of choice.


For distinct real numbers $a_1,a_2,\ldots ,a_n$ we write $\langle a_1,a_2,\ldots ,a_n\rangle$ to denote the ordering $\ll$ on the set $\{ a_1,a_2,\ldots ,a_n\}$ in which $a_1\ll a_2\ll \cdots \ll a_n$. If $A=\langle a_1,a_2,\ldots ,a_n\rangle$ and $k$ is a real number, then $A+k$ denotes the ordering $\langle a_1+k,a_2+k,\ldots ,a_n+k\rangle$, and for a nonzero $k$, $kA$ denotes the ordering $\langle ka_1,ka_2,\ldots ,ka_n\rangle$. For disjoint sets $\{ a_1,a_2,\ldots ,a_n\}$ and $\{ b_1,b_2,\ldots ,b_m\}$, if $A=\langle a_1,a_2,\ldots ,a_n\rangle$ and $B=\langle b_1,b_2,\ldots ,b_m\rangle$, then $AB$ denotes the ordering $\langle a_1,a_2,\ldots ,a_n,b_1,b_2,\ldots ,b_m\rangle$.

% A chaotic ordering of Z

\section{A chaotic ordering of $\mathbb{Z}$}\label{4.sec2}

\begin{defn}\label{perm} Define the ordering $A_n$ on $[-2^{n-1},2^{n-1}-1]$, $n\geq 1$, inductively by setting $A_1=\langle 0, -1\rangle$ and $A_{n+1}=(2A_n)(2A_n+1)$.
\end{defn}

Thus $A_2=\langle 0,-2,1,-1\rangle$ and $A_3=\langle 0, -4, 2, -2,1, -3,3,-1\rangle$.

\begin{lem}
(i) Each $A_n$ is chaotic, $n\geq 1$. (This means that if $a,b,c \in [-2^{n-1},2^{n-1}-1]$ and $a+c=2b$, then $b$ cannot lie between $a$ and $c$, in the ordering $A_n$.)

(ii) Each $A_{n+1}$ extends $A_n$, $n\geq 1$. (This means that the numbers $-2^{n-1}$, $-2^{n-1}+1$,$\dots,2^{n-1}-1$ appear in $A_{n+1}$ in the same order that they appear in $A_n$.)
\end{lem}


\begin{proof}
(i) Clearly $A_{1}$ is chaotic. Assume that $n\geq 1$ and that $A_n$ is chaotic, that is, contains no monotonic 3-term AP. Then so are $2A_{n}$ and $2A_{n}+1$. Suppose $a$, $b=a+d$, $c=a+2d$ is a 3-term AP contained in $A_{n+1}=(2A_n)(2A_n+1)$. Since $a$ and $c$ have the same parity, $a$ and $c$ must both appear in $2A_n$ or in $2A_n+1$. But $2A_n$ and $2A_n+1$ are chaotic, and hence $b$ cannot appear between $a$ and $c$. Thus $A_{n+1}$ is chaotic.

(ii) We see that $A_2$ extends $A_1$. Assume now that $n\geq 2$ and that $A_n$ extends $A_{n-1}$. Then $2A_n$ extends $2A_{n-1}$ and $2A_n+1$ extends $2A_{n-1}+1$. Hence $A_{n+1}=(2A_n)(2A_n+1)$ extends $A_n=(2A_{n-1})(2A_{n-1}+1)$.
\end{proof}

\begin{defn}\label{ordZ} The linear ordering $<_\mathbb{Z}$ on $\mathbb{Z}$ is defined as follows. For all $a,b\in \mathbb{Z}$,
$$a<_\mathbb{Z} b \Leftrightarrow \mbox{ whenever }a,b\in [-2^{n-1},2^{n-1}-1], \ a \mbox{ precedes }b \mbox{ in }A_n.$$
\end{defn}

This definition makes sense in view of part (ii) of Lemma 2.1. Part (i) clearly implies the following theorem.

\begin{thm}\label{chaoZ}
The linear ordering $<_\mathbb{Z}$ of $\mathbb{Z}$ is chaotic.
\end{thm}

% A chaotic ordering of Q

\section{A chaotic ordering of $\mathbb{Q}$}\label{secQ}

Let $\mathbb{Q}=\{ r_1,r_2,\ldots \}$ be a fixed enumeration of $\mathbb{Q}$, and for each $n\geq 1$ let $X_n=\{ r_1,r_2,\ldots ,r_n\}$. We can produce a chaotic ordering of $X_n$ by choosing $k \in \mathbb{N}$ so that
$kX_n\subseteq \mathbb{Z}$, restricting the ordering $<_\mathbb{Z}$ of $\mathbb{Z}$ to $kX_n$ to give a chaotic ordering of $kX_n$, and then dividing by $k$ to give a chaotic ordering of $X_n$. Different values of $k$ may give different chaotic orderings of $X_{n}$. The essential point is that there exists at least one chaotic ordering of $X_{n}$ for each $n\ge 1$.

Construct a rooted tree $T$ by letting the vertices at level $n$ be the chaotic orderings of $X_n$, for each $n\geq 1$. A vertex $p$ at level $n$ is adjacent to a vertex $q$ at level $n+1$ if and only if $q$ extends $p$.

Some branches of $T$ may terminate. For example, $6$ cannot be inserted into $\langle 2,4,3, 0\rangle$.

By K\"{o}nig's infinity lemma, $T$ has an infinite branch $p_1\subset p_2\subset p_3\subset \cdots ,$
where $p_n\subset p_{n+1}$ means that the ordering $p_{n+1}$ of $X_{n+1}=\{ r_1,r_2,\ldots ,r_n,r_{n+1}\}$ extends the ordering $p_n$ of $X_n=\{ r_1,r_2,\ldots ,r_n\}$.

The union of the chain of orderings $p_1\subset p_2\subset p_3\subset \cdots $ is a linear ordering of $\mathbb{Q}$. Call this ordering $<_\mathbb{Q}$. Thus by definition, for $a,b\in \mathbb{Q}$
$$a<_\mathbb{Q} b \Leftrightarrow \mbox{ whenever }a,b\in X_n, \ a \mbox{ precedes }b \mbox{ in }p_n.$$

Since each $p_n$ is a chaotic ordering of $X_n$, we have proved the following theorem.

\begin{thm} The linear ordering $<_\mathbb{Q}$ of $\mathbb{Q}$ (defined above) is chaotic.
\end{thm}

% A chaotic ordering of R

\section{A chaotic ordering of $\mathbb{R}$}\label{secR}


Let $B$ be a basis for the vector space $\mathbb{R}$ over the field $\mathbb{Q}$. Let $<_\mathbb{Q}$ be a chaotic ordering of $\mathbb{Q}$. Extend $<_\mathbb{Q}$ to a linear ordering of $\mathbb{R}$ as follows. For distinct $a,b\in \mathbb{R}$ write $$a=\sum _{i=1}^ka_i\gamma _i \mbox{ and } b=\sum _{i=1}^kb_i\gamma _i,$$
where $\gamma _1,\gamma _2,\ldots ,\gamma _k\in B$, $\gamma _1<\gamma _2<\cdots <\gamma _k,$ and $a_1,\ldots a_k,b_1,\ldots ,b_k\in \mathbb{Q}$.



Let $j=\min \{ i: 1\leq i\leq k \mbox{ and } a_i\not= b_i\}$. Then we define the ordering $<_\mathbb{R}$ on $\mathbb{R}$ by
$$a<_\mathbb{R}b \Leftrightarrow a_j<_\mathbb{Q}b_j.$$
We claim that $<_\mathbb{R}$ is a chaotic ordering of $\mathbb{R}$. (It is clearly a linear order.)

For suppose that $a,b,c\in \mathbb{R}$, $a,b,c$ distinct, with $a+c=2b$. Write
$$a=\sum _{i=1}^ka_i\gamma_i \mbox{, } b=\sum _{i=1}^kb_i\gamma _i \mbox{, and }c=\sum _{i=1}^kc_i\gamma _i, $$
where $\gamma _1,\gamma _2,\ldots ,\gamma _k\in B$, $\gamma _1<\gamma _2<\cdots <\gamma _k$,
$a_i,b_i,c_i\in \mathbb{Q}$, $1\leq i\leq k$.

Note that since $a+c=2b$,

$$ a_i+c_i=2b_i \ \mbox{for each }i, \ 1\leq i\leq k.$$

Let $j=\min \{ i: 1\leq i\leq k, \mbox{ and not all of } a_i, b_i, c_i \mbox{ are equal}\}$. Then no two of $a_j$, $b_j$, $c_j$ are equal since $a_j+c_j=2b_j$ would imply that all three are equal.

Thus for $1\leq i\leq j-1$, all three of $a_i$, $b_i$, $c_i$ are equal. Then $a<_\mathbb{R}b<_\mathbb{R}<c$ implies that $a_j<_\mathbb{Q}b_j<_\mathbb{Q}c_j$ in $\mathbb{Q}$, which is not possible since $<_\mathbb{Q}$ is a chaotic ordering of $\mathbb{Q}$.

This establishes our claim, and completes the proof of the following theorem.

\begin{thm} The linear ordering $<_\mathbb{R}$ of $\mathbb{R}$ (defined above) is chaotic.
\end{thm}

Note that in Theorem 4.1, $\mathbb{R}$ can be replaced by any field of characteristic 0.

% Remarks

\section{Remarks\label{sec4t}}

\begin{enumerate}
\item Definition 2.1 can be generalized by replacing 2 by $k$, for any $k\ge2$. Fix $k\geq 2$. Define the permutation $C_n$ of $[-(k-1)k^{n-1},k^{n-1}-1]$, $n\geq 1$, inductively by setting $C_1=\langle 0, -1,-2, \cdots ,-(k-1)\rangle $ and $ C_{n+1}=(kC_n)(kC_n+1)\cdots (kC_n+k-1)$, $n\geq 1$.

All of the above arguments in Sections 2, 3, and 4 can now be repeated with little change, resulting in a linear ordering of $\mathbb{R}$ with respect to which there is no monotonic $(k+1)$-term AP, but there are monotonic $k$-term AP's.

\item Let $\mathbb{N}$ denote the set of nonnegative integers, and for $a,b\in\mathbb{N}$, let $\ a=\sum _{i=0}^ka_i2^i$ and $b=\sum _{i=0}^kb_i2^i$, $a_i,b_i\in \{ 0,1\}$. From Definition 2.1, restricted to $\mathbb{N}$, it is not hard to see that $a<_\mathbb{Z}b$ if and only if $(a_0, a_1, \dots, a_k)$ precedes $(b_0, b_1, \dots, b_k)$ in the standard lexicographic ordering of finite binary sequences. It easily follows that

$$a<_\mathbb{Z}b\Leftrightarrow \sum _{i=0}^k\frac{a_i}{2^i}<\sum _{i=0}^k\frac{b_i}{2^i}.$$

Thus $<_\mathbb{Z}$, restricted to $\mathbb{N}$, can be defined in terms of $<.$

\item The last equivalence suggests defining an explicit chaotic linear ordering $<_\mathbb{D}$ of the set $\mathbb{D}$ of nonnegative dyadic rationals,
$$\mathbb{D}=\left\{ \frac{p}{2^n}: p,n\in \mathbb{N}\right\}.$$
For $a,b\in \mathbb{D}$, let $\displaystyle a=\sum _{i=-\infty }^\infty a_i2^i$, $\displaystyle b=\sum _{i=-\infty }^\infty b_i2^i$, $a_i,b_i\in \{0,1\}$. Let
$$a^\ast =\sum _{i=-\infty }^\infty a_i2^{-i} \mbox{ and } b^\ast =\sum _{i=-\infty }^\infty b_i2^{-i} .$$
As remarked above, in case $a,b\in \mathbb{N}$ then
$$a<_\mathbb{Z}b \Leftrightarrow a^\ast <b^\ast.$$

Now we define, for all $a,b\in \mathbb{D}$,
$$a<_\mathbb{D}b \Leftrightarrow a^\ast <b^\ast.$$

To see that $<_\mathbb{D}$ is chaotic, for $a,b\in \mathbb{D}$ choose $q$ so that $2^qa, 2^qb\in \mathbb{N}$.
Then $\displaystyle (2^qa)^\ast =\frac{1}{2^q}\cdot a^\ast$ and
$$a<_\mathbb{D}b\Leftrightarrow a^\ast<b^\ast \Leftrightarrow \frac{1}{2^q}\cdot a^\ast < \frac{1}{2^q}\cdot b^\ast
\Leftrightarrow (2^qa)^\ast <(2^qb)^\ast \Leftrightarrow 2^qa<_\mathbb{Z}2^qb. $$


Since $<_\mathbb{Z}$ is chaotic, so is $<_\mathbb{D}$.

\item Note that the mapping $\phi$ from $\mathbb{D}$ to $\mathbb{D}$ defined by $\phi(a)=a^*, a \in \mathbb{D},$ is a bijection and, by definition, $a<_\mathbb{D} b$ if and only if $\phi (a) <\phi(b)$ for all $a,b\in \mathbb{D}$. Thus,
$(\mathbb{D}, <_{\mathbb{D}})$ and $(\mathbb{D}, <)$ are {\it order-isomorphic}.

Since $\phi(\mathbb{N})=\mathbb{D}\cap[0,2)$ and $\phi(\mathbb{D}\cap[0,2))=\mathbb{N}$, we have that $(\mathbb{N}, <_\mathbb{D})$ and $ (\mathbb{D}\cap [0,2),<)$, as well as $(\mathbb{D}\cap [0,2),<_{\mathbb{D}})$ and $(\mathbb{N}, <)$, are order-isomorphic.

Since $<_{\mathbb{D}}$ and $<_{\mathbb{Z}}$ agree on $\mathbb{N}$, we conclude, as in Remark 2, that
$(\mathbb{N},<_{\mathbb{Z}})$ and $(\mathbb{D}\cap [0,2), <)$ are order-isomorphic.

\end{enumerate}

% Acknowledgements

\paragraph{Acknowledgments.} The authors would like to thank Rado\v{s} Radoi\v{c}i\'c for initiating their interest in the combinatorial properties of linear orderings. The authors would also like to acknowledge the IRMACS Centre at ¶¡ÏãÔ°AV for its support while they were conducting the research presented in this work.


\bibliographystyle{amsplain}
\bibliography{tom-all}
\end{document}