2.1 A basic introduction to Szemerédi’s theorem

We consider an important and deepFootnote ³⁸ result of additive number theory: Szemerédi’s theorem (on arithmetic progressions). I begin with some basic definitions.

An arithmetic progression of interest to computational mathematicians is one of the longest known arithmetic progressions of primes:Footnote ³⁹

Note that oftentimes we deal with arbitrarily long arithmetic progressions, where this is commonly taken to mean finite arithmetic progressions of arbitrary length, i.e., without the specification of some k.

We can now state a finitaryFootnote ⁴⁰ version of our theorem:

This is equivalent, via a routine compactness argument, to an infinitary version, proved in 1975 by E. Szemerédi, thereby providing an answer to a long-standing conjecture of Turán and Erdős:Footnote ⁴¹

Theorem 2.5 (Szemerédi, infinitary).

Let A be a subset of the integers ${\mathbb {Z}}$ with positive upper density, i.e.,

(2.1) $$ \begin{align} \delta(A):= \limsup_{N \rightarrow \infty} \frac{|A \cap [-N, N]|}{2N+1}>0. \end{align} $$

Then A contains arbitrarily long arithmetic progressions.

This theorem will be the main focus of our paper.Footnote ⁴² It tells us that, for some very large (positive density) set $A \subset {\mathbb {Z}}$ , one will always find arbitrarily long arithmetic progressions in A. This is quite remarkable for a few reasons.Footnote ⁴³ First, no assumptions are laid down on the set under consideration aside from its size. Thus, even if two sets A and B look entirely different (but are both sufficiently large), each will have arbitrarily long arithmetic progressions. For instance, A could be randomly generated and B could itself be an arithmetic progression (an infinitely long one), and yet both will have long arithmetic progressions contained in them. In fact, it is quite easy to extract arithmetic progressions from either of these extreme cases, i.e., very random and very structured cases, though for entirely different reasons. Indeed, every (known) proof of Szemerédi’s theorem relies on what Terry Tao has called a fundamental dichotomy between structure and randomness.Footnote ⁴⁴ Very roughly speaking, this dichotomy can be exploited to exhaustively characterize any sufficiently large set, and thus prove that any such set has arithmetic progressions. The dichotomy will be an important aspect of our philosophical discussion as it has implications for the relationship between content, impurity, and explanation.

One might be unimpressed by the presence of arithmetic progressions in very large sets: of course, if you choose something large enough, you will find what you are after. However, one finds that other related patterns are quite easily avoided in large sets. The canonical example is:

And yet, Szemerédi’s theorem says that one cannot avoid arithmetic progressions in large subsets of integers. Thus, the lack of a priori constraints on the sets considered and the ease of eliminating other patterns from large sets provide two reasons for thinking that Szemerédi’s theorem is particularly “deep.” Furthermore, it has an impressive relationship to further developments in mathematics; I will say more about this at the end of the section.

2.2 A radically impure proof of Szemerédi’s theorem

Szemerédi’s original proof was entirely combinatorialFootnote ⁴⁵ and thus paradigmatically pure (see [Reference Szemerédi59]). It is, however, incredibly intricate and has been judged, even by the best professional mathematicians working in this field, as “remarkably subtle” (see [Reference Tao, Granville, Nathanson and Solymosi61]). Indeed, it is quite rare, except in the most difficult and involved of proofs, to include a schematic diagram outlining the proof steps, but this is just what Szemerédi does (see Section 6).

In 1977, Hillel Furstenberg gave an incredibly different and highly impure proof of Szemerédi’s theorem.Footnote ⁴⁶ The first step was to show that Szemerédi’s theorem (Theorem 2.5) is in fact equivalent to a theorem about the behavior of dynamical systems.Footnote ⁴⁷ This dynamical analogue could then be proved using techniques from ergodic theory. (All of this will be made precise below.) The important thing to note at this point is that the impurity is both elemental and topical: elemental because Furstenberg’s proof uses highly infinitary techniques to prove a result with explicit combinatorial, finitary content and topical because dynamical systems (more precisely, measure-preserving systems) are intuitively very different from mere sets of positive integers. I believe both aspects of the impurity contribute to the explanatory power of Furstenberg’s proof.

Before turning to our criteria of selection, let me make the finitary–infinitary distinction more precise, as this will feature throughout the discussion. As mentioned above, finitary mathematics can be understood to mean the “theory of finite sets.” Indeed, we have the following result:Footnote ⁴⁸

On the other hand, one can understand infinitary mathematics to mean the “theory of infinite sets.” This distinction can take on new contours in different contexts, e.g., finitary mathematics in Hilbert’s Program is weaker than what I am calling finitary here. When appearing in the mathematical wild, rather than in more precise logical contexts, finitary mathematics employs notions like: the cardinality of finite sets (of course), upper and lower bounds of such sets, and measures of bounded sets. Infinitary mathematics then employs notions like: sequences, measurable sets and functions, general measurability and integrability, convergence, and compactness. This battery of concepts should suffice to make clear when and why a result is called either finitary or infinitary below.Footnote ⁵⁰ To slightly belabor the point: Szemerédi’s theorem (given in Theorem 2.4) is avowedly finitary, Furstenberg’s proof of it is avowedly infinitary, and thus Furstenberg’s proof is elementally impure.

2.3 Criteria of selection

Let me here provide some motivation as to why I believe Szemerédi’s theorem is worthy of philosophical attention and why an analysis of it might yield impressive philosophical dividends.

First, Szemerédi’s theorem does not require infinitary and impure techniques to prove it.Footnote ⁵¹ This sets it apart from now canonical number-theoretic examples that utilize resources far beyond what one would think necessary to prove them, e.g., Fermat’s Last Theorem, the Paris–Harrington theorem, and Friedman’s finitary version of Kruskal’s theorem. In attempting to elucidate the explanatory dividends of infinitary and impure methods in mathematics, it is crucial that I examine results that admit of multiple varieties of proof. This allows for a fruitful comparison of techniques, a comparison that (I hope) inclines one think that infinitary and impure methods, though not “required” per se, are very much an essential part of mathematical practice and explanation.Footnote ⁵²

Second, the ergodic proof of Szemerédi’s theorem has been subjected to metamathematical analysis by Jeremy Avigad and Henry Towsner (see [Reference Avigad7, Reference Avigad and Towsner8, Reference Towsner63]). The metamathematical data available will allow us to make some of our observations more precise, e.g., the stage of the ergodic proof of Szemerédi’s theorem where crucial explanatory work is done may involve axiomatically strong mathematics. Nonetheless, I do not believe that it is primarily the axiomatic strength of the ergodic results that drives the explanatory power of Furstenberg’s proof. The axiomatic strength is, rather, a side effect of the move to “explanatorily appropriate” resources.Footnote ⁵³

