May | 2013 | A kind of library

Mérida, XI SLALM, 1998

May 29, 2013

This one is incredible. No beard, and I do not look yet like an orca.

I’m in the last row, sort of in the middle. Xavier Caicedo is on the second row, to the left. My friend Juan Carlos Rivera is on the last row as well. I should probably stop now.

MSRI, The continuum hypothesis, 2001

May 29, 2013

Workshop, May 29 – June 01, 2001. Apparently continuing with the nostalgia theme.

Here is the list of participants.

Leave a Comment » | Workshop | Permalink
Posted by andrescaicedo

I ran into this picture a few days ago, when looking at the old photos from the Martin Conference. I posted here the group picture from that conference. John Steel should be posting the other pictures soon (well, I’ve been waiting since 2001, so we’ll see), or I may post them if that ends up not happening.

This one is the conference photo from the Logic Colloquium 2000. The website has many other pictures available as well. It was an interesting meeting.

Paris, July 23 – 31, 2000. The meeting site will be the Sorbonne, where David Hilbert presented his famous list of problems at the International Congress of Mathematicians in August 1900.

As I recall, at the opening we listened to a recording of part of Hilbert’s address, including his Wir müssen wissen. Wir werden wissen.

I like this picture very much. You can see me behind Joel Hamkins, in what seems to be row eight. (I believe I met Joel and his wife, Barbara Gail Montero, at this conference.) Paul Larson still has hair.

1 Comment | Conferences | Permalink
Posted by andrescaicedo

SQuaREs, 2013

May 23, 2013

This week (May 20-May 24) I am in Palo Alto, at the American Institute of Mathematics, for the third year of a SQuaRE meeting on Descriptive aspects of Inner model theory. The previous two meetings are mentioned here and here. See also this post on some of our results.

This time two other SQuaRE meetings are happening simultaneously, one on the Possible shape of the numerical ranges for certain classes of matrices, and one on Singular cardinal combinatorics. Here you have the two set theory-related groups:

From left to right: Menachem Magidor, Paul Larson, Grigor Sargsyan, John Steel, Martin Zeman, me, Assaf Rinot, Dima Sinapova, James Cummings, Sy Friedman, and Ralf Schindler.

1 Comment | Workshop | Permalink
Posted by andrescaicedo

Olden days

May 23, 2013

Martin Conference, Berkeley, May 27-28, 2001.

(If someone has a version in higher resolution, or pictures of the conference, please contact John Steel, or myself.)

Read the rest of this entry »

2 Comments | Conferences, Life | Permalink
Posted by andrescaicedo

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

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.

Leave a Comment » | Students | Tagged: Bartel Leendert van der Waerden, Endre Szemeredi, Frank Plumpton Ramsey, Giuseppe Cornacchia, Issai Schur, Neil Hindman, Richard Rado, Summer Kisner | Permalink
Posted by andrescaicedo

BEST

May 18, 2013

BEST 2013 and NSF funded travel awards – Announcement 3

DATES: June 16 – 19, 2013

PLACE: University of Nevada, Las Vegas

Please consult the conference webpage.
The 20-th meeting of BEST will be hosted at University of Nevada, Las Vegas, as a AAAS-PD symposium during June 16 (Sunday) – June 19 (Wednesday), 2013. It is organized by Liljana Babinkostova, Andrés Caicedo, Sam Coskey and Marion Scheepers.

Contributed and invited talks will be held on Monday, Tuesday and possibly Wednesday at the University of Las Vegas, Nevada.

BEST PLENARY SPEAKERS: The four invited plenary speakers are:

Todd Eisworth (Ohio University).
Masaru Kada (Osaka Prefecture University, Japan).
Thilo Weinert (University of Bonn, Germany).
Lynne Yengulalp (University of Dayton).

In addition to these four plenary talks, the program has ten reserved speaking slots for students, four reserved slots for post-docs and 2 reserved slots for pre-tenure tenure track faculty, and several slots for contributed talks.

TRAVEL AWARDS: Graduate students speakers, post-doc speakers and pre-tenure tenure track speakers are strongly encouraged to apply for to BEST for an NSF-funded travel award. The travel expenses (airfare and lodging) of awarded speakers will be reimbursed up to the $700 maximum amount of the award, and registration fees of awardees will be reimbursed.

There are ten (10) travel awards of up to $700 plus registration fee available for graduate student presenters.
There are four (4) travel awards of up to $700 plus registration fee available for post-doc presenters.
There are two (2) travel awards of up to $700 plus registration fee available for pre-tenure, tenure track faculty members.

