Evan Chen (陳誼廷) on WordPress

 

https://usamo.wordpress.com/all-posts/

https://usamo.wordpress.com/2015/03/14/writing/

Writing

POSTED ON MARCH 14, 2015 BY EVAN CHEN (陳誼廷)

9

In high school, I hated English class and thought it was a waste of time. Now I’m in college, and I still hate English class and think it’s a waste of time. (Nothing on my teachers, they were all nice people, and I hope they’re not reading this.)

However, I no longer think writing itself is a waste of time. Otherwise, I wouldn’t be blogging, even about math. This post explains why I changed my mind.

1. Guts

My impression is that teachers in high school got it all wrong.

In high school, students are told to learn algebra because “we all use math every day”. This is obviously false, and somehow the students eventually are led to believe it.

You can’t actually be serious. Do people really think that knowing the Pythagorean Theorem will help in your daily life? I sure don’t, and I’m an aspiring mathematician. (Tip: Even real mathematicians stopped doing Euclidean geometry ages go.) It’s hilarious when you think about it. We’ve convinced millions of kids all over the country that they’re learning math because it’s useful in their lives, and they grudgingly believe it.

The actual answer of why we teach math in schools is that it is supposed to teach students how to think. But even the teachers have lost sight of this. Most high school math teachers are now just interested in making sure their students can “do” certain classes of problems in a short time, where “do” here doesn’t refer to solving the problem but regurgitating the solution that’s already been presented. The process is so repetitive and artificial that in high school I wrote computer programs to do my homework for me, because all the “problems” were just the same thing with numbers changed. If you’re interested in just how far off math is, I encourage you to read Lockhart’s Lament.

How can this happen? I think the answer is that many high schoolers don’t really have the guts to think, “my math teachers don’t have a clue”, even though they like to joke about it. I have the guts to say this now because I know lots of math. And it’s amazing to know that millions and millions of people are just plain wrong about something I believe in.

But on to the topic of this post…

2. The world lied to me

I was always told that the purpose of English class was to learn to write. Why is this important? Because it was important to be able to communicate my ideas.

Dead wrong. Somehow the skill of being able to argue on the nature of love in Romeo and Julietwas going to help me when I was writing a paper on Evan’s Theorem years down the road? That’s what my parents said. It sounds absurd when I put it this way, but people believe it. (And let’s not forget the fact that theorems are named by last name…)

I claim that the situation is just like math. People are just being boneheads. As it turns out, the standard structure of an English essay is nothing more than a historical accident. Even the fact that essays are about literature is a historical accident. But that’s beyond the scope of what I have to say.

So what is the purpose of writing? It turns out that there is one, and that it has nothing to do with communication. It’s that writing clarifies thinking.

3. Writing lets you see everything

“I sometimes find, and I am sure you know the feeling, that I simply have too many thoughts and memories crammed into my mind…. At these times… I use the Pensieve. One simply siphons the excess thoughts from one’s mind, pours them into the basin, and examines them at one’s leisure.”

— Harry Potter and the Goblet of Fire

Here’s some advice to all of you still in doing math contests — start keeping track of the problems you solve.

There’s superficial reasons for doing this. A few days ago I was trying to write a handout on polynomials, and I was looking for some problems on irreducibility. I knew I had seen and done a bunch of these problems in the past, but of course like most people I hadn’t bothered to keep track of every problem I did, so I could only remember a few off my head. So I had to go through the painful process of looking through my old posts on the Art of Problem Solving forums, searching through old databases, mucking through pages of garbage looking for problems that I did ages ago that I could use for my handout. And all the time I was thinking, “man, I should have kept track of all the problems I did”.

But there are deeper reasons for this. As I started collating the problems and solutions into a list, I started noticing some themes in the solutions that I never noticed before. For example, basically every solution started with the line “Assume for contradiction that  is not irreducible and write ”. And then from there, one of three things happened.

• The problem would take the coefficients modulo some prime or prime power, and then deduce some things about  and . Obviously this only worked on the problems with integer coefficients.
• The problem would start looking at absolute values of the coefficients and try to achieve some bound that showed the polynomial had to reduce in a certain way.
• If the problem had multiple variables, the solution would reduce to a case with just one-variable. This was always the case with problems that had complex coefficients as well.

You can’t really be serious — I’m only noticing this now? Here I was, already a retired contestant, looking at problems I had done long long ago and only realizing now there was a common theme. I had already done all the work by having done all the problems. The only difference was that I didn’t write anything down; as a result I could only look at one problem at a time.

Needless to say, I was very angry for the rest of the day.

4. External and Working Memory

Why does this happen? More profoundly, it turns out that humans have a finite working memory. You can only keep so many things in your head at once. That’s why it’s a stupid idea to not write down problems and (sketches of) solutions after you solve them and keep them somewhere you can look at.

I probably did at least 1000 olympiad problems over the course of my life. Did I manage to keep all the solutions in my head? Of course not. That’s why at the IMO in 2014, I didn’t try a maximality argument despite the  in the problem. I think if I had kept better records I wouldn’t have missed this. How else do you get exactly  in the lower bound? It’s not even an integer! Poof. There goes my neat 42.

I didn’t realize this wasn’t just a math thing until much later. I was talking about something along these lines during my interview for Harvard College; my interviewer was an artist. When I was talking about writing things down because I couldn’t keep them all in my head, he said something that surprised me — his easel was covered with sticky notes where he wrote down any ideas that occurred to him. He called it “external memory”, a term I still use now.

It’s actually obvious when you think about it. Why do people have to-do lists and calendars and reminders? Because you can’t keep track of everything in your head. You can try and might even get good at it, but you’ll never do as well as the old-fashioned pen and paper.

This isn’t just about “I need to remember to do  in exactly  time”. There’s a reason we use blackboards during math lectures instead of just talking. The ideas in math are really, really hard, because math is only about ideas, and nothing else. If the professors didn’t write the steps on the board, no one would be able to keep more than two or three steps in their head at once. The difficulty is only compounded by the fact that math has its own notation. We didn’t develop this notation because we were bored. We developed notation because the ideas we’re trying to express are so complex that the English language can’t even express them. In other words, mathematicians were forced to create a whole new set of symbols just to write down their ideas.

5. An Imperfect Analogy to Teaching

But so far I haven’t really argued anything other than “if you want to remember something you better write it down”. There’s a difference between a to-do list and an exposition. One is just a collection of disconnected bullet points. The other needs to do more, it needs to explain.

The following quote is excerpted from Richard Rusczyk’s article “Learning Through Teaching” ).

You can’t just “kind of get it” or know it just well enough to get by on a test; teaching calls for complete understanding of the concept.

• How do you know that?
• When would you use that?
• How could you come up with that in the first place?

If you can’t answer these questions for something you “know”, then you can’t teach it.

I knew this was true from my own experiences teaching, but it took me more time to realize that writing well is a similar skill. The difference is the medium: when you’re teaching in person, you get real-time feedback on whether what you said makes sense. You don’t get this live feedback when you’re writing, and so you need to be much more careful. Yet all the nuances of teaching are still there — distinguishing between details, main ideas, hardest steps; deciding what can be worked out from what other things, even deciding which things are worth including and which things should be omitted.

This all really started to become obvious to me when I started my olympiad geometry textbook. In senior year of high school, I decided that I had a good enough understanding of olympiad geometry to write a textbook on it. I felt like I could probably do better than all the existing resources; not as hard as it sounds, since to my knowledge there aren’t any dedicated books for olympiad geometry.

After I had around 200 pages written, I realized that I had gotten a lot better at geometry. There were lots of things that happened in the process of thinking about the best way to teach geometry.

1. Most basically, I did in fact fill in gaps in my knowledge. For example, I studied projective transformations for the first time in order to write the corresponding section in my book. The ideas definitely clicked much faster when I was thinking about how to teach it.
2. I made new connections. I realized for the first time that symmedians and harmonic quadrilaterals are actually the same concept; I discovered a lemma about directed angles that I wished I had known before; I found a new proof to Menelaus using an elegant strategy I had used on Monge’s Theorem. None of this would have happened from just doing problems.
3. Most profoundly, I got a much better understanding for when to apply certain techniques. One of the main goals of my book was to make solutions natural — a reader should be able to understand where a solution came from. That meant that at every page I was constantly fighting to try and explain how I had thought up of something. This unending reflection was exhausting and reduced me to a rate of about one page written per hour\footnote{But conveniently, this process is something that just requires a laptop, not even paper and pencil. So I got a lot of pages written during office assistant.}. But it improved my own ability significantly.

Ultimately what this exemplifies is that trying to explain something lets you understand it better. And that’s in part because you can only manage so many things in your head at once. If you think keeping track of your appointments in your head is hard, try doing that with a complex argument. Can’t do it. Writing solves this problem.

6. Finding the Truth

But that’s not a perfect analogy. What I’ve presented above is a model where you have ideas in your head and you output them onto paper. This isn’t totally accurate, because as you write, something else can happen: the ideas can change.

I’ll draw an analogy from painting, again courtesy of Paul Graham.

