Monica Agana – The classical theory of rearrangements

July 16, 2017

Monica was my last masters student at Boise State, completing her thesis in December 2015, while I was already at Mathematical Reviews. My colleague at Boise State Zach Teitler coadvised her for the last few months. The following picture is from graduation day.

Monica Agana

Monica

Monica’s thesis, The classical theory of rearrangements, discusses Riemann’s famous rearrangement theorem for conditionally convergent series of real numbers, prior results, and some extensions and related topics. This previous blog post discusses some of these.

Advertisements

“A survey of the density topology on the reals”

February 12, 2015

Stuart Nygard, one of my current Master’s students, just returned from attending this year’s Winter School in Abstract Analysis. He gave a survey talk on the general topic of his thesis, the density topology. His slides can be found here.

Slides of most of the talks can also be downloaded at the conference website, here. Sadly, there do not seem to be slides for the tutorials on the analysis section.


Shehzad Ahmed – Coanalytic determinacy and sharps

January 12, 2015

Shehzad is my most recent student, having completed his M.S. thesis on May last year. He is currently pursuing his PhD at Ohio University. His page is here, and he also keeps a blog.

Shehzad Ahmed

Shehzad

His thesis, \mathbf \Pi^1_1-determinacy and sharps, is a survey of the Harrington-Martin theorem, showing the equivalence between a definable fragment of determinacy, and a large cardinal hypothesis.

After the fold, I review the basic notions, and give the tiniest of hints of what the theorem is and how its proof goes. Since the material is technical, the post is not really self-contained.

Read the rest of this entry »


Daniel Donado – Metric spaces on omega_1 under determinacy

August 24, 2014

Daniel was my first masters student, completing his M.S. in June 2010. I co-advised him together with my friend and colleague Ramiro de la Vega, at the Universidad de los Andes, in Bogota. The following picture is from his Facebook profile.

Daniel Donado

Daniel

Daniel’s thesis, Metric spaces on \omega_1 under the axiom of determinacy (in Spanish), is part of a vastly unexplored field: general topology in the absence of choice.

Work on this area has been mostly about highlighting pathologies, illustrating how vastly different results can be when we keep standard definitions but work in setting where the axiom of choice fails badly. Even in the setting of the real numbers with the standard topology, things may not work as expected: Every set of reals may be Borel (in fact F_{\sigma\sigma}), there may be Borel infinite Dedekind-finite sets, etc. In his PhD thesis at UC Berkeley, Apollo Hogan showed that, instead, we can carry out a systematic and detailed study of general topology if instead of dealing with arbitrary models with absurd failures of choice, we concentrate on settings where the absence of choice is compensated by a rich combinatorial structure. Specifically, Apollo (who was a student at Berkeley at the same time I was there) considered topology under the axiom of determinacy. Daniel’s thesis is a survey of some of the results discovered by Apollo.

Daniel begins by reviewing some of the basic consequences of \mathsf{AD}, the axiom of determinacy. To state \mathsf{AD}, we need to consider certain ideal games between two players, that I will just call I and II. In all these games the format is the same: players I and II alternate with I playing first. In each turn, the corresponding player picks a natural number, repetitions being allowed, and both players having knowledge of all the moves both have made previously. They play for infinitely many rounds. At the end, a sequence of natural numbers \langle n_0,n_1,n_2,\dots\rangle has been produced, with n_0,n_2,n_4,\dots being the numbers picked by player I, and n_1,n_3,\dots being the ones picked by II. We have one of these games for each set A\subseteq\mathbb N^{\mathbb N}, where \mathbb N^{\mathbb N} is the set of all infinite sequences of natural numbers. In the game associated to such an A, player I wins iff the sequence \langle n_0,n_1,n_2,\dots\rangle is in A. Otherwise, player II is the winner.

A strategy \sigma for player I is a function that tells player I what to play each time. Formally, this is just a function from the set of finite sequences of numbers to \mathbb N. A strategy for II is defined similarly. We say that a strategy for I is winning if and only if player I wins the game whenever they play following the strategy. That is, in any such game we have  n_0=\sigma(\langle\rangle), n_2=\sigma(\langle n_1\rangle), n_4=\sigma(\langle n_1,n_3\rangle), etc, and at the end we have that \langle n_0,n_1,n_2,\dots\rangle\in A. Winning strategies for player II are defined similarly. We say that A is determined iff one of the players has a winning strategy.

It is easy to give examples of determined sets A. Using the axiom of choice, we can give examples of undetermined sets, but deep theorems in descriptive set theory indicate that no undetermined set can be particularly simple. For instance, it is a celebrated theorem of Martin that all Borel sets are determined. Here, \mathbb N^{\mathbb N} is made into a topological space by taking the product topology of countably many copies of the discrete set \mathbb N.

