Pathological Periodicity, Part III: The Periodic Decomposition Problem and Vitali sets.

This is Part III of the series Pathological Periodicity. The previous installment is Part II: The Cage of Continuity; start from the beginning with Part I: Relearning the Basics.

Introduction

It has been 5 months since my last post. I did not intend for there to be such a substantial gap between installments, but a handful of things have gotten in the way of my writing. For one, the list of deeply interrelated questions vying for center stage in Pathological Periodicity has grown without bound; naturally, I ended up pursuing too many of these simultaneously, making it difficult to finish writing about any of them. On top of that, several months back I began to learn about a totally distinct topic in 3-D algebraic topology, prompted by a former professor of mine. It was perhaps a bit over-ambitious to try to handle both projects at once given my other time constraints, but oh well, I guess I can’t help but learn these things the hard way still.

Anyhow, my thoughts on what to emphasize in this series and how to organize it have naturally changed over the last few months. I had originally planned to hold off on a detailed discussion of the Periodic Decomposition Problem, which I informally introduced in Part I, until a later post. As such, I initially drafted this post as a discussion of the pathological examples promised at the end of Part II. But it now seems to me that the most interesting results and examples will be best appreciated after a formal introduction to this problem. That is what we will begin here.

Specifically, in this installment I will reproduce — albeit with a twist! — the classic, choice-dependent proof of a foundational result in the literature on the decomposition problem, which I have decided to call the Periodic Decomposition Theorem (PDT). Unlike the classic proof, however, the one here will allow us to conclude the PDT’s precise level of dependence on the Axiom of Choice (AC). We will see that over ZF, the PDT is equivalent to the existence of a selector for \(\mathbb R/(p\mathbb Z + q\mathbb Z)\) whenever \(p/q\) is irrational, i.e. a set containing a single element from each coset in the quotient. However, assuming I am interpreting some foundational theorems in descriptive set theory correctly (despite my shaky grasp of their proofs), these selectors and thus the PDT are equivalent, over ZF, to the existence of a Vitali set — a selector for \(\mathbb{R}/\mathbb{Q}\). As will be explained below, the existence of Vitali sets is one of many famous examples of a weak choice principle: a statement that follows from AC but is strictly weaker than it (and not provable in ZF).

In fact, the equivalence sharpens in a way I find wonderful. The PDT gives the necessary and sufficient condition for any function in \(\mathbb{R}^\mathbb{R}\) to decompose into a sum of any finite number of periodic summands. And yet what turns out to be equivalent to all of it (and to the existence of a Vitali set) is the existence of just one single decomposition of one single function: writing \(\operatorname{Id}(x) = x\) as the sum of a function with period \(1\) and a function with period \(\sqrt{2}\).

Let me begin with some basic background on the periodic decomposition problem, and formally state the PDT. In the next section, I will be borrowing from a survey of this problem by the Hungarian mathematicians Bálint Farkas and Szilárd Gy. Révész.¹ Let’s jump in.

Remark. Before we begin: this post builds directly on the terminology and notation set up earlier in the series. In particular I will write \(P_f\) for the period module of \(f\) — the group of all of its periods — and \(\Delta_p\) for the difference operator \(\Delta_p f(x) := f(x+p) - f(x)\). Both are introduced in Part II: The Cage of Continuity, along with the basic facts about period modules that I will use without comment. If anything below looks unfamiliar, that is the place to look.

The Periodic Decomposition Problem

The periodic decomposition problem begins with the observation that if a function \(f: \mathbb{R}\to \mathbb{R}\) can be written as

\[f = f_1+\cdots +f_n, \tag{1}\]

where each \(f_i\) is periodic and has a period \(p_i\), then we must have

\[\Delta_{p_1}\cdots \Delta_{p_n} f = 0. \tag{2}\]

Thus, Equation 2 is a necessary condition for \(f\) to be decomposable in this manner. The decomposition problem, which goes back at least to the 1970s in Hungary, consists of determining when the implication can be reversed.² This is a nice generalization of the fact that a function is periodic with period \(p\) if and only if \(\Delta_p f = 0\).

It will help to have a name for the thing being asked about. I will say that \(f\) admits a \((p_1, \ldots, p_n)\)-decomposition if it can be written as in Equation 1 with \(p_i \in P_{f_i}\) for each \(i\). Note that nothing in this definition requires the \(p_i\) to be incommensurable (i.e. \(p_i/p_j\not\in \mathbb Q\)), nor the summands to be anything more than periodic. Finer distinctions along these lines will matter in the next post; here the plain notion is all we need.