The model of painting I used to have is that you would have something you want to draw, and then you sit down and draw it, then polish up the details. (That’s how I did all my high school art projects, anyways.) But this turns out to not be true: Countless paintings, when you look at them in x-rays, turn out to have limbs that have been moved or facial features that have been readjusted. I was surprised when I first read this. But it makes sense if you can think about it: how you can be sure what’s in your head is what you want if you can’t even see it yet?

I propose that writing does the same thing. I don’t start by thinking “these are the ideas and I will now write them down”. Rather, I just write my thoughts down, not sure where they’re going to end up. That’s how my geometry textbook actually got written. I didn’t start with a table of contents. I started by putting down ideas, finding the connections between them, noticing new things I hadn’t before. I created new sections on the fly as the need arose, added new things as I thought of them, and let the whole thing sort itself out with a simple \verb+\tableofcontents+. You can even think of the table of contents as a natural bucket sort — put down related ideas near each others, add section headers as needed, and bam, you have an outline of the main ideas. And I never know what this outline will look like until it’s actually been written.

By the same token, revising shouldn’t be the art of modifying the presentation of an idea to be more convincing. It should be the art of changing the idea itself to be closer to the truth, which will automatically make it more convincing. This is consistent with the Latin: the word “revise” literally means “see again”.

This is where high school and college essays get it really wrong. In a college essay, the goal is to “sell an idea” to the reader. If something in the essay looks unconvincing, you fix it by trickery: re-writing it in a way that it sounds more convincing without changing the underlying idea. The way you say something goes a long way in selling it. That’s what English class should have taught you. Sure, some teachers tell you to make concessions or counterarguments, but you’re doing this to try and pretend to be “honest”. You only write such things with an agenda in mind.

But since when are you always right? That’s absurd. The English class model is “I have a thesis that I know is right, and now I’m going to explain to the reader why”. But how can you know you’re right about a thesis before you’ve written it down? If the thesis and its accompanying argument is even remotely complex, it wouldn’t have been possible to sort through the whole thing in your head. Worse still, if the thesis is nontrivial, odds are that someone who is about as smart as you will disagree with you. And as Yan Zhang often reminds the SPARC attendees, you should really only expect to be right about half the time when you disagree with someone about as smart as you. If an essay is supposed to move you closer to the truth, and your original thesis is wrong half the time, do you scrap half your essays? Unfortunately, I don’t think you’d ever pass English class that way.

The culture that’s been instilled, where the goal of writing is to convince, is intellectually dishonest. I might even go to say it’s dangerous; I’ll have to think about that for a while. There are times when you do want to write to convince others (grant proposals, anyone?) but it seems highly unfortunate that this type of writing has become synonymous with writing as a whole.

7. Conclusion

So this post has a few main ideas. The main purpose of writing is not in fact communication, at least not if you’re interested in thinking well. Rather, the benefits (at least the ones I perceive) are

• Writing serves as an external memory, letting you see all your ideas and their connections at once, rather than trying to keep them in your head.
• Explaining the ideas forces you to think well about them, the same way that teaching something is only possible with a full understanding of the concept.
• Writing is a way to move closer to the truth, rather than to convince someone what the truth is.

So now I’ll tell you how I actually wrote my geometry book, or this blog post, or any of my various olympiad articles. It starts because I have an idea — just a passing thought, like “this would be a good way to explain Masckhe’s Theorem”. Some time later I’ll another such thought which is related to the first. Then a third. My memory is especially bad, so pretty soon it bothers me so much that I have to write it down, because I’m starting to lose track. And as I write the first ideas down, I start noticing new ideas, so I add in these ideas, and then more new ideas start flooding in. There are so many things I want to say and I just keep writing them down. That’s how I ended up with a 400-page textbook written from what originally was just meant to be a short article. There were too many things to say that other people hadn’t said yet, and I just had to write them all down. The miraculous things is that these ideas naturally sorted themselves out. The bulleted main ideas I listed above weren’t things I realized until I looked at the resulting table of contents.

I’m sometimes told by people I respect that they like my writing. But I think this actually just translates to “I like the ideas in your writing”, and so I take it as a big compliment.

 

https://usamo.wordpress.com/2016/11/11/notes-on-publishing-my-textbook/

Notes on Publishing My Textbook

POSTED ON NOVEMBER 11, 2016 BY EVAN CHEN (陳誼廷)

2

 

Hmm, so hopefully this will be finished within the next 10 years.

— An email of mine at the beginning of this project

My Euclidean geometry book was published last March or so. I thought I’d take the time to write about what the whole process of publishing this book was like, but I’ll start with the disclaimer that my process was probably not very typical and is unlikely to be representative of what everyone else does.

Writing the Book

The Idea

I’m trying to pin-point exactly when this project changed from “daydream” to “let’s do it”, but I’m not quite sure; here’s the best I can recount.

It was sometimes in the fall of 2013, towards the start of the school year; I think late September. I was a senior in high school, and I was only enrolled in two classes. It was fantastic, because it meant I had lots of time to study math. The superintendent of the school eventually found out, though, and forced me to enroll as an “office assistant” for three periods a day. Nonetheless, office assistant is not a very busy job, and so I had lots of time, all the time, every day.

Anyways, I had written a bit of geometry material for my math club the previous year, which was intended to be a light introduction. But in doing so I realized that there was much, much more I wanted to say, and so somewhere on my mental to-do list I added “flesh these notes out”. So one day, sitting in the office, after having spent another hour playing StarCraft, I finally got down to this item on the list. I hadn’t meant it to be a book; I was just wanted to finish what I had started the previous year. But sometimes your own projects spiral out of your control, and that’s what happened to me.

Really, I hadn’t come up with a brilliant idea that no one had thought of before. To my knowledge, no one had even tried yet. If I hadn’t gone and decided to write this book, someone else would have done it; maybe not right away, but within many years. Indeed, I was honestly surprised that I was the first one to make an attempt. The USAMO has been a serious contest since at least the 1990’s and 2000’s, and the demand for this book certainly existed well before my time. Really, I think this all just goes to illustrate that the Efficient Market Hypothesis is not so true in these kind of domains.

Setting Out

Initially, this text was titled A Voyage in Euclidean Geometry and the filename Voyage.pdf would persist throughout the entire project even though the title itself would change throughout.

The beginning of the writing was actually quite swift. Like everyone else, I started out with an empty LaTeX file. But it was different from blank screens I’ve had to deal with in my life; rather than staring in despair (think English essay mode), I exploded. I was bursting with things I wanted to write. It was the result of having years of competitive geometry bottled up in my head. In fact, I still have the version 0 of the table of contents that came to life as I started putting things together.

• Angle Chasing (include “Fact 5”)
• Centers of the Triangle
  • The Medial Triangle
  • The Euler Line
  • The Nine-Point Circle
• Circles
  • Incircles and Excircles
  • The Power of a Point
  • The Radical Axis
• Computational Geometry
  • All the Areas (include Extended Sine Law, Ceva/Menelaus)
  • Similar Triangles
  • Homothety
  • Stewart’s Theorem
  • Ptolemy’s Theorem
• Some More Configurations (include symmedians)
  • Simson lines
  • Incircles and Excenters, Revisited
  • Midpoints of Altitudes
• Circles Again
  • Inversion
  • Circles Inscribed in Segments
  • The Miquel Point (include Brokard, this could get long)
  • Spiral Similarity
• Projective Geometry
  • Harmonic Division
  • Brokard’s Theorem
  • Pascal’s Theorem
• Computational Techniques
  • Complex Numbers
  • Barycentric Coordinates

Of course the table of contents changed drastically over time, but that wasn’t important. The point of the initial skeleton was to provide a bucket sort for all the things that I wanted to cover. Often, I would have three different sections I wanted to write, but like all humans I can only write one thing at a time, so I would have to create section headers for the other two and try to get the first section done as quickly as I could so that I could go and write the other two as well.

I did take the time to do some things correctly, mostly LaTeX. Some examples of things I did:

• Set up proper amsthm environments: earlier versions of the draft had “lemma”, “theorem”, “problem”, “exercise”, “proposition”, all distinct
• Set up an organized master LaTeX file with \include’s for the chapters, rather than having just one fat file.
• Set up shortcuts for setting up diagrams and so on.
• Set up a “hints” system where hints to the problems would be printed in random order at the end of the book.
• Set up a special command for new terms (\vocab). At the beginning all it did was made the text bold, but I suspected that later I might it do other things (like indexing).

In other words, whenever possible I would pay O(1) cost to get back O(n) returns. Indeed the point of using LaTeX for a long document is so that you can “say what you mean”: you type \begin{theorem} … \end{theorem}, and all the formatting is taken care of for you. Decide you want to change it later, and you only have to change the relevant code in the beginning.

And so, for three hours a day, five days a week, I sat in the main office of Irvington High School, pounding out chapter after chapter. I was essentially typing up what had been four years of competition experience; when you’re 17 years old, that’s a big chunk of your life.