Finally, Szemerédi’s theorem is an absolutely central result in number theory, and its proofs, especially Furstenberg’s, have generated impressive developments in diverse fields of mathematics.Footnote ⁵⁴ I take these facts to be quite important because, to my mind, many philosophical analyses of mathematics are unsatisfying or fail outright because they extract conclusions from results that have no obvious mathematical significance.Footnote ⁵⁵ This should then lead one to doubt the significance of the philosophical conclusions drawn. That is, if one is attempting to provide a philosophy of mathematics, the examples analyzed should be of acknowledged mathematical import.Footnote ⁵⁶ Szemerédi’s theorem, on the other hand, has been a locus of work in number theory and combinatorics for almost half a century, and, as we shall see, gave rise to entirely new sub-fields of mathematics. Finally, the conceptual approaches used to prove this theorem have shown astonishing applicability in the solution of other, long-standing questions, e.g., whether the prime numbers contain arbitrarily long arithmetic progressions.Footnote ⁵⁷ Indeed, the full significance of these results is not yet understood.

3.1 Furstenberg’s ergodic proof of Szemerédi’s theorem

Here I provide the conceptual contours of Furstenberg’s ergodic proof of Szemerédi’s theorem.Footnote ⁵⁸ The summary here should contain all the mathematical material needed to engage with the discussion below.

First, a word on “ergodic theory.” Broadly speaking, ergodic theory is the study of the long-term behavior of dynamical systems:

Intuitively, we study the time-evolution of X under transformation T.

For example, we might consider the finite system $(X, T)$ where X is a finite set and T a permutation of the elements of X. Alternatively, we might understand a dynamical system as the action of a group G on a set X.Footnote ⁵⁹ Thus far, at this level of abstraction, little interesting can be said. However, applying a little more structure to dynamical systems will yield surprising results. Classical ergodic theory, which is what concerns us here, studies measure-preserving systems:

These definitions, along with the information above on Szemerédi’s theorem, should suffice for an outline of the ergodic proof.

Let us call the first stage in the ergodic proof of Szemerédi’s theorem the Correspondence Stage. Furstenberg realized that Szemerédi’s theorem would follow from a generalization of a famous recurrence result called Poincaré Recurrence in ergodic theory.Footnote ⁶⁰ (In essence, a recurrence result describes how points in a dynamical system return close to themselves after sufficiently many iterations of map T.Footnote ⁶¹ ) This generalization is now called Furstenberg Multiple Recurrence in his honor. Indeed, one can also show that Szemerédi’s theorem implies Furstenberg Multiple Recurrence, thereby establishing a correspondence between the combinatorial and ergodic settings. Let me now state these results more precisely.

Theorem 3.3 Let $(X, \mathscr{B}, \mu, T)$ be a measure-preserving system and let $E \in \mathscr{B}\ {\it with}\ \mu(E) >0$ . Then for any $k \geq 1$ ,

(3.1) $$ \begin{align} \liminf_{N \rightarrow \infty} \frac{1}{N} \sum^{N-1}_{n=0} \mu(E \cap T^{n}E \cap \cdots \cap T^{(k-1)n}E)>0. \end{align} $$

Then we can show

I will not prove these results here.Footnote ⁶² However, let me attempt to give my reader a sense as to how the various ideas fit together.

We begin with a problem about arithmetic progressions in the integers and wish to convert it to an ergodic setting. The basic idea here is that we can identify subsets $A \subset {\mathbb {Z}}$ with subsets of the ambient set or space X in the measure-preserving system. Similarly, we can identify functions on the integers with functions on the dynamical system. After this is done, the task of finding an arithmetic progression in some $A \subset {\mathbb {Z}}$ is in fact equivalent to finding an arithmetic progression in the subset of X identified with A. Let me try to make this a bit more precise. We can show, for our measure-preserving system $(X, \mathscr {B}, \mu , T)$ , that there is a probability measure $\mu $ on X such that $\mu (E)=\mu (T^{n}E)$ for all $n \in {\mathbb {Z}}$ and measurable sets $E \subset X$ with E of positive measure. Then, the existence of some k-length arithmetic progression in $A \subset {\mathbb {Z}}$ (the assertion of Szemerédi’s theorem) is equivalent to the existence of some $x \in X$ such that a recurrence pattern $x, T^{n}x, \ldots , T^{(k-1)n}x$ is in E.

In particular, we show that

(3.2) $$ \begin{align} \liminf_{N \rightarrow \infty} \frac{1}{N} \sum^{N-1}_{n=0} \mu \left(E \cap T^{n}E \cap \cdots \cap T^{(k-1)n}E \right)>0 \end{align} $$

for $\mu (E)> 0$ . This implies the recurrence claim above, i.e., $x, T^{n}x, \ldots , T^{(k-1)n}x$ is in E, since it shows that the intersection of sets $E \cap T^{n}E \cap \cdots T^{(k-1)n}E$ is non-empty for infinitely many n. This concludes the Correspondence Stage of the proof.

The second stage of the proof involves showing 3.2 holds, i.e., proving Furstenberg Multiple Recurrence. I believe this is where the ergodic proof yields great explanatory dividends. In short, any proof of 3.2 requires decomposing the system under consideration into a structured component and a random component, which, by the Correspondence Stage of the proof, is equivalent to decomposing any $A \subset {\mathbb {Z}}$ into a structured set and a random set. Tao presents the situation with usual adeptness as a “fundamental dichotomy between structure and randomness.” He continues,

I will have much more to say about structure theorems below. Returning to the proof sketch, it turns out that in the ergodic setting the requisite structure theorem and the dichotomy between structure and randomness are particularly explicit. Let’s sketch how the structure theorem is applied in the ergodic setting.

The dichotomy presents itself as that between the periodicity of some $E \subset X$ under transformation T (structured case) or the mixing of E under transformation T (random case). If E is periodic, then this simply means $T^{l}E=E$ for some $l>0$ , i.e., we have a very obvious recurrence of E under T for some $l>0$ . Establishing 3.2 is then trivial as the summand will be $\mu (E)$ whenever n is a multiple of l. Even in the less well-behaved case of near-periodicity, we can show 3.2 in a very similar fashion. When all E for a space X are near-periodic, then we say the measure-preserving system is compact.

On the other hand, we get the random scenario when E has a “mixing” property. Intuitively, this can be thought of as follows: if E is some event in the probability space X, then T “mixes” the space randomly such that all events $\left \{ E, T^{1}E, T^{2}E, \ldots \right \}$ are independent of one another. This yields 3.2 trivially as then each recurrence pattern is just $\mu (E)^{k}$ . As in the structured case, even when we relax the mixing to the case of “weak-mixing,” 3.2 can be proven. When all E in X have this weak-mixing property, we say that the system is a weak-mixing system. In either the compact or weak-mixing cases, we can prove our desired result quite easily.