The axiom of determinacy is the statement that all A\subseteq \mathbb N^{\mathbb N} are determined. In particular, this statement contradicts the axiom of choice. See here for slides of a talk I gave a few years ago containing a quick introduction to the subject.

The short remainder of this post (after the fold) is by necessity more technical.

Read the rest of this entry »


Summer Kisner – Schur’s theorem

May 19, 2013

My student Summer Kisner completed her M.S. this term, and graduated on Saturday.

2013--5-18 Summer

2013–5-18 Summer

Here is a copy of the slides she used on her defense. (The slides display incorrectly on my computer, but it seems to be a problem on my end. If it is not, please let me know, and I’ll see what I can do.)

Her thesis, Schur’s theorem and related topics in Ramsey theory, discusses Schur’s theorem, one of the first result in what we now call Ramsey theory. The result states that if the positive integers \mathbb Z^+ are partitioned into finitely many sets, \mathbb Z^+=A_1\cup\dots\cup A_n, then for some i, 1\le i\le n, there are integers x,y,z (not necessarily different), all of them in A_i, such that x+y=z. One usually describes this in terms of colors: We color the positive integers with finitely many colors, and there is a monochromatic triple x,y,z with x+y=z.

This result is a cornerstone of Ramsey theory. It was significantly generalized by Rado (using the notion of partition regularity), and is connected to van der Waerden’s and Szemerédi’s famous results.

Nowadays, Schur’s theorem is typically proved as a corollary of Ramsey’s theorem. This is usually stated in terms of graphs, but I will use the notation from the partition calculus. Let {}[X]^k denote the collection of k-sized subsets of the set X. Suppose that X is infinite, and consider a coloring c:[X]^k\to C, where the set C of colors is finite. Ramsey’s theorem asserts that under these assumptions, there is an infinite subset H of X that is homogeneous or monochromatic for c, in the sense that c assigns the same color to all k-sized subsets of H. In fact, we have finitary versions of this result: For any n and any l=|C|, if we only require that H has size at least n, then there is an m such that it suffices to assume that X has size at least m. Even for k=l=2, the study of Ramsey numbers, the least m seen as a function of n, proves to be incredibly difficult and computationally unfeasible. For example, if n=5, then we know that 43\le m\le 49, but its exact value is not known.

To deduce Schur’s theorem from Ramsey’s, let r be such that, for any for coloring of {}[\{1,\dots,r\}]^2 using n colors, there is a monochromatic set of size 3. The least such r we denote R_n(3). We want to show that if \mathbb Z^+=A_1\cup\dots\cup A_n, then there is a monochromatic solution to the equation x+y=z. In fact, we claim that it suffices to consider \{1,\dots,r-1\} rather than the whole set of positive integers. Indeed, given a partition \{1,\dots,r-1\}=A_1\cup\dots\cup A_n, consider the coloring of {}[\{1,\dots,r\}]^2 where if a<b, then the set $\{a,b\}$ has color i, where b-a\in A_i. By definition of r, we can find a<b<c such that \{a,b\},\{a,c\},\{b,c\} all have the same color. Now notice that c-a=(c-b)+(b-a), that is, b-a,c-b,c-a are monochromatic for the original coloring of \{1,\dots,r-1\}.

An easy inductive argument gives us that R_n(3)\le 3\cdot n!, so this gives the upper bound 3\cdot n!-1 for the so-called n-th Schur number s(n). To see the upper bound R_n(3)\le 3\cdot r!, note that R_1(3)=3, and verify inductively that R_{n+1}(3)\le (n+1)R_n(3): Suppose that |X|\ge (n+1)R_n(3), and consider a coloring of [X]^2 with n+1. Fix an element a\in X, and note that for some color i there are R_n(3) elements b\in X such that \{a,b\} has color i. Let Y be the set of all these b, that is, Y=\{b\in X\mid\{a,b\} has color i\}. Note that if for some b,c\in Y we have that \{b,c\} has color i as well, then \{a,b,c\} is monochromatic with color i. Hence we may assume that the coloring, restricted to {}[Y]^2, only uses n colors. We are now done, since |Y|\ge R_n(3).

Schur’s original proof predated Ramsey, and gives a slightly better bound than s(n)\le 3\cdot n!. Indeed, from his proof, we obtain that s(n)\le \lceil n!e\rceil.