I spent surprisingly little time revising (before first submission). Mostly I just fired away. I have always heard things about how important it is to rewrite things and how first drafts are always terrible, but I’m glad I ignored that advice at least at the beginning. It was immensely helpful to have the skeleton of the book laid out in a tangible form that I could actually see. That’s one thing I really like about writing; helps you collect your thoughts together.

It’s possible that this is part of my writing style; compared to what everyone says I should do, I don’t do very much rewriting. My first and final drafts tend to look pretty similar. I think this is just because when I write something that’s not an English essay, I already have a reasonably good idea what I want to say, and that the process of writing it out does much of the polishing for me. I’m also typically pretty hesitant when I write things: I do a lot of pausing for a few minutes deciding whether this sentence is really what I want before actually writing it down, even in drafts.

Some Encouragement

By late October, I had about 80 or so pages content written. Not that impressive if you think about it; I think it works out to something like 4 pages per day. In fact, looking through my data, I’m pretty sure I had a pretty consistent writing rate of about 30 minutes per page. It didn’t matter, since I had so much time.

At this point, I was beginning to think about possibly publishing the book, so it was coming out reasonably well. It was a bit embarrassing, since as far as I could tell, publishing books was done by people who were actually professionals in some way or another. So I reached out to a couple of teachers of mine (not high school) who I knew had published textbooks in one form or another; I politely asked them what their thoughts were, and if they had any advice. I got some gentle encouragement, but also a pointer to self-publishing: turns out in this day and age, there are services like Lulu or CreateSpace that will just let you publish… whatever you want. This gave me the guts to keep working on this, because it meant that there was a minimal floor: even if I couldn’t get a traditional publisher, the worst I could do was self-publish through Amazon, which was at any rate strictly better than the plan of uploading a PDF somewhere.

So I kept writing. The seasons turned, and by February, the draft was 200 pages strong. In April, I had staked out a whopping 333 pages.

The Review Process

Entering the MAA’s Queue

I was finally beginning to run out of things I wanted to add, after about six months of endless typing. So I decided to reach out again; this time I contacted a professor (henceforth Z) that I knew, whom I knew well from time at the Berkeley Math Circle. After some discussion, Z agreed to look briefly at an early draft of the manuscript to get a feel for what it was like. I must have exceeded his expectations, because Z responded enthusiastically suggesting that I submit it to the Problem Book Series of the MAA. As it turns out, he was on the editorial board, so in just a few days my book was in the official queue.

This was all in April. The review process was scheduled to begin in June, and likely take the entirety of the summer. I was told that if I had a more revised draft before the review that I should also send it in.

It was then I decided I needed to get some feedback. So, I reached out to a few of my close friends asking them if they’d be willing to review drafts of the manuscript. This turned out to not go quite as well as I hoped, since

• Many people agreed eagerly, but then didn’t actually follow through with going through and reading chapter by chapter.
• I was stupid enough to send the entire manuscript rather than excerpts, and thus ran myself a huge risk of getting the text leaked. Fortunately, I have good friends, but it nagged at me for quite a while. Learned my lesson there.

That’s not to say it was completely useless; I did get some typos fixed. But just not as many as I hoped.

The First Review

Not very much happened for the rest of the summer while I waited impatiently; it was a long four month wait for me. Finally, in the end of August 2014, I got the comments from the board; I remember I was practicing the piano at Harvard when I saw the email.

There had been six reviews. While I won’t quote the exact reviews, I’ll briefly summarize them.

1. There is too much idiosyncratic terminology.
2. This is pretty impressive, but will need careful editing.
3. This project is fantastic; the author should be encouraged to continue.
4. This is well developed; may need some editing of contents since some topics are very advanced.
5. Overall I like this project. That said, it could benefit from some reading and editing. For example, here are some passages in particular that aren’t clear.
6. This manuscript reads well, written at a fairly high level. The motivation provided are especially good. It would be nice if there were some solutions or at least longer hints for the (many) problems in the text. Overall the author should be encouraged to continue.

The most surprising thing was how short the comments were. I had expected that, given the review had consumed the entire summer, the reviewers would at least have read the manuscript in detail. But it turns out that mostly all that had been obtained were cursory impressions from the board members: the first four reviews were only a few sentences long! The fifth review was more detailed, but it was essentially a “spot check”.

I admit, I was really at a loss for how I should proceed. The comments were not terribly specific, and the only real action-able item were to use less extravagant terms in response to 1 (I originally had “configuration”, “exercise” vs “problem”, etc.) and to add solutions (in response to 5). When I showed he comments to Z, he commented that while they were positive, they seemed to suggest that the publication may not be anytime soon. So I decided to try submitting a second draft to the MAA, but if that didn’t work I would fall back on the self-publishing route.

The reviewers had commented about finding a few typos, so I again enlisted the help of some friends of mine to eliminate them. This time I was a lot smarter. First, I only sent the relevant excerpts that I wanted them to read, and watermarked the PDF’s with the names of the recipients. Secondly, this time I paid them as well: specifically, I gave dollars for each chapter read, where  was the number of errors found. I also gave a much clearer “I need this done by X” deadline. This worked significantly better than my first round of edits. Note to self: people feel more obliged to do a good job if you pay them!

All in all my friends probably eliminated about 500 errors.

I worked as rapidly as I could, and within four weeks I had the new version. The changes that I made were:

• In response to the first board comment, I eliminated some of the most extravagant terminology (“demonstration”, “configuration”, etc.) in favor of more conventional terms (“example”, “lemma”).
• I picked about 5-10 problems from each chapter and added full solutions for them. This inflated the manuscript by another 70 pages, for a new total of 400 pages.
• Many typos and revisions were corrected, thanks to my team of readers.
• Some formatting changes; most notably, I got the idea to put theorems and lemmas in boxes using mdframed (most of my recent olympiad handouts have the same boxes).
• Added several references.

I sent this out and sat back.

The Second Review

What followed was another long waiting process for what again were ended up being cursory comments The delay between the first and second review was definitely the most frustrating part — there seemed to be nothing I could do other than sit and wait. I seriously considered dropping the MAA and self-publishing during this time.

I had been told to expect comments back in the spring. Finally, in early April I poked the editorial board again asking whether there had been any progress, and was horrified to find out that the process hadn’t even started out due to a miscommunication. Fortunately, the editor was apologetic enough about the error that she asked the board to try to expedite the process a little. The comments then arrived in mid-May, six weeks afterwards.

There were eight reviewers this time. In addition to some stylistic changes suggested (e.g. avoid contractions), here were some of the main comments.

• The main complaint was that I had been a bit too informal. They were right on all accounts here: in the draft I had sent, the chapters had opened with some quotes from years of MOP (which confused the board, for obvious reasons) and I had some snarky comments about high school geometry (since I happen to despise the way Euclidean geometry is taught in high school.) I found it amusing that no one had brought it up yet, and happily obliged to fix them.
• Some reviewers had pointed out that some of the topics were very advanced. In fact, one of the reviewers actually recommend against the publication of the book on the account that no one would want to buy it. Fortunately, the book ended up getting accepted anyways.
• In that vein, there were some remarks that this book, although it serves its target audience well, is written at a fairly advanced level.

Some of the reviews were cursory like before, but some of them were line-by-line readings of a random chapter, and so this time I had something more tangible to work with.

So I proceeded to make the changes. For the first time, I finally had the brains to start using gitto track the changes I made to the book. This was an enormously good idea, and I wish I had done so earlier.

Here are some selected changes that were made (the full list of changes is quite long).

• Eliminate a bunch of snarky comments about high school, and the MOP quotes.
• Eliminate about 250 contractions.
• Eliminate about 50 instances of unnecessary future tense.
• Eliminate the real product from the text.
• Added in about seven new problems.
• Added and improved significantly on the index of the book, making it far more complete.
• Fix more references.
• Change the title to “Euclidean Geometry in Mathematical Olympiads” (it was originally “Geometra Galactica”).
• Change the name of Part II from “Dark Arts” to “Analytic Techniques”. (Hehe.)
• Added people to the acknowledgments.
• Changes in formatting: most notably I change the font size from 11pt to 10pt to decrease the page count, since my book was already twice as long as many of the other books in the series. This dropped me from about 400 pages back to about 350 pages.
• Fix about 200 more typos. Thanks to those of you who found them!

I sent out the third draft just as June started, about three weeks after I had received the comments. (I like to work fast.)

The Last Revisions

There were another two rounds afterwards. In late June, I got a small set of about three pages of additional typos and clarifying suggestions. I sent back the third draft one day later.

Six days later, I got back a list of four remaining edits to make. I sent an updated fourth draft 17 minutes after receiving those comments. Unfortunately, it then took another five weeks for the four changes I made to be acknowledged. Finally, in early August, the changes were approved and the editorial board forwarded an official recommendation to MAA to publish the book.

Summary of Review Timeline

In summary, the timeline of the review process was

• First draft submitted: April 6, 2014
• Feedback received: August 28, 2014
  Second draft submitted: November 5, 2014
• Feedback received: May 19, 2015
  Third draft submitted: June 23, 2015