STUDENT SPEAKERS: BEST seeks to promote student participation in the conference via short (20 minute) presentations. To this end there are ten (10) NSF funded BEST travel awards available for students. To apply for one of these awards,

Prior to May 25, 2013 submit an abstract for the proposed presentation at the abstract submission site.
Prior to June 10, 2013 submit a resume including current affiliation, advisor name and stage of study, and a separate statement of goals.
Prior to June 10, 2013 have the advisor separately submit a recommendation letter, outlining the benefit of participation in the conference via presentation to the student.

In addition to the BEST travel awards, up to 20 travel awards of up to $150 each are also available from the AAAS-PD to help students (including students participating in BEST) defray travel expenses to participate in the AAAS-PD annual meeting.

Student speakers are also eligible for a AAAS-PD award of excellence for their presentation at BEST 20. Winners of these awards will be announced at the AAAS-PD banquet on June 18, 2013. Student participants will be guests at this banquet.

POST-DOC and PRE-TENURE TENURE TRACK SPEAKERS: BEST also seeks to be a forum for early career set theoretic scholars. In particular there are four (4) NSF funded BEST travel awards available for post-docs, and two (2) NSF funded BEST travel awards available for pre-tenure tenure track faculty. To apply for one of these awards,

Prior to May 25, 2013 submit an abstract for a proposed 25 minute presentation at the abstract submission site.
In the case of an application for a BEST post-doc travel award, prior to June 10, 2013 submit a resume including current affiliation, post-doc mentor name, and a list of publications, and a separate statement that addresses the applicant’s professional goals, and availability of travel funds.
In the case of an application for a BEST tenure track, pre-tenure, travel award, prior to June 10, 2013 submit a resume including current affiliation, years towards tenure, a current list of publications, and a separate statement that addresses the applicant’s professional goals, and availability of travel funds.

CONTRIBUTED TALKS: The BEST schedule will also have a number of slots for 25 minute contributed talks. Anyone wishing to speak at BEST 20 should submit an abstract as soon as possible (prior to June 10) at the abstract submission site. It is strongly recommended to also contact one of the organizers as soon as possible to indicate interest/intention in presenting a talk at BEST 20.

Important deadlines:

DEADLINE 1: REGISTRATION: Please consult the registration page. Early registration ends May 31. After that only on-site registration will be possible. Registration fees are dependent on date of registration. We kindly request that tenure track mathematicians planning to participate in BEST 20 consider acting as judges for the student presentations. The registration form has a place where willingness to act as a judge can be indicated. There are also a number of excursions available that can be indicated on the registration form. Also please consider attending the award banquet – meal choices are available on the registration form.

DEADLINE 2: ABSTRACTS: Atlas Conferences, Inc. is providing abstract services for BEST 20. Abstracts submitted by April 24 will appear in the proceedings of the annual conference of the AAAS-PD. The deadline for submitting an abstract is June 10. To submit an abstract, follow this link.

LODGING: Las Vegas offers many lodging options. Please see the lodging page on the conference website for lodging suggestions by the AAAS-PD.

Leave a Comment » | BEST, Conferences | Permalink
Posted by andrescaicedo

	116c- Homework 7 \| A… on 116c- Lecture 18
	116c- Lecture 17 \| A… on 116c: Mathematical Logic (Set…
	116c- Lecture 18 \| A… on 116c- Homework 7
	116c- Lecture 19 \| A… on 116c- Lecture 13
	580 -Partition calcu… on 580 -III. Partition calcu…
	580 -Partition calcu… on 580 -Partition calculus (…
	Nosferatu \| A kind o… on The cabinet of Doctor Cal…
	Monica Agana –… on 414/514 The theorems of Rieman…
	The Dalek invasion o… on The Dalek invasion of Boi…
	andrescaicedo on Help!
	Asaf Karagila on On anti-foundation and coding…
	andrescaicedo on On anti-foundation and coding…
	Asaf Karagila on On anti-foundation and coding…
	On anti-foundation a… on Interpretations
	andrescaicedo on MSC2020

A kind of library

Mérida, XI SLALM, 1998

MSRI, The continuum hypothesis, 2001

Paris, Logic Colloquium 2000

SQuaREs, 2013

Olden days

Summer Kisner – Schur’s theorem

BEST

Categories

Recent Comments

Mathematical links

My pages

Others

Mathoverflow

Math.StackExchange

Archives

May 2013
M	T	W	T	F	S	S
« Apr				Jun »
		1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30	31