Notice that the identity \(\operatorname{Id}(x) = x\) always satisfies Equation 2 (for \(n\geq 2\)) no matter which \(p_i\) we choose. But if the \(p_i\) are all commensurable,³ the intersection \(\bigcap_i p_i\mathbb{Z}\) contains some nonzero number \(p\). This means it cannot be the case that \(\operatorname{Id}\) has a decomposition of the form Equation 1, for in that case the sum on the right-hand side of Equation 1 would be periodic with period \(p\), and \(\operatorname{Id}\) has no periods other than \(0\). However, for a system of \(n\) pairwise incommensurable real numbers \(p_1,\ldots, p_n\), we do have the following theorem assuming the Axiom of Choice, which I will refer to as the Periodic Decomposition Theorem (PDT).

Theorem 1 (Periodic Decomposition Theorem) Let \(p_1,\ldots, p_n\) be pairwise incommensurable. Then a function \(f:\mathbb{R}\to\mathbb{R}\) admits a \((p_1,\ldots,p_n)\)-decomposition if and only if Equation 2 holds.

This appears to have been first proved by the Italian analysts Stefano Mortola and Roberto Peirone in 1999 (20+ years after the decomposition problem was first posed), and has been the point of departure for much work on this problem since then.⁴

Mortola and Peirone tackle the problem assuming the existence of a basis for \(\mathbb{R}\) as a \(\mathbb{Q}\)-vector space — a Hamel basis. Later we will see that this is one of the famous weak choice principles, sitting, in terms of deductive strength, between the existence of a Vitali set and the existence of a well-ordering of the reals.

The motivating insight is that, granted such a basis, it is easy to decompose \(\operatorname{Id}\) into a sum of two periodic functions. Write \(B = \{b_\alpha\}_{\alpha\in A}\) for the basis, so that every real \(x\) has a unique expansion

\[x = \sum_{\alpha\in A} x_\alpha\, b_\alpha, \qquad x_\alpha\in\mathbb{Q},\]

with all but finitely many \(x_\alpha\) equal to zero. Pick two distinct indices \(\alpha_1\neq\alpha_2\) and split the expansion in two:

\[f_1(x) := x_{\alpha_1} b_{\alpha_1}, \qquad\qquad f_2(x) := \sum_{\alpha\neq\alpha_1} x_\alpha\, b_\alpha.\]

Adding \(b_{\alpha_1}\) to \(x\) bumps the coordinate \(x_{\alpha_1}\) by one and leaves every other coordinate alone, so \(f_2\) does not notice: \(b_{\alpha_1}\in P_{f_2}\). Adding \(b_{\alpha_2}\) leaves \(x_{\alpha_1}\) alone, so \(b_{\alpha_2}\in P_{f_1}\). And of course \(f_1+f_2 = \operatorname{Id}\). So \(\operatorname{Id}\), a function with no nonzero period whatsoever, is the sum of two periodic functions.

Mortola and Peirone realized this could be pushed a great deal further: a more sophisticated version of the same Hamel-basis maneuver decomposes not just \(\operatorname{Id}\), but any \(f\) satisfying Equation 2 for any system of \(n\) pairwise-incommensurable periods \(p_1,\ldots p_n\). All of the work is concentrated into a single lemma:

Lemma 1 (Mortola–Peirone) Let \(p, q\) be incommensurable, and let \(g:\mathbb{R}\to\mathbb{R}\) be \(p\)-periodic. Then there exists a \(p\)-periodic \(f:\mathbb{R}\to\mathbb{R}\) such that \(\Delta_q f = g\).

Said differently: the operator \(\Delta_q\), restricted to the space of \(p\)-periodic functions, maps that space onto itself. After we discuss some set-theoretic preliminaries, we will give a proof that closely resembles theirs but replaces the Hamel basis with a weaker assumption that ends up being equivalent to the existence of a Vitali set.

For now, let’s proceed to the proof of the PDT that follows once the lemma is in hand.

Proof. Necessity is the observation we opened with, so only sufficiency is at issue. We argue by induction on \(n\).

For \(n=1\), the hypothesis \(\Delta_{p_1}f = 0\) says exactly that \(f\) is \(p_1\)-periodic, so \(f = f_1\) is already a decomposition.

Suppose the theorem holds for \(n\), and let \(p_1,\ldots,p_{n+1}\) be pairwise incommensurable with \(\Delta_{p_1}\cdots\Delta_{p_{n+1}}f = 0\). Since difference operators commute, we may read this as \[\Delta_{p_1}\cdots\Delta_{p_n}\big(\Delta_{p_{n+1}}f\big) = 0,\] so the inductive hypothesis applies to the function \(\Delta_{p_{n+1}}f\): there are \(g_1,\ldots,g_n\) with \(p_i\in P_{g_i}\) and \[\Delta_{p_{n+1}}f = g_1+\cdots+g_n.\] Each \(g_i\) is \(p_i\)-periodic, and \(p_{n+1}\) is incommensurable with \(p_i\), so Lemma 1 applies to the pair \((p_i, p_{n+1})\): there is a \(p_i\)-periodic \(f_i\) with \(\Delta_{p_{n+1}}f_i = g_i\). Put \(h := f_1+\cdots+f_n\). Since \(\Delta_{p_{n+1}}\) is linear, \[\Delta_{p_{n+1}}h = \sum_{i=1}^{n} \Delta_{p_{n+1}}f_i = \sum_{i=1}^{n} g_i = \Delta_{p_{n+1}}f,\] and therefore \(\Delta_{p_{n+1}}(f-h) = 0\). That is, \(f_{n+1} := f - h\) is \(p_{n+1}\)-periodic, and \[f = h + f_{n+1} = f_1+\cdots+f_n+f_{n+1}\] is a decomposition of the required form.