• Feedback received: June 29, 2015
  Fourth draft submitted: June 29, 2015
• Official recommendation to MAA made: August 2015

I think with traditional publishers there is a lot of waiting; my understanding is that the editorial board largely consists of volunteers, so this seems inevitable.

Approval and Onwards

On September 3, 2015, I got the long-awaited message:

It is a pleasure to inform you that the MAA Council on Books has approved the recommendation of the MAA Problem Books editorial board to publish your manuscript, Euclidean Geometry in Mathematical Olympiads.

I got a fairly standard royalty contract from the publisher, which I signed off without much thought.

Editing

I had a total of zero math editors and one copy editor provided. It shows through on the enormous list of errors (and this is after all the mistakes my friends helped me find).

Fortunately, my copy editor was quite good (and I have a lot of sympathy for this poor soul, who had to read every word of the entire manuscript). My Git history indicates that approximately 1000 corrections were made; on average, this is about 2 per page, which sounds about right. I got the corrections on hard copy in the mail; the entire printout of my book, except well marked with red ink.

Many of the changes fell into general shapes:

• Capitalization. I was unwittingly inconsistent with “Law of Cosines” versus “Law of cosines” versus “law of cosines”, etc and my copy editor noticed every one of these. Similarly, cases of section and chapter titles were often not consistent; should I use “Angle Chasing” or “Angle chasing”? The main point is to pick one convention and stick with it.
• My copy editor pointed out every time I used “Problems for this section” and had only one problem.
• Several unnecessary “quotes” and italics were deleted.
• Oxford commas. My god, so many Oxford commas. You just don’t notice when the IMO Shortlist says “the circle through the points E, G, and H” but the European Girls’ Olympiad says “show that KH, EM and BC are concurrent”. I swear there were at least 100 of these in the boko. I tried to write a regular expression to find such mistakes, but there were lots of edge cases that came up, and I still had to do many of these manually.
• Inconsistency of em dashes and en dashes. This one worked better with regular expressions.

But of course there were plenty of other mistakes like missing spaces, missing degree spaces, punctuation errors, etc.

Cover Art

This was handled for me by the publisher: they gave me a choice of five or so designs and I picked one I liked.

(If you are self-publishing, this is actually one of the hardest parts of the publishing logistics; you need to design the cover on your own.)

Proofs

It turns out that after all the hard work I spent on formatting the draft, the MAA has a standard template and had the production team re-typeset the entire book using this format. Fortunately, the publisher’s format is pretty similar to mine, and so there were no huge cosmetic changes.

At this point I got the proofs, which are essentially the penultimate drafts of the book as they will be sent to the printers.

Affiliation and Miscellani

There was a bit more back-and-forth with the publisher towards the end. For example, they asked me if I would like my affiliation to be listed as MIT or to not have an affiliation. I chose the latter. I also send them a bio and photograph, and an author questionaire, asking me for some standard details.

Marketing was handled by the publisher based on these details.

The End

Without warning, I got an email on March 25 announcing that the PDF versions of my book were now available on MAA website. The hard copies followed a few months afterwards. That marked the end of my publication process.

If I were to do this sort of thing again, I guess the main decision would be whether to self-publish or go through a formal publisher. The main disadvantage seems to be the time delay, and possibly also that the royalties are lesser than in self-publishing. On the flip side, the advantages of a formal publisher were:

• Having a real copy editor read through the entire manuscript.
• Having a committee of outsiders knock some common sense into me (e.g. not calling the book “Geometra Galactica”).
• Having cover art and marketing completely done for me.
• It’s more prestigious; having a real published book is (for whatever reason) a very nice CV item.

Overall I think publishing formally was the right thing to do for this book, but your mileage may vary.

Other advice I would give to my past self, mentioned above already: keep paying O(1) for O(n), use git to keep track of all versions, and be conscious about which grammatical conventions to use (in particular, stay consistent).

Here’s a better concluding question: what surprised me about the process, i.e, what was different than what I expected? Here’s a partial list of answers:

• It took even longer than I was expecting. Large committees are inherently slow; this is no slight to the MAA, it is just how these sorts of things work.
• I was surprised that at no point did anyone really check the manuscript for mathematical accuracy. In hindsight this should have been obvious; I expect reading the entire book properly takes at least 1-2 years.
• I was astounded by how many errors there were in the text, be it math or grammatical or so on. During the entire process something like 2000 errors were corrected (admittedly several were minor, like Oxford commas). Yet even as I published the book, I knew that there had to be errors left. But it was still irritating to hear about them post-publication.

All in all, the entire process started in September 2013 and ended in March 2016, which is 30 months. The time was roughly 30% writing, 50% review, and 20% production.

https://usamo.wordpress.com/2017/01/05/facts-about-lie-groups-and-algebras/

Facts about Lie Groups and Algebras

POSTED ON JANUARY 5, 2017 BY EVAN CHEN (陳誼廷)

 

In Spring 2016 I was taking 18.757 Representations of Lie Algebras. Since I knew next to nothing about either Lie groups or algebras, I was forced to quickly learn about their basic facts and properties. These are the notes that I wrote up accordingly. Proofs of most of these facts can be found in standard textbooks, for example Kirillov.

1. Lie groups

Let  or , depending on taste.

Definition 1

A Lie group is a group  which is also a -manifold; the multiplication maps  (by ) and the inversion map  (by ) are required to be smooth.

A morphism of Lie groups is a map which is both a map of manifolds and a group homomorphism.

 

Throughout, we will let  denote the identity, or  if we need further emphasis.

Note that in particular, every group  can be made into a Lie group by endowing it with the discrete topology. This is silly, so we usually require only focus on connected groups:

Proposition 2 (Reduction to connected Lie groups)

Let  be a Lie group and  the connected component of  which contains . Then  is a normal subgroup, itself a Lie group, and the quotient  has the discrete topology.

 

In fact, we can also reduce this to the study of simply connected Lie groups as follows.

Proposition 3 (Reduction to simply connected Lie groups)

If  is connected, let  be its universal cover. Then  is a Lie group,  is a morphism of Lie groups, and .

 

Here are some examples of Lie groups.

Example 4 (Examples of Lie groups)

•  under addition is a real one-dimensional Lie group.
•  under addition is a complex one-dimensional Lie group (and a two-dimensional real Lie group)!
• The unit circle  is a real Lie group under multiplication.
•  is a Lie group of dimension . This example becomes important for representation theory: a representation of a Lie group  is a morphism of Lie groups .
•  is a Lie group of dimension .

 

As geometric objects, Lie groups  enjoy a huge amount of symmetry. For example, any neighborhood  of  can be “copied over” to any other point  by the natural map . There is another theorem worth noting, which is that:

Proposition 5

If  is a connected Lie group and  is a neighborhood of the identity , then generates  as a group.

 

2. Haar measure

Recall the following result and its proof from representation theory:

Claim 6

For any finite group ,  is semisimple; all finite-dimensional representations decompose into irreducibles.

 

Proof: Take a representation  and equip it with an arbitrary inner form . Then we can average it to obtain a new inner form

which is -invariant. Thus given a subrepresentation  we can just take its orthogonal complement to decompose . 
We would like to repeat this type of proof with Lie groups. In this case the notion doesn’t make sense, so we want to replace it with an integral  instead. In order to do this we use the following:

Theorem 7 (Haar measure)

Let  be a Lie group. Then there exists a unique Radon measure  (up to scaling) on which is left-invariant, meaning

for any Borel subset  and “translate” . This measure is called the (left) Haar measure.

 

Example 8 (Examples of Haar measures)

• The Haar measure on  is the standard Lebesgue measure which assigns  to the closed interval . Of course for any ,  for .
• The Haar measure on  is given by

  

  In particular, . One sees the invariance under multiplication of these intervals.

• Let . Then a Haar measure is given by

  

• For the circle group , consider . We can define

  

  across complex arguments . The normalization factor of  ensures .

 

Note that we have:

Corollary 9

If the Lie group  is compact, there is a unique Haar measure with .

 

This follows by just noting that if  is Radon measure on , then . This now lets us deduce that

Corollary 10 (Compact Lie groups are semisimple)

 is semisimple for any compact Lie group .

 

Indeed, we can now consider

as we described at the beginning.

3. The tangent space at the identity

In light of the previous comment about neighborhoods of  generating , we see that to get some information about the entire Lie group it actually suffices to just get “local” information of  at the point  (this is one formalization of the fact that Lie groups are super symmetric).

To do this one idea is to look at the tangent space. Let  be an -dimensional Lie group (over ) and consider  the tangent space to  at the identity . Naturally, this is a -vector space of dimension . We call it the Lie algebra associated to .

Example 11 (Lie algebras corresponding to Lie groups)

•  has a real Lie algebra isomorphic to .
•  has a complex Lie algebra isomorphic to .
• The unit circle  has a real Lie algebra isomorphic to , which we think of as the “tangent line” at the point .

Example 12 ()

Let’s consider , an open subset of . Its tangent space should just be an -dimensional -vector space. By identifying the components in the obvious way, we can think of this Lie algebra as just the set of all  matrices.

