Rainbow Arithmetic Progressions II: The Collaboration

by Derrick Stolee

In the previous post I briefly discussed the algorithms that played a role in the recent paper Rainbow arithmetic progressions. Today, I want to take a detour from our typical discussion of computational methods and instead discuss the collaboration that led to this paper.

It is important to explicitly say that while this paper was very collaborative, and used the expertise and hard work of many individuals, this blog post was written entirely by me during office hours and in a hurry. Any opinions, errors, or other reason to be angry with the content here is entirely my fault and not the fault of my fantastic coauthors. While I’m at it, let me actually list my coauthors by name:

Steve Butler, Craig Erickson, Leslie Hogben, Kirsten Hogenson, Lucas Kramer, Richard L. Kramer, Jephian C.-H. Lin, Ryan R. Martin, Nathan Warnberg, and Michael Young.

The Setup

Iowa State has an existing Discrete Mathematics Seminar that features research talks by students, faculty, and visitors. We can typically fill every week of the academic year with quality talks, and that brings all of our Discrete Math faculty and graduate students into the same room every week. The seminar is usually the only way we learn what other people in the group are working on. Collaboration between graduate students is uncommon in order to make sure our graduate students have enough independent research to justify a dissertation. Certain programs, such as Leslie Hogben’s Early Graduate Research (EGR; pronounced “eager”) class aim to help with this, but in one semester there is only so much they can do.

As far as I can tell, the idea to do a working seminar was initiated by Leslie and Michael. Leslie’s experience with EGR helped her know what could be possible with graduate students, but we wanted to see what would happen when faculty were allowed to make meaningful contributions, instead of having graduate students be completely independent. Michael had recently advised a Masters student through a creative component on various problems in rainbow colorings of arithmetic progressions, so he had some problems with some initial, unpublished work.

Michael presented the existing work on these topics, and had two main “problems” at hand. One was the anti-van der Waerden numbers that we discussed. The other was a related counting problem, but there was no immediate dependence between the problems. The hope was that certain people were attracted to different problems, and the group would naturally split into two. We did not want to make that distinction until both problems were fully discussed, and I think that is our downfall. We abandoned one problem and continued as one large group. This led to an 11-author paper.

The Working

The working seminar met for one hour a week, immediately after the normal seminar (with a 10-minute break between). We would open the floor to questions and comments from last time, to see if anything needed to be clarified. If anyone had an idea to get started, then that person would go to the board and start writing their ideas. The rest of the group would watch and comment as necessary. It was very interactive: one person was at the board directing the conversation, but all participants were able to chip in and comment or question.

One goal that we had was that no one would spend time working on the problem outside of the seminar. Graduate students took responsibility of writing up the details of the discussion from the day, including concrete questions to tackle the next week. Still, this should not be overly taxing on the graduate students, so the writing would rotate among the students. However, a couple students who were farther along (and had written some papers of their own) were particularly good at this and thus were tasked more frequently in writing the details of a proof.

In reality, we couldn’t always stop ourselves from thinking about the problem between sessions. For one thing: I needed “quiet time” to program and create algorithms for computing these anti-van der Waerden numbers. Others would come to the next meeting with a proof idea that they could almost get to work. Sometimes it was also a good way to procrastinate from other tasks, such as writing grant proposals. (I am certainly guilty of this: I wrote one of my proofs while I was stuck on a different problem for two days with no progress and instead decided to have a successful research experience by thinking about arithmetic progressions.)

One thing that was particularly effective was that there were several faculty present that had very different perspectives on the problem and on proof strategies. Michael came up with several helpful ways to prove upper bounds by induction. Ryan presented a strong connection between anti-van der Waerden numbers and Szemerédi numbers. Leslie had interesting number-theoretic contributions. Steve could take a nap in the back, wake up when we were stuck on something, and then fix the proof with a few words.

The Writing

In the beginning, graduate students would log what we discussed that week. This took the form of a common TeX file that had a section for each meeting, and each section was about a page long. This sometimes would have repetitions or revisions from previous weeks, but the file grew and grew with no sense of organization. The point was to write everything down and not really to organize right away. In November, we had a good idea of what the research directions were, and perhaps what could be achieved in the coming months. It was time to start writing a paper.

Graduate students took the charge of writing the first drafts. Leslie became chair of a “writing committee” that had a separate meeting time from the seminar (and mostly was handled via email) where the students and Leslie got together and discussed organization and split the portions into writing assignments. The next week, written portions would be traded for revision. Every line was scrutinized. This was happening in parallel with the working seminar, so new results and ideas would be added into the draft as they were discussed.

The revision process brought a few things to light. Some students had never written a proof for a research paper, so their proofs read like homework solutions. Others had typical grammatical quirks and phrasing that simply needed to be honed. Multiple students told me later that this was a “wake-up call” and they learned a lot from others critique of their writing. It was very collegial: no blaming, no shaming. Just honest, constructive criticism.

The Revising

Once we felt that all research goals were attained or out of reach, we turned attention to revising the paper. Now, the writing committee expanded to include the entire group and take over the normal seminar time. The entire group was tasked with reading a certain section and taking notes before the next meeting. There was a group Dropbox folder, but only certain members had write privileges. Everyone else had read-only access to get the most-recent draft.