However, not all systems are either compact or weak-mixing.Footnote ⁶⁵ Nonetheless, provided that X is not completely weak-mixing (i.e., totally random), we can always find some structured component Y of X, which will itself give rise to a compact system. We can then analyze the map from $X \rightarrow Y$ , called an extension map, which itself has structured or random behavior. If $X \rightarrow Y$ is a weak-mixing or compact extension,Footnote ⁶⁶ then, even if X is neither of these, we can reduce the task of showing 3.2 holds in X to showing this holds in Y, and, since Y is compact, showing 3.2 holds in Y can be done easily. However, like systems, not all extensions are either weak-mixing or compact. If $X \rightarrow Y$ is some such intermediate case, then we can find some intermediate extension $X \rightarrow Y_{1} \rightarrow Y$ such that $Y_{1} \rightarrow Y$ is a compact extension. We can then pass to Y and show 3.2 holds. Thus, we must show that if 3.2 holds in $Y_{1}$ it holds in X. This process can be continued (transfinitely) by constructing a tower $X \rightarrow Y_{\alpha } \rightarrow \cdots \rightarrow Y_{1} \rightarrow Y$ where each step $Y_{n+1} \rightarrow Y_{n}$ is a compact extension and $X \rightarrow Y_{\alpha }$ is weak-mixing. This is the essence of the Furstenberg Structure Theorem:

This is the ergodic analogue of the number-theoretic result discussed above in the quote by Tao. In essence, it says that any measure-preserving system, irrespective of its given behavior, can be decomposed in a very precise way, viz., in terms of structured (compact) and random (weak mixing) components. Since it is easy to show that 3.2 holds in each of these cases, we can show that it holds for any measure-preserving system, and thus, by Furstenberg Correspondence, that Szemerédi’s theorem holds.Footnote ⁶⁸

Thus, the ergodic approach to Szemerédi’s theorem yields a highly perspicuous proof structure, which, in every case considered, will us tell why a system (and thus subset of integers) has the recurrence pattern (arithmetic progression) it does:Footnote ⁶⁹

1. 1. Correspondence Stage

   1. (a) Convert Szemerédi’s theorem into a theorem about recurrence in a measure-preserving system, i.e., Furstenberg Multiple Recurrence (Theorem 3.3).

   2. (b) Prove that these theorems are equivalent (or simply that Furstenberg Multiple Recurrence implies Szemerédi’s theorem).

2. 2. Structure Theorem Stage

   1. (a) Prove Furstenberg Multiple Recurrence.

   2. (b) This must be done for any measure-preserving system for arbitrary k.

   3. (c) Classify each system as either structured (compact), random (weak-mixing), or neither. If the system is structured or random, we are done.

   4. (d) If the system is neither, use extensions to construct a (transfinite) tower via the Furstenberg Structure Theorem (Theorem 3.5), and eventually reduce to either the compact or weak mixing case. Q.E.D.

3.2 The Structure Theorem as “Reason Why”

I claim that the Furstenberg Structure Theorem provides the reason why Szemerédi’s theorem holds. But what, precisely, do I mean by this? Recall that, on the number-theoretic version of Szemerédi’s theorem, we consider arbitrary subsets $A \subset {\mathbb {Z}}$ and show that they contain arbitrarily long arithmetic progressions. Unsurprisingly, given the lack of explicit constraints on A, one can find such arithmetic progressions in various subsets for very different reasons.Footnote ⁷⁰ For example, consider some random subset A of ${\mathbb {Z}}$ , where this means each integer n in A has an independent probability of $\delta $ with $0<\delta <1$ . It is now quite simple to show that A in fact has infinitely many arithmetic progressions of length k because any such progression will have a probability of $\delta ^{k}$ of lying in A.Footnote ⁷¹ On the other hand, were we to consider some “structured” set, we would get the same answer for an entirely different reason. For example, consider the Bohr set $\left \{ n \in {\mathbb {Z}} : ||n \alpha ||_{{\mathbb R}/{\mathbb {Z}}} \leq \delta \right \}$ with $\delta $ as above, $\alpha \in {\mathbb R}$ , and $|| \cdot ||$ yielding the distance between the argument and the nearest integer. For any $\alpha $ , each $\alpha n$ can be made arbitrarily close to n, and so each n is correlated with periods of $\alpha $ . The sequence of such periods will then just be the arithmetic progression we seek.

As I showed above, the ergodic situation precisely mirrors the number-theoretic situation. Namely, we obtain Furstenberg Multiple Recurrence (Equation 3.2) in an arbitrary measure preserving system because systems exhibit either sufficient randomness (weak-mixing) or sufficient structure (compactness). In the weak-mixing case, on average, the events $T^{n}E, T^{2n}E, \ldots , T^{(k-1)n}E$ are uncorrelated such that the measure of the set in question in 3.2 is approximately $\mu (E)^{k}$ fairly often (thus satisfying 3.2). As in the random number-theoretic case, since the systems under consideration are sufficiently mixing (random), sooner or later we will find the desired recurrence property “by dumb luck” (see [Reference Avigad7], Section 4, for a nice discussion of the structure theorem). We will also find the recurrence property in sufficiently structured systems (compact) because these systems will have events $T^{n}E$ recur at regular intervals, i.e., the intersection of E and $T^{n}E$ over k-many iterations of $T^{n}$ will be non-empty. Again, this is analogous to the number-theoretic case described above: sufficient structure in the original set (or system) will guarantee the existence of the desired arithmetic progression (or recurrence property).

The moral here is that we can find multiple recurrence patterns in random systems, structured systems, and various systems in between; however, the reason we can do this always turns upon the classification of the system itself. This would seem to dash any hopes of a general reason for a result like Furstenberg Multiple Recurrence (or Szemerédi’s theorem); namely, the proof of the theorem would have to amount to checking the existence of recurrence patterns for each X, given some classification of X. Such a task seems hopeless, and I daresay would not produce an explanation of why the theorem is true. One could not then even state the theorem as such; rather, we would have some conjunction of independent theorems. In order to avoid this situation, one would hope for a result that would allow us to group prima facie very different systems into one class that shares some feature F, which in turn allows us to understand why recurrence patterns occur in each X. And this is just what the Furstenberg Structure Theorem Footnote ⁷² provides for the ergodic equivalent of Szemerédi’s theorem. Thus, the reason why we can always find the desired recurrence pattern for any system X is that every X can be decomposed into components that we know how to handle, thereby obviating the need to classify each X and check for recurrence patterns. Now, one might reasonably ask: why do we need the ergodic setting to do this? If all proofs of Szemerédi’s theorem use a Structure Theorem, why can’t we run the aforementioned process for arbitrary subsets $A \subset {\mathbb {Z}}$ and find arbitrarily long arithmetic progressions? These questions are important and will be answered more fully in another paper where I explicitly compare both the ergodic and combinatorial proofs. Suffice it to say, for now, that the overall proof structure in the combinatorial case does not resemble that of the ergodic proof given above.Footnote ⁷³ One cannot easily “read off” the existence of arithmetic progressions from the combinatorial structure theorem as one can do with the ergodic proof. Put differently, the structural result that provides the reason why the theorem holds is rendered evident in the ergodic case, while it is not at all evident in the combinatorial case.