This Lie algebra goes by the notation .

 

Example 13 ()

Recall  is a Lie group of dimension , hence its Lie algebra should have dimension . To see what it is, let’s look at the special case  first: then

Viewing this as a polynomial surface  in , we compute

and in particular the tangent space to the identity matrix  is given by the orthogonal complement of the gradient

Hence the tangent plane can be identified with matrices satisfying . In other words, we see

By repeating this example in greater generality, we discover

4. The exponential map

Right now,  is just a vector space. However, by using the group structure we can get a map from  back into . The trick is “differential equations”:

Proposition 14 (Differential equations for Lie theorists)

Let  be a Lie group over  and  its Lie algebra. Then for every  there is a uniquehomomorphism

which is a morphism of Lie groups, such that

We will write  to emphasize the argument  being thought of as “time”. Thus this proposition should be intuitively clear: the theory of differential equations guarantees that  is defined and unique in a small neighborhood of . Then, the group structure allows us to extend  uniquely to the rest of , giving a trajectory across all of . This is sometimes called a one-parameter subgroup of , but we won’t use this terminology anywhere in what follows.

This lets us define:

Definition 15

Retain the setting of the previous proposition. Then the exponential map is defined by

The exponential map gets its name from the fact that for all the examples I discussed before, it is actually just the map . Note that below,  for a matrix ; this is called the matrix exponential.

Example 16 (Exponential Maps of Lie algebras)

• If , then  too. We observe  (where ) is a morphism of Lie groups . Hence

  

• Ditto for .
• For  and , the map  given by  works. Hence

  

• For , the map  given by  works nicely (now  is a matrix). (Note that we have to check  is actually invertible for this map to be well-defined.) Hence the exponential map is given by

  

• Similarly,

  

  Here we had to check that if , meaning , then . This can be seen by writing  in an upper triangular basis.

 

Actually, taking the tangent space at the identity is a functor. Consider a map  of Lie groups, with lie algebras  and . Because  is a group homomorphism, . Now, by manifold theory we know that maps  between manifolds gives a linear map between the corresponding tangent spaces, say . For us we obtain a linear map

In fact, this  fits into a diagram

Here are a few more properties of :

• , which is immediate by looking at the constant trajectory .
• , i.e. the total derivative  is the identity. This is again by construction.
• In particular, by the inverse function theorem this implies that  is a diffeomorphism in a neighborhood of , onto a neighborhood of .
•  commutes with the commutator. (By the above diagram.)

5. The commutator

Right now  is still just a vector space, the tangent space. But now that there is map , we can use it to put a new operation on , the so-called commutator.

The idea is follows: we want to “multiply” two elements of . But  is just a vector space, so we can’t do that. However,  itself has a group multiplication, so we should pass to  using , use the multiplication in  and then come back.

Here are the details. As we just mentioned,  is a diffeomorphism near . So for , close to the origin of , we can look at  and , which are two elements of close to . Multiplying them gives an element still close to , so its equal to  for some unique , call it .

One can show in fact that  can be written as a Taylor series in two variables as

where  is a skew-symmetric bilinear map, meaning . It will be more convenient to work with  than  itself, so we give it a name:

Definition 17

This  is called the commutator of .

 

Now we know multiplication in  is associative, so this should give us some nontrivial relation on the bracket . Specifically, since

we should have that , and this should tell us something. In fact, the claim is:

Theorem 18

The bracket  satisfies the Jacobi identity

Proof: Although I won’t prove it, the third-order terms (and all the rest) in our definition of  can be written out explicitly as well: for example, for example, we actually have

The general formula is called the Baker-Campbell-Hausdorff formula.

Then we can force ourselves to expand this using the first three terms of the BCS formula and then equate the degree three terms. The left-hand side expands initially as , and the next step would be something ugly.

This computation is horrifying and painful, so I’ll pretend I did it and tell you the end result is as claimed. 
There is a more natural way to see why this identity is the “right one”; see Qiaochu. However, with this proof I want to make the point that this Jacobi identity is not our decision: instead, the Jacobi identity is forced upon us by associativity in .

Example 19 (Examples of commutators attached to Lie groups)

• If  is an abelian group, we have  by symmetry and from . Thus  in  for any abelian Lie group .
• In particular, the brackets for  are trivial.
• Let . Then one can show that

  

• Ditto for .

 

In any case, with the Jacobi identity we can define an general Lie algebra as an intrinsic object with a Jacobi-satisfying bracket:

Definition 20

A Lie algebra over  is a -vector space equipped with a skew-symmetric bilinear bracket  satisfying the Jacobi identity.

A morphism of Lie algebras and preserves the bracket.

 

Note that a Lie algebra may even be infinite-dimensional (even though we are assuming  is finite-dimensional, so that they will never come up as a tangent space).

Example 21 (Associative algebra  Lie algebra)

Any associative algebra  over  can be made into a Lie algebra by taking the same underlying vector space, and using the bracket .

 

6. The fundamental theorems

We finish this list of facts by stating the three “fundamental theorems” of Lie theory. They are based upon the functor

we have described earlier, which is a functor

• from the category of Lie groups
• into the category of finite-dimensional Lie algebras.

The first theorem requires the following definition:

Definition 22

A Lie subgroup  of a Lie group  is a subgroup  such that the inclusion map  is also an injective immersion.

A Lie subalgebra  of a Lie algebra  is a vector subspace preserved under the bracket (meaning that ).

 

Theorem 23 (Lie I)

Let  be a real or complex Lie group with Lie algebra . Then given a Lie subgroup , the map

is a bijection between Lie subgroups of  and Lie subalgebras of .

 

Theorem 24 (The Lie functor is an equivalence of categories)

Restrict  to a functor

• from the category of simply connected Lie groups over 
• to the category of finite-dimensional Lie algebras over .

Then

1. (Lie II)  is fully faithful, and
2. (Lie III)  is essentially surjective on objects.

If we drop the “simply connected” condition, we obtain a functor which is faithful and exact, but not full: non-isomorphic Lie groups can have isomorphic Lie algebras (one example is  and ).

 

https://usamo.wordpress.com/2017/04/08/on-designing-olympiad-training/

Some Thoughts on Olympiad Material Design

POSTED ON APRIL 8, 2017 BY EVAN CHEN (陳誼廷)

10

(This is a bit of a follow-up to the solution reading post last month. Spoiler warnings: USAMO 2014/6, USAMO 2012/2, TSTST 2016/4, and hints for ELMO 2013/1, IMO 2016/2.)

I want to say a little about the process which I use to design my olympiad handouts and classes these days (and thus by extension the way I personally think about problems). The short summary is that my teaching style is centered around showing connections and recurring themes between problems.

Now let me explain this in more detail.

 

1. Main ideas

Solutions to olympiad problems can look quite different from one another at a surface level, but typically they center around one or two main ideas, as I describe in my post on reading solutions. Because details are easy to work out once you have the main idea, as far as learning is concerned you can more or less throw away the details and pay most of your attention to main ideas.

Thus whenever I solve an olympiad problem, I make a deliberate effort to summarize the solution in a few sentences, such that I basically know how to do it from there. I also make a deliberate effort, whenever I write up a solution in my notes, to structure it so that my future self can see all the key ideas at a glance and thus be able to understand the general path of the solution immediately.

The example I’ve previously mentioned is USAMO 2014/6.

Example 1 (USAMO 2014, Gabriel Dospinescu)

Prove that there is a constant  with the following property: If  are positive integers such that  for all , then

 

If you look at any complete solution to the problem, you will see a lot of technical estimates involving  and the like. But the main idea is very simple: “consider an  table of primes and note the small primes cannot adequately cover the board, since ”. Once you have this main idea the technical estimates are just the grunt work that you force yourself to do if you’re a contestant (and don’t do if you’re retired like me).

Thus the study of olympiad problems is reduced to the study of main ideas behind these problems.

 

2. Taxonomy

So how do we come up with the main ideas? Of course I won’t be able to answer this question completely, because therein lies most of the difficulty of olympiads.

But I do have some progress in this way. It comes down to seeing how main ideas are similar to each other. I spend a lot of time trying to classify the main ideas into categories or themes, based on how similar they feel to one another. If I see one theme pop up over and over, then I can make it into a class.

I think olympiad taxonomy is severely underrated, and generally not done correctly. The status quo is that people do bucket sorts based on the particular technical details which are present in the problem. This is correlated with the main ideas, but the two do not always coincide.

An example where technical sort works okay is Euclidean geometry. Here is a simple example: harmonic bundles in projective geometry. As I explain in my book, there are a few “basic” configurations involved:

• Midpoints and parallel lines
• The Ceva / Menelaus configuration
• Harmonic quadrilateral / symmedian configuration
• Apollonian circle (right angle and bisectors)

(For a reference, see Lemmas 2, 4, 5 and Exercise 0 here.) Thus from experience, any time I see one of these pictures inside the current diagram, I think to myself that “this problem feels projective”; and if there is a way to do so I try to use harmonic bundles on it.