That is the entire proof. What makes it go is that Lemma 1 lets us lift a decomposition of \(\Delta_{p_{n+1}}f\) to a decomposition of \(f\) itself, one summand at a time.

Needless to say, I was very excited to find Mortola and Peirone’s paper. Months ago I tried to prove the PDT by exactly this induction, but I got as far as reducing the whole problem to the need for Lemma 1 and then simply could not produce it. I knew Mortola and Peirone had proved it and I suspected they probably did so via a similar route, but somehow I failed to find a pdf of their paper at the time. As such, an earlier draft of this post contained proofs of weaker versions of the PDT that I was able to prove on my own. Those I could show were equivalent to existence of a Vitali set, but I was very dissatisfied not being able to say for sure whether the PDT in general was. So I am quite happy to have finally found a copy of the paper, even though it forced me to rewrite a good chunk of this post.

And the rewrite was well worth it, for the following reason. Notice where the Axiom of Choice appears in the induction argument above: nowhere! It is pure ZF. All of the choice consumed by the PDT is consumed inside Lemma 1. So the question of how much choice the PDT needs reduces entirely to the question of how much choice that one lemma needs. To make sense of this, let’s review some set theory.

A little set theory

For the last 100 years, set theory has acted as the de facto foundation for most of mathematics. The majority of mathematicians use set theory fairly informally; they know set theorists have worked out all kinds of axiomatic systems to justify their manipulations with sets, and that the system called “Zermelo–Fraenkel Set Theory with the Axiom of Choice (ZFC)” in particular seems to work well for most of their purposes. But they often don’t concern themselves too much with the details of these axioms. In these posts, we will still use set theory relatively informally, but we will concern ourselves heavily with the exact dependence of statements on the Axiom of Choice.

Recall that the Axiom of Choice (AC) states that given any family of nonempty sets \(\mathscr F\), there exists a choice function or selector \(S\) on \(\mathscr F\) such that \(S(X) \in X\) for all \(X\in \mathscr F\). AC is equivalent to a great many other statements, including the Well-Ordering Theorem (every set can be well-ordered) and the assertion that every vector space has a basis.

Whenever \(\mathscr F\) is pairwise disjoint, which is the only case we will care about, notice that a choice function exists iff there exists a set \(S\) so that \(S\cap X\) contains a single element for every \(X\in\mathscr F\). Such a set is also called a selector by some, in a harmless abuse of terminology. Others call it a transversal. I will generally use selector.

AC in full generality is quite powerful, but when applied in practice you often don’t need to actually assume that literally any family as above has a choice function. You just need to assume that one exists for the kinds of family you are actually working with; or perhaps that a basis exists for the specific vector spaces you are interested in; or that a particular set can be well-ordered; etc.

If you are working with finite families of sets, you don’t even need an additional axiom. Finite choice, as it is called, can be proved from the axioms of ZF alone. Once the family is infinite, however, ZF alone no longer guarantees you a choice function. Sometimes you can still write one down by hand — if every member of the family happens to be a nonempty set of natural numbers, just take the least element of each — but in general you cannot, and asserting that you can means adding an axiom to your underlying set theory. A statement that follows from the Axiom of Choice but is neither equivalent to it nor provable in ZF is what I will call a weak choice principle. Examples include the Axiom of Countable Choice,⁵ and the Axiom of Dependent Choice (DC), which we will meet shortly. But the two principles we care about most in this series are the assertion that there exists a Vitali set (call this assertion VIT for brevity), and the assertion that there is a Hamel basis (call this HB).

Recall that a Vitali set is a selector for \(\mathbb{R}/\mathbb{Q}\), so that VIT is equivalent to the assertion that a selector exists for \(\mathbb{R}/\mathbb{Q}\). This makes it as restricted a form of AC as one could ask for: it is the single instance of AC applied to the family of cosets of \(\mathbb Q\). In addition to this, Vitali sets are famous as the quintessential (non-constructive) examples of nonmeasurable subsets of the real line.

Meanwhile HB also seems to be nearly as restrictive a form of AC as VIT. After all, AC is equivalent to the statement that every vector space has a basis, and asserting a Hamel basis cuts this down to the single vector space \(\mathbb{R}\) over \(\mathbb{Q}\).