One might, at this point, also complain that I have ignored essential details about the systems under consideration. One might think that the real reason why some X has the recurrence pattern it does is because of the kind of system X is, e.g., highly structured, highly random, etc., and that the kind of high-level structural result I consider abstracts from these details. The way to actually explain why a particular system has the patterns it does requires a careful analysis of that system in particular. There may be something to this complaint.Footnote ⁷⁴ However, though this kind of criticism may be fairly levelled at particular high-level structural results, it does not really hold here.Footnote ⁷⁵ As we have seen, the Furstenberg Structure Theorem gives an exhaustive means of characterizing each system (and set given our Correspondence Principle) without, as it were, digging into the nitty gritty details of the particular system (or set). When we apply the structure theorem to a particular system, even though the system might lie anywhere along the spectrum of structure and randomness, we will be able to classify the system precisely.

This classification does rely on our understanding the two ends of the spectrum, i.e., why a random system and why a highly structured system will have the recurrence pattern.Footnote ⁷⁶ However, this is the only requisite contribution of “lower-level” or “system-specific” results, and this contribution is relatively simplistic, i.e., the structured and random extremes are quite easy to understand.Footnote ⁷⁷ Once we know how to deal with the extremes and have the Structure Theorem in hand, the actual classifications of the various systems (or sets) do not really matter and certainly do not contribute to the explanation of why Furstenberg Multiple Recurrence (and thus Szemerédi’s theorem) holds. We bypass examining each particular system because each system will have the pattern it does in virtue of the same reasons that compact and weak mixing systems have this pattern; however, the only reason we can assert this is because of the Furstenberg Structure Theorem. Thus, I believe the Furstenberg Structure Theorem makes very explicit the reason why Szemerédi’s theorem is true, and thus the ergodic proof should be considered, in the basic sense of answering the why-question latent in the theorem, explanatory. Let me now turn to an explicit discussion of how this explanatory work can be done by such intuitively foreign concepts.

4.1 Motivating the investigation of content

It is quite striking that Szemerédi’s theorem, a finitary and combinatorial result, can be proved using infinitary and ergodic techniques. It is even more striking that these techniques yield an explanatory proof (or so I claim). We may then say that Szemerédi’s theorem possesses an explanatory proof that is both elementally and topically impure.Footnote ⁷⁸ But how is this possible? How do such intuitively different conceptual resources “get a grip on” the theorem to be proved? In this section, I will focus upon answering this question and thus explicate the relationship between explanation and topical impurity.Footnote ⁷⁹

Recall that a proof is topically pure if it draws only on what belongs to the content of the theorem or what the theorem is about. It would seem that the ergodic proof of Szemerédi’s theorem is topically impure since ergodic theory is concerned with very different entities than those present in the theorem: at the most basic level of analysis, measure-preserving systems are quite different from sets of natural numbers or integers.Footnote ⁸⁰ And yet, the structural fact that serves as the “reason why” Szemerédi’s theorem holds is present in both the ergodic and combinatorial settings (the Furstenberg Structure Theorem and the Szemerédi Regularity Lemma, respectively). It is difficult to square all this information, and I believe we are faced with a “content-purity” dilemma.

On the one hand, are we to say that, in some sense, Szemerédi’s theorem has “implicit” or “hidden” ergodic content in virtue of the shared structural fact? This kind of suggestion has an impressive pedigree. Bourbaki claims something in this vicinity,Footnote ⁸¹ though I take the ultimate point to be more subtle:

If, however, we follow the Bourbakiste suggestion (or some coarse version of it), then we should say that the ergodic proof of Szemerédi’s theorem is topically pure. I take this to be a strange and unwelcome consequence. Furthermore, the notion of “implicit” or “hidden” content, as it stands, is too vague to be of service. I consider some proposals below that attempt to provide a more useful notion of “hidden” content.

On the other hand, we might retain the idea that the entities of ergodic theory are intuitively quite different from those of combinatorics (and Szemerédi’s theorem), and thus the ergodic proof is topically impure as I have claimed. Obviously, I subscribe to this view, as I wish to argue for the association between impurity and explanation. However, merely relying upon the “first glance” or “intuitive” characterization of the content of a theorem leaves the explanatory potential of the ergodic setting itself unexplained.Footnote ⁸² Again, we should ask how the intuitively different ergodic resources “get a grip on” the explicitly combinatorial Szemerédi’s theorem and how these new resources are then exploited to generate an explanatory proof. I believe that it is reasonable to answer the first question in terms of the content of Szemerédi’s theorem, especially since topical purity/impurity is also analyzed in this way. Given that neither the “implicit” nor the “intuitive” analysis of mathematical contentFootnote ⁸³ sufficiently answers this question, I argue for a new notion called structural content, which is able to save intuitive purity/impurity ascriptions and simultaneously explicate the intervention of surprising and explanatorily rich conceptual resources. Let us begin, then, by characterizing the various types of mathematical content on offer in greater detail.

4.2 Intuitive and formal mathematical content

A natural starting point is the analysis given in [Reference Arana and Mancosu5]. Here Arana and Mancosu draw an important distinction between “informal” or “intuitive” content and “formal” or “axiomatic” content. Loosely, the former notion amounts to what someone with a casual acquaintance with mathematics would understand by some statement. This might profitably be understood as what one “grasps” upon a first reading.Footnote ⁸⁴ For instance, Szemerédi’s theorem is about a particular kind of regularity in sufficiently dense subsets of the integers (infinitary formulation) or in sufficiently large subsets of the natural numbers (finitary formulation). On the other hand, the formal notion of content amounts to the “inferential role of [a] statement within an axiomatic system” ([Reference Arana and Mancosu5], 327).