An example where technical sort fails is the “pigeonhole principle”. A typical problem in such a class looks something like USAMO 2012/2.

Example 2 (USAMO 2012, Gregory Galperin)

A circle is divided into congruent arcs by  points. The points are colored in four colors such that some  points are colored Red, some  points are colored Green, some points are colored Blue, and the remaining  points are colored Yellow. Prove that one can choose three points of each color in such a way that the four triangles formed by the chosen points of the same color are congruent.

 

It’s true that the official solution uses the words “pigeonhole principle” but that is not really the heart of the matter; the key idea is that you consider all possible rotations and count the number of incidences. (In any case, such calculations are better done using expected value anyways.)

Now why is taxonomy a good thing for learning and teaching? The reason is that building connections and seeing similarities is most easily done by simultaneously presenting several related problems. I’ve actually mentioned this already in a different blog post, but let me give the demonstration again.

Suppose I wrote down the following:

You can tell what each of the ‘s, ‘s, ‘s have in common by looking for a few moments. But what happens if I intertwine them?

This is the same information, but now you have to work much harder to notice the association between the letters and the numbers they’re next to.

This is why, if you are an olympiad student, I strongly encourage you to keep a journal or blog of the problems you’ve done. Solving olympiad problems takes lots of time and so it’s worth it to spend at least a few minutes jotting down the main ideas. And once you have enough of these, you can start to see new connections between problems you haven’t seen before, rather than being confined to thinking about individual problems in isolation. (Additionally, it means you will never have redo problems to which you forgot the solution — learn from my mistake here.)

 

3. Ten buckets of geometry

I want to elaborate more on geometry in general. These days, if I see a solution to a Euclidean geometry problem, then I mentally store the problem and solution into one (or more) buckets. I can even tell you what my buckets are:

1. Direct angle chasing
2. Power of a point / radical axis
3. Homothety, similar triangles, ratios
4. Recognizing some standard configuration (see Yufei for a list)
5. Doing some length calculations
6. Complex numbers
7. Barycentric coordinates
8. Inversion
9. Harmonic bundles or pole/polar and homography
10. Spiral similarity, Miquel points

which my dedicated fans probably recognize as the ten chapters of my textbook. (Problems may also fall in more than one bucket if for example they are difficult and require multiple key ideas, or if there are multiple solutions.)

Now whenever I see a new geometry problem, the diagram will often “feel” similar to problems in a certain bucket. Exactly what I mean by “feel” is hard to formalize — it’s a certain gut feeling that you pick up by doing enough examples. There are some things you can say, such as “problems which feature a central circle and feet of altitudes tend to fall in bucket 6”, or “problems which only involve incidence always fall in bucket 9”. But it seems hard to come up with an exhaustive list of hard rules that will do better than human intuition.

 

4. How do problems feel?

But as I said in my post on reading solutions, there are deeper lessons to teach than just technical details.

For examples of themes on opposite ends of the spectrum, let’s move on to combinatorics. Geometry is quite structured and so the themes in the main ideas tend to translate to specific theorems used in the solution. Combinatorics is much less structured and many of the themes I use in combinatorics cannot really be formalized. (Consequently, since everyone else seems to mostly teach technical themes, several of the combinatorics themes I teach are idiosyncratic, and to my knowledge are not taught by anyone else.)

For example, one of the unusual themes I teach is called Global. It’s about the idea that to solve a problem, you can just kind of “add up everything at once”, for example using linearity of expectation, or by double-counting, or whatever. In particular these kinds of approach ignore the “local” details of the problem. It’s hard to make this precise, so I’ll just give two recent examples.

Example 3 (ELMO 2013, Ray Li)

Let  be nine real numbers, not necessarily distinct, with average . Let denote the number of triples  for which . What is the minimum possible value of ?

 

Example 4 (IMO 2016)

Find all integers  for which each cell of  table can be filled with one of the letters ,  and  in such a way that:

• In each row and column, one third of the entries are , one third are  and one third are ; and
• in any diagonal, if the number of entries on the diagonal is a multiple of three, then one third of the entries are , one third are  and one third are .

 

If you look at the solutions to these problems, they have the same “feeling” of adding everything up, even though the specific techniques are somewhat different (double-counting for the former, diagonals modulo  for the latter). Nonetheless, my experience with problems similar to the former was immensely helpful for the latter, and it’s why I was able to solve the IMO problem.

 

5. Gaps

This perspective also explains why I’m relatively bad at functional equations. There are somethings I can say that may be useful (see my handouts), but much of the time these are just technical tricks. (When sorting functional equations in my head, I have a bucket called “standard fare” meaning that you “just do work”; as far I can tell this bucket is pretty useless.) I always feel stupid teaching functional equations, because I never have many good insights to say.

Part of the reason is that functional equations often don’t have a main idea at all. Consequently it’s hard for me to do useful taxonomy on them.

Then sometimes you run into something like the windmill problem, the solution of which is fairly “novel”, not being similar to problems that come up in training. I have yet to figure out a good way to train students to be able to solve windmill-like problems.

 

6. Surprise

I’ll close by mentioning one common way I come up with a theme.

Sometimes I will run across an olympiad problem  which I solve quickly, and think should be very easy, and yet once I start grading  I find that the scores are much lower than I expected. Since the way I solve problems is by drawing experience from similar previous problems, this must mean that I’ve subconsciously found a general framework to solve problems like , which is not obvious to my students yet. So if I can put my finger on what that framework is, then I have something new to say.

The most recent example I can think of when this happened was TSTST 2016/4 which was given last June (and was also a very elegant problem, at least in my opinion).

Example 5 (TSTST 2016, Linus Hamilton)

Let  be a positive integers. Prove that we must apply the Euler  function at least times before reaching .

 

I solved this problem very quickly when we were drafting the TSTST exam, figuring out the solution while walking to dinner. So I was quite surprised when I looked at the scores for the problem and found out that empirically it was not that easy.

After I thought about this, I have a new tentative idea. You see, when doing this problem I really was thinking about “what does this  operation do?”. You can think of  as an infinite tuple

of prime exponents. Then the  can be thought of as an operation which takes each nonzero component, decreases it by one, and then adds some particular vector back. For example, if  then  is decreased by one and each of  and  are increased by one. In any case, if you look at this behavior for long enough you will see that the  coordinate is a natural way to “track time” in successive  operations; once you figure this out, getting the bound of  is quite natural. (Details left as exercise to reader.)

Now when I read through the solutions, I found that many of them had not really tried to think of the problem in such a “structured” way, and had tried to directly solve it by for example trying to prove  (which is false) or something similar to this. I realized that had the students just ignored the task “prove ” and spent some time getting a better understanding of the  structure, they would have had a much better chance at solving the problem. Why had I known that structural thinking would be helpful? I couldn’t quite explain it, but it had something to do with the fact that the “main object” of the question was “set in stone”; there was no “degrees of freedom” in it, and it was concrete enough that I felt like I could understand it. Once I understood how multiple  operations behaved, the bit about  almost served as an “answer extraction” mechanism.

These thoughts led to the recent development of a class which I named Rigid, which is all about problems where the point is not to immediately try to prove what the question asks for, but to first step back and understand completely how a particular rigid structure (like the  in this problem) behaves, and to then solve the problem using this understanding.

https://usamo.wordpress.com/2017/03/06/on-reading-solutions/

On Reading Solutions

POSTED ON MARCH 6, 2017 BY EVAN CHEN (陳誼廷)

3

(Ed Note: This was earlier posted under the incorrect title “On Designing Olympiad Training”. How I managed to mess that up is a long story involving some incompetence with Python scripts, but this is fixed now.)

Spoiler warnings: USAMO 2014/1, and hints for Putnam 2014 A4 and B2. You may want to work on these problems yourself before reading this post.

1. An Apology

At last year’s USA IMO training camp, I prepared a handout on writing/style for the students at MOP. One of the things I talked about was the “ocean-crossing point”, which for our purposes you can think of as the discrete jump from a problem being “essentially not solved” () to “essentially solved” (). The name comes from a Scott Aaronson post:

Suppose your friend in Boston blindfolded you, drove you around for twenty minutes, then took the blindfold off and claimed you were now in Beijing. Yes, you do see Chinese signs and pagoda roofs, and no, you can’t immediately disprove him — but based on your knowledge of both cars and geography, isn’t it more likely you’re just in Chinatown? . . . We start in Boston, we end up in Beijing, and at no point is anything resembling an ocean ever crossed.

I then gave two examples of how to write a solution to the following example problem.

Problem 1 (USAMO 2014)

Let , , ,  be real numbers such that  and all zeros , , , and  of the polynomial  are real. Find the smallest value the product

can take.

 

Proof: (Not-so-good write-up) Since  for every (where ), we get  which equals to . If  this is  and . Also, , this is . 

Proof: (Better write-up) The answer is . This can be achieved by taking , whence the product is , and .

Now, we prove this is a lower bound. Let . The key observation is that

Consequently, we have

This proves the lower bound. 

You’ll notice that it’s much easier to see the key idea in the second solution: namely,

which allows you use the enigmatic condition .