VIT and HB, however, are not equally weak. According to recent research, they sit in a strictly ordered chain with VIT at the bottom: over ZF, granting a Hamel basis yields a Vitali set, a well-ordering of \(\mathbb{R}\) yields a Hamel basis, and of course AC yields any and all of these.

That a Hamel basis yields a Vitali set is not hard to see and has been long known. First, take your existing basis and get a new basis \(B\) containing \(1\) (replace any basis element in the expansion for \(1\) with \(1\)). Then the \(\mathbb{Q}\)-span of \(B\setminus\{1\}\) is a complementary subspace to \(\mathbb{Q}\) in \(\mathbb{R}\), and hence a selector for \(\mathbb{R}/\mathbb{Q}\).⁶ The converses are another matter entirely. That ZF + HB does not imply a well-ordering of the reals is a theorem published in 2018, and that ZF + VIT does not imply HB is proved in a 2020 book under a large-cardinal assumption, though a preprint from two months ago (June 2026!) claims this assumption can be dropped.⁷

To be clear, VIT is still stronger than what can be proved in ZF alone. The famous witness to this is the Solovay model, a model of ZF + DC in which all subsets of the real line are Lebesgue measurable, so that no Vitali set can exist in it.⁸ Saharon Shelah later built a different model of ZF + DC which likewise contains no Vitali set, and whose consistency rests on nothing beyond the consistency of ZF.⁹ So we can say with confidence that VIT is independent of ZF, provided ZF is consistent at all.

So where does this leave the PDT? As we saw, Mortola and Peirone’s argument only uses AC in Lemma 1, and does so by assuming the existence of a Hamel basis. The proof we will give in the next section needs only selectors for quotients of the form \(\mathbb{R}/(p\mathbb{Z}+q\mathbb{Z})\), for all pairs \(p, q\) with \(p/q\not\in\mathbb{Q}\). But a selector for \(\mathbb{R}/(p\mathbb{Z}+q\mathbb{Z})\) is not literally a Vitali set: \(p\mathbb{Z}+q\mathbb{Z}\) is not \(\mathbb{Q}\). So the question naturally arises: over ZF, what does the existence of a selector for a quotient by one subgroup of \(\mathbb R\) imply about the existence of one for another, and in particular for \(\mathbb{R}/\mathbb{Q}\)?

Transferability of selectors and Borel equivalence relations

It will be helpful now to recast these quotients in terms of equivalence relations. For a countable additive subgroup \(\Gamma\subset \mathbb R\), let \(E_\Gamma\) be the equivalence relation \(x E_\Gamma y \iff x-y\in \Gamma\). The equivalence classes of \(E_\Gamma\) are of course the cosets in \(\mathbb R/\Gamma\). I.e. \(\mathbb R/\Gamma = \mathbb R/ E_\Gamma\). This relation moreover is Borel and countable (every equivalence class is a countable set). Leaning on the theory of countable Borel equivalence relations, I claim the following proposition:

Proposition 1 Let \(p/q\notin\mathbb Q\) and let \(G = p\mathbb Z + q\mathbb Z\). Over ZF, a selector for \(\mathbb{R}/G\) exists if and only if a selector for \(\mathbb{R}/\mathbb{Q}\) exists.

This may look trivial, but the “over ZF” has made it actually quite challenging to prove; the naive proof one is tempted to try uses a lot of choice. And unfortunately, there does not seem to be any published work stating this proposition exactly. Nonetheless I am convinced that, at worst, Proposition 1 is a special case of well-established, if highly technical, results in descriptive set theory that are choice-free at least when applied to this specific statement. At best, I might be able to sidestep the heavy machinery to give a more elementary (if still non-obvious) proof inspired by one I found from 1975 that shows you can “transfer” selectors in the case of \(\mathbb R/\mathbb Q\) and \(\mathcal P (\omega)/\textnormal{fin}\).

Tracing the relevant literature, the extent to which it uses AC, and attempting an elementary proof has turned into a separate post I am writing and hoping to publish soon. For now, I will give an extremely condensed preview of the literature that justifies asserting Proposition 1, leaving all definitions and detailed citations for the later post.

Again let \(G = p\mathbb Z + q\mathbb Z\). Then the countable Borel relations \(E_G\) and \(E_\mathbb Q\) are both examples in ZF of hyperfinite, nonsmooth equivalence relations; though showing hyperfiniteness for \(E_G\) is less straightforward than for \(E_\mathbb{Q}\). One of the classic theorems in descriptive set theory is that any two countable hyperfinite, nonsmooth relations are bi-embeddable (see this paper). In turn, for any countable subgroups \(\Gamma_1, \Gamma_2 \subset \mathbb R\), ZF proves that if \(E_{\Gamma_1}\) and \(E_{\Gamma_2}\) are bi-embeddable, then a selector for one exists iff a selector for the other exists. This last assertion is the one relatively easy thing here to prove outright in ZF: given an injection \(\varphi:\Gamma_1\to\Gamma_2\) such that \(xE_{\Gamma_1}y\iff \varphi(x)E_{\Gamma_2}\varphi(y)\) and a selector for \(\mathbb{R}/\Gamma_2\), one can write down a selector for \(\mathbb{R}/\Gamma_1\) by an explicit formula, using a fixed enumeration of \(\Gamma_2\) to pick canonical representatives. I will give the construction in the follow-up post.