During the meeting, Leslie would have the draft up on the projector screen and we would go through things line-by-line. Typical edits would be word-choice changes, or reworking the structure of a sentence. Sometimes flaws in proofs were found and these would be tasked to fix offline. On a few instances, the revision process actually created problems, but with so many eyes on the draft, these would be caught relatively quickly.

In the recent weeks, we started going through the entire paper in one sitting with very few comments. This worked out very well, leading to very polished language that seems to have one voice throughout.

A few parts of the paper were less collaborative: the abstract, introduction, and conclusions. After the rest of the paper was written, organized, and solidified, a few faculty took turns at writing and editing these sections. It can be very hard to create a narrative for a collection of results that have origins from so many different people. It took careful effort from our more experienced faculty to do these tasks, and I think that is appropriate.

The Role of Computation

This blog is about computational methods, so I want to briefly comment on the role the computations had in this effort. It became very clear from the early discussions that we could not do much right away without some more information. As part of the creative component, a brute force algorithm was used to determine the anti-van der Waerden numbers for n < 10. I normally complain about people using "brute force" instead of "exhaustive" or "complete", but really the algorithm was "Write down all colorings. Check if any satisfy the properties." This clearly would not suffice. Because of the collaborative goals, I spent as little time as possible crafting a backtrack search algorithm that had very simple, but non-trivial, pruning mechanisms. This gave us significant insight to what was going on.

The most important use of computational data is to not try proving things that are false. It can sometimes also lead you to a correct answer, but it is most frequently used to not waste time trying to prove a false statement. This was a big reason why I did not hesitate to write code for these algorithms as soon as possible.

As we continued with the seminar, certain questions, such as “What form do these extremal colorings have?” became interesting and led to recursive constructions and sharpness conjectures. Sometimes the questions were not answered by the data because my algorithm would print out one good coloring and then quit. Questions such as “do all extremal colorings satisfy this property?” required a small modification to the code and a recomputation. Sometimes I could do this on my laptop during seminar, and other times I had to go back to my office and respond the following week.

One particular area where computations were important was in the numbers \mathrm{aw}(\mathbb{Z}_n, k), where we has less intuition. The fact that \mathrm{aw}(\mathbb{Z}_n,3) was not even close to monotonic led us to think about different approaches. One of our main theorems is that we can tell you the exact value of \mathrm{aw}(\mathbb{Z}_n,3), provided that all prime divisors of n are below 100. This depends significantly on the computations for these values and properties of the extremal colorings for those values. We formed conjectures that would make this theorem apply to all values of n and not depend on computation.

This leads me to what I think is the most noble goal of computational methods, which is to lead researchers to the truth, even if the truth requires standard mathematical arguments to prove it. It is easier to prove a theorem once you know it is (probably) true. Simpler proofs of theorems frequently come after the long, complicated proofs are first presented. It is the same with computation: It provides evidence that can motivate or reinforce conjectures.

A Personal Opinion

What Worked: Collaboration on steroids! Discussions were varied, everyone had meaningful contributions. The graduate students doing the main writing was an excellent experience for them and let the faculty keep participating without it killing their week.

What Did Not Work: Big(!) group. It would be better to split into smaller groups, no more than 4 grad students and 2 faculty per group. This would increase the workload for everyone, and would likely lead to weaker papers. However, it would be a more meaningful experience for each graduate student. Overall, three good papers might be better than one great paper. At least, better for the purposes of this seminar. Also, a 12-author paper will look confusing on anyone’s C.V. We want this to boost the students’ vitas, not add a confusing bullet point.

Ideas for Future: Next year will be a strange year. Most of the discrete mathematics faculty will be at the IMA Thematic Year on Discrete Structures for at least a semester, if not a year. I will be the only discret faculty member sticking around for the fall. I still want to do the working seminar, but I want to do it differently. We can start as a big group of all participants, and I present three or four problems that I find interesting and approachable. After the problems are presented, I can take problem rankings from the students. Then, I assign smaller groups of no more than four students. Instead of one big group meeting every week, the groups rotate for which is in the seminar room with me, and the others meet separately. This way, each meeting will begin with what the graduate students have done on their own, and I can contribute recommendations and ideas. The hope is that the students will take more ownership of the early research process, not just the writing. If this works, then I’ll write about it on the blog again next year.

A Side Node

All coauthors now have an Erdős number of at most 3, and those whose Erdős number is 3 now has at least five internally-disjoint paths of length 3 from them to Erdős: Butler-Graham-Erdős, Hogben-Godsil-Erdős, Martin-Szemerédi-Erdős, Stolee-West-Erdős, and Young-Pach-Erdős. When I brought this up with my coauthors, they were quick to point out that those with Erdős number 2 have several paths of distance two (but alas, I have just one). One even pointed out that West actually has an Erdős number of i due to the pen-name G. W. Peck, so that must make my Erdős number 1+i and ||1+i|| = \sqrt{2} < 2. So there.