Unfortunately I have the following confession to make:

In practice, most solutions are written more like the first one than the second one.

The truth is that writing up solutions is sort of a chore that people never really want to do but have to — much like washing dishes. So must solutions won’t be written in a way that helps you learn from them. This means that when you read solutions, you should assume that the thing you really want (i.e., the ocean-crossing point) is buried somewhere amidst a haystack of other unimportant details.

 

2. Diff

But in practice even the “better write-up” I mentioned above still has too much information in it.

Suppose you were explaining how to solve this problem to a friend. You would probably not start your explanation by saying that the minimum is , achieved by  — even though this is indeed a logically necessary part of the solution. Instead, the first thing you would probably tell them is to notice that

In fact, if your friend has been working on the problem for more than ten minutes, this is probably the only thing you need to tell them. They probably already figured out by themselves that there was a good chance the answer would be , just based on the condition . This “one-liner” is all that they need to finish the problem. You don’t need to spell out to them the rest of the details.

When you explain a problem to a friend in this way, you’re communicating just the difference: the one or two sentences such that your friend could work out the rest of the details themselves with these directions. When reading the solution yourself, you should try to extract the main idea in the same way. Olympiad problems generally have only a few main ideas in them, from which the rest of the details can be derived. So reading the solution should feel much like searching for a needle in a haystack.

 

3. Don’t Read Line by Line

In particular: you should rarely read most of the words in the solution, and you should almost never read every word of the solution.

Whenever I read solutions to problems I didn’t solve, I often read less than 10% of the words in the solution. Instead I search aggressively for the one or two sentences which tell me the key step that I couldn’t find myself. (Functional equations are the glaring exception to this rule, since in these problems there sometimes isn’t any main idea other than “stumble around randomly”, and the steps really are all about equally important. But this is rarer than you might guess.)

I think a common mistake students make is to treat the solution as a sequence of logical steps: that is, reading the solution line by line, and then verifying that each line follows from the previous ones. This seems to entirely miss the point, because not all lines are created equal, and most lines can be easily derived once you figure out the main idea.

If you find that the only way that you can understand the solution is reading it step by step, then the problem may simply be too hard for you. This is because what counts as “details” and “main ideas” are relative to the absolute difficulty of the problem. Here’s an example of what I mean: the solution to a USAMO 3/6 level geometry problem, call it , might look as follows.

Proof: First, we prove lemma . (Proof of , which is USAMO 1/4 level.)

Then, we prove lemma . (Proof of , which is USAMO 1/4 level.)

Finally, we remark that putting together  and  solves the problem. 

Likely the main difficulty of  is actually finding  and . So a very experienced student might think of the sub-proofs  as “easy details”. But younger students might find challenging in their own right, and be unable to solve the problem even after being told what the lemmas are: which is why it is hard for them to tell that  were the main ideas to begin with. In that case, the problem  is probably way over their head.

This is also why it doesn’t make sense to read solutions to problems which you have not worked on at all — there are often details, natural steps and notation, et cetera which are obvious to you if and only if you have actually tried the problem for a little while yourself.

 

4. Reflection

The earlier sections describe how to extract the main idea of an olympiad solution. This is neat because instead of having to remember an entire solution, you only need to remember a few sentences now, and it gives you a good understanding of the solution at hand.

But this still isn’t achieving your ultimate goal in learning: you are trying to maximize your scores on future problems. Unless you are extremely fortunate, you will probably never see the exact same problem on an exam again.

So one question you should often ask is:

“How could I have thought of that?”

(Or in my case, “how could I train a student to think of this?”.)

There are probably some surface-level skills that you can pick out of this. The lowest hanging fruit is things that are technical. A small number of examples, with varying amounts of depth:

• This problem is “purely projective”, so we can take a projective transformation!
• This problem had a segment  with midpoint , and a line  parallel to , so I should consider projecting  through a point on .
• Drawing a grid of primes is the only real idea in this problem, and the rest of it is just calculations.
• This main claim is easy to guess since in some small cases, the frogs have “violating points” in a large circle.
• In this problem there are  numbers on a circle,  odd. The counterexamples for even alternate up and down, which motivates proving that no three consecutive numbers are in sorted order.
• This is a juggling problem!

(Brownie points if any contest enthusiasts can figure out which problems I’m talking about in this list!)

5. Learn Philosophy, not Formalism

But now I want to point out that the best answers to the above question are often not formalizable. Lists of triggers and actions are “cheap forms of understanding”, because going through a list of methods will only get so far.

On the other hand, the un-formalizable philosophy that you can extract from reading a question, is part of that legendary “intuition” that people are always talking about: you can’t describe it in words, but it’s certainly there. Maybe I would even be better if I reframed the question as:

“What does this problem feel like?”

So let’s talk about our feelings. Here is David Yang’s take on it:

Whenever you see a problem you really like, store it (and the solution) in your mind like a cherished memory . . . The point of this is that you will see problems which will remind you of that problem despite having no obvious relation. You will not be able to say concretely what the relation is, but think a lot about it and give a name to the common aspect of the two problems. Eventually, you will see new problems for which you feel like could also be described by that name.

Do this enough, and you will have a very powerful intuition that cannot be described easily concretely (and in particular, that nobody else will have).

This itself doesn’t make sense without an example, so here is an example of one philosophy I’ve developed. Here are two problems on Putnam 2014:

Problem 2 (Putnam 2014 A4)

Suppose  is a random variable that takes on only nonnegative integer values, with, , and . Determine the smallest possible value of the probability of the event .

 

Problem 3 (Putnam 2014 B2)

Suppose that  is a function on the interval  such that  for all  and

How large can  be?

 

At a glance there seems to be nearly no connection between these problems. One of them is a combinatorics/algebra question, and the other is an integral. Moreover, if you read the official solutions or even my own write-ups, you will find very little in common joining them.

Yet it turns out that these two problems do have something in common to me, which I’ll try to describe below. My thought process in solving either question went as follows:

In both problems, I was able to quickly make a good guess as to what the optimal / was, and then come up with a heuristic explanation (not a proof) why that guess had to be correct, namely, “by smoothing, you should put all the weight on the left”. Let me call this optimal argument .

That conjectured  gave a numerical answer to the actual problem: but for both of these problems, it turns out that numerical answer is completely uninteresting, as are the exact details of . It should be philosophically be interpreted as “this is the number that happens to pop out when you plug in the optimal choice”. And indeed that’s what both solutions feel like. These solutions don’t actually care what the exact values of  are, they only care about the properties that made me think they were optimal in the first place.

I gave this philosophy the name Equality, with poster description “problems where looking at the equality case is important”. This text description feels more or less useless to me; I suppose it’s the thought that counts. But ever since I came up with this name, it has helped me solve new problems that come up, because they would give me the same feeling that these two problems did.

Two more examples of these themes that I’ve come up with are Global and Rigid, which will be described in a future post on how I design training materials.

https://usamo.wordpress.com/2018/01/05/lessons-from-math-olympiads/

Lessons from Math Olympiads

POSTED ON JANUARY 5, 2018 BY EVAN CHEN (陳誼廷)

1

In a previous post I tried to make the point that math olympiads should not be judged by their relevance to research mathematics. In doing so I failed to actually explain why I think math olympiads are a valuable experience for high schoolers, so I want to make amends here.

1. Summary

In high school I used to think that math contests were primarily meant to encourage contestants to study some math that is (much) more interesting than what’s typically shown in high school. While I still think this is one goal, and maybe it still is the primary goal in some people’s minds, I no longer believe this is the primary benefit.

My current belief is that there are two major benefits from math competitions:

1. To build a social network for gifted high school students with similar interests.
2. To provide a challenging experience that lets gifted students grow and develop intellectually.

I should at once disclaim that I do not claim these are the only purpose of mathematical olympiads. Indeed, mathematics is a beautiful subject and introducing competitors to this field of study is of course a great thing (in particular it was life-changing for me). But as I have said before, many alumni of math olympiads do not eventually become mathematicians, and so in my mind I would like to make the case that these alumni have gained a lot from the experience anyways.

2. Social experience

Now that we have email, Facebook, Art of Problem Solving, and whatnot, the math contest community is much larger and stronger than it’s ever been in the past. For the first time, it’s really possible to stay connected with other competitors throughout the entire year, rather than just seeing each other a handful of times during contest season. There’s literally group chats of contestants all over the country where people talk about math problems or the solar eclipse or share funny pictures or inside jokes or everything else. In many ways, being part of the high school math contest community is a lot like having access to the peer group at a top-tier university, except four years earlier.

There’s some concern that a competitive culture is unhealthy for the contestants. I want to make a brief defense here.

I really do think that the contest community is good at being collaborative rather than competitive. You can imagine a world where the competitors think about contests in terms of trying to get a better score than the other person. [1] That would not be a good world. But I think by and large the community is good at thinking about it as just trying to maximize their own score. The score of the person next to you isn’t supposed to matter (and thinking about it doesn’t help, anyways).

Put more bluntly, on contest day, you have one job: get full marks. [2]