Unfortunately, it seems descriptive set theorists generally work in ZFC without paying too much attention to how much choice they do or do not use; theorems like the one on bi-embeddability were not proved with our need for choiceless results in mind. So far, the results we need seem choiceless when applied to our context, though I am still verifying this. But luckily for us, prominent set theorists Paul Larson and Jindřich Zapletal pay very careful attention to usage of choice principles, and in Discontinuous homomorphisms, selectors, and automorphisms of the complex field (in ZF) (2020), they cite the bi-embeddability theorem in asserting that a Vitali selector exists iff one exists for \(\mathcal P(\omega)/\textnormal{fin}\), all while working entirely in ZF. So for now, we will proceed assuming the relevant machinery does indeed imply Proposition 1 holds without recourse to AC.

The PDT and the existence of a Vitali set

Now we can tackle the main result of this post:

Theorem 2 (The PDT, Vitali sets, and a single decomposition) Over ZF, the following three statements are equivalent:

1. \(\operatorname{Id}\) admits a \((1, \sqrt{2})\)-decomposition;
2. there exists a Vitali set;
3. the Periodic Decomposition Theorem (Theorem 1) holds.

To prove this, we first need a proof of Lemma 1 that gets by with a selector for \(\mathbb R/G\), as opposed to a Hamel basis. Thankfully, it turns out to be pretty easy to replace a Hamel basis with such a selector without altering their proof too much. ¹⁰ In the following, we assume the existence of this selector.

Proof. Let \(G := p\mathbb{Z}+q\mathbb{Z}\). Because \(p/q\notin\mathbb{Q}\), this sum is direct: every element of \(G\) is \(mp+nq\) for a unique pair of integers \((m,n)\). Assuming there is a selector \(S\) for \(\mathbb{R}/G\), for each \(x\in\mathbb{R}\) let \(y_x\in S\cap (x+G)\) be the unique representative of \(x\), so that \[x = y_x + m(x)\,p + n(x)\,q\] with \(m(x), n(x)\in\mathbb{Z}\) uniquely determined by \(x\). Note that translating by \(q\) does not change the coset, and so \[y_{x+q} = y_x, \qquad m(x+q) = m(x), \qquad n(x+q) = n(x)+1,\] while translating by \(p\) leaves both \(y_x\) and \(n(x)\) alone.

Now define \(f:\mathbb{R}\to\mathbb{R}\) coset by coset, as follows:

\[f(x) := \begin{cases} \sum_{k=0}^{n(x)-1} g(y_x + kq) & \text{if } n(x) > 0, \\ 0 & \text{if } n(x) = 0, \\ -\sum_{k=n(x)}^{-1} g(y_x + kq) & \text{if } n(x) < 0. \end{cases} \tag{3}\]

\(f\) is \(p\)-periodic. The right-hand side of Equation 3 depends on \(x\) only through \(y_x\) and \(n(x)\), and translating by \(p\) changes neither. So \(f(x+p) = f(x)\).

\(\Delta_q f = g\). Fix a coset representative \(y\), and write \(F(n)\) for the value Equation 3 assigns to a point with \(y_x = y\) and \(n(x) = n\). I claim that \[F(n+1) - F(n) = g(y+nq) \qquad\text{for every } n\in\mathbb{Z}. \tag{4}\] For \(n\geq 1\) the two sums differ by the single term \(k = n\); for \(n=0\) we get \(F(1)-F(0) = g(y) - 0\); for \(n = -1\) we get \(F(0)-F(-1) = 0 + g(y-q)\); and for \(n\leq -2\) the two sums again differ by the single term \(k=n\). So Equation 4 holds in every case, including at the two seams where the definition changes form.

Now take any \(x\) and write \(y = y_x\), \(n = n(x)\). Since \(y_{x+q} = y\) and \(n(x+q) = n+1\), \[\Delta_q f(x) = f(x+q) - f(x) = F(n+1) - F(n) = g(y+nq).\] Finally, \(g\) is \(p\)-periodic, so \(g(y + nq) = g(y + m(x)p + nq) = g(x)\). Hence \(\Delta_q f = g\), as required.

Putting now our proofs of Lemma 1 and Theorem 1 together with Proposition 1:

Proposition 2 Over ZF, VIT implies the PDT.