This distinction is drawn in the context of their discussion of Desargues’ theorem, the exact statement of which does not matter for our purposes. One of the primary questions under investigation is whether the spatial proof of this (ostensibly) planar result is to be judged as impure (following Hilbert) or pure (following Michael Hallett) in light of metamathematical data from Hilbert’s Grundlagen der Geometrie. In particular, Arana and Mancosu are concerned with articulating a notion of mathematical content that “…can support an adequate account of talk of purity in mathematical practice” ([Reference Arana and Mancosu5], 324). They conclude that only intuitive content is able do this work. I take no issue with this conclusion; indeed, my assertion that the ergodic proof of Szemerédi’s theorem is (topically) impure relies upon the availability and cogency of intuitive content. However, it is worth considering whether we might utilize other, more nuanced, articulations of mathematical content in cases that warrant them. The theorem considered here is one such case: intuitive content cannot help us make sense of why it is that the ergodic setting is adept at modeling and explaining Szemerédi’s theorem. I outline a third kind of content below that I believe is up to the task; however, before turning to this positive proposal, let me reflect on the less familiar notion of formal content to see whether some version of it might provide a serviceable sort of “hidden” or “implicit” content.

4.2.2 Can we utilize formal content?

According to Arana and Mancosu, the case of Desargues’ theorem is analogous to that of the Gödel sentence because it can serve as a spatial incidence axiom in Hilbert’s axiomatic system of the Grundlagen, i.e., the planar Desargues’ theorem can play the same inferential role as an explicitly spatial mathematical proposition.Footnote ⁹⁰ They summarize the situation in the following way:

[I]n both cases, we have sentences whose ordinary understanding indicates that it has content of one type (e.g., arithmetical or planar), but that an analysis of the sentences’ inferential roles reveals that these sentences have tacit content of another type (e.g., infinitary or spatial, respectively) ([Reference Arana and Mancosu5], p. 333).

Nonetheless, even though they believe that the Isaacson–Hallett notion of formal content makes sense for Desargues’ theorem, they ultimately reject its use. And this is because appealing to formal content generates verdicts contrary to mathematical practice; most pressingly, purity ascriptions become trivial. Related considerations and worries will appear below. However, at present we only consider whether it is intelligible to say that Szemerédi’s theorem has formal content and, if so, whether formal content can help to explicate the relationship between impurity and explanation.

There are, certainly, some similarities between our case study and the phenomenon of hidden content at work in Gödel sentences and Desargues’ theorem. Our ordinary or intuitive understanding of Szemerédi’s theorem indicates that it has finitary, combinatorial content; however, it is equivalent to an ostensibly infinitary result (Furstenberg Multiple Recurrence), and its ergodic proof makes essential use of a transfinite constructionFootnote ⁹¹ (the tower of extensions in the Furstenberg Structure Theorem). This initial assessment of the situation suggests that the notion of formal content may be of use in explicating this surprising confluence of mathematical resources. However, closer examination reveals that formal content is not really available to us. Consider the case of the Gödel sentence G. Let us write the formal content of G as:

(4.1) $$ \begin{align} \mathscr{F}_{G}:= \left\{\psi: \, \, \vdash_{\operatorname{\mathrm{\mathsf{PA}}}} G \leftrightarrow \psi \right\}. \end{align} $$

That is, the formal content of G is the class of statements such that each statement is provably equivalent to G in $\operatorname {\mathrm {\mathsf {PA}}}$ . Thus, as it should be, some $\psi $ expressing by coding $\text {Con}(\operatorname {\mathrm {\mathsf {PA}}})$ is included in the formal content of G. However, when we think of formal content in the above fashion, there is a rather restricted set of circumstances in which this will make sense, viz., when we have an independence result. In the case of G, while we can prove $G \leftrightarrow \psi $ in $\operatorname {\mathrm {\mathsf {PA}}}$ , we cannot prove the property that $\psi $ expresses, i.e., $\text {Con}(\operatorname {\mathrm {\mathsf {PA}}})$ , in $\operatorname {\mathrm {\mathsf {PA}}}$ by Gödel’s Second Incompleteness Theorem. Thus, we have the requisite independence. In the case of Szemerédi’s theorem ( $\mathsf {SZ}$ ), we could try to write its formal content as:

(4.2) $$ \begin{align} \mathscr{F}_{\mathsf{SZ}}:= \left\{\psi: \, \, \vdash_{\operatorname{\mathrm{\mathsf{ZFC}}}} \mathsf{SZ} \leftrightarrow \psi \right\}. \end{align} $$

Letting some $\psi $ be Furstenberg Multiple Recurrence, we would register the “hidden” infinitary ergodic content of Szemerédi’s theorem. However, Furstenberg Multiple Recurrence is not independent of $\operatorname {\mathrm {\mathsf {ZFC}}}$ , the system in which we prove the equivalence. This has the effect of saying that Szemerédi’s theorem and Furstenberg Multiple Recurrence have the same formal content; indeed, all theorems of $\operatorname {\mathrm {\mathsf {ZFC}}}$ would then have the same formal content, rendering this notion (as it stands) entirely trivial and, a fortiori, entirely unhelpful in illuminating the relationship between impurity and explanation.

Another way of seeing the unavailability of formal content in our case is via the absence of a coding phenomenon. According to Isaacson,“The relationship of coding constitutes a rigid link between the arithmetical and the higher-order truths, which pulls the ostensibly arithmetical truth up into the higher-order” ([Reference Isaacson and Hart34], 221). There is no such mechanism at work in the Furstenberg Correspondence Principle.Footnote ⁹² Rather, we have an identification of sets and functions in the combinatorial and ergodic contexts, along with a clever choice of “unconventional” dynamical system that effects this identification.Footnote ⁹³ This should be thought of as a “modeling” of the combinatorial phenomenon in the ergodic setting, rather than indicating the presence of coded or “hidden” formal content.Footnote ⁹⁴

Of course, these considerations need not rule out the possibility of using formal content to explicate Furstenberg Correspondence in the future. This would depend upon a reverse mathematical analysis of both Szemerédi’s theorem and Furstenberg Multiple Recurrence and the existence of an independence result.Footnote ⁹⁵ That is, we would need to show that some system $\mathsf {T}$ proves Szemerédi’s theorem and its equivalence with Furstenberg Multiple Recurrence but not Multiple Recurrence itself. It is very likely that Szemerédi’s theorem can be proved in $\operatorname {\mathrm {\mathsf {RCA_{0}}}}$ and perhaps even weaker systems, although this would require some rather tedious work to verify. Furthermore, the metamathematical analysis of the infinitary content of Furstenberg Correspondence in [Reference Avigad7], Section 5, indicates that it is reinterpretable in computational or combinatorial terms. Thus, given this metamathematical data, it would appear that the independence result required for formal content to make sense is unlikely to materialize.