Because we have a culture of this shape, we now get a group of talented students all working towards the same thing, rather than against one another. That’s what makes it possible to have a self-supportive community, and what makes it possible for the contestants to really become friends with each other.

I think the strongest contestants don’t even care about the results of contests other than the few really important ones (like USAMO/IMO). It is a long-running joke that the Harvard-MIT Math Tournament is secretly just a MOP reunion, and I personally see to it that this happens every year. [3]

I’ve also heard similar sentiments about ARML:

I enjoy ARML primarily based on the social part of the contest, and many people agree with me; the highlight of ARML for some people is the long bus ride to the contest. Indeed, I think of ARML primarily as a social event, with some mathematics to make it look like the participants are actually doing something important.

(Don’t tell the parents.)

3. Intellectual growth

My view is that if you spend a lot of time thinking or working about anything deep, then you will learn and grow from the experience, almost regardless of what that thing is at an object level. Take chess as an example — even though chess definitely has even fewer “real-life applications” than math, if you take anyone with a 2000+ rating I don’t think many of them would think that the time they invested into the game was wasted. [4]

Olympiad mathematics seems to be no exception to this. In fact the sheer depth and difficulty of the subject probably makes it a particularly good example. [5]

I’m now going to fill this section with a bunch of examples although I don’t claim the list is exhaustive. First, here are the ones that everyone talks about and more or less agrees on:

• Learning how to think, because, well, that’s how you solve a contest problem.
• Learning to work hard and not give up, because the contest is difficult and you will not win by accident; you need to actually go through a lot of training.
• Dual to above, learning to give up on a problem, because sometime the problem really is too hard for you and you won’t solve it even if you spend another ten or twenty or fifty hours, and you have to learn to cut your losses. There is a balancing act here that I think really is best taught by experience, rather than the standard high-school moral cheerleading where you are supposed to “never give up” or something.
• But also learning to be humble or to ask for help, which is a really hard thing for a lot of young contestants to do.
• Learning to be patient, not only with solving problems but with the entire journey. You usually do not improve dramatically overnight.

Here are some others I also believe, but don’t hear as often.

• Learning to be independent, because odds are your high-school math teacher won’t be able to help you with USAMO problems. Training for the highest level of contests is these days almost always done more or less independently. I think having the self-motivation to do the training yourself, as well as the capacity to essentially have to design your own training (making judgments on what to work on, et cetera) is itself a valuable cross-domain skill. (I’m a little sad sometimes that by teaching I deprive my students of the opportunity to practice this. It is a cost.)
• Being able to work neatly, not because your parents told you to but because if you are sloppy then it will cost you points when you make small (or large) errors on IMO #1. Olympiad problems are difficult enough as is, and you do not want to let them become any harder because of your own sloppiness. (And there are definitely examples of olympiad problems which are impossible to solve if you are not organized.)
• Being able to organize and write your thoughts well, because some olympiad problems are complex and requires putting together more than one lemma or idea together to solve. For this to work, you need to have the skill of putting together a lot of moving parts into a single coherent argument. Bonus points here if your audience is someone you care about (as opposed to a grader), because then you have to also worry about making the presentation as clean and natural as possible.

  These days, whenever I solve a problem I always take the time to write it up cleanly, because in the process of doing so I nearly always find ways that the solution can be made shorter or more elegant, or at least philosophically more natural. (I also often find my solution is wrong.) So it seems that the write-up process here is not merely about presenting the same math in different ways: the underlying math really does change. [6]

• Thinking about how to learn. For example, the Art of Problem Solving forums are often filled with questions of the form “what should I do?”. Many older users find these questions obnoxious, but I find them desirable. I think being able to spend time pondering about what makes people improve or learn well is a good trait to develop, rather than mindlessly doing one book after another.

  Of course, many of the questions I referred to are poor, either with no real specific direction: often the questions are essentially “what book should I read?”, or “give me a exhaustive list of everything I should know”. But I think this is inevitable because these are people’s first attempts at understanding contest training. Just like the first difficult math contest you take often goes quite badly, the first time you try to think about learning, you will probably ask questions you will be embarrassed about in five years. My hope is that as these younger users get older and wiser, the questions and thoughts become mature as well. To this end I do not mind seeing people wobble on their first steps.

• Being honest with your own understanding, particularly of fundamentals. When watching experienced contestants, you often see people solving problems using advanced techniques like Brianchon’s theorem or the n-1 equal value principle or whatever. It’s tempting to think that if you learn the names and statements of all these advanced techniques then you’ll be able to apply them too. But the reality is that these techniques are advanced for a reason: they are hard to use without mastery of fundamentals.

  This is something I definitely struggled with as a contestant: being forced to patiently learn all the fundamentals and not worry about the fancy stuff. To give an example, the 2011 JMO featured an inequality which was routine for experienced or well-trained contestants, but “almost impossible for people who either have not seen inequalities at all or just like to compile famous names in their proofs”. I was in the latter category, and tried to make up a solution using multivariable Jensen, whatever that meant. Only when I was older did I really understand what I was missing.

• Dual to the above, once you begin to master something completely you start to learn what different depths of understanding feel like, and an appreciation for just how much effort goes into developing a mastery of something.
• Being able to think about things which are not well-defined. This one often comes as a surprise to people, since math is a field which is known for its precision. But I still maintain that this a skill contests train for.

  A very simple example is a question like, “when should I use the probabilistic method?”. Yes, we know it’s good for existence questions, but can we say anything more about when we expect it to work? Well, one heuristic (not the only one) is “if a monkey could find it” — the idea that a randomly selected object “should” work. But obviously something like this can’t be subject to a (useful) formal definition that works 100% of the time, and there are plenty of contexts in which even informally this heuristic gives the wrong answer. So that’s an example of a vague and nebulous concept that’s nonetheless necessary in order to understanding the probabilistic method well.

  There are much more general examples one can say. What does it mean for a problem to “feel projective”? I can’t tell you a hard set of rules; you’ll have to do a bunch of examples and gain the intuition yourself. Why do I say this problem is “rigid”? Same answer. How do you tell which parts of this problem are natural, and which are artificial? How do you react if you have the feeling the problem gives you nothing to work with? How can you tell if you are making progress on a problem? Trying to figure out partial answers to these questions, even if they can’t be put in words, will go a long way in improving the mythical intuition that everyone knows is so important.

  It might not be unreasonable to say that by this point we are studying philosophy, and that’s exactly what I intend. When I teach now I often make a point of referring to the “morally correct” way of thinking about things, or making a point of explaining why X should be true, rather than just providing a proof. I find this type of philosophy interesting in its own right, but that is not the main reason I incorporate it into my teaching. I teach the philosophy now because it is necessary, because you will solve fewer problems without that understanding.

4. I think if you don’t do well, it’s better to you

But I think the most surprising benefit of math contests is that most participants won’t win. In high school everyone tells you that if you work hard you will succeed. The USAMO is a fantastic counterexample to this. Every year, there are exactly 12 winners on the USAMO. I can promise you there are far more than 12 people who work very hard every year with the hope of doing well on the USAMO. Some people think this is discouraging, but I find it desirable.

Let me tell you a story.

Back in September of 2015, I sneaked in to the parent’s talk at Math Prize for Girls, because Zuming Feng was speaking and I wanted to hear what he had to say. (The whole talk was is available on YouTube now.) The talk had a lot of different parts that I liked, but one of them struck me in particular, when he recounted something he said to one of his top students:

I really want you to work hard, but I really think if you don’t do well, if you fail, it’s better to you.

I had a hard time relating to this when I first heard it, but it makes sense if you think about it. What I’ve tried to argue is that the benefit of math contests is not that the contestant can now solve N problems on USAMO in late April, but what you gain from the entire year of practice. And so if you hold the other 363 days fixed, and then vary only the final outcome of the USAMO, which of success and failure is going to help a contestant develop more as a person?

For that reason I really like to think that the final lesson from high school olympiads is how to appreciate the entire journey, even in spite of the eventual outcome.

Footnotes

1. I actually think this is one of the good arguments in favor of the new JMO/USAMO system introduced in 2010. Before this, it was not uncommon for participants in 9th and 10th grade to really only aim for solving one or two entry-level USAMO problems to qualify for MOP. To this end I think the mentality of “the cutoff will probably only be X, so give up on solving problem six” is sub-optimal.
2. That’s a Zuming quote.
3. Which is why I think the HMIC is actually sort of pointless from a contestant’s perspective, but it’s good logistics training for the tournament directors.
4. I could be wrong about people thinking chess is a good experience, given that I don’t actually have any serious chess experience beyond knowing how the pieces move. A cursory scan of the Internet suggests otherwise (was surprised to find that Ben Franklinhas an opinion on this) but it’s possible there are people who think chess is a waste of time, and are merely not as vocal as the people who think math contests are a waste of time.
5. Relative to what many high school students work on, not compared to research or something.
6. Privately, I think that working in math olympiads taught me way more about writing well than English class ever did; English class always felt to me like the skill of trying to sound like I was saying something substantial, even when I wasn’t.