For the reverse direction, let me first explain the thought process that led me there. Before I knew whether any of this was true, it was evident that the PDT does imply the existence of nonmeasurable (though not necessarily Vitali) sets, and is thus independent of ZF, per Solovay. This follows because \(\operatorname{Id}\) (and in fact any \(f\) with \(\lim_{x\to \infty} f(x) = \infty\)) cannot have a measurable decomposition (see the survey by Farkas and Révész), yet must have a decomposition in ZF + PDT. This suggested to me that a possible way to prove the converse is to show that a decomposition of \(\operatorname{Id}\) must itself induce a Vitali-type set. I thought that maybe one of the nonmeasurable pre-images of a summand in the decomposition must actually be such a Vitali-type set.

But I was stuck on how to prove this, and I was not sure if it was even true. So I set this down for a few months while I worked on other questions. It turns out that I was most of the way there. The function \(\operatorname{Id}\) is in fact the correct one to consider, and the easiest selector to find is a particular intersection of the pre-images of the summands.

The key is to see that if \(x = f(x) + g(x)\) is a \((p,q)\)-decomposition of \(\operatorname{Id}\), then \(f(x + nq) = f(x) + nq\) and \(g(x+mp) = g(x) + mp\), and thus \(f(x)\in [0, q)\) and \(g(x)\in [0, p)\) can occur only once per coset. To put this more formally:

Lemma 2 Suppose \(p, q > 0\) with \(p/q\not\in \mathbb{Q}\), and suppose \(\operatorname{Id}\) admits a \((p, q)\)-decomposition, \(\operatorname{Id} = f + g\) with \(p\in P_f\) and \(q\in P_g\). Then the set \[S := \{x\in \mathbb{R}: \lfloor f(x)/q \rfloor = 0 = \lfloor g(x)/p \rfloor \} \tag{5}\] is a selector for \(\mathbb{R}/(p\mathbb{Z} + q\mathbb{Z})\).

Proof. Since \(\operatorname{Id} = f+g\) and \(nq\in P_g\) for every \(n\in\mathbb{Z}\),

\[f(x+nq) = (x+nq) - g(x+nq) = (x+nq) - g(x) = f(x) + nq,\]

and symmetrically \(g(x+mp) = g(x)+mp\) for every \(m\in\mathbb{Z}\), using \(mp\in P_f\).

Let \(x\in \mathbb{R}\). Then \(f(x) = nq + t\) for some \(n\in \mathbb{Z}\) and \(t\in [0, q)\), where \(n\) may be zero. This means \(x - nq\) is in the same coset as \(x\), and \(f(x-nq) = f(x) - nq = t\in [0, q)\). Similarly, \(g(x) = mp + s\) for some \(m\in \mathbb{Z}\) and \(s\in [0, p)\), and thus \(x - mp\) is in the same coset as \(x\), and \(g(x-mp) = g(x) - mp = s\in [0, p)\). Let \(y = x - nq - mp\). Then \(y\) is in the same coset as \(x\), and, since \(p\in P_f\) and \(q\in P_g\), we have \(f(y) = f(x-nq) = t\in [0, q)\) and \(g(y) = g(x-mp) = s\in [0, p)\). Thus \(y\in S\). In other words, each coset intersects \(S\) at least once.

Now we observe that this \(y\) must be unique. Let \(y_1, y_2\in S\) be in the same coset. Then \(y_1 - y_2 = mp + nq\) for some \(m, n\in \mathbb{Z}\). But then \(f(y_1) - f(y_2) = nq\) and \(g(y_1) - g(y_2) = mp\). Since \(f(y_i)\in [0, q)\) and \(g(y_i)\in [0, p)\), we must have \(n = m = 0\), and thus \(y_1 = y_2\). Therefore, each coset intersects \(S\) at most once. This finishes the proof that \(S\) is a selector for \(\mathbb{R}/(p\mathbb{Z} + q\mathbb{Z})\).

A perfectly simple, elementary proof that eluded me for months! And with it we can close the circle and prove Theorem 2:

Proof. (1) \(\Rightarrow\) (2). Given \(\operatorname{Id} = f+g\) with \(1\in P_f\) and \(\sqrt{2}\in P_g\), Lemma 2 turns the decomposition into a selector for \(\mathbb{R}/(\mathbb{Z}+\sqrt{2}\,\mathbb{Z})\), and Proposition 1 turns that selector into a Vitali set.

(2) \(\Rightarrow\) (3). This is Proposition 2.

(3) \(\Rightarrow\) (1). Immediate: as we observed at the outset, \(\Delta_1\Delta_{\sqrt{2}}\operatorname{Id} = 0\), and \(1/\sqrt{2}\notin\mathbb{Q}\), so the PDT applies to \(\operatorname{Id}\) with this pair.