Finally, it is worth considering whether a looser notion of hidden higher-order content might be of interest. This would then no longer involve Arana and Mancosu’s gloss of hidden higher-order content as formal content, and thus the need for an independence result would no longer be present. Isaacson himself suggests something along these lines when dealing with “in principle” provability. That is, there might be cases where a theorem is provable in $\operatorname {\mathrm {\mathsf {PA}}}$ , but this proof would be “infeasibly long” and thus “the higher-order perspective is essential for actual conviction as to the truth of an arithmetically expressed sentence” ([Reference Isaacson and Hart34], p. 221). I am rather sympathetic to the idea that various statements in some $\mathsf {L_{\mathsf {T}}}$ could be said to have higher-order content in light of the unsurveyability of their proofsFootnote ⁹⁶ in the system $\mathsf {T}$ .Footnote ⁹⁷ It is implausible that Szemerédi’s theorem has hidden higher-order content in this sense: its proof is very difficult but is by no means unsurveyable. However, something like, say, Fermat’s Last Theorem (FLT) seems a good candidate for an ascription of “loose” higher-order content. Few seem to doubt that it is “in principle” provable in some (higher-order) non-conservative extension of $\operatorname {\mathrm {\mathsf {PA}}}$ ; however, actually producing and understanding such a proof appears to be nearly impossible (see [Reference McLarty47]). It is then reasonable to ascribe some sort of hidden higher-order content to FLT but not to Szemerédi’s theorem.

4.3 A further refinement of mathematical content

Thus, though the notion of formal content and looser versions of “hidden” higher-order content may be useful in particular circumstances, they cannot help us to understand the case at hand. Should we then evaluate Szemerédi’s theorem in terms of intuitive content alone? Unfortunately, as I have indicated, this articulation of content fails to capture crucial data about the theorem, data that would be desirable to have for philosophical discussions relating content, purity, explanation, mathematical evidence, and likely other topics. In particular, we should like to say something about the relationship between the combinatorial and ergodic settings in light of both the equivalence between Szemerédi’s theorem and Furstenberg Multiple Recurrence and the epistemic dividends generated by the ergodic proof. I find it quite reasonable that this connection be captured in our understanding of the content of Szemerédi’s theorem. In short, then, intuitive content fails to capture mathematical information of interest, while formal content is unavailable to us and, even if it were, is neglectful of important epistemic distinctions.Footnote ⁹⁸ Is there then another, “intermediate” notion of content that might make sense of the ergodic proof of Szemerédi’s theorem? I believe that there is and attempt to use the somewhat sketchy suggestions of Bourbaki to develop this idea. Call this third sort of content structural content.

Bourbaki describes the “axiomatic method” as a “systematic study of the relations existing between different mathematical theories,” which takes as its central concept that of the mathematical structure ([Reference Bourbaki11], 222). Consider Bourbaki’s description of a mathematical structure:

I propose that the structural content of a theorem is the instantiation of a particular fundamental mathematical structure by the entities intuitively involved in the statement. Let me fix intuitions with a simple example: the realization that $({\mathbb R}, +)$ is a particular instance of a group structureFootnote ⁹⁹ contributes additional content to a theorem involving addition on the real numbers. This content cannot be what we are calling intuitive: it seems doubtful that a mathematical novice proving a theorem about $({\mathbb R}, +)$ that is not explicitly group-theoretic would grasp the group axioms. Nor would a theorem involving $({\mathbb R}, +)$ gain a contribution of strictly formal content from the realization that $({\mathbb R}, +)$ is the instantiation of a fundamental structure; the understanding that $({\mathbb R}, +)$ is a group does not involve seeing that it can serve as an axiom in a system but rather the understanding that $({\mathbb R}, +)$ satisfies particular axioms. Furthermore, this realization will induce a relational fact about the particular entity in question, $({\mathbb R}, +)$ , and other groups, i.e., the fact that they all instantiate the group structure. This fact contributes content that is of a much more global character than intuitive content, while not being merely inferential. We might then fruitfully compare various instances of group structures once we realize that they can all be identified as such.

Bourbaki is careful to note that this description of the mathematical universe via structures is “…schematic, and idealized as well as frozen” (ibid., p. 229). As such, it is open to revision, and, in particular “[the] definition of structures is not sufficiently general” (ibid., footnote on p. 226). I want to suggest that we can proceed by taking a mathematical structure to be a somewhat more flexible notion than a concept defined by explicit axioms. Of course, once we broaden the notion of mathematical structure to include more than explicit axiomatizations, some further attempt at characterization must be made especially if we wish to avoid pointless “gerrymandered” properties. A natural suggestion is that we appeal to compositional facts about mathematical objects: for some object X in (conceptual) domain D write

(4.3) $$ \begin{align} X\, \text{can be identified as}\, Y \sim Z \end{align} $$

for more restricted objects $Y, Z$ in the same domain under appropriate relation $\sim $ (this may be a cross product, direct product, set-theoretic union, etc.). It is not difficult to find such results, especially in algebraic contexts. Indeed, there are vast swathes of mathematics concerned with “structure theorems”: structure theory of countable Abelian groups, of semisimple Lie algebras, of group schemes of finite type, etc. I mention these other examples to convince my reader that the compositional facts I advert to are deeply embedded in mathematical practice, and, as such, provide a reasonable starting point for my intermediate notion of content.Footnote ¹⁰⁰

These compositional facts are not restricted to algebraic contexts.Footnote ¹⁰¹ We have seen that subsets of integers of positive density can be decomposed in such a fashion by appeal to a Structure Theorem, which expresses the dichotomy between structure and randomness.Footnote ¹⁰² Thus, according to my content proposal, Szemerédi’s theorem, simply by virtue of the fact that it involves sufficiently dense subsets of ${\mathbb {Z}}$ , has as part of its content the dichotomy between structure and randomness. Even though the theorem is not obviously about this dichotomy, as an intuitive reading or the “verbal form” of the mathematical propositionFootnote ¹⁰³ would suggest, I believe we should consider the instantiation of this dichotomy to be included in its content. However, and here is the crucial point, this structural fact about how the objects in question may be decomposed need not be (and is not) endemic to the integers or the naturals alone. One can similarly see the dichotomy at work in the ergodic setting: measure-preserving systems also exhibit this structural fact as expressed by the Furstenberg Structure Theorem. We might think of the different mathematical objects in question (sets of integers, measure-preserving systems) as multiple realizations of this same high-level structural fact.Footnote ¹⁰⁴ Thus, by appealing to structural content, we allow that intuitively different mathematical domains retain some degree of conceptual independence, facilitating various practical distinctions like purity ascriptions, but we gain a principled way to talk about surprising confluences of such domains. Both the ergodic and number-theoretic settings exhibit the structural dichotomy in question, i.e., they both encode the same sort of information (the confluence), but each context obviously involves different objects that serve to made the dichotomy precise in different ways (the independence).

