On K.F.Roth's "On Certain Sets of Integers";
David John Wilson

Master's Essay


For my Masters of Science Essay I have written an expository article on K.F.Roth's seminal paper "On Certain Sets of Integers". In this paper Roth proved his eponymous theorem:

Roth's Theorem:
For every density d in the interval (0,1), there exists an integer N(d) such that every subset A of {1,..,N} with density at least dN must contain a three term arithmetic progression.

In fact, in his paper Roth proved a stronger statement, giving a bound on the density of a subset of {1,..,N} avoiding all three term arithmetic progressions. It is this result that we will investigate and clarify the proof.

I was supervised by Dr. Doron Zeilberger for the entirety of the project.

Article and Report:

My work is currently in three forms. First there is an Article which works through Roth's paper and clarifies every single step. Although Roth's original paper was a mere six pages long, this article is around forty. I have assumed minimal knowledge of asymptotic notation and basic calculus; hopefully the paper should be understandable to an advanced Undergraduate student.

The second version of my project is a longer Report. This has the same expository treatment of Roth's paper as the above article, but then continues by investigating other proofs and generalisations of Roth's Theorem. This additional material is covered with more brevity and requires some knowledge of basic arithemetic combinatorics techniques. This Report consitutes my Masters Essay.

Finally I am in the process of creating a Roth's Theorem Wiki. (There is also an "interactive paper" but I have now switched to the Wiki). This contains a facsimilie of Roth's paper. However, whenever an unexplained statement appears the user can click on the statement to be taken to a proof of the statement (and similarly click to return to the proof). Although the paper is up in its entirety, the explanations are still being updated and so this wiki is, as yet, unfinished.


As well as the above article and report I also created a Maple Package, roth, with programs related to the paper. To run this file, simply save a copy of the file and type the following

run (`directory/roth.txt`):

into Maple (where directory is the directory you saved the file into). You can also view Sample Output from some of the programs in this file or a Maple Document.

If you don't want to trawl through the entire Maple Package I have also created a Maplet which provides some of the key features of the package (calculating A(x), a(x) and generating A-sets) in a more user-friendly environment. To run the maplet you must have Maple installed on your computer. Then save the linked page (with file suffix .maplet) and either double-click on the save file (which should run using Maple's maplet launcher), or open the file in Maple and run the worksheet like a regular Maple worksheet.


I was honoured to be asked by Dr. Zeilberger to talk at the Rutgers Experimental Mathematics seminar on April 21st 2011. The talk was filmed and posted on YouTube, in two parts: Part One and Part Two. I have also posted my presentation slides from the talk.

Return home

Maintained by David Wilson and last modified 05/01/12