The argument runs verbatim for any positive, incommensurable \(p\) and \(q\), not just with \(1\) and \(\sqrt{2}\), but this is a particularly “cute” pair to use. After all, the term “incommensurable” comes from the Latin translation for the Greek asúmmetros which Euclid used for pairs of lengths with irrational ratios, and the first such pair they discovered was the diagonal and side of a unit square. Anyhow, all of these single-pair statements — that \(\operatorname{Id}\) has a \((1,\sqrt{2})\)-decomposition, that it has a \((1,\pi)\)-decomposition, that it has a \((\sqrt{3},\sqrt{5})\)-decomposition — are equivalent to one another, and each of them is equivalent to the PDT in full.

To me, this is pretty neat. Statement (3) quantifies over every real function and every finite system of periods while statement (1) asks for a single decomposition of a single specific function along a single specific pair of numbers. You wouldn’t necessarily expect these two statements to be equivalent to each other and to a famous weak choice principle.

But this is only the beginning. There are many possible variations of the PDT that can be considered by altering the conditions on the summands in the decomposition. We could also generalize beyond periodicity by considering operators \(T:A\to A\) on arbitrary sets and \(T\)-invariance of functions \(f:A\to \mathbb{R}\) defined by \(f(Tx) = f(x)\); this is actually the route taken by Farkas and Révész in the 2007 paper mentioned above, where the PDT falls out as a corollary of a more general “invariant decomposition” theorem.¹¹ In each such variation or generalization, we can ask what choice principles the resulting decomposition theorems require or are equivalent to. I’ll be writing more about this in the future.

Conclusion

Here is why we should care about all this: AC is very powerful when it comes to proving that things exist. Indeed, in some ways, it is a little too powerful: AC together with the rest of ZF can be used to assert the existence of objects that are impossible to explicitly construct, and some of these are very bizarre (as Pathological Periodicity will attest to). This seems to be one of many factors that push a (fairly small) minority of mathematicians to reject ZFC as an axiom system.

I don’t think it is necessary to reject ZFC outright. I do think however that figuring out precisely how much various proofs throughout “standard” mathematics depend on AC and on weaker choice principles is in and of itself highly interesting and worthwhile mathematics. Doing so gives us a more accurate picture of the spectrum of deductive strength held by results that are provable in ZFC, and of how far the objects ZFC proves as exist sit from anything you could explicitly construct.

Philosophically, I think this matters because, even if you accept the existence of mathematical objects that cannot be explicitly constructed, such objects come with domains of applicability that differ considerably from others. Grant a Hamel basis, for instance, and there exist \(\mathbb{Q}\)-linear functions \(\mathbb{R}\to\mathbb{R}\) that fail to be \(\mathbb{R}\)-linear. These are quite pathological: they are nowhere continuous, their graphs are dense in the plane, and they are nonmeasurable. But you will never write one down, never evaluate one at a point, never compute anything with one. Nor will you do so with the summands of any periodic decomposition of \(\operatorname{Id}(x)\). Their existence is a fact about what ZFC can prove that is beyond the reach of ZF, not a fact you can put to work to model the motion of a ball or the behavior of a quantum system. Locating a theorem on the spectrum above means knowing, for that theorem, roughly how much it depends on objects whose relationship to the rest of material reality is distinctly indirect.

A good chunk of Pathological Periodicity will be about parsing out this spectrum specifically within the literature on the Periodic Decomposition Problem. Today, we got a nice start by pinning down the PDT exactly. Throughout the rest of the series, we will seek to pin down the deductive strength of other variants of the PDT, as well as that of some of the highly pathological phenomena that arise amongst functions admitting a periodic decomposition.¹²

← Previously: Part II: The Cage of Continuity

Footnotes

1. B. Farkas and Sz. Gy. Révész, The periodic decomposition problem (2015).

2. Farkas and Révész credit the question to Imre Z. Ruzsa, who posed it in the 1970s; it is Problem 1.1 in their survey, and the survey itself is dedicated to him on the occasion of his 60th birthday. Ruzsa is best known as a number theorist, which makes it all the more interesting that he seems to have set a generation of Hungarian analysts to work on this problem. Beyond posing the question, his most important direct contribution seems to be the joint paper Periodic decomposition of integer valued functions, with G. Károlyi, T. Keleti and G. Kós.

3. A reminder from Part II, since the word does double duty in this series. Two nonzero real numbers \(p\) and \(q\) are commensurable if \(p/q\in\mathbb{Q}\) — equivalently, if some nonzero integer multiple of one equals an integer multiple of the other, so that \(p\mathbb{Z}\cap q\mathbb{Z}\neq\{0\}\) — and incommensurable otherwise. Two periodic functions \(f\) and \(g\) are incommensurable if they share no period other than \(0\), that is, if \(P_f\cap P_g = \{0\}\), and commensurable otherwise. The two notions are related but not interchangeable: if \(f\) and \(g\) are incommensurable functions, then any nonzero period of one is incommensurable with any nonzero period of the other. Knowing that any one period of \(f\) is incommensurable with a period of \(g\) however does not allow you to conclude the functions are incommensurable.