In terms of lower bounds, one can quickly check by induction that s(n)\ge (3^n+1)/2. Indeed, s(1)=2=(3^1+1)/2, since 1+1=2. Given a coloring c of \{1,\dots,k\} using colors \{1,\dots,n\} and without monochromatic triples, we describe a coloring c' of \{1,\dots,3k+1\} using colors \{1,\dots,n+1\}, again without monochromatic triples. This gives the result. To define c', start by letting c'(i)=c(i) for i\le k. Now let c'(j)=n+1 for k+1\le j\le 2k+1, and finally let c'(j)=c(j-(2k+1)) for 2k+2\le j\le 3k+1.

Slightly better bounds are known. For example, Anne Penfold Street shows that s(n)\ge (89\cdot 3^{n-4}+1)/2 in

 W.D. Wallis, Anne Penfold Street, Jennifer Seberry Wallis. Combinatorics: Room squares, sum-free sets, Hadamard matrices. Lecture Notes in Mathematics, Vol. 292. Springer-Verlag, Berlin-New York, (1972). MR0392580 (52 #13397).

Schur proved his theorem in order to establish a result related to Fermat’s last theorem, namely that it cannot be established by a naive argument involving modular arithmetic: Suppose that x, y, z are integers, and x^n+y^n=z^n. Then, for any prime p, the equality holds modulo p and, if p is large enough, then we also have that p\not\mid xyz. Hence, to prove that Fermat’s equation admits no solutions (x,y,z), it would suffice to show that there are arbitrarily large primes p such that p must divide one of x,y,z. What Schur proved is that this is not possible and, indeed, for any n and all sufficiently large primes p, there are nontrivial solutions to Fermat’s equation modulo p. To see this, let p>s(n) and let G be the subgroup of (\mathbb Z/p\mathbb Z)^* consisting of n-th powers. Then (\mathbb Z/p\mathbb Z)^* is union of cosets of G, say (\mathbb Z/p\mathbb Z)^*=\bigcup_{i=1}^k a_iG where the k displayed sets are disjoint. Note that k=n/\mathrm{gcd}(n,p-1)\le n. Now color (\mathbb Z/p\mathbb Z)^* using k colors, by letting t have color i iff t\in a_iG. By choice of p, we have a monochromatic Schur triple, that is, there are \alpha,\beta,\gamma\in (\mathbb Z/p\mathbb Z)^* such that \alpha+\beta=\gamma and \alpha,\beta,\gamma\in a_iG for some i. But then there are x,y,z, all nonzero modulo p, such that \alpha=a_i x^n, \beta=a_i y^n, and \gamma=a_i z^n, so (x,y,z) is a nontrivial solution to Fermat’s equation modulo p.

It is actually an interesting problem to try and determine the optimal size \mathcal N of p as a function of n. Fourier-analytic methods give here the best known bounds. Cornacchia proved in 1909 that \mathcal N(n)\le (n-1)^2(n-2)^2+6n-2, at least if n itself is prime.

Let me close with an open problem: We could consider a multiplicative (rather than additive) version of Schur’s theorem: For any n there is an s'(n) such that if \{1,2,\dots,s'(n)\} is colored using n colors, then there is a monochromatic set \{x,y,z\} with xy=z. Indeed, this follows as a simple corollary of Schur’s result: Just note that s'(n)\le 2^{s(n)}, since we could just color the powers of two and apply the additive version. what if we combine the two? It is still open whether in any finite coloring of \mathbb Z^+ there are integers x,y such that x,y,x+y,xy all receive the same color. This was originally asked by Hindman.


Coloring problems

January 12, 2012

My student Tommy Chartier completed his M.S. in December.

Read the rest of this entry »


Master’s thesis

October 6, 2011

My student

Thomas Chartier

will be will defending his Master’s thesis for a Mathematics degree, titled

Coloring Problems

 

Abstract: We consider two coloring problems which have a combinatorial flavor. The chromatic number of the plane, \chi, is the least number of colors necessary to color {\mathbb R}^2 in such a way that no two points at a unit distance apart receive the same color. It is well known that 4\le\chi\le 7. We begin by discussing the arguments that give these bounds.

The main point the talk considers the problem of whether given any n\in{\mathbb Z}^+, one can color the positive integers in such a way that for all a\in{\mathbb Z}^+, the numbers a,2a,3a,\dots,na are assigned different colors. Such colorings are referred to as satisfactory. We begin with an example which provides insight into the underlying structure inherent in all satisfactory colorings, present a sufficient condition for guaranteeing the existence of satisfactory colorings, and analyze the resulting structure.

 

The defense will be held Thursday, October 13, 2011, 2:40-3:30 pm, in Room MP-201. Refreshments will be served in the math lounge at 2:15 pm.