A little more explicitly: the proofs of Szemerédi’s theorem ( $T_{C}$ ; Theorem 2.5) and Furstenberg Multiple Recurrence ( $T_{E}$ ; Theorem 3.3) rely on their respective Structure Theorems, the Szemerédi Regularity LemmaFootnote ¹⁰⁵ ( $S_{C}$ ; Theorem 6.1), and the Furstenberg Structure Theorem ( $S_{E}$ ; Theorem 3.5). Thus, we have a class of theorems $\mathscr {T}$ , of which $T_{C}, T_{E}$ are members, defined by the fact that all theorems in the class rely on Structure Theorems (theorems showing how a particular entity can be decomposed into a structured and random part) for their proof. The presence of Structure Theorems in these proofs then indicates that there is a general structural fact in the offing, i.e., the dichotomy between structure and randomness. And so, we have found an incredibly important higher level property of the theorems in $\mathscr {T}$ , a property that is not made explicit by the intuitive content of the theorems. Crucially, the fact that $T_{C}, T_{E} \in \mathscr {T}$ allows us to make sense of the surprising intervention of the Furstenberg Structure Theorem in the proof of Szemerédi’s theorem and makes the ergodic context suitable to prove a number theoretic result. This is because the objects manipulated in each context (subsets of integers and measure-preserving systems) can be decomposed into structured and random components.Footnote ¹⁰⁶ The fundamental dichotomy between structure and randomness allows us to make sense of the confluence of these prima facie very different domains, and its clear expression in the ergodic context will help to render the ergodic proof of Szemerédi’s theorem explanatory.

4.4 An objection and two interpretations of my view

Let me respond to a natural objection. One might think that in offering this notion of structural content I have tried to have my cake and eat it too. I have tried to provide a notion of content that retains intuitive ascriptions of purity/impurity and also explicates the intervention of impure resources. This has been done, more or less, by carving out a genus of mathematical results, a sort of mathematical natural kind if you will, under which both Szemerédi’s theorem and Furstenberg Multiple Recurrence fall.Footnote ¹⁰⁷ However, one might think that this then requires saying that the ergodic proof of Szemerédi’s theorem is pure, thereby impaling us on the first horn of the content-purity dilemma.Footnote ¹⁰⁸ This objection would be analogous to that leveled by Arana and Mancosu against proponents of formal content:Footnote ¹⁰⁹ privileging formal content “…threatens to trivialize purity, in making it the case that every theorem has a pure proof, when the content of that theorem is fully understood” ([Reference Arana and Mancosu5], p. 336). Similarly, one might say that every theorem has a pure proof once investigators have dug “deeply enough” and uncovered the requisite structural similarities. Another way of putting this objection would be to appeal to the topical content of a theorem and observe the purity metric it induces. For example, under my construal of structural content, both Szemerédi’s theorem and Furstenberg Multiple Recurrence are topically close insofar as both subsets of integers and measure-preserving systems instantiate the dichotomy between structure and randomness. This topical closeness then indicates that the ergodic resources used to prove Szemerédi’s theorem do not involve an appeal to impure techniques.

In response, I am inclined to restrict the ways in which the topical content of a theorem induces a purity constraint.Footnote ¹¹⁰ If we are interested in philosophically explicating mathematics as practiced, then the purity constraints we delineate should map closely onto the activity of mathematicians. There is a good deal of evidence that, when speaking of a “pure” proof, mathematicians are operating with an intuitive notion of content.Footnote ¹¹¹ Thus, intuitive content is what philosophers should appeal to in making claims about the purity or impurity of proofs. Nonetheless, I believe the arguments provided above support the existence of structural content. Structural content is intelligibly part of what a theorem is about precisely because the entities intuitively involved in the theorem instantiate particular structural features. However, we should block the move from the presence of structural content to a structural purity constraint because the notion of purity generated is not acknowledged by the mathematical community and, like formal content, would trivialize ascriptions of purity made in practice.

Furthermore, from a strictly conceptual perspective (independent of a methodological interest to generate philosophical theses generally consonant with mathematical practice), structural content enjoys a crucial advantage over formal content: it is able to coexist with intuitive content. If both notions were not simultaneously available to us, then we would be in no better a position than the proponent of formal content. Structural content, however, keeps the original mathematical concepts in view, whereas formal content ignores these concepts altogether by privileging the inferential role of a statement as the determinant of the statement’s content. Indeed, the ascription of structural content requires that we recognize the intuitive content of a theorem, for it is the entities intuitively recognized that instantiate the structural features of interest. We must initially acknowledge that two domains of mathematics are ostensibly unrelated but interact in surprising ways. Only then can we acknowledge and begin to uncover the “deep-lying reasons” for this interaction, reasons which are not about only one domain or the other but rather encompass both. Thus, we can retain a purity constraint generated by intuitive content: ergodic theory and combinatorics involve intuitively different concepts and movement between these domains should be considered an instance of impurity. However, these domains fall within a larger structural genus, which elucidates an important commonality between them without obliterating their intuitive differences (as is done by formal content). We can then comprehend the possibility of these domains interacting in an intelligible way given their membership in a common genus.

I have been quite cautious in my description of structural content. In particular, I have been arguing for a view that ergodic theory and combinatorics are genuinely distinct mathematical domainsFootnote ¹¹² but that particular propositions involving entities from each domain share structural content. As I said above, this has been done to honor mathematical practice and various intuitions and epistemic virtues derived from it. One way to put the point is that the more abstract structural content “follows” from our grasp of the “given” intuitive content. That is, we must grasp (in a relatively brute sense) what the theorem in question is about and only then can further structural facts be brought to light. Now, as I have repeatedly stressed, not any structural fact will do, e.g., inferential roles and the associated construal of content will be rather useless for understanding explanation and other epistemic virtues. Thus, it is instructive to think of all this in terms of conceptual distance: in order to make sense of what explanation in mathematics looks like, we cannot go “too far” past the intuitive content of a theorem (as formal content does). Nonetheless, I have claimed that we must go somewhat beyond it: explanatory facts are not often surface-level but require difficult stages of reflection and abstraction. This is quite reasonable because it is natural to think that the cognitive state we are in when we understand “the why” is of a much higher grade than that which we are in when we grasp the statement of the theorem or have a merely cogent (non-explanatory) proof.Footnote ¹¹³