4. S. Mortola and R. Peirone, The sum of periodic functions (1999). The survey attributes Corollary 6.3 jointly to them and to a two-author paper of Farkas and Révész, Decomposition as the sum of invariant functions with respect to commuting transformations (2007). The two lines of argument appear to have been arrived at independently, though they seem to rely on similar induction and “lifting” arguments. Farkas and Révész, however, work in a much more general setting with arbitrary commuting transformations. See also footnote 11.

5. Remarkably there is a model of ZF called the Feferman–Lévy model in which \(\mathbb{R}\) is both uncountable and yet a countable union of countable sets, leading the Axiom of Countable Choice (AC\(_\omega\)) to fail (hence it is independent of ZF). There are plenty of models of ZF+DC where AC fails as discussed below, and there is also a model of ZF + AC\(_\omega\) where DC fails. Proofs of all this, which go well over my head at the moment, can be found in The Axiom of Choice (1973) by Thomas Jech.

6. In general, if \(V= W\oplus U\) (i.e. \(W\) and \(U\) are complementary subspaces of \(V\)), then every coset of \(W\) meets \(U\) at exactly one point, and \(U\) is therefore a selector for \(V/W\).

7. That VIT does not imply a Hamel basis is proved by Larson and Zapletal in their book Geometric Set Theory (2020), assuming consistency of an inaccessible cardinal; Larson and Shelah claim, in their 2026 preprint Discontinuous homomorphisms without Hamel bases, that this assumption can be removed. That the existence of a Hamel basis does not imply a well-ordering of \(\mathbb{R}\) is the main result of M. Beriashvili, R. Schindler, L. Wu and L. Yu, Hamel bases and well-ordering the continuum (2018).

8. R. M. Solovay, A model of set-theory in which every set of reals is Lebesgue measurable (1970).

9. S. Shelah, Can you take Solovay’s inaccessible away? (1984). Shelah proves ZF + DC + “every set of reals is Lebesgue measurable” is equiconsistent with ZFC + “there exists an inaccessible cardinal”, meaning that Solovay’s extra hypothesis genuinely cannot be dropped. On the other hand, ZF + DC + “every set of reals has the Baire property” is equiconsistent with ZF alone. This second model is the most relevant for this post since we only need a model of ZF containing no Vitali sets, which can never have the Baire property. To be clear, I have not studied this paper or Solovay’s, and the subtleties around inaccessible cardinals and the forcing constructions used to build these models are well beyond what I currently understand. I am relying on the standard statements of these results as they are reported in the literature, and if I have misrepresented them the fault is mine. A similar caveat applies to Larson–Zapletal and the other recent set-theoretic papers I cite, though I have begun diving into some of the papers on Borel equivalence relations a bit more than Solovay/Shelah.

10. The idea of using a selector for such a quotient is inspired by the way Farkas and Révész use one in Proposition 1.3 of their survey, which gives the proof of the PDT in the special case of a decomposition into two summands. See also the next footnote.

11. I.e., the 2007 paper cited above. I still need to fully digest this paper, but from what I understand so far it seems their overall strategy is a generalization the one we employ here in adapting Mortola and Peirone. In particular, their Lemma 11 is analogous to Lemma 1; they work with transformations \(S, T\) and show that for \(S\)-invariant \(g\), there exists an \(S\)-invariant \(f\) such that \(\Delta_T f = g\). They prove this by invoking selectors for \(\tilde A : = A/\sim_S\) and \(\tilde A/\sim_T\), where \(\sim_S\) is the equivalence class \(x\sim_S y \iff S^nx = S^my\) for some integers \(m,n\), and similarly for \(\sim_T\). And then in their theorem 15, they perform a similar “lift” using Lemma 11 during an induction. It seems that in full generality, their results really do need the full power of AC, given that they take \(A\) to be an arbitrary set.

12. As a little preview: assuming a selector for a particular quotient of \(\mathbb R\) involving an uncountable subgroup, there exist whole vector subspaces of \(\mathbb{R}^\mathbb{R}\) consisting entirely of periodic functions, and yet generated by 2 or more pairwise incommensurable functions (this answers Question 4 of Part I). It is unclear to me as of yet where the existence of this selector sits among the weak choice principles relative to VIT, and whether the existence of such subspaces implies the existence of the selector. The two-dimensional case is prototypical. It already takes a bit of creativity to find incommensurable periodic \(f\) and \(g\) with periodic sum; ensuring \(\alpha f + \beta g\) is periodic for every single \((\alpha, \beta)\in \mathbb{R}^2\) is considerably harder, and is what requires more choice than is available in ZF. The first post I write on this will probably confine itself to the two-dimensional case over \(\mathbb{R}\). I have been working on pushing it further — to more general function spaces over other fields, and possibly to an uncountable-dimensional subspace of \(\mathbb{R}^{\mathbb{R}}\) with the same property — but I am still working out the details.