However, the more metaphysically adventurous may be inclined to press a little here. If the connection between Szemerédi’s theorem and Furstenberg Multiple Recurrence is as robust as I claim, why retain the initial intuitive distinction? Why not, once we have ascended to the “reason why,” throw away the ladder? Why not remove the linguistic veil and see the world aright? I must admit that I am not entirely sure what to think here. It is unreasonable to assimilate ergodic theory and combinatorics tout court; the connective tissue given by structural content is not always present. However, perhaps all theorems expressing the dichotomy between structure and randomness are, in some very strong sense, the same thing. What would the consequences of such a view be? First, obviously, we would lose all ability to make purity/impurity ascriptions. But I would imagine the adventurous reader would be unbothered by this: purity/impurity is not the interesting thing here, and all such claims should be thrown away. Second, such a strong metaphysical assertion would ripple throughout mathematical practice in different ways, e.g., new results could be absorbed into the genus we have uncovered, intuitively distinct domains would no longer appear such, etc. But, again, I do not see why the adventurous reader would care. Ultimately, then, the preferred interpretation likely reduces to one’s view of the role of philosophy: should it be the queen of the sciences and not beholden to the practice of other disciplines? Or should it serve a more interpretive role, explicating the methods and concepts of other disciplines without upsetting the scenery too much? I leave this to the tastes of my reader.

4.5 Summary and the prospect of generalization

Let me summarize the dialectic thus far. The equivalence of Szemerédi’s theorem and Furstenberg Multiple Recurrence is surprising and may suggest that Szemerédi’s theorem has hidden higher-order content: in this case, hidden infinitary and ergodic content. That is, in some sense, Szemerédi’s theorem is about both subsets of integers and infinitary measure-preserving systems. However, a consequence of this view is that we must call the ergodic proof pure. In order to better understand whether some version of this “hidden” content view could be made intelligible, I examined Arana and Mancosu’s discussion of intuitive and formal content. We saw that the notion of formal content operative in other discussions of hidden higher-order content (Isaacson and Hallett) is unavailable to us and agreed with the argument of [Reference Arana and Mancosu5] that intuitive content is essential for making purity ascriptions. Nonetheless, intuitive content fails to explicate the relationship between combinatorics and ergodic theory in the ergodic proof of Szemerédi’s theorem.

Thus, I have tried to excavate a third kind of mathematical content: structural content. The ultimate point of this third kind is that it occupies the middle ground between intuitive and formal. Intuitive content is important and useful in mathematical practice, yet it does not help us to make sense of surprising convergences of mathematical results; formal content is useful only in very restricted contexts and may trivialize important epistemic distinctions. Structural content, on the other hand, is slightly coarser than intuitive content but still occurs within mathematical practice. I have described it as the instantiation of particular structural facts by intuitively recognized entities that induce higher-level dependencies between theorems, linking them in a conceptual nexus that crosses over intuitively distinct domains. Of course, unrestricted appeal to any property shared by various theorems (e.g., all theorems involving prime $p=5$ ) will not be useful; this may be a case of “gerrymandering” mathematical properties. I have tried to avoid such an issue by suggesting an important class of compositional properties. In our case, it is clear that both Szemerédi’s theorem and Furstenberg Multiple Recurrence require structure theorems in their respective proofs, i.e., the instantiation of the dichotomy between structure and randomness is apparent. Thus, the ascription of structural content is reasonable. Finally, I noted that my proposal may be interpreted in either a metaphysically weak or strong sense, and if one opts for the strong reading, then much of the above discussion about “saving the appearances” of mathematical practice becomes otiose.

Let me also note that I believe my content proposal may be generalized. Of course, this will require similar analyses of theorems proved via intuitively impure techniques. I will not undertake this here but would like to mention an exemplary case consistent with my philosophical discussion: the complex analytic (impure) and arithmetical (pure) proofs of the Prime Number Theorem.Footnote ¹¹⁴ The Prime Number Theorem (PNT) asserts that $\pi (x) \sim x/\log (x)$ as $x \rightarrow \infty $ where $\pi (x)$ counts the number of primes $p \leq x$ (that is, the number of primes up to integer x is approximately $x/\log (x)$ as $x \rightarrow \infty $ ). This was independently proved by Hadamard and de la Vallée Poussin in 1896 via appeal to complex function theory (see [Reference de la Vallée Poussin14, Reference Hadamard30]). Indeed, they showed that the PNT is in some sense equivalent to the non-existence of zeroes of the Riemann zeta function $\zeta (s)$ in complex variable $s=\sigma + it$ for $\text {Re}(s)=1$ . It was long thought that an, “‘elementary’ proof of the PNT, not depending on analytical ideas remote from the problem itself,” would be desirable ([Reference Ingham33], p. 651). This was achieved, again independently, by Selberg and Erdős whose analyses were entirely elementary and arithmetical. Many of the details are not germane to our discussion here; however, it is crucial to note the following structural similarity between the complex-analytic and arithmetical proofs as brought out by Ingham’s incisive review of the Selberg and Erdős papers. Ingham extracts four analytical properties of $f:= -\zeta ^{\prime }/\zeta $ which “embody the essential analytical fact on which previous proofs of the PNT [impure, complex-analytic ones] have been based.” He goes on to note that

Arana reads this as indicating the presence of implicit complex-analytic content in explicitly arithmetical statements (see [Reference Arana, Alvarez and Arana4]). My position should, by now, be quite predictable. What we have instead is the instantiation of higher-level structural properties by complex-analytic functions and prime numbers, respectively. Selberg and Erdős eliminate essential appeal to strictly complex-analytic content and pass to these structural features. Thus, we need not relinquish the intuitive impurity of the complex-analytic proof of PNT by appeal to mysterious “hidden” content; we have instead the presence of structural content.Footnote ¹¹⁵

Finally, this discussion of content serves as a first and very important step in understanding how it is possible for impure proofs to be explanatory. The presence of structural content also helps to disarm the two conceptual reasons provided for thinking that impurity and explanation may come apart.Footnote ¹¹⁶ I believe that my notion of structural content provides one reason to think that these worries may not always be apposite. That is, the presence of structural content will help to ensure both that the intended why-question is being answered and that the data relevant to answering this question is preserved in a detour through impure resources. If one can show that particular structural facts crucial to the proof of a theorem T in context X also occur in context Y, then it is entirely reasonable to think that a proof of T in context Y will be a candidate explanatory proof. This is precisely what happens in the ergodic proof of Szemerédi’s theorem. We see the instantiation of the dichotomy between structure and randomness in both the number-theoretic and ergodic contexts but because of the greater conceptual clarity in the ergodic context, which occurs in part because the infinitary nature of the objects smooths out many inessential details, the impure proof is explanatory, while the pure proof is not. Let me now turn to this.Footnote ¹¹⁷